Research And Application Of Mark-based Distance Transformation Algorithm

Distance transform is an important operation in the analysis and processing of digital image. Ithas played a good role in the skeleton line extraction, image segmentation and registration, actionrecognition, the shortest path computation etc, so the distance transform algorithm has been theresearch focus in the image processing area.According to the accuracy, existing distance transform algorithms can be classified as:approximate distance transform and distance transform completely. Although the approximatedistance transform algorithm is simple and fast, there exists a fatal defect: inaccurate results.Though the complete distance transform algorithm can overcome the above shortcoming, it alsobrings in some new problems such as designing complexity and time consumption large. So thispaper dedicated to study out a simple, efficient and complete distance transform algorithm.Firstly, this paper proposes a complete mark-based distance transform algorithm. Whenprocesses the two-dimensional image, the relative positions between the target point and thebackground pixels are marked at first, then with the search radius strategies and neighborhoodpixel’s distance transform information set a small search region for each pixel, and finally figureout the the distance transform in the search region by contour tracing method. Because the three-dimensional image is superimposed by several two-dimensional images, thus when processes thethree-dimensional image, first calculates the distance transform of each two-dimensional image,then adopt the same search radius strategy as two-dimensional to set a search region for each pixel,and in the three-dimensional search region figure out each pixel’s final three-dimensional distancetransform. Experiments show that our algorithm has a greater advantage in time and spaceconsumption, precision, and may of parallelism both in two-dimensional and three-dimensionalimage processing.Then, this paper proposes a cell separation method which integrates the distance transformand the watershed. This method add a distance threshold mechanism on the basis of the traditionalwatershed method, firstly uses the OSTU method to preprocess the cell image, and fills the holewith the boundary tracking method, then calculates the cell image’s distance transform, accordingto the cell characteristic set a distance threshold for watershed segmentation, finally designs an areathreshold, using this threshold to deal with the "over segmentation" and "incomplete segmentation"problems. Experiment proves that our method has the efficiency of segmentation. Simultaneously, this paper also applies the mark-based distance transform algorithm to theskeleton line extraction, and proposes a new skeleton extraction method which integrates thethinning and distance transform into Snake model; the method not only enhances all the advantagesof thinning and distance transform method, but also avoids their shortcoming which is couldn’tguarantee continuous, single-pixel and location accuracy. The experiment also proved the excellentcharacteristics of our algorithm. Finally, summarizes the whole research work of this paper andputs forward the future work.