셀프 업데이팅 맵 - 딥러닝을 활용한 실내 매장 변화 검출 알고리즘 개발기

이전 아티클을 통해 우리는 실내 지도 자동 업데이트(Self-Updating Map) 기술을 소개한 바 있다. 본 아티클은 해당 기술을 연구하는 과정에서 겪었던 시도들에 대한 기록이다. 비슷한 문제를 풀고 있는 연구원들에게 작은 도움이 되길 바란다.

Problem?

우리의 미션은 실내 지도 자동 업데이트를 위하여 시간 간격을 두고 촬영한 이미지들로부터 관심 지점(Point of Interest, POI)의 변화를 검출하는 일이었다. 여기서 POI란 유용하거나 흥미를 끌 수 있으며 위치가 잘 알려진 랜드마크를 의미하는데, 우리는 대상 공간을 대형 쇼핑몰로 지정하고 POI를 쇼핑몰 내 개별 매장으로 정의하였다. 이때, 검출하고자 하는 POI 변화는 기존 매장이 새로운 곳으로 바뀌거나 없어진 경우, 그리고 매장이 없던 자리에 새로 생긴 경우가 된다. 

대형 쇼핑몰은 여러가지 변화가 많이 일어나는 공간이다. 많은 매장들이 생겼다가 없어지고, 같은 자리에 다른 매장이 들어서기도 한다. 또한, 계절이나 시간에 따라 내부 인테리어와 진열대의 모습, 할인 정보 등이 달라진다. 나아가, 쇼핑몰을 스캔하여 촬영한 이미지에는 시시각각 변하는 보행자의 모습도 담겨 있다. 여러분이 만약 지도 제작자라면 지도에 어떤 변화를 업데이트하게 될까? 매장의 변화는 업데이트하고 그 외의 것은 업데이트하지 않을 것이다. 우리는 이러한 업데이트를 자동으로 수행하고자 한다. 그렇다면 업데이트할 변화와 업데이트하지 않을 변화, 즉 단순한 시각적 변화가 발생한 경우와 실제로 POI 변화가 발생한 경우를 어떻게 자동으로 구별할 수 있을까?

우리는 (지금 글을 읽는 여러분처럼) “그렇게 어렵진 않을 것 같은데?”라는 생각으로 직관적인 방법들을 먼저 시도해보았다.

Naive trial 1. Keypoint matching based

처음 시도한 방법은 각 이미지에서 keypoint를 검출하고 local descriptor를 이용하여 두 이미지의 유사성을 비교하는 것이었다. 이 방법은 기존 image matching, image retrieval 문제에서 많이 사용되어 왔지만, 대형 쇼핑몰과 같은 실내 공간에서는 정확도를 보장하기가 어렵다. 실내에서 촬영된 이미지들은 중요하지 않으면서 keypoint가 쉽게 검출될 수 있는 부분들을 많이 포함하고 있기 때문에, 매칭 시에 (우리가 원하는 대로) 매장 내부에 집중하기 보다는 두 이미지에서 공통으로 등장하는 매장 외관의 천장과 바닥의 모서리, 천장에 달린 조명에 집중할 위험성이 있다.

이는 실제 POI 변화가 발생하더라도 두 이미지에 등장하는 공통된 부분들 때문에 POI 변화 검출에 실패할 수 있음을 의미한다. 그림 1은 실제 POI 변화가 발생한 두 이미지에 SIFT feature[3]를 계산하여 매칭한 결과이다. 각 이미지에서 검출된 keypoint 위치들을 노란색 동그라미로 나타내고 두 이미지에서 높은 유사도를 갖는 상위 30 개의 keypoint들을 파란색 실선으로 연결하였다. 유사도가 높은 keypoint들이 주로 두 이미지의 동일한 인테리어에 집중하는 것으로 보아 POI 변화는 발생하지 않았다고 판단할 것임을 짐작할 수 있다.

그림 1. Keypoint 기반의 POI 변화 탐색 방법의 실패 예시.

Naive trial 2. Object detection based

다음으로, 물체 검출(object detection) 알고리즘을 이용하여 간판을 검출하고 두 이미지에 등장하는 각 간판들을 비교하는 방법을 시도해보았다. POI를 대표할 수 있는 특징이 간판이며, 간판이 변화했으면 POI 변화도 발생했을 것이라는 직관적인 아이디어로부터 착안했다. 간판만을 잘 검출해낸다면 중요하지 않은 변화들은 자연스럽게 신경쓰지 않을 수 있고, 두 이미지에서 비교해야 할 영역도 크게 줄일 수 있다. 그림 2는 POI의 겉모습은 변하였지만 간판은 변하지 않은 예시이다. 간판 영역만을 검출하여 비교할 경우 POI 변화는 발생하지 않았다는 결과를 얻을 수 있을 것이다.

그림 2. 간판 검출이 유용하게 쓰일 수 있는 예시.

그러나 이 방법은 (당연히도) 간판 검출의 성능에 크게 의존하는 방법이기 때문에 검출기(detector)가 간판을 잘못 검출할 경우 치명적일 수 있다. 간판은 주로 텍스트와 이미지 등으로 구성되어 있어서 POI 변화 관련이 없는 세일 정보나 픽토그램 등이 간판으로 오분류되는 경우가 잦고, 간판의 위치도 매장별로 다양해서 위치를 기반으로 한 간판 검출도 적용하기 어렵다. 

간판 검출이 잘 동작하더라도 POI 변화를 검출하기 어려운 경우도 있다. 간판은 변했지만 매장은 변하지 않은 경우(그림 3)에는 비교 알고리즘이 잘 동작하지 않을 것이다. 간판을 캘리그래피로 제작하거나 로고만 이용하는 경우도 적지 않기에 OCR을 이용하여 간판의 문자를 비교하는 방법도 적용하기가 쉽지 않다. 공사 중이던 매장이 오픈한 경우(그림 4)는 어떨까. 없던 POI가 생긴 경우이므로 변화가 발생한 것이지만 간판으로 검출된 부분이 비슷하다면 간판 비교 방법은 POI 변화가 일어나지 않았다고 판단할 것이다.

그림 3. 간판이 변하였지만 POI는 변하지 않은 예시. 

그림 4. 간판은 변하지 않았지만 POI는 변한 예시.

실제 POI 변화 예시들을 보니 어떠한가? 직관적이고 단순한 접근으로는 풀기 어려운 문제임은 분명해 보인다. 흥미로운 점은, 인간은 복잡한 생각 없이도 POI 변화가 존재하는 예시를 굉장히 쉽게 구분해낼 수 있다는 점이다. 인간은 어떻게 이미지로부터 같은 POI 쌍과 다른 POI 쌍을 구분하는 것일까?

인간은 이미지를 접하는 순간 중요한(의미론적인) 특징부터 찾아 비교하고 구분할 것이다. 우리도 이와 비슷한 동작을 하는 모델을 설계하고자 하였고 Convolutional network(ConvNet)이 인간과 유사한 수준의 객체 인식 성능을 보이는 것으로 최근 논문들을 통해 보고되어 온 바 있다.  우리는 ConvNet이 인간처럼 의미론적 특징을 찾고 비교하여 POI 변화를 잘 판단해주길 기대하며 ConvNet을 기반으로 한 접근을 시도하였다.

How can we measure the “POI change”?

두 이미지 간의 POI 변화를 검출하도록 네트워크를 학습시키기 위해선 먼저 “POI 변화 정도”를 수치적으로 표현할 수 있어야 한다. 일반적으로 둘 이상의 데이터들 간의 거리는 임의의 특징 공간 상에서 정의된 metric을 이용하여 표현할 수 있다. 하지만 metric을 결정하는 일은 어렵고 목적이나 사람에 따라 주관적일 수 있다. 그림 5 (a)를 살펴 보자. 우측 고양이들 중 좌측 고양이와 "비슷한" 고양이는 어느 고양이일까? 눈이나 몸의 색, 얼굴 생김새의 닮음 등 여러 요소에 의해 비슷함이 정의될 수 있을 것이다. 또한 어떤 목적을 위해서 비슷한 고양이를 찾느냐에 따라 고려해야 할 요소가 달라질 것이다. 

이렇듯 결정이 까다로운 metric을 직접 결정하지 않고 데이터들 간의 관계를 통해 학습하는 방법을 metric learning이라고 한다. 그림 5 (b)에 동일한 색깔과 모양을 갖는 도형들은 서로 연관성을 갖는다고 가정하자. Metric learning의 목적은 우리가 가정한 도형들 사이의 연관성을 바탕으로 어지럽게 섞여있는 도형들의 멀고 가까움을 잘 정의할 수 있는 특정 metric을 학습하는 것이다. 이를 특징 표현 관점에서 보면 "도형들이 잘 구분될 수 있는 특징 공간을 찾는 것"이라고 이해할 수 있다. 데이터들 간의 관계를 바탕으로 구분력 있는(discriminant) 특징 공간을 만들 수 있으면 학습 시에 사용되지 않은 새로운 데이터가 입력되더라도 쉽게 멀고 가까움을 표현할 수 있게 된다. 예를 들어 그림 5 (c)와 같이 학습에 사용되지 않았던 회색 사각형이 새롭게 추가되더라도 잘 정의된 특징 공간 내에서는 해당 도형의 위치를 쉽게 결정할 수 있을 것이다. 색깔로 판단했을 때는 회색 동그라미들과 닮았고, 모양으로 판단했을 때는 분홍색 사각형들과 닮았기 때문에 그 중간에 위치시키는 것이 적절할 것이다.

그림 5. (a): "비슷한"이 뭘까? (b): Metric learning (c): 잘 정의된 특징 공간에 의해 쉽게 결정되는 새로운 데이터의 위치.

우리가 풀어야하는 문제 역시 “POI 변화를 어떻게 정의할까?”의 문제, 즉, POI 변화를 판단할 수 있는 metric을 결정하는 문제라고 생각할 수 있다. 다행히도 우리 문제에서는 같은 POI가 포함된 이미지들을 구분하는 것이 쉬우므로 데이터들 간의 관계를 쉽게 정의할 수 있었다. 그래서 우리는 ConvNet을 이용하여 POI 변화에 적절한 metric을 학습하고자 하였다.

Which network model did we use?

영상 검색(image retrieval)에 주로 사용되는 triplet 네트워크를 이용하여 metric learning을 진행하였다. Triplet 네트워크는 이름에서 유추할 수 있듯, 구조가 동일하고 파라미터를 공유하는 세 개의 네트워크로 구성된다.

그림 6. 특징 추출을 위한 네트워크 구조는 여러 개의 convolutional layer들과 fully-connected layer, L2-normalized layer로 구성된다.

우리의 목적은 metric learning을 이용하여 이미지를 POI 변화에 대해 구분력 있는 N 차원의 특징 공간으로 전이시키는 것이다. 따라서 ConvNet의 마지막 단에 fully-connected layer를 덧붙여서 이미지가 N 차원의 특징 벡터로 변환될 수 있도록 하였다. 구체적으로 이미지 분류(image classification)에서 좋은 성능을 보인 ResNet-101 네트워크에서 분류기(classifier)를 제거하고 2048 차원을 출력하는 fully-connected layer를 연결하였다. 또한 특징 사이의 거리를 Euclidean distance로 쉽게 계산하기 위하여 L2 정규화 layer를 추가하였다(그림 6).

기준 이미지(reference image), 관련 이미지(relevant image) 그리고 비관련 이미지(non-relevant image)로 이루어진 triplet이 네트워크에 입력되면 각 이미지의 N 차원의 특징 벡터(xr, xp, xn)가 출력된다. 기준 이미지와 관련 이미지는 POI 변화가 발생하지 않은 이미지 쌍을 이용하고, 비관련 이미지는 기준 이미지와 같은 POI를 포함하지 않는 모든 이미지 중에서 골라 이용한다. 관대하게 보면, 비관련 이미지는 기준 이미지로부터 POI 변화가 발생한 매장이라고 생각할 수 있다!

How to train

네트워크 모델 학습에는 다음과 같이 정의되는 triplet loss를 목적 함수로 이용하였다. 

두 특징 벡터 간의 거리를 d(.)라고 정의하면 triplet loss는 "POI 변화가 발생한 이미지들 사이의 거리(A)는 POI 변화가 발생하지 않은 이미지들 사이의 거리(B)보다 일정 수준(m) 이상 멀어야 한다."라고 해석할 수 있다. 단순하게 변화가 발생한 특징 벡터 간의 거리(A)는 멀게, 변화가 발생하지 않은 특징 벡터 간의 거리(B)는 가깝게 만드는 것이 아니라 상대적인 차이(A-B)를 조절하도록 학습한다. POI 변화가 발생하였지만 매우 유사하게 보일 수도 있고(그림 1), POI 변화가 발생하지 않았지만 인테리어 변화나 영상 촬영 각도 등에 의해 매우 달라보일 수도 있기 때문에(그림 2, 3), 무리하게 목적 함수를 줄이도록 학습하면 어려운 예시에 대해서 과적합(overfitting)되는 문제가 발생할 수 있기 때문이다. 

또한 좋은 학습 데이터 쌍을 고르는 일은 상대적인 차이를 계산하는 목적 함수를 이용할 때 매우 중요한데, 본 네트워크 학습 시에는 다음과 같은 고려 사항들이 있다. 

  • 전체 triplet은 데이터 개수(N)의 제곱(N2)만큼 얻을수 있으며 이는 방대한 양이기 때문에 전체 triplet을 이용하려 할 경우 학습 시간이 길어진다는 점과
  • 구분하기 쉬운 이미지 triplet을 이용하면 loss가 너무 작아서 학습이 잘 이루어지지 않거나, 학습된 네트워크의 성능이 매우 떨어진다는 점이다.

위 두 가지 사항을 해결하기 위해서는 전체 triplet을 모두 학습에 이용하지 않고, 쉽게 구분하기 어려운 triplet 위주로 학습하는 작업이 필요하다. 즉, 전체 이미지 쌍 중에서 쉽게 구분할 수 없는 이미지 triplet을 선별하는 작업(hard triplet mining)이 필요한 것이다. 우리는 학습 시에 특정 iteration 간격으로 이미지 쌍 간의 거리를 계산해서 어려운 이미지 triplet(기준 이미지, 매우 다른 관련 이미지, 매우 비슷한 비관련 이미지)들을 선별하는 작업을 함께 진행하였다.

The network says

이렇게 학습된 네트워크는 앞선 예시 이미지 쌍(그림 1, 2, 3, 4)들의 변화를 어떻게 판단하고 있을까? 각 이미지 쌍을 네트워크에 통과시켜 얻은 특징 벡터 간의 Euclidean distance를 변화 정도로 정의하고 결과를 확인하였다.

그림 7. (a): 학습된 네트워크를 이용하여 판단한 이미지 쌍의 POI 변화 정도. 좌측 두 이미지 쌍은 실제 POI 변화가 발생하였다. (b): POI 변화 이미지 쌍의 CAM 결과.

그림 7 (a)에서 확인할 수 있듯 학습된 네트워크는 실제로 POI 변화가 발생한 이미지 쌍에서 변화 발생 정도가 높다고 판단하였다. 네트워크가 이러한 판단을 내린 근거를 class activation map(CAM)[4]을 통해 짐작해 보았다. 그림 (b)에서 네트워크가 판단하기에 "변화가 발생한 영역"을 분홍색으로, "변화가 발생하지 않은 영역" 하늘색으로 나타내었다. 인간이 판단을 내리는 기준과 유사하게, 우리가 학습시킨 네트워크도 단순한 시각적 변화들(간판 색상, 인테리어, 조명 변화 등)을 무시하고 POI 변화를 정확하게 판단하는 것을 확인할 수 있다.

What to be done more?

자, 이제 우리는 metric learning을 이용해 두 이미지에서의 POI 변화를 검출할 수 있게 되었다. 하지만 이는 두 이미지를 비교하는 방법론에 대한 것일 뿐이며, 실제로 실내 지도 자동 업데이트 시스템을 구축하기 위해서는 본 아티클에서 중점적으로 다룬 내용 외에도 생각해 볼 문제들이 많이 남아있다. 예를 들어 다음과 같은 것들이다.

  • 비교해야 할 적절한 이미지 쌍을 어떻게 골라내어야 할까? 실내 자율 주행 로봇이 이동하며 이미지들을 취득했기 때문에 정확하게 같은 위치, 같은 각도로 촬영된 이미지 쌍은 존재하기 어렵다. 또한 같은 POI가 수많은 이미지에서 다른 촬영 각도와 크기로 등장할 수 있다. 
  • 어떤 평가 방법이 적합할까? 구축한 시스템이 잘 동작하는 지 확인하기 위해선 평가가 필요하며, 검출 알고리즘을 평가할 때에는 임계 값을 기준으로 성공률을 조사하는 방법이 일반적이다. 하지만 수 백 개의 상호들 중에 POI 변화가 실제로 존재하는 상호는 수 개에 불과하기 때문에 우리 문제에서는 모두 "POI 변화가 없다"라고 판단하더라도 성공률이 90%가 넘을 것이다.

앞서 설명한 metric learning과 이 문제들에 대해 우리가 찾은 답은 올해 컴퓨터 비전 및 패턴 인식 학회(Computer Vision and Pattern Recognition)에서 우리가 발표할 논문[1]과 아래의 아티클에서 확인할 수 있다. 또, “나는 더 좋은 방법을 알고있는데?” 라는 생각이 든다면 함께 공개될 데이터 셋과 성능 측정 코드를 이용하여 도전해보길 바란다.

셀프 업데이팅 맵, AI와 로봇이 바뀐 상호를 찾아주는 기술

 

References

[1] J. Revaud, M. Heo, R. Rezende, C. You, S.-G. Jeong, Did it change? Learning to detect Point-of-interest changes for proactive map updates., CVPR, 2019.
[2] A. Gordo, J. Almazán, J. Revaud, and D. Larlus. Deep image retrieval: Learning global representations fornimage search., ECCV, 2016.
[3] D. G. Lowe. Distinctive image features from scale-invariant keypoints., IJCV, 2004.
[4] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba. Learning deep features for discriminative localization, CVPR, 2016.

Related Articles

VIDEOS