Background Information

To compute the optical flow, we first need to partition the images evenly to define the dimension and starting point of the search areas and the reference boxes. The larger the search areas and reference boxes, the more computational power is required, which means more logic elements would be used on an FPGA. The reference boxes and search areas are usually squares for calculation and display simplicity; however, the dimension of both can be arbitrary.

The red box in Figure 1 outlines the reference box in image1. the black box represents the first match area candidate in the search area, which is enclosed by a blue box in image2. In this example, we would partition the entire pictures into multiple 4x4 search areas and define the reference box to be 2x2. Starting from the first match candidate, every pixel in the reference box is compared with the corresponding pixels in the match area. The absolute differences of data of each pair of corresponding pixels rare summed up and the value is stored to a temporary register to keep track of the minimum sum. The coordinates of the first pixel in the match area is also stored to a temporary register to keep track the position where the minimum sum has been computed. The position of the starting pixel is then updated.

We would go through the entire search area by moving the match area across each row. A complete search is done when both increments in x- and y-direction reach length–1. The total number of calculation for a single search area is therefore (length of search area – length of reference area–1)².

After computing the minimum sum of absolute differences and find out the address of that corresponding box, we can move on to the next partition and compute the optical flow of the next search area. When all the partitions have been searched, we can draw a line from the center of the each search area to the center of its corresponding reference box to present a complete optical flow.

Figure 1: A schematic for the algorithm of optical flow