Patch-dictionary method for whole image recovery

Yangyang Xu and Wotao Yin

Background

Various algorithms have been proposed for dictionary learning such as KSVD $^{[1]}$ and the online dictionary learning method $^{[2]}$ . Among those for image processing, many use image patches to form dictionaries; see $^{[3]}$ for example, which uses patch-dictionary for image denoising.

We address an open issue regarding whole-image recovery: the large number of overlapping patches lead to a large number of free coefficients in the recovery, which can cause overfitting and slow computation. This issue has limited most of the patch-based methods to the “local” or “nearly local” kinds of image processing tasks, such as denoising, inpainting, deblurring, and super-resolution. For these tasks, one or a few patches can be processed at a time, independently of the majority of the remaining patches, so the overfitting issue does not arise. We consider the more difficult “global” kind of task, such as compressive sensing and medical image recovery, where each piece of the measurements encodes the whole image and thus it is either impossible or very ineffective to process one or a few patches at a time.

Notation and our method

We shall recover an image mathbf{M} from its corrupted measurement mathbf{b}=mathcal{A}(mathbf{M})+mathbf{xi} , where denotes a linear operator, and is some noise. Depending on the applications, can take different forms.

Let $mathcal{R}_{ij}(mathbf{M})$ denote the (i,j) -th patch ( $mathcal{R}_{ij}$ is a linear operator) and assume its has an (approximately) sparse representation under a given dictionary mathbf{D} , i.e., $mathcal{R}_{ij}(mathbf{M})=mathbf{D}mathbf{y}_{ij}$ where $mathbf{y}_{ij}$ is an (approximately) sparse vector. When a set of patches together covers every pixel of , we can represent by

$mathbf{M}=(mathcal{T}_P)^{-1}sum_{(i,j)in P}mathcal{R}_{ij}^top(mathbf{D}mathbf{y}_{ij}),quad mathcal{T_P}:=sum_{(i,j)in P}mathcal{R}_{ij}$

where $mathcal{R}_{ij}^top$ is the adjoint of $mathcal{R}_{ij}$ , and $(mathcal{T}_P)^{-1}$ is an operator that averages the overlapping patches.

Now, we take as a set of covering but non-overlapping patches. Then $mathcal{T}_P=mathcal{I}$ , the identify operator. Constructing such a is equivalent to partitioning mathbf{M} into non-overlapping blocks, such as the following two partitions.

Two examples of non-overlapping patches that cover a whole image

To recover mathbf{M} from mathbf{b} , we solve the following model

$mathop{mathrm{minimize}}_{mathbf{y}}sum_{(i,j)in P}|mathbf{w}_{ij}odotmathbf{y}_{ij}|_1+frac{1}{2nu}|mathcal{A}mathcal{T}_P^{-1}(sum_{(i,j)in P}mathcal{R}_{ij}^top(mathbf{D}mathbf{y}_{ij}))-mathbf{b}|_2^2,qquadqquad(*)$

where $mathbf{w}_{ij}$ is a weight vector. The model () can be solved by many convex optimization methods, for example, YALL1 in our numerical experiements.

When a set of non-overlapping patches is used in (), the solution sometimes bears the grid artifact. An effective strategy to avoid this artifact is to solve multiple instances of () with 's that arrange their patches in different ways, like the two examples above though we use up to five different, and then take the average of the solutions. Of course, the different instants of () can be solved in parallel.

It is important to use non-overlapping patches since this limits the number of free variables in () and improves solution quality (despite the possible grid artifact). If all the overlapping patches are used, there will be far more free variables.

Selected numerical results

LEFT: image denoising results by solving () with all the overlapping patches (PSNR = 26.98); RIGHT: the same with just one set of non-overlapping patches (PSNR = 30.57)

We solve five instances of () with 's that arrange their patches in different ways. Out of the five recovered images $mathbf{M}_1,ldots,mathbf{M}_5$ , the one with the highest PSNR is denoted by $mathbf{M}_{mbox{best}}$ . We also compute $mathbf{M}_j^{av}=frac{1}{j}sum_{i=1}^jmathbf{M}_i$ , which is the running average of the first recovered images. The table below reports their PSNRs. Image PSNRs improve as more average is taken.

The quality of dictionary plays a vital role in image recovery. We tested recovering images from their compressive circulant measurements and report their PSNRs below. The four columns in each group, from left to right, correspond to: the solution to () with the learned dictionary , that with the discrete cosine transform (DCT) , that with the adaptively updated dictionary (see Sec. 2.2 of our report or $^{[3]}$ ), the solution to a total variation model. The winner is the adpatively updated dictionary.

More numerical results, as well as the technical details, can be found in our report.

Citation

Y. Xu and W. Yin. A fast patch-dictionary method for whole-image recovery. UCLA CAM report 13-38, 2013.

References

$^{[1]}$ . M. Aharon, M. Elad, and A. Bruckstein. KSVD: an algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 54(2006), pp. 4311–4322.

$^{[2]}$ . J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online dictionary learning for sparse coding, in Proceedings of the 26th Annual Iternational Conference on Machine Learning, ACM, 2009, pp. 689–696.

$^{[3]}$ . M. Elad, and M. Aharon. Image denoising via sparse and redundant representations over learned dictionaries, IEEE Transactions on Image Processing, 15(2006), pp. 3736–3745.

« Back