Tuesday, March 05, 2013

SPASH: Sparse Shape Reconstruction - implementation -

After reading the following paper I wonder how the knolls presented there compare with the Rvachev functions (use chrome to read this more complete russian wikipedia entry). Some of that work seems to have morphed into the F-rep acronym and a nice introduction is given in this pdf. I use these functions every once in while to produce complex geometries very rapidily. One of the attraction of the method was the fact that the function is actually differentiable as opposed to the Boolean functions that are not. 

Without further due here is today's SPASH paper: Sparse Shape Reconstruction by Alireza Aghasi and Justin Romberg. The abstract reads:
This paper introduces a new shape-based image reconstruction technique applicable to a large class of imaging problems formulated in a variational sense. Given a collection of shape priors (a shape dictionary), we define our problem as choosing the right elements and geometrically composing them through basic set operations to characterize desired regions in the image. This combinatorial problem can be relaxed and then solved using classical descent methods. The main component of this relaxation is forming certain compactly supported functions which we call “knolls”,and reformulating the shape representation as a basis expansion in terms of such functions. To select suitable elements of the dictionary, our problem ultimately reduces to solving a nonlinear program with sparsity constraints. We provide a new sparse nonlinear reconstruction technique to approach this problem. The performance of proposed technique is demonstrated with some standard imaging problems including image segmentation, X-ray tomography and diffusive tomography.

An implementation is available from the SPASH page:

SPASH is a Matlab implementation of the sparse shape reconstruction idea proposed by Aghasi and Romberg. Two sample programs are made available for public access which can be further extended or modified to suit other imaging applications. The package is subject to update and more open access tools will be available in the future.

Demo 1: conains the code for segmentation with missing pixels. The zipped folder contains a Demo file (Demo_CV_Rec.m) which performs the sparse segmentation iteratively. All program settings are available and controlable via setting_file.m . The program also requires a dictionary file (M.mat) containing the shape information. The supplementary zipped folder contains codes that would be helpful in generating a shape dictionary.  
Demo 2:  conains the code for a text recognition (Captcha) example. The zipped folder contains a Demo file (Demo_CV_Rec.m) which iteratively performs a segmentation and identifies the underlying characters. All program settings are available insetting_file.m. The program also requires a dictionary file (M.mat) and an indexing rule (IndexPack.Mat). The supplementary zipped folder contains codes that would be helpful in generating a desired dictionary and the corresponding indexing pack. For a faster runtime, the default example uses 5760 character shapes. However, the supplementary codes can generate dictionaries and index rules for larger problems such as the one proposed in the original paper.

 Here a video presentation about the R-functions:

No comments: