From mathematical morphology to machine learning of image operators. (English) Zbl 07595686
Summary: Morphological image operators are a class of non-linear image mappings studied in Mathematical Morphology. Many significant theoretical results regarding the characterization of families of image operators, their properties, and representations are derived from lattice theory, the underlying foundation of Mathematical Morphology. A fundamental representation result is a pair of canonical decompositions for any translation-invariant operator as a union of sup-generating or an intersection of inf-generating operators, which in turn can be written in terms of two basic operators, erosions and dilations. Thus, in practice, a toolbox with functional operators can be built by composing erosions and dilations, and then operators of the toolbox can be further combined to solve image processing problems. However, designing image operators by hand may become a daunting task for complex image processing tasks, and this motivated the development of machine learning based approaches. This paper reviews the main contributions around this theme made by the authors and their collaborators over the years. The review covers the relevant theoretical elements, particularly the canonical decomposition theorem, a formulation of the learning problem, some methods to solve it, and algorithms for finding computationally efficient representations. More recent contributions included in this review are related to families of operators (hypothesis spaces) organized as lattice structures where a suitable subfamily of operators is searched through the minimization of U-curve cost functions. A brief account of the connections between morphological image operator learning and deep learning is also included.
MSC:
| 68U10 | Computing methodologies for image processing |
| 68T10 | Pattern recognition, speech recognition |
| 06E30 | Boolean functions |
| 06D50 | Lattices and duality |
Keywords:
mathematical morphology; image operator; machine learning; automatic design; operator representation; operator decompositionReferences:
| [1] | Abu-Mostafa, Y., Lin, H., Magdon-Ismail, M.: Learning From Data. AMLBook (2012) |
| [2] | Atashpaz-Gargari, E., Reis, M., Braga-Neto, U., Barrera, J., Dougherty, E.: A fast branch-and-bound algorithm for U-curve feature selection. Pattern Recognit. (2018). doi:10.1016/j.patcog.2017.08.013 |
| [3] | Banon, G., Barrera, J.: Minimal representations for translation-invariant set mappings by Mathematical Morphology. SIAM J. Appl. Math. (1991). doi:10.1137/0151091 · Zbl 0742.68085 |
| [4] | Banon, G., Barrera, J.: Decomposition of mappings between complete lattices by Mathematical Morphology. Part I. General lattices. Signal Process. (1993). doi:10.1016/0165-1684(93)90015-3 |
| [5] | Banon, G.; Barrera, J., Bases da Morfologia Matemática para a Análise de Imagens Binárias (1994), Recife, PE, Brazil: IX Escola de Computação, Recife, PE, Brazil |
| [6] | Barrera, J., Salas, G.: Set operations on closed intervals and their applications to the automatic programming of morphological machines. J. Electron. Imaging (1996). doi:10.1117/12.240717 |
| [7] | Barrera, J., Banon, G., Lotufo, R.: Mathematical morphology toolbox for the khoros system. In: Proceedings of the SPIE 2300, Image Algebra and Morphological Image Processing V, 30 June 1994. SPIE (1993). doi:10.1117/12.179195 |
| [8] | Barrera, J., Dougherty, E., Tomita, N.: Automatic programming of binary morphological machines by design of statistically optimal operators in the context of computational learning theory. J. Electron. Imag. (1997). doi:10.1117/12.260010 |
| [9] | Barrera, J., Banon, G., Lotufo, R., Hirata, R., Jr.: MMach: a mathematical morphology toolbox for the KHOROS system. J. Electron. Imaging (1998). doi:10.1117/1.482637 |
| [10] | Barrera, J., Terada, R., Lotufo, R.A., Hirata, N.S.T., Hirata, R., Jr., Zampirolli, F.A.: An OCR based on Mathematical Morphology. In: Nonlinear Image Processing IX. Proceedings of SPIE, vol. 3304, pp. 197-208 (1998). doi:10.1117/12.304600 |
| [11] | Barrera, J., Terada, R., Hirata, R., Jr., Hirata, N.: Automatic programming of morphological machines by PAC learning. Fundam. Inform. (2000). doi:10.3233/FI-2000-411208 · Zbl 0958.68140 |
| [12] | Beucher, S.: Watersheds of functions and picture segmentation. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 82), pp. 1928-1931 (1982). doi:10.1109/ICASSP.1982.1171424 |
| [13] | Brun, M., Dougherty, E., Hirata, R., Barrera, J.: Design of optimal binary filters under joint multiresolution-envelope constraint. Pattern Recognit. Lett. (2003). doi:10.1016/S0167-8655(02)00217-9 · Zbl 1053.68111 |
| [14] | Brun, M., Hirata, R., Jr., Barrera, J., Dougherty, E.: Nonlinear filter design using envelopes. J. Math. Imaging Vis. (2004). doi:10.1023/B:JMIV.0000026558.10581.e6 · Zbl 1478.94096 |
| [15] | Castro, J.: Model selection for learning boolean hypothesis. PhD thesis, Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil (2018). doi:10.11606/T.45.2019.tde-02042019-231050 |
| [16] | Dellamonica, D., Jr., Silva, P., Humes, C., Jr., Hirata, N., Barrera, J.: An exact algorithm for optimal MAE stack filter design. IEEE Trans. Image Process. (2007). doi:10.1109/TIP.2006.888358 |
| [17] | Dornelles, M., Hirata, N.: A genetic algorithm based approach for combining binary image operators. In: Proceedings of 21st International Conference on Pattern Recognition, pp. 3184-3187 (2012) |
| [18] | Dornelles, M., Hirata, N.: Selection of windows for W-operator combination from entropy based ranking. In: 28th SIBGRAPI Conference on Graphics, Patterns and Images, pp. 64-71 (2015) |
| [19] | Dougherty, E.: Optimal mean-square N-observation digital morphological filters I. Optimal binary filters. CVGIP Image Underst. (1992). doi:10.1016/1049-9660(92)90006-O · Zbl 0777.68084 |
| [20] | Dougherty, ER; Giardina, CR, Error bounds for morphologically derived measurements, SIAM J. Appl. Math. (1987) · Zbl 0631.68079 · doi:10.1137/0147028 |
| [21] | Dougherty, ER; Haralick, M., Unification of Nonlinear Filtering in the Context of Binary Logical Calculus, Part I: Binary Filters, J. Math. Imaging Vis., 2, 2, 173-183 (1992) · Zbl 0814.93068 · doi:10.1007/bf00118588 |
| [22] | Dougherty, E., Lotufo, R.: Hands-on Morphological Image Processing, vol. 59. SPIE Press, Bellingham (2003) |
| [23] | Dougherty, E.R., Barrera, J., Mozelle, G., Seungchan, K., Brun, M.: Multiresolution analysis for optimal binary filters. J. Math. Imaging Vis. (2001). doi:10.1023/A:1008311431244 · Zbl 0990.68177 |
| [24] | Estrela, G.; Gubitoso, M.; Ferreira, C.; Barrera, J.; Reis, M., An efficient, parallelized algorithm for optimal conditional entropy-based feature selection, Entropy (2020) · doi:10.3390/e22040492 |
| [25] | Franchi, G.; Fehri, A.; Yao, A., Deep morphological networks, Pattern Recognit. (2020) · doi:10.1016/j.patcog.2020.107246 |
| [26] | Freeman, H., Computer Processing of Line-Drawing Images, ACM Comput., 6, 1, 57-97 (1974) · Zbl 0287.68067 · doi:10.1145/356625.356627 |
| [27] | Gonzalez, R.; Woods, R., Digital Image Processing (2006), USA: Prentice-Hall Inc, USA |
| [28] | Goodfellow, I.; Bengio, Y.; Courville, A., Deep Learning (2016), Cambridge: MIT Press, Cambridge · Zbl 1373.68009 |
| [29] | Goutsias, J., Morphological analysis of discrete random shapes, J. Math. Imaging Vis. (1992) · Zbl 0797.68169 · doi:10.1007/BF00118590 |
| [30] | Haralick, R.; Sternberg, S.; Zhuang, X., Image analysis using mathematical morphology, IEEE Trans. Pattern Anal. Mach. Intell. (1987) · doi:10.1109/TPAMI.1987.4767941 |
| [31] | Harvey, N., Marshall, S.: The use of genetic algorithms in morphological filter design. Signal Process. Image Commun. (1996). doi:10.1016/0923-5965(95)00033-X |
| [32] | Hashimoto, R., Barrera, J.: From the sup-decomposition to sequential decompositions. J. Math. Imaging Vis. (2001). doi:10.1023/A:1012276422769 · Zbl 1014.68209 |
| [33] | Hashimoto, R.; Barrera, J., Sup-Compact and Inf-Compact Representations of \(W\)-Operators, Fundam. Inform., 45, 4, 283-294 (2001) · Zbl 0974.68223 |
| [34] | Hashimoto, R., Barrera, J.: A note on Park and Chin’s algorithm. IEEE Trans. Pattern Anal. Mach. Intell. (2002). doi:10.1109/34.982891 |
| [35] | Hashimoto, R., Barrera, J.: A greedy algorithm for decomposing convex structuring elements. J. Math. Imaging Vis. (2003). doi:10.1023/A:1022847527229 · Zbl 1020.68105 |
| [36] | Hashimoto, R., Barrera, J., Ferreira, C.: A combinatorial optimization technique for the sequential decomposition of erosions and dilations. J. Math. Imaging Vis. (2000). doi:10.1023/A:1008373522375 · Zbl 1055.90584 |
| [37] | Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2009), New York, NY, USA: Springer Science and Business Media, New York, NY, USA · Zbl 1273.62005 · doi:10.1007/978-0-387-84858-7 |
| [38] | Heijmans, H., Morphological Image Operators (1994), Boston, MA, USA: Academic Press, Boston, MA, USA · Zbl 0869.68119 |
| [39] | Hils, D., Visual languages and computing survey: Data flow visual programming languages, J. Vis. Lang. Comput., 3, 1, 69-101 (1992) · doi:10.1016/1045-926X(92)90034-J |
| [40] | Hirata, N.: Multilevel training of binary morphological operators. IEEE Trans. Pattern Anal. Mach. Intell. (2009). doi:10.1109/TPAMI.2008.118 |
| [41] | Hirata, N., Barrera, J.: A unifying view for stack filter design based on graph search methods. Pattern Recognit. (2005). doi:10.1016/j.patcog.2005.02.018 |
| [42] | Hirata, N.S.T., Papakostas, G.A.: Omacn hine-learning morphological image operators. Mathematics (2021). doi:10.3390/math9161854 |
| [43] | Hirata, N., Barrera, J., Dougherty, E.: Design of statistically optimal stack filters. In: XII Brazilian Symposium on Computer Graphics and Image Processing, pp. 265-274 (1999). doi:10.1109/SIBGRA.1999.805734 |
| [44] | Hirata, N., Dougherty, E., Barrera, J.: A switching algorithm for design of optimal increasing binary filters over large windows. Pattern Recognit. (2000). doi:10.1016/S0031-3203(99)00165-X |
| [45] | Hirata, N., Dougherty, E., Barrera, J.: Iterative design of morphological binary image operators. Opt. Eng. (2000). doi:10.1117/1.1327178 |
| [46] | Hirata, R., Jr., Dougherty, E., Barrera, J.: Aperture filters. Signal Process. (2000). doi:10.1016/S0165-1684(99)00162-0 · Zbl 1037.94502 |
| [47] | Hirata, N., Barrera, J., Terada, R., Dougherty, E.: The incremental splitting of intervals algorithm for the design of binary image operators. In: Talbot, H., Beare, R. (eds.) Proceedings of 6th International Symposium on Mathematical Morphology, pp. 219-228. CSIRO Publishing, Clayton (2002) |
| [48] | Hirata, R.; Barrera, J.; Hashimoto, R.; Dantas, D.; Esteves, G., Segmentation of microarray images by mathematical morphology, Real-Time Imaging, 8, 6, 491-505 (2002) · Zbl 1010.68958 · doi:10.1006/rtim.2002.0291 |
| [49] | Hirata, R., Jr., Brun, M., Barrera, J., Dougherty, E.R.: Multiresolution design of aperture operators. J. Math. Imaging Vis. (2002). doi:10.1023/A:1020377610141 · Zbl 1016.68151 |
| [50] | Julca-Aguilar, F., Hirata, N.: Image operator learning coupled with CNN classification and its application to staff line removal. In: 14th IAPR International Conference on Document Analysis and Recognition (2017). doi:10.1109/ICDAR.2017.18 |
| [51] | Karp, R.: Reducibility among combinatorial problems. In: R. Miller, J. Thatcher (eds.) Proceedings of a symposium on the Complexity of Computer Computations. Plenum Press, New York (1972). doi:10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [52] | Kleitman, D.; Markowsky, G., On Dedekind’s Problem: The Number of Isotone Boolean Functions, II. Trans. Amer. Math. Soc., 213, 373-390 (1975) · Zbl 0321.05010 · doi:10.1090/S0002-9947-1975-0382107-0 |
| [53] | Konstantinides, K., Rasure, J.R.: The Khoros software development environment for image and signal processing. IEEE Trans. Image Process. (1994). doi:10.1109/83.287018 |
| [54] | LeCun, Y.; Boser, B.; Denker, JS; Henderson, D.; Howard, RE; Hubbard, W.; Jackel, LD, Backpropagation applied to handwritten zip code recognition, Neural Comput., 1, 4, 541-551 (1989) · doi:10.1162/neco.1989.1.4.541 |
| [55] | Long, J., Shelhamer, E., Darrell, T.: Fully convolutional networks for semantic segmentation. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2015). doi:10.1109/CVPR.2015.7298965 |
| [56] | Maragos, P.A.: A unified theory of translation-invariant systems with applications to morphological analysis and coding of images. PhD thesis, School of Electrical and Computer Engineering (ECE), Georgia Institute of Technology (1985) |
| [57] | Marcondes, D., Simonis, A., Barrera, J.: Learning the hypotheses space from data: Learning space and u-curve property (2020). arxiv:2001.09532. ArXiv preprint |
| [58] | Marcondes, D., Simonis, A., Barrera, J.: Learning the hypotheses space from data, part II: convergence and feasibility. arXiv preprint (2020). arxiv:2001.11578 |
| [59] | Martins-Jr., D., Cesar-Jr., R., Barrera, J.: W-operator window design by minimization of mean conditional entropy. Pattern Anal. Appl. (2006). doi:10.1007/s10044-006-0031-0 |
| [60] | Matheron, G., Random Sets and Integral Geometry (1975), New York, NY, USA: John Wiley, New York, NY, USA · Zbl 0321.60009 |
| [61] | Matheron, G., Serra, J.: The birth of mathematical morphology. In: Talbot, H., Beare, R. (eds.) Proceedings of 6th International Symposium on Mathematical Morphology, pp. 1-16. CSIRO Publishing, Clayton (2002) |
| [62] | Mondal, R., Purkait, P., Santra, S., Chanda, B.: Morphological networks for image de-raining. In: Couprie, M., Cousty, J., Kenmochi, Y., Mustafa, N. (eds.) Discrete Geometry for Computer Imagery. Springer, Cham (2019). doi:10.1007/978-3-030-14085-4_21 · Zbl 1522.68700 |
| [63] | Montagner, I., Hirata Jr, R., Hirata, N., Canu, S.: Kernel approximations for w-operator learning. In: 29th SIBGRAPI Conference on Graphics, Patterns and Images, pp. 386-393 (2016) |
| [64] | Montagner, I., Hirata, N., Hirata, R., Jr.: Staff removal using image operator learning. Pattern Recognit. (2017). https://doi.org/10.1016/j.patcog.2016.10.002 |
| [65] | Park, H., Chin, R.: decomposition of arbitrarily shaped morphological structuring elements. IEEE Trans. Pattern Anal. Mach. Intell. (1995). doi:10.1109/34.368156 |
| [66] | Pavlidis, T., Algorithms for Graphics and Image Processing (1982), Rockville, MD, USA: Computer Science Press, Rockville, MD, USA · Zbl 0482.68086 · doi:10.1007/978-3-642-93208-3 |
| [67] | Reis, M.: Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets – algoritmos e aplicações. PhD thesis, Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil (2012). doi:10.11606/T.45.2012.tde-05022013-123757 |
| [68] | Reis, M., Barrera, J.: Solving problems in mathematical morphology through reductions to the u-curve problem. In: International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing. Springer (2013). doi:10.1007/978-3-642-38294-9_5 · Zbl 1382.68275 |
| [69] | Reis, M.; Estrela, G.; Ferreira, C.; Barrera, J., featsel: A framework for benchmarking of feature selection algorithms and cost functions, SoftwareX, 6, 193-197 (2017) · doi:10.1016/j.softx.2017.07.005 |
| [70] | Reis, M., Estrela, G., Ferreira, C., Barrera, J.: Optimal boolean lattice-based algorithms for the U-curve optimization problem. Inf. Sci. (2019). doi:10.1016/j.ins.2018.08.060 · Zbl 1441.68213 |
| [71] | Ris, M., Barrera, J., Martins-Jr, D.: U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem. Pattern Recognit. (2010). doi:10.1016/j.patcog.2009.08.018 · Zbl 1178.90296 |
| [72] | Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer (2015). doi:10.1007/978-3-319-24574-4_28 |
| [73] | Ronse, C., Why mathematical morphology needs complete lattices, Signal Process., 21, 2, 129-154 (1990) · Zbl 0734.94001 · doi:10.1016/0165-1684(90)90046-2 |
| [74] | Ronse, C.: A lattice-theoretical morphological view on template extraction in images. J. Vis. Commun. Image Represent. (1996). doi:10.1006/jvci.1996.0024 |
| [75] | Ruderman, D.: The statistics of natural images. Netw. Comput. Neural Syst. (1994). doi:10.1088/0954-898X_5_4_006 · Zbl 0824.92030 |
| [76] | Santos, C., Hirata, N., Hirata, R., Jr.: An information theory framework for two-stage binary image operator design. Pattern Recognit. Lett. (2010). doi:10.1016/j.patrec.2009.03.019 |
| [77] | Schmitt, M., Mathematical morphology and artificial intelligence: An automatic programming system, Signal Process., 16, 4, 389-401 (1989) · doi:10.1016/0165-1684(89)90032-7 |
| [78] | Serra, J., Image Analysis and Mathematical Morphology (1982), Cambridge, MA, USA: Academic Press, Cambridge, MA, USA · Zbl 0565.92001 |
| [79] | Serra, J.: Image Analysis and Mathematical Morphology. Vol. 2: Theoretical Advances. Academic Press, Cambridge (1988) |
| [80] | Serra, J.; Vincent, L., An overview of morphological filtering, Circuits Syst. Signal Process., 11, 1, 47-108 (1992) · Zbl 0787.93095 · doi:10.1007/BF01189221 |
| [81] | Soille, P., Morphological Image Analysis (2003), Berlin, Germany: Springer-Verlag, Berlin, Germany · Zbl 1012.68212 |
| [82] | Sternberg, S., Grayscale morphology, Comput. Vis. Graph. Image Process., 35, 3, 333-355 (1986) · doi:10.1016/0734-189X(86)90004-6 |
| [83] | Van Droogenbroeck, M.; Talbot, H., Fast computation of morphological operations with arbitrary structuring elements, Pattern Recognit. Lett., 17, 14, 1451-1460 (1996) · doi:10.1016/S0167-8655(96)00113-4 |
| [84] | Vincent, L.M.: Efficient computation of various types of skeletons. In: Loew, M.H. (ed.) Medical Imaging V: Image Processing, vol. 1445, pp. 297-311. International Society for Optics and Photonics, SPIE, Bellingham (1991). doi:10.1117/12.45227 |
| [85] | Wilson, S.S.: Training structuring elements in morphological networks. In: Dougherty, E.R. (ed.) Mathematical Morphology in Image Processing, Chap. 1, pp. 1-41. Marcel Dekker, New York (1993). doi:10.1201/9781482277234 |
| [86] | Zhang, A., Lipton, Z., Li, M., Smola, A.: Dive into Deep Learning. Self-published, Open Source Book (2020). https://d2l.ai |
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.
