COMP9517: Computer Vision
Feature Representation Part 2
Week 3 COMP9517 2021 T1 1
Feature Types
• Colour features (Part 1) – Colourmoments
– Colourhistogram
• Texture features (Part 1)
– Haralick texture features
– Localbinarypatterns(LBP)
– Scale-invariant feature transform (SIFT)
– Texture feature encoding
• Shape features (Part 2)
Week 3
COMP9517 2021 T1 2
– – –
Basic shape features
Shapecontext
Histogram of oriented gradients (HOG)
Shape Features
• Shape is an essential feature of material objects that can be used to identify and classify them
• Example: object recognition
Week 3 COMP9517 2021 T1 3
Shape Features
• Human perception of an object or region involves capturing prominent / salient aspects of shape
• Shape features in an image are normally extracted after the image has been segmented into object regions
Week 3 COMP9517 2021 T1 4
Shape Features
– Invariance to rigid transformations
– Tolerance to non-rigid deformations
– Correspondenceunknown
Week 3 COMP9517 2021 T1
• Challenges
?
5
Basic Shape Features • Simple geometrical shape descriptors
Week 3
COMP9517 2021 T1
6
Net Area
Principal Axes
Convex Area:
Area of the convex hull that encloses the object
Basic Shape Features • Convexity versus concavity of an object
An object O is called convex (or concave) if the straight line between any two points in the object is (or is not) contained in the object
a,bO, 01 (1−)a+bO
b a
Convex The smallest convex set that contains the object
Concave
• Convex hull of an object
• Convex deficiency of an object
Set difference between the convex hull and the object
Week 3 COMP9517 2021 T1 7
Basic Shape Features • Simple geometrical shape descriptors
Week 3
COMP9517 2021 T1
8
Compactness:
Ratio of the area of an object to the area of a circle with the same perimeter
Circularity:
Ratio of 4𝜋 times the area of an object to the second power of its perimeter (4𝜋𝐴/𝑃2 equals 1 for a circle)
Basic Shape Features • Simple geometrical shape descriptors
Week 3
COMP9517 2021 T1
9
Elongation:
Ratio between the length and width of the object’s bounding box
Eccentricity:
Ratio of the length of the minor axis to the length of the major axis
Boundary Descriptors • Chain code descriptor
– –
The shape of a region can be represented by labelling the relative position of consecutive points on its boundary
A chain code consists of a list of directions from a starting point and provides a compact boundary representation
Example: 2,1,0,7,7,0,1,1
Week 3
COMP9517 2021 T1
10
Boundary Descriptors • Local curvature descriptor
– –
The curvature of an object is a local shape attribute
Convex (versus concave) parts have positive (versus negative) curvature
s
0
0s1
Week 3
COMP9517 2021 T1
11
Boundary Descriptors • Two interpretations of local curvature
SupposetheboundaryisparameterizedasC:[0,1]→R2 C(s)=x(s),y(s)
C Outside s−s
r(s) Inside
Geometrical interpretation
(s)= 1 r(s)
C
+
τ(s) Physical interpretation
(s)= dτ(s) ds
Tangent
Week 3
COMP9517 2021 T1
12
Boundary Descriptors • Global curvature descriptors
–
Total bending energy
o Amount of physical energy stored in a rod bent to the contour
B= C2(s)ds
o Circular objects have the smallest contour bending energy B = 2 / r
–
Total absolute curvature
o Absolute value of the curvature integrated along the object contour
K = C|(s)|ds
o Convex objects have the smallest total absolute curvature K = 2
Week 3
COMP9517 2021 T1 13
Boundary Descriptors • Radial distance descriptor
–
Use the centroid of the shape as the reference point and compute the radial distance for all N pixels along its boundary
22 d(n)= (x(n)−x) +(y(n)−y)
forn=0,1, ,N−1
Scale invariance is achieved by normalising d(n) by the maximum
distance to obtain the radial distance r(n)
The number of times the signal r(n) crosses its mean can be used as a
measure of boundary roughness
Week 3
COMP9517 2021 T1 14
– –
Application Example • Combining feature descriptors to classify objects
3000
24 13
4
15 17
5
23 27
14
725
6
1
18 3
9 26
21 1122 20
0
8 1 1 1 12 2690 1
0
Circularity
Week 3
COMP9517 2021 T1
15
Area
Shape Context
• Shape context is a point-wise local feature descriptor
– Pick n points on the contour of a shape
– For each point pi construct a histogram hi of the relative coordinates of the other n − 1 points => this is the shape context of pi
(d) (f) (e)
S. Belongie, J. Malik, J. Puzicha, “Shape matching and object recognition using shape contexts,” IEEE Transactions on Pattern Analysis and Machine Intelligence 24(4):509-522. https://doi.org/10.1109/34.993558
Week 3 COMP9517 2021 T1 16
Application Example • Shape matching
Week 3 COMP9517 2021 T1 17
• Shape matching
Shape Context
– Step 1: Sample a list of points on shape edges
For example from Canny edge detector (Gaussian filtering, intensity gradient, non-maximum suppression, hysteresis thresholding, edge tracking)
Week 3 COMP9517 2021 T1 18
Shape Context Step 2: Compute the shape context for each point
Step 3: Compute the cost matrix between two shapes P and Q
The cost between any two points 𝑝 ∈ 𝑃 and 𝑞 ∈ 𝑄 with corresponding shape
• Shape matching –
–
contexts 𝑔 and h is defined as
𝑞
𝑝
Week 3
COMP9517 2021 T1
19
• Shape matching
Week 3
COMP9517 2021 T1 20
–
Step 4: Find the one-to-one matching that minimises the total cost between pairs of points on the two shapes
Step 5: Transform or deform one shape to the other based on the previous one-to-one point matching
o Choose the desired transformation (for example affine) o Apply least-squares or RANSAC fitting
Shape Context
–
Shape Context – Step 6: Compute the shape distance
• Shape matching
Other costs may also be taken into consideration o Appearance of the image at the points
o Bending energy of the transformation
Week 3 COMP9517 2021 T1 21
Application Example • Shape matching
1) Sample points
2) Compute shape context 3) Compute cost matrix
4) Find point matching
5) Perform transformation 6) Compute distance
Week 3
COMP9517 2021 T1
22
Histogram of Oriented Gradients
• HOG describes the distributions of gradient orientations in localized areas and does not require initial segmentation
N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” Computer Vision and Pattern Recognition 2005. https://doi.org/10.1109/CVPR.2005.177
Week 3 COMP9517 2021 T1 23
Histogram of Oriented Gradients
• Step 1: Calculate gradient magnitude and orientation at each pixel with a gradient operator => gradient vector
Week 3 COMP9517 2021 T1 24
Histogram of Oriented Gradients
• Step 2: Divide orientations into N bins and assign the gradient magnitude of each pixel to the bin corresponding to its orientation => cell histogram
– For example 9 bins evenly divided from 0 to 180 degrees
Week 3 COMP9517 2021 T1 25
Histogram of Oriented Gradients
• Step 3: Concatenate and block-normalise cell histograms to generate detection-window level HOG descriptor
# orientations/cell # features = (7 x 15) x 9 x 4 = 3780
# blocks # cells/block
Week 3 COMP9517 2021 T1
26
Histogram of Oriented Gradients • Detection via sliding window on the image
Week 3 COMP9517 2021 T1 27
Histogram of Oriented Gradients • Detection via sliding window on the image
HOG feature map
Detector response map
Week 3
COMP9517 2021 T1
28
Application Example • Human detection
Week 3 COMP9517 2021 T1 29
Application Example • Human detection
Week 3 COMP9517 2021 T1 30
Application Example • Deformable part model
P. Felzenszwalb, D. McAllester, D. Ramanan, “A discriminatively trained, multiscale, deformable part model,” Computer Vision and Pattern Recognition 2008. https://doi.org/10.1109/CVPR.2008.4587597
Week 3 COMP9517 2021 T1 31
Summary
• Feature representation is essential in solving almost all types of computer vision problems
• Most commonly used image features:
– Colourfeatures(Part1)
• Colour moments and histogram
– Texture features (Part 1) • Haralick, LBP, SIFT
– Shapefeatures(Part2)
• Basic, shape context, HOG
Week 3
COMP9517 2021 T1 32
Summary
• Other techniques described
– Descriptor matching
– Featureencoding(Bag-of-Words)
– k-means clustering
– AlignmentandRANSAC
– Spatialtransformations
– Shapefeatures
– Shapematching
– Slidingwindowdetection
Week 3
COMP9517 2021 T1 33
References and Acknowledgements
• Szeliski, Chapter 4 (in particular Sections 4.1.1 to 4.1.3 and 4.3.2), Chapter 6 (in particular Sections 6.1.1 to 6.1.4)
• Some content are extracted from the above resource, James Hays slides, and slides from Michael A. Wirth
• L. Liu et al., From BoW to CNN: two decades of texture representation for texture classification, International Journal of Computer Vision, 2019
• And other resources as indicated by the hyperlinks
Week 3 COMP9517 2021 T1 34