Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-07-01
2003-03-18
Do, Anh Hong (Department: 2721)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S232000, C382S253000, C375S240010
Reexamination Certificate
active
06535644
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of image processing systems, and in particular to the communication and presentation of wavelet encoded images.
2. Description of Related Art
There are several ways to process information hierarchically. Wavelets offer a highly efficient framework for representing and processing hierarchically structured information or processes. In general terms, a wavelet representation of a function consists of a coarse overall approximation together with detail coefficients that influence the function at various scales. In image processing, wavelet encodings are used to encode images via a hierarchy of terms.
A variety of alternative wavelet encoding techniques are common in the art. An example wavelet encoding technique that uses straightforward average and difference terms is presented herein for ease of understanding. Two image elements, such as two pixel values a, b, can be encoded as two other values, Q, Z, where Q=(a+b)/2, the average term, and Z=(a−b), the difference term. To decode the values a, b, from the encodings Q, Z: a=Q+Z/2, and b=Q−Z/2. Four pixel values a
0
, b
0
, a
1
, a
2
can be represented as two pair of encodings Q
0
, Z
0
, Q
1
, Z
1
, and the two average terms Q
0
, Q
1
can be represented as encodings Q, Y, where Q is the average of Q
0
and Q
1
, and Y is the difference between Q
0
and Q
1
.
The use of wavelets offer a number of advantages and efficiencies. If all four pixel values are equal, the Q term will equal this value, and each of the difference terms Y, Z
0
, and Z
1
will be zero. Techniques are common in the art for very efficient encodings and representations of zero-laden encodings. Note also that, because the Q term represents the average of the pixel values, the Q term can be used in place of the four pixel values until the difference terms Y, Z
0
, and Z
1
are received and processed. That is, as the difference terms in a wavelet encoding are being processed, the average terms can be displayed, thereby presenting an image that iteratively becomes more and more detailed.
FIG. 1
illustrates an example wavelet encoding of a sixteen element block A
110
, each element
111
,
112
, . . . representing, for example, the value of a picture element (pixel) for rendering on a display screen. An index block
110
′ is shown in
FIG. 1
for ease of reference to the individual elements of block A
110
. That is, the upper left element
111
of block A
110
is referenced as a
0
, the next lower element
112
is referenced as a
1
, and so on.
Blocks B
120
and Z
130
represents the average and difference blocks corresponding to a pair-wise encoding of the individual elements of the block A
110
. That is, cell b
0
121
of block B
120
represents the average of elements a
0
111
and a
1
112
, and cell Z
0
131
of block Z
130
represents the difference of elements a
0
111
and a
1
112
.
Blocks C
140
and Y
150
represents the average and difference blocks corresponding to a pair-wise encoding of the individual elements of the block B
120
. That is, cell c
0
141
of block C
140
represents the average of elements b
0
121
and b
1
122
, and cell Y
0
151
of block Y
150
represents the difference of elements b
0
121
and b
1
122
.
In like manner, blocks D
160
and X
170
represent the average and difference blocks corresponding to block C
140
, and blocks E
180
and W
190
represent the average and difference blocks corresponding to block D
160
.
As discussed above, each of the cells of blocks E
180
, D
160
, C
140
, and B
120
represent the average value of the pixel elements of block A
110
contained within the respective cell. The single cell of block E
180
, for example, has a value of 0.625, which is the average of all the pixel elements of block A. The upper left cell c
0
141
of block C
140
has a value of 0, which is the average of all the pixel elements of block A in the upper left region ((2+0+(−3)+1)/4). Thus, a display of blocks E
180
, D
160
, C
140
, B
120
, and A
110
, in that order, will present a progressively more detailed, or finer-resolution, view of the image represented by the pixel elements of block A
110
.
Note that the values of the cells of the block D
160
can be determined from the value of block E
180
and W
190
, as discussed above, and as illustrated in FIG.
2
. That is, d
0
=E+W/2, and d
1
=E−W/2. In like manner, the value of the cells of block C
140
can be determined from the value of this determined block D
160
and the difference block X
170
; block B
120
can be determined from C
140
and Y
150
; and block A
110
can be determined from B
120
and Z
130
. Thus, the communication of blocks E
180
, W
190
, X
170
, Y
150
, and Z
130
is sufficient to communicate the sixteen element values a
0
-a
15
of block A
110
. Note also that the blocks E
180
and W
190
contain one value each; X
170
contains two values; Y
150
contains four values; and Z
130
contains eight values. Thus, the communication of blocks E
180
, W
190
, X
170
, Y
150
, and Z
130
require the communication of a total of sixteen values, the same number of values contained in the original block A
110
.
Wavelets are commonly used to communicate images so that increasingly more detailed views of the image can be displayed while the more detailed information is being received. This provides the advantage of providing a distraction to the viewer while the image is being downloaded, as well as to allow the user to terminate the transmission when it is determined that a sufficient amount of detail has been communicated.
BRIEF SUMMARY OF THE INVENTION
It is an object of this invention to exploit the progressive-resolution characteristics of wavelets to provide a rendering of an image, or images, that takes advantage of the human perceptive system.
As is known in the field of art, a human's visual field is typically drawn to a focal point, or focal area, within a scene. As the radial distance from that focal area increases, the human perceives less and less detail. This phenomenon is termed foveation. Artists purposely add a detail or feature to define such a focal point, to either bring the user's attention specifically to the feature, or to put the scene in proper perspective, or to diminish the distracting effects caused by a lack of focus. Commercial artists take advantage of this phenomenon in advertising to draw the viewer's attention to the item being advertized. Internet advertising is becoming increasingly popular, with multiple advertisers typically vying for a viewer's attention. Copending U.S. patent application “EVOLVING ADVERTISEMENTS VIA AN EVOLUTIONARY ALGORITHM”, U.S. Ser. No. 09/277,650, filed Mar. 26, 1999, for J. David Schaffer, provides a method for evaluating and evolving an advertising campaign based on measures of viewer interest, including the number of users who select the advertised page, and so on, and is included by reference herein.
In like manner, computer applications are being developed to assist users in locating items of potential interest among a multitude of available items. Copending U.S. patent application “DEVICE AND METHOD FOR A LATTICE DISPLAY”, U.S. Ser. No. 09/282,321, filed Mar. 31, 1999, for Jacquelyn Martino, Nevenka Dimitrova, and Kaushal Kurapati, presents a system for displaying multiple images in a hierarchical manner, depending upon a measure of each image's potential interest to the viewer, and is incorporated by reference herein. In this referenced patent application, images having a high potential interest to the user are presented with more prominence than others, where prominence is effected via the image's size, location, resolution, brightness, border trim, and so on.
The expressed object of this invention, and others are achieved by providing a method and apparatus for rendering wavelets in a hierarchical manner. Different images,
LandOfFree
Hierarchical foveation based on wavelets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical foveation based on wavelets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical foveation based on wavelets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3083861