«

»

Aug 28

Model-Based Dynamic Sampling

Introduction

The goal of our research is to build a dynamic image sampling framework where only the most informative pixels are sampled in order to get the highest fidelity image with the least number of samples. Our algorithm, which we call Model Based Dynamic Sampling (MBDS) [1], is based on the principals of Bayesian Experimental Design (BED) and is adapted to allow a broad class of posterior distributions so that an application specific model can be selected. It also allows for the incorporation of a general class of constraints in the measurement projection, which is essential in many applications [1].

Overview of the MBDS Algorithm

Let y^{(k)} denote the vector composed of the first k measurements, and let x denote the unknown signal. Then on the k^{th} measurement, the entire vector of past and present measurements is given by
\begin{equation}
y^{(k)} = A^{(k)} x + w^{(k)},
\end{equation}
where A^{(k)} is the projection matrix, and w^{(k)} is Gaussian measurement noise that is assumed to be both independent of x and to have independent components, with variance \sigma_{noise}^2.

Since we are limited to pixel-wise measurements the rows of A^{(k)} are vectors with 1 where a measurement is made and 0 everywhere else. Our goal will then be to add new rows to A^{(k)} so as to acquire the most informative pixels. For this we first model the posterior distribution p_k \left( x \vert y^{(k)} \right). Then we find the pixel location where the posterior variance is largest and measure that location in the next iteration.

The MBDS framework has been constructed to allow the use of a wide range of prior distributions. The reason for this is that different images are best represented by different priors. Although, as a result of this modification there is no closed form expression for the posterior variance, and therefore we estimate it using samples from the posterior distribution. Given we have L samples \left\lbrace X^{(k,1)}, X^{(k,2)}, ....... X^{(k,L)}, \right\rbrace from p_k \left( x \vert y^{(k)} \right), the mean and variance of pixel location s is given by,
\begin{equation}
\hat{\mu}_s^{(k)} = \frac{1}{L} \displaystyle\sum\limits_{i=1} ^{L} X^{(k,i)}_{s}
\end{equation}
\begin{equation}
\hat{\sigma}^{(k)}_s= \frac{1}{L-1} \displaystyle\sum\limits_{i=1} ^{L} \left( X^{(k,i)}_s - \hat{\mu}^{(k)} _s \right)^2
\end{equation}

Then by finding the location where this quantity is largest, we update the A matrix,

\begin{equation}
A^{(k+1)} = \begin{pmatrix}
A^{(k)} \\ m^{(k)t}
\end{pmatrix}.
\label{New_meas_A}
\end{equation}

Sampling from the Posterior Distribution

For most images sampling from the posterior distribution is intractable. Therefore, we introduce a computationally efficient method for computing the stochastic samples through a local updating technique. Instead of sampling from p_k \left( x \vert y^{(k)} \right) at each iteration, we store L stochastic samples in memory, and update only a window surrounding the measured pixel location s.

Consider that we have L stochastic samples from the previous iteration  \left\lbrace X^{(k-1,1)}, X^{(k-1,2)} ...X^{(k-1,L)}\right\rbrace. We now sample from p_k \left( w_s \vert y^{(k)}, w_{\tilde{s}}  \right) , the conditional distribution of the window surrounding the measured pixel, w_s, given all the measurements, y^{(k)}, and the other pixels in the image, w_{\tilde{s}}  , to generate samples  \left\lbrace W^{(k,1)}_s, W^{(k,2)}_s ...W^{(k,L)}_s\right\rbrace. Next, we use these stochastically generated samples to replace these corresponding windows of pixels in the L stochastic samples  \left\lbrace X^{(k-1,1)}, X^{(k-1,2)} ...X^{(k-1,L)}\right\rbrace to form  \left\lbrace X^{(k,1)}, X^{(k,2)} ...X^{(k,L)}\right\rbrace. In our implementation we use the Hastings-Metropolis algorithm to generate these stochastic samples.

Results

We use the MBDS algorithm to measure two images, one a synthetic image generated by myself, and the other an image given to us by Prof. Kaldindi's group. The results are shown as videos, where each frame is after 1% of new samples are added. The first image in each video shows the sampling locations in red, and the second the measured image, and the third the reconstructed image.

MBDS used to measure a synthetic image. Images show the results after approximately 14% of the image is measured. 

Synth

Original Image

Sample_Matrix_1435

Selected Samples

Measured_Image_1435

Measured Image

MAP_Estimate_1435

Reconstructed Image

This video shows from left to right, the sampling locations, the measured image and the reconstructed image. 1% of new samples are added between frames. 

MBDS used to measure an image provided by Prof. Kaldindi's group. Images show the results after approximately 43% of the image is measured. 

G_tech

Original Image

Sample_Matrix_4300

Selected Samples

Measured_Image_4300

Measured Image

MAP_Estimate_4300

Reconstructed Image

This video shows from left to right, the sampling locations, the measured image and the reconstructed image. 1% of new samples are added between frames. 

References

[1]. Dilshan Godaliyadda, G.M.; Buzzard, G.T.; Bouman, C.A, "A model-based framework for fast dynamic image sampling," Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on , vol., no., pp.1822,1826, 4-9 May 2014