Mixed-Resolution Patch-Matching (MRPM)

Harshit Sureka and P. J. Narayanan

Center for Visual Information Technology (CVIT)
International Institute of Information Technology, Hyderabad, India (IIIT-H)


[Abstract]     [Paper]    [Code]    [Algorithm]   [GPU]    [Results]    [Conclusions]    [BibTex]


Abstract: Matching patches of a source image with patches of itself or a target image is a first step for many operations. Finding the optimum nearest-neighbors of each patch using a global search of the image is expensive. Optimality is often sacrificed for speed as a result. We present the Mixed-Resolution Patch-Matching (MRPM) algorithm that uses a pyramid representation to perform fast global search. We compare mixed- resolution patches at coarser pyramid levels to alleviate the ects of smoothing. We store more matches at coarser resolutions to ensure wider search ranges and better accuracy at finer levels. Our method achieves near optimality in terms of average error compared to exhaustive search. Our approach is simple compared to complex trees or hash tables used by others. This enables fast parallel implementations on the GPU, yielding upto 70x speedup compared to other iterative approaches. Our approach is best suited when multiple, global matches are needed.

Paper: Mixed-Resolution Patch-Matching [PDF] (ECCV 2012)
Poster --> [pdf]
Spotlight --> [wmv]
Presentation --> Available Soon



Pyramid Patch-Matching (PPM)

Pyramid Patch-Matching
Simple Algorithm
  • Gaussian Image Pyramid
  • Exhaustive Search at coarsest resolution level
  • Upsampling of matches which provides a search range at finer levels
  • Search within this range to find matches
  • Possible to use other patch-matching and nearest-neighbor algorithms for search

Mixed-Resolution Patch-Matching (MRPM)

MRPM Algo
MRPM

  • Mixed-Resolution Vectors: Extending traditional patch-vectors that contain information from a single resolution level to MR-vectors that include information from multiple resolution levels.
  • More confident matching at coarse resolutions
  • Better match-accuracy
  • Replaced patch-vectors in PPM with MR-vectors and achieved state-of-the-art patch-matching accuracy.


GPU Implementation
  • Independent search for each match
  • Multi-core implementation using openMP
  • GPU implementation using CUDA
  • Much easier GPU implementation compared to other iterative approaches.
  • Near-linear speed-up w.r.t. no. of cores on the CPU
  • Additional 70x speed-up on GeForce GTX 580 graphics card
    compared to the CPU implementation run on a quad-core machine

Results:

PPM and MRPM compared with Coherency Sensitive Hashing shown to be faster and more accurate than PatchMatch.
CSH's dataset of 133 image pairs available at their webpage and used in our experiments.

Proximity to Ground Truth
PPM captures 4% more of the ground truth matches than CSH and MRPM captures 8% more than CSH.
Best K Matches
CSH
PPM
MRPM
Best Match
92.43%
92.48%
93.57%
Best 5 Matches
88.06%
89.7%
91.51%
Best 10 Matches
81.72%
85.69%
89.87%


Error
MRPM consistently achieves lower error valus than PPM and CSH running at speeds similar to them.
Error Comparison


Conclusions

We proposed a simple multiresolution approach for nearest-patch fi nding using  mixed-resolution vectors for matching. Our simplicity enables fast parallel implementations. We find near-optimal match locations and reach lower error values  than Coherency Sensitive Hashing. Advantages of the MRPM method are more pronounced when several nearest matches are needed. The advantages in time  and quality over CSH diminish while nding one closest match. Several applications require matched patches to be coherent. Upsampling maintains coherency  but including other cues in our framework is part of the future work. We further  wish to explore matching patches across arbitrary rotations and scale and in  videos.

We hypothesize that the Mixed-Resolution approach has application in several other problems. We encourage researches to explore the applicability of this idea in other tasks of image editing and computer vision.

Key Reference:
S. Korman and S. Avidan. Coherency Sensitive Hashing (CSH). International Conference on Computer Vision, 2011.

BibTex
@article{sureka_mrpm2012,
  author  = {Harshit Sureka and P. J. Narayanan},
  title   = {Mixed-Resolution Patch-Matching},
  journal = {European Conference on Computer Vision (ECCV)},
  year    = {2012},
  volume  = {Part VI},
  number  = {LNCS 7577},
  pages   = {187--198},
  month   = {October}
}

©Harshit Sureka, October 1 2012