1. Field of the Invention
The present invention relates to graph-based image segmentation processing.
2. Description of the Related Art
A region segmentation method is used as a technique for segmenting an image into a plurality of regions so that attributes such as color, pattern, and brightness become the same. The segmented regions can undergo encoding processing, and region recognition and identification for each segmented region. This can reduce the processing amount in comparison with image processing at the pixel level. Recently, it is becoming popular to perform image processing in a built-in device controlled by software. It is considered that even the built-in device can perform complicated image processing on a high-resolution image by executing image processing for each region after region segmentation.
Various methods have been proposed regarding region segmentation of an image. Literatures which present methods for clustering pixels to segment an image into regions are, for example, literatures 1, 2, and 3:    Literature 1: Dorin Comaniciu, Peter Meer, “Mean Shift: A Robust Approach toward Feature Space Analysis”, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 24, No. 5, pp. 603-619, 2002    Literature 2: Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, Sabine Susstrunk, “SLIC Superpixels”, EPFL Technical Report, No. 149300, June 2010    Literature 3: Andrea Vedaldi, Stefano Soatto, “Quick Shift and Kernel Methods for Mode Seeking”, In Proceedings of the European Conference on Computer Vision (ECCV), 2008
Literature 1 proposes a non-parametric feature space search method called mode-seeking. This search method is a method (Mean-shift method) of detecting local maximum positions at distribution densities for input points obtained by projecting pixels in an image to a predetermined feature space. The input points are connected to the detected local maximum positions to cluster pixels. This method is based on convergent calculation by iterative processing, and the total processing amount is large.
Literature 2 proposes a pixel clustering method based on mode-seeking, similar to literature 1, but adopts a method of moving a feature space to increase the kernel density estimation. Since this method is not convergent calculation, the processing amount is smaller than that in the Mean-shift method. However, the calculation amount is O(n^2) proportional to almost the square of the number n of data, so the total processing amount is large.
Literature 3 proposes a method of distributing and arranging cluster centers serving as initial positions not to overlap edges in an image, and clustering pixels based on a k-mean method using the cluster centers as seeds to segment the image into regions. This method includes iterative processing, but the calculation amount is much smaller than those in the above-described methods. However, since the k-mean method needs to be executed between respective cluster centers, data of the entire image needs to be held for clustering. It is difficult to implement this method in a built-in device for which it is hard to ensure a large-capacity memory.
Unlike the above-mentioned region segmentation methods by clustering, literatures 4 and 5 present graph-based region segmentation methods in which pixels are set as nodes, adjacent pixels are connected to form an edge, and an image is handled as a graph to segment the image into regions:    Literature 4: Jianbo Shi, Jitendra Malik, “Normalized Cuts and Image Segmentation”, IEEE Trans. PAMI, Vol. 22, No. 8, August 2000    Literature 5: Pedro F. Felzenszwalb, Daniel P. Huttenlocher, “Efficient Graph-Based Image Segmentation”, International Journal of Computer Vision, Vol. 59, No. 2, September 2004
According to the method in literature 4, an edge having, as a feature amount, an affinity representing the similarity between nodes is set between nodes, and an edge to be cut for region segmentation is specified. To obtain the cut, the eigenvalue problem of a matrix representing the affinity needs to be solved, requiring a large calculation amount.
According to the method in literature 5, similar to literature 4, pixels are set as nodes, adjacent pixels are connected to form an edge, and the dissimilarity in color or the like between adjacent pixels is calculated as the feature amount of an edge. After calculating the feature amounts of all edges, the edges are sorted in the order of magnitude of the feature amount. In the order of sorted edges, it is determined whether to merge regions to which nodes, that is, pixels at the two ends of each edge belong. Regions determined to be merged are merged. The same merging determination processing is performed for all edges. At the end of the merging determination processing for all edges, the image has been segmented into a plurality of regions each having the same attributes. This method has features in which the calculation amount itself is smaller than those in the aforementioned methods, processing is possible at high speed, and the accuracy is high.
In the region segmentation method in literature 5, sort processing can reduce processing for searching for an edge having a maximum feature value in a region. The sort processing amount depends on the number of edges generated in an image to be processed. According to the method in literature 5, edges are generated between a pixel of interest and eight neighboring pixels. Therefore, time is taken to sort all edges.
Generally, sort processing is often executed as sequential processing, and it is hard to increase the speed of sort processing by hardware. Thus, when a built-in device performs image processing on a high-resolution image by using the method in literature 5, sort processing in region segmentation becomes a bottleneck.