Designating corridors to provide estimates of structures

• US 8,538,167 B2
• Filed: 01/07/2010
• Issued: 09/17/2013
• Est. Priority Date: 01/07/2010
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Otts, Daniel W.
• Primary Examiner(s): Le, Vu
• Assistant Examiner(s): WOLDEMARIAM, AKLILU K
• Application Number:
  US12/683,924
• Publication Number:
  US 20110164821A1
• Time in Patent Office: 1,349 Days
• Field of Search: 382/149, 382/154, 382/145
• US Class Current: 382/203
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

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.

Claims

1. A method comprising:

receiving sensor data generated in response to sensing one or more structures, the sensor data describing a plurality of structural features of the structures;

identifying the structural features of the sensor data;

representing each structural feature by one or more vectors to yield a plurality of vectors;

generating a score matrix that describes a plurality of relationships among the vectors;

identifying one or more candidate corridors from at least some of the vectors according to the score matrix;

designating one or more candidate corridors as designated corridors, each designated corridor comprising an opening defined by at least two structural features; and

generating a layout of the one or more structures from the structural features and the designated corridors,

wherein the structural features are represented by at least one endpoint and a set of vectors comprising at least one open vector and at least one closed vector different from the open vector, the at least one open vector originating at the endpoint of a wall and pointing in the direction of a space adjacent to an excluding the wall, and the at least one closed vector originating at the at least one endpoint and pointing towards the wall.

2. The method of claim 1, a relationship of the plurality of relationships comprising an orientation relationship indicating a subset of vectors that point in opposite directions.

3. The method of claim 1, a relationship of the plurality of relationships comprising a location relationship indicating a subset of vectors that point toward each other.

4. The method of claim 1, a relationship of the plurality of relationships comprising a distance relationship indicating one or more distances from each vector to each other vector.

5. The method of claim 1, the generating the score matrix further comprising:

assigning a plurality of score matrix values to each vector, each score matrix value describing one or more relationships among the each vector and a particular other vector, the assigning comprising;

assigning the score matrix value of zero if the each vector and the particular other vector do not point toward each other; and

assigning a score matrix value equal to a distance between the each vector and the particular other vector if the each vector and the particular other vector point toward each other.

6. The method of claim 1, further comprising:

the generating the score matrix further comprising;

assigning a plurality of score matrix values to each vector, each score matrix value describing one or more relationships among the each vector and a particular other vector; and

the identifying one or more candidate corridors from at least some of the vectors according to the score matrix further comprising;

identifying the candidate corridor if the score matrix value exceeds a minimum score.

7. The method of claim 1, the identifying one or more candidate corridors further comprising:

identifying a candidate corridor as a candidate doorway if a distance between the vectors of the candidate corridor is less than or equal to a width of a typical doorway; and

identifying a candidate corridor as a candidate gap if the distance between the vectors of the candidate corridor exceeds the width of the typical doorway.

8. The method of claim 1, the designating one or more candidate corridors further comprising:

designating a candidate corridor as a designated corridor if the candidate corridor and the at least two structural features defining the candidate corridor are substantially aligned.

9. The method of claim 1, the designating one or more candidate corridors further comprising:

determining an alignment angle indicating an alignment of a candidate corridor and the at least two structural features defining the candidate corridor;

comparing the alignment angle to a threshold angle; and

designating the candidate corridor as a designated corridor if the alignment angle does not exceed the threshold angle.

10. The method of claim 1, the designating one or more candidate corridors further comprising:

identifying one or more subsets of candidate corridors, a subset comprising candidate corridors having a vector in common and substantially the same alignment angle, the alignment angle indicating the alignment of the candidate corridor and the at least two structural features defining the candidate corridor; and

designating a maximum of one designated corridor for each subset of candidate corridors.

11. A system comprising:

an interface operable to;

receive sensor data generated in response to sensing one or more structures, the sensor data describing a plurality of structural features of the structures; and

a processor operable to;

identify the structural features of the sensor data;

represent each structural feature by one or more vectors to yield a plurality of vectors;

generate a score matrix that describes a plurality of relationships among the vectors;

identify one or more candidate corridors from at least some of the vectors according to the score matrix;

designate one or more candidate corridors as designated corridors, each designated corridor comprising an opening defined by at least two structural features; and

generate a layout of the one or more structures from the structural features and the designated corridors,

wherein the structural features are represented by at least one endpoint and a set of vectors comprising at least one open vector and at least one closed vector different from the open vector, the at least one open vector originating at the endpoint of a wall and pointing in the direction of a space adjacent to an excluding the wall, and the at least one closed vector originating at the at least one endpoint and pointing towards the wall.

12. The system of claim 11, a relationship of the plurality of relationships comprising an orientation relationship indicating a subset of vectors that point in opposite directions.

13. The system of claim 11, a relationship of the plurality of relationships comprising a location relationship indicating a subset of vectors that point toward each other.

14. The system of claim 11, a relationship of the plurality of relationships comprising a distance relationship indicating one or more distances from each vector to each other vector.

15. The system of claim 11, the processor operable to generate the score matrix by:

assigning a plurality of score matrix values to each vector, each score matrix value describing one or more relationships among the each vector and a particular other vector, the assigning comprising;

assigning the score matrix value of zero if the each vector and the particular other vector do not point toward each other; and

assigning a score matrix value equal to a distance between the each vector and the particular other vector if the each vector and the particular other vector point toward each other.

16. The system of claim 11, further comprising:

the processor operable to generate the score matrix by;

assigning a plurality of score matrix values to each vector, each score matrix value describing one or more relationships among the each vector and a particular other vector; and

the processor operable to identify one or more candidate corridors from at least some of the vectors according to the score matrix by;

identifying the candidate corridor if the score matrix value exceeds a minimum score.

17. The system of claim 11, the processor operable to identify one or more candidate corridors by:

identifying a candidate corridor as a candidate doorway if a distance between the vectors of the candidate corridor is less than or equal to a width of a typical doorway; and

identifying a candidate corridor as a candidate gap if the distance between the vectors of the candidate corridor exceeds the width of the typical doorway.

18. The system of claim 11, the processor operable to designate one or more candidate corridors by:

designating a candidate corridor as a designated corridor if the candidate corridor and the at least two structural features defining the candidate corridor are substantially aligned.

19. The system of claim 11, the processor operable to designate one or more candidate corridors by:

determining an alignment angle indicating an alignment of a candidate corridor and the at least two structural features defining the candidate corridor;

comparing the alignment angle to a threshold angle; and

designating the candidate corridor as a designated corridor if the alignment angle does not exceed the threshold angle.

20. The system of claim 11, the processor operable to designate one or more candidate corridors by:

identifying one or more subsets of candidate corridors, a subset comprising candidate corridors having a vector in common and substantially the same alignment angle, the alignment angle indicating the alignment of the candidate corridor and the at least two structural features defining the candidate corridor; and

designating a maximum of one designated corridor for each subset of candidate corridors.