Co-visibility graph(공가시성 그래프)

 로보틱스에서 motion planning을 하게 될 때 visibility graph(가시성 그래프)를 사용하는 경우가 있습니다. visibility graph란 로봇이 이동을 할 때 자신의 앞에 보이는 장애물을 어떻게 하면 회피해서 갈 수 있는지에 대해 알 수 있는 방법을 고안하는 단계에서부터 시작하게 됩니다. 설명하기에 앞서 간단한 그림을 사용하여 설명해드리겠습니다.

 위 그림은 두 개의 직사각형 모양의 장애물이 있고, 로봇은 검은 점과 붉은 점을 이동해야 하는 상황을 나타낸 것입니다. 먼저 로봇이 지나갈 수 있는지를 visibility graph를 그려 확인하는 과정으로 시작점과 도착점에서 장애물까지 직선으로 선을 긋습니다. 위 그림에서 파란색으로 그려진 부분에서 시작점과 도착점의 visibility graph가 만나고 있음을 알고 있습니다. visibility graph를 그릴 때 주의할 점은 점에서부터 시작되는 visibility graph는 곡선이 될 수 없으며 도달하는 부분까지 직선으로 이어져 있어야 한다는 점입니다.

 이번 포스팅에서 설명하게 될 co-visibility graph(공가시성 그래프)를 이해하기 위해 사전지식으로 visibility graph에 대해 간단히 설명드렸습니다. 이름에서 알 수 있듯이 co-visibility graph는 두 개 이상의 점에서 나오는 직선이 특정 점에 도달하게 되었을 때 visibility graph의 갯수를 나타냅니다.

 Vision 분야에서의 visibility graph를 먼저 설명드리도록 하겠습니다.

 이 그림에서 파란 삼각형은 카메라를 나타낸 것이며 초록색 도형은 카메라에 비치는 물체를 나타낸 것이며 노란 점은 카메라에서 해당 도형에 도달하는 visibility graph를 나타낸 것입니다. 실제 점은 훨신 더 촘촘하게 나타낼 수 있으나 보기 쉽게 설명드리기 위해 일부 점만을 나타낸 것입니다.

 다음 그림은 두 개의 카메라로 도형을 바라보게 된 경우입니다.

 두 대의 카메라를 사용하여 특정 물체를 바라보게 되었을 때 보시는 바와 같이 붉은 점으로 표현된 부분은 두 대의 카메라의 시야에 모두 들어오는 부분입니다. 이렇게 두 대 이상의 카메라에서 영사되어 겹치게 되는 부분의 갯수를 표현하는 것을 co-visibility graph라 합니다.

 위의 그림을 보았을 때 노란점의 경우 한 대의 카메라에서만 해당 부분이 보이며 붉은점의 경우 두 대의 카메라에서 해당 부분을 볼 수 있음을 알 수 있습니다.

 이러한 co-visibility graph의 특성은 Visual-SLAM에서 시각정보로 지도를 그리게 되었을 때 주로 사용됩니다. 각 카메라의 영사 정보를 사용하여 상관관계를 판단하여 실제와 최대한 비슷한 지도를 만들 수 있는 것이지요.