US 7,227,996 B2Grant

Image processing method and apparatus for comparing edges between images

Issue Date:2007-06-05

•32 Claims

•23 Drawing Sheets

Abstract

An image processing method for detecting an object from an input image using a template image, including inputting a specified image with respect to both a template image and an input image, calculating an edge normal direction vector of said specified image, generating an evaluation vector from said edge normal direction vector, subjecting the evaluation vector to orthogonal transformation, a step of performing a product sum calculation of corresponding spectral data with respect to each evaluation vector that has been subjected to orthogonal transformation and has been obtained for each of said template image and said input image, and a step of subjecting it to inverse orthogonal transformation and generating a similarity value map. The formula of the similarity value, the orthogonal transformation, and the inverse orthogonal transformation each have linearity. The pattern recognition is one in which the component of the similarity value is not subjected to positive/negative reversal through variations in brightness of the background.

Metadata

Assignee

Matsushita Electric Industrial Co., Ltd.

Inventors

Kazuyuki Imagawa
Tetsuya Yoshimura
Katsuhiro Iwasa
Hideaki Matsuo
Yuji Takata

Application Information

Application Number:US 10/057,756

Filing Date:2002-01-25

Priority Date:2001-02-01

Art Unit:2624

Classifications

IPC:

G06K9/00G06K9/46G06K9/62G06K9/66

Patent Drawings (23 sheets)

Description

Background of the Invention

[0001] 1. Field of the Invention

[0002] The present invention relates to an image processing method for detecting an object from an input image using a template image, and relates to an image processing apparatus therefor.

[0003] 2. Description of the Related Art

[0004] Conventionally, a technique is well known in which a template image is pre-registered, and the position in an input image of an image similar to the template image is detected by pattern matching between the input image and the template image. However, since distorted perceptions are liable to be shaped according to the manner in which the background of the image similar to the template image is formed, Japanese Published Unexamined Patent Application No. Hei-5-28273 discloses a technique that has been developed to solve this problem. In this publication, a similarity value between the template image and the image corresponding to the template image is defined by the mathematical Formula 1.

Formula 1

[0005] Cv: Correlation coefficient (similarity value)
[0006] M: Number of pixels of template image in x direction
[0007] N: Number of pixels of template image in y direction
[0008] Sx: Derivative value of input image S in x direction
[0009] Sy: Derivative value of input image S in y direction
[0010] Tx: Derivative value of template image T in x direction
[0011] Ty: Derivative value of template image T in y direction

[0012]

\begin{matrix} σ_{S0} = \sqrt{\frac{1}{MN} \sum_{i = 1}^{M} \sum_{j = 1}^{N} ({Sx}_{ij}^{2} + {Sy}_{ij}^{2})} \\ σ_{T0} = \sqrt{\frac{1}{MN} \sum_{i = 1}^{M} \sum_{j = 1}^{N} ({Tx}_{ij}^{2} + {Ty}_{ij}^{2})} \\ ρ_{V0} = \frac{1}{MN} \sum_{i = 1}^{M} \sum_{j = 1}^{N} ({Tx}_{ij} {Sx}_{ij} + {Ty}_{ij} {Sy}_{ij}) \\ Cv = \frac{ρ_{V0}}{σ_{T0} σ_{S0}} \end{matrix}

[0013] In detail, an inner product (cos θ) of an angle θ between a normal direction vector of the edge of the template image and a normal direction vector of the edge of the input image is a component of the similarity value.

[0014] However, there exists a problem in that, as described later in detail, if the brightness of a background periphery of an image of an object is uneven, the positive and negative values of the inner product are reversed. This makes the similarity value unsuitable for the real image, and distorted perceptions are easily produced, thus making it difficult to obtain a desirable recognition result.

[0015] Additionally, the similarity value formula is nonlinear with respect to the normal direction vectors of the edges of the input and template images, and processing for the template image and processing for the input image must be performed simultaneously.

[0016] Further, the template image is scanned on the input image. A correlated calculation of the input image and the reference image must be performed for each scanning point. Therefore, in practicality, a resulting expansion of the amount of calculation makes real-time processing impossible.

Objects and Summary of the Invention

[0017] It is therefore an object of the present invention to provide an image processing method and an image processing apparatus capable of obtaining an accurate, clear recognition result and capable of performing high speed processing.

[0018] In an image processing method according to a first aspect of the present invention, the amount of matching between a template image and an input image is evaluated using a similarity value map. An evaluation vector is generated for each of the template and input images. The evaluation vector includes a component in which a normal direction vector of an edge of a specified image undergoes an even number of angular transformations.

[0019] With this structure, the matching therebetween is properly evaluated with no influence on the similarity value even in a case in which the positive and negative of an inner product (cos θ) of an angle θ between a normal direction vector of the edge of the template image and a normal direction vector of the edge of the input image are reversed by unevenness in the brightness of its background.

[0020] An image processing method according to a second aspect of the present invention includes a step of inputting a specified image for each of a template image and an input image and calculating a normal direction vector of an edge of the specified image; a step of generating an evaluation vector from the edge normal direction vector; a step of subjecting the evaluation vector to an orthogonal transformation; a step of performing a product sum calculation of corresponding spectral data for each evaluation vector, which has been subjected to orthogonal transformation, obtained for the template image and input image; and a step of subjecting a result of the product sum calculation to an inverse orthogonal transformation and generating a map of similarity values; in which a formula of the similarity values, the orthogonal transformation, and the inverse orthogonal transformation each have linearity.

[0021] With this structure, a Fourier transformation value of the template image and a Fourier transformation value of the input image do not need to be simultaneously calculated. In other words, the Fourier transformation value of the template image is obtained prior to that of the input image, thus making it possible to lighten the processing burden and improve processing speed.

[0022] An image processing method according to a third aspect of the present invention includes a step of compressing each evaluation vector, which has been subjected to the orthogonal transformation, so as to reduce the processing amount.

[0023] With this structure, what is processed is limited only to an effective component (e.g., low-frequency component). Thereby processing speed is improved.

[0024] In an image processing method according to a fourth aspect of the present invention, for the template image, the steps taken until the evaluation vector that has been subjected to the orthogonal transformation is compressed are executed before the input image is input, and the result is stored in a recording unit.

[0025] With this structure, processing relating to the template image is completed merely by reading from the recording unit, and processing speed is improved.

[0026] In an image processing method according to a fifth aspect of the present invention, the evaluation vector is normalized with respect to a vector length.

[0027] With this structure, the stability of pattern extraction is improved without undergoing length variations though the strength of the edge of the input image varies, and the vector length varies according to a photographic condition.

[0028] In an image processing method according to a sixth aspect of the present invention, the evaluation vector of the template image is normalized by the number of edge normal direction vectors.

[0029] Therefore, independent of whether the number of edges of the template image is large or small, a similarity is evaluated on the same scale by dividing it by n and normalizing it.

[0030] In an image processing method according to a seventh aspect of the present invention, the data amount is reduced by use of complex conjugate properties of an orthogonal transformation before performing a product sum calculation, and the data amount is restored after performing the product sum calculation.

[0031] With this structure, the data amount is greatly reduced to improve processing speed, and memory capacity is saved.

[0032] In an image processing method according to an eighth aspect of the present invention, the template image is enlarged/reduced to various sizes, and the evaluation vector of each size is subjected to addition processing.

[0033] With this structure, matching does not need to be repeatedly carried out for each size, and processing speed is improved.

[0034] In an image processing method according to a ninth aspect of the present invention, for the template image, the addition processing of the evaluation vector is carried out after executing the step of compressing each evaluation vector so as to reduce the processing amount.

[0035] With this structure, the amount of data subjected to addition processing is reduced, and processing speed is improved.

[0036] In an image processing method according to a tenth aspect of the present invention, the template image is an image of a typified face.

[0037] With this structure, not only the total position of a face but also the partial position of a main face part, such as the eyes, nose, or mouth, are recognized.

[0038] In an image processing method according to an 11th aspect of the present invention, a peak pattern that steepens the peak of the similarity value is prepared. The result obtained by subjecting data of this peak pattern to an orthogonal transformation is applied to the product sum calculation.

[0039] With this structure, a part similar to a template is detected from the input image more clearly and stably while reflecting the peak pattern.

[0040] In an image processing method according to a 12th aspect of the present invention, a mask pattern that depends on the template image is formed. The result obtained by subjecting data of this mask pattern to an orthogonal transformation is applied to the product sum calculation.

[0041] With this structure, closer detection is performed while adding attributes other than the shape of the template image.

[0042] In an image processing method according to a 13th aspect of the present invention, the mask pattern shows an average of the number of pixels in an image of the template image.

[0043] With this structure, attributes of the template image are reflected by a simple mask pattern.

[0044] An image processing method according to a 14th aspect of the present invention further includes a step of, for the template image, processing positive and negative signs of the evaluation vector of the original template image and generating an evaluation vector of a bilaterally symmetrical image with respect to the original template image, by which the generated evaluation vector is applied to the product sum calculation.

[0045] With this structure, amount of the template image to be recorded is reduced, and the evaluation vector of the template image that has been bilaterally reversed is generated without direct calculation, thus making it possible to improve processing speed.

[0046] In an image processing method according to a 15th aspect of the present invention, a map of point biserial correlation coefficients is generated on the basis of an extracted face image, and a position of the face part is calculated.

[0047] With this structure, the position of the face part is specified more accurately.

[0048] In an image processing method according to a 16th aspect of the present invention, the distribution of projection values in the y-direction is calculated on the basis of the extracted face image by use of the mask pattern. Two maximum points are calculated from this distribution. An extent between these maximum points is output as a mouth range.

[0049] With this structure, the mouth range is specified more accurately.

[0050] In an image processing method according to a 17th aspect of the present invention, the input image is divided into only the face image and parts other than the face image on the basis of the extracted face image. A digital watermark is embedded only into the face image. The face image into which the digital watermark has been embedded and parts other than the face image are combined and output.

[0051] With this structure, watermark data is concentratively embedded into the face part which might be falsified.

[0052] In an image processing method according to a 18th aspect of the present invention, the input image is divided into only the face image and parts other than the face image on the basis of the extracted face image. Only the face image is edited. The face image that has been edited and parts other than the face image are combined and output.

[0053] With this structure, only the face image is corrected without exerting any influence on parts other than the face.

[0054] In an image processing method according to a 32nd aspect of the present invention, a face image is cut out from the input image on the basis of the extracted face image. A facial inner image is then extracted from the face image that has been cut out. A feature that serves to correct the face image is then calculated on the basis of the extracted face image. A correction function is then determined on the basis of the obtained feature, and image correction based on the determined correction function is applied at least to the face image that has been cut out.

[0055] With this structure, the face image is corrected according to the feature of only the facial inner image without being adversely affected by images that are not the face image. Therefore the viewability of the face image is infallibly improved.

[0056] The above, and other objects, features and advantages of the present invention will become apparent from the following description read in conjunction with the accompanying drawings, in which like reference numerals designate the same elements.

Brief Description of the Drawings

[0057] FIG. 1 is a block diagram of an image processing apparatus according to Embodiment 1 of the present invention.

[0058] FIG. 2(a) is a view showing a template image.

[0059] FIG. 2(b) is a view showing an edge extraction image (x component) of the template image.

[0060] FIG. 2(c) is a view showing an edge extraction image (y component) of the template image.

[0061] FIG. 3 is an explanatory drawing for explaining the compression processing of an evaluation vector.

[0062] FIG. 4(a) is a view showing an input image.

[0063] FIG. 4(b) is a view showing an edge extraction image (x component) of the input image.

[0064] FIG. 4(c) is a view showing an edge extraction image (y component) of the input image.

[0065] FIG. 5(a) is a view showing a map of similarity values.

[0066] FIG. 5(b) is a view showing the input image.

[0067] FIG. 6 is a drawing to which reference will be made in explaining a positive/negative reversal of an inner product.

[0068] FIG. 7(a) is a view showing a template image.

[0069] FIG. 7(b) is a view showing an input image.

[0070] FIGS. 8(a) and 8(b) are views showing template images.

[0071] FIG. 9 is a block diagram of an image processing apparatus according to Embodiment 2 of the present invention.

[0072] FIGS. 10(a) and 10(b) are graphs showing conjugate properties.

[0073] FIG. 11(a) is a block diagram of a template image processing part according to Embodiment 3 (first example) of the present invention.

[0074] FIG. 11(b) is a block diagram of a template image processing part according to Embodiment 3 (second example) of the present invention.

[0075] FIG. 12 is a view showing an input image.

[0076] FIG. 13(a) is a view showing a template image.

[0077] FIG. 13(b) is a view showing an edge extraction image.

[0078] FIG. 13(c) is a view showing an enlargement/reduction template image.

[0079] FIG. 13(d) is a view showing a template image.

[0080] FIG. 13(e) is a view showing an edge extraction image.

[0081] FIG. 13(f) is a view showing an enlargement/reduction template image.

[0082] FIG. 14 is a view showing a face extraction result.

[0083] FIG. 15 is a block diagram of an image processing apparatus according to Embodiment 4 of the present invention.

[0084] FIG. 16 is a view showing a peak pattern.

[0085] FIG. 17 is a block diagram of an image processing apparatus according to Embodiment 5 of the present invention.

[0086] FIG. 18(a) is a view showing a template image.

[0087] FIG. 18(b) is a view showing a mask pattern.

[0088] FIG. 19 is a block diagram of an image processing apparatus according to Embodiment 6 of the present invention.

[0089] FIG. 20(a) is a view showing an original template image.

[0090] FIG. 20(b) is a view showing a template image that has been subjected to a bilateral reversal.

[0091] FIG. 21 is a block diagram of a part of the image processing apparatus according to embodiment 6 of the present invention.

[0092] FIG. 22(a) is a view showing an input image.

[0093] FIG. 22(b) is a view showing the eyes/eyebrow candidate range.

[0094] FIG. 22(c) is a view showing a recognition result.

[0095] FIG. 23(a) is a view showing a filter shape according to embodiment 7 of the present invention.

[0096] FIG. 23(b) is an explanatory drawing of an overall range mask.

[0097] FIG. 23(c) is an explanatory drawing of a range-1 mask.

[0098] FIG. 23(d) is an explanatory drawing of a range-2 mask.

[0099] FIG. 24 is a block diagram of a part of an image processing apparatus according to Embodiment 8 of the present invention.

[0100] FIG. 25(a) is a view showing an input image.

[0101] FIG. 25(b) is an explanatory drawing of a mouth candidate range.

[0102] FIG. 25(c) is a graph of projection values.

[0103] FIG. 25(d) is an explanatory drawing of a mask pattern.

[0104] FIG. 25(e) is a view showing a projection-value map image.

[0105] FIG. 25(f) is a graph of projection values.

[0106] FIG. 26 is a block diagram of a part of an image processing apparatus according to Embodiment 9 (first example) of the present invention.

[0107] FIG. 27(a) is a view showing an input image.

[0108] FIG. 27(b) is a view showing an output image.

[0109] FIG. 28 is a block diagram of a part of the image processing apparatus according to Embodiment 9 (second example) of the present invention.

[0110] FIGS. 29(a) and 29(b) are views showing input images.

[0111] FIG. 29(c) is a view of an edited image.

[0112] FIG. 30 is a block diagram of a part of the image processing apparatus according to Embodiment 9 (third example) of the present invention.

Detailed Description of the Preferred Embodiments

(Embodiment 1)

[0113] FIGS. 1 through 8(b) show the basic form of an image processing apparatus of the present invention.

[0114] Referring to FIG. 1, the image processing apparatus according to Embodiment 1 includes two different processing parts, i.e., a template image processing part 100 and an input image processing part 200. The apparatus evaluates matching between a template image and an input image using a map of similarity values L. In this image processing apparatus, both the template image processing part 100 and the input image processing part 200 perform orthogonal transformation with linearity, then perform multiplication, and calculate the similarity values L by inverse orthogonal transformation.

[0115] It should be noted that FFT (Fast Discrete Fourier Transformation) is used as an orthogonal transformation in all embodiments described later. However, not only FFT but also Hartley transformation or number theoretic transformation can be used. In such cases, it will be understood that the term “Fourier transformation” in the following description should be replaced by Hartley transformation or number theoretic transformation.

[0116] Both the template image processing part 100 and the input image processing part 200 employ an inner product of edge normal direction vectors so that a correlation becomes proportionately higher with proximity between the directions of the edge normal direction vectors. This inner product is evaluated using an even-numbered times angle expression. For convenience, only a double size angle is hereinafter described as an example of even-numbered times angle, but the same effect with the present invention is produced using other even-numbered times angles such as a quadruple size or a sextuple size.

[0117] An edge extraction unit 1 in the template image processing part 100 applies differential processing (edge extraction) to a template image in x and y directions, and outputs an edge normal direction vector of the template image.

[0118] In this embodiment, a Sobel filter of Formula 2 is used for the x direction, and a Sobel filter of Formula 3 is used for the y direction.

[0119]

\begin{matrix} [\begin{matrix} - 1 & 0 & 1 \\ - 2 & 0 & 2 \\ - 1 & 0 & 1 \end{matrix}] & Formula 2 \end{matrix}

[0120]

\begin{matrix} [\begin{matrix} - 1 & - 2 & - 1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{matrix}] & Formula 3 \end{matrix}

[0121] An edge normal direction vector of the template image defined by the following formula is obtained with these filters.
{right arrow over (T)}=(T_X,T_Y) Formula 4

[0122] This embodiment takes an example in which an image of a person in a specific posture who is walking through a pedestrian crossing is extracted from an input image of the vicinity of the pedestrian crossing.

[0123] The template image of the person is that of FIG. 2(a), for example. If the filter processing of Formula 2 is applied to the template image of FIG. 2(a), a result (x component) as shown in FIG. 2(b) is obtained. If the filter processing of Formula 3 is applied to the template image of FIG. 2(a), a result (y component) as shown in FIG. 2(c) is obtained.

[0124] An evaluation vector generation unit 2 inputs an edge normal direction vector of the template image from the edge extraction unit 1, and outputs the evaluation vector of the template image to an orthogonal transformation unit 3 through processing described later.

[0125] First, the evaluation vector generation unit 2 normalizes the length of the edge normal direction vector of the template image according to the following formula.

[0126]

\begin{matrix} \vec{U} = (U_{X}, U_{Y}) = \frac{\vec{T}}{\langle \vec{T} \rangle} & Formula 5 \end{matrix}

[0127] Generally, the edge strength of the input image varies according to the existing photographic condition. However, an angular difference between the edges of the input and template images (or, a subordinate function value that varies according to this angular difference) is not susceptible to the photographic condition.

[0128] Therefore, in the present invention, the edge normal direction vector of the input image is normalized to a length of 1 in the input image processing part 200, as described later. According to this, the edge normal direction vector of the template image is normalized to 1 in length in the template image processing part 100.

[0129] As a result, the stability of pattern extraction is improved. Usually, it is desirable to have a normalization length of 1, but other constants can be used.

[0130] Concerning a trigonometric function, the following double size formula is established as is well known.
cos(2Θ)=2cos(Θ)²−1
sin(2Θ)=2cos(Θ)sin(Θ) Formula 6

[0131] The evaluation vector generation unit 2 calculates the evaluation vector of the template image defined by the following formula 7.

Formula 7

[0132] When assumed to be a threshold (for fine edge removal), the evaluation vector {right arrow over (V)} of the template image is:

[0133]

if \langle \vec{T} \rangle \geq a

\vec{V} = (V_{X,} V_{Y}) = \frac{1}{n} (\cos (2 α), \sin (2 α)) = \frac{1}{n} (2 U_{X}^{2} - 1, 2 U_{X} U_{Y})

else \vec{V} = \vec{0}

[0134] wherein n is the number of {right arrow over (T)} when |{right arrow over (T)}|≧a.

[0135] Formula 7 will be described. The reason why a vector smaller than constant “a” is set as a 0 vector is to remove a noise, for example.

[0136] Next, a description will be given of the fact that x and y components of this evaluation vector are each divided by “n” for normalization.

[0137] Generally, the shape of the template image is arbitrary, thereby leading to various edge shapes. For example, there is a situation in which the number of edges is small as shown in FIG. 8(a), or the number of edges is larger (than that of FIG. 8(a)) as shown in FIG. 8(b). Therefore, in this embodiment, the similarity is intended to be evaluated on the same scale by dividing it by “n” for normalization independent of whether the number of the edges is small or large.

[0138] However, the normalizing processing of dividing by “n” does not necessarily need to be performed. Normalizing processing may be omitted in a situation in which only one template image is used or in which only template images the same as the number of edges are used.

[0139] Next, a description will be given of the fact that the x and y components of Formula 7 serve as a subordination function of the cosine/sine for a double size of the x and y components of Formula 5.

[0140] If the inner product cos θ of an angle θ between an evaluation vector T of the template image and an evaluation vector I of the input image is used as a similarity scale as in the conventional technique, the following problem will arise.

[0141] For example, let us suppose that the template image is that of FIG. 7(a), and the input image is that of FIG. 7(b). In the background of FIG. 7(b), the left background part of an image of a specified object is brighter than the image of the specified object, and the right background part of the image of the specified object is darker than the image of the specified object.

[0142] If considered only from the images, the images of the specified object completely coincide with each other when the center of the template image of FIG. 7(a) coincides with the center of the input image of FIG. 7(b). Therefore the similarity value must be the maximum at this time. Herein, if the edge normal direction vector that is directed outward from the image of the object is positive, the edge normal direction vector must be directed in the same direction (outward/inward) in the brighter background part of FIG. 7(b) and in the darker background part thereof when deserving from the image of the specified object.

[0143] However, if the brightness of the background of FIG. 7(b) is uneven in the right and left background parts with the specified object are between these values at this time, the directions are opposed as shown by arrows in FIG. 7(b) (i.e., outward from the specified object in the brighter background part, and inward from the specified object in the darker background part). Originally, it is to reach the maximum similarity value. But the similarity value is not necessarily high in this case, and thereby a distorted perception is easily shaped.

[0144] A detailed description of the above problem is given with reference to FIG. 6. An angle between the evaluation vector T of the template image and the evaluation vector I of the input image is θ. Its inner product, i.e., cos θ, is used as a similarity value. The direction of the evaluation vector I of the input image has two possibilities, i.e., either I of FIG. 6 or I′ precisely opposite thereto because of unevenness in brightness of the background that exists in the periphery of the image of the specified object, as described above.

[0145] Therefore, the inner product used as a similarity scale could have two products, i.e., cos θ and cos θ′. Herein, θ+θ′=π, and cos θ′=cos(π−θ)=−cos θ.

[0146] Therefore, if cos θ is used as the similarity scale, a similarity value will be oppositely reduced when there is a need to act properly to increase the similarity value, and the similarity value will be oppositely increased when there is a need to act properly to reduce the similarity value.

[0147] In other words, according to the prior art similarity value, matching between the template image and the input image cannot be correctly evaluated. As a result, disadvantageously, a wrong recognition value is easily formed by the conventional technique, and a recognition result is clear even if images have the same shape.

[0148] Therefore, in the present invention, a cosine that is double the size of θ, i.e., cos(2θ) is used for the formula of the similarity value. Thereby, cos(2θ′)=cos(2θ) from the double size formula of Formula 6 even if cos θ′=−cos θ. In other words, the similarity value rises irrespective of the background when there is a need to act to increase the similarity value. Therefore, the matching therebetween is correctly evaluated in spite of the unevenness in brightness of the background. This applies to the quadruple size or the sextuple size as well as the double size.

[0149] Moreover, the properties of the similarity value monotonically decreasing with respect to angle θ do not change even if an even-numbered times angle cosine is used.

[0150] Therefore, according to the present invention, patterns are stably extracted by an even-numbered times angle evaluation regardless of the brightness condition of the background.

[0151] More specifically, the similarity value is defined by the following formula in the present invention.

Formula 8

[0152] Similarity value

[0153]

L (x, y) = \sum_{i} \sum_{j} K_{X} (x + i, y + j) V_{X} (i, j) + K_{Y} (x + i, y + j) V_{Y} (i, j)

[0154] {right arrow over (K)}=(K_X,K_Y): Evaluation vector of input image

[0155] {right arrow over (V)}=(V_X,V_Y): Evaluation vector of template image

[0156] Since Formula 8 consists only of addition and multiplication, the similarity value is linear for each evaluation vector of the input and template images. Therefore, when Formula 8 is subjected to Fourier transformation, Formula 9 is obtained by a discrete correlation theorem of Fourier transformation (reference: Fast Fourier Transformation translated by Hiroshi Miyakawa published by Science and Technology).
{tilde over (L)}(u,v)={tilde over (K)}_X(u,v){tilde over (V)}_X(u,v)*+{tilde over (K)}_Y(u,v){tilde over (V)}_Y(u,v)* Formula 9

[0157] {tilde over (K)}_X,{tilde over (K)}_Y: Fourier transformation values of Kx, Ky
[0158] {tilde over (V)}_X*,{tilde over (V)}_Y*: Fourier transformation complex conjugate of Vx, Vy

[0159] Hereinafter, Fourier transformation value represented as ˜, and complex conjugate represented as *.

[0160] The similarity value of Formula 8 is obtained by subjecting Formula 9 to inverse Fourier transformation. From careful consideration of Formula 9, the following two respects will become apparent.

[0161] (1) First, the Fourier transformation value of the template image and the Fourier transformation value of the input image is simply multiplied together in a transformation value that has been subjected to orthogonal transformation.

[0162] (2) Secondly, the Fourier transformation value of the template image and the Fourier transformation value of the input image do not need to be simultaneously calculated. That is, the Fourier transformation value of the template image may be calculated prior to that of the input image.

[0163] Therefore, in this embodiment, the template image processing part 100 includes a recording unit 5 to record the output of a compression unit 4 before inputting the input image. Thereby, after the input image is received in the input image processing part 200, the template image processing part 100 is not required to process the template image. The processing performance is thus concentrated on processing subsequent to the input image processing part 200 and a multiplication unit 10, thus improving the processing speed.

[0164] Next, a description is given of a structure subsequent to the evaluation vector generation unit 2. As shown in FIG. 1, in the template image processing part 100, the evaluation vector of the template image that is output from the evaluation vector generation unit 2 is subjected to Fourier transformation by the orthogonal transformation unit 3, and is output to the compression unit 4.

[0165] The compression unit 4 compresses the evaluation vector that has been subjected to Fourier transformation, and stores it in the recording unit 5. As shown in FIG. 3, the evaluation vector subjected thereto includes various frequency components in both x and y directions. By experiments carried out by the present inventors, it is known that sufficient accuracy is obtained by processing the low frequency components (e.g., halves on the low frequency side in the x and y directions, respectively) without processing all of the frequency components. In FIG. 3, the range (−a≦x≦a, −b≦y≦b) having no oblique line is an original one. The range (−a/2≦x≦a/2, −b/2≦y≦b/2) having oblique lines is the one that has been compressed. That is, the processing amount is ¼ as much as before.

[0166] Thereby, an object to be processed is compressed, and the processing speed is improved.

[0167] The compression unit 4 and the recording unit 5 is omitted when a data amount is small, or when high-speed processing is not required.

[0168] Next, the input image processing part 200 will be described. The input image processing part 200 performs almost the same processing as the template image processing part 100. That is, according to Formula 2 and Formula 3, the edge extraction unit 6 outputs an edge normal direction vector of the input image defined by the following formula.

Formula 10

[0169] Edge normal direction vector of input image
{right arrow over (I)}=(I_X,I_Y)

[0170] I_x: Derivative value of input image in x direction

[0171] I_y: Derivative value of input image in y direction

[0172] The evaluation vector generation unit 7 inputs the edge normal direction vector of the input image from the edge extraction unit 6, and outputs an evaluation vector of the input image defined by the following two formulas.

Formula 11

[0173] Length normalized vector of input image

[0174]

\vec{J} = (J_{X}, J_{Y}) = \frac{\vec{I}}{\langle \vec{I} \rangle}

Formula 12

[0175] When assumed to be a threshold (for fine edge removal), the evaluation vector {right arrow over (K)} of the input image is:
if |{right arrow over (I)}|≧a
{right arrow over (K)}=(K_X,K_Y)=(cos(2β), sin(2β))=(2J_X²−1,2J_XJ_Y)
else
{right arrow over (K)}={right arrow over (O)}

[0176] The input image processing part 200 differs from the template image processing part 100 only in the fact that normalizing processing of division by “n” is not performed. In other words, evaluation by the even-numbered times angle, the normalizing processing to 1 in length, and the noise removal processing are performed in the same way as in the template image processing part 100.

[0177] Next, a structure subsequent to the evaluation vector generation unit 7 will be described. As shown in FIG. 1, in the input image processing part 200, the evaluation vector of the input image that is output from the evaluation vector generation unit 7 is subjected to Fourier transformation by the orthogonal transformation unit 8, and is output to the compression unit 9.

[0178] The compression unit 9 compresses the evaluation vector that has been subjected to Fourier transformation, and outputs the result to the multiplication unit 10. Herein, the compression unit 9 compresses the object to be processed to the same frequency band as the compression unit 4 (e.g., halves on the low frequency side in the x and y directions, respectively, in this embodiment).

[0179] The compression unit 9 is, of course, omitted when the data amount is small, or when high-speed processing is not required, and the compression unit 9 is likewise omitted when the compression unit 4 is omitted in the template image processing part 100.

[0180] Next, the multiplication unit 10 and other construction subsequent to this will be described. When the processing in the template image processing part 100 and in the input image processing part 200 is completed, the multiplication unit 10 inputs a Fourier transformation value of each evaluation vector of the template and inputs images from the recording unit 5 and the compression unit 9.

[0181] Thereafter, the recording unit 5 performs a product-sum-calculation according to Formula 9, and outputs the result (i.e., the Fourier transformation value of the similarity value L) to an inverse orthogonal transformation unit 11.

[0182] The inverse orthogonal transformation unit 11 subjects the Fourier transformation value of the similarity value L to inverse Fourier transformation, and outputs the map L(x,y) of the similarity value L to a map processing unit 12. The map processing unit 12 extracts a high-value point (peak) from the map L(x,y), and outputs its position and its value. The map processing unit 12 and the construction subsequent to this is freely arranged if necessary.

[0183] Next, a processing example by the template image of FIG. 2 will be described with reference to FIG. 4 and FIG. 5. If the input image is as shown in FIG. 4(a), the edge extraction unit 6 extracts an edge component in the x direction as shown in FIG. 4(b), and extracts an edge component in the y direction as shown in FIG. 4(c).

[0184] As a result of the aforementioned processing, a similarity value map L(x,y) shown in FIG. 5(a) is obtained. Herein, the front end of the arrow indicated as the “maximum value” is a peak of this map, and, as is apparent from a comparison with the input image of FIG. 5(b), it is understood that the correct point is clearly recognized at only one point.

[0185] In the conventional technique, the calculation must be performed by the number of times of the product, i.e., 2AB in order to successively scan the template image on input images and to obtain ρ_γ0Formula 1 at each position, wherein the size of the input image is A(=2^γ) and the size of the template image is B. Herein, the number of calculations is evaluated by the number of times of the product with high calculation costs.

[0186] In contrast, in this embodiment, FFT is performed twice by the orthogonal transformation unit 3 and 8, the product sum calculation is then performed by the multiplication unit 10, and inverse FFT is performed once by the inverse orthogonal transformation unit 11. The number of calculations is merely the number of times of the product of 3{(2γ−4)A+4}+2A.

[0187] In a comparison of the number of calculations therebetween, the number of calculations of the product according to this embodiment is about 1/100 of the number of calculations of the product according to the conventional technique, if A=256×256=2¹⁶, and B=60×60. As a result, unusually high-speed processing is carried out.

[0188] The discrete correlation theorem of Fourier transformation cannot be used in such a nonlinear formula as Formula 1 of the conventional technique. Therefore, in the conventional technique, processing for the template image cannot be performed prior to that for the input image as shown in FIG. 1 of this embodiment. In other words, in the conventional technique, both the template image and the input image must be processed simultaneously. Also in this respect, the processing speed in this embodiment is higher than that in the conventional technique.

(Embodiment 2)

[0189] In this embodiment, a conjugate compression unit 13 and a conjugate restoring unit 14 are added to the elements of FIG. 1 as shown in FIG. 9. The conjugate compression unit 13 further halves the Fourier transformation value of the evaluation vector of the template image that has been read from the recording unit 5 by use of complex conjugate properties of Fourier transformation.

[0190] This respect will be described. The following formula is established for the spectrum obtained by real number Fourier transformation.
Ã(u,v)={tilde over (A)}(−u,−v)* Formula 13

[0191] In detail, a spectral value at a specific point is equal to the complex conjugate of a spectral value at a position symmetrical to that point in a uv coordinate system. Use of this property makes it possible to reduce the processing amount by half of the uv coordinate system as shown in FIG. 10(a). Since the compression unit 4 and the compression unit 9 further compress it, the data amount is reduced to ⅛ of the original data as shown in FIG. 10(b). Therefore, the processing speed is improved, and memory capacity is saved.

[0192] As a result, in this embodiment, the Fourier transformation value that the conjugate compression unit 13 has read from the recording unit 5 is halved, and is output to the multiplication unit 10. Thereafter, the conjugate reconstruction unit 14 performs processing by which the output from the multiplication unit 10 is doubled, and outputs the result to the inverse orthogonal transformation unit 11.

[0193] These constitute the basis of the present invention. A useful technique will be hereinafter disclosed by application of this basis.

(Embodiment 3)

[0194] In this embodiment, a first example and a second example will be described. A technique for performing face extraction by using an enlarged/reduced template image is disclosed in both examples. According to this technique, processing by use of similar templates different in size is carried out efficiently and at high speed. The application of this technique is not limited to face extraction.

First Example

[0195] FIG. 11(a) is a block diagram of a template image processing part 101 according to Embodiment 3 (first example) of the present invention. Some modifications have been made to the template image processing part 100 of FIG. 1 or FIG. 9 as shown in the figure.

[0196] First, when a template image is input to the template image processing part 101, the image is enlarged/reduced by a enlargement/reduction unit 15. Thereafter, the enlarged/reduced template image is output to an edge extraction unit 1.

[0197] When an evaluation vector generation unit 2 outputs the evaluation vector of the template image, an addition unit 16 applies addition processing to this. The data obtained by the addition processing is output to an orthogonal transformation unit 3.

[0198] The addition unit 16 performs addition processing for each size range according to the following formula.

Formula 14

Evaluation Vector of Template Image
{right arrow over (V)}=(V_X(x,y), V_Y(x,y))

[0199]

V_{X} (x, y) = \sum_{i = a}^{b} V_{Xi} (x, y)

V_{Y} (x, y) = \sum_{i = a}^{b} V_{Yi} (x, y)

wherein the size range is a b.

[0200] Although image processing is carried out using one template image in Embodiments 1 and 2, templates with multiple sizes may be processed using a plurality of templates in this embodiment.

[0201] Moreover, the sizes of the templates are separated into specific ranges, and a template processing result is superimposed thereon.

[0202] Referring now to FIG. 12, an example of an input image includes the face image of a person. In this example, a template image of a straight face, such as that of FIG. 13(a), is prepared. A template image of a face inclined at a specific angle as shown in FIG. 13(d) is also prepared. The degree to which the face to be prepared is inclined is appropriately selected.

[0203] When the edges of the template images of FIGS. 13(a) and 13(d) are extracted, appearances shown in FIG. 13(b) and 13(e), respectively, are obtained in this embodiment. Further, when the image of FIG. 13(a) or 13(d) is input, an evaluation vector corresponding to the edge image is generated as shown in FIG. 13(c) or 13(f).

[0204] As in Embodiments 1 and 2, data concerning the template images are stored in the recording unit 5.

[0205] When the input image is received, a procedure subsequent to those of the input image processing part 200 and the multiplication unit 10 is performed in the same way as in Embodiments 1 and 2.

[0206] Corresponding similarity value maps are calculated for superimposed template data of all size ranges of the template images. A detection result, such as that shown in FIG. 14, is obtained. As is apparent from FIG. 14, not only the overall position of the face but also its size and the positions of the main face parts, such as the eyes, nose, and mouth, are recognized.

[0207] At this time, it is desirable to display the processing result on a display or to output it to a printer as shown in FIG. 14 in the stage subsequent to the map processing unit 12.

[0208] According to First Example, the following effects are obtained:

[0209] (1) Even if template data in a specific size range is added, and image processing is performed with layered templates, a part similar to the template often shows a high similarity value. Therefore, when similarity values of all sizes are calculated, the processing of the product sum calculation part and the processing of the inverse orthogonal transformation part must be repeatedly performed NM times, wherein N is the number of templates, and M is the number of sizes. On the other hand, the number of processings reaches NM/H by use of the superimposed template, wherein H is the width of a superimposed range. Therefore, improvements in efficiency is accomplished, and image processing is carried out at a higher speed for face extraction, for example.

[0210] (2) Additionally, a rough candidate range of eyes, nose, and mouth are extracted not only merely by outputting the positional data for a face but also by superimposing the template on the face candidate position as shown in FIG. 14.

[0211] The positions of face parts, such the eyes, nose, and mouth, can also be more accurately extracted by processing the images in these ranges much more finely, as described in the following embodiments.

Second Example

[0212] In this example, a template image processing part 102 is constructed as shown in FIG. 11(b). That is, compared to the First Example, the position of the addition unit 16 is moved between the compression unit 4 and the recording unit 5. Thereby, the addition unit 16 performs addition processing according to the following formula 15.

[0213]

\begin{matrix} {\tilde{V}}_{X} (u, v) = \sum_{i = a}^{b} {\tilde{V}}_{Xi} (u, v) {\tilde{V}}_{Y} (u, v) = \sum_{i = a}^{b} {\tilde{V}}_{Yi} (u, v) & Formula 15 \end{matrix}

wherein the size range is a b.

[0214] The similarity value formula that is linear before being subjected to Fourier transformation is still linear after being subjected thereto. Therefore, the position of the addition unit 16 can be changed from the First Example to the Second Example, for example.

[0215] Thereby, an object to be processed by the addition unit 16 is reduced more than in the First Example because the object is compressed by compression unit 4. Therefore, processing speed is improved.

(Embodiment 4)

[0216] Referring now to FIGS. 15 and 16, Embodiment 4 discloses an efficient technique for enhancing the value of the maximum point of the similarity value map described in embodiments 1 and 2 into a stronger peak value.

[0217] Generally, in the similarity value map, a peak appears in a part overlapping the template image. In this embodiment, a peak pattern “p” around and including a maximum point is used as a filter for the similarity value map. The value of a part similar to the peak pattern in the similarity value map is amplified.

[0218] As shown in FIG. 15, in this embodiment, a peak pattern processing part 300 is added to the structure of FIG. 1 showing embodiment 1.

[0219] FIG. 16 shows a mask for this peak pattern. As indicated in FIG. 16, in this peak pattern, normalization is made to set an average value at 0.

[0220] In the peak pattern processing part 300, an orthogonal transformation unit 17 subjects this peak pattern to Fourier transformation, and a compression unit 18 compresses a Fourier transformation value before recording compressed data in a recording unit 19.

[0221] Since a mask is used, the similarity value formula is established not by Formula 8 but by the following formula 16 that reflects the mask.

Formula 16

[0222]

{\tilde{V}}_{X} (u, v) = \sum_{i = a}^{b} {\tilde{V}}_{Xi} (u, v)

{\tilde{V}}_{Y} (u, v) = \sum_{i = a}^{b} {\tilde{V}}_{Yi} (u, v)

wherein the size range is a b.
{tilde over (M)}(u,v)={tilde over (L)}(u,v){tilde over (P)}*

[0223] {tilde over (P)}: Peak pattern low frequency spectrum
[0224] L(u,v): Similarity value before filtering
[0225] M(u,v): Similarity value after filtering

[0226] The multiplication unit 10 reads data from the recording unit 5, the recording unit 19, and the compression unit 9, then performs a product-sum-calculation, and outputs the Fourier transformation value of the similarity value corrected by the peak pattern.

[0227] A peak pattern filter can filter the similarity value map L according to the following formula, but, if so, a large amount of product sum calculations will be inefficiently needed.

[0228]

\begin{matrix} M (x, y) = \sum_{l} \sum_{m} p (l, m) L (x, l, y + m) & Formula 17 \end{matrix}

[0229] In contrast, in this embodiment, simple, accurate processing is performed according to Formula 16 without performing a large amount of calculations like Formula 17.

[0230] Therefore, according to this embodiment, the peak point of the similarity value map is efficiently amplified. Additionally, a part similar to the template is clearly and stably detected from the input image while reflecting the peak pattern.

(Embodiment 5)

[0231] In this embodiment, a pixel mean in the range of the template image as well as the similarity value between the edge of the input image and the edge of the template image is added to a similarity judgment.

[0232] This structure is shown in FIG. 17. Like FIG. 15, a mask pattern processing part 400 is added to the structure of FIG. 1 of Embodiment 1.

[0233] However, the structure of FIG. 17 differs from that of FIG. 15 in that the mask pattern processing part 400 is used, not to input a peak pattern, but to input a template image. Also, a mask pattern generation unit 20 is provided for generating a mask pattern that depends on this image.

[0234] Like FIG. 15, the output of the mask pattern generation unit 20 is subjected to Fourier transformation by the orthogonal transformation unit 21. The result is then compressed by the compression unit 22, and the compressed data is recorded in the recording unit 23.

[0235] Further, since a mask is used, the similarity value formula is expressed not as Formula 8 but as the following formula that reflects the mask.

[0236]

\begin{matrix} Q (x, y) = L (x, y) + \sum_{l} \sum_{m} q (l, m) I (x + l, y + m) & Formula 18 \end{matrix}

[0237] Q(x,y): Pixel-average-added similarity value
[0238] q(l,m): Mask pattern
[0239] L(x,y): Similarity value before filtering
[0240] I(x,y): Input image data

[0241] For the same reason mentioned in Embodiment 4, a large amount of product sum calculations is inefficiently needed if multiplication is performed in this way.

[0242] Formula 19 is obtained by subjecting this to Fourier transformation, whereby the calculation is performed very simply.
{tilde over (Q)}(u,v)={tilde over (L)}(u,v)+{tilde over (q)}*(u,v){tilde over (I)}(u,v) Formula 19

[0243] The multiplication unit 10 performs a product-sum-calculation according to Formula 19.

[0244] Next, the relationship between the template image and the mask pattern is described with reference to FIG. 18. Herein, in order to add a pixel mean in the range of the template image to a similarity judgment, the mask pattern generation unit 20 generates a mask pattern as shown in FIG. 18(b) for a template image as shown in FIG. 18(a)

[0245] In greater detail, in the template image of FIG. 18(a), a value of 1/N is set at each point of the inner part (inside the circle) whose pixel mean is to be calculated, and a value of 0 is set at all other points. N is the number of points in the inner part, and the result of addition of the values of all points of the mask pattern is 1.

[0246] According to this embodiment, a mean of pixel values inside the image can also be added to the similarity value, and a specified object is extracted from the input image more accurately and more efficiently.

[0247] A mean of a square value of each pixel is calculated such that data in which each pixel of the input image is squared by the input image processing part is formed, and the same processing is applied thereto.

[0248] Therefore, a distributed value as well as a mean within a range is efficiently calculated.

(Embodiment 6)

[0249] Referring to FIG. 19, Embodiment 6 discloses a technique by which a bilaterally symmetric image with respect to a template image is efficiently processed. In addition to the structure of FIG. 1 of Embodiment 1, a symmetric vector generation unit 24 is provided between the recording unit 5 and the multiplication unit 10. As in Embodiment 1, Formula 8 is used as the similarity value formula in this embodiment.

[0250] Referring now to FIG. 20(a), a description is given of how to treat a bilaterally symmetric template image. For example, if the template image of FIG. 20(a) is an original image, a template image in which the original image has been bilaterally reversed is shown as in FIG. 20(b).

[0251] The relationship between the edge normal direction vectors of these template images is expressed by the following formula 20.

Formula 20

[0252] Edge normal direction vector of image resulting from subjecting original template image to bilateral reversal
{right arrow over (T)}′=(T′x(x,y),T′y(x,y)
T′x(x,y)=−Tx(−x,y)
T′y(x,y)=Ty(−x,y)

[0253] The evaluation vector of the template image that has been bilaterally reversed is expressed by the following formula 21.
{right arrow over (W)}=(Wx(x,y),Wy(x,y)): Evaluation vector of {right arrow over (T)}′
{right arrow over (V)}=(Vx(x,y),Vy(x,y)): Evaluation vector of {right arrow over (T)}
Wx(x,y)=2T′x²−1=2(−Tx(−x,y))²−1=2Tx(−x,y)²−1=Vx(−x,y
Wy(x,y)=2T′xT′y=2(−Tx(−x,y))Ty(−x,y)=−2Tx(−x,y)Ty(−x,y)=−Vy(−x,y Formula 21

[0254] Concerning Fourier transformation, because of the relation of Formula 22, Formula 23 is obtained by applying Formula 22 to Formula 21.
f(x)=g(−x)→{tilde over (f)}(u)={tilde over (g)}(−u) Formula 22
{tilde over (W)}_X(u,v)={tilde over (V)}_X(−u,v)
{tilde over (W)}_Y(u,v)=−{tilde over (V)}_Y(−u,v) Formula 23

[0255] In detail, the evaluation vector of the template image that has been bilaterally reversed is easily generated by, for example, reversing the positive and negative of the evaluation vector of the original template image.

[0256] Therefore, the evaluation vector of the template image that has been bilaterally reversed is obtained merely by allowing the symmetric vector generation unit 24 to apply Formula 23 to the evaluation vector of the original template image of the recording unit 5 in FIG. 19.

[0257] When simply assumed, there is no need to perform complex processing, such as a procedure in which the image of FIG. 20(b) is generated from the image of FIG. 20(a), and the evaluation vector is again calculated from the image of FIG. 20(b).

[0258] Thereby, the evaluation vector of the template image that has been bilaterally reversed is generated without direct calculations, and processing speed is improved. Additionally, recording capacity is saved because the need to purposely store the template image that has been bilaterally reversed is obviated.

(Embodiment 7)

[0259] Referring now to FIG. 22(b), in embodiment 7, eye/eyebrow extraction processing is added to the face extraction processing described in Embodiment 3. Eyes/eyebrow candidate range is roughly extracted from the input image of FIG. 22(a) according to the processing described in Embodiment 3.

[0260] Point biserial correlation coefficient filters shown in FIG. 23(a) through FIG. 23(d) are applied to each point of the image of this eye/eyebrow candidate range, a map of point biserial correlation values is then formed. Points where the correlation value in the map are high are set as an eye center point 3002 and as an eyebrow center point 3003, respectively.

[0261] The point biserial correlation coefficient η is defined by the following formula (reference; Multivariate Analysis Handbook, page 17, Modern Mathematics).

[0262]

\begin{matrix} η = \frac{\overline{x_{1}} - \overline{x_{2}}}{S} \sqrt{\frac{n_{1}}{n} (1 - \frac{n_{1}}{n})} & Formula 24 \end{matrix}

[0263] Overall range: addition of 1st range to 2nd range

[0264] n₁: Number of pixels of 1st range

[0265] n: Number of pixels of overall range

[0266] x₁: Average brightness level of 1st range

[0267] x₂: Average brightness level of 2nd range

[0268] S: Standard deviation of overall range

- [0269] Value in √ is constant when mask size is fixed.

[0270] FIG. 23(a) through FIG. 23(d), FIG. 23(a) show the positional relationships of all ranges. FIG. 23(b) shows an overall range mask. FIG. 23(c) shows a 1st range mask. FIG. 23(d) shows a 2nd range mask.

[0271] If the filter shape according to this point biserial correlation coefficient is formed as shown in FIG. 23(a), it is expected that the eyebrow center 3002 and the eye center 3003 are extracted as shown in FIG. 22(c).

[0272] Next, filter processing according to the point biserial correlation coefficient will be described.

[0273] First, main components of Formula 24 are expressed by the following formula 25.
x₁=ΣI(x+i, y+j)M1(i, j)
x₂=ΣI(x+i, y+j)M2(i, j)
x=ΣI(x+i, y+j)Ma(i, j)
x²=ΣJ(x+i, y+j)Ma(i, j) Formula 25

[0274] wherein
J(x, y)=I²(x, y)
x₁− x₂=ΣI(x+i,y+j)(M1(x,y)−M2(x,y))

[0275] M1: 1st range mask

[0276] M2: 2nd range mask

[0277] Ma: Overall range mask

[0278] I(x,y): Each pixel value of input image

[0279] The following formulas 26–28 are obtained by subjecting each component to Fourier transformation.
({tilde over ( x₁− x₂)})={tilde over (I)}({tilde over (M)}₁−{tilde over (M)}₂)* Formula 26
{tilde over ( x)}=Ĩ{tilde over (M)}_a* Formula 27
{tilde over ( x²={tilde over (J)}{tilde over (M)}_a* Formula 28

[0280] wherein
J(x, y)=I²(x, y)

[0281] In order to perform these processings, the structure of FIG. 21 is formed, for example. First, each mask of the overall range, the 1st range, and the 2nd range is subjected to Fourier transformation by the orthogonal transformation unit 51 through 53.

[0282] An input image and a result of the face extraction described in Embodiment 3 are input to the eye/eyebrow candidate range extraction unit 54 through the map processing unit 12. Based on these inputs, the eye/eyebrow candidate range extraction unit 54 extracts only the eye/eyebrow candidate range shown in FIG. 22(b) from FIG. 22(a). Data concerning this eye/eyebrow candidate range is subjected to Fourier transformation by an orthogonal transformation unit 55 without any changes. The result is then squared by a square unit 56, and is subjected to Fourier transformation by an orthogonal transformation unit 57.

[0283] Thereafter, data shown in Formula 27 is input through a multiplication unit 58 to an inverse orthogonal transformation unit 62 precedent to a η map forming unit 65. Likewise, data shown in Formula 26 is input to an inverse orthogonal transformation unit 63 through a multiplication unit 60, and data shown in Formula 28 is input to an inverse orthogonal transformation unit 64 through a multiplication unit 61. The input data is subjected to inverse Fourier transformation by the inverse orthogonal transformation unit 62 through 64, and is output to the η map forming unit 65.

[0284] Thereafter, the η map forming unit 65 performs a calculation according to Formula 24 when receiving the data from the inverse orthogonal transformation unit 62 through 64, and outputs a map η(x,y) of the point biserial correlation coefficient.

[0285] The eye/eyebrow center extraction unit 66 extracts two points having high values from the map η(x,y) output by the η map forming unit 65, and outputs them as the eyes center and an eyebrow center, respectively.

[0286] In this structure, multiplication must be performed roughly 15×15×N=225N times, wherein “15×15” (pixels) is the filter size of FIG. 23(a), and N is the number of pixels of the input image.

[0287] In contrast, according to this embodiment, the number of product calculations is roughly N+[(2γ−4)N+4]×5+12N+N+N=5N(2γ−1)+20 times. For convenience, the calculation of “√” is assumed to be equal to one multiplication processing.

[0288] That is, (calculation amount of this embodiment)<(calculation amount of the conventional technique) under the condition that γ is 22 or less.

[0289] Usually, a huge image in which N is 222 or more is not used. Therefore, it is understood that the image processing of this embodiment is smaller in the number of calculation times than that of the conventional processing, and is performed faster than that of the conventional processing.

[0290] Thus, according to this embodiment, the point biserial correlation coefficient filter processing is more efficiently performed.

[0291] The positions of other face parts, such as eye comers, mouth edges, nostrils, and irises, are calculated by variously changing the masks shown in FIG. 23(a) through FIG. 23(d).

(Embodiment 8)

[0292] This embodiment discloses a technique for expanding the function of the face extraction according to Embodiment 3 and extracting a mouth range, which is a facial organ, from a face image.

[0293] As described in Embodiment 3 with reference to FIG. 14, a mouth candidate range shown in FIG. 25(b) is extracted from the input image of FIG. 25(a).

[0294] When the extracted mouth candidate range is projected onto the Y-axis (i.e., when the total h of pixel values is plotted along the X-axis), a graph roughly shown in FIG. 25(c) is obtained.

[0295] The total h is defined by the following formula 29.

Formula 29

[0296]

h (x, y) = \sum_{i = x - w / 2}^{x + w / 2} I (x + i, y)

[0297] I(x,y): Each pixel value of input image

[0298] w: Width of mouth candidate range

[0299] h(x,y): Projection value

[0300] In order to efficiently obtain this total by use of orthogonal transformation, a mask shown in FIG. 25(d) is prepared. Formula 29 is rewritten like the following formula 30, including this mask.

[0301]

\begin{matrix} h (x, y) = \sum_{i = x - w / 2}^{x + w / 2} I (x + i, y) = \sum_{i, j} m (i, j) I (i + x, j + y) & Formula 30 \end{matrix}

[0302] m: Mask

[0303] When this is subjected to Fourier transformation, the following formula 31 is obtained.
{tilde over (h)}(u,v)={tilde over (m)}(u,v)*{tilde over (I)}(u,v) Formula 31

[0304] That is, this projection value is obtained by subjecting the input image and the mask pattern to Fourier transformation, thereafter performing the calculation of Formula 31, and subjecting the result to inverse Fourier transformation. Thereby, the map “h(x,y)” of the projection value “h” is obtained.

[0305] From the above result, it is desirable to form the structure of FIG. 24, for example. As shown in FIG. 24, the input image and the mask pattern are subjected to Fourier transformation by the orthogonal transformation unit 25 and 26, respectively.

[0306] Thereafter, the transformation value is multiplied by the multiplication unit 27, and is subjected to inverse Fourier transformation by the inverse orthogonal transformation unit 28. As a result, the map h(x,y) of the projection value is obtained.

[0307] The obtained map h(x,y) is developed by a projection data extraction unit 29. A maximum point extraction unit 30 calculates two maximum points from this map, and outputs the range between these maximum points as mouth range.

[0308] The mask pattern is, of course, beforehand subjected to Fourier transformation as in Embodiment 1, and, if so, processing performance is concentrated on the processing of the input image, so that processing speed is improved.

[0309] According to this embodiment, the position of the mouth, which is a facial organ, (more specifically, the positions of both the upper and lower lips) is accurately calculated.

(Embodiment 9)

[0310] This embodiment discloses a technique for expanding the function of the face extraction according to Embodiment 3, and for applying predetermined processing to a face image according to first and second examples of this embodiment.

First Example

[0311] In the first example, a digital watermark is embedded in an extracted face image. That is, the structure of FIG. 26 is formed. A result using part 600 is provided at the subsequent stage of the map processing unit 12 of FIG. 11.

[0312] The result-using part 600 includes a face image cutting-out unit 31 for separating an input image into a face image and a non-face image with reference to the input image and the face position that is determined by the map processing unit 12. The face image part is output from the face image cutting-out unit 31 to a digital watermark embedding unit 32. A predetermined digital watermark is embedded into the face image part. Such digital watermarks are so well known in the art that a detailed description thereof is considered unnecessary.

[0313] On the other hand, the part excluding the face image is output from the face image cutting-out unit 31 directly to an image synthesizing unit 33.

[0314] The image synthesizing unit 33 combines the face image into which the digital watermark is embedded with the part excluding the face image, and outputs an image into which the digital watermark has been embedded.

[0315] Therefore, with respect to, for example, an input image of FIG. 27(a), an output image of FIG. 27(b) into a face part of which a digital watermark has been embedded is obtained.

[0316] The name of a model to be photographed or the date of the photograph is suitable as a digital watermark.

[0317] According to this example, digital watermark data can be concentratively and easily embedded into a face part that may be subject to an attempt at falsification.

Second Example

[0318] In this example, specific editing is applied only to an extracted face image. That is, the structure of FIG. 28 is formed. A result-using part 601 is provided at the subsequent stage of the map processing unit 12 of FIG. 11.

[0319] The result-using part 601 includes the face image cutting-out unit 31 for separating an input image into a face image and a non-face image with reference to the input image and the face position that is determined by the map processing unit 12. The face image part is output from the face image cutting-out unit 31 to an image correction unit 34, and predetermined editing is applied to the face image part. Herein, such editing is well-known in the art.

[0320] On the other hand, the part excluding the face image is output from the face image cutting-out unit 31 directly to the image synthesizing unit 33.

[0321] The image synthesizing unit 33 combines the face image that has been edited with the part excluding the face image, and outputs an edited image.

[0322] Therefore, referring to, for example, an input image of FIG. 29(a), an output image in which a face range has been extracted like FIG. 29(b), and only a face part has been edited like FIG. 29(c) is obtained.

[0323] In an back-lit photographic image of a person, an image of the face part might be corrected so that the face color becomes whitish, to correct for the fact that the back-lit face is too dark and is hard to see. However, in editing by the image correction unit 34, such an image may be arbitrarily corrected.

[0324] According to this example, an image of only the face part is easily and selectively corrected, or, in other words, image correction is performed without exerting an influence on a part excluding the face.

Third Example

[0325] In this example, an extracted face image is corrected to be easily perceptible. That is, the structure of FIG. 30 is formed. First, a result-using part 602 is provided behind the map processing unit 12 of FIG. 11.

[0326] The result-using part 602 includes the face image cutting-out unit 31 for separating an input image into a face image and a non-face image. A face image that has been cut out is output to a face internal range extraction unit 35 and to the image correction unit 34.

[0327] According to the procedure described in Embodiment 3, the face internal range extraction unit 35 uses a template to calculate the positions of main face parts, such as eyes, nose, and mouth, from the cut-out face image, and extracts a facial inner image (i.e., the part of the image that is situated inside the facial boundary). In this example, the facial inner image is an image in a rectangular range having a predetermined size and centering the face center (e.g., the center of the nose). However, the size of the rectangular range is changed, and the center is located at a position slightly deviated from the face center.

[0328] The extracted facial inner image is output to an image feature extraction unit 36. The image feature extraction unit 36 calculates a useful feature for correction of a face image. In this example, the image feature extraction unit 36 calculates brightness distribution of a facial inner image, and outputs its result to a correction function determining unit 37 in the form of a brightness histogram. The image feature extraction unit 36 can, of course, output a brightness minimum value and a brightness maximum value in the brightness histogram to the correction function determining unit 37.

[0329] The correction function determining unit 37 determines a correction function by which the contrast of the facial inner image becomes clearer with reference to a feature input from the image feature extraction unit 36, and outputs this correction function to the image correction unit 34.

[0330] In this example, the image feature extraction unit 36 outputs the brightness histogram as mentioned above. Therefore the correction function determining unit 37 calculates a correction function so that the minimum brightness that appears in the histogram reaches the minimum brightness in the dynamic range, and the maximum brightness reaches the maximum brightness therein. Thereafter, the correction function determining unit 37 outputs the correction function to the image correction unit 34.

[0331] The horizontal axis of the brightness histogram of FIG. 30 indicates brightness values. It will be understood that only a part of the dynamic range that can express brightness is used. Therefore, the correction function determining unit 37 determines the correction function so as to filly use the dynamic range, and thereby the image correction unit 34 can correct the face image so that the image is easily discerned, or, more specifically, so that it can have abundant gradations in appearance. As a result of this correction, the face image is infallibly easily viewable although there might be a situation in which a part other than the face image is lightened or darkened.

[0332] Herein, since the correction function is determined on the basis only of the facial inner image, correction is never misled by a non-face part. Therefore, after correction, it is guaranteed that viewability of the face is improved.

[0333] Although FIG. 30 shows the drawing so as to make correction only to the cut-out face image, similar correction is made to the whole input image.

[0334] Further, as a feature to be sought by the image feature extraction unit 36, an index that represents the lightness/darkness of an image, such as brightness, is used as described above. In addition, a chroma average or a hue average may be used.

[0335] If the chroma average is used, the correction function determining unit 37 can output, for example, a chroma amplification coefficient to the image correction unit 34. If the hue average is used, the correction function determining unit 37 can output, for example, a hue rotational angle to the image correction unit 34.

[0336] Herein, a pale face image is more vividly corrected when the chroma average is used as a feature. When the hue average is used, a less reddish face image is corrected to be more reddish. In either case, the face image is made more natural. Additionally, a combination of two or more of brightness, chroma average, or hue average may be used as a feature.

[0337] Having described preferred embodiments of the invention with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one skilled in the art without departing from the scope or spirit of the invention as defined in the appended claims.

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

What is claimed is:

1. An image processing method comprising the steps of:

inputting a specified image for a template image;

inputting a specified image for an input image;

calculating an edge normal direction vector of said specified image;

generating an evaluation vector from said edge normal direction vector;

normalizing said evaluation vector of said template image by the number of edge normal direction vectors;

subjecting said evaluation vector to orthogonal transformation;

performing a product sum calculation of corresponding spectral data for each evaluation vector that has been subjected to orthogonal transformation;

subjecting a result of said product sum calculation to inverse orthogonal transformation and generating a map of similarity values; and

a formula of said similarity values, said orthogonal transformation, and said inverse orthogonal transformation each have linearity.

2. The image processing method of claim 1, further comprising the step of:

compressing each evaluation vector that has been subjected to orthogonal transformation so as to reduce a processing amount.

3. The image processing method of claim 1, wherein for said template image, the steps taken until said evaluation vector that has been subjected to orthogonal transformation is compressed are executed before said input image is input, and storing results thereof.

4. The image processing method of claim 1, further comprising the step of:

normalizing said evaluation vector with respect to a vector length.

5. The image processing method of claim 1, further comprising the steps of:

reducing a data amount using complex conjugate properties of orthogonal transformation before performing a product sum calculation; and

restoring said data amount after performing said product sum calculation.

6. An image processing method comprising the steps of:

inputting a specified image for a template image;

inputting a specified image for an input image;

enlarging/reducing said template image to various sizes;

calculating an edge normal direction vector of said specified image;

generating an evaluation vector from said edge normal direction vector;

subjecting said evaluation vector to orthogonal transformation;

subjecting said evaluation vector of each size to addition processing;

performing a product sum calculation of corresponding spectral data for each evaluation vector that has been subjected to orthogonal transformation;

subjecting a result of said product sum calculation to inverse orthogonal transformation and generating a map of similarity values; and

a formula of said similarity values, said orthogonal transformation, and said inverse orthogonal transformation each have linearity.

7. The image processing method of claim 6, wherein, for said template image, said addition processing of said evaluation vector is carried out after executing said step of compressing each evaluation vector so as to reduce the processing amount.

8. The image processing method of claim 1, wherein said template image is an image of a typified face.

9. The image processing method of claim 1, further comprising the steps of:

preparing a peak pattern that makes a peak of said similarity value steep; and

subjecting data of said peak pattern to orthogonal transformation to said product sum calculation.

10. The image processing method of claim 1, further comprising the steps of:

forming a mask pattern that depends on said template image; and

subjecting data of this mask pattern to orthogonal transformation to said product sum calculation.

11. The image processing method of claim 10, wherein said mask pattern includes an average of a number of pixels in an image of said template image.

12. The image processing method of claim 1, further comprising the steps of:

for said template image, processing positive and negative signs of said evaluation vector of said original template image; and

generating an evaluation vector of a bilaterally symmetrical image with respect to said original template image, by which said generated evaluation vector is applied to said product sum calculation.

13. The image processing method of claim 8, further comprising the steps of:

generating a map of point biserial correlation coefficients on the basis of an extracted face image; and

responsive to said correlation coefficients, calculating a position of said face part.

14. The image processing method of claim 8, further comprising the steps of:

calculating a distribution of projection values in a y-direction on the basis of said extracted face image by use of said mask pattern;

calculating two maximum points from said distribution; and

outputting a range between said two maximum points as a mouth range.

15. The image processing method of claim 8, further comprising the steps of:

dividing said input image into only said face image and parts other than said face image on the basis of said extracted face image;

embedding a digital watermark only into said face image;

combining said face image into which said digital watermark has been embedded with parts other than said face image to produce a combined result; and

outputting said combined result.

16. The image processing method of claim 8, further comprising the steps of:

dividing said input image into only said face image and parts other than said face image on the basis of said extracted face image;

editing only said face image;

combining said face image after editing with parts other than said face image to produce a combined result; are

outputting said combined result.

17. An image processing apparatus comprising:

a template image processing part operable to input a template image and calculate an edge normal direction vector of said template image, normalize said edge normal direction vector of said template image, generate an evaluation vector from said normalized edge normal direction vector, subject said evaluation vector to orthogonal transformation, and compress said evaluation vector that has been subjected to said orthogonal transformation so as to reduce the processing amount:

an input image processing part operable to input an input image and calculate an edge normal direction vector of said input image, generate an evaluation vector from said edge normal direction vector, subject said evaluation vector to orthogonal transformation, and compress said evaluation vector that has been subjected to said orthogonal transformation so as to reduce the processing amount;

an enlargement/reduction unit operable to enlarge or reduce said template image to various sizes;

a multiplication unit operable to perform a product sum calculation of corresponding spectral data about each evaluation vector that has been subjected to said orthogonal transformation and has been obtained for said template image and said input image;

an addition unit operable to perform addition processing of said evaluation vector of each size; and

an inverse orthogonal transformation unit operable to subject a result of said product sum calculation to inverse orthogonal transformation and further operable to generate a map of similarity values;

said evaluation vector including a component in which an edge normal direction vector of a specified image undergoes even-numbered times angular transformation, and a formula of said similarity values, said orthogonal transformation, and said inverse orthogonal transformation each have linearity.

18. The image processing apparatus of claim 17, wherein said template image processing part includes a recording unit operable to record said evaluation vector that has been compressed to reduce a processing amount and that has been subjected to orthogonal transformation, and a result obtained by compressing said evaluation vector that has been subjected to orthogonal transformation is stored in said recording unit before inputting said input image.

19. The image processing apparatus of claim 17, further comprising:

a conjugate compression unit between said recording unit and said multiplication unit;

said conjugate compression unit operable to reduce the data amount using complex conjugate properties of orthogonal transformation;

a conjugate restoring unit between said multiplication unit and said inverse orthogonal transformation unit; said conjugate restoring unit operable to restore the data amount reduced by use of the complex conjugate properties of orthogonal transformation.

20. The image processing apparatus of claim 17, wherein said addition unit is further operable to perform addition processing of said evaluation vector of said template image after compressing said vector so as to reduce the processing amount.

21. The image processing apparatus of claim 17, further comprising a peak pattern processing unit operable to subject a peak pattern by which a peak of a similarity value is made steep to orthogonal transformation and compress said peak pattern that has been subjected to said orthogonal transformation so as to reduce the processing amount, wherein a result obtained by subjecting data of this peak pattern to said orthogonal transformation is applied to a product sum calculation of said multiplication unit.

22. The image processing apparatus of claim 17, further comprising:

a mask pattern processing part operable to form a mask pattern that depends on said template image and generate data obtained by subjecting data of this mask pattern to orthogonal transformation and by compressing it, wherein a processing result of said mask pattern processing part is applied to a product sum calculation of said multiplication unit.

23. The image processing apparatus of claim 22, wherein said mask pattern includes a mean of a number of pixels inside an image of said template image.

24. The image processing apparatus of claim 17, further comprising:

a symmetric vector generation unit operable to process positive and negative signs of said evaluation vector of an original template image recorded in said recording unit, and further operable to generate an evaluation vector of a bilaterally symmetric image with respect to said original template image, wherein said evaluation vector generated by said symmetric vector generation unit is applied to a product sum calculation of said multiplication unit.

25. The image processing apparatus of 17, further comprising a map forming unit operable to form a map of a point biserial correlation coefficient on the basis of an extracted face image, and an extraction unit operable to calculate a position of a face part from the formed map.

26. The image processing apparatus of 17, further comprising a maximum point extraction unit operable to calculate a projection value distribution in a y direction by use of a mask pattern on the basis of an extracted face image, and further operable to calculate two maximum points from this distribution, and outputting a range between said maximum points such as a mouth range.

27. The image processing apparatus of 17, further comprising:

a face image cutting-out unit operable to separate an input image into only a face image and parts excluding said face image on the basis of an extracted face image;

a digital watermark embedding unit operable to embed a digital watermark only into the face image; and

an image synthesizing unit operable to combine said face image into which said digital watermark has been embedded with parts excluding said face image and outputting the combined data.

28. The image processing apparatus of 17, further comprising:

a face image cutting-out unit operable to separate an input image into only a face image and parts excluding said face image on the basis of an extracted face image;

an image correction unit operable to edit only said face image; and

an image synthesizing unit operable to combine an edited face image with parts excluding said face image and outputting them.

29. The image processing method of claim 8, further comprising:

cutting out a face image from said input image on the basis of an extracted face image;

extracting a facial inner image from said face image that has been cut out;

calculating a feature that correct said face image on the basis of said extracted face image;

determining a correction function on said basis of said obtained feature; and

applying image correction based on said determined correction function at least onto said face image that has been cut out.

30. The image processing method of claim 29, wherein said feature is a combination of at least two of brightness, chroma average, and hue average.

31. The image processing apparatus of 17, further comprising:

a face image cutting-out unit operable to cut out a face image from said input image on a basis of an extracted face image;

a face internal range extraction unit operable to extract a facial inner image from said face image that has been cut out;

a image feature extraction unit operable to calculate a feature that serves to correct said face image on a basis of said extracted face image;

a correction function determining unit operable to determine a correction function on a basis of said obtained feature; and

a image correction unit operable to apply image correction based on said determined correction function at least onto said face image that has been cut out.

32. The image processing apparatus of claim 31, wherein said feature is a combination of at least two of brightness, chroma average, and hue average.

Patent Citations (27)

Patent	Date	Inventor	Cited By
US5296945(A)	1994-03-01	Nishikawa et al.	Examiner
US5535288(A)	1996-07-01	Chen et al.	Examiner
US5751856(A)	1998-05-01	Hirabayashi	Examiner
US5781650(A)	1998-07-01	Lobo et al.	Examiner
US5905807(A)	1999-05-01	Kado et al.	Examiner
US5909501(A)	1999-06-01	Thebaud	Examiner
US5990901(A)	1999-11-01	Lawton et al.	Examiner
US6075898(A)	2000-06-01	Chase	Applicant
US6154566(A)	2000-11-01	Mine et al.	Examiner
US6195460(B1)	2001-02-01	Kobayashi et al.	Examiner
US6278791(B1)	2001-08-01	Honsinger et al.	Examiner
US6507660(B1)	2003-01-01	Wirtz et al.	Examiner
US6529630(B1)	2003-03-01	Kinjo	Examiner
US2001/0014182(A1)	2001-08-01	Funayama et al.	Examiner
US2001/0052928(A1)	2001-12-01	Imagawa et al.	Examiner
EP552770(A2)	1993-07-01		Applicant
JP5-028273	1993-02-01		Applicant
JP6-074732	1994-03-01		Applicant
JP10-063847	1998-03-01		Applicant
JP10-171989	1998-06-01		Applicant
JP11328359(A)	1999-11-01		Examiner
JP2000-030062	2000-01-01		Applicant
JP2000-099717	2000-04-01		Applicant
JP2000-148980	2000-05-01		Applicant
JP2000-149029	2000-05-01		Applicant
JP2000-209425	2000-07-01		Applicant
JP2000-242787	2000-09-01		Applicant

Non-Patent Literature (6)

Oh, Hwang-Seok, et al., “Digital Image Watermarking on a Special Object: the Human Face,” Proceedings of the SPIE, vol. 3971, Security and Watermarking of Multimedia Contents II, May 2000, pp. 536-544.Examiner
Johansson B et al.: “Detecting rotational symmetries using normalized convolution”; Sep. 3, 2000, Pattern Recognition, 2000, Proceedings, 15th International Conference on Sep. 3-7, 2000 at Los Alamitos, CA,; IEEE Comput. Soc. US, pp. 496-500, XP010533335; ISBN; 0-7695-0750-6; p. 496, Section 2: “Local orientation”, continued on the first two paragraphs of p. 497.Applicant
Rosenfeld A et al.:“Digital picture processing”; 1982, Digital Picture Processing, Orlando, Academic Press, US, vol. 1, XP002246743.Applicant
T. Awakura et al, “Automatic Recognition of Road Signs”; Technical Report of IEICE PRMU98-201 (Jan. 1999) pp. 69-76.Applicant
“Face Detection and Tracking using Edge Orientation Information” by Bernhard Fröba and Christian Küblbeck, Visual Communications and Image Processing 2001, Proceedings of SPIE vol. 4310, 2001, pp. 583-594.Applicant
English Language Abstract of JP 05-028273.Applicant