Digitale beeldverwerking met behulp van partiële differentiaalvergelijkingen

Arnaud Devos
In vele computertoepassingen worden beelden geanalyseerd die ruis bevatten. Denk bijvoorbeeld aan medische beeldvorming. Deze scriptie bestudeert hoe met niet-lineaire diffusiemodellen automatisch afbeeldingen van een hogere kwaliteit kunnen bekomen worden.

Een beeld zegt meer dan duizend woorden

In beeldverwerking is een digitale afbeelding niets anders dan een rooster van pixels (lees: matrix). Met behulp van wiskundige methodes kunnen deze getallen aangepast worden zodat een nieuwe afbeelding verkregen wordt van hogere kwaliteit. Een mogelijke manier om dit te doen, is met behulp van partiële differentiaalvergelijkingen. Hierdoor kan een afbeelding die ruis bevat, gerestaureerd en zelfs verscherpt worden. Relevante toepassingen zijn te vinden in de medische beeldvorming. Voor bijvoorbeeld MRI, Echografie en CT scan afbeeldingen, kan aanwezige ruis het verschil maken tussen een vroege vaststelling van een medisch probleem of een verkeerde diagnose. Het correct wegfilteren van ruis op dergelijke beelden is dan ook ontzettend belangrijk.

Partiële differentiaalvergelijkingen

De wiskunde die gebruikt wordt, zijn dus partiële differentiaalvergelijkingen. Een (partiële) differentiaalvergelijking is een wiskundige relatie die een onbekende functie en zijn (partiële) afgeleiden bevat. Dergelijke vergelijkingen worden vaak gebruikt om fysische processen te modelleren. Een elementaire partiële differentiaalvergelijking is de warmtevergelijking. Deze vergelijking beschrijft de verandering van de warmte in een gebied, in functie van de tijd. De vergelijking moet gekoppeld worden aan een begintemperatuur en omgevingscondities. De temperatuur wijzigt vervolgens continu in de tijd, beschreven volgens de warmtevergelijking.

Wat gebeurt er nu als deze warmtevergelijking wordt toegepast op een afbeelding met ruis? Het resultaat is dat de afbeelding waziger wordt en de ruis bijgevolg vervaagt. Deze methode heeft als nadeel dat de randen/contouren van een afbeelding ook vervagen. Dit komt omdat de warmtevergelijking de afbeelding overal even sterk vervaagt. Ze houdt geen rekening met de structuur van de afbeelding. In de wiskunde noemen we de warmtevergelijking een lineaire diffusievergelijking. Om dit probleem op te lossen, moet overgestapt worden naar een zogenaamde niet-lineaire diffusievergelijking. Op deze manier kan er meer rekening gehouden met de structuur van de afbeelding. Hoe sterk de afbeelding vervaagd wordt, zal verschillend zijn voor elke positie op de afbeelding.

Wiskundige aanpak

De meest bekende niet-lineaire partiële differentiaalvergelijking in deze context, is ontworpen in de jaren negentig van de vorige eeuw. Ze kreeg de naam van haar uitvinders: de Perona-Malik (P-M) vergelijking. In deze scriptie werd de P-M vergelijking uitvoerig bestudeerd. Ten eerste werd een bestaande numerieke methode onderzocht om de vergelijking op te lossen. Om dit op een correcte en efficiënte wijze te doen, komt er al heel wat mooie wiskunde bij kijken (analyse en lineaire algebra). Vervolgens wordt er met een kritische blik naar de vergelijking gekeken. Een cruciale vraag is of er een unieke oplossing bestaat. Er kan echter niet bewezen worden dat de P-M vergelijking een unieke oplossing bezit. Hierdoor moet de vergelijking worden aangepast. Dit is niet vanzelfsprekend. We willen immers de eigenschappen van de originele vergelijking behouden! Ook hier is reeds een voorstel gedaan, ongeveer twee jaar na het beroemde artikel van Perona & Malik. Er werd een kleine regularisatie doorgevoerd in de originele P-M vergelijking. Van deze geregulariseerde vergelijking kan er bewezen worden dat ze een unieke oplossing heeft. De wiskunde hiervoor is zeker niet triviaal. Zo neemt het bewijzen van het bestaan en uniek zijn van een oplossing toch zo'n tiental bladzijden in beslag. Zelf heb ik dit (opnieuw) bewezen op basis van twee artikels. In wetenschappelijke artikels zijn tussenstappen zelden uitgewerkt. Ik heb in mijn scriptie het bewijs zo zorgvuldig mogelijk geleverd. Tevens heb ik ervoor gekozen om enkel lemma's en stellingen te gebruiken die ik reeds gezien had in mijn opleiding Wiskunde. Hierdoor was ik soms genoodzaakt om enkele lemma's/stellingen uit de artikels te vervangen. Het heeft dan ook een zekere voldoening als je uiteindelijk tot hetzelfde resultaat komt.

Praktisch

Leuk aan deze scriptie is dat je ziet wat er gebeurt. Het oplossen van de vergelijking werd door mezelf geschreven in een wiskundige programmeertaal. Belangrijk is dat dit op zo'n efficiënt mogelijke wijze gebeurt. Dit zorgt er voor dat de oplossing in een korte tijd kan berekend worden door het computerprogramma. Er is een levenswijsheid die zegt dat je partiële differentiaalvergelijking pas volledig kan doorgronden als je ze zelf eens met de computer hebt opgelost. Door de parameters van het model aan te passen zie je wat hun invloed is. Zo krijg je steeds een beter inzicht. Het toepassen op digitale afbeeldingen maakt het nog mooier. Je selecteert een afbeelding die van slechte kwaliteit is. Vervolgens laat je het programma erop los. Dit resulteert meestal in een betere afbeelding als output.

Het resultaat (rechts) van de P-M vergelijking op een afbeelding met ruis (links).

Toekomst

De resultaten van de P-M vergelijking zijn visueel indrukwekkend. Toch moet men steeds opzoek zijn naar betere, nog straffere resultaten. Stel je bijvoorbeeld afbeeldingen voor waarbij de ruis zodanig sterk is dat de originele afbeelding nog nauwelijks herkenbaar is. Het wordt dan een lastige taak om de afbeelding te correct te herstellen. Een relatief nieuw onderzoeksgebied zou zijn om fractionele afgeleiden te gebruiken. In het middelbaar zijn we gewoon om een functie een geheel aantal keer af te leiden. Fractionele afgeleiden laten toe om bijvoorbeeld een functie een halve keer af te leiden. Recente studies hebben al het succes aangetoond van fractionele afgeleiden in de beeldverwerking.

Deze nieuwe modellen kunnen wiskundig bestudeerd worden. Opnieuw kan worden nagedacht over een efficiënte implementatie. Tenslotte kunnen ze vergeleken worden met de klassieke modellen.
Deze scriptie is een uitstekende voorbereiding voor wie zich hierin verder wil verdiepen. Misschien red je er wel levens mee.

Bibliografie

[1] E. Acerbi, V. Chiad`o Piat, G. Dal Maso, en D. Percivale. An extension theorem from con- nected sets, and homogenization in general periodic domains. Nonlinear Analysis: Theory, Methods & Applications, 18(5):481–496, 1992.
[2] E. Ba ̈nsch en K. Mikula. Adaptivity in 3d image processing. Computing and Visualization in Science, 4(1):21–30, 2001.
[3] M. Black, G. Sapiro, D. Marimont, en D. Heeger. Robust anisotropic diffusion. IEEE Transactions on image processing, pages 421–432, 1998.
[4] T. Brox. From Pixels to Regions: Partial Differential Equations in Image Analysis. PhD thesis, Saarland University, Saarbru ̈cken, Germany, 2005.
[5] W. Burger en M. J. Burge. Digital image processing: an algorithmic introduction using Java. Springer, 2016.
[6] F. Cagnetti en L. Scardia. An extension theorem for sbv functions and an application to homogenization of mumford-shah type energies. Preprint, 2008.
[7] J. Canny. A computational approach to edge detection. IEEE Transactions on pattern analysis and machine intelligence, (6):679–698, 1986.
[8] F. Catt ́e, P. Lions, J. Morel, en T. Coll. Image selective smoothing and edge detection by nonlinear diffusion. SIAM Journal on Numerical analysis, 29(1):182–193, 1992.
[9] L. Dascal. Well-posedness and maximum principle for PDE based models in image proces- sing. PhD thesis, Tel-Aviv University, 2006.
[10] H. De Bie. Function Spaces. Course notes Ghent University, 2014-2015.
[11] H. De Meyer en V. Fack. Optimisation. Course notes Ghent University, 2014-2015.
[12] R. Eymard, T. Gallou ̈et, en R. Herbin. Finite volume methods. Handbook of numerical analysis, 7:713–1018, 2000.
[13] G. H. Golub en C. F. Van Loan. Matrix computations, volume 3. JHU Press, 2012.
[14] R. C. Gonzalez en R. E. Woods. Digital Image Processing. Pearson, 2007.
[15] R. C. Gonzalez, R. E. Woods, en S. L. Eddins. Digital Image Processing Using MATLAB. Prentice-Hall, Inc., 2003.
[16] K. Ho ̈llig en J. Nohel. A diffusion equation with a nonmonotone constitutive function. In Systems of Nonlinear Partial Differential Equations, pages 409–422. Springer, 1983.
[17] J. Kaˇcur. Method of Rothe in evolution equations. Springer, 1986.
[18] J. Kaˇcur en K. Mikula. Solution of nonlinear diffusion appearing in image smoothing and
edge detection. Applied Numerical Mathematics, 17(1):47–59, 1995.
[19] B. Kawohl. Variational versus pde-based approaches in mathematical image processing. In
CRM Proceedings and Lecture Notes, volume 44, pages 113–126, 2008.
[20] S. Kichenassamy. The perona–malik paradox. SIAM Journal on Applied Mathematics, 57
(5):1328–1342, 1997.
[21] J. Koenderink. The structure of images. Biological cybernetics, 1984.
[22] P. D. Kovesi. Matlab and octave functions for computer vision and image processing. Online: http://www. csse. uwa. edu. au/ ̃ pk/Research/MatlabFns/# match, 2000.
[23] Z. Kriv ̆a. Explicit FV scheme for the Perona-Malik equation. Computational Methods in Applied Mathematics Comput. Methods Appl. Math., 5(2):170–200, 2005.
[24] Z. Kriv ́a en K. Mikula. An adaptive finite volume scheme for solving nonlinear diffusion equations in image processing. Journal of Visual Communication and Image Representa- tion, 13(1-2):22–35, 2002.
[25] C. Ley. Statistical Inference. Course notes Ghent University, 2015-2016.
[26] Mathworks. Makers of Matlab and Simulink. https://nl.mathworks.com.
[27] K. Mikula. Image processing with partial differential equations. In Modern methods in scientific computing and Applications, pages 283–321. Springer, 2002.
[28] K. Mikula en N. Ramarosy. Semi-implicit finite volume scheme for solving nonlinear diffu- sion equations in image processing. Numerische Mathematik, 89(3):561–590, 2001.
[29] K. W. Morton en D. F. Mayers. Numerical Solution of Partial Differential Equations: An Introduction. Cambridge University Press, New York, NY, USA, 2005. ISBN 0521607930.
[30] J. Neˇcas. Introduction to the theory of nonlinear elliptic equations. Chichester: John Wiley & Sons Ltd, 1986.
[31] P. Perona en J. Malik. Scale-space and edge detection using anisotropic diffusion. IEEE Transactions on pattern analysis and machine intelligence, 1990.
[32] J. Phillpot. Noise Reduction with the heat equation and the perona-malik equation. 2014.
[33] J. Ralli. PDE Based Image Diffusion and AOS. 2014.
[34] T. Roub ́ıˇcek. Nonlinear partial differential equations with applications, volume 153 of ISNM. Birkha ̈user Verlag, Basel, 2005.
[35] J. W. Schlasche. Mathematical Methods of Image Processing to Characterize Micro Cups. Master’s thesis, Universita ̈t Bremen, 2011.
[36] M. Slodiˇcka. Apprroximation Methods For Boundary Value Problems. Course notes Ghent University, 2015-2016.
[37] M. Slodiˇcka. Partial Differential Equations. Course notes Ghent University, 2015-2016.
[38] M. Slodiˇcka. Applied Functional Analysis. Course notes Ghent University, 2015-2016.
[39] A. Sparavigna. Fractional differentiation based image processing. arXiv preprint ar- Xiv:0910.2381, 2009.
[40] H. J. Trussell en M. J. Vrhel. Fundamentals of digital imaging. Cambridge University Press, 2008.
[41] C. Tsiotsios en M. Petrou. On the choice of the parameters for anisotropic diffusion in image processing. Pattern recognition, pages 1369–1381, 2013.
[42] G. University. Google Books Project. http://www.ugent.be/nl/univgent/bibliotheek/ ugent-google.htm.
[43] M. Vajnberg. Variational method and method of monotone operators in the theory of non- linear equations. John Wiley & Sons, 1973.
[44] K. Van Bockstal. Numerical techniques for partial differential equations in superconductivity and thermoelasticity. PhD thesis, Ghent University, 2015.
[45] M. Van Daele. Numerical Methods for Differential Equations. Course notes Ghent Univer- sity, 2015-2016.
[46] J. Van der Jeugt. Numerical Analysis. Course notes Ghent University, 2013-2014.
[47] D. Ventzas. Advanced image Acquisition, Processing Techniques and Applications i. InTech, 2012.
[48] J. Weickert. A review of nonlinear diffusion filtering. In International Conference on Scale- Space Theories in Computer Vision, pages 1–28. Springer, 1997.
[49] J. Weickert. Anisotropic diffusion in image processing, volume 1. Teubner Stuttgart, 1998.
[50] M. Wielgus. Perona-malik equation and its numerical properties. arXiv preprint ar- Xiv:1412.6291, 2014.
[51] Wikipedia. The Free Encyclopedia. http://en.wikipedia.org/.
[52] A. Witkin. Scale-space filtering: A new approach to multi-scale description. In Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP’84., volume 9, pages 150–153. IEEE, 1984.
[53] Q. Yang, D. Chen, T. Zhao, en Y. Chen. Fractional calculus in image processing: a review. Fractional Calculus and Applied Analysis, 19(5):1222–1249, 2016.
[54] E. Zeidler. Nonlinear Functional Analysis and its Applications II/B: Nonlinear Monotone operators. Springer-Verlag, 1990.

Universiteit of Hogeschool
Master of Science in de wiskunde
Publicatiejaar
2017
Promotor(en)
Marian Slodicka & Karel Van Bockstal
Kernwoorden