Object tracking in video with visual constraints

• US 8,085,982 B1
• Filed: 06/20/2008
• Issued: 12/27/2011
• Est. Priority Date: 06/20/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Sanjiv, Rowley, Henry A., Kim, Minyoung
• Primary Examiner(s): Johns, Andrew W
• Assistant Examiner(s): Goradia, Shefali
• Application Number:
  US12/143,590
• Time in Patent Office: 1,285 Days
• Field of Search: 382/100, 382/103, 382115-118, 382/195
• US Class Current: 382/103
• CPC Class Codes: G06F 18/2185 the supervisor being an automated module, e.g. intelligent oracle
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06V 10/76 based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/7788 the supervisor being a human, e.g. interactive learning with a human teacher
• CPC Class Codes: G06V 40/167 using comparisons between temporally consecutive images

Abstract

Embodiments of the present invention relate to object tracking in video. In an embodiment, a computer-implemented method tracks an object in a frame of a video. An adaptive term value is determined based on an adaptive model and at least a portion of the frame. A pose constraint value is determined based on a pose model and at least a portion the frame. An alignment confidence score is determined based on an alignment model and at least a portion the frame. Based on the adaptive term value, the pose constraint value, and the alignment confidence score, an energy value is determined. Based on the energy value, a resultant tracking state is determined. The resultant tracking state defines a likely position of the object in the frame given the object'"'"'s likely position in a set of previous frames in the video.

Claims

1. A computer-implemented method for tracking an object in a frame of a video, comprising:

(a) determining an adaptive term value based on an adaptive model and at least a portion of the frame, wherein the adaptive model is determined based on at least one previous frame of the video;

(b) determining a pose constraint value based on a pose model and at least a portion the frame, wherein the pose model is determined based on different possible appearances of the object;

(c) determining an alignment confidence score based on an alignment model and at least a portion the frame, wherein the alignment model detects misalignments of the tracked object;

(d) determining an energy value based on the adaptive term value, the pose constraint value, and the alignment confidence score; and

(e) determining a resultant tracking state based on the energy value, the resultant tracking state defining a likely position of the object in the frame given the object'"'"'s likely position in a set of previous frames in the video.

2. The computer-implemented method of claim 1, further comprising:

(f) determining a cropped object image L based on at least a portion of the frame, the portion defined by a tracking state u_t,

wherein the determining (b) comprises applying the pose model to the cropped object image I_t to determine the pose constraint value.

3. The computer-implemented method of claim 2, wherein the determining (c) comprises applying the alignment model to the cropped object image I_t to determine the alignment constraint value.

4. The computer-implemented method of claim 3, further comprising:

(g) constructing a set of pose subspaces,

wherein the determining (b) further comprises determining the pose constraint value, wherein the pose constraint value is a minimum pose distance between the cropped object image I_t and each pose subspace in the set of pose subspaces.

5. The computer-implemented method of claim 3, further comprising:

(g) training a classifier function,

wherein the determining (c) further comprises applying the classifier function to the cropped object image I_t to determine the alignment confidence score.

6. The computer-implemented method of claim 3, wherein the determining (d) comprises determining the energy value, wherein the energy value satisfies an equation:

E(I_t)=λ

_ad(I_t,M_a(I_{0 . . . t-1}))+λ

_pd(I_t,M_p)−

λ

_sf_s(I_t),

wherein E(I_t) is the energy value,

wherein d(I_t, M_P) is the pose constraint value,

wherein f_s(I_t) is the alignment confidence score,

wherein d(I_t, M_a(I_{0 . . . t-1})) is the adaptive term value, and

wherein λ

_a, λ

_p and λ

_s are contribution factors that are greater than zero.

7. The computer-implemented method of claim 3, further comprising:

(g) determining an emission probability based on the energy value;

(h) determining a transition probability; and

(i) determining a tracking probability based on the emission probability and the transition probability,

wherein the determining (e) comprises determining the resultant tracking state based on the tracking probability.

8. The computer-implemented method of claim 7, wherein the determining (g) comprises determining the emission probability, wherein the emission probability is a probability of receiving the frame given the tracking state u_t,

wherein the determining (h) comprises determining the transition probability, wherein the transition probability is a probability of the portion of the frame defined by the tracking state u_t including the object given a tracking state u_t-1, wherein the tracking state u_t-1 defines a portion of a previous frame F_t-1 that likely includes the object, and

wherein the determining (i) comprises determining the tracking probability, wherein the tracking probability is a probability of the portion of the frame defined by the tracking state u_t including the object given a sequence of previous frames in the sequence of frames.

9. The computer-implemented method of claim 7, wherein the determining (g) comprises determining the emission probability using a Gibbs energy function.

10. The computer-implemented method of claim 1, wherein the determining (e) comprises determining the resultant tracking state, the resultant tracking state defining a likely position of a face in the frame.

11. The computer-implemented method of claim 10, further comprising:

(f) applying a face recognition algorithm to the portion of the frame defined by the resultant tracking state to determine an identity of the face.

12. The computer-implemented method of claim 11, wherein the applying (f) comprises modeling a facial pose as a hidden state in a hidden Markov model.

13. A system for tracking an object in a frame of a video, comprising:

a pose constraint module that determines a pose constraint value based on a pose model and at least a portion the frame;

an alignment constraint module that determines an alignment confidence score based on an alignment model and at least a portion the frame;

an adaptive module that determines an adaptive term value based on an adaptive model and at least a portion of a frame in the video;

a visual constrainer that determines an energy value based on the adaptive term value, the pose constraint value, and the alignment confidence score; and

a tracker that determines a resultant tracking state based on the energy value, the resultant tracking state defining a likely position of the object in the frame given the object'"'"'s likely position in a set of previous frames in the video,

wherein the adaptive model is determined based on at least one previous frame of the video,

wherein the pose model is determined based on different possible appearances of the object, and

wherein the alignment model detects misalignments of the tracked object.

14. The system of claim 13, wherein the visual constrainer determines a cropped face image I_t according to the portion of the frame defined by the tracking state u_t, and

wherein the pose constraint module applies a pose constraint to the cropped face image I_t to determine the pose constraint value.

15. The system of claim 14, wherein the alignment constraint module applies an alignment constraint to the cropped face image I_t to determine the alignment confidence score.

16. The system of claim 15, wherein the visual constrainer constructs a set of pose subspaces, and wherein the pose constraint value is a minimum pose distance between the cropped face image I_t and each pose in the set of pose subspaces.

17. The system of claim 16, wherein the visual constrainer trains a classifier function, and

wherein the alignment constraint module applies the classifier function to the cropped face image I_t to determine an alignment confidence score.

18. The system of claim 15, wherein the visual constrainer determines the energy value, wherein the energy value satisfies an equation:

E(I_t)=λ

_ad(I_t,M_a(I_{0 . . . t-1}))+λ

_pd(I_t,M_p)−

λ

_sf_s(I_t),

wherein E(I_t) is the energy value,

wherein d(I_t, M_P) is the pose constraint value,

wherein f_s(I_t) is the alignment confidence score,

wherein d(I_t, M_a(I_{0 . . . t-1})) is the adaptive term value, and

wherein λ

_a, λ

_p and λ

_s are contribution factors that are greater than zero.

19. The system of claim 15, wherein the tracker determines an emission probability based on the energy value, determines a transition probability, determines a tracking probability based on the emission probability and the transition probability and determines the resultant tracking state based on the tracking probability.

20. The system of claim 19, wherein the emission probability is a probability of receiving the frame given the tracking state u_t,

wherein the transition probability is a probability of the portion of the frame defined by the tracking state u_t including the object given a tracking state u_t-1, wherein the tracking state u_t-1 defines a portion of a previous frame F_t-1 that likely includes the face, and

wherein the tracking probability is a probability of the portion of the frame defined by the tracking state u_t including the object given a sequence of previous frames in the sequence of frames.

21. The system of claim 13, wherein the tracker determines the emission probability using a Gibbs energy function.

22. The system of claim 13, wherein the object is a face.

23. The system of claim 22, further comprising:

a object recognizer that applies a face recognition algorithm to the portion of the frame defined by the resultant tracking state to determine an identity of the face.

24. The system of claim 23, wherein the object recognizer models a facial pose as a hidden state in a hidden Markov model.