Image interpolation from Manhattan cutset samples via orthogonal gradient method

Cutset sampling is a new approach to image sampling where 2D data is recorded densely along intersecting lines. A special case of cutset sampling is Manhattan sampling, where data is sampled densely along evenly-spaced rows and columns. This paper presents a new method for interpolating pixels from their Manhattan samples called the orthogonal gradient (OG) algorithm, which exploits the fact that pixels tend to be correlated along the direction orthogonal to the image gradient. Such an approach is enhanced by Manhattan sampling, where dense sampling along straight lines allows for better reconstruction of both sharp and soft image edges. In particular, the OG algorithm alternates between solving a constrained optimization problem, and changing the weights of the optimization problem according to the direction of the gradient of each new image estimate. The proposed method improves upon previous Manhattan interpolation algorithms, both qualitatively as well as in mean-squared error. Furthermore, unlike the previous algorithms, the OG algorithm can easily be extended to any sampling scheme.