Image processing method and apparatus for out-putting dot-processed data with suppression of false contours and other noise
This application is a continuation of application Ser. No. 07/192,601, filed May 11, 1988, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to an image processing method for processing an image in the form of digital signal and an apparatus therefor, and more particularly to an image processing method for reproducing an image with high quality and an apparatus therefor. 
     2. Related Background Art 
     There is already known the error dispersion method as a binary digitizing method for reproducing intermediate tone in digital printers or digital facsimile apparatus. In said error dispersion method, the difference in density between the original input image and the output image after processing is calculated for each pixel, and the error obtained in said calculation is dispersed into surrounding pixels with predetermined weighting. Said error dispersion method was presented by R.W. Floyd and L. Steinberg in &#34;An Adaptive Algorithm for Spatial Gray Scale&#34;, SID 75 Digest (1976). 
     Such error dispersion method can conserve the density of the input image in the output image, and, lacking periodicity in the processing, is free from Moire fringe patterns encountered in other binary digitizing methods such as the dither method or density pattern method, but is associated with the drawbacks of particular fringe patterns in the uniform density area (nonedge area) of the image or granular noises due to dispersed dots particularly in the highlight area of the image, thus leading to the deterioration of image quality. 
     For avoiding these drawbacks, U.S. Pat. No. 4,876,610 proposes a method of discriminating the characteristic of image and dispersing the error according to the result of said discrimination. Also, U.S. Pat. No. 4,878,125 proposes a method of varying the ratio of dispersion of error into the surrounding pixels according to the amount and direction of edge present in the image, and U.S. patent application Ser. No. 145,593 filed Jan. 19, 1988, proposes a method of dividing the original image into blocks, digitizing the image in each block and dispersing the error in said digitization into surrounding blocks. Both mentioned patents and the patent application are assigned in common with the present invention. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to provide an image processing method, and an apparatus therefor, free from the above-mentioned drawbacks of the conventional technology and capable of reproducing any original image with high quality and high resolution. 
     Another object of the present invention is to provide an improvement on the image processing method for digitizing input image data, and the apparatus therefor. 
     Still another object of the present invention is to provide an image processing method capable of providing a high quality image by an improvement on the error dispersion method used for intermediate tone processing of image, and an apparatus therefor. 
     Still another object of the present invention is to provide an image processing method capable of high speed image processing, and an apparatus therefor. 
     Still another object of the present invention is to provide an image processing method capable of satisfactory image reproduction by digitizing after the image is converted into a dot pattern, and an apparatus therefor. 
     Still another object of the present invention is to provide an image processing method capable of satisfactory image reproduction with a simple structure, and an apparatus therefor. 
     Still another object of the present invention is to provide an image processing method capable of providing a reproduced image faithful to the original image by conservation of density before and after the formation of the dot pattern, and an apparatus therefor. 
     Still another object of the present invention is to provide an image processing method capable of satisfactory image reproduction without deterioration in the resolution, by selecting or not the dot pattern formation depending on the characteristic of the original image, and an apparatus therefor. 
     The foregoing and still other objects of the present invention, and the advantages thereof, will become fully apparent from the following detailed description of the preferred embodiments, which is to be taken in conjunction with the attached drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a first embodiment of the present invention; 
     FIG. 2 is a block diagram showing the details of a pre-processing circuit 16 shown in FIG. 1; 
     FIG. 3 is a block diagram showing the details of a sum calculation circuit 21 shown in FIG. 2; 
     FIG. 4 is a view illustrating input data of 3×3 pixels; 
     FIG. 5 is a view illustrating data after dot forming process; 
     FIG. 6-1 is a block diagram showing the details of a binary digitizing circuit 18 shown in FIG. 1; 
     FIG. 6-2 is a chart showing an example of weighting coefficients; 
     FIG. 7 is a block diagram showing a modification of the embodiment shown in FIG. 1; 
     FIG. 8 is a block diagram of a second embodiment; 
     FIG. 9 is a block diagram showing the details of pre-processing circuit 85 shown in FIG. 8; 
     FIG. 10 is a block diagram showing the details of mixer 86 shown in FIG. 8; and 
     FIG. 11 is a chart showing the relation between the image density and the dispersion rate α. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Now the present invention will be clarified in detail by embodiments thereof shown in the attached drawings. 
     FIG. 1 is a block diagram showing an embodiment of the present invention, wherein an input sensor 11 is composed of a photoelectric conversion device such as CCD and a driving unit therefor, and reads the original image by scanning. The image data obtained from the original image by the input sensor 11 are supplied to an A/D converter 12 for conversion of data of each pixel into digital data of 8 bits or 256 levels. 
     Then a correction circuit 13 executes digital shading correction for compensating for unevenness in the sensitivity of the CCD sensor or in the luminosity of light source. The corrected data 100 are supplied to an edge detection circuit 14 and a selector 15. 
     The data are transferred in units of blocks of m×n pixels each. In the present embodiment there will be explained a case of m=3, n=3. Said transfer in block units can be achieved by a structure employing a line memory of three lines, or a structure in which image data are stored in the units of a page and are then read in units of blocks of 3×3 pixels each. 
     The edge detection circuit 14 discrimiantes whether an edge is present in the block, for example by using a Laplacian of 3×3 pixels or by comparing the difference between the maximum and minimum values in the block with a threshold value T 1  (=15 in the present embodiment) and identifying the presence or absence of an edge if said difference is respectively larger or smaller than the threshold value. The present embodiment employs the latter method, and the threshold value T 1  is determined experimentally. The discrimination of the presence of an edge in the block is conducted for selecting the dot forming (or conversion) process or not. In a block containing an edge, namely in an area containing portions of characters, the dot forming process is not adopted, in order to prevent deterioration in resolution associated with such dot formation. The edge detection circuit 14 discriminates the presence of edges as explained above, and releases a signal 200 which is &#34;1&#34; or &#34;0&#34; respectively in the presence or absence of edges. Said signal 200 is supplied to the selector 15, which transfers the received data 100 as data 300 in units of blocks to a pre-processing circuit 16 if the signal 200 is &#34;0&#34;, indicating the absence of edges, but transfers said data 100 as data 400 to a memory 17 if said signal 200 is &#34;1&#34;, indicating the presence of an edge. 
     In this manner the selector 15 is provided for conducting the pre-processing only in an area without edges, as identified by the edge detection circuit 14. 
     The pre-processing circuit 16 executes dot formation (or conversion) by summing the data of the block entered as the signal 300, and replacing said sum of densities in the block by the density of a pixel or plural pixels in a block. Such dot formation in a uniform density area not containing edges provides a periodic arrangement of dots, thus suppressing particular fringe patterns experienced in binary digitizing in the binarizing circuit to be explained later, for example with the error dispersion method. 
     Data 500 after dot forming in the preprocessing circuit 16 are supplied to a memory 17 and are synthesized with the data 400 of the edge containing area(s). The data 600 read from the memory 17 in units of pixels are supplied to a binary digitizing circuit 18 for binary digitizing using the error dispersing method. The obtained result 700 is supplied to a printer 19 for forming an image by turning on and off the dots according to the binary data 700. 
     FIG. 2 is a block diagram of the preprocessing circuit 16 shown in FIG. 1, for dot forming for the blocks not containing edges. The data 300 from the selector 15 are supplied to a sum calculation circuit 21 for calculating the sum S of the densities of the nine data (3×3 pixels) in the block, according to the following equation: ##EQU1## wherein D ij  is the density of a pixel (i, j) in the block. FIG. 3 is a block diagram of the sum calculation circuit 21. The sum S of density is supplied as a signal 301 to a dot forming circuit 22. 
     FIG. 4 illustrates density data of an input block (3×3 pixels), wherein D ij  (i=1, 2, 3; j=1, 2, 3) represents the density of the pixel (i, j). 
     FIG. 5 illustrates the density after dot forming processing, wherein A ij  (i=1, 2, 3; j=1, 2, 3) represents the density of the pixel (i, j). 
     Assuming that D max  is the maximum density produced by the printer, namely the density of a dot printed by the printer, the dot forming circuit 22 forms dots in the following manner: 
     
         ______________________________________                                    
i)    When S ≦ D.sub.max ;                                         
         A.sub.22 = S                                                     
         density for other pixels = 0                                     
ii)   When D.sub.max &lt; S ≦ 5D.sub.max ;                            
         A.sub.22 = D.sub.max                                             
         A.sub.12 = A.sub.21 = A.sub.23 = A.sub.32 = (S - D.sub.max)/4    
         density for other pixels = 0                                     
iii)  When S &gt; 5D.sub.max ;                                               
         A.sub.12 = A.sub.21 = A.sub.22 = A.sub.23 = A.sub.32             
         = D.sub.max                                                      
         density for other pixels = (S -                                  
         5D.sub.max)/4                                                    
______________________________________                                    
 
    
     wherein S is the sum of density obtained from the sum calculation circuit 21 shown in FIG. 2, and A ij  (i=1, 2, 3; j=1, 2, 3) is the density of pixel (i, j) in the block after dot formation. 
     The dots can be formed in this manner, and the formation of such periodic pattern prior to the binary digitizing allows suppression of particular patterns generated in the binary digitization for example with the error dispersing method. Also, said periodic structure allows prevention of formation of granular noises. The data 500 obtained by said dot formation are supplied to the memory 17. 
     FIG. 6-1 is a block diagram showing the details of the binarizing circuit 18 shown in FIG. 1. The image data 600 (X ij ) read from the memory 17 are added, in an adder 51, with data which are obtained by multiplying errors ε ij  generated in the preceding binary digitizing and stored in an error buffer memory 53 by weighting coefficients α kl  in a weighting generator 52 and then normalized by division by Σα kl . 
     This operation can be represented by the following equation: ##EQU2## In the first binary digitizing, the errors are not stored in the error buffer memory and are therefore not added to the input data. 
     FIG. 6-2 shows an example of the weighting coefficients, wherein 57 indicates the pixel position undergoing processing, and the values in the matrix are larger as they are closer to said pixel position under processing. The weighting generator 52 executes respective multiplications of the data a, b, c, . . . , l of the error buffer memory 53 with 1/48, 3/48, 5/48, . . . , 7/48 shown in FIG. 6-2 and sends the sum of these multiplications to the adder 51, so that the data of the error buffer memory positioned close to the pixel position 57 undergoing processing are given heavier weighting. 
     The errors ε ij  stored in the error buffer memory 53 represent differences between the correction data x&#39; ij  obtained in the adder 51 prior to the currently processed data and the binarized output data y ij . 
     The corrected data x&#39; ij  obtained by addition in the adder 51 are then compared with a threshold value T in the binarizing circuit to generate data y ij , which are in a binarized state, for example y max  or y min , such as &#34;255&#34; or &#34;0&#34;. 
     On the other hand, a calculator 55 determines the difference between the corrected data x&#39; ij  and the output data y ij , and said difference is stored in a memory position in the error buffer memory 53 corresponding to the pixel position 57 undergoing processing. The next image data are then processed in the same manner, and the obtained error ε ij  is stored in the next right position in the error buffer memory 53. The binary digitization in the error dispersing method is achieved by repeating the above-explained operation. 
     In the above-explained embodiment, dots are generated and arranged in regular manner in the uniform density areas not containing edges, so that specific patterns inherent to the error dispersing method can be suppressed. 
     The dot formation can, if wished, be performed only in the highlight area, by replacing the edge detection circuit 14 shown in FIG. 1 by a highlight area detection circuit 20 shown in FIG. 7. Said highlight area detection circuit 20 is so constructed that a highlight area is identified when the maximum density in 9 (=3×3) pixels in the block does not exceed a threshold value T 3  (for example T 3  =20). Dot formation in the highlight area allows rearrangement of dispersed dots into a regular array of dots of a short pitch, thereby producing regularity without sense of noise, and preventing granular noises experienced in highlight areas. 
     In the foregoing embodiment the dot formation is conducted according to whether an edge or a highlight area is identified in the block. In the following embodiment, the extent of dot formation is changed stepwise according to the density of the input image, thereby achieving smooth image processing. 
     FIG. 8 is a block diagram of an embodiment in which the extent of dot formation is switched stepwise according to the density of the input image, wherein the same components or signals as in FIG. 1 or 7 are represented by the same numbers. 
     The signal 100 corrected by a correction circuit 13 is supplied to an edge detection circuit 14, a pre-processing circuit 16 and a mixer 86. Said signal is transferred in the unit of a block of m×n pixels. In the following explanation it is assumed that m=n=3, but there may naturally be selected other conditions such as m=n=5 or m=3 and n=5. 
     The edge detection circuit 14 discriminates whether the block contains an edge, and releases a signal 200 which is &#34;1&#34; or &#34;0&#34; respectively if any edges are present or absent in the block. 
     FIG. 9 is a block diagram of the preprocessing circuit 85. The corrected signal 100 is supplied to a sum calculation circuit 90 for calculating the sum S of density in the block according to the following equation: ##EQU3## The calculated sum S is supplied as a signal 802 to the mixer 86 and a dot forming circuit 91, which effects dot formation according to the sum S. The sum calculation circuit 90 and the dot forming circuit 91 can be the same as the sum calculation circuit 21 and the dot forming circuit 22 shown in FIG. 2. The data after dot formation are supplied, as a signal 803, to the mixer 86. 
     FIG. 10 illustrates the process in the mixer 86. The signal 802 from the pre-processing circuit 16 and the signal 200 from the edge detection circuit 14 are supplied to a weighting determination circuit 92, which releases weighting signals 811, 812 according to the signals 200, 802. The weighting signals 811, 812 are respectively represented as 1 -α and α (0≦α≦1). These signals are respectively supplied to weighting circuit 93, 94 to obtain weighted signals 813, 814. An adder 95 adds the signals 813, 814 to obtain a signal 804. 
     In the following there will be explained the function of the present embodiment, wherein A ij  (i, j=1, 2, 3) represents the data 803 subjected to dot formation, while D ij  (i, j=1, 2, 3) represents the original data 100. The weighting determination circuit 92 receives the signals 200, 802, in which α is taken as &#34;1&#34; when the signal 200 is &#34;1&#34; indicating the presence of an edge in the block. In this state the signals 811 and 812 are respectively &#34;0&#34; and &#34;1&#34;. As in the foregoing embodiment, the dot formation is not conducted in the edge portion in order not to degrade the resolution. 
     When the signal 200 is &#34;0&#34;, indicating the absence of edges in the block, the value of α is determined according to the value of the signal 802 as shown in FIG. 11. For example, if the signal 802 is &#34;1275&#34;, the signal 812 (α) and the signal 811 (1-α) are respectively taken as 0.56 and 0.44. FIG. 11 shows only an example of the relationship between the signal 802 and α, and said relationship is not limited to this example. Also, the dot formation may be made at an arbitrary density of the signal 802 by suitably varying the relationship between the signal 802 and α. Said relationship can be set in a look-up table. The dot-formed data 803 (A ij ) are multiplied by 1-α, while the original data 100 (D ij ) are multiplied by α, and the thus weighted data 813, 814 are added in the adder 95. Thus the result 804 of addition is obtained according to the following formula: ##EQU4## 
     As explained in the foregoing, the dot formation in the non-edge areas allow prevention of deterioration in the resolution, and the stepwise weighting enables smooth dot formation of the image according to the density. In this manner it is rendered possible to prevent generation of false contour or noises by the dot formation. 
     The signal 804 from the mixer 86 is supplied to the memory 17, and the signal 805 read from said memory 17 is supplied to a binary digitizing circuit 18 for binary digitizing. Said binary digitizing circuit 18 can be the same as the circuit 18 shown in FIG. 1 or 7. The signal 806 from said circuit 18 is supplied to a printer 89 for reproducing a binary image. 
     The above-explained embodiment, in which the dot formation is conducted only in the non-edge areas through edge detection or in the highlight areas through highlight area detection, provides periodic arrangement in the dot arrangement, thereby suppressing particularly fringe patterns encountered in the binary digitizing, for example, in the error dispersion method. Also, dot formation in the highlight areas enables regular arrangement of dots, thus preventing the granular noises. Besides, the mixing, after weighting, of the original data and the data subjected to dot formation according to the image density suppresses the noises generated in the dot formation, and eliminates false contours. Furthermore there can be obtained a reproduced image faithful to the original image, since the original data can be preserved in the dot formation. 
     The foregoing embodiments can be applied also to a color image, by employing the circuit shown in FIG. 1, 7 or 8 in three sets respectively for red, green and blue (or other sets of three colors or the equivalent). In the case of having a circuit like that of FIG. 8 for each of three colors, the relationship between the signal 802 and α shown in FIG. 11 may be varied for respective colors. 
     The present invention has been explained by reference to the preferred embodiments thereof, but it is not limited to such embodiments and is subject to various modifications within the scope and spirit of the appended claims.