Abstract:
A method and apparatus for estimating and tracking a 3D object shape and pose estimation is disclosed A plurality of 3D object models of related objects varying in size and shape are obtained, aligned and scaled, and voxelized to create a 2D height map of the 3D models to train a principle component analysis model. At least one sensor mounted on a host vehicle obtains a 3D object image. Using the trained principle component analysis model, the processor executes program instructions to estimate the shape and pose of the detected 3D object until the shape and pose of the detected 3D object matches one principle component analysis model. The output of the shape and pose of the detected 3D object is used in one vehicle control function.

Description:
BACKGROUND 
       [0001]    The present invention relates, to 3D object identification and tracking methods and apparatus. 
         [0002]    Real time mapping of 2D and 3D images from image detectors, such as cameras, is used for object identification. 
         [0003]    In manufacturing, known 2D shapes or edges of objects are compared with actual object shapes to determine product quality. 
         [0004]    However, 3D object recognition is also required in certain situations. 3D object segmentation and tracking methods have been proposed for autonomous vehicle applications. However, such methods have been limited to objects with a fixed 3D shape. Other methods attempt to handle variations in 2D shapes, i.e., (the contour of an object in 2D). However, these methods lack the ability to model shape variations in 3D space. 
         [0005]    Modeling such 3D shape variations may be necessary in autonomous vehicle applications. The rough estimate of the state of some object i.e., other cars on the road, may be sufficient in some cases requiring simple object detection, such as blind spot and back up object detection applications. More detailed information on the state of the objects seems to be necessary as 3D objects, i.e., vehicles, change shape, size and pose when the vehicle turns in front of another vehicle, for example, or the location of a parked vehicle in the parking vehicle changes relative to a moving host vehicle. 
       SUMMARY 
       [0006]    A method for estimating the shape and pose of a 3D object includes detecting a 3D object external to a host vehicle using at least one image sensor, using a processor, to estimate at least one of the shape and pose of the detected three 3D object as at least one of the host vehicle and the 3D object change position relative to each other, and providing an output of the 3D object shape and pose. 
         [0007]    The method further obtaining a plurality of 3D object models, where the models are related to a type of object, but differ in shape and size, using a processor, to align and scale the 3D object models, voxelizing the aligned and scaled 3D object models, creating a 2D height map of the voxelized 3D object models, and training a principle component analysis model for each of the shapes of the plurality of 3D object models. 
         [0008]    The method stores the 3D object models in a memory. 
         [0009]    For each successive image of the 3D object, the method iterates the estimation of the shape and pose of the object until the model of the 3D object matches the shape and pose of the detected 3D object. 
         [0010]    An apparatus for estimating the shape and pose of a 3D object relative to a host vehicle includes at least one sensor mounted in a vehicle for sensing a 3D object in a vehicle&#39;s vicinity and a processor, coupled to the at least one sensor. The processor is operable to: obtain a 3D object image from the at least one sensor, estimating the shape of the object in the 3D object image, estimating the pose of the 3D object in the 3D object image, optimizing the estimated shape and pose of the 3D object until the estimated 3D object shape and pose substantially matches the 3D object image; and outputting the shape and pose of the optimized 3D object. 
         [0011]    The apparatus includes a control mounted on the vehicle for controlling at least one vehicle function, with the processor transmitting the output of the optimized shape and pose of the 3D object to the vehicle control for further processing. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
         [0012]    Various features, advantages and other uses of the present invention will become more apparent by referring to the following detailed description and drawing in which: 
           [0013]      FIG. 1  is a pictorial representation of a vehicle implementing the 3D object shape and pose estimation and tracking method and apparatus; 
           [0014]      FIG. 2  is a block diagram showing the operational inputs and outputs of the method and apparatus; 
           [0015]      FIG. 3  is a block diagram showing the sequence for training the PCA latent space model of 3D shapes; 
           [0016]      FIG. 4  is a pictorial representation of stored object models; 
           [0017]      FIG. 5  is a pictorial representation of the implementation of the method and apparatus showing the original 3D model of an object, the 3D model aligned and scaled, the aligned model voxelized, and the 2D height map of the model used for training PCA model; 
           [0018]      FIG. 6  is a demonstration of the learned PCA latent space for the 3D shape of the vehicle; 
           [0019]      FIG. 7  is a block diagram of the optimization sequence used in the method and apparatus; 
           [0020]      FIG. 8  is a sequential pictorial representation of the application of PWP3D on segmentation and pose estimation of a vehicle showing, from top to bottom, and left to right, the initial pose estimated by a detector, and sequential illustrations of a gradient-descent search to find the optimal pose of the detected vehicle; and 
           [0021]      FIG. 9  is a sequential series of image segmentation results of the present method and apparatus on a detected video of a turning vehicle. 
       
    
    
     DETAILED DESCRIPTION 
       [0022]    Referring now to  FIGS. 1-7  of the drawing, there is depicted a method and apparatus for 3D object shape and pose estimation and object tracking. 
         [0023]    By way of example, the method and apparatus is depicted as being executed on a host vehicle  10 . The host vehicle  10  may be any type of moving or stationary vehicle, such as an automobile, truck, bus, golf cart, airplane, train, etc. 
         [0024]    A computing unit or control  12  is mounted in the vehicle, hereafter referred to as a “host vehicle,” for executing the method. The computing unit  12  may be any type of computing unit using a processor or a central processor in combination with all of the components typically used with a computer, such as a memory, either RAM or ROM for storing data and instructions, a display, a touch screen or other user input device or interface, such as a mouse, keyboard, microphone, etc., as well as various input and output interfaces. In the vehicle application described hereafter, the computing unit  12  may be a stand-alone or discrete computing unit mounted in the host vehicle  10 . Alternately, the computing unit  12  may be any of one or more of the computing units employed in a vehicle, with the PWP3D engine  16  control program, described hereafter, stored in a memory  14  associated with the computing unit  12 . 
         [0025]    The PWP3D engine  16  may be used in combination with other applications found on the host vehicle  10 , such as lane detection, blind spot detection, backup object range detector autonomous vehicle driving and parking, collision avoidance, etc. 
         [0026]    A control program implementing the PWP 3D engine  16  can be stored in the memory  14  and can include a software program or a set of instructions in any programming language, source code, object code, machine language, etc., which is executed by the computing unit  12 . 
         [0027]    Although not shown, the computing unit  12  may interface with other computing units in the host vehicle  10 , which control vehicle speed, navigation, breaking and signaling applications. 
         [0028]    In conjunction with the present methods the apparatus includes inputs from sensors  18  mounted on the host vehicle  10  to provide input data to the computing unit  12  for executing the PWP3D engine  16 . Such sensors  18 , in the present example, may include one or more cameras  20 , shown in  FIG. 2 , mounted at one or more locations on the host vehicle  10 . In a single camera  20  application, the camera  20  is provided with a suitable application range including a focal point and a field of view. In a multiple camera application, each camera may be mounted a relatively identical location or different locations and may be provided with the same or different application range, including field of view and focal point. 
         [0029]    According to the method and apparatus, the first step  30  in the set up sequence, as shown in  FIG. 3  is implemented to perform optimization in the 3D space shape. First, the method trains a Principle Component Analysis (PCA) latent space model of 3D shapes. 
         [0030]    This optimization includes step  30 , ( FIG. 3 ), in which a set of 3D object models are obtained. As shown in  FIG. 4 , such models can be obtained from a source such as the Internet, data files etc., to show a plurality of different, but related, objects such as a plurality of 3D vehicles, such as vans, SUVs, sedans, hatchbacks, coupes and sport cars. The object images are related in type, but differ in size and/or shape. 
         [0031]    Next, trimesh is applied in step  32  to the 3D models obtained in step  30 , to align and scale the 3D models, see the second model  33  in  FIG. 5 . 
         [0032]    Next, in step  34 , the 3D model data from step  32  is voxelized as shown in the model at horizontal axis  3  in  FIG. 5 . 
         [0033]    Next, in step  36 , a 2D height map of the 3D voxelized models from step  34  is created for each model  28  obtained in step  30  resulting in model  37  in  FIG. 5 . 
         [0034]    Finally, in step  38 , the PCA and latent variable model is trained using the 2D height maps from step  36 . 
         [0035]    In  FIG. 6 , the learned PCA latent space is demonstrated for 3D shapes of vehicles. The vertical axis shows the first three principle components representing the major directions of variation in data. The horizontal axis shows the variations of the mean shape (index 0) along each principle component (PC). The indices along the horizontal axis are the amount of deviation from the mean in units of square root of the corresponding Eigen value. It should be noted in  FIG. 6 , that the first PC intuitively captures the important variations of vehicle fix. For example, the first PC captures the height of the vehicle (minus 3 in the horizontal axis represents an SUV and 3 represents a short sporty vehicle). 
         [0036]    In obtaining real time 3D object identification, the computing unit  12 , in step  50 ,  FIG. 2 , executing the stored set of instructions or program, first obtains a 3D object image from a sensor  28 , such as a camera  20 .  FIG. 8  shows an example of an initial 3D object image  60 . Next, the computing unit  12  estimates the shape of the object in step  52  and then estimates the pose of the object in step  54 . These steps executed on the object image  60  in  FIG. 8  are shown by the subsequent figures in  FIG. 8  in which an estimate of the object shape is superimposed over the object image. It will be understood that in real time, only the estimated object shape and pose is generated  60  by the method and apparatus, as the method is optimizing or comparing the estimated 3D object shape and pose with the initial image object  60 . Various iterations of step  56  are undertaken until the 3D object shape and pose is optimized. At this time, the 3D object shape and pose can be output in step  58  by the computing unit  12  for other uses or to other computing units or applications in the host vehicle  10 , such as collision avoidance, vehicle navigation control, acceleration and/or braking, geographical information, etc. for the control of a vehicle function. 
         [0037]    In order to implement the optimization of the latent space model, the following equations are derived 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       ( 
                       Φ 
                       ) 
                     
                   
                   = 
                   
                     - 
                     
                       
                         ∑ 
                         
                           x 
                           ∈ 
                           Ω 
                         
                       
                        
                       
                         log 
                          
                         
                           ( 
                           
                             
                               
                                 
                                   H 
                                   e 
                                 
                                  
                                 
                                   ( 
                                   Φ 
                                   ) 
                                 
                               
                                
                               
                                 P 
                                 f 
                               
                             
                             + 
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     
                                       H 
                                       e 
                                     
                                      
                                     
                                       ( 
                                       Φ 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                                
                               Pb 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0038]    Where He is the Heaviside step function, is the sign distance function of the contour of the projection of the 3D model, P f  and P b  are the posterior probabilities of the pixel x belonging to foreground and background, respectively. The objective is to compute the partial derivatives of the energy function with respect to the PCA latent space variables,          . 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       E 
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     - 
                     
                       
                         ∑ 
                         
                           x 
                           ∈ 
                           Ω 
                         
                       
                        
                       
                         
                           
                             
                               P 
                               f 
                             
                             - 
                             
                               P 
                               b 
                             
                           
                           
                             
                               
                                 
                                   H 
                                   e 
                                 
                                  
                                 
                                   ( 
                                   Φ 
                                   ) 
                                 
                               
                                
                               
                                 P 
                                 f 
                               
                             
                             + 
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     
                                       H 
                                       e 
                                     
                                      
                                     
                                       ( 
                                       Φ 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                                
                               
                                 P 
                                 b 
                               
                             
                           
                         
                          
                         
                           
                             ∂ 
                             
                               
                                 H 
                                 e 
                               
                                
                               
                                 ( 
                                 
                                   Φ 
                                    
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                           
                           
                             ∂ 
                             
                               γ 
                               i 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ∂ 
                       
                         
                           H 
                           e 
                         
                          
                         
                           ( 
                           
                             Φ 
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         ∂ 
                         
                           
                             H 
                             e 
                           
                            
                           
                             ( 
                             Φ 
                             ) 
                           
                         
                       
                       
                         ∂ 
                         Φ 
                       
                     
                     · 
                     
                       ( 
                       
                         
                           
                             
                               ∂ 
                               Φ 
                             
                             
                               ∂ 
                               x 
                             
                           
                            
                           
                             
                               ∂ 
                               x 
                             
                             
                               ∂ 
                               
                                 γ 
                                 i 
                               
                             
                           
                         
                         + 
                         
                           
                             
                               ∂ 
                               Φ 
                             
                             
                               ∂ 
                               y 
                             
                           
                            
                           
                             
                               ∂ 
                               y 
                             
                             
                               ∂ 
                               
                                 γ 
                                 i 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             
               
                 ∂ 
                 
                   
                     H 
                     e 
                   
                    
                   
                     ( 
                     Φ 
                     ) 
                   
                 
               
               
                 ∂ 
                 Φ 
               
             
             , 
           
         
       
     
         [0000]    the derivative of the Heaviside step function, is the Dirac delta function δ(Φ), whose approximation is known. Also 
         [0000]    
       
         
           
             
               ∂ 
               Φ 
             
             
               ∂ 
               x 
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               ∂ 
               Φ 
             
             
               ∂ 
               y 
             
           
         
       
     
         [0000]    are trivally computed, given the signed distance function, Φ(x,y). The only unknowns so far are 
         [0000]    
       
         
           
             
               ∂ 
               Φ 
             
             
               ∂ 
               
                 γ 
                 i 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               
                 ∂ 
                 Φ 
               
               
                 ∂ 
                 
                   γ 
                   i 
                 
               
             
             . 
           
         
       
     
         [0000]    In the following derivations, the unknowns can be reduced to computing the derivatives of           given the camera model. 
         [0000]    
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           x 
                         
                       
                       
                         
                           y 
                         
                       
                     
                     ] 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               
                                 f 
                                 u 
                               
                                
                               
                                 
                                   X 
                                   c 
                                 
                                 
                                   Z 
                                   c 
                                 
                               
                             
                             + 
                             
                               u 
                               o 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 f 
                                 v 
                               
                                
                               
                                 
                                   X 
                                   c 
                                 
                                 
                                   Z 
                                   c 
                                 
                               
                             
                             + 
                             
                               v 
                               o 
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0039]    Where f u  and f v  are horizontal and vertical focal lengths of the camera and           is the center pixel of the image (all available from the intrisic camera calibration parameters), X c =          is the 3D point in the camera coordinates that productes to pixel (x,y). The mapping from image to camera and image to object coordinate systems are known and can be stored during the rendering of the 3D model. This results in the following equations with reduction of the unknowns to 
         [0000]    
       
         
           
             
               
                 ∂ 
                 
                   X 
                   c 
                 
               
               
                 ∂ 
                 
                   γ 
                   i 
                 
               
             
             , 
           
         
       
     
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       x 
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         f 
                         u 
                       
                        
                       
                         1 
                         Z 
                       
                        
                       
                         
                           ∂ 
                           
                             X 
                             c 
                           
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     - 
                     
                       
                         f 
                         u 
                       
                        
                       
                         
                           X 
                           c 
                         
                         
                           Z 
                           c 
                           2 
                         
                       
                        
                       
                         
                           ∂ 
                           
                             Z 
                             c 
                           
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ∂ 
                       y 
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         f 
                         u 
                       
                        
                       
                         1 
                         
                           Z 
                           c 
                         
                       
                        
                       
                         
                           ∂ 
                           
                             Y 
                             c 
                           
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     - 
                     
                       
                         f 
                         u 
                       
                        
                       
                         
                           X 
                           c 
                         
                         
                           Z 
                           c 
                           2 
                         
                       
                        
                       
                         
                           ∂ 
                           
                             Z 
                             c 
                           
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0040]    Accordingly, the results is the following mapping from object coordinates to camera coordinates: 
         [0000]        X   c   =RD+T    (7)
 
         [0041]    Where R and T are object rotation and translation matrices and X is the corresponding 3D point in object coordinates. Consequently, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       
                         X 
                         c 
                       
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         r 
                         00 
                       
                        
                       
                         
                           ∂ 
                           X 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     + 
                     
                       
                         r 
                         01 
                       
                        
                       
                         
                           ∂ 
                           Y 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     + 
                     
                       
                         r 
                         02 
                       
                        
                       
                         
                           ∂ 
                           Z 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ∂ 
                       
                         Y 
                         c 
                       
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         r 
                         10 
                       
                        
                       
                         
                           ∂ 
                           X 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     + 
                     
                       
                         r 
                         11 
                       
                        
                       
                         
                           ∂ 
                           Y 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     + 
                     
                       
                         r 
                         12 
                       
                        
                       
                         
                           ∂ 
                           Z 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ∂ 
                       
                         Z 
                         c 
                       
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         r 
                         20 
                       
                        
                       
                         
                           ∂ 
                           X 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     + 
                     
                       
                         r 
                         21 
                       
                        
                       
                         
                           ∂ 
                           Y 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                     + 
                     
                       
                         r 
                         22 
                       
                        
                       
                         
                           ∂ 
                           Z 
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0042]    Where r ij  is the elements of matrix at a location R at location i and j. To make the derivationats shorter and the notations more clear, an assumption is that the stixel mesh model and the object coordinates are the same, where the height of each cell in the stixel Z and its 2D coordinates is (X,X,). This assumption does not hurt the generality of the derivations, as mapping from stixel to object coordinate (rotation and translation) easily translates to an extra step in this inference. Since only the height of the stixels change as a function of the latent variables          , the results is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         ∂ 
                         X 
                       
                       
                         ∂ 
                         
                           γ 
                           i 
                         
                       
                     
                     = 
                     0 
                   
                    
                   
                     
 
                   
                    
                   
                     
                       
                         ∂ 
                         Y 
                       
                       
                         ∂ 
                         
                           γ 
                           i 
                         
                       
                     
                     = 
                     0 
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0000]    And the only remaining unknown is 
         [0000]    
       
         
           
             
               
                 ∂ 
                 Z 
               
               
                 ∂ 
                 
                   γ 
                   i 
                 
               
             
             . 
           
         
       
     
         [0043]    Each 3D point in object coordinates, X=(X, Y,Z),falls on a triangular face in the stixel triangular mesh model, say with vertices of coordinates X j =(X j , Yj,Zj) for j=1,2,3. Moreover, change in Z is only dependent on Z 1 , Z 2  and Z 3  (and not other vertex in the 3D mesh. Therefore, the chain rule gives: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       Z 
                     
                     
                       ∂ 
                       
                         γ 
                         i 
                       
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         1 
                       
                       3 
                     
                      
                     
                         
                     
                      
                     
                       
                         
                           ∂ 
                           Z 
                         
                         
                           ∂ 
                           
                             Z 
                             j 
                           
                         
                       
                        
                       
                         
                           ∂ 
                           
                             Z 
                             j 
                           
                         
                         
                           ∂ 
                           
                             γ 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Since the method uses a PCA latent space, every stixel model Z can be represented as a linear combination of principle components as follows. 
         [0000]    
       
         
           
             
               
                 
                   Z 
                   = 
                   
                     
                       Z 
                       _ 
                     
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         D 
                       
                        
                       
                           
                       
                        
                       
                         
                           γ 
                           i 
                         
                          
                         
                           Γ 
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0044]    Where Z is the mean stixel, D is the number of dimensions in the latent space, and           is the i th  eigen vector. Eq. 13 implies: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         ∂ 
                         
                           Z 
                           j 
                         
                       
                       
                         ∂ 
                         
                           γ 
                           i 
                         
                       
                     
                     = 
                     
                       
                         
                           Γ 
                           
                             i 
                             , 
                             j 
                           
                         
                          
                         
                             
                         
                          
                         j 
                       
                       = 
                       1 
                     
                   
                   , 
                   2 
                   , 
                   3 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0045]    Where r i,j  is the j th  element of the eigen vector. Since each face in the mesh model is a plane in 3D space which passes through X, X 1 , X 2 , and X 3 , if the plane is represented with parameters A, B, C, D, the result is: 
         [0000]    
       
         
           
             
               
                 
                   
                     AX 
                     + 
                     BY 
                     + 
                     CZ 
                     + 
                     D 
                   
                   = 
                   
                     
                       0 
                       ⇒ 
                       Z 
                     
                     = 
                     
                       
                         
                           - 
                           1 
                         
                         C 
                       
                        
                       
                         ( 
                         
                           D 
                           + 
                           AX 
                           + 
                           BY 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and hence: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         ∂ 
                         Z 
                       
                       
                         ∂ 
                         
                           Z 
                           i 
                         
                       
                     
                     = 
                     
                       
                         
                           - 
                           1 
                         
                         C 
                       
                        
                       
                         ( 
                         
                           
                             X 
                              
                             
                               
                                 ∂ 
                                 A 
                               
                               
                                 ∂ 
                                 
                                   Z 
                                   i 
                                 
                               
                             
                           
                           + 
                           
                             Y 
                              
                             
                               
                                 ∂ 
                                 B 
                               
                               
                                 ∂ 
                                 
                                   Z 
                                   i 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                       
                   
                    
                   
                     i 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   3 
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0046]    Substituting X 1 , X 2  and X 3  and then solving the system of equations gives A,B,C, and D by the following determinants: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       A 
                       = 
                       
                          
                         
                           
                             
                               1 
                             
                             
                               
                                 Y 
                                 1 
                               
                             
                             
                               
                                 Z 
                                 1 
                               
                             
                           
                           
                             
                               1 
                             
                             
                               
                                 Y 
                                 2 
                               
                             
                             
                               
                                 Z 
                                 2 
                               
                             
                           
                           
                             
                               1 
                             
                             
                               
                                 Y 
                                 3 
                               
                             
                             
                               
                                 Z 
                                 3 
                               
                             
                           
                         
                          
                       
                     
                     , 
                     
                       B 
                       = 
                       
                          
                         
                           
                             
                               
                                 X 
                                 1 
                               
                             
                             
                               1 
                             
                             
                               
                                 Z 
                                 1 
                               
                             
                           
                           
                             
                               
                                 X 
                                 2 
                               
                             
                             
                               1 
                             
                             
                               
                                 Z 
                                 2 
                               
                             
                           
                           
                             
                               
                                 X 
                                 3 
                               
                             
                             
                               1 
                             
                             
                               
                                 Z 
                                 3 
                               
                             
                           
                         
                          
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       C 
                       = 
                       
                          
                         
                           
                             
                               
                                 X 
                                 1 
                               
                             
                             
                               
                                 Y 
                                 1 
                               
                             
                             
                               1 
                             
                           
                           
                             
                               
                                 X 
                                 2 
                               
                             
                             
                               
                                 Y 
                                 2 
                               
                             
                             
                               1 
                             
                           
                           
                             
                               
                                 X 
                                 3 
                               
                             
                             
                               
                                 Y 
                                 3 
                               
                             
                             
                               1 
                             
                           
                         
                          
                       
                     
                     , 
                     
                       D 
                       = 
                       
                          
                         
                           
                             
                               
                                 X 
                                 1 
                               
                             
                             
                               
                                 Y 
                                 1 
                               
                             
                             
                               
                                 Z 
                                 1 
                               
                             
                           
                           
                             
                               
                                 X 
                                 2 
                               
                             
                             
                               
                                 Y 
                                 2 
                               
                             
                             
                               
                                 Z 
                                 2 
                               
                             
                           
                           
                             
                               
                                 X 
                                 3 
                               
                             
                             
                               
                                 Y 
                                 3 
                               
                             
                             
                               
                                 Z 
                                 3 
                               
                             
                           
                         
                          
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Expanding the determinants and solving for partial derivatives of Eq. 16 yields: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         ∂ 
                         A 
                       
                       
                         ∂ 
                         
                           Z 
                           i 
                         
                       
                     
                     = 
                     
                       
                         Y 
                         3 
                       
                       - 
                       
                         Y 
                         2 
                       
                     
                   
                   , 
                   
                     
                       
                         ∂ 
                         B 
                       
                       
                         ∂ 
                         
                           Z 
                           i 
                         
                       
                     
                     = 
                     
                       
                         X 
                         2 
                       
                       - 
                       
                         X 
                         3 
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     
                       
                         ∂ 
                         C 
                       
                       
                         ∂ 
                         
                           Z 
                           i 
                         
                       
                     
                     = 
                     0 
                   
                   , 
                   
                     
                       
                         ∂ 
                         D 
                       
                       
                         ∂ 
                         
                           Z 
                           i 
                         
                       
                     
                     = 
                     
                       
                         
                           - 
                           
                             X 
                             2 
                           
                         
                          
                         
                           Y 
                           3 
                         
                       
                       + 
                       
                         
                           X 
                           3 
                         
                          
                         
                           Y 
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Finally, substituting Eq. 18 into Eq. 16, the result is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       Z 
                     
                     
                       ∂ 
                       
                         Z 
                         1 
                       
                     
                   
                   = 
                   
                     
                       
                         X 
                          
                         
                           ( 
                           
                             
                               Y 
                               2 
                             
                             - 
                             
                               Y 
                               3 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           X 
                           2 
                         
                          
                         
                           ( 
                           
                             
                               Y 
                               3 
                             
                             - 
                             Y 
                           
                           ) 
                         
                       
                       + 
                       
                         
                           X 
                           3 
                         
                          
                         
                           ( 
                           
                             Y 
                             - 
                             
                               Y 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     
                       
                         
                           X 
                           1 
                         
                          
                         
                           ( 
                           
                             
                               Y 
                               2 
                             
                             - 
                             
                               Y 
                               3 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           X 
                           2 
                         
                          
                         
                           ( 
                           
                             
                               Y 
                               3 
                             
                             - 
                             
                               Y 
                               1 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           X 
                           3 
                         
                          
                         
                           ( 
                           
                             
                               Y 
                               1 
                             
                             - 
                             
                               Y 
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             
               
                 ∂ 
                 Z 
               
               
                 ∂ 
                 
                   Z 
                   2 
                 
               
             
              
             
                 
             
              
             and 
              
             
                 
             
              
             
               
                 ∂ 
                 Z 
               
               
                 ∂ 
                 
                   Z 
                   3 
                 
               
             
           
         
       
     
         [0000]    are similarly derived. Therefore, the derivatives of the energy function with respect to latent variables is derived now. A bottom-up approach to computing 
         [0000]    
       
         
           
             
               
                 ∂ 
                 E 
               
               
                 ∂ 
                 
                   γ 
                   i 
                 
               
             
             , 
           
         
       
     
         [0000]    which is used in the algorithms is substituting data into the equations in the following order: 
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Algorithm 1: Algorithm for optimizing the shape of the object  
               
               
                 with respect to the latent variables of shape space. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                  1: 
                 for each latent variable γ i  do 
               
               
                  2: 
                  Ei ← 0 
               
               
                  3: 
                  for each pixel (x, y) ∈ Ω do 
               
               
                  4: 
                   Find the corresponding X, X 1 , X 2  and X 2  in object/stixel coordinates 
               
               
                   
                   (known fromrendering and projection matrices). 
               
               
                   
               
               
                  5: 
                   
           ∂   Z       ∂     Z   1                    ←           X        (       Y   2     -     Y   3       )       +       X   2          (       Y   3     -   Y     )       +       X   3          (     Y   -     Y   2       )               X   1          (       Y   2     -     Y   3       )       +       X   2          (       Y   3     -     Y   1       )       +       X   3          (       Y   1     -     Y   2       )                         and                 similarly                     ∂   Z       ∂     Z   2                       and                     ∂   Z       ∂     Z   3               
 
               
               
                   
               
               
                  6: 
                   
               ∂     Z   j         ∂     γ   i         ←       Γ     i   ,   j                     for                 j       =   1     ,   2   ,   3       
 
               
               
                   
               
               
                  7: 
                   
           ∂   Z       ∂     γ   i         ←       ∑     j   =   1     3              ∂   Z       ∂     Z   j                ∂     Z   j         ∂     γ   i                 
 
               
               
                   
               
               
                  8: 
                   
           ∂     X   c         ∂     γ   i         ←       r   02            ∂   Z       ∂     γ   i                       and                     ∂     Y   c         ∂     γ   i           ←       r   12            ∂   Z       ∂     γ   i                       and                     ∂     Z   c         ∂     γ   i           ←       r   22            ∂   Z       ∂     γ   i               
 
               
               
                   
               
               
                  9: 
                   
           ∂   y       ∂     γ   i         ←         f   v          1     Z   c              ∂     Y   c         ∂     γ   i           -       f   u            X   c       Z   c   2              ∂     Z   c         ∂     γ   i                 
 
               
               
                   
               
               
                 10: 
                   
           ∂   x       ∂     γ   i         ←         f   u          1   Z            ∂     X   c         ∂     γ   i           -       f   u            X   c       Z   c   2              ∂     Z   c         ∂     γ   i                 
 
               
               
                   
               
               
                 11: 
                   
           ∂       H   e          (     Φ        (     x   ,   y     )       )           ∂     γ   i         ←       δ        (   Φ   )            (           ∂   Φ       ∂   x              ∂   x       ∂     γ   i           +         ∂   Φ       ∂   y              ∂   y       ∂     γ   i             )           
 
               
               
                   
               
               
                 12: 
                   
           ∂   E       ∂     γ   i         ←     -       ∑     x   ∈   Ω                  P   f     -     P   b               H   e          (   Φ   )            P   f       +       (     1   -       H   e          (   Φ   )         )        Pb                ∂       H   e          (     Φ        (     x   ,   y     )       )           ∂     γ   i                   
 
               
               
                   
               
               
                 13: 
                  end for 
               
               
                   
               
               
                 14: 
                  
         E   i     ←       E   i     +       ∂   E       ∂     γ   i               
 
               
               
                   
               
               
                 15: 
                 end for