Patent Publication Number: US-8527439-B2

Title: Pattern identification method, parameter learning method and apparatus

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a parameter learning method for identifying a pattern of an input signal, such as image recognition, and a pattern identification method using the same. 
     2. Description of the Related Art 
     Many techniques have heretofore been conceived as a pattern identification method for classifying input data into predetermined classes, such as character recognition, face detection and gait authentication, and various new techniques are still being proposed with the goal of increasing the processing speed and improving the classification accuracy. For example, Viola &amp; Jones (2001) “Rapid Object Detection using a Boosted Cascade of Simple Features”, Computer Vision and Pattern identification (hereinafter Document 1) proposes to achieve a high-speed and highly accurate pattern identification method by combining a learning method based on AdaBoost and a technique for cascade-connecting weak classifiers using a weak classifying method, which can perform computation in a short time. 
     Another method has also been proposed in which weak classifiers are connected in a tree structure to achieve classification into three or more classes. For example, according to Huang, Ai, Li &amp; Lao (2005) “Vector Boosting for Rotation Invariant Multi-View Face Detection”, International Conference on Computer Vision (hereinafter, Document 2), face images to which orientation and inclination are labeled are learned, a face in a test image is detected, and its direction and inclination are determined. 
     As described above, techniques for performing high-speed and highly accurate pattern identification on an input image have been proposed. For example, it is required to identify the presence or absence of a face in an input image, or the presence or absence of a specific pattern (texture) with high speed and high accuracy so as to finely capture an image of a human face with an imaging apparatus or to correct a face image. However, conventional techniques as described above are not satisfactory. 
     SUMMARY OF THE INVENTION 
     The present invention has been conceived in light of the foregoing, and it is an object of the present invention to achieve a pattern identification process for identifying input data that belongs to either of two classes with high speed and high accuracy. 
     According to one aspect of the present invention, a pattern identification method for classifying input data into a first class or a second class by sequentially executing a combination of a plurality of classification processes, 
     wherein at least one of the plurality of classification processes comprises: 
     a mapping step of mapping the input data in an n-dimensional feature space as corresponding points, where n is an integer equal to or greater than 2; 
     a determination step of determining whether the input data belongs to the first class or the next classification process should be executed based on the location of the corresponding points mapped in the mapping step in the n-dimensional feature space; and 
     a selecting step of selecting a classification process that should be executed next based on the location of the corresponding points when it is determined in the determination step that the next classification process should be executed. 
     According to another aspect of the present invention, a parameter learning method for learning a parameter for pattern identification that classifies input data into a first class or a second class, the method comprises: 
     an input step of inputting a plurality of learning data items labeled as the first or second class; 
     a mapping step of mapping the learning data items in an n-dimensional feature space as corresponding points, where n is an integer equal to or greater than 1; and 
     a learning step of learning a pattern identification parameter that divides the n-dimensional feature space into feature spaces each of which is occupied with the corresponding points labeled as the same class. 
     According to still another aspect of the present invention, a parameter learning method for pattern identification that classifies input data into a first class or a second class, the method comprises: 
     an input step of inputting a plurality of learning data items labeled as the first or second class; 
     a first mapping step of provisionally mapping a plurality of learning data items labeled as the first class in an N r -dimensional feature space as corresponding points, where N r  is an integer equal to or greater than 1; 
     a first learning step of learning a provisional parameter for dividing the N r -dimensional feature space based on a distribution of the corresponding points mapped in the first mapping step in the N r -dimensional feature space; 
     a determination step of determining an n-dimensional feature space to be used for identification based on the provisional parameter; 
     a second mapping step of mapping learning data items labeled as the second class in the n-dimensional feature space as corresponding points; and 
     a second learning step of learning a parameter for dividing the n-dimensional feature space based on a distribution of the corresponding points mapped in the second mapping step. 
     According to still yet another aspect of the present invention, a pattern identification apparatus that classifies input data into a first class or a second class by sequentially executing a combination of a plurality of classification processes, 
     wherein at least one of the plurality of classification processes comprises: 
     a mapping means for mapping the input data in an n-dimensional feature space as corresponding points, where n is an integer equal to or greater than 2; 
     a determination means for determining whether the input data belongs to the first class or the next classification process should be executed based on a distribution of the corresponding points mapped by the mapping means in the n-dimensional feature space; and 
     a selecting means for selecting a classification process to be executed next based on the distribution of the corresponding points when it is determined by the determination means that the next classification process should be executed. 
     According to yet still another aspect of the present invention, a parameter learning apparatus that learns a parameter for pattern identification that classifies input data into a first class or a second class, the apparatus comprises: 
     an input means for inputting a plurality of learning data items labeled as the first or second class; 
     a mapping means for mapping the learning data items in an n-dimensional feature space as corresponding points, where n is an integer equal to or greater than 1; and 
     a learning means for learning a pattern identification parameter that divides the n-dimensional feature space into feature spaces each of which is occupied with corresponding points labeled as the same class. 
     According to still yet another aspect of the present invention, a parameter learning apparatus that learns a parameter for pattern identification that classifies input data into a first class or a second class, the apparatus comprises: 
     an input means for inputting a plurality of learning data items labeled as the first or second class; 
     a first mapping means for provisionally mapping a plurality of learning data items labeled as the first class in an N r -dimensional feature space as corresponding points, where N r  is an integer equal to or greater than 1; 
     a first learning means for learning a provisional parameter for dividing the N r -dimensional feature space based on a distribution of the corresponding points mapped by the first mapping means in the N r -dimensional feature space; 
     a determination means for determining an n-dimensional feature space to be used for identification based on the provisional parameter; 
     a second mapping means for mapping learning data items labeled as the second class in the n-dimensional feature space as corresponding points; and 
     a second learning means for learning a parameter for dividing the n-dimensional feature space based on a distribution of the corresponding points mapped by the second mapping means. 
     Further features of the present invention will become apparent from the following description of exemplary embodiments with reference to the attached drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram used to illustrate an example of the hardware configuration of an information processing apparatus according to Embodiment 1. 
         FIG. 2  is a flowchart illustrating the flow of a face detection process according to Embodiment 1. 
         FIG. 3  is a diagram illustrating the face detection process shown in  FIG. 2  in the form of a data flow diagram. 
         FIG. 4  is a diagram illustrating the structure of a pattern identification parameter according to Embodiment 1. 
         FIG. 5  is a diagram illustrating a data structure of Type-T2 node. 
         FIGS. 6A and 6B  are a flowchart illustrating step S 203  of  FIG. 2  in detail. 
         FIG. 7  is a flowchart illustrating a learning procedure according to Embodiment 1. 
         FIG. 8  is a flowchart illustrating the flow of a texture detection process according to Embodiment 2. 
         FIG. 9  is a diagram illustrating the texture detection process shown in  FIG. 8  in the form of a data flow diagram. 
         FIG. 10  is a diagram illustrating an example in which a result of the texture detection process according to Embodiment 2 is displayed on a display. 
         FIG. 11  is a flowchart illustrating the content of step S 213  of  FIG. 8 . 
         FIG. 12  is a diagram illustrating an example of an image used in learning according to Embodiment 2. 
         FIG. 13  is a flowchart illustrating a learning procedure according to Embodiment 2. 
     
    
    
     DESCRIPTION OF THE EMBODIMENTS 
     Exemplary embodiments of the present invention will now be described in detail in accordance with the accompanying drawings. 
     Embodiment 1 
     Embodiment 1 illustrates an example of an information processing apparatus that determines whether or not an input image includes a face. In order to simplify the description of the present embodiment, it is assumed that, if a face is included in inputted images, the face has a predetermined size and is arranged at a substantially center position, as in passport photographs. It is, of course, possible to detect a face of any size that is located at any position by scanning or enlarging/reducing an image. 
       FIG. 1  is a block diagram used to illustrate an example of the hardware configuration of an information processing apparatus according to Embodiment 1. In  FIG. 1 , reference numeral  100  denotes a CPU (central processing unit), which executes an information processing method described in the present embodiment in accordance with a program. Reference numeral  101  denotes a program memory, which stores programs that are executed by the CPU  100 . Reference numeral  102  denotes a RAM, which provides a memory for temporarily storing various types of information when the CPU  100  executes a program. Reference numeral  103  denotes a hard disk, which is a storage medium for saving image files, pattern identification parameters, and so on. Reference numeral  104  denotes a display, which is an apparatus that provides processing results of the present embodiment to the user. Reference numeral  110  denotes a control bus/data bus, which connects the above-described units to the CPU  100 . 
     The flow of a process for detecting a face that is executed by the information processing apparatus configured as above will be described with reference to the flowchart of  FIG. 2 . First, in step S 201 , the CPU  100  loads image data from the hard disk  103  into the RAM  102 . The image data is stored in the RAM  102  as a two-dimensional array. In the next step, step S 202 , the CPU  100  loads a pattern identification parameter created by a learning method described later from the hard disk  103  into the RAM  102 . In step S 203 , the CPU  100  determines whether or not a face is included in an image represented by the image data that has been loaded in step S 201  using the pattern identification parameter that has been loaded in step S 202 . In the next step, step S 204 , the CPU  100  displays the result of the face detection performed in step S 203  on the display  104 . 
     The processing of  FIG. 2  presented in the form of a data flow diagram is shown in  FIG. 3 . An image  205  corresponds to image data that is saved in the hard disk  103 . Through an image loading process  201 , the image  205  saved in the hard disk  103  is stored as an input image I in the RAM  102  (step S 201 ). In the hard disk  103 , a pattern identification parameter  209  is saved. In a pattern identification parameter loading process  210 , the pattern identification parameter  209  saved in the hard disk  103  is loaded, and stored in the RAM  102  as a pattern identification parameter  211  (step S 202 ). In a detection process  203 , it is determined whether or not a face is included in the input image I using the input image I and the pattern identification parameter  211 , and the determination result is written into the RAM  102  as a detection result  207  (step S 203 ). In a detection result display process  204 , the content of the detection result  207  is displayed on the display  104  (step S 204 ). 
     The content of the pattern identification parameter  211  will now be described with reference to  FIGS. 4 and 5 . A method for creating the pattern identification parameter  211  will be described later. As shown in  FIG. 4 , data indicative of the pattern identification parameter  211  has a structure in which two types of nodes represented by T1 and T2 are connected in a tree structure. Type-T1 node is connected only to a single node. Type-T2 node is connected to a plurality of nodes. A node represented by N 3  belongs to the Type-T2 node. As described above, the pattern identification process according to the present embodiment classifies input data into either a first class (e.g., an image including no face) or a second class (e.g., an image including a face) by sequentially executing a plurality of nodes, that is, a combination of a plurality of classification processes. The present embodiment can be applied regardless of the type of Type T1, and thus a detailed description of Type-T1 node is omitted here. As Type-T1 node, for example, a weak classifier as described in Document 1 may be used in which if inputted data is determined to be classified as the first class, the processing is terminated, and if inputted data is determined to be classified as the second class, the processing advances to the next node. 
       FIG. 5  shows a data structure of Type-T2 node. A plurality of this data is stored in the memory represented by the RAM  102  in  FIG. 1 . Ordinarily, the data of respective nodes have different values. Node type is stored on the top. In this case, the node is of Type T2, a sign that represents T2 is stored as the node type. Rectangle information is stored next. In the head of the rectangle information, the number of rectangles n (where n is an integer equal to or greater than 2) is stored, followed by coordinates (the upper left point, the lower right point) of the n rectangles. Thereby, the position and size of the n rectangles are defined. These plural rectangles are collectively referred to as a “rectangles group”. A parameter for censoring, which will be described later, is stored next. In the head of the censoring parameter, the threshold value θ is stored. Then, censoring coefficients that respectively correspond to the n rectangles follow. Then, the number of branch targets m and branch parameters corresponding to a number equal to m−1 follow. In each branch parameter, similar to the censoring parameter, its threshold value and coefficients that correspond to the number of rectangles are stored, and in addition thereto, a pointer that leads to a branch target node is also stored. In the node pointed by this pointer, the parameter of another node is stored. In the end, another pointer that leads to the mth branch target node (a pointer that leads to the last branch target node) is stored. 
     Before describing a method for creating the parameter (learning method), a method for detecting a face using this parameter is described.  FIGS. 6A and 6B  are a flowchart illustrating step S 203  (a process for detecting a face in an image) of  FIG. 2  in detail. First, in step D 01 , the CPU  100  initializes a pointer variable p such that it indicates the first node. In the next step, step D 02 , the type of the node indicated by p is checked. If the node indicated by p is of Type T1, the processing advances to step D 03 . If the node indicated by p is of Type T2, the processing advances to step D 11 . In step D 03 , processing is performed on Type T1 node, but this processing is well known, and thus its detailed description is omitted here. After the processing of step D 03  is finished, in step D 04 , the CPU  100  checks whether or not all of the nodes have been processed. If all of the nodes have been processed, the processing advances to step D 06 , where the CPU  100  writes a value of TRUE into the detection result  207 . This indicates that a face has been detected. If all of the nodes have not been processed yet, in step D 05 , the CPU  100  changes the pointer variable p such that it indicates the next node. Then, the processing returns to step D 02 . 
     On the other hand, if the node indicated by p is of Type T2, in step D 11 , the CPU  100  initializes a variable c to 0. Then, a loop ranging from step D 12  to step D 15  is repeated n times that correspond to the number of rectangles. A loop variable that represents a rectangle in the loop is set to i. In step D 13 , the CPU  100  obtains coordinates (X 1L , Y 1T ), (X iR , y iB ) of a diagonal line of the rectangle i from the node information of  FIG. 5 . Then, a rectangle image that corresponds to the rectangle i is extracted from the input image I, and the sum (total value) of the luminance value of the rectangle image is determined. The sum of the luminance value of the ith rectangle image is set to b i . b i  can be determined quickly using an integral image as described in Document 1. In step D 14 , the CPU  100  adds, to the variable c, a product obtained by multiplying b i  by a coefficient a i  of the rectangle i. In short, what is determined in the loop ranging from step D 12  to step D 15  is the following inner product. 
     
       
         
           
             
               
                 
                   c 
                   = 
                   
                     
                       ∑ 
                       i 
                       
                           
                       
                     
                     ⁢ 
                     
                       
                         b 
                         i 
                       
                       ⁢ 
                       
                         a 
                         i 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   ] 
                 
               
             
           
         
       
     
     In step D 16 , the CPU  100  determines whether or not the inner product c is above the threshold value θ of the censoring parameter of  FIG. 5 . If the inner product c is above the threshold value θ, the processing advances to step D 17 , where the CPU  100  writes a value of FALSE into the detection result  207 . This indicates that no face has been detected, that is, the input image I has been classified as the second class. Accordingly, the processing of the tree structure shown in  FIG. 4  is terminated here. If it is determined in step D 16  that the inner product c is not above the threshold value θ, the processing advances to step D 18  to select a node to be used next. 
     To put it differently, the above processing includes: where the number of rectangles registered in the parameter is n, 
     mapping the feature amount (the sum of luminance value) of each of n partial data items (rectangles) obtained from input data (an input image I) as corresponding points having coordinates (b 1 , b 2 , . . . b n ) in an n-dimensional feature space, and 
     determining whether the input image I belongs to a first class for non-face images (the process should be discontinued) or the classification process of the next node is executed based on the coordinate location of the mapped corresponding points in the n-dimensional feature space by applying, for example, a discrimination function (calculation of an inner product) to the coordinate value of the corresponding points. 
     If it is determined in step D 16  described above that the next classification process (node) should be executed, a classification process (node) to be executed next is selected based on the location of the corresponding point as will be described below. 
     First, in step D 18 , the CPU  100  checks whether or not all of the nodes have been processed. If all of the nodes have been processed, the processing advances to step D 19 , where the CPU  100  writes a value of TRUE into the detection result  207 . This indicates that a face has been detected, that is, the input image I has been classified as the first class. 
     On the other hand, if it is determined in step D 18  that all of the nodes have not been processed yet, a loop that starts from step D 20  is executed. The loop ranging from step D 20  to step D 27  is repeated m−1 times at the maximum. Here, m is the number of branch targets m of  FIG. 5 . A variable that represents a branch target in the loop ranging from step D 20  to step D 27  is set to k. In step D 21  of the loop, the CPU  100  initializes the variable c to 0. Then, the following inner product is determined in a loop ranging from step D 22  to step D 25 , as the loop of step D 12  to step D 15 . 
     
       
         
           
             
               
                 
                   c 
                   = 
                   
                     
                       ∑ 
                       i 
                       
                           
                       
                     
                     ⁢ 
                     
                       
                         b 
                         i 
                       
                       ⁢ 
                       
                         a 
                         ki 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
     In this formula, as the value of b i , a value determined for b i  of Formula 1 above can be used again. In step D 26 , it is checked whether or not the inner product c is above a threshold value θ k . If the inner product c is not above the threshold value θ k , the loop ranging from step D 20  to step D 27  continues to be executed. If the inner product c is above the threshold value θ k , the processing advances to step D 28 . In step D 28 , the CPU  100  assigns a pointer value that leads to the branch target k to the pointer variable p. Then, processing that starts from step D 02  is started again for the node of the branch target k. If it is determined in step D 26  that the inner product c is not above the threshold value θ k  and the loop that ends in step D 27  is finished, the processing advances to step D 30 . In step D 30 , the CPU  100  assigns a pointer value that leads to the last branch target node of  FIG. 5  to the pointer variable p. Then, the processing that starts from step D 02  is started again. Through the above-described processing, the nodes of the tree structure shown in  FIG. 4  are processed one after another. 
     A learning procedure for creating the pattern identification parameter used in  FIGS. 4 and 5  will be described. First, it is assumed that a set of learning face images f j : F={f j |j=1 . . . N f } and a set of learning non-face images g j : G={g j |j=1 . . . N g } are prepared. It is also assumed that a set of rectangles groups φ s  as indicated by the rectangle information of  FIG. 5 : Φ={φ s |s=1 . . . N φ } is prepared in advance. It is further assumed that the tree structure of  FIG. 4  is determined in advance, and a memory region for storing parameters is already allocated in the RAM  102 . At this time, each pointer value of  FIG. 5  is already determined, and therefore they can be stored. Here, it is assumed that nodes from the node represented by T1 to a node preceding the node represented by N 3  (i.e., the node indicated by T2) of  FIG. 4  have already been learned. To learn Type-T1 node, a technique as described in Document 1 can be used. 
     With the application of the above-described detection process, some of the learning images are rejected (censored) as non-face images through the nodes that precede N 3 , or are sent to another branch target by the Type-T2 node. In the node N 3 , a set of face images f j   +  that were not rejected through the nodes preceding N 3  or were not sent to another branch target: F − ={f j   + |j=1 . . . N f   + } and a set of non-face images g j   + : G + ={g j   + |j=1 . . . N g   − } are used for learning. As used herein, “face image” refers to an image in which there is a human face, and “non-face image” refers to an image in which there is no human face. 
     A flowchart illustrating the learning procedure is shown in  FIG. 7 . The processing of the loop ranging from step C 00  to step C 30  is repeated for each of the rectangles groups φ s (s=1 . . . N φ ) that belong to Φ. The loop ranging from step C 01  to step C 07  is a process for face images f j   +  that belong to F + . The loop ranging from step C 03  to step C 05  is repeated for each rectangle i on a rectangles group φ s . In step C 04 , the CPU  100  assigns the total luminance value of the pixels in a rectangle i of a face image f j   +  to an element b jsi   f  in a three-dimensional array. In the present embodiment, the total luminance value is used as an example of the feature amount of a rectangle, but other feature amount may be used. The loop ranging from step C 10  to step C 16  is a process for non-face images g j   +  that belong to G j   + . Similarly, as in the loop ranging from step C 01  to step  07 , the CPU  100  assigns the total luminance value of the pixels in a rectangle i of a non-face image g j   +  to an element b jsi   g  in the three-dimensional array. Through the above processing, the distribution of the corresponding points (b jsl   f , . . . , b jsn   f ) and (b jsl   g , . . . , b jsn   g ) for the respective face images f i   +  and the respective non-face images g j   +  in an n-dimensional space can be obtained. In other words, for the non-face images g j   +  serving as learning data labeled as the first class and the face images f i   +  serving as learning data labeled as the second class, the corresponding points are mapped in an n-dimensional feature space (n=N o ). 
     In step C 17 , the CPU  100  applies LDA, as a linear discrimination function, to the distribution of these two classes (the result obtained by mapping corresponding points) to obtain a hyperplane for separating the two classes in the n-dimensional space. As used herein, LDA is an abbreviation of linear discriminant analysis. The normal vector of this hyperplane is expressed as (a 1   s , . . . , a n   s ). In step C 18 , the CPU  100  determines a threshold value θ s . The threshold value θ s  can be determined by finding a value at which the total number of failures is the minimum after learning images are classified by finely setting a threshold value and comparing the threshold value to Σa i b i . As used herein, “the total number of failures” is the sum of “the total number of face images that have been classifies as non-face images” and “the total number of non-face images that have been classified as face images”. Alternatively, the threshold value θ s  may be determined such that the total number of non-face images that have been classified as face images is the minimum in a threshold value close to a predetermined ratio at which face images that have been classified as non-face images. 
     In step C 19 , the CPU  100  selects an s at which the total number of failures is the smallest from among the threshold values θ s  determined for respective rectangles groups φ s , and sets it as s′. Alternatively, it is possible to select an s at which the total number of non-face images that have been classified as face images is the smallest. The corresponding point (a 1   s′ , . . . , a n   s′ ) that corresponds to this s′ and its threshold value θ s′  are set as the censoring parameter (a 1 , . . . , a n ) and the threshold value θ of  FIG. 5 , respectively. In this way, a pattern identification parameter that divides a feature space in which the corresponding points labeled as the same class occupy, in an n-dimensional feature space is learned. Here, it is assumed that a space that satisfies the following formula corresponds to F + , and a space that does not satisfy the following formula corresponds to G + . 
     
       
         
           
             
               
                 
                   θ 
                   &lt; 
                   
                     
                       ∑ 
                       i 
                       
                           
                       
                     
                     ⁢ 
                     
                       
                         a 
                         i 
                       
                       ⁢ 
                       
                         b 
                         i 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     3 
                   
                   ] 
                 
               
             
           
         
       
     
     In the formula, b i  is the coordinate value of the ith corresponding point. If the above relationship cannot be obtained, the direction of the normal vector may be reversed. 
     In step C 20 , the CPU  100  divides the distribution of the corresponding points (b jsl   f , . . . , b jsn   f ) of face images obtained through the processing up to this point into m clusters by clustering. In other words, corresponding points labeled as the same class are separated into a plurality of clusters. m is a value that is determined in advance for the node N 3 . A single cluster corresponds to a single branch target. As the clustering method, the k-means or the like can be used. As a result of clustering, all of the face images f i   +  are associated with any one of clusters C 1 , . . . , C m . A loop ranging from step C 21  to step C 24  is repeated for each branch target k. k is incremented by 1 after each loop. In step C 22  of the loop, the corresponding points that correspond to face images that belong to two classes: C k  and C k|1 U . . . UC m  are separated with a hyperplane according to LDA. Then, the normal vector of the hyperplane thus obtained is stored as (a k1 , . . . , a kn ) in the corresponding region of  FIG. 5 . Subsequently, in step C 23 , for example, a threshold value θ k  at which the total number of failures is the minimum is determined. Here, it is assumed that a space that satisfies the following formula corresponds to C k , and a space that does not satisfy the following formula corresponds to C k+1 U . . . UC m . In this way, in steps C 21  to C 24 , a pattern identification parameter that further separates the corresponding points of learning data labeled as the same class into a plurality of clusters is learned (separation parameter learning), and is used as a parameter for a branch target in  FIG. 5 . 
     
       
         
           
             
               
                 
                   
                     θ 
                     k 
                   
                   &lt; 
                   
                     
                       ∑ 
                       i 
                       
                           
                       
                     
                     ⁢ 
                     
                       
                         a 
                         ki 
                       
                       ⁢ 
                       
                         b 
                         i 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     4 
                   
                   ] 
                 
               
             
           
         
       
     
     Otherwise, the direction of the normal vector may be reversed. 
     As described above, according to Embodiment 1, a face included in an input image can be detected through a process of a relatively small calculation load. In the present embodiment, a face is used as a specific example, but the present embodiment can be utilized to detect other objects such as a head or an automobile. In a detector as described in Document 1 in which weak classifiers are cascade-connected, it is known to be important to censor more non-face images at an early stage. In light of this, in the present embodiment, even when a branch structure is adopted, a rectangles group that is intended to be censored is selected, and this is used for branching. Thereby, high-speed and highly accurate pattern identification is achieved. 
     Embodiment 2 
     Embodiment 2 illustrates an example of an information processing apparatus that detects an object having a specific texture from an inputted image. Unlike Embodiment 1, in Embodiment 2, an object to be detected may not be located in a predetermined location of an input image. Furthermore, in Embodiment 1, a set of rectangles groups needs to be determined in advance, whereas in Embodiment 2, rectangles groups that are used by respective nodes for identification processing are automatically generated by preparing only rectangles that serve as candidates for elements, and setting the number of rectangles included in a single rectangles group. For the sake of simplicity, Embodiment 2 describes a binary tree, but it is easily conceivable from Embodiment 1 that the present embodiment can be applied to a multiway tree. 
     The information processing apparatus according to Embodiment 2 has the same hardware configuration as that of Embodiment 1 ( FIG. 1 ). Accordingly, reference should be made to Embodiment 1 for a description of each unit. 
     A flowchart illustrating the flow of a process for detecting a texture is shown in  FIG. 8 . First, in step S 211 , the CPU  100  loads an image from the hard disk  103  into the RAM  102 . The image is stored in the RAM  102  as a two-dimensional array. In step S 212 , the CPU  100  loads a pattern identification parameter created by a learning method described later from the hard disk  103  into the RAM  102 . In step S 213 , the CPU  100  searches an image that has been loaded in step S 211  for a region in which a predetermined texture is present using the pattern identification parameter that has been loaded in the previous step. In step S 214 , the CPU  100  displays the result of the search on the display  104 . 
     The processing of  FIG. 8  presented in the form of a data flow diagram is shown in  FIG. 9 . Reference numeral  225  denotes an image that is saved in the hard disk  103  of  FIG. 1 . In an image loading process  221 , the image  225  saved in the hard disk is stored as an input image I in the RAM  102  (step S 211 ). Reference numeral  229  denotes a pattern identification parameter that is saved in the hard disk  103 . In pattern identification parameter loading process  230 , the pattern identification parameter  229  saved in the hard disk is stored in the RAM  102  as a pattern identification parameter  231  (step S 212 ). In a search process  223 , with the use of the input image I and the pattern identification parameter  231 , a search is performed in the input image I for a predetermined texture, and a location in which the predetermined texture is found is written into the RAM  102  as a search result  227  (step S 213 ). In the present embodiment, a region in which a predetermined texture is not included is classified as a first class, and a region in which a predetermined texture is included is classified as a second class. The search result  227  is a two-dimensional array of black and white values. In a search result display process  224 , the content of the search result  227  is displayed on the display  104  (step S 214 ). 
       FIG. 10  shows an example of information displayed on the display  104 . This is merely a schematic diagram for illustrating the operation of Embodiment 2, and the present embodiment does not necessarily provide the result shown in  FIG. 10 . In a region  1001  on the left, the content of the input image I is displayed. In a region  1002  on the right, the content of the search result  227  is displayed. In the search result shown in the region  1002 , a region in which the grid patterns of the input image are present is shown in black. 
       FIG. 11  is a flowchart illustrating the content of step S 213  (a process for searching a pattern in an image) of  FIG. 8 . In a loop ranging from step L 01  to step L 07 , the processing shown in steps L 02  to L 06  is repeated for each point (x, y) on the input image I. In step L 02 , the CPU  100  cuts out a region near the point (x, y), which serves as a target pixel on the input image I, as an image R for detection. The size of the image R is the same as that of a learning image described later. Step L 03  is a detection process. This detection process is the same as that shown in  FIGS. 6A and 6B  of Embodiment 1, except that the detection process is performed for the cut-out image R, instead of the input image I. Subsequently, in step L 04 , the CPU  100  determines whether the detection result obtained in step L 03  is TRUE or FALSE (i.e., whether it is classified into the second class or the first class). If the result is determined to be TRUE, the processing advances to step L 05 , where the CPU  100  writes BLACK into the (x, y) component (a target pixel) of the search result  227 . Conversely, if the result is determined to be FALSE in step L 04 , the processing advances to step L 06 , where the CPU  100  writes WHITE into the (x, y) component (a target pixel) of the search result  227 . In this way, images into which WHITE or BLACK is written are obtained as the search result  227 . 
     A learning procedure according to Embodiment 2 will be described next. The content of the pattern identification parameter  231  according to Embodiment 2 has the same structure as those shown in  FIGS. 4 and 5  of Embodiment 1. Examples of images that are used for learning are shown in  FIG. 12 . All of the images used for learning have the same size. These images represent patterns that need to be detected. In contrast, as a pattern that needs not to be detected, an image obtained by cutting out from the background of the input image shown in the region  1001  of  FIG. 10  is used. 
     A learning image that includes a pattern that needs to be detected is denoted as p j , and a set thereof is expressed as P={p j |j=1, . . . , N p }. Likewise, a learning image that does not include a pattern that needs to be detected is denoted as q j , and a set thereof is expressed as Q={q j |j=1, . . . , N q }. Furthermore, a rectangles that is represented by rectangle coordinates (x iL , y iT ), (x iB , y iB ) in  FIG. 5  is denoted as r i , and a set thereof is expressed as R={r i |i=1, . . . , N r }. It is assumed that the tree structure of  FIG. 4  is determined in advance, and a memory for storing parameters is already allocated in the RAM  102 . At this time, each pointer value of  FIG. 5  is already determined, and therefore they can be stored. Here, it is also assumed that nodes from the node represented by T1 to a node preceding the node represented by N 3  in  FIG. 4  have already been learned. 
     With the application of the above-described detection process, some of the learning images are rejected (censored) as not including a pattern that needs to be detected through the nodes that precede N 3 , or are sent to another branch target by Type-T2 node. Accordingly, in Node N 3 , a set of pattern images p i   +  that were not rejected or were not sent to another branch target through the preceding nodes: P + ={P j   + |j=1 . . . N p   + } and a set of non-pattern images q j   + : Q + ={q j   + |j=1 . . . N q   + } are used for learning. 
       FIG. 13  shows a flowchart of learning according to Embodiment 2. The learning according to Embodiment 2 includes: 
     a first mapping process and a first learning process in which learning data is provisionally mapped using provisional rectangles groups to learn a parameter, and a rectangles group to be used is extracted; and 
     a second mapping process and a second learning process in which learning data is mapped using the extracted rectangles group to learn a parameter. 
     Through the processing ranging from step T 01  to step T 08 , a rectangles group that is presumed to be effective for determining a branch target is selected by the first mapping process and first learning process. Through the processing ranging from step T 10  to step T 18 , a censoring parameter is determined by the second mapping process and second learning process. Through the last processing ranging from step T 21  to step T 24 , a parameter for each branch target is determined. These steps will be described below one by one. 
     First, a loop ranging from step T 01  to T 07  is repeated for each pattern image p i   +  of the set P + . A loop ranging from step T 03  to T 05  in the above loop is repeated for each rectangle r i  of the set R. In step T 04  of the loop, the average luminance value of the rectangle r i  of the pattern image P i   +  is stored in an element b ji   p  of a two-dimensional array. It should be noted here that, unlike Embodiment 1, the present embodiment employs a value (average luminance) obtained by normalizing the luminance value with the number of pixels. Thereby, a difference between pixel units can be absorbed. The mapping performed in the above processing is provisional mapping for selecting a rectangles group that is actually used. In other words, the processing from step T 01  to T 07  includes: 
     determining the feature amount (average luminance) by extracting N r  rectangle images (where N r  is an integer equal to or greater than 1) from image data that belongs to P +  (learning data labeled as the first class); and 
     provisionally mapping corresponding points in an N r -dimensional feature space (first mapping). 
     Subsequently, in step T 20 , the CPU  100  clusters the distribution of N r -dimensional vectors (b j′   p , . . . , b jNr   P ) determined in the previous loop into a plurality of clusters. In other words, based on the distribution of the provisionally mapped corresponding points in the N r -dimensional feature space, a provisional pattern identification parameter that divides the N r -dimensional feature space is learned (first learning). Because a binary tree is generated in this example, the distribution is clustered into two (m=2). As the clustering method, the k-means can be used. Although it seems natural to use the Euclidean distance to determine the distance between vectors, it is also possible to use, for example, the Minkowski metric. Then, all of the pattern images in the set P +  can be assigned to a cluster (C 1  or C 2 ), and thus a hyperplane that separates two clusters can be obtained with an SVM (support vector machine) or the like. The N r -dimensional normal vector of that hyperplane is expressed as (a 1   p , . . . , a Nr   p ). It is assumed here that a natural number d and a real number u (u≧0) are constants that are determined in advance for the node N 3 . 
     In step T 08 , the CPU  100  selects an absolute value in descending order of magnitude from among the elements of the normal vector obtained above, and stops selecting when the sum of the selected elements is equal to u or less and −u or more, or when the number of the selected elements reaches d. Then, a rectangle {r i } that corresponds to the selected element {a i   p } is selected. If n rectangles are selected in this manner, these can be expressed as a rectangle group: φ={r i   φ |=1, . . . , n}. As described above, in steps T 20  and T 08 , an n-dimensional feature space that is used by nodes for identification processing is determined using a provisional parameter obtained based on provisional mapping. 
     Subsequently, a loop ranging from step T 10  to T 16  is repeated for each non-pattern image q j   +  of the set Q + . A loop ranging from step T 12  to T 14  in the above loop is repeated for each rectangle r i   φ  of the previously selected rectangles group φ. In step T 13 , the total luminance value of the rectangle r i   φ  on the non-pattern image q j   +  is assigned to the element b ji   q  of the two dimensional array. In other words, the processing ranging from step T 10  to step T 16  is a process for mapping image data that belongs to Q +  (learning data labeled as the second class) as corresponding points in the n-dimensional feature space. 
     Then, in step T 17 , a hyperplane that separates the distribution of (b j1   p , . . . , b jn   p ) from the distribution of (b j1   q , . . . , b jn   q ) is calculated. The normal vector of the hyperplane thus obtained is stored as (a 1 , . . . , a n ) in the corresponding region (censoring parameter) of  FIG. 5 . In other words, a pattern identification parameter that divides the n-dimensional feature space is learned based on the distribution of the mapped corresponding points in the n-dimensional feature space, and is stored as a censoring parameter (second learning). In step T 18 , as in the case of Embodiment 1, a threshold value θ for censoring parameter is determined. As described above, according to steps T 10  to T 18 , non-pattern images q j   +  as learning data labeled as the second class are mapped as corresponding points on the n-dimensional feature space. In this way, a pattern identification parameter that divides the n-dimensional feature space is learned based on the distribution of the mapped corresponding points. 
     The processing ranging from step T 21  to step T 24  is the same as that ranging from step C 21  to C 24  of  FIG. 7  in the Embodiment 1, except that SVM is used instead of LDA for acquiring a hyperplane that separates clusters. The number of clusters in clustering is 2 (m=2). 
     As described above, according to the present embodiment, a predetermined pattern included in an input image can be searched through a process of a relatively small calculation load. Even if patterns appear the same to the human, when they have different inclinations, there is a large difference when the pixels are compared. According to the present embodiment, it is possible to absorb this difference by using unsupervised learning in which rectangles groups are not determined in advance and a branch-type detector. 
     Embodiments of the present invention have been described in detail above, but the present invention can take the form of a system, apparatus, method, program, storage medium and so on. Specifically, the present invention may be applied to a system configured of a plurality of devices or to an apparatus configured of a single device. 
     The present invention encompasses the case where the functions of the above-described embodiments are achieved by directly or remotely supplying a software program to a system or apparatus and loading and executing the supplied program code through a computer in the system or apparatus. In this case, the supplied program is a computer program that corresponds to the flowchart indicated in the drawings in the embodiments. 
     Accordingly, the program code itself, installed in a computer so as to realize the functional processing of the present invention through the computer, also realizes the present invention. In other words, the computer program itself that realizes the functional processing of the present invention also falls within the scope of the present invention. 
     In this case, a program executed through object code, an interpreter, script data supplied to an OS, or the like may be used, as long as it has the functions of the program. 
     Examples of the a computer readable storage medium that can be used to supply the computer program include floppy® disks, hard disks, optical disks, magneto-optical disks, MOs, CD-ROMs, CD-Rs, CD-RWs, magnetic tape, non-volatile memory cards, ROMs, and DVDs (DVD-ROMs, DVD-Rs). 
     Alternatively, using a browser of a client computer to connect to an Internet website and downloading the computer program of the present invention from the website to a recording medium such as a hard disk can be given as another method for supplying the program. In this case, the downloaded program may be a compressed file that contains an automatic installation function. Furthermore, it is also possible to divide the program code that constitutes the program of the present invention into a plurality of files and download each file from different websites. In other words, a WWW server that allows a plurality of users to download the program files for realizing the functional processing of the present invention through a computer also falls within the scope of the present invention. 
     Furthermore, the program of the present invention may be encrypted, stored in a storage medium such as a CD-ROM, and distributed to users. In this case, a user that has satisfied predetermined conditions is allowed to download key information for decryption from a website through the Internet, execute the encrypted program using the key information, and install the program on a computer. 
     Also, the functions of the present embodiments may be realized, in addition to through the execution of a loaded program using a computer, through cooperation with an OS or the like running on the computer based on instructions of the program. In this case, the OS or the like performs part or all of the actual processing, and the functions of the above-described embodiments are realized by that processing. 
     Furthermore, a program loaded from the storage medium is written into a memory provided in a function expansion board installed in a computer or in a function expansion unit connected to the computer, whereby part or all of the functions of the above-described embodiments may be realized. In this case, after the program has been written into the function expansion board or the function expansion unit, a CPU or the like included in the function expansion board or the function expansion unit performs part or all of the actual processing based on the instructions of the program. 
     According to the present invention, it is possible to realize pattern identification process for identifying input data that belongs to either of two classes with high speed and high accuracy. 
     While the present invention has been described with reference to exemplary embodiments, it is to be understood that the invention is not limited to the disclosed exemplary embodiments. The scope of the following claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions. This application claims the benefit of Japanese Patent Application No. 2007-252375, filed on Sep. 27, 2007, which is hereby incorporated by reference herein in its entirety.