JPS60263276A - Shape tracking system - Google Patents

Abstract

PURPOSE:To detect a loop part in a graphic or a character by adding a code for showing the graphic or the character to a tracked contour point, and executing a successive scan of a two-dimensional area which is different from a contour tracking having no relation to a shape of the graphic or the character. CONSTITUTION:In case of tracking the contour of a two-dimensional graphic or character which exists in a prescribed area of two dimensions, first of all, the whole two-dimensional area is scanned successively irrespective of a shape of a two-dimensional graphic or character in the prescribed area, and a start point of the contour of the two- dimensional graphic or character is detected. Subsequently, a contour tracking is started from a part where the start point has been detected, and position information of a contour point is obtained. Next, by taking notice of existence of a stroke on the left or the right of the contour point, each different numerical value (reference of addition) is adopted, and a tracking point is encoded. That is to say, the contour point number of 1-8 is given counterclockwise centering around a position of a tracking contour point marked with *, and a value (0,2,4) corresponding to a code corresponding to this number is added. A code is added to the contour point tracked in this way, and a loop part can be detected by executing a successive scan of a two-dimensional area.

Description

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

(Prior Art) Conventionally, this type of method uses a flying spot scanner to track the contours of characters and figures written on paper. When an apparatus is constructed using this method, an expensive and large-sized flying spot scanner is used, resulting in an expensive and large-sized apparatus.

Additionally, methods for tracing the outline of a binary figure have been proposed in the past, but with the conventional method, it was not possible to trace the inner contour of the loop figure due to the line width of one pixel, or the line width of the figure itself was not traced. Because the focus was on the contour line, a complicated and time-consuming tracing method had to be adopted in order to trace the contour line of 8 pixels by expanding it into a storage element of 4 pixels.

On the other hand, in the above method, detection of a loop included in a character or figure or detection of a figure consisting of a plurality of blocks has to be performed by means different from tracing the outline.

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.

Figure 1 is an example of a two-dimensional pattern of a binarized loop figure with a line width of 1 pixel. represent.

Figure 2 represents the contour line to be traced equivalent to the fZ1 diagram, and 嘱aI in Figure 2 represents the outer contour line,
%b1 represents the inner contour line, and the shaded area represents the graphic area. Since Figure 1 represents a loop figure with a line width of 1 pixel, some of the pixels of logical %11 serve as outer contour points and inner contour points.

FIG. 8 shows the state of the storage device that stores the figure in FIG.
The value of N or %OI is stored. Therefore, in FIG. 8, the contour shown in FIG. 2 is stored.

Further, this storage device is provided with (m+2) x (n+2) pixels for a two-dimensional pattern of size mxn. In FIG. 8, 1cl is a symbol indicating the first tracking point (starting point) on the outer contour, and dl is a symbol indicating the second tracking point.

FIG. 4 shows the state of the storage device after tracing the outer contour in FIG. Teru.

FIG. 6 is a diagram showing an example of the order in which the next contour point is searched from the contour point being tracked. In FIG. 5, the book is the location 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.

In the state of the storage device shown in FIG. 8, the values of the storage elements corresponding to each pixel are checked one after another, starting from the storage element corresponding to the pixel in the upper left corner of FIG. With the pixel at the position where the content first changes from z6N to %11 as the starting point (point C in Figure 8),
The contents of the storage elements are % according to the order shown in the figure.
Search for a point that is not Ol, move the tracking point to the pixel of that storage element, and replace the contents of the storage element corresponding to the tracked pixel from -II with %2.

When this process is repeated and the tracking point returns to the starting point, the tracking ends.

Next, in accordance with the state of the storage device shown in FIG. 4 after tracing the outer contour, inner contour tracing is started according to 1bl in the second step. However, in this case, the point where the content of the storage element changes from %Ol to Kame1 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. 1.

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

C) An object of the present invention is to add a code representing a figure or a character to the traced contour point, and perform a two-dimensional area scanning which is different from contour tracing which is unrelated to the shape of the figure or character. This eliminates the above drawbacks and constructs a figure or character within this area based not only on the positional information of the contour points but also on the positional relationship between the encoded part and the notation of the figure or character that has not yet been tracked. A shape characterized in that it is configured and realized so that it is possible to detect the presence or absence of a block forming an untraced independent line element, and the presence or absence of a loop portion that exists inside a figure or character that has already been traced. 0 (Arrangement of the Invention) The shape tracking method according to the present invention is comprised of a plurality of means.

The first means, when tracing the outline of a two-dimensional figure or character existing within a certain two-dimensional area, sequentially scans the entire two-dimensional area regardless of the shape of the secondary figure or character within a certain value range. To start contour tracking from the point where the starting point of the contour of a dimensional figure or character is detected, and to obtain position information of the traced contour point.

The second method focuses on the presence or absence of a line element on the left or right side of a contour point, sequentially encodes the contour points using different numerical values, and detects blocks from the tracing results of the outer contour in the encoding process. This is to continue scanning the entire area, including the blocks that have already been scanned.

The eighth means is to detect the untracked information to detect the existence of a loop and trace the inner contour if untracked information exists inside a block whose outer contour has been tracked in the continuation of full-surface scanning. It is used for encoding.

The fourth means is to track and encode blocks as outer contours when other types of blocks are detected during the continuation of full-surface scanning.

The present invention is configured to detect loop parts of two-dimensional figures or characters within a certain value range and obtain block number information by repeating tracking until there are no untracked parts by the above means. It is.

(Example) Next, the present invention will be explained 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, %61 is a symbol indicating the starting point of outer contour tracking. 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, SS f
II is a symbol indicating the starting point of tracing the inner contour. 8th
9 and 9 illustrate the order in which tracking is performed according to the invention,
FIG. 3 is a diagram showing symbols and values corresponding to the symbols. In FIG. 8, (a) shows the tracking order, (b) shows the symbol thereof, and FIG. 9 shows the value corresponding to the symbol. FIG. 10 is a flowchart outlining tracking according to the present invention.

FIG. 6 shows the state of the storage device after tracing the outer contour with respect to 1a in FIG.

In other words, if the value of the memory element corresponding to the pixel one pixel to the left is \\0#, No 1, and the value of the memory element when tracking is completed is the value of the memory element corresponding to the pixel being tracked, that is, the value of 2N is Added to the corresponding value 11N and $
8#, and if the value of the storage element corresponding to the pixel one pixel to the right is 101, the value of the storage element corresponding to the pixel being tracked is added to the corresponding value %1#. However, it has been replaced with 5N.

In FIG. 7, the column containing qf represents the %bI in FIG. 2 corresponding to the state of the storage device in FIG. 6, and shows the state of the storage device after tracing the inner contour. therefore,
The value of the storage element corresponding to the pixel one pixel to the left is %0#
If so, the value of the storage element during tracking is replaced by 12 by adding 12 to the value of the storage element corresponding to the pixel being tracked, and the value of the storage element corresponding to the pixel one pixel to the right becomes %0〃, the value of the storage element corresponding to the pixel being tracked is replaced with 12〃 by adding 12〃 to %5N.

FIG. 8(a) shows an example of the order in which the next contour point is searched from the contour point being tracked. In FIG. 8(a), * indicates 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 to 7 are assigned counterclockwise with reference to number 8. Examine the value of the storage element for each pixel in the order of numbers 1-8.

FIG. 9 shows the value to be added to the value of the storage element corresponding to the pixel being tracked when the value of the storage element of the corresponding pixel corresponding to each point in FIG. 8 is βO〃. FIG.

In other words, if the value of the storage element corresponding to the pixel one pixel to the left of the pixel being tracked indicated by * is μ0, then the value %21 corresponding to the number ] corresponds to the pixel being tracked. is added to the value of the storage element. On the other hand, if the value of the storage element corresponding to the pixel one pixel to the right is 10, then the value 4# corresponding to number 5 is added to the value of the storage element corresponding to the pixel being tracked. It means that Track by adopting such addition criteria!
Encode points.

Next, detection of the starting point of contour tracking will be described.

In FIG. 8, values of storage elements corresponding to pixels are sequentially checked from the pixel at the upper left corner toward the right.

On the way, the value changes from Qi O〃 to Qi 1#, or from Qi oI to %5
If there is a point that changes to N, that pixel is the starting point for contour tracking.

Contour tracking is performed as follows.

In Fig. 8, to detect the starting point, search counterclockwise around the starting point according to the order shown in Fig. 8, first find the point where the ant 1N is present, and use this as a contour point to obtain positional information. Extract from the coordinates.

The values shown in FIG. 9 corresponding to each symbol in FIG. 8(b) are sequentially added to the value of the storage element corresponding to the pixel of the tracking point until qi 1 l is detected.

When the next contour point is detected, that pixel is treated as the next tracking point and examined in the order shown in Figure 8 (a). Here, for the tracking points after the starting point, the next positional force following the number of the immediately preceding tracking point is started.

fHJ, t, in the pattern of Figure 8, the starting point (Figure 3 (C
)) Assuming that the previous contour point is at the position of symbol H, the investigation starts from the position of symbol A. The second tracking point (FIG. 3(d)) is located at the position of symbol B as seen from the starting point. Here, since the value of the storage element corresponding to the pixel at the position of symbol A is 10, the value corresponding to symbol A, that is, 2, is added according to the addition standard, and the memory at the pixel corresponding to the starting point is Enment's value is Qi 8I. 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 the symbol from the second tracking point, so the value of the storage element corresponding to the second tracking point is the value corresponding to the symbol G - 0 〃, and the value %0 corresponding to the symbol H.

2f to the value corresponding to symbol A and stone Buddha NO. corresponding to symbol B
# and the value 0〃 corresponding to the symbol C are added υ, and the result is %8〃. Next, since the second tracking point is located at the position of symbol H when viewed from the eighth tracking point, the search starts from the position of symbol A in a counterclockwise direction. In this way, tracking is repeatedly executed, 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 has been detected and scanning is started again. At this time, from %0# to %1N
If a change point is detected, it means that another independent block exists. In this example, 1 block has 1
Since the loop is handling the corresponding figure, next we will trace the inner contour.

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 inner contour tracing from the end point of outer contour tracing to the right, values of storage elements corresponding to pixels are sequentially checked. Here %Q# to Qi 1
〃, or if there is a point that changes from %Ol to %5I,
A loop portion exists inside the figure whose contour has been traced, and this point is taken as the starting point for tracing the contour of the inner loop portion.

The contour of the inner loop portion is tracked 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 begins counterclockwise in the order shown in FIG. 8 until a point is found where the storage element of the pixel has a value other than %O. 0〃
The values of the storage elements of the pixels corresponding to the symbols are added.

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 at the starting point is already obtained by adding the value corresponding to the symbol A, i.e. %2g, to the value replaced as a result of tracing the outer contour, i.e. 51. becomes the value,
The result is 7g. Since the starting point is at the position of the symbol F when viewed from the second tracking point, the value of the storage element corresponding to that pixel is written starting from the position of the symbol G. Since the eighth tracking point is at the position of the symbol A, the value corresponding to the symbol G, i.e. %ON, and the value corresponding to the symbol H, i.e. -Ol are added to the value corresponding to the symbol A to calculate the result. It becomes 5N. The second tracking point is located at symbol E as viewed from the third tracking point.

Therefore, starting from the position of symbol F, the value of the storage element corresponding to that pixel is examined. In this way, tracing is repeatedly executed 2, and when the value of the storage element of the pixel corresponding to the symbol H is added when the tracing point returns to the starting point, the tracing ends.

Here, the number of loops is 1. In addition, with this tracking method,
For a two-dimensional pattern of m×n pixels, (m+2
) X (n + 2) storage element is empty, coordinates (i, j) (i=1.2.=・m+2:j=1.2.
Coordinates (1.,+)+ for the memory address of ...n+2)
(t+1)+(m+2+j)+(iyn+2) (memory element)U are all %Ol. That is, m
Every pixel in the two-dimensional pattern of Xn is logical%
O〃. Furthermore, the search is performed in a counterclockwise direction in 8 connected 8×3 pixels 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 (d), a code representing a figure or a character is added to the traced contour point, and a two-dimensional region is sequentially By performing scanning, there is an effect that not only the outer contour but also the inner contour of a complex figure or a loop figure with a line width of one pixel can be traced with a simple operation.

Furthermore, we can detect not only the position information of contour points but also loops.
It can also be used for feature extraction in the field of recognition such as block detection, so it has the effect of forming an inexpensive shape tracking method that can completely and quickly track contours with a simple device.

In the above, blocks are detected by 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 drawings]

FIG. 1 is a loop figure diagram having a line width of one pixel, and is a diagram showing an example of a two-dimensional (2D) turn in which characters, figures, etc. are binarized. 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 tracking is completed. FIG. 6 is a diagram showing the order of tracking according to the prior art. FIG. 6 is a diagram illustrating the state of the storage element after tracking the rainbow outer contour according to the present invention. FIG. 7 shows the state of the storage element after tracking the inner contour according to the invention. 8 and 9 illustrate the order of tracking according to the invention, 4
1 and the corresponding values of symbols. FIG. 10 is a flowchart showing the flow of tracking according to the present invention. a, b...Contour line patent applicant Hisashi Inoro, agent for NEC Corporation, patent attorney

Claims (1)

[Claims] When tracing the outline of a two-dimensional figure or character existing within a certain two-dimensional area, the entire two-dimensional area is sequentially scanned regardless of the shape of the secondary figure or character within the certain value range, and the outline of the two-dimensional figure or character is traced. Alternatively, a first means for obtaining positional information of the traced contour point by starting contour tracing from a point where the starting point of the contour of a character is detected, and focusing on the presence or absence of a line element on the left or right side of the contour point. A second means for sequentially encoding the contour points using different numerical values, detecting blocks from the tracking results of the outer contour in the encoding process, and further continuing the entire surface scan including the detected blocks. Then, in the continuation of the entire surface scan, if untracked information exists inside a block in which the outer contour has been tracked, the untracked information is detected to detect the existence of a loop, and a new inner contour is detected. eighth means for tracking and encoding, and if another type of block is detected in the continuation of said full-surface scanning, fourth means for tracking and encoding it as said outer contour; and configured to detect a loop part of the two-dimensional figure or character within the certain area and obtain block number information by repeatedly performing the tracking until the untracked part disappears. This shape tracking method is characterized by: