L1-fusion: Robust linear-time image recovery from few severely corrupted copies

We address the problem of recovering an unknown image of interest, when only few, severely corrupted copies are available. We employ, for the first time in the literature, corruption-resistant L₁-Principal-Components (L₁-PCs) of the image data-set at hand. Specifically, the calculated L₁-PCs are used for reliability-based patch-by-patch fusion of the corrupted image copies into a single high-quality representation of the original image (L₁-fusion). Our experimental studies illustrate that the proposed method offers remarkable recovery results for several common corruption types, even under high corruption rate, small number of copies, and varying corruption type among copies. An additional theoretical contribution of this work is that the L₁-PC of a data matrix of non-negative entries (e.g., image data) is for the first time shown to be optimally calculable with complexity linear to the matrix dimensions - as of now, the fastest-known optimal algorithm is of polynomial complexity. In the light of this result, L₁-fusion is carried out with linear cost comparable to that of the simple copy-averaging alternative. The linear-low cost of L₁-fusion allows for the recovered image to be, optionally, further refined by means of sophisticated single-image restoration techniques.