Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2002-01-23
2004-07-13
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S583000, C345S584000, C345S587000, C345S588000, C382S284000
Reexamination Certificate
active
06762769
ABSTRACT:
BACKGROUND
1. Technical Field
The invention is related to a system for efficiently synthesizing textures from an input sample, and in particular, to a system and method for real-time synthesis of high-quality textures using a patch-based sampling system designed to avoid potential feature mismatches across patch boundaries.
2. Related Art
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. Simply stated, the texture synthesis problem may be described as follows: Given an input sample texture, synthesize an output texture that is sufficiently different from the input sample texture, yet appears perceptually to be generated by the same underlying stochastic process.
For example, one conventional scheme uses a texture synthesis approach that, although based on a Markov Random Field (MRF) model of a given input texture, avoids explicit probability function construction and consequent sampling from it. This is accomplished by generating the output image pixel by pixel in scanline order, choosing at each step a pixel from the sample image which neighborhood is most similar with respect to a specified measure to the currently available neighborhood in the texture being synthesized. However, this scheme suffers from several problems, including a relatively slow processing speed for generating textures, and a tendency to blur out finer details and well-defined edges for some textures. Further, this scheme also tends to run into problems in cases where the texture to be synthesized consists of an arrangement of relatively small objects such as leaves, flowers, pebbles, etc.
A related scheme expands on the aforementioned scheme by providing for verbatim copying and use of small pieces, or “patches” of the input sample, rather than use of individual pixels, for synthesizing the output texture. Patches are sampled from a local probability density function (PDF) using a non-parametric sampling algorithm that works well for a wide variety of textures ranging from regular to stochastic. Visual masking is used to hide the seams between the patches. However, while faster than the aforementioned scheme, this scheme is also too slow to be useful for generation of textures in real-time. Further, this scheme also suffers from a problem whereby noticeable visual artifacts can be created in the output texture. Further, depending upon the input texture, in certain cases this scheme produces output textures the bear little resemblance to the input texture and thus have little or no photo-realism.
Another conventional scheme provides a special purpose texture synthesis algorithm that is well suited for a specific class of naturally occurring textures. This class includes quasi-repeating patterns consisting of small objects of familiar but irregular size, such as flower fields, pebbles, forest undergrowth, bushes and tree branches. However, while this scheme performs fairly well with “natural textures”; it performs poorly for other textures, such as textures that are relatively smooth or have more or less regular structures such as, for example, clouds, or brick walls. In addition, this scheme is also too slow to be useful for real-time synthesis of textures.
Some of the aforementioned problems with synthesis of various texture types have been addressed by another conventional scheme that uses patch-based sampling to generate textures from an input sample. In particular, this scheme works well on stochastic textures such as, for example, a sample texture input comprising a group of small pebbles. However, where the sample texture has a more or less regular structure, such as a brick wall, or a tire tread, this patch pasting algorithm fails to produce good results because of mismatched features across patch boundaries.
Therefore, what is needed is a system and method for reliably synthesizing realistic textures for a given input sample. Such texture synthesis should be capable of generating textures for a variety of input texture types ranging from regular to stochastic. Further, such a system and method should be capable of generating textures quickly enough so as to operate in real-time.
SUMMARY
The present invention involves a new system and method which solves the aforementioned problems, as well as other problems that will become apparent from an understanding of the following description by providing a novel approach for synthesizing textures from an input sample using patch-based sampling. A patch-based sampling system and method according to the present invention operates to synthesize high-quality textures in real-time using a relatively small input texture sample. The patch-based sampling system of the present invention works well for a wide variety of textures ranging from regular to stochastic. Further, potential feature mismatches across patch boundaries are avoided by sampling patches according to a non-parametric estimation of the local conditional Markov Random Field (MRF) density function.
The system and method of the present invention is applicable to both constrained and unconstrained texture synthesis using either regular or stochastic input textures. Examples of constrained texture synthesis include hole filling, and tileable texture synthesis. In addition, in one embodiment, as described herein, the patch-based sampling system and method of the present invention includes an intuitive randomness parameter that allows an end user to interactively control a perceived randomness of the synthesized texture.
Conventional texture synthesis schemes typically fall into one of two categories. First, one class of texture synthesis schemes compute global statistics in feature space and sample images from a texture ensemble directly. A second approach involves estimating a local conditional probability density function (PDF), then synthesizing pixels incrementally to produce an output image. The texture synthesis system and method provided by the present invention follows the second approach. Specifically, the present invention includes estimation of a local conditional PDF rather than computing global statistics in feature space and sampling images from a texture ensemble directly.
In accordance with the present invention, a Markov Random Field (MRF) is used as a texture model, and it is assumed that the underlying stochastic process is both local and stationary. The MRF is preferred because it is known by those skilled in the art to accurately model a wide range of textures. However, other more specialized conventional models, including, for example, reaction-diffusion, frequency domain, and fractals, may also be used in alternate embodiments of a system and method according to the present invention.
Note that for purposes of clarity and ease of explanation, the texture patches described herein are described as square in shape. However, it should be appreciated by those skilled in the art that any shape of texture patch, such as, for example, a rectangle, triangle, circle, oval, or any other geometric shape may be used in accordance with the system and method described herein.
Texture synthesis, according to the present invention, includes the following elements: First, the size of the texture patches that will be used for texture synthesis is determined. This determination is made either manually, or it is made automatically using conventional texture analysis techniques. Typically, as is well known to those skilled in the art, the optimum size of the texture patches is a function of the size of texture eleme
Guo Baining
Liang Lin
Shum Heung-Yeung
Xu Ying-Qing
Bella Matthew C.
Chen Po-Wei
Lyon & Harr LLP
Microsoft Corporation
Watson Mark A.
LandOfFree
System and method for real-time texture synthesis using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for real-time texture synthesis using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for real-time texture synthesis using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3226760