Systems and methods for using visual hulls to determine the number of people in a crowd

• US 6,987,885 B2
• Filed: 06/14/2004
• Issued: 01/17/2006
• Est. Priority Date: 06/12/2003
• Status: Expired due to Fees

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company), Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Gonzalez-Banos, Hector H., Guibas, Leonidas J., Yang, Danny B.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Lu, Tom Y.
• Application Number:
  US10/868,639
• Publication Number:
  US 20050025341A1
• Time in Patent Office: 582 Days
• Field of Search: 382103-104, 382/141, 382/192, 382/115, 382/154, 382173-180, 382/190, 340/573.1, 348/169
• US Class Current: 382/192
• CPC Class Codes: G06V 20/53 Recognition of crowd images, e.g. recognition of crowd congestion

Abstract

Systems, apparatuses, and methods are presented that determine the number of people in a crowd using visual hull information. In one embodiment, an image sensor generates a conventional image of a crowd. A silhouette image is then determined based on the conventional image. The intersection of the silhouette image cone and a working volume is determined. The projection of the intersection onto a plane is determined. Planar projections from several image sensors are aggregated by intersecting them, forming a subdivision pattern. Polygons that are actually empty are identified and removed. Upper and lower bounds of the number of people in each polygon are determined and stored in a tree data structure. This tree is updated as time passes and new information is received from image sensors. The number of people in the crowd is equal to the lower bound of the root node of the tree.

Claims

1. A method for determining the number of a plurality of objects in a working volume, the method comprising:

determining a first planar projection of a first visual hull of the plurality of objects, the planar projection comprising a first set of one or more shapes; and

determining a first set of one or more lower bounds, a lower bound being associated with a shape in the first set of one or more shapes, a lower bound being a lowest number of objects that can be contained in the associated shape.

2. The method of claim 1, wherein determining the first planar projection of the first visual hull of the plurality of objects comprises intersecting a plurality of planar projections of three-dimensional shapes.

3. The method of claim 2, wherein intersecting the plurality of planar projections of three-dimensional shapes comprises pixelating a planar projection of a three-dimensional shape.

4. The method of claim 3, wherein pixelating the planar projection of the three-dimensional shape comprises using hardware to pixelate the planar projection of the three-dimensional shape.

5. The method of claim 2, wherein a three-dimensional shape is an intersection of the working volume and a silhouette cone of an object.

6. The method of claim 2, wherein a three-dimensional shape is an intersection of the working volume and a silhouette cone of an object.

7. The method of claim 1, wherein the working volume does not contain all objects completely.

8. The method of claim 1, wherein determining the first set of one or more lower bounds comprises determining whether a ray exists that extends along a silhouette cone and intersects only one shape.

9. The method of claim 1, further comprising removing one or more shapes from the first set of one or more shapes, responsive to determining that the one or more shapes contains no objects.

10. The method of claim 1, further comprising determining a first set of one or more upper bounds, an upper bound being associated with a shape in the first set of one or more shapes, an upper bound being a highest number of objects that can be contained in the associated shape.

11. The method of claim 10, wherein determining the first set of one or more upper bounds comprises dividing the area of a shape by a minimum object size.

12. The method of claim 1, further comprising:

storing the first set of one or more lower bounds in a data structure;

determining a second planar projection of a second visual hull of the plurality of objects, the second planar projection comprising a second set of one or more shapes; and

determining a second set of one or more lower bounds, a lower bound being associated with a shape in the second set of one or more shapes, a lower bound being a lowest number of objects that can be contained in the associated shape.

13. The method of claim 12, wherein the working volume does not contain all objects completely.

14. The method of claim 12, wherein determining the second set of one or more lower bounds comprises determining whether a ray exists that extends along a silhouette cone and intersects only one shape.

15. The method of claim 12, further comprising removing one or more shapes from the second set of one or more shapes, responsive to determining that the one or more shapes contains no objects.

16. The method of claim 12, further comprising determining a second set of one or more upper bounds, an upper bound being associated with a shape in the second set of one or more shapes, an upper bound being a highest number of objects that can be contained in the associated shape.

17. The method of claim 16, wherein determining the second set of one or more upper bounds comprises dividing the area of a shape by a minimum object size.

18. The method of claim 12, further comprising updating the data structure.

19. The method of claim 18, wherein the data structure comprises a tree data structure, a node of the tree data structure being associated with a shape in the first set of one or more shapes.

20. The method of claim 19, wherein a node of the tree data structure comprises a lower bound of the associated shape.

21. The method of claim 19, wherein anode of the tree data structure comprises an upper bound of the associated shape.

22. The method of claim 19, wherein updating the data structure comprises one element of a group containing:

adding a node to the data structure;

removing a node from the data structure; and

updating a node in the data structure.

23. A system for determining the number of a plurality of objects in a working volume, the system comprising:

means for determining a first planar projection of a first visual hull of the plurality of objects, the planar projection comprising a first set of one or more shapes; and

means for determining a first set of one or more lower bounds, a lower bound being associated with a shape in the first set of one or more shapes, a lower bound being a lowest number of objects that can be contained in the associated shape.

24. The system of claim 23, wherein the means for determining the first planar projection of the first visual hull of the plurality of objects comprises means for intersecting a plurality of planar projections of three-dimensional shapes.

25. The system of claim 24, wherein intersecting the plurality of planar projections of three-dimensional shapes comprises pixelating a planar projection of a three-dimensional shape.

26. The system of claim 25, wherein pixelating the planar projection of the three-dimensional shape comprises using hardware to pixelate the planar projection of the three-dimensional shape.

27. The system of claim 23, wherein the working volume does not contain all objects completely.

28. The system of claim 23, wherein the means for determining the first set of one or more lower bounds comprises means for determining whether a ray exists that extends along a silhouette cone and intersects only one shape.

29. The system of claim 23, further comprising means for removing one or more shapes from the first set of one or more shapes, responsive to determining that the one or more shapes contains no objects.

30. The system of claim 23, further comprising means for determining a first set of one or more upper bounds, an upper bound being associated with a shape in the first set of one or more shapes, an upper bound being a highest number of objects that can be contained in the associated shape.

31. The system of claim 30, wherein the means for determining the first set of one or more upper bounds comprises means for dividing the area of a shape by a minimum object size.

32. The system of claim 23, further comprising:

means for storing the first set of one or more lower bounds in a data structure;

means for determining a second planar projection of a second visual hull of the plurality of objects, the second planar projection comprising a second set of one or more shapes; and

means for determining a second set of one or more lower bounds, a lower bound being associated with a shape in the second set of one or more shapes, a lower bound being a lowest number of objects that can be contained in the associated shape.

33. The system of claim 32, wherein the working volume does not contain all objects completely.

34. The system of claim 32, wherein the means for determining the second set of one or more lower bounds comprises means for determining whether a ray exists that extends along a silhouette cone and intersects only one shape.

35. The system of claim 32, further comprising means for removing one or more shapes from the second set of one or more shapes, responsive to determining that the one or more shapes contains no objects.

36. The system of claim 32, further comprising means for determining a second set of one or more upper bounds, an upper bound being associated with a shape in the second set of one or more shapes, an upper bound being a highest number of objects that can be contained in the associated shape.

37. The system of claim 36, wherein the means for determining the second set of one or more upper bounds comprises means for dividing the area of a shape by a minimum object size.

38. The system of claim 32, further comprising means for updating the data structure.

39. The system of claim 38, wherein the data structure comprises a tree data structure, a node of the tree data structure being associated with a shape in the first set of one or more shapes.

40. The system of claim 39, wherein a node of the free data structure comprises a lower bound of the associated shape.

41. The system of claim 39, wherein a node of the tree data structure comprises an upper bound of the associated shape.

42. The system of claim 39, wherein the means for updating the data structure comprises one element of a group containing:

means for adding a node to the data structure;

means for removing a node from the data structure; and

means for updating a node in the data structure.