Systems and methods for performing three-dimensional semantic parsing of indoor spaces

Patent metadata

Field	Value
Publication number	US-10424065-B2
Application number	US-201715619422-A
Country	US
Kind code	B2
Filing date	Jun 9, 2017
Priority date	Jun 10, 2016
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

Abstract

Systems and methods for performing three-dimensional semantic parsing of indoor spaces in accordance with embodiments of the invention are disclosed. In one embodiment, a method includes receiving input data representing a three-dimensional space, determining disjointed spaces within the received data by generating a density histogram on each of a plurality of axes, determining space dividers based on the generated density histogram, and dividing the point cloud data into segments based on the determined space dividers, and determining elements in the disjointed spaces by aligning the disjointed spaces within the point cloud data along similar axes to create aligned versions of the disjointed spaces normalizing the aligned version of the disjointed spaces into the aligned version of the disjointed spaces, determining features in the disjointed spaces, generating at least one detection score, and filtering the at least one detection score to determine a final set of determined elements.

First claim

What is claimed is:

1. A method for parsing three-dimensional indoor spaces, the method comprising:
receiving input data representing a three-dimensional indoor space;
determining disjointed spaces within the received input data by:
generating a density histogram on each of a plurality of axes of the three-dimensional indoor space;
determining space dividers based on the generated density histogram by:
locating a void space enclosed by a histogram signal peak on either side of the void space; and
convolving the density histogram with a series of filters in a filter bank;

dividing the input data into segments based on the determined space dividers; and

determining structural elements in the disjointed spaces by:
aligning the disjointed spaces within the input data along similar axes to create aligned versions of the disjointed spaces;
normalizing the aligned version of the disjointed spaces into a unit cube;
determining features in the unit cube;
generating at least one detection score based on the determined features representing the probability of the presence of an element; and
filtering the at least one detection score to determine a final set of determined elements.

2. The method of claim 1 , wherein the input data received can be from multiple sources.

3. The method of claim 2 , wherein the multiple sources of input data are correlated to each other by at least one reference point, creating a registered set of data.

4. The method of claim 2 , wherein the multiple sources of input data is selected from the group of: point cloud data, three-dimensional meshes, three-dimensional surface normals, depth images, RGB images, and RGB-D images.

5. The method of claim 1 , wherein determining disjointed spaces within input data further includes:
generating a graph of all neighboring segments;
evaluating each neighboring segment for a space divider between the neighboring segments;
removing edges from the graph when a space divider is detected;
creating connected components between all neighboring segments with edges remaining; and
merging connected component segments into disjointed spaces.

6. The method of claim 1 , wherein the received input data represents the interior of an entire building.

7. The method of claim 1 , wherein determining structural elements in the disjointed spaces further includes assigning determined structural elements to a class.

8. The method of claim 7 , wherein determining structural elements in the disjointed spaces further includes reevaluation of the determined structural elements by:
generating a graph of all neighboring disjointed spaces;
evaluating each neighboring disjointed space for a detected wall class between neighboring disjointed spaces;
removing edges from the graph when a space divider is detected;
creating connected components between all neighbors with edges remaining; and
merging connected component disjointed spaces.

9. A semantic parsing system comprising:
a processor;
at least one input;
a memory connected to the processor, where the memory contains;
a parsing application;

wherein the parsing application directs the processor to:
receive input data representing a three-dimensional space;
determine disjointed spaces within the received input data, where:
a density histogram on each of a plurality of axes of the three-dimensional indoor space is generated;
space dividers based on the generated density histogram are determined, where to generate the space dividers, a void space enclosed by a histogram signal peak on either side of the void space is located; and

the density histogram is convolved with a series of filters in a filter bank; and
the input data is divided into segments based on the determined space dividers; and

determine structural elements in the disjointed spaces, where:
the disjointed spaces within the input data are aligned along similar axes;
the disjointed spaces within the input data are normalized into unit cubes;
features in the unit cubes are detected;
at least one detection score is generated based on the detected features representing the probability of the presence of an element; and
the at least one detection score is filtered to determine a final set of determined elements.

10. The semantic parsing system of claim 9 , wherein the input data received can be from multiple sources.

11. The semantic parsing system of claim 10 , wherein the multiple sources of input data can be correlated to each other by at least one reference point, creating a registered set of data.

12. The semantic parsing system of claim 10 , wherein the multiple sources of input data is selected from the group of: point cloud data, three-dimensional meshes, three-dimensional surface normals, depth images, RGB images, and RGB-D images.

13. The semantic parsing system of claim 9 , wherein determining disjointed spaces within input data further includes:
generating a graph of all neighboring segments;
evaluating each neighboring segment for a space divider between the neighboring segments;
removing edges from the graph when a space divider is detected;
creating connected components between all neighboring segments with edges remaining; and
merging connected component segments into disjointed spaces.

14. The semantic parsing system of claim 9 , wherein the received input data represents the interior of an entire building.

15. The semantic parsing system of claim 9 , wherein determining structural elements in the disjointed spaces further includes assigning determined structural elements to a class.

16. The semantic parsing system of claim 9 , wherein determining structural elements in the disjointed spaces further includes reevaluation of the determined structural elements by:
generating a graph of all neighboring disjointed spaces;
evaluating each neighboring disjointed space for a detected wall between neighboring disjointed spaces;
removing edges from the graph when a space divider is detected;
creating connected components between all neighbors with edges remaining; and
merging connected component disjointed spaces.

Assignees

• Univ Leland Stanford Junior

Inventors

• Armeni Iro
• Sener Ozan
• Zamir Amir R
• Fischer Martin
• Savarese Silvio

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06F18/245

  relating to the decision surface · CPC title

• G06V10/32

  Normalisation of the pattern dimensions · CPC title

• G06V10/50

  by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis · CPC title

• G06T7/187

  involving region growing; involving region merging; involving connected component labelling · CPC title