摘要
随着图像采集技术的发展,人们可获得分辨率越来越高的图像,高效地提取高分辨率图像中大量可辨识信息对图像工程应用有重要意义。传统的多分辨率图像锥采用低通滤波技术,分割高分辨率图像时造成分割区域数量不等于图像中实际物体数量;串行的模糊C-均值(即FCM)算法分割图像时可能忽略空间上下文信息,且时间和空间复杂度很大。如何提高大幅图像的分割效率是图像处理领域的一个难题。
本文提出基于正交小波分解的多分辨率图像锥结合FCM的图像分割方法,该方法综合分析正交小波分解法、多分辨率图像锥分割算法和FCM算法的多核并行性,设计出两者相结合的P-FCM多核并行模型,采用并行化语言OpenMP实现该模型。实验验证该算法在保证分割质量的前提下,较好地提高图像分割效率。本文主要工作包括:
①对图像分割技术的研究背景、实际应用意义、国内外的研究现状和图像处理基础理论知识进行分析,并对多核并行发展及相关技术进行介绍。
②针对传统图像锥设计过程计算量大和分割图像效率低的缺点,采用多核并行的正交小波分解法设计锥结构,并提出基于多分辨率图像锥的多核并行图像分割模型(P-多核并行锥模型)。
③针对多分辨率图像锥分割图像可能存在过或低分割的问题,引入FCM算法,设计其多核并行模型,并与P-多核并行锥模型相结合,提出P-FCM多核并行模型。另外,对原始图像数据预处理时,采用矩形块并行分割方法来划分原始图像数据。
④采用OpenMP对P-FCM多核并行模型编程,并统计分析该模型算法在分割不同大小和不同分辨率的图像时P-FCM多核并行模型的加速比。
⑤通过实验验证该模型在处理高分辨率的大幅图像(大于1MB)时,随着CPU数量的增加,加速比呈接近线性方式递增。
本文提出的P-FCM多核并行模型能很好地降低计算复杂度,提高图像分割效率,满足图像工程应用中实时性强和准确性高的要求。
With the development of image acquisition technology, people can gain the higher and higher resolution image. It is useful to efficiently extract a large number of identifying information in the high resolution images for the application of Image Engineering. The traditional multiresolution image pyramid utilizes the low-pass filter technique, which easily causes the number of segmentation regions not equal to the true number of objects which really exist in the high resolution image; when the algorithm of fuzzy c-mean (FCM) is applied to segment the image, it may ignore the spatial context and also has the large complexity of time and space. How to improve the segmentation efficiency of large image is becoming a difficult problem.
In this paper, a novel technique is proposed, which combines the multiresolution image pyramid based on the orthogonal wavelet decomposition with the FCM algorithm. This paper integrally analyses the muti-core parallel feasibility of the orthogonal wavelet decomposition, the multiresolution image pyramid segmentation algorithm and FCM algorithm, designs the multi-core parallel model of P-FCM which is the combination of the multiresolution image pyramid amd FCM, and the parallel language of OpenMP is adopted to achieve this model. Experiment testifies that this model preferably improves the efficiency of image segmentation under the promise of segmentation quality.
The main contents of this paper can be summarized as follows:
①Discusses and analyzes the image segmentation technique research background, practical application of significance, research status and the basic knowledge of image processing, then introduces the development of multi-core parallelism and the related technologies.
②Aiming at the design method of traditional image pyramid is high computational complexity and the low efficiency of segmentation, a novel algorithm of multi-core parallel orthogonal wavelet decomposition is applied to design the pyramidal structure, and proposes the multi-core parallel model of image segmentation using multiresolution image pyramid (P- Multi-core Parallel Pyramidal Model).
③Aiming at the problem of over - or under -segmentation using the multiresolution image pyramid, this paper introduces the algorithm of FCM, designs its multi-core parallel model, and presents the multi-core parallel model of P-FCM, which combines the multi-core parallel model of P with the multi-core parallel model of FCM. In addition, for the original image data preprocessing, the parallel method of rectangular block is used to divide the original image data.
④The language of OpenMP is adopted to program the multi-core parallel model of P-FCM, and analyses the Speedup of the P-FCM multi-core parallel model when this algorithm is dealing with the images of different size and different resolution.
⑤Experiments testify that the algorithm of P-FCM could achieve almost linear SpeedUP with the increase of CPU’s number, especially for the high resolution large image (over 1MB) segmentation.
The multi-core parallel model of P-FCM proposed by this paper could reduce the computational complexity, improve the efficiency of image segmentation and meet the requirements of strong real-time and high accuracy in the applications of Image Engineering.
引文
[1] Rafael等著.数字图像处理[M].阮秋琦等译.二版.北京:电子工业出版社,2004.
[2]张大鹏著.模式识别与图像处理半行计算机系统设计[M].哈尔滨:哈乐滨工业大学出版社,1998.
[3] Gammage C, Chaudhary V. On Optimization and Parallelization of Fuzzy Connected Segmentation for Medical Imaging[C]. IEEE.20th International Conference on Advanced Information Networking and Applications.Vienna University of Technology, 2006.
[4]刘汝等.基于PFG的无线信道传输失真度的研究[J].华中科技大学学报:自然科学版,2004(8).
[5]章毓晋.图像工程-图像处理和分析[M].北京:清华大学出版社,1999.
[6]章毓晋.图像分割[M].北京:科学出版社,2001.
[7] Fu S K, Mui J K. A Survey of Image Segmentation[J]. Pattern Recognition, 1981 13(1):3-16.
[8] Doyel W. Operations Useful for Similarity-invariant Pattern Recognition[J].J ACM, 1962, 9(2):259~267.
[9] Prewitt J M S, Mendelsohn M L. The Analysis of Cell Images[J]. Ann N Y Acad Sci.1966, 128:1035~1053.
[10] Bartz M R. Optimizing a Video Preprocessor for OCR[J]. Proc IJCAI, 1969:79~90.
[11] Pikaz, Averbuch. A Digital Image Thresholding Based on Topological Stable State[J]. Pattern Recognition, 1996,29(5):829~843.
[12] Yen J C, Chang F J. A New Criterion for Automatic Multilevel Thresholding[J]. IEEE Trans on Image Processing.1995.4(3):370~377.
[13]秦剑,李林.基于梯度的图像分割新方法[J].计算机应用.2009, (8):2071~2073.
[14] Brink A D. Thresholding of Digital Images Using Two Dimensional Entropies [J]. Pattern Recognition, 1992,25(8):803-808.
[15] Lee C K, Wong S P. A Mathematical Morphological Aprroach for Segmenting Heavity Nosie-corrupted Images[J]. Pattern Recognition,1996, 29(8):1347~1357.
[16]白小晶.基于偏微分方程的图像分割与配准研究[D].南京:南京理工大学2010.
[17]郑宏,潘励.基于遗传算法的图像阈值自动选取[J].中国图像形学报,1999 4(4):327~330.
[18] Jian-Li Ding, Yuan-Xiang Li, Ling-Ling Wang. A Wavelet-based Multiresolution Color Image Segmentation[C]. Neural Networks and Brain, 2005. ICNN&B '05. International Conference on.
[19]刘振安等.并行图像处理算法的设计与实现[J].测控技术,2003,22(5).
[20]董开坤等.基于数学代数的并行图像处理环境[J].计算机研究与发展,2004,41(1).
[21]熊杰等.基于消息传递接口的并行图像处理算法研究J].成都大学自然学报,2010,29(2).
[22] Allgrove C C, Cowley K D, Fairhurst M C. High Performance Classification of Image Data Through the Arallel Realization of Pyramidal Processing Structures [C]. Parallel Architectures for Image Processing, IEE Colloquium on, 1994.
[23] Rahimi S, Zargham M, Thakre A, Chhillar D. A Parallel Fuzzy C-Mean Algorithm for Image Segmentation[J]. NAFIPS 2004.
[24] Wei-hong Wang, Xiao-ming Zhao, Xian-cheng Feng. Parallel Wavelet-based Image Segmentation Using MPI[C]. IEEE Region 10 Conference, 2004.
[25] Mallat S G. A Theory for Multiresolution Signal Decomposition[J]: The wavelet representation. IEEE Trans. Pattern Anal. Machine Intell. vol. 11.no.7, pp.674-693.1989.
[26] Van De Ville D, Unser M. The Marr Wavelet Pyramid. In Image Processing, 2008. ICIP 2008. 15th IEEE International Conference on. 2008.
[27]李晖.多分辨率医学图像配准技术及自适应图像插值技术的研究[D].山东,山东大学,2009:36-42.
[28] Bzedek J C. A Convergence Theorem for The Fuzzy ISODATA Clustering Algorithm[J]. IEEE PAMI,1980, 1(2):1~8.
[29] Ruspini E H. A New Approach to Clustering[J]. Inf.Cont.1969, 15:22~23.
[30] Prewitt J M. Object Enhancement and Extraction[J]. In Picture Processing and Psychopictories, B.S.Lipkin&A. Rosenfeld eds., Acad. Press, 1970:75~149.
[31] Dunn J C. A Fuzzy Relative of The ISODATA Process and Tts Use in Detecting Compact Well Separated Cluster[J]. J Cybernet, 1974, 3:32~57.
[32] Coleman G B, Andrews H C. Image Segmentation by Clustering[J]. Proceedings of the IEEE, 1979. 67(5): 773-785.
[33] Cannon R L, Dave J V, Bezdek J C. Efficient Implementation of the Fuzzy c-Means Clustering Algorithms[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1986. PAMI-8(2): 248-255.
[34] Dzung L Pham. Spatial Models for Fuzzy Clustering[J]. Computer vision and image understanding, 84(2001): 285~297.
[35] Mallat S, Zhong S. Characterization of Signals from Multiscale Edges. Pattern Analysis and Machine Intelligence[J]. IEEE Transactions on, 1992. 14(7): 710-732.
[36] Rezaee M R., et al., A Multiresolution Image Segmentation Technique Based on Pyramidal Segmentation and Fuzzy Clustering[J]. Image Processing, IEEE Transactions on, 2000. 9(7): 1238-1248.
[37] Ohya A, Kosaka A Kak.Vision-based Navigation by a Mobile Robot with Obstacle Using Single-camera Vision and Ultrasion Sensing[J]. IEEE Transactions on Robotics and Automation, 1998. 14(6):969~978.
[38] Hennessy J L, Patterson D A. Computer Architecture: A Quantitative Approach[M] .3rd Edtion. Morgan Kaufmann Publishing co., 2002.
[39]袁香菊.基于多核系统的程序优化技术的研究[D].西安:西安科技大学,2009.
[40] Slabaugh G., Boyes R, Xiaoyun Y. Multicore Image Processing with OpenMP [Applications Corner][J]. Signal Processing Magazine, IEEE, 2010. 27(2): 134-138..
[41]多核系列教材编写组著.多核程序设计[M].北京:清华大学出版社,2007:159~200.
[42] Hong T-H., et al., Image Smoothing and Segmentation by Multiresolution Pixel Linking: Further Experiments and Extensions [J]. Systems, Man and Cybernetics, IEEE Transactions on, 1982. 12(5): 611-622.
[43] Ari David Gross, Azriel Rosenfeld. Multiresolution Object Detection and Delineation[J]. Computer. Vision, Graphics, and Image Processing. 1987 39 (1): 102-115.
[44] Kelly M D. Edge detection by Computer Using Planing[J]. Mach.intell.vol.6, pp.397~409, 1971.
[45] Bezedek J C. Pattern Recognition With Fuzzy Bbjective Function Algorithms[M]. New York: Plenum Press, 1981.
[46] Hall L O., et al., A Comparison of Neural Network and Fuzzy Clustering Techniques in Segmenting Magnetic Resonance Images of the Brain[J]. Neural Networks, IEEE Transactions on, 1992. 3(5): 672-682.
[47] Bezdek J C, Hall L O, and Clarke L P. Review of MR Image Segmentation Techniques Using Pattern Recognition[J]. Med.Phys.,vol.20, no.4:1033-1048, 1993.
[48] Clark M C, et al., MRI Segmentation Using Fuzzy Clustering Techniques[J]. Engineering in Medicine and Biology Magazine, IEEE, 1994. 13(5): 730-742.
[49] Bensaid A M., et al., Validity-guided (re)clustering with Applications to Image Segmentation. Fuzzy Systems[J], IEEE Transactions on, 1996. 4(2): 112~123.
[50] Mukherjee D P, Pal Pand Das J. Sodar Image Segmentation Using Fuzzy C-Means Singal Process[J]. vol.54, no.3:730~742, 1994.
[51] Yen J, Langari R. Fuzzy Logic[M], Prentice Hall, chapter13, 1999.
[52] Kwok T, Smith K, Lozano S, Taniar D. Parallel Fuzzy C-Means Clustering for Large Data Sets[C]. Proceedings of the 8th International Euro-Par Conference on Parallel Processing, Paderborn, volume 2400 of LNCS, PP./ 365~374, 2002.
