JP5192315B2 - Indentation detection method for dividing a binary image into regions - Google Patents

Description

  The present invention relates to a digital image processing technique, and more particularly to a technique for detecting a concave point on a contour line, which is necessary when a binarized region is divided into a plurality of elementary figures.

  With the advancement of video information equipment, technology for processing television and video images with computers is becoming widespread. For example, in the case of video that has been converted into a movie, traditionally the video is simply displayed on the receiver, and the viewer selects the scene visually when trying to extract a scene showing a specific performer from here. There was a need to do. With the spread of digital video processing, it is becoming possible to automatically extract what kind of object or person appears in one frame (hereinafter referred to as “image”) in the video.

  Such a function is usually realized by comparing the shape of an object in an image with a known object, that is, by performing some kind of matching operation. However, in the matching work, it is a precondition that objects are individually photographed one by one. Therefore, it is often necessary to divide a plurality of objects into individual objects before the matching operation. As a typical example, when two pedestrians are shown in an image, objects overlap each other when they pass each other. In this case, it is impossible to detect that the person is a pedestrian (human) unless it is divided into one person.

As a similar technique for automatically performing the above-described division, Patent Document 1 discloses the following invention (hereinafter referred to as “conventional method”). In other words, an image of a human hand is input, a hand outline (edge) is first extracted, and then a point where the direction of the outline changes abruptly ("bending point" in Patent Document 1) is detected. It is. As a result, the boundary between the two fingers is detected as a bending point. Thereby, although not specified in Patent Document 1, an invention is disclosed in which a plurality of fingers are divided from an image of a hand.
Japanese Patent Laid-Open No. 2001-34764 “Moving Image Processing Method, Apparatus, and Medium”

  However, in the above conventional method, it is not clearly stated how much the direction of the contour line should be changed to be a “bending point”. As a result, the figure as shown in FIG. 2 cannot be separated well. FIG. 2 shows a figure in which two circles are overlapped, and the overlap (a) is small and (b) is large. If both are cut by a line connecting points 201 to 202 in the figure, the figure is divided into (a part of) two circles. When the conventional method is applied to this, if the change criterion is set to an angle of 90 degrees, for example, (a) is divided, but (b) is not subject to division, and there are two circles. You will lose sight. Since the angle of the point 201 in FIG. 2 increases as the overlap of the circles increases, it is generally impossible in principle to determine an appropriate determination criterion. For this reason, it is necessary to experimentally set the criterion for determining the bending point according to the application scene, and this method has low versatility.

  An object of the present invention is to solve the above-described problems and provide a dividing method that can be generally applied to a wide range of images. As a core technique for this purpose, a method for detecting a concave point on a contour line without using an empirical criterion is provided. Here, the concave point is literally a depressed point on the contour line, and means a “bent point” in the prior art where the contour line is bent outward. If a concave point can be detected, dividing a figure based on the detected point is a relatively simple task. Therefore, the present invention discloses only the method for detecting the concave point.

  In order to solve the above problem, it is only necessary to be able to define a concave point without using a concept such as an angle. For this reason, the present invention discloses a new definition of the indentation point based on the following geometric property.

First, defining a concave point is equivalent to defining a convex region, which is a complementary concept. Here, the convex region is defined as follows in geometry in the ordinary sense (Euclidean geometry).
“In a single connected region, when a line segment connecting any two points in the region is always inside the region, the region is said to be convex.”
However, this definition assumes that Euclidean geometry, that is, the points exist continuously. The present invention is intended for digital images, where there are only discrete points (pixels). In this case, the concept of inside / outside of the area becomes ambiguous. As a typical example, when an area consisting of five points shown in FIG. 3A is considered, it is not clear whether the line segment 301 in the figure is inside or outside the figure. FIG. 3B shows an example in which a right triangle 303 is drawn in the binary image 302. As long as the pixels are binary and discrete, it is impossible to draw a right triangle any more accurately. However, the hypotenuse in the figure is a jagged broken line when viewed microscopically, and it is difficult to say that it is a straight line. However, since this broken line is a straight line drawn as faithfully as possible, this is actually a straight line, and therefore a right triangle must be defined to be a convex figure.

Therefore, in the present invention, the above definition is converted using the concept of computational geometry. In computational geometry, the concept of “convex hull” is known. As shown in FIG. 4A, the convex hull means a minimum convex figure 410 including a given set of points such as 401-1. This is necessarily a convex polygon when the number of points is finite. If this is used, the above-mentioned definition of the convex region can be rephrased as follows.
“A region is convex if it matches the convex hull defined from that region.”
Here, it is known that the convex hull can be created by the following procedure when the region is composed of a set of finite discrete points. That is, as shown in FIG. 4B, first, a point on the rightmost side of the region (point P0 in FIG. 4B) is obtained. As a result, all points belonging to the region are present on the left side of the line segment 420 in the figure (this property is hereinafter referred to as “left-side rule”). Next, a directed line segment 421 is determined. Here, 421 is a line segment in which the left side rule is established with P0 as the starting point, and the angle formed with 420 (the size of the left turn, the angle a0 in the figure) is minimized. As a result of determining 421 in this way, a point P1 which is the next vertex of the convex hull is obtained. Thereafter, the same procedure is repeated to determine the directed line segment 422 and the vertex P2,. Since the region has a finite size, this repetition ends in a finite number of times, and the end point of the last directed line segment is the first vertex P0. The polygon P0P1P2... Pn-1 obtained as described above is the convex hull of the region.

Since the convex hull is a kind of polygon, the concept of inside / outside can be clearly defined even when points (pixels) exist only discretely. Further, it is clear from the above procedure that there is no point belonging to the region outside the convex hull. As a result, the definition of the convex region can be further rephrased. That is,
“When a point (pixel) that does not belong to the region is not included in a convex hull created from a certain region, the region is called a convex region.”
Based on the above definition, it is possible to determine that a concave point exists. That is, when all or part of a certain area is extracted, if that part matches the definition of the convex area, there is no concave point. For example, as shown in FIG. 1, the region 101 in FIG. 1A is a convex region and there are no concave points, and the region 102 in FIG. 1B is not a convex region, but a point 110 in the figure is a concave point. According to this method, a concave point can be detected without going through the problem of angle setting in the conventional method.

However, it is not efficient to apply the above definition to the indentation detection as it is.
That is, according to the above, first, the convex hull of the region must be obtained by the procedure shown in FIG. For this purpose, it is necessary to find the vertex of the convex hull (there is also a document called “envelope point”), but usually it is not obvious which point (pixel) on the outline is the apex, but tracing the outline It is necessary to search for vertices. When the shape of the region is complicated, in order to obtain the next vertex from one vertex, a search may be made for more than half of the length of the outline, which takes time. Furthermore, even if a convex hull is obtained, it is necessary to trace the outline again or to perform some equivalent process in order to determine whether or not a point outside the region is included inside the convex hull. Yes, processing is duplicated.
In consideration of the above situation, the present invention discloses a method for detecting a concave point without explicitly obtaining the convex hull and following the above-described definition of the convex region.

  The characteristics of the present invention based on the above are as follows. That is, the first feature of the present invention is a method for obtaining a concave point on an outline for an area in a binary image, and whether there is a point outside the area inside the convex hull formed by the area. In the method of determining whether or not there is a concave point by determining whether or not, after expressing the outline of the region by a direction difference code, the sequence of the direction difference codes is converted into two codes whose directions are adjacent to each other. There is a concave point between the step of dividing into a partial series consisting of only (referred to as “two-way series”) and comparing the directions of two adjacent parties to the set of two-way series obtained An adjacent concave point determining step for determining whether or not to perform, and an internal concave point determining step for determining whether or not there is a concave point within each two-way series for the obtained set of two-way series; , To prepare.

  According to a second feature of the present invention, in the concave point detection method having the first feature, the internal concave point determination step converts the two-direction sequence to be determined into a run expression, and then converts two adjacent runs. The difference between the run lengths (referred to as “run pair”) is used as an index of the run pair, and it is determined whether or not there is a concave point based on the change in the index shown on the left.

  According to a third feature of the present invention, in the method for detecting a concave point having the second feature, a section (referred to as a “pseudo-straight line”) in which the change in the previous period index is at most 1 is detected, Is to apply a step for determining the indentation that is different from other sections.

  According to a fourth feature of the present invention, in the method for detecting a concave point having the third feature, the method includes a step of calculating the number of pixels included inside the pseudo line from a series of indices corresponding to the pseudo line, By comparing the number of pixels calculated in the left step with the area of a right triangle whose hypotenuse is the start point and end point of the pseudo-line, it is determined whether or not there is a point outside the region inside the convex hull. There is a thing.

According to a fifth feature of the present invention, in the concave point detection method having the fourth feature, the area of a right triangle having a base length of m and a base length of n is represented by the following formula ((m + 1 ) × (n + 1) −gcd (m, n) −1) ÷ 2 + gcd (m, n) +1
However, gcd (m, n) is calculated by using the greatest common divisor of m and n.
The above mathematical formula is the same as Equation 1 described later.

  According to the present invention, it is possible to realize a region dividing method having higher versatility than the conventional method, and it is possible to contribute to further advancement and higher functionality of image recognition technology and its application devices.

  It is appropriate to implement the present invention as software that runs on a computer. The computer used here may be any computer that can execute a so-called image processing function. As an embodiment, a calculation method of a computer program having the features of the present invention will be described with reference to the drawings.

  FIG. 5 is a flowchart showing an overall image of the algorithm of the indentation detection method according to the present invention. The outline of the algorithm will be described below with reference to the same drawing.

  The indentation detection method according to the present invention is realized by the processing in step 500 (hereinafter abbreviated as “S500” or the like). First, a binary image to be processed is input (S501), and a contour line is extracted from the region to be processed (S502). Here, “area” means a connected set of pixels having a pixel value “1” in the binary image. For example, in FIG. 6A, two areas 601 and 602 are included in the binary image 600. Yes. Here, among the pixels constituting the region, the pixels that are sequentially traced at the boundary portion with the pixels outside the region are referred to as “contour lines” of the region. For example, a contour line can be obtained for the region 601 by tracing the boundary along the arrow “→” in FIG. In the present invention, when tracing the boundary, it is allowed to proceed in an oblique direction in addition to the vertical and horizontal directions (so-called “8-neighbor rule”).

  Next, the shape of the contour line is converted into an expression as a series of “direction difference codes” described below (S503). The direction difference code is an encoded representation of which direction one side is seen from the other when two pixels are adjacent in a binary image. Since the contour line is a series of adjacent pixels, it is often more convenient to indicate in which direction the pixels are arranged than to indicate the position of the pixels in order to express the shape. Therefore, eight types of codes <0>... <7> as shown in FIG. 7A are defined for the eight-direction arrows used in FIG. 6B, and these codes are arranged along the contour line. By arranging them as a series, the shape of the contour line can be expressed. For example, the series of arrows shown in FIG. 6B can be expressed as <01112122232333345555666676777> as shown by 701 in FIG. 7B (enlarged and displayed for convenience of explanation). The eight types of codes <0>... <7> used here are referred to as “direction difference codes”. In this specification, in order to avoid confusion with other codes and numerical values, the direction difference code is described in angle brackets “<>”. In addition, when the contour is a closed curve as shown in FIG. 6, there is arbitraryness depending on where the start position of the code is taken, but this may be appropriately determined according to the convenience of the processing program. In the present invention, the position where the code <0> first appears (position 710 in FIG. 7B) is set as the start position.

  Next, in the present invention, bending over 90 degrees on the contour line is removed (S504). The purpose of this step is to make the contour line smooth to some extent in advance because complicated exception processing occurs in subsequent steps if a bend exceeding 90 degrees exists on the contour line. Specifically, as shown in FIG. 8, there are bends of ± 90 degrees (same figure (a)), ± 135 degrees (same figure (b)), and 180 degrees (same figure (c)) on the contour line. In this case, an operation for removing the pixel causing the bending from the contour line is performed. As a result, the two codes that follow in the direction difference code sequence are limited to either the same or the difference of ± 1, and the subsequent processing can be simplified. As a method for realizing this step, a program that repeats the operation of scanning the direction difference code sequence from the top and rewriting the portion applicable to FIG. 8 according to the illustrated rule may be created.

  The steps described so far are collectively the preprocessing stage 550 in the indentation detection method according to the present invention. These steps may be omitted or simplified as appropriate according to various characteristics of the input image. For example, if it is certain that the input image 600 has already undergone some smoothing processing, S504 can be omitted or simplified. These steps are all well-known techniques in the field of image processing, and detailed explanations (flow charts, etc.) regarding the implementation are omitted.

In the present invention, based on the preprocessing stage 550 described above, an operation for dividing the contour into two-way series is performed as a subsequent step (S505). Here, as described in the first feature of the present invention, the two-way sequence refers to a sequence in which two code values whose directions are adjacent in the direction difference code are paired.
Specifically, a sequence of directional difference codes is obtained as shown in FIG. 9 (b) 910 for the area 900 shown in FIG. 9 (a). ), (12),..., (70).

  By dividing in this way, the global direction of the contour line can be expressed. For example, when the outline of a circle is expressed by a direction difference code, as schematically shown in FIG. 10, the code <1> appears together in the vicinity of the top point of the circle. Similarly, symbols <3>, <5>, and <7> appear together in the vicinity of the rightmost point, the lowermost point, and the leftmost point. Further, the symbols <0>, <2>, <4>, and <6> appear together in the vicinity inclined 45 ° from these. In the middle section, two types of codes appear together. For example, a two-way sequence consisting of <01> is formed between the codes <0> and <1>. By definition, the two-way sequence <01> also includes a section consisting only of preceding and following <0> and <1>. Therefore, the two-way sequence <01> and <12> are sections consisting only of <1>. (Other combinations are also the same). Here, within each two-way series, the directions may appear in reverse order microscopically. For example, in the example of FIG. 9A, the sign <0> appears after the sign <1> at the point 901 in the figure, and when viewed microscopically, the outline looks like a concave shape. . However, as shown in FIG. 3, this is a phenomenon that occurs because the pixels exist discretely, and from this alone, it cannot be determined that this point is a concave point. By using the two-direction series, it is possible to determine the unevenness globally without being caught by such a microscopic problem.

  In order to execute the division work described above, if a program that scans the direction difference code sequence from the front and determines the division point when the third type code appears is created, good. Since these operations are well-known techniques in the character string processing technology, detailed flowcharts are omitted.

  As described above, since the division into the two-way series is completed, the detection of the concave point, which is a feature of the present invention, is performed in and after S506. As the first step, it is determined from S506 to S508 whether or not there is a concave point at the boundary part of the two-way sequence. That is, for example, if <12> appears following the two-way sequence <01>, it is determined that the region is generally convex, and conversely if <70> appears subsequently, the connecting portion between the two Is determined to be a non-convex figure. An example of the latter is shown in FIG. In this example, the directional difference code sequence 1100 shown in FIG. 10A is divided into two two-way sequences 1101 and 1102, that is, <70> appears successively in the two-way sequence <01>. The shape of this contour line is as shown in FIG. 5B, and since the pixels 1111-1 and 111-2 outside the region exist on the local convex hull 1110, it is contrary to the definition of the convex region. In this way, it is determined whether or not the next series is the direction shown in FIG. 10 (this is described as “convex direction”) (S507). By repeating the process of registering as a point (S508) for all the two-way series (S506), the determination as to whether or not the given area is a globally convex area is completed. Here, the registration may be a method of storing in the memory of the image processing device, a method of outputting to the external storage device, or the like, but any method may be used as long as the indentation presence information can be used in subsequent processing. The details are not defined in the present invention. Further, when the connection portion is composed of a large number of pixels, for example, only the intermediate point may be represented.

  In subsequent steps S509 and thereafter, it is determined whether or not there is a concave point in one two-way series. These steps will be described below. In preparation for this, first, what are “run pairs” and “pseudo-straight lines” that are the characteristics of the present invention will be described.

  As already described, in the present invention, a “two-direction sequence”, that is, a sequence in which two code values whose directions are adjacent in a direction difference code is set as a unit of processing. Under this, since there are only two types of codes included in the sequence, the sequence can be expressed using the number of times one code appears successively. That is, as shown in the example of FIG. 12, when the number of consecutive codes <0> and <1> in the two-way sequence 1200 is counted, 1201 is obtained. Accordingly, the expression indicated by 1210 represents this two-way sequence. Can be expressed. Such an expression method is known as “run expression” and is practically used in an image processing apparatus (for example, a FAX apparatus). In this specification, in order to avoid confusion with other codes and numerical values, the run expression is enclosed in “”.

  The “run pair” refers to a set of two adjacent runs in the above “run expression”. That is, as shown in FIG. 13, a run with a code <0> and a run with <1> are considered in pairs from the end. In this way, the following advantages can be obtained. First, it is assumed that the contour line to be processed is sufficiently smooth and has a straight line or a shape close to a straight line. FIG. 13 shows such an example. (A) shows a straight line 1310 connecting points 1311 and 1312 in the figure, (b) shows a straight line 1320 connecting points 1311 and 1322 in the figure, (c ) Is an approximate expression of a sufficiently smooth curve (part of an ellipse) 1330 on each binary image. In the case of (a), the slope of the straight line 1310 is 13/21, and this value is smaller than 2/3 and larger than 1/2. Therefore, on the binary image, the straight line 1310 is approximated by a combination of an element side 1301 having an inclination of 2/3 and an element side 1302 having an inclination of 1/2. As represented by this example, in general, a straight line having a slope of ½ or more has a slope of n / (n + 1) and a slope (n−1) unless the slope is exactly n / (n + 1). It is approximated by a combination with / n. In the above, n represents an appropriate positive integer. When the slope of the straight line is ½ or less, as shown in FIG. 13B, the straight line is approximated by a combination of a bare edge with a slope 1 / n and a bare edge with a slope 1 / (n + 1). When the contour curve bends smoothly, it is considered that (a) and (b) in the figure are smoothly connected as illustrated in FIG.

The element sides 1301, 1302, etc. in FIG. 13 are a kind of “run pairs”. However, if the contour line is sufficiently smooth as shown in the figure, each element side has the following properties. It can be confirmed from the example in the figure.
Properties: At least one of the two runs has a run length of 1.
Therefore, if it is assumed that the contour line is smooth, it is not necessary to store both of the run lengths when storing the “run pair”, and the difference between the two may be stored instead. That is, if the two run lengths constituting a certain run pair are m and n (denoted as “run pair (m, n)”), only the value (mn) needs to be stored. Here, the value (mn) is hereinafter referred to as the “index” of the run pair. In FIG. 13, in each of the examples (a), (b), and (c), the run representations indicated by 1316, 1326, and 1336 are obtained for the two-way series indicated by 1315, 1325, and 1335, and from these, 1317, A series of indices indicated by 1327 and 1337 is obtained. In this specification, in order to avoid confusion with other codes and numerical values, the index is enclosed in brackets [].

  When the index is used, the slopes of the elementary sides in FIG. 13 can be arranged as shown in Table 1 above. Also, as shown in the table, increasing or decreasing the index is equivalent to increasing or decreasing the slope of the bare edge. Using these properties, it is possible to detect the indentation as follows. First, as shown in Table 1, an increase / decrease in the index is equivalent to an increase / decrease in the edge of the bare edge. Since there is a change in the convex direction), there is no concave point in that part. When the index increases by +1, there is a possibility of a “pseudo line” to be described later, and it cannot be determined that a concave point exists. However, when the index increases by +2 or more, a concave point exists at a portion where two run pairs are connected. Such an example is shown in FIG. In the example of FIG. 14, an index series 1417 is obtained via a run expression 1416 after obtaining a two-way series 1415 for the outline indicated by a black circle. Although illustration is omitted, it is assumed that the lower side of the figure is the inside of the region. Here, the index increases from 1 to 3 by +2 when proceeding from the second run pair to the third. In this case, the line segment 1400 in the figure is a local convex hull, and the pixel 1410 indicated by an arrow exists inside (including on the line segment), so that it can be determined that this region is not convex. Here, even if the index is another value (for example, increase from 2 to 4), only the both ends of the line segment 1400 move symmetrically, and the property that the pixel 1410 becomes the midpoint of the line segment 1400 is changed. There is no. Further, when the amount of increase in the index is larger (for example, +3), the slope of the line segment 1400 becomes larger than that in the figure, so that the pixel 1410 enters the convex hull. From the above, if there is an increase of +2 or more at any value of the index, it can be determined that the region is not convex. In this embodiment, this property is used to detect the concave point in S514 in FIG. Note that this determination method is excluded and applied when one of the run pairs is at the start or end of the two-way sequence because the line segment 1400 in the figure cannot be drawn. In an actual contour line, both m and n in the run pair (m, n) may be larger than 1. However, in such a run pair, the connection point of the two runs becomes a clear convex point, and even if the contour line is divided into front and back at this point, there is no problem in detecting the concave point. Does not occur. In this case, the run pair (m, n) may be treated as a run pair (m, 1) in the first half of the division and a run pair (1, n) in the second half.

  Next, the “pseudo line” will be described. As shown in FIG. 13, on the binary image, a straight line is represented by two types of run pairs, and their indices differ by one. Conversely, a section in which “two types of run pairs whose indices differ by ± 1” after the two-way sequence is expressed by a run pair index is referred to as a “pseudo line” in the present invention. The pseudo straight line is a necessary condition indicating the possibility that the section is a straight line. Further, the run pair index changes by 2 or more in a section that is not a quasi-straight line, and it is possible to detect a concave point by the method described above.

  As described above, the concepts of “run pair” and “pseudo line” can be defined. By using these, the processing after S509 can be configured as described below. That is, if the processing from S510 to S519 is applied to all the two-way sequences (S509), the division processing is performed based on the registered concave points (S520), and the execution is completed (S521). good. Here, S510 to S519 are configured as follows.

  First, the two-way sequence is converted into the above-described run pair expression (S510), and the analysis start point is set as the start point of the run pair expression (S511). The above two steps are preparation steps for detecting a concave point using the run pair expression. The index will be obtained at the same time as the run pair. Below this, the shape of the outline behind the analysis start point is analyzed in the following steps. That is, first, in S512, a section where the run pair starting from the analysis start point is sufficiently convex is obtained. Specifically, the indices of subsequent run pairs are sequentially compared, and the point where the index first increases is set as the end point of the section. It is determined whether or not the obtained section has reached the end point of the two-way sequence (S513). If the result is yes, that is, the end point has been reached, there are no more concave points in the two-way sequence. Then, the process loops to S509 to start the analysis of the next two-way series. If the result is no, each index is compared with the last run pair of the convex section and the next run pair (S514). When the index is increased by 2 or more, there is a concave point as described with reference to FIG. 14, and therefore the connection portion with the next run pair is registered as a concave point (S515). Since the detection process up to the next run pair is completed as described above, in order to continue further detection, the analysis start point is set as the start point of the next run pair (S516), and S512 and subsequent steps may be repeated again. In the above description, the registration in S515 may be performed in the same manner as in S508.

  On the other hand, if the index has increased by only +1 in S514, this portion may be the above-mentioned “pseudo line”, and it cannot be easily determined whether or not there is a concave point. Therefore, in such a case, first, a pseudo-linear section including the last run pair of the sections obtained in S512 is obtained (S517), and the unevenness of the pseudo-linear section is determined (S518). Thereafter, it is determined whether or not the quasi-linear section has reached the end point of the two-way sequence (S519). If the result is yes, that is, the end point is reached, the same two-way sequence is looped to S509 as in S513. Start analyzing. If the result is no, in order to continue further detection, S512 and subsequent steps are repeated again through S516 in the same manner as in S515.

Here, the process for the suspicious line, that is, S517 and S518 will be described. First, in S517, a section constituting a suspicion line is obtained from the two-way series. Since the run pair expression has already been created in S510 and its index is obtained, the index value is +0 or 0 relative to the current value in S517. What is necessary is just to obtain | require the area which becomes +1. For example, a series of metrics
[-2-1-2-2-2-1-2-2-1-2-3-2-4-4] (the first -2 is the analysis start point)
If it is obtained, a section in which -2 or -1 continues from the head is obtained. In the case of the above example, the index that is neither -2 nor -1 appears first at -3.
[-2-1-2-2-1-1-2-2-1-2]
However, it becomes the section which comprises a suspicion line. This process is a process for extracting a partial sequence satisfying a specific condition from a numerical sequence, and since it can be realized by a known technique, its details are omitted.

Next, in S518, the unevenness of the section obtained above is determined.
In this determination, a convex hull may be created by the method shown in FIG. 4, but it is not efficient as described above. Moreover, in practical use, the pseudo straight line is actually a straight line or a shape sufficiently close to the straight line in most cases. Therefore, in this embodiment, a method for determining irregularities at high speed, although approximate to the quasi-straight line, will be disclosed with reference to FIG.

  FIG. 15 shows an example of a quasi-straight line. The corresponding two-way series, run expression, and index series are as shown in 1515, 1516, and 1517, respectively. That is, this pseudo straight line is composed of two types of run pairs whose indices are -2 and -1, and the specific shape is as shown in the figure. Here, paying attention to the first and last run pairs of the pseudo-line, the pixels 1501 and 1502 in both are microscopically apexes of the contour line. This suggests that a line segment 1500 connecting the two points may be a local convex hull of the contour line. Therefore, when the segment 1500 is regarded as a temporary convex hull, if a point outside the region is included in this interior (the lower part is the interior), it is concluded that the part having the pseudo-line as the contour line is not convex. To do. As a sufficient condition for this, by comparing the number of pixels below the line segment 1500 with the number of pixels in the region and included in the rectangle 1505 in the figure, it can be concluded that the latter is not convex if the latter is smaller. Here, the above two types of pixel numbers can be calculated by the following methods.

First, the number of pixels included in a rectangle 1505 in the region can be calculated by the method shown in FIG. That is, first, a “reference pseudoline” for the pseudoline is assumed. The reference pseudo-line is a pseudo-line having the same index value as that of the pseudo-line, and the index having the larger value is concentrated in the first half of the series. For example, since -1 appears 4 times and -2 appears 6 times in the pseudo-line index of FIG. 15, they are arranged in this order. [1-1-1-1-2-2-2-2-2-2 2]
The pseudo line having the index series 1617 is the reference pseudo line. Corresponding two-way sequences and run representations are 1615 and 1616, respectively. In the figure, the pixels constituting the reference pseudo line are shown as squares. Here, the area under the reference pseudo-line can be calculated primarily as shown in FIG. That is, when the rectangle r in FIG. 15 is divided into three rectangles 1601, 1602, 1603 in FIG.
Lower area at 1601 = (i1 + 2) × (k1 × (k1 + 1) ÷ 2)
Lower area at 1602 = (i2 + 2) × (k2 × (k2-1) / 2) + k2
Lower area at 1603 = k1 × ((i2 + 2) × (k2-1) +1)
Where i1 = the absolute value of the index with the larger value,
k1 = number of occurrences of the index with the larger value,
i2 = the absolute value of the index having the smaller value,
Since k2 = the number of appearances with the smaller value of the indices, these three values may be summed. Thereafter, the area below the pseudo line is calculated based on the total value. For this purpose, the principle of FIG. 16B is used. FIG. 16B illustrates how the area below changes when the order in which the indices appear on the pseudo line changes. In the example shown in the figure, the quasi-linear index changes from [-1-2-2] shown in 1620 to [-1-2-1] shown in 1630. As a result, the pixel 1611 through which the original pseudo-line has passed is excluded above the straight line, and the pseudo-line passes through the pixel 1612. In other parts, the shape of the quasi-straight line does not change, so the area is reduced by one pixel by the pixel 1611 after all. If this principle is used, the area is reduced compared to the reference pseudo-line by summing up how much of the index in the pseudo-line appears after the reference pseudo-line. Can be calculated. For example, in the example shown in FIG. 15 and FIG.
Reference pseudo-line index 1617: [-1-1-1-1-2-2-2-2-2-2]
Pseudo-line index 1517: [-2-1-2-2-1-1-2-2-1-2]
Because
4th [-1] appearance position: 4th → 9th, area reduction = 5 pixels 3rd [-1] appearance position: 3rd → 6th, area reduction = 3 pixels 2nd [-1] appearance position: 2nd → 5th, area reduction = 3 pixels First [-1] appearance position: 1st → 2nd, area reduction = 1 pixel, 12 pixels in total Since it can be calculated that the area is reduced, it is sufficient to subtract 12 pixels from the area below the reference pseudo-line. In the above description, the case where the index value is negative or zero has been described as an example. However, when the value is positive or zero, the same calculation may be performed by rotating FIGS. 15 and 16 by 90 degrees.

但しｇｃｄ（ｍ，ｎ）はｍとｎとの最大公約数を表すNext, the number of pixels below the line segment 1500 can be calculated by the method shown in FIG. That is, when two pixels 1701 and 1702 are given as candidates for the vertex of the convex hull, the number of pixels below the line segment 1705 connecting them (including the line segment) is obtained. Here, 1702 is assumed to be separated from 1701 by m pixels in the horizontal direction and n pixels in the vertical direction. First, the case where m and n are relatively prime is shown in FIG. There are a total of (m + 1) × (n + 1) pixels in the figure. If two of 1701 and 1702 are excluded, there is no pixel on the line segment 1705, and they are symmetrically divided into two by the line segment 1705. Therefore, the number of pixels to be obtained can be obtained by halving the total number of pixels minus 2 and adding 2 pixels again. If the above is expressed by a formula,
((M + 1) × (n + 1) −2) ÷ 2 + 2 = (m + 1) × (n + 1) ÷ 2 + 1
Is the number of pixels desired. In general, m and n are not necessarily prime, but even in this case, the above idea can be extended to calculate the number of pixels. That is, as shown in FIG. 6B, in this case, the pixels 1720-1, 1720-2,... May exist on the line segment 1715. A similar calculation holds. Therefore, the problem comes down to the number of pixels in total on the line segment 1715. From the consideration of elementary number theory, this number is the greatest common divisor of m and n + 1 (however, the pixels 1711 at both ends, 1712 included)
It can be confirmed that Therefore, the equation to be obtained is as shown in Equation 1 below. As a matter of course, FIG. 11A is nothing but gcd (m, n) = 1 in FIG.

Where gcd (m, n) represents the greatest common divisor of m and n

  As described above, the processing shown in the flowchart of FIG. 18 can be realized as an approximate but fast determination method in S518. That is, assuming that the pseudo-line is given by the index series (S1801), first, the area below the pseudo-line is obtained by the method shown in FIG. 16 (S1802), and then the convex hull candidate is obtained by the method shown in FIG. The area inside is determined (S1803). The two are compared (S1804). If the former is smaller, the pseudo line is registered as a concave point (S1805), and the process is terminated (S1806). In the above, the registration in S1805 may be performed in the same way as in S508. If the section of the quasi-straight line is long, a concave point may be represented by the midpoint.

  As described above, steps up to S519 in FIG. 5 can be performed, so that it is possible to divide the region using the concave points obtained by them (S520). This application method can be considered in various ways. For example, an application of detecting a rising point of the nose by inputting a human profile is conceivable. This indicates that a function for automatically detecting a human profile from an image that has been difficult in the past can be realized by using the present invention.

  In the description so far, the case where the outline is indicated by the direction difference codes <0> and <1> has been mainly described, but other directions can be obtained by appropriately rotating or mirroring the coordinates. Needless to say, the present invention can also be applied to this case.

  As described above, the method for detecting the concave point from the outline of the region has been disclosed. In these descriptions, the region in which the contour line is basically composed of the convex section and the concave point exists only at the connection portion of the convex section is the processing target. In general, however, there are also areas where the contours essentially form concave figures. For example, in the “crescent shape”, the outer contour line is a convex figure, but the inner contour line is entirely a concave figure, and it is not rational to make only a specific point therein a concave point. How to handle such a figure is out of the subject of the present invention, and it is left to the higher-level image processing function. In addition, it can confirm that a contour line is a concave figure by the same calculation method as this invention by switching the outer side and inner side of an area | region. If this is utilized, for example, a processing method such as separating the concave figure portion on the contour line in advance can be considered as a higher-level image processing function. Therefore, the present invention leaves the possibility of application to general areas including concave figures.

  The present invention can be used in various video processing apparatuses to which image recognition technology is applied, and more specifically, application to video monitoring apparatuses, video editing apparatuses, digital cameras, and the like can be expected.

  The figure explaining the definition of the convex area | region used by this invention (binary image)   Schematic diagram explaining the problem of detecting concave points by the conventional method   The figure explaining the subject when a pixel exists discretely   Diagram explaining the definition of convex hull by computational geometry and how to create it   The flowchart which shows the whole structure of the recessed point detection method by this invention.   The figure explaining the area | region and its outline in a binary image   The figure explaining the definition and usage example of the direction difference code   The figure explaining the removal method of the bending in S504   The figure explaining the method of dividing | segmenting a direction difference code | cord | chord into a 2 direction series.   Schematic diagram explaining the behavior of a two-way sequence in a smooth convex figure   The figure explaining the basis of the uneven | corrugated determination in S507   A diagram for explaining a method of converting a two-way sequence into a run representation   Diagram explaining how to obtain run pairs and their indices from run representation   The figure explaining the basis of the uneven | corrugated determination in S514   Diagram explaining an example of a pseudo-line   The figure explaining the example of a reference pseudo-line and the area calculation method using it   The figure explaining the basis of Numerical formula 1 for calculating the area under a straight line   The flowchart which shows the approximate unevenness | corrugation determination method of the quasi-line in S518

Explanation of symbols

550 ... Pre-processing stage 1201 ... Run length 1705, 1715 ... Line segments that are candidates for the convex hull

Claims (5)

  A method for obtaining a concave point on an outline for a region in a binary image, wherein the concave point is determined by determining whether or not a point outside the region exists inside a convex hull formed by the region. In the method for determining whether or not there exists, after expressing the outline of the region by a direction difference code, the above-described sequence of direction difference codes is converted into a partial sequence consisting of only two codes whose directions are adjacent (hereinafter referred to as “two directions”). An adjacent recess that determines whether or not there is a recess point between them by comparing the two adjacent directions to the set of two-way sequences obtained A concave point characterized by comprising: a point determining step; and an internal concave point determining step for determining whether or not there is a concave point inside each two-way series with respect to the obtained set of two-way series. Point detection method.   2. The indentation point detection method according to claim 1, wherein the internal indentation point determination step is performed on two adjacent runs (hereinafter referred to as “run pairs”) after converting the two-way sequence to be determined into a run expression. And determining whether or not a concave point exists based on a change in the left index, using the difference between the run lengths as an index of the run pair.   3. The indentation detection method according to claim 2, wherein an interval in which the change in the index of the previous term is only 1 at most (hereinafter referred to as “pseudo line”) is detected, and an indentation determination different from other intervals is performed for the interval. A method for detecting a concave point, characterized by applying a step.   4. The method of detecting a concave point according to claim 3, further comprising: calculating a number of pixels included inside the pseudo line from a series of indices corresponding to the pseudo line, and calculating the number of pixels calculated in the left step A method for detecting a concave point, characterized in that it is determined whether or not there is a point outside the region inside the convex hull by comparing it with the area of a right triangle whose hypotenuse is the starting point and the ending point of a pseudo line. 5. The concave point detection method according to claim 4, wherein the area of a right triangle having a base length of m and a base length of n is expressed by the following formula ((m + 1) × (n + 1) −gcd (m, n ) -1) ÷ 2 + gcd (m, n) +1
However, the gcd (m, n) is calculated by using the greatest common divisor of m and n.

Images