# Harris Corner Detection The algoritm first computes the auto-correlation atix of an image $I$. Let $x$ and $y$ denote the coordinates of a pixel in an image, and let $u$ and $v$ represent the dispalcement in $x$ and $y$ directions respectively. The auto-correlation function $E(u,v)$ for each pixel at $(x,y)$ is defined as follows: ![[HarrisDetector.jpg]] where $w(x,y)$ is a weighting function based on a neighborhood about (x,y). The auto-correlation function is approximated by it's second order [[Taylor Expansion]] centered around $u=0,v=0$: $ E(u, v) \simeq E(0,0)+\left[\begin{array}{ll} u & v \end{array}\right]\left[\begin{array}{l} E_{u}(0,0) \\ E_{v}(0,0) \end{array}\right]+\frac{1}{2}\left[\begin{array}{ll} u & v \end{array}\right]\left[\begin{array}{ll} E_{u u}(0,0) & E_{u v}(0,0) \\ E_{v u}(0,0) & E_{v v}(0,0) \end{array}\right]\left[\begin{array}{l} u \\ v \end{array}\right] $ where $E_u,E_v$ denotes the first-order partial derivatives, and $E_{u u}, E_{u v}, E_{v u}, E_{v v}$ denote the second-order partial derivatives. We have, $E(0,0)=E_{u}(0,0) = E_{v}(0,0)=0$, so we can simplify as: $ \begin{aligned} E(u, v) & \simeq \frac{1}{2}\left[\begin{array}{ll} u & v \end{array}\right]\left[\begin{array}{ll} E_{u u}(0,0) & E_{u v}(0,0) \\ E_{v u}(0,0) & E_{v v}(0,0) \end{array}\right]\left[\begin{array}{l} u \\ v \end{array}\right] \\ & \simeq \frac{1}{2}\left[\begin{array}{ll} u & v \end{array}\right] \underbrace{\left[\begin{array}{cc} \sum_{x, y} 2 w(x, y) I_{x}^{2}(x, y) & \sum_{x, y} 2 w(x, y) I_{x}(x, y) I_{y}(x, y) \\ \sum_{x, y} 2 w(x, y) I_{x}(x, y) I_{y}(x, y) & \sum_{x, y} 2 w(x, y) I_{y}^{2}(x, y) \end{array}\right]}_{Q}\left[\begin{array}{l} u \\ v \end{array}\right] \end{aligned} $ Here, $Q=\sum_{x, y} w(x, y) \nabla I \nabla I^{T} = \sum w(x, y)\left[\begin{array}{ll} I_{x}^{2} & I_{x} I_{y} \\ I_{x} I_{y} & I_{y}^{2} \end{array}\right]$ is known as the second moment matrix. For $Q$ to be full rank it is necessary it is necessary to have non-zero gradients in both x and y dimensions inside the neighborhood. Under this condition, two positive non-zero eigenvalues $\lambda_1$ and $\lambda_2$ can be found for $Q$, and thus the pixel at $x,y$ is a corner candidate. The quality of each candidate depends on the magnitudes of both eigenvalues. If either eigenvalue is small while the other is large, the candidate is more likely to be an edge than corner. If both are large, then it's likely to be a corner. ![[HarrisEigen.jpg]] The algorithm proposes a cornerness $H(x,y)$ defined by two eigen values of $Q(x,y)$ $ \begin{aligned} H &=\lambda_{1} \lambda_{2}-k\left(\lambda_{1}+\lambda_{2}\right)^{2} \\ &=\operatorname{det}(Q)-k(\operatorname{trace}(Q))^{2} \\ &=\left(A C-B^{2}\right)-k(A+C)^{2} \end{aligned} $ The threshold value $k$ can be obtained using a heuristic (empiracally 0.04-0.06 is used) $ \frac{c}{|X||Y|} \sum_{x \in X} \sum_{y \in Y} Q(x, y) $ where $c$ is sensitivity parameter. HCD further filters the candidates using non-maximal supression to obtain the best candidate within each block of size $n\times n$ within the image. ## Shi and Tomasi Variation Shi and Tomasi propose an alternate definition of the cornerness function $H(x,y)$ given by $\min\{\lambda_1,\lambda_2\}$ where $\lambda_{1}, \lambda_{2}$ are the eigenvalues of the second moment matrix $Q$. We claim that the min function can be written as $ \min \{\alpha, \beta\}=\frac{(\alpha+\beta)-\sqrt{(\alpha-\beta)^{2}}}{2} $ Assume $\lambda_{1}=\lambda_{2}+r$ for some $r \geq 0$. We can see the above claim is valid as $ \min \left\{\lambda_{1}, \lambda_{2}\right\}=\frac{\left(\lambda_{1}+\lambda_{2}\right)-\sqrt{\left(\lambda_{1}-\lambda_{2}\right)^{2}}}{2}=\frac{\left(\lambda_{2}+r+\lambda_{2}\right)-\sqrt{\left(\lambda_{2}+r-\lambda_{2}\right)^{2}}}{2}=\lambda_{2} $ Expressing in the minimum function, we have, $ \begin{aligned} \min \left\{\lambda_{1}, \lambda_{2}\right\} &=\frac{\left(\lambda_{1}+\lambda_{2}\right)-\sqrt{\left(\lambda_{1}-\lambda_{2}\right)^{2}}}{2} \\ &=\frac{\left(\lambda_{1}+\lambda_{2}\right)-\sqrt{\lambda_{1}^{2}-2 \lambda_{1} \lambda_{2}+\lambda_{2}^{2}}}{2}\\ &=\frac{\left(\lambda_{1}+\lambda_{2}\right)-\sqrt{\left(\lambda_{1}+\lambda_{2}\right)^{2}-4 \lambda_{1} \lambda_{2}}}{2} \\ \end{aligned} $ Now we know, $ \begin{array}{c} \operatorname{Tr}(Q)=A+C=\lambda_{1}+\lambda_{2} \\ |Q|=A C-B^{2}=\lambda_{1} \lambda_{2} \end{array} $ Substituting in the minimum function expression above, $ \begin{align} \min \left\{\lambda_{1}, \lambda_{2}\right\} &=\frac{(A+C)-\sqrt{(A+C)^{2}-4\left(A C-B^{2}\right)}}{2} \\ &=\frac{(A+C)-\sqrt{A^{2}+2 A C+C^{2}-4 A C+4 B^{2}}}{2} \\ &=\frac{(A+C)-\sqrt{(A-C)^{2}+4 B^{2}}}{2} \end{align} $ Thus we can calculate the cornerness without performing eigenvalue decomposition. Shi and Tomasi define the cornerness function as $\min\{\lambda_1,\lambda_2\}$, therefore the cornerness value is low if at least one of the eigen values is smaller than $\lambda_{min}$. ![[shi-tomasi-region1.jpg]] Blue and gray areas are equivalent to "edge" areas. Red region represents "flat" areas, and green represents the corners. ## Properties of Harris Corner Detection 1. Translation Invariance: It is translation invariant, as the eigenvalues of translated corner remain the same. 2. Rotation Invariance: It is rotatio invariant. Direction of eigenvectos change but the eigenvalues remain the same. 3. Scale Invariance: Not invariant to scaling as the points become edges when scaled up. ## References: 1. http://dept.me.umn.edu/courses/me5286/vision/Notes/2015/ME5286-Lecture8.pdf 2. https://courses.cs.washington.edu/courses/cse576/06sp/notes/HarrisDetector.pdf ---