Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
2000-11-28
2004-01-27
Tran, Phuoc (Department: 2621)
Image analysis
Image enhancement or restoration
Image filter
C382S253000
Reexamination Certificate
active
06683994
ABSTRACT:
BACKGROUND OF THE INVENTION AND MATERIAL DISCLOSURE STATEMENT
The present invention relates to a methodology for filtering digital data. In particular the present invention is directed to the need for filtering ever larger amounts of data, in ever decreasing amounts of time, with greater economy and programmable flexibility. This need is particularly felt in the digital imaging arts and so will be described in terms of those problems. However, applicability will be found in other applications such as audio, video and communications for example.
In many signal processing areas, a filter whose cutoff frequency and rolloff characteristics can be programmed with high resolution is desired. Filtering tasks in audio systems include low-pass, band-pass and high-pass filters for program enhancement, surround sound level steering and crossover interfacing with speaker drivers. In video and digital image systems filters are employed for detecting, identifying and manipulating shape edges as well as obtaining average, edge and high frequency information. A problem particular to digital imaging is De-screening. De-screening is an important step performed on data right off an input scanner where the scanned material needs to be converted to gray scale images and any possible halftone contained in the scanned material needs to be “undone” to facilitate processing. This is desirable because the image system will apply its own halftone to the image data when displayed or output as a print. It is visually undesirable to further halftone a halftone. Common filtering tasks in communication systems include the minimizing of Inter-Symbol Interference (ISI) using Nyquist filters, the use of a matched filter (a filter with characteristics matched or complementary to characteristics of the signal applied to the communication channel) at the receiving end of a channel to maximize the receiver signal-to-noise ratio (SNR), and the attenuation of out-of-band interference. Changeable rolloff characteristics and frequency cutoff points allow the communication systems to operate over a variety of data rates and channel conditions.
The tasks of filtering and sampling analog signals can be done with various combinations of analog and digital filtering. A common technique is the use of a fixed analog filter with the desired frequency characteristics followed by a sampler on the analog filter output sampling at the desired sampling rate. Cost, flexibility, and performance considerations suggest the replacement of analog systems with systems or devices employing digital signal processing (DSP) techniques, particularly where programmable flexibility is desired.
One DSP technique utilized most typically in image processing operations is known as vector quantization (VQ). In VQ a block of X×Y pixels is mapped to a single “codeword” which is defined using a smaller number of bits than the number required by the original block. Codewords are stored in transmitting, receiving and storage devices, and each codeword is associated with a pre-defined set of image data. The codeword to which each pixel block is mapped, is that codeword which is associated with image data that most closely matches the image data in the pixel block. The typical process includes mapping the pixel block to a codeword, storing the codeword or transmitting it to a receiving device, and then mapping the codeword back to image data when it is retrieved from storage or received at the receiving device. Since codebook storage and codeword transmission require less space and time than storage and transmission of original image data, this process greatly reduces the resources required to reproduce the original image data.
There are typically many more combinations of pixel blocks than there are available codewords, and as indicated by the term “quantization” several input blocks will be mapped to the same single given codeword. For a fixed number of codewords, increasing the size of the pixel block reduces the quality of mapping and reconstruction since a lot more of the actual image data must be mapped to the same number of codewords. Some drawbacks of VQ are that codebook design is often very complex, and that large amounts of time are usually required to search through the codebook and to match blocks to the appropriate codeword. While codebook design can be performed off-line, the block matching searches must be performed on-line.
In hierarchical vector quantization (HVQ), block matching searches are performed two samples at a time. Thus, look up tables (LUTs) can be used directly to perform HVQ in two or more stages. In the first stage, two image pixels are mapped to one codeword, reducing the number of samples by a factor of 2. In the next stage, the process is repeated to map pairs of codewords into single codewords. Preferably, codewords are grouped in a direction perpendicular to the direction used for the previous level. As the process continues, the resulting codewords are mapped to larger and larger amounts of data.
HVQ allows for a rough approximation of the content of each image block by using simple look-up table operations. The final codeword represents a block approximation and can therefore be directly mapped to other quantities which describe certain characteristics of the approximated block, such as block activity. HVQ codebook design methods follow standard VQ codebook design algorithms and are usually performed by designing the codebooks for a single stage at a time. However there remains a need for further improvement in efficiently processing digital data (image data in particular) and allowing improved digital filtering without affecting the transmission efficiency in serial data transmission systems.
The following appears to be relevant to manipulation and compression of data. It is incorporated by reference in its entirety for its teaching.
In U.S. Pat. No. 5,602,589 to Vishwanath et al., a weighted wavelet hierarchical vector quantization (WWHVQ) procedure is initiated by obtaining an N×N pixel image where 8 bits per pixel (steps
10
and
12
). A look-up operation is performed to obtain data representing a discrete wavelet transform (DWT) followed by a quantization of the data (step
14
). Upon completion of the look-up, a data compression will have been performed. Further stages and look-up will result in further compression of the data, i.e., 4:1, 8:1, 16:1, 32:1, 64:1, . . . etc. Accordingly, a determination is made whether the compression is complete (step
16
). If the compression is incomplete, further look-up is performed. If the compression is complete, however, the compressed data is transmitted (step
18
). It is determined at a gateway whether further compression is required (step
19
). If so, transcoding is performed (step
20
). The receiver receives the compressed data (step
22
). Subsequently, a second look-up operation is performed to obtain data representing an inverse discrete wavelet transform of the decompressed data (step
24
). After one iteration, the data is decompressed by a factor of two. Further iterations allows for further decompression of the data. Accordingly, a determination is made whether decompression is complete (step
26
). If the decompression is in incomplete, further look-ups are performed. If, however, the decompression is complete, the WWHVQ procedure is ended.
Therefore, as discussed above there exists a need for a technique which will solve the problem of filtering large amounts of digital signal data in a cost effective and flexibly programmable manner. Thus, it would be desirable to solve this and other deficiencies and disadvantages with an improved processing methodology.
SUMMARY OF THE INVENTION
The present invention relates to a method of filtering data, comprising receiving input data comprised of data units and applying at least two stages of look-up-tables in an overlapping manner to the data units so as to produce a code index for each data unit. This code index is then mapped the to a filter look-up-table to output a processed data unit.
More particularl
de Queiroz Ricardo L.
Fleckenstein Patrick A.
Tran Phuoc
Wait Christopher D.
Xerox Corporation
LandOfFree
HVQ-based filtering method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with HVQ-based filtering method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and HVQ-based filtering method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225797