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

• US 20050025341A1
• Filed: 06/14/2004
• Published: 02/03/2005
• Est. Priority Date: 06/12/2003
• Status: Active Grant

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company), Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Gonzalez-Banos, Hector H., Guibas, Leonidas J., Yang, Danny B.
• Granted Patent: US 6,987,885 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• 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 objects in a working volume, the method comprising:

determining a first set of one or more polygons by intersecting a first plurality of planar projections of three-dimensional shapes, the three-dimensional shapes being intersections of silhouette cones and the working volume; and

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

2. The method of claim 1, wherein intersecting the first plurality of planar projections of silhouette cones of the working volume comprises pixelating a planar projection of a silhouette cone of the working volume.

3. The method of claim 2, wherein pixelating the planar projection of the silhouette cone of the working volume comprises using hardware to pixelate the planar projection of the silhouette cone of the working volume.

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

5. 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 polygon.

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

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

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

9. The method of claim 1, further comprising:

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

determining a second set of one or more polygons by intersecting a second plurality of planar projections of three-dimensional shapes, the three-dimensional shapes being intersections of silhouette cones and the working volume; and

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

10. The method of claim 9, wherein intersecting the second plurality of planar projections of silhouette cones of the working volume comprises pixelating a planar projection of a silhouette cone of the working volume.

11. The method of claim 10, wherein pixelating the planar projection of the silhouette cone of the working volume comprises using hardware to pixelate the planar projection of the silhouette cone of the working volume.

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

13. The method of claim 9, 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 polygon.

14. The method of claim 9, further comprising removing one or more polygons from the second set of one or more polygons, responsive to determining that the one or more polygons contains no objects.

15. The method of claim 9, further comprising determining a second set of one or more upper bounds, an upper bound being associated with a polygon in the second set of one or more polygons, an upper bound being a highest number of objects that can be contained in the associated polygon.

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

17. The method of claim 9, further comprising updating the data structure.

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

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

20. The method of claim 18, wherein a node of the tree data structure comprises an upper bound of the associated polygon.

21. The method of claim 18, wherein updating the data structure comprises:

adding nodes to the data structure;

removing redundant nodes from the data structure; and

updating nodes in the data structure.

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

means for determining a first set of one or more polygons by intersecting a first plurality of planar projections of three-dimensional shapes, the three-dimensional shapes being intersections of silhouette cones and the working volume; and

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

23. The system of claim 22, wherein intersecting the first plurality of planar projections of silhouette cones of the working volume comprises pixelating a planar projection of a silhouette cone of the working volume.

24. The system of claim 23, wherein pixelating the planar projection of the silhouette cone of the working volume comprises using hardware to pixelate the planar projection of the silhouette cone of the working volume.

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

26. The system of claim 22, wherein 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 polygon.

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

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

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

30. The system of claim 22, further comprising:

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

means for determining a second set of one or more polygons by intersecting a second plurality of planar projections of three-dimensional shapes, the three-dimensional shapes being intersections of silhouette cones and the working volume; and

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

31. The system of claim 30, wherein intersecting the second plurality of planar projections of silhouette cones of the working volume comprises pixelating a planar projection of a silhouette cone of the working volume.

32. The system of claim 31, wherein pixelating the planar projection of the silhouette cone of the working volume comprises using hardware to pixelate the planar projection of the silhouette cone of the working volume.

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

34. The system of claim 30, wherein 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 polygon.

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

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

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

38. The system of claim 30, 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 polygon in the first set of one or more polygons.

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

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

42. The system of claim 39, wherein means for updating the data structure comprises:

means for adding nodes to the data structure;

means for removing redundant nodes from the data structure; and

means for updating nodes in the data structure.