Optimization by Gaussian smoothing with application to geometric alignment

Mobahi, Hossein

Permalink

https://hdl.handle.net/2142/42330 Copy

Description

Title

Optimization by Gaussian smoothing with application to geometric alignment

Author(s)

Mobahi, Hossein

Issue Date

2013-02-03T19:35:33Z

Director of Research (if dissertation) or Advisor (if thesis)

Ma, Yi

Doctoral Committee Chair(s)

Ma, Yi

Committee Member(s)

• Huang, Thomas S.
• Forsyth, David A.
• Hoiem, Derek W.
• Soatto, Stefano

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Nonconvex Optimization
• Homotopy Continuation
• Image Alignment
• Point Cloud Alignment
• Coarse-to-fine Optimization

Abstract

It is well-known that global optimization of a nonconvex function, in general, is computationally intractable. Nevertheless, many objective functions that we need to optimize may be nonconvex. In practice, when working with such a nonconvex function, a very natural heuristic is to employ a coarse-to-fine search for the global optimum. A popular deterministic procedure that exemplifies this idea can be summarized briefly as follows. Consider an unconstrained optimization task of minimizing some nonconvex function. One starts from a highly smoothed version of the objective function and hopes that the smoothing eliminates most spurious local minima. More ideally, one hopes that the highly smoothed function would be a convex function, whose global minimum can be found efficiently. Once the minimum of the smoothed function is found, one could gradually reduce the smoothing effect and follow the continuous path of the minimizer, eventually towards a minimum of the objective function. Empirically, people have observed that the minimum found this way has high chance to be the global minimum. Despite its empirical success, there has been little theoretical understanding about the effect of smoothing on optimization. This work rigorously studies some of the fundamental properties of the smoothing technique. In particular, we present a formal definition for the functions that can eventually become convex by smoothing. We present extremely simple sufficient condition for asymptotic convexity as well as a very simple form for an asymptotic minimizer. Our sufficient conditions hold when the objective function satisfies certain decay conditions. Our initial interest for studying this topic arise from its well-known use in geometric image alignment. The alignment problem can be formulated as an optimization task that minimizes the visual difference between the images by searching the space of transformations. Unfortunately, the cost function associated to this problem usually contains many local minima. Thus, unless very good initialization is provided, simple greedy optimization may lead to poor results. To improve the attained solution for the alignment task, we propose smoothing the objective function of the alignment task. In particular, we derive the theoretically correct image blur kernels that arise from (Gaussian) smoothing an alignment objective function. We show that, for smoothing the objective of common motion models, such as affine and homography, there exists a corresponding integral operator on the image space. We refer to the kernels of such integral operators as transformation kernels. Thus, instead of convolving the objective function with a Gaussian kernel in transformation space, we can equivalently compute an integral transform in the image space, which is much cheaper to compute.

Graduation Semester

2012-12

Permalink

http://hdl.handle.net/2142/42330

Copyright and License Information

Copyright 2012 Hossein Mobahi

Owning Collections