izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2020-24-2-90-107izvestswsu-775Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentПрименение модели скоростной кластеризации пикселей в задачах предобработки изображений дистанционного зондирования ЗемлиApplication of the Pixel Velocity Clustering Model in the Tasks of Preprocessing images of Earth Remote Sensinghttps://orcid.org/0000-0001-6284-0839ХаныковИ. Г.KhanykovI. G.

Ханыков Игорь Георгиевич - магистр техники и технологии, младший научный сотрудник.14 линия В.О. 39, Санкт-Петербург 199178.

Igor G. Khanykov - Master of Computer Sciences, Junior Research Officer, St.Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS).39, 14-th Line V.O., St. Petersburg 199178.

igk@iias.spb.suСанкт-Петербургский Институт информатики и автоматизации Российской академии наук (СПИИРАН)St.Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS)20200410202024290107Copyright © Ханыков И.Г., 20202020Ханыков И.Г.Khanykov I.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://izvestswsu.elpub.ru/jour/article/view/775

Цель исследования заключается в применении модифицированного метода Уорда в скоростной обработке полноразмерных изображений дистанционного зондирования Земли.Методы. Классический метод Уорда модифицируется путем разделения вычислительного процесса на три последовательных этапа. На первом этапе строится грубая иерархия приближений. На втором этапе выполняется промежуточное улучшение качества заданного разбиения при фиксированном числе цветов. Третий этап кластеризует полученные суперпиксели классическим методом Уорда. Программно-алгоритмический инструментарий составляют четыре операции над кластерами пикселей и сегментами изображения: слияние пары кластеров в один, разделение кластера на Два исходных, выделение подмножества пикселей в отдельный кластер и реклассификация части пикселей путем исключения из одного кластера и отнесения их в другой. Оценкой качества служит суммарная квадратичная ошибка. Улучшение качества разбиения изображения обеспечивается итеративным исполнением сочетания операций слияния и разделения кластеров пикселей, в частности сегментов изображения. Один из кластеров (сегментов) разделяется надвое и пара других несовпадающих с ним объединяется в один по критерию минимального приращения суммарной квадратичной ошибки.Результаты. Предложенный модифицированный метод Уорда применен в обработке полноразмерных изображений дистанционного зондирования Земли, взятых из базы данных Института обработки сигналов и изображений Южно-Калифорнийского университета. Сопоставлены результаты обработки в режимах чистой сегментации и кластеризации.Заключение. Предложенная модель кластеризации пикселей пригодна для скоростной обработки полноразмерных изображений. Кластеризация пикселей по сравнению с сегментацией изображений позволяет более детально определить как контуры объектов интереса, так и их внутреннюю структуру.

Purpose of research is to apply the modified Ward method in high-speed processing of full-size images of Earth remote sensing.Methods. The classical Ward method is modified by dividing the computational process into three successive stages. At the first stage, a rough hierarchy of approximations is built. At the second stage, an intermediate improvement of the quality of the given partition is performed for a fixed number of colours. At the third stage, the obtained superpixels are clustered using the classical Ward method. The software-algorithmic toolkit consists of four operations on pixel clusters and image segments: merging a pair of clusters into one, dividing a cluster into two original ones, singling out a subset of pixels into a separate cluster and reclassifying some pixels by excluding them from one cluster and assigning them to another. The quality is assessed by the total squared error. Improving the image decomposition quality is ensured by iterative execution of a combination of merging and deviding pixel clusters, image segments, in particular. One of the clusters (segments) is devided in two and a couple of others non-coincident with it are combined into one according to the criterion of minimum increment of the total squared error.Results. The proposed modified Ward method is applied in the processing of full-size images of Earth remote sensing taken from the database of the USC Signal and Image Processing Institute. The results of processing in the modes of pure segmentation and clustering are compared.Conclusion. The proposed pixel clustering model is suitable for high-speed processing of full-size images. Pixel clustering in comparison with image segmentation makes it possible to define in more detail both the contours of objects of interest and their internal structure.

сегментация изображенийкластеризация пикселейскоростная кластеризациясуперпикселииерархия приближенийimage segmentationpixel clusterizationhigh-speed clusteringsuperpixelshierarchy of approximationsReferencesWard J.H., Jr. Hierarchical grouping to optimize an objective function. J. Am. Stat. Assoc. 1963. 58(301): 236-244. http:/doi.org/10.1080/01621459.1963.10500845.Ward J.H., Jr. Hierarchical grouping to optimize an objective function. J. Am. Stat. Assoc, 1963, no. 58(301), pp. 236-244. http:/doi.org/10.1080/01621459.1963.10500845.Otsu N.A. Threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man and Cybernetics. 1979. 9(1): 62-66. http:/doi.org/10.1109/TSMC.1979.4310076.Otsu N.A. Threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man and Cybernetics, 1979, no. 9(1), pp. 62-66. http:/doi.org/10.1109/TSMC.1979.4310076.Lloyd S.P. Least squares quantization in PCM. IEEE Transactions on Information Theory. 1957/1982. 28(2): 129-137. http://doi.org/10.1109/TIT.1982.1056489.Lloyd S.P. Least squares quantization in PCM. IEEE Transactions on Information Theory. 1957/1982, no. 28(2), pp. 129-137. http://doi.org/10.1109/TIT.1982.1056489.Mumford D., Shah J. Boundary detection by minimizing functionals. IEEE Conference on Computer Vision and Pattern Recognition. 1985. 17: 137-154.Mumford D., Shah J. Boundary detection by minimizing functionals. IEEE Conference on Computer Vision and Pattern Recognition, 1985, no. 17, pp. 137-154.Mumford D., Shah J. Optimal approximations by piecewise smooth functions and associated variational problems. Communications on pure and applied mathematics. 1989. 42(5): 577-685. http://doi.org/10.1002/cpa.3160420503.Mumford D., Shah J. Optimal approximations by piecewise smooth functions and associated variational problems. Communications on pure and applied mathematics, 1989, no. 42(5), pp. 577-685. http://doi.org/10.1002/cpa.3160420503.Purohit P., Joshi R.A. New Efficient Approach towards k-means Clustering Algorithm. In International Journal of Computer Applications. 2013. 65(11): 125-129. https://pdfs.semanticscholar.org/99bb/dc0435b10476f61a778e0ab00301704c647c.pdfPurohit P., Joshi R.A. New Efficient Approach towards k-means Clustering Algorithm. In International Journal of Computer Applications, 2013, no. 65(11), pp. 125-129. https://pdfs.semanticscholar.org/99bb/dc0435b10476f61a778e0ab00301704c647c.pdfYedla M., Pathakota S.R., Srinivasa T.M. Enhanced K-means Clustering Algorithm with Improved Initial Center. In International Journal of Science and Information Technologies. 2010. 1(2): 121-125. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.421.7070&rep=rep1&type=pdfYedla M., Pathakota S.R., Srinivasa T.M. Enhanced K-means Clustering Algorithm with Improved Initial Center. In International Journal of Science and Information Technologies, 2010, no. 1(2), pp. 121-125. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.421.7070&rep=rep1&type=pdfNazeer K.A.A., Sebastian M. P. Improving the Accuracy and Efficiency of the k-means Clustering Algorithm. In Proceedings of the World Congress on Engineering. 2009. https://www.researchgate.net/profile/K_A_Nazeer/publication/44260003_Improving_the_Accuracy_an d_Efficiency_of_the_k-means_Clustering_Algorithm/links/ 0fcfd51356e00827b8000000.pdfNazeer K.A.A., Sebastian M. P. Improving the Accuracy and Efficiency of the k-means Clustering Algorithm. In Proceedings of the World Congress on Engineering. 2009. https://www.researchgate.net/profile/K_A_Nazeer/publication/44260003_Improving_the_Accurac y_and_Efficiency_of_the_k-means_Clustering_Algorithm/links/0fcfd51356e00827b8000000.pdfJose A, Ravi S, Sambath M. Brain tumor segmentation using k-means clustering and fuzzy c-means algorithms and its area calculation. International Journal of Innovative Research in Computer and Communication Engineering. 2014. 2(3): 3496-3501.Jose A, Ravi S, Sambath M. Brain tumor segmentation using k-means clustering and fuzzy c-means algorithms and its area calculation. International Journal of Innovative Research in Computer and Communication Engineering, 2014, no. 2(3), pp. 3496-3501.Das A., Sabut S.K. Kernelized fuzzy C-means clustering with adaptive thresholding for segmenting liver tumors. Proceedings on Computer Science. 2016. 92: 389-395. http://doi.org/10.1016/j.procs.2016.07.395.Das A., Sabut S.K. Kernelized fuzzy C-means clustering with adaptive thresholding for segmenting liver tumors. Proceedings on Computer Science, 2016, no. 92, pp. 389-395. http://doi.org/10.1016/j.procs.2016.07.395.Chan T. F., Vese L. A. Active contours without edges. Image processing, IEEE Transactions on. 2001. 10(2): 266-277. http://w3.mi.parisdescartes.fr/~lomn/Cours/CV/Se-qVideo/Articles/ChanLevelSet.pdfChan T. F., Vese L. A. Active contours without edges. Image processing, IEEE Transactions on. 2001, no. 10(2), pp. 266-277. http://w3.mi.parisdescartes.fr/~lomn/Cours/CV/SeqVideo/Articles/ChanLevelSet.pdfSalem M.B., Ettabaa K.S., Bouhlel M.S. Hyperspectral image feature selection for the fuzzy c-means spatial and spectral clustering. In International Image Processing, Applications and Systems (IPAS) IEEE. 2016: 1-5. https://doi.org/doE10.1109/ipas.2016.7880114Salem M.B., Ettabaa K.S., Bouhlel M.S. Hyperspectral image feature selection for the fuzzy c-means spatial and spectral clustering. In International Image Processing, Applications and Systems (IPAS) IEEE. 2016: 1-5. https://doi.org/doi:10.1109/ipas.2016.7880114Sardooi E.R., Azareh A., Choubin B., Barkhori S., Singh V.P., Shamshirband S. Applying the remotely sensed data to identify homogeneous regions of watersheds using a pixel-based classification approach. Applied Geography. 2019. 111: 102071. https://doi.org/doi:10.1016/j.apgeog.2019.102071Sardooi E.R., Azareh A., Choubin B., Barkhori S., Singh V.P., Shamshirband S. Applying the remotely sensed data to identify homogeneous regions of watersheds using a pixel-based classification approach. Applied Geography. 2019. 111: 102071. https://doi.org/doi:10.1016/j.apgeog.2019.102071Xie T, Jiang H, Wang J, Tian X., Xu A.A. A new recognition algorithm of the lunar mare area basing on the DEM contrast. In International Conference on Advanced Materials and Engineering Structural Technology (2015 Apr 25). https://www.researchgate.net/profile/Junlin_Wang2/publication/295819542_A_new_recognition_algorithm_of_the_lunar_mare_area_based_on_the_DEM_contrast/links/56cdbc2408ae85c8233e66f1/A-new-recognition-algorithm-of-the-lunar-mare-area-based-on-the-DEM-contrast.pdfXie T, Jiang H, Wang J, Tian X., Xu A.A. A new recognition algorithm of the lunar mare area basing on the DEM contrast. In International Conference on Advanced Materials and Engineering Structural Technology (2015 Apr 25). https://www.researchgate.net/profile/Junlin_Wang2/publication/295819542_A_new_recognition_algorithm_of_the_lunar_mare_area_based_on_the_DEM_contrast/links/56cdbc2408ae85c8233e66f1/A-new-recognition-algorithm-of-the-lunar-mare-area-based-on-the-DEM-contrast.pdfПестунов И.А., Синявский Ю.Н. Алгоритмы кластеризации в задачах сегментации спутниковых изображений // Вестник КемГУ. 2012. 4(52): 110-125. URL: https://cyberleninka.ru/article/v/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniyPestunov I.A., Sinyavskiy Yu.N. Algoritmy klasterizatsii v zadachakh segmentatsii sputnikovykh izobrazhenii [Clustering Algorithms in Satellite Images Segmentation Tasks]. Vestnik KemGU = Bulletin of Kemerovo State University, 2012, no. 4(52), pp. 110-125 (in Russ.). Available at: https://cyberleninka.ru/article/v/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy.Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности. М.: Финансы и статистика, 1989. 607 с.Aivazyan S.A., Bukhshtaber V.M., Enyukov I.S., Meshalkin L.D. Prikladnaya statistika: Klassifikatsiya i snizhenie razmernosti [Applied statistics: Classification and reduction of dimension]. Moscow, Finansy i statistika Publ., 1989, 607 p. (In Russ.).Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988. 176 с.Mandel' I.D. Klasternyi analiz [Cluster Analysis]. Moscow, Finansy i statistika Publ., 1988, 176 p. (in Russ.)Харинов М.В., Ханыков И.Г. Применение метода Уорда для кластеризации пикселей цифрового изображения // Вестник БГУ. Математика, информатика. 2016. 4: 34-42. http://doi.org/10.18101/2304-5728-2016-4-34-42.Kharinov M.V., Khanykov I.G. Primenenie metoda Uorda dlya klasterizatsii pikselei tsifrovogo izobrazheniya [Utilization of Ward's Method for Clustering of Pi1els of Color Image]. Vestnik BGU. Matematika, informatika = BSU Bulletin. Mathematics, Informatics, 2016, no. 4, pp. 34-42 (In Russ.) http://doi.org/10.18101/2304-5728-2016-4-34-42.Харинов М.В., Ханыков И.Г. Оптимизация кусочно-постоянного приближения сегментированного изображения // Труды СПИИРАН. 2015. 3(40): 183-202. https://doi.org/10.15622/sp.40.12.Kharinov M.V., Khanykov I.G. Optimizatsiya kusochno-postoyannogo priblizheniya segmentirovannogo izobrazheniya [Optimization of Piecewise Constant Approximation for Segmented Image]. Trudy SPIIRAN = SPIIRAS Proceedings, 2015, no. 3(40), pp. 183-202 (In Russ.) https://doi.org/10.15622/sp.40.12.Khanykov I.G., Kharinov M.V., Patel C. Image segmentation improvement by reversible segment merging. 2017 International Conference on Soft Computing and its Engineering Applications (icSoftComp). IEEE, 2017. http://doi.org/10.1109/ICSOFTCOMP.2017.8280096Khanykov I.G., Kharinov M.V., Patel C. Image segmentation improvement by reversible segment merging . 2017 International Conference on Soft Computing and its Engineering Applications (icSoftComp). IEEE, 2017, http://doi.org/10.1109/ICSOFTCOMP.2017.8280096.Харинов М.В. Кластеризация пикселей иерархически структурированного изображения // Информационно-измерительные и управляющие системы. 2019. 17(5): 30-43. http://doi.org/10.18127/j20700814-201905-05.Kharinov M.V. Klasterizatsiya pikselei ierarkhicheski strukturirovannogo izobra-zheniya. Informatsionno-izmeritel'nye i upravlyayushchie sistemy [Clustering of pixels for a hierarchically structured image]. Informatsionno-izmeritelnye i upravlyayshchie sistemy = Information-measuring and Control Systems, 2019, no. 17(5), pp. 30-43 (In Russ.). http://doi.org/10.18127/j20700814-201905-05.Харинов М.В. Обобщение трех подходов к оптимальной сегментации цифрового изображения // Труды СПИИРАН. 2013. 2(25): 294-316. http://www.mathnet.ru/links/d13b2a4e766e53f82eb216ba6367bf29/trspy552.pdfKharinov M.V. Obobshchenie trekh podkhodov k optimal'noi segmentatsii tsifrovogo izobrazheniya [A generalization of three approaches to an optimal segmentation of digital image]. Trudy SPIIRAN = Tr. SPIIRAN, 2013, no. 25, pp. 294-316. (In Russ.). Available at: http://www.mathnet.ru/links/d13b2a4e766e53f82eb216ba6367bf29/trspy552.pdf

The authors declare that there are no conflicts of interest present.