Header logo is

Image Construction by Linear Programming


Conference Paper


A common way of image denoising is to project a noisy image to the subspace of admissible images made for instance by PCA. However, a major drawback of this method is that all pixels are updated by the projection, even when only a few pixels are corrupted by noise or occlusion. We propose a new method to identify the noisy pixels by 1-norm penalization and update the identified pixels only. The identification and updating of noisy pixels are formulated as one linear program which can be solved efficiently. Especially, one can apply the ν-trick to directly specify the fraction of pixels to be reconstructed. Moreover, we extend the linear program to be able to exploit prior knowledge that occlusions often appear in contiguous blocks (e.g. sunglasses on faces). The basic idea is to penalize boundary points and interior points of the occluded area differently. We are able to show the ν-property also for this extended LP leading a method which is easy to use. Experimental results impressively demonstrate the power of our approach.

Author(s): Tsuda, K. and Rätsch, G.
Book Title: Advances in Neural Information Processing Systems 16
Journal: Advances in Neural Information Processing Systems 16
Pages: 57-64
Year: 2004
Month: June
Day: 0
Editors: Thrun, S., L.K. Saul, B. Sch{\"o}lkopf
Publisher: MIT Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Seventeenth Annual Conference on Neural Information Processing Systems (NIPS 2003)
Event Place: Vancouver, BC, Canada

Address: Cambridge, MA, USA
Digital: 0
ISBN: 0-262-20152-6
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Image Construction by Linear Programming},
  author = {Tsuda, K. and R{\"a}tsch, G.},
  journal = {Advances in Neural Information Processing Systems 16},
  booktitle = {Advances in Neural Information Processing Systems 16},
  pages = {57-64},
  editors = {Thrun, S., L.K. Saul, B. Sch{\"o}lkopf},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = jun,
  year = {2004},
  month_numeric = {6}