Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-03-19
2001-03-13
Rogers, Scott (Department: 2724)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S462000, C358S465000, C358S466000, C382S252000, C382S176000
Reexamination Certificate
active
06201612
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for converting a multi-level digitized image to a bi-level image.
Multi-level digitized images are generated by, for example, digital cameras, scanners, and computer software. In a multi-level monochrome image, each picture element or pixel can take on various levels of gray, the number of levels being greater than two. A multi-level color image comprises a plurality of color planes, each pixel having more than two possible levels in each color plane.
Multi-level images are often printed or displayed by bi-level output devices capable of expressing only two levels, normally a black level and a white level in a monochrome output device, or an on-level and an off-level for each color plane in a color output device. Before being output by such a device, a multi-level image must be converted to bi-level form.
Among the known techniques for converting multi-level images to bi-level images are halftone patterns, dithering, error diffusion, and mean error minimization. These terms are sometimes used with overlapping meanings; for example, mean error minimization is often referred to as error diffusion.
A halftone pattern is an m×m pattern of bi-level output pixels, generated from a single input pixel by using different threshold values for different pixels in the output pattern (m is an integer greater than one). Halftone patterns are often used on input images with relatively low information content, such as television images.
Dithering tiles an input image with an n×n matrix of differing threshold values, where n is an integer greater than one, and converts each input pixel to a single bi-level output pixel by comparing the input pixel value with the corresponding threshold value. Dithering is used in high-resolution image processing equipment, including copiers.
A problem with halftone patterns and dithering is the limited number of gray levels that can be expressed (m
2
+1, or n
2
+1). With small values of m and n, the limited gray scale produces unwanted contour lines in what should be smooth areas. If the value of m or n is increased to provide more gray levels, spatial resolution is lost, and the converted image begins to have a visibly blocky appearance. For this reason, dithering is rarely practiced with values of n larger than four.
The error diffusion and mean error minimization methods smooth out the errors caused by bi-level quantization. In error diffusion, the quantization error of a pixel is distributed over a certain number of subsequently-processed pixels. In the mean error minimization method, the value of a pixel is modified according to a weighted average of the quantization errors in a certain number of preceding pixels. Both methods give the same result, and can achieve comparatively smooth gray-scale expression with comparatively little loss of spatial resolution.
The error diffusion method and mean error minimization methods, however, require much computation to distribute the quantization error of each pixel individually. Processing is particularly slowed by the frequent need to access a memory area in which the quantization error values are stored.
Error diffusion or mean error minimization can also be used when a multi-level image is converted to a multi-level image with a smaller number of levels, a process sometimes referred to as color reduction. Compared with bi-level error diffusion, multi-level error diffusion yields a considerable improvement in image quality, even if the number of output levels is only three, but requires a multi-level output device, which is more expensive than a bi-level output device.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an image processing apparatus, method, and computer program for converting a multi-level image to a bi-level image, combining high processing speed with smooth expression of gray levels.
Another object of the invention is to avoid blurring of edges in the converted bi-level image.
The invented method comprises the steps of:
dividing an input multi-level image into blocks;
modifying the pixel values in each block according to block quantization errors in neighboring blocks quantized previously;
quantizing each modified block, thereby generating a bi-level output block; and
calculating and storing a single block quantization error for each block.
The quantizing step can be carried out by a bi-level quantization process, by comparing the modified value of each pixel in a modified block with a corresponding threshold value. Alternatively, the quantizing step can be carried out by a multi-level quantization process, by comparing the average modified value of the pixels in the block with a plurality of threshold values, and outputting a fixed pattern of bi-level pixels corresponding to the quantized level of the block as a whole.
Preferably, both of these processes are employed, and a step of detecting edges in the blocks is added. Bi-level quantization is used in blocks with edges. Multi-level quantization is used in blocks without edges.
The invented image processing apparatus comprises an image partitioner for dividing the input image into blocks, and a block error diffusion processor for modifying pixel values, generating bi-level output blocks, and calculating and storing block quantization errors. The apparatus preferably also comprises a selector for detecting edges and choosing between the bi-level quantization process and the multi-level quantization process.
The invented computer program comprises computer code means, stored in a computer-readable medium, for carrying out the steps described above.
REFERENCES:
patent: 4709274 (1987-11-01), Tanioka et al.
patent: 5018024 (1991-05-01), Tanioka et al.
patent: 5034990 (1991-07-01), Klees et al.
patent: 5077615 (1991-12-01), Tsuji et al.
patent: 5130823 (1992-07-01), Bowers et al.
patent: 5748794 (1998-05-01), Maeda et al.
patent: 5757976 (1998-05-01), Shu et al.
Miyata et al., “A Study of Improvement of Image Quality in Hardcopy using Multi Level Error Diffusion Method,” 25th Image Engineering Conference, 1994, pp. 101-104.
Kurabayashi Kazuyo
Matsushiro Nobuhito
Akin Gump Strauss Hauer & Feld L.L.P.
Oki Data Corporation
Rogers Scott
LandOfFree
Image processing method and apparatus employing block error... 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 and apparatus employing block error..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing method and apparatus employing block error... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527269