JPS6353586B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a method for identifying halftone image regions such as multilevel digitized documents.

Document images often contain a mixture of halftone images (such as photographs), character images, and line images (such as graphs). When transmitting, storing, or otherwise processing such document images, it is generally beneficial to be able to identify areas of halftone images in advance from other areas.

Regarding the identification of halftone image areas in document images, etc., refer to "Parallel field segmentation of free-format documents" described in "Proceedings of the 20th Annual Conference of the Information Processing Society of Japan (1978)" (pages 453 and 454). ``Method for generating image area signals'' described in Japanese Patent Application Laid-open No. 55-100549 are well known.

However, the former method requires a human to check the results each time a process is performed and repeats the process until a satisfactory result is obtained, and is not real-time processing. Further, a buffer memory capable of storing at least two pages of original images is required.

On the other hand, since the latter method does not process an image by dividing it into meshes, the processing time per pixel is long. In order to shorten processing time, the number of scan lines put into the buffer can be reduced, but this will also make the mask smaller and reduce the accuracy of identification. On the other hand, if you want to improve accuracy, you will have to increase the number of scan lines put into the buffer, making the mask larger.
Processing speed decreases and the burden of creating and maintaining mask patterns increases. Furthermore, when this method is applied to multivalued digitized images, creating and maintaining mask patterns becomes a significant burden.

The present invention has been made in view of the above-mentioned problems, and its purpose is to provide a method suitable for identifying areas of halftone images of multivalued digitized images, particularly document images, in real time. It is in.

Another object of the present invention is to provide a method for identifying halftone images that does not require large buffer memory or human intervention.

Therefore, in the present invention, an image such as a multi-level digitized document is divided into meshes of a predetermined size, and each mesh is calculated as a halftone image regarding the density level of a pixel or the density level difference between adjacent pixels. Check whether the requirements are met. Then, when this requirement is satisfied, “1”
A bit pattern (referred to as a sample space) is created in which bits corresponding to the mesh set to (or "0") are arranged according to the mesh arrangement on the image. For each bit (x) of "0" (or "1") on the column (n-1) immediately before the arbitrary column (n) of interest among the columns in the main scanning direction of this sample space, When a predetermined number or more of "1" (or "0") bits are adjacent, the bit (x) is changed to "1" (or "0"). Then, among the "1" (or "0") bits on column (n-1), each bit that is not connected in the main scanning direction by a predetermined number or more is changed to "0" (or "1"). Next, among the "1" (or "0") bits on the column of interest (n), each bit that is not connected to a predetermined number of "1" (or "0") bits in the sub-scanning direction is set to "0". ” (or “1”)
Change to Thus, a "1" (or "0") bit on column (n) indicates that the corresponding mesh is a region of a halftone image.

When the processing of the attention column (n) is finished, the attention column is set to 1.
By repeating similar processing while sequentially shifting columns, the halftone image area of the entire image is identified.

Next, an embodiment of the present invention will be explained in order of processing steps.

[1] The original image to be processed, such as a document, is read with a scanner and converted into a multi-level digital image. Here, it is assumed that the pixel density level is digitized into 17 values from 0 (white) to 16.

In the present invention, an image is M
Pixel (sub-scanning direction) x N pixels (main-subscanning direction)
Use meshes divided into sizes of . Here, the scanning line density of the image reading scanner is 8 lines/mm in both the main and sub-scanning directions, and M=N=
16, but it can be determined appropriately depending on the type of scanner. Furthermore, M≠N is also allowed.

[2] While reading the 17-value digitized image for 16 scanning lines, check for each mesh the necessary conditions for a halftone image regarding the pixel density level or the density level difference between adjacent pixels (if these are not met, the mesh will be halftone). Check whether conditions (conditions that cannot occur in the image area) are satisfied. In this example,
The following two conditions are determined.

(b) Divide the range of density levels 0 to 16 into three level regions. Here, 0 to 4 are low level regions, 5 to 12 are intermediate level regions, and 13 to 16 are high level regions. The 17-value digitized image is ternarized into these three level regions, and for each mesh, the number of pixels belonging to the low level region n ₁ and the number of pixels belonging to the intermediate level region n ₂
are counted, and if n ₂ n ₁ , the flag f ₁ is set to "1" for that mesh.

(b) In parallel with the determination in (a) above, calculate the frequency distribution of density level differences (absolute values) between adjacent pixels for each mesh. In this embodiment, only a set of pixels adjacent in the main scanning direction is considered as a set of adjacent pixels (this is generally valid). Since the mesh size is 16×16, the number of samples is 15×16=
It becomes 240. When the sample with the highest frequency is other than 0, that is, when there are many pairs of adjacent pixels with a density level difference (absolute value) of 1 or more,
The flag _f2 is set to "1" for that mesh.

(c) Take the logical sum f=f ₁ ∨f ₂ of the above flag f ₁ and flag f ₂ for each mesh, and write it to the bit corresponding to the mesh in the buffer. This bit f has a one-to-one correspondence with the mesh, and when it is "1", it means that the corresponding mesh satisfies the necessary conditions as a halftone image.

In this way, a pattern of binary bits (f) obtained by reducing the original image to 1/16 (because M=N=16) in both the main and sub-scanning directions is found in the buffer. This bit pattern is called the sample space. The bit string in the main scanning direction of the sample space corresponds one-to-one to a set of 16 scanning lines of the original image, and will be referred to as a "sequence". The subsequent processing is performed on the sample space.

[3] Assume that on the sample space shown in FIG. 1, column n is a column of interest in which a halftone image is to be identified. A bit
corresponds to the mesh directly above the corresponding mesh)
Find out the value of .

If bit

If bit
+C+D)3), convert bit X to "1"; otherwise, leave bit

This processing stage performs so-called fusion processing, and when the bit C of interest advances to the rightmost end, the process moves to the next processing stage.

[4] Length of a run of “1” (a series of “1” bits) on the column n-1 before the column n of interest (run length)
l is compared with a predetermined threshold value L, and all bits in the "1" run where l<L are converted to "0".

In this processing step, a process is performed to remove from the target halftone image area an area other than an area extending in the main scanning direction with a width of L mesh or more. If the scanning line density of the scanner is 8 lines/mm for a horizontally written document, it is generally appropriate to set L=4. In other words, only areas that extend in the main scanning direction with a width of 8 mm or more are subject to evaluation as halftone image areas. In other words, the threshold value L should be appropriately selected depending on the type of image to be processed and the purpose of subsequent processing.

When the above processing is completed for all bits of column n-1, the process proceeds to the next stage.

[5] If the noted bit Y of the noted column n is “0”, leave it as is; if it is “1”, as shown in Figure 2,
The values of the upper and lower bits E and Y are checked, and if both bits are "0", the noticed bit Y is converted to "0" and the noticed bit is shifted to the right. In other words,
Among the "1" bits on the column of interest n, two or more "1" bits are not connected in the sub-scanning direction.
Convert to “0”.

In this processing stage, a process is performed in which areas with a small spread in the sub-scanning direction are excluded from evaluation targets for halftone image areas. In this example, the spread in the sub-scanning direction is 2 mesh widths, that is, 8 lines/mm.
If the scanning line density is , areas with a width of less than 4 mm are excluded from evaluation of halftone image areas.

It goes without saying that the condition for the number of quick connection bits may be increased or decreased depending on the minimum width of the evaluation target area in the sub-scanning direction.

Now, the value of the bit on column n after completing the processing step [5] indicates the determination result of the corresponding mesh. In other words, the mesh corresponding to the "1" bit is identified as a halftone image area.

After completing the identification process for the column n of interest, the next column n+
1 is set as the column of interest again and the same process is executed. Thereafter, the column of interest is sequentially shifted to identify the entire image.

Note that the next column (n+1) of the column of interest (n) is referred to in the processing step [5]. In other words, [5]
The next column (n+
It is sufficient if the processing results of [1] and [2] for 1) are completed in time. Therefore, if this embodiment is to be executed in real time, the capacity of the sample space buffer for four columns will suffice. It is also clear that when the determination result and the original image are output in synchronization, a memory with a capacity of 32 (=2×M) scanning lines is sufficient as a buffer for storing the original image.

Additionally, the various conditions (the size conditions described above) in this embodiment can be applied to both horizontally written documents and vertically written documents if the main scanning direction is selected to be parallel to the character lines.

An example of a device for realizing the above embodiment is shown in the third example.
It is shown and explained in the figure.

201 is a scanner that reads the original image, converts it into 17-level digital data, and sends it. This original image data is stored in buffer 202 via control interface 203. Batsuhua 202 is
It can be configured with a memory or shift register with a capacity for 2M (M=16) scanning lines. The original image data is also sequentially input to arithmetic circuits 204 and 205. The arithmetic circuit 204 executes the arithmetic operation in (a) of [2] above, and outputs the flag _f1 . Arithmetic circuit 205
executes the operation (b) in [2] above, and sets the flag f ₂
Output. The flags f ₁ and f ₂ are logically summed by the OR circuit 211 and the resultant f is written into the sample space buffer 206 through the control interface 207 . The buffer 206 only needs to have a capacity that can store four columns of sample space. 208 is a microprocessor for executing the processes [3] to [5] above, and a program therefor is stored in the control memory 209.

Processor 208 accesses the sample space within buffer 206 via common bus 212 and control interface 207 to perform predetermined processing. The final processing result and the original image data output from the buffer 202 are sequentially sent out from the output interface 210 via the common bus 212 in synchronization with the scanning of the original image.

The present invention has been described in detail above, and it is possible to identify a halftone image area in an image such as a document by real-time processing without using a large capacity buffer or requiring the intervention of human judgment. It is possible, and the effects are significant.

[Brief explanation of drawings]

FIGS. 1 and 2 are explanatory diagrams of processing in a sample space in an embodiment of the present invention, and FIG. 3 is a block diagram showing an example of an apparatus for implementing the present invention. 201... Scanner, 202... Original image buffer, 204, 205... Arithmetic circuit, 206... Sample space buffer, 208... Microprocessor, 209... Control memory, 203, 207...
Control interface, 210...Output interface, 212...Common bus.

Claims (1)

[Claims] 1 Divide a multivalued digitized image into meshes of a predetermined size, check whether each mesh satisfies the requirements for a halftone image regarding pixel density levels or density level differences between adjacent pixels, and when the requirements are met. A sample space is created in which mesh-corresponding bits set to "1" (or "0") are arranged according to the mesh arrangement on the image, and among the columns in the main scanning direction in the sample space, A predetermined number or more of “1” (or “0”) in each bit (x) of “0” (or “1”) on the column (n-1) immediately before any column (n) of interest. When the bits are adjacent, each bit (x) is set to “1” (or “0”)
Then, among the "1" (or "0") bits on the column (n-1), each bit that is not connected in the main scanning direction for a predetermined number or more is changed to "0" (or "1"). and then “1” on the column (n)
(or "0") bits in which "1" (or "0") bits are not connected in the sub-scanning direction more than a predetermined number of bits are changed to "0" (or "1"). A halftone image identification method characterized in that a mesh corresponding to a "1" (or "0") bit on column (n) is determined to be a region of a halftone image.