Context-aware tracking of a video object using a sparse representation framework
View Patent ↗A method, system, and/or computer program product tracks an object in a video. A bounding box is defined by the user in a first frame, thus representing the object to be tracked based on a point of interest. A static dictionary D is populated with the densely overlapping patches from a search window. A new frame in the video is detected, and candidate patches, in the new frame, that potentially depict the object being tracked are identified. The candidate patches are co-located with the multiple densely overlapping patches to form a dynamic candidate dictionary Y of candidate patches. Candidate patches that best match the densely overlapping patches from the first frame are identified by an L1-norm solution, in order to identify a best-matched patch in the new frame.
1. A method to track an object in a video, the method comprising:
initializing, by one or more processors, a first frame in a video by detecting a search window over an object to be tracked, wherein initializing the first frame comprises defining multiple densely overlapping patches within the search window;
populating, by one or more processors, a static dictionary D with the densely overlapping patches from the search window;
detecting, by one or more processors, a new frame in the video, wherein the new frame includes the object being tracked;
identifying, by one or more processors, candidate patches, in the new frame, that potentially depict the object being tracked;
co-locating, by one or more processors, the candidate patches with the multiple densely overlapping patches to form a dynamic candidate dictionary Y of candidate patches;
identifying, by one or more processors, candidate patches that best match the densely overlapping patches from the first frame to generate selected candidate patches by minimizing a solution:
min∥Dα k −y k ∥ 2 2 +λ∥α k ∥ 1
where the solution minimizes a square of a L2-norm for a distance between atoms in a dictionary D of the densely overlapping patches times an n-dimensional coefficient vector α k (Dα k ) and each candidate patch (y k ) in dictionary Y, plus a Lagrange Multiplier lambda (λ) times an L1-norm of α k , wherein the Lagrange multiplier is determined by the gradient between an initial atom d k from D and the candidate atom y k from Y;
weighting, by one or more processors, the selected candidate patches based on a sparse coefficient of confidence of the selected candidate patches belonging to the object being tracked;
identifying, by one or more processors, a highest weighted candidate patch, from the selected candidate patches, as a patch that depicts the object being tracked in the new frame of the video; and
constructing, by one or more processors, a confidence map for candidate patches in the dictionary Y, wherein the confidence map is a 2-D matrix that depicts a level of confidence that a patch from the new frame matches a densely overlapping patch from the first frame wherein the confidence map is based on:
y x,y =α xy D′ [x,y]εO w
where α xy is a ‘n’ dimensional coefficient vector for each candidate patch at location (x, y), where [x,y] are elements of (ε) and object window (O w ) that describe locations in an object window in the new frame, wherein D′=[D o D b ], wherein D o is a dictionary of object patches from the object being tracked, wherein D b is a dictionary of background patches outside of the object being tracked, and wherein D o and D b are both used to discriminate the object patches from the background patches.
2. The method of claim 1 , further comprising:
setting, by one or more processors, a multi-level object pyramid for the object to be tracked, wherein the multi-level object pyramid comprises multiple sizes of search windows;
matching, by one or more processors, a variation in a size of the object to be tracked to one of multiple sizes of search windows, wherein said matching to the multi-level object pyramid accommodates movement towards and away from a video camera that created the video;
adjusting, by one or more processors, the confidence map computed based on a distribution of the sparse coefficients resulting from said matching of the variation in the size of the object to be tracked to said one of the multiple sizes of search windows.
3. The method of claim 2 , further comprising:
cyphering, by one or more processors, the confidence measure according to:
C
(
x
,
y
)
=
{
max
(
α
xy
)
,
if
max
(
α
xy
)
∈
D
o
0
otherwise
wherein C(x,y) classifies a patch as foreground or background based on a maximum coefficient value, wherein if a maximum coefficient value for α xy belongs to the object dictionary Do, then a corresponding candidate patch is deemed to be an object patch.
4. The method of claim 2 , further comprising:
compensating, by one or more processors, for partial occlusion of the object being tracked by identifying a centroid in the confidence map, wherein the centroid in the confidence map is determined by scanning an object window in the new frame that maximizes a mean of the sparse calculations.
5. A computer program product for tracking an object in a video, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code readable and executable by a processor to perform a method comprising:
initializing a first frame in a video by detecting a search window over an object to be tracked, wherein initializing the first frame comprises defining multiple densely overlapping patches within the search window;
populating a static dictionary D with the densely overlapping patches from the search window;
detecting a new frame in the video, wherein the new frame includes the object being tracked;
identifying candidate patches, in the new frame, that potentially depict the object being tracked;
co-locating the candidate patches with the multiple densely overlapping patches to form a dynamic candidate dictionary Y of candidate patches;
identifying candidate patches that best match the densely overlapping patches from the first frame to generate selected candidate patches by minimizing a solution:
min∥Dα k −y k ∥ 2 2 +λ∥α k ∥ 1
where the solution minimizes a square of a L2-norm for a distance between atoms in a dictionary D of the densely overlapping patches times an n-dimensional coefficient vector α k (Dα k ) and each candidate patch (y k ) in dictionary Y, plus a Lagrange Multiplier lambda (λ) times an L1-norm of α k , wherein the Lagrange multiplier is determined by the gradient between an initial atom d k from D and the candidate atom y k from Y;
weighting the selected candidate patches based on a sparse coefficient of confidence of the selected candidate patches belonging to the object being tracked;
identifying a highest weighted candidate patch, from the selected candidate patches, as a patch that depicts the object being tracked in the new frame of the video; and
constructing a confidence map for candidate patches in the dictionary Y, wherein the confidence map is a 2-D matrix that depicts a level of confidence that a patch from the new frame matches a densely overlapping patch from the first frame, wherein the confidence map is based on:
y x,y =α xy D′ [x,y]εO w
where α x,y is a ‘n’ dimensional coefficient vector for each candidate patch at location (x, y), where [x,y] are elements of (ε) and object window (O w ) that describe locations in an object window in the new frame, wherein D′=[D o D b ], wherein D o is a dictionary of object patches from the object being tracked, wherein D b is a dictionary of background patches outside of the object being tracked, and wherein D o and D b are both used to discriminate the object patches from the background patches.
6. The computer program product of claim 5 , wherein the method further comprises:
setting a multi-level object pyramid for the object to be tracked, wherein the multi-level object pyramid comprises multiple sizes of search windows;
matching a variation in a size of the object to be tracked to one of multiple sizes of search windows, wherein said matching to the multi-level object pyramid accommodates movement towards and away from a video camera that created the video
adjusting the confidence map computed based on a distribution of the sparse coefficients resulting from said matching of the variation in the size of the object to be tracked to said one of the multiple sizes of search windows.
7. The computer program product of claim 6 , wherein the method further comprises:
cyphering the confidence measure according to:
C
(
x
,
y
)
=
{
max
(
α
xy
)
,
if
max
(
α
xy
)
∈
D
o
0
otherwise
wherein C(x,y) classifies a patch as foreground or background based on a maximum coefficient value, wherein if a maximum coefficient value for α xy belongs to the object dictionary Do, then a corresponding candidate patch is deemed to be an object patch.
8. The computer program product of claim 6 , wherein the method further comprises:
compensating for partial occlusion of the object being tracked by identifying a centroid in the confidence map, wherein the centroid in the confidence map is determined by scanning an object window in the new frame that maximizes a mean of the sparse calculations.
9. A computer system comprising:
a processor, a computer readable memory, and a computer readable storage medium;
first program instructions to initialize a first frame in a video by detecting a search window over an object to be tracked, wherein initializing the first frame comprises defining multiple densely overlapping patches within the search window;
second program instructions to populate a static dictionary D with the densely overlapping patches from the search window;
third program instructions to detect a new frame in the video, wherein the new frame includes the object being tracked;
fourth program instructions to identify candidate patches, in the new frame, that potentially depict the object being tracked;
fifth program instructions to co-locate the candidate patches with the multiple densely overlapping patches to form a dynamic candidate dictionary Y of candidate patches;
sixth program instructions to identify candidate patches that best match the densely overlapping patches from the first frame to generate selected candidate patches by minimizing a solution:
min∥Dα k −y k ∥ 2 2 +λ∥α k ∥ 1
where the solution minimizes a square of a L2-norm for a distance between atoms in a dictionary D of the densely overlapping patches times an n-dimensional coefficient vector α k (Dα k ) and each candidate patch (y k ) in dictionary Y, plus a Lagrange Multiplier lambda (λ) times an L1-norm of α k , wherein the Lagrange multiplier is determined by the gradient between an initial atom d k from D and the candidate atom y k from Y;
seventh program instructions to weight the selected candidate patches based on a sparse coefficient of confidence of the selected candidate patches belonging to the object being tracked;
eighth program instructions to identify a highest weighted candidate patch, from the selected candidate patches, as a patch that depicts the object being tracked in the new frame of the video;
ninth program instructions to construct a confidence map for candidate patches in the dictionary Y, wherein the confidence map is a 2-D matrix that depicts a level of confidence that a patch from the new frame matches a densely overlapping patch from the first frame wherein the confidence map is based on:
y x,y =α xy D′ [x,y]εO w
where α xy is a ‘n’ dimensional coefficient vector for each candidate patch at location (x, y), where [x,y] are elements of (ε) and object window (O w ) that describe locations in an object window in the new frame, wherein D′=[D o D b ], wherein D o is a dictionary of object patches from the object being tracked, wherein D b is a dictionary of background patches outside of the object being tracked, and wherein D o and D b are both used to discriminate the object patches from the background patches; and wherein
the first, second, third, fourth, fifth, sixth, seventh, eighth, and ninth program instructions are stored on the computer readable storage medium for execution by the processor via the computer readable memory.
10. The computer system of claim 9 , further comprising:
tenth program instructions to set a multi-level object pyramid for the object to be tracked, wherein the multi-level object pyramid comprises multiple sizes of search windows;
eleventh program instructions to match a variation in a size of the object to be tracked to one of multiple sizes of search windows, wherein said matching to the multi-level object pyramid accommodates movement towards and away from a video camera that created the video
twelfth program instructions to adjust the confidence map computed based on a distribution of the sparse coefficients resulting from said matching of the variation in the size of the object to be tracked to said one of the multiple sizes of search windows; and wherein
the tenth, eleventh, and twelfth program instructions are stored on the computer readable storage medium for execution by the processor via the computer readable memory.
11. The computer system of claim 10 , further comprising:
thirteenth program instructions to cypher the confidence measure according to:
C
(
x
,
y
)
=
{
max
(
α
xy
)
,
if
max
(
α
xy
)
∈
D
o
0
otherwise
wherein C(x,y) classifies a patch as foreground or background based on a maximum coefficient value, wherein if a maximum coefficient value for α xy belongs to the object dictionary Do, then a corresponding candidate patch is deemed to be an object patch; and wherein
the thirteenth program instructions are stored on the computer readable storage medium for execution by the processor via the computer readable memory.
12. The computer system of claim 10 , further comprising:
thirteenth program instructions to compensate for partial occlusion of the object being tracked by identifying a centroid in the confidence map, wherein the centroid in the confidence map is determined by scanning an object window in the new frame that maximizes a mean of the sparse calculations; and wherein
the thirteenth program instructions are stored on the computer readable storage medium for execution by the processor via the computer readable memory.