수.알.못. 개발자가 해본 이미지 검색

어쩌다 보니 이미지 검색을 만드는 문제를 풀게 되어서 짧은 기록을 남긴다.

문제

이미지를 검색해야 한다. 80,000 정도의 이미지를 검색을 해야 하는데 제약조건은 crop/rotation에 영향을 받지 않아야 한다는 조건이 붙었다.

진행

이미지의 고윳값을 찾자

바로 떠오르는 알고리즘은 sift, 문제에서도 친절하게 sift 를 사용하는 게 어떠냐라는 설명을 달아줬기에 sift로 낙찰(1).

기본적인 로직은

1. 빛으로 인해 생기는 문제를 없애기 위해 이미지 픽셀 정규화 (흑백으로 바꾸기, 효과가 있는지는 모르겠다)
2. 이미지의 scale/rotation invariant feature 찾기
3. 이미지들의 특징점을 저장하기
4. 입력 이미지의 특징점들을 검색하기

로 설정을 했다.

사실 1, 2 는 opencv 에서 아주 잘 구현되어 있어서 고민 없이 바로 작성이 가능했다(물론 80,000장이나 되는 이미지의 특징점을 추출해야 해서 병렬처리가 필요했다).

python + opencv 로 간단하게 Pool 모듈을 활용해서 구현(2).

opencv + pool example

특징점들은 128개의 정수로 이루어져 있다(3).

특징점을 검색

이제 이미지에서 원하는 특징점은 찾았는데 어떻게 검색 해야 할까?

기본적으로 opencv 예제에서는 Image To Image, 즉 어떤 이미지 한 장에 대해서 카메라 입력이나 다른 이미지가 유사한지를 비교한다. 영상처리 수업과제였다면 적당한 matcher를 찾아서 결과만 짠! 하고 보여주면 되지만 지금은 80,000장에서 같은 이미지를 찾아야 한다.

다행히도 문제에 ElasticSearch를 쓰세요 라는 이야기가 있어 ES를 사용하기로 했다. lucene 을 한번 써 본 경험도 있고 해서 금방 되겠다라고 생각했는데...

구글링을 해보니 이미지 특징점들을 넣어주면 자동으로 해시값을 생성해서 ES에 인덱싱해주는 플러그인이 있었다(elasticsearch-image-features). 단점은 최신 버전인 ES 5.0 에서는 지원이 안 되고 (Image plugin 가 지원을 안 해서 오류가 발생) 2.2 버전 등 특정한 버전에서만 작동이 되어서 서버에 설치된 ES 버전을 낮추고 플러그인을 설치했다.

image-features 플러그인이 sift descriptor에 대해서 거리계산 부분이 없었다. 거리 계산이야 간단하니 기능을 추가했다 (자랑스러운 내 pr).

logic 1, 2 에서 만든 이미지 descriptor 들은 정수의 리스트이다. 정수의 리스트를 한 단어로 생각하면 앞서 구했던 특정점들의 집합은 이미지에 대한 공유한 문서로 볼 수가 있다. 이 정수들을 이용해서 해시값을 구한 뒤 얻어진 해시값을 이용해서 문서의 거리를 계산해서 유사한 문서를 출력한다.

문제가 생겼다. ES가 설치된 서버의 사양이 부족한 건지, 이미지를 수백 장 넣으면 ES 대몬이 아예 죽어버린다. 인덱싱된 이미지 300장 정도에서는 결과가 정상적으로 나왔지만 79,700장의 이미지가 남아있었다. 또, 한번 검색에 1분 이상이 걸렸다. 어떻게 해결해야 하는지 떠오르는 방법이 없어서 플러그인을 안 쓰고 직접 구현하기로 했다.

일단은 특징점을 그대로 인덱스를 해봤다. 그리고 다시 이미지 검색을 해봤는데 물론 아예 작동하지 않는다(4).

그다음으로 시도해본 방법은 128개의 숫자를 다시 n 개로 샘플링 해서 인덱스를 하는 방법이었다.

  • 이미지의 같은 위치의 특징점들은 128 개의 값을 가지고 있고 값이나 순서도 같다고 가정을 하면, 순서대로 i 번째 원소를 선택하면 차원이 조금 더 낮은 벡터를 얻을 수 있다.
  • 물론 정보에 손실이 있겠지만, 보통 이미지에서 특징점들이 수천 개를 뽑으니 큰 문제는 없다.

하지만 이 방법도 작동하지 않았다. 원본 이미지와 잘린 이미지에서 추출한 특징점 벡터가 매우 유사하지만 똑같지 않다는 것을 확인했다. ES에서 기본적으로 scoring은 word(0) from Doc(i), word(n) from Doc(j) 가 같으면 1점을 주는 형식인데 128개의 벡터가 유사하지 동일하지 않아서 다른 단어로 인식했다(5).

정상적인 해결책은 ES에서 scoring 함수를 작성해서 추가하는 것이다. 그러나 그 부분은 ES 부터 공부를 해야해서 포기했다.

기존 특징점 값들을 어떤 고유한 값들로 바꾸는 작업이 필요했다.

simple mean binary hashing
  1. 특징점 벡터를 하나 받아서 해당 벡터를 ‘step’만큼 건너뛰면서 샘플링 한다.
  2. 샘플링된 벡터에 평균값을 기준으로 “0 if x > mean else 1”로 치환한다.
  3. 결과를 공백 문자를 분리자로 조합을 하면 특징점 벡터가 정보를 조금은 유지한 채로 이진수 문자열로 변환된다.

결과

충분히 만족할 만한 시간(1,000ms 이하)에서 crop 된 이미지에서 원본 이미지를 찾아온다. 또, 핸드폰에서 모니터를 찍은 사진에서 같은 사진을 찾아온다.

결론

이라기보다는 문제를 풀면서 아쉬웠던 점들을 나열해보면.

  1. 자동으로 인덱스 된 이미지 중 몇 개를 뽑아서 crop / rotation 등등 해서 얼마나 결과를 잘 찾아오는지 에 대한 분석 스크립트를 만들었으면 좋았을 것 같다.
  2. 특징점 벡터를 0/1으로 인코딩 하지 말고 quantile 같은 조금 더 다양한 값으로 했으면 어땠을까
  3. mean 대신 median을 썼을 때 성능 향상이 있을까
  4. 특징점 벡터가 sparse 하니 기준값을 구할 때 0을 제외하고 했으면 어떻게 되었을까
  5. ES를 잘 써야겠다.
  6. Root Sift이라는 알고리즘이 좋다고 쓰여있는데 적용하면 정말로 성능 향상이 있을까?

정도이다.

조금 더 공부해야겠다.

참고

(1) sift는 특허가 아직도 살아있다. 상업적인 용도로 쓰려면 돈을 내야 하므로 상업적인 용도로는 surf를 쓰면 된다.

(2) 맥북 에어에서 돌려야 되서 process를 4개를 줬는데, 비싼 서버(160$/month)에서 돌리니 16개를 줘도 잘 돈다. 비싼 서버에서 적당한 크기 이미지 (400x400 정도인 거 같다) 80,000장을 4시간 정도 안에 끝낸다.

덧) 쓰레드 병렬성보다는 프로세스 병렬성이 비싸지만, 구현은 쉽다. 메모리 공유는 pipe로 처리해보자.

(3) opencv 에서 내부적으로 round off 오류를 최소화하기 위해 float -> int 로 값을 바꾼다.

https://cw.fel.cvut.cz/wiki/_media/courses/a4m33mpv/cviceni/2_hledani_korespondenci/gradient-descriptor.png

8개의 원소를 가진 벡터 * 16(칸) = 128개

(4) 나중에 알게 된 거지만 ES에서 문서를 인덱싱할 때 field(어떻게 부르는지 모르겠다) 에 들어갈 값과 해당 문서를 어떻게 자를 지(tokenizer) 등을 설정을 해줘야 한다.

(5) 예를 들어, ‘apple’ / ‘bpple’은 서로 다른 단어이므로 기본적인 scoring 함수에서는 서로 다르다고 인식한다. 내가 검색해야 할 특징점들은 <1,0,0,0,2>/ <1,0,0,0,3> 이런 식으로 비슷하지만 다른 벡터의 거리를 scoring 해야 한다.

Like what you read? Give Sung Min Lee a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.