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:
- 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.
- 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.
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.
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