(50-1) 11 * << * >> * Русский * English * Содержание * Все выпуски

Segmentation of earth remote sensing images based on agglomerative pixel clustering using the minimum increment of the total squared error as a decision function
I.G. Khanykov1, V.A. Nenashev1, M.V. Kharinov2

1State University of Aerospace Instrumentation, 67 Bolshaya Morskaya street, Saint Petersburg, 190000, Russia;
2Federal Research Center of Russian Academy of Sciences, 39 14th Line V.O., Saint Petersburg, 199178, Russia

  Полный текст (PDF)

DOI: 10.18287/COJ1591

ID статьи: 1591

Аннотация:
Among cluster analysis methods applied to grayscale image segmentation, Arifin's algorithm is particularly notable. This algorithm enables partitioning the original image into a number of clusters ranging from N_max to 1 in linear time, where N_max represents the number of grayscale levels in the original image. Arifin's algorithm incrementally enlarges pixel clusters by combining a "minimum pair" at each iteration within the calculation cycle, characterized by the minimum distance Dist between clusters. The original method calculates Dist by taking the product of interclass and intraclass variances; however, this approach involves cumbersome formulas and lacks a quality assessment for the resulting partitions. This study introduces two modifications to Arifin's algorithm that simplify the calculation of Dist for identifying "minimum pairs" and performing cluster merging sequences, while also enabling evaluation of cluster partition quality. The first modification uses the increment of the total squared error as a distance function for Dist, whereas the second modification employs partial entropy. In the first approach, partition quality is evaluated based on the total squared error or standard deviation, while in the second, it is assessed by the information content. A computer program has been developed to implement the first modification of Arifin's algorithm, incorporating a difference formula to compute partition quality. This program has been tested using standard test images of various sizes, including full-scale aerospace images (three images at 1024×1024 pixels and one at 2050×2050 pixels). The practical significance of the modification, which leverages the increment of the total squared error to create a series of suboptimal piecewise-constant partitions, lies in reducing the number of operations per cycle needed to determine the "minimum pair" among all adjacent clusters, thereby halving processor time.

Ключевые слова:
clustering, segmentation, objective function, total squared error, variance, entropy.

Благодарности:
The paper was prepared with the financial support of the Ministry of Science and Higher Education of the Russian Federation, grant agreement No. FSRF-2023-0003, "Fundamental principles of building of noise-immune systems for space and satellite communications, relative navigation, technical vision and aerospace monitoring".

Citation:
Khanykov IG, Nenashev VA, Kharinov MV. Segmentation of earth remote sensing images based on agglomerative pixel clustering using the minimum increment of the total squared error as a decision function. Computer Optics 2026; 50(1): 1591. DOI: 10.18287/COJ1591.

References:

  1. Jain J, Li J, Chiu MT, Hassani A, Orlov N, Shi H. OneFormer: One Transformer to Rule Universal Image Segmentation. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) 2023; 2989-2998.
  2. Hoeser T, Bachofer F, Kuenze C. Object Detection and Image Segmentation with Deep Learning on Earth Observation Data: A Review---Part II: Applications. Remote Sens 2020; 12(18): 3053. DOI: 10.3390/rs12183053.
  3. Otsu N. A Threshold Selection Method from Gray-level Histograms. IEEE Transactions on Systems, Man, and Cybernetics. 1979; 9(1): 62-66. DOI: 10.1109/TSMC.1979.4310076
  4. Kapur JN, Sachoo PK, Wong AKC. A New Method for Gray-Level Picture Thresholding Using the Entropy of the Histogram. Computer Vision, Graphics and Image Processing. 1985; 29(1): 273-285. DOI: 10.1016/0734-189X(85)90125-2
  5. Kittler J, Illingworth J. Minimum Error Thresholding. Pattern Recognition. 1986; 19: 41-47. DOI: 10.1016/0031-3203(86)90030-0
  6. Ward JHJ. Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association. 1963; 58: 236-244. DOI: 10.1080/01621459.1963.10500845
  7. Arifin AZ, Asosno A. Image segmentation by histogram thresholding using hierarchical cluster analysis. Pattern Recognition Letters. 2006; 27(13): 1515-1521. DOI: 10.1016/j.patrec.2006.02.022.
  8. Tong H, Tong F, Zhou W, Zhang Y. Purifying SLIC Superpixels to Optimize Superpixel-Based Classification of High Spatial Resolution Remote Sensing Image. Remote Sens. 2019; 11: 2627. DOI: 10.3390/rs11222627.
  9. Berkeley Segmentation Dataset 500 (BSDS500). Source: <https://paperswithcode.com/dataset/bsds500> (accessed on 2024.04.18)
  10. Rahkar Farshi T, Demirci R, Feizi-Derakhshi MR. Image Clustering with Optimization Algorithms and Color Space. Entropy 2018; 20: 296. DOI: 10.3390/e20040296.
  11. Cardone B, Di Martino F, Miraglia V. A Novel Fuzzy-Based Remote Sensing Image Segmentation Method. Sensors 2023; 23: 9641. DOI: 10.3390/s23249641.
  12. Huang S, Zhang O, Chen Q. Ship Target Detection Method in Synthetic Aperture Radar Images Based on Block Thumbnail Particle Swarm Optimization Clustering. Remote Sens. 2023; 15: 4972. DOI: 10.3390/rs15204972.
  13. Wang Z. Unsupervised Wavelet-Feature Correlation Ratio Markov Clustering Algorithm for Remotely Sensed Images. Appl. Sci. 2024; 14: 767. DOI: 10.3390/app14020767.
  14. Olkina DS. Algorithm of Semantic Image Segmentation for Solving the Problem of Positioning an Aircraft on the Earth's Surface. Trudy MAI. 2023. № 130. DOI: 10.34759/trd-2023-130-18 (In Russian)
  15. Bukirev AS. Method for Diagnosing an Aircraft on-board Equipment Complex Based on Machine Learning. Trudy MAI. 2023; 133. Source: <https://trudymai.ru/published.php?ID=177672> (In Russian)
  16. Khanykov IG. Technology modification for distance calculation between pairs of adjacent clusters in multilevel thresholding. Trudy MAI. 2021; 118: 1-34. DOI: 10.34759/trd-2021-118-13.
  17. Koshkarov AS, Gulii DD, Bariaksheva VP. Multi-Rotor Unmanned Aerial Vehicle Emergency Landing Algorithm Based on Underlying Surface Image Analysis. Trudy MAI. 2023; 132. Source: https://trudymai.ru/published.php?ID=176854 (In Russian)
  18. Lukin VN, Nikitin IK. Algoritm poiska sobytii v videoposledovatel'nostiakh. Trudy MAI. 2017; 96. (In Russian)
  19. Molotkov AA, Tretiakova ON. Application of Machine Vision in Laser Technologies. Trudy MAI. 2022; 127. DOI: 10.34759/trd-2022-127-25. (In Russian)
  20. Nenashev VA, Khanykov IG. Formation of the complex image of the Earth surface based on the pixel clustering of the location images in the multi-position airborne system. Informatics and Automation 2021; 20(2): 302-340. DOI: 10.15622/ia.2021.20.2.3.
  21. Nenashev VA, Shepeta AP, Kryachko AF. Fusion radar and optical information in multi-position on-board location systems. In Proceedings of the 2020 Wave Electronics and Its Application in Information and Telecommunication Systems (WECONF), St. Petersburg, Russia, 1-5 June 2020; pp. 1-5. - DOI: 10.1109/WECONF48837.2020.9131451.
  22. Schwab M, Mayr1 A, Haltmeie M. Deep Gaussian mixture model for unsupervised image segmentation. 2024; arXiv:2404.12252v1. DOI: 10.48550/arXiv.2404.12252
  23. Andriyanov NA, Dementiev VE. Developing and Studying the Algorithm for Segmentation of Simple Images Using Detectors Based on Doubly Stochastic Random Fields. Pattern Recognition and Image Analysis 2019; 29(1): 1--9. DOI:10.1134/s105466181901005x.
  24. Krasheninnikov V, Kuvayskova Yu, Subbotin A. Pseudo-gradient algorithm for identification of doubly stochastic cylindrical image model. 24th International Conference on Knowledge Based and Intelligent Information & Engineering Systems 2020; 1858--1867. DOI: 10.1016/j.procs.2020.09.225.
  25. Signal and Image Processing Institute open dataset, Volume 2: Aerials. Source: <https://sipi.usc.edu/database/database.php?volume=aerials&image=38#top>
  26. Modified Arifin's method. Source: <https://github.com/IgorKhanykov/ModifOfAACM>

Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20