×

Contrast invariant SNR and isotonic regressions. (English) Zbl 1477.68525

Summary: We design an image quality measure independent of contrast changes, which are defined as a set of transformations preserving an order between the level lines of an image. This problem can be expressed as an isotonic regression problem. Depending on the definition of a level line, the partial order between adjacent regions can be defined through chains, polytrees or directed acyclic graphs. We provide a few analytic properties of the minimizers and design original optimization procedures together with a full complexity analysis. The methods worst case complexities range from \(O(n)\) for chains, to \(O(n\log n)\) for polytrees and \(O(\frac{n^2}{\sqrt{\epsilon}})\) for directed acyclic graphs, where \(n\) is the number of pixels and \(\epsilon \) is a relative precision. The proposed algorithms have potential applications in change detection, stereo-vision, image registration, color image processing or image fusion. A C++ implementation with Matlab headers is available at https://github.com/pierre-weiss/contrast_invariant_snr.

MSC:

68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] ApS, M. (2017). The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox/index.html
[2] Ballester, C., Cubero-Castan, E., Gonzalez, M., & Morel, J. (2000). Contrast invariant image intersection. In Advanced mathematical methods in measurement and instrumentation (pp. 41-55).
[3] Ballester, C., Caselles, V., Igual, L., Verdera, J., & Rougé, B. (2006). A variational model for P+XS image fusion. International Journal of Computer Vision, 69(1), 43-58.
[4] Barlow, R., & Brunk, H. (1972). The isotonic regression problem and its dual. Journal of the American Statistical Association, 67(337), 140-147. · Zbl 0236.62050
[5] Best, M. J., & Chakravarti, N. (1990). Active set algorithms for isotonic regression; a unifying framework. Mathematical Programming, 47(1-3), 425-439. · Zbl 0715.90085
[6] Bovik, A. C. (2010). Handbook of image and video processing. Cambridge: Academic Press. · Zbl 0967.68155
[7] Boyer, C., Weiss, P., & Bigot, J. (2014). An algorithm for variable density sampling with block-constrained acquisition. SIAM Journal on Imaging Sciences, 7(2), 1080-1107. · Zbl 1343.94021
[8] Brunk, H. D. (1955). Maximum likelihood estimates of monotone parameters. The Annals of Mathematical Statistics, 26(4), 607-616. · Zbl 0066.38503
[9] Caselles, V., & Monasse, P. (2009). Geometric description of images as topographic maps. Berlin: Springer. · Zbl 1191.68759
[10] Caselles, V., Coll, B., & Morel, J.-M. (1999). Topographic maps and local contrast changes in natural images. International Journal of Computer Vision, 33(1), 5-27.
[11] Caselles, V., Coll, B., & Morel, J.-M. (2002). Geometry and color in natural images. Journal of Mathematical Imaging and Vision, 16(2), 89-105. · Zbl 0994.68167
[12] Chambolle, A., & 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. · Zbl 1255.68217
[13] Chambolle, A., & Pock, T. (2016). An introduction to continuous optimization for imaging. Acta Numerica, 25, 161-319. · Zbl 1343.65064
[14] Combettes, PL; Pesquet, J-C; Bauschke, H. (ed.); Burachik, R. (ed.); Combettes, P. (ed.); Elser, V. (ed.); Luke, D. (ed.); Wolkowicz, H. (ed.), Proximal splitting methods in signal processing, 185-212 (2011), New York · Zbl 1242.90160
[15] Deledalle, C.-A., Papadakis, N., Salmon, J., & Vaiter, S. (2017). Clear: Covariant least-square refitting with applications to image restoration. SIAM Journal on Imaging Sciences, 10(1), 243-284. · Zbl 1365.49034
[16] Delon, J. (2004). Midway image equalization. Journal of Mathematical Imaging and Vision, 21(2), 119-134. · Zbl 1433.68511
[17] Droske, M., & Rumpf, M. (2004). A variational approach to nonrigid morphological image registration. SIAM Journal on Applied Mathematics, 64(2), 668-687. · Zbl 1063.49013
[18] Dykstra, R. L., Robertson, T., et al. (1982). An algorithm for isotonic regression for two or more independent variables. The Annals of Statistics, 10(3), 708-716. · Zbl 0485.65099
[19] Ehrhardt, M. J., & Arridge, S. R. (2014). Vector-valued image processing by parallel level sets. IEEE Transactions on Image Processing, 23(1), 9-18. · Zbl 1374.94094
[20] Felzenszwalb, P. F., & Zabih, R. (2011). Dynamic programming and graph algorithms in computer vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(4), 721-740.
[21] Géraud, T., Carlinet, E., Crozet, S., & Najman, L. (2013). A quasi-linear algorithm to compute the tree of shapes of ND images. In International symposium on mathematical morphology and its applications to signal and image processing (pp. 98-110). Springer. · Zbl 1382.68261
[22] Horowitz, E., et al. (2006). Fundamentals of data structures in C++. New Delhi: Galgotia Publications.
[23] Kolmogorov, V., Pock, T., & Rolinek, M. (2016). Total variation on a tree. SIAM Journal on Imaging Sciences, 9(2), 605-636. · Zbl 1367.68331
[24] Kronrod, A. S. (1950). On functions of two variables. Uspekhi Matematicheskikh Nauk, 5(1), 24-134. · Zbl 0040.31603
[25] Kyng, R., Rao, A., & Sachdeva, S. (2015). Fast, provable algorithms for isotonic regression in all \[L_p\] Lp-norms. In Advances in neural information processing systems (pp. 2701-2709).
[26] Luss, R., Rosset, S., & Shahar, M. (2010). Decomposing isotonic regression for efficiently solving large problems. In Advances in neural information processing systems (pp. 1513-1521).
[27] Maes, F., Collignon, A., Vandermeulen, D., Marchal, G., & Suetens, P. (1997). Multimodality image registration by maximization of mutual information. IEEE Transactions on Medical Imaging, 16(2), 187-198.
[28] Matheron, G. (1975). Random sets and integral geometry. Hoboken: Wiley. · Zbl 0321.60009
[29] Moisan, L. (2012). Modeling and image processing. Lectures notes of ENS Cachan.
[30] Monasse, P., & Guichard, F. (2000). Fast computation of a contrast-invariant image representation. IEEE Transactions on Image Processing, 9(5), 860-872.
[31] Nesterov, Y. (1983). A method of solving a convex programming problem with convergence rate \[o(1/k^2)\] o(1/k2). Soviet Mathematics Doklady, 27(2), 372-376. · Zbl 0535.90071
[32] Nesterov, Y. (2013). Introductory lectures on convex optimization: A basic course (Vol. 87). New York: Springer. · Zbl 1086.90045
[33] Nesterov, Y., Nemirovskii, A., & Ye, Y. (1994). Interior-point polynomial algorithms in convex programming (Vol. 13). Philadelphia: SIAM. · Zbl 0824.90112
[34] Pardalos, P. M., & Xue, G. (1999). Algorithms for a class of isotonic regression problems. Algorithmica, 23(3), 211-222. · Zbl 0921.68045
[35] Rudin, L. I., Osher, S., & Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 60(1-4), 259-268. · Zbl 0780.49028
[36] Serra, J. (1982). Image analysis and mathematical morphology. Cambridge: Academic Press. · Zbl 0565.92001
[37] Spielman, D. A., & Teng, S.-H. (2004). Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on theory of computing (pp. 81-90). ACM. · Zbl 1192.65048
[38] Stout, Q. F. (2014). Fastest isotonic regression algorithms. Retrieved 2014 from http://web.eecs.umich.edu/ qstout/IsoRegAlg_1408HrB12.pdfHrB.
[39] Stout, Q. F. (2013). Isotonic regression via partitioning. Algorithmica, 66(1), 93-112. · Zbl 1263.05080
[40] Van Eeden, C. (1957). Maximum likelihood estimation of partially or completely ordered parameters. I. Indagationes Mathematicae, 19, 128-136. · Zbl 0086.12803
[41] Viola, P., & Wells, W. M, I. I. I. (1997). Alignment by maximization of mutual information. International Journal of Computer Vision, 24(2), 137-154.
[42] Wang, Z., Bovik, A. C., Sheikh, H. R., & Simoncelli, E. P. (2004). Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing, 13(4), 600-612.
[43] Weiss, P., Blanc-Féraud, L., & Aubert, G. (2009). Efficient schemes for total variation minimization under constraints in image processing. SIAM Journal on Scientific Computing, 31(3), 2047-2080. · Zbl 1191.94029
[44] Weiss, P., Fournier, A., Blanc-Féraud, L., & Aubert, G. (2011). On the illumination invariance of the level lines under directed light: Application to change detection. SIAM Journal on Imaging Sciences, 4(1), 448-471. · Zbl 1214.65009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.