Method for finding important changes in 3D point clouds

Patent metadata

Field	Value
Publication number	US-9558564-B1
Application number	US-201514701760-A
Country	US
Kind code	B1
Filing date	May 1, 2015
Priority date	May 2, 2014
Publication date	Jan 31, 2017
Grant date	Jan 31, 2017

Abstract

A motion detector comprising a sensor apparatus and a calculator arranged for: generating first and second successive frames comprising each a 3-D cloud of points, wherein each point represents a position in space of a surface of at least an object in the field of vision of said sensor apparatus; transforming each of the first and second frames by: mapping each cloud of 3-D points into a 2-D grid of cells associated each to a sequence of predetermined volumes; and associating to each cell of the 2-D grid of cells a sequence of the lists of the points contained in corresponding volumes of the sequence of predetermined volumes; comparing the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames; and indicating that motion occurred based on the sequence of lists being different in the first and second frames.

First claim

What is claimed is:

1. A motion detector comprising:
a sensor apparatus having a field of vision; and
a calculator arranged for:
generating first and second successive frames each comprising a 3-D cloud of points, wherein each point represents a position in space of a surface of at least an object in the field of vision of said sensor apparatus;
transforming each of the first and second frames by:
mapping each cloud of 3-D points into a 2-D grid of cells, each cell of the 2-D grid having a predetermined surface and each 2-D grid cell being associated to a sequence of predetermined volumes; and
associating to each cell of the 2-D grid of cells a sequence of lists of points, each list comprising the 3-D points contained in a corresponding volume of said sequence of predetermined volumes;
comparing the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames; and
indicating that motion occurred based on the sequence of lists being different in the first and second frames.

2. The motion detector of claim 1 , wherein said calculator is arranged for comparing the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames by:
generating for each cell of the 2-D grid a histogram comprising as many entries as there are lists in the sequence of lists associated to the cell, each entry being the number of points in the list; and
comparing the histograms generated for each cell for the first and second frames.

3. The motion detector of claim 2 , wherein the calculator is arranged for comparing the histograms by calculating a distance between the histograms, the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames being different if the distance between their histograms is greater than a predetermined threshold.

4. The motion detector of claim 3 , wherein the calculator is arranged for marking the cells of the first and second 2-D grids having histograms distant by more than said predetermined threshold.

5. The motion detector of claim 1 , wherein:
the calculator is arranged for comparing in priority the sequence of lists associated to the 2-D grid cells proximal to the sensor apparatus;
the calculator is arranged for marking the cells of the first and second 2-D grids having different sequence of lists for the first and second frames; and
the calculator is arranged for considering as identical the sequences of lists associated to the 2-D grid cells located in a shadow zone of any marked cell, the shadow zone comprising an area of the 2-D grid expanding from the marked cell, away from the sensor apparatus, between two lines originating at the sensor apparatus and being tangent with the marked cell.

6. The motion detector of claim 1 , wherein the calculator is arranged for displaying one of the first and second frames with a highlighting of the points of the lists that differ from the corresponding lists in the other frame.

7. The motion detector of claim 1 , wherein the calculator is arranged for considering two compared sequences of lists as identical if each of the compared sequences of lists comprises less than a first predetermined minimum number of points.

8. The motion detector of claim 1 , wherein the calculator is arranged for considering two compared sequences of lists as identical if:
at least one of the compared sequences of lists comprises less than a second predetermined minimum number of points; and
the largest of the compared sequence of lists comprises less than a third predetermined minimum number of points.

9. The motion detector of claim 1 , wherein the calculator is arranged for considering a sequence of lists associated to a cell of the 2-D grid of cells as empty if at least a predetermined number of the lists comprise each less points than a fourth predetermined minimum number of points.

10. The motion detector of claim 1 , wherein the calculator is arranged for considering a sequence of lists associated to a cell of the 2-D grid of cells as empty if the sequence comprises less than a predetermined minimum number of consecutive non-empty lists.

11. The motion detector of claim 1 , wherein said predetermined volumes associated to a 2-D grid cell are all located below a predetermined height over said cell.

12. The motion detector of claim 11 , wherein a height of a ground surface in the field of view of the sensor is known for each cell of the 2-D grid, and wherein said predetermined height defines a predetermined space above said ground plane.

13. The motion detector of claim 1 , wherein the sensor apparatus is one of a LIDAR sensor, an ultrasound sensor, a radar sensor, a sonar sensor and an RFID sensor.

14. A method for detecting motion, the method comprising:
providing a sensor apparatus having a field of vision;
generating first and second successive frames comprising each a 3-D cloud of points, wherein each point represents a position in space of a surface of at least an object in the field of vision of said sensor apparatus;
transforming each of the first and second frames by:
mapping each cloud of 3-D points into a 2-D grid of cells, each cell of the 2-D grid having a predetermined surface and each 2-D grid cell being associated to a sequence of predetermined volumes; and
associating to each cell of the 2-D grid of cells a sequence of lists of points, each list comprising the 3-D points contained in a corresponding volume of said sequence of predetermined volumes;
comparing the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames; and
indicating that motion occurred based on the sequences of lists being different in the first and second frames.

15. The method of claim 14 , wherein said comparing the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames comprises:
generating for each cell of the 2-D grid a histogram comprising as many entries as there are lists in the sequence of lists associated to the cell, each entry being the number of points in the list; and
comparing the histograms generated for each cell for the first and second frames.

16. The method of claim 15 , wherein comparing the histograms comprises calculating a distance between the histograms, the sequences of lists associated to the same cells of the 2-D grids obtained for the first and second frames being different if the distance between their histograms is greater than a predetermined threshold.

17. The method of claim 16 , wherein indicating that motion occurred based on the lists of points being different in the first and second frames comprises marking the cells of the first and second 2-D grids having histograms distant by more than said predetermined threshold.

18. The method of claim 14 , wherein:
said comparing comprises comparing in priority the sequence of lists associated to the 2-D grid cells proximal to the sensor apparatus;
the method comprising: marking the cells of the first and second 2-D grids having different sequence of lists for the first and second frames; and
considering as identical the sequences of lists associated to the 2-D grid cells located in a shadow zone of any marked cell, the shadow zone comprising an area of the 2-D grid expanding from the marked cell, away from the sensor apparatus, between two lines originating at the sensor apparatus and being tangent with the marked cell.

19. The method of claim 14 , wherein said indicating that motio

Assignees

• Hrl Lab Llc
• Hrl Lab Llc

Inventors

• Korchev Dmitriy V
• Owechko Yuri

Classifications

• G06T2207/10028

  Range image; Depth image; 3D point clouds · CPC title

• G06T3/0037

  Physics · mapped topic

• G06K9/6212

  Physics · mapped topic

• G06T7/20 Primary

  Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51) · CPC title

• G06V20/52

  Surveillance or monitoring of activities, e.g. for recognising suspicious objects (recognising microscopic objects G06V20/69) · CPC title