A Dense SURF and Triangulation based
Spatio-Temporal Featurefor Action Recognition
Do Hang Nga

Keiji Yanai

The University of Electro-Communications, Tokyodohang@mm.cs.uec.ac.jp, yanai@cs.uec.ac.jp

Introduction
 A method of extracting ST features• An extension of method proposed by Noguchi et al.[1] Improvements:• Simple yet efficient selection of interest points• Novel ST descriptors

 Performance on UCF-101: 62.5%• Fisher Vector encoding based video representation• Multiclass linear SVMs
[1] A. Noguchi and K. Yanai. A surf-based spatio-temporal feature for featurefusion-based action recognition. In ECCV WS on Human Motion: Understanding,Modeling, Capture and Animation, 2010.
MMM’14The University of Electro-Communications, TokyoRelated Works• Comparison with some methods of extracting
local ST features based on interest points
i.e.: 3D-SIFT, 3D-HOG, STIP, Trajectory[2]– Selection of interest points– Vectorization[2] H. Wang, A. Klaser, C. Schmid, and C-L. Liu. Dense trajectories and motion
boundary descriptors for action recognition. International Journal of Computer
Vision, 103(1):60–79, 2013.
MMM’14The University of Electro-Communications, Tokyo

Related Works
Point Selection

3D-SIFT

Random

3D-HOGSTIP

MMM’14Harris operator

Trajectory

Dense sampling

Proposed

Dense sampling + Flow
The University of Electro-Communications, Tokyo

Related Works
Vectorization
3D-SIFT
3D-HOG, STIP
Trajectory

Proposed
MMM’14The University of Electro-Communications, Tokyo

Overview of Our Method.......
Keypoint extraction(Dense SURF)

Optical Flow estimation(LDOF)....
MMM’14The University of Electro-Communications, Tokyo

Overview of Our Method....
Motion compensation

Delaunay
Triangulation
MMM’14

Point selection

FeatureExtraction

The University of Electro-Communications, TokyoOverview of Our Method....
Motion compensation

Delaunay
Triangulation
MMM’14

Point selection

FeatureExtraction

The University of Electro-Communications, TokyoMotion Compensation• Baseline (Noguchi et al.’s work):– no motion compensation– no features extracted from videos with camera motion• Ours: simple yet efficient motion compensation
Estimate direction& magnitude ofcamera flow

MMM’14

If camera moves

Cancelcameramotion

The University of Electro-Communications, Tokyo

Motion Compensation+• Estimation of camera motion
e.g.: 𝑥 direction (same for 𝑦 direction)?

+-Camera moved
to the left𝒇𝒙 𝒄𝒂𝒎𝒆𝒓𝒂 =𝑷 𝒙𝒊 𝒇 𝒊

𝑷𝒔. 𝒕.

𝒇𝒙 𝒊 < 𝟎𝒇𝒙 𝒊 > 𝜺𝑓 𝑥 𝑖 : horizontal optical flow of point 𝑖
𝑓 𝑥 𝑐𝑎𝑚𝑒𝑟𝑎 : horizontal magnitude of camera flow
MMM’14The University of Electro-Communications, Tokyo

Motion Compensation• Compensation of motion of keypoints
e.g.: 𝑥 direction (same for 𝑦 direction)
𝒇𝒙 𝒌 = 𝒇𝒙 𝒌 − 𝝀𝒇𝒙 𝒄𝒂𝒎𝒆𝒓𝒂
1 𝑖𝑓 𝑐𝑎𝑚𝑒𝑟𝑎 𝑖𝑠 𝑚𝑜𝑣𝑖𝑛𝑔 𝑟𝑖𝑔ℎ𝑡
𝜆=−1 𝑖𝑓 𝑐𝑎𝑚𝑒𝑟𝑎 𝑖𝑠 𝑚𝑜𝑣𝑖𝑛𝑔 𝑙𝑒𝑓𝑡

MMM’14The University of Electro-Communications, Tokyo

Interest Point Selection• Principals of point selection
Baseline: at least once flow > fixed thresholdOurs:① flow > flexible threshold② prefer points with more movements
MMM’14The University of Electro-Communications, Tokyo

Interest point selection• Why motion threshold should be flexible?
Because magnitude of movement varies largely
from action to action
Large
movements
SurfingHigh jump

Ice dancing

Apply lipstick

TypingShaving beard

Smallmovements
MMM’14The University of Electro-Communications, Tokyo

Interest Point Selection• Why motion threshold should be flexible?
Because magnitude of movement depends onthe environmentLarge
movements

Smallmovements
MMM’14The University of Electro-Communications, TokyoInterest Point Selection
𝑚𝑎𝑥𝑡ℎ𝑟𝑒𝑠ℎ• Estimation of motion threshold𝑎𝑣𝑒𝑟– done for every frame– In each of 4 directions: 𝑥 + , 𝑥 − , 𝑦 + , 𝑦 −– e.g. motion threshold for frame 𝑓𝑟 in 𝑥 + direction

𝒕𝒉𝒓𝒆𝒔𝒉𝒇𝒓 + = 𝒂𝒗𝒆𝒓𝒇𝒓 + + 𝜶 𝒎𝒂𝒙𝒇𝒓 + − 𝒂𝒗𝒆𝒓𝒇𝒓 +𝒙

𝑖𝑓 𝒇𝒙+𝒊𝒙

𝒙𝒙≥ 𝒕𝒉𝒓𝒆𝒔𝒉𝒇𝒓 + , 𝑡ℎ𝑒𝑛 𝑝𝑜𝑖𝑛𝑡 𝑖 𝑖𝑠 𝑚𝑜𝑣𝑖𝑛𝑔 𝑟𝑖𝑔ℎ𝑡𝒙

𝑖𝑓 𝒕𝒉𝒓𝒆𝒔𝒉𝒇𝒓 + < ε, 𝑡ℎ𝑒𝑛 𝑛𝑜 𝑝𝑜𝑖𝑛𝑡 𝑖𝑠 𝑚𝑜𝑣𝑖𝑛𝑔 𝑟𝑖𝑔ℎ𝑡𝒙

MMM’14The University of Electro-Communications, TokyoInterest point selection• Why points with more movements should bepreferred?
Because they are more representative
representative(move more frequently)

not representative

Cutting in kitchen

Sumo Wrestling

MMM’14The University of Electro-Communications, Tokyo

Interest Point Selection• Algorithm of selecting interest points

MMM’14The University of Electro-Communications, Tokyo

Feature Extraction.....
Motion compensation

Delaunay
Triangulation

Point selection

Proposed feature
Spatial descriptors
Temporal descriptors...........
MMM’14

Spatio-Temporal (ST)descriptors

The University of Electro-Communications, Tokyo

Feature Extraction
Spatial descriptors[1]:
SURF descriptors (64-D)
of 3 points of the triple(first frame)

concatenate

192-Ddescriptor
PCA

PCA-SURF(96-D)
MMM’14The University of Electro-Communications, Tokyo

Feature Extraction
Temporal descriptors:① Histogram of Oriented Optical Flow (HOOF)[3]② Histogram of Direction of Flow (HDF)[1][3] R. Chaudhry, A. Ravichandran, G. Hager, and R. Vidal. Histograms of oriented opticalflow and binetcauchy kernels on nonlinear dynamical systems for the recognition of humanactions. In Proc. of IEEE Computer Vision and Pattern Recognition, pages 1932– 1939, 2009

MMM’14The University of Electro-Communications, Tokyo

Feature Extraction• HOOF (Histogram of Oriented Optical Flow )– 𝟑 𝑵 − 𝟏 flow vectors of 3 points are binned to a𝐵-bin histogram– 𝑣 = 𝑥, 𝑦 with 𝜃 = tan−1 𝑦 in the range:𝜋𝑏−1𝜋𝑏− +𝜋≤𝜃 <− +𝜋2𝐵𝑜2
𝐵𝑜will contribute by 𝑥 2 + 𝑦 2
to the sum in bin 𝑏– Histogram is normalized tosum up to 1MMM’14

𝐵=4

The University of Electro-Communications, Tokyo

Feature Extraction• HDF (Histogram of Direction of Flow)– 𝟑 𝑵 − 𝟏 flow vectors are binned to a 4-bin
histogram based on direction of movements:• 𝑓𝑥 + ≥ 0: moving forward or horizontally still• 𝑓𝑥 − ≥ 0: moving backward• 𝑓𝑦+ ≥ 0: moving up or vertically still• 𝑓𝑦 − ≥ 0: moving down

– Histogram is normalized
to sum up to 1
MMM’14𝑓𝑦 + ≥ 0𝑓𝑥 + ≥ 0

𝑓𝑥− ≥ 0𝑓𝑦− ≥ 0

The University of Electro-Communications, Tokyo

Feature Extraction
ST descriptors:① Area of Triangle (AT)[1]② Histogram of Angle of Triangle (HAT)③ Histogram of Angle of Flow (HAF)• AT (Area of Triangle)

Proposedby us– concatenated by areas of triangles at 𝑁 frames– normalized to sum up to 1

MMM’14The University of Electro-Communications, Tokyo

Feature Extraction
NOVEL
frame kMMM’14

HAFk+1k+2

HATk+3k+N-1

The University of Electro-Communications, Tokyo

Feature Extraction• HAT (Histogram of Angle of Triangle)– 2 smallest angles of each triangle arebinned to a 5 bin-histogram:0 − 15 , 15 − 30 , 30 − 45 , 45 − 60 , [60 − 90]– Each angle is weighted by sum of magnitude of its
two edges– The histogram is normalized to sum up to 1

MMM’14The University of Electro-Communications, Tokyo

Feature Extraction• HAF (Histogram of Angle of Flow)– 𝟑 𝑵 − 𝟏 angles shaped by adjacent trajectories
are binned similarly to HOOF
𝜋𝑏−1
𝜋𝑏− +𝜋≤𝜃 <− +𝜋2
𝐵2𝐵– Each angle is weighted by sum of magnitude of its
two edges– The histogram is normalized to sum up to 1

MMM’14The University of Electro-Communications, Tokyo

Summary of
Proposed ST Descriptor
SpatialTemporalSpatioTemporalFeature
PCA-SURF
HOOF
HDF
AT

Dimension
964(∗)
45(∗)
5HAT
HAF4(∗)

Proposed ST118∗ : adjustable

MMM’14The University of Electro-Communications, Tokyo

Classification Framework
FeatureExtraction

VideoEncoding

ST Features

Gaussian
MixtureModelFisherVectors
MMM’14

ActionClassification

Multiclasslinear SVMs

The University of Electro-Communications, Tokyo

Experiments and Results• Dataset: UCF-101– 101 actions, 13320 videos• Evaluation method: workshop THUMOS’13 1– 3 training/test splits• Methods of extracting ST features to compare:– Baseline[1]– HOG, MBH (Dense Trajectories[2])– Proposed
1 http://crcv.ucf.edu/ICCV13-Action-Workshop/: The First International Workshop

on Action Recognition with a Large Number of Classes, in conjunction with ICCV '13
MMM’14The University of Electro-Communications, Tokyo

Experiments and Results

MMM’14Method

Precision

Baseline[1]

38.2%

HOG

56.4%

MBH

61.6%

Proposed

62.5%

Combined(HOG+MBH+Proposed)

74.7%

The University of Electro-Communications, TokyoConclusions• A method of extracting ST features as anextension of Noguchi etal.’s method[1]• Better performance than dense trajectory
based features[2]– complementary to [2]• Future works:– handle more complicated camera motion– combine with other features
MMM’14The University of Electro-Communications, Tokyo