Clustering is a basic operation in imageprocessing and computer vision, and it plays an important role in unsupervised patternrecognition and image segmentation. While there are many methods for clustering, the sing...
详细信息
Clustering is a basic operation in imageprocessing and computer vision, and it plays an important role in unsupervised patternrecognition and image segmentation. While there are many methods for clustering, the single-link hierarchical clustering is one of the most popular techniques. In this paper, with the advantages of both optical transmission and electronic computation, we design efficient parallel hierarchical clustering algorithms on the arrays with reconfigurable optical buses (AROB). We first design three efficient basic operations which include the matrix multiplication of two N x N matrices, finding the minimum spanning tree of a graph with N vertices, and identifying the connected component containing a specified vertex. Based on these three data operations, an O(log N) time parallel hierarchical clustering algorithm is proposed using N-3 processors. Furthermore, if the connectivity of the AROB with four-port connection is allowed, two constant time clustering algorithms can be also derived using N-4 and N-3 processors, respectively. These results improve on previously known algorithms developed on various parallel computational models. (C) 2000 Academic Press.
暂无评论