Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
2000-06-23
2004-10-26
Williams, Kimberly (Department: 2626)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003150, C358S445000, C358S003080, C358S470000, C382S232000
Reexamination Certificate
active
06809840
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of digital image processing, and more particularly to methods for adaptively sub-sampling an image.
BACKGROUND OF THE INVENTION
In many imaging applications, an image is sub-sampled such that only a part of the pixels of the original image, regularly or irregularly distributed on the image grid, are retained in order to reduce memory usage. Later on, in order to reconstruct the original image from these retained scattered image values, various interpolation methods may be employed to fill in the missing image values.
The most straightforward sub-sampling approach is the uniform sub-sampling scheme on a regular image grid. For example, we may divide the image into 4×4 cells, and only retain the image pixel at the right bottom corner of each cell to achieve the 4× sub-sampling, in which case, only approximately 6.25% of the original image pixels are retained. The benefit of uniform sub-sampling is that the positions of remaining pixels are known, and it is not necessary to track their coordinates. However, since uniform sub-sampling is an image independent scheme that takes no advantage of structures in a given image, images structures are not well preserved when a high sub-sampling ratio is required. For example, in the 4× sub-sampling case, where only around 6.25% of the original image pixels are retained, the resulting reconstructed image is usually not satisfactory.
There are many ways to take image content into consideration during sub-sampling. In general, fine sub-sampling is required in the neighborhood of sharp edge transitions, whereas coarse sub-sampling may be sufficient in relatively smooth regions. This approach is normally called the non-uniform sub-sampling. The image sub-sampling process is binary in nature, i.e., the value of each image pixel is either retained (sampled) or discarded. Non-uniform sub-sampling is similar in concept to digital halftoning.
Digital halftoning is a technique that is commonly used in digital image processing to create the appearance of intermediate tones when only two colorant levels are available (see R. Ulichney, “Digital Halftoning,” MIT Press, Cambridge, Mass., 1987). Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that intermediate gray levels can be created by turning some of the pixels “on” and some of the pixels “off” in some small region. The fraction of the pixels that are turned on will determine the apparent gray level.
One digital halftone technique employs a blue noise dither matrix M(m,n). M is typically a two dimensional array of W by W size (i.e., W is 128). For each pixel I(x,y) in a digital image, the x-y location of the pixel is used to determine the specific entry M(x
d
,y
d
) in the blue noise dither matrix, where x
d
and y
d
are given by:
x
d
=x
%
W
and
y
d
=y
%
W
(1)
Modular operators “%” are typically used since the size of the dither matrix is normally smaller than that of the image. I(x,y) is then compared with M(x
d
,y
d
), and based on the result, the output pixel O(x,y) is either turned on or off. There are two advantages associated with blue noise dithering. First, it is a point comparison process, thus is fast to implement; second, it generates uniformly distributed dot patterns at slowly varying image areas, thus creating a pleasing appearance.
Although digital halftoning using a blue noise dither matrix is known in the art, it is not apparent how this technique could be used to perform non-uniform or adaptive sub-sampling.
There is a need therefore for an improved efficient method for adaptively sub-sampling an image that takes image content into consideration and has the advantages associated with blue-noise halftoning.
SUMMARY OF THE INVENTION
The need is satisfied according to the present invention by providing a digital image processing method for adaptively sub-sampling an image to X % of original pixels that includes the steps of generating an edge map of the image; normalizing the edge map to N-bits; applying a shift to the normalized edge map such that X % of the pixels will be ones when the normalized shifted edge map is halftoned using a blue noise halftoning technique; halftoning the edge map using the blue noise halftoning technique to generate a halftone mask; and sub-sampling the image at the pixel locations represented by ones in the halftone mask.
ADVANTAGES
The present invention has a main advantage that since image content is considered during the sub-sampling, the reconstructed image using a suitable reconstruction method (e.g. so-called Kriging method) will retain better fine details compared to that generated by uniform sub-sampling methods.
The present invention has yet another advantage in that an arbitrary sub-sampling ratio can be achieved within a small margin while it is usually hard for a uniform sub-sampling method to achieve certain sub-sampling ratios because the regular sample grid must fall on integer coordinates or a re-sampling procedure needs to be employed (re-sampling may introduce additional loss of image structures).
The present invention also has the advantage of efficiency and fast implementation speed. With the usage of a local variance operator, histogram analysis and blue noise halftone technique, only one scan of the original image is required as compared to other non-uniform sub-sampling methods normally using iterative scans of the original image to satisfy certain criterion such as the mean square error (MSE) of the reconstructed image.
REFERENCES:
patent: 4597010 (1986-06-01), Carr
patent: 6154195 (2000-11-01), Young et al.
patent: 6167167 (2000-12-01), Matsugu et al.
patent: 6169766 (2001-01-01), Aoki et al.
patent: 6704123 (2004-03-01), Av-Shalom et al.
Lefebvre et al., “Prediction from Wrong Models: The Kriging Approach,”IEEE Antennas and Propagation Magazine, vol. 38, No. 4, Aug. 1996, pp. 35-45.
Spaulding et al., “Methods for generating blue-noise dither matrices for digital halftoning,”Journal of Electronic Imaging, Apr. 1997, vol. 6(2), p. 208.
R. Ulichney, Digital Halftoning, 1987, Massachusetts Institute of Technology.
Luo Jiebo
Yu Qing
Close Thomas H.
Eastman Kodak Company
Vida Melanie
Williams Kimberly
LandOfFree
Image processing method for adaptively sub-sampling an 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 Image processing method for adaptively sub-sampling an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing method for adaptively sub-sampling an image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301993