Abstract

We consider computational imaging problems where we have an insufficient number of measurements to uniquely reconstruct the object, resulting in an ill-posed inverse problem. Rather than deal with this via the usual regularization approach, which presumes additional information which may be incorrect, we seek bounds on the pixel values of the reconstructed image. Formulating the inverse problem as an optimization problem, we find conditions for which a system’s measurements can produce a bounded result for both the linear case and the non-negative case (e.g., intensity imaging). We also consider the problem of selecting measurements to yield the most bounded results. Finally we simulate examples of the application of bounded estimation to different two-dimensional multiview systems.

© 2013 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. K. Louis, “A unified approach to regularization methods for linear ill-posed problems,” Inverse Probl. 15, 489–498 (1999).
    [CrossRef]
  2. C. L. Lawson and R. J. Hanson, Solving Least Squares Problems (Society for Industrial and Applied Mathematics, 1987).
  3. M. Fornasier and H. Rauhut, “Compressive sensing,” in Handbook of Mathematical Methods in Imaging, O. Scherzer, ed. (Springer, 2011), pp. 187–228.
  4. S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Rev. 43, 129–159 (2001).
    [CrossRef]
  5. D. L. Donoho and J. Tanner, “Sparse nonnegative solution of underdetermined linear equations by linear programming,” Proc. Natl. Acad. Sci. USA 102, 9446–9451 (2005).
    [CrossRef]
  6. A. M. Bruckstein, M. Elad, and M. Zibulevsky, “Sparse non-negative solution of a linear system of equations is unique,” 3rd International Symposium on Communications, Control and Signal Processing, 2008 (ISCCSP, 2008), pp. 762–767.
  7. A. M. Bruckstein, M. Elad, and M. Zibulevsky, “On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations,” IEEE Trans. Inf. Theory 54, 4813–4820 (2008).
    [CrossRef]
  8. M. Wang and A. Tang, “Conditions for a unique non-negative solution to an underdetermined system,” in 47th Annual Allerton Conference on Communication, Control, and Computing, 2009 (IEEE, 2009), pp. 301–307.
  9. P. E. Gill, W. Murray, and M. H. Wright, Numerical Linear Algebra and Optimization (Addison-Wesley, 1991).
  10. G. Dantzig, Linear Programming and Extensions (Princeton University, 1998).
  11. D. L. Marks and D. J. Brady, “Three-dimensional source reconstruction with a scanned pinhole camera,” Opt. Lett. 23, 820–822 (1998).
    [CrossRef]
  12. “CVX: matlab software for disciplined convex programming|CVX research, inc.” http://cvxr.com/cvx/ .
  13. M. Grant and S. Boyd, “Graph implementations for nonsmooth convex programs,” in Lecture Notes in Control and Information Sciences, V. Blondel, S. Boyd, and H. Kimura, eds. vol. 371 (Springer, 2008), pp. 95–110.

2008 (1)

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations,” IEEE Trans. Inf. Theory 54, 4813–4820 (2008).
[CrossRef]

2005 (1)

D. L. Donoho and J. Tanner, “Sparse nonnegative solution of underdetermined linear equations by linear programming,” Proc. Natl. Acad. Sci. USA 102, 9446–9451 (2005).
[CrossRef]

2001 (1)

S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Rev. 43, 129–159 (2001).
[CrossRef]

1999 (1)

A. K. Louis, “A unified approach to regularization methods for linear ill-posed problems,” Inverse Probl. 15, 489–498 (1999).
[CrossRef]

1998 (1)

Boyd, S.

M. Grant and S. Boyd, “Graph implementations for nonsmooth convex programs,” in Lecture Notes in Control and Information Sciences, V. Blondel, S. Boyd, and H. Kimura, eds. vol. 371 (Springer, 2008), pp. 95–110.

Brady, D. J.

Bruckstein, A. M.

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations,” IEEE Trans. Inf. Theory 54, 4813–4820 (2008).
[CrossRef]

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “Sparse non-negative solution of a linear system of equations is unique,” 3rd International Symposium on Communications, Control and Signal Processing, 2008 (ISCCSP, 2008), pp. 762–767.

Chen, S. S.

S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Rev. 43, 129–159 (2001).
[CrossRef]

Dantzig, G.

G. Dantzig, Linear Programming and Extensions (Princeton University, 1998).

Donoho, D. L.

D. L. Donoho and J. Tanner, “Sparse nonnegative solution of underdetermined linear equations by linear programming,” Proc. Natl. Acad. Sci. USA 102, 9446–9451 (2005).
[CrossRef]

S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Rev. 43, 129–159 (2001).
[CrossRef]

Elad, M.

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations,” IEEE Trans. Inf. Theory 54, 4813–4820 (2008).
[CrossRef]

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “Sparse non-negative solution of a linear system of equations is unique,” 3rd International Symposium on Communications, Control and Signal Processing, 2008 (ISCCSP, 2008), pp. 762–767.

Fornasier, M.

M. Fornasier and H. Rauhut, “Compressive sensing,” in Handbook of Mathematical Methods in Imaging, O. Scherzer, ed. (Springer, 2011), pp. 187–228.

Gill, P. E.

P. E. Gill, W. Murray, and M. H. Wright, Numerical Linear Algebra and Optimization (Addison-Wesley, 1991).

Grant, M.

M. Grant and S. Boyd, “Graph implementations for nonsmooth convex programs,” in Lecture Notes in Control and Information Sciences, V. Blondel, S. Boyd, and H. Kimura, eds. vol. 371 (Springer, 2008), pp. 95–110.

Hanson, R. J.

C. L. Lawson and R. J. Hanson, Solving Least Squares Problems (Society for Industrial and Applied Mathematics, 1987).

Lawson, C. L.

C. L. Lawson and R. J. Hanson, Solving Least Squares Problems (Society for Industrial and Applied Mathematics, 1987).

Louis, A. K.

A. K. Louis, “A unified approach to regularization methods for linear ill-posed problems,” Inverse Probl. 15, 489–498 (1999).
[CrossRef]

Marks, D. L.

Murray, W.

P. E. Gill, W. Murray, and M. H. Wright, Numerical Linear Algebra and Optimization (Addison-Wesley, 1991).

Rauhut, H.

M. Fornasier and H. Rauhut, “Compressive sensing,” in Handbook of Mathematical Methods in Imaging, O. Scherzer, ed. (Springer, 2011), pp. 187–228.

Saunders, M. A.

S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Rev. 43, 129–159 (2001).
[CrossRef]

Tang, A.

M. Wang and A. Tang, “Conditions for a unique non-negative solution to an underdetermined system,” in 47th Annual Allerton Conference on Communication, Control, and Computing, 2009 (IEEE, 2009), pp. 301–307.

Tanner, J.

D. L. Donoho and J. Tanner, “Sparse nonnegative solution of underdetermined linear equations by linear programming,” Proc. Natl. Acad. Sci. USA 102, 9446–9451 (2005).
[CrossRef]

Wang, M.

M. Wang and A. Tang, “Conditions for a unique non-negative solution to an underdetermined system,” in 47th Annual Allerton Conference on Communication, Control, and Computing, 2009 (IEEE, 2009), pp. 301–307.

Wright, M. H.

P. E. Gill, W. Murray, and M. H. Wright, Numerical Linear Algebra and Optimization (Addison-Wesley, 1991).

Zibulevsky, M.

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations,” IEEE Trans. Inf. Theory 54, 4813–4820 (2008).
[CrossRef]

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “Sparse non-negative solution of a linear system of equations is unique,” 3rd International Symposium on Communications, Control and Signal Processing, 2008 (ISCCSP, 2008), pp. 762–767.

IEEE Trans. Inf. Theory (1)

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations,” IEEE Trans. Inf. Theory 54, 4813–4820 (2008).
[CrossRef]

Inverse Probl. (1)

A. K. Louis, “A unified approach to regularization methods for linear ill-posed problems,” Inverse Probl. 15, 489–498 (1999).
[CrossRef]

Opt. Lett. (1)

Proc. Natl. Acad. Sci. USA (1)

D. L. Donoho and J. Tanner, “Sparse nonnegative solution of underdetermined linear equations by linear programming,” Proc. Natl. Acad. Sci. USA 102, 9446–9451 (2005).
[CrossRef]

SIAM Rev. (1)

S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Rev. 43, 129–159 (2001).
[CrossRef]

Other (8)

A. M. Bruckstein, M. Elad, and M. Zibulevsky, “Sparse non-negative solution of a linear system of equations is unique,” 3rd International Symposium on Communications, Control and Signal Processing, 2008 (ISCCSP, 2008), pp. 762–767.

C. L. Lawson and R. J. Hanson, Solving Least Squares Problems (Society for Industrial and Applied Mathematics, 1987).

M. Fornasier and H. Rauhut, “Compressive sensing,” in Handbook of Mathematical Methods in Imaging, O. Scherzer, ed. (Springer, 2011), pp. 187–228.

M. Wang and A. Tang, “Conditions for a unique non-negative solution to an underdetermined system,” in 47th Annual Allerton Conference on Communication, Control, and Computing, 2009 (IEEE, 2009), pp. 301–307.

P. E. Gill, W. Murray, and M. H. Wright, Numerical Linear Algebra and Optimization (Addison-Wesley, 1991).

G. Dantzig, Linear Programming and Extensions (Princeton University, 1998).

“CVX: matlab software for disciplined convex programming|CVX research, inc.” http://cvxr.com/cvx/ .

M. Grant and S. Boyd, “Graph implementations for nonsmooth convex programs,” in Lecture Notes in Control and Information Sciences, V. Blondel, S. Boyd, and H. Kimura, eds. vol. 371 (Springer, 2008), pp. 95–110.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (9)

Fig. 1.
Fig. 1.

Input to forward model x, a vector of pixels on the object, and output of model y, a vector of detector samples. In this paper we are concerned with bounding the potential values for each object point xk.

Fig. 2.
Fig. 2.

Two-dimensional case (two unknown pixels) with a single measurement. The solid line represents the solution to Ax=y and the shaded region represents the values of x within the bounds. a(1) is the first (and only) row of A. In this case both pixels are bounded as the solution set is only in the non-negative quadrant for a finite range.

Fig. 3.
Fig. 3.

Two-dimensional unbounded case. Lower bounds exist but not upper bounds, as the solution set to Ax=y continues to infinity in the non-negative quadrant.

Fig. 4.
Fig. 4.

Pinhole camera in the high frequency limit. We assume there is no occlusion, so each point on the detector receives light from sources along a ray through the scene.

Fig. 5.
Fig. 5.

Simulated occluding structures.

Fig. 6.
Fig. 6.

Polar plots of number of pixels seen given a single view for each view angle, and given two views, one at 0° and the other at the given range of view angles.

Fig. 7.
Fig. 7.

Two-dimensional simulated objects.

Fig. 8.
Fig. 8.

Max (a–d) and min (e–h) bounds for each pixel given the collected data for a system with the stated total collection size. Least-mean square estimate of image with the given collections shown for comparison (i–l).

Fig. 9.
Fig. 9.

Average bounds for the three objects versus total collection size.

Tables (1)

Tables Icon

Table 1. Summary of Optimization Problems to Find Bounds on kth Pixel, the Corresponding Dual Problems, and the Resulting Conditions for Existence of Boundsa

Equations (26)

Equations on this page are rendered with MathJax. Learn more.

y=f(x),
ϕ(x)=yf(x).
minx{yf(x)+μx},
minxxSubject tof(x)=y,
minxxf(x)=y.
minxxAx=y.
minxxAx=yx0,
xk(min)=minxxkAx=y,
xk(mix)=minxxkAx=y.
maxxcTxAx=y.
ATλ=ek.
y=(a1,a2)(x1x2).
(a1a2)λ=(10),
AT(λ1,λ2,,λn)=(e1,e2,,en)ATΛ=I,
xk(min)=minxxkAx=yx0,
xk(mix)=maxxxkAx=yx0.
maxxcTxAx=yx0,
x2=a1a2x1+1a2y.
x˜k(min)=minλyTλATλek,
x˜k(max)=minλyTλATλek.
K=maxλ,ββ0ATλ=ββ0,
F={x|(AA1)x=(yy1),x0}={x|Ax=y,x0}{x|A1x=y1,x0}=FF1.
(AA1)Tλ=ek.
(AA1)Tλek.
(AA1)Tλ=β,
K=maxλ,ββ0(AA1)Tλ=ββ0.

Metrics