JPH0670797B2 - Image run length calculation method - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for calculating an image run length.

2. Description of the Related Art Conventionally, when a characteristic parameter such as an area and a center of gravity of an object is calculated based on a binary image of the object,
The number of pixels in which the logic "0" or logic "1" for each pixel stored in the image memory is continuous in the X direction (TV screen raster scanning direction), that is, the run length, is determined by hardware or software in the Y direction. Individual determination is performed by sequentially obtaining the data in the direction (perpendicular to the raster scanning direction) and processing this run length data by the SRI algorithm (connectivity analysis).

Problems to be Solved by the Invention In such a prior art, when the run length is obtained by hardware, the calculation can be performed in a short time, but there is a drawback that dedicated hardware is required and the apparatus becomes expensive. Further, when the run length is obtained by software, there is a problem that it takes a long processing time as a result of two-dimensionally searching the connected area of the image data.

Furthermore, regarding the process of processing run length data with the SRI algorithm (connectivity analysis), the shape of the object becomes complicated, and the run length data increases as the number of objects increases. There is a problem that the processing time is long because the number of data to be compared increases exponentially.

An object of the present invention is to provide a method for calculating an image run length, which enables an image run length to be calculated in a short time with a simple configuration.

Means for Solving the Problems The present invention traces a contour of a binary image represented by a large number of pixels having XY coordinates in a predetermined direction to obtain a closed loop of contour lines, At the time of this tracking, a chain code for each pixel forming the contour line is obtained, and this chain code is on the right of each pixel forming the contour line,
Consists of a total of eight pixel directions (0 to 7) that are adjacent to diagonally upper right, upper, diagonally upper left, left, diagonally lower left, lower, and diagonally right lower, and configure the contour line when tracing the contour. By combining the first chain code dir1 of the adjacent pixel immediately before reaching each pixel and the second chain code dir2 of the adjacent pixel immediately after moving from the pixel forming the contour line, X
Direction or Y direction (X in the embodiment
Direction), a determination table (Table 2) for determining the start point S and the end point E, which are at least two roles on the run length, is determined in advance, and either the X direction or the Y direction (the other direction) is executed. For each coordinate y in the example (Y direction), each of the roles S,
A run length table (FIG. 17) is created by associating E with the coordinate x1 of the start point S and the coordinate x2 of the end point E in one of the above directions (X direction in the embodiment). , N = x2-x1 + 1 is calculated, and the run length of the image is calculated.

Further, according to the present invention, the contour is traced with the left hand so that the pixel follows a logical value of either logic "1" or logic "0" (logic "1" in the embodiment), and each contour is configured. The chain code of the pixel is "0" for the right of the adjacent pixel, "1" for the upper right diagonal, "2" for the upper diagonal, "3" for the upper left diagonal, "4" for the left diagonal, and "5" for the lower diagonal left. , "6" for the bottom and "7" for the diagonally lower right, It is characterized by setting in.

Operation According to the present invention, either the logical value of the logical "1" or the logical "0" of the binary image represented by a large number of pixels in the XY plane (the logical "1" in the embodiment described later is used. )) In the left hand, the contour is traced in one direction, that is, counterclockwise in the embodiment, and the inclusion relation of the closed loop of the contour line image is investigated. Based on the above, the individual separation is performed and the processing time required for the individual separation is shortened.

At the time of this tracking, a chain code for each pixel forming the contour line is determined in correspondence with the directions (0 to 7) of a total of eight pixels adjacent to the periphery, as shown in FIG.
When tracing the contour, the first chain code dir1 of the adjacent pixel immediately before reaching each pixel forming the contour (that is, the immediately adjacent pixel entering each pixel forming the contour) is obtained. Together with the adjacent pixel immediately after moving from the pixel forming the contour line (that is, the adjacent pixel emerging from the pixel forming the contour line)
To obtain the second chain code dir2 of, and thus by the combination of the first and second chain codes dir1, dir2,
A determination table for determining at least two roles S and E of whether the pixel forming the contour line is the start point S or the end point E is determined in advance, for example, as in Table 2 described later. Based on this judgment table, a run-length table is created as shown in FIG. 17 described later, and this run-length table has either the X direction or the Y direction (the later-described direction). For each coordinate y in the Y direction), each of the roles S and E of the run length and the coordinate x1 and the end point E of the start point S in either one of the directions (X direction in the embodiment described later) The coordinate x2 is created in correspondence with the coordinate x2, and the run length n is calculated for each coordinate y in the other direction (Y direction in one embodiment as described above).

Such a method is a one-dimensional search, the processing time is very short even if it is realized by software, and no special hardware is required, and the configuration is simplified.

Embodiment FIG. 1 is a flow chart showing the overall steps of an embodiment of the present invention, and FIG. 2 is a block diagram showing a configuration for performing the arithmetic processing. The image memory 1 stores a binary image for each pixel obtained by imaging an object, for example, and the processing circuit 2 realized by a microcomputer or the like is stored in the image memory 1. The contents are calculated to calculate the characteristic parameter. In calculating the characteristic parameters, steps n1 to n3 in FIG. 1 are calculated.
Then, the contour line is tracked, and in steps n4 to n7, the basic feature parameters, that is, the moment, the area, the center of gravity, the posture angle, and the circumscribed rectangle are calculated, and the farthest point and the closest point are detected. The direction from the center of gravity of is calculated. In step n8, the derived characteristic parameters, that is, the moment ratio, the area ratio, the aspect ratio, etc. are calculated, the total amount of holes of the object is calculated, and the total area and the total perimeter are calculated.

First, a method of tracking contour lines will be described first. FIG. 3 shows a binary image stored in the image memory 1 and representing a bright object in a dark background. In this FIG.
Black circles indicate pixels of logic "0" as shown in FIG. 4 (1), and white circles indicate pixels of logic "1" as shown in FIG. 4 (2). The contour line of the object in this image is searched by the following steps (1) to (5).

(1) From the upper left to the lower right of the binary image shown in FIG. 3, that is, from the left to the right in the X direction and from the upper to the lower in the Y direction, in this order, each pixel has a logical "0". , Or dark to logical "1" or bright.

(2) If the point surrounded by the square frame 30 in FIG. 3 is detected as a candidate on the contour line and the contour line has not been traced yet,
This point has no tracked information called markers,
Determined as the starting point for contour tracking. For each pixel, information indicating whether or not the tracking has been completed is also stored as described above.

(3) As shown in FIG. 5, set the current pixel on the contour line to Q.
When the pixel before moving to the pixel Q is P, the search for the pixel moving from the pixel Q is processed according to FIG. That is, of the eight neighboring points of the pixel Q, the pixel P3 in the direction of the pixel P → pixel Q and the four pixels P1, P2; P5, P4 on the left and right of the direction are examined in the order of P1 → P5, The first found pixel of logic "1" is selected. When the pixel Q is the starting point, the pixel P1 is selected as the pixel to the left of the starting point. If the pixel P1 has a searched marker, the contour search is terminated.

(4) The contour line is traced in this way, and when the contour line is returned to the original starting point, the contour tracing is ended. FIG. 6 shows the traced result. Since the contour line is traced in such a manner that the pixel traces the area of logic "1" with the left hand, the contour line of the object is counterclockwise in this embodiment. In FIG. 6, the contour line is indicated by reference numeral 31.

Such a procedure is similarly performed for tracking the outline of a hole. Tracking the outline of a hole is performed clockwise as shown in FIG.
Indicated by 32. The starting points in FIGS. 6 and 7 are indicated by double circles.

(5) When the contour line tracking is completed in this way, the contour lines 31,3
The tracked information called a marker is attached to the pixel on 2 above. Therefore, again in the above step (1), the candidate points on the contour lines 31 and 32, for example, the broken line frame 3 in FIG.
Even if the point indicated by 3 is detected, no further tracking is performed because the marker, which is the tracked information, is stored in the candidate point.

This contour line is the starting point indicated by the double circle in FIG.
It is recorded and stored by a chain code in which S1 and the moving direction from S1 are sequentially represented by the numbers 0 to 7 shown in FIG. For example, the chain code of the contour line 31 starting from the starting point S1 in FIG. 6 is “54565465 ...”.

The advantages (a1) to (a3) of contour line tracking by the procedures (1) to (5) are listed below.

(A1) Whether the contour line represents an object or a hole,
It is common.

(A2) Simple structure and fast processing.

(A3) In contour line tracking, since image information is used one-dimensionally (in a linear form), even if the size (area) of the object is N times larger and the number of pixels increases, the time required for tracking is It is only the square root of N.

In order to reduce the time required to detect the starting point of the contour line, in one embodiment of the present invention, the starting point is detected by hardware. Therefore, a so-called mask operator for the size of 3 × 3 pixels shown in FIG. 9 is adopted. Each pixel A to I of this mask operator represents an active value of each pixel, that is, a logic "0" or a logic "1". When the following Expression 1 or Expression 2 is satisfied, the pixel corresponding to the pixel E is set as the candidate of the starting point of the contour line, and X-
Store the position of the Y coordinate system.

... E = 1 (truth value) (1) A, B, C, ... E = 1 (truth value) (2) In the detection of the start point of the contour line by this hardware configuration, for example, The points in the square frame shown in Fig. 10 are candidates for the starting point. For each candidate point, the procedure for contour line tracking described above is performed. Since double tracking is avoided for each pixel by using a marker, only the double circle candidate point of each pixel of the square frame actually becomes the starting point of the contour line. This starting point includes a starting point S1 on the outer circumference of the object and a starting point S2 on the outline of the hole.

In such a configuration, since the detection of the starting point in tracing the contour line is performed by the hardware configuration,
Next, there is an advantage that the detection speed can be remarkably improved as compared with the two-dimensional search in which the computer program by the software to be executed is executed to detect the starting point.

In order to detect the starting point of the contour line, a procedure of detecting the starting point by software instead of the hardware configuration will be described as another embodiment of the present invention. This procedure is, so to speak, a thinning-out method, that is, the X of one image shown in FIG.
The logical value of each pixel is checked at predetermined intervals m (for example, m = 4 in this embodiment) in the Y direction and the Y direction. Pixels whose logical values are to be examined are indicated by a box in FIG. In the X direction, the logical values of the pixels at constant intervals m are checked from the left to the right in FIG. 11, and if a section in which the logical value changes from logic “0” to logic “1” is found, this section Inside, the point where the logic “0” changes to the logic “1” is examined for each pixel. For example, when the pixel 34 is a logical "0" and the next examined pixel 35 is a logical "1", the logical value of each pixel is the logical value of the pixel 34 along the arrow 36 in the X direction. It is checked whether or not the logical value has changed from "0" to "1". As a result, the dot 37 indicated by the double circle is the pixel
This is the first point between logic 34 and 35 that changes from logic "0" to logic "1", and this pixel 37 is detected as a candidate for the start point.
Then, from the starting point 37, the contour line is traced. With such software, pixels are thinned out at regular intervals m, so to speak, to detect the start point of the contour line, so that the number of image data to be inspected is significantly reduced, and the processing speed can be increased. it can.

After the above-described procedure of tracing the contour line, secondly, the discrimination between the object and the hole and the determination of the inclusion relation are performed as described below. After the contour is detected, the
As shown in FIG. 12, by searching for the point at the top and the leftmost of the points, that is, point S1S2 in FIGS. 6, 7, and 10, and examining the pixel directly above it, , It can be determined whether the contour represents an object or a hole. For example, in FIG. 6, contour line 31
Since the pixel 38 immediately above the starting point S1 is a logic "0",
It is determined that it is the contour line 31 of the object. Further, the starting point S2 in FIG. 7 is that the pixel 39 immediately thereabove is the logic "1",
The contour line 32 is determined to be the contour line of the hole. The contour line 31 of the object is 0-LOOP (Object Loop), and the latter is H-LOOP (H
ole Loop), and manage by assigning a loop number.

On the other hand, regarding the contour line, the following items (b1) to (b4) are considered when the inclusion relation is considered.

(B1) Contour of an object that does not belong to other contours (Master Obj
ect Loop, abbreviated MO-LOOP).

(B2) The contour line of the hole belonging to the contour line MO-LOOP (Ma
ster Hole Loop, abbreviation MH-LOOP).

(B3) A contour line (Slave Object Loop, abbreviated as S-O-LOOP) of an object belonging to the contour line MH-LOOP.

(B4) Contour line of the hole belonging to the contour line S-O-LOOP (Sl
ave Hole Loop, abbreviated SH-LOOP).

FIG. 12 shows four such contour lines. The above (b1) to (b4) will be referred to as contour lines, that is, loop attributes. This attribute has the following procedure (6)-
It can be determined by (8).

(6) Loop numbers are assigned to the contour lines in order from the one located at the upper left.

(7) The attribute of the contour line at the top left is MO-LOOP
And

(8) Focusing on the starting point S3 of the contour line in FIG. 13 in the order of the loop number, search for another contour line to the left of S3. If there is a contour line, the loop number should be smaller than that of the contour line of interest at present, and the attribute of the contour line in relation to inclusion is already determined. The attribute is determined as shown in Table 1 from the type of contour line currently focused and the attribute of the left contour line.

Here, attributes marked with * belong to the object to which the left contour line belongs. The attributes marked with ** are
It shall belong to the left contour line.

Thirdly, the procedure for converting a chain code into run length data will be described according to the present invention.

In the present invention, the procedure of contour line tracking does not use the conventional idea of run length at all, so that it is easy to detect an object having a complicated shape, and from the information of the contour line, data corresponding to run length can be immediately obtained. It can be calculated and obtained. For example, FIG. 14 shows a sequence of points on the traced contour line. In the figure, in the horizontal direction where there is a rectangular frame,
That is, it corresponds to the run length in the X direction.
Reference mark S indicates the starting point of the contour line.

Now, paying attention to arbitrary three points on the contour line, as shown in FIG. 15, let P _i−1 , P ₁ and P _{i + 1} . Assuming that the chain code from the point P _i-1 to the point P ₁ is dir1 and the chain code from the point P ₁ to P _{i + 1} is dir2, as shown in Table 2 from the relationship between dir1 and dir2, The run length roles S, E, T, and X of the point P ₁ are uniquely determined.

FIG. 16 shows an example of such a role on the run length, and the chain code dir of FIGS. 16 (1) to 16 (9).
Table 3 shows 1, dir2 and its role.

Then, next, the XY coordinates of all the pixels forming the contour line are obtained, and the table shown in FIG. 17 is created together with the loop number (that is, marK) and the role (that is, role) on the run length. For example, in FIG. 14, when the points on the contour line are R1 and R2 and the X coordinates are x1 and x2 on the line 40 where the Y coordinate is y, the contour point sequence information in FIG. Corresponding to, the X coordinate and its role
S and E are stored. mark is the information that manages the closed loop, r
ole is information indicating the start and end of the run, and the like.

In the table of FIG. 17, the outline point sequence information is arranged in ascending order, that is, the X coordinate is arranged in order from a small value to a large value to make it easy to use in the calculation described later.

Run length n on line 40 of Y coordinate y in FIG.
Is as in the following third formula.

n = x2-x1 + 1 (3) In this way, the run length n can be easily obtained.
As shown in FIGS. 16 (4), 16 (7) and 16 (8), when the role is T, there is a single pixel in the X direction (left and right direction in FIG. 16). As a result, the run length n is 1. The table of FIG. 17 will be referred to as a run length table (abbreviated as RLT) in the following description.

By using this run length table, for example, on the line 41 having the Y coordinate y as shown in FIG. 18, the contour point sequence information of FIG. 17 has the X coordinates of the four points 42 to 45. Is stored, and its roles S and E are also stored,
In this way, the run lengths na and nb of the contour line 46 of the object can be easily calculated.

Also, for example, as shown in FIG. 19, the contour line of the object
47 and hole outlines 48, 49 exist, and at this time, in the Y-coordinate line 50, points 51 to 56 are stored as the outline point sequence information in FIG. 17, and the roles S and 51 of these points 51 to 56 are stored. E can be stored and the run length nc, nd, ne can be calculated in this way.

The present invention has an excellent advantage that the run length can be easily obtained in the relatively complicated images shown in FIGS. 18 and 19.

Fourth, the procedure for calculating the center of gravity and the posture angle that are the characteristic parameters using the run length table will be described.

Generally, in order to obtain the area and the center of gravity of an object, it is sufficient to count the pixels having a logical value of "1", but the image information must be examined two-dimensionally (planarly). Further, in order to obtain the attitude angle, it is necessary to further calculate the moment of inertia including the calculation of the square of the X coordinate and the Y coordinate, and the time required for this calculation becomes long.

For example, in order to obtain the area of the object shown in FIG. 20, the number of pixels with a value of 1 for each Y coordinate, that is, the line Si (run length shown by the broken line in the figure) is calculated, and all the Si constituting the object are calculated.
However, all binary images will be examined.

However, using the run length table described above, the X coordinates of the two end points of Si can be immediately known. Therefore, the area can be easily obtained.

Similarly, the moments around the origin of the object are
Since ni can be expressed by the following equation, these also
It will be obtained from the information in the run length table.

The first moment (geometric moment) about the Y-axis is The second moment (moment of inertia) about the Y-axis is The first geometrical moment about the X axis is Second moment (moment of inertia) about X axis, The product moment of inertia is However, Is a simplified version of.

When the equations 6 to 10 are calculated, the center of gravity G (gx, g
y) and the attitude angle θ can be calculated as follows.

gx = (value of formula 8) / area ... (11) gy = (value of formula 9) / area ... (12) θ = − (90−θ1) A ≧ 0 B <0 ... (13) θ = −θ1 A ≧ 0 B ≧ 0 (14) θ = θ1 A <0 B ≧ 0 (15) θ = 90−θ1 A <0 B <0 (16) where A = (value of expression 10 )-(Value of expression 8) x (value of expression 6)
/ Area ... (18) B = {(value of the ninth equation)-(value of the seventh equation)} × (1-1 / area) ... (19) tan2.theta.1 = 2A / B ... (20) .

The area is obtained from the above-mentioned fifth formula.

Fifth, the derived feature parameter is calculated based on the basic feature parameter relating to the object and the hole calculated as described above. Basic feature parameters are area, center of gravity, perimeter, moment of inertia, attitude angle, major axis length,
Derived feature parameters such as minor axis length, farthest point, nearest point, etc., such as ratio calculation of moment ratio, area ratio, aspect ratio, etc. of objects, total calculation of object hole area, total perimeter, etc. .

Although in the above-described embodiment the contour tracing was done so that the pixel follows the area of the logical "1" with the left hand, i.e., counterclockwise in the illustrated embodiment, other implementations of the invention. As an example, the contour line may be traced so that the pixel traces the region of logic "1" with the right hand, that is, the trace in the clockwise direction. At this time, in the judgment table of Table 2, the start point is set to E. By replacing the end point with S, the second table can be used as it is. As yet another example, the contour line may be traced so that the pixel traces the area of logic "0" with the left hand or the right hand.

EFFECTS OF THE INVENTION According to the present invention, a contour line is treated as a chain code which is a one-dimensional data string, and the processing time required for individual separation can be shortened.

Further, according to the present invention, the chain code includes a total of eight pixels adjacent to the right, right diagonally upper, upper, left diagonally upper, left, left diagonally lower, lower and diagonally right lower of each pixel forming the contour line. The direction is set to "0" to "7" as shown in FIG. 8, and the determination table is determined in advance, whereby a run length table is created when tracing the contour, and thereafter. Can be calculated by calculating the run length n for each coordinate y in either the X direction or the Y direction (for example, the Y direction) based on this run length table, and the run length can be calculated in a short time. Can be calculated.

[Brief description of drawings]

FIG. 1 is a flow chart showing the procedure of one embodiment of the present invention, FIG. 2 is a block diagram showing the construction of one embodiment of the present invention, and FIG. 3 is a bright object in the dark background for contour line tracing. FIG. 4 is a diagram showing a logical value of a pixel, FIG. 5 is a diagram showing a pixel to be searched, FIG. 6 is a diagram showing a tracking result of an object, and FIG. 7 is a tracking result of a hole. , FIG. 8 is a diagram showing the principle of the chain code, FIG. 9 is a diagram of an operator used to detect the starting point by the hardware configuration, and FIG. 10 is a candidate by the hardware configuration. The figure which shows the binary image which shows the detection of the point, Figure 11 the figure which shows the detection of the candidate point when detecting the starting point with the software,
FIG. 12 is a diagram showing the attributes of the contour line, FIG. 13 is a diagram for explaining the starting point S3 of the contour line, FIG. 14 is a diagram for explaining the point sequence on the contour line, and FIG. 15 is the contour line. Showing the three points and the chain code, FIG. 16 is a view for explaining the role of each point, FIG. 17 is a view showing a contour point sequence table according to the present invention, and FIG. 18 is a contour point sequence information. Figure 19 to explain the
The figure is a diagram for explaining other contour point sequence information, and FIG. 20 is a diagram showing a procedure for calculating the area of an object. 1 ... Image memory, 2 ... Processing circuit, S1, S2 ... Starting point

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Shin Hiramatsu 1-1 Kawasaki-cho, Akashi-shi, Hyogo Prefecture Kawasaki Heavy Industries Ltd. Akashi Plant Co., Ltd. (72) Kazuki Ogura 1-1, Kawasaki-cho, Akashi-shi, Hyogo Kawasaki Heavy Industries Akashi Plant Co., Ltd. (72) Inventor Yoichi Nakamura 1-1 Kawasaki-cho, Akashi-shi, Hyogo Kawasaki Heavy Industries Ltd. Akashi Plant Co., Ltd. (56) Reference JP-A-59-55583 (JP, A) JP-A-1- 277976 (JP, A)

Claims (2)

[Claims] 1. A contour of a binary image represented by a large number of pixels having XY coordinates is traced in one predetermined direction,
The closed loop of the contour line is obtained, and at the time of this tracking, the chain code for each pixel forming the contour line is obtained. This chain code is the right of each pixel forming the contour line,
Consists of a total of eight pixel directions (0 to 7) that are adjacent to diagonally upper right, upper, diagonally upper left, left, diagonally lower left, lower, and diagonally right lower, and configure the contour line when tracing the contour. By combining the first chain code dir1 of the adjacent pixel immediately before reaching each pixel and the second chain code dir2 of the adjacent pixel immediately after moving from the pixel forming the contour line, X
The determination table for determining the start point S and the end point E that are at least two roles on the run length in either the direction Y or the direction Y is determined in advance, and the determination table for either the direction X or the direction Y is determined. For each coordinate y in the direction, a run length table is created by associating each of the roles S and E of the run length with the coordinate x1 of the start point S and the coordinate x2 of the end point E in one of the directions. , Run length n, n = x2-x1 + 1 is calculated. 2. The contour is traced so that the pixel follows the logical value of either logic "1" or logic "0" with the left hand, and the chain code of each pixel forming the contour is adjacent. "0" to the right of the pixel, "1" to the upper right, "2" to the upper, "3" to the upper left, "4" to the left, "5" to the lower left, "6" to the lower, and so on. When setting the diagonally lower right to "7", the judgment table The run length calculation method of an image according to claim 1, wherein the run length is calculated.