Image Processing Apparatus Using Two-Dimensional Space Frequency to Discriminate Image Type

1. Field of the Invention

The present invention relates to an image processing apparatus capable of image discrimination.

2. Description of the Prior Art

The known digital image processing apparatus of this sort only has an insufficient precision in the image identification and is incapable of faithfully reproducing the entire image area of an original including a picture image, a character or a line image and a dot (of screen-tone) image, since a series of image processing procedures based on erroneous image discrimination is applied over the entire area of the original image. Particularly, it has been difficult to distinguish a dot image from a character or line image, and the dot image cannot be reproduced satisfactorily when processing for a character image area is applied also to a dot image area.

An object of the present invention is to eliminate the drawbacks mentioned above.

Another object of the present invention is to provided an improvement in an image processing apparatus capable of image discrimination.

Still another object of the present invention is to provide an image processing apparatus capable of exact image discrimination.

Still another object of the present invention is to provide an image processing apparatus capable of providing a reproduced image of a high quality.

Still another object of the present invention is to provide an image processing apparatus capable of providing an image which is a faithful reproduction of the original image.

Still another object of the present invention is to provide an image processing apparatus capable of providing a faithfully reproduced image by exactly discriminating different image areas and applying an appropriate image processing to the nature of image for each image area.

Still another object of the present invention is to provide an image processing apparatus capable of exactly distinguishing a dot image from a character or line

Still another object of the present invention is to provide an image processing apparatus capable of high-speed image processing.

According to the present invention, these objects are attained by providing an image processing apparatus in which input image data is binarized, and image tone is discriminated by means of an examination of the characteristics of two dimensional space frequency relating to the input image data, on the basis of the binary data. This processing is preferably carried out with the entered data divided into blocks, the nature of the image in each block being determined individually. More specifically, in one embodiment, the number of transitions of the binary data in a block may be obtained by way of the discrimination. Alternatively, the sum of the differences in density of adjacent image data may be used for the discrimination. The sum is in one embodiment the sum of the absolute values of the differences. The discrimination preferably discriminates half-tone image, line image and dot image. Processing to smooth the image data in each block and, e.g., reproduce a dot image using half-tone processing, may be provided. Non-half-tone processing is preferably also provided for data to which such processing is appropriate. The binarization may be performed on the basis of the average value of the data in a block.

The foregoing and still other objects and features of the present invention will be more fully appreciated from the following detailed description of the preferred embodiments, which is to be taken in conjunction with the attached drawings.

FIG. 1 is a chart showing density distribution when an original is divided into image blocks of 8.times.8 pixels each;

FIG. 2 is a chart showing an example of an binary digitized pattern obtained from the original shown in FIG. 1;

FIG. 3 is a block diagram showing an embodiment of the image processing apparatus of the present invention;

FIG. 4 is a flow chart showing the procedure of image processing executed by a microprocessor GP;

FIG. 5 is a schematic view showing the structure of an image memory IM;

FIG. 6 is a chart showing an example of density distribution when the original image is divided into image blocks of 8.times.8 pixels each;

FIG. 7 is a chart showing an example of a dither matrix;

FIG. 8 is a flow chart showing the procedure of image processing in a second embodiment of the present invention;

FIG. 9 is a flow chart showing the procedure of image processing in a third embodiment of the present invention; and

FIG. 10 is a chart showing the relationship between T and .DELTA.D.sub.max in various images.

Now the present invention will be clarified by detailed description of the preferred embodiments thereof shown in the attached drawings.

First will be explained in steps the image discriminating algorithm of the present embodiment.

An original image is read with a scanner, for example, composed of a charge-coupled device, and is digitized to obtain a digital image, which is then divided into blocks of N.times.M pixels each, wherein N indicates the number of pixels in the main scanning direction, while M indicates the number of pixels in the subsidiary scanning direction. In the case that the scanner has a resolving power of 16 pixels/mm, for example, it is found that M and N should preferably be equal to 8. It is therefore assumed that the image is divided into blocks of 8.times.8 pixels.

The density of each pixel in each block is binary-digitized with a fixed threshold value to obtain a binary block pattern. Then, in said binary block pattern, there is determined the sum S of the number of transitions of binary levels between immediately neighboring pixels.

As an example, in an image block of N.times.M=8.times.8 shown in FIG. 1, in which the density in each pixel can vary from 0 (white) to 15 (black), a binary digitizing with a fixed threshold value at a level 7 provides a binary block pattern shown in FIG. 2. In the first main scanning line l1 (uppermost row), there exist two transitions ##EQU1##

The total number S of the transitions in all the main and subsidiary scanning lines is equal to 27 in the example shown in FIG. 2. It is to be noted that said number S may vary from 0 to M(N-1)+N(M-1).

The average of the densities of the pixels in the thus divided block is determined. In the example shown in FIG. 1, the average density is approximately equal to 5. Said average density may be employed in obtaining the binary block pattern in Step 2.

The aforementioned total number S obtained in each block is compared with pre-determined values P1, P2 to discriminate the nature of the image according to the following criteria: ##EQU2## wherein P1<P2.

The above-mentioned criteria of discrimination are based on the statistics that the two-dimensional spatial frequency of the original decreases in the order dot image>character image>picture image, and, in the present embodiment there are practically employed a value in a range of 8-10 for P1 and a value in a range of 20-24 for P2. In the present embodiment the total number S of transitions is determined on a binary block pattern obtained with a fixed threshold value from each block, but it is also possible to use two fixed threshold values to obtain two binary block patterns, to determine the total number of transitions in each binary block pattern and to discriminate the nature of the image according to the result of these calculations. In any case it is required to obtain a value enabling to discriminate the two-dimensional variation of the image density.

The pixels in each block are converted into binary image signals according to the result of discrimination in Step 4.

(5-1) : In the case that the block is discriminated as a picture image area, the pixels in the block are subjected to a dither process, in which the image densities in the block are respectively compared with threshold values for example in an 8.times.8 threshold value matrix to obtain binary signals "1" or "0".

(5-2) : In the case that the block is discriminated as a character image area, the binary block pattern as shown in FIG. 2 is released without further process. Otherwise the binary block pattern may be obtained by binary digitizing in which the average density determined in Step 3 is used as a fixed threshold value.

(5-3) : In case the block is discriminated as a dot image area, the densities of the pixels in the block are replaced by the average density ("5" in this example) obtained in the Step 3 before proceeding to the dither processing. Stated differently, the process employed in the dot image area is so-called density pattern processing, and the dither matrix to be employed in this case is preferably of a dot concentrated type, in which, as shown in FIG. 7, the threshold value gradually increases or decreases around a certain point. It is rendered possible to suppress noises which are generally generated as Moire stripes as the result of interference between a dot image of a high spatial frequency and the pattern of the dither matrix for binary digitizing, by calculating the average density for each block and applying a dither matrix of the dot concentrated type.

Steps 1 to 5 of the above-described algorithm are repeated in succession for different blocks, and it is rendered possible to binary digitize on original document on a semi-real time basis for image reproduction on a binary printer such as a laser beam printer.

Now there will be explained an embodiment of the image processing apparatus of the present transition, which performs the above-explained image processing by means of a computerized procedure, particularly the software of a microcomputer designed exclusively for image processing and having the structure of a multi-microprocessor. FIG. 3 is a block diagram of the structure of the present embodiment, in which are shown a scanner SC composed of a charge-coupled device for reading the original image, a microprocessor GP exclusively for image processing, and a laser beam printer PR. The original image is read by the scanner SC, and the obtained image signal is subjected to analog-to-digital conversion by an unrepresented A/D converter and temporarily stored in an image memory IM. The image data in the image memory IM are processed by a software of the microprocessor GP according to the aforementioned algorithm for conversion into binary signals, which are supplied to the laser beam printer PR. A microprocessor SP controls the entire system according to a program stored in a program memory SM, and the image memory IM is utilized in the course of the image processing.

FIG. 4 is a flow chart showing the procedure of image processing executed by the microprocessor GP shown in FIG. 3. In the illustrated procedure, steps 1 and 2 take image data from the image memory IM and form blocks of 8.times.8 pixels each, and Step 3 binary digitizes the data of each pixel in the block with a fixed threshold value and determines the total number S of the transitions Steps 4 and 5 discriminate the nature of the image according to the thus determined number S. If the discriminations at steps 4 and 5 both provide negative results, the block is discriminated as a screen-tone image area and Step 6 determines the average density in the block and replaces the data of the pixels in said block with said average density. Then Step 9 applies a dither process to the block in which the density is homogenized. On the other hand, in the case that the discriminations in Steps 4 and 5 respectively provide negative and affirmative results, the block is discriminated as a character image area and the program proceeds to Step 7, which releases the binary data obtained in Step 3 without any change. In case the discrimination in Step 4 provides an affirmative result, the block is discriminated as a picture image area, and the block is subjected to a dither process in Step 8. Step 10 stores the binary data of the block obtained in Steps 7, 8 or 9 into the image memory IM.

In the present embodiment, the image memory IM is so constructed, as shown in FIG. 5, to store at least pixel data of multiple levels of 16 lines and binary data of 16 lines, wherein a line corresponds for example to a main scanning line read by the scanner. Memory areas a1, a2 are used for storing the pixel data sequentially read by the scanner SC and for reading said data in a unit of 8.times.8 pixels. For example the memory area al serially stores the pixel data from the scanner SC, while pixel data in the unit of each block of 8.times.8 pixels are read from the memory area a2 by the microprocessor GP. Also for example a memory area b1 is used for storing binary data of each block of 8.times.8 pixels by the microprocessor GP, while binary image data already stored are sequentially read in the direction of scanning lines from a memory area b2, and supplied to the printer PR for image reproduction. In this manner the present embodiment simultaneously performs, through parallel data processing with plural microcomputers, the write-in of multi-level pixel data and the read-out in the unit of block of multi-level pixel data, and also simultaneously performs the write-in of binary data in the unit of a block and the read-out of binary data. It also can calculate the parameter S two-dimensionally at a high speed and can therefore process and release the image data on substantially real time basis. The scanner SC and the printer PR are controlled by the microprocessor SP in synchronization with the microprocessor GP.

In the following there will be explained, as a variation of the foregoing first embodiment, the binary digitizing method for the preparation of the binary block pattern in the Step 2. Though a genuine binary digitizing with a fixed threshold value "7" is employed in the foregoing embodiment, it is also possible, for improving the precision of discrimination of a picture image area, to inspect the change in the density in the main or subsidiary scanning direction, and invert the binary signal (for example from "0" to "1") when the difference in the densities between the neighboring pixels exceeds a determined value .DELTA.L. As an example, if a photographic image area shows a density distribution 5.fwdarw.7.fwdarw.6.fwdarw.6.fwdarw.8 for a .DELTA.L equal to 7, the corresponding binary density pattern is 0.fwdarw.0.fwdarw.0.fwdarw.0.fwdarw.0, thus including no transitions. Since a drastic density change rarely appears in a picture image area, this method allows a more accurate discrimination of the picture image area.

It is also effective to determine the difference between the density of a pixel and the average density of 8 pixels two-dimensionally surrounding said pixel and to invert the binary signal when said difference exceeds a determined value .DELTA.L.

In the foregoing embodiment three binary digitizing processes are selectively applied to the image data according to the result of discrimination thereof, but it is also possible to achieve a faster image processing by applying three binary digitizing processes in parallel to the same image data and selecting one of three series of binary image data thus obtained according to the result of discrimination.

In the following there will be stepwise explained in steps the image discriminating algorithm in a second embodiment of the present invention.

An original image is read with a scanner composed, for example, of a charge-coupled device, and is digitized to obtain a digital image, which is then divided into blocks of N.times.M pixels each, wherein N indicates the number of pixels in the main scanning direction, while M indicates the number of pixels in the subsidiary scanning direction. In the case that the scanner has a resolving power of 16 pixels/mm, it is found that M and N should preferably be equal to 8. It is therefore assumed that the image is divided into blocks of 8.times.8 pixels.

In each divided block, there is determined, in the main and subsidiary scanning directions, the density difference between immediately neighboring pixels, and a total sum T of the absolute values of said differences is calculated. As an example, in a block of N.times.M=8.times.8 as shown in FIG. 6, there is obtained a sum T=455. Said sum T is obtained according to an equation (1) to be explained in connection with a third embodiment of the present invention.

In the above-shown example in which the density can vary from 0 (white) to 15 (black), the sum T may vary from 0 to 1680 according to the nature of the image.

The average of the densities of the pixels in thus divided block is determined. In the example shown in FIG. 6, the average density is approximately equal to 5.

The aforementioned total sum T obtained in each block is compared with predetermined values R1, R2 to identify the nature of the image according to following criteria: ##EQU3## wherein R1<R2.

The above mentioned criteria of discrimination are based on the statistics that the two-dimensional spatial frequency of the original decreases in the order of dot image>character image>picture image, and the values R1, R2 are determined according to the reproducing ability of the apparatus for character and dot images.

In the present embodiment the total sum T of the absolute values of the density difference between the neighboring pixels is determined for each block, but it is also possible to obtain a parameter representing the nature of the image by applying a determined operation to the density difference between the neighboring pixels. In any case it is required to obtain a value enabling to identify the two-dimensional variation of the image density.

The pixels in each block are converted in to binary image signals according to the result of discrimination in Step 4.

(5-1): In the case that the block is discriminated as a picture image area, the pixels in the block are subjected to a dither processing, in which the image densities in the block are respectively compared with threshold values, for example, in an 8.times.8 threshold value matrix to obtain binary signals "1" or "0". The dither matrix shown in FIG. 7 is of dot concentrated type capable of reproducing 16 density levels. The densities shown in FIG. 6 are binary digitized by the corresponding threshold values in the dither matrix to obtain white "1" and black "0" signals.

(5-2): In the case that the block is discriminated as a character image area, there is effected a complete binary digitizing with a fixed threshold value. In the present embodiment, a threshold value "7" equal to a half of the maximum density level is adopted for binary digitizing, but it is also effective to select the threshold value in response to the background density (for example the minimum density or most frequently appearing density) of the original image in the block. Also the average density in each block may be adopted as the threshold value.

(5-3): In the case that the block is discriminated as a dot image area, the densities of the pixels in the block are replaced by the average density obtained in Step 3, before proceeding to the dither process with the dither matrix shown in FIG. 7. Stated differently, the process employed in the dot image area is a so-called density pattern processing, and the dither matrix to be employed in this case is preferably of a dot concentrated type, because it is possible to suppress noises generally generated as Moire stripes as the result of interference between a dot image of a high spatial frequency and the pattern of the dither matrix for binary digitizing, by calculating the average density for each block and applying a dither matrix of the dot concentrated type.

Steps 1 to 5 of the above-described algorithm are repeated in succession for different blocks, and it is rendered possible to binary digitize an original document on a semi-real time basis for image reproduction on a binary printer such as a laser beam printer.

Now there will be explained an image processing apparatus of the second embodiment of the present invention.

As in the first embodiment, the image processing apparatus of the second embodiment performs the above-explained image processing by means of a computerized procedure, particularly a software of a microcomputer designed exclusively for image processing and having the structure of multi-microprocessor.

The circuit structure can be same as that shown in FIG. 3 and will not therefore be explained in detail.

FIG. 8 is a flow chart showing the procedure of image processing executed by the microprocessor GP. In the illustrated procedure, Steps 1 and 2 take image data from the image memory IM and form blocks of 8.times.8 pixels each, and Step 3 determines the total sum T of the absolute values of the density differences between the immediately neighboring pixels in the block as explained before. Steps 4 and 5 identify the nature of the image according to thus determined sum T. In the case that the discriminations in Steps 4 and 5 both provide negative results, the block is identified as a dot image area and a Step 6 determines the average density in the block and replaces the data of the pixels in the block with said average density. Then a Step 9 applies a dither processing to the block in which the density is homogenized. On the other hand, in the case that the discriminations in Steps 4 and 5 respectively provide negative and affirmative results, the block is discriminated as a character image and the program proceeds to Step 7, in which the pixels in the block are binary digitized with a fixed threshold value. In the case that the discrimination in Steps 4 provides an affirmative result, the block is discriminated as a picture image area, and the block is subjected to a dither processing in Step 8. A step 10 stores the binary data of the block obtained in Steps 7, 8 or 9 into the image memory IM.

Also in the second embodiment, the image memory IM is capable, as shown in FIG. 5, of storing at least pixel data of multiple levels of 16 lines and binary data of 16 lines, wherein a line corresponds for example of a main scanning line read by the scanner. Memory areas a1, a2 are used for storing the pixel data sequentially read by the scanner SC and for reading said data in a unit of 8.times.8 pixels. For example the memory area al serially stores the pixel data from the scanner SC, while pixel data in the unit of a block of 8.times.8 pixels are read from the memory area a2 by the microprocessor GP. Also for example, a memory area b1 is used for storing binary data of each block of 8.times.8 pixels by the microprocessor GP, while binary image data already stored are sequentially read in the direction of scanning line from a memory area b2 and supplied to the printer PR for image reproduction. In this manner the present embodiment simultaneously performs, through parallel data processing with plural microcomputers, with write-in of multi-level pixel data and the read-out in the unit of block of multi-level pixel data, and also simultaneously performs the write-in of binary data in the unit of a block and the read-out of binary data. It also can calculate the parameter T two-dimensionally at a high speed and can therefore process and release the image data on substantially a real time basis.

In the foregoing embodiment three binary digitizing processes are selectively applied to the image data according to the result of discrimination thereof, but it is also possible to achieve a faster image processing by applying three binary digitizing processes in parallel manner to same image data and selecting one of three series of binary image data thus obtained according to the result of discrimination.

In the following there will be explained in steps the image discriminating algorithm in a third embodiment of the present invention.

An original image is read with a scanner composed for example of a charge-coupled device, and is digitized to obtain a digital image, which is then divided into blocks of N.times.M pixels each, wherein N indicates the number of pixels in the main scanning direction, while M indicates the number of pixels in the subsidiary scanning direction. In the case that the scanner has a resolving power of 16 pixels/mm, the most preferred value for M is 4 or 8.

(Step 2)

In each of the thus divided blocks there are calculated the total sum T of the absolute values of the density differences between the immediately neighboring pixels and a maximum density difference .DELTA.D.sub.max between the maximum and minimum densities in said block, and an image tone parameter PS=T/.DELTA.D.sub.max is calculated for each block.

Said sum T is obtained by the following equation: ##EQU4## wherein D(i,j) represents the density of each pixel in the block and said image tone parameter PS can be regarded as a value equivalent to the two-dimensional spatial frequency. Consequently the variation of the image density can be two-dimensionally discriminated from said parameter PS.

The aforementioned parameter PS obtained in Step 2 is utilized to identify the nature of the image according to following criteria: ##EQU5## wherein A and B are predetermined values, and, for example, A is selected in a range from 1 to 2 while B is selected equal to or larger than 8.

Binary digitizing is conducted in one of following three methods according to the image tone discriminated in Step 3:

(i) For a picture (half tone) image area:

"0" for D(i,j).ltoreq.M(i,j)

wherein M(i,j) represents an array of threshold values generally called a dither matrix of a size which, in the present embodiment, is same as that of the block (M.times.M) but is generally represented as 2n.times.2n (n=1, 2, 3, . . . ). The distribution of the threshold values in said matrix can be a scattered type as represented by Beyer's matrix, a concentrated type resembling a dot screen, or any other types:

(ii) For a character (line) image area:

"0" for D(i,j).ltoreq.K

wherein K is a fixed threshold value approximately equal to half of the maximum density. For example, if the maximum density is at the 63th level, K is selected at about 31st level:

(iii) For a dot tone image area: ##EQU6## In this case the average density is determined in the block and is binary digitized with the dither matrix M(i,j). A reproduction more faithful to the original is possible by the use of a dither matrix of a dot concentrated type.

A higher speed in the data processing can be attained by processing the same image data with the above-described processes in parallel and selecting one of thus obtained three series of binary digitized data according to the result of discrimination.

Now there will be explained an image processing apparatus of the third embodiment of the present invention.

As in the first embodiment, the image processing apparatus of the third embodiment performs the above-explained image processing by means of a computerized procedure, particularly the software of a microcomputer designed exclusively for image processing and having a structure of multiple microprocessors.

The circuit structure can be same as that shown in FIG. 3 and will not therefore be explained in detail.

FIG. 9 is a flow chart showing the procedure of image processing executed by the microprocessor GP. In the illustrated procedure, Steps 1 and 2 take image data from the image memory IM and form blocks of 4.times.4 or 8.times.8 pixels each, and a Step 3 determines the maximum density difference .DELTA.D between the maximum and minimum densities, and calculates the total sum T of the absolute values of the density differences between the immediately neighboring pixels according to the equation (1), thus determining the image tone parameter PS=T/.DELTA.D.sub.max Steps 4 and 5 discriminate the nature of the image according to thus determined parameter PS. In case the discriminations at the steps 4 and 5 both provide negative results, the block is discriminated as a dot image area and a Step determines the average density in the block and replaces the data of the pixels in the block with said average density. Then Step 9 applies a dither process to the block in which the density is homogenized. On the other hand, in the case that the discriminations in Steps 4 and 5 respectively provide negative and affirmative results, the block is discriminated as a character image area and the program proceeds to Step 7, in which the pixels in the block are binary digitized with a fixed threshold value. In the case that discrimination in Step 4 provides an affirmative results, the block is discriminated as a picture image area, and the block is subjected to a dither processing in Step 8. Step 10 stores the binary data of the block obtained in Steps 7, 8 or 9 into the image memory GM.

In the case that of data processing for a block of 8.times.8 pixels in the third embodiment, the image memory GM is capable, as shown in FIG. 5, of storing at least the multi-level pixel data of 16 lines and binary pixel data of 16 lines, in which a line discriminates a main scanning line read for example by the scanner. Memory areas a1, a2 are used for storing the pixel data sequentially read by the scanner SC and for reading said data in a unit of 8.times.8 pixels. For example, the memory area a1 serially stores the pixel data from the scanner SC, while pixel data in the unit of a block of 8.times.8 pixels are read from the memory area a2 by the microprocessor GP. Also, for example, a memory area b1 is used for storing binary data of each block of 8.times.8 pixels by the microprocessor GP, while binary image data already stored are sequentially read in the direction of scanning line from a memory area b2 and supplied to the printer PR for image reproduction. In this manner the present embodiment simultaneously performs, through parallel data processing with plural microcomputers, with write-in of multi-level pixel data and the read-out in the unit of block of multi-level pixel data, and also simultaneously performs the write-in of binary data in the unit of a block and the read-out of binary data. It also can calculate the parameter PS at a high speed and can therefore process and release the image data on substantially real time basis.

FIG. 10 shows a planer plotting of the maximum density difference .DELTA.D.sub.max in a block as a function of the total sum T of the absolute values of the density differences between the neighboring pixels for various images, including picture, character and dot images. FIGS. in the dot images represent the density of the screen, while those in the character images represent the character size. Picture images are principally of human faces. As will be understood from FIG. 10, the parameter T/.DELTA.D.sub.max can clearly separate the domains of these images.

Furthermore, the present embodiment allows one to significantly improve the precision of distinction between a high-density dot image area and a character image area.

Constants employed in FIG. 10 are: M=4, A=1 to 2, and B=8 or larger.

In the foregoing embodiment, the image tone parameter PS is defined by T/.DELTA.D.sub.max, but said parameter may diverge to infinity in a picture image area where T and .DELTA.D.sub.max may converge to zero. In order to avoid such inconvenience, the image tone parameter may be also be defined in the following manner:

wherein C1 is a constant; or

wherein PS=T/.DELTA.D.sub.max, and C2 is a constant.

In the foregoing embodiment the image tone parameter PS is calculated from the maximum density difference .DELTA.D.sub.max, but said difference may be replaced by the average density in the block or by the arithmetic average of the maximum and minimum densities in the block.

The foregoing embodiments discriminate the nature of image of each block, but it is also possible, with the above-described methods, to discriminate each pixel. In this case plural pixels surrounding an object pixel are taken as a block, to which the above-described methods are applied to discriminate said object pixel. In this manner it is rendered possible to determined the processing method for each pixel and to obtain a more faithful reproduction of the image.

The present invention is not limited to the foregoing embodiments but is subject to various modifications within the scope and spirit of the appended claims.