그래프 일치
Graph matching그래프 매칭은 그래프 사이의 유사성을 찾는 문제다.[1]
그래프는 컴퓨터 비전, 패턴 인식 등 여러 분야의 구조 정보를 인코딩하는 데 흔히 사용되며, 그래프 매칭은 이들 분야에서 중요한 도구다.[2] 이러한 영역에서는 일반적으로 데이터 그래프와 모델 그래프 간의 비교를 가정한다.
정확한 그래프 매칭의 경우는 그래프 이형성 문제로 알려져 있다.[1]그래프를 다른 그래프의 일부와 정확히 일치시키는 문제를 서브그래프 이형성 문제라고 한다.
부정확한 그래프 일치는 정확한 일치가 불가능할 때, 예를 들어 두 그래프에서 정점 수가 다를 때 일치하는 문제를 가리킨다.이 경우 가능한 최선의 일치점을 찾아야 한다.예를 들어 영상 인식 애플리케이션에서 영상 처리의 영상 분할 결과는 일반적으로 모델 그래프 데이터보다 정점 수가 훨씬 큰 데이터 그래프를 생성한다.귀속 그래프의 경우 정점과 가장자리 수가 같더라도 일치가 부정확할 수 있다.[1]
두 가지 범주의 검색 방법은 두 그래프 사이의 정점 쌍과 그래프 일치를 최적화 문제로 공식화하는 방법의 식별에 기초한 것이다.[3]그래프 편집 거리는 그래프 일치를 위해 제안된 유사성 측도 중 하나이다.[4][5]알고리즘의 클래스를 오류 내성 그래프 매칭이라고 한다.[5]
참고 항목
참조
- ^ a b c Endika Bengoetxea, "분포 알고리즘의 추정을 이용한 비작위 그래프 일치", 박사 D, 2002, 2장:그래프 일치 문제(2017년 6월 28일 회수)
- ^ Endika Bengoetxea, 박사학위, 추상적
- ^ 컴퓨터 비전의 그래프 기반 방법: 개발 및 적용, 페이지 58
- ^ 그래프 편집 거리와 커널 시스템 사이의 간격 연결, 페이지 16
- ^ a b Horst Bunke, Xiaoyi Jang, "그래프 매칭 및 유사성" in: Intelligent Systems and Interface, 페이지 281-304 (2000) doi:10.1007/978-1-4615-4401-2_10
