Complexity accuracy tradeoffs of Lie operators in motion estimation

Lie operators are known to be effective in detecting very small degrees of object motions such as scaling, rotations and deformations. In this paper, we apply multiple Lie operators in combination to increase the accuracy of the conventional translation-only motion estimation. We propose the following three motion estimation methods using Lie operators with varying computational complexities, including the serial search, iterative search and the dynamic programming like search methods. We seek to study the tradeoffs allowed by the different combinations of Lie operators between the improved accuracy and the extra computational complexity associated with estimating the motion parameters. Both analytical and experimental results show that the proposed Lie-operator approaches can offer significant increases in the accuracy of the motion estimation with only low to moderate increase in the computational complexity. We also demonstrate that the iterative search method based on Lie operators has much lower complexity than motion search using an affine motion model for small motion parameters, while providing accuracy improvements very close to those attainable by the affine model approach.