Fast Bounding Box Hierarchy

We introduce a fast algorithm designed for Bounding Box Hierarchy (BBH), a hierarchical tree structure wherein leaf nodes encapsulate sets of original bounding boxes, and non-leaf nodes represent merging operations of their children. A straightforward algorithm employs a bottom-up strategy in a brute force approach to construct the tree, entailing the iterative merging of candidate pairs with the minimum distance until reaching the root node. A pivotal challenge inherent to this brute force paradigm lies in its computational bottleneck, as determining the candidate pair with the minimum distance necessitates a global operation, rendering it highly computationally intensive. Our novel approach strategically circumvents this bottleneck by introducing the computation of approximate minimum distance pairs within local neighborhoods. By using the transformation of 2D bounding boxes into 1D space through Morton coding, the computational cost associated with identifying candidate bounding boxes for merging is significantly diminished, reducing it from O(N<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) to O(logN). Compared with brute force approach which has the overall time complexity O(N<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup>), our algorithm is only O(Nlog(N). The acceleration is critical for computation sensitive applications, particularly in embedded systems and mobile devices. Our approach also supports multi-class bounding box inputs, making it particularly useful for computer vision tasks where bounding boxes are inherently associated with class labels. We validate our algorithm on both real world data and simulated data.