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

y^{(k)} = A^{(k)} x + w^{(k)},

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,

\hat{\mu}_s^{(k)} = \frac{1}{L} \displaystyle\sum\limits_{i=1} ^{L} X^{(k,i)}_{s}

\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

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

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

### 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.

Original Image

Selected Samples

Measured Image

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.

Original Image

Selected Samples

Measured Image

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