Self correcting tracking of moving objects in video

• US 7,983,448 B1
• Filed: 05/24/2007
• Issued: 07/19/2011
• Est. Priority Date: 06/02/2006
• Status: Expired due to Fees

• Current Assignee: University of Central Florida Research Foundation Inc. (State University System of Florida)
• Original Assignee: University of Central Florida Research Foundation Inc. (State University System of Florida)
• Inventors: Caglar, Mehmet B, da Vitoria Lobo, Niels
• Primary Examiner(s): Bella; Matthew C
• Assistant Examiner(s): Newman; Michael A
• Application Number:
  US11/753,233
• Time in Patent Office: 1,517 Days
• Field of Search: 382/103, 382/107, 382/190, 382/199, 382/224, 382/225, 382/226, 382/227
• US Class Current: 382/103
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 7/251 involving models
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 40/113 Recognition of static hand signs
• CPC Class Codes: G06V 40/28 Recognition of hand or arm movements, e.g. recognition of deaf sign language static hand signs G06V40/113

Abstract

Apparatus, methods, systems and devices for identifying and tracking a human hand in a video. The steps for identifying the hand includes detecting parallel lines (bars), detecting curved fingertips (curves), grouping the detected parallel lines and curved fingertips according to a parallel line decision tree and a curved fingertip decision tree, respectively, and merging the parallel line group and the curved fingertip group to identify candidate hands.

Claims

1. A method for detection and tracking of a moving object comprises the steps of:

detecting at least two primitive classes for identifying the moving object within plural frames of video to generate plural primitive candidates for each class by

detecting plural primitive candidates for each of the at least two primitive classes;

extracting a primitive model of each of the at least two primitive classes;

superimposing the primitive model on each primitive candidate; and

determining which primitive candidate is a primitive;

grouping each detected primitive candidates in each class separately according to a decision tree corresponding to each primitive class;

training the decision tree corresponding to the primitive class;

merging primitive groups for each class of primitives to identify the object being tracked; and

tracking the moving object through the plural frames of video according to the merged primitive groups.

2. The method of claim 1, wherein the grouping step comprises the steps of:

creating one group for each detected primitive in each class to generate plural groups of primitive candidates for each of the at least two primitive classes using the decision tree that is trained corresponding to the primitive class;

determining group membership of each of the plural groups from the plural primitive candidates detected in the detecting step;

voting to eliminate primitive groups based on voting results; and

eliminating subset groups and small groups to reduce false primitive positives, wherein the grouping step yields primitive candidate locations for each primitive class.

3. The method of claim 2, wherein the creating one group for each detected primitive candidate_step comprises the step of:

forming N groups when there are N primitives detected for a given primitive class, wherein each detected primitive is a representative of a different primitive group.

4. The method of claim 1, wherein the primitive group merging step comprises the steps of:

merging primitive groups of a first class with primitive groups of a second class; and

determining which merged first and second class groups include the object.

5. The method of claim 1, wherein tracking the object through the plural frames of video comprises the steps of:

tracking the moving object forward and backward through each of plural sets of video frames to obtain plural trajectories of the object;

recording each of the plural trajectories;

merging the plural trajectories;

assigning weights to each of the merged trajectories;

generating a trajectory histogram from the merged trajectories; and

extracting and separating the moving object from the trajectory histogram.

6. A system for identifying and tracking a human hand in a video comprising:

a video device for generating plural frames of video;

a processor for executing instructions;

a set of detecting instructions for detecting the human hand in the video comprising;

a parallel line set of instructions for detecting parallel line primitives;

a curved fingertip set of instructions for detecting curved fingertip primitives;

a grouping set of instructions for grouping the plural detected parallel line primitives and plural curved fingertip primitives according to a parallel line decision tree and a curved fingertip decision tree, respectively; and

a merging set of instructions for merging the parallel line groups and the curved fingertip groups to identify candidate hands; and

a set of tracking instructions for tracking the human hand through the plural frames of video.

7. The system of claim 6, wherein the parallel line set of instructions for detecting parallel lines comprises:

a first subset of parallel line instructions for detecting plural lines in an image;

a second subset of parallel line instructions for determining if two of the plural lines are parallel to generate plural pairs of parallel lines;

a third subset of parallel line instructions for determining plural properties of each pair of parallel lines; and

a fourth subset of parallel line instructions for eliminating pairs of parallel lines that are not candidates for fingers according to the plural properties.

8. The system of claim 6, wherein the curved fingertip set of instructions for detecting curved fingertips comprises:

a first subset of curved fingertip instructions for extracting a model edge from a fingertip model;

a second subset of curved fingertip instructions for grouping together neighboring pixels having a same orientation for each fingertip group;

a third subset of curved fingertip instructions for marking a middle point of each curved fingertip group as a fingertip top candidate;

a fourth subset of curved fingertip instructions for superimposing the fingertip model on each fingertip top candidate in the image;

a fifth subset of curved fingertip instructions for scaling each fingertip model;

a sixth subset of curved fingertip instructions for matching each fingertip top candidate to the scaled fingertip model; and

a seventh subset of curved fingertip instructions for marking each fingertip top candidate as a fingertip when the matching to the superimposed fingertip model surpasses a threshold.

9. The system of claim 6, wherein the grouping set of instructions for grouping the plural detected parallel lines and plural curved fingertips comprises:

a first subset of grouping instruction for creating one group for each detected parallel line and each detected curved fingertip to generate plural parallel line groups and plural curved fingertip groups;

a second subset of grouping instruction for determining group membership of each of the plural parallel line groups and plural curved fingertip groups according to the parallel line decision tree and the curved fingertip decision tree, respectively;

a third subset of grouping instruction for voting to eliminate parallel line groups and curved fingertip groups based on voting results; and

a fourth subset of grouping instruction for eliminating subset groups and small groups to reduce false primitive positives, wherein the grouping step yields parallel line candidate locations and curved fingertip candidate locations.

10. The system of claim 6, wherein the merging set of instructions for merging the parallel line group and the curved fingertip groups to identify candidate hands comprises:

a first subset of merging instructions for detecting intersections between the merged parallel line groups and curved fingertip groups; and

a second subset of merging instructions for determining which intersecting parallel line groups and fingertip groups are finger candidates.

11. The system of claim 6, wherein the tracking set of instructions for tracking the detected human hand comprises:

a first subset of tracking instruction for tracking the human hand forward and backward through each of plural sets of video frames to obtain plural trajectories of the human hand;

a second subset of tracking instruction for recording each of the plural trajectories;

a third subset of tracking instruction for merging the plural trajectories;

a fourth subset of tracking instruction for assigning a weight to each of the merged trajectories;

a fifth subset of tracking instruction for generating a trajectory histogram from the weighted trajectories; and

a sixth subset of tracking instruction for extracting and separating the human hands from the trajectory histogram.

12. The system of claim 6, further comprising:

a set of object detection instructions for detecting an object carried in one of the detected human hands.

13. The system of claim 12, further comprising:

a set of object tracking instructions for tracking a transfer of the detected object from one detected human hand to another detected human hand.

14. A method for detection and tracking of moving hands in a video comprises the steps of:

detecting parallel line primitives in plural frames of the video to generate plural parallel line primitives by detecting plural lines in an image;

determining when two of the plural lines are parallel to generate plural pairs of parallel lines;

determining plural properties of each pair of parallel lines; and

eliminating pairs of parallel lines that are not candidates for fingers according to the properties;

detecting curved fingertip primitives in plural frames of the video to generate plural curved fingertip primitives;

grouping each parallel line primitives according to a parallel line decision tree;

grouping each curved fingertip primitive according to a curved fingertip decision tree; and

merging parallel line groups and curved fingertip groups to identify the moving hand; and

tracking the moving hand through the plural frames of video according to the merged primitive groups.

15. The method of claim 14, wherein the detecting curved fingertip primitives step comprises the step of:

extracting a model edge from a fingertip model;

grouping together neighboring pixels having a same directional orientation for each curved fingertip group;

marking a middle point of each pixel group as a fingertip top candidate;

superimposing the fingertip model on each fingertip top candidate in the image;

scaling each fingertip model along at least one fingertip model dimension;

comparing each fingertip top candidate to the scaled fingertip model; and

marking each fingertip top candidate as a fingertip when the comparison of the scaled superimposed fingertip model with the fingertip top candidate surpasses a threshold.

16. The method of claim 14, wherein the merging step further comprises the steps of:

detecting intersections between the merged parallel line groups and merged curved fingertip groups; and

determining which intersecting parallel line groups and curved fingertip groups are a finger.

17. The method of claim 14, further comprising the steps of:

detecting an object in one of the hands;

dividing the video into intervals of 5 frames or longer;

determining the object velocity during each interval;

comparing the object velocity to each hand velocity to determine which hand is more likely to carry the object; and

marking one of the 5 or more frames as an exchange of the object when the object changes hands in the frame.

18. The method of claim 17, wherein the tracking step comprises the step of:

tracking the object forward and backward through each of plural sets of video frames to obtain plural trajectories of the object;

recording each of the plural trajectories;

merging the plural trajectories;

assigning weights to each of the merged trajectories;

generating a trajectory histogram from the merged trajectories; and

extracting and separating the hands from the trajectory histogram.

19. The method of claim 18, further comprising the steps of:

(a) determining how many hands are detected in each set of video frames;

(b) when two hands are detected,

determining if the two hands interact;

(c) when two hands are interacting,

determining if the two hands are shaking; and

determining if an object is detected or object is being exchanged;

(d) when one hand is detected,

determining if the one detected hand includes the object;

(d) when the object is detected with the hand;

determining if the hand is moving the object;

determining if the hand is putting the object down; and

repeating step (d) when the object is put down;

(e) when the object is not detected with the hand; and

determining when the object is picked up by the hand; and

going to step (d) when the object is picked up;

repeating steps (a) through (e) for a next set of video frames.