FPGA -based implementation of Optical flow [600746]

FPGA -based implementation of Optical flow
Algorithm
R. Allaoui , H. H . Mouane , Z. Asrih, S. Mars, I. El hajjouji, A. El mourabit
National School of Applied Science, UAE University
Tangier, Morocco
rachidallaoui9 [anonimizat]

Abstract—In this paper, we describe an FPGA
implementation of the optical flow (OF) algorithm for real time
estimation of moving objects from a video sequence. Lucas –
Kanade (LK) approach has been chosen to meet the real time and
hardware resource constraints. In our approach, to allow
accurate calculation, we adopt a high level synthesis approach to
increase the accuracy of the system and to more deal with fixed –
point precision. Hardware designs of the architectures are
performed using Xilinx System Generator from Xilinx (XSG) and
Modelsim tools. The proposed architecture is validate d by
hardware co -simulation.
Keywords —Optical Flow ; FPGA; XSG
I. INTRODUCTION
Nowada ys, the domain of driving assistance systems
(ADAS) is a changing sector. The aim of such systems is to
help driver in his perception of the road scene. Since in ADAS
systems, the embedded camera is moving, actually, the
detection of the moving objects (pedestrians,
vehicle movement s …) is a challenging task. Among the
reported methods in the literature, OF algorithm is the most
adapted for moving camera and often offers a convenient and
useful image motion representation. Unlike background
subtraction method which is frequently used in video
surveillance field where camera is fixed [ 1] [2]. Different
methods are used to find the optical flow estimation [ 3] [4].
However, th ese systems suffer from the drawbacks of limited
speed or the need of larger area. LK algorithm is the most
adequate in terms of calculation complexity to the embedded
FPGA platform [3]. The principle of the L&K optical flow
estimation is to assume the br ightness constancy to find
velocity vector (u, v) between two successive frames. The
accuracy of the estimation of the displacement from the video
sequence is the main concern.
Indeed, compared to Horn and Schunck algorithm, LK
method requires less hardware and computational complexity.
Therefore, LK is a good candidate for FPGA -based embedded
applications. However, its main drawback is the low accuracy
in the large displacement estimation. The most previous
hardware architecture used only integer representation to
implement the different arithmetic operators of the algorithm
[5]–[9]. Thus, different results can be observed due to the fact
that precision and noise issues as well as resources usage ar e
closely related to precision of the used arithmetic operators. In this paper, we use a high level synthesis (HLS)
methodology to implement operators on hardware. Besides the
speed -up time of development through abstraction, HLS is a
best way to find the best compromise between speed, area and
consumption power of each used basic operations.
The paper is organized as follows: in section 2, we present
the optical flow algorithm and Lucas Kanade’s approach. In
section 3 we describe the high level impleme ntation of the
system using XSG. In section 4 we report the experimental
results.
II. OPTICAL FLOW
Optical flow algorithm estimates the motion field from the
apparent motion of the objects or the edges in the video
sequence or from a successive frames . The bas ic assumption
of optical flow algorithms is the brightness constancy
constraint which can be formulated as :

  , , , , I x y t I x x y y t t    (1)
where I(x, y, t) is the intensity of pixel (x, y) at frame t and
I(x+ ∆x, y + ∆y, t+ ∆t) is the intensity of the corresponding
pixel at frame t + ∆t.
By developing the second member of equation (1)
using the first order of Taylor series, we have :

 , , , , x x y y t I x y t I x y t I v I v I    (2)
So,

x x y y tI v I v I  (3)
where
, ( ,)x y yI I II I I
x y t       are the spatio –
temporal gradients,
 , , T
T
xyxyv v vtt
 is the optical
flow.
The Brightness constancy constraint assumes that any
change in the image brightnes s is due only to motion in a short
time. In other words, if the time interval between frames is
small, any other effect (such as changes in lighting conditions)
causing brightness changes can be neglected.
Equation (3) is known as the aperture problem. To resolve
this equation, it is necessary to add one or
more parameters to calculate the optical flow v.
This work was supported by PPR2 grant of CNRST and MENFES

Since 1981, many optical flow algorithms have been
proposed. We have focused on a classical gradient model
based on LK’s approach. It is based on that the optical flow is
essentially constant in a local neighborhood of the central
pixel. i.e., the central pixel and his
neighbors, in the observation window, move in the same way.
Considering an observation window of n pixels, each pixel
  1,2, , iq i n
satisfied (3), we obtain



1 1 1
2 2 2. .
. .
. . x x y y t
x x y y t
x n x y n y t nI q v I q v I q
I q v I q v I q
I q v I q v I q 
 
  (4)

We formulate (4) in a matrix form,
.Av B , where :


1
21
2xy
xy
x n y nI q I q
I q I q
I q I qA




;
x
yv
vv
 ;


1
2

t
t
tnIq
Iq
IB
q





The formed system of equations is an over-determined one
because there are more equations than unknown parameters.
Assuming that the matrix A is regular and the rank of matrix
A is equal to numbers of unknowns the system will be
resolved in the least square sense. If we multiply
.Av B , by
the transpose matrix of A, we have:
. . .TTA Av A B
(5)
This means,

2
1 1 1
2
1 1 1.n n n
x x y x t
x
n n n
y
x y y y tI I I I Iv
vI I I I I   
                   
   (6)
By substitution, we solve this system with 2 equations and
two unknowns and we obtain,

2
2
x
yce bfvac b
be afvac b     (7)
where
, xyvv are the components of optical flow and
2
1n
x
iaI

,
1n
xy
ib I I
 ,
2
1n
y
icI
 ,
1n
xt
ie I I

1n
yt
if I I
 III. IMPLEMENTATION
A. Xilinx System Generator
System Generator is a system -level modeling tool that
facilitates FPGA hardware design. It extends Simulink in
many ways to provide a modeling environment that is well
suited to hardware desi gn. The tool provides high -level
abstractions that are automatically compiled into an FPGA
through dedicated tools . The tool also provides access to
underlying FPGA resources through low -level abstractions,
allowing the construction of highly efficient FPG A designs
[10].
B. Implementation steps
Fig. 1 shows the different stages to compute the optical
flow from two frames. Below we describe in detail the
functionality of each stage.
1) After the acquisition of the frames, we store two
consecutive frames to perform the temporal gradient using the
difference filter kernel [-1 1].
2) We convert the RGB -images to a grayscale level , to
perform spatial gradient calculation. Sobel operator kernels are
used to calculate horizontal and verti cal gradients Ix and I y.
Matlab preload function is used to compute S patio -temporal
derivatives Ix, Iy and It .

Fig. 1. Optical flow computation stages

Fig. 2. Matrix element calculation blocks (Example a=sum(Ix ²) calculation)
3) Least square matrices construction consists in
calculating a, b, d, e and f.
The optical flow block has three inputs ports, which are the
signals from Matlab workspace. Each signal (Ix, Iy or It) is
leaded to a 3×3 line buffer (first bloc from left in Fig. 2) which
is implemented using sin gle port RAM blocks as showed in
Fig.3.
The line buffer block buffers a sequential stream of pixels
to construct 3 lines of output. We output 9 pixel values by
integrating 3 registers in each line.
Second Bloc in Fig. 2 performs the l east square matri x
construction for integration of neighborhood velocities
estimations . The computation of the least -square matrices is
the most expensive stage in terms of computational resources.
Indeed, there is five terms -a, b, d, e and f – to be calculated.
Each one compu tation used up 9 DSPs multipliers and 8
adders as Fig. 4 showed.
4) Velocity estimation requires a division operation. At
this stage the resolution of the incoming data bits is significant
and expensive arithmetic operations are required. For
example, if we use 8 bits in the first two stages, to become 16
bits after multiplication and 20 bits after addition in the
construction of the least -square matrices.

Fig. 3. Line buffer Bloc Two dividers are used to calculate vx and vy. For each
one, we should calculate th e numerator and denominator as
shows Fig. 5. So, 6 DSPs multipliers and 3 subtractors are
added to make the data width more large and the
computational resources more expensive.
The dividers used in this implementation perform fixed –
point division with high radix algorithm option selected.
5) The graphical representation of velocity field vectors is
performed using a Matlab post -load function, so we can
evaluate the movement direction.

Fig. 4. Least square matri x construction Bloc

Fig. 5. Velocity calculation block

IV. RESU LTS
The developed prototype system has been implemented on
a Virtex 6 XC6VLX75t board . Two video sequences were used
to validate the implemented system: Yosemite and road scene.
Results are shown in Fig 7 and 9 respectively. Red vectors
start from the pix el in movement. Accuracy for optical flow
computations is estimated by average angular error compared
to ground truth, computed across the optical flow field. Our
implementation results in an average angular error on the test
sequence of 15.8 degrees. The processing speed is about 30
fps. Hardware -resource usage is illustrated in Table1. Table 2
presents the speed and the normalized speed for the motion
estimation in the two used videos. The results show the
efficiency of the used methodology in the impleme ntation of
the LK algorithm.
TABLE I . HARDWARE RESOURCE EST IMATION
Estimated Resource Value
Slices 1812
Flip Flops 3574
Block RAMs 6
LUTs 1488
I/O Blocks 112
Multipliers 51
TABLE II . PROCESSING SPEED AND NORMALIZED SPEED OF THE CHOSEN
SEQUENCES
Yosemite Road scene
Image resolution 252×316 360×480
Processing Speed
(ms/frame) 0,3 0,65
Normalized speed
(ns/pixel) 3,74 3,74

(a)
(b)
Fig. 6. Yosemite 1st and 2nd images sequence, (a) previous image, (b) current
image.

Fig. 7. Simulation results of Yosemite movement

. (a) (b)
Fig. 8. Traffic scene, (a) previous image, (b) current image

Fig. 9. Simulation results in a road scene
V. CONCLUSION
The system described in this article shows the
implementation of Lucas & Kanade approach for optical flow
estimation in Xilinx System Generator to detect and track
moving objects in a road scene. The system was modeled in

Virtex 6 XC6VLX75t board . A hardware co-simul ation has
been performed in order to evaluate and validate the
performance of the designed system.
REFERENCES
[1] B. Patel; N. Patel, Motion Detection based on multi -frame video
under surveillance systems , March 2012 , Vol. 12.
[2] N. Lu; J. Wang; Q. Wu; L. Yang, An improved Motion
Detection method for real time Surveillance , February 2012
[3] B. D. Lucas and T. Kanade, “An iterative image registration
technique with an application to stereo vision,” in Proc. DARPA
Image Understanding Workshop, Apr. 1984, pp. 121 –130.
[4] B. K. P. Horn and B. G. Schunck, "Determining Optical Flow,"
Massachusetts Institute of Technology 1980 .
[5] H. Niitsuma and T. Maruyama, “Real -Time detection of moving
objects,” Lecture Notes in Computer Science, FPL 2004, vol.
3203, pp. 1153 –1157, Sep. 2004 .
[6] P. Cobos and F. Monasterio, “FPGA implementation of camus
correlation optical flow algorithm for real time images,” in Proc.
14th Int. Conf. Vision Interface, 2001, pp. 32 –38.
[7] S. Maya -Rueda and M. Arias -Estrada, “FPGA processor for real –
time optical flo w computation,” Lecture Notes in Computer
Science, vol. 2778, pp. 1103 –1016, 2003.
[8] M. V. Correia and A. C. Campilho, “Real -time implementation of
an optical flow algorithm,” in Proc. Int. Conf. Pattern
Recognition, 2002, pp. 247 –250.
[9] J. L. Barron, D. J. F leet, and S. Beauchemin, “Performance of
optical -flow techniques,” Int. J. Comput. Vis., vol. 12, no. 1, pp.
43–77, 1994.
[10] System Generator for DSP User Guide (v11.4 ). Available online:
https://www.xilinx.com/support/documentation/sw_manuals/xilin
x11/sysgen _user.pdf