1 of 43

PatchMatch Algorithm

DIPA Final Project

​

2 of 43

Introduction

Google

Cisco

Netscope

1150

3000

1800

3 of 43

PatchMatch Algorithm

  • Efficiently find the similar patch

* C. Barnes, E. Shechtman, A. Finkelstein, and D. Goldman. Patchmatch: a randomized correspondence algorithm for structural image editing. TOG, 2009.

  1. Random Initialization
  1. Random Search
  1. Propagation

Iteration Process

A

B

  1. Random Initialization

4 of 43

PatchMatch Algorithm

  • Efficiently find the similar patch

* C. Barnes, E. Shechtman, A. Finkelstein, and D. Goldman. Patchmatch: a randomized correspondence algorithm for structural image editing. TOG, 2009.

  1. Random Initialization
  1. Random Search
  1. Propagation

Iteration Process

A

B

  1. Propagation

5 of 43

PatchMatch Algorithm

  • Efficiently find the similar patch

* C. Barnes, E. Shechtman, A. Finkelstein, and D. Goldman. Patchmatch: a randomized correspondence algorithm for structural image editing. TOG, 2009.

  1. Random Initialization
  1. Random Search
  1. Propagation

Iteration Process

A

B

  1. Propagation

6 of 43

PatchMatch Algorithm

  • Efficiently find the similar patch

* C. Barnes, E. Shechtman, A. Finkelstein, and D. Goldman. Patchmatch: a randomized correspondence algorithm for structural image editing. TOG, 2009.

  1. Random Initialization
  1. Random Search
  1. Propagation

Iteration Process

A

B

  1. Random Search

7 of 43

PatchMatch Algorithm

  • Efficiently find the similar patch

* C. Barnes, E. Shechtman, A. Finkelstein, and D. Goldman. Patchmatch: a randomized correspondence algorithm for structural image editing. TOG, 2009.

  1. Random Initialization
  1. Random Search
  1. Propagation

Iteration Process

A

B

  1. Random Search

8 of 43

PatchMatch Algorithm

  • Efficiently find the similar patch

* C. Barnes, E. Shechtman, A. Finkelstein, and D. Goldman. Patchmatch: a randomized correspondence algorithm for structural image editing. TOG, 2009.

  1. Random Initialization
  1. Random Search
  1. Propagation

Iteration Process

A

B

  1. Random Search

9 of 43

PatchMatch �Simulation Result

Original Image

Initialization

10 of 43

PatchMatch �Simulation Result

Original Image

1/4 iteration

11 of 43

PatchMatch �Simulation Result

Original Image

3/4 iteration

12 of 43

PatchMatch �Simulation Result

Original Image

1 iteration

13 of 43

PatchMatch �Simulation Result

Original Image

2 iterations

14 of 43

PatchMatch �Simulation Result

Original Image

3 iterations

15 of 43

PatchMatch �Simulation Result

Original Image

4 iterations

16 of 43

PatchMatch �Simulation Result

Original Image

5 iterations (SNR* = 27.860412)

ISO 12232: Electronic Still Picture Cameras

  • SNR: 32.04 dB = excellent image quality
  • SNR: 20 dB = acceptable image quality

 

17 of 43

Image Completion in PatchMatch Paper

18 of 43

Image Completion

Original Image

Image with Hole

19 of 43

PatchMatch for Image Completion

Bounding Box

20 of 43

PatchMatch for Image Completion

Bounding Box

21 of 43

PatchMatch for Image Completion

Bounding Box

22 of 43

How Big the Bounding Box Should Be?

    • As small as possible so that we won’t lose information

​

    • The smallest bounding box is given as mask extended by patch width
      • By dilating the mask

​

Bounding Box

23 of 43

Blur Issue

Output Image

24 of 43

How to Determine the Patch Size?

    • Big enough to see the global structure first

​

    • Small enough in the end so that it is aware of local smoothness

Image Pyramid

25 of 43

Improvement

Original Image

Previous result

26 of 43

Improvement

Original Image

Current result

27 of 43

Issues

  • Not working well if crossing some boundary of objects

Original Image

Mask

28 of 43

Issues

  • Not working well if crossing some boundary of objects

Original Image

Output Image

29 of 43

Incorporating Constraints

30 of 43

Improvement

Original Image

Previous result

31 of 43

Improvement

Original Image

Current result

32 of 43

Interactive GUI

33 of 43

Image Completion Results

Output Image

Original Image

34 of 43

Image Completion Results

Masked Image

Original Image

35 of 43

Image Completion Results

Masked Image

Original Image

36 of 43

Image Completion Results

Output Image

Original Image

37 of 43

Image Completion Results

Masked Image

Original Image

38 of 43

Image Completion Results

Output Image

Original Image

39 of 43

Image Completion Results

Original Image

Masked Image

40 of 43

Image Completion Results

Output Image

Original Image

41 of 43

Image Completion Results

Result of SIGGRAPH 2017

Original Image

42 of 43

Future Work

  • Adopt KNN rather than the most similar patch
  • Figure out a way for better initialization
  • Find how to determine patch size
  • Speed up our application to real time
  • Improve the sensitivity issues for initialization and patch size

​

43 of 43

Image Completion Results

Original Image

Ours