POOR TEXTURAL IMAGE MATCHING BASED ON GRAPH THEORY

Shiyu Chen, Xiuxiao Yuan, Wei Yuan, Yang Cai2016 · DOI

Abstract

Image matching lies at the heart of photogrammetry and computer vision. For poor textural images, matching results are often degraded by low contrast, repetitive patterns, discontinuity, or occlusion. This paper proposes an edge-weight strategy to improve graph matching algorithms specifically for these challenging scenarios. Experimental results across four typical landscapes—forest, desert, farmland, and urban areas—demonstrate that the proposed algorithm significantly outperforms traditional SIFT. The method doubled the number of corresponding points and achieved an overall recall rate of 68%, verifying its effectiveness for automated image alignment in difficult environments.

Introduction

Standard image matching algorithms, such as SIFT (Scale-Invariant Feature Transform) or NCC (Normalized Cross-Correlation), rely heavily on radiometry—the unique local pixel appearance of a feature. However, these methods frequently fail when processing "poor textural" images. In landscapes like dense forests or barren deserts, local patches often appear identical (ambiguity) or lack sufficient contrast to define distinct points.

To address this, the authors propose moving beyond local appearance to leverage global geometric relationships. By representing feature points as nodes in a graph, the problem shifts from comparing pixel values to comparing the spatial arrangement of points, which remains more stable across different viewpoints and lighting conditions.

Methodology

The proposed Edge-Weighted High-Order Graph Matching (EW-HOGM) approach follows a structured pipeline to ensure robust alignment in low-signal environments.

Workflow of the proposed EW-HOGM algorithm for poor textural image matching.

To prevent feature clustering in high-contrast areas, the algorithm utilizes UR-SIFT (Uniform Robust SIFT) to extract evenly distributed points. For each point in the source image, a set of $k$ potential candidates is identified in the target image using an Approximate Nearest Neighbor (ANN) search.

2. 3rd-Order Affinity Tensor and Edge-Weighting

The core innovation lies in the use of a 3rd-order affinity tensor. Unlike 2nd-order matching which compares pairs of points, 3rd-order matching compares triplets (triangles). This provides affine invariance, allowing the system to handle scale changes and rotations more effectively.

Geometric constraints using 3rd-order affinity tensors based on triangle interior angles.

As shown in the figure above, the algorithm compares triangles in graph $G_P$ and $G_Q$ by analyzing their interior angles ($\theta_i, \theta_j, \theta_k$). The authors introduced a novel edge-weighting strategy to mitigate the impact of outliers. This strategy boosts the influence of triangles with similar geometric signatures while suppressing noise, which is critical in poor texture images where false matches are prevalent.

3. Optimization

The matching problem is solved using a power iteration algorithm to derive a soft assignment matrix $\mathbf{Z}$, which is then discretized into a hard assignment matrix $\mathbf{Z}^*$ to establish final point correspondences.

Experimental Results

The EW-HOGM algorithm was tested against aerial imagery of four difficult landscapes. The results indicate a substantial improvement over standard SIFT in both the quantity and reliability of matches.

Landscape Method Matched Pairs Recall Rate
Forest SIFT 11 22.0%
EW-HOGM 34 68.0%
Desert SIFT 9 30.0%
EW-HOGM 19 63.3%
Urban SIFT 6 6.0%
EW-HOGM 68 68.0%

In urban environments characterized by repetitive architectural features, the proposed method found over ten times as many correct matches as SIFT. The matches were also more uniformly distributed, which is essential for accurate aerial triangulation and mapping.

Conclusion

By prioritizing geometric structure over radiometric appearance, the EW-HOGM algorithm provides a robust solution for matching images with poor texture. The integration of 3rd-order tensors with a specialized edge-weighting strategy allows the system to overcome the ambiguity and noise that typically defeat standard computer vision tools. Future work will focus on optimizing the computational complexity of high-order matching to improve scalability for larger datasets.

Summary updated

Abstract

Image matching lies at the heart of photogrammetry and computer vision. For poor textural images, the matching result is affected by low contrast, repetitive patterns, discontinuity or occlusion, few or homogeneous textures. Recently, graph matching became popular for its integration of geometric and radiometric information. Focused on poor textural image matching problem, it is proposed an edge-weight strategy to improve graph matching algorithm. A series of experiments have been conducted including 4 typical landscapes: Forest, desert, farmland, and urban areas. And it is experimentally found that our new algorithm achieves better performance. Compared to SIFT, doubled corresponding points were acquired, and the overall recall rate reached up to 68%, which verifies the feasibility and effectiveness of the algorithm.
BibTeX
@inproceedings{chen2016poor,
  author = {Shiyu Chen and Xiuxiao Yuan and Wei Yuan and Yang Cai},
  title = {{POOR TEXTURAL IMAGE MATCHING BASED ON GRAPH THEORY}},
  booktitle = {˜The},
  year = {2016},
  doi = {10.5194/isprs-archives-xli-b3-741-2016},
}
Figure