| TR#: | PHD-2007-09 |
| Class: | PHD |
| Title: | Multiscale Methods for Image Processing |
| Authors: | Yair Koren |
| Supervisors: | Irad Yavneh |
| PHD-2007-09.pdf | |
| 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 gridless. 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 the scalar and vector versions 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 a bottom up extremely fast 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 hyperspectral 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, we have wrapped all vector quantization implementations with a simple and friendly graphical interface so that the reader may test and compare our algorithms with others. The graphical interface was implemented by Mahmood Yassin and the tool may be downloaded at http://www.cs.technion.ac.il/ irad/Quantization. The tool is an integral part of this work. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2007/PHD/PHD-2007-09), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the PHD technical reports of 2007
To the main CS technical reports page