Pruning for image segmentation: Improving computational efficiency for large-scale remote sensing applications

Xianwei Lv, C. Persello, Wufan Zhao*, Xiao Huang, Zhongwen Hu, Dongping Ming, A. Stein

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
23 Downloads (Pure)


Image segmentation is a fundamental step in object-based image analysis and other workflows. However, high-efficiency remains a challenge, especially for the analysis of large-scale Earth observation images. In recent years, considerable effort has been paid to designing merging criteria, automatic scale selection, and object-specific optimisation. These segmentation methods usually rely on the region-adjacency graph (RAG) model and the nearest neighbour graph (NNG) model, which provide acceptable merging performance. Low efficiency occurs due to many redundant edge weight updates in the RAG model. In this study, we propose a generic dynamic pruning framework to improve the efficiency of existing region-merging-based segmentation algorithms, opening the door for large-scale applications in remote sensing. The proposed pruning framework includes intra-object and inter-object pruning modules for the RAG model. Inter-object pruning divides the RAG model into multiple sub-RAG models to reduce the redundant edge weight updates between adjacent objects. Intra-object pruning iteratively divides the sub-RAG into smaller RAGs. In our experimental analysis, we employ the proposed pruning framework with six region-merging segmentation methods and validate the effectiveness on four 10–20M pixel images and a 100M pixel data set. The pruning framework improves the performance of various segmentation algorithms by reducing computational complexity while maintaining segmentation accuracy. We observed a significant improvement in efficiency, with various achieving super-linear speed-up while maintaining the stability of segmentation accuracy. In single-core mode, the computation time of tested algorithms is enhanced by two to ten times on the four test images. In the multicore mode, speed-up increased up to 40 times with eight CPU cores. The computational cost was reduced by 36.15% to 95.77% in the number of weight updates, which is independent of hardware characteristics. On the large-scale image, two modes achieved speed-ups of 36.07 and 102.74, respectively.

Original languageEnglish
Pages (from-to)13-29
Number of pages17
JournalISPRS journal of photogrammetry and remote sensing
Early online date8 Jun 2023
Publication statusPublished - Aug 2023


  • Image segmentation
  • Nearest neighbour graph
  • Pruning
  • Region adjacency graph
  • Region-merging
  • UT-Hybrid-D


Dive into the research topics of 'Pruning for image segmentation: Improving computational efficiency for large-scale remote sensing applications'. Together they form a unique fingerprint.

Cite this