Advanced
Performance Analysis of Modified LLAH Algorithm under Gaussian Noise
Performance Analysis of Modified LLAH Algorithm under Gaussian Noise
Journal of Korea Multimedia Society. 2015. Aug, 18(8): 901-908
Copyright © 2015, Korea Multimedia Society
  • Received : April 03, 2015
  • Accepted : July 10, 2015
  • Published : August 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
호섭 류
Department of Electronic Engineering, Pukyong National University
한훈 박
Department of Electronic Engineering, Pukyong National University
hanhoon_park@pknu.ac.kr

Abstract
Methods of detecting, describing, matching image features, like corners and blobs, have been actively studied as a fundamental step for image processing and computer vision applications. As one of feature description/matching methods, LLAH(Locally Likely Arrangement Hashing) describes image features based on the geometric relationship between their neighbors, and thus is suitable for scenes with poor texture. This paper presents a modified LLAH algorithm, which includes the image features themselves for robustly describing the geometric relationship unlike the original LLAH, and employes a voting-based feature matching scheme that makes feature description much simpler. Then, this paper quantitatively analyzes its performance with synthetic images in the presence of Gaussian noise.
Keywords
1. 서 론
영상 정합은 입력 영상에서 코너(corner)나 블롭(blob)과 같은 특징(feature)을 검출하고, 특징이 가지는 고유 정보를 기술(description)한 후, 같은 기술정보를 가지는 특징을 찾음(matching)으로써, 영상간의 기하 변환을 계산하는 과정을 말한다 [1] . 이처럼, 특징을 검출, 기술, 매칭하는 과정은 영상 정합을 포함한 다양한 영상 처리 및 컴퓨터 비전 응용 분야의 핵심 과정으로 [2 , 3] , 다양한 방법들이 개발되어 왔다 [4 , 5] . 하지만 현재 보고된 대부분의 방법의 경우 특징 기술을 위해 특징 주변의 밝기 분포, 그래디언트(gradient) 분포 등을 활용하는데, 텍스처(texture)가 열악한 장면(scene)에서는 특징 주변으로부터 특징 기술에 필요한 충분한 정보를 확보하기 어렵기 때문에 유용성이 크게 떨어진다.
텍스처가 열악한 장면에 대한 효과적인 특징 기술/매칭 방법으로, LLAH(Locally Likely Arrangement Hashing) [6] 는 검출된 특징의 이웃 특징들 사이의 기하 관계를 이용하여 특징을 기술할 수 있으며, Fig. 1 과 같이 텍스트, 랜덤 점, 별자리 영상 등의 텍스처가 매우 열악한 영상(주위 픽셀의 밝기 변화가 거의 없음)에 대해서도 우수한 성능을 가진다 [6 , 7 , 8] . 그러나, 특징 기술 과정이 복잡하고, 검출된 특징의 신뢰도에 의한 영향이 매우 큰 데 [9] , 검출된 특징의 신뢰도는 시점에 의한 영상 변환이나 잡음 등에 의해 크게 떨어질 수 있다. 그러므로, 기존의 LLAH 응용 분야는 높은 신뢰도를 가진 특징 검출이 가능한 분야로 국한되었다. 본 논문에서는 기존의 LLAH와 달리 특징 기술을 위해 중심 특징을 포함하고, 보팅(voting) 기반 특징 매칭 방법을 도입하여 특징 기술 과정을 간소화함으로써, 보다 효율적이고 가우시안 잡음의 영향에 강인한 변형된 LLAH 방법을 제안하고, 성능을 평가한다.
PPT Slide
Lager Image
Recognition of text, random dots, constellation using LLAH.
2. 관련 연구
- 2.1 LLAH
특징 사이의 기하 관계를 이용하여 특징을 기술하는 방법은 별자리 인식 분야에서 주로 연구되어 왔다 [10 , 11] . 별자리의 경우 각 별의 위치는 쉽게 검출할 수 있지만, 주변에 텍스처가 거의 없기 때문에 각 별을 독립적으로 기술할 수 없으며, 서로 간의 기하 관계를 이용할 수밖에 없다. 또한, 별자리 인식 자체가 별 사이의 기하학적인 관계를 찾는 것이므로 자연스러운 접근 방법이라 할 수 있다. 그러나, 별자리의 경우 촬영 환경에 따른 영향(예, 시점 변화에 따른 원근(perspective) 왜곡)이 거의 없어 별 사이의 각도나 거리 등을 이용하여 쉽게 인식될 수 있으나, 일반적인 장면의 경우 그렇지 못하기 때문에 특징 사이의 기하 관계를 보다 효과적으로 기술할 수 있는 방법이 필요하다. LLAH는 특징 주변의 텍스처가 부족한 텍스트 영상 인식을 위해 개발된 방법으로, 텍스트 영상이 어파인(affine) 또는 원근 변환을 가지거나 각종 잡음, 이상치(outlier) 등을 포함하더라도 효과적으로 각 특징을 기술할 수 있다.
LLAH의 대략적인 특징 기술 과정은 다음과 같다. 특징이 미리 검출되어 있다고 가정했을 때, 특징을 기술하기 위해 우선 임의의 중심 특징( Fig. 2 에서의 p )으로부터 거리가 가까운 순서대로 f 개의 이웃 특징들을 선택한다. 다음으로, 선택한 f 개의 이웃 특징들로부터 m 개의 특징을 조합(Combination)한다. 이는 특징 기술의 안정성(서로 다른 시점의 영상들에서 잡음 등으로 인해 특징이 추가, 제거되거나 특징의 위치가 크게 변하는 경우에 대해 성능 유지)을 보장하기 위한 것으로, 이때 f 로부터 조합될 수 있는 모든 m 조합의 수( fCm )가 중심 특징의 기술자(descriptor)의 개수가 된다. 각 기술자는 앞에서 선택된 이웃 특징 m 으로부터 다시 n (4 또는 5)개의 특징들을 선택하여 만들어지는 삼각형들의 영역비(area ratio)와 교차비(cross ratio)를 이용하여 식 (1)과 (2)처럼 계산된다( Fig. 2 참조).
PPT Slide
Lager Image
Feature description using neighbor features in LLAH. a-e: neighbors of feature p.
PPT Slide
Lager Image
PPT Slide
Lager Image
여기서, Δ( a , b , c )는 특징 a , b , c 로 이루어진 삼각형의 면적을 의미한다. 그러므로, 각 기술자는 mCn 차원을 가지는데, 이웃 특징의 순서에 따라 기술자가 달라질 수 있다. 영상의 회전으로 인해 이웃 특징의 순서가 바뀔 수 있으므로, 회전 불변성을 가지는 기술자를 생성하기 위해 중심 특징을 기준으로 이웃 특징의 수만큼 이웃 특징들을 회전시키면서 기술자를 생성한다. 생성된 기술자는 미리 생성된 해시(hash) 테이블을 이용하여 미리 정의된 값을 가지는 1차원 인덱스(index)로 변환된다. 각 특징은 fCm 개의 인덱스를 가지지만 일반적으로 모든 이웃 특징이 신뢰할 수 있다고 할 수 없기 때문에, 특징 매칭은 하나 이상의 같은 인덱스를 가지는 특징을 찾는 과정을 통해 이루어진다.
- 2.2 보팅을 이용한 특징 매칭
일반적으로 특징 매칭은 특징 기술자 사이의 직접적인 유클리디안(Euclidean) 거리를 이용한다. 속도향상을 위해 클러스터링(clustering) [12] 이나 LLAH [6] 에서처럼 해싱 방법을 이용할 수도 있다. 그러나, 이러한 방법들은 기본적으로 각 특징이 하나 혹은 적은 수의 기술자를 가질 경우에 대한 것으로, 다수의 기술자를 가질 경우 각 기술자로부터 계산된 유클리디안 거리를 통합하는 과정이 필요하다. 모든 기술자를 신뢰할 수 없다면, 단순히 평균을 취하는 등의 방법에 비해 보팅을 이용하는 것이 보다 효과적이다 [11] . 보팅 방법은 각 특징이 v 개의 기술자를 가진다고 할 때, 한 특징의 각 기술자와 유사한 기술자를 가지는 모든 특징을 보팅함으로써, 가장 많은 보팅(< v )을 받은 특징을 찾는다. 여기서, 각 기술자 사이의 유사도는 앞서 설명한 방법들을 사용할 수 있다. 직접적인 유클리디안 거리를 이용한다면, 보팅을 이용한 특징 매칭은 다음과 같이 표현된다.
PPT Slide
Lager Image
여기서,
PPT Slide
Lager Image
k 번째 특징의 i 번째 기술자를 의미하고, ε 은 미리 정해진 상수이다. votel ( k )는 k 번째 특징에 의한 l 번째 특징의 보팅 값을 계산하는 함수를 의미한다.
3. 변형된 LLAH 알고리즘
기존의 LLAH 알고리즘에서는 Fig. 2 와 같이 중심특징을 제외하고 이웃 특징들만을 이용하여 mCn ( n =4 또는 5)개의 조합을 구성하고 각 조합의 영역비와 교차비를 계산하여 기술자를 생성한다. 그러나, 본 논문에서는 기존의 LLAH 알고리즘과 달리 Fig. 3 에서처럼 이웃 특징뿐만 아니라 중심 특징도 함께 이용하여 기술자를 생성한다. 이는 기술자 생성에 필요한 이웃 특징의 수를 하나 줄이는 것을 가능하게 하며 ( mCn , n =3 또는 4), 기존의 LLAH 알고리즘 보다 이용되는 이웃 특징의 수가 적기 때문에 기술자의 안정성이 향상될 수 있다.
PPT Slide
Lager Image
Neighbor feature selection for feature description in modified LLAH.
또한, LLAH 알고리즘에서는 해싱 방법을 사용하여 기술자를 비교하는데, 이 때 기술자의 안정성을 보장하기 위해서 기술자 생성 과정에서 fCm mCn ( n =4 또는 5)의 총 두 번의 조합 과정이 요구된다. 또한, 회전 불변성을 가지는 기술자를 생성하기 위한 추가적인 과정을 필요로 한다. 그러나, 본 논문에서는 한 번의 조합 과정( mCn , n =3 또는 4)으로 영역비나 교차비 값으로 이루어진 다수의 스칼라(scalar) 기술자를 생성하여 보팅 방법을 사용하여 기술자를 비교한다. 스칼라 기술자이므로 기술자 생성의 순서는 상관없으며 본질적으로 회전 불변성을 가진다. 이는 기술자 생성 과정의 효율성을 크게 향상시킬 수 있다.
4. 실험 결과 및 고찰
- 4.1 실험 환경
본 논문에서 제안된 변형된 LLAH 알고리즘의 성능 분석을 위해 Fig. 4 와 같이 700*700의 크기를 가지는 영상에 각각 150 픽셀, 100 픽셀, 70 픽셀의 평균거리를 가지는 특징 30개, 60개, 120개를 임의로 배치한 영상을 이용하였다. 식 (1)과 (2)의 영역비와 교차비는 각각 어파인 변환과 원근 변환에 불변인 기하정보로서, 실영상과 유사한 조건에서의 성능 분석을 위해서는 일정 크기의 어파인 변환과 원근 변환을 포함하고 일정 크기의 잡음을 포함하는 영상이 마련되어야 한다. 그러나, 어파인 변환이나 원근 변환 크기에 따른 성능을 정량적으로 분석하기 쉽지 않기때문에 본 논문에서는 가우시안 잡음에 의한 좌표 변환에 따른 성능(특징의 매칭율 및 매칭 속도)을 분석한다. 이를 위해, 각 영상에 삽입된 특징의 좌표에 일정 크기의 가우시안 잡음을 추가하였다(제안된 알고리즘은 영상의 2차원 이동이나 회전 변환에는 불변이기 때문에 고려하지 않았다). 잡음에 의한 특징의 좌표 변환은 어파인 변환이나 원근 변환을 부분적으로 포함하므로, 어파인 변환이나 원근 변환의 영향을 간접적으로 파악할 수 있다. 물론, 잡음에 의한 좌표 변환은 어파인 변환이나 원근 변환보다 열악한 조건이므로 변환 크기에 따른 성능 저하는 보다 클 수 있다. 그러므로, 본 논문에서는 실험 조건에 따른 상대적인 성능 차이를 분석하는 데 보다 초점을 둔다.
PPT Slide
Lager Image
Random dot images used in experiments. Number of features: (a) 30, (b) 60, (c) 120.
특징 매칭(식 (3))에서 ε = 0.05로 설정되었다. 각 알고리즘은 병렬처리 없이 구현되었으며, i3 3.3GHz CPU와 4GB RAM을 가지는 PC에서 실행되었다.
- 4.2 실험 결과 및 고찰
Table 1 , 2 , 3 은 각각 특징의 수가 30, 60, 120인 경우에 대해 중심 특징의 선택 여부, 이웃 특징의 수( m , n )와 가우시안 잡음의 크기(표준편차 σ )에 따른 특징의 매칭율 결과이며, 매칭율은 같은 조건 하에서 100번 반복 수행한 평균이다.
Matching rate [%] when the mean distance between features is 150 pixels
PPT Slide
Lager Image
Matching rate [%] when the mean distance between features is 150 pixels
Matching rate [%] when the mean distance between features is 100 pixels
PPT Slide
Lager Image
Matching rate [%] when the mean distance between features is 100 pixels
Matching rate [%] when the mean distance between features is 70 pixels
PPT Slide
Lager Image
Matching rate [%] when the mean distance between features is 70 pixels
교차비가 영역비에 비해 보다 높은 자유도를 가지는 변환에 불변임에도 불구하고, 모든 경우에 대해 영역비를 이용했을 때보다 교차비를 이용했을 때 매칭율이 감소됨을 알 수 있다. 이는 영역비를 계산할 때 보다 교차비를 계산할 때 특징을 하나 더 이용하기 때문이며, 이는 이용되는 특징의 개수에 따라 가우시안 잡음 영향 역시 증가함을 보여준다.
전체적인 매칭율을 살펴보면 제안하는 기술 방법(중심 특징 함께 사용)이 기존의 LLAH 방법에서처럼 이웃 특징만을 사용하는 것에 비해 높은 매칭율을 보이며, σ 가 증가할수록 매칭율 차이가 비율적으로 커짐을 알 수 있다. 이는 중심 특징을 함께 사용함으로써, 같은 m 값을 가지더라도 보팅을 위한 조합의 수가 커지기 때문이며(예, 6 C 3 > 6 C 4 , 8 C 4 > 8 C 5 ), Fig. 5 에서 보는 것처럼, 조합의 수가 증가하면 매칭율은 증가한다. 또한, 일부 조합의 수가 작아지는 경우(예, 8 C 3 < 8 C 4 , 9 C 3 < 9 C 4 )에도 이웃 특징의 수가 줄기때문에 이상치(잡음의 크기에 따라 일부 특징의 경우 이상치와 같은 역할을 할 수도 있음)에 의한 영향이 감소하는 것도 매칭율 향상에 도움을 준 것으로분석된다.
PPT Slide
Lager Image
Matching rate (when the number of features is 30) and matching time (for each feature) with different m values in the modified LLAH. For (a) area ratio and (b) cross ratio.
Table 2 3 에서 보는 것처럼 특징 사이의 평균거리가 감소할수록 매칭율은 감소했다. 이는 특징의 수가 늘고 평균 거리가 짧아지면 특징이 밀집하거나 일직선에 가깝게 배치되기 때문에, 잡음의 영향이 커져 약간의 잡음에도 영역비나 교차비의 변화가 매우 크게 나타날 수 있기 때문이다. 실제로 Fig. 6 에서 보는 것처럼 평균 거리가 짧아질수록 영역비와 교차비의 변화는 비례적으로 증가했다. 결과적으로, 기하관계를 이용하여 기술된 특징의 매칭율은 특징 사이의 평균 거리에 의해 크게 영향을 받으며, 매칭율 향상을 위해서는 특징이 밀집되지 않도록 특징 사이의 평균 거리를 일정 이상 유지시키는 것이 필요하다 [9] .
PPT Slide
Lager Image
Variation of area ratio and cross ratio caused by the Gaussian noise in the modified LLAH when m = 7 and n = 3. For (a) area ratio and (b) cross ratio.
Table 1 , 2 , 3 에서 보는 것처럼, 보팅을 이용한 특징 매칭은 일반적으로 m 값이 증가할수록 매칭율은 증가한다. 그러나, Fig. 5 에서 보는 것처럼 일정 크기 이상이 되면 매칭율은 포화되고, 무엇보다 처리 시간이 급격하게 증가하기 때문에 9 이상이 되면 효율성이 크게 떨어졌다. 그러므로, Table 1 , 2 , 3 에서는 9이하의 매칭율만을 고려하였으며, 8일 때 가장 효과적임을 알 수 있다.
모든 경우에 대해 매칭율은 잡음의 세기가 증가할수록 감소하는데, 잡음의 세기가 일정 크기 이상이 되면 매칭율이 급격히 감소함을 알 수 있다. 이는 Fig. 6 에서 보는 것처럼 영역비와 교차비의 평균값이 0.474, 0.448 정도인데 잡음의 세기가 2 이상이 되면 영역비와 교차비의 변화량이 평균 0.2~0.3 정도(표준편차 역시 비례적으로 증가함)가 되어 영역비와 교차비가 크게 달라질 수 있기 때문이다. 앞서 언급한 것처럼, 잡음에 의한 좌표 변환은 어파인 변환이나 원근 변환보다 매우 열악한 조건으로, 성능 저하속도가 매우 빨랐다. 그러나, 실험 조건에 따른 상대적인 성능 차이를 분석하는 데는 큰 문제가 없는 결과를 보였다. 또한, 영상의 가장자리에 위치한 특징의 경우 이웃 특징이 상대적으로 밀집되어 분포하기 때문에 앞서 언급한 이유로 매칭율이 급격히 떨어질 수 있다. 실험에서 사용된 영상의 경우 특징의 수가 많지 않기 때문에 가장자리에 위치한 특징의 매칭율 저하가 전체 매칭율에 크게 영향을 미쳤을 것으로 판단된다.
5. 결 론
본 논문에서는 특징 주변의 텍스처 정보가 아닌 이웃 특징 사이의 기하 관계를 이용하여 특징을 기술하기 위한 방법으로, 기존 LLAH 방법 [6] 을 특징 선택, 기술, 매칭 과정을 변형한 LLAH 방법을 제안하고, 가우시안 잡음에 대한 제안된 방법의 성능을 분석하였다.
특징 기술에 사용되는 특징의 수가 증가할수록 잡음의 영향이 커지기 때문에, 어파인 변환에 불변인 영역비를 이용하는 것이 원근 변환에 불변인 교차비를 이용하는 것보다 향상된 결과를 보였으며, 중심특징을 함께 사용하는 것은 이웃 특징만을 사용하는 것에 비해 특징 기술을 위한 조합의 수를 증가시켜 보팅에 의한 특징 매칭의 성능을 개선하는 효과를 가졌다. 이웃 특징의 수를 증가시키는 것은 보팅에 의한 특징 매칭율을 향상시킬 수 있으나, 일정 수 이상이 되면 매칭율은 포화되고 무엇보다 계산 시간이 급격하게 증가하기 때문에 많은 수의 이웃 특징을 사용하는 것은 실용적인 측면에서 바람직하지 않았다. 결과적으로, 8 개의 이웃 특징과 중심 특징을 사용하여 영역비를 계산한 후, 보팅에 의한 특징 매칭을 수행하는 것이 가장 좋은 성능을 보였다.
향후 효과적으로 이웃 특징 사이의 평균 거리를 일정 이상 유지시킬 수 있는 방법에 대한 추가 연구를 수행할 계획이다. 또한, 기존 LLAH 방법과의 정성적, 정량적 성능 비교, 분석 실험이 이루어져야 할 것이다.
BIO
류 호 섭
2012년 8월 부경대학교 전자공학과 졸업(공학사)
2015년 2월 부경대학교 대학원 전자공학과 졸업(공학석사)
관심분야 : 증강현실, 영상처리 및 컴퓨터 비전
박 한 훈
2000년 2월 한양대학교 전자통신전파공학과 졸업(공학사)
2002년 2월 한양대학교 대학원 전자통신전파공학과 졸업(공학석사)
2007년 8월 한양대학교 대학원 전자통신전파공학과 졸업(공학박사)
2007년 9월~2008년 10월 한양대학교 BK21박사후연구원
2008년 11월~2011년 10월 NHK방송기술연구소 박사후연구원
2011년 11월~2012년 2월 한양대학교 전기정보통신기술연구소 연구교수
2012년 3월~현재 부경대학교 전자공학과 부교수
관심분야 : 증강현실, 인간컴퓨터상호작용, 3차원 영상처리/비전 등
References
Szeliski Richard 2006 “Image Alignment and Stitching: A Tutorial,” Foundations and Trends in Computer Graphics and Computer Vision 2 (1) 1 - 104    DOI : 10.1561/0600000009
Kim M.-K. 2013 “Finger-Knuckle-Print Verification Using Vector Similarity Matching of Keypoints,” Journal of Korea Multimedia Society 16 (9) 1057 - 1066    DOI : 10.9717/kmms.2013.16.9.1057
Choi K.-W. , Jung D.-U. , Lee S.-H. , Choi J.-S. 2012 “Interaction Augmented Reality System Using a Hand Motion,” Journal of Korea Multimedia Society 15 (4) 425 - 438    DOI : 10.9717/kmms.2012.15.4.425
Tuytelaars T. , Mikolajczyk K. 2007 “Local Invariant Feature Detectors: A Survey," Foundations and Trends in Computer Graphics and Vision 3 (3) 177 - 280    DOI : 10.1561/0600000017
Li J. , Allinson N.M. 2008 “A Comprehensive Review of Current Local Features for Computer Vision," Neurocomputing 71 (10-12) 1771 - 1787    DOI : 10.1016/j.neucom.2007.11.032
Nakai T. , Kise K. , Iwamura M. “Use of Affine Invariants in Locally Likely Arrangement Hashing for Camera-Based Document Image Retrieval,” Proceedings of International Conference on Document Analysis Systems 2006 541 - 552
Uchiyama H. , Saito H. “Random Dot Markers,” Proceedings of IEEE Virtual Reality Conference 2011 35 - 38
Seo B.-K. , Uchiyama H. , Park J.-I. “stAR: Visualizing Constellations with Star Retrieval,” Proceedings of ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia 2011 Article No. 53
Uchiyama H. , Marchand E. “Toward Augmenting Everything: Detecting and Tracking Geometrical Features on Planar Objects,” Proceedings of International Symposium on Mixed and Augmented Reality 2011 17 - 25
Padgett C. , Kreutz-Delgado K. , Udomkesmalee S. 1997 “Evaluation of Star Identification Techniques,” Journal of Guidance, Control and Dynamics 20 (2) 259 - 267    DOI : 10.2514/2.4061
Kolomenkin M. , Pollak S. , Shimshoni I. , lindenbaum M. 2008 “Geometric Voting Algorithm for Star Trackers,” IEEE Transactions on Aerospace and Electronic Systems 44 (2) 441 - 456    DOI : 10.1109/TAES.2008.4560198
Muja M. , Lowe D.G. “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration,” Proceeding of International Conference on Computer Vision Theory and Applications 2009 331 - 340