Volume-based coverage analysis for sensor placement in 3D environments

• US 8,442,306 B2
• Filed: 08/13/2010
• Issued: 05/14/2013
• Est. Priority Date: 08/13/2010
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Garaas, Tyler W., Sullivan, Alan
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US12/856,475
• Publication Number:
  US 20120039526A1
• Time in Patent Office: 1,005 Days
• Field of Search: 382/154, 382/285, 345419-427, 356 12- 14, 348 42- 60, 348143-160
• US Class Current: 382/154
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G08B 13/19641 Multiple cameras having overlapping views on a single scene

Abstract

Coverage of sensors in a CTV system in a three-dimensional environment are analyzed by partitioning a 3D model of the environment into a set of voxels. A ray is cast from each pixel in each sensor through the 3D model to determine coverage data for each voxel. The coverage data are analyzed to determine a result indicative of an effective arrangement of the set of sensors.

Claims

1. A method for analyzing coverage of a three-dimensional environment by a set of sensors, comprising the steps of:

partitioning a 3D model of the environment into a set of voxels, wherein each voxel represents a portion of the environment; and

casting a ray from each pixel in each sensor through the set of voxels of the 3D model to determine locations in the environment that can be sensed by the set of sensors to produce coverage data for each voxel, wherein the coverage data includes an identity of each sensor, a number of rays cast through each voxel, and angles from which each voxel can be sensed by the set of sensors; and

analyzing the coverage data to determine a result indicative of an effective arrangement of the set of sensors, and wherein description of the environment, the voxels and the coverage data are three dimensional, and the steps are performed in a processor.

2. The method of claim 1, the set of sensors includes cameras, charge-coupled sensors, complementary metal-oxide-semiconductor sensors, lasers sensors, ranging sensors, passive infrared sensors, or ultrasound transducers.

3. The method of claim 1, further comprising:

visualizing the result.

4. The method of claim 1, further comprising:

simulating the result.

5. The method of claim 1, further comprising:

ranking the result.

6. The method of claim 1, wherein the environment is indoors, and the description of the environment indicates floors, ceilings, walls, halls, doorways, and static objects.

7. The method of claim 1, wherein the environment is outdoors, and the description of the environment includes buildings, bridges, and streets.

8. The method of claim 1, wherein the voxels are uniformly sized voxels and arranged in a regular 3D grid.

9. The method of claim 1, wherein the partitioning is according to

10. The method of claim 1, further comprising:

rendering a distance into a depth buffer associated with each sensor to 3D determine locations of intersections between the corresponding ray and the set of voxels, wherein the distance is from each pixel in each sensor along each ray to a point of intersection with the 3D model.

11. The method of claim 1, wherein the description of the environment uses world coordinates, and the set of pixels uses window coordinates, and further comprising:

multiplying window coordinates of the pixel along with the distances by an inverse modeling matrix that converts the world coordinates to the windows coordinates.

12. The method of claim 1, wherein each ray has an origin, a direction, and a length.

13. The method of claim 3, wherein properties of the visualization comprise any of the following, color, intensity, translucency, or voxel size, or combinations thereof.

14. The method of claim 1, further comprising:

normalizing the coverage data.

15. The method of claim 3, wherein the visualizing is a raw visualization.

16. The method of claim 3, wherein the visualizing is a volumetric visualization.

17. The method of claim 3, wherein the visualizing is a projective visualization.

18. The method of claim 3, further comprising:

downsampling the coverage data before the visualizing.

19. A method for analyzing coverage of a three-dimensional environment by a set of sensors, comprising the steps of:

partitioning a 3D model of the environment into a set of voxels, wherein each voxel represents a portion of the environment, wherein the partitioning is according to

20. The method of claim 19, wherein the constructing accounts for occlusions by subtracting shadow volumes from the description of the field of view.