“ProxImaL: efficient image optimization using proximal algorithms”

  • ©

Conference:


Type(s):


Title:

    ProxImaL: efficient image optimization using proximal algorithms

Session/Category Title:   OPTIMIZING IMAGE PROCESSING

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Computational photography systems are becoming increasingly diverse, while computational resources—for example on mobile platforms—are rapidly increasing. As diverse as these camera systems may be, slightly different variants of the underlying image processing tasks, such as demosaicking, deconvolution, denoising, inpainting, image fusion, and alignment, are shared between all of these systems. Formal optimization methods have recently been demonstrated to achieve state-of-the-art quality for many of these applications. Unfortunately, different combinations of natural image priors and optimization algorithms may be optimal for different problems, and implementing and testing each combination is currently a time-consuming and error-prone process. ProxImaL is a domain-specific language and compiler for image optimization problems that makes it easy to experiment with different problem formulations and algorithm choices. The language uses proximal operators as the fundamental building blocks of a variety of linear and nonlinear image formation models and cost functions, advanced image priors, and noise models. The compiler intelligently chooses the best way to translate a problem formulation and choice of optimization algorithm into an efficient solver implementation. In applications to the image processing pipeline, deconvolution in the presence of Poisson-distributed shot noise, and burst denoising, we show that a few lines of ProxImaL code can generate highly efficient solvers that achieve state-of-the-art results. We also show applications to the nonlinear and nonconvex problem of phase retrieval.

References:


    1. Almeida, M., and Figueiredo, M. 2013. Frame-based image deblurring with unknown boundary conditions using the alternating direction method of multipliers. In Proc. ICIP, 582–585.Google Scholar
    2. Attouch, H., Bolte, J., and Svaiter, B. F. 2011. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Mathematical Programming 137, 1, 91–129.Google ScholarCross Ref
    3. Beck, A., and Teboulle, M. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2, 1, 183–202. Google ScholarDigital Library
    4. Becker, S., Candès, E., and Grant, M. 2011. Templates for convex cone problems with applications to sparse signal recovery. Mathematical Programming Computation 3, 3, 165–218.Google ScholarCross Ref
    5. Bernstein, G. L., Shah, C., Lemire, C., DeVito, Z., Fisher, M., Levis, P., and Hanrahan, P. 2015. Ebb: A DSL for physical simluation on CPUs and GPUs. arXiv e-Print 1506.07577.Google Scholar
    6. Bertalmio, M., Sapiro, G., Caselles, V., and Ballester, C. 2000. Image inpainting. In Proc. SIGGRAPH, 417–424. Google ScholarDigital Library
    7. Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3, 1, 1–122. Google ScholarDigital Library
    8. Brooke, A., Kendrick, D., Meeraus, A., and Rosenthal, R. 1988. GAMS: A user’s guide. Course Technology.Google Scholar
    9. Bruck, R. 1975. An iterative solution of a variational inequality for certain monotone operators in Hilbert space. Bulletin of the American Mathematical Society 81, 5 (Sept.), 890–892.Google ScholarCross Ref
    10. Chambolle, A., and Pock, T. 2011. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40, 1, 120–145. Google ScholarDigital Library
    11. Danielyan, A., Katkovnik, V., and Egiazarian, K. 2012. BM3D frames and variational image deblurring. IEEE Trans. Image Processing 21, 4, 1715–1728. Google ScholarDigital Library
    12. Debevec, P. E., and Malik, J. 1997. Recovering high dynamic range radiance maps from photographs. In Proc. ACM SIGGRAPH, 369–378. Google ScholarDigital Library
    13. Diamond, S., and Boyd, S. 2015. Convex optimization with abstract linear operators. In Proc. IEEE ICCV. Google ScholarDigital Library
    14. Diamond, S., and Boyd, S. 2016. Matrix-free convex optimization modeling. In Optimization and Applications in Control and Data Sciences. Springer. To appear.Google Scholar
    15. Diamond, S., and Boyd, S. 2016. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research. To appear.Google Scholar
    16. Dupe, F.-X., Fadili, M., and Starck, J.-L. 2011. Inverse problems with Poisson noise: Primal and primal-dual splitting. In Proc. ICIP.Google Scholar
    17. Esser, E., Zhang, X., and Chan, T. F. 2010. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences 3, 4, 1015–1046. Google ScholarDigital Library
    18. Evangelidis, G. D., and Psarakis, E. Z. 2008. Parametric image alignment using enhanced correlation coefficient maximization. Pattern Analysis and Machine Intelligence, IEEE Transactions on 30, 10, 1858–1865. Google ScholarDigital Library
    19. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. In ACM Trans. Graph., vol. 21, ACM, 249–256. Google ScholarDigital Library
    20. Fergus, R., Singh, B., Hertzmann, A., Roweis, S. T., and Freeman, W. T. 2006. Removing camera shake from a single photograph. ACM Trans. Graph. 25, 3, 787–794. Google ScholarDigital Library
    21. Fienup, J. R. 1982. Phase retrieval algorithms: a comparison. Applied Optics 21, 15, 2758–2769.Google ScholarCross Ref
    22. Figueiredo, M., and Bioucas-Dias, J. 2010. Restoration of Poissonian images using alternating direction optimization. IEEE Trans. Image Processing 19, 12, 3133–3145. Google ScholarDigital Library
    23. Foley, T., and Hanrahan, P. 2011. Spark: Modular, compos-able shaders for graphics hardware. ACM Trans. Graph. (SIGGRAPH) 30, 4. Google ScholarDigital Library
    24. Fougner, C., and Boyd, S. 2015. Parameter selection and preconditioning for a graph form solver. arXiv e-Print 1503.08366.Google Scholar
    25. Geman, D., and Yang, C. 1995. Nonlinear image recovery with half-quadratic regularization. IEEE Trans. Image Processing 4,7, 932–946. Google ScholarDigital Library
    26. Giselsson, P., and Boyd, S. 2014. Diagonal scaling in Douglas-Rachford splitting and ADMM. In Proceedings of the 53rd IEEE Conference on Decision and Control.Google Scholar
    27. Goldstein, T., and Osher, S. 2009. The split Bregman method for ℓ1 -regularized problems. SIAM Journal on Imaging Sciences 2, 2, 323–343. Google ScholarDigital Library
    28. Grant, M., and Boyd, S., 2014. CVX: MATLAB software for disciplined convex programming, version 2.1. http://cvxr.com/cvx.Google Scholar
    29. Gu, J., Hitomi, Y., Mitsunaga, T., and Nayar, S. 2010. Coded Rolling Shutter Photography: Flexible Space-Time Sampling. In Proc. IEEE ICCP.Google Scholar
    30. Hallac, D., Leskovec, J., and Boyd, S. 2015. Network lasso: Clustering and optimization in large graphs. In Proc. ACM SIGKDD, 387–396. Google ScholarDigital Library
    31. Heide, F., Rouf, M., Hullin, M. B., Labitzke, B., Heidrich, W., and Kolb, A. 2013. High-quality computational imaging through simple lenses. ACM Trans. Graph. 32, 5, 149. Google ScholarDigital Library
    32. Heide, F., Steinberger, M., Tsai, Y.-T., Rouf, M., Pajak, D., Reddy, D., Gallo, O., Liu, J., Heidrich, W., Egiazarian, K., Kautz, J., and Pulli, K. 2014. FlexISP: A flexible camera image processing framework. ACM Trans. Graph. (SIGGRAPH Asia) 33, 6. Google ScholarDigital Library
    33. Hestenes, M., and Stiefel, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. N.B.S. 49, 6, 409–436.Google Scholar
    34. Joshi, N., Zitnick, C. L., Szeliski, R., and Kriegman, D. J. 2009. Image deblurring and denoising using color priors. In Proc. IEEE CVPR, 1550–1557.Google Scholar
    35. Krishnan, D., and Fergus, R. 2009. Fast image deconvolution using hyper-Laplacian priors. In Advances in Neural Information Processing Systems, 1033–1041.Google Scholar
    36. Krishnan, D., and Szeliski, R. 2011. Multigrid and multilevel preconditioners for computational photography. ACM Trans. Graph. 30, 6, 177. Google ScholarDigital Library
    37. Kunisch, K., and Pock, T. 2013. A bilevel optimization approach for parameter learning in variational models. SIAM Journal on Imaging Sciences 6, 2, 938–983.Google ScholarDigital Library
    38. Lehoucq, R., and Sorensen, D. 1996. Deflation techniques for an implicitly restarted Arnoldi iteration. SIAM Journal on Matrix Analysis and Applications 17, 4, 789–821. Google ScholarDigital Library
    39. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. In ACM Trans. Graph., vol. 23, 689–694. Google ScholarDigital Library
    40. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In Proc. ECCV. 377–389.Google Scholar
    41. Li, G., and Pong, T. K. 2015. Global convergence of splitting methods for nonconvex composite optimization. arXiv e-Print 1407.0753.Google Scholar
    42. Lofberg, J. 2004. YALMIP: A toolbox for modeling and optimization in MATLAB. In Proc. IEEE Int. Symp. Computed Aided Control Systems Design, 294–289.Google ScholarCross Ref
    43. Möllenhoff, T., Strekalovskiy, E., Moeller, M., and Cremers, D. 2015. The primal-dual hybrid gradient method for semiconvex splittings. SIAM Journal on Imaging Sciences 8, 2, 827–857.Google ScholarCross Ref
    44. Moreau, J.-J. 1965. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France 93, 273–299.Google Scholar
    45. Ochs, P., Chen, Y., Brox, T., and Pock, T. 2014. iPiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences 7, 2, 1388–1419.Google ScholarCross Ref
    46. O’Donoghue, B., Chu, E., Parikh, N., and Boyd, S. 2015. Operator splitting for conic optimization via homogeneous self-dual embedding. arXiv e-Print 1312.3039.Google Scholar
    47. Paige, C., and Saunders, M. 1982. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Mathematical Software 8, 1, 43–71. Google ScholarDigital Library
    48. Parikh, N., and Boyd, S. 2013. Proximal algorithms. Foundations and Trends in Optimization 1, 3, 123–231. Google ScholarDigital Library
    49. Pock, T., and Chambolle, A. 2011. Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In Proceedings of the IEEE International Conference on Computer Vision, 1762–1769. Google ScholarDigital Library
    50. Pock, T., Cremers, D., Bischof, H., and A. Chambolle. 2009. An algorithm for minimizing the Mumford-Shah functional. In Proceedings of the IEEE International Conference on Computer Vision, 1133–1140.Google Scholar
    51. Ragan-Kelley, J., Barnes, C., Adams, A., Paris, S., Durand, F., and Amarasinghe, S. 2013. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. ACM SIGPLAN 48, 6, 519–530. Google ScholarDigital Library
    52. Robini, M. C., and Zhu, Y. 2015. Generic half-quadratic optimization for image reconstruction. SIAM Journal on Imaging Sciences 8, 3, 1752–1797.Google ScholarCross Ref
    53. Rockafellar, R. 1976. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research 1, 2, 97–116. Google ScholarDigital Library
    54. Schmidt, U., and Roth, S. 2014. Shrinkage fields for effective image restoration. In Proc. IEEE CVPR, 2774–2781. Google ScholarDigital Library
    55. Sidky, E. Y., and Pan, X. 2008. Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization. Physics in medicine and biology 53, 17, 4777.Google Scholar
    56. Tian, L., and Waller, L. 2015. 3D intensity and phase imaging from light field measurements in an LED array microscope. Optica 2, 2, 104–111.Google ScholarCross Ref
    57. Tsai, Y.-T., Steinberger, M., Pajak, D., and Pulli, K. 2014. Fast ANN for high-quality collaborative filtering. In High Performance Graphics.Google Scholar
    58. Udell, M., Mohan, K., Zeng, D., Hong, J., Diamond, S., and Boyd, S. 2014. Convex optimization in Julia. Workshop on High Performance Technical Computing in Dynamic Languages. Google ScholarDigital Library
    59. Vidimice, K., Wang, S.-P., Ragan-Kelley, J., and Matusik, W. 2013. OpenFab: A programmable pipeline for multi-material fabrication. ACM Trans. Graph. (SIGGRAPH) 32, 4. Google ScholarDigital Library
    60. Wytock, M., Wang, P.-W., and Zico Kolter, J. 2015. Convex programming with fast proximal and linear operators. arXiv e-Print 1511.04815.Google Scholar
    61. Zhang, L., Wu, X., Buades, A., and Li, X. 2011. Color demosaicking by local directional interpolation and nonlocal adaptive thresholding. Journal of Electronic Imaging 20, 2, 023016–023016.Google ScholarCross Ref
    62. Zhu, Y. 2015. An augmented ADMM algorithm with application to the generalized lasso problem. Journal of Computational and Graphical Statistics, just-accepted.Google Scholar
    63. Zoran, D., and Weiss, Y. 2011. From learning models of natural image patches to whole image restoration. In Proc. IEEE ICCV, 479–486. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page: