Corner Detection - The Harris & Stephens / Plessey / Shi-Tomasi Corner Detection Algorithm

The Harris & Stephens / Plessey / Shi-Tomasi Corner Detection Algorithm

Harris and Stephens improved upon Moravec's corner detector by considering the differential of the corner score with respect to direction directly, instead of using shifted patches. (This corner score is often referred to as autocorrelation, since the term is used in the paper in which this detector is described. However, the mathematics in the paper clearly indicate that the sum of squared differences is used.)

Without loss of generality, we will assume a grayscale 2-dimensional image is used. Let this image be given by . Consider taking an image patch over the area and shifting it by . The weighted sum of squared differences (SSD) between these two patches, denoted, is given by:

S(x,y) = \sum_u \sum_v w(u,v) \, \left( I(u+x,v+y) - I(u,v)\right)^2

can be approximated by a Taylor expansion. Let and be the partial derivatives of, such that

I(u+x,v+y) \approx I(u,v) + I_x(u,v)x+I_y(u,v)y

This produces the approximation

S(x,y) \approx \sum_u \sum_v w(u,v) \, \left( I_x(u,v)x + I_y(u,v)y \right)^2,

which can be written in matrix form:

S(x,y) \approx \begin{pmatrix} x & y \end{pmatrix} A \begin{pmatrix} x \\ y \end{pmatrix},

where A is the structure tensor,

A = \sum_u \sum_v w(u,v) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} = \begin{bmatrix} \langle I_x^2 \rangle & \langle I_x I_y \rangle\\ \langle I_x I_y \rangle & \langle I_y^2 \rangle \end{bmatrix}

This matrix is a Harris matrix, and angle brackets denote averaging (i.e. summation over ). If a circular window (or circularly weighted window, such as a Gaussian) is used, then the response will be isotropic.

A corner (or in general an interest point) is characterized by a large variation of in all directions of the vector . By analyzing the eigenvalues of, this characterization can be expressed in the following way: should have two "large" eigenvalues for an interest point. Based on the magnitudes of the eigenvalues, the following inferences can be made based on this argument:

  1. If and then this pixel has no features of interest.
  2. If and has some large positive value, then an edge is found.
  3. If and have large positive values, then a corner is found.

Harris and Stephens note that exact computation of the eigenvalues is computationally expensive, since it requires the computation of a square root, and instead suggest the following function, where is a tunable sensitivity parameter:

M_c = \lambda_1 \lambda_2 - \kappa \, (\lambda_1 + \lambda_2)^2 = \operatorname{det}(A) - \kappa \, \operatorname{trace}^2(A)

Therefore, the algorithm does not have to actually compute the eigenvalue decomposition of the matrix and instead it is sufficient to evaluate the determinant and trace of to find corners, or rather interest points in general.

The Shi-Tomasi corner detector directly computes because under certain assumptions, the corners are more stable for tracking. Note that this method is also sometimes referred to as the Kanade-Tomasi corner detector.

The value of has to be determined empirically, and in the literature values in the range 0.04 - 0.15 have been reported as feasible.
One can avoid setting the parameter by using Noble's corner measure which amounts to the harmonic mean of the eigenvalues:

M_c' = 2 \frac{\operatorname{det}(A)}{\operatorname{trace}(A) + \epsilon},

being a small positive constant.

The covariance matrix for the corner position is, i.e.

\frac{1}{\langle I_x^2 \rangle \langle I_y^2 \rangle - \langle I_x I_y \rangle^2} \begin{bmatrix} \langle I_y^2 \rangle & -\langle I_x I_y \rangle\\ -\langle I_x I_y \rangle & \langle I_x^2 \rangle \end{bmatrix}.

Read more about this topic:  Corner Detection

Famous quotes containing the words harris, stephens and/or corner:

    “Mr. Brownlow: The law supposes that your wife acts under your direction.
    Bumble: If that’s what the law supposes, sir, then the law’s an ass. And if that’s the eye of the law, sir, then the law’s a bachelor.”
    —Vernon Harris (c. 1910)

    “Crouching down where nothing stirs
    In the silence of the furze,
    Crouching down again to brood
    In the sunny solitude.”
    —James Kenneth Stephens (1882–1950)

    “I have no desire for riches. Honest poverty and a conscience torpid through virtuous inaction are more to me than corner lots and praise.”
    —Mark Twain [Samuel Langhorne Clemens] (1835–1910)