Exact histogram specification for digital images using a variational approach. (English) Zbl 1329.49077
Summary: We consider the problem of exact histogram specification for digital (quantized) images. The goal is to transform the input digital image into an output (also digital) image that follows a prescribed histogram. Classical histogram modification methods are designed for real-valued images where all pixels have different values, so exact histogram specification is straightforward. Digital images typically have numerous pixels which share the same value. If one imposes the prescribed histogram to a digital image, usually there are numerous ways of assigning the prescribed values to the quantized values of the image. Therefore, exact histogram specification for digital images is an ill-posed problem. In order to guarantee that any prescribed histogram will be satisfied exactly, all pixels of the input digital image must be rearranged in a strictly ordered way. Further, the obtained strict ordering must faithfully account for the specific features of the input digital image. Such a task can be realized if we are able to extract additional representative information (called auxiliary attributes) from the input digital image. This is a real challenge in exact histogram specification for digital images. We propose a new method that efficiently provides a strict and faithful ordering for all pixel values. It is based on a well designed variational approach. Noticing that the input digital image contains quantization noise, we minimize a specialized objective function whose solution is a real-valued image with slightly reduced quantization noise, which remains very close to the input digital image. We show that all the pixels of this real-valued image can be ordered in a strict way with a very high probability. Then, transforming the latter image into another digital image satisfying a specified histogram is an easy task. Numerical results show that our method outperforms by far the existing competing methods.
MSC:
| 49N90 | Applications of optimal control and differential games |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 68U10 | Computing methodologies for image processing |
Keywords:
exact histogram specification; image processing; strict-ordering; variational methods; quantization noise; smooth nonlinear optimization; convex minimization; perturbation analysisReferences:
| [1] | Arici, T., Dikbas, S., Altunbasak, Y.: A histogram modification framework and its application for image contrast enhancement. IEEE Trans. Image Process. 18(9), 1921-1935 (2009) · Zbl 1371.94028 · doi:10.1109/TIP.2009.2021548 |
| [2] | Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing, 2nd edn. Springer, Berlin (2006) · Zbl 1110.35001 |
| [3] | Avanaki, A.N.: Exact global histogram specification optimized for structural similarity. Opt. Rev. 16(6), 613-621 (2009) · doi:10.1007/s10043-009-0119-z |
| [4] | Avez, A.: Calcul Différentiel. Masson, Paris (1991) · Zbl 0502.46002 |
| [5] | Baus, F., Nikolova, M., Steidl, G.: Fully smoothed ℓ1−TV models: bounds for the minimizers and parameter choice. Tech. report, hal-00722743, v2. See http://hal.archives-ouvertes.fr/hal-00722743 · Zbl 1292.49036 |
| [6] | Bonnans, J.-F., Gilbert, J.-C., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization (Theoretical and Practical Aspects). Springer, Berlin (2003) · Zbl 1014.65045 · doi:10.1007/978-3-662-05078-1 |
| [7] | Bioucas-Dias, J.; Figueiredo, M.; Nowak, R., Total variation-based image deconvolution: a majorization-minimization approach, 14-19 May |
| [8] | Black, M., Rangarajan, A.: On the unification of line processes, outlier rejection, and robust statistics with applications to early vision. Int. J. Comput. Vis. 19, 57-91 (1996) · doi:10.1007/BF00131148 |
| [9] | De Bruijn, N.G.: Some classes of integer-valued functions. Indag. Math. 17(3) (1955) · Zbl 0067.27301 |
| [10] | Cahen, P.-J., Chabert, J.-L.: Integer-valued Polynomials. Mathematical Surveys and Monographs, vol. 48. Amer. Math. Soc., Providence (1997) · Zbl 0884.13010 |
| [11] | Chan, R.; Nikolova, M.; Wen, Y., A variational approach for exact histogram specification, No. 6667, 86-97 (2012) · doi:10.1007/978-3-642-24785-9_8 |
| [12] | Chen, S., Ramli, A.R.: Contrast enhancement using recursive mean-separate histogram equalization for scalable brightness preservation. IEEE Trans. Consum. Electron. 49(4), 1301-1309 (2003) · doi:10.1109/TCE.2003.1261233 |
| [13] | Cheng, H.D., Jiang, X.H., Sun, Y., Wang, J.: Color image segmentation: advances and prospects. Pattern Recognit. 34(12), 2259-2281 (2001) · Zbl 0991.68137 · doi:10.1016/S0031-3203(00)00149-7 |
| [14] | Ciarlet, P.G.: Introduction to Numerical Linear Algebra and Optimization. Cambridge University Press, Cambridge (1989) |
| [15] | Coltuc, D.; Bolon, P., Robust watermarking by histogram specification, No. 2, 236-239 (1999), New York |
| [16] | Coltuc, D., Bolon, P., Chassery, J.-M.: Exact histogram specification. IEEE Trans. Image Process. 15(5), 1143-1152 (2006) · doi:10.1109/TIP.2005.864170 |
| [17] | Cox, I. J.; Roy, S.; Hingorani, S. L., Dynamic histogram warping of image pairs for constant image brightness, No. 2, 366-369 (1995) |
| [18] | Delon, J.: Midway image equalization. J. Math. Imaging Vis. 21(2), 119-134 (2004) · Zbl 1433.68511 · doi:10.1023/B:JMIV.0000035178.72139.2d |
| [19] | Dontchev, A.L., Zollezi, T.: Well-Posed Optimization Problems. Springer, New York (1993) · Zbl 0797.49001 |
| [20] | Evans, L.C., Gariepy, R.F.: Measure Theory and Fine Properties of Functions. Studies in Advanced Mathematics. CRC Press, Roca Baton (1992) · Zbl 0804.28001 |
| [21] | Ferradans, S., Xia, G.-S., Peyré, G., Aujol, J.-F.: Optimal transport mixing of Gaussian texture models. Tech. report, Preprint Hal-00662720 (2012) |
| [22] | Fiacco, A., McCormic, G.: Nonlinear Programming. Classics in Applied Mathematics. SIAM, Philadelphia (1990) · Zbl 0713.90043 |
| [23] | Figueiredo, M.A.T., Bioucas-Dias, J.M., Nowak, R.D.: Majorization-minimization algorithms for wavelet-based image restoration. IEEE Trans. Image Process. 16(12), 2980-2991 (2007) · doi:10.1109/TIP.2007.909318 |
| [24] | Gonzalez, R.C., Woods, R.E.: Digital Image Processing. Publishing House of Electronics Industry, Beijing (2005) |
| [25] | Gousseau, Y., Morel, J.M.: Are natural images of bounded variation? SIAM J. Math. Anal. 33(3), 634-648 (2001) · Zbl 1002.49030 · doi:10.1137/S0036141000371150 |
| [26] | Hall, E.L.: Almost uniform distributions for computer image enhancement. IEEE Trans. Comput. C-23, 207-208 (1974) · Zbl 0283.68069 · doi:10.1109/T-C.1974.223892 |
| [27] | Hazewinkel, M. (ed.): Diophantine Equations. Encyclopaedia of Mathematics. Springer, Berlin (2001) · Zbl 1038.00003 |
| [28] | Hunter, D., Lange, K.: A tutorial on MM algorithms. Am. Stat. 58(1), 30-37 (2004) · doi:10.1198/0003130042836 |
| [29] | Jongen, H.T., Jonker, P., Twilt, F.: Nonlinear Optimization in Finite Dimensions, 1st edn. Kluwer Academic, Amsterdam (1986) · Zbl 0611.90071 |
| [30] | Kim, Y.: Contrast enhancement using brightness preserving bi-histogram equalization. IEEE Trans. Consum. Electron. 43(1), 1-8 (1997) · doi:10.1109/30.580378 |
| [31] | Lafontaine, J.: Introduction aux Variétés Différentielles, 2nd edn. EDP Sciences, France (2010) |
| [32] | Krishnan, D., Lin, P., Tai, X.: An efficient operator splitting method for noise removal in images. Commun. Comput. Phys. 1, 847-858 (2006) · Zbl 1137.94308 |
| [33] | Meyer, C.D.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000) · Zbl 0962.15001 · doi:10.1137/1.9780898719512 |
| [34] | Mignotte, M.: An energy based model for the image edge histogram specification problem. IEEE Trans. Image Process. 21, 379-386 (2012) · Zbl 1372.94179 · doi:10.1109/TIP.2011.2159804 |
| [35] | Mumford, D., Desolneux, A.: Pattern Theory: The Stochastic Analysis of Real-World Signals. A.K. Peters, Natick (2010) · Zbl 1210.94002 |
| [36] | Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program., Ser. A 103(1), 127-152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
| [37] | Portilla, J., Simoncelli, E.P.: A parametric texture model based on joint statistics of complex wavelet coefficients. Int. J. Comput. Vis. 40, 49-71 (2000) · Zbl 1012.68698 · doi:10.1023/A:1026553619983 |
| [38] | Lysaker, M., Tai, X.: Noise removal using smoothed normals and surface fitting. IEEE Trans. Image Process. 13(10), 1345-1357 (2004) · Zbl 1286.94022 · doi:10.1109/TIP.2004.834662 |
| [39] | Narasimhan, S., Nayar, S.: Contrast restoration of weather degraded images. IEEE Trans. Pattern Anal. Mach. Intell. 25, 713-724 (2003) · doi:10.1109/TPAMI.2003.1201821 |
| [40] | Ni, K., Bresson, X., Chan, T., Esedoglu, S.: Local histogram based segmentation using the Wasserstein distance. Int. J. Comput. Vis. 84(1), 97-111 (2009) · doi:10.1007/s11263-009-0234-0 |
| [41] | Nikolova, M.: Local strong homogeneity of a regularized estimator. SIAM J. Appl. Math. 61, 633-658 (2000) · Zbl 0991.94015 · doi:10.1137/S0036139997327794 |
| [42] | Nikolova, M.: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vis. 20(1-2), 99-120 (2004) · Zbl 1366.94065 · doi:10.1023/B:JMIV.0000011920.58935.9c |
| [43] | Nikolova, M.: Weakly constrained minimization. Application to the estimation of images and signals involving constant regions. J. Math. Imaging Vis. 21(2), 155-175 (2004) · Zbl 1435.94081 · doi:10.1023/B:JMIV.0000035180.40477.bd |
| [44] | Pólya, G.: Über ganzwertige ganze Funktionen. Rend. Circ. Mat. Palermo 40, 1-16 (1915) · JFM 45.0655.02 · doi:10.1007/BF03014836 |
| [45] | Pratt, W.K.: Digital Image Processing, 2nd edn. Wiley, New York (1991) · Zbl 0728.68142 |
| [46] | Rosenfeld, A., Kak, K.: Digital Picture Processing. Academic Press, Upper Saddle River (1982) · Zbl 0564.94001 |
| [47] | Reza, A.M.: Realization of the contrast limited adaptive histogram equalization (CLAHE) for real-time image enhancement. J. VLSI Signal Process. 38(1), 35-44 (2004) · doi:10.1023/B:VLSI.0000028532.53893.82 |
| [48] | Rolland, J.-P., Vo, V., Bloss, B., Abbey, C.K.: Fast algorithms for histogram matching: Application to texture synthesis. J. Electron. Imaging 9(1), 39-45 (2000) · doi:10.1117/1.482725 |
| [49] | Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [50] | Russ, J.C.: The Image Processing Handbook, 2nd edn. CRC Press, New York (1995) · Zbl 1204.68248 |
| [51] | Sapiro, G.; Caselles, V., Histogram modification via partial differential equations, No. 3, 632-635 (2002), New York |
| [52] | Sen, D., Sankar, P.: Automatic exact histogram specification for contrast enhancement and visual system based quantitative evaluation. IEEE Trans. Image Process. 20, 1211-1220 (2011) · Zbl 1372.94229 · doi:10.1109/TIP.2010.2083676 |
| [53] | Sim, K., Tso, C., Tan, Y.: Recursive sub-image histogram equalization applied to gray scale images. Pattern Recognit. Lett. 28, 1209-1221 (2007) · doi:10.1016/j.patrec.2007.02.003 |
| [54] | Tan, T., Sim, K., Tso, C.: Image enhancement using background brightness preserving histogram equalisation. Electron. Lett. 48(3), 155-157 (2012) · doi:10.1049/el.2011.3421 |
| [55] | Vogel, C., Oman, M.: Iterative method for total variation denoising. SIAM J. Sci. Comput. 17, 227-238 (1996) · Zbl 0847.65083 · doi:10.1137/0917016 |
| [56] | Wan, Y., Shi, D.: Joint exact histogram specification and image enhancement through the wavelet transform. IEEE Trans. Image Process. 16(9), 2245-2250 (2007) · doi:10.1109/TIP.2007.902332 |
| [57] | Wang, C., Ye, Z.: Brightness preserving histogram equalization with maximum entropy: a variational perspective. IEEE Trans. Consum. Electron. 51(4), 1326-1334 (2005) · doi:10.1109/TCE.2005.1561863 |
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.
