Fish body midline segmentation using binary search
Body and caudal fin locomotion is ubiquitous in aquatic vertebrates, and kinematic models describing it are used in robotics, biomechanics and fisheries research. This paper presents a new algorithm to translate continuous body midlines of fish into a series of interconnected segments by identifying favorable joint positions along the body. The algorithm employs binary search to generate parsimonious kinematic models, aiming at minimizing the number of segments yet keeping approximation error below a user-defined threshold. To achieve this, the algorithm maximizes the length of each segment by determining the most distal joint position through repetitive shrinking of the search space. Theoretical and empirical analysis using two different datasets show that the binary search algorithm is substantially faster when compared to segment growing algorithm, which employs linear search to generate its models. There is four-fold improvement in computation time when generating models with less than 10 segments, which are typically sufficient to describe fish and fish-inspired robot movements. Furthermore, the multi-segment models generated by the binary search algorithm matched the ground truth models obtained through dynamic programming in over 97% of cases, and on average, contained one fewer segment than those produced by the Ramer–Douglas–Peucker algorithm, which is widely used in curvature simplification tasks. Our findings suggest that the binary search algorithm provides a computationally efficient approach for generating compact kinematic models and may facilitate the analysis of large datasets with high temporal and spatial resolution.