Dense optical flow acceleration

Patent metadata

Field	Value
Publication number	US-10074151-B2
Application number	US-201514871857-A
Country	US
Kind code	B2
Filing date	Sep 30, 2015
Priority date	Sep 30, 2015
Publication date	Sep 11, 2018
Grant date	Sep 11, 2018

Abstract

Described herein are technologies related to technologies to facilitate real-time computer vision applications, especially those with autonomous or semi-autonomous locomotive robots (e.g., drones or self-driving cars). More particularly, the technologies described herein facilitate, for example, real-time motion estimation using dense optical flow. The technologies accelerate dense optical flow (DOF) processing of images by using the parallel processing techniques of a single-instruction, multiple data (SIMD) computing system.

First claim

What is claimed is:

1. A parallel-processing computing system that facilitates acceleration of dense optical flow (DOF) determinations, the system comprising:
an image handler configured to obtain an image that is stored in a memory;
an initializer configured to obtain a thread count (T) and a total number of iterations (n) for convergence of an iterative dense optical flow (DOF) operation performed on the obtained image,
the initializer being further configured to determine a number of iterations per thread (IPT) based upon the thread count and the total number of iterations; and

a parallel processor configured to simultaneously execute multiple threads, each thread performing the iterative converging DOF operation on pixels of the obtained image, the parallel processor being further configured to repeat the simultaneous execution of the multiple threads a number of times matching the determined IPT number to produce DOF data of the image,
wherein the simultaneous execution of the multiple threads is performed in accordance with an execution of a successive over-relaxation (SOR) operation performed simultaneously on each of the pixels included within a plurality of windows that are defined within the image, and
wherein the SOR operation is performed on each of the pixels within each window from among the plurality of windows without local dependencies within its own respective window.

2. A system as recited in claim 1 , wherein the simultaneous execution of the multiple threads includes dispatching some of the threads with a delay between one dispatch to the next.

3. A system as recited in claim 1 , wherein the IPT number is based upon the total number of iterations divided by the thread count.

4. A system as recited in claim 1 , wherein the image is formatted as a canonical discretized rectangular grid of pixels and the processor of the parallel-processing computing system is a single-instruction multiple-data (SIMD) processor.

5. A system as recited in claim 4 , wherein each window from among the plurality of windows defined within the image is an SIMD window.

6. A system as recited in claim 5 , wherein the SOR operation performed on each pixel of each window from among the plurality of windows is performed with dependencies outside its own respective window.

7. A system as recited in claim 5 , wherein the SOR operation performed on each pixel of each window from among the plurality of windows is performed with dependencies to diagonally adjacent neighbors that are outside its own respective window.

8. A system as recited in claim 5 , wherein the production of the DOF data includes transforming results of the simultaneous SOR operations to correspond with a canonical discretized rectangular grid of pixels.

9. A system as recited in claim 1 , wherein performing the SOR operation without local dependencies includes removing single-instruction multiple-data (SIMD) dependencies.

10. One or more non-transitory computer-readable media storing processor-executable instructions that, when executed, cause processors to implement a method comprising:
obtaining an image by a parallel-processing computing system;
obtaining a thread count (T) and a total number of iterations (n) for convergence of an iterative dense optical flow (DOF) operation performed on the obtained image;
determining a number of iterations per thread (IPT) based upon the thread count and the total number of iterations; and
simultaneously executing multiple threads of a processor of the parallel-processing computing system, wherein each thread performs the iterative converging DOF operation on pixels of the obtained image, to repeat the simultaneous execution of the multiple threads a number of times matching the determined IPT number to produce DOF data of the image, and to take action based upon the produced DOF data,
wherein the simultaneous execution of the multiple threads is performed in accordance with an execution of a successive over-relaxation (SOR) operation performed simultaneously on each of the pixels included within a plurality of windows that are defined within the image, and
wherein the SOR operation is performed on each of the pixels within each window from among the plurality of windows without local dependencies within its own respective window.

11. One or more non-transitory computer-readable media as recited in claim 10 , wherein the simultaneous execution of the threads includes dispatching some of the threads with a delay between one dispatch to the next.

12. One or more non-transitory computer-readable media as recited in claim 10 , wherein the IPT number is based upon the total number of iterations divided by the thread count.

13. One or more non-transitory computer-readable media as recited in claim 10 , wherein the image is formatted as a canonical discretized rectangular grid of pixels and the processor of the parallel-processing computing system is a single-instruction multiple-data (SIMD) processor.

14. One or more non-transitory computer-readable media as recited in claim 13 , wherein each window from among the plurality of windows defined within the image is an SIMD window.

15. One or more non-transitory computer-readable media as recited in claim 14 , wherein the SOR operation performed on each of the pixels within each window from among the plurality of windows is performed with dependencies outside its own respective window.

16. One or more non-transitory computer-readable media as recited in claim 14 , wherein the SOR operation performed on each of the pixels within each window from among the plurality of windows is performed with dependencies to diagonally adjacent neighbors that are outside its own respective window.

17. One or more non-transitory computer-readable media as recited in claim 14 , wherein the production of the DOF data includes transforming results of the simultaneous SOR operations to correspond with a canonical discretized rectangular grid of pixels.

18. One or more non-transitory computer-readable media as recited in claim 10 , wherein performing the SOR operation without local dependencies includes removing single-instruction multiple-data (SIMD) dependencies.

Assignees

• Intel Corp

Inventors

• Eldar Avigdor

Classifications

• G06T2207/20021

  Dividing image into blocks, subimages or windows · CPC title

• G06T2207/10016

  Video; Image sequence · CPC title

• G06T1/0007

  Image acquisition · CPC title

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title