Full Record

Author | Mobahi, Hossein |

Title | Optimization by Gaussian smoothing with application to geometric alignment |

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

Publication Date | 2013 |

Date Accessioned | 2013-02-03 19:35:33 |

Degree | PhD |

Discipline/Department | 0112 |

Degree Level | doctoral |

University/Publisher | University of Illinois – Urbana-Champaign |

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. |

Subjects/Keywords | Nonconvex Optimization; Homotopy Continuation; Image Alignment; Point Cloud Alignment; Coarse-to-fine Optimization |

Contributors | Ma, Yi (advisor); Ma, Yi (Committee Chair); Huang, Thomas S. (committee member); Forsyth, David A. (committee member); Hoiem, Derek W. (committee member); Soatto, Stefano (committee member) |

Language | en |

Rights | Copyright 2012 Hossein Mobahi |

Country of Publication | us |

Record ID | handle:2142/42330 |

Repository | uiuc |

Date Indexed | 2020-03-09 |

Grantor | University of Illinois at Urbana-Champaign |

Issued Date | 2013-02-03 19:35:33 |

Sample Search Hits | Sample Images

…111
viii
LIST OF FIGURES
1.1
2.1
Time evolution of a Gaussian function under heat (top)
and Schrodinger (bottom) equations. Time progression is
from left *to* right. . . . . . . . . . . . . . . . . . . . . . . . . .
k(…

…σ 2 )](x),
Left *to* Right: The function g(x; σ) = [f
2
− x2
2
5
2 2
−x 2
−e
, with increasing values of σ.
where f (x) = e
Nonconvex regions are colored by pink. . . . . . . . . . . . . . 11
2.2
2.3…

…intensity values. Obviously, the correct alignment is attained at θ = −1, due
*to* reflection symmetry. The objective function for zLK is
shown in (c) and for z in (d). Blue, green and red respectively indicate local maxima, global maximum…

…x29; Segmented and rectified facade. (b),(c) Same task from
a different view. (c) Segmentation result refined *to* the
orange box by matching. (d) Point-wise match between
two regions of the facades using our…

…points in P. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Optimization landscape for minimizing the function (5.19).
The spectrum from blue *to* red indicates small *to* large values.
Top Row : Input P, which is a rotated version of Q…

…Middle
Row : Transformed P *to* match Q using ICP. Bottom Row:
Transformed P *to* match Q using proposed method. . . . . . .
Top Row : Input P, which is a rotated version of Q. Middle
Row : Transformed P *to* match Q using ICP. Bottom Row:
Transformed P *to*…

…match Q using proposed method. . . . . . .
Top Row : Input P, which is a rotated version of Q. Middle
Row : Transformed P *to* match Q using ICP. Bottom Row:
Transformed P *to* match Q using proposed method. . . . . . .
x
95
98
105
106
107
NOTATIONS…

…applications are nonconvex. Good news is, however, real
problems often have some kind of regularity and structure. Sometimes, by
recognizing and exploiting these structures, it is possible *to* find a reasonable solution for a non-convex optimization task in…