Two-dimensional pattern matching
WORLD SCIENTIFIC eBooks · 2002
This thesis contains formal derivations of several two-dimensional pattern matching algorithms.The two-dimensional pattern matching problem is to find all exact occurrences of a given twodimensional pattern matrix within a larger matrix.Two-dimensional pattern matching is mostly applied in image processing (and image recognition in particular), although there are other applications as well.We give a formal derivation (and correctness proof) for several known algorithms in this field, as well as a few improvements to some of these algorithms. SamenvattingDit afstudeerverslag bevat formele afleidingen voor enige algoritmen voor twee-dimensionale patroonherkenning.Het probleem van twee-dimensionale patroonherkenning bestaat uit het vinden van de voorkomens van een gegeven twee-dimensionale patroonmatrix binnen een grotere matrix.Twee-dimensionale patroonherkenning wordt vooral toegepast binnen de beeldverwerking (en in het bijzonder beeldherkenning), maar er zijn ook andere toepassingen.We geven een formele afleiding (tevens correctheidsbewijs) van verschillende bekende algoritmen die dit probleem oplossen.Daarnaast introduceren we enige verbeteringen op sommige van deze algoritmen.