Graphics Reference
In-Depth Information
3.4.2
Patch-Based Methods
A promising class of inpainting methods incrementally fills in patches of the target
region
by copying patches from the surrounding image. That is, the region outside
the hole,
, acts as a source region for the appearance of new patches inside
the hole. Here, we present the algorithm proposed by Criminisi et al. [
108
], which is
effective and easy to understand. Until the target region is completely filled in, we
iterate over the following steps:
=
I
−
1. Determine a priority
P
(
p
)
for every pixel
p
∈
∂
.
2.
Select the pixel
p
with highest priority and denote the
W
ˆ
×
W
patch of pixels
p
. A typical value for
W
is 9.
3. Find the patch of pixels
centered around it as
q
⊂
that best matches
p
.
4. Overwrite the pixels in
p
∩
with the corresponding pixels from
q
, and
shrink the target region
accordingly.
One cycle of the process is illustrated in Figure
3.20
.
The first step, computing the priorities of the pixels on the boundary of the fill
front, is the most important. Criminisi et al. proposed that the priority be the product
of a
confidence term
C
(
)
(
)
. The confidence term is high when
the pixel is surrounded by many pixels whose intensities are already known. For
example, the point
A
at the end of the “peninsula” in Figure
3.21
a is a good candidate
for filling in since it juts out into a region of known pixels. On the other hand, the
point
B
at the end of the “dent” in Figure
3.21
a is a bad candidate for filling in since
almost all the pixels in its neighborhood are unknown. Initially, we set the confidence
C
p
and a
data term
D
p
(
p
)
=
0 for all
p
∈
, and
C
(
p
)
=
1 for all
p
∈
. Then
C
(
p
)
for any point on the fill
Φ
Ω
Ψ
^
Ψ
^
(a)
(b)
Figure 3.20.
One cycle of patch-based inpainting. (a) The patch of pixels
p
centered around
the pixel on the fill front with the highest priority is selected. The patch of pixels
q
⊂
that
best matches
p
is determined. (b) Pixels are copied from
q
to shrink the target region.
