Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-11-09
2001-03-13
Tran, Phuoc (Department: 2721)
Image analysis
Image compression or coding
Transform coding
C382S240000
Reexamination Certificate
active
06201897
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the transformation and selective inverse transformation of very large digital images that may consist of 1,000,000 or more pixels across, and of a potentially unlimited number of lines in length.
With the introduction of commercial one meter resolution satellites, and the need to mosaic multiple very high resolution images together to gain a regional view, the size of images has increased to the point that terabyte (2{circumflex over ( )}40) and larger digital images are becoming common. The term “digital image”refers to any form of data that can be represented using a two or more dimensional grid. Other types of high volume imagery include seismic surveys and hyperspectal imagery.
The need to transform, compress, transmit and/or store, and then decompress and inversely transform selective areas of such large digital images is an essential requirement in many applications, such as for GIS processing and for reception of imagery from satellites with limited transmission bandwidth and compute power.
PRIOR ART
Image transformation typically involves one or more steps of filtering that extract characteristics from an image by sifting the image components in a systematic way. In
FIG. 1
an original image I(x,y)
10
is filtered in a compound step in which a first filtered image I′
12
is produced by applying a filter to the image I and a second filtered image I″
14
is obtained by filtering the image I′. The image I (and the images I′ and I″) are illustrated as multi-dimensional arrays of picture elements, called “pixels”. Each pixel represents a correspondingly-located picture element of a visible image that may be observed by the eye. The image I is a two-dimensional array of pixels that is divided into horizontal elements. Each horizontal element—called a “line”—is one pixel high by n pixels long. In
FIG. 1
, the image
10
includes consecutive lines denoted as L
10
, L
11
, L
12
, L
13
and L
14
(among others). A pixel
11
is included for illustration in line L
10
, it being understood that every line is comprised of an equal number of pixels such as the pixel
11
. The pixels of the image
10
are digital numbers that represent the magnitudes of elements of visibility such as brightness, color content, and so on. Thus when applied in sequence to a digitally-driven display device, each pixel causes generation of a spot that is a portion of the image I at a corresponding location. These spots are the visual pixels that make up the visual image to which the digital image I(x,y) is the counterpart.
The image
10
may be filtered for a number of reasons, for example in order to eliminate one kind of information so that another type of information may be emphasized. Two kinds of filtration are lowpass filtration and highpass filtration. Lowpass filtration reduces or eliminates information above a certain frequency in an image. Highpass filtration does the opposite.
For purposes of illustration, the images
12
and
14
are illustrated in the same format as the image
10
, that is they are shown as being comprised of lines of pixels. The pixels of the filtered images
12
and
14
are produced by applying a filter to image pixels. Although the filters are, in practice, complex equations that receive the digital numbers representing pixels and produce digital numbers that are the pixels of the filtered images, it is useful for an understanding of this art to present the filters as discrete apparatuses that can be positioned on and moved with respect to the lines of an image.
Refer now to
FIGS. 1 and 1
a
. A filter
13
is applied to the unfiltered image I(x,y). As represented in
FIG. 1
a
, and by example, the filter
13
could have three components, denoted as a, b, and c. These components arc termed “filter coefficients”, and each is represented in a filter equation by a number. The filter
13
is oriented vertically with respect to the image
10
so that it spans three lines. To filter the image
10
, the filter is advanced along the three lines, producing, at each pixel position a filter output in the form of a digital number. The digital number output by the filter
13
is a combination of three products. Each product is obtained by multiplying the value of a coefficient by the digital number of the pixel (P) with which the coefficient is aligned. The combination of products may be arithmetic or algebraic; for example, it may be produced by adding the signed values of the products. Each filter output is the digital number for a pixel in a filtered image. In this example, assume that the filter output P′ is the digital value for the pixel of the filtered image
12
at the location that corresponds to the pixel aligned with the coefficient b. As the filter
13
is advanced through the image
10
along the lines that it spans (three in this example), toward the right edge, it produces a line of pixels for the filtered image
12
. When the filter
13
reaches the right edge of the image
10
, its position is shifted downward (by one line in this example) and it is returned to the left edge of the image
10
. Now it is moved (“scanned”) from left to right along the lines L
12
, L
13
, L
14
of the image
10
to produce the next line of pixels for the filtered image
12
. In this manner, the image
12
would be produced by scanning the filter
13
along the lines of the image
10
in a sequence from the upper left hand corner of the image in the manner described until the pixel at the lower right-hand corner of the image
10
has been filtered. At the upper and lower edges of the image
10
, the filter
13
is positioned so that the coefficient b is aligned with the line at the edge. Along the upper edge, the product produced by the coefficient a would be assigned a predetermined value; similarly, along the lower edge, the product produced by the coefficient c would be assigned a predetermined value.
Assume for illustration that the filtered image I″ is produced by a filter
15
that has three coefficients and that is oriented vertically on the image I′. Assume further that the line L
12
″ is produced by the filter
15
scanning the three lines L
11
′, L
12
′, L
13
′. In turn, each of these lines is produced by filtering three corresponding lines of the unfiltered image I(x,y). For example, the line L
11
′ is produced by filtering the lines L
10
, L
11
, and L
12
. Manifestly, in order to produce line L
12
′, three lines of the image I′ must be available, that is the lines L
11
′, L
12
′ and L
13
′; in turn, in order to produce these three lines, five lines of the unfiltered image I(x,y) must be available—the lines L
10
, L
11
, L
12
, L
13
and L
14
. In the prior art, advantage has been taken of this relationship.
FIG. 1
illustrates a prior art compound filter apparatus that is incorporated into the ER Mapper product produced by the assignee of this application. In the prior art compounded filtration apparatus of
FIG. 1
, the filters
13
and
15
are implemented algorithmically in filter functions
16
and
18
. As an input to each filter function (or as an integral component thereof), a buffer is provided that stores only the consecutive image lines of the preceding image that are necessary to perform the filter function. Thus, the buffer
16
a
needs a capacity of only five lines of the unfiltered image I(x,y), while the buffer
18
a
needs a capacity of only three lines of the filtered image I′. Further, the buffers
16
a
and
18
a
are managed in real time in such a manner as to reduce the memory requirements for a processor performing the filter functions
16
and
18
. Thus, as the unfiltered image I(x,y) is being acquired line-by-line, the buffer
16
a
is managed as a first in—first out (FIFO) queue to store the five lines of the image
10
that are necessary to produce the three lines of image
12
that will produce the one line of the image
14
. Similarly, the buffer
18
a
is managed as a three-
Earth Resource Mapping
Gray Cary Ware & Freidenrich
Tran Phuoc
LandOfFree
Transformation and selective inverse transformation of large... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transformation and selective inverse transformation of large..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transformation and selective inverse transformation of large... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444073