Lucas-Kanade tracker
m |
(Added documentation of Ruby source code) |
||
Line 33: | Line 33: | ||
The crucial parts of the implementation (here: 2-d isometric model, three degrees of freedom) are only a few lines of code. An initial parameter vector <code>p</code> (obtained by performing object recognition), an image <code>img</code> and a template <code>tpl</code> are required. In this example we are using a 2-d isometric model with three degrees of freedom (i.e. <code>p</code> has three elements). In | The crucial parts of the implementation (here: 2-d isometric model, three degrees of freedom) are only a few lines of code. An initial parameter vector <code>p</code> (obtained by performing object recognition), an image <code>img</code> and a template <code>tpl</code> are required. In this example we are using a 2-d isometric model with three degrees of freedom (i.e. <code>p</code> has three elements). In | ||
this case the tracking algorithm (inverse compositional Lucas-Kanade) is initialised as follows: | this case the tracking algorithm (inverse compositional Lucas-Kanade) is initialised as follows: | ||
− | + | # three numbers indicating x-, y-position and angle | |
− | + | p = Vector[ xshift, yshift, rotation ] | |
− | + | # retrieve width and height of tracking template | |
+ | w, h = *tpl.shape | ||
+ | # create a 2-D array with x-values and a 2-D array with y-values | ||
+ | x, y = xramp( w, h ), yramp( w, h ) | ||
sigma = 5.0 | sigma = 5.0 | ||
gx = tpl.gauss_gradient_x( sigma ) | gx = tpl.gauss_gradient_x( sigma ) | ||
gy = tpl.gauss_gradient_y( sigma ) | gy = tpl.gauss_gradient_y( sigma ) | ||
− | c = Matrix[ [ 1, 0 ], [ 0, 1 ], [ -y, x ] ] * Vector[ gx, gy ] | + | # compute Jacobian matrix (note that x, y, gx, and gy are 2-D arrays) |
− | hs = ( c * c.covector ).collect { |e| e.sum } | + | c = Matrix[ [ 1, 0 ], [ 0, 1 ], [ -y, x ] ] * Vector[ gx, gy ] |
+ | # compute Hessian matrix | ||
+ | hs = ( c * c.covector ).collect { |e| e.sum } | ||
A tracking step then is done by applying the following piece of code to each image <code>img</code>. Usually the tracking step is performed | A tracking step then is done by applying the following piece of code to each image <code>img</code>. Usually the tracking step is performed | ||
multiple times on each image to improve the tracking estimate. | multiple times on each image to improve the tracking estimate. | ||
− | field = MultiArray.new( MultiArray::SFLOAT, w, h, 2 ) | + | # allocate 3-D array with warp vectors |
− | field[ 0...w, 0...h, 0 ] = x * cos( p[2] ) - y * sin( p[2] ) + p[0] # compute | + | field = MultiArray.new( MultiArray::SFLOAT, w, h, 2 ) |
− | field[ 0...w, 0...h, 1 ] = x * sin( p[2] ) + y * cos( p[2] ) + p[1] # | + | # compute first component of warp vectors |
− | diff = img.warp_clipped_interpolate( field ) - tpl | + | field[ 0...w, 0...h, 0 ] = x * cos( p[2] ) - y * sin( p[2] ) + p[0] |
− | s = c.collect { |e| ( e * diff ).sum } | + | # compute second component of warp vectors |
− | d = hs.inverse * s | + | field[ 0...w, 0...h, 1 ] = x * sin( p[2] ) + y * cos( p[2] ) + p[1] |
− | p += Matrix[ [ cos(p[2]), -sin(p[2]), 0 ], | + | # take difference of warped image and template |
+ | diff = img.warp_clipped_interpolate( field ) - tpl | ||
+ | # multiply with Jacobian (note that some elements of c are 2-D arrays) | ||
+ | s = c.collect { |e| ( e * diff ).sum } | ||
+ | # get estimate for change of pose | ||
+ | d = hs.inverse * s | ||
+ | # update pose vector | ||
+ | p += Matrix[ [ cos(p[2]), -sin(p[2]), 0 ], | ||
[ sin(p[2]), cos(p[2]), 0 ], | [ sin(p[2]), cos(p[2]), 0 ], | ||
[ 0, 0, 1 ] ] * d | [ 0, 0, 1 ] ] * d |
Revision as of 23:29, 15 October 2008
|
The Lucas Kanade tracking algorithm iteratively tries to minimise the difference between the image and a warped template. The technique can be used for image alignment, tracking, optic flow analysis, and motion estimation.
For the documentation of the mathematics have a look at the web-page of the CMU-project "Lucas-Kanade 20 years on" and at the publication by Baker and Matthews.
Implementation
The crucial parts of the implementation (here: 2-d isometric model, three degrees of freedom) are only a few lines of code. An initial parameter vector p
(obtained by performing object recognition), an image img
and a template tpl
are required. In this example we are using a 2-d isometric model with three degrees of freedom (i.e. p
has three elements). In
this case the tracking algorithm (inverse compositional Lucas-Kanade) is initialised as follows:
# three numbers indicating x-, y-position and angle p = Vector[ xshift, yshift, rotation ] # retrieve width and height of tracking template w, h = *tpl.shape # create a 2-D array with x-values and a 2-D array with y-values x, y = xramp( w, h ), yramp( w, h ) sigma = 5.0 gx = tpl.gauss_gradient_x( sigma ) gy = tpl.gauss_gradient_y( sigma ) # compute Jacobian matrix (note that x, y, gx, and gy are 2-D arrays) c = Matrix[ [ 1, 0 ], [ 0, 1 ], [ -y, x ] ] * Vector[ gx, gy ] # compute Hessian matrix hs = ( c * c.covector ).collect { |e| e.sum }
A tracking step then is done by applying the following piece of code to each image img
. Usually the tracking step is performed
multiple times on each image to improve the tracking estimate.
# allocate 3-D array with warp vectors field = MultiArray.new( MultiArray::SFLOAT, w, h, 2 ) # compute first component of warp vectors field[ 0...w, 0...h, 0 ] = x * cos( p[2] ) - y * sin( p[2] ) + p[0] # compute second component of warp vectors field[ 0...w, 0...h, 1 ] = x * sin( p[2] ) + y * cos( p[2] ) + p[1] # take difference of warped image and template diff = img.warp_clipped_interpolate( field ) - tpl # multiply with Jacobian (note that some elements of c are 2-D arrays) s = c.collect { |e| ( e * diff ).sum } # get estimate for change of pose d = hs.inverse * s # update pose vector p += Matrix[ [ cos(p[2]), -sin(p[2]), 0 ], [ sin(p[2]), cos(p[2]), 0 ], [ 0, 0, 1 ] ] * d
A full implementation is available as an example application with HornetsEye. The implementation does interpolation which is very important for the stability of the Lucas-Kanade tracker. Furthermore the gradient is computed using the surroundings of the initial template to avoid boundary effects. You can find a listing of the source code here.
See Also
External Links
- Hornetseye implementation
- J. Wedekind, B. P. Amavasai, K. Dutton, M. Boissenin: A Machine Vision Extension for the Ruby Programming Language (also see foils (PDF))
- CMU project: "Lucas-Kanade 20 years on"
- S. Baker, I. Matthews: Lucas-Kanade 20 Years On: A Unifying Framework, International Journal of Computer Vision, Vol. 56, No. 3, March, 2004, pp. 221-255.
- NASA high definition videos