没有合适的资源?快使用搜索试试~ 我知道了~
首页Real-Time Texture Synthesis by Patch-Based Sampling基于样图的纹理合成
Real-Time Texture Synthesis by Patch-Based Sampling基于样图的纹理合成
需积分: 41 9 下载量 44 浏览量
更新于2023-07-05
收藏 6.42MB PDF 举报
Real-Time Texture Synthesis by Patch-Based Sampling基于样图的纹理合成 论文
资源详情
资源推荐
Real-Time Texture Synthesis by
Patch-Based Sampling
LIN LIANG, CE LIU, YING-QING XU, BAINING GUO,
and HEUNG-YEUNG SHUM
Microsoft Research China, Beijing
We present an algorithm for synthesizing textures from an input sample. This patch-based sampling
algorithm is fast and it makes high-quality texture synthesis a real-time process. For generating
textures of the same size and comparable quality, patch-based sampling is orders of magnitude
faster than existing algorithms. The patch-based sampling algorithm works well for a wide variety
of textures ranging from regular to stochastic. By sampling patches according to a nonparametric
estimation of the local conditional MRF density function, we avoid mismatching features across
patch boundaries. We also experimented with documented cases for which pixel-based nonpara-
metric sampling algorithms cease to be effective but our algorithm continues to work well.
Categories and Subject Descriptors: I.2.10 [Artificial Intelligence]: Vision and Scene Understand-
ing—texture; I.3.3 [Computer Graphics]: Picture/Image Generation; I.4.7 [Image Processing
and Computer Vision]: Feature Measurement—texture
General Terms: Algorithms
Additional Key Words and Phrases: Texture synthesis, patch-pasted nonparametric sampling
1. INTRODUCTION
Texture synthesis has a variety of applications in computer vision, graphics, and
image processing. An important motivation for texture synthesis comes from
texture mapping. Texture images usually come from scanned photographs, and
the available photographs may be too small to cover the entire object surface.
In this situation, a simple tiling will introduce unacceptable artifacts in the
forms of visible repetition and seams. Texture synthesis solves this problem by
generating textures of the desired sizes. Other applications of texture synthesis
include various image processing tasks such as occlusion fill-in and image/
video compression.
The texture synthesis problem may be stated as follows. Given an input sam-
ple texture I
in
, synthesize a texture I
out
that is sufficiently different from the
given sample texture, yet appears perceptually to be generated by the same
underlying stochastic process. In this work, we use the Markov Random Field
Authors’ address: Microsoft Research China, 5F, Beijing Sigma Center, No. 49., Zhichun Road,
Haidian District, Beijing, 100080, PRC; email: bainguo@microsoft.com.
Permission to make digital/hard copy of part or all of this work of personal or classroom use is
granted without fee provided that the copies are not made or distributed for profit or commercial
advantage, the copyright notice, the title of the publication, and its date appear, and notice is given
that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers,
or to redistribute to lists, requires prior specific permission and/or a fee.
C
°
2001 ACM 0730-0301/01/0700-0127 $5.00
ACM Transactions on Graphics, Vol. 20, No. 3, July 2001, Pages 127–150.
128
•
L. Liang et al.
(MRF) as our texture model and assume that the underlying stochastic pro-
cess is both local and stationary. We choose MRF because it is known to ac-
curately model a wide range of textures. Other successful but more special-
ized models include reaction-diffusion [Turk 1991; Witkin and Kass 1991], fre-
quency domain [Lewis 1984], and fractals [Fournier 1982; Worley 1996] (see also
Perlin [1985]).
In recent years, a number of successful texture synthesis algorithms have
been proposed in graphics and vision. Motivated by psychology studies, Heeger
and Bergen [1995] developed a pyramid-based texture synthesis algorithm
that approximately matches marginal histograms of filter responses. Zhu et al.
[1997, 1998] introduced a mathematical model called FRAME, which integrates
filters and histograms into MRF models and uses a minimax entropy princi-
ple to select feature statistics. Several texture synthesis algorithms are based
on matching joint statistics of filter responses. De Bonet’s [1997] algorithm
matches the joint histogram of a long vector of filter responses. Portilla and
Simoncelli [1999] developed an iterative projection method for matching the
correlations of certain filter responses. These methods, along with many oth-
ers in the literature [Iverson and Lonnestad 1994; Wu et al. 2000], represent
two different approaches to texture synthesis. The first is to compute global
statistics in feature space and sample images from the texture ensemble [Zhu
et al. 2000] directly.
1
The second approach is to estimate the local conditional
probability density function (PDF) and synthesize pixels incrementally [Zhu
et al. 1997].
The texture synthesis algorithm we propose follows the second approach. In
their pioneer work, Zhu et al. [1997] explored this approach using the analyt-
ical FRAME model and an accurate but expensive Markov chain Monte Carlo
method. More recently, Efros and Leung [1999] demonstrated the power of
sampling from a local PDF by presenting a nonparametric sampling algorithm
that works well for a wide variety of textures ranging from regular to stochas-
tic. Efros and Leung’s algorithm, while much faster than Zhu et al. [1997],
is still too slow. Inspired by a cluster-based texture model [Popat and Picard
1993], Wei and Levoy [2000] significantly accelerated Efros and Leung’s algo-
rithm using tree-structured vector quantization (TSVQ). However, this TSVQ-
accelerated nonparametric sampling algorithm is still not real-time. Another
problem with Efros and Leung [1999] and Wei and Levoy [2000] is that they
break down for some textures. Efros and Leung [1999] attribute the problem
of their algorithm to the fact that it is a greedy algorithm and it can “slip”
into a wrong part of the search space and start to grow “garbage.” Wei and
Levoy’s algorithm also suffers quality problems. Ashikhmin [2001] noted the
quality problems of Wei and Levoy’s algorithm on a class of textures and has
developed a special-purpose algorithm for that class. It is possible to combine
Ashikhmin’s algorithm with that of Wei and Levoy, as Hertzmann et al. [2001]
have done.
1
Please also see Heeger and Bergen [1995], DeBonet [1997], Portilla and Simoncelli [1999], and
Zhu et al. [2000].
ACM Transactions on Graphics, Vol. 20, No. 3, July 2001.
Patch-Based Sampling
•
129
Fig. 1. Texture synthesis example: (a) 192 × 192 input sample texture; (b) 256 × 256 texture
synthesized by patch-based sampling. The synthesis takes 0.02 seconds on a 667 MHz PC.
In this article we show that high-quality texture can be synthesized in real-
time on a midlevel PC. A key ingredient of our patch-based sampling algorithm
is a sampling scheme that uses texture patches of the sample texture as build-
ing blocks for texture synthesis. The patch-based sampling algorithm is fast.
For synthesizing textures of the same size and comparable (or better) quality,
our algorithm is orders of magnitude faster than existing texture synthesis al-
gorithms including Wei and Levoy [2000]. Figure 1 shows an example produced
by our algorithm. After spending 0.6 seconds analyzing the input sample, our
algorithm took 0.02 seconds to synthesize this texture on a 667 MHz PC. The
patch-based sampling algorithm works well for a wide variety of textures rang-
ing from regular to stochastic. We examined documented cases for which Efros
and Leung [1999], Wei and Levoy [2000], and Ashikhmin [2001] cease to be
effective and have found that our algorithm continues to produce good results.
In particular, the texture patches in our sampling scheme provide implicit con-
straints for avoiding garbage as found in some textures synthesized by Efros
and Leung [1999].
The patch-based sampling algorithm is an extension of our earlier work on
texture synthesis by random patch pasting [Xu et al. 2000]. Praun [2000] has
successfully adapted this patch-pasting algorithm for texture mapping on 3-D
surfaces. Unfortunately, these patch-pasting algorithms suffer from mismatch-
ing features across patch boundaries. The patch-based sampling algorithm, on
the other hand, avoids mismatching features across patch boundaries by sam-
pling texture patches according to the local conditional MRF density. Patch-
based sampling includes patch pasting as a special case, in which the local
PDF implies a null statistical constraint.
Patch-based sampling is amenable to acceleration and the fast speed of our al-
gorithm is partially attributable to our carefully designed acceleration scheme.
The core computation in patch-based sampling can be formulated as a search for
approximate nearest neighbors (ANN). We accelerate this search by combining
ACM Transactions on Graphics, Vol. 20, No. 3, July 2001.
130
•
L. Liang et al.
an optimized technique for general ANN search, a novel data structure called
the quadtree pyramid for ANN search of images, and principal components
analysis of the input sample texture.
The patch-based sampling algorithm is easy to use and flexible. It is ap-
plicable to both unconstrained and constrained texture synthesis. Examples of
constrained texture synthesis include hole filling and tileable texture synthesis.
The patch-based sampling algorithm has an intuitive randomness parameter.
The user can utilize this parameter to interactively control the randomness of
the synthesized texture.
In concurrent work, Efros and Freeman [2001] developed a texture quilting
algorithm. For unconstrained texture synthesis, texture quilting is very similar
to patch-based sampling. There are several differences between our work and
that of Efros and Freeman [2001]. First, we accelerate patch-based sampling
and demonstrate that it can run in real-time, whereas they do not explore the
issue of speed. Second, we show how to solve constrained texture synthesis prob-
lems, which they do not address. Finally, patch-based sampling and Efros and
Freeman [2001] use different techniques to improve the transitions between
texture patches. We apply feathering [Szeliski and Shum 1997] while Efros
and Freeman use a minimum error boundary cut. Later, we compare these two
boundary treatment techniques in detail.
The rest of the article is organized as follows. In Section 2, we introduce
patch-based sampling and its applications to unconstrained and constrained
texture synthesis. In Section 3, we present our acceleration techniques. The
texture synthesis results and speed are discussed in Section 4, followed by
conclusions and suggestions for future work in Section 5.
2. PATCH-BASED SAMPLING
The patch-based sampling algorithm uses texture patches of the input sample
texture I
in
as the building blocks for constructing the synthesized texture I
out
.
In each step, we paste a patch B
k
of the input sample texture I
in
into the synthe-
sized texture I
out
. To avoid mismatching features across patch boundaries, we
carefully select B
k
based on the patches already pasted in I
out
, {B
0
, ..., B
k−1
}.
The texture patches are pasted in the order shown in Figure 3. For simplicity,
we only use square patches of a prescribed size w
B
× w
B
.
2.1 Sampling Strategy
Let I
R
1
and I
R
2
be two texture patches of the same shape and size. We say that
I
R
1
and I
R
2
match if d(R
1
, R
2
) <δ, where d() represents the distance between
two texture patches and δ is a prescribed constant.
Assuming the Markov property, the patch-based sampling algorithm esti-
mates the local conditional MRF (FRAME or Gibbs) density p(I
R
| I
∂ R
)ina
nonparametric form by an empirical histogram. Define the boundary zone ∂ R
of a texture patch I
R
as a band of width w
E
along the boundary of R as shown
in Figure 2. When the texture on the boundary zone I
∂ R
is known, we would
like to estimate the conditional probability distribution of the unknown texture
patch I
R
. Instead of constructing a model, we directly search the input sample
ACM Transactions on Graphics, Vol. 20, No. 3, July 2001.
Patch-Based Sampling
•
131
Fig. 2. A patch-based sampling strategy. In the synthesized texture shown in (b), the hatched area
is the boundary zone. In the input sample texture shown in (a), three patches have boundary zones
matching the texture patch I
R
in (b) and the red patch is selected.
texture I
in
for all patches having the known I
∂ R
as their boundary zones. The
results of the search form an empirical histogram 9 for the texture patch I
R
.
To synthesize I
R
, we just pick an element from 9 at random. Mathematically,
the estimated conditional MRF density is
p(I
R
| I
∂ R
) =
X
i
α
i
δ(I
R
− I
R
i
),
X
i
α
i
= 1,
where I
R
i
is a patch of the input sample texture I
in
whose boundary zone I
∂ R
i
matches the boundary zone I
∂ R
and δ() is Dirac’s delta. The weight α
i
is a
normalized similarity scale factor.
With patch-based sampling, the statistical constraint is implicit in the bound-
ary zone ∂ R. A large boundary zone implies a strong statistical constraint. Gen-
erally speaking, a nonparametric local conditional PDF such as in Efros and
Leung [1999] and Wei and Levoy [2000] is faster to estimate than the analyt-
ical FRAME model in Zhu et al. [1997]. On the down side, the nonparametric
density estimation is subject to greater statistical fluctuations, because in a
small sample texture I
in
there may be only a few sites that satisfy the local
statistical constraints.
2.2 Unconstrained Texture Synthesis
Now we use the patch-based sampling strategy to choose the texture patch B
k
,
the kth texture patch to be pasted into the output texture I
out
.
As Figure 3(a) shows, only part of the boundary zone of B
k
overlaps the
boundary zone of the already pasted patches {B
0
, ...,B
k−1
} in I
out
.Wesay
that two boundary zones match if they match in their overlapping region. In
Figure 3(a), B
k
has a boundary zone E
B
k
of width w
E
. The already pasted
patches in I
out
also have a boundary zone E
k
out
of width w
E
. According to the
patch-based sampling strategy, E
B
k
should match E
k
out
.
For the randomness of the synthesized texture I
out
, we form a set 9
B
con-
sisting of all texture patches of I
in
whose boundary zones match E
k
out
. Let B
(x, y)
ACM Transactions on Graphics, Vol. 20, No. 3, July 2001.
剩余23页未读,继续阅读
秋水长天点点滴滴
- 粉丝: 9
- 资源: 56
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功