Patent Abstract:
In one aspect, a computerized method to automatically detect buildings includes determining if each point of a set of filtered points is on a line by processing the set of filtered points in one pass including a) locating a first point of the set of filter points nearest to a second point of the set of filtered points, b) determining if the distance between the first point and the second point is greater than a distance threshold; c) determining if the first point and the second point have collinearity greater than a collinearity threshold; and d) designating the first point as an endpoint of a line that includes the second point if the distance between the first point and the second point is greater than the distance threshold and if the first point and the second point have collinearity greater than the collinearity threshold.

Full Description:
BACKGROUND 
       [0001]    Laser Detection and Ranging (LADAR) sensor, sometimes referred to as laser radar, uses laser beams to measure distances. A LADAR sensor can be used to form images of scenes with a high degree of definition (e.g., 3 cm resolution at 1,000 meters). LADAR sensors are classified as three-dimensional (3-D) sensor because the output of the data from these sensors includes 3-D data with, for example, x-, y-, and z-coordinates. Other 3-D sensors include, but are not limited to, synthetic aperture radar (SAR) and stereo-optic imagers. 
       SUMMARY 
       [0002]    In one aspect, a computerized method to automatically detect buildings includes receiving three-dimensional (3-D) data from a 3-D sensor and filtering the 3-D data to form a set of filtered points that include points greater than an altitude threshold. The method also includes determining if each point of the set of filtered points is on a line by processing the set of filtered points in one pass including a) locating a first point of the set of filter points nearest to a second point of the set of filtered points, b) determining if the distance between the first point and the second point is greater than a distance threshold; c) determining if the first point and the second point have collinearity greater than a collinearity threshold; d) designating the first point as an endpoint of a line that includes the second point if the distance between the first point and the second point is greater than the distance threshold and if the first point and the second point have collinearity greater than the collinearity threshold; e) repeating steps a to e substituting an unprocessed point as the first point and the first point as the second point if the first point is designated as an endpoint. The method further includes generating an output file comprising a set of lines corresponding to building edges based on the processing of the set of filtered points in one pass. 
         [0003]    In another aspect, an apparatus includes circuitry to automatically detect buildings. comprising circuitry to receive three-dimensional (3-D) data from a 3-D sensor and filter the 3-D data to form a set of filtered points comprising points greater than an altitude threshold. The circuitry also includes circuitry to determine if each point of the set of filtered points is on a line by processing the set of filtered points in one pass including circuitry to: a) locate a first point of the set of filter point nearest to a second point of the set of filtered points; b) determine if the distance between the first point and the second point is greater than a distance threshold; c) determine if the first point and the second point have collinearity greater than a collinearity threshold; d) designate the first point as an endpoint of a line that includes the second point if the distance between the first point and the second point is greater than the distance threshold and if the first point and the second point have collinearity greater than the collinearity threshold; and e) repeat steps a to e substituting an unprocessed point as the first point and the first point as the second point if the first point is designated as an endpoint. The circuitry further includes circuitry to generate an output file comprising a set of lines corresponding to building edges based on the processing of the set of filtered points in one pass. 
         [0004]    In a further aspect, an article includes a non-transitory machine-readable medium that stores executable instructions to automatically detect buildings. The instructions cause a machine to receive three-dimensional (3-D) data from a 3-D sensor and filter the 3-D data to form a set of filtered points comprising points greater than an altitude threshold. The instructions also cause the machine to determine if each point of the set of filtered points is on a line by processing the set of filtered points in one pass including instructions that cause the machine to: a) locate a first point of the set of filter point nearest to a second point of the set of filtered points; b) determine if the distance between the first point and the second point is greater than a distance threshold; c) determine if the first point and the second point have collinearity greater than a collinearity threshold; d) designate the first point as an endpoint of a line that includes the second point if the distance between the first point and the second point is greater than the distance threshold and if the first point and the second point have collinearity greater than the collinearity threshold; and e) repeat steps a to e substituting an unprocessed point as the first point and the first point as the second point if the first point is designated as an endpoint. The instructions further cause the machine to generate an output file comprising a set of lines corresponding to building edges based on the processing of the set of filtered points in one pass. 
     
    
     
       DESCRIPTION OF THE DRAWINGS 
         [0005]      FIG. 1  is a flowchart of an example of a process to detect buildings. 
           [0006]      FIG. 2  is a flowchart of an example of a process to filter 3-D data. 
           [0007]      FIGS. 3A and 3B  are a flowchart of an example of a process to determine building edges. 
           [0008]      FIG. 4  is a computer on which any of the processes of  FIGS. 1 to 3B  may be implemented. 
       
    
    
     DETAILED DESCRIPTION 
       [0009]    Described herein are techniques for using data from a three-dimensional (3-D) sensor (e.g., a Laser Detection and Ranging (LADAR) sensor, a synthetic aperture radar (SAR) and so forth) to detect buildings. For example, a 3-D sensor is used to generate a file that may be used by geo-engines (e.g., GOOGLE® Earth, GOOGLE® maps and so forth) to present a geographic scene with buildings identified (e.g., with an overlay). In one particular example, keyhole markup language (KML) files are automatically (e.g., without user intervention) generated that identify buildings (e.g., three-dimensional (3-D) buildings). 
         [0010]    Prior art attempts to identify buildings in a geographic scene have been performed manually or semi-automatically. For example, a user would typically locate buildings and choose the dimensions and heights of the buildings in a geographic scene and then semi-automated algorithms would generate KML file(s) defining the buildings. Other approaches may try to identify the raised flat areas of building roofs. These approaches may suffer when the roofs are irregularly shaped or when equipment (e.g. air conditioners, cooling towers, or decorative structures) are present on the rooftops. 
         [0011]    Referring to  FIG. 1 , an example of process to automatically detect buildings from data from a 3-D sensor is a process  100 . Process  100  receives 3-D data from a 3-D sensor ( 104 ) and filters the 3-D data ( 108 ). From the filtered 3-D data, process  100  determines building edges ( 114 ) and generates an output file ( 122 ). For example, the output file is a set of lines corresponding to edges of buildings. In one particular example, the output file is a KML script file that can be used with commercially available software such as GOOGLE® Earth to show buildings in a geographic scene. 
         [0012]    Referring to  FIG. 2 , one example of a process to filter the 3-D data from a 3-D sensor in processing block  108  is a process  200 . Process  200  determines the highest z value for each x-y position ( 204 ). For example, the x-y plane is the ground and the z-coordinate represents height or altitude from the ground. For each x-y position with the highest z value determined in processing block  204 , process  200  determines the greatest z value (altitude) within a specified horizontal distance (e.g., 1 to 5 meters) from the x-y position ( 208 ). Process  200  determines if the greatest z value (altitude) determined in processing block  208  is greater than an input threshold (e.g., 10 meters for an urban environment, 5 meters for suburban or country environment) ( 212 ). For example, the input threshold is used to filter out low to the ground objects (e.g., fences) that are not buildings. If the z value is not greater than the input threshold, process  200  sets (e.g., amends) the z value (altitude) for that point to zero ( 216 ). 
         [0013]    If the z value is greater than the input threshold, process  200  stores the difference of the z value (altitude) and the input threshold, and the z value ( 218 ). For example, both the altitude and the building height are stored for output to a KML file. Process  200  outputs all x-y points have a non-zero z value, which form a set of filtered points ( 222 ). 
         [0014]    Referring to  FIGS. 3A and 3B , an example of a process to detect building edges in processing block  114  is a process  300 . Building edges are generally lines. Process  300  generates an empty set of lines ( 304 ). As process  300  is executed the empty set of lines becomes populated with lines if building edges are detected. Process  300  selects any point called point A from the set of filtered points ( 308 ). For example, the set of filtered points generated by process  200  is used in processing block  308 . Process  300  removes a point, called point A, from the set of filtered points and designates point A as a starting point ( 312 ). For example, point A may be any point in the set of filtered points. 
         [0015]    Process  300  determines the nearest point to point A, which is designated as point B. Process  300  determines if the set of filtered points is empty ( 322 ) and if the set of filtered points is not empty removing point B from the set of filtered points ( 328 ). Process  300  determines a distance from point A to the point B ( 332 ) and determines if the distance from point A to point B is greater than a distance threshold ( 338 ). For example, a distance beyond the distance threshold is considered too far away to be part of the same line. In one example, a distance threshold of 1.0 meter produces good results for a data set derived from a dense urban environment. 
         [0016]    If the distance from point A to point B is less than or equal to the distance threshold, process  300  determines a collinearity of point A and point B ( 342 ). Process  300  determines if the collinearity determined in processing block  342  is greater than a collinearity threshold ( 346 ). For example, a point that is beyond the collinearity threshold is considered to be too far from the line to be part of the line. In one particular example, a collinearity threshold of 0.5 meter, for example, produces good results for a data set from a dense urban environment. 
         [0017]    If the collinearity determined in processing block  342  is less than or equal to a collinearity threshold, process  300  designates point B as an end point, sets point A equal to point B ( 358 ) and repeats processing block  320 . For example, in processing block  358  point B becomes or is re-designated as point A. 
         [0018]    If the set of filtered points is empty, the distance determined in processing block  332  is greater than the distance threshold or the collinearity determined in processing block  342  is greater than the collinearity threshold, process  300  determines if the end of a line has been reached ( 362 ). 
         [0019]    If the end of the line has been reached, process  300  determines a distance from the start point of the line to the end point of the line ( 368 ) and determines if the distance from the start point to the end point is greater than an allowable line length ( 372 ). If the distance from the start point to the end point is greater than the allowable line length process  300  adds the line to the set of lines ( 376 ). For example, lines that are smaller than the allowable line length are not considered building edges. For example, 2 meters would be used for houses, and 5 meters would be used for larger buildings. 
         [0020]    Process  300  determines if the set of filtered points is empty ( 382 ) and if the set of filtered points is empty, merges lines that are collinear ( 386 ). For example, two lines that have endpoints that are close to each other (e.g., 1.0 meter) may be merged. Referring to  FIG. 4 , a computer  400  may be used to execute all or part of the processes described herein (e.g., the processes  100 ,  200 ,  300 ). The computer  400  includes a processor  402 , a volatile memory  404 , a non-volatile memory  406  (e.g., hard disk), for example, and a user interface (UI)  408  (e.g., a mouse, a keyboard, a touch screen and so forth). In other examples of a computer  400 , the UI  408  may not be included. Non-volatile memory  406  includes an operating system  416 ; data  418 ; and computer instructions  412  which are executed out of volatile memory  404  to perform all or part of processes  100 ,  200 ,  300 . In one example, the data  418  may include unfiltered points  422  (e.g., received from a 3-D sensor), filtered points  424  (e.g., as an output of a process  200 ), a set of lines  426  (e.g., as an output of a process  300 ) and an output file  428  (e.g., as an output of a process  100 ). 
         [0021]    The processes described herein (e.g., processes  100 ,  200 ,  300 ) are not limited to use with the hardware and software of  FIG. 4 ; they may find applicability in any computing or processing environment and with any type of machine or set of machines that is capable of running a computer program. The processes may be implemented in hardware, software, or a combination of the two. The processes may be implemented in computer programs executed on programmable computers/machines that each includes a processor, a storage medium or other article of manufacture that is readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device to perform any or part of the processes  100 ,  200 ,  300 , for example, and to generate output information. 
         [0022]    The processes described herein are not limited to the specific embodiments described herein. For example, the processes are not limited to the specific processing order of the process steps in  FIGS. 1 to 3B . Rather, any of the processing steps of  FIGS. 1 to 3B  may be re-ordered, combined or removed, performed in parallel or in serial, as necessary, to achieve the results set forth above. 
         [0023]    Process steps in  FIGS. 1 to 3B  associated with implementing the system may be performed by one or more programmable processors executing one or more computer programs to perform the functions of the system. All or part of the system may be implemented as, special purpose logic circuitry (e.g., an FPGA (field programmable gate array) and/or an ASIC (application-specific integrated circuit)). 
         [0024]    While the invention is shown and described in conjunction with a particular embodiment having an illustrative architecture having certain components in a given order, it is understood that other embodiments well within the scope of the invention are contemplated having more and fewer components, having different types of components, and being coupled in various arrangements. Such embodiments will be readily apparent to one of ordinary skill in the art. All documents cited herein are incorporated herein by reference. Other embodiments not specifically described herein are also within the scope of the following claims.

Technology Classification (CPC): 6