Computer Vision MT25, Lucas-Kanade tracking
Flashcards
@State the general problem that Lucas-Kanade tracking tries to solve, and give examples of what each might be in the problem of trying to identify Pac-Man on a game screen.
We have:
- An image $I$ (the game screen)
- A template $T$, which we wish to locate within the image (a small patch of Pac-Man)
- A guess of the current location of the template within the image, given by $W(\pmb x, \pmb p)$, where:
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
We want:
- Some update $\Delta \pmb p$ such that $ \vert \vert I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x) \vert \vert _ 2$ is minimised over all $\pmb x$ (i.e. an improvement to our guess of where Pac-Man is inside the image)
In Lucas-Kanade tracking, we have:
- An image $I$ (e.g. a game screen)
- A template $T$, which we wish to locate within the image (e.g. a small patch of Pac-Man)
- A guess of the current location of the template within the image, given by $W(\pmb x, \pmb p)$, where:
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
and we want:
- Some update $\Delta \pmb p$ such that $ \vert \vert I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x) \vert \vert _ 2$ is minimised over all $\pmb x$ (e.g. an improvement to our guess of where Pac-Man is inside the image)
What does the loss/energy function $E$ look like in terms of $\Delta \pmb p$, and how does Lucas-Kanade tracking approximate this?
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
In general, we have:
\[E(\Delta \pmb p) = \sum _ {x \in T} (I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x))^2\]Lucas-Kanade tracking approximates this via a first-order Taylor expansion as:
\[E(\Delta \pmb p) \approx \sum _ {x \in T} \left(I(W(\pmb x, \pmb p)) + \nabla I^\top \frac{\partial W}{\partial \pmb p} \Delta \pmb p - T(x)\right)^2\]In Lucas-Kanade tracking, we have:
- An image $I$ (e.g. a game screen)
- A template $T$, which we wish to locate within the image (e.g. a small patch of Pac-Man)
- A guess of the current location of the template within the image, given by $W(\pmb x, \pmb p)$, where:
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
and we want:
- Some update $\Delta \pmb p$ such that $ \vert \vert I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x) \vert \vert _ 2$ is minimised over all $\pmb x$ (e.g. an improvement to our guess of where Pac-Man is inside the image)
In general, we aim to minimise the energy function
\[E(\Delta \pmb p) = \sum _ {x \in T} (I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x))^2\]
Lucas-Kanade tracking approximates this via a first-order Taylor expansion as
\[E(\Delta \pmb p) \approx \sum _ {x \in T} \left(I(W(\pmb x, \pmb p)) + \nabla I^\top \frac{\partial W}{\partial \pmb p} \Delta \pmb p - T(x)\right)^2\]
@State the update that this leads to.
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
\[\Delta \pmb p = \pmb M^{-1} \pmb b\]
where
\[\begin{aligned} \pmb M &= \sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right)^\top \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right) \\ \pmb b &= \sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right)^\top (T(\pmb x) - I(W(\pmb x, \pmb p)) \end{aligned}\]In Lucas-Kanade tracking, we have:
- An image $I$ (e.g. a game screen)
- A template $T$, which we wish to locate within the image (e.g. a small patch of Pac-Man)
- A guess of the current location of the template within the image, given by $W(\pmb x, \pmb p)$, where:
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
and we want:
- Some update $\Delta \pmb p$ such that $ \vert \vert I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x) \vert \vert _ 2$ is minimised over all $\pmb x$ (e.g. an improvement to our guess of where Pac-Man is inside the image)
In general, we aim to minimise the energy function
\[E(\Delta \pmb p) = \sum _ {x \in T} (I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x))^2\]
Lucas-Kanade tracking approximates this via a first-order Taylor expansion as
\[E(\Delta \pmb p) \approx \sum _ {x \in T} \left(I(W(\pmb x, \pmb p)) + \nabla I^\top \frac{\partial W}{\partial \pmb p} \Delta \pmb p - T(x)\right)^2\]
@Prove that this leads to the update
\[\Delta \pmb p = \pmb M^{-1} \pmb b\]
where
\[\begin{aligned}
\pmb M &= \sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right)^\top \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right) \\
\pmb b &= \sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right)^\top (T(\pmb x) - I(W(\pmb x, \pmb p))
\end{aligned}\]
- $\pmb x$ is an arbitrary point in the template
- $W$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
- (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)
Taking the partial derivative of $E(\Delta \pmb p)$ with respect to $\Delta \pmb p$, we have
\[\frac{\partial E(\Delta \pmb p)}{\partial \Delta \pmb p} = 2\sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} (I(W(\pmb x, \pmb p)) + \nabla I^\top \frac{\partial W}{\partial \pmb p} \Delta \pmb p) - T(\pmb x) \right)\]Setting this to zero gives
\[\sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right)^\top \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right) \Delta \pmb p = \sum _ {\pmb x \in T} \left( \nabla I^\top \frac{\partial W}{\partial \pmb p} \right)^\top (T(\pmb x) - I(W(\pmb x, \pmb p)))\]