Skip to Content
CSE559AComputer Vision (Lecture 17)

CSE559A Lecture 17

Local Features

Types of local features

Edge

Goal: Identify sudden changes in image intensity

Generate edge map as human artists.

An edge is a place of rapid change in the image intensity function.

Take the absolute value of the first derivative of the image intensity function.

For 2d functions, ∂f∂x=lim⁡Δx→0f(x+Δx)−f(x)Δx\frac{\partial f}{\partial x}=\lim_{\Delta x\to 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}

For discrete images data, ∂f∂x≈f(x+1)−f(x)1\frac{\partial f}{\partial x}\approx \frac{f(x+1)-f(x)}{1}

Run convolution with kernel [1,0,−1][1,0,-1] to get the first derivative in the x direction, without shifting. (generic kernel is [1,−1][1,-1])

Prewitt operator:

Mx=[10−110−110−1]My=[111000−1−1−1]M_x=\begin{bmatrix} 1 & 0 & -1 \\ 1 & 0 & -1 \\ 1 & 0 & -1 \\ \end{bmatrix} \quad M_y=\begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ -1 & -1 & -1 \\ \end{bmatrix}

Sobel operator:

Mx=[10−120−210−1]My=[121000−1−2−1]M_x=\begin{bmatrix} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1 \\ \end{bmatrix} \quad M_y=\begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \\ \end{bmatrix}

Roberts operator:

Mx=[100−1]My=[01−10]M_x=\begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} \quad M_y=\begin{bmatrix} 0 & 1 \\ -1 & 0 \\ \end{bmatrix}

Image gradient:

∇f=(∂f∂x,∂f∂y)\nabla f = \left(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\right)

Gradient magnitude:

∣∣∇f∣∣=(∂f∂x)2+(∂f∂y)2||\nabla f|| = \sqrt{\left(\frac{\partial f}{\partial x}\right)^2 + \left(\frac{\partial f}{\partial y}\right)^2}

Gradient direction:

θ=tan⁡−1(∂f∂y∂f∂x)\theta = \tan^{-1}\left(\frac{\frac{\partial f}{\partial y}}{\frac{\partial f}{\partial x}}\right)

The gradient points in the direction of the most rapid increase in intensity.

Application: Gradient-domain image editing

Goal: solve for pixel values in the target region to match gradients of the source region while keeping the rest of the image unchanged.

Poisson Image Editing 

Noisy edge detection:

When the intensity function is very noisy, we can use a Gaussian smoothing filter to reduce the noise before taking the gradient.

Suppose pixels of the true image fi,jf_{i,j} are corrupted by Gaussian noise ni,jn_{i,j} with mean 0 and variance σ2\sigma^2. Then the noisy image is gi,j=(fi,j+ni,j)−(fi,j+1+ni,j+1)≈N(0,2σ2)g_{i,j}=(f_{i,j}+n_{i,j})-(f_{i,j+1}+n_{i,j+1})\approx N(0,2\sigma^2)

To find edges, look for peaks in ddx(f∘g)\frac{d}{dx}(f\circ g) where gg is the Gaussian smoothing filter.

or we can directly use the Derivative of Gaussian (DoG) filter:

ddxg(x,σ)=12πσ2e−x22σ2\frac{d}{dx}g(x,\sigma)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{x^2}{2\sigma^2}}
Separability of Gaussian filter

A Gaussian filter is separable if it can be written as a product of two 1D filters.

ddxg(x,σ)=12πσ2e−x22σ2ddyg(y,σ)=12πσ2e−y22σ2\frac{d}{dx}g(x,\sigma)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{x^2}{2\sigma^2}} \quad \frac{d}{dy}g(y,\sigma)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{y^2}{2\sigma^2}}
Separable Derivative of Gaussian (DoG) filter
ddxg(x,y)∝−xexp⁡(−x2+y22σ2)ddyg(x,y)∝−yexp⁡(−x2+y22σ2)\frac{d}{dx}g(x,y)\propto -x\exp\left(-\frac{x^2+y^2}{2\sigma^2}\right) \quad \frac{d}{dy}g(x,y)\propto -y\exp\left(-\frac{x^2+y^2}{2\sigma^2}\right)
Derivative of Gaussian: Scale

Using Gaussian derivatives with different values of 𝜎 finds structures at different scales or frequencies

(Take the hybrid image as an example)

Canny edge detector
  1. Smooth the image with a Gaussian filter
  2. Compute the gradient magnitude and direction of the smoothed image
  3. Thresholding gradient magnitude
  4. Non-maxima suppression
    • For each location q above the threshold, check that the gradient magnitude is higher than at adjacent points p and r in the direction of the gradient
  5. Thresholding the non-maxima suppressed gradient magnitude
  6. Hysteresis thresholding
    • Use two thresholds: high and low
    • Start with a seed edge pixel with a gradient magnitude greater than the high threshold
    • Follow the gradient direction to find all connected pixels with a gradient magnitude greater than the low threshold
Top-down segmentation

Data-driven top-down segmentation:

Interest point

Key point matching:

  1. Find a set of distinctive keypoints in the image
  2. Define a region of interest around each keypoint
  3. Compute a local descriptor from the normalized region
  4. Match local descriptors between images

Characteristic of good features:

  • Repeatability
    • The same feature can be found in several images despite geometric and photometric transformations
  • Saliency
    • Each feature is distinctive
  • Compactness and efficiency
    • Many fewer features than image pixels
  • Locality
    • A feature occupies a relatively small area of the image; robust to clutter and occlusion
Harris corner detector

Applications of local features

Image alignment

3D reconstruction

Motion tracking

Robot navigation

Indexing and database retrieval

Object recognition

Last updated on
Computer Vision (Lecture 16)Computer Vision (Lecture 18)