# Parallelization of the Honeybee Search Algorithm for Object Tracking
## 1 Introduction  
Object tracking deals with the problem of following a specific object from a video source in a frame by frame basis, and tries to solve several challenges such as the occlusion of objects [1, 2]; and the abrupt changes in light, color or size [3]. Different approaches, known as trackers, have been proposed in order to solve the object tracking problem, but no definitive answer has been found [3, 4, 5, 6, 7]. Usually, researchers compare trackers against each other regarding speed and accuracy with focus on trackers which provide the most accurate results but have considerable low speeds. In general, trackers are slower because they perform more operations to provide better accuracy. This apparent negative correlation between accuracy and speed makes it challenging to select a suitable tracker for any given application [8]. In summary, the studied problem in this work is how to accelerate a specific tracker without having negative effects on their accuracy. The Graphics Processing Unit (GPU) is a useful tool to accelerate computational tasks in general, including object tracking [9, 10]. This device thrives at the moment of accelerating trackers such as the Normalized Cross-Correlation (NCC) [11, 12, 13]. Although NCC is not a recent tracker it is oneof the most studied trackers due to its low complexity and good performance regarding accuracy. NCC is well positioned compared to other trackers that used the ALOV video dataset for testing and evaluation [3]. Moreover, this work presents a GPU-based parallel version of the Honeybee Search Algorithm (HSA, detailed in Section 2.2) [14; 15; 16; 17] to achieve greater NCC acceleration. While a GPU allows accelerating computations by performing numerous operations in parallel, HSA achieves acceleration by performing a heuristic search rather than an exhaustive search. In other words, HSA, such as other heuristics, converges to the optimal solutions after several iterations. It is important to mention that HSA is considered a pioneer on the subject of bio-inspired bees applied to the field of artificial intelligence [18]. Adaptation of Swarm Intelligence (SI) algorithms, such as HSA, for parallel execution on a GPU, is not a new idea. The research of [PERSON] and [PERSON] [19] proposes that when an SI algorithm is parallelized through the GPU, the implementation must fall in one of the following four categories: (1) naive parallel model, (2) multiphase parallel model, (3) all-GPU parallel model, or (4) multiswarm parallel model. They identified those models by observing several parallel implementations of SI algorithms [20; 21; 22; 23; 24], most of which are based on the Particle Swarm Optimization heuristic. We selected HSA for this study as it differs from other SI algorithms on the following basis: (1) it can be used for real-valued optimization problems, while other heuristics are limited to discrete problems, (2) it is not explicitly designed for route searching problems, and (3) according to our knowledge, the parallelization of HSA has not been proposed or developed for object tracking. SI has been used for object tracking in a few works [25; 26], but as far as we know, the parallelized SI algorithms have been mostly tested with benchmarking functions, and less frequently used for object tracking [27]. This work uses the unique combination of: NCC as the tracker function, the HSA for heuristic search, and a GPU for hardware acceleration. Experiments performed within this work show that the addition of HSA improves the speed against a purely GPU-accelerated NCC. Also, there are no observed adverse effects on the accuracy of the results and these are confirmed using a proposed evaluation criterion, called Score-Time Efficiency. The Score-Time Efficiency is used to facilitate the comparison of different tracker proposals regarding speed and accuracy. This work can be considered a proof of concept to increase the acceleration of object tracking by parallelizing HSA using the GPU with the NCC tracker as its fitness function.