Graduation Year

2015

Document Type

Dissertation

Degree

Ph.D.

Degree Name

Doctor of Philosophy (Ph.D.)

Degree Granting Department

Computer Science and Engineering

Major Professor

Sudeep Sarkar, Ph.D.

Co-Major Professor

Sanjukta Bhanja, Ph.D.

Committee Member

Srinivas Katkoori, Ph.D.

Committee Member

Xiaoning Qian, Ph.D.

Committee Member

Clifford R. Merz, Ph.D.

Keywords

Energy Minimization, Nanoscale Image Processing, Non-Boolean Computing, Quadratic Optimization

Abstract

Quadratic optimization problems arise in various real world application domains including engineering design, microeconomics, genetic algorithms, integrated circuit chip design, probabilistic graphical models and computer vision. In particular, there are many problems in computer vision that require binary quadratic optimization such as motion segmentation, correspondences, figure-ground segmentation, clustering, grouping, subgraph matching, and digital matting. The objective of an optimization algorithm can be related to the state of a physical system, where the goal is to bring the initial arbitrary state of the system to a state with minimum possible energy. By recognizing that the Hamiltonian of nanomagnets can be expressed in a quadratic form, we exploit the energy minimization aspect of these nanomagnets to solve the quadratic optimization problem in a direct manner. Most hard problems especially in computer vision can be naturally cast as energy minimization problems and solving these using traditional techniques like simulated annealing, graph cuts evidently associate with exorbitant computational efforts. In this dissertation, transcoding the conceptual crossover between the magnetic Hamiltonian and the optimization problem, we envision a nanomagnetic coprocessor with a grid of nanomagnets embracing an optimization heuristic enabling to solve energy minimization in a single clock cycle. We will essentially be solving an optimization problem with each input-and-readout cycle as compared to orders of magnitude more clock cycles that would be needed in a Boolean logic circuit. The dissertation presents results for quadratic minimization problem in the context of perceptual organization of edges in computer vision and compare quality of results using traditional optimization methods and that expected from magnetic computing. The dissertation also presents image processing algorithms for analysis of results produced by actual fabrication of the magnetic systems.

Share

COinS