JPH0832816A - Image compression method - Google Patents

Abstract

(57) [Abstract] [Purpose] By integrating a plurality of connected components and cutting them out as one pattern, it is possible to improve the prediction accuracy of the symbol sequence and the position and enable a high compression rate. [Structure] A thickening / thinning processing unit 102 performs thickening processing as preprocessing on an input image, and then adds thinning processing that does not affect a connected component. 1 due to deterioration such as scratches
The pattern separated by about pixels becomes a pattern in which the connected components are integrated by the thickening and thinning processing, and can be cut out in a shape closer to the original pattern. The pattern cutout unit 103 cuts out a connected component from the preprocessed image,
The template generation matching unit 104 performs pattern matching to create and update the template.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention improves the prediction efficiency by accurately cutting out a symbol composed of a plurality of connected components such as Chinese characters, and an image which is efficiently coded when performing predictive coding. Regarding the compression method.

[0002]

2. Description of the Related Art A connected component is cut out from a document image, one connected component is regarded as one pattern and registered as a template, and among the cut out patterns, a similar pattern is replaced with a template to obtain image information. There are image compression methods that reduce (see, eg, US Pat. No. 5,303,313).

FIG. 14 shows the configuration of the conventional image compression apparatus described in the above publication. The image compression apparatus includes an image analysis unit 1401 and a predictive coding unit 1402. The image analysis unit 1401 matches a pattern cutout unit 1403 that cuts out a pattern from a document image and a cutout pattern with a registered template. A pattern matching unit 1404 that takes a pattern, a character that succeeds in matching are integrated into the template, and a character that fails in matching is created in a template and registered in a template generation unit 1405, and a rearrangement process that rearranges the characters in reading order. The unit 1406.

FIG. 15 is a diagram for explaining a conventional image compression method. 1501 is a document image composed of English characters, 150
2 is a template, 1503 is position information, and 1504 is a symbol (template number). Document image 1501
The connected component (character pattern) is cut out from. In the example of the figure, first, the connected component “H” is cut out, and this is subjected to pattern matching with the pattern registered in the template 1502. In this case, since nothing is registered, no matching is performed and the connected component “H” is newly registered as a template. In addition, the connected component “H” is the symbol “1”.
Expressed by (template number), its symbol 1504
And the position information (eg, the position of the center of gravity) 1503 of That is, each clipped connected component (character pattern) is represented by the symbol 1504 and the symbol position information 1503.

Next, the connected component "e" is cut out, and since this also does not match the pattern registered in the template, it is newly registered as a template and is represented by the symbol "2". Hereinafter, connected components “t”, “o”,
Similarly, “l”, “d”, and “m” are processed and registered as templates, symbols “3” to “7” are assigned to each, and the position information is stored in the memory.

Then, when the next "e" after "m" is cut out, this connected component "e" matches the pattern "e" registered in the template, and is not newly registered as a template. However, an average of the registered pattern and the matched pattern (or a representative value of both patterns) is created to update the template. As a result, similar patterns are updated so that their representative patterns are registered.

Also, the already assigned "2" is assigned to the symbol. In the same manner, when the symbols up to the number “9” are used in the same manner, the character “h”,
Symbols "a" and "b" are assigned to "a", respectively.

As described above, the document image includes a symbol string (template number string), symbol position information, and
It is decomposed into pattern information of each template. And
By predictively encoding these pieces of information by the predictive encoding unit 1402, the image is compressed at a high compression rate. As described above, the above-described conventional compression method is a method that considers compression of a text image, that is, since the typed characters are originally the same pattern, a large compression is achieved by eliminating the redundancy in this information. It is a method of obtaining a rate.

[0009]

By the way, when the pattern is cut out as described above, the characters are not extracted in the correct reading order. That is, when scanning a document from top to bottom (and from left to right) in sequence with an image input device,
In the example of FIG. 15, the characters “H”, “t”, and “l” are extracted, and “t” is extracted before the character “e” next to “H”.

If the symbols can be rearranged in the order of reading rather than encoding the symbol string which is not in the correct reading order, the prediction efficiency of the symbol string can be improved and a high compression rate can be obtained. Therefore, conventionally, the reading order is rearranged as follows.

FIG. 16 is a diagram for explaining rearrangement into the conventional reading order. The rearrangement is performed as follows. (1) Register a pattern in a row. First, the pattern "A"
To the line (currently registered line).

(2) According to the coordinate of the horizontal axis (x-axis) of the next pattern, temporary insertion is performed at an appropriate place in the current row.
The next pattern is "E", which is provisionally inserted at the position shown in FIG.

(3) If the horizontal projection of the pattern overlaps the adjacent pattern (or the adjacent pattern), it is registered in the current row. There is no overlap between the pattern "E" and the adjacent patterns "A" and "D".

(4) If they do not overlap, create a new line,
Register on that line. Therefore, the pattern "E" is registered in a new line.

(5) Thereafter, the processes of (2)-(4) are repeated. The next pattern "D" is the pattern "A", "D"
Therefore, the patterns “B” and “C” are also registered in the current line.

In the case of a document image consisting of alphabets such as English, one pattern corresponds to almost one character even if the connected component is simply one pattern. Therefore, the above-mentioned rearrangement is effective when the unit of the cut out pattern matches (or is very close to) the unit of the symbol.

However, for example, when a Japanese document image is cut out in units of connected components, a character such as Japanese Kanji is composed of a plurality of connected components, and the connected components do not correspond to the characters. The above sort is not done correctly. For this reason, the prediction efficiency of the symbol sequence and the position is reduced, and a high compression rate cannot be obtained. That is, in the prior art, since the connected component is cut out as it is as a pattern, the compression rate in the Japanese document is much lower than that in the English document.

It is an object of the present invention to provide an image compression method in which a plurality of connected components are integrated and cut out as one pattern to improve the prediction accuracy of symbol sequences and positions and to enable a high compression rate. It is in.

[0019]

In order to achieve the above object, according to the invention of claim 1, a connected component is cut out from a document image, and the connected component is regarded as a pattern and registered as a template, and is similar to the pattern. In an image compression method for compressing image information by replacing another pattern with the template, a thickening process is performed on the document image before clipping the connected component, and the thickened image is processed. Further, it is characterized by performing a thinning process in which connected components are preserved.

According to the second aspect of the present invention, the connected component is cut out from the document image generated by reading the document in the main scanning direction and the sub-scanning direction, the connected component is regarded as a pattern and registered as a template, and the pattern is added. In the image compression method for compressing image information by replacing another pattern similar to the above with the template, the connected component is cut out so that the connected component has an overlap in the sub-scanning direction and one adjacent connected component is extracted. It is characterized by cutting out as a pattern.

According to the third aspect of the present invention, the extraction of the connected components is characterized by collecting adjacent connected components into one and predicting and extracting the pattern width of the combined connected components.

According to the fourth aspect of the present invention, the connected component is cut out from the document image, the connected component is regarded as a pattern and registered as a template, and other patterns similar to the pattern are replaced with the template, and the connected component is also replaced. In an image compression method for compressing image information by allocating a symbol to a symbol, a connected component that is close to the connected component to which the symbol is allocated is obtained, and a set of symbols of the adjacent connected component and its relative position are recorded. Then
It is characterized in that the number of recorded symbols that match the relative position of the symbol is counted, and when the counted value is equal to or more than a predetermined value, the symbol group is integrated as one symbol.

[0023]

In one embodiment, the input image is subjected to a thickening process as a preprocess and then a thinning process which does not affect the connected component. In this pre-processing, the pattern separated by about one pixel due to deterioration such as blurring becomes a pattern in which connected components are integrated, and can be cut out in a form closer to the original pattern. Connected components are cut out from the preprocessed image and pattern-matched with the template. When the matching is successful, the template is updated, and when the matching is unsuccessful, a new template is created. The symbols are rearranged, and the symbol sequence and its position are encoded.

[0024]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be specifically described below with reference to the drawings.

<First Embodiment> FIG. 1 shows the structure of a first embodiment of the present invention. In the figure, 101 is an image input device such as a scanner, 102 is a thick pattern for the separated pattern,
A thickening / thinning processing unit that performs a thinning process to create a combined pattern, 103 a pattern cutting unit, 104 a template generation matching unit that generates a template and performs pattern matching, 105 a rearrangement unit that rearranges symbols, 106 Is an encoding unit that encodes pattern information and position information, 107 is a storage unit that stores an input image and generated data, 108 is a control unit that controls the whole, and 109
Is a data communication path.

FIG. 2 is a processing flowchart of the first embodiment of the present invention. The operation will be described with reference to the drawings. First, the image is input by scanning the document in the main scanning direction and the sub scanning direction by the image input device 101 such as a scanner (step 201). Next, the thickening / thinning processing unit 10
In step 2, the input image is subjected to thickening processing (for example, expansion processing) as preprocessing (step 202). Then, thinning processing (for example, contraction processing, thinning processing) that does not affect the connected components is added (step 203). FIG. 3 is a diagram for explaining pattern integration by thickening and thinning processing. In the figure, for example, even if the pattern 301 is separated by about one pixel due to deterioration such as blurring, it can be made into a pattern 303 in which connected components are integrated by thickening and thinning processing, and the pattern can be cut out in a shape closer to the original pattern. It becomes possible to do.

The pattern cutout unit 103 cuts out the connected component from the image subjected to the above-mentioned preprocessing (step 204), and the template generation matching unit 104 performs pattern matching in the same manner as described in the prior art (step). 205, 206). If matching fails, create a new template (step 20).
7) If the matching is successful, the registered template is updated (step 208). When these processes are performed on all the connected components, symbols are assigned to the connected components, the symbol rearrangement unit 105 rearranges the symbols (step 209), and the encoding unit 106 rearranges the symbol string and symbol position. Is predictively encoded (step 210).

<Embodiment 2> FIG. 4 shows the construction of Embodiment 2 of the present invention, in which the thickening / thinning processing unit 102 of Embodiment 1 is replaced with a pattern integration processing unit 402.
The other components are the same as those in the first embodiment. Figure 5
9 is a processing flowchart of the second embodiment. Image input device 4
01 (step 501), and the connected components are cut out by the pattern cutout unit 403 (all the connected components may be subjected to the thickening and thinning processes of the first embodiment as preprocessing for cutting out). (Steps 502 and 503), the pattern integration processing unit 402 performs the following processing.

The pattern integration processing unit 402 determines whether or not the connected components overlap in the vertical direction (step 50).
4) Then, it is determined whether or not the connected components are close to each other (step 505).

FIGS. 6A, 6B, and 6C are diagrams for explaining the integration processing of connected components that overlap in the vertical direction. The connected components 601 to 605 forming the “word” of FIG. 6A have overlap in the vertical direction (sub-scanning direction), and the connected components are close to each other (for example, the distance between them is within 5 pixels). Yes, it is cut out as one pattern.

In the connected component “word” and the connected component “positive” in FIG. 6B, a part 608 of the connected component 607 and a part 609 of the connected component 606 have an overlap in the vertical direction. Moreover, since the connected component "word" and the connected component "positive" are close to each other, the connected component "word" and "positive" are integrated as one pattern (step 506). Step 50
Since the processing from 7 is the same as that of the first embodiment, the description thereof is omitted.

As described above, many characters in Japanese are combined into one pattern by integrating and cutting out connected components that have overlap in the vertical direction and are adjacent to each other.
It is possible to cut out as one pattern, so that the rearrangement by the conventional method is correctly performed, and the efficiency of predicting the symbol sequence and the position is improved. Further, this pattern integration process is a relatively simple process and can be operated at high speed.

The connected component 610 shown in FIG. 6 (c).
Since “rooster” and 611 “self” have no overlap in the vertical direction, one character will be cut out left and right. However, in many cases, it is divided into edges and structures, each of which has a meaning as a pattern, and in the above example, the frequency of "self" following "rooster" is high. To do. In addition, the separation into left and right (horizontal direction), that is, the separation into "side" and "making",
It does not adversely affect the rearrangement of symbols.

<Third Embodiment> FIG. 7 shows the structure of the third embodiment, in which a pattern width prediction unit 703 is further added to the structure of the second embodiment. FIG. 8 is a processing flowchart of the third embodiment. Similar to the second embodiment, the connected components are cut out (step 802), and the pattern integration processing unit 702 integrates the adjacent (closer than a predetermined distance) connected components as a temporary pattern (steps 804 and 805). The pattern width can be predicted by collecting the connected components that are close to each other and viewing some of them as macros.

FIG. 9 is a diagram for predicting the pattern width by combining adjacent connected components into one. 901 and 902 are
Since they are connected components and the connected components 901 and 902 are close to each other, they are put together as one pattern, and the pattern width prediction unit 703 predicts the pattern width 906 (step 806). Since the pattern cutout unit 704 performs pattern division based on the pattern width prediction in the pattern width prediction unit 703, it is possible to more reliably cut out as a symbol having meaning, which is composed of a plurality of connected components. .

Note that 904 is grouped into one because three connected components are close to each other, and is further grouped into one because 903 and 904 are close to each other, and its pattern width is predicted as described above. To be done. The processing from step 808 onward is the same as described above, and will be omitted.

<Embodiment 4> FIG. 10 shows the construction of Embodiment 4, in which the thickening / thinning processing unit of Embodiment 1 is replaced with a connected component processing unit, and the other constituent elements are the same as those of Embodiment 1. Is the same as FIG. 11 is a processing flowchart of the fourth embodiment. Step 1101 to Step 1106
The processing up to is similar to that described in the related art.
By the processing up to step 1106, a symbol is assigned to each connected component.

Next, the connected component processing unit 1002 searches for connected components that are close to each other (that is, within a predetermined distance) with respect to all connected components (step 1108).
Then, the set of adjacent symbols and the relative position of the symbols are recorded in the data storage unit 1007 (step 110).
9).

FIG. 12 is a diagram for explaining a set of adjacent symbols. In this example, the connected component 120 on the "I" side is
Since 1 and the connected component 1202 of the structure are close to each other,
A set AB of the symbol A of the connected component 1201 of the side and the symbol B of the connected component 1202 of the structure is recorded. The next character "of" (the assigned symbol is C) is not recorded because it is not in close proximity to "I". The same applies to "name". “Before” means four connected components 1203, 1204, 1
205, 1206, which are close to each other, so that the symbol sets E, F, G, and H are recorded. Thereafter, similar processing is performed, and in the example of FIG. 12, a set of symbols (I, J), (M, N, O) and the like are recorded.

The relative position of the symbol set is recorded for the following reason. FIG. 13 is a diagram illustrating an inconvenience when the relative position is not recorded. That is, the symbols (A, B) are assigned to the "horizon" and "part", respectively.
When (B, A) is assigned and the relative position is not recorded, the difference between (A, B) and (B, A) cannot be seen, and if this is replaced with one symbol, the characters that should be different become the same character. Become. Further, regarding “cedar” and “bayashi”, the symbols (A, B) are assigned to the cedar and (C, A, B, D) are assigned to the forest. Then, if the cedar (A, B) and the "cedar" (A, B) in "Hayashisu" are replaced with one symbol, the font balance is lost.

Further, the symbols 1301 and 1302, 1
If 303 and 1304 and 1305 and 1306 are not distinguished and replaced with one symbol, the same pattern is obtained.
For the above reasons, the relative position of the symbol set is recorded, but the coordinates of the symbol set (A, B) are (XA, Y
A) and (XB, YB), the relative position is (XA
-XB) and (YA-YB) may be recorded. Moreover, it can be easily checked whether or not these numerical values match.

Next, the connected component processing unit 1002 refers to the recorded data, and counts those whose symbol pairs match and their relative positions match (step 111).
0, 1111). Then, a set of symbols that appears a predetermined number of times or more (for example, in the example of FIG. 12, a set of symbols AB
Appear twice) are integrated as one symbol (step 1112). Hereafter, rearrange the symbols (Step 1
113) and encode (step 1114).

As described above, in the fourth embodiment, as a post-cutting process, a set of symbols existing in other places in the image is integrated as one symbol, so that the pattern can be more reliably approximated to the pattern. Are extracted, and the efficiency of predictive coding of symbol sequences and positions is improved.

[0044]

As described above, according to the first aspect of the invention, since the image is thickened and thinned as a preprocessing for cutting out, the separated patterns are connected due to deterioration such as blurring. As a result, the original pattern is restored and thus the success rate of pattern matching is improved and the compression rate can be improved.

According to the second aspect of the present invention, since the connected components which overlap in the vertical direction and which are adjacent to each other are collectively cut out as one pattern, the cut-out of the pattern is not the connected component, and It is possible to cut out in a shape close to a symbol such as an edge or a structure in, and as a result, the hit probability of prediction of the symbol sequence or position is improved, and more efficient coding can be performed when performing predictive coding. it can.

According to the third aspect of the invention, by collecting the adjacent connected components and estimating the pattern width, the pattern can be cut out in a form closer to the symbol, and the symbol series and position The efficiency of the predictive coding is improved and the compression rate is improved.

According to the fourth aspect of the present invention, when the sets of adjacent symbols are integrated into one symbol, it is taken into consideration that there are a predetermined number or more of similar sets of symbols in other places in the image. Therefore, the integrated symbol is
The probability of being a meaningful symbol is high, and the pattern is more reliably cut out in a form close to the symbol, the efficiency of predictive coding of the symbol series and the position is improved, and the compression rate can be improved.

[Brief description of drawings]

FIG. 1 shows a configuration of a first embodiment of the present invention.

FIG. 2 is a processing flowchart of the first embodiment of the present invention.

FIG. 3 is a diagram illustrating integration of patterns by thickening and thinning processing.

FIG. 4 shows a configuration of a second embodiment of the present invention.

FIG. 5 is a processing flowchart of a second embodiment of the present invention.

6 (a), (b), and (c) are diagrams illustrating a process of integrating connected components that overlap in the vertical direction.

FIG. 7 shows a configuration of a third embodiment of the present invention.

FIG. 8 is a processing flowchart of a third embodiment of the present invention.

FIG. 9 is a diagram for predicting a pattern width by collectively collecting adjacent connected components.

FIG. 10 shows a configuration of a fourth embodiment of the present invention.

FIG. 11 is a processing flowchart according to the fourth embodiment of the present invention.

FIG. 12 is a diagram illustrating sets of adjacent symbols.

FIG. 13 is a diagram illustrating an inconvenience when a relative position is not recorded.

FIG. 14 shows a configuration of a conventional image compression device.

FIG. 15 is a diagram illustrating a conventional image compression method.

FIG. 16 is a diagram for explaining rearrangement into a conventional reading order.

[Explanation of symbols]

 Reference Signs List 101 image input device 102 thickening / thinning processing unit 103 pattern cutout unit 104 template generation matching unit 105 symbol rearranging unit 106 encoding unit 107 data storage unit 108 control unit 109 data communication path

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Internal reference number FI Technical display location G06K 9/34 H04N 1/417

Claims (4)

[Claims] 1. An image compression method for compressing image information by extracting a connected component from a document image, regarding the connected component as a pattern, registering it as a template, and replacing another pattern similar to the pattern with the template. An image compression method characterized by performing a thickening process on the document image before cutting out the connected component, and further performing a thinning process in which the connected component is stored on the thickened image. . 2. A connected component is cut out from a document image generated by reading a document in a main scanning direction and a sub-scanning direction, the connected component is regarded as a pattern and registered as a template, and another pattern similar to the pattern. In the image compression method for compressing image information by replacing the connected component with the template, the connected component is cut out so that the connected component has an overlap in the sub-scanning direction,
An image compression method is characterized in that adjacent connected components are cut out as one pattern. 3. The image compression method according to claim 2, wherein the extraction of the connected component is performed by collecting adjacent connected components into one and predicting the pattern width of the combined connected component and extracting the pattern width. 4. A connected component is cut out from a document image, the connected component is regarded as a pattern and registered as a template, another pattern similar to the pattern is replaced with the template, and a symbol is assigned to the connected component. In an image compression method for compressing image information, a neighboring connected component is obtained from the connected components to which the symbol is assigned, a set of symbols of the neighboring connected component and their relative positions are recorded, and the recorded An image compression method, characterized in that a set of symbols and those whose relative positions match each other are counted, and when the count value is a predetermined value or more, the set of symbols is integrated as one symbol.