Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
2000-09-07
2002-10-29
Boudreau, Leo (Department: 2621)
Image analysis
Pattern recognition
Feature extraction
C382S218000, C382S260000, C382S263000, C382S264000, C382S266000, C382S269000, C382S282000, C382S298000, C382S299000, C345S596000, C345S613000, C348S574000, C358S426010, C358S451000
Reexamination Certificate
active
06473525
ABSTRACT:
BACKGROUND OF THE INVENTION
1, Field of the Invention
The present invention relates to inverse dithering, and more particularly, to a method for detecting an image edge within a windowed portion of a dithered image.
2. Description of Related Art
Dithering has long been a method to maintain the perceptual quality of continuous tone images in low bit depth video displays. The illusion of true continuous tone images can be produced on display devices incapable of providing a required number of amplitude levels necessary for achieving a full, continuous tone image by dithering. By dithering the images may be displayed on systems having low bit-depth frame buffers while maintaining a reasonable image quality. The technique is also referred to as half-toning when the result produces a binary (black and white) image. Dithering enables a respectable display at a lower amplitude resolution by distributing quantization noise over small areas.
One process for improving the quality of a dithered image is referred to as inverse dithering. Inverse dithering strives to restore the original continuous tone nature of a predithered image. In inverse dithering, low-pass filters are used to reverse the effects of dithering such as graininess of the picture. However, use of low-pass filtering tends to blur the object edges of the image. Therefore, the inverse dithering process must ultimately achieve two conflicting goals. First, the effects of the original dithering must be smoothed, and at the same time the object edges or the high-frequency content of the original image must be maintained without undesirable blurring.
Inverse dithering may be discussed in a larger context of an image-rendering system. As illustrated in
FIG. 1
, a simplified image-rendering system consists of a dithering system
10
that receives as input, pixel values of an image I(x,y). The originally received image may be a monochromatic or a color image. The original image I(x,y) will have an amplitude resolution of g
r
bits per pixel and the pixel values will be within the range of
I
(
x,y
)&egr;{0,1,2, . . . ,2
q′
−1}. (1)
The image I(x,y) is reduced in amplitude resolution to m bits per pixel by the dithering process. The dithered image I
d
(x,y) will consist of pixels having values within the range of
I
d
(
x,y
)&egr;{0,1,2, . . . ,2
m
−1}. (2)
The dithered image I
d
(x,y) is processed by an image buffer
15
which in many computer display systems would typically comprise a frame buffer. However, the image buffer
15
may comprise any number of other mechanisms for holding or transporting an image such as a communication channel. The image buffer
15
actually drives the necessity for amplitude reduction of the original image I(x,y) due to the limited amount of memory in the buffer for storage or the narrow bandwidth of a communication channel.
The inverse dithering system
20
receives the dithered image I
d
(x,y) and produces a reconstructed image I
r
(x,y) having a higher amplitude resolution of q″-bits per pixel. The amplitude resolution of the original and reconstructed images may be the same, but this is not required. The reconstructed image will have pixel values within the range
I
r
(
x,y
)&egr;{0,1,2, . . . ,2
q
″−1}. (3)
A variety of methods have been developed for performing inverse dithering. The majority of these methods have been focused on the specialized case of inverse half-toning or, in other words, recovery of full gray scale from binary images. In one technique, a gray scale image is constructed from a binary image by means of a statistically generated lookup table. This method utilizes statistics generated during the original dithering process to perform the statistical analysis necessary to generate the lookup table. The statistical analysis requires complex calculations, and the storage of the lookup table greatly increases the memory requirements.
Another method utilizes cascading of adaptive run-length algorithms with statistical smoothing and impulse removal. A class of iterative, nonlinear algorithms have been proposed that are based on the theory of Projection Onto Convey Sets (POCS). This technique involves performing multiple iterations of an inverse dithering process until a a final inverse dithered image is determined. This requires a great deal of processing due to the multiple iterations. Other methods have used information generated by a wavelet decomposition to perform the inverse dithering process.
There are also methods for reconstructing a dithered color image referred to as “color recovery”. The color recovery technique requires a renormalization process that increases the overhead requirements for processing the inverse dithering algorithm.
Some of the aforementioned techniques require prior knowledge of the dither mask used to dither the original image. Also, most of these methods involve highly complex calculations and require a great deal of memory in order to perform the inverse dithering processes. These requirements limit the ease and speed in which an inverse dithering process may be performed. Thus, there has arisen a need for a method of inverse dithering that is substantially less computationally complex and requires less memory resources than those of methods presently utilized.
OBJECTS OF THE INVENTION
Accordingly, it is an object of the present invention to provide a method and apparatus for inverse dithering image which has been dithered according to any one of a plurality of dithering methods.
It is also an object of the present invention to provide a technique for determining whether an image edge exists within a region of support of a filter processing the dithered image.
It is yet another object of the present invention to provide a technique for detecting an edge of a dithered image based upon predetermined data.
It is still further an object of the present invention to provide further advantages and features, which will become more apparent to those skilled in the art from the disclosure, including a preferred embodiment, which shall be described below.
SUMMARY OF THE INVENTION
The present invention is directed to the above need. A method in accordance with the present invention includes the steps of selecting a pixel within a support region for processing, computing the differences between pixel values in the region and the selected pixel to form a current difference map and determining from the current difference map whether pixels in the region differ by no more than one resolution level from each other. If pixels in the the region differ from each other by more than one resolution level, determining that an edge exists within the region. If pixels in the region differ from each other by one resolution level or less, determining that an edge does not exist within the region.
A method for detecting an image edge within a dithered image, comprising the steps of selecting a pixel within a support region for processing, computing a table of difference maps for the region, computing the differences between pixel values in the region and the selected pixel to form a current difference map and comparing the current difference map to the difference maps of the table. If the current difference map matches a difference map from the table, determining that an edge does not occur within the region. If the current difference map does not match a difference map from the table, determining that an edge does occur within the region.
REFERENCES:
patent: 4926268 (1990-05-01), Kawamura et al.
patent: 5379130 (1995-01-01), Wang et al.
patent: 5493419 (1996-02-01), Jodoin et al.
patent: 5598184 (1997-01-01), Barkans
patent: 5905504 (1999-05-01), Barkans et al.
patent: 5974197 (1999-10-01), Lee et al.
patent: 405861 (1995-08-01), None
patent: 0769741 (1997-04-01), None
Kim, et al. “Inverse halftoning using binary permutation filters”, IEEE, pp. 1296-1311, Sep. 1995.*
“display of dither images by A. N. Netravali and E. G. Bowen of Bell Laboratories”, 6 pgs. Proceedings of the SI
Cheung Shiufun
Iyengar Giridharan
MacNamara Robert
Ulichney Robert A.
Boudreau Leo
Compaq Computer Corporation
Mariam Daniel G.
Oppenheimer Wolff & Donnelly LLP
Sherry Leah
LandOfFree
Method for detecting an image edge within a dithered image 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 for detecting an image edge within a dithered image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for detecting an image edge within a dithered image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2937093