Types of Image Feature:

  • Edges
  • Corners (also known as interest points)
  • Blobs (also known as regions of interest )

Image Corners/Keypoints

Keypoints Structure (from OpenCV):

  • pt: x & y coordinates of the keypoint
  • size: keypoint diameter
  • angle: keypoint orientation
  • response: keypoint detector response on the keypoint (that is, strength of the keypoint)
  • octave: pyramid octave in which the keypoint has been detected
  • class_id: object id

feature detector + feature descriptor


Define the auto-correlation surface or SSD surface or the weighted sum of squared differences:

\[\begin{aligned} E_{AC}(\Delta \mathbf{u}) &= \sum_{i} \omega(\mathbf{x}_i) [ \mathbf{I}_0 ( \mathbf{x}_i + \Delta \mathbf{u} ) - \mathbf{I}_0 (\mathbf{x}_i) ]^2 \\ &\approx \sum_{i} \omega(\mathbf{x}_i) [ \mathbf{I}_0(\mathbf{x}_i) + \nabla \mathbf{I}_0(\mathbf{x}_i) \cdot \Delta\mathbf{u} - \mathbf{I}_0(\mathbf{x}_i) ]^2 \\ &= \sum_{i} \omega(\mathbf{x}_i) [ \nabla \mathbf{I}_0(\mathbf{x}_i) \cdot \Delta\mathbf{u} ]^2 \\ &= \Delta\mathbf{u}^T \cdot \mathbf{M} \cdot \Delta\mathbf{u} \end{aligned}\]


\[\nabla \mathbf{I}_0(\mathbf{x}_i) = ( \frac{\partial{\mathbf{I}_0}}{\partial{x}}, \frac{\partial{\mathbf{I}_0}}{\partial{y}} ) (\mathbf{x}_i)\]

written by simply the gradient

\[\nabla \mathbf{I} = [\mathbf{I}_x, \mathbf{I}_y]\]

and the auto-correlation matrix with the weighting kernel $\omega$

\[\mathbf{M} = \omega * \begin{bmatrix} \mathbf{I}_x^2 & \mathbf{I}_x\mathbf{I}_y \\ \mathbf{I}_x\mathbf{I}_y & \mathbf{I}_y^2 \end{bmatrix}\]

then create a score equation, which will determine if a window can contain a corner or not

\[R = det(\mathbf{M}) - k (trace(\mathbf{M}))^2\]


\[det(\mathbf{M}) = \lambda_1 \lambda_2\] \[trace(\mathbf{M}) = \lambda_1 + \lambda_2\]

and, $\lambda_1$ and $\lambda_2$ are the eigen values of $\mathbf{M}$, we can compute it by

\[det(\lambda E - M) = 0\]

So the values of these eigen values decide whether a region is corner, edge or flat

  • When $ |R| $ is small, which happens when $\lambda_1$ and $\lambda_2$ are small, the region is flat.
  • When $R<0$, which happens when $\lambda_1 » \lambda_2$ or vice versa, the region is edge.
  • When $R$ is large, which happens when $\lambda_1$ and $\lambda_2$ are large and $\lambda_1 \sim \lambda_2$, the region is a corner.


  • cv::goodFeaturesToTrack

The Shi-Tomasi corner detector is based entirely on the Harris corner detector. However, one slight variation in a “selection criteria” made this detector much better than the original. It works quite well where even the Harris corner detector fails.

Later in 1994, J. Shi and C. Tomasi made a small modification to it in their paper Good Features to Track which shows better results compared to Harris Corner Detector.

The scoring function in Harris Corner Detector was given by (Harris corner strength):

\[\mathbf{R} = \lambda_1 \lambda_2 - k(\lambda_1 + \lambda_2)^2\]

Instead of this, Shi-Tomasi proposed (get the minimum eigenvalue):


If $R$ is greater than a certain predefined value, it can be marked as a corner


FAST (Features from Accelerated Segment Test) algorithm was proposed by Edward Rosten and Tom Drummond in their paper “Machine learning for high-speed corner detection” in 2006 (Later revised it in 2010).

Feature Detection

检测 局部像素灰度 变化明显的地方。

  • 在图像中选取像素p,假设它的亮度为 $I_p$;
  • 设置一个阈值 $T$;
  • 以像素 $p$ 为中心,选取半径为3的 Bresenham圆 上的16个像素;
  • 假设选取的圆上有连续的N个点的亮度大于 $I_p+T$ 或 $I_p-T$,则该点 $p$ 可被认为是特征点(N通常取12,即为 FAST-12,其他常用的N取值有9和11,分别被成为 FAST-9FAST-11);
  • 循环以上四步;

Non-maximal Suppression

FAST角点经常出现“扎堆”的情况,通过 非极大值抑制,在一定区域内仅保留响应极大值的角点,避免角点集中的问题。


in 2004, D.Lowe, University of British Columbia, came up with a new algorithm, Scale Invariant Feature Transform (SIFT) in his paper, Distinctive Image Features from Scale-Invariant Keypoints, which extract keypoints and compute its descriptors.



In 2006, three people, Bay, H., Tuytelaars, T. and Van Gool, L, published another paper, “SURF: Speeded Up Robust Features” which introduced a new algorithm called SURF. As name suggests, it is a speeded-up version of SIFT.



BRIEF Descriptor

  • BRIEF: Binary Robust Independent Elementary Features





As an OpenCV enthusiast, the most important thing about the ORB(Oriented FAST and Rotated BRIEF) is that it came from “OpenCV Labs”. This algorithm was brought up by Ethan Rublee, Vincent Rabaud, Kurt Konolige and Gary R. Bradski in their paper ORB: An efficient alternative to SIFT or SURF in 2011. As the title says, it is a good alternative to SIFT and SURF in computation cost, matching performance and mainly the patents. Yes, SIFT and SURF are patented and you are supposed to pay them for its use. But ORB is not !!!

ORB is basically a fusion of FAST keypoint detector and BRIEF descriptor with many modifications to enhance the performance.

oriented FAST

  • use FAST to find keypoints, then apply Harris corner measure to find top N points among them

  • multiscale
    • use pyramid to produce multiscale-features
  • rotation invariance (Orientation): It computes the intensity weighted centroid of the patch with located corner at center. The direction of the vector from this corner point to centroid gives the orientation. To improve the rotation invariance, moments are computed with x and y which should be in a circular region of radius r, where r is the size of the patch. 旋转部分计算如下:

    • 在一个小的图像块 B 中,定义 图像块的一阶矩 为: \(M_{pq} = \sum_{x,y \in B} x^p y^q I(x,y), \quad p,q \in \{ 0,1\}\)

    • 通过矩找到图像块的质心: \(C = \bigg( \frac{M_{10}}{M_{00}}, \frac{M_{01}}{M_{00}} \bigg)\)

    • 几何中心 $O$ 与 质心 $C$ 连接得到 方向向量$\vec{OC}$,于是特征点的方向定义为: \(\theta = arctan( \frac{M_{01}}{M_{10}} )\)

rotated BRIEF

  • Binary Robust Independent Elementary Features


  • Fast Retina KeyPoint


SubPixel Corners

  • Subpixel Corners: Increasing accuracy
  • Use the OpenCV function cornerSubPix to find more exact corner positions (more exact than integer pixels)

在 亚像素角点 $\mathbf{q}$ 的求解中,“垂直向量,乘积为0”

\[<\nabla \mathbf{I}(\mathbf{p}_i), \mathbf{q} - \mathbf{p}_i> = 0\]


use pyramid to produce multiscale-features

  • 均值金字塔:2*2邻域均值滤波
  • 高斯金字塔:向下降采样图像(4层),高斯核5*5
  • 拉普拉斯金字塔

Image Edges


  • 正交表示
  • 普吕克坐标表示

Image Blobs