Method and system for detecting and tracking shopping carts from videos

• US 8,325,982 B1
• Filed: 07/23/2009
• Issued: 12/04/2012
• Est. Priority Date: 07/23/2009
• Status: Active Grant

• Current Assignee: Videomining Corporation
• Original Assignee: Videomining Corporation
• Inventors: Moon, Hankyu, Sharma, Rajeev, Jung, Namsoon
• Primary Examiner(s): Tabatabai, Abolfazl
• Application Number:
  US12/460,818
• Time in Patent Office: 1,230 Days
• Field of Search: 382/103, 382/104, 382/107, 382/236, 348/169, 348/170, 348/171, 348/172, 348/285.1, 348/208.2, 348/208.14, 348/352, 348/94, 348/154, 348/155, 348/208.1, 348/208.16, 348/347
• US Class Current: 382/103
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: G06V 10/25 Determination of region of interest [ROI] or a volume of interest [VOI]
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

Abstract

The present invention is a method and system for detecting and tracking shopping carts from video images in a retail environment. First, motion blobs are detected and tracked from the video frames. Then these motion blobs are examined to determine whether or not some of them contain carts, based on the presence or absence of linear edge motion. Linear edges are detected within consecutive video frames, and their estimated motions vote for the presence of a cart. The motion blobs receiving enough votes are classified as cart candidate blobs. A more elaborate model of passive motions within blobs containing a cart is constructed. The detected cart candidate blob is then analyzed based on the constructed passive object motion model to verify whether or not the blob indeed shows the characteristic passive motion of a person pushing a cart. Then the finally-detected carts are corresponded across the video frames to generate cart tracks.

Claims

1. A method for detecting and tracking shopping carts, utilizing a position-dependent cart shape and motion model based on video images, comprising the following steps of:

a) detecting and tracking motion blobs from the video images, wherein pixels within the same motion blob go through the same motion,

b) detecting presence of carts within the detected motion blobs by collecting evidence from motions of pixels within the detected motion blobs,

c) constructing a motion model of carts that characterizes the motion of passive objects pushed by humans,

d) extracting motion features that characterize the motion of passive object by constructing a histogram of relative motions among points within the motion blobs,

e) verifying presence of carts in the detected motion blobs based on the motion model of carts, and

f) tracking the verified carts so that their individual identities can be maintained across the video images,

wherein the histogram captures characteristic rigid motion of a cart and passive motion of the cart relative to a person pushing the cart.

2. The method according to claim 1, wherein the method further comprises a step of detecting the motion blobs by detecting and aggregating motion foreground pixels according to the proximities among the motion foreground pixels.

3. The method according to claim 1, wherein the method further comprises a step of detecting the presence of carts by testing each hypothesis about cart presence at a certain position and orientation,

wherein the hypotheses about cart positions and orientations are determined by the positions and motions of the detected motion blobs.

4. The method according to claim 1, wherein the method further comprises a step of collecting the evidence by finding linear edges in the motion blobs that are moving and by collecting votes from the linear edges.

5. The method according to claim 1, wherein the method further comprises a step of constructing the motion model of carts by estimating a distribution of the motion features within the motion blobs that contain carts.

6. The method according to claim 5, wherein the method further comprises a step of constructing the motion model of carts by estimating a distribution of the motion features within the motion blobs that only contain humans.

7. The method according to claim 1, wherein the method further comprises a step of tracking the verified carts by maintaining and updating a list of cart tracks,

wherein the matches between the detected carts and the cart tracks in the list of cart tracks are found by comparing positions and orientations of the verified carts and the position and orientation of the last cart in each list of cart tracks.

8. The method according to claim 7, wherein the method further comprises a step of maintaining the presence of carts that are not in motion by detecting the presence of human figures near the carts.

9. An apparatus for detecting and tracking shopping carts, utilizing a position-dependent cart shape and motion model based on video images, comprising:

a) means for detecting and tracking motion blobs from the video images, wherein pixels within the same motion blob go through the same motion,

b) means for detecting presence of carts within the detected motion blobs by collecting evidence from motions of pixels within the detected motion blobs,

c) means for constructing a motion model of carts that characterizes the motion of passive objects pushed by humans,

d) means for extracting motion features that characterize the motion of passive object by constructing a histogram of relative motions among points within the motion blobs,

e) means for verifying presence of carts in the detected motion blobs based on the motion model of carts, and

f) means for tracking the verified carts so that their individual identities can be maintained across the video images,

wherein the histogram captures characteristic rigid motion of a cart and passive motion of the cart relative to a person pushing the cart.

10. The apparatus according to claim 9, wherein the apparatus further comprises means for detecting the motion blobs by detecting and aggregating motion foreground pixels according to the proximities among the motion foreground pixels.

11. The apparatus according to claim 9, wherein the apparatus further comprises means for detecting the presence of carts by testing each hypothesis about cart presence at a certain position and orientation,

wherein the hypotheses about cart positions and orientations are determined by the positions and motions of the detected motion blobs.

12. The apparatus according to claim 9, wherein the apparatus further comprises means for collecting the evidence by finding linear edges in the motion blobs that are moving and by collecting votes from the linear edges.

13. The apparatus according to claim 9, wherein the apparatus further comprises means for constructing the motion model of carts by estimating a distribution of the motion features within the motion blobs that contain carts.

14. The apparatus according to claim 13, wherein the apparatus further comprises means for constructing the motion model of carts by estimating a distribution of the motion features within the motion blobs that only contain humans.

15. The apparatus according to claim 9, wherein the apparatus further comprises means for tracking the verified carts by maintaining and updating a list of cart tracks,

wherein the matches between the detected carts and the cart tracks in the list of cart tracks are found by comparing positions and orientations of the verified carts and the position and orientation of the last cart in each list of cart tracks.

16. The apparatus according to claim 15, wherein the apparatus further comprises means for maintaining presence of carts that are not in motion by detecting presence of human figures near the carts.