Abstract:
One embodiment of the present invention provides a system for detecting an occurrence of an object in an image. During operation, the system selects a subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow. The system then performs an evaluation step on the subwindow to determine if the object exists in the subwindow, wherein performing the evaluation step involves updating the currently estimated likelihood of the object being detected in the subwindow. If evaluation of the subwindow is not complete after performing the evaluation step, the system stores information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

Description:
FIELD OF THE INVENTION 
     The present invention relates to techniques for detecting objects within images. More specifically, the present invention relates to a method and an apparatus for detecting an object within an image using parallel incremental evaluations of sub-windows of the image. 
     BACKGROUND 
     As computer systems are becoming more powerful, they are being used for increasingly computationally intensive tasks involving large images. One such task is “object detection.” The goal of object detection is to determine the presence and location of objects of a given type (such as faces) within one or more digital images. Typically, object detection begins by training a classifier (an object detector) to recognize the presence of the object of interest within a 2D window of a suitable aspect ratio. Then the trained detector is applied to a comprehensive set of subwindows to identify those subwindows that produce a detector response above a given acceptance threshold. 
     For example, the detector may be trained to determine whether a given 20×20 window of grayscale pixels represents a low resolution frontal view of a human face. To determine whether a digital image contains a face, the detector can be applied to every 20×20 scan window in an image, so that it can take into account a comprehensive set of positions, scales and orientations. Specifically, we can first check all 20×20 windows centered at each pixel, then we may scale down the image to, say, 90% of its original size and again check every 20×20 window. Note that by applying the detector to scaled down versions of the image we can look for larger (or smaller) examples of the object. Furthermore, we can also resample each scaled image at various angles and scan the result to search for the presence and location of the object at various angular orientations. 
     Traditional methods for object detection analyze the scan windows sequentially, which means that they fully analyze each window before proceeding to the next window. This typically involves scanning subwindows in each row, left-to right, and each column, top-to-bottom. Furthermore, it can involve performing object detection for each scale, small-to-large, and each orientation. Consequently, object detection is very computationally intensive because it involves analyzing subwindows of any discrete position, scale and orientation. For example, a 1024×768 image analyzed at six scales and six orientations has well over 10 million subwindows. 
     Furthermore, traditional object detection systems are not suitable for a variety of contexts in which object detection is needed. For example, certain applications of face detection do not require finding all the faces in the image. For example, for a “show images containing faces” search feature it is sufficient to find a single face in an image to determine whether to show the image. Moreover, some applications can only devote fixed amount of time per image, such as video surveillance systems that provide real-time image analysis. These applications try to do the best they can while keeping up with the frame rate. Other applications can take more time, but need the best intermediate results, such as a computer-assisted person tagging system, in which the user can start correcting the tag assignments before the system has analyzed all images in full. Hence, in some cases comprehensive detection may take more time than the system can allow, and in other cases it is better for the system to spend more time in the hope of finding more instances of the object. 
     Unfortunately, the speed/detection rate tradeoff is hard-coded in traditional systems and cannot be changed dynamically. While it is possible to interrupt a traditional detection process and ask for all found instances of the object, the number of instances (or detection probability) is linear on the time spent. In other words, all things being equal, interrupting a traditional system after half of the time needed to fully analyze an image will on average detect 50% of the object occurrences. 
     Hence, what is needed is a method and an apparatus for detecting an object within an image without the above-described problems. 
     SUMMARY 
     One embodiment of the present invention provides a system for detecting an occurrence of an object in an image. During operation, the system selects a subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow. The system then performs an evaluation step on the subwindow to determine if the object exists in the subwindow, wherein performing the evaluation step involves updating the currently estimated likelihood of the object being detected in the subwindow. If evaluation of the subwindow is not complete after performing the evaluation step, the system stores information associated with the subwindow to facilitate subsequent evaluation of the subwindow. 
     In a variation on this embodiment, storing the information associated with the subwindow involves updating and storing the currently estimated likelihood of the object being detected within the subwindow. 
     In a further variation, storing the information associated with subwindows also involves: storing the subwindow itself, or storing location information for the subwindow; and storing intermediate results, if any, associated with evaluation of the subwindow. 
     In a variation on this embodiment, selecting the subwindow to be evaluated involves: selecting a new subwindow; or selecting a partially evaluated subwindow. 
     In a variation on this embodiment, if the currently estimated likelihood of the object being detected in the subwindow drops below a minimum value, the system discards the subwindow. 
     In a variation on this embodiment, if currently estimated likelihood of the object being detected in the subwindow exceeds a predetermined value, the system fully evaluates the subwindow. 
     In a variation on this embodiment, storing the information associated with the subwindow involves storing the information ordered by estimated likelihood to facilitate selecting the subwindow later based on the currently estimated likelihood of the object being detected within the subwindow. 
     In a variation on this embodiment, performing the evaluation step on the subwindow involves using an incrementally evaluatable detector, which is based on a neural network. 
     In a variation on this embodiment, the system is configured to: perform a first evaluation step on a first subwindow to determine if the object exists in the first subwindow; perform a first evaluation step on a second subwindow to determine if the object exists in the second subwindow; and to subsequently perform a second evaluation step on the first subwindow. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         FIG. 1  illustrates an image processing system in accordance with an embodiment of the present invention. 
         FIG. 2  illustrates information that is stored for a partially evaluated subwindow in accordance with an embodiment of the present invention. 
         FIG. 3  presents a flow chart illustrating the object detection process in accordance with an embodiment of the present invention. 
         FIG. 4  illustrates an example of a neural network in accordance with an embodiment of the present invention. 
         FIG. 5A  illustrates an initial state in the process of incrementally evaluating a neural network in accordance with an embodiment of the present invention. 
         FIG. 5B  illustrates the system after one step in the process of incrementally evaluating a neural network in accordance with an embodiment of the present invention. 
         FIG. 5C  illustrates the system after two steps in the process of incrementally evaluating a neural network in accordance with an embodiment of the present invention. 
         FIG. 5D  illustrates the system after all steps in the process of incrementally evaluating a neural network in accordance with an embodiment of the present invention. 
         FIG. 6  illustrates equivalent input deltas to two hidden unit in a neural network can produce different output deltas in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
     The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices, such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as a LAN, a WAN, or the Internet. 
     Image Processing System 
       FIG. 1  illustrates an image processing system  100  in accordance with an embodiment of the present invention. This image processing system  100  includes a scan manager  104 , which receives an image  102  as input. Scan manager  104  locates a subwindow  103  of the image  102 , and then transforms the subwindow  103  by rotating it or scaling it to produce a scan window  106  that feeds into a classifier  108 . For example, image  102  can be a 1024 by 786 pixel grey-scale image, and scan window  106  can be a 20 by 20 pixel grey-scale subwindow of image  102 . 
     Note that the terms “subwindow” and “scan window” are used interchangeably throughout this specification. Also note that the term “subwindow” as used in this specification and appended claims is not meant to be limited to a rectangular subwindow. In general, the term subwindow can refer to any sub-region of the window of any shape. 
     Classifier  108  can include any type of classifier that can determine whether or not the scan window  106  contains a desired object. Moreover, classifier  108  supports incremental evaluation operations for scan window  106 . More specifically, classifier divides the evaluation of scan window  106  into a number of evaluation steps (step 1 , step 2  and step 3 ). Each of these evaluation steps can be performed separately, and produces information which can be stored in lookup structure  114 . 
     Lookup structure  114  can generally be any type of data structure, which can store information associated with partially evaluated scan windows. Referring to  FIG. 2 , this information can include an estimated likelihood  202  that the object of interest is contained within the scan window. It can also include the scan window itself (or location information for the scan window)  204 , as well as intermediate results for the scan window during the evaluation process  206 . 
     In one embodiment of the present invention, lookup structure  114  is a heap, which maintains a partial ordering of the scan windows based upon their estimated likelihoods of containing the object. This facilitates retrieving the scan window with the highest estimated likelihood of containing the object. 
     Note that classifier  108  can either process new scan windows received from scan manager  104 , or alternatively, can process partially evaluated scan windows retrieved from lookup structure  114 . This process is described in more detail below with reference to the flow chart illustrated in  FIG. 3 . 
     Detectors that Support Incremental Evaluation 
     The present invention uses a class of detectors that can be incrementally evaluated. In these detectors, a given subwindow can be evaluated in a fixed number of evaluation steps. After each evaluation step, the detector determines its best guess of the likelihood of the object being present in the given subwindow. 
     Using such detectors has the following advantages. (1) We can discontinue the evaluation of the detector after a certain number of steps if the likelihood of the presence of the object remains low, thereby saving unnecessary computation and speeding up detection. (2) We can incrementally evaluate multiple detectors simultaneously and focus the analysis on the most promising detectors. This allows us to discover many of the objects of interest shortly after the beginning of the analysis. 
     DEFINITIONS 
     Let W and H be positive integers defining a 2D window of fixed size. Let U be the space of all subwindows with aspect ratio W/H in all images. The dimensions of U are implementation-dependent and may include the image, the x and y coordinates within the image, the scale, and the orientation. This general definition of U simplifies the notation and allows us to refer to any subwindows (training examples, test examples, places where we search for the object, etc.) simply as points in U. In this specification, we will consider only a space with finite and discrete dimensions. 
     The training space TεU contains a set of points that represent centers of the objects used for training the detector. The search space XεU is the space of all subwindows in all images which we are searching for occurrences of the object of interest. XP is the set of all points representing such occurrences (i.e. centers of objects). 
     CεU is the calibration space. It contains a set of N points CP={cp 1  . . . cp N }εC which represent N examples of the object of interest. We will need those objects to calibrate the detector, as described later in the paper. 
     X, T and C are disjoint subspaces of U. T and C are representative of X. 
     The object detector D W,H : U→[0;1] determines the likelihood of the object of interest being present at a given point in U. The point in U is mapped onto a 2D normalized grid of W by H pixels (translating, scaling, rotating, normalizing the lighting appropriately). This 2D grid is analyzed by the detector to determine the likelihood. 
     A detector is incrementally evaluatable if the evaluation computations can be broken down into S steps. After each step iε[1;S], the detector returns D i (x), its best guess to the presence of the object at the evaluation point x. Thus D S (x)=D(x). There are three desirable conditions of incrementally evaluatable detectors: that the sequence D 1 (x) . . . D S (x) is somewhat monotonic; that the time to evaluate all steps does not exceed too much the time to fully evaluate the detector; and that there is a large number of steps S. The benefits of the method described in this specification directly relate to how well the detector satisfies these conditions. 
     μ i ε[0,1], and σ i ε[−1;1] are our estimates of the mean and the standard deviation of the detector&#39;s response at step i when applied at the center of an object. They are computed during the calibration of the detector (as described below). NR i (x)εR is the normalized response of the detector at step i applied at point x. It indicates how promising point x is for further evaluation. 
     t R εR is the rejection threshold. If the normalized response of the detector falls below t R  the evaluation of the detector is suspended, since it is unlikely that there is an object at that point. 
     t A εR is the acceptance threshold. If the normalized response of the detector exceeds t A  the detector is fully evaluated, since it is likely that there is an object at that point. 
     Parallel Incremental Detector Evaluation 
     The trained detector needs to be calibrated before being applied on the test image(s). Calibration is done once only and can be thought as part of the training process. During calibration we estimate the mean and standard deviation of the detector&#39;s response at each step i when applied at the center of a positive example. We use the calibration examples CP to estimate these values: 
     
       
         
           
             
               
                 
                   
                     μ 
                     i 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       1 
                       N 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           
                             [ 
                             
                               1 
                               , 
                               N 
                             
                             ] 
                           
                         
                         
                             
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           D 
                           i 
                         
                         ⁡ 
                         
                           ( 
                           
                             cp 
                             j 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     σ 
                     i 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       
                         
                           1 
                           N 
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               j 
                               ∈ 
                               
                                 [ 
                                 
                                   1 
                                   , 
                                   N 
                                 
                                 ] 
                               
                             
                             
                                 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               ( 
                               
                                 
                                   
                                     D 
                                     i 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       cp 
                                       j 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   μ 
                                   i 
                                 
                               
                               ) 
                             
                             2 
                           
                         
                       
                       - 
                       
                         μ 
                         i 
                       
                     
                   
                 
               
             
           
         
       
     
     We will use μ i  and σ i  during the search to compute the normalized response of the detector applied at step i on a location x: 
     
       
         
           
             
               
                 NR 
                 i 
               
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               
                 
                   
                     D 
                     i 
                   
                   ⁡ 
                   
                     ( 
                     x 
                     ) 
                   
                 
                 - 
                 
                   μ 
                   i 
                 
               
               
                 σ 
                 i 
               
             
           
         
       
     
     The normalized response is a measurement of how well the partially evaluated window is doing with respect to an average positive (object) example. The vast majority of windows we evaluate don&#39;t have the object, so their normalized responses would do very poorly. If the normalized response is too low, we can discontinue evaluating the window. Alternately, if the normalized response is promisingly high, we can perform a full evaluation at that window. 
     The search technique is illustrated in  FIG. 3 . During the scanning process we maintain a heap of the partially evaluated detectors ordered by their normalized response. Initially, the heap is empty (step  301 ), so we perform a first step evaluation of the first scan window of the image and insert the partially evaluated detector into the heap (step  303 ). In step  304 , we must decide whether to work on evaluating the most promising detector we have in the heap (step  305 ) or whether to go to step  303  to start a new detector. This decision can be based on the number of unexplored windows left and the expected frequency of objects. The more unexplored windows there are, the more likely we will want to start a new detector on one of them. Alternatively, the more promising the best found detector is, the more likely we would work on it instead. Clearly, if no windows are left, step  304  must choose the “yes” branch. In step  305 , we remove the most promising detector from the heap and perform an evaluation step on it. If its new normalized response is higher than the acceptance threshold (step  306 ), we fully evaluate it (step  307 ) to see if it is indeed an instance of the object, in which case we add it to the list of found objects. In case the response is not high enough, we check whether it is lower than our rejection threshold or we have fully evaluated the detector (step  308 ) in which case we discard the current detector (by never putting it back in the heap). Only if the revised normalized response is between the rejection and acceptance thresholds do we insert the detector back in the heap (step  309 ). 
     There are various methods to choose appropriate values of t A  and t R . We set t R =−3, i.e. an incremental evaluation is discontinued if its response is three standard deviations less than the normalized response of the average positive example. We use a different value of t A  for each evaluation step i. During calibration, we perform incremental evaluation of a large number of non-object windows and we set t A,i  as the normalized response of the highest 1% of normalized responses of non-object examples. In other words, we fully evaluate a test window if it performs better than the top 1% of the non-object examples. For the heuristic at step  304 , we choose to evaluate the top detector x in the heap if NR i (x)&gt;t A,i *k where k=19. This value was picked empirically. A more sophisticated rule, taking into account the size of the heap and the number of unexplored windows left, could result in better performance. 
     A heap performs insertion and deletion in O(log N). An alternative method with constant time insert and delete is to subdivide the space of normalized response into bins and consider any detector from the highest occupied bin as the “top”. This may not guarantee we always work on the best example, but may work well in practice. 
     Creating an Incrementally Evaluatable Detector from a Neural Network 
     The method described in this paper requires that the detector be incrementally evaluatable. Neural networks are often used as the basis for object detectors. In this section we describe a method for incrementally evaluating a neural network. 
     We will discuss a two layer feed-forward neural network with a single output neuron; however, the method naturally extends to other types of neural networks. 
     The neural net consists of a layer of input units, a layer of hidden units and an output unit ( FIG. 4 ). Each hidden unit has a weight for each input unit w h,i  and a threshold weight w h,0 . The output unit has a weight for each hidden unit w h  and a threshold weight w 0 . The response D(x) of the neural network when presented with an input vector x is: 
     
       
         
           
             D 
             = 
             
               σ 
               ( 
               
                 
                   w 
                   0 
                 
                 + 
                 
                   
                     ∑ 
                     h 
                     
                         
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       w 
                       h 
                     
                     ⁢ 
                     
                       σ 
                       ( 
                       
                         
                           w 
                           
                             h 
                             , 
                             0 
                           
                         
                         + 
                         
                           
                             ∑ 
                             i 
                             
                                 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               w 
                               
                                 h 
                                 , 
                                 i 
                               
                             
                             ⁢ 
                             
                               x 
                               i 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               ) 
             
           
         
       
     
     Where σ(y) is the sigmoid threshold function, for example 
               σ   ⁡     (   y   )       =       1     1   +     e     -   y           .           
For simplicity, we are omitting the current image x as the input parameter of D.
 
     We can break down the neural network response function as follows: 
     
       
         
           
             
               
                 
                   
                     R 
                     ⁡ 
                     
                       ( 
                       h 
                       ) 
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       w 
                       
                         h 
                         , 
                         0 
                       
                     
                     + 
                     
                       
                         ∑ 
                         i 
                         
                             
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           w 
                           
                             h 
                             , 
                             i 
                           
                         
                         ⁢ 
                         
                           x 
                           i 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   R 
                   = 
                     
                   ⁢ 
                   
                     
                       w 
                       0 
                     
                     + 
                     
                       
                         ∑ 
                         i 
                         
                             
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           w 
                           h 
                         
                         ⁢ 
                         
                           σ 
                           ⁡ 
                           
                             ( 
                             
                               R 
                               ⁡ 
                               
                                 ( 
                                 h 
                                 ) 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   D 
                   = 
                     
                   ⁢ 
                   
                     σ 
                     ⁡ 
                     
                       ( 
                       R 
                       ) 
                     
                   
                 
               
             
           
         
       
     
     R(h) represents the raw (pre-sigmoid) value of hidden unit h and R is the raw value of the output unit. 
     The initial response (at step  0 ) is computed as follows: 
                       R   0     ⁡     (   h   )       =       ⁢       w     h   ,   0       +       ∑   i             ⁢           ⁢       w     h   ,   i       ⁢     μ   i                       R   =       ⁢       w   0     +       ∑   h             ⁢           ⁢       w   h     ⁢     σ   ⁡     (       R   0     ⁡     (   h   )       )                           D   0     =       ⁢     σ   ⁡     (     R   0     )                   
where μ i  is the mean (expected) value of the i-th input. This mean depends on the raw input as well as on the preprocessing operations. It can be estimated by applying the detector at random places in the calibration space and taking the mean value of the input vector. Intuitively, D 0 (x) represents our best guess of the detector&#39;s response without considering any of the inputs of x. Note that the initial guess of the neural net does not depend on the input vector x and therefore, for efficiency, can be computed during the calibration phase.
 
     The full evaluation consists of I*H number of steps (I is the size of the input vector and H is the number of hidden units). At each step k we evaluate the response as follows: and 
     1. Pick a unique pair &lt;h k ,i k &gt; of a hidden unit h=h k  and an input unit i=i k ; and 
     2. Evaluate the response as follows: 
                       R   k     ⁡     (   h   )       =       ⁢     {                 R     k   -   1       ⁡     (   h   )       +         w     h   ,     i   k         ⁡     (       x     i   k       -     μ     i   k         )       ⁢           ⁢   if   ⁢           ⁢   h       =     h   k                     R     k   -   1       ⁡     (   h   )       ⁢           ⁢   otherwise                           R   k     =       ⁢       R     k   -   1       +       w     h   k       ⁡     (       σ   ⁡     (       R   k     ⁡     (     h   k     )       )       -     σ   ⁡     (       R     k   -   1       ⁡     (     h   k     )       )         )                       D   k     =       ⁢       σ   ⁡     (     R   k     )       .                 
After the last step, the network response equals that of full evaluation:
 D I*H =D 
(We can prove that by summing R k (h) for all steps. The intermediate terms cancel out and we are left with the formula for R(h). The same proof applies to the R k  and therefore to D k .)
 
     We have described the general mechanism for incremental evaluation of a neural network. Now we need to pick the optimal way to select the h k  and i k  to use at each step, so that the network response at each step converges to the final network response as quickly as possible. 
     Clearly the optimal &lt;h k ,i k &gt; pair is the one with the highest partial derivative. However, maintaining the partial derivatives at each step requires more computations than evaluating the neural network in full. We have to settle for a sub-optimal method that requires preferably constant-time computations at each evaluation step. The parallel evaluation method of this specification imposes an even stricter requirement: the ordering must not depend on the input vector at all (otherwise, we cannot estimate NR, i.e. how well one neural network is doing with respect to another). Thus, the ordering must be precomputed during the calibration step. 
     Intuitively, we want to start with the &lt;h k ,i k &gt; pairs that result in the largest change to the network response. Once we get the largest changes out of the way, the neural net response should be close to the final one. 
     Let the notation  h,i R k  mean “the raw value of the output unit at step k, should we choose hidden unit h and input unit i.” Similarly, let  i R k (h) mean “the raw value of hidden unit h at step k, should we choose input i.” We omit h and i when specifying R k-1 , the raw value at the previous step, because they have been chosen already. 
     Let  h i k  be the optimal input unit at step k, should we choose hidden unit h. We want to pick the input i that maximizes the change in the raw response of the h-th hidden unit: 
     
       
         
           
             
               
                   
               
               h 
             
             ⁢ 
             
               i 
               
                 
                     
                 
                 k 
               
             
             = 
             
               
                 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     max 
                   
                   i 
                 
                 ( 
                 
                   
                      
                     i 
                   
                   ⁢ 
                   
                     
                       
                         R 
                         k 
                       
                       ⁡ 
                       
                         ( 
                         h 
                         ) 
                       
                     
                     - 
                     
                       
                         R 
                         
                           k 
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         h 
                         ) 
                       
                     
                   
                    
                 
                 ) 
               
               = 
               
                 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     max 
                   
                   i 
                 
                 ( 
                 
                    
                   
                     
                       w 
                       
                         h 
                         , 
                         i 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           x 
                           i 
                         
                         - 
                         
                           μ 
                           i 
                         
                       
                       ) 
                     
                   
                    
                 
                 ) 
               
             
           
         
       
     
     Unfortunately we cannot use the specific value of x i  during calibration. Instead we use Monte-Carlo sampling to estimate the mean deviation from the calibration set that includes object and non-object windows: 
               α   i     =         1   N     ⁢       ∑     p   =   1     N     ⁢           ⁢          p     ⁢       x   i     -     μ   i                ≈            x   i     -     μ   i                    
where  p x i  denotes the value of x i  for the p-th random sample. Thus we have:
 
     
       
         
           
             
               
                   
               
               h 
             
             ⁢ 
             
               i 
               
                 
                     
                 
                 k 
               
             
             = 
             
               
                 
                   arg 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   max 
                 
                 i 
               
               ⁢ 
               
                 ( 
                 
                    
                   
                     
                       w 
                       
                         h 
                         , 
                         i 
                       
                     
                     ⁢ 
                     
                       α 
                       i 
                     
                   
                    
                 
                 ) 
               
             
           
         
       
     
     Note that we are selecting the maximum i only over those inputs that have not been chosen previously with the same hidden unit, i.e.: ∀b&lt;k,  h i k ≠ h i b    
     The task of picking the optimal hidden unit is more difficult. Again, we want to pick the hidden unit h that maximizes the change in the raw value of the output unit: 
     
       
         
           
             
               
                 
                   
                     h 
                     k 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       
                         arg 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         max 
                       
                       h 
                     
                     ⁢ 
                     
                       
                          
                         
                           h 
                           , 
                           i 
                         
                       
                       ⁢ 
                       
                         
                           R 
                           k 
                         
                         - 
                         
                           R 
                           
                             k 
                             - 
                             1 
                           
                         
                       
                        
                     
                   
                 
               
             
             
               
                 
                   
                     h 
                     k 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       
                         
                           
                             arg 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             max 
                           
                           h 
                         
                         ⁢ 
                         
                            
                           
                             w 
                             h 
                           
                            
                         
                         ⁢ 
                         
                           σ 
                           ⁡ 
                           
                             ( 
                             
                               
                                 R 
                                 k 
                               
                               ⁡ 
                               
                                 ( 
                                 h 
                                 ) 
                               
                             
                             ) 
                           
                         
                       
                       - 
                       
                         σ 
                         ⁡ 
                         
                           ( 
                           
                             
                               R 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             ⁡ 
                             
                               ( 
                               h 
                               ) 
                             
                           
                           ) 
                         
                       
                     
                     ❘ 
                   
                 
               
             
           
         
       
     
     The problem is that we cannot, in general, provide a good estimate for |σ(R k (h))−σ(R k-1 (h))|, the magnitude of the post-sigmoid change of the response of hidden unit h. We can estimate |R k (h)−R k-1 (h)|, the pre-sigmoid (raw) magnitude change, but the post-sigmoid magnitude depends on other factors, such as the current value of the hidden unit and on the direction of change, as shown on  FIG. 6 .  FIG. 6  illustrates how even though the pre-sigmoid deltas of the two hidden units are equal (Δx 1 =Δx 2 ) their post-sigmoid deltas are different (Δy 1 ≠Δy 2 ). 
     We can, however, estimate it for the first few evaluation steps, since we know the initial value of each hidden unit R 0 (h). The strategy we have found to work best is to estimate the optimal hidden units for the first few steps and then to iterate the hidden units in order for the rest of the steps. 
     The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.