Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1992-07-22
2001-01-30
Couso, Yon J. (Department: 2723)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S251000
Reexamination Certificate
active
06181826
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed to the field of digital image processing and more particularly to apparatus and methods for quantizing and/or reconstructing multi-dimensional digital image signals.
BACKGROUND OF THE INVENTION
Efficient storage, transmission, processing, compression, etc. of digital signals or images requires that the amplitude, intensity, or gray scale values of each channel be quantized to discrete levels. The more aggressive the quantization (the fewer levels used), the less the storage or the more efficient the compression, etc. However, quantization can produce artifacts that appear as noise and contouring in the reconstructed image.
While there is considerable art dealing with more effective ways to quantize (linearly or non-linearly) digital signals or images, this invention describes a method and apparatus whereby a reconstructed image can have more levels than the number of levels stored in non-dependent images (or representations).
A patent that addresses obtaining additional signal level resolution is U.S. Pat. No. 4,032,977 entitled “GRAY SCALE INTERPOLATION TECHNIQUE” by Henry H. J. Liao wherein a method and apparatus are disclosed that utilize “probabilistic information to carry out a maximum likelihood estimation process so that the gray scale information is introduced with minimum statistical error”. The need for additional signal level (gray scale) resolution is recognized and addressed by utilizing adjacent data elements to form a prediction matrix.
A patent of particular interest, as it provides a method for generating the non-dependent representations that can utilize the method of this invention, is U.S. Pat. No. 4,969,204 entitled “HYBRID RESIDUAL-BASED HIERARCHICAL STORAGE AND DISPLAY METHOD FOR HIGH RESOLUTION DIGITAL IMAGES IN A MULTIUSE ENVIRONMENT” by Melnychuck et. al. This patent discloses a method wherein a hierarchical storage scheme contains lower resolution representations that do not require next lower resolution representations for display, i.e. non-dependent hierarchical representations.
The present solution to this problem of quantization artifacts, such as contouring, is achieved by encoding the digital signal or image with greater than one non-dependent representations. In a hierarchical storage scheme, a “non-dependent” representation is defined as a component of a hierarchy that does NOT require additional information (from other representations stored in the hierarchy) for display. Typically, hierarchies with residual or subband representations do not satisfy this “non-dependent” definition as any representation must be combined with a modified base image in order to create an image for display. In these cases, there is only one non-dependent representation—the base image or lowest spatial resolution image.
A practical example of an image storage scheme featuring non-dependent image representations (wherein this invention could be practiced) is the Kodak Photo CD storage scheme which features the following non-dependent files or representations:
Spatial resolution
Representation Name
512 × 768 pixels
BASE
256 × 384 pixels
BASE/4
128 × 192 pixels (2
BASE/16
versions)
The above spatial resolution numbers are for the luma files; the Photo CD file format also includes two chroma files that are spatially subsampled at each resolution level. These files are denoted Y, C1, C2, respectively. These files or representations satisfy the “non-dependent” definition as they can be meaningfully displayed without requiring information from any of the other files or representations. A more expanded and detailed discussion of these and other Photo CD files will appear later in the text.
By applying specific encoding and reconstruction methods to these non-dependent representations, it is possible to obtain additional signal level resolution while maintaining both the non-dependent files, and the not requiring additional information for display criteria of these non-dependent files.
There are many methods that can be employed to generate a digitized, spatially sampled representation of a signal or image. These methods are well know in the art and are not detailed herein. Without loss of generality, the detailed description that follows commences with a signal or an image that is spatially or temporally sampled with each sample being digitized to one of a finite number of discrete amplitude levels. In addition, the detailed description is in terms of a single channel signal or single channel image. Those skilled in the art will recognize that this invention can be applied to multiple channels, and multiple dimensions, and can be utilized with other quantization and schemes, decomposition/encoding (such as subbands). In addition, those skilled in the art will also recognize that while the disclosure describes operating on entire images, the invention could be practiced on selected portions of an image or performed a pixel at a time.
A general description of the preferred embodiment of a Photo CD system having both dependent and non-dependent files or representations is undertaken. Then a description of the spatial decomposition for the Photo CD system is described under this section of the specification, followed by detailed examples of specific encoding and reconstruction schemes illustrating the practice of the present invention within the Photo CD hierarchical storage scheme is discussed under the section entitled “DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS.”
1. GENERAL DESCRIPTION OF A PHOTO CD SYSTEM
A Photo CD system that is the basic vehicle for the present invention is illustrated in
FIG. 1. A
film strip
2
, having images recorded thereon, is scanned by a film scanner
3
. The scanner
3
may contain electronics (not shown) for converting the scanned image into analog or digital images which represent the image generally on a pixel-by pixel basis. If the scanner's output is analog in nature the signals at its output are converted to digital signals by the use of an analog-to-digital converter (not shown). The digitized images are then forwarded to a workstation
4
for processing wherein the images are enhanced, balanced, compressed/decompressed and displayed for operator approval. The method of the present invention is enabled with the software and electronics of the workstation
4
. In the preferred embodiment of the invention the digital representations of the images are in three channels identified generically as the Y, C1, and C2 channels.
Referring to
FIG. 2
, by utilizing the residual hierarchical format of the type disclosed in U.S. Pat. No. 4,969,204 the Y, C1, C2 channels of the starting 2048×3072 pixel image are decomposed into five images, BASE/16, BASE/4, BASE, 4BASE, and 16BASE which form an Image Pac. The 4BASE and the 16BASE images are stored as compressed residual images. For reconstruction of 4BASE and 16BASE images, the residuals plus an interpolated lower resolution image are used, therefore the 4BASE and 16BASE images are “dependent” by definition. The name BASE is given to the image that is sized for television, and the remainder are named by how they compare to the BASE.
Referring back to
FIG. 1
, the processed digital images (Image Pac) are then written onto a compact disk by a CD writer
5
. A CD player
7
is used to read user selected images from the compact disk under user control and to reconstruct and to forward the selected images for display on, for example, a standard TV display
8
or to cause a printing of the selected image by a printer, such as a thermal printer
9
. In a variant of the system (not shown) the CD player
7
may be a computer with a Photo-CD reader (CDI) incorporated therein and the images on the compact disk may be read out for display on the computer's monitor with the operator interacting with the image through appropriate computer programs.
The 16BASE digitized images from the scanner
3
have a very high resolution (2048×3072 pixels) which permits certain printers to print images that corre
Lawton James
Weldy John A.
Bocchetti Mark G.
Couso Yon J.
Eastman Kodak Company
LandOfFree
Method and associated apparatus for achieving additional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and associated apparatus for achieving additional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and associated apparatus for achieving additional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472176