Dopasowanie wykresu - Graph matching

Dopasowywanie grafów to problem znajdowania podobieństwa między grafami .

Wykresy są powszechnie używane do kodowania informacji strukturalnych w wielu dziedzinach, w tym w zakresie widzenia komputerowego i rozpoznawania wzorców , a dopasowywanie wykresów jest ważnym narzędziem w tych obszarach. W tych obszarach powszechnie przyjmuje się, że porównanie odbywa się między wykresem danych a wykresem modelu .

Przypadek dokładnego dopasowania grafów jest znany jako problem izomorfizmu grafów . Problem dokładnego dopasowania grafu do części innego grafu nazywamy problemem izomorfizmu podgrafów .

Niedokładne dopasowanie wykres odnosi się do problemów, gdy dokładnie pasujące dopasowanie jest możliwe, na przykład, gdy liczba wierzchołków dwóch wykresach są różne. W takim przypadku wymagane jest znalezienie najlepszego możliwego dopasowania. Na przykład, w uznawaniu obraz zastosowań, wyniki segmentacji obrazu w przetwarzaniu obrazu zazwyczaj produkuje wykresy danych z numerami wierzchołków znacznie większych niż w modelu wykresach dane oczekiwanych dopasować przeciw. W przypadku grafów przypisywanych , nawet jeśli liczby wierzchołków i krawędzi są takie same, dopasowanie nadal może być tylko niedokładne.

Dwie kategorie metod przeszukiwania to te, które opierają się na identyfikacji możliwych i niemożliwych parowania wierzchołków między dwoma grafami oraz metody, które formułują dopasowanie grafów jako problem optymalizacyjny . Odległość edycji wykresu jest jedną z miar podobieństwa sugerowanych przy dopasowywaniu wykresów. Klasa algorytmów nazywana jest odpornym na błędy dopasowywaniem grafów.

Zobacz też

Bibliografia