JPS5847063B2 - Contour tracking method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a contour tracking method for recognizing two-dimensional patterns such as characters and figures.

Conventional methods of this type include methods that use flying, spot, and scanners to track the outline of characters written on paper, but when a device is configured using this method,
Since it uses an expensive and large-sized flying, spot, or scanner, it has disadvantages such as the equipment being expensive and large.

Furthermore, a method for tracing the outline of a binary figure has been proposed in the past, but the conventional method has the drawback that it is not possible to trace the inner outline of a loop figure whose line width is 1 pixel.

The conventional method will be explained with reference to FIGS. 1, 2, 7, 8, and 9.

FIG. 1 is an example of a binarized loop figure with a line width of 1 pixel, where logic 1 indicates the figure part and logic O indicates the background part.

FIG. 2 shows the contour to be traced of pattern 1 in FIG. 1, in which 2 is the outer contour of pattern 1, and 3 is the inner contour.

The logic 1 pixels that touch this contour in four connected directions in the vertical and horizontal directions are defined as contour points.

Since pattern 1 in FIG. 1 is a loop figure with a line width of 1 pixel, some pixels of logic 1 serve both as outer contour points and inner contour points.

FIG. 7 shows the state of the storage device that has stored the figures shown in FIG. 1, and each storage means stores a value of 1 or 0 corresponding to each pixel in FIG. 1.

FIG. 8 shows the state of the storage device after tracking the outer contour, and the values in the storage device corresponding to the contour points for which tracking has been completed range from 1 to 2.
It has been rewritten as .

FIG. 9 shows the order in which the next contour point is searched from the contour point being tracked.

* is the position of the contour point being tracked. It is assumed that the contour point tracked immediately before is located at number 8, and numbers 1 to 7 are at number 8.
It is attached counterclockwise with reference to .

The values in the storage means corresponding to each pixel are checked in the order of numbers 1 to 8.

Contour tracking is performed as follows.

In the state of the storage device shown in FIG. 7, values in the storage means corresponding to each pixel are sequentially checked from the storage means corresponding to the pixel at the upper left corner of FIG. 1 toward the right.

Starting from the storage means whose value changes from 0 to 1 (second column, second row in FIG. 7), storage means whose value is 1 or 2 are detected in the order shown in FIG. 9.

Next, the tracking point is transferred to the storage means, and the value of the storage means corresponding to the tracked pixel is rewritten to 2.

By repeating this process and returning to the starting point, tracing of the outer contour is completed as shown in FIG.

Next, in the state of the storage device shown in FIG. 8 after tracking the outer contour, even if you try to detect the starting point for tracing the inner contour in the same way as before, the storage device whose value changes from 0 to 1 will not work. The starting point cannot be detected because it does not exist.

As described above, the conventional method has the disadvantage that it is not possible to trace the inner contour of a loop figure having a line width of one pixel as shown in FIG.

In order to eliminate these drawbacks, the present invention provides four binary storage means corresponding to each pixel of the binarized pattern, so that the inner contour of a loop figure with a line width of one pixel can be stored. This will be explained in detail below with reference to the drawings.

FIG. 3 is for explaining the relationship between the contour shown in FIG. 2 and a binary storage means for storing the contour. Pixel 4 is the central pixel, and pixel 4 is the central pixel and is in a logic 1 state.

Pixels marked with * are not related to the following explanation, and are
The figure shows four binary storage means 41 corresponding to pixel 4.
~44 states are represented.

A general random access memory is used as the storage means, and the expression shown in FIG. 3 is used to clearly explain the correspondence with the upper, lower, left, and right adjacent pixels.

The same expression is used in FIGS. 4, 5, and 6.

That is, for example, the correspondence relationship between pixel 4 in FIG. At 42,
The relationship is such that the same left neighbor is stored as the same 41, respectively.

Next, a method of contour detection will be explained.

First, the binary storage means 41 to 44 have logic 0 as an initial value.
is memorized.

Then, the logic 0 (or logic 1) is adjacent to either the top, bottom, left or right of the logic 1 (or logic O) pixel in the two-dimensional pattern.
), among the four binary storage means corresponding to the logic 1 (or logic 0) pixel, the logic 0 is selected.
Logic 1 (or logic O) is stored in the storage means corresponding to the pixel direction of (or logic 1), and logic 0 (or logic 1) is stored in the other storage means, and the two-dimensional pattern is memorize the outline of

For example, when there is a logic 0 pixel above and to the right of the logic 1 pixel 4 as shown in FIG. Since the pixel to the left of pixel 4 and the lower corner pixel is logic 1, it remains logic 0.

FIG. 4 shows the state of the storage means obtained by performing the above-described processing on all logic 1 pixels of pattern 1 in this manner.

Incidentally, if the logical values of the four binary storage means corresponding to a certain pixel in pattern 1 are all O, the state is not written in the diagram.

4, 5, and 6 are diagrams for explaining contour tracking, and 5 in the figures is a storage device having four binary storage means corresponding to each pixel of pattern 1. , 10-33
indicates a portion of the four binary stored contents corresponding to the pixel.

Although the storage means of the storage device 5 are not necessarily arranged two-dimensionally as shown in the figure, the representation as shown in the figure is used to make it easier to understand the correspondence with each pixel of the pattern 1.

Also, Fig. 4 shows the outline (initial state of the storage means in which logical values are written), Fig. 6 shows the state of the storage means at a stage in the middle of tracking the outer contour, and Fig. 5 shows the state of the storage means after tracing the outer contour. FIG.

Next, a contour tracking method will be explained.

In the storage device 5 shown in FIG. 4, four memories corresponding to pixels are used to check the status of the storage means corresponding to each pixel in sequence from the storage means corresponding to the pixel in the upper left corner to the right. Among the means, when a pixel whose content is 1 in the storage means (41 or 42 in FIG. 3) corresponding to the left or lower contour is detected, this pixel is set as the starting point of contour tracing.

In the example of FIG. 4, the pixel corresponding to the storage means 10 (the pixel in the second column and second row of FIG. 1) is the starting point.

A storage means in which logic 1 is continuously written starting from the storage means 10 (this corresponds to outlines 2 and 3 in FIG. 2).

) in the direction of looking at the logic O pixels to the right and the logic 1 pixels to the left in the direction of the contour line, 1 is obtained.
0゜1L12...... It can be traced in numerical order, and a logical O is written in the storage means it passed through.

This will be explained in more detail with reference to FIG.

FIG. 6 shows the state of each storage means at the stage when the outer contour has been traced to the storage means 21.

Next, the position of the corresponding pixel is stored in the storage means 22, and a logical value O is written in the storage means 22.

Next, in the counterclockwise direction from the storage means 22, the storage means 30, 23, and 33 whose logical value can be 1 are checked in order to see if their logical value is 1.

Since the logical value of the storage means 23 is 1 encountered at the beginning, the tracking position is transferred to the storage means 23, the position of the corresponding pixel is stored in the storage means 23, and the logical value O is written in the storage means 23.

Next, in the same manner, the logical values are checked in the order of the storage means 3L32 and 10 in a counterclockwise direction starting from the storage means 23.

The storage means 10 is the starting point of contour tracing, and since tracing has been completed, a logical value of 0 is stored.

Therefore, the contents of the storage means 31, 32, 10 are all 0, and the tracing of the outer contour 2 of the pattern 1 is now completed.

By tracking the storage means in this way, the positions of successive contour points can be stored.

The state of the storage device 5 at this time is shown in FIG.

The inner contour tracking is done in the same way as the outer contour tracking.
The tracing of the inner contour 3 of the pattern 1 is completed by detecting the storage means 24 as a starting point and sequentially tracing it to the storage means 29.

Then, the contour tracing ends when all the storage means in the storage device 5 become logical 0.

Because of this method, the outline can be completely traced with a simple device without using an expensive and large flying spot scanner. It is possible to reliably track the outline of

Note that the above has one segment, and the surrounding area is logically O.
Although a two-dimensional pattern surrounded by pixels has been described, the present invention is not limited to this, and can also be used for a two-dimensional pattern having two or more segments.
Even if there is a logic 1 pixel around it, there is a logic 0 outside it.
It can be used by assuming the number of pixels.

Moreover, although the starting point of tracking and the direction of tracking are only one example, they are not limited to this.

As described above, according to the present invention, by using four memory means corresponding to each pixel of a two-dimensional pattern, contour tracking can be performed completely with a simple device, and therefore an inexpensive recognition device can be created. There are advantages.

[Brief explanation of drawings]

Figure 1 is a diagram showing an example of a two-dimensional pattern such as a binarized character, Figure 2 is a diagram showing the outline of the two-dimensional pattern in Figure 1, and Figure 3a is an example of the pattern in Figure 1. Figure 3 shows the storage states of four storage means, and Figure 4 shows the logical values of pixels adjacent to the logic 1 pixel on the upper, lower, left, and right sides. FIG. 5 is a diagram showing the state of the storage means in which data has been written. FIG. 5 is a diagram showing the state in which the outer contour has been tracked in FIG. 4. FIG. 6 is a diagram showing the state of the storage means in the middle of tracking the outer contour. Figure, Figure 7, Figure 8,
FIG. 9 is a diagram for explaining a conventional method of directly tracing a contour from a binary pattern. In the figure, 1 is a pattern example, 2 is an outer contour, 3 is an inner contour, and 4 is a pattern example.
is the logical 1 pixel of pattern 1, 5 is the storage device, 41 to 4
4 and 10 to 33 are binary storage means. In the drawings, the same or corresponding parts are designated by the same reference numerals.

Claims (1)

[Scope of Claims] 1. In a contour tracing method for a binary two-dimensional pattern such as a character or a figure, four binary storage means are provided corresponding to each pixel of the two-dimensional pattern, The four binary storage means correspond to the four directions of the top, bottom, left, and right of the pixels on the pattern, and the logic 1 of the two-dimensional pattern is
(or logic O) when there is a logic O (or logic 1) pixel adjacent to either the top, bottom, left or right of the logic 1 (or logic 0) pixel, the above logic 1 (
or storing a logic 1 (or logic O) in the storage means corresponding to the direction of the logic 0 (or logic 1) pixel among the four binary storage means corresponding to the logic 0 (or logic 0) pixel;
Logic O (or logic 1) is stored in the other storage means to store the outline of the two-dimensional pattern, and the outline stored in the storage means, that is, the logic 1 (or logic 1) is continuously stored.
or logic 0), the above-mentioned storage means are tracked in consecutive order. 2 While tracing the contours, that is, the storage means that are continuously logical 1 (or logical 0) in the consecutive order, store the logical O (or logical 1) in the storage means that has finished tracing, and store the logical 1 2. The contour tracking method according to claim 1, wherein the tracking is completed when the storage means that is in the state of (or logical O) is exhausted.