Abstract:
Moving objects are classified based on maximum margin classification and discriminative probabilistic sequential modeling of range data acquired by a scanner with a set of one or more 1D laser line scanner. The range data in the form of 2D images is pre-processed and then classified. The classifier is composed of appearance classifiers, sequence classifiers with different inference techniques, and state machine enforcement of a structure of the objects.

Description:
FIELD OF THE INVENTION 
       [0001]    This invention relates generally to image processing, and more particularly to classifying objects using range scanners in computer vision applications. 
       BACKGROUND OF THE INVENTION 
       [0002]    Object classification is widely used in computer vision applications. While most common applications use 2D camera images, there is a need for accurate classification methods for 3D range data. For example, the objects can be part moving on an assembly line. 
         [0003]    The innovation of new sensor technologies results in new types of data collection techniques. In conjunction, new applications of automations appear and machines are substituted for more and more human labor. 
         [0004]    Generally, object classification can use several type of data acquisition techniques such as inductive loop detector, video detector, acoustic detector, range sensor, and infrared detector. One system uses a laser sensor that outputs range and intensity information for object detection and classification. 
       SUMMARY OF THE INVENTION 
       [0005]    The embodiments of the invention provide a method and system for classifying objects based on maximum margin classification and discriminative probabilistic sequential modeling of range data acquired by a scanner with a set of one or more 1D laser line scanner. 
         [0006]    The method includes pre-processing and classification phases. Different techniques, such as median filtering, background and foreground detection, 3D reconstruction and object prior information, are used during pre-processing steps to denoise the range data, and extract the most discriminative features. Then, a classifier is trained. The classifier is composed of an appearance classifier, a sequence classifier with different inference techniques, and state machine enforcement. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]      FIG. 1  is a block diagram of object classification according to embodiments of the invention; and 
           [0008]      FIG. 2  is a schematic of a scanner with a 1D laser line scanners according to embodiments of the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0009]    Notation 
         [0010]    We use the following notations to represent all the variables described herein, which are either explicitly defined or obvious from the description. We use bold character to represent vectors, i.e., data sequences in this case, and unbold character to represent single variables. For example, x i =         x i,1 , x i,2 , . . . , x i,T     i              represents the sequence indexed by i, and x i,j  represents the single variable of the sequence i at time step j. For an arbitrary single sequence, we skip the sequence index i and write the sequence as X i =         x, x 2 , . . . , x T           . 
         [0011]    Overview 
         [0012]      FIG. 1  shows a system and method for classifying an object  80  according to embodiments of our invention. Range data  101  are acquired by a scanner  90  from the object  80  as input for the method. 
         [0013]    As shown in  FIG. 2 , the scanner  90  includes a 1D laser line sensor. The scanner is arranged a on pole  202  near the object is to be identified. It is understood that the invention can be worked with just one sensor. 
         [0014]      FIG. 2  also shows the field of view  203  for each sensor. The sensor acquires one or more side views of the object. 
         [0015]    The 1D (line) measurements of the range data are accumulated over time, and 2D images of range profile of the object are constructed. The 2D range image is used for object type classification. Output is a class  109  of the object. 
         [0016]    The above steps can be performed in a processor  199  connected to memory and input/output interfaces as known in the art. 
         [0017]    The method includes a preprocessing phase, and a classifying phase. During preprocessing, we denoise  110  the range data, remove 120 irrelevant background information, 3D project  130  the remaining foreground pixels using range information, and sensor scanning geometries, correct  140  the range, and extract features  155 . 
         [0018]    For classification  170 , we use outputs of a appearance classifier such as multi-class support vector machine (SVM) as features for a sequence classifier such as a conditional random field (CRF) classification to obtain initial class labels, enforce  180  object structure using discriminative properties of objects and feature attributes, and the sequential structure, and finally obtain the object class  109 . 
         [0019]    Preprocessing 
         [0020]    Initial Denoising 
         [0021]    One major problem with the range data is the noise due to non-zero angle of incidence, reflectance of and objects surfaces, imperfect operation of scanner, and interfering noise from the environment. Therefore, we first denoise the range data. 
         [0022]    We use a 2D median filter to denoise the range data. Median filtering tends to preserve detail information, e.g., edges, while denoising the signal. We use an M×N neighborhood window around a corresponding pixel in the input image to be filtered, where M and N are specified empirically from the data. Median filtering reduces noise significantly even with a relatively small neighborhood. The tradeoff between the detail information and the amount of denoising is balanced by the order of the filter. The higher the order the higher the noise reduction, but less detail remains in the image. 
         [0023]    Background Estimation and Removal 
         [0024]    Some pixels can be totally corrupted during acquisition. Because of that, at the first step of background estimation, we determine “good” pixels and “bad” pixels based on a median amplitude of each row of pixels. Then, we use pixel based background estimation by fitting a single Gaussian distribution on the history of the range values of each good pixel when there is no object in the scene. At each new test sample from the same pixel, the determination is based on hypothesis testing as either foreground or background. For bad pixels, the decision is based on the hypothesis testing using the amplitude values of the signal. Finally, we use median filtering on the background mapping in order to remove irrelevant regions of noisy pixels. 
         [0025]    3D Projection 
         [0026]    Depending on environmental conditions and deployment errors, positions and orientations of the sensors relative to object can be inaccurate. To solve this issue, we back project good foreground pixels to 3D using initial sensor information, and fit a plane to a ground plane. We use a RANdom SAmple Consensus (RANSAC) process for plane fitting. This plane modifies the sensor location and orientation. The estimated base plane is assumed to correspond to the y=0 plane of a world coordinate system. Given the relative locations and orientations of the sensor with respect to base plane and the sensor field of view, we determine the 3D coordinates of each sensor measurement in a world coordinate system with back projection. The 3D projection is helpful in the following ways. We extract planar side view information from 3D values, which we use during range correction, and features. In addition, unlike 2D images, which are subject to perspective deformation of the world to image plane, the features we obtain from the 3D values are scale invariant and more informative. 
         [0027]    Range Correction 
         [0028]    The noise level of the measurements changes based on the surface reflectance. For example, a black object can result in noisy measurements. We exploit 3D information and planar side structure of the object to further correct range values. We assume that each column of measurement comes from a vertical line in 3D space. However different lines of scans can have different depth values (such as pole and body can be at different depth values). We initially determine the top 30% of depth values for each column of measurement. 
         [0029]    Next, we median filter these measurements over time with an empirically specified filter order and obtain the depth values of each column of measurement. The larger the median filter order, the larger the area is assumed to have the same depth. Then, we correct outlier range values with the ones projected to the estimated plane. After range correction the noisy samples are relocated to correct positions and the object has a smooth structure. 
         [0030]    Features 
         [0031]    We use a binary height map as our features, which is equal to the quantized side view of the 3D projection. Initially, we take a part of the object above the base plane, and quantize such that each pixel corresponds to a small height value. For some objects, due to background removal, parts of the object that touch the base are removed. Therefore, we first detect the bottom of the object in the side view and shift the object to touch the base. Moreover, to incorporate partial temporal information, we take overlapping 70×11 patches of pixels using a sliding window technique. One patch is taken for each column on the image. Then, this patch is passed to classifying phase as a feature to obtain a classification of the center column. 
         [0032]    Classification 
         [0033]    Classification is performed by the following steps. First, the height features are classified in the appearance classification  160 , and the appearance classification output is denoised using a sequence classification  170 . This approach is highly accurate because it benefits from both the maximum-margin nature of the appearance classification such as SVM and the power of discriminative probabilistic sequential model such as CRF. At last, we use a structure enforcement using a finite state machine to prevent invalid predictions, e.g. a object with only a single tire. 
         [0034]    Appearance Classification 
         [0035]    The multi-class max-margin classifier SVM assigns initial labels to each time step of the image sequence. The sequential structure of the data is not taken into account during learning in this step except the windowing procedure in feature extraction. SVM takes the 70×11 dimensional height feature described above, and labels each features as either a object body, tire ort pole state, see  FIG. 4 . The window with length  11  is shifted along the time axis, and each column of the range data is classified in that manner during testing. We use a linear kernel SVM, which enables fast processing. 
         [0036]    Sequence Classification 
         [0037]    The SVM assigns initial labels but does not consider the sequential structure of the object. Therefore, we use the CRFs as an additional layer to exploit the sequential correlations between time steps. This stage performs as a denoising part on the predictions of SVMs, removing inconsistencies. A sequential learning problem can be formulated as finding the optimal fiuictionf that can predict y=f(x), given N training sequences 
         [0000]      {(x i ,y i )} i=1   N , where x i =         x i,1 , x i,2 , . . . , x i,T     i             , 
         [0000]      and 
         [0000]      y i =         y i ,y i,2 , . . . , y i,T     i               
         [0000]    is the label sequence. 
         [0038]    One common approach to solve the sequence labeling problem using probabilistic sequential modeling is to use generative models to sequence labeling problem, such as hidden Markov models (HMM). Another common approach is to use discriminative models. One such model is the Maximum Entropy Markov Model (MEMM). In addition to being a discriminative model, MEMMs provide the ability to model arbitrary features of observation sequences. One can handle overlapping features in this way. However, the label bias problem limits the performance of MEMMs. 
         [0039]    Therefore, we use the CRFs as the sequence labeler to smooth noisy SVM outputs. A linear chain conditional random field is defined as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                        
                       
                         ( 
                         
                           y 
                           | 
                           x 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         
                           Z 
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                       
                        
                       
                         
                           ∏ 
                           
                             t 
                             = 
                             1 
                           
                           T 
                         
                          
                         
                           Ψ 
                            
                           
                             ( 
                             
                               
                                 y 
                                 t 
                               
                               , 
                               
                                 y 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 x 
                                 t 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
             
               
                 
                   
                     Ψ 
                      
                     
                       ( 
                       
                         
                           y 
                           t 
                         
                         , 
                         
                           y 
                           
                             t 
                             - 
                             1 
                           
                         
                         , 
                         
                           x 
                           t 
                         
                       
                       ) 
                     
                   
                    
                   exp 
                    
                   
                     
                       { 
                       
                         
                           
                             ∑ 
                             j 
                           
                            
                           
                             
                               λ 
                               j 
                             
                              
                             
                               
                                 g 
                                 j 
                               
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     
                                       t 
                                       - 
                                       1 
                                     
                                   
                                   , 
                                   
                                     y 
                                     t 
                                   
                                   , 
                                   x 
                                 
                                 ) 
                               
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             k 
                           
                            
                           
                             
                               μ 
                               k 
                             
                              
                             
                               
                                 u 
                                 k 
                               
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     t 
                                   
                                   , 
                                   x 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       } 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0040]    where 
         [0000]      Ψ(y t ,y t−1 , x t )
 
         [0000]    is the potential function, 
         [0000]      g j (y t−1 ,y t ,x) 
         [0000]    is the transition feature function from state, and 
         [0000]      y t−1  to y t ; u k (y t ,x), 
         [0000]    is state feature function at state y i ; λj and a μ k  are the parameters estimated at the learning process, and Z(x) is the normalization factor as a function of the observation sequence. Maximum likelihood parameter estimation of the above exponential family distribution corresponds to the maximum entropy solution. 
         [0041]    Inference 
         [0042]    After the model parameters are learned, an inference process labels a test sequence. We give a brief overview of conventional inference methods on probabilistic sequential models. One way of labeling a test sequence is the most likely labeling using the joint density y*=arg max), p(y|x). The solution can be efficiently determined via a Viterbi process using recursion 
         [0000]      (δ t ( j )=max i Ψ( j,i,x   t )δ t−1 ( i ),
 
         [0000]    which propagates the most likely path based on the maximum product rule. However, in many applications, accurately predicting whole label sequence is very difficult so that individual predictions are used. This is achieved via predicting y i,t  from a marginal distribution p(y i,t |x i ) using a dynamic programming forward-backward procedure, 
         [0043]    The forward recursion is 
         [0000]      α t ( j )=Σ i Ψ( j,i,x   t )α t−1 ( i ),
 
         [0000]    where α t (j) are the forward variables. The backward recursion is 
         [0000]      β t ( i )=Σ j Ψ t+1 )β t+1 ( j ),
 
         [0000]    where β t (i) are the backward variables, from which the marginal probabilities can be determined. 
         [0044]    Structure Enforcement 
         [0045]    The final step of classification is the enforcement of object constraints. This module takes output of the CRF. If labels do not correspond to a valid object, in other words, the labels do not correspond to some finite state machine. We convert the labels to labels of a most similar valid object model defined in a object grammar. If the CRF result is valid, this means there is no need for any correction. This is the case for a great majority of objects. The process is an error correcting regular grammar parser. 
         [0046]    Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.