We propose a parallel graph-based data clustering algorithm using CUDA GPU, based on exact clustering of the minimum spanning tree in terms of a minimum isoperimetric criteria. We also provide a comparative performance analysis of our algorithm with other related ones which demonstrates the general superiority of this parallel algorithm over other competing algorithms in terms of accuracy and speed.
Normalized cut @cite_13 is another popular graph-based data clustering algorithm for which XianLou and ShuangYuan @cite_1 developed a parallel version and gained about 2.34 times speed up in the best case. In the context of hierarchical clustering, firstly, Olson @cite_14 , introduced a parallel algorithm. Also, Dahlhaus @cite_2 presented another parallel algorithm and used his algorithm to solve the undirected split decomposition problem in graphs. Amal Elsayed @cite_18 , designed and implemented a parallel document clustering based on hierarchical approach and for the best case, they gained a 5 times speed up over $65 On the other hand, some other parallel algorithms are developed on the various architectures and models. @cite_0 , implemented a parallel version of k-means clustering on map-reduce model. Middelmann and Sanders @cite_10 proposed a heuristic graph-based image segmentation algorithm and implemented a parallel algorithm for shared-memory machines.
@cite_18 @cite_14 @cite_10 @cite_1 @cite_0 @cite_2 @cite_13
2132603077 2746372354 2063266501 2063149017
A novel graph theoretic approach for data clustering is presented and its application to the image segmentation problem is demonstrated. The data to be clustered are represented by an undirected adjacency graph G with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of G to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size ( approximately 2000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of G, which can be efficiently constructed using the Gomory-Hu algorithm (1961). However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. The new clustering algorithm is applied to the image segmentation problem. The segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in G), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours. > The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate. Vision tasks, such as segmentation, grouping, recognition, can be formulated as graph partition problems. The recent literature witnessed two popular graph cut algorithms: the Ncut using spectral graph analysis and the minimum-cut using the maximum flow algorithm. We present a third major approach by generalizing the Swendsen-Wang method - a well celebrated algorithm in statistical mechanics. Our algorithm simulates ergodic, reversible Markov chain jumps in the space of graph partitions to sample a posterior probability. At each step, the algorithm splits, merges, or regroups a sizable subgraph, and achieves fast mixing at low temperature enabling a fast annealing procedure. Experiments show it converges in 2-30 seconds on a PC for image segmentation. This is 400 times faster than the single-site update Gibbs sampler, and 20-40 times faster than the DDMCMC algorithm. The algorithm can optimize over the number of models and works for general forms of posterior probabilities, so it is more general than the existing graph cut approaches. This paper proposes a parallel algorithm using CUDA GPU to accelerate the process of image segmentation algorithm based on Normalized Cut. After giving a summary of the key concepts and theory of normalized cut and CUDA, detailed implementation issues are discussed including the calculation of affinity matrix, transforming symmetric matrices to symmetric tridiagonal matrices, calculation of generalized eigenvalue value and its associated eigenvetor, the choice of splitting point, stopping criterion etc. This algorithm doesn't sparse the similarity matrix, so there is no information loss in transforming, which will lead to a more real and reliable segmentation. The experiment shows that the parallel algorithm using CUDA not only segment the image reliably but also have a great performance speed-up.