  We consider the problem of removing and replacing clouds in satellite image
sequences, which has a wide range of applications in remote sensing. Our
approach first detects and removes the cloud-contaminated part of the image
sequences. It then recovers the missing scenes from the clean parts using the
proposed "TECROMAC" (TEmporally Contiguous RObust MAtrix Completion) objective.
The objective function balances temporal smoothness with a low rank solution
while staying close to the original observations. The matrix whose the rows are
pixels and columnsare days corresponding to the image, has low-rank because the
pixels reflect land-types such as vegetation, roads and lakes and there are
relatively few variations as a result. We provide efficient optimization
algorithms for TECROMAC, so we can exploit images containing millions of
pixels. Empirical results on real satellite image sequences, as well as
simulated data, demonstrate that our approach is able to recover underlying
images from heavily cloud-contaminated observations.
