Patent Publication Number: US-8538167-B2

Title: Designating corridors to provide estimates of structures

Description:
TECHNICAL FIELD 
     This invention relates generally to the field of sensor data analysis and more specifically to designating corridors to provide estimates of structures. 
     BACKGROUND 
     Enforcement, security, and military forces may perform operations in structures such as buildings. These forces may need to know the layout, for example, the floor plan, of the structures. In certain situations, however, the layout may not be available. 
     SUMMARY OF THE DISCLOSURE 
     In accordance with the present invention, disadvantages and problems associated with previous techniques for fusing multi-sensor data may be reduced or eliminated. 
     In particular embodiments, analyzing data includes receiving sensor data generated in response to sensing one or more structures. The structural features of the sensor data are identified. Each structural feature is represented by one or more vectors. A score matrix describing relationships among the vectors is generated. Candidate corridors are identified from at least some of the vectors according to the score matrix. One or more candidate corridors are designated as designated corridors. Each designated corridor comprises an opening defined by at least two structural features. A layout of the structures is generated from the structural features and the designated corridors. 
     Certain embodiments of the invention may provide one or more technical advantages. A technical advantage of one embodiment may be that structural features indicated by sensor data are represented by vectors. The vectors are then placed in a score matrix in order to determine navigable corridors defined by the structural features. Another technical advantage of one embodiment may be that corridors may be designated as doorways or gaps. The designated doorways and gaps aid in the identification of structures sensed by the sensors. 
     Certain embodiments of the invention may include none, some, or all of the above technical advantages. One or more other technical advantages may be readily apparent to one skilled in the art from the figures, descriptions, and claims included herein. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       For a more complete understanding of the present invention and its features and advantages, reference is now made to the following description, taken in conjunction with the accompanying drawings, in which: 
         FIG. 1  illustrates one embodiment of a system configured to designate corridors to provide estimates of structures; 
         FIG. 2  illustrates an example of a method for designating corridors to provide estimates of structures; 
         FIG. 3  illustrates examples of structural features; 
         FIG. 4  illustrates representing the structural features of  FIG. 3  by vectors; 
         FIG. 5  illustrates the orientations and locations of the open vectors of  FIG. 4 ; 
         FIG. 6  illustrates examples of distances between vector endpoints; 
         FIG. 7  illustrates examples of alignment angles for designating a corridor; and 
         FIG. 8  illustrates an example of more than one candidate corridor located between vectors. 
     
    
    
     DETAILED DESCRIPTION OF THE DRAWINGS 
     Embodiments of the present invention and its advantages are best understood by referring to  FIGS. 1 through 8  of the drawings, like numerals being used for like and corresponding parts of the various drawings. 
       FIG. 1  illustrates one embodiment of a system  10  configured to designate corridors to provide estimates of structures  20 . In the illustrated embodiment, system  10  includes sensors  24 , a computing system  26 , and an output device  28 . Computing system  26  includes an interface (IF)  30 , logic  32 , and memory  34 . Logic  32  includes a processor  36  and applications such as a layout generator  38 . Output device  28  displays a layout  40 . 
     In certain embodiments, system  10  receives sensor data from one or more sensors  24  sensing structures  20  and generates layout  40  of structures  20 . In the embodiments, system  10  represents structural features indicated by sensor data by vectors, and places the vectors in a score matrix. System  10  then identifies candidate corridors between pairs of vectors according to the score matrix. System  10  designates candidate corridors as designated corridors according to the alignment of the structural features and the corridor. The designated corridors are used to determine structures  20  sensed by the sensors. 
     In the illustrated embodiment, structures  20  may be one or more natural and/or manmade physical objects. Examples of structures  20  include buildings such as military, corporate, residential, academic, or medical buildings. In certain embodiments, a structure  20  may have internal features that are not visible outside of structure  20 . For example, a building may have rooms bordered by walls such that the rooms are not visible outside of the building. The layout of the structure, such as the floor plan of a building, may describe at least some of these internal features. 
     Structures  20  may have structural features that are physical features of the geometry of the structure. For example, the structural features of the building may include walls of a room and corners of a room where two walls meet. Structural features may be used to generate a layout  40  of the structures  20 . The layout of a room may be provided in two dimensions (2D) or three dimensions (3D). A wall, or “plate,” may be represented by a line in a two-dimensional layout or a plane in a three-dimensional layout. A corner may be represented by a type of n-hedral, which is a set of n lines with a common point, where n is an integer. The common point may be called the “corner point.” A corner may be represented by a dihedral, or 2-hedral, in a two-dimensional layout or a trihedral, or 3-hedral, in a three-dimensional layout. 
     Structural features may define openings, such as navigable corridors of the structures  20 . Examples of corridors may include doorways and gaps. A doorway may be an opening between structural features, such as walls, for entering and exiting the structure or a room of the structure. A gap may be an opening between structural features that does not possess characteristics of a typical doorway. For example, a gap may be larger than a typical doorway. A gap may indicate the presence of certain internal features of the structures  20 , such as stairwells. 
     Sensors  24  may generate sensor data in response to sensing one or more structures  20 . The sensor data may describe the structural features of the structures. Sensor  24  may be any suitable sensing device. Examples of sensor  24  include radar sensors, video cameras, camcorders, closed-circuit television cameras, digital cameras, surveillance cameras, infrared cameras, x-ray cameras, and/or satellite cameras. In certain embodiments, more than one sensor  24  may send data to computing system  26 . 
     Computing system  26  receives sensor data from one or more sensors  24  and fuses the sensor data to generate a layout  40  of structures  20 . Interface  30  receives input, sends output, processes the input and/or output, and/or performs other suitable operation. Interface  30  may comprise hardware and/or software. 
     Logic  32  performs the operations of the component, for example, executes instructions to generate output from input. In certain embodiments, layout generator  38  generates a layout  40  of structures  20 . In the embodiments, layout generator  38  receives sensor data and identifies structural features of the sensor data. Layout generator  38  represents the structural features by vectors, and generates a score matrix that describes relationships among the vectors. Layout generator  38  identifies candidate corridors from the vectors according to the score matrix. In some embodiments, layout generator  38  may test a width of each candidate corridor to determine whether to designate the corridor as a doorway or a gap. Layout generator  38  designates designated corridors from at least some of the candidate corridors. For example, layout generator  38  may designate a candidate corridor as a designated corridor if the corridor substantially aligns with the walls that define it. Layout generator  38  estimates structures according to the structural features and the designated corridors. A method that layout generator  38  may use to generate layout  40  is described in more detail with respect to  FIG. 2 . 
     Logic  32  may include hardware, software, and/or other logic. Logic  32  may be encoded in one or more tangible media and may perform operations when executed by a computer. Certain logic  32 , such as processor  36 , may manage the operation of a component. Examples of a processor  36  include one or more computers, one or more microprocessors, one or more applications, and/or other logic. 
     In particular embodiments, the operations of the embodiments may be performed by one or more computer readable media encoded with a computer program, software, computer executable instructions, and/or instructions capable of being executed by a computer. In particular embodiments, the operations of the embodiments may be performed by one or more computer readable media storing, embodied with, and/or encoded with a computer program and/or having a stored and/or an encoded computer program. 
     Memory  34  stores information an applications such as layout generator  38 . Memory  34  may comprise one or more tangible, computer-readable, and/or computer-executable storage medium. Examples of memory  34  include computer memory (for example, Random Access Memory (RAM) or Read Only Memory (ROM)), mass storage media (for example, a hard disk), removable storage media (for example, a Compact Disk (CD) or a Digital Video Disk (DVD)), database and/or network storage (for example, a server), and/or other computer-readable medium. Output device  28  outputs layout  40  generated by computing system  26 . 
     Output device may provide layout  40  in any suitable manner, for example, as a visual display, a printed hard copy, or an audio file. Examples of output device  28  includes a computer display, a printer, or a speaker. 
       FIG. 2  illustrates an example of a method  200  for designating corridors to provide estimates of structures. The method may be performed by system  10  of  FIG. 1 . 
     In certain embodiments, sensor data is received at step  204 . The sensor data may be generated in response to sensing structures  20  and may describe structural features of structures  20 . The structural features of the sensor data are identified at step  208 . The structural features of the sensor data may be identified in any suitable manner. 
     In some embodiments, portions of sensor data that are likely to represent the same physical feature, such as a wall or a corner of a structure, may be identified as a structural feature. As an example, portions of sensor data representing physical features proximate to each other, such as physical features within less than 2 inches of each other, may be likely to represent the same physical feature. In some embodiments, sensor data may comprise data received from multiple sensors, and identifying the structural features may include fusing the data.  FIG. 3  illustrates examples of structural features comprising corner feature  50   a  and wall features  50   b ,  50   c , and  50   d.    
     Referring back to  FIG. 2 , the method represents each structural feature by one or more vectors at step  212  to yield a plurality of vectors. A structural feature may be represented by vectors in any suitable manner. 
       FIG. 4  illustrates representing the structural features of  FIG. 3  by vectors. In certain embodiments, a structural feature is represented by at least one endpoint (e) and a set of vectors comprising at least one open vector (v o ) and at least one closed vector (v c ). An open vector originates at the endpoint and points in the direction of the space beside a wall. A closed vector originates at the endpoint and points towards the wall itself. In some embodiments, the open vector and the closed vector may be co-linear with the line representing the wall. 
     Referring back to  FIG. 2 , the method may define a score matrix at step  216 . A score matrix describes one or more relationships among the open vectors. Examples of relationships include relative orientation, relative location, and distance. The score matrix may be an M×M matrix, where M represents the number of open vectors. 
     In some embodiments, a score matrix may be calculated by multiplying an orientation mask describing the orientation relationships, a location mask describing the location relationships, and/or a distance mask describing the distance relationships among the vectors. The orientation mask and the location mask may be determined based on the open vectors.  FIGS. 5 and 6  describe examples of relationships used to determine the score matrix. 
       FIG. 5  illustrates the orientations and locations of the open vectors of  FIG. 4 . An orientation mask may identify open vectors oriented in opposite directions. Open vectors that point in opposite directions may indicate a possibility that the opening exists between the vectors. Open vectors may point in opposite directions if the difference between the directions of the vectors equals 180 degrees plus or minus a margin of error. As an example, the margin of error may be in the range of 0-20 degrees, such as 5 degrees or 10 degrees. Open vectors that do not point in opposite directions may indicate that the opening does not exist between the vectors. Examples of vectors that do not point in opposite directions include vectors that point in the same direction and vectors that point in perpendicular directions. 
     In some embodiments, a determination whether vectors point in opposite directions may be made independent of the positions of the vectors. As an example, if a first vector points east and a second vector points west, the vectors may be identified as pointing in opposite directions regardless of their relative positions in the north-south direction. The relative positions of the vectors may affect an angle of alignment of the vectors and, thus, may be taken into consideration when designating corridors as described with respect to  FIG. 7  below. 
     As an example, the vectors of  FIG. 5  may yield the following orientation mask, where a “1” indicates the vectors point in opposite directions and a “0” indicates the vectors do not point in opposite directions. 
     
       
         
         
             
             
         
       
     
     A location mask may identify open vectors pointing toward each other. Open vectors that point toward each other may indicate that an opening exists somewhere between the vectors and, therefore, that the vectors possibly point to the same opening. Open vectors that do not point toward each other may indicate that the opening does not exist between the vectors and, therefore, the vectors point to different openings. 
     In some embodiments, a first open vector may point to a second open vector if the vectors are oriented in opposite directions according to the orientation mask and the second vector is located on the same side of the first vector as the opening indicated by the first vector. As an example, the vectors of  FIG. 5  may yield the following location mask, where a “1” indicates the vectors point toward each other and a “0” indicates the vectors do not point toward each other. 
     
       
         
         
             
             
         
       
     
       FIG. 6  illustrates examples of the distances between endpoint e 2  and the other endpoints of  FIGS. 3-5 . As described above, the score matrix may describe the distance between two vectors. The distance between vectors may be given by any suitable function. For example, a Euclidean distance d(a,b) may be calculated between an endpoint “a” of vector v o a and an endpoint “b” of vector v o b. If the endpoint “a” comprises the coordinates (a x , a y , a z ) and the endpoint “b” comprises the coordinates (b x , b y , b z ), then the distance may be given by:
 
 d ( a,b )=√{square root over (( ax−bx ) 2 +( ay−by ) 2 +( az−bz ) 2 )}{square root over (( ax−bx ) 2 +( ay−by ) 2 +( az−bz ) 2 )}{square root over (( ax−bx ) 2 +( ay−by ) 2 +( az−bz ) 2 )}
 
     The distances between the other combinations of endpoint pairs may be described in a similar manner. The distances between the combinations of endpoint pairs of  FIG. 6  may be arranged in the following distance mask: 
     
       
         
         
             
             
         
       
     
     In some embodiments, the score matrix may be defined by multiplying the orientation mask, the location mask, and the distance mask. That is, values having a common location in each mask may be multiplied together. As an example, the score matrix value for the v o   3 - v   o   4  combination of  FIGS. 3-6  may be calculated by multiplying the orientation mask value of 1, the location mask value of 0, and the distance mask value of d(e 3 ,e 4 ) to yield a score matrix value of 0. Similar calculations may be performed for the other combinations of example vectors to yield the following score matrix: 
     
       
         
         
             
             
         
       
     
     Referring back to  FIG. 2 , the method identifies candidate corridors according to the score matrix at step  220 . Vector pairs having score matrix values less than a minimum score may not be designated as candidate corridors. For example, a score matrix value of zero may indicate that the orientation and/or location of the vector pair fails to indicate a corridor. As another example, a relatively small score matrix value, such as less than a few inches, may indicate that an error occurred in the sensor data or that the opening in the wall is non-navigable. Score matrix values exceeding the minimum score may be designated as candidate corridors. In some embodiments, the minimum score may be a value in the range of less than 2, 2-6, 6-12, or 12-20 inches. 
     At step  224 , the candidate corridors may be further identified as either candidate doorways or candidate gaps. A candidate corridor may be identified as a doorway if its width is approximately equal to that of a typical doorway. The corridor width may be the distance between structural features that define the corridor, as indicated by the score matrix value. A score matrix value indicating a width of a typical doorway may be approximately one meter. In some embodiments, the typical doorway width may be a value in the range of 0.4-0.8, 0.8-1.2, or 1.2-2.0 meters. In some embodiments, a candidate corridor may be identified as a gap if the score matrix value exceeds the width of a typical doorway. A gap may indicate the presence of certain internal features of the structures  20 , such as stairwells. 
     Designated corridors may be designated from the candidate corridors at step  228 . In some embodiments, a designated corridor may be a corridor having a substantially aligned alignment angle. The alignment angle may indicate an alignment of the corridor and the structural features that define the corridor.  FIG. 7  illustrates examples of alignment angles θ 1  and θ 2  of candidate corridors  52   a  and  52   b  respectively. If an alignment angle θ is greater than a threshold angle, then the vectors are not substantially aligned. The threshold angle may have any suitable value, such as a value in the range of 0 to 45 degrees, for example, 15 degrees. 
     In some embodiments, a maximum of one corridor per open vector may be designated for a particular angle of alignment. As an example,  FIG. 8  illustrates a structure having three substantially aligned wall features  50   e ,  50   f , and  50   g  with a first opening defined by wall features  50   e  and  50   f  and a second opening defined by wall features  50   f  and  50   g . The wall features may be represented by open vectors as shown. A score matrix of the vectors may identify candidate corridor  52   c  for the first opening and candidate corridor  52   d  for the second corridor. In addition, the score matrix may identify candidate corridor  52   e  defined by wall feature  50   e  and  50   g  based on the orientation and location of vectors v o   9  and v o   12 . Candidate corridor  52   e , however, should not be designated as a designated corridor because wall feature  50   f  precludes navigability for a portion of candidate corridor  52   e . Accordingly, the candidate corridor having the smallest width may be selected as the only designated corridor for a particular vector at a particular alignment angle. As an example, for vector v o   9 , candidate corridor  52   c  may be designated and candidate corridor  52   e  may not be designated. 
     Referring back to  FIG. 2 , one or more structures  20  are estimated at step  232 . In certain embodiments, the layout of structures  20  is determined. The layout may indicate structural features, such as walls and corners, as well as designated corridors, such as doorways and gaps, of structures  20 . The method then terminates. 
     Modifications, additions, or omissions may be made to system  10  without departing from the scope of the invention. The components of system  10  may be integrated or separated. Moreover, the operations of system  10  may be performed by more, fewer, or other components. For example, the operations of sensors  29  and computing system  26  may be performed by one component, or the operations of layout generator  38  may be performed by more than one component. As used in this document, “each” refers to each member of a set or each member of a subset of a set. A subset may include 0, 1, or more members. 
     Modifications, additions, or omissions may be made to the methods described herein without departing from the scope of the invention. The methods may include more, fewer, or other steps. Additionally, steps may be performed in any suitable order. 
     Although this disclosure has been described in terms of certain embodiments, alterations and permutations of the embodiments will be apparent to those skilled in the art. Accordingly, the above description of the embodiments does not constrain this disclosure. Other changes, substitutions, and alterations are possible without departing from the spirit and scope of this disclosure, as defined by the following claims.