JP2005196678A - Template matching method, and objective image area extracting device - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To extract an objective image area by a template of remarkably small data amount with high accuracy. <P>SOLUTION: The template data 13 is composed of a positive point indicating a position where an edge of an objective image exists, of a processed area, and a negative point indicating a position where the edge does not exist, of the processed area, and a matching value is calculated in accordance with the positional relationship of each of positive points and negative points and each edge existing on the image of the processed area. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention relates to an image processing technique, and more particularly, to a technique for specifying a region of a target image included in an input image based on template data indicating a shape feature of the target image and extracting information related to the target image region.

Conventionally, a template matching method has been widely used as a technique for specifying a target image included in an input image based on template data indicating characteristics of the target image. As shown in FIG. 13, the processing area having the same size as the template data T is scanned in units of pixels on the input image, and the consistency between the input image and the template data is shown for each processing area image W. A matching value is obtained, and a desired target image area is specified based on the processing area where the maximum value is obtained.
For the matching value, for example, a normalized correlation coefficient is used. The normalized correlation coefficient R (x, y) is determined by the pixel value W (x + i, y + j) of the pixel u (i, j) in the processing region image W and the pixel u ′ (i) in the template data T. , j) and the pixel value T (i, j), are obtained based on equation (4). Wavg is an average pixel value in the processing area, and Tavg is an average pixel value of the template. This normalized correlation coefficient approaches 1 if the correlation between both images is high, and approaches -1 if the correlation is low.

Such a template matching method is used, for example, in an electronic component board mounting apparatus. In this type of device, the part that is to be attached to the board is picked up by an image pickup device such as a camera, and the suction position and direction are recognized and the position and direction are corrected based on the template matching method described above. Thus, it is possible to place the components on the board and mount them with high accuracy.
The recognition of the specific component suction position and direction is performed by the following method. First, vertical and horizontal projection distributions are created from the component image in the captured image, and the approximate position and direction of the target component are recognized from the projection distribution. Then, based on the rough position information and direction information, the side of the four corners of the target part is predicted to be in which region, and a template matching method using a template having the shape of the four corners in that region is performed. Thus, the position of the accurate part is recognized.

Conventionally, various techniques have been proposed in order to improve the region extraction accuracy of such a template matching method.
First, as a first technique, for example, a technique such as Patent Document 1 has been proposed. In this template matching method, a mask region set so as to be treated as invalid data in the calculation of a matching value is provided on the template data. By using such a template, it is devised so that a minute angle shift of the template does not affect the correlation calculation when the matching value is obtained.

As a second conventional technique, an apparatus for extracting a human face region using the template matching method described above has been proposed (see, for example, Non-Patent Document 1). In this case, the human face area in the image is specified by searching the grayscale image including the human face area using the mosaic face template as shown in FIG.
In addition, as a third conventional technique, an edge image of a skin color extraction region is created from a skin color extraction image obtained by extracting only skin color pixels corresponding to a preset skin color from a digital color image including a human face region, There has also been proposed a technique for extracting a human face region by searching through an image by template matching using an elliptical template.

The applicant has not yet found prior art documents related to the present invention by the time of filing other than the prior art documents specified by the prior art document information described in this specification.
JP-A-8-315147 Tomoharu Nagao, “Introduction to Image Processing in C Language”, Shosodo, November 20, 2000, p. 204-211

However, such a conventional technique has a problem that the processing time is long because of the large number of templates necessary for extracting the target image area, and erroneous extraction is easily caused by the influence of noise.
First, in the first prior art described above, in order to recognize the position of a component, it is necessary to create projection distributions in the vertical and horizontal directions of the component as a target image in the captured image. In addition, since a monochrome binarized image or grayscale image captured for both the target image and the template data is used, the number of templates increases, and there is a problem that it takes a long time for correlation calculation in performing matching processing. is there.

  In the second prior art described above, a mosaic face template is used. In this case, both the input image and the template data use monochrome grayscale images, and template matching with the entire face in the image is performed. This increases the number of templates. For this reason, there are problems that the amount of memory for storing templates increases and the processing time for template matching increases. Furthermore, in such a method of searching for a face region using the gray level information of an image, a change due to the orientation of the face in the image greatly affects the recognition rate, such as when a person in the image is facing sideways. There is also the problem of giving.

  In the third prior art described above, an edge image of a skin color extraction region is created from a skin color extraction image obtained by extracting only skin color pixels corresponding to a preset skin color from a digital color image including a human face region. A face region is extracted by searching the image by template matching using an elliptical template. However, this method has a problem that the elliptical edge template is caught by the edge of a region other than the face and whose color is close to the color of the person's skin.

When the third prior art is actually applied to an image of a digital camera or the like, the face template 302 matches the face area 301 as shown in FIG. If there is an object with a rough surface, many edges appear as noise on the edge image of the skin color extraction region, and the face template 303 is matched to an erroneous region where such noise exists. .
Further, in the case of detecting the position of the target angle having a specific angle from the edge image of the triangle, as shown in FIG. 16, although the corner template 312 matches the desired target angle 311, two triangles are created. There is a problem that the corner template 313 is matched to an incorrect region.

  The present invention is for solving such a problem, and makes it possible to accurately extract a target image region with a template having an extremely small data amount. An object of the present invention is to provide a template matching method and a target image region extraction apparatus.

  In order to achieve such an object, the template matching method according to the present invention uses a processing region image in an arbitrary processing region acquired from an edge image of an input image, and template data indicating the shape characteristics of the target image. In the template matching method for calculating the matching value indicating the matching between the processing region image and the target image and identifying the target image region in the input image based on the matching value, the template data is the target image in the processing region. The positive point indicating the position where the edge exists and the negative point indicating the position where the edge does not exist in the processing region, and the positional relationship between each positive point and the negative point and each edge existing in the processing region image Accordingly, a first step of calculating a matching value is provided.

  At this time, the edge image is composed of a plurality of pixels indicating the image of the edge included in the input image with respective gradation values, and as a first step, the position of each point is determined for each positive point and negative point. A second step of calculating an evaluation value based on the gradation value of each pixel of the processing region image corresponding to the above, and a third step of calculating a matching value from the evaluation value of the positive point and the negative point. Good.

  Further, as a second step, for each positive point, a step of calculating a gradation value of a pixel corresponding to the position of the positive point in the processing region image as an evaluation value, and for each negative point, an edge image A value obtained by subtracting the gradation value of the pixel corresponding to the position of the negative point in the processing area image from the number of gradations is provided as an evaluation value, and the third step is calculated in the second step. A step of calculating the matching value from the sum of the evaluation values may be provided.

  In addition, as a first step, a fourth step of generating a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data as matching candidate information, and each positive point of the template data based on the matching candidate information And a fifth step of converting the coordinates of the negative point and generating new template data used for calculating the matching value.

  At this time, as a fourth step, a step of holding a plurality of individuals having chromosome information including a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data, A step of designating as an individual, a step of generating a child individual from a parent individual based on a genetic algorithm, and a step of outputting a parameter included in chromosome information of the child individual as matching candidate information may be provided.

  Further, in addition to the fourth step, among the held individuals, the one with the lowest matching value obtained using new template data generated based on the matching candidate information of the individual is selected as a replacement candidate And when the matching value obtained using the new template data generated based on the matching candidate information of the child individual is higher than the matching value of the replacement candidate, the child individual is replaced by the new individual. May be provided as a step.

Further, negative points in the template may be arranged so as not to overlap other edges of the target image existing around the edges of the target image.
At this time, the negative point may be arranged inside the region formed by the edge of the target image, or may be arranged outside the region formed by the edge of the target image.

Moreover, you may arrange | position a negative point around this shape along the shape which arrangement | positioning of a positive point forms.
Further, the positive points may be arranged at a density according to the ratio at which the edge of the target image appears in the area where the positive points are arranged, or the negative points are arranged in the area where the negative points are arranged. You may arrange | position with the density according to the ratio which edges other than appear.
Further, a human face image may be used as the target image, and an edge indicating the lower outline of the human face image may be used as the edge of the target image.

Further, as template data, face template data having a positive point indicating a position where an edge indicating the lower outline of the human face image exists and a negative point indicating a position where no edge indicating the lower outline of the human face image exists is used. Alternatively, a semi-elliptical shape may be used as an edge indicating the lower outline of the human face image.
At this time, positive points may be arranged at a high density in the cheek outline area of the human face image and may be arranged at a low density in the jaw outline area of the human face image, or negative points may be arranged at the lower outline of the human face image. Of the outer region of the region formed by the edges shown, it may be arranged at a high density in the cheek contour region of the human face image and may be arranged at a low density in the jaw contour region of the human face image.

  In addition, the target image region extraction apparatus according to the present invention is configured to specify the region of the human face image included in the input image using any one of the template matching methods described above.

  In addition, another target image region extraction apparatus according to the present invention includes an image input unit that generates an edge image indicating an outline of an object from an input image, an image holding unit that stores and holds the edge image, and the shape of the target image to be extracted. A template data holding unit that stores and holds template data indicating a characteristic, a matching candidate output unit that generates a plurality of types of parameters used for coordinate conversion of the template data as matching candidate information, and template data read from the template data holding unit A template coordinate calculation unit that generates coordinate data based on the matching candidate information and generates new template data, and a processing region image extracted from the processing region sequentially set on the edge image of the image holding unit and the template data coordinate conversion unit Matching that shows consistency with template data A matching calculation processing unit that calculates the target area, and when the matching value obtained from the matching calculation processing unit exceeds a predetermined reference value, the processing region from which the matching value is obtained is specified as a region including the target image. A region information extraction unit that outputs region information related to the target image region based on the coordinate position of the specified processing region and the template data, and the template data includes the edge of the target image in the processing region. It consists of positive points that indicate positions and negative points that indicate positions where no edge exists in the processing area. In the template coordinate calculation unit, the position of each positive point and negative point and each edge that exists in the processing area image The matching value is calculated according to the relationship.

  At this time, the edge image is composed of a plurality of pixels indicating the edge image included in the input image with respective gradation values, and the position of each point is determined for each positive point and negative point in the template coordinate calculation unit. The evaluation value may be calculated based on the gradation value of the pixel of the processing region image corresponding to, and the matching value may be calculated from the evaluation value of these positive points and negative points.

  Further, the template coordinate calculation unit calculates the gradation value of the pixel corresponding to the position of the positive point in the processing region image as an evaluation value for each positive point, and the gradation of the edge image for each negative point. A value obtained by subtracting the gradation value of the pixel corresponding to the position of the negative point in the processing area image from the number may be calculated as an evaluation value, and the matching value may be calculated from the sum of the evaluation values.

  In addition, the matching candidate output unit includes an individual group holding unit for storing and holding a plurality of individuals having chromosome information including a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data, and an individual group holding unit. A parent individual designating unit that designates one or more of each retained individual as a parent individual, and a child individual is generated from the parent individual based on a genetic algorithm, and parameters included in the chromosome information of the child individual are matched with candidate information And a new individual generation unit that outputs as

  Further, the matching candidate output unit replaces the individual held in the individual group holding unit with the lowest matching value obtained using new template data generated based on the matching candidate information of the individual. If the matching value obtained using the step of selecting as a candidate and the new template data generated based on the matching candidate information of the child individual is higher than the matching value of the replacement candidate, the child individual is replaced with the replacement candidate. A step of holding it as a new individual may be provided.

According to the present invention, it is possible to search for an edge position of a target image with a template having an extremely small data amount, and it is possible to recognize an edge other than the target image with a negative point and extract a target image region with high accuracy.
Therefore, the processing time required for the matching value calculation process can be significantly reduced and the storage capacity for holding the template data compared to the conventional case where a plurality of templates are used or a grayscale image is used as template data. Can be significantly reduced, and the target image region can be extracted with high accuracy without being affected by noise.

Next, embodiments of the present invention will be described with reference to the drawings.
[First Embodiment]
First, with reference to FIG. 1, a template matching method according to a first embodiment of the present invention and a target image region extraction apparatus using the same will be described. FIG. 1 is a block diagram showing a configuration of a target image area extracting apparatus according to a first embodiment of the present invention.

This target image region extraction apparatus is composed of a computer that performs image processing as a whole, and hardware including a microprocessor such as a CPU and a DSP (Digital Signal Processor) and its peripheral circuits and a program prepared in advance cooperate with each other. Alternatively, various functional means are realized by hardware alone.
The function means includes an image input unit 1, an image holding unit 2, a template data holding unit 3, a matching candidate output unit 4, a template coordinate calculation unit 5, a matching calculation processing unit 6, a target area specifying unit 7, and target area information. An extraction unit 8 is provided.

  The template matching method according to the present embodiment compares the processing region image sequentially acquired from the edge image of the input image with the template data indicating the geometric feature of the target image, and based on the matching value indicating the matching between the two, When a desired target image region is extracted from an edge image of an input image, template data including a positive point indicating an edge position and a negative point indicating a position without an edge in the target image is used. . Then, the matching value is calculated according to the positional relationship between each positive point and negative point and each edge existing in the processing region image. Further, the target image region extraction apparatus according to the present embodiment uses such a template matching method to extract target region information such as the position, rotation angle, and size of a desired target image region in the input image. It is a thing.

Next, each functional means will be described with reference to FIG.
The image input unit 1 captures an input image 10 captured by an imaging device such as a camera via a communication line or a recording medium or directly from the imaging device, and performs an edge extraction process to show an edge image indicating the contour of an object 11 is a functional means for generating and outputting 11. At this time, for example, when extracting a human face area, skin color pixels are extracted, noise is removed, and edges are extracted by a differential filter, with respect to the input image 10 composed of the digital color image. Then, after the obtained edge image is binarized, blur processing is performed by a low-pass filter, and the edge image has a predetermined number of gradations, for example, 7 gradations (3 bits) or 3 gradations (2 bits). 11 is generated. A known process may be used for these image processes. In the edge image 11 thus obtained, the edge portion is generally expressed by black pixels having a large gradation value, and the region having no edge is expressed by white pixels having a small gradation value.

The image holding unit 2 includes a storage device such as a memory or a hard disk, and is a functional unit that stores and holds the edge image 11 generated by the image input unit 1.
The template data holding unit 3 includes a storage device such as a memory or a hard disk, and is a functional unit that holds template data 13 input in advance as template data indicating the shape characteristics of the target image to be extracted from the input image 10. This template data 13 is formed from positive points representing edge positions in the target image and negative points representing positions without edges. Actually, from the coordinate information indicating the positions of these positive points and negative points. It is configured.

The matching candidate output unit 4 is a functional unit that randomly selects conversion parameters such as a center position, a rotation angle, and an enlargement ratio when the template data 13 is matched with the edge image 11 and outputs it as matching candidate information 14.
The template coordinate calculation unit 5 is a functional unit that performs coordinate conversion of the template data 13 read from the template data holding unit 3 based on the matching candidate information 14 from the matching candidate output unit 4 and outputs the template data 15 as new template data 15.

The matching calculation processing unit 6 uses the template data 15 from the template coordinate calculation unit 5 to sequentially perform matching value calculation processing, which will be described later, on the edge image 11 read from the image holding unit 2, thereby sequentially on the edge image 11. This is a functional means for calculating a matching value for each set processing region and outputting it as a calculation result 16.
At this time, the matching calculation processing unit 6 calculates a matching value according to the positional relationship between the positive point or the negative point set in the template data 15 and the edge existing in the edge image 11 as the matching value calculation processing. .

The target area specifying unit 7 compares the matching value included in the calculation result 16 from the matching calculation processing unit 6 with a preset reference value, and when a matching value exceeding the reference value is found, the matching value is detected. This is a functional means for specifying that the processing area from which the value is obtained is a position where a desired target image exists, and outputting processing area information 17 indicating the processing area.
The target area information extraction unit 8 is information on a desired target image area in the input image 10 based on the coordinate information indicating the processing area specified by the processing area information 17 from the target area specifying unit 7 and the template data 15. This is a functional means for outputting target area information 18 indicating the position, angle, size, etc. of the target image area.

[Configuration of template data]
Next, the configuration of template data used in the present embodiment will be described with reference to FIGS. FIG. 2 is a configuration example of template data used in this embodiment. FIG. 3 shows another configuration example of template data used in this embodiment.
For example, when a face area is extracted from an input image, as shown in the template data 13 in FIG. 2, positive points 21 are arranged as feature points along the edge indicating a human face outline, here, a semi-elliptical jaw outline. The negative point 22 is arranged outside the region 23 formed by the positive points 21, that is, outside the outline of the face.

In the template data 13 of FIG. 3, positive points 21 are arranged as feature points along the edges indicating the outline of the human face as in FIG. 2, and a negative point is formed outside the region 23 formed by these positive points 21. A point 22 </ b> A is arranged, and a negative point 22 </ b> B is arranged inside the region 23.
Note that the feature points including the positive points 21 and the negative points 22, 22A, 22B are designated by coordinate information on a template area having a predetermined size equal to the processing area.

[Template data conversion processing]
Next, template data conversion processing used in the present embodiment will be described with reference to FIG. 4A and 4B are explanatory views showing the conversion processing of template data used in the present embodiment, wherein FIG. 4A is an explanatory view showing conversion related to the rotation angle and center coordinates, and FIG. 4B is an explanatory view showing conversion related to the enlargement ratio. (C) is a mathematical formula used for conversion of template data.
The template coordinate calculation unit 5 converts the template data 13 based on the matching candidate information 14 from the matching candidate output unit 4. The matching candidate information 14 includes center coordinates x, y, a rotation angle θ, and an enlargement factor M as conversion parameters for the template data 13.

For example, as shown in FIG. 4A, the center positions x and y are coordinates serving as a reference for a feature point group including positive points and negative points in a matching value calculation process with the edge image 11, for example, jaws in a human face. New template data having a center position at designated x and y is obtained.
The rotation angle θ is a conversion parameter indicating the amount of rotation of the feature point group. For example, when the template data 13 indicates a face outline, the feature point group indicating the outline is rotated by θ around a predetermined origin coordinate. New template data is obtained.

Further, the enlargement ratio M is a conversion parameter indicating the degree of enlargement / reduction of the template data 13, for example, as shown in FIG. 4B. New template data in which the feature point group is enlarged / reduced by the enlargement ratio M is obtained.
The coordinate information of the point sequence P of the feature point group constituting the template data 13, that is, p1 to pn is given in advance by the equation (1) in FIG. 4C, and the equation (2) based on the conversion parameter. ) And Equation (3) are used to perform affine transformation on the point sequence P, and the new coordinate information obtained by the transformation becomes the point sequence H of the feature point group of the template data 15, that is, h1 to hn.

[Matching value calculation process]
Next, a matching value calculation method according to the present embodiment will be described with reference to FIG. FIG. 5 is a flowchart showing the matching value calculation processing according to the first embodiment of the present invention. In the following, a case where a matching value between the two processing regions is calculated using an image of one processing region set in the edge image 11 and the template data 15 will be described as an example.
First, the matching calculation processing unit 6 reads the image data of the processing region from the edge image 11 (step 100), and sets the matching value m to an initial value (m = 0) (step 101).

Next, an arbitrary positive point h is selected and read from the template data 15 (step 102). Then, the gradation value g of the pixel at the position corresponding to the coordinate information hx, hy of the positive point h in the processing area image is acquired and calculated as an evaluation value corresponding to the positive point h (step 103). The value g is added to the matching value m (step 104).
In this way, the above steps 102 to 104 are repeatedly executed for all positive points h (step 105: NO).

  In step 105, when all positive points h are selected and the positive point evaluation process is completed (step 105: YES), an arbitrary negative point h is read from the template data 15 (step 106). Then, a gradation value g of a pixel at a position corresponding to the coordinate information hx, hy of the negative point h in the processing region image is acquired, and a value L-g obtained by subtracting this from the gradation number L of the edge image 11 is obtained. The evaluation value corresponding to the negative point h is calculated (step 107), and this evaluation value L-g is added to the matching value m (step 108).

In this way, the above steps 106 to 108 are repeatedly executed for all negative points h (step 109: NO), and when all negative points h are selected and the negative point evaluation process is completed (step 109). :)), the normalized matching value is calculated by dividing the obtained matching value m by the number N of positive points and negative points (step 110), and the series of matching value calculation processes is terminated.
Thereby, the obtained matching value m takes a value from 0 to 1, and a larger value indicates that the matching between the processing region image and the template data 15 is higher.

As described above, in the present embodiment, template data including positive points indicating edge positions of the target image and negative points indicating positions without the edges of the target image are used, and each positive point and negative point are included in the processing region image. Since the matching value is calculated according to the positional relationship with each existing edge, it is possible to search for the edge position of the target image using a template with an extremely small amount of data, and recognize edges other than the target image. The target image area can be extracted with high accuracy.
Therefore, the processing time required for the matching value calculation process can be greatly shortened as compared with the conventional case where a plurality of templates are used or a grayscale image is used as the template data, and a memory for storing the template data. The capacity can be greatly reduced.

Further, when calculating the matching value, for each positive point and negative point, an evaluation value is calculated based on the gradation value of the pixel of the processing area image corresponding to the position of each point, and the matching value is calculated from these evaluation values. Therefore, the matching value can be calculated only by the calculation for the gradation value of the pixel of the processing area image, and the processing can be simplified.
In this case, more specifically, for each positive point, the gradation value of the pixel corresponding to the position of the positive point is calculated as an evaluation value, and the number of gradations of the edge image for each negative point. Since the value obtained by subtracting the gradation value of the pixel corresponding to the position of the negative point from is calculated as the evaluation value, and the matching value is calculated from the sum of these evaluation values, the calculation of the matching value is only the addition / subtraction process. The matching value can be calculated in a very short time.

[Template matching process]
Next, with reference to FIG. 6, a template matching process will be described as an operation of the target image region extraction apparatus according to the first embodiment of the present invention. FIG. 6 is a flowchart showing the template matching process according to the first embodiment of the present invention.
First, the image input unit 1 takes in the input image 10 to be processed, generates an edge image 11 (step 120), and holds the edge image 11 in the image holding unit 2 (step 121).

Next, the matching candidate output unit 4 selects a conversion parameter such as a center position, a rotation angle, and an enlargement ratio by matching candidate selection processing using a random generation function and outputs it as matching candidate information 14 (step 122). .
The template coordinate calculation unit 5 converts the template data 13 read from the template data holding unit 3 in advance based on the matching candidate information 14 and outputs the converted template data 15 (step 123).

  The matching calculation processing unit 6 reads a processing region image corresponding to an arbitrary processing region from the edge image 11 of the image holding unit 2 (step 124), and performs the above-described matching value calculation processing of FIG. Perform (step 125). Then, the matching value obtained for each processing region image by this matching value calculation processing is output as the calculation result 16 together with the region information indicating the processing region.

  The target area specifying unit 7 compares the matching value included in the calculation result 16 from the matching calculation processing unit 6 with a preset reference value (step 126), and no matching value exceeding the reference value is found. In such a case (step 126: NO), only when there is an unprocessed processing area (step 127: YES), the process returns to step 124 to shift to a matching process for a new processing area.

At this time, when there is no unprocessed processing area and the matching process using the template data 15 is completed (step 127: NO), for example, the used matching candidate is determined only when there is an unprocessed matching candidate. If the number has not been reached (step 128: YES), the process returns to step 122 and shifts to a process for generating the template data 15 using a new matching candidate.
On the other hand, when there is no unprocessed matching candidate, for example, when the number of used matching candidates reaches a predetermined number and the matching processing for all the matching candidates is completed (step 128), the desired target image is the input image 10 As a result, the series of template matching processing is terminated.

When a matching value exceeding the reference value is found in step 126 (step 126: YES), the target area specifying unit 7 is an area in which the processing area from which the matching value is obtained includes a desired target image area. It identifies that there is, and outputs processing area information 17 indicating the processing area (step 129).
The target area information extraction unit 8 grasps the reference position of the processing area image on the input image 10 based on the processing area information 17 from the target area specifying unit 7, and based on the template data 15, for example, the leftmost of the processing area A rectangular area surrounded by the points, the uppermost point, the rightmost point, and the lowermost point is grasped, and the target area information 18 is generated and output from these pieces of information (step 130), and a series of template matching processes is terminated.

  FIG. 7 shows the extraction result of the face area according to this embodiment. In the result of FIG. 15 according to the prior art described above, since the trunk of the tree has a color close to the skin color and the surface is rough, many edges appear as noise on the edge image of the skin color extraction region, and there is a face template there. 303 matched. According to the present embodiment, since the template data is composed of positive points and negative points, the template is not caught by noise as shown in FIG. The face template 202 matches correctly.

  FIG. 8 shows the extraction result of the corner region according to this embodiment. In the result of FIG. 16 according to the prior art described above, the corner template 313 to the wrong region created by the two triangles has been matched. According to the present embodiment, since the template data is composed of positive points and negative points, as shown in FIG. 8, extra edges formed by two triangles, that is, edges other than the target image are recognized by the negative points. Thus, the difference from the desired corner region is considered in the matching value, and the corner template 212 composed of positive points and negative points is correctly matched to the desired corner region 211.

  Further, in the present embodiment, a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data are randomly generated as matching candidate information, and each positive point and negative of the template data are generated based on this matching candidate information. Since the coordinates of the points are converted and new template data used for calculating the matching value is generated, there is a possibility that a large number of types of target images having different positions, rotation angles, or sizes may be included in the input image 10. Even if there is, a desired target image area can be efficiently extracted from such a vast search space with a small amount of template data.

In the above, FIG. 2 and FIG. 3 are shown as configuration examples of the template data, but the present invention is not limited to this.
For example, as template data, a positive point may be arranged at the edge of the target image and a negative point may be arranged so as not to overlap other edges of the target image existing around the edge. As a result, it is possible to avoid a case where other edges of the target image that are not used for specifying the target image by positive points are recognized as negative edges other than the extracted image, and template matching can be performed with higher accuracy. It can be carried out.

At this time, a negative point may be additionally arranged inside the region formed by the edge of the target image. As a result, when there are few other edges of the target image inside the area, the misperception due to the negative points is avoided, and edges other than the extracted image can be recognized by the negative points, and a relatively small number Matching accuracy can be further improved by simply adding negative points.
Alternatively, a negative point may be additionally arranged outside the area formed by the edge of the target image. As a result, when there are few other edges of the target image outside the region, the above misidentification due to the negative point is avoided, and edges other than the extracted image can be recognized by the negative point, and a relatively small number Matching accuracy can be further improved by simply adding negative points.

  Further, as other template data, data in which negative points are arranged around these positive points along the shape formed by the positive points arranged on the edge of the target image may be used. Thereby, the edge of the target image can be efficiently identified with a small number of positive points and negative points, and the edge of the target image can be effectively matched with a template having a small amount of data.

  As another template data, when positive points are arranged in a region where an edge of the target image exists, positive points may be arranged at a density according to the ratio of the appearance of the edge in the region. As a result, the number of positive points can be adjusted according to the amount of edges to be specified by positive points, and matching with the edges of the target image can be performed effectively with a template having a small amount of data.

  As another template data, when negative points are arranged in a region existing around the edge of the target image, the negative points may be arranged at a density corresponding to the ratio of the edges other than the target image appearing in the region. Good. Thereby, the number of negative points can be adjusted according to the amount of other edges to be recognized at the negative points, and the edges of the target image can be effectively matched with a template having a small amount of data.

  Further, when the template matching method or the target image region extraction device according to the present embodiment is used when extracting a human face image region from an input image, the target image is a human face image, and the person image is an edge of the target image. It is only necessary to use an edge indicating the lower contour of the face image. Thus, since the lower contour from which a relatively clear edge is obtained is used in the human face image, the region of the human face image is efficiently obtained with high accuracy. Can be extracted.

Further, as template data, face template data having positive points indicating positions where edges indicating the lower contour of the human face image exist and negative points indicating positions where edges indicating the lower contour of the human face image are not present. It can be used, and it can be avoided that the face template data is matched to an area other than the human face image, and the human face image area can be efficiently extracted with high accuracy.
At this time, a semi-elliptical shape may be used as an edge indicating the lower outline of the human face image, and the face template data can be easily configured. Compared to using a mosaic face template or an ellipse-like contour edge of the entire face, the number of components of the template can be reduced, so that the matching processing time can be shortened. .

Furthermore, the positive points of the face template data may be arranged at a high density in the cheek outline region of the human face image and may be arranged at a low density in the jaw outline region of the human face image, and there are edges other than the human face image. Even if the edge of the chin contour that is easy to do is not clear, the human face image region can be extracted with high accuracy.
The negative points are arranged at a high density in the cheek contour region of the human face image out of the region formed by the edge indicating the lower contour of the human face image and low in the jaw contour region of the human face image. Even when the edge of the skin color area is taken from the color image and the edge image including the face area is created, the chin and neck are joined and the chin edge is not clear. The human face area can be extracted with high accuracy.

[Second Embodiment]
Next, with reference to FIG. 9, a template matching method according to a second embodiment of the present invention and a target image region extraction apparatus using the same will be described. FIG. 9 is a block diagram showing a configuration of a target image area extracting apparatus according to the second embodiment of the present invention.
In the first embodiment described above, the case of selecting a random candidate when selecting a matching candidate has been described. In the present embodiment, a case will be described in which matching candidates are selected based on a genetic algorithm (GA).

  In the target image region extraction apparatus shown in FIG. 9, the above-described configuration is the same as that described above except that a matching candidate output unit 4A and a matching calculation processing unit 6A are provided instead of the matching candidate output unit 4 and the matching calculation processing unit 6 in FIG. It has the same configuration and uses the same template data as described above, and the same or equivalent parts as in FIG.

The matching candidate output unit 4A randomly selects conversion parameters such as a center position, a rotation angle, and an enlargement ratio when matching the template data 13 with the edge image 11 based on a genetic algorithm, and outputs it as matching candidate information 14. Functional means.
Using the template data 15 from the template coordinate calculation unit 5, the matching calculation processing unit 6 </ b> A sequentially performs the matching value calculation processing, which will be described later, on the edge image 11 read from the image holding unit 2, so This is a functional means for calculating a matching value for each set processing area and outputting it as a calculation result 16 together with area information of the processing area. At this time, in order to adjust the genetic algorithm, the obtained matching value is output to the matching candidate output unit 4A.

[Matching candidate selection process based on genetic algorithm]
Next, with reference to FIG. 9 and FIG. 10, the matching candidate selection process based on the genetic algorithm in the matching candidate output part 4A concerning this Embodiment is demonstrated. FIG. 9 is a block diagram illustrating a configuration example of the matching candidate output unit 4A. FIG. 10 is a configuration example of chromosome information used in the genetic algorithm.

  A genetic algorithm is information about the genetic mechanism of an organism, such as crossover that generates a new individual from multiple individuals, mutations that change part of the chromosomal information, or even an individual's wrinkle according to some criteria. This is a method for obtaining the optimal solution from existing information by incorporating it into the processing technology (for example, see Takeshi Yasui / Tomoharu Nagao, “Genetic Algorithm”, Shoshodo, ISBN4-7856-9046-1 C3055, etc.) .

  FIG. 10 is a block diagram illustrating a configuration example of the matching candidate output unit 4A. As a functional means for realizing such a genetic algorithm, the matching candidate output unit 4A includes an individual group holding unit 41, a parent individual designating unit 42, a crossover / mutation processing unit 43, a replacement target, as shown in FIG. A selection unit 44 and an individual replacement processing unit 45 are included.

Next, with reference to FIG. 12, the matching candidate information generation process according to the present embodiment will be described.
The individual group holding unit 41 holds in advance a plurality of individuals having chromosome information including conversion parameters such as a center position, a rotation angle, and an enlargement ratio that determine template data conversion. FIG. 11 shows a configuration example of an individual (chromosome information). In the configuration example of the individual 51, the x-coordinate 61 and y-coordinate 62 indicating the center position, the rotation angle θ63, and the enlargement factor M64 are each represented by a binary bit string and connected.

The parent individual designating unit 42 generates address information 52 at random and outputs the address information 52 to the individual group holding unit 41, so that any one of the individual held in the individual group holding unit 41 in advance is set as a parent individual. Specify (step 150). In addition to the random information, the address information 52 may be specified in an order having regularity, or may be selected with a probability corresponding to an evaluation value such as matching effectiveness of each individual.
The crossover / mutation processing unit 43 receives a plurality of individuals 51 selected by the address information 52 from the individual group holding unit 41, and determines them as child individuals based on a genetic algorithm such as crossover or mutation with respect to the parent individual. A new individual called is generated (step 151), and parameters included in the chromosome information of the child individual are output as matching candidate information 14 (step 152).

As a result, the template coordinate calculation unit 5 converts the template data 13 based on the conversion parameters included in the matching candidate information 14 from the matching candidate output unit 4A to generate new template data 15.
Then, the matching calculation processing unit 6A executes matching value calculation processing similar to that described above based on the template data 15, calculates the matching value, and outputs the calculation result 16 to the target region specifying unit 7. As a result, the target region specifying unit 7 and the target region information extracting unit 8 perform the same processing as described above, and desired target region information 18 is obtained.

Thereafter, the matching calculation processing unit 6A feeds back the matching value 19 obtained as described above to the matching candidate output unit 4A.
In the individual replacement processing unit 45 of the matching candidate output unit 4A, the individual held in the individual group holding unit 41 is evaluated based on the matching value 19 fed back from the matching calculation processing unit 6A. Replace with a sex individual.

At this time, the replacement target selection unit 44 selects, as the replacement candidate individual 54, the one with the lowest matching value obtained when using these individuals among the individuals 51 held in the individual group holding unit 41, The individual replacement processing unit 45 is notified (step 153). As for the matching value of each solid, a matching value with the edge image 11 or a predetermined sample edge image is obtained using template data obtained by performing coordinate conversion with parameters included in the solid chromosome information in advance. It may be left.
The individual replacement processing unit 45 compares the matching value of the replacement candidate individual 54 with the fed-back matching value 19 of the child individual (step 154).

Here, when the matching value 19 of the child individual is higher than the matching value of the replacement candidate individual 54 (step 155: YES), a replacement instruction 55 is output to replace the replacement candidate individual 54 with the child individual. In response to this, the individual group holding unit 41 replaces the replacement candidate individual 54 with the child individual having high matching effectiveness (step 154). As a result, the individual is trapped, and the series of matching candidate information generation processing ends.
If the matching value of the child individual is not higher than the matching value of the replacement candidate individual 54 (step 155: NO), the child individual with low matching effectiveness is discarded, that is, the trap is performed, and the series of matching candidate information generation processing ends. To do.

Normally, it is unclear how the extracted image in the input image matches efficiently with the template data converted by what center position, rotation angle, and magnification, and it is possible to find conversion parameters effective for matching early, This is an important issue for shortening the extraction processing time.
In this embodiment, since the matching candidate information is generated using the genetic algorithm, the matching is performed using the parent individual selected by the address information 52 as a clue from among the conversion parameters having a huge number of combinations. Effective individuals can be evolved to find desired conversion parameters efficiently.

Therefore, when using template data generated by changing each conversion parameter in turn, compared to using template data generated based on random conversion parameters, template matching necessary to find the desired extracted image The number of processes can be greatly reduced, and the extraction processing time can be greatly shortened.
In addition, the individual with the lowest matching value is selected as the replacement candidate among the individuals or the parent individual, and if the matching value of the child individual is higher than the matching value of the replacement candidate, the child individual is retained instead of the replacement candidate Therefore, the matching value of the individual or the whole parent individual can be improved, and an optimal conversion parameter can be found with higher efficiency.

  Note that the individual replacement process is not limited to the above process procedure, and other process procedures used in the genetic algorithm may be used. For example, the lifetime information of each individual may be added to the chromosome information, and the individual may be deleted according to the arrival of the lifetime, and when selecting a parent individual from the individual group, according to the matching value of each individual Individuals having a high matching value with probability may be preferentially selected.

It is a block diagram which shows the structure of the target image area extraction apparatus concerning the 1st Embodiment of this invention. It is an example of composition of template data (face outline). It is another example of composition of template data (face outline). It is explanatory drawing which shows the conversion process of template data. It is a flowchart which shows the matching value calculation process concerning the 1st Embodiment of this invention. It is a flowchart which shows the template matching process concerning the 1st Embodiment of this invention. It is the extraction result (face area) by the target image area extraction device concerning a 1st embodiment of the present invention. It is the extraction result (corner area | region) by the target image area extraction apparatus concerning the 1st Embodiment of this invention. It is a block diagram which shows the structure of the target image area extraction apparatus concerning the 2nd Embodiment of this invention. It is a structural example of the matching candidate output part concerning the 2nd Embodiment of this invention. It is an example of composition of an individual (chromosome information). It is a flowchart which shows the matching candidate information generation process concerning the 2nd Embodiment of this invention. It is explanatory drawing which shows the conventional template matching process. It is an example of composition of conventional template data (mosaic face template). It is the extraction result (face area) by the conventional object image area extraction technique. It is the extraction result (corner area | region) by the conventional object image area | region extraction technique.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 ... Image input part, 2 ... Image holding part, 3 ... Template data holding part, 4, 4A ... Matching candidate output part, 5 ... Template coordinate calculation part, 6, 6A ... Matching calculation process part, 7 ... Target image position specification , 8 ... Target area information extraction unit, 10 ... Input image, 11 ... Edge image, 13, 15 ... Template data, 14 ... Matching candidate information, 16 ... Calculation result, 17 ... Processing area information, 18 ... Target area information, 19 ... matching value, 21 ... positive point, 22, 22A, 22B ... negative point, 41 ... individual group holding unit, 42 ... parent individual designation unit, 43 ... crossover / mutation processing unit, 44 ... replacement target selection unit, 45 ... Individual replacement processing unit 51... Individual, 52. Address information, 54. Replacement candidate individual, 55. Replacement instruction, 61... X coordinate, 62.

Claims (23)

Using a processing area image in an arbitrary processing area acquired from the edge image of the input image and template data indicating the shape characteristics of the target image, a matching value indicating the matching between the processing area image and the target image is obtained. In the template matching method for calculating and specifying the region of the target image in the input image based on the matching value,
The template data consists of a positive point indicating a position where the edge of the target image exists in the processing area and a negative point indicating a position where the edge does not exist in the processing area,
A template matching method comprising: a first step of calculating the matching value according to a positional relationship between each positive point and negative point and each edge existing in the processing region image. The template matching method according to claim 1,
The edge image is composed of a plurality of pixels each representing an edge image included in the input image with gradation values,
The first step includes, for each positive point and negative point, a second step of calculating an evaluation value based on a gradation value of a pixel of the processing region image corresponding to the position of each point, and A template matching method comprising: a third step of calculating the matching value from evaluation values of positive points and negative points. The template matching method according to claim 2, wherein
The second step calculates, for each positive point, a gradation value of a pixel corresponding to the position of the positive point in the processing region image as an evaluation value, and for each negative point, Calculating a value obtained by subtracting the gradation value of the pixel corresponding to the position of the negative point in the processing region image from the number of gradations of the edge image as an evaluation value,
The template matching method, wherein the third step includes a step of calculating the matching value from the sum of the evaluation values calculated in the second step. The template matching method according to claim 1,
The first step includes a fourth step of generating a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data as matching candidate information, and each of the template data based on the matching candidate information. A template matching method, further comprising: a fifth step of converting the coordinates of the positive point and the negative point and generating new template data used for calculating the matching value. The template matching method according to claim 4, wherein
The fourth step includes a step of holding a plurality of individuals having chromosome information including a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data; A step of designating as an individual, a step of generating a child individual from the parent individual based on a genetic algorithm, and a step of outputting a parameter included in chromosome information of the child individual as the matching candidate information, Template matching method. The template matching method according to claim 5, wherein
In the fourth step, among the held individuals, the one having the lowest matching value obtained using new template data generated based on the matching candidate information of the individual is selected as a replacement candidate. And when the matching value obtained using the new template data generated based on the matching candidate information of the child individual is higher than the matching value of the replacement candidate, the child individual is substituted for the replacement candidate A template matching method, further comprising the step of holding as a new individual. The template matching method according to claim 1,
The template matching method, wherein the negative points are arranged so as not to overlap other edges of the target image existing around an edge of the target image. The template matching method according to claim 7, wherein
The template matching method, wherein the negative point is arranged inside an area formed by an edge of the target image. The template matching method according to claim 7, wherein
The template matching method, wherein the negative point is arranged outside an area formed by an edge of the target image. The template matching method according to claim 1,
The template matching method, wherein the negative points are arranged around a shape formed by the arrangement of the positive points. The template matching method according to claim 1,
The template matching method, wherein the positive points are arranged at a density corresponding to a ratio of appearance of the edge of the target image in an area where the positive points are arranged. The template matching method according to claim 1,
The template matching method, wherein the negative points are arranged at a density corresponding to a ratio of edges other than the target image appearing in an area where the negative points are arranged. The template matching method according to claim 1,
The template matching method, wherein the target image is a human face image, and an edge of the target image is an edge indicating a lower contour of the human face image. The template matching method according to claim 1,
The template data includes face template data having a positive point indicating a position where an edge indicating a lower contour of a human face image is present and a negative point indicating a position where an edge indicating a lower contour of the human face image is not present. A template matching method characterized by that. The template matching method according to claim 14, wherein
A template matching method using a semi-elliptical shape as an edge indicating a lower contour of the human face image. The template matching method according to claim 14, wherein
The template matching method, wherein the positive points are arranged at a high density in a cheek outline region of the person face image and arranged at a low density in a jaw outline region of the person face image. The template matching method according to claim 14, wherein
The negative points are arranged at a high density in the cheek contour region of the human face image out of the region formed by the edge indicating the lower contour of the human face image, and in the jaw contour region of the human face image. A template matching method characterized by being arranged at a low density.   18. A target image region extraction device that identifies a region of a human face image included in an input image using the template matching method according to claim 1. An image input unit for generating an edge image indicating an outline of an object from the input image;
An image holding unit for storing and holding the edge image;
A template data holding unit for storing and holding template data indicating the shape characteristics of the target image to be extracted;
A matching candidate output unit that generates a plurality of types of parameters used for coordinate conversion of the template data as matching candidate information;
A template coordinate calculation unit that converts the template data read from the template data holding unit based on the matching candidate information to generate new template data; and
A matching calculation processing unit that calculates a matching value indicating a match between the processing region image extracted from the processing region sequentially set on the edge image of the image holding unit and the template data generated by the template data coordinate conversion unit; ,
When the matching value obtained from the matching calculation processing unit exceeds a predetermined reference value, a target region specifying unit that specifies the processing region from which the matching value is obtained as a region including the target image;
An area information extraction unit that outputs area information related to the target image area based on the coordinate position of the identified processing area and the template data;
The template data consists of a positive point indicating a position where the edge of the target image exists in the processing area and a negative point indicating a position where the edge does not exist in the processing area,
The template coordinate calculation unit calculates the matching value according to a positional relationship between each positive point and negative point and each edge existing in the processing region image. The target image region extraction device according to claim 19,
The edge image is composed of a plurality of pixels each representing an edge image included in the input image with gradation values,
The template coordinate calculation unit calculates an evaluation value for each positive point and negative point based on a gradation value of a pixel of the processing region image corresponding to the position of each point, and the positive point and the negative point. The target image area extracting apparatus, wherein the matching value is calculated from the evaluation value. The target image region extraction device according to claim 20,
The template coordinate calculation unit calculates, as an evaluation value, a gradation value of a pixel corresponding to the position of the positive point in the processing region image for each positive point, and for each negative point, the edge image A value obtained by subtracting the gradation value of the pixel corresponding to the position of the negative point in the processing area image from the number of gradations of
The target image area extracting apparatus, wherein the matching value is calculated from a sum of the evaluation values. The target image region extraction device according to claim 19,
The matching candidate output unit
An individual group holding unit for storing and holding a plurality of individuals having chromosome information including a plurality of types of parameters used for coordinate conversion of each positive point and negative point of the template data;
A parent individual designating unit that designates as a parent individual any one of the individuals held in the individual group holding unit;
A target image region extraction apparatus comprising: a new individual generation unit that generates a child individual from the parent individual based on a genetic algorithm and outputs a parameter included in chromosome information of the child individual as the matching candidate information . The target image region extraction device according to claim 22,
The matching candidate output unit
A step of selecting the lowest matching value obtained using new template data generated based on matching candidate information of the individual among the individuals held in the individual group holding unit as a replacement candidate; ,
When the matching value obtained using the new template data generated based on the matching candidate information of the child individual is higher than the matching value of the replacement candidate, the child individual is replaced with the new replacement candidate. A target image area extracting apparatus, further comprising a step of holding the object as an individual.