Detecting corners using structure tensor matrix

Question

How does eigenvalues of structure tensor matrix help in detecting corners?

For eg, in Harris corner detection, we consider the matrix

$$M = \sum_{w} w \cdot \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} $$

We say that if both eigenvalues are high, then it is a corner. If one of them is high, then it is an edge. If both are low, then it is neither corner nor edge. How do we come to this conclusion?

Answer 1

I'll simply present a series of results relevant to this question.

1. Note that eigenvalues of this matrix are non-negative

Let $x = [u\ v]^T$
$$x^TMx = [u\ v] \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} = u^2 I_x^2 + 2uv I_x I_y + v^2 I_y^2 = (uI_x + vI_y)^2 \geq 0$$
Hence $M$ is positive-semidefinite and hence eigenvalues are always non-negative.

2. Eigen vector of the matrix corresponding to largest eigen-value gives the direction of maximum change

Consider a symetric matrix $A$. We want the direction of maximum change
i.e. $$\max_{x} \frac{\Vert Ax \Vert}{\Vert x \Vert}$$ Maximizing the above is equivalent to maximizing $\Vert Ax \Vert$ by fixing $\Vert x \Vert = 1$. Also maximizing $\Vert Ax \Vert$ is equivalent to maximizing $\Vert Ax \Vert^2$ $$ \max_x \Vert Ax \Vert^2 \quad s.t. \quad \Vert x \Vert = 1 $$ Lagrangian gives $$ \max_x \quad x^TA^TAx + \lambda (1 - x^Tx) $$ Differentiate w.r.t. $x$ and equate to $0$ $$ 2A^TAx - \lambda x = 0 $$ $$ A^TAx = \lambda x $$ Hence $$ \Vert Ax \Vert^2 = \lambda \Vert x \Vert^2 = \lambda$$ To maximize this quantity, choose $\lambda$ as the largest eigenvalue and hence $x$ is the eigenvector corresponding to this eigenvalue. Since $A$ is symmetric $A^TA = A^2$ and hence eigenvalues of $A$ are sqrt of eigenvalues of $A^TA$ and eigenvectors remain same.

3. Eigenvectors of $M$ are orthogonal
   Since $M$ is symmetric, it's eigenvectors are orthogonal. See here. We found that the eigenvector that corresponds to largest eigenvalue is in the direction of maximum change. Hence the second eigenvector will be in the perpendicular direction to this eigenvector.

4. Eigenvalues in smooth region
   In smooth region, $I_x=I_y=0$ and hence eigenvalues are $0$

5. Eigenvalues at edges
   Let's say the edge is oriented at an angle of $\theta$. Hence $$I_x=c \ \sin(\theta);\quad I_y=c \ \cos(\theta)$$ $$ M = c^2 \begin{bmatrix} \sin^2(\theta) & \sin(\theta)\ \cos(\theta) \\ \sin(\theta)\ \cos(\theta) & \cos^2(\theta) \end{bmatrix} $$ Eigenvalues are given by $$ (\sin^2(\theta) - \lambda)(\cos^2(\theta) - \lambda) - \sin^2(\theta)\cos^2(\theta) = 0 $$ $$ \lambda^2 - 2\lambda + \sin^2(\theta)\cos^2(\theta) - \sin^2(\theta)\cos^2(\theta) = 0 $$ $$ \lambda^2 - 2\lambda = 0 $$ $$ \lambda = 0, 2 $$ Hence at an edge, one eigenvalue is $0$ and the other isn't.

6. Eigenvectors at edges
   Consider a vertical edge. Hence $$I_x=c;\quad I_y=0 $$ $$ M = \begin{bmatrix} c^2 & 0 \\ 0 & 0 \end{bmatrix} $$ Eigen vector corresponding to largest eigenvalue is $v = [1\ 0]^T$ i.e. gives the normal to the edge.

Also note that, for the eigenvector in the direction where there is change in pixel intensity, eigenvalue is high. For the eigenvector in the direction where there is no change in intensity, eigenvalue is low. So, eigenvalues represent the amount of change in pixel intensity observed along the direction of it's corresponding eigenvector.

7. Eigenvalues and eigenvectors at a corner
   Let's consider a corner where a vertical edge crosses a horizontal edge. The first eigen vector gives normal to the stronger edge. The second eigenvector, which is perpendicular to the first gives normal to the other edge. Since the change is high along both directions, the eigenvalues corresponding to both the eigenvectors will be large.

Thus, to summarize

• In smooth regions, eigenvalues are close to 0.
• At edges, one eigenvalue is large and the other is close to 0.
• At corners, both eigenvalues are large.

In other words,

• if both eigenvalues are small, there is little change in intensities along any direction => smooth region
• if one eigenvalue is large and the other is small, there is change in intensities along one direction => edge
• if both eigenvalues are high, then there is change in intensities along 2 perpendicular directions => corner

References:
https://stackoverflow.com/a/23172317/3337089

TODO:

1. Add proof showing positive definite matrices have positive eigenvalues
2. Add details about the curve trace - $\alpha$ * determinant