Volume-Based Coverage Analysis for Sensor Placement in 3D Environments

• US 20120039526A1
• Filed: 08/13/2010
• Published: 02/16/2012
• 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: Sullivan, Alan, Garaas, Tyler W.
• Granted Patent: US 8,442,306 B2
• Time in Patent Office: Days
• 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 3D model to determine coverage data for each voxel; and

analyzing the coverage data to determine a result indicative of an effective arrangement of the set of sensors, and wherein the 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 determining further comprising:

casting a ray from each pixel in each sensor through the set of voxels to determine locations in the environment that can be sensed by the set of sensors.

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

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

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

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

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

12. The method of claim 6, 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.

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

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

16. The method of claim 1, further comprising:

normalizing the coverage data.

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

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

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

20. The method of claim 3, further comprising:

downsampling the coverage data before the visualizing.

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

21. 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

constructing a description of the field of view for each sensor; and

projecting the descriptions of the field of view through the set of voxels to determine 3D coverage data; and

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

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