Nonconvex optimization by Gaussian smoothing and continuation with applications to image alignment

Опубликовано 28 июля 2016, 22:48

We investigate a well-known heuristic for optimization of nonconvex functions. The idea is to start from a highly smoothed version of the objective function that "hopefully" makes it convex (easy to globally minimize). This minimizer then initiates a gradient descent loop which follows the minimizer path while the objective function gradually deforms back to the original. This heuristic sometimes converges to the global minimum of the original function. The smoothing process is closely related to some fundamental processes in physics such as heat equation and schrodinger's equation. Yet, surprisingly, there is almost no theoretical understanding about this heuristic when used for global optimization. In the first part of the talk (perhaps of interest to a broad spectrum of audience), I present some results in these directions which include answers to the following questions: 1. What conditions guarantee a function is asymptotically (infinite smoothed) convex? 2. Is there any closed form for asymptotic minimizers? 3. How big is the class of asymptotically convex functions? 4. I also discuss some preliminary ideas and plans for developing performance guarantees for this optimization approach. Second part of the talk shows how these ideas can be applied to a fundamental problem in computer vision, namely the image alignment. We prove that the traditional lucas-kanade type alignment is only optimal when geometric transform is limited to displacement. We then discuss the optimal way to smooth the alignment objective for more general transformation models. We introduce a new concept called "transformation kernel" which allows efficient computation of the smoothed objective for common transformation models such as affine and homography. We show that smoothing the objective function outperforms lucas-kanade type of alignment.