GB2181875A - Symbol pattern matching - Google Patents

Abstract

In a method of matching first and second symbol patterns an AND-NOT error map is formed (rather than an exclusive - OR error map) each picture element pattern present in the first symbol and not the second being tagged in a first manner, +, and each picture element present in the second symbol and not the first being tagged in a second manner -. The AND-NOT error map is then processed to form a weighted AND-NOT error map in which each tagged element is replaced by the number of similarly tagged elements in the surrounding 3 x 3 area. The weight numbers are then summed and the sum is compared with a threshold value, to give an indication of whether or not the symbols match. The method can be used, for example, as part of an image compression technique in a facsimile system. <IMAGE>

Description

SPECIFICATION Symbol pattern matching Background to the invention This invention relates to a method of matching symbol patterns. The invention is particularly, although not exclusively, concerned with a symbol matching method for use in a text image data compression scheme, e.g. for use in a digital facsimile system.

Digital facsimile is an increasingly important aspect of office automation. Equipment is widely available that can scan and digitize black and white documents at a resolution of 7.7 dots per mm. horizontally and vertically.

At this resolution, an A4 document generates about 0.5 Mbytes of image data and compression is therefore of great importance.

One known method of compressing twolevel image data is the Modified Read Code (MRC) scheme described for example in "Inter- national digital facsimile coding standards", by R. Hunter et al, Proc. IEEE Vo1.68, No.7, pages 854-867 (1980). This scheme exploits the local redundancy in the image, and can compress typical office documents by factors of between 8 and 30, depending on the information content.

Another known method of compressing two-level image data is the Combined Symbol Matching (CSM) scheme described in "Combined Symbol Matching facsimile data compression system", by W.K.Pratt et al, Proc.

IEEE, Vo1.68, No.7, pages 786-796 (1980).

This scheme exploits the redundancy due to the repetition of symbol patterns, obtaining increased compression by encoding only the first occurrence of each distinct symbol pattern in the image. A library of symbol patterns is maintained in a memory. When a symbol pattern is encountered in the image data, it is compared with the patterns already in the library and, if no match is found, it is added to the library. Each symbol is then encoded in terms of its position in the image and the identity of the corresponding pattern in the library.

The compression obtained by symbol matching is determined not only by the coding efficiency, but also by the number of symbols in the final library. Ideally, the library should contain exactly one copy of each distinct symbol in the document, but in practice it is usually much larger, containing many superfluous entries due to incorrect isolation of symbols and inefficient matching.

A good matching method is crucial to the reliability of a symbol-matching scheme. The matching criterion must be tight enough to prevent mismatches while able to recognise matches between identical symbols distorted by noise. In the CSM scheme mentioned above, a match is determined by constructing an exclusive-OR error map, containing an indication of each picture element (pel) that differs in the two symbols. From this is formed a weighted error map, by replacing each error indication by a count of the number of errors in the surrounding 3 x 3 neighbourhood. The contents of the weighted error map are then summed, to provide a weighted error count.

This is then compared with a threshold value to produce a decision on whether or not the symbols match. The threshold value is varied according to the number of black pels in the symbol: the larger the number of black pels the larger the threshold.

This approach has been found less effective for matching very small symbols or those composed of very thin strokes, of the order of one picture element in thickness. The object of the present invention is to provide an improved method of matching symbol patterns which is more effective in these cases.

Summary of the invention According to the invention there is provided a method of matching first and second symbol patterns comprising the steps: (a) constructing an AND-NOT error map in which each picture element present in the first symbol and not in the second is tagged in a first manner and each picture element present in the second symbol and not in the first is tagged in a second manner, (b) constructing a weighted AND-NOT error map in which elements forming part of a cluster of similarly-tagged elements in the AND NOT error map are given greater weight values than those not forming part of such clusters, (c) summing the weight values to produce an error count, and (d) comparing the error count with a threshold value.

As will be described in more detail below, it is found that the weighted AND-NOT error map is more effective than the previously proposed weighted exclusive-OR error map for matching small symbols.

In a preferred form of the invention, the threshold value is derived from an estimate of the combined perimeter lengths of the two symbol patterns. It has been found that this gives better results than the previously proposed method of deriving the threshold value from the black pel count.

According to a second aspect of the invention, there is provided a method of compressing image data comprising the steps: (a) maintaining a library of symbol patterns, (b) scanning the image data to isolate symbol patterns, (c) matching each symbol pattern isolated from the image with the symbol patterns in the library, using a method in accordance with the first aspect of the invention, (d) if no match is found, entering the symbol pattern from the image into the library, and (e) encoding each symbol pattern in the image by an indication of the corresponding pattern in the library.

The invention also includes apparatus for performing the method in accordance with the first or second aspect of the invention.

Brief description of the drawings One data compression method and matching method in accordance with the invention will now be described by way of example with reference to the accompanying drawings.

Figure 1 illustrates the overall data compression method.

Figure 2 illustrates the matching method used in the data compression method.

Figure 3 shows two examples illustrating the matching method.

Figure 4 is a graph used to determine a threshold for use in the matching method.

Description of an embodiment of the invention The overall image compression method is shown in Figure 1. The original uncompressed image data 10 consists of an array of bits, one for each picture element (pel) in the image. The compression method uses a library 11, which holds symbol patterns which have been previously encountered. Initially, the library may be empty, or it may contain symbols entered from processing a previous document.

The image compression method comprises the following steps.

(a) Symbol Extraction For the purposes of extraction from the image, a symbol is defined to be any 8-connected black object which can be entirely contained within a square window whose sides measure 32 pels (or about 4mm).

Each scan line is searched from left to right for a run of between 1 and 32 black pels which are not connected to any black pels in the previous scan line. The boundary is then traced in a clock-wise direction starting from the last black pel in the run and ending at the first black pel.

The boundary-following algorithm is described in detail in "Coding of two-level pictures by pattern-matching and substitution", by 0. Johnson et al, Bell System Technical Journal, Vol. 62, pages 2513-2547 (1983).

The trace is aborted if the object traced becomes more than 32 pels wide or 32 pels high. The trace is also aborted if the boundary goes above the current scan line, since the object will have already been traced and processed.

When the symbol has been completely traced, a rectangular block of the same dimensions as the symbol, and completely containing it, is copied to another part of memory.

Any black pels lying outside the traced perimeter are then deleted from the copy. The symbol is then deleted from the memorized image by performing a logical exclusive-OR with the copy of the symbol. The copy is then passed to the screening and matching processes.

The remainder of the image, after all the symbols have been extracted, is referred to as the residual image (12).

(b) Candidate Screening In order to minimize the number of applications of the time-consuming matching process, a number of basic features of the current symbol are measured and compared with those of the library symbols. Only library symbols whose features are sufficiently close to those of the current symbol are selected for matching. These are then sorted so that the symbols most likely to result in a successful match are processed first.

The features used for screening are the width and height of the symbol block, the number of internal white runs in the horizontal direction, and the number of internal white runs in the vertical direction. Two symbols are considered likely to match if their widths and heights differ by no more than 2, and their numbers of internal white runs in either direction differ by no more than 5.

(c) Symbol Matching Those library symbols which pass the screening process are then matched against the candidate symbols.

The symbol matching step is described in more detail below with reference to Figure 2.

(d) Library Maintenance When no matching symbol is identified, the current symbol is added to the library. The library contains the full bit-map representation of each symbol pattern, up to a maximum of 192K bits, together with a table giving the bit address of each pattern, its screening features, and the number of times it has been used, up to a maximum of 512 symbols. When either of these limits is exceeded, one or more of the least used library symbols is deleted to make room for a new symbol.

(e) Symbol Coding The location and identification of symbols is encoded by the procedure described in the above paper by 0. Johnson et al. Variable length codewords are used to define starting positions and library identifications, with special codes for 'new symbol', 'same symbol', and 'no more symbols (on current scan line)'.

The patterns of new library symbols are encoded using the Modified Read Code.

(f) Residue Coding The residual image, from which all symbols have been deleted, is encoded using the Modified Read Code. To reduce memory require ments, each line of the residual image may be encoded as soon as all the symbols starting on that line have been removed. The image buffer need only hold 33 scan lines at a time, which is sufficient to trace all symbols starting in one scan line.

Referring now to Figure 2, this shows the symbol matching step in more detail.

First, one of the candidate symbol patterns from the library is selected. The joint perimeter length P of the two symbol patterns (i.e. the current symbol extracted from the image and the candidate symbol) is then calculated. For this purpose, the external perimeter length of each symbol is estimated by the value 2 (CH+CW) where CH is the height of the character (in pels) and CW is its width.

The internal perimeter length of each symbol is estimated by the value 2 (VR+HR) where VR and HR are the numbers of vertical and horizontal internal white runs in the character.

The joint perimeter length P is calculated by adding together these values for both symbols.

A threshold value T is then calculated from P using an empirically derived relationship. The way in which this relationship is derived will be described below.

The two patterns are then registered one against the other, in such a manner that the distance between the corresponding block edges of the two patterns does not- exceed one pel. There may be as few as one or as many as nine ways of doing this, depending on the relative block dimensions of the two symbols. The most central registration of the two patterns is taken first.

The two patterns are then compared and an unweighted AND-NOT error map is constructed. In this map, each pel present in the current pattern and not in the candidate pattern is tagged with a + each pel present in the candidate pattern and not in the current pattern is tagged with a-.

This map is then used to generate a weighted AND-NOT error map as follows. For each element tagged with a + , the number of similarly tagged elements in the surrounding 3 x 3 area is counted (including the central element). This procedure is repeated for the elements tagged with a The weights of all the elements in the weighted error map are then added together to give a weighted error count W.

Figure 3 shows two examples of the way in which these error maps are generated. In the first example (Figure 3a) the current and candidate symbol patterns are both the letter "n", although because of noise and differences in the alignment of the scanning matrix they are not exactly the same shape. In the second example (Figure 3b) the current symbol pattern is "s" and the candidate symbol pattern is a.

For comparison, Figure 3 also shows the unweighted and weighted exclusive-OR error maps used in the previously proposed method described above. It can be seen that the weighted exclusive-OR error count is 88 in Figure 3a and 81 in Figure 3b; that is the error count is actually higher for the two similar symbols "n" than for the dissimilar symbols "s" and "a". In contrast, the weighted AND-NOT error count is 50 in Figure 3a and 77 in Figure 3b. This indicates that the present method, based on the weighted AND NOT error count, is better able to match the two "n" patterns while still distinguishing between the "s" and "a".

The reason for the superior performance of the AND-NOT method over the exclusive -OR method can be seen from Figure 3a. In this case, the vertical strokes of the "n" are very thin, just one pel in thickness, and the separation between them differs by one pel. It is therefore not possible to superimpose these two patterns such that both vertical strokes coincide. The shift of one vertical stroke between the two patterns results in a vertical band two pels thick in the exclusive-OR error map, and this gives a high weighted exclusive OR error count. In contrast, in the weighted AND-NOT error map, the errors reinforce each other only if they result from black pels in the same pattern. As a result, there is not the same clustering effect as in the exclusive-OR map, and the error count is significantly reduced.

Referring again to Figure 2, the weighted AND-NOT error count W is compared with the previously calculated threshold T and if W is less than T, a match is indicated.

If no match is detected, the matching procedure is repeated for each other possible registration between the two symbol patterns. If none of the possible registrations produces a match, the next candidate symbol pattern is selected from the library and the whole process is repeated.

Referring now to Figure 4, this illustrates how the relationship between the threshold T and the joint perimeter P length is initially determined. A typical sample document is scanned and, for each pair of symbols in the document, the joint perimeter length P and the weighted AND-NOT error count W are calculated as described. Also, for each pair of symbols, a subjective judgement is made as to whether the symbols are the same.

The results are plotted on a graph as shown in Figure 4, using an 0 for points corresponding to pairs of symbols judged to be the same, and an X otherwise. A line is then drawn such that all the X's lie above the line.

This line represents the desired threshold value, and only those points below the line are recognised as matches. It can be seen that there are some 0 points above the line, and these correspond to pairs of symbols which, because of the noise, will not be re cognised as matching. These may result in duplicated symbols in the library. In this example, the line is represented by the equation: T = 15 if P is less than or equal to 80 = 15 + 0.4 (P-80) if P is greater than 80.

This equation is used to calculate the threshold value T from P in the matching process (Figure 2).

Some possible modifications It will be appreciated that many modifications may be made to the above method without departing from the scope of the present invention.

For example, the threshold value T may be calculated from the symbol black pel count, rather than from the perimeter length. Alternatively, the rectangular block size, or the lesser of the height and width of the symbol, may be used.

The matching process of Figure 2 may be modified by calculating an unweighted error count for each possible registration of a pair of patterns, and performing the full procedure only if the unweighted error count is lower than that for previous registrations of the same two patterns. This avoids having to perform the relatively lengthy task of generating a weighted error map for every possible registration.

In the procedure described above, the matching procedure is terminated as soon as a candidate pattern is found which results in a match. However, in a modified form of the invention, all the candidates may be tried, and the best match selected (i.e. the one that produces the lowest error count).

Claims (9)

1. A method of matching first and second symbol patterns comprising the steps: (a) constructing an AND-NOT error map in which each picture element present in the first symbol and not in the second is tagged in a first manner and each picture element present in the second symbol and not in the first is tagged in a second manner, (b) constructing a weighted AND-NOT error map in which elements forming part of a cluster of similarly-tagged elements in the AND NOT error map are given greater weight values than those not forming part of such clusters, (c) summing the weight values to produce an error count, and (d) comparing the error count with a threshold value.

2. A method according -to Claim 1 wherein the threshold value is derived from an estimate of the combined perimeter lengths of the two symbol patterns.

3. A method according to Ciaim 2 wherein the estimate of the combined perimeter lengths of the patterns is obtained by adding together estimates of the internal and external perimeter lengths of the patterns, the estimate of the internal perimeter lengths being obtained by counting the numbers of internal runs of picture elements of a predetermined value within the patterns.

4. A method according to any preceding claim wherein the step of constructing the weighted AND-NOT error map is performed by counting, for each tagged element in the AND NOT error map, the number of similarly tagged elements within a predetermined area including the tagged element in question.

5. A method according to Claim 4 wherein said predetermined area comprises a 3 x 3 area of picture elements centred on the tagged element in question.

6. A method of compressing image data comprising the steps: (a) maintaining a library of symbol patterns, (b) scanning the image data to isolate symbol patterns, (c) matching each symbol pattern isolated from the image with the symbol patterns in the library, using a method in accordance with the first aspect of the invention, (d) if no match is found, entering the symbol pattern from the image into the library, and (e) encoding each symbol pattern in the image by an indication of the corresponding pattern in the library.

7. A method according to Claim 6 wherein the residue of the image, after removal of said symbol patterns, is encoded by a run-length encoding technique.

8. A method of matching symbol patterns substantially as hereinbefore described with reference to the accompanying drawings.

9. A method of compressing image data substantially as hereinbefore described with reference to the accompanying drawings.