Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2001-08-03
2004-03-02
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
Reexamination Certificate
active
06700585
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention is related to computer graphics and more particularly to a system and method for synthesis of parametric texture map (PTM) textures.
2. Background
Various techniques have been utilized to render graphical images via computer systems. One representation of visual images is referred to as a texture. A texture refers to a graphics data structure which models the surface appearance of an object. A texture may represent the visual experience of many materials and substances (e.g., terrain, plants, minerals, fur, and skin). Textures may be created digitally by sampling a physical surface utilizing photographic techniques. Alternatively, textures may be created manually utilizing a suitable graphics design application.
Texture synthesis refers to creating a new texture of a selected size from a sample texture of a fixed size. For example,
FIG. 1A
depicts exemplary texture
101
. Texture
101
includes a distribution of diamonds and stars. Although the diamonds and stars appear to be distributed in a semblance of order, a degree of randomization is apparent. The diamonds and stars seem to be arranged according to a stochastic process.
FIG. 1B
depicts exemplary synthesized texture
102
. Synthesized texture
102
is not merely an enlarged or upscaled version of texture
101
. Synthesized texture
102
possesses approximately the same degree of detail per unit of area as texture
101
. The distribution of diamonds and stars in synthesized texture
102
does not exactly correspond to the distribution in texture
101
. However, it appears that the same stochastic process has generated the distribution of synthesized texture
102
.
Synthesizing a new texture that appears to a observer to have been generated from the same stochastic process may be quite challenging. In particular, interpolation techniques (such as Fourier coefficient algorithms) are not helpful, because the level of visual detail as a function of area is not maintained in the larger synthesized texture. Moreover, boundary conditions present a number of difficulties. In particular, seams and repetitions may be visually evident thereby reducing the realism of the synthesized texture.
A texture synthesis algorithm has been developed by Li-Yi Wei and Marc Levoy which addresses the preceding texture synthesis issues. The algorithm is described in
Fast Texture Synthesis Using Tree
-
Structured Vector Quantization
, Li-Yi Wei and Marc Levoy, SIGGRAPH 2000 Conference Proceedings, pg. 479-488, which is incorporated herein by reference. The algorithm begins by utilizing a texture of a given size to generate a texture of some arbitrary larger size. Wei and Levoy describe (a) modeling or estimating the stochastic process associated with the original texture and (b) sampling from the original texture to synthesize or produce the new texture having the larger size. At a high level, the algorithm synthesizes the new texture by modeling the original texture using Markov Random Field concepts. The algorithm assembles the new texture in a pixel by pixel manner. Each pixel of the new matrix is determined by comparing its “neighborhood” to all neighborhoods in the original matrix.
Specifically, the synthesis algorithm taught by Wei and Levoy begins by receiving a data structure defining a texture. The data structure is a matrix of red, green, and blue (RGB) values defining the texture, where RGB is a well-known encoding method for representing the red, green, and blue chromatic channels of a pixel. A second matrix is created that is equal in size to the desired size of the texture to be synthesized. The second matrix is initialized with white random noise.
The algorithm proceeds by examining each pixel of the second matrix in raster scan order (e.g., from left to right and top to bottom). The algorithm transforms each pixel by first determining the neighborhood of each pixel. The neighborhood refers to a group of pixels that are relatively adjacent to the respective pixel of the second matrix. Also, the neighborhood is preferably chosen to be causal. Specifically, it is selected so that it only contains pixels that have already been synthesized and not pixels containing noise values. For example,
FIG. 1C
depicts exemplary matrix
103
. Matrix
103
comprises pixel
104
and exemplary neighborhood
105
. Neighborhood
105
only contains pixels that are previous to pixel
104
in the raster scan order. It shall be appreciated that this is not always possible. Accordingly, the first few pixels are allowed to contain neighborhoods with noise values. However, after a number of pixels have been synthesized, it is preferred to only utilize causal neighborhoods. Also, when a pixel is selected that is close to an edge of the matrix, the neighborhood may be selected in a toroidal manner, i.e., the neighborhood wraps around to the other side of the matrix.
The value of each respective pixel is assigned by comparing it to each pixel in the original matrix. Specifically, each pixel of the second matrix is assigned the color of the pixel in the original matrix that possesses a neighborhood that most closely matches the respective neighborhood of the pixel to be synthesized. The determination of most-closely matching neighborhoods is performed by utilizing a simple norm (sum of square differences) calculation. For example, R
1
, G
1
, B
1
may represent the red, green, and blue components or channels of a pixel in a neighborhood of the original or sample texture. R
2
, G
2
, B
2
may represent the red, green, and blue components or channels of a corresponding pixel in a neighborhood of the texture to be synthesized. The square of the difference equals (R
1
−R
2
)
2
+(G
1
−G
2
)
2
+(B
1
−B
2
)
2
. The sum of the differences then equals the summation of the previous calculation for each pixel pair between the two neighborhoods. The lowest norm corresponds to the most closely matching neighborhood.
Wei and Levoy also describe optimizations to the algorithm. First, multi-resolution synthesis is described to adapt to larger sized neighborhoods. The multi-resolution synthesis operates by building Gaussian pyramids from the original matrix and the noise matrix. A Gaussian pyramid is a hierarchy of low-pass filtered versions of the original image, such that successive levels correspond to lower frequencies. The Gaussian pyramid is produced by low-pass filtering via convolution with a Gaussian filter kernel. Although Gaussian pyramids are described, other pyramid or multi-resolution data structures may be utilized in lieu thereof. The algorithm proceeds by transforming the noise Gaussian pyramid from lower to higher resolutions. The only modification for the multi-resolution case is that each neighborhood contains pixels in the current resolution and all lower resolutions.
Wei and Levoy further describe acceleration of the algorithm utilizing tree-structured vector quantization (TSVQ). As described in
Vector Quantization and Signal Compression
, A. Gersho and R. M. Gray (1992), which is incorporated herein by reference, TSVQ is a well-known technique for data compression. The tree generated by TSVQ may be used as a data structure for efficient nearest-point queries. To find the nearest point of a given query vector, the tree is traversed from the root in a best-first ordering by comparing the query vector with the two children codewords and then following the one that has a closer codeword. This process is repeated for each visited node until a leaf node is reached. The best codeword is then returned as the codeword of that leaf node. Unlike full searching, the result codeword may not be the best or closest one, since only part of the tree is traversed. However, the result codeword usually approximates the exact solution, and the computation is more efficient than full searching.
To use TSVQ in the synthesis algorithm, the set of neighborhood pixels are collected for each input pixel and treated as a vector of a size equal to the number of pixels in the neighborh
Hewlett--Packard Development Company, L.P.
Razavi Michael
Yang Ryan
LandOfFree
System and method for synthesis of parametric texture map... 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 synthesis of parametric texture map..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for synthesis of parametric texture map... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3240672