Information Technology Reference
In-Depth Information
•
Compute the error surface between the newly chosen block and the old blocks at
the overlap region. Find the minimum cost path along this surface and make that
the boundary of the new block. Paste the block onto the texture.
•
Repeat the above steps until the whole image is completed.
The minimal cost path through error surface of two overlapping blocks
B
1 and
B
2,
is calculated as follows. Taking the vertical overlaps for example, the error surface
is defined as
(B
ov
1
- B
ov
2
)
2
(
B
ov
1
and
B
ov
2
indicate the overlap regions). To find the
minimal vertical cut
through
this surface we traverse the error function
e(i,j)
and
compute the cumulative minimum error E for all paths:
E(i,j) = e(i,j) + min(E(i
-
1,j-1), E(i-1),j, E(i-1,j+1)) (1)
In the end, the minimum value of the last row in E will indicate the end of the
minimal vertical path though the surface and one can trace back and find the path of
the best cut. Similar procedure can be applied to horizontal overlaps. Fig. 1 gives an
intuitive outline of the IQ algorithm.
The sizes of the block and overlap are chosen by the user, and the block size must
be big enough to capture the relevant structures in the texture, but small enough so
that the interaction between these structures is left up to the algorithm. The size of
the overlap is usually chosen to be 1/6 of the size of the block in the original image
quilting algorithm. But in our implementation, we assign it to be 1/4 of the block
size. The error is computed using the L2 norm on pixel values. The error tolerance is
set to be within 1.1 times the error of the best matching block.
In IQ, the patch matching method is SSD (sum of squared difference), but this
method is computationally expensive (on the order of hours) if SSD computation is
carried out literally. However, it can be accelerated by
Fast Fourier Transform
(FFT)
[6].
2.1 Discussion
The IQ algorithm is a milestone of the development of texture synthesis. With such
a simple idea, it works extremely well for a wide range of textures. For regular
textures, see Fig. 2(a), 2(b), the patterns of the input textures are monotonously
repetitive, and the output images naturally preserve the repeatability of the input
images and give satisfying results. For irregular textures, see Fig. 2(c), since the
input texture is stochastic and no specific layout to preserve, this algorithm also
works well.
However, IQ has limitations in synthesizing textures consisting of an
arrangement of small objects. These textures are commonly available in the real
world. Fig. 2(d) depicts the result of IQ for a natural image composing two
