JPS63204376A - Contour tracking method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a method for tracing the outline of a sampled figure, and in particular to a method for rapidly obtaining a contour coordinate sequence of a figure from a compression-encoded image of a drawing or document. This invention relates to a contour tracking method suitable for.

[Conventional technology]

Conventionally, as a method for extracting a contour coordinate string of a figure or an object in an image, as described in Japanese Patent Application Laid-Open No. 111786/1986, the method is based on scanning the image from two directions perpendicular to each other. First find the coordinates of each image change point,
Next, the continuity of these coordinate values was checked to obtain a contour coordinate sequence.

[Problem that the invention seeks to solve]

In the above-mentioned conventional technology, it is necessary to extract image change points in each of the horizontal and vertical directions, but this calculation requires a large amount of processing because it involves processing over the entire image.

Furthermore, after the coordinates of image change points are extracted, tracking is performed using a type of mask on the coordinate table, which poses problems such as increased processing time.

An object of the present invention is to solve the above problems and provide a high-speed contour tracking method. [Means for solving the problem] The above purpose is to input the image change point for each line and to memorize the image change point of the current line and the image change point of the line immediately before the current line. Then, a basic shape constituting a part of the contour is extracted by referring to the stored image change point of the current line and the stored image change point of the previous line, and the extracted basic shape is extracted. This is achieved by integrating the shapes and converting them into a contour coordinate sequence.

[Effect]

In order to extract the basic shape forming a part of the contour line, the stored image change point of the current line and the image change point (X position II) of the line immediately before this line are referred to. In addition to extracting a specific basic shape from the positional relationship at this time,
- Connect with the basic shape extracted in the process before the line using a pointer.

Once the basic shape has been extracted for one line, 0 or more processes are performed for all lines, such as transferring the image change point of the current line to the previous line storage unit and inputting the image change point of the new line to the current line storage unit. After that, the basic shapes connected by pointers are integrated to obtain one contour coordinate string.

With the above method, contour tracking can be executed using image change points in only one direction, and since a pointer is attached to the basic shape, conversion to contour coordinates can be executed at high speed.

Note that in the process of transferring the contents of the current line storage section to the previous line storage section, actual data transfer can be omitted by alternately switching the addresses of each line storage means.

〔Example〕

The present invention will be explained below with reference to the drawings. FIG. 1 is an overall configuration diagram of the contour tracking method of the present invention.

In FIG. 1, 1 is an image change point file, 2 is a control unit,
3 is the image change point input section, 4 is the current line buffer, 5 is the previous line buffer, 6 is the basic shape extraction section, 7 is the basic shape link table, 8 is the contour coordinate file. 0 Image change point file 1 contains the line The coordinates of each image changing point are stored, and the 1 image changing point input unit 3 inputs l! Current line buffer 4 is input. At this time, the image change points that were already stored in the current line buffer 4 are transferred to the previous line buffer 5.The primary basic shape extraction unit 6 reads out the contents of the line buffers 4 and 5 one by one.
A basic shape constituting a part of one contour line is extracted based on a comparison of the magnitudes of these coordinates.

The extracted basic □ shape is stored in the basic shape link table 7. At this time, a line buffer 4, which performs a link using a pointer with the basic shape extracted one line before,
When all basic shapes have been extracted for the contents of 5, 1
When 0 or more processes for reading the image change point of the next line from the image change point file 1 are completed for all lines, the contour coordinate conversion unit 8 integrates the basic shapes in the basic shape link table 7 while following the pointer. Create a contour coordinate string,
Output to contour coordinate file 9 and finish contour tracking.

The control unit 2 controls the entire process described above.

FIG. 2 shows ten types of basic shapes extracted by the basic shape extraction section 6. All six contour lines can be expressed by combinations of these basic shapes. Numbers from ■ to [phase] are assigned to this basic shape, and this is called an RD code (run type direction code). The end point of the arrow at the tip of the RD code is called I(sad, and the opposite end point is called Ta1l. The black circle in the figure is the representative point position of the RD code, which was determined to specify the position. 6 Contour When a line is described in a basic shape called an RD code, the pointer is operated so that the Head of the RD code always links to the other party's Ta1l.

Figure 3 is an example of how the outline of a figure in an 8x69 image is described using RD codes.The outline of figure 50 is written using 14 RD codes (■■ ■・
...@) can be expressed. It is easy to convert this RD code string into a general contour coordinate string. If only the representative point position of the RD code is used as a contour line coordinate string, intermediate coordinates will be missing, but these can be interpolated using the representative point positions of the preceding and following RD codes.0 For example, in (■■...), the representative of ■ If the point position is (2,5,L,S) and the representative point position of ■ is (1,5°2.5), the intermediate coordinates are (2,5,2,5), and the coordinate string ((2,5,1,5)(2,5°2.5
)(L, S, 2.5)...), and the reason why the representative point position has a fraction of 0.5 is because it is based on the coordinates of the center of the pixel, and the fractions are rounded down. It goes without saying that it may be simplified.

FIG. 4 shows an example of the data structure of the line buffer, in which the current line buffer 4 and the previous line buffer 5 store the X coordinate string of the image change point.
An exit code is included at the end of the data. Note that the pointer P1 is used to read out the previous line buffer 5, and the pointer P2 is used to read out the current line buffer 4.

FIG. 5 shows the combination of runs between the lower lines in FIG. 1, which shows the RD code extraction automaton of the basic shape extraction section 6. The upper row is the run type of the previous line, the lower row is the run type of the current line, and B
indicates a black run (1, that is, a series of black pixels on the image), and W indicates a white run (O, that is, a series of white pixels). is the position of the image change point currently read out from the line buffer 4. There are six states in total.

State 1 is always passed through when scanning starts and ends for each line. In each state, there are three types of state transition depending on the comparison result of xl and X2, and at that time, RD codes ① to [phase] are extracted. The rules for reading image change points Xi and X2 from each line buffer 5.4 are as follows.

It is assumed that among the compared image change points, the line buffer with the smaller value is read out. If they are the same, they are read from both line buffers.According to this automaton, for example, the extraction condition for RD code ■ is that XI>X2 holds true in state 1, and after updating X2, in state 3 Xi> X2
This can be said to be the case when . According to a graphical interpretation, this means that it has been confirmed that the area above the currently focused run (in this example, the black run) is the background part. As explained with reference to FIG. 4, the ψ code is included at the end of the line buffer, and in processing this is regarded as the left edge B, so that all the data are successively output.

FIG. 6 is a diagram illustrating the specific processes to be executed based on the automaton shown in FIG. 5, organized by state.

Update the X coordinate of the representative point position of the RD code and extract the RD code based on the size conditions of xl and X2.

Updating the number to the registration secondary state Reading out the secondary image change point. When registering the RD code, there is a linking process with the RD code that is already waiting for linking. R.D.
The code includes: (1) Items that do not wait for a link■ [Phase]... Both Head and Ta1l are pointing upwards (
2) Items that are waiting for a link■■■■■■■■...There are two types with Head or Ta1 pointing downwards.For (2), manage it with a pointer as a link waiting list when extracting the RD code, The currently extracted RD code and the RD codes on the link waiting list are sequentially linked.

FIG. 7 shows an example of the basic shape link table 7.

The basic shape link table 7 is the representative point 71 of the RD code.
1X, Y and their code numbers C0DE, a LINK pointer that links between RD codes, and W-L that temporarily lists the RD codes that are waiting to be linked.
This is a table consisting of five items of INK pointers. Also, A as a pointer for operating the basic shape link table 7.

There are three, B and C. The A pointer is a pointer pointing to the address where a new RD code is registered.

The B pointer is a pointer pointing to the start address of the link waiting RD code list, and the C pointer is a pointer pointing to the start address of the link waiting RD code list.
This is a pointer to the final address of the code list. Note that the values in FIG. 7 are an example of processing the image in FIG. 3.

FIG. 8 is a flowchart (PAD) showing the contour tracking processing procedure of the control unit 2 shown in FIG. Also, define the variable names used in the flowchart.

C-Line -Boffor: Current line buffer 4P -Line-Buffer S previous line buffer 5Status: Status number (1 to 6) A, B, C: Pointer Flag: B pointer control flag (0 or 1): Current scan Line number of inner image ”.

5tatus=1: Set the initial state of the automaton to 1.

A=O, B=1. C=1. Flag=O; Initialization of various variables 5 top 2: NY+1. Execute the following process 5to
p2.1 Shifting the two-line buffer Here, the buffer shift is a method of switching the address of the line buffer based on the odd or even number of K without actually transferring data.

The contents of C-Line-Boffor are converted to P-Line
- Transfer to Buffer (actually C-Line-Bo
(Switch the address of ffor and P-Line-Boffor) Step2, 2: Read image change point for one line, if K>NY, C-Line-Buffe
r (1) = ψ Otherwise, 1 image change point file 1
The image change points for one line are read out, and C-Line-
Boffor Heset.

5top2,3: Initialization for contour tracking between two lines Pz=1. Pz=1 Initialization of read pointer of second line buffers 5, 4 X1=P-Line-Boffor (PL
): Set the first data of the previous line buffer 5 to variable X1
Set X 2 = C-Line-Buffer (P 2
) ;Set the first data of current line buffer 4 to variable x2
Set to 5top2, 4: Contour tracking processing between 2 lines (
(Execute the following process until both XI and X2 become ψ code) Step2.4. l: RD code extraction, endorsement, link processing 5top 2.4.2: Xi, X2+71 data update (Note) Steps 2.4.1 and 2.4.2 are based on the table in Figure 6.

5top 3: Convert the RD code obtained in 5top 2 into a coordinate string.

As described above, according to this embodiment, the image memory for contour tracking is economical because it only requires a line buffer for two lines. This method is faster than the method that uses image change point positions.

Furthermore, the 10 types of basic shapes that make up the outline are general-purpose shapes that can be applied to any figure, and can faithfully describe the outline of a single figure. In addition, image files of documents and drawings are usually run-length encoded, and are compatible with the contour tracking method of the present invention.

Furthermore, this embodiment does not use any special arithmetic unit, and high speed is guaranteed even if a normal general-purpose computer is used.

〔Effect of the invention〕

According to the present invention, contour tracking can be performed using image change points in only one direction, and the basic shape extracted from position comparison of image change points between two lines.

Since a pointer is provided, there is no need for extra searching when converting to contour coordinates, which has the effect of obtaining a contour coordinate string at high speed.

[Brief explanation of the drawing]

FIG. 1 is an overall configuration diagram of an embodiment of the present invention, FIG. 2 is a diagram of types of basic shapes, and FIG. 3 is an example of outline description of a figure using the basic shape of FIG. , Figure 4 shows the data structure of the line buffer,
Figure 5 shows the automaton of the basic shape extraction part in Figure 1, and the 6th
The figure shows the image change point analysis table showing the automaton in Figure 5 by state, Figure 7 shows the data structure of the basic shape link table in Figure 1, and Figure 8 shows the flowchart of the entire process (PAD).
It is. 1... Image change point file, 2... Control unit, 3...
・Image change point input section, 4...Current line buffer, 5
...Previous line buffer, 6...Basic shape extraction section, 7
...Basic shape link table, 8.Contour coordinate conversion section, 9..Contour coordinate file,
, , Agent □yo 41,11□A. ■ Z Figure ￥ J 3 Figure 50 Figure Section Nr ((D■■■■■■■■■■■■O) No 4 Figure 4 To Akimi Zai - Lai〉 °zo 5 Scenery η Line Han “n 7r Atsushi 5 Figure (a) Overall diagram of Oshimaton V:J 6 Kuchitomi 7 Figure

Claims (1)

[Claims] 1. In a contour tracing method that creates a contour coordinate string by tracing the outline of a figure from an image described by image change points, the image change points are input line by line, and the image change points of the current line and the current line are input. The image change point of the previous line is stored, and the stored image change point of the current line and the stored 1
Contour tracking characterized by extracting a basic shape constituting a part of the contour by referring to the image change point of the previous line, and integrating the extracted basic shapes and converting them into a contour coordinate string. Method.