# Performance Optimization of Object Tracking Algorithms in OpenCV on GPUs
## 3 Analysis of OpenCV Object Tracking Algorithms
### Optical Flow Algorithm  
Optical flow is a representative motion estimation algorithm, which compares two consecutive frames to calculate an object's vector. The optical flow consists of _sparse_ and _dense_ optical flows. Sparse optical flow has high-speed throughput by minimizing \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Occupancy Calculator** & **VGA** & **HD** & **FHD** \\ \hline Number of VGPRs used & 76 & 76 & 76 \\ Number of SGPRs used & 94 & 94 & 94 \\ LDS memory used & 3840 & 3840 & 3840 \\ Global work size & 6144 & 6144 & 6144 \\ Number of VGPR-limited waves & 12 & 12 & 12 \\ Number of LDS-limited waves & 17 & 17 & 17 \\
**Kernel occupancy** & **30** & **30** & **30** \\ \hline
**HW Perf Counter** & **VGA** & **HD** & **FHD** \\ \hline GlobalWorkSize & 768/8/1 & 768/8/1 & 768/8/1 \\ WorkGroupSize & 8/8/1 & 8/8/1 & 8/8/1 \\ Time & 18.44 & 66.59 & 154.42 \\ LocalMemSize & 3840 & 3840 & 3840 \\ VGPRs & 76 & 76 & 76 \\ SGPRs & 94 & 94 & 94 \\
**Wavefronts** & **96** & **96** & **96** \\ FetchSize & 37,467.44 & 149,170.43 & 414,024.81 \\ CacheHit & 76.99 & 70.93 & 66.39 \\ VALUInsts & 400,422.48 & 1,373,869.12 & 3,303,635.24 \\ SALUInsts & 78,081.27 & 262,919.63 & 626,184.05 \\
**VALUBusy** & **39.24** & **38.03** & **37.80** \\
**SALUBusy** & **6.77** & **6.49** & **6.35** \\
**MemUnitBusy** & **53.00** & **53.07** & **48.65** \\ FlatVMemInsts & 63,293.07 & 217,756.61 & 524,978.30 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Profiling results of the runHaarClassifier kernel. computation only with interesting features. However, the sparse optical flow has poor accuracy due to exploiting only a fraction of points. Dense optical flow has high accuracy due to calculating all pixels, but a long computation time is its disadvantage. Therefore, optimizing the execution of dense optical flow algorithm achieves both high accuracy and suitable execution time. Farneback optical flow [39] is a representative dense optical flow algorithm provided by OpenCV. Figure 5b shows the execution flow of the Farneback algorithm. The algorithm uses video files or cameras as the input media because it processes continuous images. At the preprocessing stage, the cvtColor function converts input images to grayscale images as in the Haar algorithm. After preprocessing, the calcOpticalFlowFarnback function calculates the optical flow vector. The calcOpticalFlowFarnback function launches diverse kernels to compute the optical flow, and these kernels are repeatedly executed in several groups. The gaussianBlur, resizeLN, and polynoniaExpansion kernels form one group, and updateMatrics, boxFilter5, and updateFlow form another. The execution flow of the entire calcOpticalFlowFarnback function contains both groups and repeats with the resizeLN and KF kernels. The optical flow algorithm executes 77 kernels for processing two consecutive frames. The algorithm launches some kernels twice in succession because it processes continuous frames. In Figure 5b, the parts marked \"\(\times\)2\" represent two consecutive kernel calls. We measured and analyzed the performance of the Farneback optical flow algorithm. The experiment environment is identical to the Haar experiment case. Figure 7a shows the processing time of consecutive frames by resolution. As shown in the figure, the frame processing time increases when the video resolution increases. Figure 7b is the breakdown result of Figure 7a and represents the execution time proportion of each kernel. The parenthesis to the right of the kernel name means the number of launches while processing consecutive frames. For example, boxFilter5(12) means that the kernel boxFilter5 is called 12 times while processing consecutive frames. Therefore, a kernel that accounts for a large portion of the time may have a short execution time. Actually, the three kernels _boxFilter_, _gaussianBlur_, and _updateMatrices_ account for a large portion in the frame processing time, but their unit execution time is not large (1-2% of the frame processing time).