Computer Vision lectures 6.1-8

Equation of circle

(xi - a)² + (yi - b)² = r²

If the radius is known

2D Hough Space - Accumulator array = A(a,b)

If the radius is not known

3D Hough Space - Accumulator array = A(a,b,r)

Using Gradient Information

can save lots of computation,

edge detection (xi, yi)

edge direction (phi)

a = x - r cos(phi)

b = y - r sin(phi)

Can you use Hough Transforms for other objects,

beyond lines and circles?

Yes

Generalized Hough Transform

Find the object center (xc,yc) given edges (xi,yi,phi)

create accumulator A(xc,yc)

initialize A(xc,yc) = 0 and ∀(xc,yc)

for each edge point (xi,yi,phi)
for each entry rk in table, compute

xc = xi + rk cos ak

yc = yi + rk sin ak

increment accumulator A(xc,yc) = A(xc,yc)+1

find local maxima in A(xc,yc)

Application of Hough Transforms

Detecting shape features

Hough transform

deals with occlusion, detects multiple instances, robust to noise

Template

an example of how an object looks

Sum of Squared Differences

A way to measure similarities using sum of squared differences

SIGMA(d=1,D) (vd-wd)²

Defining Similarity Using SSD

we need to measure the SSD between each sub window and the template (good matches correspond to low ssd scores)

Shortcomings of SSD

works if the face in the image has similar brightness and contrast

works if the face in the image has the same size as the face in template

works if the image is rotated in the same way as the template

works if the face in the image is fully visible

Normalizing for brightness

we can subtract from every window its average intensity value

template is normalized by subtracting from its average intensity

each sub window is normalized by subtracting from its average intensity right before measuring its SSD with the normalized template

DO NOT normalize the entire input image in single step

Normalize for Contrast

Brightness normalization - we subtract from every window its average intensity value

Contrast normalization (done after brightness normalization) - we divide each window by the standard deviation of values in that window

Normalized Cross-correlation

provides alternative way to find matches of a template with an image (instead of looking for lowest SSD score we look for highest normalized cross-correlation score)

Detection at Different Scales

SSD and normalized cross-correlation assume that the object that we want to detect is about as large as the template. Therefore we need to fix the scaling

Scaling the Image

Approach by scaling the image down by a factor of 3 (1/3), and then get normalized cross-correlation scores between scaled down image and the template. Or we scale up by a factor of 3.

Scaling the Template

Alternative to scaling the image, same method but with the template instead.

Multiscale Search

used when we do not know the size of the object we want to detect. (has more potential false matches)

In-Plane Rotations

do not change what is visible, change orientation of the visible parts.

Out-of-Plane Rotations

the object rotates in a way that changes what is visible.

Handling Rotations

Done in similar way for multi-scale (search at multiple rotation and grab high score)

Number of Detection Results

Set a threshold on the score

Any score above the threshold qualifies as a detection (except non-maxima suppression)

Cropping

beneficial in a way so that we can keep parts of a template that is most likely to be present in the image.

Measuring Accuracy

we need to use some dataset of images. For every image in that dataset, we need to set annotations that specify how many objects of interest are present and the bounding box of every object of interest.

Is a Detection Correct?

measure the intersection over union (IoU) score between the detection and the ground truth

# of pixels in A ∩ B
—————————
# of pixels in A U B

True positive

a detection box whose IoU score with a ground truth box is over the threshold

False positive

detection box whose maximum IoU score with all ground truth boxes is under the threshold.

False negative

a ground truth box G is a false negative if its maximum IoU score with all detection boxes is under the threshold

Thresholds

2 types required:
IoU threshold - usually 0.5
detection threshold

detection threshold

Changing the detection threshold usually leads to one of the two numbers (true positives or false positives) getting better and the other one getting worse