Single pass peak detection in LIDAR sensor data stream

Patent metadata

Field	Value
Publication number	US-11733384-B2
Application number	US-201916379782-A
Country	US
Kind code	B2
Filing date	Apr 9, 2019
Priority date	Feb 20, 2019
Publication date	Aug 22, 2023
Grant date	Aug 22, 2023

Abstract

A system and a method determines a traveling time for a light pulse between a light pulse source and a pixel of a light sensor array based on a “Find Frequent Items in a Data Steam” technique. In one embodiment, raw timestamp data output from a pixel as a data stream may be temporarily stored, processed twice and then discarded to provide an exact determination of a traveling time estimate. In another embodiment, the raw timestamp data is processed once and discarded to provide an approximate determination of a traveling time estimate. The traveling time estimate may be updated during processing and the most-frequently occurring timestamp is available when processing the data stream is complete. There is no need to keep the raw data in a memory, thereby reducing the memory requirement associated with determining the traveling time of a light pulse.

First claim

What is claimed is:

1. A method to determine a traveling time for a light pulse between a light pulse source and a pixel of a light sensor array, the method comprising:
generating a data stream of a plurality of timestamp values for a plurality of light pulses traveling between the light pulse source and the pixel, each timestamp value comprising a time of flight for a corresponding light pulse to travel between the light pulse source and the pixel; and
determining, using a find-frequent-items-in-a-data-stream process, a most frequent occurrence of the traveling time of a light pulse between the light pulse source and the pixel to be a most frequent time stamp value in the data stream of the plurality of timestamp values by:
initializing a value for each element in a set of elements to be equal to zero, the set of elements comprising a predetermined number of elements;
initializing a value of a counter associated with each element in the set of elements;
processing the plurality of timestamp values by determining whether each timestamp value equals the value of an element in the set of elements:
replacing the value of an element with the timestamp value and incrementing the value of the counter associated with the element that was replaced based on the value of the element in the set of elements equaling zero;
incrementing the value of the counter associated with the element having the value that equals the timestamp value based on the timestamp value equaling the value of the element in the set of elements;
decrementing the value of all of the counters associated with the elements in the set of elements based on the timestamp value not equaling the value of an element in the set of elements;

after all timestamp values in the plurality of timestamp values have been processed,
initializing the value of each counter corresponding to the elements in the set of elements;
determining whether each timestamp value in the plurality of timestamp values equals the value of an element of the set of elements;
incrementing the value of the counter associated with the element having the value that equals the timestamp value based on the timestamp value equaling the value of an element in the set of elements; and
determining the element in the set of elements associated with the counter value that is a greatest to be the timestamp value representing the traveling time for a light pulse between the light pulse source and the pixel.

2. The method of claim 1 , wherein the plurality of timestamp values comprises a frame of timestamp values.

3. The method of claim 1 , wherein the plurality of timestamp values comprises a stream of timestamp value data.

4. The method of claim 1 , wherein the timestamp values comprise unquantized values.

5. The method of claim 1 , wherein the plurality of timestamp values comprises a first group of timestamp values and a second group of timestamp values,
wherein processing the plurality of timestamp values comprises using the first group of timestamp values, and
wherein processing the plurality of timestamp values after all timestamps values in the plurality of timestamp values have been processed comprises using the second group of timestamp values.

6. The method of claim 5 , wherein the first group of timestamp values comprises timestamp values from a first frame, and the second group of timestamp values comprises timestamp values from a second frame that is subsequent to the first frame.

7. The method of claim 6 , wherein the first group of timestamp values and the second group of timestamp values together comprise a frame of timestamp values.

8. The method of claim 1 , further comprising adding at least one pair of neighboring values to the plurality of timestamp values for each timestamp value of the plurality of timestamp values, each respective pair of neighboring values bracketing a corresponding timestamp value by a predetermined number of integer units of resolution of the timestamp values.

9. A system to determine a traveling time for a light pulse between a light pulse source and a pixel of a light sensor array, the system comprising:
a plurality of registers;
a plurality of counters, each counter associated with a corresponding register; and
a timestamp evaluator circuit configured to determine whether each timestamp value of a plurality of timestamp values equals a value stored in one of the plurality of registers,
the timestamp evaluator circuit configured to replace the value of a register with the timestamp value and to increment a value of the counter associated with the register based on the value stored in the register equaling zero,
the timestamp evaluator circuit configured to increment the value of the counter associated with the register based on the timestamp value equaling the value stored in a register, and
the timestamp evaluator circuit configured to decrement the value of all of the counters associated with all of the registers based on the timestamp value not equaling the value stored in all of the registers, and

after all timestamp values in the plurality of timestamp values have been evaluated, the timestamp evaluator circuit further configured to:
initialize a value of each counter,
determine whether each timestamp value in the plurality of timestamp values equals the value stored in a register,
increment the value of the counter associated with a register storing a value that equals the timestamp value based on the timestamp value equaling the value stored in the register, and
determine the timestamp value of the register associated with the value of the counter that is a greatest to be the timestamp value representing the traveling time for a light pulse between the light pulse source and the pixel.

10. The system of claim 9 , wherein the plurality of timestamp values comprises a frame of timestamp values.

11. The system of claim 9 , wherein the timestamp values comprise unquantized values.

12. The system of claim 9 , wherein the plurality of timestamp values comprises a first group of timestamp values and a second group of timestamp values,
wherein the timestamp evaluator circuit processing the plurality of timestamp values comprises using the first group of timestamp values, and
wherein the timestamp evaluator circuit further configured to:
determine whether each timestamp value of the first group of timestamp values equals a value stored in one of the plurality of registers,
replace the value of a register with the timestamp value and increment a value of the counter associated with the register based on the value stored in the register equaling zero,
increment the value of the counter associated with a register based on the timestamp value equaling the value stored in the register, and
decrement the value of all of the counters associated with all of the registers based on the timestamp value not equaling the value stored all of the registers, and

wherein after all timestamp values in the first group of timestamp values have been evaluated, the timestamp evaluator circuit further configured to:
initialize a value of each counter,
determine whether each timestamp value in the second group of timestamp values equals the value stored in a register,
increment the value of the counter associated with a register storing a value that equals the timestamp value based on the timestamp value equaling the value stored in the register, and
determine the timestamp value of the register associated with the value of the counter that is a greatest to be the timestamp value representing the traveling time for a light pulse between the light pulse source and the pixel.

13.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Shi Lilong
• Wang Yibing Michelle

Classifications

• G01S17/10 Primary

  using transmission of interrupted, pulse-modulated waves (determination of distance by phase measurements G01S17/32) · CPC title

• G01B9/02014

  by using pulsed light · CPC title

• G01S7/4808

  Evaluating distance, position or velocity data · CPC title

• G01S7/4865 Primary

  Time delay measurement, e.g. time-of-flight measurement, time of arrival measurement or determining the exact position of a peak (peak detection in noise, signal conditioning G01S7/487) · CPC title

• G01S17/36

  with phase comparison between the received signal and the contemporaneously transmitted signal · CPC title