A Sparse Branch and Bound Optimization of Noisy Weighted DAG Modification Under Constraints: A Method for Monocular Data Association to Multiple Laser Planes

The line segments of multiple (and nearly parallel) planar laser sources appearing in monocular video are objectively associated to their respective laser sources. Such association is a precursor to 3D surface digitization where each laser plane develops a 3D surface. In this work, the detected laser line segments are modeled as a weighted directed acyclic graph (wDAG), in which the graph nodes represent the line segments and their maximum path hopes from any source node represents the laser source label. However, due to noise and occlusions, the structure of the wDAG will normally vary from that expected in the ideal cases. Furthermore, it is essential to robustness to incorporate the association information of the previous frames in the new frame associations. The proposed work objectively modifies the current frame’s wDAG under these constraints so the resulting wDAG becomes in an appropriate structure for the labeling of the detected line segments. Branch and bound (BnB) optimization has been a good choice for global optimization of combinatorial problems. Rather than approaching the optimization as a pure (or full) combinatorial problem, the proposed prioritizations of the branch modification actions are nearly optimal. The high priority actions will very likely lead to an optimal modification. This aspect is exploited by the proposed sparse variant of BnB (SBnB) optimization. It significantly reduces the number of the branches to be considered, in addition to those contributed by the bounding part of the BnB optimization. The proposed approach was tested on numerous monocular videos and plausible association results were efficiently achieved.