Performance measurement index for compressed sensing of structured signals

Compressed sensing/sparse signal recovery has entered a new phase, i.e. exploiting structure of signals for improved performance. Almost all the natural signals have rich structure (e.g. images, videos, speech signals, bio-signals), and we have known theoretically and empirically that exploiting such structure can improve performance. However, in the literature on compressed sensing of structured signals, the mean square error (MSE) still serves as the main (or even the only) performance index for measuring recovery quality. It's time to re-think about the use of MSE if you read the following nice paper:

Zhou Wang, AlanC.Bovik, Mean Squared Error: Love it or Leave it? A New Look at Signal Fidelity Measures, IEEE Signal Processing Magazine, vol.26, no.1, 2009, pp.98-117

The authors list the implicit assumptions when using MSE, which I quote below:

1) Signal fidelity is independent of temporal or spatial relationships between the samples of the original signal. In other words, if the original and distorted signals are randomly re-ordered in the same way, then the MSE between them will be unchanged.

2) Signal fidelity is independent of any relationship between the original signal and the error signal. For a given error signal, the MSE remains unchanged, regardless of which original signal it is added to.

3) Signal fidelity is independent of the signs of the error signal samples.

4) All signal samples are equally important to signal fidelity. 

Obviously, when we measure the recovery quality of structured signals, the above assumptions are violated.

The authors give a number of nice examples. Here is one of them:

(a) is the original image, and (b)-(d) are three images added noise. (b),(c),(d) almost have the same MSE, but clearly their recovery quality is different. MSE fails to show such difference. In contrast, the other two measurement indexes, SSIM and CW-SSIM, express well the difference.

SSIM, standing for Structural SIMilarity (SSIM) index, is proposed for structured signals, especially images. The basic form of SSIM (measuring small patches of an image) is:

which measures the similarities of three aspects of the image patches: the similarity l(x,y) of the local patch luminances (brightness values), the similarity c(x,y) of the local patch contrasts, and the similarity s(x,y) of the local patch structures. The SSIM index is computed locally within a sliding window that moves pixel-by-pixel across the image. The SSIM score of the entire image is then computed by simple averaging the SSIM values across the image.

There are many variants of the basic SSIM index. Interested people can read the paper and the references cited.

The codes of computing SSIM can be found here: https://ece.uwaterloo.ca/~z70wang/research/ssim/

Note that the SSIM index can be easily modified to measure 1-D structured signals.

Added:
Igor has two posts on SSIM in his Nuit Blanche: 

http://nuit-blanche.blogspot.com/2011/11/why-stop-there.html

http://nuit-blanche.blogspot.com/2011/11/randomized-thoughts-and-feedbacks.html

And here is the most recent improvement on SSIM:

CALIBRATING MS-SSIM FOR COMPRESSION DISTORTIONS USING MLDS, by C. Charrier, K. Knoblauch, L. T. Maloney and A. C. Bovik, ICIP 2011.