JP4624487B2 - Image outline extraction processing method and outline extraction processing apparatus - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a contour line extraction processing method for extracting a contour line from an image, and in particular, a contour line extraction processing method suitable for extracting a contour line representing a boundary between a main object such as a person in a processed image and a background, and The present invention relates to a contour line extraction processing device.
[0002]
[Prior art]
When a main object such as a person as a subject is cut out from an image to be processed such as a photographic image, it is divided into an image area of the main object and an image area of the background, so that an outline representing the boundary between the main object and the background It is necessary to extract a line from the image to be processed. In such a contour line extraction operation, it is sufficient if one contour line can be accurately extracted for the main object.
[0003]
[Problems to be solved by the invention]
However, when the above contour line extraction operation is performed manually, that is, when the operator performs tracing with a pointing device such as a mouse while looking at the image displayed on the display or the like, the burden on the operator is high and There arises a disadvantage that uniform processing cannot be performed due to a difference in skills. On the other hand, various processing methods for automating the contour line extraction operation are known. However, a large number of contour lines that are not necessary for the general method are extracted, or a continuous contour line cannot be obtained and post-processing is performed. It is hard to say that it is easy to use.
[0004]
The present invention has been devised to solve such problems of the prior art, and its main purpose is to automate the contour line extraction operation in order to reduce the work burden on the operator. It is possible to extract an appropriate contour line by performing processing suitable for extracting the contour line that represents the boundary between the object and the background, and to shorten the processing time by increasing the efficiency of the processing procedure. Another object of the present invention is to provide a contour line extraction processing method and a contour line extraction processing apparatus.
[0005]
[Means for Solving the Problems]
In order to achieve such an object, in the present invention, as described in claim 1, in a contour line extraction processing method for extracting a contour line representing a boundary between a main object in a processed image and its background, Divide the image to be processed into a grid, and from the multiple cells obtained by this, A cell including pixels having edge strength exceeding a predetermined threshold is extracted as an edge cell, and a continuous area in which the edge cells are gathered together is created, and a plurality of continuous areas are created in the image area of the main object. In this case, the number of divisions into the cells of the image to be processed is reduced to one continuous area, and the continuous area Extract the cells located on the outer periphery of as contour cells, After searching for the connection point that is the passing point of the contour line on the boundary line of the contour cell and the non-contour cell in the vicinity, connect the connection points to each other. The contour line was extracted. According to this, since the contour line is extracted using the contour cell as a guideline, the contour line extraction process can be made more efficient. In the case of extracting a contour line in pixel units, “points” shown below correspond to pixels, and “line” represents a continuous pixel row under a predetermined condition (for example, eight adjacent conditions). A “cell” is a collection of pixels partitioned into rectangles, and a “region” represents a collection of cells or pixels. It is desirable that the cells have a substantially square shape with substantially the same number of vertical and horizontal pixels.
[0006]
Also, After searching for the connection points that are the passing points of the contour line on the cell dividing line, the contour line is extracted so as to connect the connection points to each other. So The rough position of the contour line is specified, and the contour line extraction process can be made more efficient. In this case, a connection point may be required in addition to the boundary line between the contour cells and the boundary line between the contour cell and the non-contour cell adjacent thereto, and the boundary between the non-contour cells as necessary. Although it is preferable to add a line to the search target, it is desirable to limit the non-contour cell to be searched to a predetermined neighboring position in order to avoid that the contour line greatly deviates from the contour cell.
[0007]
Also, When extracting a contour cell, a cell including a pixel having an edge intensity exceeding a predetermined threshold is extracted as an edge cell, and a continuous region in which the edge cells are continuous with each other is created, and is positioned on the outer periphery of the continuous region. Cell to be extracted as a contour cell So Contour cells that are substantially continuous along the contour line can be obtained, and the contour line extraction process based on the contour cell becomes efficient. In this case, if the image to be processed is color for detection of edge strength, it is preferable to perform processing after conversion to a monochrome grayscale image based on the luminance level or the like. Note that a constant value may be used as the threshold value of the edge strength, but it may be appropriately set to an appropriate value according to the image to be processed.
[0008]
Also, The number of divisions of the processed image into cells Less To consolidate continuous areas into one So A continuous region of edge cells is formed so as to entirely surround the image area of the main object, and an appropriate cell through which a contour line passes can be reliably extracted as a contour cell. For example, when the main object is unique in the image to be processed, such as a human face photograph, a single continuous region is created in the image to be processed.
[0009]
In the contour line extraction processing method, Claim 2 As shown in the above, when creating a continuous area of edge cells, if the image to be processed is a portrait of a person, the cells lined up directly below each of the edge cells at the top left and top right corners, and the bottom of them. A configuration can be adopted in which a continuous region is created with all cells between the left and right bottom cells positioned as edge cells. According to this, since a contour cell suitable for a human face photograph is extracted, the contour line extraction process can be performed efficiently. In a person's face photo, the upper body of the person as the main object is cut off at the left and right and lower edges, so that it is possible to avoid unnecessary contour extraction processing by uniformly using this as an edge cell. .
[0010]
In the contour line extraction processing method, Claim 3 As shown in Fig. 4, when searching for a connection point, a contour cell and a non-contour cell in a region closed by the contour cell are searched, and the boundary line of these cells is directed to the inside of the closed region by the contour cell. The structure to search can be taken. According to this, it is possible to improve the efficiency of the connection point search process by excluding the outside of the closed region due to the contour cell that is unlikely to pass the contour line and giving priority to the portion where the connection point is highly likely to exist. .
[0011]
In the contour line extraction processing method, Claim 4 As shown in FIG. 5, when searching for connection points, it is possible to adopt a configuration in which connection points are searched for in different cases based on the relative positional relationship between a pair of adjacent contour cells according to a predetermined arrangement. According to this, the efficiency of the connection point search process can be improved. In this case, the arrangement of the contour cells may be set in the order in which cells located on the outer periphery of the continuous region are extracted as contour cells by, for example, clockwise search.
[0012]
In the contour line extraction processing method, Claim 5 As shown in the above, when a pair of adjacent contour cells are arranged in either the top and bottom or left and right directions, search on the boundary line between the pair of contour cells, and if the connection point cannot be extracted with this, A configuration can be adopted in which a search is made on a boundary line with a non-contour cell that is in contact with each contour cell. According to this, it is possible to improve the efficiency of the connection point search process by giving priority to the portion where the connection point is highly likely to exist.
[0013]
In the contour line extraction processing method, Claim 6 As shown in Fig. 2, when a pair of adjacent contour cells are arranged in an oblique direction, a search is made on the boundary line with a non-contour cell that touches both of the pair of contour cells, and if a connection point cannot be extracted with this, It is possible to adopt a configuration in which a search is made on a boundary line with a non-contour cell that is in contact with only one of the contour cells. According to this, it is possible to improve the efficiency of the connection point search process by giving priority to the portion where the connection point is highly likely to exist.
[0014]
In the contour line extraction processing method, Claim 7 As shown in Fig. 5, when extracting the contour line, it is possible to sequentially search for the contour points constituting the contour line by using the nearest connection point according to a predetermined arrangement from the connection point as the start point as a target point. it can. According to this, one contour line can be obtained by connecting the nearest connection points sequentially with the contour points, and the contour line extraction process can be performed efficiently. In this case, a point that satisfies a predetermined condition as a contour point, for example, a point having an edge strength exceeding a predetermined threshold may be extracted from the adjacent points to be a contour point. The array of connection points may be set in the order of extraction according to the array of contour cells.
[0015]
In the contour line extraction processing method, Claim 8 As shown in, when the contour points are searched sequentially from the start point to the target point, if the total number of extracted points exceeds the predetermined value (maximum allowable value), the search is stopped at that stage, It is possible to adopt a configuration in which all points extracted in (1) are rejected and points on the line segment connecting the start point and the target point are used as contour points. According to this, the stray in the contour point search can be avoided by limiting the number of contour points. In this case, the maximum allowable value of the number of contour points may be set based on the distance between the start point and the target point.
[0016]
In the contour line extraction processing method, Claim 9 As shown in the above, when the contour points are sequentially searched from the start point to the target point, if the distance from the newly extracted point to the target point is less than a predetermined value (minimum distance), the search is performed at that stage. It is possible to adopt a configuration in which a point on the line segment that ends and connects the last extracted point and the target point is a contour point. According to this, the stray in the vicinity of the target connection point can be avoided.
[0017]
In the contour line extraction processing method, Claim 10 As shown in Fig. 3, when searching for contour points sequentially from the start point to the target point, if already extracted points are extracted and overlapped, the search is stopped at that stage, and the double extracted points are It is possible to adopt a configuration in which all points extracted after extraction are rejected, and the points on the line segment connecting the double extracted points and the target points are contour points. According to this, it is possible to avoid a stray caused by extracting useless contour points. In this case, it is not necessary to determine whether or not double extraction has been performed for all of the already extracted points, and the range of already extracted points to be retrospectively matched is limited to a predetermined number of points in order to improve the efficiency of processing. It is desirable. The number of already extracted points to be collated may be determined according to the distance between the start point and the target point, for example.
[0018]
In the contour line extraction processing method, Claim 11 As shown in the above, when the contour points are sequentially searched from the start point toward the target point, when the number of times of continuous retreat with respect to the target point reaches a predetermined value (retraction limit number), the search is performed at that stage. Stop and reject all points extracted after the point where the reverse starts, and take the point on the line segment connecting the point extracted just before starting the reverse and the target point as the contour point Can do. According to this, it is possible to avoid straying far away from the target point. In this case, the backward limit frequency may be set based on the distance between the start point and the target point. Here, retreating with respect to the target point means that the distance to the target point is increased.
[0019]
In the contour line extraction processing method, Claim 12 As shown in the above, when searching for contour points sequentially from the start point to the target point, if the next point cannot be extracted, that is, a point that satisfies a predetermined condition in the neighboring points around the current point If there is no point, a point closest to the target point among neighboring points around the current point can be used as a contour point. According to this, it is possible to avoid interruption of the contour point search process.
[0020]
In the contour line extraction processing method, as shown in claim 13, the contour line Extract the next point from the remaining points excluding the previous point and the points on both sides of the neighboring points around the current point And According to this, by suppressing the bending angle of the contour line to 90 degrees or less, it is possible to prevent the contour line from bending at a steep angle and proceeding in a wrong direction greatly deviating from the target point. Here, the eight adjacent points refer to points that are in contact with the current point side by side in any of the vertical, horizontal, and diagonal directions. Further, the points on both sides in contact with the point immediately before being excluded from the search target refer to the four adjacent conditions, that is, the points in contact with the immediately preceding point side by side in either the vertical or horizontal direction.
[0021]
In the contour line extraction processing method, as shown in claim 14, the contour line In order to sequentially search the contour points constituting the, a predetermined number of points arranged in the direction of each adjacent point around the current point are searched simultaneously with the adjacent points to extract the next point. According to this, by increasing the number of points to be searched at the same time, it is possible to avoid the contour line from moving in the wrong direction by falling into a small break.
[0022]
In the present invention, Claim 15 In the contour line extraction processing device that extracts a contour line representing the boundary between the main object in the image to be processed and its background, as shown in Fig. 3, a plurality of cells obtained by dividing the image to be processed in a grid pattern An edge cell extraction unit that extracts cells including pixels having edge strength exceeding a predetermined threshold as edge cells, and a continuous region in which edge cells are gathered together To determine whether or not the continuous area is unique in the image area of the main object, and if not, combine the continuous areas into one by reducing the number of divisions of the processed image into cells. Continuous area creation part and continuous area A contour cell extraction unit that extracts a cell located on the outer periphery of the contour cell as a contour cell, and a connection point search unit that searches for a connection point that is a passing point of the contour line on the boundary line of the contour cell and the neighboring non-contour cell; An outline point search unit that sequentially searches for outline points constituting the outline so as to connect the connection points to each other. According to this, it is possible to increase the efficiency of the contour line extraction process.
[0024]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, the configuration of the present invention will be described in detail with reference to the accompanying drawings.
[0025]
FIG. 1 shows a schematic configuration of an outline extraction processing apparatus to which the present invention is applied. This apparatus includes an image input unit 1 having an external storage device, an edge strength detection data creation unit 2, an edge strength threshold setting unit 3, an edge cell extraction unit 4, a continuous region creation unit 5, and a contour cell extraction. Unit 6, connection point search unit 7, contour point search unit 8, facial photograph processing unit 9, extracted contour line output unit 10, extracted contour line editing unit 11, target image memory 12 a, edge strength The image memory 12 includes a detection memory 12b and an edge strength memory 12c, a calculation memory 13, and a controller 14 that controls the operation of each part. Contour line extraction performed by these parts. The program is composed of an image processing engine operating on a predetermined OS and an outline extraction library. The obtained contour line can be output to a display or the like by the extracted contour line output unit 10 and can be edited by the extracted contour line editing unit 11 via an input device such as a keyboard or a mouse.
[0026]
As shown in FIG. 2 (A), this apparatus extracts a contour line representing the boundary between the main object in the image to be processed and its background. First, as shown in FIG. 2 (B). The image to be processed is divided into a grid pattern, and a cell located on the outer periphery of the image area of the main object is extracted as a contour cell from the plurality of cells obtained thereby. Then, a connection point serving as a passing point of the contour line is searched on a boundary line related to the contour cell and the non-contour cell in the vicinity thereof, and the contour line is extracted so as to connect the connection points obtained thereby. Here, for convenience of drawing, the main object is shown as a line drawing, but only gray scales actually appear.
[0027]
When extracting contour cells from the image to be processed, as shown in FIG. 3, a cell including pixels having edge strength exceeding a predetermined threshold is extracted as an edge cell, and the edge cells are gathered in a continuous state. After creating an area, a cell located on the outer periphery of the continuous area is extracted as a contour cell. These processes are performed by the edge cell extraction unit 4 and the contour cell extraction unit 6 shown in FIG.
[0028]
Here, when creating a continuous region of edge cells, a single continuous region is created in the image area of the main object so that an appropriate contour cell is extracted. When a plurality of continuous regions of edge cells are created in the image region of the main object, the plurality of continuous regions are integrated into one by changing the number of divisions of the image to be processed into cells. As a result, continuous contour cells surrounding the image area of the main object can be extracted. Usually, when the number of divisions is large, that is, the cells are small, the contour line can be easily extracted, but a plurality of edge cell continuous regions are likely to be generated. For this reason, it is preferable to reduce the number of divisions gradually from the condition that the number of divisions is increased so that the continuous region is unique. For example, as shown in FIG. 4, when the continuous area of edge cells is not unique, the number of divisions is reduced and the process is repeated. The continuous area creating process is performed by the continuous area creating unit 5 shown in FIG.
[0029]
The determination of continuity between edge cells is performed under eight adjacent conditions arranged in the up / down / left / right and diagonal directions. Whether or not the continuous area is unique may be determined by the number of label numbers generated in the image area of the main object after labeling in units of cells. Specifically, first, a number 1 is assigned to edge cells that are continuous under 8 adjacent conditions. Next, the same number is assigned to the non-edge cells that are continuous under the four adjacent conditions of only the top, bottom, left and right. Then, the non-edge cells in the non-edge cell area in contact with the outer periphery are renumbered to 0. Further, the same number as the edge cell is assigned to the non-edge cell surrounded by the edge cell. Thus, if the continuous area of the edge cell is unique, the generated label numbers are only 0 and 1. When labeling is performed in the example shown in FIG. 4, three numbers 1, 2, and 3 are generated in the edge cell, and it can be seen that the continuous region is not unique.
[0030]
Further, when creating a continuous region of edge cells, if the image to be processed is a human face photo, special processing is performed by the face photo processing unit 9 shown in FIG. That is, as shown in FIG. 3, a continuous region is created with all the cells arranged directly below each of the edge cells at the upper left end and the upper right end, and the cells between the lower left and right cells positioned at the bottom of the cells, as edge cells. In this case, the upper left edge and upper right edge cells may be set by searching the left edge and right edge cells of the image from the upper edge.
[0031]
This special face photograph processing will be described with another example. When the edge cells at the upper left corner and the upper right corner are at the left and right edges of the image to be processed as shown in FIG. The non-edge cells included in the cell row along the edge are replaced with edge cells. On the other hand, as shown in FIG. 5B, when the edge cells at the upper left corner and the upper right edge are not at the left and right edges of the image to be processed, the cell row aligned immediately below the edge cells at the upper left edge and the upper right edge, and the image to be processed The non-edge cells included in the cell row arranged between the left and right bottom cells along the lower edge are replaced with edge cells. Incidentally, if the special processing is not performed in the example shown in FIG. 3, the continuous region of the edge cell is as shown in FIG. 6A, and the contour cell extraction processing is performed on the continuous region in this state. Then, as shown in FIG. 6B, a contour cell appears in the image area of the main object, and a wasteful process is performed later.
[0032]
Next, in extracting a contour cell from a continuous region of edge cells, a search is started from the edge cell at the lower left corner of the continuous region as shown in FIG. Extract as At this time, an array of contour cells is generated at the same time, and the contour cells are numbered in the order of extraction as shown in FIG.
[0033]
This contour cell extraction is performed in the search order shown in FIG. Here, the edge cell first found by searching clockwise among neighboring cells (eight neighboring conditions) around the current cell is defined as a contour cell. There are eight search orders depending on the positional relationship between the current cell and the previous cell. Here, each rectangular frame shown in FIG. 8 corresponds to a cell, but the search order shown in FIG. 8 is also adopted in contour point search described later, in which each rectangular frame corresponds to a point (pixel). To do.
[0034]
Next, a procedure for searching for a connection point that becomes a passing point of the contour line will be described. Here, as shown in FIG. 9, the contour cell and the non-contour cell in the region closed by the contour cell are set as search targets, and the boundary line of these cells is searched toward the inside of the closed region by the contour cell. . This connection point is searched on the condition that it has an edge strength exceeding a predetermined threshold as a contour point that constitutes the contour line, specifically, the first point found on the cell boundary line is connected Let it be a point. This connection point becomes an entrance and an exit of the contour line with respect to the cell, and a pair is extracted for each cell. This connection point search process is performed by the connection point search unit 7 shown in FIG.
[0035]
The connection point search process will be described using another example. As shown in FIG. 10, the contour cells are numbered in the order in which the search is advanced clockwise from the search start cell at the lower left corner. And a connection point is searched on the boundary line concerning a contour cell toward the inside of the closed region by a contour cell.
[0036]
In this connection point search, a connection point is searched for in each case based on the relative positional relationship between a pair of adjacent contour cells in accordance with a predetermined arrangement. In other words, since the contour cells are extracted under eight adjacent conditions, there are three ways of arranging a pair of adjacent contour cells, up, down, left, and right, and diagonal, and the search according to the positional relationship is made after determining the positional relationship between the search target cells. Search according to the method.
[0037]
First, as shown in FIG. 11, when a pair of adjacent contour cells are arranged in the vertical direction, the boundary line AB between the pair of contour cells A and B is searched. At this time, the search is performed toward the inside of the region closed by the contour cell, and the search is started from the outermost point P of the boundary line AB. If the connection point cannot be extracted, the search is performed on the boundary lines AC and BD on the boundary lines with the non-contour cells C and D that are in contact with the contour cells A and B and are located inside the closed region of the contour cells. If no connection point is found, the point P is set as a connection point.
[0038]
When a connection point is found on the boundary line AC / BD with the non-contour cell C / D, the search range is expanded to the inner non-contour cell C / D. There are various modes in the passing state, and here, as shown in FIGS. 11B and 11C, a total of four non-contour cells C, D, E, and F arranged inside the contour cells A and B, respectively. If the outline passes through other non-contour cells, the point P is set as a connection point. Here, the upper limit is 5 for the number of connection points applied to the non-contour cell. When a pair of adjacent contour cells are arranged in the left-right direction, the same procedure as described above can be performed by replacing the positional relationship of the cells with the left and right.
[0039]
On the other hand, as shown in FIG. 12, when a pair of adjacent contour cells A and B are arranged in an oblique direction, the non-contact region that is in contact with both of the pair of contour cells A and B and is located inside the closed region by the contour cell. The boundary line with the contour cell C is searched. At this time, the search is started from the intersection P of the pair of contour cells A and B. If the connection point cannot be extracted here, as shown in FIGS. 12B and 12C, it is in contact with only one of the pair of contour cells A and B and is located inside the closed region by the contour cell. Search on boundary lines AD and BE with non-contour cells D and E. In this case, the search object is limited to the non-contour cell F and the non-contour cell G that touch both of the non-contour cells C and D, and the number of connection points related to the non-contour cell is limited to four. And
[0040]
Next, the outline extraction procedure for connecting the connecting points will be described. Here, as shown in FIG. 13, the nearest connection point according to a predetermined arrangement from the connection point (start connection point) S that is the starting point of the search is set as a target point (target connection point) E, and this target connection point. A point satisfying a predetermined condition is sequentially extracted from the starting connection point S toward E, and set as a contour point constituting the contour line. At this time, the edge intensity for each pixel is compared with a threshold value, and a pixel having an edge intensity exceeding a predetermined threshold value is set as a contour point. This contour point search process is performed by the contour point search unit 8 shown in FIG. Here, the contour line is searched to connect a pair of connection points set on the boundary line of one cell, but it is allowed to enter the adjacent cell in the process. In addition, the square frame in the cell shown in a figure shows a point (pixel).
[0041]
In the extraction of the contour line, as shown in FIG. 8, the points outside the closed region by the contour cell are preferentially extracted from the adjacent points around the current point (eight adjacent conditions). Here, the connection points are arranged clockwise according to the arrangement of the contour cells, and according to the arrangement, the front point of the pair of nearest connection points is the start connection point, and the rear point is the target connection point. Continue the search. As a result, the left side in the direction of travel is always located outside the closed area of the contour cell, and the first one found by searching for neighboring points around the current point in the same clockwise direction as the array of connection points. By using the contour points, the outer points are preferentially extracted from the adjacent points.
[0042]
In the search for the contour line connecting the connection points, the following processing is performed in order to avoid the stray and reliably reach the target connection point.
[0043]
First of all, if the total number of extracted points exceeds the predetermined maximum allowable value, the search is stopped at that stage and all the points extracted so far are rejected in order to avoid unnecessary increase of contour points. Then, as shown in FIG. 14, points on the line segment connecting the connection points S and E are set as contour points. The maximum allowable value of the number of extraction points may be set based on the distance between the connection points, and here the maximum allowable value p _max = D × 2, that is, twice the distance between connection points. In the example shown in FIG. 14, since the distance d = 12 (4 neighboring distances) between the connection points S and E, the maximum allowable value p _max = 24.
[0044]
Second, in order to avoid stray in the vicinity of the target connection point, the distance from the newly extracted point to the target connection point is equal to or smaller than a predetermined value (minimum distance), that is, the newly extracted point is predetermined. The search is terminated at that stage, and the point on the line segment connecting the last extracted point and the target connection point is set as the contour point. In the example shown in FIG. 15A, since the newly extracted point P falls within the region near the target connection point, the search is stopped here, and the point P and the target connection are connected as shown in FIG. A point on a line segment connecting point E is complemented as a contour point. Here, the minimum distance for stopping the search is 4 (4 neighborhood distance).
[0045]
Third, in order to avoid useless contour point extraction, already extracted points are extracted by overlapping, that is, when a newly extracted point is the same as an already extracted point, the search is performed at that stage. The process is stopped, and points extracted twice after the previous extraction are rejected, and points on the line segment connecting the double extraction points and the target connection points are set as contour points. In the example shown in FIG. 16 (A), since S, A, B, C, D, F, P, G, H, I, and P are extracted in this order, and the point P is extracted in an overlapping manner, FIG. ), The points G, H, I, and P are deleted and replaced with the target connection point E, and the final extraction points are sequentially S, A, B, C, D, F, P, and E, and double A point on the line segment connecting the extraction point P and the target connection point E is complemented as a contour point. The number of already extracted points to be collated when determining whether or not they have been extracted twice is set based on the distance between connection points.
[0046]
Fourth, in order to avoid moving far away from the target connection point, when the number of continuous retreats to the target connection point reaches a predetermined value (reverse limit number), the search is stopped at that stage, All the points extracted after the starting point are rejected, and the points on the line segment connecting the points extracted immediately before starting the retraction and the target connection points are set as contour points. In the example shown in FIG. 17 (A), if the limit number of retreats is the distance d = 12 between the connection points S and E, since the retreat is continued 12 times from the point 12 to the point 23, the search is performed here. As shown in FIG. 17B, the points 12 to 23 starting to move backward are deleted and replaced with the target connection point E, and the final extracted points are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, E, and the points on the line segment connecting the point 11 extracted immediately before starting the retraction and the target connection point E are complemented as contour points. In FIG. 17, the retracted points are shown with an underline. Although the points are retracted once at points 4 and 7, the search is not stopped because the limit of the number of retreats has not been reached.
[0047]
Fifth, in order to avoid interruption of the contour point search process, when the next point cannot be extracted, a point closest to the target connection point is extracted from the neighboring points around the current point. And In the example shown in FIG. 18, there is no point A to G that is the next candidate for the point 6 that satisfies the contour point condition, and therefore the point that is closest to the target connection point E among the points A to G that are candidates. Select C. Here, after the point C is extracted, points that satisfy the contour point condition are sequentially extracted, and the final extracted points are S, 1, 2, 3, 4, 5, 6, C, 7, 8, 9, 10 in order. , 11, E.
[0048]
Furthermore, the following special processing is performed as necessary in order to avoid large deviation from the actual contour line.
[0049]
First of all, in order to avoid the bending of the contour line at a steep angle, when searching for the contour point sequentially, among the eight adjacent points around the current point, the point immediately before and the point that touches the top, bottom, left and right, That is, the next point is extracted from the remaining points excluding the point that contacts the previous point under the four adjacent conditions. In the example shown in FIG. 19, among the 8 adjacent points around the current point, the point extracted immediately before and the points 1 and 7 on both sides thereof are excluded from the extraction target, and the contour is selected from the remaining points 2 to 6. Extract points. Thereby, the bend angle of the contour line can be suppressed to 90 degrees or less.
[0050]
Secondly, in order to avoid a drop into the break, a search is made simultaneously with the adjacent points for the points aligned in the direction of each adjacent point with the current point as the center, that is, the points aligned in the direction with each adjacent point; Whether or not a predetermined condition is satisfied, and if any of them satisfies the condition, these points are collectively set as a contour point. In the example shown in FIG. 20, among the 8 adjacent points around the current point, points 1 to 7 excluding the point extracted immediately before are candidates, and each of these adjacent points 1 to 7 is arranged in that direction. Judgment is made with a total of three points including the two points. For example, the determination is performed by combining the adjacent point 1 and the two points 1 ′ · 1 ″ arranged in the direction. By this, there is a point that does not satisfy the condition, so that it is possible to avoid folding in the wrong direction.
[0051]
In order to perform the avoiding process of the sharp bend and the drop into the cut at the same time, as shown in FIG. 21, among the 8 adjacent points around the current point, the point extracted immediately before and the points on both sides thereof 1 and 7 are excluded from the extraction target, and each of the remaining points 2 to 6 and a point aligned in the direction are simultaneously determined to extract a contour point.
[0052]
22 and 23 show an example in which the positional relationship between the current point and the previous point is different from the above example. In FIG. 22, the previous point and the adjacent points among the eight neighboring points around the current point are shown in FIG. The next point is extracted from the remaining points 2 to 6 excluding the points 1 and 7 in contact with the top, bottom, left and right. In FIG. 23, in addition to the conditions shown in FIG. 22, a point aligned in the direction of each adjacent point 2-6 around the current point is searched simultaneously with the adjacent point to extract the next point.
[0053]
Below, the procedure of the whole outline extraction process is demonstrated according to the flow shown in FIG. First, after the processed image data is sent from the image input unit 1 shown in FIG. 1 to the target image memory 12a of the image memory 12, if the processed image is a color image in step 101, the edge shown in FIG. The intensity detection data creation unit 2 converts the image into a monochrome grayscale image (for example, 256 gradations) based on the luminance level. If the image is noisy at step 102, smoothing processing is performed. The processed image data obtained in this way is stored in the edge strength detection memory 12b shown in FIG.
[0054]
Next, at step 103, the edge strength for every pixel is obtained using the image data to be processed in the edge strength detection memory 12b shown in FIG. 1, and stored in the edge strength memory 12c shown in FIG. . In calculating the edge strength, template type filter processing may be performed. For this purpose, a local operator, for example, a 3 × 3 pixel Prewitt operator can be used to determine not only the edge strength but also the edge direction from the level difference between adjacent pixels.
[0055]
In the next step 104, the edge strength threshold setting unit 3 shown in FIG. 1 sets an edge strength threshold suitable for the image to be processed. In setting the edge strength threshold, a histogram is created from the edge strength data of all pixels, and the cumulative value of the frequencies obtained by adding the frequencies in order from the maximum edge strength is a predetermined ratio to the total number of pixels. The edge strength when reaching the threshold value is set as a threshold value. Here, the ratio with respect to the total number of pixels serving as a determination criterion is, for example, 8.65% when the smoothing process is performed and 9.40% when the smoothing process is not performed.
[0056]
Next, in step 105, the image to be processed is divided into a grid pattern by the edge cell extraction unit 4 shown in FIG. 1, and is divided into edge cells and non-edge cells depending on whether or not pixels having edge strength exceeding a threshold value are included in step 106. To do. In step 107, the continuous area creation unit 5 shown in FIG. 1 performs labeling in units of cells, and then in step 108, it is determined whether or not the continuous area is unique. After decreasing the number and increasing the cell size, the process returns to step 105.
[0057]
If it is determined in step 108 that the continuous region is unique, in step 110, the contour cell extraction unit 6 shown in FIG. In step 111, the connection point search unit 7 shown in FIG. 1 searches for the connection point, and in step 112, the contour point search unit 8 shown in FIG.
[0058]
Next, a procedure (steps 103 to 109) for creating a continuous region of edge cells shown in FIG. 24 will be described in detail with reference to FIG. First, in step 201, an edge strength threshold de serving as an edge cell criterion is set. In step 202, an array of the number of image divisions dev [i] is set. For example, the arrangement is 48, 36, 24, 18, 12, 8, 6, 4, 3, 2, 1, and the number of divisions is reduced in this order to obtain a single continuous region.
[0059]
Next, in step 203, a loop for creating a continuous area is started on the condition that the cell label number is unique, that is, the continuous area of the edge cell is unique. In step 204, the cell is divided by the division number dev [i]. To do. In step 205, an edge cell determination loop is started under the condition that all cells are completed, and the cells are classified into edge cells and non-edge cells based on the edge strength for each cell. That is, in step 206, it is determined whether or not there is a pixel having an edge strength exceeding the edge strength threshold de in the cell. If there is a corresponding pixel, the cell is set as an edge cell in step 207, and if there is no corresponding pixel, step In 208, the cell is set as a non-edge cell. If all the cells have been completed in step 209, the process exits the edge cell determination loop.
[0060]
In step 210, labeling processing is performed on a cell-by-cell basis. In step 211, consecutive cells are replaced with the same label number, and in step 212, it is determined whether the label number is unique, that is, whether the continuous area is unique. If it is not unique, the process returns to step 204, and the process is repeated with the next smallest number of divisions according to the array of the number of divisions dev [i], and this is repeated until the continuous area becomes unique. finish. As a result, a single continuous area is set in the processed image.
[0061]
Next, the procedure of the special process for face photography (see FIGS. 3 and 5) by the face photograph processing unit 9 shown in FIG. 1 will be described according to the flow shown in FIG. First, in step 301, a loop for searching for the upper left edge cell is started. In step 302, the upper left cell of the image to be processed is set as a start position. Then, in step 303, it is determined whether the cell is an edge cell. In 304, the cell moves to the cell immediately below. If it is the lowest end here, it moves to the uppermost cell of the cell row on the right. If it is determined in step 303 that the cell is an edge cell, the loop is terminated in step 305, and in step 306, all cells arranged immediately below the upper left edge cell are defined as edge cells.
[0062]
Next, in step 307, a loop for searching for the upper right edge cell is started. In step 308, the upper right cell is set as the start position. In step 309, it is determined whether or not the cell is an edge cell. If it is the lowermost end, it moves to the upper end of the left cell row. If it is determined in step 309 that the cell is an edge cell, the loop is terminated in step 311, and in step 312, all cells arranged directly below the upper right edge cell are defined as edge cells. In step 313, all cells between the left and right bottom cells are set as edge cells.
[0063]
Next, the connection point search procedure in the connection point search unit 7 shown in FIG. 1 will be described according to the flow shown in FIG. 27, FIG. 28, and FIG. First, index IDX of a pair of contour cells A and B to be searched in step 401 shown in FIG. _A ・ IDX _B In step 402, the traveling direction from the contour cell A to the contour cell B is examined. In step 403, it is determined whether dx = 0, that is, whether they are arranged vertically. If dx = 0, the process proceeds to step 404 to perform the up / down connection process. If it is determined in step 403 that dx = 0 is not satisfied, the process proceeds to step 405, where it is determined whether dy = 0, that is, whether they are arranged side by side. I do. If it is determined in step 405 that dy = 0 is not satisfied, the process proceeds to step 407 to perform oblique connection processing.
[0064]
In step 408, the index IDX of the contour cells A and B is displayed. _A ・ IDX _B , And increment index IDX of contour cell B in step 409. _B Is equal to the total number of contour cells NUM, that is, whether contour cell B is out of the array of contour cells. If contour cell B is out of the array, index IDX is determined in step 410. _B Is set to 0, and the process returns to step 402, and a connection point search process is performed between the last contour cell (contour cell A) and the first contour cell (contour cell B). If the contour cell B is in the array of contour cells, the index IDX of the contour cell A in step 411 _A Is determined to be equal to the total number NUM. If contour cell A is out of the array of contour cells, the process ends. If contour cell A is within the array, the process returns to step 402.
[0065]
In the vertical connection process in step 404 shown in FIG. 27, as shown in FIG. 28, it is first determined in step 501 whether or not a point satisfying the condition as a connection point is on the boundary line AB. If there is a point that satisfies the condition, the point is set as a connection point in step 502 (see FIG. 11A). If there is no corresponding point, the process proceeds to step 503. In step 503, it is determined whether or not a point satisfying the connection point condition is on the boundary line AC / BD. If there is a corresponding point, the process proceeds to step 504, and if there is no corresponding point, extraction is performed in step 509. The point P is regarded as a connection point because it is impossible.
[0066]
In step 504, it is determined whether or not a point satisfying the connection point condition exists on the boundary line CD. If there is a corresponding point, in step 505, each point on the boundary line AC / CD / BD is connected in order. Points (see FIG. 11B). If there is no corresponding point on the boundary line CD, the process proceeds to step 506, where it is determined whether or not a point satisfying the connection point condition is on the boundary line CE / DF. Proceeding to step 507, if there is no corresponding point, in step 509, point P is set as a connection point. In step 507, it is determined whether or not a point satisfying the connection point condition exists on the boundary line EF. If there is a point corresponding to this point, in step 508, each point on the boundary line AC, CE, EF, DF, or BD is displayed. Points are sequentially set as connection points (see FIG. 11C). If there is no corresponding point on the boundary line EF, the point P is set as a connection point in step 509.
[0067]
The procedure of the left / right connection process in step 406 shown in FIG. 27 is performed in the same procedure by replacing the cell positional relationship in the above-described vertical connection process with the left / right.
[0068]
In the oblique connection process in step 407 shown in FIG. 27, as shown in FIG. 29, first, in step 601, it is determined whether there are points on the boundary line AC and BC that satisfy the condition as a connection point. If there is a point corresponding to this point, in step 602, two points on the boundary line AC / BC are sequentially set as connection points (see FIG. 12A). If there is no corresponding point, the process proceeds to step 603, where it is determined whether or not a point that satisfies the connection point condition is on the boundary line AC. If there is a corresponding point, the process proceeds to step 604, and the corresponding point If no, go to step 605.
[0069]
In step 604, it is determined whether or not there are all points on the boundary lines CG, EG, and BE that satisfy the connection point condition. If there are such points, the process proceeds to step 606, where the boundary lines AC, CG, EG, Each point on the BE is set as a connection point in order (see FIG. 12B). If there is no corresponding point, extraction is impossible in step 609, and a point P where the contour cells A and B are in contact with each other is set as a connection point.
[0070]
In step 605, it is determined whether or not a point satisfying the connection point condition is on the boundary line BC. If there is a corresponding point, the process proceeds to step 607. If there is no corresponding point, the point P is connected to the connection point in step 609. And In step 607, it is determined whether or not there are all points on the boundary line AD, DF, CF that satisfy the connection point condition. If there is such a point, in step 608, the boundary line AD, DF, CF, BC is These points are sequentially designated as connection points (see FIG. 12C). If there is no corresponding point, point P is set as a connection point in step 609.
[0071]
Next, the contour point search procedure by the contour point search unit 8 shown in FIG. 1 will be described according to the flow shown in FIGS. First, in step 701 shown in FIG. 30, the start connection point S and the target connection point E are set, and in step 702, the distance d between the connection points S and E is obtained. Then, in step 703, the maximum allowable value p that limits the total number of points to avoid unnecessarily increasing contour points. _max And the minimum distance d to the target connection point E, which is a reference for stopping the search by approaching the target connection point E in step 704. _min Set. In step 705, the size of the history buffer for temporarily storing the extracted points is set. This history buffer is a target for determining whether or not it has been extracted twice. Here, the maximum allowable value p _max X2. In the next step 706, the limit number D of reverse limits for limiting the continuous reverse is set, and the process proceeds to step 707 shown in FIG.
[0072]
In step 707, a contour point search loop is started with the arrival condition of the target connection point E as an exit condition. In step 708, the condition as a contour point among the eight next candidate points, that is, a predetermined edge strength is determined. A point that satisfies the condition exceeding the threshold is searched, and it is determined in step 709 whether there is a point that satisfies the condition. If there is a corresponding point, the process proceeds to step 711. If there is no corresponding point, step 710 is performed. Then, a point closest to the target connection point E is selected from the adjacent points (see FIG. 18).
[0073]
Next, in step 711, it is determined whether or not the extraction point p is the target connection point E. If it is not the target connection point E, the process proceeds to step 712, and if it is the target connection point E, the process proceeds to step 721. The target connection point E is stored in the history buffer, and the loop is terminated at step 722.
[0074]
In step 712, the distance between the extraction point p and the target connection point E is a predetermined value (minimum distance) d. _min It is determined whether or not (see FIG. 15), and the minimum distance d _min If larger, go to Step 713. Minimum distance d _min If it is below, the process proceeds to step 712, where the extracted point p is stored in the history buffer as a contour point, the loop is terminated in step 722, and finally extracted from the start connecting point S to the last extracted point p. A point and a point on a line segment connecting the last extracted point p and the target connection point E are contour points.
[0075]
In step 713, the total number of points extracted so far is the maximum allowable value p. _max Whether or not the maximum allowable value p is determined. _max If not, the process proceeds to step 714 and the maximum allowable value p is reached. _max If it exceeds, the process proceeds to step 715, where all the points extracted so far are rejected, that is, all the points extracted after the start connection point S and stored in the history buffer are deleted. Then, the target connection point E is selected, the target connection point E is stored in the history buffer in step 721, the loop is ended in step 722, and finally on the line segment connecting the start connection point S and the target connection point E. The points become contour points (see FIG. 14).
[0076]
In step 714, it is determined whether or not the extracted point is the same as the already extracted point, that is, whether or not the same as the extracted point is in the one stored in the history buffer (see FIG. 16). If there is no corresponding point, the process proceeds to step 716. If there is a corresponding point, the process proceeds to step 717 to reject all the points extracted after the previous extraction of double extracted points, that is, stored in the history buffer. Delete all the points after the double extraction point from the points. In step 718, the target connection point E is selected. In step 721, the target connection point E is stored in the history buffer. In step 722, the loop is terminated. Finally, the double extraction point is determined from the start connection point S. The points extracted before the previous extraction and the points on the line segment connecting the double extraction point and the target connection point E are contour points.
[0077]
In step 716, it is determined whether or not the vehicle has moved backward, that is, whether or not the distance between the extracted point and the target connection point E has increased (see FIG. 17). If not, the extracted point p is stored in the history buffer as a contour point, and the process returns to step 708 to search for the next contour point.
[0078]
In step 719, it is determined whether or not the number of continuous backward movements has reached a predetermined value (reverse limit number). If the reverse limit number has been reached, the process proceeds to step 720 and extracted after the point where the reverse movement is started. In step 721, all the points extracted after the backward start point are deleted from the points stored in the history buffer, and the target connection point E is selected in step 718. The target connection point E is stored in the history buffer, and the loop is terminated in step 722. Finally, the points extracted from the start connection point S to the point immediately before starting the reverse, and the point immediately before starting the reverse, A point on a line segment connecting the target connection point E is a contour point. If it is determined in step 719 that the number of continuous retreats has not reached the retreat limit number, the extracted point p is stored as a contour point in the history buffer, and then the process returns to step 708 to search for the next contour point.
[0079]
【The invention's effect】
As described above, according to the present invention, it is possible to extract an appropriate contour line by performing a process suitable for extracting the contour line representing the boundary between the main object and the background, and to improve the efficiency of the processing operation. The processing time can be shortened by reducing the burden.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a schematic configuration of an outline extraction processing apparatus to which the present invention is applied.
FIG. 2A is a schematic diagram showing a contour extraction result according to the present invention.
(B) Schematic diagram showing the contour extraction situation according to the present invention
FIG. 3 is a schematic diagram showing an edge cell extraction situation according to the present invention.
FIG. 4 is a schematic diagram showing another example of edge cell extraction status according to the present invention.
FIGS. 5A and 5B are schematic views showing another example of the processing state for a face photograph according to the present invention.
FIGS. 6A and 6B are schematic diagrams showing the contour cell extraction status according to the present invention.
FIGS. 7A and 7B are schematic diagrams showing a contour cell extraction situation according to the present invention.
FIG. 8 is a schematic diagram illustrating the search order of contour points and contour cells according to the present invention.
FIG. 9 is a schematic diagram showing a connection point search situation according to the present invention.
FIG. 10 is a schematic diagram showing another example of a connection point search situation according to the present invention.
FIGS. 11A to 11C are schematic diagrams showing connection point search situations according to the present invention.
FIGS. 12A to 12C are schematic diagrams showing connection point search situations according to the present invention.
FIG. 13 is a schematic diagram showing a contour point search situation according to the present invention.
FIG. 14 is a schematic diagram illustrating a contour point searching method according to the present invention.
FIGS. 15A and 15B are schematic diagrams for explaining a contour point searching method according to the present invention.
FIGS. 16A and 16B are schematic diagrams for explaining a contour point searching method according to the present invention.
FIGS. 17A and 17B are schematic diagrams for explaining a contour point searching method according to the present invention.
FIG. 18 is a schematic diagram illustrating a contour point searching method according to the present invention.
FIG. 19 is a schematic diagram illustrating a contour point searching method according to the present invention.
FIG. 20 is a schematic diagram for explaining a contour point searching method according to the present invention.
FIG. 21 is a schematic diagram for explaining a contour point searching method according to the present invention.
FIG. 22 is a schematic diagram illustrating a contour point searching method according to the present invention.
FIG. 23 is a schematic diagram for explaining a contour point searching method according to the present invention.
FIG. 24 is a flowchart showing the entire outline extraction process according to the present invention.
FIG. 25 is a flowchart of continuous area creation processing according to the present invention.
FIG. 26 is a flowchart of special processing for facial photographs according to the present invention.
FIG. 27 is a flowchart of connection point search processing according to the present invention.
FIG. 28 is a flowchart of upper and lower connection processing in connection point search according to the present invention.
FIG. 29 is a flowchart of oblique connection processing in connection point search according to the present invention.
FIG. 30 is a flowchart showing a part of contour point search processing according to the present invention.
FIG. 31 is a flowchart showing the remainder of contour point search processing according to the present invention.
[Explanation of symbols]
1 Image input section
2 Edge strength detection data generator
3 Edge strength threshold setting part
4 Edge cell extraction unit
5 Continuous area creation part
6 Contour cell extraction unit
7 Connection point search unit
8 Contour point search unit
9 Face photo processing section
10 Extracted contour line output section
11 Extracted contour editing section
12 Image memory
12a Memory for target image, 12b Memory for edge strength detection, Memory for 12c edge strength
13 Operation memory
14 Controller

Claims (15)

A contour line extraction processing method for extracting a contour line representing a boundary between a main object in a processed image and its background,
A state in which the processing target image is divided into a lattice shape, and a cell including pixels having edge strength exceeding a predetermined threshold is extracted as an edge cell from the plurality of cells obtained thereby, and the edge cells are continuous with each other. When a plurality of continuous areas are created in the image area of the main object, the continuous area is reduced to one by reducing the number of divisions of the processed image into the cells. Then, a cell located on the outer periphery of the continuous region is extracted as a contour cell, and after searching for a connection point that is a passing point of the contour line on a boundary line of the contour cell and its neighboring non-contour cell, A contour line extraction processing method , wherein the contour line is extracted so as to connect connection points to each other . In creating the continuous region of the edge cells, if the image to be processed is a human face photo, the cells lined directly under the edge cells at the upper left corner and the upper right corner, and the left and right leftmost cells among them. The contour line extraction processing method according to claim 1 , wherein the continuous region is created by setting all cells between the lower end cells as edge cells. When searching for the connection point, search for the contour cell and the non-contour cell in the region closed by the contour cell, and search the boundary line of the cell toward the inside of the closed region by the contour cell. The contour line extraction processing method according to claim 1 . 2. The contour according to claim 1 , wherein when searching for the connection point, the connection point is searched in a case-by-case manner based on a relative positional relationship between a pair of adjacent contour cells according to a predetermined arrangement. Line extraction processing method. When the adjacent pair of contour cells are arranged in either the top and bottom or left and right directions, search for the boundary line between the pair of contour cells, and if it is impossible to extract the connection point, the pair of contour cells 5. The contour line extraction processing method according to claim 4 , wherein a search is performed on a boundary line with each non-contour cell in contact therewith. When the pair of adjacent contour cells are arranged in an oblique direction, a search is performed on a boundary line with a non-contour cell that is in contact with both of the pair of contour cells. 5. The contour line extraction processing method according to claim 4 , wherein a search is made on a boundary line with a non-contour cell that contacts only one of the two. Claims Upon extracting the contour line, as the target point nearest connection point from the connection point as a starting point in accordance with a predetermined sequence, characterized by sequentially searching for a contour points constituting the contour line 1. A contour line extraction processing method according to 1. In sequentially searching the contour points from the start point to the target point,
When the total number of extracted points exceeds a predetermined value, the search is stopped at that stage, all the points extracted so far are rejected, and points on the line segment connecting the start point and the target point are determined. The contour line extraction processing method according to claim 7 , wherein the contour point is the contour point. In sequentially searching the contour points from the start point to the target point,
When the distance from the newly extracted point to the target point is less than or equal to a predetermined value, the search is terminated at that stage, and the point on the line segment connecting the last extracted point and the target point is the contour. The contour line extraction processing method according to claim 7 , wherein the contour line extraction processing method is a point. In sequentially searching the contour points from the start point to the target point,
If already extracted points are extracted and extracted, the search is stopped at that stage, all the points extracted after the previous extraction of the double extracted points are rejected and the double extracted. The contour line extraction processing method according to claim 7 , wherein a point on a line segment connecting the point and the target point is set as the contour point. In sequentially searching the contour points from the start point to the target point,
When the number of consecutive backward movements with respect to the target point reaches a predetermined value, the search is stopped at that stage, all points extracted after the point where the backward movement is started are rejected, and immediately before the backward movement is started. The contour line extraction processing method according to claim 7 , wherein a point on a line segment connecting the point extracted to the target point and the target point is set as the contour point. In sequentially extracting the contour points from the start point toward the target point,
8. The contour line extraction processing method according to claim 7 , wherein when the next point cannot be extracted, a point closest to the target point among neighboring points around the current point is set as the contour point. . In order to sequentially search for the contour point , the next point is extracted from the remaining points excluding the immediately preceding point and the points on both sides in contact with the adjacent points around the current point. The contour line extraction processing method according to claim 7 . Upon sequentially searches the contour points, the points arranged in the center in the direction of each adjacent point the current point to search concurrently with said adjacent points claim 7, characterized in that to extract the following: contour extraction method. A contour line extraction processing device for extracting a contour line representing a boundary between a main object in a processed image and its background,
An edge cell extraction unit that extracts a cell including a pixel having an edge intensity exceeding a predetermined threshold as an edge cell from a plurality of cells obtained by dividing the image to be processed in a grid pattern;
Create a continuous region in which the edge cells are continuous with each other, determine whether the continuous region is unique in the image area of the main object, and if not, go to the cell of the processed image A continuous region creating unit that integrates the continuous regions into one by reducing the number of divisions of
A contour cell extraction unit that extracts cells located on the outer periphery of the continuous region as contour cells;
A connection point search unit for searching for a connection point that is a passing point of the contour line on a boundary line of the contour cell and the non-contour cell in the vicinity thereof;
An outline extraction processing apparatus comprising: an outline point search unit that sequentially searches for outline points constituting the outline so as to connect the connection points to each other.

Images