BSU Bulletin. Mathematics, Informatics
Bibliographic description:
METHODS FOR ACCELERATING THE CLASSICAL WARD METHOD FOR CLUSTERING PIXELS OF IMAGE // BSU Bulletin. Mathematics, Informatics. - 2018. №3. . - С. 60-71.
Title:
METHODS FOR ACCELERATING THE CLASSICAL WARD METHOD FOR CLUSTERING PIXELS OF IMAGE
Financing:
Codes:
Annotation:
Segmentation refers to the stage of pre-processing images. Further selection of ob- jects, recognition of features, analysis of scenes and prediction of situations depend on its results. The requirements to modern segmentation algorithms are as follow- ing: refusal to use a priori information, availability of a quality functional for evaluation of the result, a variable number of segments in decomposition of the original image, linear computational complexity and adequacy of the segmentation results. The Ward method is appropriate among the methods of cluster analysis that satisfy most of the above requirements. However, its high computational complex- ity prevents its direct application. The aim of the study is to find a way to over- come the excessively high computational complexity of the classical Ward method. The methods: classical methods of cluster analysis that meet the current require- ments for modern image segmentation algorithms are compared. The choice of the classical Ward method is substantiated. Its advantages and disadvantages are given. The application of the idea of reversible operations in image processing is de- scribed. Results: a number of some modifications of the computational process of the Ward method are given. A typical block scheme of a sequence of algorithms is proposed, that allows to circumvent the problem of computational complexity char- acteristic of the Ward method. Experimental results are presented to improve the quality of traditional segmentation. Practical significance: the proposed scheme al- lows to circumvent the problem of computational complexity by dividing the proc- essing course into three consecutive stages. The scheme is suitable for improving the quality of any traditional segmentation.
Keywords:
cluster methods, hierarchical image segmentation, the Ward method, re- versible calculations, improving the image quality.
List of references:
Porshnev S. V., Levashkina А. O. Universal'naya klassifikatsiya algoritmov segmentatsii izobrazhenij [The Universal Classification of Image Segmentation Algo- rithms]. Zhurnal nauchnykh publikatsij aspirantov i doktorantov - The Journal of Sci- entific Publications of Post-Graduate Students and Doctoral Students. 2008. V. 3. Pp. 163–172.
Ward J. H., Jr. Hierarchical grouping to optimize an objective function. J. Am. Stat. Assoc. 1963. V. 58. Issue 301. Pp. 236–244.
Otsu N. A threshold selection method from gray-level histograms. IEEE trans- actions on systems, man, and cybernetics. 1979. V. 9, No. 1. Pp. 62–66.
Lloyd S. P. Least squares quantization in PCM. IEEE Transactions on Informa- tion Theory (1957/1982). V. 28, No. 2. Pp. 129–137. DOI: 10.1109/TIT.1982.1056489.
Mumford D., Shah J. Boundary detection by minimizing functionals. IEEE Con- ference on Computer Vision and Pattern Recognition. 1985. V. 17. Pp. 137–154.
Mumford D., Shah J. Optimal approximations by piecewise smooth functions and associated variational problems. Communications on pure and applied mathemat- ics. 1989. V. 42, No. 5. Pp. 577–685.
Wang Z., Bovik A. C. A Universal Image Quality Index. IEEE signal processing letters. 2002. V. 9, No. 3. Pp. 81–84.
Kharinov M. V., Khanykov I. G. Primenenie metoda Uorda dlya klasterizatsii pikselej tsifrovogo izobrazheniya [Utilization of Ward’s Method for Clustering of Pix- els of Color Image]. Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, informatika. [Bulletin of Buryat State University. Mathematics, Informatics]. 2016. No. 4. Pp. 34–42.
Kharinov M. V., Khanykov I. G. Optimizatsiya kusochno-postoyannogo pribliz- heniya segmentirovannogo izobrazheniya [Optimization of Piecewise-Constant Ap- proximation for Segmented Image]. Trudy SPIIRAN [SPIIRAS Proceedings]. 2015. V. 3, No. 40. Pp. 183–202.
Khanykov I. G., Kharinov M. V., Patel C. Image Segmentation Improvement by Reversible Segment Merging. (2017, December 1-2). Int. Conf. on Soft Computing and its Engineering Applications, icSoftComp-2017, IEEE Gujarat Section Proceed- ings. Pp. 1–8. DOI: 10.1109/icsoftcomp.2017.8280096.
Kharinov M. Reclassification formula that provides to surpass K-means method // arXiv preprint arXiv:1209.6204. 2012. Pp. 1–4.
Dvoenko S. D. Meanless k-means as k-meanless clustering with the bi-partial approach. Proceedings of PRIP 2014 Conference, Minsk. 2014. Pp. 50–54.
Toffoli T. Reversible Computing. International Colloquium on Automata, Lan- guages, and Programming. Springer, Berlin, Heidelberg, 1980. Pp. 632–634.
Ward J. H., Jr. Hierarchical grouping to optimize an objective function. J. Am. Stat. Assoc. 1963. V. 58. Issue 301. Pp. 236–244.
Otsu N. A threshold selection method from gray-level histograms. IEEE trans- actions on systems, man, and cybernetics. 1979. V. 9, No. 1. Pp. 62–66.
Lloyd S. P. Least squares quantization in PCM. IEEE Transactions on Informa- tion Theory (1957/1982). V. 28, No. 2. Pp. 129–137. DOI: 10.1109/TIT.1982.1056489.
Mumford D., Shah J. Boundary detection by minimizing functionals. IEEE Con- ference on Computer Vision and Pattern Recognition. 1985. V. 17. Pp. 137–154.
Mumford D., Shah J. Optimal approximations by piecewise smooth functions and associated variational problems. Communications on pure and applied mathemat- ics. 1989. V. 42, No. 5. Pp. 577–685.
Wang Z., Bovik A. C. A Universal Image Quality Index. IEEE signal processing letters. 2002. V. 9, No. 3. Pp. 81–84.
Kharinov M. V., Khanykov I. G. Primenenie metoda Uorda dlya klasterizatsii pikselej tsifrovogo izobrazheniya [Utilization of Ward’s Method for Clustering of Pix- els of Color Image]. Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, informatika. [Bulletin of Buryat State University. Mathematics, Informatics]. 2016. No. 4. Pp. 34–42.
Kharinov M. V., Khanykov I. G. Optimizatsiya kusochno-postoyannogo pribliz- heniya segmentirovannogo izobrazheniya [Optimization of Piecewise-Constant Ap- proximation for Segmented Image]. Trudy SPIIRAN [SPIIRAS Proceedings]. 2015. V. 3, No. 40. Pp. 183–202.
Khanykov I. G., Kharinov M. V., Patel C. Image Segmentation Improvement by Reversible Segment Merging. (2017, December 1-2). Int. Conf. on Soft Computing and its Engineering Applications, icSoftComp-2017, IEEE Gujarat Section Proceed- ings. Pp. 1–8. DOI: 10.1109/icsoftcomp.2017.8280096.
Kharinov M. Reclassification formula that provides to surpass K-means method // arXiv preprint arXiv:1209.6204. 2012. Pp. 1–4.
Dvoenko S. D. Meanless k-means as k-meanless clustering with the bi-partial approach. Proceedings of PRIP 2014 Conference, Minsk. 2014. Pp. 50–54.
Toffoli T. Reversible Computing. International Colloquium on Automata, Lan- guages, and Programming. Springer, Berlin, Heidelberg, 1980. Pp. 632–634.
Article.pdf