Kao, C.-C.C.-C.KaoLai, J.-H.J.-H.LaiJA-LING WUSHAO-YI CHIEN2018-09-102018-09-10201219457871http://www.scopus.com/inward/record.url?eid=2-s2.0-84868139442&partnerID=MN8TOARShttp://scholars.lib.ntu.edu.tw/handle/123456789/370666Spectral graph methods are widely employed in image segmentation, and they exhibit excellent performance. However, for high-resolution images, it is impractical to directly calculate the eigenvectors of the affinity matrix owing to the high computational requirements. The Nystrom method provides an efficient way to approximate the large-scale affinity matrix by low-rank approximation. In the machine learning field, previous studies have mainly focused on less data points with high dimensional features. To the best of our knowledge, this is the first study to discuss the performance of sampling methods for Nystrom approximation, in which we focus on the pixel-wise affinity matrix for a single image. In this paper, we propose a mean-shift segmentation-based Nystrom sampling technique for image analysis. The experimental results show that for images with simple compositions and backgrounds, k-means sampling performs better, whereas for images with more complicated compositions and backgrounds, the proposed method can perform better. © 2012 IEEE.diffusion map; image segmentation; mean-shift; Nyström approximation; spectral graph theoryAffinity matrix; Computational requirements; Data points; Excellent performance; High dimensional feature; High resolution image; K-means; Low rank approximations; Mean shift; Nystrom method; Sampling method; Sampling technique; Single images; Spectral graph theory; Exhibitions; Graph theory; Image segmentation; Pixelsconference paper10.1109/ICME.2012.512-s2.0-84868139442