DCSH - Matching Patches in RGBD Images

Yaron Eshet, Simon Korman, Eyal Ofek, Shai Avidan

Abstract

Patch matching is a fundamental component of many image processing tasks, yet traditional 2D methods are limited by perspective and geometric distortions. We present Depth Coherency Sensitive Hashing (DCSH), a framework that utilizes RGBD data to match patches based on their underlying 3D geometry. By warping patches to canonical fronto-parallel views and employing a novel Social-CSH algorithm for linear-time neighbor retrieval, our method achieves significant improvements in both speed and reconstruction quality over state-of-the-art 2D techniques.

Introduction

Most computer vision algorithms for denoising, texture synthesis, and super-resolution rely on "patch matching"—the process of finding similar small squares of pixels across an image. Traditionally, this search occurs in the 2D image plane. However, 2D patches are merely deformed projections of 3D surfaces. Two patches that appear distinct in an image due to perspective, tilt, or distance may actually be identical in the real world. DCSH addresses this by leveraging depth information to "undo" camera distortions, searching for matches in a normalized 3D space.

Methods

Depth-Aware Matching (DCSH)

The core of the DCSH algorithm is the transformation of image patches into a geometry-aware representation. This involves two primary steps:

  1. Fronto-Parallel Warping: Using depth maps, the algorithm estimates the 3D surface normal of every patch. It then mathematically warps these patches so they appear as if viewed head-on at a fixed distance. This normalization allows the algorithm to find high-quality matches that 2D-only methods would miss due to perspective skew.
  2. Prototypical Viewpoints: To mitigate resampling artifacts caused by extreme warping, the system uses k-means clustering on 5D vectors (position and surface normal) to identify $L$ dominant planes in the scene. Matching is performed within these "prototypical" views and then merged.
Overview of the DCSH matching process: (a) selecting prototypical viewpoints and (b) warping patches to a fronto-parallel plane.

Social-CSH

Standard fast matching algorithms like Coherency Sensitive Hashing (CSH) typically scale quadratically ($k^2$) as the number of desired neighbors ($k$) increases. This is problematic for high-quality denoising, which often requires hundreds of matches per pixel.

Social-CSH introduces a "friend-of-a-friend" logic: it identifies a small set of seed neighbors and then explores their respective neighbors. Because similar patches tend to cluster in high-dimensional space, this approach allows the algorithm to scale linearly ($O(k)$) with the number of neighbors, providing a 10x–50x speedup without significant loss in accuracy.

Illustration of warping a tilted 3D surface patch to a canonical fronto-parallel view to improve matching accuracy.

Experimental Results

The authors evaluated the pipeline using a custom iPhone RGBD dataset consisting of high-resolution images with reliable multi-view stereo depth maps.

  • Performance: Social-CSH achieved speedups of 20x to 40x compared to standard CSH when retrieving 200 nearest neighbors.
  • Reconstruction: In image reconstruction tasks, DCSH reduced the Root Mean Square Error (RMSE) by nearly 50% in specific cases (e.g., the "Dress" image RMSE dropped from 13.31 to 6.86).
  • Denoising: The full DCSH pipeline outperformed the industry-standard BM3D algorithm by an average of 0.5 dB in PSNR, demonstrating superior preservation of fine textures and patterns.

Conclusion

DCSH demonstrates that 3D geometry is a powerful guide for patch-based vision tasks. By matching in a normalized 3D space, the algorithm finds more relevant matches more efficiently. While the method relies on reliable depth data, it sets a new benchmark for RGBD-based image processing. Future work may extend this framework to image inpainting and super-resolution.

Summary updated

Abstract

We extend patch based methods to work on patches in 3D space. We start with Coherency Sensitive Hashing (CSH), which is an algorithm for matching patches between two RGB images, and extend it to work with RGBD images. This is done by warping all 3D patches to a common virtual plane in which CSH is performed. To avoid noise due to warping of patches of various normals and depths, we estimate a group of dominant planes and compute CSH on each plane separately, before merging the matching patches. The result is DCSH - an algorithm that matches world (3D) patches in order to guide the search for image plane matches. An independent contribution is an extension of CSH, which we term Social-CSH. It allows a major speedup of the k nearest neighbor (kNN) version of CSH - its runtime growing linearly, rather than quadratic ally, in k. Social-CSH is used as a subcomponent of DCSH when many NNs are required, as in the case of image denoising. We show the benefits of using depth information to image reconstruction and image denoising, demonstrated on several RGBD images.
BibTeX
@inproceedings{eshet2013dcsh,
  author = {Yaron Eshet and Simon Korman and Eyal Ofek and Shai Avidan},
  title = {{DCSH - Matching Patches in RGBD Images}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  doi = {10.1109/iccv.2013.18},
}
Figure