[Graph similarity] 그래프 유사도 측정1

하고 있는 프로젝트에서 그래프 자료구조를 사용해보기로 해서 정리하는 글이다.

어디에 사용할건지

서로 다른 프레임에서 추출된 _feature points_를 _graph_로 만들면 프레임간 매칭단계 구현이 좀 더 단순해 지지않을까? 좀 더 세련되지지 않을까? 하는 생각으로 시작한다.

Graph similarity? Graph isomorphism? Graph matching?

graph matching 이라는 키워드로 처음 검색을 했다. 나는 template matching 처럼 두 객체 사이의 유사 정도를 판단하는 의미로 graph matching 이라는 단어를 쓴건데 graph matching 이라는 키워드는 내 생각과 다른 개념이었다.

graph에서 matching 이라는 단어는 _subgraph_를 의미한다(내가 생각한건 matching 알고리즘의 개념). graph matching도 따지고 보면 두 graph의 node를 각각 매칭해서 유사도를 판단하는 것이니까 아예 다른 개념은 아닌 듯 하다.

뭐부터 해야하나?

먼저 point들로부터 그래프를 구성하고(graph representation), 그래프를 사용하기 편한 행렬로 변환하고(adjacency matrix), 변환된 행렬끼리 유사도를 측정(similarity measurement)하려고 한다.

Representation

그래프에도 여러 타입이 있는데 나는 undirected complete graph를 구현해서 사용할 예정.
그래프의 node는 point의 feature가 저장되고 edge에는 두 노드가 이루는 벡터의 length, orientation을 가중치로 저장된다.

Adjacency matrix

그래프를 표현하는 방법에는 인접행렬(adjacency matrix)과 인접리스트(adjacency list)가 있는데 인접행렬이 좀더 구현이 간단하여 인접행렬을 사용한다.

위와 같은 complete graph가 있으면 다음과 같이 인접행렬을 만든다.