Image Completion with Structure Propagation
Boris Indelman & Omri Lavi
Project Supervisor: Gur Harary
Completing unknown
"holes" in an image is a challenging task. In this project a novel
approach to image completion will be tested. In this approach the user manually
specifies important missing structure information by extending a few curves from
the known to the unknown regions. The algorithm then synthesizes image patches
along these user-specified curves in the unknown region using patches selected
around the curves in the known region. The remaining unknown regions are filled
using patch-based texture synthesis.
In our approach we assume that:
n For For natural images, the most salient missing
structures can often be approximated by a few well-defined curves.
n There exists a synthesis ordering for image
completion:
n the regions with salient structures should be completed
n filling in other regions.
Our image completion works in three
steps:
n user interaction to specify the curves
n structure propagation to synthesize regions with
salient structures
n and texture propagation to fill in the remaining
unknown regions
We introduce the concept of structure propagation using a single
curve C specified by the user. The problem we address is how to synthesize
missing structure and texture along curve C in the unknown region by using samples
around the curve in the known region. Applying structure propagation for
multiple non-intersecting curves is straightforward.
Figure 1
We thus consider structure propagation as a graph labeling problem.
For each anchor position pi, we find a label xi ∈{1, 2, ...,N} corresponding to one
of the sample patches. We select the
sample patch P(xi) from P, and paste it at point pi as shown in Figure 1.
Energy Minimization :
We define the following energy on G
E(X) =Xi∈V E1(xi) + X (i,j)∈EE2(xi, xj), (1)
Where
E1(xi) = ks ・ ES(xi) + ki
・ EI (xi). (2)
ES(xi), EI (xi) and E2(xi, xj) are energy terms for structure, completion,
and coherence constraints, respectively.Minimization
ES(xi) encodes the structure similarity between the source patch
and the structure indicated by the user at each node i as shown in figure 2.
Figure 2
EI (xi) constrains the synthesized patches on the boundary of
unknown region to match well with the
known pixels, as shown in the green box in Figure 3.
E2(xi, xj) encodes the coherence constraint between two adjacent
synthesized patches P(xi) and P(xj), where xi and xj are labels for adjacent
nodes, as shown in the red box in Figure 3.
Figure 3
Algorithm Flow Chart:
Dynamic programming (DP)
Since G is a single chain, minimizing the energy E(X) for
structure propagation can be regarded as searching for a minimal cost path with
dynamic programming
Belief Propagation (BP)
Why BP?
n Multiple
Intersecting Curves
n Complexity
of DP >> Complexity of BP
Belief
propagation is a probability inference algorithm proposed by Pearl [1988] that
has become popular lately in machine learning and computer vision (e.g.,
[Freeman et al. 2000]). Belief propagation is a local message passing algorithm
that can minimize the Gibbs energy defined on any pair wise undirected graph,
e.g., our energy (X). he basic mechanism
of belief propagation is for each node in a graph to receive messages from its
neighbors, then to send updated messages back to each of them.
Results:
Conclusions:
n By using an
intuitive interface and efficient optimization algorithms, our system
effectively integrates human knowledge into the completion process to produce
good results even for many challenging images.
n Allows the
user to control the completion process for image editing applications.
n if there
are not enough samples in the image, it will be impossible to synthesize the
desired structure or texture.
n works well
only if the missing salient structures can be represented by a set of simple
curves.
Project Book and Presentation: