Patent Publication Number: US-8983127-B2

Title: Object tracking with opposing image capture devices

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is the 35 U.S.C. §371 national stage of, and claims priority to and the benefit of, PCT application PCT/US2010/034706, filed May 13, 2010, which claims priority to and the benefit of U.S. Provisional Application No. 61/315,543, filed on Mar. 19, 2010, herein incorporated by reference in its entirety. 
    
    
     FIELD OF THE DISCLOSURE 
     The present disclosure relates to computerized tracking of objects, and more specifically, to object tracking using computer-based vision. 
     BACKGROUND 
     Vision-based tracking systems for tracking objects in motion can be classified into two genres: inside-looking-out, in which the optical sensor is placed on the moving object and the scene is stationary; and outside-looking-in, in which the optical sensor is stationary and observes the moving object. One conventional approach to vision-based tracking relies on markers in the environment for use as reference points. Another conventional approach relies on a pre-loaded model of the physical environment. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Many aspects of the disclosure can be better understood with reference to the following drawings. The components in the drawings are not necessarily to scale, emphasis instead being placed upon clearly illustrating the principles of the present disclosure. 
         FIG. 1  is a diagram showing the relationship between image capture devices and an object being tracked, according to some embodiments. 
         FIG. 2  is a diagram showing an orthogonal configuration of image capture devices, according to some embodiments. 
         FIG. 3  is a flowchart of a process to compute successive positions for an object being tracked, according to some embodiments. 
         FIG. 4  is a diagram illustrating a process to compute average optical flow vectors, according to some embodiments. 
         FIG. 5  is a flowchart of a process to compute successive positions for an object being tracked, according to some embodiments. 
         FIG. 6  is a diagram illustrating a process to compute angular velocity, according to some embodiments. 
         FIG. 7  is a hardware block diagram of a tracking system, according to some embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     Disclosed herein are implementations of an inside-out vision-based tracking system which uses a computing device and an orthogonal configuration of two pairs of opposing image capture devices. An image capture device may take the form, for example, of a digital video camera. In some embodiments, the image capture device is a perspective camera. 
     The arrangement of image capture devices moves along with the object being tracked. The computing device receives a series of images from each image capture device and calculates successive positions for the object. The arrangement of image capture devices, in conjunction with polar correlation of optical flow, reduces the complexity of computing the object&#39;s three-dimensional motion. 
     Possible applications for the tracking system embodiments disclosed herein include, but are not limited to: a handheld controller for playing games; an input device for human-computer interactions like scrolling, pointing, tracking, etc.; and an input device for interacting with virtual environments. The tracking system embodiments can also be mounted on a mobile platform for use in robotic applications such as tracking, localization, and mapping. 
       FIG. 1  is a diagram showing the relationship between the image capture devices and the object being tracked. The image capture arrangement  110  includes a plurality of image capture devices  120 - 1 ,  120 - 2 ,  120 - 3 ,  120 - 4 . Arrangement  110  travels along with an object  130  being tracked. A computing device (see  FIG. 7 ) receives a series of images from each image capture device  120 - 1 ,  120 - 2 ,  120 - 3 ,  120 - 4  and processes these images to compute successive positions for the moving object. A new object position is based on a previous position of the object, a translation of the object, and a current orientation of the object. These computations are described in more detail below. 
     As noted above, the image capture devices  120  are arranged in an orthogonal manner, with two sets of opposing pairs. Although the object being tracked is not shown in  FIG. 2 , this image capture device is stationary with respect to the object and thus observes the moving object. The image capture device arrangement  110  is therefore said to be “worn by” or “held by” the object being tracked. 
       FIG. 2  is a diagram showing the orthogonal configuration of image capture devices in various embodiments of the tracking system disclosed herein. The image capture devices  120  are arranged as a first opposing pair  210  and a second opposing pair  220 . The arrangement  110  is orthogonal, such that devices  120  are equidistant from, and at right angles to, each other. The position s k  and orientation m k  of each image capture device  120  with respect to the coordinate system of the arrangement  110  is as follows. For device  120 - 1 , s 1 =[0, 0, 1] T ; 
               m   1     =         [         1       0       0           0       1       0           0       0       1         ]     r     .           
For device  120 - 2 , s 2 =[0, 0, −1] T ;
 
               m   2     =         [           -   1         0       0           0       1       0           0       0         -   1           ]     r     .           
For device  120 - 3 , s 3 =[1, 0, 0] T ;
 
               m   3     =         [         0       0         -   1             0       1       0           1       0       0         ]     r     .           
For device  120 - 4 , s 4 =[−1, 0, 0] T ;
 
     
       
         
           
             
               m 
               2 
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         1 
                       
                     
                     
                       
                         0 
                       
                       
                         1 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           - 
                           1 
                         
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                   
                   ] 
                 
                 r 
               
               . 
             
           
         
       
     
     Devices  120  are held in this fixed arrangement relative to each other by a rig (not shown). In addition to keeping the image capture device arrangement fixed, the rig structure allows the arrangement to be secured to the object ( 130  in  FIG. 1 ) that is being tracked. As can be appreciated, this rig can be implemented using a wide variety of different mechanisms. 
     As noted above, the tracking system computes successive positions for the moving object  130  ( FIG. 1 ) from images provided by the image capture devices.  FIG. 3  is a flowchart of a process performed by some embodiments of computing device  710  ( FIG. 7 ) to compute successive positions for the moving object  130 . The process  300  begins at block  310 , where computing device  710  analyzes a time series of images to compute the optical flow for images from each image capture device  120 . Optical flow, also known as image motion, refers to a vector describing the motion of each pixel from one image of a scene to the next image of a scene. In some embodiments, the time series is a pair of images or a pair of successive images. At block  320 , computing device  710  divides an image into subsections, and uses the optical flow vectors to compute an average optical flow for each subsection. In some embodiments, the subsections are of equal size. In some embodiments, the subsection is a quadrant. In some embodiments, the average optical flow is computed at symmetric points within the subsections. 
     Having computed an average optical flow per subsection, per image capture device, processing moves to block  330 , where computing device  710  obtain the object&#39;s direction of translation in a simplified manner by taking advantage of the orthogonal image capture device configuration. The principle of polar correlation holds that opposing image capture devices have components of optical flow in common: the rotation terms. These common components allow the rotation terms to be cancelled out of the average optical flow, leaving only translation terms. While considering optical flow across all subsections and all image capture devices, block  330  uses polar correlation to cancel out the rotation terms of optical flow, leaving only translation terms. Computing device  710  computes the object&#39;s direction of translation from these translation terms. 
     At block  340 , computing device  710  computes the direction of translation of object  130  based on the translation terms of the average optical flow. The direction of translation is not based on rotation terms within the average optical flow (which have been cancelled out in bock  330 ). Finally, at block  350 , computing device  710  computes the object&#39;s next position based on the direction of translation (block  340 ), together with the object&#39;s current position and the object&#39;s current orientation. 
       FIG. 4  is a diagram illustrating a process performed by some embodiments of computing device  710  ( FIG. 7 ) to compute average optical flow vectors. Optical flow vectors  410  are computed for image pairs, as described earlier in connection with  FIG. 3 . The image  420  is divided into quadrants  430 . The center point of each quadrant is a quadrantization point Q i   k    440  (repeated for each corresponding image capture device C k ). At each quadrantization point Q i   k , computing device  710  computes the average optical flow vector  450 , having some uniform constant magnitude λ and angle θ, as the average of all flow vectors&#39; angles in that quadrant. 
       FIG. 5  is a flowchart of a process performed by some embodiments of computing device  710  ( FIG. 7 ) to compute successive positions for the moving object  130 . Where the chart of  FIG. 3  focused on the computation of direction of translation of object  130 , the flowchart of  FIG. 5  shows how the direction of translation computation fits into the overall computation of the next position. The process  500  begins at block  510 , where computing device  710  computes optical flow for successive image pairs. At block  520 , computing device  710  uses polar correlation to compute the object&#39;s direction of translation from the optical flow. (The concept of polar correlation and it use was described in connection with  FIG. 3 .) At block  530 , computing device  710  computes the object&#39;s translation vector from the direction of translation. In some embodiments, a constant magnitude of translation is assumed. 
     At block  540 , computing device  710  computes the object&#39;s rotation, by using the direction of translation to remove translation terms from optical flow, which leaves the rotation terms. At block  550 , computing device  710  computes the object&#39;s current orientation, by cumulatively applying previously computed rotations of the object. More specifically, block  550  computes the Euler angles of rotation by normalizing the angular velocity and then multiplying it with a constant magnitude. (Computation of angular velocity is discussed later in connection with  FIG. 6 ). A rotation matrix R for every time frame is then computed from these Euler angles. Finally, at block  560 , computing device  710  computes the object&#39;s next position based on the orientation ( 550 ), the translation ( 530 ) and the current position. 
       FIG. 6  is a diagram illustrating a process performed by some embodiments of computing device  710  ( FIG. 7 ) to compute angular velocity. In this process, the object&#39;s direction of translation (block  520 ) is used to compute the focus of expansion, and angular velocity is then computed from the focus of expansion. More specifically, as can be seen in  FIG. 6 , the direction of translation  610  intersects a sphere surrounding an image capture device  120  at a point known as the focus of expansion  620 . To reduce computation complexity, this sphere is approximated with a cube  630  at the object&#39;s origin, with four of its faces lining up with the image planes  640  of the corresponding image capture devices  120 . Computing device  710  computes the focus of expansion point  620  as the intersection of direction of translation  610  and cube  630 . Computing device  710  projects focus of expansion point  620  onto the side faces of cube  630 , thus providing a local focus of expansion  650  for each image capture device  120 . 
     The angular velocity of image capture device arrangement  110  is computed from local focus of expansion  650  as follows. The translational component of optical flow at point P always lies on the line connecting the (local) focus of expansion  650  and the point P. Therefore the component of optical flow perpendicular to the line connecting focus of expansion  650  and the point P has a projection which includes only the rotational component of optical flow. 
     Computing device  710  uses this projected component of optical flow to produce a linear equation in three unknowns, which correspond to the three rotation terms. This linear equation is produced for each point with optical flow. Computing device  710  combines these equations into a family of linear system equations. Computing device  710  then uses back-substitution to solve the system, thus producing the angular velocity. For cameras shifted from the rig center optical flow also has a component of translation due to the rotation of rig, but when the rotation is small, this rotational component makes a small contribution and therefore can be ignored. 
     Having described various aspects of the tracking system and various aspects of the operation of computing device  710 , further details of the computations involved will now be provided. As noted above, polar correlation can be used to cancel out common components of optical flow. Before further describing polar correlation, the concept of optical flow will be further explained. Given two successive images of a scene, the motion of each pixel in the first image to the second image is defined as a vector [u, v] T  called optical flow, where u and v are velocity components in the x and y direction respectively. 
     Using the instantaneous model of optical flow, for an image capture device C k , the optical flow vector [u, v] T  at point P(x, y) can be written as: 
                       u   k     =           -     t   x   k       +     xt   z   k       Z     +       ω   x   k     ⁢   xy     -       ω   y   k     ⁡     (       x   2     +   1     )       +       ω   z   k     ⁢   y         ,           (   1   )                 v   k     =           -     t   y   k       +     yt   z   k       Z     +       ω   x   k     ⁡     (       y   2     +   1     )       -       ω   z   k     ⁢   xy     -       ω   z   k     ⁢     x   .                 (   2   )               
where t k =[t k   x , t k   y , t k   z ] T  is the translation and ω k =[ω k   x , ω k   y , ω k   z ] T  is the angular velocity of image capture device C k  and Z is the z component (i.e., depth) of the three-dimensional point corresponding to the image point P(x, y).
 
     For an image capture device shifted from the origin:
 
 t   k   =m   k [(ω× s   k )+ T],ω   k   =m   k ω,  (3)
 
where t k  is the translation, ω k  is the angular velocity of image capture device C k  placed at position s k  with orientation m k , and T=[T x , T y , T z ] T  is the translation and ω=[ω x , ω y , ω z ] T  is the angular velocity of the rig.
 
     Substituting values of position and orientation for a particular image capture device (e.g., image capture device  1 ) into equation (3), we get: 
                       t   1     =     [             ω   y     +     T   x                   -     ω   x       +     T   y                 T   z           ]       ,       ω   1     =       [           ω   x               ω   y               ω   z           ]     .               (   4   )               
Substituting equation (4) in equations (1) and (2), we get:
 
                       u   1     =           -     ω   y       -     T   x     +     xT   z       Z     +       ω   x     ⁢   xy     -       ω   y     ⁡     (       x   2     +   1     )       +       ω   z     ⁢   y         ,           (   5   )                 v   1     =           ω   x     -     T   y     +     yT   z       Z     +       ω   x     ⁢     x   ⁡     (       x   2     +   1     )         -       ω   y     ⁢   xy     -       ω   z     ⁢     x   .                 (   6   )               
Equations (5) and (6) represent the optical flow in image capture device  1  in terms of the rig motion parameters T and ω. Similarly equations for image capture device  2 ,  3 , and  4  can also be obtained.
 
     Having described optical flow, the use of polar correlation to cancel out common components of optical flow will now be further explained. Consider four symmetric points of the form Q 0 (x, y), Q 1 (−x, y), Q 2 (−x, −y) and Q 3 (x, −y). Let the optical flow vector at these symmetric points for image capture device C k  be [u k   Qi , v k   Qi ] T  (for i=0 to 3). The equations for flow vectors at these symmetric points in image capture device  1  can be obtained by substituting the coordinates of these points in terms of x and y in equations (5) and (6) for image capture device  1 . The equations for optical flow at point Q 0  in image capture device  1  are: 
                       u     Q   0     1     =           -     ω   y       -     T   x     +     xT   z       Z     +       ω   x     ⁢   xy     -       ω   y     ⁡     (       x   2     +   1     )       +       ω   z     ⁢   y         ,           (   7   )                 v     Q   0     1     =           ω   x     -     T   x     +     xT   z       Z     +       ω   x     ⁡     (       x   2     +   1     )       -       ω   y     ⁢   y     -       ω   z     ⁢     x   .                 (   8   )               
Similarly equations for all the four image capture devices at these four symmetric points Q 0  to Q 3  can be obtained. Next, we compute a quantity [L k   x , L k   y ] for image capture device C k  as:
 
                       L   x   k     =         ∑     i   =   0     3     ⁢     u     Q   i     k       4       ,       L   y   k     =           ∑     i   =   0     3     ⁢     v     Q   i     k       4     .               (   9   )               
Next a quantity [G x , G y , G z ] is computed as:
 
                       G   x     =         -     L   x   1       +     L   x   2       2       ,       G   y     =         -     L   y   1       -     L   y   2     -     L   y   3     -     L   y   4       4       ,       G   z     =           L   x   3     -     L   x   4       2     .               (   10   )               
By substituting equation (9) for all the four image capture devices in equation (10) we get:
 
 G   x   =T   x   /Z,G   y   =T   y   /Z,G   z   =T   z   /Z.   (11)
 
[G x , G y , G z ] is the scaled version of translation T=[T x , T y , T z ] T  of the rig. The computation of [G x , G y , G z ] cancels all the rotation terms and we are left with only translation terms. This technique uses the concept of polar correlation, which holds that opposing image capture devices have common components of optical flow, which can be canceled out as shown above to obtain the direction of translation of the rig.
 
     After computing optical flow in each image capture device, flow vectors from each frame are passed through a quadrantization step to get an estimate of optical flow at symmetric points Q 0 (x, y), Q 1 (−x, y), Q 2 (−x, −y) and Q 3 (x, −y) in preparation for polar correlation. Each frame is divided into four quadrants. The center points of each quadrant are called quadrantization points Q i   k  (for i=0 to 3) for image capture device C k . Each quadrantization point is associated with a vector with some uniform constant magnitude λ and angle as the average of all flow vectors&#39; angles in that quadrant. 
     The angular velocity can be computed as follows. After computing the scaled version of translation of the rig, the translation t k  of each image capture device C k  is obtained using
 
 t   k   =m   k   T,   (12)
 
where m k  is the orientation of image capture device C k  and T is the translation of the rig. Using the translation of each image capture device, a synthetic translational field [u k   t , v k   t ] is generated for each image capture device, as
 
     
       
         
           
             
               
                 
                   
                     
                       u 
                       t 
                       k 
                     
                     = 
                     
                       
                         
                           - 
                           
                             t 
                             x 
                             k 
                           
                         
                         + 
                         
                           x 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             t 
                             z 
                             k 
                           
                         
                       
                       Z 
                     
                   
                   , 
                   
                     
                       v 
                       t 
                       k 
                     
                     = 
                     
                       
                         
                           
                             - 
                             
                               t 
                               y 
                               k 
                             
                           
                           + 
                           
                             yt 
                             z 
                             k 
                           
                         
                         Z 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     A synthetic translational flow vector is generated for all points where the optical flow has been computed. The translational component of optical flow at point P will lie on the line that joins the point P to the focus of expansion (FOE). Therefore, using the synthetic translational flow at each point provides the direction of the line joining the point P and the FOE. When a image capture device C k  is shifted from the rig center, an optical flow vector in that image capture device has three components, vec(o)=vec(o t )+vec(o tr )+vec(o r ), where vec(o t ) is a translational component due to translation of the rig, vec(o tr ) is a translational component due to rotation of the rig, [(ω×s k ) term in equation (3)], and vec(o r ) is a rotational component due to rotation of the rig. The component of optical flow perpendicular to the line connecting the FOE and the point P includes a projection of the translational component vec(o tr ) due to the rotation of the rig, and a projection of the rotational component vec(o r ) due to rotation of rig. (See  FIG. 6 .) Let vec(F) be the vector going from the FOE (x 0 , y 0 ) to a point P(x, y) on the image plane. Then,
 
 {right arrow over (F)} =( x−x   0 ) î +( y−y   0 ) ĵ.   (14)
 
Let vec(F p ) be a vector perpendicular to vec(F), obtained by 90° rotation. Then,
 
 {right arrow over (F)}   p =( y   0   −y ) î +( x−x   0 ) ĵ.   (15)
 
Normalizing the vector vec(F p ) produces
 
                       F   →     pn     =           (       y   0     -   y     )             (       y   0     -   y     )     2     +       (     x   -     x   0       )     2           ⁢     i   ^       +         (     x   -     x   0       )             (       y   0     -   y     )     2     +       (     x   -     x   0       )     2           ⁢       j   ^     .                 (   16   )               
As noted above, the translational component of the optical flow will lie on the line connecting the image point and the FOE. Therefore, vec(o t ) will always lie on the line joining point P and the FOE. Now the component of (vec(o r )+vec(o tr )) perpendicular to vec(F) is obtained, by taking a dot product between (vec(o r )+vec(o tr )) and vec(F pn ). The motive behind normalizing vec(F p ) is that the component of (vec(o r )+vec(o tr )) perpendicular to vec(F) can be found directly by computing a dot product between (vec(o r )+vec(o tr )) and vec(F pn ). Using the computed optical flow over the image frames from the four image capture devices, on selected interest points, the following numerical value is obtained
 
η=( {right arrow over (o)}   r   +{right arrow over (o)}   tr )· {right arrow over (F)}   pn ,  (17)
 
by taking the projection of the flow vector perpendicular to the line connecting the point to the FOE. Extracting the rotational component and translational component due to the rotation of the rig (from equations (5) and (6) for Image capture device  1 ) produces
 
                         o   →     r     =         [         ω   x     ⁢   xy     -       ω   y     ⁡     (       x   2     +   1     )       +       ω   z     ⁢   y       ]     ⁢     i   ^       +       [         ω   x     ⁡     (       y   2     +   1     )       -       ω   y     ⁢   xy     -       ω   z     ⁢   x       ]     ⁢     j   ^           ,           (   18   )                       ⁢         o   →     tr     =           -     ω   y       Z     ⁢     i   ^       +         ω   y     Z     ⁢       j   ^     .                   (   19   )               
Substituting equations (16), (18) and (19) in equation (17) results in an equation of the form:
 
ω x   c   1 +ω y   c   2 +ω z   c   3 =η,  (20)
 
where c 1 , c 2  and c 3  are in terms of x 0 , y 0 , x, y and Z. Similar methods produce equations for image capture devices  2 ,  3  and  4 . Thus each point in an image capture device results in one equation in three unknowns ω x , ω y  and ω z . Choosing a uniform constant value for depth Z and using all the points in all the four image capture devices, a family of equations is obtained having the form:
 
 PX=Q,   (21)
 
where X=[ω x , ω y , ω z ] T , P is a N×3 matrix and Q is a N×1 vector of known quantities, for a total of N interest points. Pre-multiplying both sides of equation (21) by P T  results in
 
 P   T   PX=P   T   Q.   (22)
 
Since P T P is a 3×3 matrix and P T Q is a 3×1 vector, the result is linear equations in three unknowns. Solving this system of equations produces ω x , ω y  and ω z , the angular velocity of the rig.
 
       FIG. 7  is a hardware block diagram of an embodiment of the tracking system described above. Tracking system  700  includes a computing device  710  communicatively coupled to an image capture device arrangement  110 . Computing device  710  includes a processor  720  (e.g., microprocessor, digital signal processor, microcontroller, digital signal controller), memory  730 , and storage device  740 . These components are coupled via a bus  750 . Omitted from  FIG. 7  are a number of conventional components that are unnecessary to explain the operation of tracking system. 
     Computing device  710  communicates with image capture device arrangement  110  to receive a series of images or scenes. Embodiments of tracking system process the received images as explained above in order to track motion of the object through 3D space. In some implementations, computing device  710  communicates with each image capture device  120  individually. In other implementations, computing device  710  communicates with a particular one of the devices  120 , and that device  120  communicates with the others. In still other implementations, computing device  710  communicates with a central unit separate from the devices  120 , and that unit communicates with all the devices  120 . 
     In the embodiment of  FIG. 7 , tracking instructions  760  reside in memory  730  as instructions which, when executed by processor  720 , implement the computations and processes described in connection with  FIGS. 3-6 . In other embodiments (not shown), these functions and processes are implemented in specialized hardware logic, including, but not limited to, a programmable logic device (PLD), a programmable gate array (PGA), a field programmable gate array (FPGA), an application-specific integrated circuit (ASIC), a system on chip (SoC), and a system in package (SiP). Such digital logic implementations are not limited to pure digital but may also include analog sections or components. 
     Tracking instructions  760  can be embodied in any computer-readable medium for use by or in connection with a processor. In the context of this disclosure, a “computer-readable medium” can be any means that can contain or store the instructions for use by the processor. The computer readable medium can be, for example but not limited to, a system or that is based on electronic, magnetic, optical, electromagnetic, or semiconductor technology. 
     Specific examples of a computer-readable medium using electronic technology would include (but are not limited to) the following: random access memory (RAM); read-only memory (ROM); and erasable programmable read-only memory (EPROM or Flash memory). A specific example using magnetic technology includes (but is not limited to) a portable computer diskette. Specific examples using optical technology include (but are not limited to) compact disk (CD) and digital video disk (DVD). 
     The foregoing description has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the disclosure to the precise forms disclosed. Obvious modifications or variations are possible in light of the above teachings. The implementations discussed, however, were chosen and described to illustrate the principles of the disclosure and its practical application to thereby enable one of ordinary skill in the art to utilize the disclosure in various implementations and with various modifications as are suited to the particular use contemplated. All such modifications and variation are within the scope of the disclosure as determined by the appended claims when interpreted in accordance with the breadth to which they are fairly and legally entitled.