Method and Device for the Automatic Matching of Seal Prints

The present invention relates to a method and a device for the automatic matching of seal prints, especially to a method and a device which can identify whether two digitized seal prints are obtained from the same source.

The matching of seal prints is a very important method to identify whether a documents genuine, in the oriental society, especially in the Chinese society. In the Chinese society, a document made by an author shall contain a seal print. While the seal print is identified a genuine print of the original seal owned by the author, the document is deemed genuine; i.e., the document is deemed made by the author.

Although the application of computer systems becomes common in the oriental society, using a computer to automatically identify whether a seal print is genuine, is still under development. Among the technologies already available, several semi-automatic seal print matching systems are widely used by the bank to identify the seal prints printed on the withdrawal slips. To describe such a semi-automatic matching system, the function of the seal prints in the bank practice will be introduced.

While a customer opens a savings account in a bank, the customer shall register his (her) seal print with the bank. The seal print is printed on a "seal print card" and is kept by the bank. When the customer withdraw his money from the bank, he fills a withdrawal slip and chop the original seal on the slip so that the seal print of the seal appears on the slip. The slip is then given to a teller of the bank. The teller matches the seal print on the slip with the seal print as recorded on the seal print card. If the seal prints are identical, the teller allows the withdrawal; Otherwise, the withdrawal is rejected.

While the semi-automatic system is used to help the teller in the identification of the seal print, the seal print of the original seal is recorded in the computer of the semi-automatic matching system. In doing this, the print of the original seal is printed on the seal print card and is then scanned by a scanner. The scanner scans the seal print, converts the image into a digitized format and saves the image data in a computer. When the customer wishes to withdraw his money from the bank, he fills a withdrawal slip and prints a seal print on the slip. The teller then recalls the image of the original seal print from the computer and uses the scanner to scan the seal print on the withdrawal slip. The system displays both the image of the original seal print and the image of the seal print on the withdrawal slip on the screen of the system, with different colors. The teller adjusts the position of the image of the seal print on the withdrawal slip with the help of a mouse, or merely by means of moving the withdrawal slip in relating to the scanner (in such a case, the scanner is a CCD camera). The identification of the two seal prints is conducted by the teller with human eyes. In other words, while the two images are overlapped with each other, the teller determines whether they are identical according to the image as displayed on the screen. If the pixels of the two images are overlapped to some extend, the two seal prints are considered identical; Otherwise, they are considered not identical.

Taiwan utility model registration No. 78873 relates to an "Image identification Platform" and discloses one of the semi-automatic seal print matching systems as described above. Although the semi-automatic systems can help the tellers to display the registered seal print in a very short time without the need to look up the seal print card, however, it is necessary for the teller to identify the seal print with human eyes. There is no objective criteria for the tellers to determine whether a seal print is genuine; All are decided based on experiences of the tellers. Especially when the seal print is printed by a counterfeit seal which is made by computerized imitation technology, a great amount of lose will happen to the bank.

It is then necessary for the industry to have an automatic seal print matching system that can match seal prints under objective criteria automatically.

The object of this invention is to provide an automatic seal print matching device that can match seal prints automatically.

Another object of this invention is to provide an automatic seal print matching device that can match seal prints with objective criteria.

Another object of this invention is to provide an automatic seal print matching device that can enhance the speed of the matching of seal prints.

Another object of this invention is to provide an automatic seal print matching method that has the above-said advantages.

According to the present invention, a method and a device for the automatic matching of seal prints is provided. The device of this invention comprises: a first memory to store reference seal prints, an input device to obtain the image of a test seal print, a second memory to store the test seal print, an image structure similarity calculation device to calculate the similarity in the structure of the image of the reference seal print and the test seal print, a line distribution similarity calculation device to calculate the similarity in the distribution of the lines in the reference seal print and the test seal print, a incompleteness calculation device to calculate the incompleteness of the image of the reference seal print and the test seal print, and a determination device to determine whether the two seal prints are from the same source according to a pre-determined threshold.

The above and other objects and advantages of this invention can be fully understood from the detailed description by referring to the following drawings. In the drawings,

FIG. 1 illustrates the system schematics of the automatic seal print matching device of this invention.

FIG. 2 illustrates the flow chart of the method for automatic matching for seal prints of this invention.

FIG. 3 illustrates a digitized image of a seal print.

FIG. 4 illustrates the image data of FIG. 3 after the process of thinning and feature abstraction.

FIG. 5 shows two seal print to be matched according to the method of the invention.

FIG. 6 shows the result of overlapping of the images of FIG. 5.

FIG. 7 shows a 2*2 mask used in this invention to label the surrounded area of the seal prints.

FIG. 8 shows an image containing a surrounded area to be labeled.

FIG. 9 shows the image of FIG. 8 as labeled.

FIG. 10 shows the image of FIG. 9 after some surplus pixels are deleted.

FIG. 11 shows a digitized image of a test seal print.

FIG. 12 shows a digitized image of an other test seal print.

FIG. 13 shows a digitized image of a third test seal print.

In the automatic matching of seal prints of the present invention, the matching of seal prints is processed according to the following factors:

1. Similarity in the structure of the image of the seal prints.

2. Similarity in the distribution of the lines in the seal prints.

3. Incompleteness of the image of the seal prints.

According to the embodiment of the present invention, the similarity in the image structure of the seal prints are calculated according to the following processes:

1. Digitization of the seal prints to be matched.

2. Thinning of the digitized image of the seal prints.

3. Abstracting the feature points of the seal print images. Here, the "feature points" include the terminal points and cross points of the lines obtained from the thinning process.

4. Mating of the coordinates of the feature points of the seal prints.

5. Calculating the similarity of the image structure of the seal prints. The calculation of the similarity in the line distribution of the seal prints includes:

1. Digitization of the images of the two seal prints.

2. Locating the reference points of the two images.

3. Adjusting the image of the reference seal print with a rotation parameter.

4. Overlapping the two images at the reference points.

5. Calculating the similarity in the line distribution of the seal prints.

An index of similarity of the two seal prints (Index) is calculated according to the following equation:

Index=(W.sub.1 *Similarity in image structure+W.sub.2 *Similarity in line distribution)/W wherein W, W.sub.1 and W.sub.2 are constants and W=W.sub.1 +W.sub.2. In some embodiments W.sub.1 is 5 and W.sub.2 is 1.

The calculation of the incompleteness of the images of the seal prints includes:

1. Digitization of the images of the two seal prints.

2. Labeling the surrounded areas of the images.

3. Recording the number of the surrounded areas and the scope of the areas in sequence from large to small.

4. Calculating the difference in area of the surrounded areas of the two seal prints.

5. Taking the difference as the index of incompleteness of the seal prints.

In determining the two seal prints are from a same source, the "index of similarity" is taken as the major factor. Thus, if the index of similarity is equal to or greater than a predetermined threshold, the two seal prints are considered from the same source; Otherwise, they are considered from different source.

While the index of incompleteness of the seal prints is greater than a threshold of incompleteness, the device generates a warning signal to the operator. The incompleteness of seal prints happens in the following two cases:

1. Defected seal prints: In printing the seal prints, the print could be polluted by the ink or defected because of mal-printing. In obtaining the "original" seal print, such as printing on the seal print card, it is required that the prints be perfect. Under this procedure, only those prints with index of incompleteness equal to or less than a threshold of incompleteness are accepted as "original" prints.

2. Counterfeit seals: The index of incompleteness discloses very fine differences between seal prints. Although the computerized imitation technology makes it possible to imitate the image of a seal print, the imitation will have very small difference with the original. The index of incompleteness can help the teller to find out possible imitating seal prints.

The following is a detailed description of an embodiment of the device and the method for the automatic matching of seal prints of this invention.

FIG. 1 illustrates the system schematics of the automatic seal print matching device of this invention. FIG. 2 illustrates the flow chart of the method for automatic matching for seal prints of this invention.

As shown in FIG. 1, the device for the automatic matching of seal prints of this invention comprises: a first memory (1) to store reference seal prints, an input device (2) to obtain the image of a test seal print, a second memory (3) to store the test seal print, an image structure similarity calculation device (4) to calculate the similarity in the structure of the image of the reference seal print and the test seal print, a line distribution similarity calculation device (5) to calculate the similarity in the distribution of the lines in the reference seal print and the test seal print, an incompleteness calculation device (6) to calculate the incompleteness of the image of the reference seal print and the test seal print, and a determination device (7) to determine whether the two seal prints are from the same source according to a pre-determined threshold.

The matching of seal prints of the present invention will be described according to FIG. 2 in the followings.

At 101 a test pattern representing the seal print to be matched is obtained. First, at 101, the input device 2 inputs the digitized image of a test seal print and stores it in the second memory 3. The input device 2 can be an image scanner or a CCD (charge coupler device) camera. In application, the test seal print is printed on a piece of paper and the input device 2 takes the picture (image) of the seal print and converts it into a digitized format. FIG. 3 illustrates a digitized image of a seal print. If the image is a black-and-white image, "00" can be used to represent the "background" pixels and "FF" can be used to represent the "image" pixels.

The digitized image of a reference seal print is stored in the first memory 1. The image is similar to that shown in FIG. 3. Here, the reference seal print is the "original" seal print and the test seal print is the seal print to be determined whether it is a genuine print of the origin seal of the reference seal print. We use pattern P to represent the image data of the test seal print and pattern Q to represent the image data of the reference seal print.

At 102 the image structure similarity calculation device 4 conducts the "thinning" of both pattern P and pattern Q. Here, thinning means the processing of a digitized image to abstract the lines contained in the image such that the lines can be one-pixel wide. Taiwan patent application No. 78102864 relates to a "Method and Device for the thinning and feature abstraction of binary images" and disclosed an effective approach for the thinning of digitized images.

As an image is processed with thinning, it contains several line sections or curve sections. Statistics shows that the lines or curves will have terminal points and cross points. The terminal points and cross points are then taken as feature points at 103. The feature points abstraction technology disclosed in the above-said Taiwan patent can be a suited approach for this purpose and is taken for reference. FIG. 4 illustrates the image data of FIG. 3 after the process of thinning and feature abstraction.

At 110 the similarity in image structure of the seal prints are calculated. The similarity is calculated by matching of the feature points of the patterns representing the seal prints. The matching of the feature points can be processed according to any pattern matching technology. Taiwan patent application No. 79109743 relates to a "Method and Device for the Automatic Matching and Identification of Planar Point Patterns" and discloses an effective approach for the matching of two planar point patterns.

In this conventional art of matching, the two patterns to be matched are:

Pattern P={p1, p2, p3, . . . , pm}, m is the number of points in pattern P;

Pattern Q={q2, q2, q3, . . . , qn}, n is the number of points in pattern Q.

At 111, an initial mated possibility S.sup.(0) (pi, qj) is designated to every pair of points consisted of a point from pattern P (point pi, i=1, 2, 3, . . . , m) and a point from pattern Q (qj, j=1, 2, 3, . . . , n). Here, "mated" means when two patterns P and Q are identical or similar, for every point pi there is an only point qj that is overlapped with or is very close to pi when pi and qj are in the same planar coordinate; "mated possibility" means the possibility that pi and qj are mated. In practice, the initial mated possibilities are supposed of one value. A "coarse mating" step is recommended to decide the initial mated possibility in which pairs of points pi and qj that are not qualified mated are given the initial mated possibility of 0 and others are given the initial mated possibility of 1.

At 112, the initial mated possibility is adjusted repeatedly by the mated possibilities of other pairs of points (ph and qk, h=1, 2, 3, . . . , m, h.noteq.i and k=1, 2, 3, . . . , m, k.noteq.j) under the premise that pi and qj are mated. If S.sup.(r) (pi, qj) represents the mated possibility of pi and qj at the r.sup.th time of adjustment, then we have: ##EQU1## wherein Cijhk(h, k) represents the mated possibility of ph and qk if pi and qj are mated and ##EQU2## 1 represents the distance between the related points.

As the mated possibilities of all pi and qj points are obtained, a "sequential-forward selection" is used to select the mated pairs from the patterns at 113. According to the sequential-forward selection approach, a matrix ›Sij! is used to represent the mated possibilities. In the selection of the mated pairs, the pi and qj points with the highest mated possibility is selected as a mated pair and the elements in column i and row j of ›Sij! are deleted. The selection is repeated until ›Sij! is an empty cell. Number of mated pairs K is recorded.

After the mated pairs are selected, at 114 the similarity of the patterns (Score) is calculated according to the following equation: ##EQU3## wherein: C is a constant; ##EQU4## S represents a scaling ratio between pattern P and pattern Q.

The value of Score so obtained is considered the image structure similarity of the two seal prints for the purpose of this invention. Other method of matching of planar point patterns can also be used in the calculation of the similarity in image structure and are taken for reference.

In calculating the similarity in image structure, weights may be used to emphasize any of X.sub.1 to X.sub.4 so that the value of Score may be increased or decreased.

In the calculation of the similarity in line distribution of the seal prints, the line distribution calculation device 5 determines reference points in both images at 120. The "reference point" will be used as the basis such that the two images may be overlapped for the purpose of matching. The test pattern is preferably adjusted (transformed), using the reference point as the axis according to an equation to be described hereinafter at 123.

The location of the reference point includes the following steps:

At 121, the pixel at the most left-upper corner of a pattern is set as the original point (0,0). At 122 the coordinate of the reference point is calculated. If the pattern is consisted of black-and-white image data, the gray levels of the pixels are "00" (blank) and "FF" (point). Supposing the number of pixels with the gray level of "FF" is N, which coordinates are (X.sub.1, Y.sub.1), (X.sub.2, Y.sub.2), . . . , (X.sub.N, Y.sub.N), the coordinate of the reference point (X.sub.G, Y.sub.G) may be defined as: ##EQU5##

Although it is not intended to limit the scope of this invention, the reasons to select the center of gravity as the reference point of a seal print include: that the center of gravity exists in almost every planar point pattern and that every planar point pattern will have only one center of gravity. The calculation of the center of gravity is a two dimensional calculation and its level of complication is O(2n.sup.2). If we try to locate a reference point such that most points in the patterns are overlapped, the calculation could be a four dimensional one where the level of complication is O(n.sup.4). Nevertheless, the adoption of the center of gravity also enjoy the benefits of the equivalence of moment of force. Since noises could exist in all images, the distribution of noises can be deemed even at any position. By using the center of gravity as the reference point the distortion cause by noises can be reduced due to the symmetric distribution of the noises.

Under such conditions, due to the similarity in the distribution of the feature points, if two seal prints were printed by a same seal, the number of overlapping points must be very great, so long as the reference points are identical. In the other hand, if they were printed by two different seal, no matter how the reference points are decided, there can not be a great number of overlapping points. This is because the seal prints are different in the basic structure.

Of course, other points can serve as reference points. For example, if the seal is a rectangular seal, its corners can be used as reference points. The benefits of using a corner as a reference point include that, in deciding the position of the reference point, only the area around the corner shall be processed. The disadvantages, however, include that the stability of the position of the reference point will be distorted by noises existing at that area. Moreover, a rectangular seal has four corners but not one. At least four times of overlapping shall be processed which means long processing time. Last but not the least, this approach can not apply to round seals.

While the test pattern was printed by the same seal as was the reference pattern, it is possible that the test pattern has been shifted, rotated or scaled, relative to the reference. In such case, the factor X.sub.3 in equation (2) is still unreasonably great and Score is not as great as it should be. In order to obtain a correct result, at 123 a geometric transformation is used to adjust the coordinates of the feature points of the test pattern, as follows:

If a cell M represents the mated pairs of points of pattern P and pattern Q wherein M=m.sub.1, m.sub.2, . . . , m.sub.k and pi(xi, yi) represents mated points in pattern P (i=1, 2, . . . , m) and qmi(xmi, ymi) represents mated points of individual pi point in pattern Q (I=1, 2, . . . , m), then the a geometric transformation R whereby ##EQU6## has the minimum value is deemed an ideal transformation for pattern Q for the purpose of matching wherein ##EQU7## wherein r1 and r2 represent translation in the vertical and the horizontal direction, r3 and r4 represent rotation.

The test pattern can be transformed according to the above equation (4) such that the value of X.sub.3 can be reduced. This transformation can be called "least mean-square-error registration".

At 124 the test pattern, after transformation, is overlapped with the reference pattern using the reference points are the axis. FIG. 5 shows two seal print to be matched and FIG. 6 shows the result of overlapping of the images of FIG. 5.

At 125 the similarity in line distribution of the two patterns is calculated. If the number of points (pixels with the gray level of "FF") in the reference pattern is N, and in the test pattern is N.sub.2 and the number of the overlapped points is N.sub.12, the similarity in line distribution can be calculated according to the following equation: ##EQU8##

From the above-said steps, the similarity in image structure and the similarity in line distribution of the two patterns can be obtained. At 130 an index of similarity is calculated by the determination device 7, according to the following equation:

Index=(W.sub.1 *Similarity in image structure+W.sub.2 *Similarity in line distribution)/W wherein W, W.sub.1 and W.sub.2 are constants and W=W.sub.1 +W.sub.2. In some embodiments W.sub.1 is 5 and W.sub.2 is 1.

As described in above, incompleteness may exist while the seal print is a defected print or while the seal is counterfeit. At 140 the incompleteness of the test pattern is calculated by the incompleteness calculation device 6.

In the calculation of the incompleteness, at 141 the surrounded areas of the test pattern is labeled.

In labeling the surrounded areas a 2*2 mask is used to help processing the digitized image of pattern Q. FIG. 7 shows a 2*2 mask used in to label the surrounded area of the test pattern. The mask is positioned at the most left-upper corner of the test pattern and the labeling is conducted from left to right, from up to down. Each time four pixels are processed:

1) If pixel A is FF, it is kept as FF; otherwise,

2) If pixels B and D are FF, A is set a value such as 1; otherwise,

3) If pixel D is FF and pixel B is a value n, A is set as n; otherwise,

4) If pixel B is FF and D is a value m, A is set as m; otherwise,

5) If pixels B and D are n, A is set as n; otherwise,

6) If pixel B is n and pixel D is m, A is set as n or m.

Because the value of a pixel is determined according to the value of its left and upper neighbor pixel, some surplus labels will be remained at the right-down corner of the pattern. At 142 the surplus labels are deleted.

The above-said labeling processing is described in details by referring to the figures. FIG. 8 shows an image containing a surrounded area to be labeled. The area surrounded by pixels with FF will be labeled with the help of the mask of FIG. 7, as follows:

1) No label will be made before the first FF pixel of a row, i.e., the d1, c3 and b3 pixels of the pattern of

FIG. 7. Pixels a1-c1, a2-b2 and a3 are remained 00.

2) When position A is d1, f1, c2, g2, b3, g3, . . . , they are kept as FF.

3) When position A is d2, f2, c3, . . . , because positions B and D are FF, they are labeled with a value. The value begins from 1 and is cumulated. In FIG. 7, pixel d2 is the first to be labeled and is given the value 1; f2 is the second to be labeled and is given the value 2; c3 is the third and is given the value 3; and so on.

4) When position A is c4, because position D is FF and B is 3 (m), it is given the value 3.

5) When position A is e3, because position B is FF and D is 1 (n), it is given the value 1.

6) When position A is e4, because positions B and D are 1, it is given the value 1.

7) When position A is d3, because position D is 3 (m) and B is 1 (n), it is given the value 3 or 1. Here, d3 is given as 1.

FIG. 9 shows the image of FIG. 8 as labeled. As shown in this figure, the labels of 1, 2 and 3 are considered equivalent; All represent surrounded area. These labels are then set as 1. Counting the number of the pixels labeled as 1 can give the area of the surrounded area.

After the labeling, some surplus values are remained at the right-down corner of the pattern. These pixels, i.e., pixels h6, g7, h7, . . . , are not in the surrounded area. These pixels are then deleted at 142. FIG. 10 shows the result of deletion.

At 143 the number and area of the surrounded areas are recorded. At 144 the areas are recorded in sequence according to their area.

At 145 the difference of the surrounded areas of the two patterns are calculated. Supposing M.sub.area represents the number of the surrounded areas and A.sub.1, A.sub.2, . . . A.sub.m represent the surrounded areas, both of the reference pattern, and N.sub.area represents the number of the surrounded areas and B.sub.1, B.sub.2, . . . B.sub.n represent the surrounded areas, both of the test pattern, the incompleteness of the seal prints can be calculated according to the following equation: ##EQU9##

After the steps from 110 to 145, the similarity of the patterns can be determined at 150 by the determination device 7. In the embodiment of this invention, the similarity of the seal prints is determined taking the index of similarity as a major factor. The incompleteness is taken as a reference factor, or a warning factor, as follows:

1. If Index of similarity>=Threshold:

In some embodiments if Index of similarity is equal to or greater than the threshold the seal prints are considered identical.

2. If Incompleteness >=Threshold of incompleteness:

In some embodiments, such at the registration of the seal print cards, when the incompleteness is equal to or greater than a threshold, the seal print is considered a defected print. In the matching of seal prints, the incompleteness discloses tiny differences in the seal prints. Warning signals will be generated if the incompleteness is equal to or greater than a threshold.

The following is a description of the embodiments of the method and device for the automatic matching of seal prints. In these embodiments, the threshold of similarity is set as 80(%) and the threshold of incompleteness is set as 200.

FIG. 11 shows a digitized image of a test seal print. As shown in the figure, the seal print is printed by the same seal of FIG. 3 which is the reference seal print for the purpose of this embodiment. After matching, the following results are obtained:

1. Similarity in image structure: 100.

2. Similarity in line distribution: 45.

3. Index of similarity: 91.

4. Incompleteness: 123.

Since the "Index" (91) is greater than the threshold of similarity (80) and the incompleteness (123) is less than the threshold of incompleteness (200), the two seal prints are considered identical.

FIG. 12 shows a digitized image of an other test seal print. As shown in the figure, the seal print is printed by a different seal with that of FIG. 3 which is the reference seal print for the purpose of this embodiment. After matching, the following results are obtained:

1. Similarity in image structure: 0.

2. Similarity in line distribution: 0.

3. Index of similarity: 0.

4. Incompleteness: 622.

Since the "Index" (0) is smaller than the threshold of similarity (80) and the incompleteness (622) is greater than the threshold of incompleteness (200), the two seal prints are considered different.

FIG. 13 shows a digitized image of a third test seal print. As shown in the figure, the seal print is printed by an imitation seal in accordance with the seal of FIG. 3 which is the reference seal print for the purpose of this embodiment. After matching, the following results are obtained:

1. Similarity in image structure: 100.

2. Similarity in line distribution: 44.

3. Index of similarity: 91.

4. Incompleteness: 234.

Although the "Index" (91) is greater than the threshold of similarity (80), because the incompleteness (234) is greater than the threshold of incompleteness, the two seal prints are considered different. A warning signal is generated so that the operator may pay more attention.

The forgoing description of the preferred embodiments of this invention s chosen and presented for the purposes of illustration and description. It is evident that various modifications may be made thereto in light of the above instructions which are. not specifically described above but which are clearly within the scope and spirit of the present invention. It is therefore intended that all the modifications and variations fall within the scope and spirit of the present invention as determined by the appended claims when interpreted in accordance with the breadth to which they are fairly, legally, and equitably entitled.