Integrated circuits with optical flow computation circuitry

• US 9,819,841 B1
• Filed: 04/17/2015
• Issued: 11/14/2017
• Est. Priority Date: 04/17/2015
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Denisenko, Dmitry N.
• Primary Examiner(s): Fujita, Katrina
• Application Number:
  US14/689,792
• Time in Patent Office: 942 Days
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: H04N 5/144 Movement detection for video coding H04N19/503; analysis of motion in general G06T7/20
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

An integrated circuit with optical flow computation circuitry is provided. The optical flow computation circuitry may include a first image shift register for receiving pixel values from a current video frame, a second image shift register for receiving pixel values from a previous video frame, column shift registers for storing column sums of various gradient-based values, square sum registers for storing square sums generated at least partly based on the column sum values, and an associated computation circuit that constructs a gradient matrix based on values stored in the square sum registers and that computes a 2-dimensional optical flow vector based on an inverse of the gradient matrix and differences between the current and previous frames. Optical flow computing circuitry configured in this way may be capable of supporting dense optical flow calculation for at least one pixel per clock cycle while supporting large window sizes.

Claims

1. An integrated circuit, comprising:

a first storage circuit that stores image data from a current video frame;

a second storage circuit that stores image data from a previous video frame;

a plurality of column sum shift registers, wherein each column sum shift register receives input from at least the first storage circuit;

a plurality of square sum registers, wherein each square sum register receives input from a respective column sum shift register; and

an optical flow computation circuit that computes one pixel of output per clock cycle at least partly based on input from each square sum register of the plurality of square sum registers.

2. The integrated circuit defined in claim 1, wherein the second storage circuit receives the image data of the previous video frame from an external memory device.

3. The integrated circuit defined in claim 2, wherein the computation of the pixel output from the optical flow computation circuit only requires communication with the external memory when receiving the image data of the previous video frame at the second storage circuit.

4. The integrated circuit defined in claim 1, wherein the computation of the pixel output from the optical flow computation circuitry does not involve any communication with an external memory device.

5. The integrated circuit defined in claim 1, wherein the optical flow computation circuit is configured to compute a gradient matrix for a window size of at least 20 by 20 pixels.

6. The integrated circuit defined in claim 1, wherein the optical flow computation circuit is configured to compute a gradient matrix for a window size of at least 50 by 50 pixels.

7. The integrated circuit defined in claim 1, further comprising:

programmable logic circuitry.

12. The integrated circuit defined in claim 1, wherein the plurality of column sum shift registers includes a first column sum shift register that receives input from only the first storage circuit and a second column sum shift register that receives input from the first and second storage circuits.

13. The integrated circuit defined in claim 1, wherein the plurality of column sum shift registers includes first, second, and third column sum shift registers that receive input from only the first storage circuit and fourth and fifth column sum shift registers that receive input from the first and second storage circuits.

14. The integrated circuit defined in claim 13, wherein the first column sum shift register determines a first column sum based on a horizontal gradient associated with the current video frame.

15. The integrated circuit defined in claim 14, wherein the second column sum shift register determines a second column sum based on the horizontal gradient and a vertical gradient associated with the current video frame.

16. The integrated circuit defined in claim 15, wherein the third column sum shift register determines a third column sum based on the vertical gradient.

17. The integrated circuit defined in claim 16, wherein the fourth column sum shift register determines a fourth column sum based on the horizontal gradient and a difference between the current video frame and the previous video frame.

18. The integrated circuit defined in claim 17, wherein the fifth column sum shift register determines a fifth column sum based on the vertical gradient and the difference between the current video frame and the previous video frame.

8. A method for computing an optical flow output on an integrated circuit, comprising:

computing a first gradient matrix for a first pixel by computing column sum values based on horizontal and vertical gradient values associated with a column of pixels and by computing a square sum value based on the column sum values; and

computing a second gradient matrix for a second pixel by reusing at least part of the first gradient matrix associated with the first pixel and by subtracting a left-most column sum in a window associated with the first pixel from the square sum value, wherein the second pixel is different than the first pixel.

9. The method defined in claim 8, wherein computing the second gradient matrix further comprises adding a right-most column sum in another window associated with the second pixel to the square sum value.

10. The method defined in claim 9, wherein the right-most column sum is computed by identifying a column sum associated with a third pixel that is located immediately above the second pixel.

11. The method defined in claim 10, wherein the right-most column sum is computed by further subtracting a first gradient-based value from the column sum associated with the third pixel and adding a second gradient-based value of the second pixel.