Denisty Estimation + Mean shift, Markov Random Fields,Feature and corner detection

Question 1

Limitations and beyond Kmeans

Answer 1

Limitations
1-Needs k to be provided
2-Non Optimal
3-Forces symetry

Beyond:
1-Create Density Function
2-Look For modes

Question 2

Creating density function for segmentatiton

Answer 2

Starting point: set of samples
Approac: Density estimation

Density function:computionally complex

Question 3

Mean Shift

Answer 3

-Find stationary peaks without computing distribution function.
-models distribution using continuos nonparametric model

Avoid density function? Estimate gradient instead.

Meanshift steepest ascend method

Meanshfit vector same direction as gradient.

Procedure:
-Compute mean shift vector
-move kernel window
-stop if gradient close to 0
-prube mode by perturbation

Question 4

Meanshift properties and optimization

Answer 4

Properties:
1-Automatic convergence speed
2-Steps are smaller towards mode.
3-Convergence depends on step size

Optimization
1-Divide space into windows and run parallelly

Pros
1.Doesnt assume cluster spherical
2.1 parameter window size
3- Find a variable nr of modes
4-robust to outliers

Cons
1-depends on window size -> hard to find the best, if bad modes are merged
2-computionally expensive
3-doesnt scale well with dimension of feature space

Question 5

Mean shift Clustering

Answer 5

Clustering criterion
1. Define attraction basin as the region for which trajectories lead to same mode.

2. All data points in same basin = cluster

To perserve discontinuities we have a joint domain spatial+color

Question 6

Segmentation and optimization

Answer 6

1 additional approach -> segmentation is a per-pixel labelling task.

Labelling::
-Define a set of labels
-Define and energy function
-Assign a label to minimize the energy

Energy function:
1-Data term
Depends on specific image features at pixel location
Evaluates how good label fits pixel
Defines match criterion based on image feature vector.

2.Smoothing term
Depends on labels of neighbors.
Normally 4 neighbors considered
Favors same label at adjacen pixels.

Balance:
1-To detect strong boundaries: dont penalize with smoothing term
2-Weak boundaries like noise shouldnt affect labelling so smoothing term shouldnt be too weak.

Question 7

Markov Random FIelds

Answer 7

The energy function evaluated over the whole
image is defined as:
𝐸 𝑓 = ෍
𝑝∈Ω
𝐸data 𝑝, 𝑓𝑝 + ෍
𝑞∈𝐴(𝑝)
𝐸smooth(𝑓𝑝, 𝑓𝑞)
* This model is called Markov Random Field (MRF)
* The model considers local interactions between
adjacent pixels
-Interactions are modeled considering a graph
Goal: select the labelling that minimizes the
energy function

Question 8

Optimizing Random Markov Fields using Belief Propagation

Answer 8

MRF-> minimization problem
Belief Propagation:algorithm to solve it

Based on message passing between neighboring pixels
Message has info about labels
Run several iterations

A message is a function mapping
– The ordered discrete set of labels – 𝐿
– Into an array of length 𝑚 having, for
each position, the message value
* Non-negative real values
– Message value for label 𝑙 sent from 𝑝
to 𝑞 at time 𝑡
– Function of the label 𝑙 ∈ 𝐿

The reply of node 𝑝 depends on
– The data term at 𝑝 for label ℎ (minimized)
– The smoothing term if the labels 𝑙 and ℎ are different
– The information brought by the neighbors of 𝑝
(excluding 𝑞) in the previous iteration (time 𝑡 − 1)
– Node 𝑞 is excluded from the computation
* It cannot influcence the opinion of 𝑝 about 𝑞 itself

Question 9

Features

Answer 9

Feature is a meaningful part of image.
Output: a set of points + description of the region (AKA
signature, fingerprint, …)

The ideal keypoints shall be
– Stable and repeatable
– Invariant to transformations (e.g., rotations)
– Insensitive to illumination changes
– Accurate

The ideal descriptor shall be
– Robust to occlusion and clutter
– Robust to noise, blur, compression, discretization
– Discriminative
– Stable over changes in viewing angle and illumination
– Computationally efficient (many features per image)

Question 10

Harris Corners to detect salient points(corners)

Answer 10

Idea: Consider image and shifted version
if uniform region:two similar patches.
if salient point; different patches.

Corner = large difference.

Harris.
- Conisder a patch and a displacement.
- Similarity is measured with autocorrelation.

Autocorrelation matrix properties.
-real
-symetric
-orthogonal eigenvectors
-points to max data spread eigenvectors

Studying the eigenvalues we get information
about the type of patch
– If both eigenvalues are small: uniform region
– Only one large eigenvalue: edge
– Two large eigenvalues: corner

The Harris corner detector is
– Invariant to brightness offset:
– Invariant to shift and rotations
– Not invariant to scaling

Question 11

Beyond Harris Corners

Answer 11

Susan and Usan
-Analyze circular window around point
-no derivatives
-edge and corner detector
-robust to noise

USAN: Comparte between nucleus and pixels. The portion with intensity difference from nucleus given a threshold.

Susan i smalles usan.

Harris focuses on specific point.
OTHERS on BLOBS(diferent properties than surrounding).

Question 12

MSER

Answer 12

Connected areas with uniform intensity surrounded by contrasting background (blobs)
MSER DETECTOR IS SAME AS BLOB DETECTOR.

ALG:
Apply thresholds
compute connected binary regions
compute statistics
analyze how presisten is blob.

Question 13

Scale Space Concept

Answer 13

Goal: analyze image at multi scales
Tool: scale space 0> original signal to family of derived signals.

-fine details are gradually suppressed.

Requirements:
Linearity
Spatial shift invariance
no new local extrema created
scale invariance

Gaussian smoothing does it

Question 14

Edge detection in scale space

Answer 14

Strong edges found at all scales.
At fine scales,accurate but many.
At coarse scales, inacurate but strong.
Combine them.

Question 15

SIFT Feature in detail
Keypoint detection
Descriptor calculation

Invariant to: translation, rotation, scale and other
transforms

Application
Matching and
registration
* Object recognition
* Query by example

Answer 15

-image content mapped into local fature cordinates

SIFT features:
– Local – robust to occlusions
– Distinctive – distinguish objects in large databases
– Dense – many features can be found even on
small objects
– Efficiency

Algorithm
* Scale-space extrema detection
* Keypoint localization
* Orientation measurement
* Descriptor calculation

Question 16

SIFT 1.scale space

Answer 16

-organized in octaves (from one to other sigma of gaussian is doubled)
(last image in one octave same smoothing as first one in next octave)

To detect extrema:
1-Layer substraction.
evaluate differences between images with same smooting but different smoothing intensity. (difference of gaussians)
Scale space + substraction of consecutive layers

2)Laplacian of Gausians ->smoothing + derivative filter.
removes noise
zero crossing
isotropic

Question 17

SIFT 2.Keypoint localization

Answer 17

-search for maxima and minima of DoG
-compares with 8 neighbors in current, previous and next scale level.
-done in all scales ->scale independent.

Subpixel accuarcy = interpolation

More scale levels considered
– More points
– More unstable
– Best value: s=3

Discard edge points – require that both
eigenvalues of 𝐻 are large
* Means: require that both
curvatures are high
* Similar to the discussion about
Harris corners
* Similar considerations about
eigenvalues ratios

Question 18

SIFT 3.Orientation measurement

Answer 18

-each keypoint has its scale.
-select that gaussian for that scale. (scale invariance)
-compute magnitude and orientation

Rotation invariance: the dominant
local direction shall be measured
36 bins of 10° for histogram. Look for 2 peaks. Fit parabolas.

Question 19

SIFT 4. Descriptor calculation

Answer 19

SIFT evaluates a descriptor for each keypoint
– In the image 𝐿 corresponding to the keypoint scale
– Considering coordinates that are rotated based on
the measured keypoint orientation.

Compute gradient
magnitude and direction

Values weighted with a
gaussian function
centered on the
keypoint

Evaluate histogram of
each region
– 8 bins (45° each)
* Save the values

• Additional details are considered by the SIFT
  algorithm
• Enhanced invariance to illumination: feature
  vector normalized to unit length
• Enhanced robustness to large gradient
  magnitudes: threshold to 0.2 on all the
  components
  – Nonlinear illumination effect – e.g., camera saturation
  – Further normalization to 1 after thresholding

Question 20

SIFT robustness

Answer 20

Noise:random rotations
Affine transfor: Random scale change + 2% noise

Question 21

Beyond SIFT

Answer 21

PCA
-reduces dimensionality
-max variance of projected data
-min mean squared dist

Principal component #1 points in the direction
of largest variance
* Each other principal component
– Is orthogonal to the previous ones
– Points in the direction of largest variance of the
residual subspace

Question 22

BEYOND SIFT 2.
PCA SIFT
SURF

Answer 22

PCA SIFT.
1-3 same as sift
4->refer to 41 41 patch normalized to a canonical direction

SIFT: weighted histograms
* PCA-SIFT: concatenate horizontal and vertical
gradients (39x39) into a long vector
– Length: 2 directions x 39x39 = 3042
* Normalize the vector to unit norm
* Reduce the vector using PCA
– E.g., from 3042 to 36.

SURF
Speed-up
computations by
fast approximation
of hessian matrix
and descriptors
using integral
images
Integral image 𝐼Σ(𝑥, 𝑦)
– Each pixel represents
the sum of all pixels in
the rectangle between
A box filter is composed of black and white rectangles
– White: positive weight
– Black: negative weight
* Box filters exploit the integral image
– Calculation is constant-time irrespective of the filter size.
Keypoints: compute the Hessian matrix in scale
space, find the maximum of the determinant

• Faster than SIFT
• Less robust to illumination and viewpoint
  changes WRT SIFT

Question 23

BEYOND SIFT 3. GLOH
BRIEF
ORB

Answer 23

Gradient Location-Orientation Histogram
* Obtained (again) modifying the 4th step of the
SIFT algorithm
* Computes SIFT descriptor using a log-polar
location grid.

PCA used for reducing dimensionality to 128

BRIEF
Based on:
– Gaussian smoothing
– Pairs of pixels compared inside a window
– Build a vector with comparison output
* Vectors compared using the Hamming distance (XOR)
Random pattern provides the best performance
– Best solution: isotropic gaussian distribution

• Oriented FAST and Rotated
  BRIEF
• FAST corner detector
• Add rotation invariance to
  BRIEF
• Orientation assignment
  based on the intensity
  centroid WRT the central
  pixel