GPS 정확도 개선을 위한 좌충우돌 얼레벌레 MapMatching 구현기

 

들어가며

정말 오랜만에 글을 쓰는 것 같다.

못해도 한달에 한개는 작성하자고 마음먹었었는데 시간이 어느새...

이번에 GPS 관련하여 검토한 것이 있어 기록해두기로 했다.

GPS는 그냥 WW(내 사이드 프로젝트) 하면서 날씨 정보를 받아오기 위한 하나의 단계에 지나지 않았는데...

GPS..너란 녀석...어려운 녀석이였군아

나는 어쩌다 Map Matching 을 알게 되었나

위에서 말한 것처럼 GPS 관련 프로젝트에 투입되었다.

사용자의 정확한 현재 위치를 가져올 수 있는 것이 중요했다.

그러나 GPS는 절대 정확한 녀석이 아니다. 수많은 오류와 그로 인한 오차가 발생한다.

우리가 사용하는 카카오맵, 네이버지도도 가끔씩 잘못된 위치를 가리킨다.

그래서 이를 보정하기 위한 방법을 찾아나서야 했고,

이 과정에서 알게 된 것이 Map Matching Algorithm 이다.

맵 매칭 알고리즘에 관한 것은 카카오에서 아주 자세하게 설명을 해두었다.

맵매칭 (부정확한 GPS포인트들로부터 경로 추정하기)

맵매칭은 도로 네트워크에 차량의 위치 측정치를 매핑하여 정확한 모빌리티 사용자의 위치와 이동경로를 추정하는 과정으로, 내비게이션 길안내, 택시/대리 등의 이동경로 기반한 요금 산정, 교통흐름 분석, 이동 방향 결정 등에 활용된다. GPS 위치가 정확하고 업데이트 주기가 빠른 경우 GPS를 가까운 도로 네트워크 상에 매핑만 하면 되지만, 실 서비스에서는 실내, 도심, 터널 등의 환경에서 GPS 위치가 부정확하고, 수 십 초 이상 수신기 되지 않는 상황이 빈번하게 발생되어 확률 모델 적용이 필요하다. 발표에서는 위 같은 상황에 대응 가능하도록 자체 개발된 Hidden Markov Model(HMM) 기반 맵매칭 알고리즘과 일평균 수백만 이동 경로에 적용된 서비스 시스템에 대해 설명하고, 실 데이터 처리 분석 결과를 공유한다.

 

그러나 처음에는 와닿지 않았다. '이렇게 까지 해야하나..?' 라는 생각이 들었기 때문이다.

설명해준 것이 현재 우리 프로젝트의 성격과 약간 다르다고 판단하기도 했고....

하지만 아무것도 하지 않을 순 없었다.

일단 우리 상황에 맞게끔 매칭을 시도해보자! 라는 마음으로 지도 데이터를 구하러 다녔다. 

백문이불여일코 : OSM 지도 데이터 가져오기

맵 매칭을 구현하기 위해서는 준비물이 필요하다.

1. GPS 데이터 (여기서는 좌표 뿐만아니라 Location 객체를 의미)

2. 지도 데이터

1번을 2번 상에 매칭시키는 것이라고 이해하면 된다.

쉽게 말해 2번은 매칭 대상을 의미한다.

 

OSM이 모죠🤔

지도 데이터를 어디서 구해올까 하다가 OSM (Open Street Map) 을 알게 되었다.

오픈스트리트맵

오픈스트리트맵은 누구나 참여할 수 있는 오픈 소스 방식의 무료 지도 서비스이다. 비영리 단체인 오픈스트리트맵 재단이 운영하고 2005년 설립되었다. 비영리 재단인 위키백과를 모델로 하고 있어 누구나 편집하고 활용할 수 있다. 위키백과

OSM에서 지도 데이터를 얻는 법

1. 해당 링크로 들어가서 '내보내기' 탭을 클릭한다.

(지도 데이터를 얻고 싶은 지역으로 이동한 후 내보내기 하는 것을 추천한다.)

 

2. 수동으로 다른 지역 선택 클릭

3. 내보내기 클릭

그러면 바로 .osm 형식으로 지도 데이터가 다운로드 된다.

(optional) 4. 원하는 형식으로 변환하기

나는 .geojson 형식이 좀 더 다루기 쉬울 것 같아 해당 확장자로 변환하기로 했다.

OSM to GeoJSON Converter Online - MyGeodata Cloud

난 여기서 변환해주었다.

그러면 이제 내가 원하는 구역의 지도 데이터를 얻을 수 있다.

 

변환된 파일을 열어보면 이런식으로 생겼다.

나는 이중에 roads.geojson을 사용했다.

안에는 각 도로에 대한 정보와 링크의 좌표 (선분의 형태) 로 존재한다.

나는 도보 데이터가 필요했기 때문에 이중에 'footway'로 분류된 것만을 뽑아서 사용했다.

지도 데이터를 표시한 결과

알고리즘 구현하기

지도 데이터를 구해왔으니 매칭을 시켜볼 차례다.

가장 직관적으로 떠오른 생각은 '실제 위치가 보정되어야 할 경로 근처에 찍힌다'는 것이었다.

그러니까 가장 현재 위치라고 찍힌 GPS를 가장 가까운 선분에 매칭시키기로 했다는 것이다.

이 결과 내가 구현한 매칭 알고리즘은 다음과 같은 순서를 가진다.

1. 현재 위치를 수집한다.
2. 현재 위치와 가장 가까운 선분(링크)을 구한다.
3. 현재 위치를 해당 선분에 매칭시킨다.

매칭 시키는 방법은 선분 AB와 현재 위치 P에 수선의 발을 내려 수행했다.

결과

선분 AB (분홍색 마커)와 현재 위치 P (초록색 마커)의 수선의 발을 내린 결과 (빨간색 마커) 이다.

문제점 및 개선

그러나 이 알고리즘에는 문제가 있었다.

단순히 거리만을 가지고 위치 보정을 수행하고 있었기 때문에

사용자의 진행 방향과는 상관없는 곳에 매칭이 되는 경우가 종종 있었다.

그 외에도 여러가지 개선해야할 점들이 존재했다.

또한, OSM 지도 데이터를 바탕으로 알고리즘이 구현되어서, 프로젝트 적용에도 완벽하게 들어맞지 않았다.

그래서 프로젝트 특성에 맞게 또 여러 요소를 고려하여 최적의 보정값을 찾을 수 있도록

알고리즘을 수정했고, 수정된 알고리즘은 다음과 같다.

1. 현재 위치를 수집한다.
2. 일정 반경 안에 들어오는 선분들을 수집한다.
3. 각 선분에 해당하는 보정 값 후보들을 선정한다.
4. 각 후보값들의 거리, 시간, 각도를 고려해 최적의 보정값을 선택한다.

완벽한 알고리즘은 아니지만 기존의 알고리즘 보다는 개선된 것을 확인할 수 있었다.

마치며

글은 굉장히 짧게 쓰여졌지만 정말 고생했다....

틈틈히 개선해 나가야할 것들이 한두개가 아니겠지만....

(내 기준) 불가능 해보이던 걸 해내고 나니 뿌듯하다.

차근차근 해나가면 되는건데...난 뭐가 매사에 그렇게 불안할까 ㅋㅋ

GPS..역시나 하면 할수록 어려운 녀석임에 틀림없다.

그러나 난 네가...좀 좋아지려고 한다 ㅋ 쿸....

---

공부하며 작성된 글이라 잘못된 정보가 있을 수 있습니다.

말씀해주시면 수정하겠습니다. 감사합니다.

References

아래 글을 참고하여 작성 되었습니다.

맵 매칭(Map Matching)