Contour-Based Image Registration using Bipartite Graph Matching with Munkres Algorithm

Qingsong Zhu, Tiexiang Wen, Ricang Ye, Qi Li, Yaoqin Xie, Jia Gu, Lei WangApplied Mathematics & Information Sciences 2013 · DOI

TL;DR

This paper introduces a novel contour-based image registration method specifically for aligning color and depth data from Kinect sensors. By leveraging sub-pixel contour refinement, shape context descriptors, and Munkres algorithm for bipartite graph matching, the method achieves robust correspondence and accurate transformation estimation, outperforming existing approaches.

What Problem Does This Paper Address?

Image registration, the process of aligning images from different sources or viewpoints, is crucial in many computer vision applications. This paper focuses on a specific challenge: registering color images with depth data captured by the Microsoft Kinect. While Kinect provides synchronized RGB and depth information, these images often suffer from blur and noise, and their inherent differences make direct feature matching difficult. Existing methods, particularly those relying on SIFT features, struggle to effectively match intensity images with depth data, leading to incorrect correspondences and registration errors. The authors aim to bridge this gap by developing a robust method that can accurately align these distinct data types.

Methods

The proposed method employs a multi-stage approach:

  1. Preprocessing: Both color and depth images are smoothed to reduce noise. A median filter is used for color images, while depth images undergo a median filter after zero pixels (indicating unstable depth measurements) are filled using median values from multiple frames.
  2. Contour Detection and Refinement: Canny edge detection is used to extract initial boundary contours. To improve accuracy, these contours are then refined to a sub-pixel level using a B-spline model. This global approach is noted for its robustness to noise.
  3. Shape Descriptor Computation: For the refined contours, shape context descriptors are computed. This descriptor is chosen for its robustness to scale, translation, rotation, and deformation, making it suitable for matching contours that might not be perfectly aligned initially.
  4. Bipartite Graph Matching: The core of the correspondence finding lies in treating the problem as a bipartite graph matching task. A cost matrix is constructed where each entry represents the "cost of matching" between points on contours from the two images, calculated using the Chi-square statistic on their shape context descriptors. The Munkres algorithm (specifically an improved version) is then applied to find the optimal assignment of points, minimizing the total matching cost. This step is crucial for establishing reliable point correspondences.
  5. Transformation Estimation: Once a set of reliable correspondence points is established, the RANSAC (Random Sample Consensus) algorithm is used to estimate the transformation matrix that best aligns the two images. RANSAC is effective in handling outliers that may arise during the correspondence process.

Datasets

The paper evaluates its method on a series of natural images captured by the Kinect for Xbox 360. Specific examples include images of a woman, a bear with an umbrella, an umbrella, and a chair. The authors do not introduce a new benchmark dataset but rather use these diverse natural scenes to demonstrate the method's performance.

Key Insights and Ideas

  • Contour-based approach for diverse data: The paper highlights the effectiveness of using contour information, rather than just point features like SIFT, for registering images with fundamentally different characteristics (color vs. depth).
  • Sub-pixel contour refinement is critical: Achieving sub-pixel accuracy in contour localization, using B-splines, significantly improves the precision of subsequent feature matching.
  • Shape context for robust descriptors: The choice of shape context as a descriptor proves effective in handling variations and potential distortions between corresponding contours.
  • Munkres algorithm for optimal assignment: Framing the correspondence problem as a bipartite graph matching and solving it with the Munkres algorithm provides a principled way to find the best pairings between contour points.
  • RANSAC for outlier rejection: The integration of RANSAC is essential for robustly estimating the transformation model, effectively discarding erroneous correspondences.

Key Results

The proposed contour-based method, using Munkres algorithm for bipartite graph matching, demonstrated superior performance compared to other methods (COPAP, ACO, and Hungarian algorithm) in terms of both Root Mean Square Error (RMSE) and computational cost.

  • RMSE: The paper reports significantly lower average RMSE values for their method across various test cases. For instance, in the "Woman" case, their method achieved an RMSE of 0.4135, compared to 0.4405 for Hungarian and Nan for COPAP.
  • Computational Cost: The method also showed a competitive or superior computational cost. For the "Bear" case, their method took only 6.242 seconds, significantly less than COPAP (30.0764s) and Hungarian (17.4582s).
  • Qualitative Results: Figures 4-7 visually demonstrate the quality of correspondence points found by their method, showing more accurate and dense pairings compared to the other algorithms, especially in challenging scenarios.

Limitations and Future Work

The authors acknowledge that their method's performance is dependent on the quality of contour extraction. While they use Canny edge detection and B-spline refinement, further improvements in contour detection could lead to even better results.

For future work, the authors plan to focus on:

  • Improving execution time: While their method is competitive, further optimization of the algorithm's speed is a goal.
  • Implementing more complex scenarios: Extending the method to handle more challenging registration tasks, such as those involving significant occlusions or more extreme viewpoint changes, is also on the agenda.

Summary updated

Abstract

Image registration is a vital research topic in image processing.In this paper, we present a novel method to register color image and depth information captured by Kinect for Xbox 360.A contour-based approach is employed to find the correspondence points and estimate the transformation parameters model between color image and depth image.In our paper, the boundary contours are detected by Canny edge detector and located to sub-pixel level by a B-spline model.The shape descriptors of contours are computed by shape context.The correspondence points on both similar contours will have similar shape descriptors, which enables us to solve a bipartite graph matching with Munkres algorithm.Based on the correspondence points, the transform model that best aligns the two images can be estimated via RANSAC method.Experiments on a series of natural images are used for compare with some existing approaches and demonstrate the effectiveness of our method.
BibTeX
@inproceedings{zhu2013contour,
  author = {Qingsong Zhu and Tiexiang Wen and Ricang Ye and Qi Li and Yaoqin Xie and Jia Gu and Lei Wang},
  title = {{Contour-Based Image Registration using Bipartite Graph Matching with Munkres Algorithm}},
  booktitle = {Applied Mathematics \& Information Sciences},
  year = {2013},
  doi = {10.12785/amis/080132},
}
Figure