JP2009289295A - Image extraction method and apparatus - Google Patents

Abstract

PROBLEM TO BE SOLVED: To automatically extract a desired object with high accuracy.
[Solution]
The feature quantity extraction device 20 obtains the feature quantity distribution of the input image and binarizes it. The template data generation device 22 automatically generates a plurality of template sets having different sizes from the selected template data. The template scanning device 26 raster-scans each template on the image at a sampling pitch corresponding to the size, and obtains the first shape conformance at each location. The template graphic element deforming device 30 moves a representative point of a certain graphic element constituting the template graphic within the movement range, and generates a new curve segment connecting the representative points after the movement. When the shape conformity evaluation device 32 evaluates the second shape conformance at each portion, the representative point moves so that the second shape conformance is greater than or equal to a predetermined reference value. The boundary line generation device 34 generates a line connecting the representative points.
[Selection] Figure 2

Description

  The present invention relates to an image extraction method and apparatus, and more specifically, to an image extraction method and apparatus for extracting an object of a specific category from an image, and a storage medium.

JP-A-8-7107 JP-A-8-16779 JP 7-334675 A Japanese Patent Publication No. 7-34219 JP-A-3-240884 JP 7-225847 A JP-A-6-251149 JP-A-7-107266 JP-A-8-7075 JP-A-8-77336 Japanese Examined Patent Publication No. 6-4068 Japanese Patent Publication No. 8-20725 Japanese Patent No. 2642368 Japanese Patent Laid-Open No. 9-50532 JP-A-6-168331 JP-A-5-242160

M. Kass, A. Witkin, D. Terzopoulos, Snakes, "Active Contour Models, International Journal of Computer Vision, pp.321-331, 1988 A.De Bimbo and P.Pa1a, "Visua1 Image Retrieval by Elastic Matching of User Sketches", IEEE Trans. On Pattern Analysis and Machine Intelligence, vol. 19, pp. 121-132, 1997 L.H.Steib and J.S.Duncan, "Boundary Finding with Parametrically Deformable Mode1s", IEEE Trans. On Pattern Analysis and Machine Intelligence, vol. 14, pp. 1061-1075, 1992 F. S. Cohen, Z. Huang, Z. Yang, "Invariant Matching and Identification of Curves Using B-Splines curve Representation", IEEE Trans. On Image Processing, vo1. 4, pp. 1-10, 1995 G. C. H. Chuang and C. C. J. Kuo, "Wave1et Descriptor of Planar Curves: Theory and App1ications", IEEE Trans. On Image Processing, vol. 5, pp. 56-70, 1996

  Conventionally, various methods are known as processing for extracting a specific subject or object from an image. The first method is to select a region having a predetermined range of color component values (or shade values) including pixel values of an object specified by the user or a point on the background, or specify the region of the extracted subject. A method of repeating (JP-A-8-7107, JP-A-8-16779, JP-A-7-334675, JP-B-7-34219, etc.), and a rough rough contour including an outline to be extracted A method of specifying a line region or a local region and obtaining and cutting out a target boundary contour line by processing such as thinning or clustering within the specified region (Japanese Patent Laid-Open Nos. 3-240884 and 7-225847, JP-A-6-251149, JP-A-7-107266, JP-A-8-7075, JP-A-8-77336, JP-B-6-4068 and JP-B-8. 20,725 JP, etc.) there is.

  As a second method, a closed curve (or polygonal boundary) is set so as to roughly surround the image portion to be cut out, and a cutout mask image that is almost similar to the shape of the target object is generated using only color component information. There is a method (Japanese Patent No. 2642368).

  As a third method, image dictionary data obtained by mosaicing an input grayscale image by a coarse / fine search using multiple resolutions in a configuration (such as JP-A-9-50532) that detects a target object from an image and extracts the contour thereof. A dynamic contour method (M. Kass, A. Witkin, D. Terapoulos, Snakes, “Active Control Models, International Journal of Computer” that obtains the position and size of a target object with reference to FIG. There is a method of extracting a contour using Vision, pp.321-331, 1988).

  In addition, as a technique that can be used to determine the presence or absence of a specific object in an image, or to search and extract an image in which a specific object exists from a database, a template prepared in advance is scanned on the image, and each position A method of calculating a matching level in the image, and searching for a position where the matching level is equal to or higher than a predetermined threshold (Japanese Patent Laid-Open No. 6-168331), inputting a region and a component name of a component in an image when creating an image database In addition, a method of searching for an image having a predetermined feature at a high speed (Japanese Patent Laid-Open No. 5-242160), a degree of similarity with an example given by a user (such as a sketch and an image) is obtained, and the degree of similarity is high Image retrieval method (Reference 1: A. De Bimbo and P. Pa1a, "Visua1 Image Retrieval by Elastic M , “Attaching of User Sketches”, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 19, pp. 121-132, 1997, etc., and a method for detecting a boundary line (Reference 2: L). Steib and JS Duncan, “Boundary Finding with Parametrically Deformable Modes 1”, IEEE Trans. On Pattern Analysis and Machine Int.

  A method using a spline curve as a method for modeling a curve parametrically (FS Cohen, Z Huang, Z Yang, "Invariant Matching and Identification of Curves Reply E". Image Processing, vo1.4, pp. 1-10, 1995), a method using a Fourier descriptor (Literature 2), and a method using a wavelet descriptor (G. C. H. C. Chang and C. C. J. J. et al. Kuo, "Wave1et Descriptor of Planar Curves: Theory and Applications", IEEE Trans. On Image Processing, vol. 5, pp. 56-70, 1996).

  However, since the image extraction method according to the first method described above requires an operation based on a relatively detailed instruction from the user, the process of searching for and extracting (cutting out) an object having a specific shape from the image is automated. Can not.

  In the second method typified by a method of specifying a closed curve or the like that roughly encloses an image part to be cut out (Japanese Patent No. 2642368), the ratio of the area of the region having the same color component included in the closed curve is used. If there is an area in the background within the closed curve that has the same color as the subject, or if the closed curve area has an area that is twice or more the area to be cut out, erroneous extraction such as extraction of the background portion is likely to occur. There is a problem and lacks versatility.

  In the contour detection apparatus described in Japanese Patent Laid-Open No. 9-50532 showing the third method, the so-called dynamic contour method is used, so that the background portion (portion other than the extraction target) of the input image has a complex texture pattern. In many cases, it is difficult to reflect the complexity of the contour line to be extracted. That is, there is a problem that an unnatural uneven shape deviating from the original contour shape is extracted.

  The contour extraction method described in Document 2 assumes a probabilistic model in which the contour model parameters and the contour model error are assumed to be Gaussian distributions. Therefore, when those distributions are actually non-Gaussian, the correct contours are assumed. Is difficult to extract efficiently, and the tolerance for the difference between the contour model and the shape of the extraction target is low.

  It is an object of the present invention to provide an image extraction method and apparatus that solves such problems.

  It is another object of the present invention to provide an image extraction method and apparatus that can extract a desired image with higher accuracy at a higher speed.

  The image extraction method according to the present invention provides a predetermined evaluation function value relating to at least one of a first matching degree relating to a feature value between an input image and a local template and a second matching degree relating to a gradient of the feature value. A first matching step for performing a first matching process to be obtained; and executed when the evaluation function value of the first matching process is equal to or greater than a predetermined threshold value to obtain a distribution function value of edge points on the graphic element A second matching step for performing a second matching process for adding a representative point to a predetermined position in a section where non-edge points exist continuously for a certain length or longer, and each representative based on the result of the second matching process. A contour extracting step for moving a point and extracting a contour line connecting the representative points; and an image region extracting step for extracting an image region including the contour line.

  The image extraction apparatus according to the present invention obtains a predetermined evaluation function value related to at least one of a first matching degree related to a feature value between an input image and a local template and a second matching degree related to a gradient of the feature value. First matching means for performing a first matching process to be obtained and executed when an evaluation function value of the first matching process is equal to or greater than a predetermined threshold value to obtain a distribution function value of edge points on the graphic element Second matching means for performing a second matching process for adding a representative point to a predetermined position in a section where non-edge points exist continuously for a certain length or longer, and each representative based on the result of the second matching process. It comprises a contour line extracting means for moving a point and extracting a contour line connecting the representative points, and an image area extracting means for extracting an image area including the contour line.

  An image extraction method according to the present invention includes an image input step, a feature amount extraction step of extracting a feature amount distribution of an input image by the image input step, and a curve or a line connecting a plurality of representative points and the representative points. A template model input step for inputting a template model including a minute as a graphic element, and a template set having a graphic element substantially similar to the graphic element of the template model from the template model and generating a plurality of template sets having different sizes from each other A first matching for obtaining a predetermined evaluation function value relating to at least one of a first matching degree relating to the value of the feature quantity between the input image and the template and a second matching degree relating to a gradient of the feature quantity; A first matching step for performing processing, and a result of the first matching processing A template selection step of selecting one of the template sets based on the evaluation function value of the first matching process is equal to or greater than a predetermined threshold value, and obtaining a distribution function of edge points on the graphic element; A second matching step for performing a second matching process for adding the representative point to a predetermined position in a section where non-edge points exist continuously for a certain length or longer, and the representative point based on a result of the second matching process A representative point update step for moving the image, a template update step for generating an update template including a curved line or a line segment connecting the representative point after the movement and the representative point as a graphic element, and image data including the update template is extracted. And an image extraction step.

  An image extraction method according to the present invention includes an image input unit for inputting an image, a feature amount extraction unit for extracting a feature amount distribution of an input image by the image input unit, and a curve connecting a plurality of representative points and the representative points. Alternatively, template model input means for inputting a template model including a line segment as a graphic element, and a plurality of template sets having graphic elements substantially similar to the graphic element of the template model from the template model and having different sizes from each other are generated. A template set generating means for obtaining a predetermined evaluation function value relating to at least one of a first matching degree relating to the feature value between the input image and the template and a second matching degree relating to a gradient of the feature quantity; First matching means for performing the matching process and the tenth based on the result of the first matching process. A template selection means for selecting one of the rate sets, and when the evaluation function value of the first matching process is equal to or greater than a predetermined threshold value, a distribution function of edge points on the graphic element is obtained, and a fixed length Second matching means for performing a second matching process for adding the representative point to a predetermined position in a section where non-edge points exist continuously, and moving the representative point based on the result of the second matching process Representative point updating means, template update means for generating an update template that includes a curve or a line segment connecting the representative point after movement and the representative point as a graphic element, and image extraction for extracting image data including the update template Means.

  As a result, the complexity of the contour line shape to be extracted can be set for each location on the contour line by appropriately giving the position and number of representative points in advance, so that it has a predetermined category shape while retaining it. A target can be automatically and efficiently searched from an image, and the image data or contour line data can be extracted with high accuracy. Even when the background portion has a complex texture pattern, a specific shape can be stably searched and extracted without being affected by the influence. In particular, unique features on the shape to be extracted, for example, the shape of corners (corner portions) and the spatial arrangement of irregularities are maintained, and the extraction target in the input image for the template model shape is within the range. The deformation allowance can be increased.

  The movement range of the representative point is set in advance. The movement range of the representative point may be set in advance based on the position of another representative point. Thus, it is possible to efficiently search for and extract an object while maintaining an approximate shape without allowing any deformation of the graphic elements of the template.

  The first matching process is to obtain a predetermined evaluation function value related to at least one of the first matching degree related to the feature value between the input image and the template and the second matching degree related to the gradient of the feature value. In the first matching process, a predetermined evaluation function value relating to at least one of the first matching degree relating to the value of the feature quantity between the input image and the template and the second matching degree relating to the gradient of the feature quantity is obtained as a graphic element of the template. It is to obtain the above representative points and the points along the curve connecting them. Accordingly, a desired shape can be efficiently searched even under a complicated background.

  The second matching process is executed when the evaluation function value of the first matching process is equal to or greater than a predetermined threshold, and the first matching process moves the center of gravity position of the template and The evaluation function value is obtained by setting the movement range of each representative point so that the relative position to the representative point position is generally maintained. Thereby, a desired object can be efficiently searched from an image having an arbitrary background, and therefore image data of the object or its contour can be efficiently extracted.

  A curve connecting representative points is represented by a predetermined spline function passing through each representative point. Thus, an image or contour line having an arbitrary smoothness can be extracted from model data described with a small number of parameters.

  The representative point is added to a predetermined position based on the evaluation function value of the second matching process after the update template is generated, or the representative point is deleted. As a result, the model data is automatically modified so that it conforms to the contour shape portion of the input image having a complexity that does not fit the given model data. As a result, the range of the shape of the object that can be automatically extracted is greatly expanded with respect to one model data. Therefore, even if the deformation amount of the target belonging to the extraction category is relatively large, the number of corresponding model data can be limited to a small number.

  The evaluation function of the second matching process is a distribution function of edge points on the graphic element, and adds the representative point to a predetermined position in a section where non-edge points exist continuously for a certain length or more.

  The template model input step (means) includes a step (means) for selecting a basic template belonging to the extraction category. Thereby, the object which should be extracted from an input image can be searched only by selecting an extraction category, and the outline or image can be extracted.

  The gradient of the feature amount is an inclination of a line segment or a curve constituting the graphic element at a predetermined point on the graphic element of the template model, and the second feature amount represents the degree of coincidence of the inclination. Thereby, an image or a contour line is extracted so as to preserve the local shape of the template model at a certain level.

  The deformation mode is a geometric transformation including at least one of a perspective transformation and an affine transformation for all or part of the graphic elements of the template model. Thereby, the geometric phase of the local shape of a template model is preserve | saved, and an image or an outline can be extracted.

  The evaluation function is the sum of the edge ratio on the graphic element of the template or the distance between the feature amount gradient at each point on the graphic element and the edge intensity gradient at the point corresponding to each point on the edge data. Thereby, it is possible to handle the difference in shape data when the template model data is given as a grayscale image or the like.

  The graphic element is a contour line to be extracted. The graphic element may also be an image obtained by thinning out an image of a target to be extracted at a predetermined resolution, or an image obtained by thinning out an outline image of a target to be extracted at a predetermined resolution. In this way, by using the abstracted data related to the object to be extracted with the details omitted, it becomes possible to easily cope with various deformations of the object to be extracted.

  The graphic element is represented by a predetermined spline curve parameter. A graphic element is also represented by a predetermined Fourier descriptor or wavelet descriptor parameter. As a result, the data regarding the contour of the image to be extracted becomes compact, and the memory capacity required for storing the template data can be reduced. In addition, since a smooth shape, a complicated shape, and the like of an extraction target can be stored in advance as data for each core portion, a contour line regarding a desired target can be stably obtained even under various backgrounds.

  The movement range of the representative point is larger when the evaluation function value is equal to or greater than a predetermined threshold value, and when the representative point on the graphic element is a non-edge point related to the feature quantity, it is larger than when the representative point is an edge point related to the feature quantity. Thereby, the search range of the representative point can be set adaptively, and it is possible to easily cope with the difference in the background pattern and the variety of target shape conversion.

  The movement range is set so that the sign of the secondary differential value at the representative point of the contour line obtained at a predetermined resolution of the graphic element after the movement of each representative point is retained. As a result, it is possible to extract a contour line that retains local unevenness of the shape (a distinction between the degree of concave or convex).

  In the update step, the graphic element of the template model has at least one open end, and the open end position is moved based on the feature amount distribution after generation outside the update template or in the generation process, thereby updating the shape of the graphic element. Is done. Thereby, even if it is a target which has a partial shape with a high freedom degree of a shape, the outline and image corresponding to the shape change can be extracted with few template models.

  The movement position of the representative point is determined such that the edge ratio on the curve or line segment connecting the representative points after the movement becomes the maximum or a predetermined reference value or more. As a result, it is possible to extract a contour line having a high degree of matching with an edge distribution relating to the feature quantity of the input image (so-called gray level image edge strength and texture edge in the spatial frequency domain).

  The movement position of the representative point and the number of representative points are determined so that the predetermined information amount reference value of the updated template model for the feature amount distribution is maximized. As a result, it is possible to avoid adverse effects caused by the parameters of the template model approximating the input image with an excessively high order, for example, extraction of an uneven shape sensitive to noise and unnatural.

  A graphic element is represented by a parameter of a predetermined order Fourier descriptor or wavelet descriptor that is variable depending on the location. As a result, even with an extraction target or shape model in which a complicated shape portion and a simple shape portion are mixed, the shape can be approximated with desired accuracy and with a small number of parameters.

  The feature amount is a representative value of the local spatial frequency component that is a representative value of the local spatial frequency component. As a result, the texture boundary can be stably captured, and the outline and image of the target can be stably extracted even for a combination of an arbitrary background and a pattern of the extraction target.

  The representative point update step includes a step of obtaining a maximum likelihood estimation value of a predetermined local geometric transformation parameter for the template data that most closely matches the distribution of the feature amount. Thereby, it is possible to extract the outline of the extraction target belonging to the same category while eliminating the influence of noise and preserving the shape characteristics.

  The maximum likelihood estimate is a first evaluation function term consisting of a predetermined linear sum of prior probability distributions corresponding to a plurality of geometric transformation modes and a second evaluation that gives the posterior probability of the geometric transformation mode for the feature quantity. It is obtained as a geometric transformation parameter value that maximizes a predetermined evaluation function consisting of function terms. Thereby, the geometric transformation parameter optimum value can be estimated based on Bayes' law.

  According to the present invention, the template data is preliminarily given by executing the template data scanning and the conformity evaluation on the shape, and the deformation (movement range, shape constraint condition, local geometric transformation, etc.) given the constraint condition. It is possible to automatically search for an object that matches the given information from the image. In addition, the tolerance of deformation is high within a compatible range, and noise extraction and contour extraction can be performed.

  When deforming a template, an overall set of constraints on deformation (movement of representative points) is given, or a local geometric transformation is estimated that preserves the geometric phase, so global shape information Are always maintained and are not easily affected by local noise. Therefore, even if the background has a complicated pattern, extraction of an unnatural contour is effectively prevented.

It is a schematic block diagram of one Example of this invention. 2 is a schematic block diagram of an image processing device 16. FIG. It is a schematic diagram which shows an example of template data, and a movement range. It is a table | surface which shows the example of template data. It is an operation | movement flowchart of a present Example. 3 is a display screen example of the image display device 14. It is a schematic diagram of the example of description of the edge ratio on a thick line. It is a schematic diagram which shows the mode of the deformation | transformation of the template figure in the update template production | generation process process. It is a schematic diagram which shows the mode of the movement of the representative points P6 and P7 accompanying P5 having moved to P5 '. It is an operation | movement flowchart of the change part of the Example which changed the update template production | generation process (S7 of FIG. 5). It is an example of a human body template model. It is a flowchart which shows the estimation procedure of a geometric (affine) transformation parameter. It is a schematic diagram explaining the outline estimation procedure of the template model which has an indefinite part. It is a flowchart of the template update process in 3rd Example. It is an example of FIG.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

  FIG. 1 shows a schematic block diagram of an embodiment of the present invention. Reference numeral 10 denotes an image input device, 12 denotes an image storage device for storing image data and template model data, 14 denotes an image display device, 16 denotes an image processing device, and 18 denotes an instruction selection device including a pointing device such as a mouse. The image input device 10 includes an imaging device such as an image scanner or a digital camera, or an image data transfer device connected to an image database.

  In this embodiment, image data including an object to be separated and extracted from the background is input from the image input device 10 and stored in the image storage device 12. The image data stored in the image storage device 12 is displayed in a predetermined format at a predetermined position on the screen of the image display device 14.

  A schematic configuration of the image processing apparatus 16 is shown in FIG. 20 is a feature quantity extraction device that extracts the feature quantity of the input image, 22 is a template model selection apparatus, 24 is a template data generation apparatus that generates template data of multiple resolutions, and 26 is a template scan and a feature of the input image. A template scanning device that executes a first matching evaluation with a quantity; 28, a moving range / condition update setting device that updates and sets the moving range / condition of each representative point on the template; 30, an update template generation device; Is a shape matching degree evaluation apparatus that evaluates the shape matching degree after deformation by evaluating the shape fitting degree after deformation by the second matching process with the image feature amount, and 34 is a spline that smoothly connects the representative points of the update template A boundary line generating device that generates a boundary line of the graphic element by an interpolation curve, Border display device which displays superimposed on the input image on the screen of the device 14, 38 is a mask data generation device for generating mask data indicating a boundary inside region of updating template. Although not shown, a storage device for storing boundary lines and / or mask data of the update template is further provided.

  First, a template model and a parametric curve expression method used in this embodiment will be described.

  The template data is mainly composed of abstract graphic elements or representative image (graphic) patterns representative of extraction categories (person, car, fish, airplane, etc.), and typically outlines constituting them. The background including the data or its outline is given by a solid gray image or color image. The contour line data is not limited to representing the outer shape of the corresponding category, but may include main shape data constituting the category (for example, eyes, nose and mouth constituting a human face). Not too long.

  The contour lines of the graphic elements belonging to each category are composed of curves or line segments that pass between the representative points, and are preliminarily expressed parametrically by spline curves, Fourier descriptors, wavelet descriptors, and the like.

  For example, the entire contour model is composed of J spline curves, and the jth spline curve

ここに、ｊ＝０，１，・・・，Ｊである。また、Ｑ_N，m＋1（ｔ）は、

のように表わされる。Ｃ_Ｎ＝［Ｃ_ｘ，Ｎ，Ｃ_ｙ，Ｎ］は、Ｎ番目の制御点位置を示すベクトルである。 r _j (t) = [x _j (y), y _j (t)]
Is an m _{j -th} order B-spline with n _j +1 control points,

Here, j = 0, 1,..., J. Q _{N, m + 1} (t) is

It is expressed as C _N = [C _{x, N} , C _{y, N} ] is a vector indicating the Nth control point position.

と表現される。但し、

である。ｔは、弧長ｓと全周長Ｓを用いて、ｔ＝２πｓ／Ｓのように表わされる。フーリエ記述子を用いて曲線の一部を表現する場合には、その両端点で When using a Fourier descriptor,

It is expressed. However,

It is. t is expressed as t = 2πs / S using the arc length s and the total circumference S. When expressing a part of a curve using a Fourier descriptor,

  x (t) = x (2π−t)

y (t) = y (2πone t)
Therefore, b _k = d _k = 0.

ここで、

である。 When using wavelet descriptors,

here,

It is.

ここに、ｋ，ｍ，ｎは、０又は正の整数であり、関数φ，ψは、双直交３次スプライン関数等が用いられる。 Each wavelet function has periodicity and is defined as follows. That is,

Here, k, m, and n are 0 or a positive integer, and a bi-orthogonal cubic spline function or the like is used for the functions φ and ψ.

  Contour lines constituting the template are not composed of a contour line representing the shape to be extracted as a single closed curve, but are composed of partial contour lines having a shape representing the category to be extracted (for example, the same applicant as the present application). (Japanese Patent Laid-Open No. 7-320086) may be used.

  The distribution of representative points and the parameters of these curves (for example, the order of the B-spline function and the number of control points) express and reflect the complexity and smoothness of the shape of the object to be extracted. FIG. 3A shows an example of graphic elements constituting the template. The template data generation device 24 may generate this graphic element by extracting contour lines from the image data.

  As exemplified in FIGS. 3B and 4A, 4B, the template data includes representative point positions and data related to parameters such as spline curves (curve order and type) as well as representative values. Point movement range data or shape constraint conditions described later are given.

  Rather than explicitly representing the movement range at each representative point, the concave or convex shape in the vicinity of the representative point is simply retained, or the curvature is retained and no new loop is generated. Local shape conditions may be given and given as movement condition data for each representative point. In this case, the movement of the representative point is performed under the two conditions that the local shape condition thus determined is not violated and that the later-described goodness of fit regarding the shape of the updated template after the movement does not satisfy the reference value. The range is gradually expanded to search, and the movement of the representative point is stopped at a position where the fitness level is equal to or higher than the reference value.

とする。（ｘ_ｊ，ｙ_ｊ）は、ｊ番目の代表点位置を示す。数８は、代表点（ｘ_ｊ，ｙ_ｊ）の近傍の形状に関する凹凸及び曲率の保持されるべき範囲の概算値を示す。 As the shape constraint condition, for example, as described in the fourth line of FIG.

And (X _j , y _j ) indicates the j-th representative point position. Expression 8 shows an approximate value of the range in which the unevenness and curvature of the shape in the vicinity of the representative point (x _j , y _j ) should be maintained.

とする。これと形状拘束条件により、（ｘ_ｊ−１，ｙ_ｊ−１），（ｘ_ｊ，ｙ_ｊ）が定まれば、（ｘ_ｊ＋１，ｙ_ｊ＋１）は、数８及び数９を満たす範囲の平均値として求めることが出来る。数９でｄ_ｊは、点（ｘ_ｊ，ｙｊ）と（ｘ_ｊ＋１，ｙ_ｊ＋１）とを結ぶ線分長の基準値、μはその許容する変化幅の基準値をそれぞれ示す。 As a constraint on size, for example,

And If (x _j−1 , y _j−1 ) and (x _j , y _j ) are determined by this and the shape constraint condition, (x _{j + 1} , y _{j + 1} ) is the average of the range satisfying Equation 8 and Equation 9. It can be obtained as a value. In Equation 9, d _j represents a reference value of the length of the line segment connecting the points (x _j , yj) and (x _{j + 1} , y _{j + 1} ), and μ represents a reference value of the allowable change width.

  FIG. 3 shows the j−1, j, and j + 1th representative points, the parametric curves connecting them, and the movement ranges. The movement range data is given in advance as giving a deformation tolerance from the original template shape accompanying the movement of the representative points constituting the template. Each movement range generally differs depending on knowledge about the non-rigidity (elasticity, presence / absence of joints, etc.) and a priori shape of each part to be extracted, and can also be changed appropriately in the process of template deformation and update.

  For example, the head of a person usually has a convex shape approximated by a quadratic curve (elliptical shape) function, but the movement range of the representative points constituting this head does not generate a new concave portion due to the movement. It is determined on the condition. When the contour curve forming the head is expressed as a function of the arc length along the contour line, the occurrence of a recess is detected by the second-order differential value (or an approximate value corresponding thereto) being positive. .

  Therefore, the size and shape of the movement range of a certain representative point is such that when a representative point adjacent to that point is fixed, the curve connecting the representative points is in the vicinity of the representative point after the movement. (Approximate value) is determined to be in a non-positive range. Strictly speaking, this range changes relatively with the movement of the other representative points excluding the representative point. However, as the range in which the deformation amount is not large and the similarity of the shape is maintained, it is previously determined for each representative point. It is fixed and set (the size and shape of the range may be different for each representative point).

  An image extraction procedure in this embodiment will be described. FIG. 5 shows a flowchart of the operation. Image data is input from the image input device 10 such as a photographing unit, is stored in the image storage device 12, and is displayed on the screen of the image display device 14 as illustrated in FIG. 6 (S1). In FIG. 6, 40 is a screen of the image display device 14, 42 is an input image, 44 is template model image data, 46 is a target position confirmation indicator, 48 is an extraction instruction button, and 50 is a template scroll button.

  The feature quantity extraction device 20 obtains a feature quantity distribution (such as edge intensity distribution or information on the local spatial frequency at each point) of the input image, and binarizes it with a predetermined threshold (S2).

  The template selection device 22 displays the template model image data 44 on the display screen 40 of the image display device 14. When the user selects template data in the extracted category, information on the selected template data (for example, data illustrated in FIG. 4) is read (S3). By scrolling the display contents of the template model image data 44 from the list displayed in the template model image data 44 with the scroll button 50 to display a desired one and selecting it with the instruction selection device 18, one desired template model is displayed. Image data can be selected. For the extraction category, for example, the name of the extraction category may be verbally input by a voice input device such as a microphone and a voice recognition device. When the desired template data is selected by the user, the template data generating device 22 automatically generates a plurality (usually less than 10) of template sets having different sizes from the selected template data (S4).

  The template scanning device 26 raster-scans each template on the image at a predetermined sampling pitch (for example, one tenth of the width of the template figure) according to the size (S5), and the first scanning is performed at each location. The shape matching degree is obtained (S6). Specifically, as a parameter representing the degree of conformity of the shape, an edge on the outline of the graphic element on the template or on the bold line obtained by thickening the outline to a predetermined width (typically about 5 pixels) The sum of the inner products (absolute values) of the gradient vectors indicating the ratio of the points and the direction of the edge strength gradients at the edge points (or their distance) (or the edge points, the inner product value is the reference value) The ratio of the above points) is obtained.

  As illustrated in FIG. 7, the edge ratio on the thick line refers to the sampling point on the center line of the thick line and the minute point (thick line region cell) including the sampling point when the edge exists. Is the ratio of the number of edge points to the total number of sampling points. The first shape matching degree represents the overall shape similarity between the extraction target in the image and the template.

  As the fitness parameter, as shown in Japanese Patent Laid-Open No. 9-185719 filed by the same applicant as the present application, the reciprocal of an error relating to image data (such as color intensity distribution of color components) in the vicinity of the contour line of the template model. It may be used as a measure of goodness of fit.

  In the process of scanning of multiple templates with different sizes and fitness evaluation, when the fitness parameter of a certain template exceeds a predetermined reference value, scanning of the template is stopped and the target object is confirmed for the user. Indicator 46 (FIG. 6) is displayed. At this stage, information on the position and size of the target is extracted. When the user presses the extraction button 48 to instruct the start of the extraction execution process, the next update template generation process (S7) is executed.

  FIG. 8 shows a state of deformation of the template figure in the update template generation process. In FIG. 8A, the degree of matching between the initial shape of the template figure and the object shape of the input image (such as the edge ratio on the interpolation curve) of the representative points P1, P2,. Is displayed. Representative points other than these are points with relatively good matching, and an optimal destination is detected within each movement range as shown in FIG.

  In the update template generation process (S7), the template graphic element transformation device 30 moves the representative point of a certain graphic element (curve segment) constituting the template graphic within the movement range (or according to the movement conditions such as Equation 8 and Equation 9). ) Moved (S7a), the template graphic element deforming device 30 generates a new curved segment connecting the representative points after the movement (S7b), and the shape conformity evaluation device 32 determines the second shape conformance at each portion. By evaluating (S7c), the representative points are moved so that the second shape conformity is equal to or greater than a predetermined reference value, and finally, the boundary line generating device 34 is a curve ( Or a line segment). In the course of executing these processes, movement conditions are relaxed as necessary (S7d), and finally the entire template is deformed to satisfy the movement conditions (S7e).

  The boundary line display device 36 displays the boundary line superimposed on the input image on the screen of the image display device 14. The update template data is generated as binary mask data indicating the boundary line data or the area.

  Movement and fitness evaluation are not performed while moving each representative point at the same time. Instead, priority is given to moving a representative point that relays a segment with a low edge ratio that is adjacent to a representative point that is an end point of a segment with a high edge ratio. Is efficient. FIG. 8B shows the shape of the update template representing the curve connecting the representative points after moving in such a manner. In FIG. 8B, Pi in FIG. 8A has moved to Pi ′ in FIG. 8B. For example, in FIG. 8A, for a representative point P5 adjacent to the representative point Q that is an end point of a segment with a high edge ratio, a predetermined radius (for example, an arc length from Q to P5) centered on the point Q is used. First, the destination of P5 is searched on the arc.

  In the search for the destination of the representative point position, the above-mentioned movement range is represented by a predetermined probability distribution (particularly, a value having a value of 0 outside the movement range), and the representative point position given by the distribution is stochastically The position where the value is greater than or equal to a predetermined reference value (or large amount) may be estimated by generating and evaluating the shape adaptability of the curve segment including the representative point each time.

  The movement destination of the representative point is determined based on the evaluation result of the second shape suitability. The second shape fitness is defined for each representative point, and the edge ratio on the curve (or line segment) connecting the representative points (usually two) adjacent to the representative point and the curve (or line segment). ) It is represented by a linear sum of the degree of coincidence (the proportion of points that coincide within the allowable range) within the allowable range of the above feature amount gradient (such as the gradient of the edge intensity distribution).

  The movement range / condition update setting device 28 expands the movement range of the representative point according to the second shape suitability value or relaxes the movement condition (S7d), and from the area that has not been searched yet. An optimum representative point position, that is, a representative point position that maximizes the second shape suitability may be searched and moved. That is, by deforming the template graphic element described above based on the second shape conformance, even if the target has a slightly different contour from the contour shape data of the template belonging to the extraction category, As a result of the expansion of the representative point movement range or the relaxation of the movement conditions, the entire contour can be extracted.

  In the example shown in FIG. 8, as P5 moves to P5 ', the movement range of the remaining representative points that are present continuously is updated based on the position of P5'. This is shown in FIG. Specifically, for example, the movement range is set with the constraint condition that at least one of the shape of the curve passing through P5 ′, P6 ′, and P7 ′ is convex and the size of the curve is maintained at the same level. Set and run the search. Which condition or both conditions are used depends on the degree of non-rigidity to be extracted and the presence or absence of a joint, but is defined in the template data in advance.

  In FIG. 9, the sizes of the search ranges of P6 and P6 ′ and P7 and P7 ′ are approximately the same, and the arrangement of each search range is a constraint condition that the shape is convex (for example, in Equations 8 and 9). (Conditions shown) are applied. As shown in FIG. 9 (b), the newly set movement range may be far away from the original movement range.

  When the representative point is moved by giving only the movement constraint condition without explicitly setting the movement range, the rate of change in the tangential direction of the curve passing through P5 ′, P6 ′, and P7 ′ is positive ( (See Equation 8 and Equation 9).

  As the curve connecting the representative points after movement, it is desirable to use the same type of curve as the curve constituting the original template. However, the order of the parameters and the like can be changed to best suit the shape to be extracted. For example, when using a B-spline curve, the order and the number of control points may be changed.

ここで、Ｔは転置行列を示し、Ｂ（ｓ）はＢスプライン行列、ｔは曲線セグメントの長さ、ＱはＢスプラインパラメータをそれぞれ示す。 An example of a method for determining a curve parameter constituting the updated template will be described. It is assumed that a certain curve segment v (s) = (x (s), y (s)) ^T is modeled using an nth-order B-spline function. The optimum value of the parameter after the representative point movement is estimated as follows, for example. That is,

Here, T represents a transposed matrix, B (s) represents a B spline matrix, t represents a length of a curve segment, and Q represents a B spline parameter.

となる。ここで、（σ_ｘ）^２，（σ_ｙ）^２は、Ｅ_ｖ’（ｓ）＝（Ｅ_{ｘ’（ｓ）}，Ｅ_{ｙ’（ｓ）}）に対する分散を示す。 The contour to be extracted corresponding to the curve segment is set to v ′ (s) = (x ′ (s), y ′ (s)) ^T, and the feature value (edge intensity value, etc.) at each point is E _v ′ ( s), and E _v ′ (s) is normally distributed with respect to E _v (s), the probability distribution density function is

It becomes. Here, (σ _x ) ² and (σ _y ) ² indicate variances with respect to E _v ′ (s) = (E _{x ′ (s)} , E _{y ′ (s)} ).

で与えられる。Ｑの階数等は、以下に示す情報量基準ＡＩＣ（Ｑ）が最小となるｎなどのようにして求められる。具体的には、

である。Ｎｕｍｂｅｒ（Ｑ）は、Ｑの要素数である。 In this embodiment, in order to simplify the explanation and make it easy to understand, E _v (s) is binary (0 or 1), and the contour model data of the template figure is E _v (s) = 1. It shall be given as a set. At this time, the most likely estimate is

Given in. The rank of Q and the like are obtained in the following manner, such as n that minimizes the information criterion AIC (Q) shown below. In particular,

It is. Number (Q) is the number of elements of Q.

  The expansion of the movement range typically involves simply expanding the shape of the original movement range at a predetermined magnification. However, it may be an anisotropic expansion in which the tangent direction of the curve including the representative point of the template graphic element is increased. At this time, it goes without saying that the search is performed within a range satisfying the above-described movement condition.

  If the number of representative points whose second shape conformance is less than a predetermined reference value (for example, 0.3) is less than or equal to a certain number (for example, a majority) of the template even after the restriction on movement is relaxed, The above-described processing may be executed by stopping the deformation and switching to another template having a different size.

  When the edge ratio is very high (for example, 0.9 or more) on the curve segment of the template connecting the representative points in the vicinity of the representative point, it is not necessary to search for the movement destination of the representative point as described above. Good.

  As shown in FIG. 8C, when there is a non-edge point of the feature amount extracted previously on the curve (or line segment) connecting the representative points, the non-edge point is added as an additional representative point. (If such non-edge points are continuous, the midpoint on the continuous non-edge line segment is set as a new representative point), and the movement range is similarly set (or moved) for the representative point. It is also possible to perform a movement search so as to satisfy the condition) and move to a position satisfying the constraint condition to generate a curve connecting the representative point adjacent to the representative point. The addition of the representative point can be automatically performed, but may be executed according to a user instruction. If an appropriate representative point position is not detected, the movement range is expanded or the movement condition is relaxed in the same manner.

  Finally, the updated template contour line is displayed (S8), mask data is generated from the contour line data (S9), and the contour line or mask data is recorded in the storage device as necessary (S10), and the processing is performed. Exit.

  Each of the above processes may be formed in a predetermined program format that can be executed by a computer, and each part of the processing may be performed by hardware such as a predetermined gate array (FPGA, ASLC, etc.) or a predetermined computer program. It is clear that the present invention can be realized even in a form in which partial hardware modules that realize some of the elements shown in 1 are mixed. When a hardware module is included, each component does not necessarily have the same configuration as that illustrated in FIG. 1, and the function is substantially the same, or one component is a plurality of components in FIG. 1. Needless to say, those having functions are included in the technical scope of the present invention. This point is the same in the following embodiments.

  An embodiment in which the update template generation process (S7 in FIG. 5) is changed will be described. In this modified embodiment (second embodiment), the template scan and the fitness evaluation are executed, the position of the extraction target and an appropriate template model are selected, and then the update template generation process specific to this embodiment is executed. To do. A flowchart of the specific processing procedure is shown in FIG.

  First, representative points including a segment having a low shape matching degree are automatically extracted from the template data before update (S11), and the template data is divided into local regions so as to include the representative points (S12). In the case of using a template that has been divided into regions for each shape element that has been collected in advance, this region division processing is unnecessary.

  In the local region including the representative point, estimation and conversion of geometric conversion parameters as described below are executed (S13). In the present embodiment, the template is updated by local geometric deformation (such as local affine transformation, local bilinear transformation, and local perspective transformation) in the vicinity region of a predetermined representative point. The geometric transformation parameter is obtained as a parameter that best fits the object in the input image based on the Bayesian estimation method of the stochastic process regarding the curve parameter.

  Further, in order to finely adjust the contour model shape as necessary, a curved segment connecting the converted representative points is generated (S14), and the second shape conformance is evaluated, as in the above-described embodiment. (S15) The template shape is deformed and updated (S16).

  The significance of performing local geometric deformation and fitness evaluation in this embodiment is that the relative positional relationship between representative points (ie, geometric phase and concave or convex shape) is generally maintained, By converting the positions of a plurality of representative points in a specific region so as to match a given deformation mode, it is possible to improve the efficiency of searching for a contour model that matches the extraction target.

ｘ’＝ｘｗ’、ｙ’＝ｙｗ’、［ｕｖ］は変換前の座標、［ｘｙ］は変換後の座標、｛ａ_ｉｊ｝｛ａ_ｉ｝｛ｂ_ｉ｝及びｗは変換パラメータである。 The affine transformation, perspective transformation, and bilinear transformation are each given by the following equations. That is,

x ′ = xw ′, y ′ = yw ′, [uv] is a coordinate before conversion, [xy] is a coordinate after conversion, {a _ij } {a _i } {b _i }, and w are conversion parameters.

  The neighborhood area may be a rectangular area having a predetermined size including a plurality of representative points, or the template may be divided in advance for each predetermined block, and the deformation may be performed for each block. For example, in a template representing a human body, a region divided into blocks for each meaningful shape, such as a head, a torso, a chest, and a leg, may be used as a neighborhood region. FIG. 11 shows the result of dividing each part of the human body in advance and performing a predetermined geometric transformation on each part of the original data FIG. 11A. FIG. 11B, FIG. 11C, and FIG. Is illustrated. Needless to say, the contour data actually used is the outermost contour of each figure in FIG.

上式の最右辺の対数をとり、またＰ（ｂ）が定数であることを考慮すると、結局、

となる。 The template is deformed by moving the position of each point (or representative point) in the vicinity region by the above-described geometric transformation. Taking affine transformation as an example, a procedure for obtaining an optimum transformation parameter will be described. When the prior probability of the transformation parameter set {a _ij } is P (a), the prior probability of the image data is P (b), and a transformation parameter is given, the template figure element obtained by the transformation is the feature quantity of the input image. And P (b | a), which is a feature quantity b of the image, and P (a | b), the posterior probability that the conversion parameter set of the corresponding template is {a _ij } Let the conversion parameter to be obtained be {a _opt }. {A _opt } is given by the following equation as a parameter that gives the maximum posterior probability max [P (a | b)] according to Bayes' law. That is,

Taking the logarithm of the rightmost side of the above equation and considering that P (b) is a constant, after all,

It becomes.

Next, a procedure for estimating a geometric (affine) transformation parameter will be specifically described with reference to FIG. The prior probability distribution P (a) of the geometric transformation parameter and the posterior probability P (b | a) that the template figure element obtained by the transformation matches the feature quantity of the input image are obtained as shown in the following equation (S21). These are substituted into the right side of Equation 18 to obtain the maximum posterior probability evaluation function (S22). A parameter {a _opt } that maximizes the value of the obtained function is obtained by an optimization method such as a continuous gradient hill climbing method (S23).

ここで、σは分散、ａ（ｕ，ｖ）はアフィン変換により点（ｕ，ｖ）が移される座標、ｂは入力画像の２値のエッジマップ（エッジ強度分布を所定の閾値で２値化したもの）をそれぞれ示す。テンプレートデータが濃淡画像の場合、Ｎは当該代表点を含む局所領域又は予め分割された当該代表点を含む領域上の点の集合となり、ｂはエッジ強度分布を示す。 Assume that the template data consists of line figures, and affine transformation into binary template data t (u, v) in a set N of points on a local line segment (curve element) constituting a graphic element of a template including a representative point Assume that the error resulting from performing {a} is Gaussian. Under this assumption, the posterior probability P (b | a) is given by the following equation. That is,

Where σ is the variance, a (u, v) is the coordinate to which the point (u, v) is moved by affine transformation, b is the binary edge map of the input image (the edge intensity distribution is binarized with a predetermined threshold value) Each). When the template data is a grayscale image, N is a set of points on a local region including the representative point or a region including the representative point divided in advance, and b indicates an edge intensity distribution.

ここで、ｍ_ｉｊ，σ_ｉｊはそれぞれａ_ｉｊの平均及び分散を示し、

である。ｍｏｄｅ＝｛回転_１、回転_２、・・・、倍率_１、倍率_２、・・・、シフト_１、・・・、その他｝のように表わされ、各変形モードごとに、ｍ_ｉｊ及びσ_ｉｊのパラメータ値が与えられる。‘その他’のモードは、特定の名称が与えられない任意の変換モードである。 The prior probability distribution P (a) is assumed to take a high value in a deformation mode that gives scaling, rotation or shift in the horizontal or vertical direction,

Here, m _ij and σ _ij indicate the mean and variance of a _ij , respectively.

It is. mode = {rotation ₁ , rotation ₂ ,..., magnification ₁ , magnification _2, ..., shift ₁ ,..., etc.}, and m _ij and σ _ij for each deformation mode. Parameter values are given. 'Other' mode is any conversion mode that is not given a specific name.

The optimum transformation parameters are obtained by substituting Equations 19, 20, 21, and 22 into Equation 18 and using a continuous gradient hill climbing method or the Powel method for V _mode and {a _ij }. It is done. The above is an example of a method for obtaining an optimum conversion parameter, and it goes without saying that other optimization methods (EM algorithm, dynamic programming, genetic algorithm, etc.) may be used.

  Using the template data converted by the conversion parameter obtained by the method described above as an initial value, generation of a curve connecting the movement of the representative points and the representative points based on the second shape fitness evaluation shown in the first embodiment Processing may be performed.

  When the contour line (closed curve) to be extracted is obtained by the above-described method, the closed curve data is displayed on the screen of the image display device 14, and if necessary, mask data is generated as area data inside the closed curve. Is recorded in a predetermined storage means.

  You may use the variable shape template which consists of a graphic element which has an indefinite part in part. The indeterminate part is a part with a large degree of freedom of deformation, and it is a constraint that the new loop shape does not occur with the deformation and that the shape corresponding to the indeterminate part is known in advance as concave or convex. A part where no other specific constraint is imposed.

  As an extraction target, for example, portions having joints such as a person's chest and legs are known in advance to have a greater degree of freedom of deformation than other portions. Define it above.

  As in the first embodiment, template scanning and fitness evaluation are executed, and the position to be extracted and an appropriate template model are selected. Next, template update is executed by deformation of the graphic elements constituting the template and shape suitability evaluation. At that time, first, the template is deformed by the method shown in the first embodiment or the second embodiment except for the indefinite portion, and then the contour of the indefinite portion is estimated.

  Two methods will be described as methods for estimating the contour of the indefinite portion. In the first method, contour tracking with one end point of the indefinite portion as the start point and the other end point is executed for each indefinite portion. A curve that approximates the contour of the indefinite portion obtained as a result may be generated. FIGS. 13A and 13B show an example of the contour shape extraction process of the indefinite portion by the first method.

In the second method, as shown in FIG. 13 (c), the probe circle whose diameter is a line segment connecting both end points of the indeterminate part is moved outward if the indeterminate part is convex, and inward if it is concave. However, the radius and the position of the circle are changed little by little at each place, and the position and radius of the circle where the contour to be extracted is in contact with the circle at two locations (p _j , q _j ) are obtained. Thereby, the coordinates of the contour line are determined sequentially. This method is suitable for extracting a contour line having no branch. After extracting the approximate shape by this method, the extracted shape may be used as the initial contour model, and the detailed shape may be extracted by the method described in the first embodiment or the second embodiment.

  FIG. 14 shows a flowchart of the template update process in the third embodiment. The process shown in FIG. 14 corresponds to S7 in FIG.

  First, a curve segment pair having end points is selected (S31), and the shape of the template graphic element other than the indefinite portion is updated by the method described in the previous embodiment (S32). Next, the start point and the end point are set from the opposite end points of the adjacent graphic elements after the update (S33), and the above-described method, that is, the contour tracking connecting the start point and the end point (first method), or the contour by the probe circle Position determination (second method) is executed (S34). The above processing is repeated until all the end points are eliminated (S35). When one closed curve is formed by the graphic elements of the template (S35), it is output as updated template data (S36).

  With such a configuration, it is possible to stably extract the contour of the extraction target that is known in advance to have high shape uncertainty (degree of freedom) for a specific portion. That is, even if there is an object in the image that has a part that differs greatly from the shape of the given template, the most probable curve that complements the remaining defined part shape gap for the outline of the different part (e.g. , A curve obtained by contour tracing as a condition satisfying the continuity of the shape at the end points or the continuity of the image feature amount.

  As a fourth embodiment, as a process corresponding to the template update process (S7 in FIG. 5), a curve along a graphic element (or line segment) constituting a template passing between representative points (or a center line of the curve). A thick line having a predetermined width may be generated as shown in FIG. 15, and the boundary position inside the thick line may be estimated based on the feature values (color component values, local spatial frequency representative values, etc.) on both sides of the thick line. . In this case, the same process as in the previous embodiment is performed before the template update process.

  Specifically, as shown in FIG. 15, a nucleus for region growth is set on at least one of the contour line 1 or the contour line 2 of the thickened region. In the region growing process, a region near the nucleus whose image feature value difference in the nucleus is smaller than a predetermined threshold is merged with the nucleus, and the growth result from the contour line 1 and the growth result from the contour line 2 are obtained as a result. Integrate. Alternatively, one boundary line is estimated based on the growth result from any one of the contour lines.

  The boundary position is, for example, a region based on the maximum edge strength position of the feature amount on a line substantially orthogonal to the direction of the thick line, or the similarity of feature amounts (for example, color components) from predetermined sampling points on both sides of the thick line. It is determined as the boundary position by growth.

  In this embodiment, the contour line finally extracted does not necessarily have to be expressed by a parametric curve.

10: image input device 12: image storage device 14: image display device 16: image processing device 18: instruction selection device 20: feature quantity extraction device 22: template model selection device 24: template data generation device 26: template scanning device 28: Movement range / condition update setting device 30: update template generation device 32: shape conformity evaluation device 34: boundary line generation device 36: boundary line display device 38: mask data generation device 40: screen 42 of image display device 14: input image 44: Template model image data 46: Target position confirmation indicator 48: Extraction instruction button 50: Template scroll button

Claims (4)

A first matching process is performed for obtaining a predetermined evaluation function value related to at least one of a first matching degree relating to a feature value between the input image and a local template and a second matching degree relating to a gradient of the feature quantity. 1 matching step;
This is executed when the evaluation function value of the first matching process is equal to or greater than a predetermined threshold value, obtains a distribution function value of edge points on the graphic element, and obtains a section where non-edge points exist continuously for a certain length or more. A second matching step for performing a second matching process for adding a representative point to a predetermined position;
An outline extracting step of moving the representative points based on a result of the second matching process and extracting an outline connecting the representative points;
An image region extracting step for extracting an image region including the contour line. A first matching process is performed for obtaining a predetermined evaluation function value related to at least one of a first matching degree relating to a feature value between the input image and a local template and a second matching degree relating to a gradient of the feature quantity. 1 matching means,
This is executed when the evaluation function value of the first matching process is equal to or greater than a predetermined threshold value, obtains a distribution function value of edge points on the graphic element, and obtains a section where non-edge points exist continuously for a certain length or more. A second matching means for performing a second matching process for adding a representative point to a predetermined position;
Contour extraction means for moving the representative points based on the result of the second matching process and extracting contour lines connecting the representative points;
An image extraction apparatus comprising: an image region extraction unit that extracts an image region including the contour line. Inputting an image;
A feature amount extraction step of extracting a feature amount distribution of the input image by the image input step;
A template model input step for inputting a template model including a plurality of representative points and a curve or a line segment connecting the representative points as a graphic element;
A template set generating step for generating a plurality of template sets having different graphic sizes from the template model and having a graphic element substantially similar to the graphic element of the template model;
A first matching process is performed for obtaining a predetermined evaluation function value relating to at least one of a first matching degree relating to the feature value of the input image and the template and a second matching degree relating to a gradient of the feature value. 1 matching step;
A template selection step of selecting one of the template sets based on a result of the first matching process;
This is executed when the evaluation function value of the first matching processing is equal to or greater than a predetermined threshold value, obtains a distribution function of edge points on the graphic element, and determines a predetermined interval of non-edge points continuously longer than a certain length. A second matching step for performing a second matching process for adding the representative point to a position;
A representative point update step of moving the representative point based on a result of the second matching process;
A template update step for generating an update template including a curve or a line segment connecting the representative point after movement and the representative point as a graphic element;
An image extraction method comprising: an image extraction step of extracting image data including the update template. An image input means for inputting an image;
Feature quantity extraction means for extracting the feature quantity distribution of the input image by the image input means;
A template model input means for inputting a template model including a plurality of representative points and curves or line segments connecting the representative points as graphic elements;
A template set generating means for generating a plurality of template sets having different graphic sizes from the template model and having a graphic element substantially similar to the graphic element of the template model;
A first matching process is performed for obtaining a predetermined evaluation function value relating to at least one of a first matching degree relating to the feature value of the input image and the template and a second matching degree relating to a gradient of the feature value. 1 matching means,
Template selection means for selecting one of the template sets based on a result of the first matching process;
This is executed when the evaluation function value of the first matching processing is equal to or greater than a predetermined threshold value, obtains a distribution function of edge points on the graphic element, and determines a predetermined interval of non-edge points continuously longer than a certain length. A second matching means for performing a second matching process for adding the representative point to a position;
Representative point updating means for moving the representative point based on the result of the second matching process;
A template updating means for generating an update template including a curve or a line segment connecting the representative point after movement and the representative point as a graphic element;
An image extraction method comprising image extraction means for extracting image data including the update template.

Images