Multi-dimensional Image Thresholding Algorithm Without A Criterion

Image thresholding is one of the most classical and important techniques of image segmentation. It is an old but hot topic in digital image processing. Image thresholding is the pre-processing of most of image processing techniques. It will deeply affect the following image understanding or image analysis. As a traditional image segmentation method, image thresholding is one of the most basic and popular techniques of image segmentation, because of its simple process, low time complexity but efficient results. After analyzing most of image thresholding methods, this paper proposed an image thresholding algorithm without a criterion——the optimal evolution algorithm (OEA) which is different from other image thresholding methods. Furthermore, the optimal evolution algorithm has been extended to high dimensional space. The principal work and remarks of this paper are as follow:(1) Unlike other image thresholding algorithms, we try to find an image thresholding algorithm without a criterion. According to the theories of biological evolution and genetic algorithm, we assume that there exists an optimal evolution direction. The direction is consistent and stable in the evolution process.(2) According to the theories of biological evolution and genetic algorithm, we established the population evolution model and the threshold updating model. After defining the chromosomes'coding rule, the sampling method, the initialization method of the evolution direction, the fitness function and the selection mechanism, we proposed an image thresholding algorithm without a criterion—the optimal evolution algorithm. Experimental results show that the optimal evolution direction does exist; the population is strongly attracted by the direction; the direction is the most stable direction during the population's evolution. The optimal evolution algorithm performs well in image thresholding experiments.(3) To solve the problems found in the experiments, we improve the optimal evolution algorithm. We discover the relationship between the initial threshold and the optimal threshold in biological evolution by detailed in the population evolution model. Based on the relationship, we improve the threshold updating model; establish a threshold modification model to obtain a fast and stable OEA. The improved OEA solved the problems that the optimal threshold obtained by OEA and the iterative times are unstable while randomly initialize the threshold; thresholding results contain some noise because the optimal threshold obtained by OEA is too close to the class which has more samples than the other. Detailed population evolution model supports the existence of the optimal evolution direction. Experimental results show that the improved OEA is much more efficient.(4) Based on theories of OEA and the idea of two-dimensional image thresholding methods, we extended OEA to two-dimensional space, and proposed an algorithm framework for two-dimensional image thresholding without a criterion—2D-OEA. Results show that 2D-OEA is a fast, stable and efficient image thresholding algorithm. Compared with 1D-OEA, the properties and the results of 2D-OEA are much better.(5) Image thresholding algorithm is one-dimensional or two-dimensional, because the computational complexity is too high and there is no corresponding region division method in high-dimensional space for image thresholding. To decrease computational complexity and find a region division method in high-dimensional space, we establish an orientation model of normal vector, and propose hypercubic division method and hyperplane division method in high-dimensional space for image thresholding. Based on these two region division methods in high-dimensional space, we proposed a high-dimensional image thresholding algorithm without a criterion—N-dimensional optimal evolution algorithm, ND-OEA. The ND-OEA has a rapid and stable convergence. The computational complexity of ND-OEA is much lower than ( )O L2 N which is the computational complexity of high-dimensional image thresholding algorithm in theory. Experimental results show that ND-OEA is a fast and efficient image thresholding algorithm. With the increasing of the space's dimension, hypercubic division method is losing more and more pixels belonging to the object, but hyperplane division method's thresholding results are stable. ND-OEA presents a multi-dimensional image thresholding algorithm without a criterion. It solves the problem of computational complexity in high-dimensional space. With the increasing of space's dimension, the global relationship between the object and the background is getting more and more clear, details of the object are losing more and more seriously, but the contrast between object and background is getting more and more strong. ND-OEA's thresholding results, which is strong contrast between the object and the background in high-dimensional space, are consistent with the selection mechanism of human visual system. So ND-OEA is an intelligent algorithm.(6) We apply ND-OEA to color image thresholding, and propose an edge detection algorithm based on ND-OEA. Three color images, whose objects are hardly segmented from the background by most image thresholding algorithm, are selected to test ND-OEA. Results show that ND-OEA can find the optimal hyperplane in color space without building a color space model; edge detection algorithm based on ND-OEA is an efficient edge detection algorithm, and edges detected by it have clear contours, rich details, nice connectivity.