System and method for forming optimized perimeter surveillance

• US 8,370,111 B2
• Filed: 03/27/2009
• Issued: 02/05/2013
• Est. Priority Date: 03/31/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Mattikalli, Raju S., Grube, Robert W., Thunemann, Paul Z.
• Primary Examiner(s): Barbee, Manuel L
• Application Number:
  US12/412,800
• Publication Number:
  US 20100106420A1
• Time in Patent Office: 1,411 Days
• Field of Search: 702/2, 702/5, 702/94, 702/95, 702/127, 702150-152, 702/188, 340/541, 340551-562, 340565-567, 340/686.1, 348/143, 348/152
• US Class Current: 702/188
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G08B 13/183 by interruption of a radiation beam or barrier
• CPC Class Codes: G08B 13/196 using television cameras

Abstract

A method for forming a virtual tripwire through a subregion of an area of interest. The method may involve performing a geometric analysis of terrain in the subregion, the geometric analysis determining a location for each one of a pre-designated plurality of candidate sensors that may potentially be used in forming the virtual tripwire. A viewshed for each candidate sensor is determined. Each viewshed represents a coverage region for its associated candidate sensor. A geometric beginning point and a geometric end point within the subregion are each defined for the virtual tripwire. The viewsheds are analyzed to determine a number of the candidate sensors required to form a path for the virtual tripwire from the beginning point to the end point.

Claims

1. A method, implemented using a computer, for forming a virtual tripwire through a subregion of an area of interest, the method comprising:

using geographic information system to perform a geometric analysis of terrain in said subregion, said geometric analysis determining a location within the subregion for each one of a pre-designated plurality of candidate sensors that may potentially be used in forming said virtual tripwire, and a viewshed for each said candidate sensor, each said viewshed representing a coverage region for its associated said candidate sensor;

defining a geometric beginning point and a geometric end point within the subregion for said virtual tripwire;

defining a maximum distance for one or more gaps that are allowed to exist along said virtual tripwire; and

using the computer to analyze said viewsheds to initially determine a minimum number of said candidate sensors required to form a path for said virtual tripwire from said beginning point to said end point, and which also satisfies the maximum distance for said one or more gaps.

2. The method of claim 1, wherein each said viewshed is split into a plurality of wedges, with each one of said wedges defining a subset of points having an unimpeded line of sight path to its associated said sensor.

3. The method of claim 2, wherein each said viewshed wedge forms a node, and instance of overlap between the wedges of different ones of the viewsheds forms an arc within in a wedge adjacency graph.

4. The method of claim 2, wherein said analyzing said viewsheds comprises finding overlapping ones of the wedges of different ones of the viewsheds that define form a continuous, unbroken length path for said virtual tripwire.

5. The method of claim 4, wherein analyzing said viewsheds comprises solving a linear integer problem using said pieces of each of adjacent ones of said viewsheds that are overlapping, to determine said minimum number of candidate sensors required to form said continuous path.

6. The method of claim 1, wherein said analyzing said viewsheds to determine a number of said candidate sensors comprises analyzing said viewsheds to determine a minimum number of said viewsheds that enables said virtual tripwire to be created with predetermined distance gaps between adjacent ones of the viewsheds, to thus form a non-continuous path for said virtual tripwire.

7. The method of claim 1, wherein said viewshed of a given one of said candidate sensors comprises a portion of said subregion of said area of interest where a line-of-sight may exist from any point within said portion of said subregion to said given one of the candidate sensors.

8. The method of claim 7, further comprising designating portions of said terrain that are not to be considered before performing said geometric analysis of said terrain in said subregion of said area of interest.

9. The method of claim 1, further comprising defining a minimum distance thickness of said virtual tripwire, and analyzing said viewsheds to determine a minimum number of said candidate sensors that enable said virtual tripwire to be formed with said minimum distance thickness.

10. The method of claim 1, further comprising displaying, on a display, said virtual tripwire overlayed on a digital elevation model of said terrain in said subregion of said area of interest.

11. The method of claim 10, further comprising displaying, on said display, said viewsheds of selected ones of said candidate sensors that have been used to construct said virtual tripwire, with said virtual tripwire being overlayed on said viewsheds of said selected ones of said candidate sensors.

12. The method of claim 1, wherein said defining a maximum distance for one or more gaps comprises enabling a negative trim width to be selected prior to analyzing said viewsheds, with said negative trim width representing a maximum distance segment along said virtual tripwire when said virtual tripwire is determined, where no viewshed overlap exists between any two adjacent ones of said candidate sensors.

13. A method, implemented using a computer, for determining placements of a plurality of sensors that are used to monitor a geographic area of interest, the method comprising:

obtaining a digital elevation model that includes as a portion thereof said area of interest;

selecting an initial number of candidate sensors to be deployed within said area of interest, and to be used in monitoring said area of interest;

selecting a minimum thickness for at least a substantially continuous path through said area of interest;

using a computer based geographic information system to perform a geometric analysis of terrain in said area of interest using said digital elevation model, and said initial number of candidate sensors, to determine a viewshed for each said candidate sensor, said viewshed of each of said candidate sensors representing a region made up of a collection of subregions, where each said subregion has a line-of-sight to its associated said candidate sensor; and

using the computer to analyze all of said viewsheds and to initially determine a minimum subset of said candidate sensors that have viewsheds that form the least substantially continuous path through said area of interest from a designated beginning point to a designated ending point, and while meeting said selected minimum thickness.

14. The method of claim 13, further comprising enabling tailoring of said minimum subset of said candidate sensors to provide a modified, minimum subset of said candidate sensors that includes fewer sensors than said minimum subset, such that gaps are formed between the viewsheds of adjacent ones of said modified subset of candidate sensors.

15. The method of claim 13, further comprising enabling a user to select a larger number of said candidate sensors than that defined by said minimum subset, to provide a greater percentage of overlap of said viewsheds.

16. The method of claim 13, wherein analyzing all of said viewsheds comprises considering a height above a ground surface that certain ones of said candidate sensors are to be mounted at.

17. The method of claim 13, wherein selecting an initial number of candidate sensors comprises selecting an initial number of a plurality of one of radar devices and optical imaging devices.

18. A method, implemented using a computer, of determining placements for a plurality of sensors that ensures formation of an optimized virtual tripwire through a geographic region, and that maximizes an area covered by the sensors, comprising:

obtaining a digital elevation model of said geographic region that includes as a portion thereof an area of interest;

using a geographic information system to perform a geometric analysis of terrain in the area of interest using the digital elevation model;

providing an initial number of candidate sensors that may be used to form said virtual tripwire;

defining a maximum length of one or more gaps permitted to exist in said virtual trip wire;

determining a viewshed for each said candidate sensor, the viewshed of each said candidate sensor representing a region made up of a collection of subregions, where each said subregion has a line-of-sight to its associated sensor; and

using the computer to analyze all the viewsheds and using the geometric analysis of the terrain of the area of interest, and the maximum length of said one or more gaps, to initially determine placements for each one of the candidate sensors within the area of interest such that portions of adjacent viewsheds generate a continuous, uninterrupted path that forms the virtual tripwire, and further such that a region covered by said sensors is maximized, and further which meets said maximum length for said one or more gaps.

19. A system for forming a virtual tripwire in a vicinity of a designated boundary line within an area of interest, the system comprising:

a geographic information system for performing a geographic analysis of terrain in said vicinity of said boundary line, said geographic information system adapted to determine a location for each one of a pre-designated plurality of candidate sensors within said area of interest, that may potentially be used in forming said virtual tripwire, and a viewshed for each said candidate sensor, with each said viewshed representing a coverage region for its associated said candidate sensor, and further such that certain ones of said candidate sensors have viewsheds that at least partially overlap with one another; and

an optimization system responsive to information input by a user that defines a minimum desired thickness for said virtual tripwire, and further responsive to information generated by said geometric information system, for analyzing said viewsheds to initially determine a minimum number of ones of said candidate sensors required to form a path from a designated beginning point to a designated ending point, the path representing the virtual tripwire having a thickness in accordance with the minimum desired thickness.