טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentRam Idan
SubjectWavelets for Graphs and their Deployment to Image Processing
DepartmentDepartment of Electrical Engineering
Supervisors Professor Israel Cohen
Professor Michael Elad
Full Thesis textFull thesis text - English Version


Abstract

In this dissertation we introduce novel methods for processing signals defined on graphs and high dimensional data clouds. Finding efficient methods to represent and process such signals is quite a challenging problem since they are non-uniformly sampled. As such, traditional signal processing methods are usually not helpful, since they are designed for data defined on regular Euclidean grids. Our solution consists of changing the way we look at the data by ``putting an order in the disorder''.

We develop several methods which enable us to return to the comfort zone of uniformly sampled one dimensional (1D) signal processing, by reordering the given topologically complicated data. This makes the processing of the resulting signals much simpler and intuitive, and allows us to develop new algorithms which are based on common 1D methods. Throughout this work we explore the use of these algorithms mainly for image processing, and demonstrate high quality results.


Our work starts by introducing a generalized tree-based wavelet transform (GTBWT), which is an extension of the 1D discrete wavelet transform to functions defined on graphs and high dimensional data points. This transform is calculated by adding data-dependent permutation operators into the classical 1D wavelet filter-bank implementation. We show how this transform is applicable to images, by converting them to graph-structures. This is achieved by breaking the image into overlapping patches and referring to the resulting set of points as a point-cloud. This leads to a multi-scale and highly robust decomposition that is adaptive to the image content and is highly effective for sparsifying it. We use the above construction to further develop a redundant tree-based wavelet transform (RTBWT) frame, which is a redundant image representation that can be used as a powerful sparsity-promoting regularizer in general inverse problems in image processing. We demonstrate the application of the RTBWT to image denoising and deblurring, and even harness it for face image compression.


Finally, we strip-down the proposed scheme to its core, and introduce an image processing scheme that is based only on permutations obtained by reordering of its patches, without the multi-scale treatment used by the aforementioned transforms. We reorder the corrupted image pixels using such permutations, and apply on the resulting 1D signal either relatively simple one-dimensional smoothing operations (such as filtering or interpolation) or the non-local means (NL-means) algorithm. We demonstrate the application of this scheme to image denoising and inpainting.