  Images of static scenes submerged beneath a wavy water surface exhibit severe
non-rigid distortions. The physics of water flow suggests that water surfaces
possess spatio-temporal smoothness and temporal periodicity. Hence they possess
a sparse representation in the 3D discrete Fourier (DFT) basis. Motivated by
this, we pose the task of restoration of such video sequences as a compressed
sensing (CS) problem. We begin by tracking a few salient feature points across
the frames of a video sequence of the submerged scene. Using these point
trajectories, we show that the motion fields at all other (non-tracked) points
can be effectively estimated using a typical CS solver. This by itself is a
novel contribution in the field of non-rigid motion estimation. We show that
this method outperforms state of the art algorithms for underwater image
restoration. We further consider a simple optical flow algorithm based on local
polynomial expansion of the image frames (PEOF). Surprisingly, we demonstrate
that PEOF is more efficient and often outperforms all the state of the art
methods in terms of numerical measures. Finally, we demonstrate that a
two-stage approach consisting of the CS step followed by PEOF much more
accurately preserves the image structure and improves the (visual as well as
numerical) video quality as compared to just the PEOF stage.
