Abstract:
The present invention discloses an object-detection method and a multi-class Bhattacharyya Boost algorithm used therein, wherein firstly, integral images are calculated from an image data in order to speed up the extraction of the characteristics of the objects; then, multiple rectangles of different sizes are scanned at different locations of the image data, and the multi-class Bhattacharyya Boost algorithm is used to detect multi-class objects. In the present invention, the detection framework can use only one single boosted cascade to determine the status and position of the object inside the image data. The simultaneous multi-class detection of the present invention can effectively overcome the detection difficulties resulting from the diversification of object appearances under different conditions. Therefore, the present invention can detect multiple objects simultaneously and can also detect one object having multiple classes of appearances, and further, the detection speed and the system robustness of the present invention are superior to those of the conventional technologies.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to a detection method and an algorithm, particularly to an object-detection method, which can process objects having multiple classes of appearances, and a Multi-class Bhattacharyya Boost (MBH-Boost) algorithm used therein. 
   2. Description of the Related Art 
   To integrate the digital image processing technology with automatic monitoring/control, building security, or man-machine interaction is an active field the academic circle and the industry endeavor to study and develop. Various achievements thereof will enable automatic processes to replace some human works. Among this field, object detection is a critical preprocessing because it is only after the system has known the positions of target objects that the succeeding processes, such as identifying human faces or other objects in a security system, or monitoring/tracing human beings or vehicles in a monitoring/control system, can be executed. Therefore, object-detection technology has universal utility. And, some objective and measurable factors, such as detection speed, detection accuracy and detection robustness, can be used to evaluate the performance of a detection algorithm. 
   Recently, the learning mechanism of a boosting algorithm has been often used in object detection, and it can also be integrated with a cascade framework to increase detection speed. The efficiency and accuracy of the object-detection technology based on the boosted cascade has acquired general attention in academic circles, and further researches are also being undertaken, for example, determining the interference factors in detecting human faces, such as illumination, occlusion and rotation angles, and promoting detection accuracy under the influence of a variety of extrinsic factors. 
   In resolving those discussed above, the present invention proposes an object-detection method and a multi-class Bhattacharyya Boost algorithm used therein to overcome the problems. 
   SUMMARY OF THE INVENTION 
   The primary objective of the present invention is to provide a method to detect objects with multiple classes of appearances, wherein the multi-class object can be detected via only using a single boosted cascade, and the execution efficiency and the detection accuracy thereof is promoted thereby. 
   Another objective of the present invention is to propose a novel Multi-class Bhattacharyya Boost (MBH-Boost) algorithm to overcome the difficulties resulting from the diversified classes of the object appearances shown in different conditions and to enhance the robustness of the system. 
   According to the present invention, the objection-detection method is based on a multi-class cascade framework. Initially, an object-detection system is provided with an image data; multiple rectangles on the image data are separately scanned by the multi-class object-detection method, and the integral image thereof is used to calculate the projection of the image data; the calculation results will be used to perform multi-class classifications on those rectangles. 
   According to the object-detection method of the present invention, the Multi-class Bhattacharyya Boost (MBH-Boost) algorithm is used in the object-detection system. Firstly, training data D Γ  of a set Γ of multiple classes, a set φ of the projection directions of weak learners, and an iteration number T are provided; a weighted value w t   x (i) with respect to each item in D Γ  is worked out via iterative calculations; an optimal projection direction φ t  is worked out via the weighted value w t   x (i); w t   x (i) is updated to be w t+1   x (i) according to the classification result of the optimal projection direction φ t ; and after T iterations, a vector-valued classifier F, which is used as a decision boundary, can be worked out. The class-wise calculation results for the set Γ={A, B, C, . . . } correspondingly give the component-wise values of the classifier F, i.e., H A , H B , H C , . . . , whose maximal positive value will be used as the classification standard. 
   To enable the objectives, technical contents, characteristics and accomplishments of the present invention to be more easily understood, the embodiments of the present invention are described below in cooperation with the attached drawings. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a schematic diagram of the multi-class training data according to the present invention. 
       FIG. 2  is a schematic diagram showing that the action of the projection directions on the classes A, C, and E according to the present invention. 
       FIG. 3  is a flow chart of the object-detection process according to the present invention. 
       FIG. 4  is a schematic diagram showing the different-size rectangles according to the present invention. 
       FIG. 5  is a schematic diagram for rectangles of different kinds at specified positions of an image according to the present invention. 
       FIG. 6  is a schematic diagram showing the object detection according to the present invention. 
       FIG. 7  is a schematic diagram showing the calculation of characteristics inside the image according to the present invention. 
       FIG. 8  is a schematic diagram showing the detection of characteristic images and the designation of the characteristics according to the present invention. 
       FIG. 9  is another schematic diagram showing the detection of characteristic images and the designation of the characteristics according to the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The primary objective of the present invention is to provide a method to detect objects with multiple classes of appearances, and the method of the present invention is based on two core elements: (1) a classification algorithm—a Multi-class Bhattacharyya Boost (MBH-Boost) algorithm, (2) a detection framework—a multi-class cascade, which are to be described below. 
   The novel Multi-class Bhattacharyya Boost (MBH-Boost) algorithm primarily functions to simultaneously process the detection of multiple kinds of objects with multiple classes of appearances, and classifier sharing is the primary principle thereof. All classes of objects have a common projection direction; however, an independent decision boundary of each class will be separately learned according to the training data of each kind. Via sharing a common projection, the calculation amount is obviously reduced, and the execution speed increases. In the other side, the independent decision boundary of each kind speeds up the convergence of classification error rate. Therefore, even though only few weak learners are used, classification accuracy rate still maintains high. In theory, the present invention provides a mechanism of selecting an optimal projection direction, and it is proved that the error upper bound is directly lowered thereby; in experiment, the present invention is verified in the detection of four kinds of human faces, and the results thereof show the Multi-class Bhattacharyya Boost (MBH-Boost) algorithm of the present invention is superior to the conventional methods. 
   In general, the target object is a very scarce incident in comparison with the others in the image, and such a characteristic is often used to speed up the detection process. Among the approaches thereby, the cascade detection framework proposed in 2001 is a well-known one; however, it can only be used to detect a single-class object. The present invention proposes a multi-class cascade framework to solve the problem. In each node of the cascade structure, the embedded classifiers are sequentially learned from the training data varying from simplicity to complexity. In contrast with the other methods for detecting the multi-class object, the algorithm of the present invention needs only a single boosted cascade framework; therefore, the algorithm of the present invention is superior to the conventional ones in detection speed, accuracy, and robustness. 
   Besides, the detection method of the present invention neither applies any further limitation to the desired object nor applies any special presumption between different classes of the object; therefore, the present invention has superior generality and flexibility in application; for example, the present invention is adaptable to (1) identify various kinds of objects, such as human beings, vehicles, or human faces, (2) identify multiple classes of variant appearances of a single object, such as the frontal face, the profile face and the rotated face of a human being, or human faces under different lighting conditions, (3) identify the combination case of two abovementioned ones. Thus, the present invention can be widely applied to the automatic processing system based on digital image processing technology. 
   The MBH-Boost of the present invention is an algorithm based on machine learning, and the system must be constructed through a well-designed training stage before it can be used to reliably perform the testing stage for its practical application. These two stages are to be described below. 
   Training Stage 
   The method of the present invention will be exemplified by the detection of profile faces. As shown in  FIG. 1 , Γ={A, B, . . . , I} designates the set of the denotations of nine profile faces having different rotation angles, and |Γ|=9. 
   Training Data: 
   Training data D Γ  is a set of object images and non-object images and has the correct labels thereof. There are nine classes in the exemplifying profile face detection, and nine types of training data are expressed as: 
                         D             ⁢   A       =       {       (       x             ⁢   1               ⁢   A       ,     y             ⁢   1               ⁢   A         )     ,   …   ⁢           ,     (       x                ⁢     D             ⁢   A            A     ,     y                ⁢     D             ⁢   A            A       )       }     =       D             ⁢     A   ⁢           +     ⁢               ⋃     D             ⁢     A   ⁢           -     ⁢                                 D             ⁢   B       =       {       (       x             ⁢   1               ⁢   B       ,     y             ⁢   1               ⁢   B         )     ,   …   ⁢           ,     (       x                ⁢     D             ⁢   B            B     ,     y                ⁢     D             ⁢   B            B       )       }     =       D             ⁢     B   ⁢           +     ⁢               ⋃     D             ⁢     B   ⁢           -     ⁢                             ⋮               D             ⁢   I       =       {       (       x             ⁢   1               ⁢   I       ,     y             ⁢   1               ⁢   I         )     ,   …   ⁢           ,     (       x                ⁢     D             ⁢   I            I     ,     y                ⁢     D             ⁢   I            I       )       }     =       D             ⁢     I   ⁢           +     ⁢               ⋃     D             ⁢     I   ⁢           -     ⁢                                 D   Γ     =       D   A     ⋃     D   B     ⋃           ⁢     …   ⁢           ⁢     D   I                       (   1   )               
MBH Weak Learner:
 
   Each MBH weak learner has a projection direction, and in the present invention, the MBH weak learners share a common projection direction for all the classes of the desired object. According to the positive and negative training data of each class, two distributions are formed in a one-dimensional subspace after projection. According to the distributions, each class learns and obtains its own decision boundary independently. Let f be a weak leaner, which comprises a projection direction φ, and x be a pattern input to f. The decision process can be expressed as: 
                         f   ⁡     (   x   )       =       [         h   A     ⁡     (   x   )       ,   …   ⁢           ,       h   I     ⁡     (   x   )         ]     ⁢           ⁢     (     profile   ⁢           ⁢   face   ⁢           ⁢   detection     )                   =     [           h   χ     ⁡     (   x   )       ⁢          χ   ∈   Γ     ]       ,           ⁢     (     general   ⁢           ⁢   case     )                       (   2   )               
wherein
 
   
     
       
         
           
             
               
                 
                   
                     
                       h 
                       χ 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ln 
                         ⁢ 
                         
                           
                             
                               
                                 p 
                                 k 
                                 
                                   χ 
                                   + 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 ϕ 
                                 ) 
                               
                             
                             / 
                             
                               
                                 p 
                                 k 
                                 
                                   χ 
                                   - 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 ϕ 
                                 ) 
                               
                             
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ϕ 
                           T 
                         
                         ⁢ 
                         x 
                       
                       ∈ 
                       
                         
                           b 
                           k 
                         
                         . 
                         
                           
 
                         
                         ⁢ 
                         
                           
                             p 
                             k 
                             
                               χ 
                               + 
                             
                           
                           ⁡ 
                           
                             ( 
                             ϕ 
                             ) 
                           
                         
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             
                               i 
                               k 
                               
                                 χ 
                                 + 
                               
                             
                             ⁡ 
                             
                               ( 
                               ϕ 
                               ) 
                             
                           
                           
                               
                           
                         
                         ⁢ 
                         
                           
                             
                               w 
                               χ 
                             
                             ⁡ 
                             
                               ( 
                               i 
                               ) 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           and 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               p 
                               k 
                               
                                 χ 
                                 - 
                               
                             
                             ⁡ 
                             
                               ( 
                               ϕ 
                               ) 
                             
                           
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             
                               i 
                               k 
                               
                                 χ 
                                 - 
                               
                             
                             ⁡ 
                             
                               ( 
                               ϕ 
                               ) 
                             
                           
                           
                               
                           
                         
                         ⁢ 
                         
                           
                             w 
                             χ 
                           
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       i 
                       k 
                       χ 
                     
                     ⁡ 
                     
                       ( 
                       ϕ 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       i 
                       ⁢ 
                       
                          
                         
                           
                             
                               x 
                               i 
                             
                             ∈ 
                             
                               D 
                               χ 
                             
                           
                           , 
                           
                             
                               
                                 ϕ 
                                 T 
                               
                               ⁢ 
                               
                                 x 
                                 i 
                               
                             
                             ∈ 
                             
                               b 
                               k 
                             
                           
                         
                         } 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 3 
                 ) 
               
             
           
         
       
     
   
   Refer to  FIG. 2  showing the action of two projection directions and corresponding weak learners on the classes of A, C, and E in the 10-bin subspace. 
   Multi-Class Bhattacharyya Boost (MBH-Boost) Algorithm: 
   To utilize the MBH-Boost algorithm, the following parameters and data are needed: (1) the training data D Γ  of detection classes Γ={A, B, C, . . . I}, (2) the set Φ of projection directions of the weak learner, (3) the number of iteration T. In the “t”th iteration of MBH-Boost algorithm, the weighted value w t   x (i) of each component in the training data D Γ  is updated, and an optimal projection direction φ t  will be derived from the weighted value w t   x (i); f t  the vector-valued weak learner can also be worked out from the optimal projection direction φ t  in the “t”th iteration. The execution process can be expressed by the following algorithm. 
   
     
       
             
           
         
             
                 
             
             
               Algorithm:MBHBoost 
             
             
                 
             
           
           
             
               
                 
                   
                     
                       
                         Input 
                         : 
                         
                           Face 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           classes 
                         
                       
                       , 
                       
                         Γ 
                         ; 
                         
                           
                             D 
                             Γ 
                           
                           = 
                           
                             
                               ⋃ 
                               
                                 ?? 
                                 ∈ 
                                 Γ 
                               
                             
                             ⁢ 
                             
                               D 
                               ?? 
                             
                           
                         
                         ; 
                         
                           Projection 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           set 
                         
                       
                       , 
                       
                         Φ 
                         ; 
                         
                           Number 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           of 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           iterations 
                         
                       
                       , 
                       
                         
                           T 
                           . 
                           
                             
 
                           
                           ⁢ 
                           
                             Output 
                             : 
                             
                               A 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               vector 
                               ⁢ 
                               
                                 - 
                               
                               ⁢ 
                               valued 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               MBH 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               classifier 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 F 
                                 . 
                                 
                                   
 
                                 
                                 ⁢ 
                                 
                                   Initialize 
                                   : 
                                   
                                     the 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     weight 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     vector 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       
                                         w 
                                         1 
                                         ?? 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         i 
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                           
                         
                         = 
                         
                           1 
                           / 
                           
                              
                             
                               D 
                               ?? 
                             
                              
                           
                         
                       
                       , 
                       
                         
                           for 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           i 
                         
                         = 
                         1 
                       
                       , 
                       2 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         
                            
                           
                             D 
                             ?? 
                           
                            
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         and 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ∀ 
                           
                             ?? 
                             ∈ 
                             
                               
                                 
                                   Γ 
                                   . 
                                   
                                     
 
                                   
                                   ⁢ 
                                   for 
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 t 
                               
                               ← 
                               1 
                             
                           
                         
                       
                       , 
                       2 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         T 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         do 
                       
                     
                   
                 
                 
                   
                     
                       
                           
                       
                       ⁢ 
                       
                         ⌊ 
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   
                                                     
                                                       
                                                         
                                                           
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                               
                                                             ⁢ 
                                                             
                                                             1. 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             Determine 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             the 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             optimal 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             projection 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             
                                                             ϕ 
                                                             t 
                                                             
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             from 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             Φ 
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                               
                                                             ⁢ 
                                                             
                                                             by 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             solving 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             
                                                             
                                                             ( 
                                                             4 
                                                             ) 
                                                             
                                                             . 
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                               
                                                             ⁢ 
                                                             
                                                             2. 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             Construct 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             the 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             MBH 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             weak 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             learner 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             
                                                             f 
                                                             t 
                                                             
                                                             
                                                             
                                                             
                                                             
                                                           
                                                         
                                                       
                                                       
                                                         
                                                           
                                                               
                                                             ⁢ 
                                                             
                                                             associated 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             with 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             
                                                             ϕ 
                                                             t 
                                                             
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             using 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             
                                                             
                                                             ( 
                                                             2 
                                                             ) 
                                                             
                                                             . 
                                                             
                                                             
                                                           
                                                         
                                                       
                                                     
                                                   
                                                 
                                                 
                                                   
                                                     
                                                         
                                                       ⁢ 
                                                       
                                                         
                                                           
                                                             3. 
                                                             ⁢ 
                                                             
                                                               
                                                             
                                                             ⁢ 
                                                             
                                                             
                                                             w 
                                                             
                                                             t 
                                                             + 
                                                             1 
                                                             
                                                             ?? 
                                                             
                                                             ⁡ 
                                                             
                                                             ( 
                                                             i 
                                                             ) 
                                                             
                                                             
                                                           
                                                           ← 
                                                           
                                                             
                                                             
                                                             w 
                                                             t 
                                                             ?? 
                                                             
                                                             ⁡ 
                                                             
                                                             ( 
                                                             i 
                                                             ) 
                                                             
                                                             
                                                             ⁢ 
                                                             
                                                             
                                                             exp 
                                                             ⁡ 
                                                             
                                                             ( 
                                                             
                                                             
                                                             - 
                                                             
                                                             y 
                                                             i 
                                                             ?? 
                                                             
                                                             
                                                             ⁢ 
                                                             
                                                             
                                                             h 
                                                             t 
                                                             ?? 
                                                             
                                                             ⁡ 
                                                             
                                                             ( 
                                                             
                                                             x 
                                                             i 
                                                             ?? 
                                                             
                                                             ) 
                                                             
                                                             
                                                             
                                                             ) 
                                                             
                                                             
                                                             / 
                                                             
                                                             Z 
                                                             t 
                                                             ?? 
                                                             
                                                             
                                                           
                                                         
                                                         , 
                                                       
                                                     
                                                   
                                                 
                                               
                                             
                                           
                                           
                                             
                                               
                                                   
                                                 ⁢ 
                                                 
                                                   
                                                     
                                                       for 
                                                       ⁢ 
                                                       
                                                           
                                                       
                                                       ⁢ 
                                                       i 
                                                     
                                                     = 
                                                     1 
                                                   
                                                   , 
                                                   2 
                                                   , 
                                                   … 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   , 
                                                   
                                                     
                                                        
                                                       
                                                         D 
                                                         ?? 
                                                       
                                                        
                                                     
                                                     ⁢ 
                                                     
                                                         
                                                     
                                                     ⁢ 
                                                     and 
                                                     ⁢ 
                                                     
                                                         
                                                     
                                                     ⁢ 
                                                     
                                                       ∀ 
                                                       
                                                         ?? 
                                                         ∈ 
                                                         
                                                           Γ 
                                                           . 
                                                         
                                                       
                                                     
                                                   
                                                 
                                               
                                             
                                           
                                         
                                       
                                     
                                     
                                       
                                         
                                             
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 Z 
                                                 t 
                                                 ?? 
                                               
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               is 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               a 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               normalization 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               factor 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               such 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               that 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               
                                                 w 
                                                 
                                                   t 
                                                   + 
                                                   1 
                                                 
                                                 ?? 
                                               
                                             
                                           
                                         
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                       
                                     ⁢ 
                                     
                                       is 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       a 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         distribution 
                                         . 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                             ⁢ 
                             Output 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             an 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             MBH 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             classifier 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               F 
                               : 
                               
                                 F 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                           
                           = 
                           
                             
                               
                                 ∑ 
                                 
                                   t 
                                   = 
                                   1 
                                 
                                 T 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   f 
                                   t 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                             = 
                             
                               
 
                             
                             ⁢ 
                             
                               
                                 [ 
                                 
                                   
                                     
                                       H 
                                       ?? 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       x 
                                       ) 
                                     
                                   
                                   = 
                                   
                                     
                                       
                                         ∑ 
                                         
                                           t 
                                           = 
                                           1 
                                         
                                         T 
                                       
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         
                                           h 
                                           t 
                                           ?? 
                                         
                                         ⁡ 
                                         
                                           ( 
                                           x 
                                           ) 
                                         
                                       
                                     
                                     ❘ 
                                     
                                       ?? 
                                       ∈ 
                                       Γ 
                                     
                                   
                                 
                                 ] 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
             
             
                 
             
           
        
       
     
   
   The vector-valued output of the classifier F includes the calculation results H A , H B , H C  . . . respectively corresponding to each class in each set Γ, which can be used as the decision boundaries of the corresponding classes. In each of the iterations, the projection direction is selected according to: 
                       ϕ   t     =         arg   ⁢           ⁢   min       ϕ   ∈           ⁢   Φ       ⁢       ∑     χ   ∈   Γ       ⁢       Δ   t   χ     ×       BHC   t   χ     ⁡     (   ϕ   )               ,     
     ⁢   where     ⁢     
     ⁢         BHC   t   χ     ⁡     (   ϕ   )       =       ∑     k   =   1     m     ⁢             p   k     χ   +       ⁡     (   ϕ   )       ⁢       p   k     χ   -       ⁡     (   ϕ   )           .                 (   4   )               
In theory, it is based on the following formulae:
 
   
     
       
         
           
             
               
                 
                   
                     BHC 
                     t 
                     χ 
                   
                   ⁡ 
                   
                     ( 
                     ϕ 
                     ) 
                   
                 
                 = 
                 
                   
                     Z 
                     t 
                     χ 
                   
                   / 
                   2. 
                 
               
             
             
               
                 ( 
                 5 
                 ) 
               
             
           
           
             
               
                 
                   
                     
                       
                         Δ 
                         t 
                         χ 
                       
                       = 
                       
                         
                            
                           
                             D 
                             χ 
                           
                            
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                                
                               
                                 D 
                                 χ 
                               
                                
                             
                           
                           ⁢ 
                           
                             
                               
                                 w 
                                 1 
                                 χ 
                               
                               ⁡ 
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                             ⁢ 
                             
                               exp 
                               ( 
                               
                                 
                                   - 
                                   
                                     y 
                                     i 
                                     χ 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       τ 
                                       = 
                                       1 
                                     
                                     
                                       t 
                                       - 
                                       1 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       h 
                                       τ 
                                       χ 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       
                                         x 
                                         i 
                                         χ 
                                       
                                       ) 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       = 
                       
                         
                           
                              
                             
                               D 
                               χ 
                             
                              
                           
                           ⁢ 
                           
                             Z 
                             1 
                             χ 
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               
                                  
                                 
                                   D 
                                   χ 
                                 
                                  
                               
                             
                             ⁢ 
                             
                               
                                 
                                   w 
                                   2 
                                   χ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   i 
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 exp 
                                 ( 
                                 
                                   
                                     - 
                                     
                                       y 
                                       i 
                                       χ 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       ∑ 
                                       
                                         τ 
                                         = 
                                         2 
                                       
                                       
                                         t 
                                         - 
                                         1 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         h 
                                         τ 
                                         χ 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           x 
                                           i 
                                           χ 
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         = 
                         … 
                       
                     
                   
                 
                 
                   
                     
                       = 
                       
                         
                            
                           
                             D 
                             χ 
                           
                            
                         
                         ⁢ 
                         
                           Z 
                           1 
                           χ 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         … 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           Z 
                           
                             t 
                             - 
                             1 
                           
                           χ 
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                                
                               
                                 D 
                                 χ 
                               
                                
                             
                           
                           ⁢ 
                           
                             
                               w 
                               t 
                               χ 
                             
                             ⁡ 
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       = 
                       
                         
                            
                           
                             D 
                             χ 
                           
                            
                         
                         ⁢ 
                         
                           
                             ∏ 
                             
                               τ 
                               = 
                               1 
                             
                             
                               t 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               Z 
                               τ 
                               χ 
                             
                             . 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 6 
                 ) 
               
             
           
         
       
     
   
   The optimal solution of the upper bound of the error rate under the projection direction selected by formula (4) can be derived from formulae (5) and (6), as shown below: 
                     ∑     χ   ∈   Γ       ⁢       Δ   t   χ     ×       BHC   t   χ     ⁡     (   ϕ   )           =         1   2     ⁢       ∑     χ   ∈   Γ       ⁢            D   χ          ⁢       ∏     τ   =   1     t     ⁢           ⁢     Z   τ   χ             ∝       ∑     χ   ∈   Γ       ⁢            D   χ          ⁢       ∏     τ   =   1     t     ⁢           ⁢       Z   τ   χ     .                     (   7   )               
Multi-Class Cascade:
 
   As mentioned above, the multi-class cascade can be used to improve detection accuracy, execution speed, and robustness. In utilizing the MBH-Boost algorithm to construct the nodes of the cascade framework, firstly, the training targets (target detection rate μ and false-positive rate ν) of each node are to be preset, and target detection rate μ is usually preset to range from 99.5%˜99.9%, and false-positive rate ν is usually preset to range from 40%˜50%. Let F k  be the classifier embedded into the k th node, and the training data in the k th node would be the data passing through the anterior k−1 nodes. Additionally, a voluminous database Q, which collects various images except the object images (human faces in this embodiment), will be constructed to create a negative training data. 
   The constructing process of the multi-class cascade framework can be expressed by the following algorithm. 
                           Algorithm:Multi-Class Cascade:Training                             Input   :   Φ     ;     D   Γ     ;     A   ⁢           ⁢   set   ⁢           ⁢   of   ⁢           ⁢   images   ⁢           ⁢   containing   ⁢           ⁢   no   ⁢           ⁢   faces   ⁢           ⁢   Q     ;                 Target   ⁢           ⁢   detection   ⁢           ⁢   rate   ⁢           ⁢   μ     ;     False   ⁢     -     ⁢   positive   ⁢           ⁢   rate   ⁢           ⁢     ν   .     
     ⁢     Output   :     A   ⁢           ⁢   cascade   ⁢           ⁢   of   ⁢           ⁢   MBH   ⁢           ⁢   classifiers   ⁢           ⁢     {       F   1     ,   …   ⁢           ,     F   ɛ       }             ;                 Number   ⁢           ⁢   of   ⁢           ⁢   stage   ⁢           ⁢   used   ⁢           ⁢     s   ??       ,       ∀     ??   ∈     Γ   .     
     ⁢     Initialize   :     k   ←   1             ;       Γ   k     ←   Γ     ;                   while   ⁢           ⁢     Γ   k       ≠     0   /   do                         ⁢     ⌊             With   ⁢           ⁢     D   Γk     ⁢           ⁢   and   ⁢           ⁢   Φ     ,     apply   ⁢           ⁢   MBH   ⁢     -     ⁢   Boost   ⁢           ⁢   to   ⁢           ⁢   derive                   F   k     =       [       H   k   ??     ❘     ??   ∈     Γ   k         ]     ⁢           ⁢   where   ⁢           ⁢   each   ⁢           ⁢   component   ⁢           ⁢     H   k   ??                     should   ⁢           ⁢   achieve   ⁢           ⁢   the   ⁢           ⁢   preset   ⁢           ⁢     (     μ   ,   ν     )     ⁢           ⁢   requirements     ;                 foreach   ⁢           ⁢   ??     ∈       Γ   k     ⁢           ⁢   do                 ⌊               D     ??   +       ←     {       (     x   ,   y     )     ❘       (     x   ,   y     )     ∈         D     ??   +       ⋀       H   k   ??     ⁡     (   x   )         ≥     θ   k   ??           }       ;                 D     ??   -       ←     False   ⁢     -     ⁢   Positives   ⁢           ⁢   from   ⁢           ⁢     D     ??   -       ⁢           ⁢   or   ⁢           ⁢   from                     Q   ⁢           ⁢   such   ⁢           ⁢   that   ⁢           ⁢          D     ??   -              =          D     ??   +              ;               if   ⁢           ⁢   not   ⁢           ⁢   enough   ⁢           ⁢   False   ⁢     -     ⁢   Positives   ⁢           ⁢   then               ⌊         s   ??     ←   k     ;         Γ   k     ←       Γ   k     -     {   ??   }         :     s   ←   k       ;                             Γ     k   +   1       ←     Γ   k       ;     k   ←     k   +   1       ;                                      
Testing Stage
 
   As shown in  FIG. 3 , during testing stage, the first step S 1  is to provide an image data for the detection system; referring to  FIG. 4 , the second step S 2  is that the detection system scans multiple rectangles  10  in the image data, and the rectangles  10  are of different sizes, such as 24×24, 30×30, 38×38 . . . ; in the third step S 3 , the integral images are used to perform the rapid calculation of the projection in the image data defined by each weak learner, and referring to  FIG. 5 , the projection calculation is to calculate the difference between the sums of the gray-level values in balck region(s) of each rectangle  10  and the sum of gray-level values in the remaining white region(s), and the calculation results will be input to the weak learner; in the fourth step S 4 , according to the classification results output by multiple previously trained weak learners, the MBH-Boost algorithm is used to perform multi-class classification on the rectangle  10 , and a detection framework cascaded by vector-valued classifiers is used to perform the detection in order to determine whether the object is the desired one. Thus, the detection process is completed. 
   When a test pattern “x” (a rectangle) is input into a multi-class cascade framework having completed the learning, it will be processed as follows: 
   
     
       
             
           
         
             
                 
             
             
               Algorithm:Multi-Class Cascade:Testing 
             
             
                 
             
           
           
             
               
                 
                   
                     
                       
                         Input 
                         : 
                         
                           A 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           test 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           pattern 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           x 
                         
                       
                       ; 
                       
                         Face 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         classes 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         Γ 
                       
                       ; 
                       
                         A 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         cascade 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         of 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           detectors 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             { 
                             
                               
                                 F 
                                 1 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 F 
                                 s 
                               
                             
                             } 
                           
                         
                         ; 
                         
                           Number 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           of 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           stages 
                         
                       
                       , 
                       
                         s 
                         ?? 
                       
                       , 
                       
                         ∀ 
                         
                           ?? 
                           ∈ 
                           
                             Γ 
                             . 
                             
                               
 
                             
                             ⁢ 
                             
                               Output 
                               : 
                               
                                 A 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 vector 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 of 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 boolean 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   output 
                                   ⁢ 
                                   s 
                                 
                               
                             
                           
                         
                       
                       , 
                       
                         
                           
                             output 
                             ⁡ 
                             
                               ( 
                               Γ 
                               ) 
                             
                           
                           . 
                           
                             
 
                           
                           ⁢ 
                           
                             Initialize 
                             : 
                             
                               k 
                               ← 
                               1 
                             
                           
                         
                         ; 
                         
                           Λ 
                           ← 
                           Γ 
                         
                         ; 
                       
                     
                   
                 
                 
                   
                     
                       
                         while 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         Λ 
                       
                       ≠ 
                       
                         0 
                         / 
                         do 
                       
                     
                   
                 
                 
                   
                     
                       
                           
                       
                       ⁢ 
                       
                         ⌊ 
                         
                           
                             
                               
                                 
                                   Jointly 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   evaluate 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     
                                       H 
                                       k 
                                       ?? 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       x 
                                       ) 
                                     
                                   
                                 
                                 , 
                                 
                                   
                                     ∀ 
                                     
                                       ?? 
                                       ∈ 
                                       Λ 
                                     
                                   
                                   ; 
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   foreach 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   ?? 
                                 
                                 ∈ 
                                 
                                   Λ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   do 
                                 
                               
                             
                           
                           
                             
                               
                                 ⌊ 
                                 
                                   
                                     
                                       
                                         
                                           if 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             
                                               H 
                                               k 
                                               ?? 
                                             
                                             ⁡ 
                                             
                                               ( 
                                               x 
                                               ) 
                                             
                                           
                                         
                                         &lt; 
                                         
                                           
                                             θ 
                                             k 
                                             ?? 
                                           
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           then 
                                         
                                       
                                     
                                   
                                   
                                     
                                       
                                         ⌊ 
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           
                                             
                                               output 
                                               ⁡ 
                                               
                                                 ( 
                                                 ?? 
                                                 ) 
                                               
                                             
                                             ← 
                                             False 
                                           
                                           ; 
                                           
                                             Λ 
                                             ← 
                                             
                                               Λ 
                                               - 
                                               
                                                 { 
                                                 ?? 
                                                 } 
                                               
                                             
                                           
                                           ; 
                                         
                                       
                                     
                                   
                                   
                                     
                                       
                                         
                                           else 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           if 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           k 
                                         
                                         = 
                                         
                                           
                                             s 
                                             ?? 
                                           
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           then 
                                         
                                       
                                     
                                   
                                   
                                     
                                       
                                         ⌊ 
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           
                                             
                                               output 
                                               ⁡ 
                                               
                                                 ( 
                                                 ?? 
                                                 ) 
                                               
                                             
                                             ← 
                                             True 
                                           
                                           ; 
                                           
                                             Λ 
                                             ← 
                                             
                                               Λ 
                                               - 
                                               
                                                 { 
                                                 ?? 
                                                 } 
                                               
                                             
                                           
                                           ; 
                                         
                                       
                                     
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   k 
                                   ← 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                 ; 
                               
                             
                           
                         
                       
                     
                   
                 
               
             
             
                 
             
           
        
       
     
   
   The algorithm of the present invention provides each class of the object with a Boolean output, which denotes whether the test pattern (rectangle) is the object of one specified class. 
   When the detection of a human face  14  is used for exemplification, the detection process is as follows: firstly, referring to  FIG. 6 , the image data  16  is provided; referring to  FIG. 7 , different sizes of rectangles of the image data  16  are scanned, and the integral images are used to calculate the projections; the MBH-Boost algorithm is used to perform multi-class classification of the human face  14 ; the single cascade of vector-value classifiers is used to speed up the detection in order to determine the viewing angles and the lighting conditions of the human face  14 , as shown in  FIG. 8  and  FIG. 9 . 
   The object-detection method of the present invention can designate the desired object and the class thereof. When it is exemplified by the human face detection under different lighting conditions or with different rotation angles, the execution results are shown in  FIG. 9 , wherein the light incident angles and the rotation angles of the human face are all appropriately designated. From the above examples, it can be concluded: the object-detection method of the present invention can overcome the detection difficulties resulting from the diversified classes of the appearances under different conditions, and the robustness of the system can also be obviously improved. As shown in the embodiment of human face detection, in comparison with other detection algorithms, the algorithm of the present invention has the characteristics of instant detection, higher detection accuracy, capability of dealing with multi-class appearances resulting from the rotation angle of the object, viewing angle of the camera, lighting conditions, and occlusion. 
   Those embodiments described above are not to limit the scope of the present invention but only to clarify the present invention to enable the person skilled in the art to understand, make, and use the present invention. Any equivalent modification and variation according to the spirit of the present invention disclosed herein is to be included within the scope of the present invention.