Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-08-30
2004-04-20
Williams, Kimberly A. (Department: 2626)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003060, C358S003130, C358S003170, C358S003180, C358S003190, C382S270000
Reexamination Certificate
active
06724499
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a pseudo-halftone image expression method for use in expressing such an image having halftones as a black-white and color photograph gradually with binary dots.
2. Description of the Related Art
In case of four basic colors of cyanic, magenta, yellow and black, a raster plotter can merely express seven total colors including mixed colors of red, green and blue thereof in addition to the four colors. It can not express more than eight colors even though a ground color of white is additionally included. Various methods have been developed, however, to create pseudo halftones in the art. Generally known methods include a pattern dither method which realizes a pseudo halftone expression by distributing thresholds for binarization into a matrix of 4×4 dots, for example, and increasing the number of formed dots in accordance with gray levels.
FIG. 8
exemplifies some threshold matrixes.
FIGS. 8A-8C
respectively illustrate the threshold matrixes of a Bayer type, mesh type and whirlpool type.
The pattern dither method can advantageously realize the pseudo halftone expression with a relatively simple algorithm, high-speed processing and small computation complexity. It has a disadvantage, however, that a coarse image quality is remarkable such that the same pattern is seen repeatedly, for example.
There are other methods suitable for processing a full color image such as a photograph in general while their algorithms are more sophisticated and their computational complexities are larger than those of the pattern dither method that tries to realize the pseudo halftone expression with a simple algorithm. An error diffusion method represents such methods. This method replaces a subject dot with the nearest basic color or a mixed color thereof and compensates an error, which is caused relative to the original color by the replacement, at a later color replacement.
The error diffusion method, on the other hand performs a fine compensation on a dot basis and thus enables the pseudo halftone expression to be processed with a relatively higher image quality. It has a disadvantage, however, that its computation complexity becomes enormous because of the error compensation computing on a dot basis. The error diffusion method also has other disadvantages that the compensation cannot be achieved until the errors are stored when a light color is painted out, and that the compensation cannot over take an image with a sharp density variation and degrades the image quality extremely. In addition, the method is difficult for use in processing vector data while it is effective for raster data and the like because the computation is achieved along with scanning.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of such the disadvantages and accordingly has an object to provide a pseudo-halftone image expression method capable of processing vector data with a high image quality and small computational complexity.
The present invention is provided with a pseudo-halftone image expression method for expressing gray levels of n×n/m by varying the number of formed dots within a matrix of n×n dots on an m-dot basis (where n denotes an integer of 8 or more and m denotes an integer of 4 or more). A dot formation rule corresponding to each gray level within a matrix is divided into at least two stages, from a low gray level to a high gray level. In a first stage, dots are arranged at random and in dispersion so as to separate a dot from each other. In a second stage, dots are extended in random directions in turn so as to prevent an island of successive dots from coupling with each other using the dots arranged at the first stage as a nucleus.
A factor for degrading the image quality according to the conventional pattern dither method is a remarkable texture noise. This is caused by regular increase of the dots both in length and width within the matrix in accordance with the variation of the gray levels from a low level to a high level. Another factor for degrading the image quality is an irregular dense pattern that appears at a portion where a mass of dots joins with each other when the gray level varies from a certain level to a next level and the number of dots increases.
According to the present invention, the number of formed dots within the matrix is varied on a multi-dot basis in accordance with gray level variations. In addition, the dots are arranged at random and in dispersion at the first stage so as to separate a dot from each other. The dots are also extended in random directions in turn at the second stage so as to prevent the island of successive dots from coupling with each other. Thus, a smooth and excellent image can be obtained without any regular arrangement and local concentration of dots. The method of the present invention employs a fixed pattern system in accordance with gray levels. Thus, it is possible to realize a high-speed processing without such the computation on a dot basis as is performed in the error diffusion method and to process vector data easily as well.
Due to the following reason, n is defined with an integer of 8 or more. If n is less than 8, it becomes difficult to arrange plural dots within the matrix at random and in dispersion and also to express gradually in accordance with an island growth, resulting in the regular noise and irregular dense.
According to a preferred embodiment of the present invention, a third stage may be provided following to the second stage as a dot formation rule corresponding to gray levels within a matrix. In the third stage, a new dot that does not couple to each island is arranged before an island of different dots formed at the second stage is coupled to each other. Then, dots are extended from a low gray level to a high gray level in turn using the new dot as a nucleus. Thus, an extreme dense variation due to a linkage between islands can be avoided and a further smooth and excellent image can be obtained.
According to another preferred embodiment of the present invention, a half dot formation pattern in lower gray levels among the whole gray levels to be expressed may be stored. Then, another half dot formation pattern in higher gray levels may be determined as an inverted pattern of the dot formation pattern in the lower gray levels. Thus, it is possible to reduce a data amount of the pattern to be stored down to half the original storage amount. As a result, a time for obtaining the pattern and memory capacity for storing the pattern can be reduced by half.
According to further preferred embodiment of the present invention, a position of the dot to be arranged within the matrix at the first stage may be determined by arranging a plurality of dots at random within the matrix, and repeating predetermined times a process of moving each dot so as to be separated from the nearest dot by a predetermined distance. In addition, a position of the dot to be arranged within the matrix at the first stage may be determined to the emptiest position among dots already arranged.
Other features and advantages of the invention will be apparent from the following description of the preferred embodiments thereof.
REFERENCES:
patent: 5053887 (1991-10-01), Thompson
patent: 5555102 (1996-09-01), Dalton
patent: 5557709 (1996-09-01), Shu
patent: 5684932 (1997-11-01), Shu
patent: 5703695 (1997-12-01), Nguyen
patent: 5706105 (1998-01-01), Naylor, Jr.
patent: 5760920 (1998-06-01), Lin et al.
patent: 5917951 (1999-06-01), Thompson et al.
patent: 6020978 (2000-02-01), Cooper et al.
patent: 6025930 (2000-02-01), Thompson et al.
patent: 6172773 (2001-01-01), Ulichney
patent: 6266155 (2001-07-01), Lee et al.
patent: 6381037 (2002-04-01), Balasubramanian et al.
patent: 6433891 (2002-08-01), Yu et al.
patent: 6445465 (2002-09-01), Samworth
patent: 2002/0196454 (2002-12-01), Atkins et al.
patent: 2003/0035146 (2003-02-01), Yu et al.
Ulichney, Robert A.; Void-and-cluster method for dither array generation, Sep. 1993, SPIE, Proceedings
Knoble Yoshida & Dunleavy
Mutoh Industries Ltd.
Vida Melanie
Williams Kimberly A.
LandOfFree
Pseudo halftone image expression 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 Pseudo halftone image expression method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pseudo halftone image expression method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3202323