Ph.D Thesis
Ph.D Student Koren Yair Multiscale Methods for Image Processing Department of Computer Science Professor Irad Yavneh

Abstract

Multigrid methods were established as optimal solvers for elliptic partial differential equations in the 1970s. Thereafter, many applications of these methods to image processing and computer vision problems were proposed. These methods are generally used as black boxes in order to solve partial differential equations within computer vision algorithms. Speed of computation is the main advantage gained by this approach. But multiscale methods are not inherently limited to speeding up the solution of differential equations. Indeed, algebraic multigrid was later developed to solve problems which are irregular or even grid-less. In this work, we have used insights from classical multigrid approaches in order to invent new methods which solve other problems. As a result, better solutions to difficult problems are attained and speed is but the minor benefit of these methods. We focus in this work on image processing and scientific computing problems, with an emphasis on quantization. Chapter 1 is an introduction to the quantization problem and a discussion of the hardness of it. In chapter 2 we adapt a multigrid full approximation scheme (FAS) to the scalar quantization problem. In chapter 3 we introduce a novel multiscale redistribution scheme over the representation levels of a quantizer in order to avoid local minima. In chapter 4 we describe an extremely fast bottom up greedy aggregation algorithm. The algorithm initializes a large amount of representatives and then aggregates them in pairs until the required number of representatives is reached. In chapter 5 we describe an improvement to the LBG quantization algorithm with respect to speed of computation and final result. The algorithm calculates the optimal amount of splitting needed per representation level instead of splitting each representative, arbitrarily, into two. Chapter 6 deals with the design of optimal filters in order to distinguish between two hyper-spectral sources with a regular camera. This problem is related to quantization as we are trying to find a more concise representation of the originally vast amount of data. In chapter 7 we deal with eigenproblems and an application to Google's PageRank problem. We apply an algebraic multigrid framework to the eigenvector problem when the matrix is stochastic. All of the algorithms described in this work have been implemented and tested. Moreover, a simple and friendly graphical interface wrapping these implementations may be downloaded at http://www.cs.technion.ac.il/~irad/Quantization. The tool is an integral part of this work.