Files in this item
Files  Description  Format 

application/pdf Hossein_Mobahi.pdf (13MB)  (no description provided) 
Description
Title:  Optimization by Gaussian smoothing with application to geometric alignment 
Author(s):  Mobahi, Hossein 
Director of Research:  Ma, Yi 
Doctoral Committee Chair(s):  Ma, Yi 
Doctoral Committee Member(s):  Huang, Thomas S.; Forsyth, David A.; Hoiem, Derek W.; Soatto, Stefano 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Nonconvex Optimization
Homotopy Continuation Image Alignment Point Cloud Alignment Coarsetofine Optimization 
Abstract:  It is wellknown 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 coarsetofine 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 wellknown 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. 
Issue Date:  20130203 
URI:  http://hdl.handle.net/2142/42330 
Rights Information:  Copyright 2012 Hossein Mobahi 
Date Available in IDEALS:  20130203 
Date Deposited:  201212 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois