Image recognition method

[0002] 1. Field of the Invention

[0003] The present invention relates to an image recognition method which identifies an object by searching the position and orientation of the object included in the image data.

[0004] 2. Description of the Related Art

[0005] Various image recognition methods for identifying a specific object from image data have been known, but a general method is storing multi-grayscale image data obtained by shooting with a CCD camera (hereafter raw image data) in a memory and using binary images of this raw image data for identifying an object from background images other than the object. In the case of CCD where 1 pixel has 256 grayscales of resolution, for example image light to be input to CCD is sampled as 256 grayscale digital signals, then this sample is compared with a threshold value, and is converted into one of two types of digital signals (e.g. “0” or “1”).

[0006] The image recognition method using binary images, however, has the following drawbacks.

[0007] When a raw image includes a shadow of an object and mirror reflection light, the shadow of the object and the mirror reflection light are amplified to be noise during binarizing processing depending on the setting of the threshold value, which may cause object recognition error. For example, when a square object placed on a workbench is shot by a CCD camera (128×128 pixels) as shown in FIG. 23, the raw image has a luminance value distribution shown in the three-dimensional graph in FIG. 24. In the case of the raw image shown in FIG. 24, the difference in the luminance value distribution in the object, a wall disposed at the lower right of the object and the workbench is clearly shown. If the raw image shown in FIG. 23 is binarized, however, the binary image becomes like the one in FIG. 25, where the luminance value of the wall is amplified to the same level as the object, becoming noise, and it is difficult to identify the wall and the object.

[0008] Image recognition methods used for removing the noises are, a method of performing fine line processing on a binary image, or a method of recognizing the end points, branching points and length of a skeletal line, and crossing points and angle between skeletal lines, after performing fine line processing on a binary image so that geometric features of the object are extracted in order to identify the object. The problem of these types of methods is that the processing time is lengthy. In order to decrease the influence of the above mentioned noises, it is also possible to set two types of level values in advance, and to binarize only the image signals between these level values, however this method is inappropriate for image processing which requires real-time processing, since it is difficult to select the level values and processing time is long. In the case of a visual servo-mechanism using a feedback loop, for example, if the above mentioned processing methods are used, it takes too much time for the recognition processing of an object, and when the recognition processing of a moving object at a certain position is completed, the moving object has already moved to a distance position, which makes it difficult to trace the moving object.

[0009] Also, in the case of the above mentioned processing methods, the threshold level which was set becomes appropriate while the lighting conditions on the mobile object and background image change as the object moves, so a recognition error of the object occurs. In such a case, an optimum threshold value must be calculated again along with the conditional changes, but deciding on an optimum threshold value is difficult, and the processing time tends to be long.

[0010] Also, when a CCD image sensing device is used, the characteristics of the CCD change according to the ambient temperature environment, that is, the luminance value of the output image changes due to the change of the stored charge amount according to the light receiving amount of CDD, so a threshold value once set may become inappropriate. In such a case, the threshold value must be calculated again, and just like the above case, deciding on an optimum threshold value is difficult, and the processing time tends to be long.

[0011] With the foregoing in view, it is an object of the present invention to provide an image recognition method with a high real-time characteristic where (1) the position and orientation information of an object is accurately determined, regardless the noise and change of luminance value of the object caused by changes of the ambient environment, such as illumination conditions, without executing binary processing, and (2) the object can be accurately recognized at very high-speed.

[0012] To achieve the above object, the inventors energetically researched focusing on a genetic algorithm method (hereafter “GA method”) while performing research on an image processing method using raw image data without involving binary processing, and reached the present invention.

[0013] The image recognition method in accordance with the present invention comprises the steps of storing search models, where all or a part of shape and luminance value distribution of an object are modeled as image data in advance, obtaining input image data including the object, distributing the search models in the area of the input image data, and assigning the position and orientation information to each one of the search models as individual information, determining a function value to indicate correlation with the object for each one of the search models, and searching the solution of at least the position information of the object from the above input image data by evolving the search models using a genetic algorithm based on the above function values.

[0014] In other words, search models which overlap with the objects are generated by preparing the search models in advance and distributing the plurality of search models in the area of the above input image data. Here, a function value to evaluate the correlation between the object included in the above input image data and the search model (in the genetic algorithm, this function value is called the “goodness-of-fit”. This phrase is used hereafter) is determined, the degree to which the search model overlaps with the object is evaluated, the search models are evolved using the GA method based on this goodness-of-fit, and a solution on the position information and orientation information of the selected search models are regarded as the position information and orientation information of this object, in order to recognize this object. Since image processing is possible using multi-grayscale input image data itself, the amplification of noise caused by deviation of the threshold value from the optimum value, along with the change of the luminance value during binary processing, which occurs in the case of the conventional method, does not occur, and image processing can be executed smoothly, which makes it possible to accurately recognize the position information and orientation information of the object.

[0015] When a plurality of search models are distributed in the area of the above input image data, it is preferable to distribute the search models randomly by generating the position information and orientation information of each search model. By this method, all input image data can be efficiently searched.

[0016] For the above function value, the sum of values determined from the luminance value of the above input image data in the internal area of the search model can be used. By this method, the function value can be determined using simple and quick calculation.

[0017] It is also preferable to assign constraints for the evolution of the position and orientation information of the above search models, in order to limit the search range of the object included in the above input image data. By this method, a local search can be very efficiently executed, so that the recognition processing time for the object can be decreased considerably.

[0018] It is also preferable to regard a search model having the highest function value at a desired control timing as the optimum solution without waiting for the conversion of evolution, since the object can be recognized at ultra-high-speed and the moving object can be traced.

[0019] FIG. 1 is a functional block diagram depicting a configuration example of the image recognition equipment in accordance with the present invention;

[0020] FIG. 2 is a schematic diagram depicting a fish, which is an object, and a search model corresponding to this fish;

[0021] FIG. 3 is a diagram depicting a state where search models are randomly distributed;

[0022] FIG. 4 is a diagram depicting an example of a square object and its luminance value distribution;

[0023] FIG. 5 is a diagram depicting a state where an object in the input image data and a search model overlap;

[0024] FIG. 6 is an explanatory drawing depicting a two-dimensional shape search model;

[0025] FIG. 7 is a diagram depicting a frame model;

[0026] FIG. 8 is a diagram depicting a plane model;

[0027] FIG. 9 is a diagram depicting a plane-strip model;

[0028] FIG. 10 is image data when an image of a fish swimming in a tank is shot from the top;

[0029] FIG. 11 is a three-dimensional graph depicting a result when a goodness-of-fit is calculated using a frame model;

[0030] FIG. 12 is a three-dimensional graph depicting a result when a goodness-of-fit is calculated using a plane model;

[0031] FIG. 13 is a three-dimensional graph depicting a result when a goodness-of-fit is calculated using a plane-strip model;

[0032] FIG. 14 is a flow chart depicting an embodiment of search processing using GA;

[0033] FIG. 15 is a schematic diagram depicting a binary data array of position and orientation information of a search model;

[0034] FIG. 16 is an explanatory drawing depicting an embodiment of a genetic control;

[0035] FIG. 17 is a graph depicting a goodness-of-fit vs. number of alterations of generation when a frame model is used;

[0036] FIG. 18 is a graph depicting a goodness-of-fit vs. number of alterations of generation changes when a plane model is used;

[0037] FIG. 19 is a graph depicting a goodness-of-fit vs. the number of alterations of generation when a plane-strip model is used.

[0038] FIG. 20 is a schematic diagram depicting a state when a fish in a tank is caught and traced with a CCD camera secured to the hand of a manipulator;

[0039] FIG. 21 is an embodiment of a control flow of the visual servo-mechanism in accordance with the present invention;

[0040] FIG. 22 is a diagram depicting a state when the search models are randomly distributed;

[0041] FIG. 23 is an image when a square object placed on a workbench and a wall are shot from the top;

[0042] FIG. 24 is a graph depicting the luminance value distribution of the multi-grayscale image shown in FIG. 23; and

[0043] FIG. 25 is a graph depicting the luminance value distribution of the binary image, which is the multi-grayscale image shown in FIG. 23, after it is binarized.

[0044] 1 Image recognition equipment

[0045] 2 Image sensing means

[0046] 3 Raw image (multi-grayscale image) data

[0047] 4 Image memory

[0048] 5 Search model creation part

[0049] 5aShape modeling means

[0050] 5bLuminance value distribution modeling means

[0051] 6 Search model distribution means

[0052] 7 Genetic control part

[0053] 7aGoodness-of-fit calculation means

[0054] 7bRearrangement means

[0055] 7cSelection means

[0056] 7dCrossing means

[0057] 7eMutation means

[0058] 7fRegeneration means

[0059] 8 Fish (object)

[0060] 9 Model shape of fish

[0061] 10 Search model

[0062] 11 Search model

[0063] 11a11jSearch model

[0064] 12 Object

[0065] 13 Background image

[0066] 14 Search model

[0067] 20 Fish

[0068] 21 Image data

[0069] 22 Peak of goodness-of-fit of frame model

[0070] 23 Peak of goodness-of-fit of plane model

[0071] 24 Peak of goodness-of-fit of plane-strip model

[0072] 30 Hand of manipulator

[0073] 31 CCD camera

[0074] 32 Tank

[0075] 3333b, 33c, 33d, 33eSearch model

[0076] 34a, 34bSearch model

[0077] 35a, 35b, 35c, 35dSearch model

[0078] FIG. 1 is a functional block diagram depicting an image recognition equipment in accordance with the present invention. The image recognition equipment 1 in accordance with the present invention comprises an image memory 4 for storing multi-grayscale image data 3 which is shot by the image sensing means 2 and is output (hereafter raw image data), a search model creation part 5 for creating search models in advance by modeling the shape and luminance value distribution of the object, search model distribution means 6 for distributing a plurality of search models in the image sensing area of the raw image data 3 and assigning the position and orientation information to each one of the above search models, and a genetic control part 7 for executing image processing on each one of the distributed search models based on the genetic control, and finally the image recognition equipment 1 outputs the search result of the object included in the raw image data.

[0079] The search model creation part 5 further comprises shape modeling means 5afor modeling the object shape into polygons and three-dimensional shapes, and luminance value distribution modeling means 5bfor modeling the luminance value distribution of the object. In order to identify the object, fish 8, shown in FIG. 2, for example, the shape of the fish is modeled to a triangular shape 9, and the luminance value distribution of the fish is assigned to the area inside the triangle or the frame part.

[0080] The genetic control part 7 further comprises goodness-of-fit calculation means 7afor calculating the goodness-of-fit indicating the correlation between the object included in the raw image data and distributed search models, rearrangement means 7bfor rearranging the search models with assigning order of priority based on the above goodness-of-fit, selection means 7cfor selecting search models to remain active, crossing means 7dfor rearranging and crossing a part of a set or sets of Position and orientation information of the search models, mutation means 7efor randomly changing a part or all of the positional orientation information of the search models in order to cause mutation, and regeneration means 7ffor regenerating the search models before the above crossing or mutation.

[0081] In the search model distribution means 6, the plurality of search models 11a, 11b, 11c, . . . are randomly distributed in the image sensing area of the raw image data by setting the positions of the centers of gravity (X_p, Y_p) of the search models us shown in

[0082] FIG. 3. By this, the search models 11fand 11g, which overlap the object, the fish 8, are obtained.

[0083] Next, an example of a method for calculating the goodness-of-fit of the search model by the goodness-of-fit calculation means 7aof the genetic control part 7 will be described. As FIG. 4 shows, it is assumed that the shape of the object 12 is square, and the numbers written in squares 12a, 12b, 12c, . . . , which correspond to the pixels of the object 12, indicate the luminance values. For the search model of the object 12, a model having the same shape and same luminance value distribution as the object 12 is used.

[0084] It is also assumed that there is input image data which includes the object 12 in the background image 13 where the luminance value distribution is 1, as shown in FIG. 5(a) and (b), land that the search model 14 which overlaps with the object 12 is distributed on this input image data. At this time, the goodness-of-fit of the search model 14 is calculated according to the following procedure. At first, the product of the luminance value of the input image data and the luminance value of the search model 14 is calculated in each overlapping pixel 15, 15, 15, . . . Then the sum of the luminance values of all the pixels in the internal area of the search model 14 is calculated, and this sum of the luminance values is regarded as a goodness-of-fit. Therefore in the case of FIG. 5(a), the goodness-of-fit of the search model is 92, and in the case of FIG. 5(b), the goodness-of-fit of the search model is 156. The goodness-of-fit of a search model which does not overlap with the object is 70, which is the same as the sum of the luminance values of the object shown in FIG. 4. In this way, the correlation, that is, the degree of overlapping between the object and a search model becomes greater, the goodness-of-fit becomes greater, and the goodness-of-fit reaches its peak when the object and the search model match. When the search models 11a, 11b, . . . are distributed in the image sensing area of the input image data, using the same procedure as above, the goodness-of-fit can be calculated for each one of these search models. Based on the goodness-of-fit calculated in this way, the optimum solution of the position and orientation information of the object is searched using the later mentioned GA method.

[0085] Next, the processing content of the search model distribution means 6 and the goodness-of-fit calculation means 7aWill be more fully described. At first, a mathematical method for distributing the search models in the image sensing area of the input image data will be described. FIG. 6 is a schematic diagram for describing a search model with a two-dimensional shape. In the present invention, needless to say the search models can be applied not only to a two-dimensional but to a three-dimensional space as well. As FIG. 6 shows, the image sensing area Ω is defined as Ω={(X, Y}|0≦X≦X_max, 0≦Y≦Y_max}, and it is assumed that the search model 10 which center of gravity is at the origin is created in this sensing area is created. In this embodiment, the position of a search model indicates the position of the center of gravity of the search model. The luminance value m at a point (X₀, Y₀) in the internal area S of the search model 10, including borders, is given by the following formula.

[0086] m=m(X₀, Y₀)  (1)

[0087] The luminance value m in this embodiment is 1 within the internal area S (including borders) of the search model, otherwise it is 0. The present invention, however, is not limited to this, for the luminance value m may be a multi-grayscale value which can express shading, as seen in the search model shown in FIG. 5.

[0088] Next, a procedure for converting the internal area S of the search model 10 to the area Sp shown in the image sensing area Ω will be described. A point (X₀, Y₀) inside the internal area S of the search model 10 is converted to a point (X₁, Y₁) inside the internal area Sp of the search model 11, so that the search model 11 after conversion has the orientation angle θ at the position P (X_p, Y_p). $\begin{array}{cc}\begin{array}{c}\left(\begin{array}{c}{X}_1\\ Y_1\end{array}\right)=T\left(\theta \right)\left(\begin{array}{c}{X}_0\\ Y_0\end{array}\right)+\left(\begin{array}{c}{X}_p\\ Y_p\end{array}\right)\\ =\left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)\left(\begin{array}{c}{X}_0\\ Y_0\end{array}\right)+\left(\begin{array}{c}{X}_p\\ Y_p\end{array}\right)\end{array}& \left(2\right)\end{array}$

[0089] wherein T(θ) is rotational operator.

[0090] Also, according to the above conversion formula (2), the luminance value m (X₀, Y₀) before conversion is converted to the luminance value m_p(X₁, Y₁). The luminance value m_p(X₁, Y₁) of this embodiment is 1 inside the internal area S_pof the search model 11, otherwise it is 0. In this way, by specifying the positional coordinate (X_p, Y_p) and the orientation angle θ, the search models can be distributed in the image sensing area of the input image data according to the above conversion formula (2).

[0091] The multi-grayscale luminance value p inside the image sensing area Ω of the input image data is given by p=p (X, Y).

[0092] The goodness-of-fit function F (X_p, Y_p, θ) for calculating goodness-of-fit of a search model in accordance with the present invention is defined by the following formula (3).

[0093] F(X_p, Y_p, θ)=∫p(X, Y)m_p(X₁, Y₁)ds  (3)

[0094] In the above formula (3), ds is an area element in the, image sensing area Ω, and the integrated range is a common area of the image sensing area Ω and the internal area S_pof the search model 11. So if (X_p, Y_p, θ) is specified, the goodness-of-fit. F (X_p, Y_p, θ) when a search model is disposed at an arbitrary point (X_p, Y_p) in the image sensing area Ω at orientation angle θ can be calculated. In this embodiment, the integrated value, which is the product of the luminance value of the input image data and the luminance value of the search model, is used as shown in the above formula (3) as an appropriate example to indicate the correlation between the search model and the object, but the goodness-of-fit to indicate the correlation between the search model and the object may be determined using a value determined from the above input image data and the luminance value of the search model. For example, a mean value <m> of the luminance value m of the search model is determined, an absolute value of deviations of this pixel is determined using this mean value <m>, and the sum of the inverse number S of the mean values is regarded as a goodness-of-fit, or more simply, the sum of the input image data p and the luminance value m of the search model or the sum of the absolute value of the difference between the input image data p and the luminance value of the search model can be regarded as a goodness-of-fit.

[0095] The above value of goodness-of-fit changes depending on how the luminance value distribution is assigned to search models. Preferable search models are (1) a frame model bordering the contour of the object, (2) a plane model matching. the shape of the object, and (3) a plane-strip model where a strip of an additional area is added around the above plane model considering the differential information based on brightness around the object. These models will be described below with reference to FIG. 7-FIG. 9. FIG. 7 is a diagram depicting a frame model, FIG. 8 a plane model, and FIG. 9 a plane-strip model.

[0096] In the case of the frame model shown in FIG. 7, the search model is modeled in a rectangular shape and has a luminance value distribution only in the frame area S₁. The luminance value in each element dS₁, dS₂, . . . dS_i, . . . of the frame area S₁is set to 1, and the luminance values in the other area are set to 0. Therefore the goodness-of-fit function F in the above formula (3) is transformed as follows. $\begin{array}{cc}\begin{array}{c}F\left(X_p,Y_p,\theta \right)=p_1{m}_{\mathrm{p1}}+p_2{m}_{\mathrm{p2}}+\dots +p_i{m}_{\mathrm{pi}}+\dots \\ =p_1+p_2+p_3+\dots +p_i+\dots \\ ={\Sigma }_i{p}_i\\ =\left(\mathrm{Sum}\mathrm{of}\mathrm{luminance}\mathrm{values}p\mathrm{in}\mathrm{the}\mathrm{frame}\mathrm{area}{S}_1\right)\end{array}& \left(4\right)\end{array}$

[0097] In the above formula (4), p_iis a luminance value of the image sensing area 9 corresponding to the i-th element dS₁in the frame area S₁, and m_piis a luminance value of the i-th element dS_iin the frame area S_i. In this embodiment, the setting is m_pi=1.

[0098] In the case of the plane model shown in FIG. 8, the search model is modeled in a rectangular shape and has a luminance value distribution in the internal area S₂. The luminance value of each element dS₁₁, dS₁₂, . . . dS₂₁, . . . in the internal area S₂is set to 1, and the luminance values in the other areas are set to 0. Therefore, the goodness-of-fit function F in the above formula (3) is transformed as follows. $\begin{array}{cc}\begin{array}{c}F\left(X_p,Y_p,\theta \right)=p_{11}{m}_{\mathrm{p11}}+p_{12}{m}_{\mathrm{p12}}+\dots +p_{\mathrm{ij}}{m}_{\mathrm{pij}}+\dots \\ =p_{11}+p_{12}+p_{13}+\dots +p_{\mathrm{ij}}+\dots \\ ={\Sigma }_i{\Sigma }_j{p}_{\mathrm{ij}}\\ =\left(\mathrm{Sum}\mathrm{of}\mathrm{luminance}\mathrm{values}p\mathrm{in}\mathrm{the}\mathrm{internal}\mathrm{area}{S}_2\right)\end{array}& \left(5\right)\end{array}$

[0099] In the above formula (5), p_ijis a luminance value f the image sensing area Ω corresponding to the element dS_ijat the i-th row and j-th column in the internal area S₂, and m_pijis a luminance value of the element dS_ijat the i-th row and j-th column in the internal area S₂. In this embodiment, the setting is m_pij=1.

[0100] In the case of the plane-strip model shown in FIG. 9, the search model is modeled in a rectangular shape and has a strip of additional area K_ioutside the border of the internal area S₂of the plane model, and the luminance value in each element dS₁₁, dS₁₂, . . . in the internal S₂is set to 1, the luminance value in each element dK₁, dK₂, . . . of the additional are K₁is set to −1, and the luminance values in the other areas are set to 0. Therefore, in the same way as the above formulas (4) and (5), the goodness-of-fit function F of the formula (3) is transformed as follows. $\begin{array}{cc}\begin{array}{c}F\left(X_p,Y_p,\theta \right)={\Sigma }_i{\Sigma }_j{p}_{\mathrm{ij}}-{\Sigma }_k{p}_k^{\prime }\\ =\left(\mathrm{Sum}\mathrm{of}\mathrm{luminance}\mathrm{values}p\mathrm{in}\mathrm{the}\mathrm{internal}\mathrm{area}{S}_2\right)\\ =\left(\mathrm{Sum}\mathrm{of}\mathrm{luminance}\mathrm{values}{p}^{\prime }\mathrm{in}\mathrm{the}\mathrm{additional}\mathrm{area}{K}_1\right)\end{array}& \left(6\right)\end{array}$

[0101] In the above formula (6), P_ijis a luminance value of the image sensing area Ω corresponding to the element dS_ijat i-th row and j-th column in the internal area S₂, and pk′ is a luminance value of the image sensing area Ω corresponding to the k-th element dK_kin the additional area K₁. In this way, disposing a strip of additional area and setting the luminance value distribution in this additional area to be a negative value, the change of luminance value of the area around the object is considered in the goodness-of-fit function of the plane-strip model, therefore the object can be accurately detected.

[0102] The above frame model, plane model and plane-strip model are modeled in a rectangular shape, but the present invention is not limited to this, and can be modeled in various shapes, such as a triangular shape and a three-dimension shape. Also for this embodiment, three values, 0, 1 and −1 are used as the luminance values of the search models, but the present invention is not limited to this, where multi-grayscale values to express shading can be used. When multi-grayscale values are used for the luminance values of the search models, the goodness-of-fit can be determined not by the above formulas (4), (5) and (6) but by the sum of the products of the luminance values m of the search models and luminance value p of the input image data.

[0103] In order to validate the effect of the above frame model, plane model and plane-strip model, the goodness-of-fit of the image data 21 (128×128 pixels) on the fish 20 swimming in the tank is shot from the top, as shown in FIG. 10, was calculated for each pixel by using the goodness-of-fit functions of the formulas (4) to (6) above, and the result was created into a three-dimensional graph. The shape of the search model is triangular, as shown in FIG. 2, and the orientation angle θ was set to 0. For the goodness-of-fit, a normalized value was used. The results are shown in FIG. 11 (frame model), FIG. 12 (plane model) and FIG. 13 (plane-strip model).

[0104] As these figures show, the goodness-of-fit increases as the search model approaches the position of the fish 20, and reaches the peak when the search model overlaps with the fish 20. In the case of the frame model shown in FIG. 11, the difference of goodness-of-fit between the object (fish) and the background image (water surface) is small, but a peak 22 appears near the object, whereas in the case of the plane model shown in FIG. 12, a gentle peak 23 appears, and in the case of the plane-strip model shown in FIG. 13, a sharp peak 24 appears. Therefore in this case, the position and orientation of the object can be most accurately detected with the plane-strip model, but the sharp peak means that it takes more time to detect the position and orientation compared with the frame model and plane model. With the plane model which has a gentle slope near the peak, on the other hand, it takes little time to obtain a solution around the peak, since this model is flexible with small deviations.

[0105] Next, a genetic control in the genetic control part 7, that is, a search method using a GA (Genetic Algorithm) will be described. GA is an artificial model used to simulate the evaluation mechanism advocated by J. H. Holland and others in the USA who learned from the adaptation process in living systems in nature based on genetic information and natural selection. The references on GA include: “J. H. Holland: Adaptation in Natural and Artificial Systems, Univ. of Michigan Press (1975), MIT Press (1992)”, “D. E. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley (1989)”, Ankyoin, Nagao: Genetic Algorithms, pp. 53-81, Shokodo (1993)”, and “Nobuo Sannomiya, Hajime Kita, Hisashi Tamaki, Takashi Iwamoto: Genetic Algorithms and Optimization, compiled by the System Control Society, Asakura Shoten (1998)”.

[0106] With reference to FIG. 14, an example of search processing using GA will be described next. At first, raw image data, including the object, is obtained from an image sensing means, such as a CCD camera, and is stored in the image memory (Step 1). Then a plurality of search models are randomly distributed in the image sensing area of the raw image data, the position and orientation information is assigned to each one of the search models as individual information, and these search models are regarded as first generation individuals (Step 2). Specifically, the respective position and orientation of each search model is randomly generated using pseudo-random numbers or physical random numbers, and a set of first generation search models is generated. For example, 23 bits of the binary data array shown in FIG. 15 is prepared for each search model, where the first 7 bits are allocated to a position in the X direction (X), next 7 bits are allocated to a position in the Y direction (Y), and the last 9 bits are allocated to an orientation (θ) and the numeric values of (X, Y, θ) are randomly generated.

[0107] Next, the goodness-of-fit for each one of the above search models is calculated using the above mentioned goodness-of-fit function (Step 3). Then it is determined whether this search processing is terminated based on the later mentioned “GA termination conditions” (Step 4), and if the search processing is continued, the first generation search models are “rearranged” in the sequence of goodness-of-fit (Step 5). In this way individuals having a higher goodness-of-fit are “selected” and survive (Step 6). Also, a part of the position and orientation information of a set or sets of search models, out of the selected search models, are recombined and “crossed” at a predetermined probability (Step 7). In addition to the crossed search models, a part of the search models before crossing may be “regenerated” here (Step 7).

[0108] Next, a part or all of the position and orientation information of the search models which are crossed or regenerated in this way are randomly changed for “mutation” (Step 8). In addition to the mutated search models, a part of the search models before mutation may be “regenerated” (Step 8). For example, in the case of the position and orientation information in FIG. 15, a part or all of each bit string of the positions X and Y and orientation θ are “mutated”. Mutating the lower bit string of the positions X and Y, in particular, is effective for a local search where the search range is restricted, and mutating the entire bit string is effective for a global search.

[0109] At the end of the above genetic control, the second generation individuals are generated. Then the second generation individuals are fed back and the above mentioned Step 3 and later genetic control is executed repeatedly. Here, “GA termination conditions” (Step 4) is set, for example, to terminate the search processing when the goodness-of-fit matches the condition to reach a peak (condition when the slope of goodness-of-fit becomes a negative near the solution of the position and orientation information). GA termination condition may be set to terminate the search processing when the goodness-of-fit converges to a threshold value or more even if the goodness-of-fit reaches the peak, or terminating the search processing after one generation to several generations of short cycles have elapsed without waiting for the convergence of the goodness-of-fit. Particularly when a real-time operation is required, it s preferable to regard the position and orientation information of a search model having the highest goodness-of-fit as the optimum solution without waiting for the convergence of the goodness-of-fit.

[0110] It is not always necessary to execute genetic control in the sequence of “rearrangement “selection”, “crossing and regeneration” and “mutation and regeneration”, as shown in this embodiment, but one, two or more types of control out of these may be used combined in an appropriate sequence.

[0111] As a more concrete embodiment, genetic control using the position and orientation information comprised of 8-bit binary data array will be described with reference to FIG. 16. At first, it is assumed that there is position and orientation information G₁, G₂, . . . G₆of the N-th generation search models, then the position and orientation information G₁, G₄and G₅, which have the highest third goodness-of-fit out of these search models are selected as information on superb individuals, and are rearranged in the sequence of goodness-of-fit so as to generate the position and orientation information G₁′-G₃′. Then a part of this position and orientation information G₁′-G₃′ are crossed by mutually recombining so as to generate the position and orientation information G₄″, G₅″ and G₆″, and at the same time, the position and orientation information before crossing, that is, G₁′-G₃′, are regenerated so as to generate the position and orientation information G₁″, G₂″ and G₃″. And based on an appropriate probability, the position and orientation information G₄″ and G₆″ are selected, then the lower 3 bits of G₄″ are mutated from “0” to “1”, the lower 1 bit of G₆″ is mutated from “1” to “0”, and the N+1th generation individuals (search models) are generated.

[0112] Genetic control was actually performed based on the flow shown in FIG. 14 using the multi-grayscale image shown in FIG. 10. The result is shown in FIG. 17 (frame model), FIG. 18 (plane model) and FIG. 19 (plane-strip model).

[0113] In each graph, the abscissa indicates the “number of alternations of generations” and the ordinate indicates the highest goodness-of-fit” among the search models existent in each generation. The graph of the frame model shown in FIG. 17 has a gentle curve, and converges to about 0.8 at around the 130^thgeneration, and the graph of the plane model shown, in FIG. 18 converges to about 0.82 at around the 70^thgeneration, presenting very good convergence. In the graph of the plane-strip model shown in FIG. 19, on the other hand, convergence is good up to around the 40^thgeneration, but declines in later generations since the curve ascends very gently. For all of the plane model, frame model and plane-strip model, the object was detected and the peak of goodness-of-fit was generated regardless the fluctuation of environmental conditions, such as illumination, and regardless the changes of the level of goodness-of-fit.

[0114] In this way, the present invention can search position information and orientation information of an object using raw image data without using binary images like a conventional search method.

[0115] Next, a method of limiting the search range for an object includes in the input image data by adding constraints to the evolution of the position and orientation information of the distributed search models will be described with reference to FIG. 20-FIG. 22.

[0116] As FIG. 20 shows, there is a visual servo-mechanism where a CCD camera 31, secured on the hand 30 of the manipulator which is driven in the X-Y direction, is moved above the fish 33 swimming in the tank 32, so as to trace the fish. Since the object, the fish 33, always moves, it is difficult to predict the movement. So, if the convergence of goodness-of-fit of the individuals (search models) waited for a predetermined time and the hand 30 is then moved to a position based on the instructed value, the fish may no longer exist there. Therefore it is preferable that a search model which has the highest goodness-of-fit among the search models, after a short cycle of the first generation to several generations, is regarded as the optimum solution without waiting for convergence of the goodness-of-fit, so as to improve the speed of searching a solution, and the position and orientation information of the search model is instructed to the manipulator.

[0117] FIG. 21 is an embodiment of the control flow of such a visual servo-mechanism. When the raw data, including the object output from the CCD camera 31, is input (Step 20), many search models 33a, 33b, 33c, 33dand 33eare randomly distributed throughout the entire image sensing area of the raw image data, as shown in FIG. 22 (Step 21). Here, a binary data array comprised of 23-bits as shown in FIG. 15 is used for the position and orientation information of the search models, where 7 bits are allocated to the position X, 7 bits to the position Y, and 9 bits to the orientation angle θ. Then, the goodness-of-fit F is calculated for each search model (Step 22), priority is assigned to the search models, rearranging them in the sequence of goodness-of-fit (Step 23), a search model having the highest goodness-of-fit is regarded as the optimum solution (Step 24), the position and orientation information on this search model is instructed to the control system of the manipulator (Step 25), and the CCD camera 31 is moved to this position.

[0118] Next, it is determined whether the goodness-of-fit F exceeds the predetermined set value S for each one of the search models (Step 26), then if the goodness-of-fit F exceeds the value S, this search model is regarded as a probable individual and the lower 2 bits of the position X and the position Y respectively and all the bits of the orientation angle θ among the position and orientation information are randomly changed in order to cause mutation (Step 27), and if the goodness-of-fit F is the threshold value S or less, the individual is regarded as unnecessary, and all 23 bits of the position and orientation information of this search model are randomly changed in order to cause mutation (Step 28). In other words, a value S is set in advance such that the goodness-of-fit F of a search model 33e, which significantly overlaps with the object 8, sufficiently exceeds the value S, as shown in FIG. 22, then if a search model meets this condition, the position and orientation information of the search model 33eis locally mutated in the Step 27 so as to generate the search models 34aand 34bshown by the two-dot chained lines, near the probable individual, and for the search models 33a, 33b, 33cand 33d, which do not overlap with the object and have the goodness-of-fit F which is less then the value S, all the position and orientation information of the search models 33a, 33b, 33cand 33dare mutated in the Step 28, so as to generate new search models 35a, 35b, 35cand 35dshown by the dotted lines. In this way, the mutation in the Step 27 is effective to search the object locally, and the mutation in the Step 28 is effective to search the object globally.

[0119] The new search models generated in this way are stored in the image memory, and when raw image data output from the CCD camera 31 is input again (Step 20), the search models stored in the image memory are fed back, the goodness-of-fit F is calculated for these search models (Step 22), and the processing in Steps 23, 24, . . . is executed repeatedly as mentioned above. The visual servo-mechanism based on such feedback control executes the global search (Step 27) and the local search (Step 28) simultaneously, and obtains the optimum solution without waiting for convergence of the goodness-of-fit (Step 24), so it is possible to accurately recognize and trace the object at very high-speed

[0120] In the above embodiment, search models, where all shape and luminance value distributions of the object are modeled, are used, but the present invention is not limited to this and search models where a part of the shape and luminance value distributions of the object, including characteristic points, are extracted and modeled, may be used.

[0121] Another application example involves applying the image recognition method in accordance with the present invention to human face image collation processing. Specifically, the face image, which is the object, is input as multi-grayscale input image data, and this face image and search models registered in the database are pattern-matched using the above mentioned image recognition method. Here, search models where a plurality of characteristic points (e.g. ridge of the nose, lines of eyes and mouth) are extracted from the registered face images are prepared. So a plurality of search models are prepared for each one of the registered face images. And the face image, which is the object, and the search models including the characteristic points, are sequentially pattern-matched. If the image recognition method in accordance with the present invention is used, image processing is executed at high-speed without involving binary processing, so collation processing for an enormous number of registered face images can be executed at very high-speed.

[0122] For the above mentioned raw images, not only monochrome but also color images using multi-color signals can be processed in the same way.

[0123] For the above mentioned raw image data, not only digital image data, which is output from such digital equipment as a CCD camera, but also A-D converted analog image data, which is output from a video for example, can be used.

[0124] In this way, according to the image recognition method of the present invention, a function value to indicate the correlation with the object is determined for each one of the search models distributed in the area of the input image data, and the search models are evolved and selected using the genetic algorithm method based on the function value, so as to search the solution of at least the position information of the object out of the above input image data, therefore, binary processing for multi-grayscale input image data is unnecessary, amplification of noise due to binary processing can be avoided, and the position information and orientation information of the object can be accurately determined, to recognize the object, recognized regardless the change of luminance value of the object due to environmental changes. Also, the position information of the object included in the raw image can be obtained without executing threshold setting processing and geometric characteristic extracting processing, such as fine line processing, which are required for binary processing, so smooth image processing can be executed.

[0125] Also, by using a method of limiting the search range of the object included in the above input image data by assigning constraints to evolve the position and orientation information of the search models, a quick search focusing on a local area is possible, and it is possible to quickly recognize the object even for an application where real-time processing is required.

[0126] Also, by regarding the position and orientation information of a search model which has the highest function value at a desired control timing without waiting for convergence of evolution, the object can be searched at very high-speed, and a moving object in particular can be accurately recognized and traced.