Modified balanced iterative reducing and clustering using hierarchies (m-BIRCH) for visual clustering

In modern visual clustering applications where datasets are large and updates with new data may be ongoing, methods of online clustering are extremely important. Online clustering algorithms incrementally cluster the data points, use a fraction of the dataset memory, and update the clustering decisions when new data comes in. In this paper we adapt a classic online clustering algorithm called balanced iterative reducing and clustering using hierarchies (BIRCH) to incrementally cluster large datasets of features commonly used in visual clustering, e.g., 840 K color SIFT descriptors, 1.09 million color patches, 60 K outlier corrupted grayscale patches, and 700 K grayscale SIFT descriptors. We use the algorithm to cluster datasets consisting of non-convex clusters, e.g., Hopkins 155 3D motion segmentation dataset. We call the adapted version modified-BIRCH (m-BIRCH). BIRCH was originally developed by the database management community, but has not been used in computer vision. Modifications made in m-BIRCH enable data-driven parameter selection and effectively handle varying density regions in the feature space. Data-driven parameter selection automatically controls the level of coarseness of the data summarization. Effective handling of varying density regions is necessary to well represent the different density regions in the data summarization. Our implementation of the algorithm provides a useful clustering tool and is made publicly available.