JPH057751B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to a contour tracing method for recognizing two-dimensional patterns such as characters and figures.

(Prior Art) Conventionally, this type of method employs a method in which a flying spot scanner is used to trace the contours of characters and figures written on paper. When configuring a device using this method, an expensive and large flying spot scanner is used.
The equipment was expensive and large.

Additionally, methods for tracing the contours of binary figures have been proposed in the past, but in conventional methods, the line width is one pixel, so it is not possible to trace the inner contours of loop figures, or the figure itself cannot be traced. Because the focus was on the contour line instead of the contour line, a complicated and time-consuming tracing method had to be used to trace a three-pixel contour line by expanding it into a four-pixel memory element.

On the other hand, in the above method, it is necessary to detect an internal loop portion included in a character or figure, or to detect a figure consisting of a plurality of blocks, by a means different from tracing the outline.

Note that the block here includes all significant pixels that form an outer contour and is independent from the surroundings, and the loop refers to a loop-shaped block that has a closed inner contour (the same shall apply hereinafter). .

Next, these problems will be explained in detail with reference to the drawings.

A shape tracking method according to the prior art will be explained with reference to FIGS. 1 to 5.

FIG. 1 is an example of a two-dimensional pattern of a binarized loop figure with a line width of 1 pixel. In FIG. 1, a logic "1" indicates a figure part and a logic "0" indicates a background part. Therefore, in this case, "1" corresponds to a significant pixel and "0" corresponds to a meaningless pixel.

Figure 2 shows the contour line to be traced equivalent to Figure 1. In Figure 2, "a" represents the outer contour line, "b" represents the inner contour line, and the shaded area represents the shape of the figure. It represents the department. Figure 1 shows a loop shape with a line width of 1 pixel, so
Most of the logic "1" pixels serve as both outer and inner contour points.

FIG. 3 shows the state of a storage device that has stored the figure shown in FIG. 1, and a value of "1" or "0" is stored in the storage element corresponding to each pixel in FIG. 1. Therefore, in FIG. 3, the contour shown in FIG. 2 is stored. In addition, this storage device stores (m
+2)×(n+2) pixels. In FIG. 3, "c" is a symbol indicating the first tracking point (starting point) on the outer contour, and "d" is a symbol indicating the second tracking point.

FIG. 4 shows the state of the storage device after tracking the outer contour in FIG. There is.

FIG. 5 is a diagram showing an example of the order in which the next contour point is searched from the contour point being tracked. In Figure 5,
* is the position of the contour point being tracked. Assuming that the contour point tracked immediately before is located at number 8, numbers 1 to 7 are assigned in a counterclockwise direction with reference to number 8. Therefore, the values of the storage elements corresponding to each pixel are checked in the order of numbers 1 to 8.

Contour tracking is performed as follows.

First, in order to find the starting point of tracking, in the state of the storage device shown in FIG. 3, start with the storage element corresponding to the pixel in the upper left corner of FIG. As the value is examined, the contents of the storage element are initially “0”.
Starting from the pixel at the position where the value changes from "1" to "1" (point c in Figure 3), search for a point where the content of the storage element is not "0" according to the order of numbers shown in Figure 5, and store that memory. The tracking point is moved to the pixel of the element, and the contents of the storage element corresponding to the tracked pixel are replaced from "1" to "2". When this is repeated and the tracking point returns to the starting point, tracking ends.

Next, in accordance with the state of the storage device in FIG. 4 after tracing the outer contour, inner contour tracing is started according to "b" in FIG. However, in this case, the point where the content of the storage element changes from "0" to "1" is not detected, and inner contour tracing is impossible.

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

Furthermore, in contour tracking according to the conventional technology, the purpose was only to trace the contour, so when tracing the shape of a figure or character, the tracing result of one contour is transferred to a loop included inside the figure or character. This method has the disadvantage that it cannot be used to trace the contour of a loop portion, and the presence or absence of a loop portion must be detected by another means.

(Objective of the Invention) The object of the present invention is to add numerical values representing figures or characters to tracked contour points, and to target the contour points independently of the shape of the figures or characters to which the numerical values are attached. By performing sequential scanning of the entire two-dimensional area, the above drawbacks are removed, and not only the position information of the contour points but also the parts assigned numerical values representing figures or characters and the parts of figures or characters that have not yet been tracked can be obtained. Based on the positional relationship with the pattern, detects whether there are blocks that form untraced independent line elements that make up a figure or character within this area, and whether there are loops that exist inside a figure or character that has already been traced. The object of the present invention is to provide a shape tracking method that enables the following.

(Structure of the Invention) The shape tracking method according to the present invention consists of a plurality of processes.

The first process is a shape tracking method that traces the outline of a two-dimensional figure or character that exists within a certain two-dimensional area and is composed of significant pixels having a first numerical value. , which scans in the first direction while detecting changes in pixel values.

The second process is such that the change in the numerical value of the pixel detected in the first process is from the non-significant pixel to the significant pixel having the first numerical value, or from the non-significant pixel to (the first numerical value + the second numerical value). ), this changed pixel is set as the starting point of the contour point.

In the third process, pixels around the pixel that was the starting point of the contour point in the second process are rotated along a predetermined first rotation direction immediately before the starting point of the contour point in the second process. The pixels scanned at The value of the pixel at the center contour point is changed by adding the second numerical value to the pixel value at the contour point, and if an invalid pixel is found on the side of the center contour point in the first direction, the value of the pixel at the center contour point is changed. The third value (≠ second numerical value, and ≠ first numerical value + second numerical value) is added to the pixel value of the point.
When a significant pixel is found, the significant pixel is set as a new contour point.

A fourth process converts pixels around the new contour point found in the third process from the pixel next to the contour point tracked immediately before, along the first rotation direction, to the value of the contour point. While making changes, the search is performed sequentially until a significant pixel is found. When a significant pixel is found, that significant pixel is set as a new contour point, and the surroundings of this new contour point are similarly investigated, one after another. This is a contour tracing process in which a contour point is tracked until the starting point of the contour point is found.

A fifth process is for returning to the first process and restarting the scanning when the starting point of the contour point is found in this contour tracing process.

(Example) Next, the present invention will be described in detail with reference to the drawings.

FIG. 6 corresponds to the tracking of the outer contour shown in FIG. 3 and shows the state of the storage element after the outer contour has been tracked according to the invention. In FIG. 6, "e" is a symbol indicating the starting point of outer contour tracing. FIG. 7 shows the state of the storage element after the inner contour has been tracked according to the invention in FIG. In FIG. 7, "h" is a symbol indicating the starting point of tracing the inner contour. FIGS. 8 and 9 are diagrams showing the order in which tracking is performed according to the present invention, symbols indicating positions relative to the tracking points, and values corresponding to the symbols. In FIG. 8, a indicates the tracking order, b indicates a symbol temporarily attached to pixels surrounding the pixel being tracked for the purpose of the following explanation,
Figure 9 shows the value that has already been added to the pixel being tracked (the pixel marked with * in the figure) when the value of the storage element corresponding to the pixel at the position corresponding to that symbol is "0". It shows the numerical value to be added. FIG. 10 is an example of a flowchart showing an outline of tracking according to the present invention.

The processes used in the present invention include the first to fifth processes.

In the first and second processes, the entire surface of a two-dimensional fixed area (for example, as shown in FIG. 3) is scanned to detect the starting point of the outline (outer outline or inner outline) of a two-dimensional figure or character. I can do it.

The first and second processes are operations for searching for a starting point for shape tracking. This operation uses a so-called raster scan method to sequentially check the values of storage elements, and the values change from "0" to "1" or from "0" to "5" (from "0" to "1" in the conventional technology). When the pixel changes, the operation starts from this "1" pixel (see steps _S1 and _S2 in FIG. 10).

The third, fourth, and fifth processes are operations that trace the contour from the starting point found by the first and second processes. In other words, the values of pixels around the tracking point (the pixel being tracked) are sequentially checked in a predetermined direction, and the tracking point is moved to the first pixel found that is "1" or more ("1" in the conventional technology). This is an operation of moving over pixels one after another and tracing the contour (see step _S3 in Figure 10). The operation ends when it returns to the starting point (Step S ₄ in Figure 10).
reference). The search for pixels around a contour point starts from the pixel next to the pixel of the immediately preceding contour point, so that the pixel of the immediately preceding contour point is examined last.

FIG. 8a shows an example of the order in which the next contour point is searched from the contour point being tracked. * in Figure 8a
is the position of the contour point being tracked, and the contour point tracked immediately before is numbered 8. For example, as shown in the figure, the upper left position is number 8, and numbers 1-
Number 7 is numbered counterclockwise with reference to number 8. Examine the value of the storage element for each pixel in the order of numbers 1-8.

There are two differences from the prior art in the third, fourth, and fifth processes.

One of them is the search for contour points at the starting point. In the case of a starting point, there is no preceding contour point, so it is necessary to determine in advance which surrounding pixel to start from. In the prior art, the order is shown in FIG. 5, but in this embodiment, the order is shown in FIG. 8a.

Another difference is the value of the storage element (the numerical value assigned to the significant pixel). In the conventional technology, the pixel value (the above numerical value) is set to "1" after the tracking point moves.
This value is updated from "2" to "2", but this embodiment is characterized by updating this value.

Figure 9 shows that when the value of the memory element of the corresponding pixel corresponding to each point being tracked in * in Figure 8 is "0", the value of the memory element corresponding to the pixel being tracked is added. FIG.

That is, when searching pixels around the tracking point in the second operation described above, if the search target pixel is "0", the value shown in FIG. 9 is added to the pixel at the tracking point. Therefore, if the search target pixel is to the left of the tracking point and is "0", "2" is added to the pixel at the tracking point (marked with * in the figure). However, even if the right side of the tracking point is "0", if the tracking point moves and the image is no longer the search target before it becomes the search target, "4" will not be added.

FIG. 6 shows the state of the storage device after tracing the outer contour for "a" in FIG.
In other words, if the value of the storage element corresponding to the pixel one pixel to the left is "0", when tracking is completed, the value of the storage element corresponding to the pixel being tracked will be "1".
"2" is added to "3" and replaced with "3", and the value of the storage element corresponding to the pixel one pixel to the right becomes "0".
If so, the value of the storage element corresponding to the pixel being tracked is replaced by "5" by adding "4" to the corresponding value "1".

In FIG. 7, the column containing "h" represents "b" in FIG. 2, corresponding to the state of the storage device in FIG. 6, and indicates the state of the storage device after tracing the inner contour. Therefore, if the value of the storage element corresponding to the pixel one pixel to the left is "0", the value of the storage element during tracking will be "2" added to the value of the storage element corresponding to the pixel being tracked. If the value of the storage element corresponding to the pixel one pixel to the right is "0", the value of the storage element corresponding to the pixel being tracked will be "5".
"2" is added to and replaced with "7".

These situations can be seen at the contour points being tracked in Figure 8b (*
Symbol A indicating the relative position of the search point around it
This will be explained in more detail using ~H.

In Figure 3, to detect the contour point following the starting point, search counterclockwise around the starting point in the order shown in Figure 8a, and find the point where "1" exists first. , position information is extracted from the coordinates using this as a contour point. Until this “1” is detected,
The values shown in FIG. 9 corresponding to each symbol in FIG. 8b are
The values of the storage elements corresponding to the pixels of the tracking point are sequentially added. When the next contour point is detected, the pixels of that contour point are examined as the next tracking point in the order shown in FIG. 8a. For tracking points after the starting point, the search starts from the next position following the number of the previous tracking point.

For example, in the pattern of FIG. 3, it is assumed that the immediately preceding contour point is at the position of symbol H when viewed from the starting point (c of FIG. 3), and the investigation starts from the position of symbol A. Second
The th tracking point (FIG. 3d) is located at the position of symbol B when viewed from the starting point. Here, since the value of the storage element corresponding to the pixel at the position of symbol A is "0", the value corresponding to symbol A, that is, "2" is added according to the addition standard, and the value of the storage element corresponding to the pixel at the position of the starting point is The value of the storage element becomes "3". Next, since the starting point is at the position of symbol F when viewed from the second tracking point, the search starts from the position of symbol G in a counterclockwise direction.
When examined sequentially, the third tracking point is at the position of symbol D from the second tracking point, so the value of the storage element corresponding to the second tracking point is symbol G.
The value "0" corresponding to the symbol H, the value "0" corresponding to the symbol H, the value "2" corresponding to the symbol A, and the symbol B
The value "C" corresponding to the symbol C and the value "0" corresponding to the symbol C are added, and the result is "3".
becomes. Next, since the second tracking point is located at the position of symbol H when viewed from the third tracking point, the search begins counterclockwise from the position value of symbol A. Tracking is repeated in this manner, and if the value corresponding to the symbol H is added when the tracking point returns to the starting point, the tracking ends. At this point, one block is detected and scanning is started again. At this time, if a change point from "0" to "1" is detected, it means that another independent block exists. In this embodiment, since we are dealing with a figure in which one loop corresponds to one block, the inner contour will be tracked next.

Tracking of the inner contour is performed in the same way as tracking of the outer contour. It should be noted that the main parts of the operations of the independent blocks other than those described above are the same as those described above, so a description thereof will be omitted.

Here, in the state of the storage device shown in FIG. 6 after tracing the outer contour, the inner contour will be traced. This time, in order to detect the starting point of the inner contour tracing from the outer contour end point to the right,
The values of the storage elements corresponding to the pixels are sequentially checked. Here, from “0” to “1” or “0”
If there is a point that changes from "5" to "5", this point is set as the starting point of inner contour tracking.

In the case of FIG. 6, this corresponds to the point g that changes from "0" to "5".

The contour of the inner loop portion is traced in the same manner as the outer contour portion. In FIG. 8, starting from the value of the storage element of the pixel corresponding to the symbol H, the search starts counterclockwise in the order shown in FIG. 8, and points where the storage element of the pixel has a value other than "0" are found. The values of the storage elements of the pixels corresponding to the "0" symbol are added up to the "0" symbol.
In FIG. 6, the second tracking point is located at symbol B when viewed from the starting point. Therefore, the value of the storage element corresponding to the pixel of the starting point has already been replaced as a result of tracing the outer contour, i.e.
The value is obtained by adding the value corresponding to the symbol A, that is, "2" to "5", resulting in "7". As seen from the second tracking point, the starting point is at the value of the symbol F, so starting from the position of the symbol G, the value of the storage element corresponding to that pixel is examined. Since the third tracking point is at the position of symbol A, the value corresponding to symbol G, that is, "0", and the value that corresponds to symbol H, that is, "0" are added to the value corresponding to symbol A. becomes “5”. The second tracking point is located at symbol E as viewed from the third tracking point. Therefore, starting from the position of the symbol F, the value of the storage element corresponding to that pixel is examined.
In this way, tracking is repeatedly performed, and when the tracking point returns to the starting point and the value of the storage element of the pixel corresponding to the symbol H is added, the tracking ends.

Note that in the present invention, it is possible to determine what part of a figure the pixel forms based on the value of the pixel replaced by the above-described operation. A typical example is loop detection. (See steps S ₁ and S ₂ in Figure 10).

This is the same full-scale scan “3” to “1” as described above.
Alternatively, it can be detected by searching for a point of change from "1" to "0".

For example, in a two-dimensional full-surface scan after tracking the outer contour, the sixth point corresponding to "d" in FIG.
The memory element at position "f" in the figure is given the numerical value "3" and the right side is "0", so a change from "3" to "0" is detected by scanning from left to right. However, it can be seen that the figure including "d" in FIG. 3 is loop-shaped. Here, if there is a broken part in this figure and it does not form a loop, if you trace the outline according to the rules shown in Figures 8 and 9, you can find the broken end of the loop. From there, it returns along the contour in the direction of the starting point, and in the process of returning, "4" shown in Figure 9 is added to the number "3" given to the position of "f" in Figure 6. , depending on the scan from left to right at the position of "f", it does not go from "3" to "0" but from "7" to "0".
Therefore, it is no longer detected as a loop. The same goes for other pixels, so by scanning and examining the numerical values assigned to each significant pixel, you can detect loops (see step _S5 in Figure 10) and detect the number of blocks (see step S5 in Figure 10). (output possible in relation to step _S2 in the figure).

Therefore, in the case of FIG. 3 (FIG. 6), the number of loops is one. In addition, in this tracking method, for a two-dimensional pattern of m × n pixels, (m + 2) × (n + 2)
There are storage elements with coordinates (i, j) (i=
1, 2, ... m + 2: j = 1, 2, ... n + 2)
Coordinates (1, j), (i, 1),
All storage elements corresponding to (m+2, j) and (i, n+2) are set to "0". That is, m×
One pixel around the n two-dimensional pattern is all set to logic "0". In addition, the 8-connected 3×3 pixels are checked in a counterclockwise direction around the tracking point, and if the search starts from the position of symbol A at the starting point, it is always checked up to the position of symbol H at the end point.

(Effects of the Invention) As explained above, in the present invention, numerical values representing figures or characters are added to tracked contour points, and sequential scanning of a two-dimensional area is performed, which is different from contour tracing which is unrelated to the shape of figures or characters. By implementing this method, it is possible to trace not only the outer contour but also the inner contour of a complex figure or a loop figure with a line width of 1 pixel with a simple operation.

Furthermore, it can be used not only for contour point position information but also for feature extraction in recognition fields such as loop detection and block detection. Another advantage is that a shape tracking method can be formed.

In the above, block detection means checking the number of blocks of characters or figures, and the number of blocks is equal to the number of outer contours.

[Brief explanation of the drawing]

FIG. 1 is a diagram of a loop figure having a line width of one pixel, and is a diagram showing an example of a binary two-dimensional pattern such as a character or a figure. FIG. 2 is a diagram showing the contour line to be traced in FIG. 1. FIG. 3 is a diagram showing the state of a storage element in which numerical values have been replaced and written. FIG. 4 is a diagram showing the state of the storage element after the outer contour tracing according to the prior art is completed. FIG. 5 is a diagram showing the order of tracking destination search according to the prior art. FIG. 6 shows the state of the storage element after tracking the outer contour according to the invention. FIG. 7 shows the state of the storage element after tracking the inner contour according to the invention. 8th
9 and 9 are diagrams showing the order of tracking destination search, symbols of related positions, and corresponding values of the symbols according to the present invention. FIG. 10 is a flowchart showing an example of the flow of tracking according to the present invention. a, b...contour line.

Claims (1)

[Scope of Claims] 1. A shape tracking method for tracing the outline of a two-dimensional figure or a character existing in a certain two-dimensional area and constituted by significant pixels having a first numerical value, comprising: a first process of scanning in a first direction while detecting a change in the numerical value of the pixel; and a change in the numerical value of the pixel detected in the first process has the first numerical value from the non-significant pixel. a second process in which, in the case of a change from a significant pixel or an insignificant pixel to a significant pixel having a numerical value of (the first numerical value + the second numerical value), the changed pixel is set as the starting point of the contour point; Scanning pixels around the pixel that is the starting point of the contour point in the second process, along a determined first rotation direction, immediately before the pixel that is the starting point of the contour point in the second process. From the pixel that
The investigation is performed sequentially until a significant pixel is found, and in the process of this investigation, if an insignificant pixel is found on the opposite side of the first direction from the central contour point that is the center of this investigation, the value of the pixel at this central contour point is The value of the pixel at this central contour point is changed by adding the second numerical value to When the value of the pixel at the center contour point is changed by adding a third value (≠ second numerical value and ≠ first numerical value + second numerical value), and the significant pixel is found,
a third process in which the significant pixel becomes a new contour point, and pixels around the new contour point discovered in the third process are converted along the first rotation direction,
Starting from the next pixel of the contour point tracked just before, the above values are changed while sequentially investigating until a significant pixel is found. When a significant pixel is found, that significant pixel is set as a new contour point and the same process is performed. A fourth process is a contour tracing process in which the surroundings of this new contour point are investigated and the contour points are tracked one after another until the starting point of the contour point is found, and in the contour tracing process, the contour point a fifth process of returning to the first process and restarting the scanning when a starting point of the shape is found.