Cutset sampling and reconstruction of images

Ashish Farmer*, Awlok Josan, Matthew A. Prelee, David L. Neuhoff, Thrasyvoulos N. Pappas

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations


This paper presents a new approach to sampling images in which samples are taken on a cutset with respect to a graphical image model. The cutsets considered are Manhattan grids, for example every Nth row and column of the image. Cutset sampling is motivated mainly by applications with physical constraints, e.g. a ship taking water samples along its path, but also by the fact that dense sampling along lines might permit better reconstruction of edges than conventional sampling at the same density. The main challenge in cutset sampling lies in the reconstruction of the unsampled blocks. As a first investigation, this paper uses segmentation followed by linear estimation. First, the ACA method [1] is modified to segment the cutset, followed by a binary Markov random field (MRF) inspired segmentation of the unsampled blocks. Finally, block interiors are estimated from the pixels on their boundaries, as well as their segmentation, with methods that include a generalization of bilinear interpolation and linear MMSE methods based on Gaussian MRF models or separable autocorrelation models. The resulting reconstructions are comparable to those obtained with conventional sampling at higher sampling densities, but not generally as good as conventional sampling at lower rates.

Original languageEnglish (US)
Title of host publicationICIP 2011
Subtitle of host publication2011 18th IEEE International Conference on Image Processing
Number of pages4
StatePublished - 2011
Event2011 18th IEEE International Conference on Image Processing, ICIP 2011 - Brussels, Belgium
Duration: Sep 11 2011Sep 14 2011

Publication series

NameProceedings - International Conference on Image Processing, ICIP
ISSN (Print)1522-4880


Other2011 18th IEEE International Conference on Image Processing, ICIP 2011


  • Markov random fields
  • cutsets
  • image reconstruction
  • interpolation
  • sampling

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Signal Processing


Dive into the research topics of 'Cutset sampling and reconstruction of images'. Together they form a unique fingerprint.

Cite this