| | This Article | | | |
| | | | Share | | | |
| | | | Bibliographic References | | | |
| | | | Add to: | | | |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| | | | Search | | | |
| | | | |
A Robust Competitive Clustering Algorithm With Applications in Computer Vision
May 1999 (vol. 21 no. 5) pp. 450-465
Abstract—This paper addresses three major issues associated with conventional partitional clustering, namely, sensitivity to initialization, difficulty in determining the number of clusters, and sensitivity to noise and outliers. The proposed Robust Competitive Agglomeration (RCA) algorithm starts with a large number of clusters to reduce the sensitivity to initialization, and determines the actual number of clusters by a process of competitive agglomeration. Noise immunity is achieved by incorporating concepts from robust statistics into the algorithm. RCA assigns two different sets of weights for each data point: the first set of constrained weights represents degrees of sharing, and is used to create a competitive environment and to generate a fuzzy partition of the data set. The second set corresponds to robust weights, and is used to obtain robust estimates of the cluster prototypes. By choosing an appropriate distance measure in the objective function, RCA can be used to find an unknown number of clusters of various shapes in noisy data sets, as well as to fit an unknown number of parametric models simultaneously. Several examples, such as clustering/mixture decomposition, line/plane fitting, segmentation of range images, and estimation of motion parameters of multiple objects, are shown. [1] J. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum, 1981.
[2] J.C. Bezdek and N.R. Pal, “Some New Indexes of Cluster Validity,” IEEE Trans. Systems, Man, and Cybernetics—Part B, vol. 28, no. 3, pp. 301-315, 1998.
[3] L. Bobrowski and J.C. Bezdek, "C-Means Clustering With the l1and l∞Norms," IEEE Trans. Systems, Man and Cybernetics, vol. 21, no. 3, pp. 545-554, 1991.
[4] Y. Choi and R. Krishnapuram, "Fuzzy and Robust Formulations of Maximum-Likelihood-Based Gaussian Mixture Decomposition," Proc. Int'l Conf. Fuzzy Systems, pp. 1,899-1,905,New Orleans, Sept. 1996.
[5] T. Darrell and A. Pentland, "Cooperative Robust Estimation Using Layers of Support," Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 474-487, May 1995.
[6] R.N. Davé, "Use of the Adaptive Fuzzy Clustering Algorithm to Detect Lines in Digital Images," Intelligent Robots and Computer Vision VIII, vol. 1,192, pp. 600-611, 1989.
[7] R. Dave, Characterization and Detection of Noise in Clustering Pattern Recognition Letters, vol. 12, pp. 657-664, 1991.
[8] R.N. Davé and K. Bhaswan, "Adaptive Fuzzy C-Shells Clustering and Detection of Ellipses," IEEE Trans. Neural Networks, vol. 3, no. 5, pp. 643-662, May 1992.
[9] R.N. Dave and R. Krishnapuram, Robust Clustering Methods: A Unified View IEEE Trans. Fuzzy Systems, vol. 5, pp. 270-293, 1997.
[10] R.N. Davé and K.J. Patel, "Progressive Fuzzy Clustering Algorithms Characteristic Shape Recognition," North Amer. Fuzzy Information Processing Soc., pp. 121-124,Toronto, 1990.
[11] D. Dubois and H. Prade, Possibility Theory: An Approach to Computerized Processing of Uncertainty.New York: Plenum Press, 1988.
[12] H. Frigui and R. Krishnapuram, "A Robust Clustering Algorithm Based on M-Estimator," Proc. First Int'l Conf. Neural, Parallel and Scientific Computations, vol. 1, pp. 163-166,Atlanta, May 1995.
[13] H. Frigui and R. Krishnapuram, “A Comparison of Fuzzy Shell-Clustering Methods for the Detection of Ellipses,” IEEE Trans. Fuzzy Systems, vol. 4, no. 2, pp. 193-199, May 1996.
[14] H. Frigui and R. Krishnapuram, "A Robust Clustering Algorithm Based on Competitive Agglomeration and Soft Rejection of Outliers," Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 550- 555,San Francisco, 1996.
[15] H. Frigui and R. Krishnapuram, "Clustering by Competitive Agglomeration," Pattern Recognition, vol. 30, no. 7, pp. 1,223-1,232, 1997.
[16] I. Gath and A.B. Geva, Unsupervised Optimal Fuzzy Clustering IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 773-781, 1989.
[17] E.E. Gustafson and W.C. Kessel, "Fuzzy Clustering With a Fuzzy Matrix," IEEE CDC, pp. 761-766,San Diego, Calif., 1979.
[18] F.R. Hampel, E.M. Ronchetti, P.J. Rousseeuw, and W.A. Stahel, Robust Statistics: The Approach Based on Influence Functions.New York: John Wiley&Sons, 1986.
[19] D.C. Hoaglin, F. Mosteller, and J.W. Tukey, Understanding Robust and Exploratory Data Analysis.New York: John Wiley&Sons, 1983.
[20] A. Hoover, G. Jean-Baptiste, X. Jiang, P.J. Flynn, H. Bunke, D. Goldgof, K. Bowyer, D. Eggert, A. Fitzgibbon, and R. Fisher, “An Experimental Comparison of Range Segmentation Algorithms,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol 18, no. 7, pp. 673-689, July 1996.
[21] Y. Huang, K. Palaniappan, X. Zhuang, and J.E. Cavanaugh, "Optic Flow Field Segmentation and Motion Estimation Using a Robust Genetic Partitioning Algorithm," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 12, pp. 1,177-1,190, Dec. 1995.
[22] P.J. Huber, Robust Statistics.New York: John Wiley&Sons, 1981.
[23] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
[24] J. Jolion,P. Meer,, and S. Bataouche,“Robust clustering with applications in computer vision,” IEEE Trans. Pattern Analysis amd Machine Intelligence, vol. 13, no. 8, pp. 791-801, Aug. 1991.
[25] L. Kaufman and P.J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis.New York: Wiley Interscience, 1990.
[26] P.R. Kersten, "The Fuzzy Median and the Fuzzy Mad," Proc. ISUMA/NAFIPS, pp. 85-88,College Park, Md., Sept. 1995.
[27] J. Kim, R. Krishnapuram, and R.N. Dave, "On Robustifying the C-Means Algorithms," Proc. ISUMA/NAFIPS, pp. 630-635,College Park, Md., 1995.
[28] R. Krishnapuram and C.P. Freg, "Fitting an Unknown Number of Lines and Planes Image Data Through Compatible Cluster Merging," Pattern Recognition, vol. 25, no. 4, pp. 385-400, 1992.
[29] R. Krishnapuram, H. Frigui, and O. Nasraoui, Fuzzy and Possibilistic Shell Clustering Algorithm and Their Application to Boundary Detection and Surface Approximation IEEE Trans. Fuzzy Systems, vol. 3 pp. 29-60, 1995.
[30] R. Krishnapuram and J.M. Keller, “A Possibilistic Approach to Clustering,” IEEE Fuzzy Systems, vol. 1, no. 2, pp. 98-110, 1993.
[31] R. Krishnapuram and J. Keller, "Fuzzy and Possibilistic Clustering Methods for Computer Vision," S. Mitra, M. Gupta, and W. Kraske, eds., Neural and Fuzzy Systems, vol. IS12, pp. 135-159. SPIE Institute Series, 1994.
[32] Y. Liu and T.S. Huang, "A Sequence of Stereo Image Data of a Moving Vehicle in an Outdoor Scene," Tech. Rep., Beckman Inst., Univ. of Illinois at Urbana Champaign, 1990.
[33] Y. Liu and and T.S. Huang,“Vehicle-type motion estimation from multi-frame Images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 8, pp. 802-808, 1993.
[34] O. Nasraoui and R. Krishnapuram, "A Genetic Algorithm for Robust Clustering Based on a Fuzzy Least Median of Squares Criterion," Proc. Amer. Fuzzy Information Processing Soc. Conf., pp. 217-221,Syracuse, N.Y., 1997.
[35] Y. Ohashi, "Fuzzy Clustering and Robust Estimation," Ninth Meeting of SAS Users Group Int'l,Hollywood Beach, Fla., 1984.
[36] P. Rousseeuw and A. Leory, Robust Regression and Outlier Detection. Wiley Series in Probability and Statistics, 1987.
[37] G.S. Sebestyen and A. Roemder, Decision-Making Process in Pattern Recognition.New York: Macmillan Company, 1962.
[38] C.V. Stewart, “MINPRAN: A New Robust Estimator for Computer Vision,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 10, pp. 925-938, Oct. 1995.
[39] G. Taubin,“Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 11, pp. 1115-1137, Nov. 1991.
[40] L.A. Zadeh, "Fuzzy Sets as a Basis for a Theory of Possibility," Fuzzy Sets and Systems, vol. 1, pp. 3-28, 1978.
[41] Z. Zhang, R. Deriche, O. Faugeras, and Q.T. Luong, “A Rubust Technique for Matching Two Uncalibrated Images through the Recovery of the Unknown Epipolar Geometry,” Artificial Intelligence J., vol. 78, pp. 87-119, 1995.
[42] X. Zhuang,T.S. Huang,, and R.M. Haralick,“A simplified linear optic flow-motion algorithm,” Computer Vision, Graphics, and Image Processing, vol. 42, pp. 334-344, 1988.
[43] X. Zhuang, Y. Huang, K. Palaniappan, and Y. Zhao, “Gaussian Mixture Density Modeling Decomposition, and Applications,” IEEE Trans. Image Processing, vol. 5, pp. 1293-1302, 1996.
[44] X. Zhuang, T. Wang, and P. Zhang, A Highly Robust Estimator Through Partially Likelihood Function Modeling and Its Application in Computer Vision IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, pp. 19-35, 1992.
Index Terms:
Robust clustering, fuzzy clustering, competitive clustering, robust statistics, optimal number of clusters, linear regression, range image segmentation, motion estimation.
Citation:
Hichem Frigui, Raghu Krishnapuram, "A Robust Competitive Clustering Algorithm With Applications in Computer Vision," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, no. 5, pp. 450-465, May 1999, doi:10.1109/34.765656 Usage of this product signifies your acceptance of the Terms of Use.
|
