Rozpoznawanie wzorców składniowych

Rozpoznawanie wzorców składniowych lub rozpoznawanie wzorców strukturalnych jest formą rozpoznawania wzorców , w której każdy obiekt może być reprezentowany przez zestaw symbolicznych, nominalnych cech o zmiennej liczności . Pozwala to na reprezentację struktur wzorcowych z uwzględnieniem bardziej złożonych wzajemnych relacji między atrybutami, niż jest to możliwe w przypadku płaskich, numerycznych wektorów cech o ustalonej wymiarowości, stosowanych w klasyfikacji statystycznej .

Rozpoznawanie wzorców składniowych może być stosowane zamiast statystycznego rozpoznawania wzorców, jeśli wzorce mają wyraźną strukturę. Jednym ze sposobów przedstawienia takiej struktury jest użycie ciągów symboli z języka formalnego . W tym przypadku różnice w strukturach klas są zakodowane jako różne gramatyki .

Przykładem tego może być diagnostyka serca za pomocą pomiarów EKG . Przebiegi EKG można aproksymować za pomocą ukośnych i pionowych odcinków linii. Jeśli normalne i niezdrowe przebiegi można opisać jako gramatyki formalne, zmierzony sygnał EKG można sklasyfikować jako zdrowy lub niezdrowy, najpierw opisując go w kategoriach podstawowych segmentów linii, a następnie próbując przeanalizować opisy zgodnie z gramatyką. Innym przykładem jest teselacja wzorów płytek.

Drugim sposobem reprezentacji relacji są grafy , w których węzły są połączone, jeśli powiązane są odpowiednie podwzorce. Element można oznaczyć jako należący do klasy, jeśli jego reprezentacja grafu jest izomorficzna z prototypowymi wykresami klasy.

Zazwyczaj wzorce są konstruowane z prostszych wzorców podrzędnych w sposób hierarchiczny. Pomaga to w podziale zadania rozpoznawania na łatwiejsze podzadania polegające na identyfikacji najpierw wzorców podrzędnych, a dopiero potem rzeczywistych wzorców.

Metody strukturalne dostarczają opisów elementów, które same w sobie mogą być przydatne. Na przykład rozpoznawanie wzorców składniowych można wykorzystać do ustalenia, jakie obiekty są obecne na obrazie. Ponadto metody strukturalne są skuteczne w znajdowaniu odwzorowania korespondencji między dwoma obrazami obiektu. W warunkach naturalnych odpowiadające sobie cechy będą znajdować się w różnych pozycjach i/lub mogą być przesłonięte na dwóch obrazach ze względu na położenie aparatu i perspektywę, jak w przypadku rozpoznawania twarzy . Algorytm dopasowywania wykresów zapewni optymalną zgodność.

Zobacz też

• Indukcja gramatyczna
• Dopasowywanie ciągów
• Algorytm Hopcrofta-Karpa
• Strukturalna teoria informacji

  Schalkoff, Robert (1992). Rozpoznawanie wzorców - podejście statystyczne, strukturalne i neuronowe . John Wiley i synowie. ISBN 0-471-55238-0 .

  Bunke, Horst (1993). Rozpoznawanie wzorców strukturalnych i składniowych , Chen, Pau & Wang (red.) Podręcznik rozpoznawania wzorców i wizji komputerowej . Świat naukowy. s. 163–209. ISBN 981-02-1136-8 .

  Flasiński, Mariusz (2019). Rozpoznawanie wzorców składniowych . Świat naukowy. ISBN 978-981-3278-46-2 .