Trajectory features and distance metrics for hierarchical video segmentation
A method to perform hiearchical video segmentation includes: defining voxels over a spatio-temporal video; grouping into segments contiguous voxels that display similar characteristics including similar appearance or motion; determining a trajectory-based feature that complements color and optical flow cues, wherein trajectory cues are probabilistically meaningful histograms combinable for use in a graph-based framework; and applying a max-margin module for cue combination that learns a supervised distance metric for region dissimilarity that combines color, flow and trajectory features.
1. A system to perform hierarchical video segmentation, comprising:
a processor coupled to a camera;
wherein the processor executes:
defining voxels over a spatio-temporal video;
grouping into segments contiguous voxels that display similar characteristics including similar appearance or motion;
determining a trajectory-based feature that complements color and optical flow cues, wherein trajectory cues are probabilistic histograms combinable in a graph-based framework; and
applying a max-margin cue combination that learns a supervised distance metric for region dissimilarity that combines color, flow and trajectory features;
generating a max-margin distance metric for video segmentation that combines a plurality of feature channels;
determining feature representation φ(S) for a segment S as a stacked up histograms from all the individual cues;
learning feature weighting as a linear combination w T |φ(S i )−φ(S j ), where an optimal weight w* is determined by solving an optimization problem of the form:
min
w
,
ξ
ij
1
2
w
T
w
+
λ
N
+
∑
i
,
j
ξ
ij
+
+
λ
N
-
∑
i
,
j
ξ
ij
-
s
.
t
.
y
ij
w
T
ϕ
(
s
i
)
-
ϕ
(
s
j
)
≤
2
y
ij
-
1
+
ξ
ij
,
∀
i
,
j
w
±
0
,
ξ
ij
≥
0
,
where ξ ij denote slack variables and λ is a soft margin trade-off parameter, N + and N − are the number of pairs of segments that have the same or different ground truth label and ξ ij + , ξ ij − are slack variables with respective membership in those positive or negative sets.
2. The system of claim 1 , comprising representing trajectories as probabilistic histogram features.
3. The system of claim 1 , comprising generating histogram-based features in a graph-based hierarchical segmentation.
4. The system of claim 1 , comprising applying a naive Bayes distance for video segmentation that provides a probabilistic framework to combine a plurality of feature channels.
5. The system of claim 1 , comprising a speed-up of the graph-based segmentation.
6. The system of claim 1 , comprising:
starting the trajectories at interest points;
tracking the trajectories using a median filtered optical flow at multiple scales;
evolving the trajectories until the trajectories shrink to non-corner points; and
extracting a shape cue and length cue from each trajectory.
7. The system of claim 1 , wherein (x, y, z) is a trajectory that ends at pixel location (x,y) in frame z, comprising:
extracting the shape cue at a frame z by considering trajectories that have length at least L+1 and tracked through frames z−L, . . . , z−1, z; and
defining a trajectory cue as the 2L-dimensional displacement vector {(x i −x i-1 ,y i −y i-1 )} i=1 . . . L .
8. The system of claim 1 , comprising using geometric lengths of trajectories as an indicator of motion and depth differences for the length cue.
9. The system of claim 1 , comprising combining cues for segmentation by determining distances from the trajectory shape and length cues, denoted by d t and d l ,
respectively:
d=[ 1−(1− d c )(1− d f )(1− d t )(1− d l )] 2 .
10. The system of claim 1 , comprising generating learned weights as a linear combination of feature dimensions.
11. The system of claim 1 , comprising generating learned weights as a linear combination of feature dimensions.
12. The system of claim 11 , comprising generating a probabilistic representation of the trajectory cue for a segment, wherein the representation is also used for histogram mergers in a graph-based hierarchical segmentation framework.
13. A method to perform hierarchical video segmentation, comprising:
a processor coupled to a camera;
wherein the processor executes:
defining voxels over a spatio-temporal video;
grouping into segments contiguous voxels that display similar characteristics including similar appearance or motion;
determining a trajectory-based feature that complements color and optical flow cues, wherein trajectory cues are probabilistic histograms combinable in a graph-based framework; and
applying a max-margin cue combination that learns a supervised distance metric for region dissimilarity that combines color, flow and trajectory features;
generating a max-margin distance metric for video segmentation that combines a plurality of feature channels;
determining feature representation φ(S) for a segment S as a stacked up histograms from all the individual cues;
learning feature weighting as a linear combination w T |φ(S i )−φ(S j ), where an optimal weight w* is determined by solving an optimization problem of the form:
min
w
,
ξ
ij
1
2
w
T
w
+
λ
N
+
∑
i
,
j
ξ
ij
+
+
λ
N
-
∑
i
,
j
ξ
ij
-
s
.
t
.
y
ij
w
T
ϕ
(
s
i
)
-
ϕ
(
s
j
)
≤
2
y
ij
-
1
+
ξ
ij
,
∀
i
,
j
w
±
0
,
ξ
ij
≥
0
,
where ξ ij denote slack variables and λ is a soft margin trade-off parameter, N + and N − are the number of pairs of segments that have the same or different ground truth label and ξ ij + , ξ ij − are slack variables with respective membership in those positive or negative sets.
14. The method of claim 13 , comprising representing trajectories as probabilistic histogram features.
15. The method of claim 13 , comprising generating histogram-based features in a graph-based hierarchical segmentation.