Research On Graph Theory Based Image Segmentation And Its Embedded Application

Image Segmentation is a low-level technique of image processing. It partitions images into meaningful connected regions by some specific image features. The high-level applications of it include image & video processing tasks, covering fields of broadcast, computer network, pattern recognition, and machine vision, etc. Research on image segmentation techniques has duration of several decades of years. Although there exist many methods, multiple classes, and a huge literature in this field, the problem of global segmentation having vision consistency with human eyes is not solved well.Among all of these image segmentation methods, the one based on Minimum Spanning Tree (MST) and region comparison predicates has the capability of capturing global features. It also runs quickly, having computational complexity nearly linear to the pixel number. The two dominant advantages give it the possibility to application. Our work mainly bases on the MST-based algorithm.In order to improve the segmentation results and computational speed, we concentrate the modification efforts on two sides: algorithm and program. The algorithm details of the concepts, theories, data structures, and implementation ways are studied.We find that the bottle neck of the algorithm dues to the number of graph edges, i.e., the actual number of computed vertices in the mapped graph. Instead of mapping the image pixel by pixel, our work represents with one vertex a square block of image pixels with fixed size of N×N, N=1,2,3. This trick utilizes the similarity of local image features among neighboring pixels, significantly decreasing the number of graph edges. The fixed square blocks simplify the work of deciding whether one pixel belongs to some block. We change the neighboring system to adapt with the square blocks. It consists of two layers: the basic and super connection. The basic connection keeps the proximity of regions, and the super connection keeps the continuity of regions. They improve the capability of capturing global features. The segmentation produces neither over-segmented nor under-segmented regions. We classify the algorithm into three stages: preprocessor, kernel, and postprocessor. The structure facilitates the balance of computational loads. The original algorithm has a big portion of computation in the kernel. Therefore we move the procedure of graph building from kernel into the preprocessor by keeping the interfaces unchanged. The modification improves the ability of parallel processing.Analyzing and representing images in a hierarchical way has a long history. It has advantages of showing image contents in different definitions. Graph pyramids in image segmentation can accumulate local features, representing in a coarse definition the global features. Pyramids have two classes: regular and irregular pyramid. Irregular pyramid is also called adaptive pyramid, which overcomes the rigidity of regular pyramid and is adaptive to the contents of images. The irregular pyramid structure is the main implementation in segmentation methods. Many data structure and decimation schemes about irregular pyramids have been presented, but most of them are too complex.Our work use the MST-based segmentation algorithm as an irregular contraction kernel because of its advantages of global segmentation, high running speed, and simple algorithm structure. The blocks are used in level 0 to improve convergence speed. A new fast neighbor region searching method is given to efficiently construct the edges in higher level. These efforts limit the contraction factor and pyramid height, and show a new irregular pyramid segmentation algorithm with embedded blocks. More efficient segmentation and higher running speed are verified by the experimental results.We use some modifications to form a parameter independent segmentation algorithm. Firstly, the feature of parent vertex is replaced by the mean value of its region in our irregular pyramid. It reduces the affect of noise without other methods, therefore removing the Gaussian filter parameter in the original algorithm. Secondly, the parameter of limiting small regions is replaced by the edge weight difference between maximum and minimum value. The modification adapts the algorithm to each level of the irregular pyramid. Thirdly, the deviation of the image feature is computed to replace a threshold parameter in constructing the blocks. Fourthly, the intrinsic contraction of the pyramid gets rid of the procedure of merging small components. Therefore it removes the corresponding parameter. Good segmentation results and fast solution make our algorithm have a possibility to real-time applications. Based on the work of software/hardware designs on the decoder of High Definition Television System-on-a-Chip platform, we analyze the optimizations of temporal and spatial resources on embedded platform with MIPS processor. The optimization of the MST-based segmentation algorithm is firstly recalled. Then we concentrate the optimization work on program codes, including running time profiling, cache using, function call, and dynamic memory, etc. Finally our segmentation algorithm is ported to MIPS development platform Malta as software IP. It runs in a host-target way on an embedded software system, with components including boot loader, Linux kernel, API and lib. The segmentation program reads/writes image data files via network.In a word, we study the MST-based image segmentation method and pyramid structures. At the same time, a series of efforts are given to improve the segmentation results and running speed. We also optimize the program in running time and space aspects, and present a porting to embedded platform. The experimental results show good values of our work on theory and application.