A Fast Normalized Cut with Automated Constraints via Graph Coarsening

Overview

Abstract

We present a new constrained K-way data clustering algorithm based on Normalized Cut by Shi and Malik. A novelty in our algorithm lies in selecting constraints automatically from the data by using a multiscale coarsening algorithm. The coarsening algorithm is adopted from the work by Sharon, et al. But, unlike their work to use this for image segmentation directly, we apply this algorithm only to obtain the constraints for K-way clustering. Furthermore, our algorithm is formulated in a more effective way than the traditional Rayleigh-Ritz projection algorithm for image segmentation with a priori partial grouping constraints by Yu and Shi. A number of test results demonstrate the effectivity of the algorithm to obtain image segmentations in comparisons with the state of the art algorithms. This is the joint work with Dr. Ivan Ojeda-Ruiz. 

Brief Biography

Young Ju Lee obtained his Ph.D from Penn State University in 2004 under the direction of Professor Jinchao Xu. He then did Postdoc at UCLA until 2007 with Professor Russel E. Caflisch. He then got a tenure track job in Rutgers, The State University of New Jersey, Piscataway. He move to the Department of Mathematics at Texas State University in 2013. He is currently an Associate Professor. His research was supported in part by National Science Foundation and also the American Chemical Society. He held a NRF Brainpool Fellow in the year 2020 and Shapiro Fellow at Penn State in the Spring of 2022.