Advanced
Analysis of Straight Line Detection Using PCA
Analysis of Straight Line Detection Using PCA
Journal of the Korea Institute of Information and Communication Engineering. 2015. Sep, 19(9): 2161-2166
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : June 10, 2015
  • Accepted : July 31, 2015
  • Published : September 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
정수 오
ojs@pknu.ac.kr

Abstract
본 논문은 주성분 분석을 이용한 직선 검출 알고리즘을 분석하여 새로운 두 기능이 추가된 개선된 알고리즘을 제안한다. 첫 번째 기능은 검출된 직선을 통해 무효 화소를 제거하고 다시 직선을 검출하는 것이고, 두 번째 기능은 겹치지 않는 블록들에서 직선 검출을 통해 후보 직선들 선택하고, 각 후보 직선의 주변 화소들을 이용해 유효 직선을 검출하는 것이다. 제안된 알고리즘은 정제된 직선 영상에서는 기존 알고리즘보다 적은 계산량으로 더 정확한 직선을 검출하고 있다.
Keywords
Ⅰ. 서 론
직선 검출은 영역 분할을 필요로 하는 디지털 영상처리 영역에서 필수적인 기술이다. 자동 부품 검사기를 위한 부품 영역 검출, 도로 영상의 차선 검출, 3차원 영상 분석을 위한 소실점 검출 등이 직선 검출이 사용되는 예들이다 [1 - 4] . 직선 검출을 위해 가장 보편적으로 사용되는 허프변환(hough transform)은 에지 화소들에서 발생 가능한 모든 직선들의 매개변수들을 매개변수 공간으로 대응시켜 보팅(voting)하는 알고리즘으로 계산적 부담이 있고 정밀한 직선 검출이 어렵다 [3 - 5] .
본 논문은 주성분 분석(PCA)을 이용한 직선 검출 알고리즘을 제안한다. 주성분 분석 [6 - 9] 은 다차원 데이터 집합에서 데이터간 분산을 최대로 하는 새로운 주성분들을 찾는 알고리즘으로 영상처리 영역에서 자주 사용되고 있다. 직선은 일렬로 모여 있는 데이터들의 집합이므로 특정 방향에 대해 매우 큰 분산을 갖고, 직교 방향에 대해 매우 작은 분산을 갖는다. 따라서 제안된 알고리즘은 에지 화소들을 데이터 집합으로 한 주성분 분석에서 최대 고유값 (eigen value)을 갖는 주성분의 고유 벡터 (eigen vector)로부터 직선 기울기를 구하고 다른 성분의 고유값으로 직선의 신뢰성을 평가하여 직선을 검출한다. 그리나 제안된 알고리즘은 잡음이나 다수의 직선을 포함하는 영상에서 잘못된 직선을 검출할 수 있다. 이를 보완하기 위해 유효 직선 화소만으로 직선 검출을 수행하는 알고리즘과 영상을 블록으로 나누어 먼저 직선 후보를 검출하고 이들을 근거로 유효 직선을 검출하는 개선된 알고리즘도 제안하고 있다.
제안된 알고리즘을 평가하기 위해 먼저 직선 생성 방법을 제시하여 분석하고, 생성된 직선과 임의의 직선에서 기존 알고리즘과 제안된 알고리즘으로 직선 검출하여 성능을 분석한다. 제안된 알고리즘은 다소 정제된 직선을 포함하는 영상에서는 적은 계산으로도 보다 정확한 직선을 검출할 수 있는 것을 보여줄 것이다.
Ⅱ. 주성분 분석
주성분 분석은 다차원 데이터 집합을 최대 제곱 오차 관점에서 데이터 정보를 더 잘 나타낼 수 있는 주성분들의 데이터 집합으로 변환하는 기법이다 [6 - 9] . 예를 들어 그림 1 과 같이 데이터 집합 A가 주어질 때 xy 공간에 표현된 데이터 집합을 E 1 E 2 공간으로 변환하면 E 2 축의 분산을 최대화하여 데이터들 더 잘 표현할 수 있다. 또한 모든 데이터가 E 2 축 위에 투영되어 서로 겹치지 않으면 E 1 축을 줄일 수 있다. 따라서 주성분 분석에 의해 찾은 E 1 E 2 공간은 데이터 집합의 정보를 잘 나타낼 수 있을 뿐만 아니라 일부 주성분들만 유지시켜 저차원 데이터 집합으로 변환할 수 있다. 주성분의 비교, 축소 등은 영상 인식, 압축, 잡음 제거 등 영상처리 영역에서 활용되고 있다. 또한 주성분 E 2 를 활용하여 직선 근사 알고리즘으로도 사용되고 있다.
PPT Slide
Lager Image
주성분 분석 Fig. 1 PCA
Ⅲ. 영상에서 직선의 표현
영상은 격자 모양의 작은 화소들로 구성되어 있어 직선을 실제 모습 그대로 표현할 수 없다. 그래서 효율적인 직선 검출을 위해 영상에서 직선 표현에 대한 분석은 필요하다. 직선 표현 능력을 분석하기 위해 그림 2 와 같이 주어진 한 화소 굵기의 수평 직선을 직선 중심을 축으로 회전하여 다양한 직선들을 생성하고 있다. 여기서 l 은 직선 길이로 5~61의 홀수 길이를 갖고, θ 는 직선 기울기로 1~180도의 값을 갖는다.
PPT Slide
Lager Image
직선 생성 Fig. 2 Line generation
회전은 직선을 구성하는 화소를 개별적으로 회전하는 방식(PR)과 영상 자체를 회전하는 방식(IR)을 사용하여 비교한다. 격자 형태의 화소로 이루어진 직선은 그림 2 에서 1도 간격으로 회전시킬 때 변화가 없을 수 있다. 그림 3 은 주어진 직선을 180회 회전시킬 때 생성되는 서로 다른 직선의 수를 보여주고 있다. 직선 길이가 짧을수록 서로 다른 직선의 수가 적고, 직선 길이가 59 화소 이상이 되어야 180개의 서로 다른 직선을 만들어 낸다. 그리고 PR과 IR을 비교할 때 직선 길이가 33 화소이상에서는 같은 성능을 보이지만 33 화소보다 작을 때 IR이 더 많은 직선을 생성하고 있다. 이는 PR은 화소단위로 일대일 회전 이동하는 반면 IR은 회전된 화소가 화소들 사이에 이동할 때 화소 수를 증가시켜 더 다양하게 표현하기 때문이다. 이후 실험은 IR 회전을 사용한다.
PPT Slide
Lager Image
주어진 직선에서 생성된 직선의 수 Fig. 3 Number of line generated from a given line
그림 4 는 일부 직선에 대해 기울기를 변화시킬 때 직선이 유지하는 수(NofUL)를 보여주고 있다. 예를 들어 직선 길이 7인 2점 쇄선의 경우 81~99도의 19개 직선 기울기에 대해 같은 직선으로 표현되어 그들의 NofUL이 19인 것을 보여주고 있다. 이는 하나의 작은 직선이 19 개의 다른 직선이 될 수 있음 나타내기도 한다. 또한 최대 NofUL는 수직 직선과 수평 직선에서 발생하고 다음 크기의 NofUL는 70/110도와 45/135도 주변에서 발생하고 있는 것을 보여주고 있고, 이들에서 검출되는 직선은 신뢰도가 떨어질 수 있음을 나타낸다. 그림 4 에서 직선 길이가 길수록 NofUL가 작아지다 59 이상에서 NofUL가 1로 모든 기울기에서 다른 직선을 생성하고 있는 것을 보여주고 있다. 따라서 직선 길이와 검출된 기울기를 통해 실제 직선을 예상할 수 있다.
PPT Slide
Lager Image
기울기들(θ)에서 NofUL Fig. 4 NofUL at θs
Ⅳ. 주성분 분석을 이용한 직선 검출
주성분들은 데이터 집합의 공분산 (covariance) 행렬로부터 계산된 고유값 (eigen value)과 고유벡터 (eigen vector)에서 얻을 수 있다. 여기서 고유값과 고유벡터는 각각 주성분들의 중요도(분산)와 방향을 나타낸다. 2차원 공간 특징인 에지 화소를 데이터 집합으로 직선을 검출하고 있으므로 데이터 집합은 2차원이고, 이들의 고유값 (Evalue)과 고유벡터 (Evector)는 식 (1)과 같이 표현할 수 있다.
PPT Slide
Lager Image
여기서 최대 고유값이 λ 2 이면 고유벡터 E 2 가 최대 주성분으로 직선의 방향 벡터가 되고, λ 1 는 E 1 에 대한 분산으로 직선의 굵기를 나타낸다. 이때 직선의 기울기 θ 는 방향 벡터 E 2 의 요소들을 이용해 식 (2)와 같이 계산할 수 있다.
PPT Slide
Lager Image
Ⅴ. 직선 검출 실험 및 결과 분석
성능 평가를 위해 그림 2 에서 생성된 직선들에 대해 허프변환 알고리즘과 제안된 알고리즘을 이용해 직선 검출을 수행하고 결과를 비교하였다. 그림 5 는 주어진 직선에서 기울기가 1~180도인 입력 직선에 대해 출력되어야 할 최적의 직선 기울기를 보여주고 있다.
PPT Slide
Lager Image
입력 θ 대 출력 θ Fig. 5 Input θ vs. output θ
표 1 은 주어진 직선에서 기울기가 1~180도인 직선들에 대해 검출된 직선 기울기와 최적의 직선 기울기의 평균 오차를 보여주고 있다. HT_1.0과 HT_0.5는 각각 1과 0.5도의 기울기 검출 해상도인 허프변환 알고리즘이고 PCA는 주성분 분석을 이용한 알고리즘이다. 허프 변환 알고리즘은 변환 영역에서 최대 빈도를 갖는 직선을 선택하였다. 두 허프변환 알고리즘은 거의 성능 차이가 없으나 PCA는 허프변환 알고리즘의 평균 오차를 17%~81%를 줄여주고 있다.
평균 오차(˚)Table. 1 Average error(˚)
PPT Slide
Lager Image
평균 오차(˚) Table. 1 Average error(˚)
그림 6 은 길이 59인 직선에서 직선 기울기에 따른 오차를 보여주고 있다. 허프변환 알고리즘에서 직선 기울기 45도 전후에서 2도의 검출 오차가 발생하는데 이는 기울기 43도와 47도인 직선 영상이 기울기 45도인 직선 영상에 몇 화소가 추가되어 생성되면서 기울기 45도인 직선으로 검출되어 발생한다. 그러나 PCA는 수평 직선과 수직 직선의 전후 기울기에서만 0.8도의 검출 오차를 갖고 나머지 기울기에서 0.2도 이하의 작은 검출 오차를 갖는다. 직선 길이를 증가시키면서 실험을 재수행한 결과 허프변환 알고리즘은 직선 길이가 118이상에서 정확한 직선을 검출하였는데 PCA는 65이상에서 정확한 직선을 검출하였다. 여기서 정확한 직선 검출은 모든 직선의 검출 오차가 0.5도 이하인 경우이다.
PPT Slide
Lager Image
직선 검출 오차 (l = 59) Fig. 6 Line detection error (l = 59)
표 2 는 최적으로 생성된 직선 영상에서 주성분 분석으로 검출된 직선의 한 특징인 고유값 λ 1 의 최대와 평균을 보여주고 있다. 이상적 직선에서 λ 1 은 직선 길이에 의존적이지만 0.2미만이다. 이는 주성분 분석에 의해 검출된 직선의 유효성을 판단하는 근거가 될 수 있다.
평균 고유값 λ1Table. 2 Average eigen value λ1
PPT Slide
Lager Image
평균 고유값 λ1 Table. 2 Average eigen value λ1
그림 7 l = 59, θ = 44로 생성된 직선을 대상으로 검출된 직선 예이다. 허프변환의 경우 허프공간에서 발생 빈도수가 직선 길이의 1/2이상인 모든 직선들을 출력하였다. 그래서 HT_0.5에서 두 직선이 검출되었다.
PPT Slide
Lager Image
생성된 직선에서 검출된 직선들 Fig. 7 Lines detected from a generated line
검출된 직선 기울기는 각각 (45.0, 42.5), (45), (44.0369)로 PCA가 가장 우수하다.
그림 8 은 임의 직선들에서 직선 검출 성능을 비교하고 있다. (a)는 최대 2×2 화소로 구성된 곧지 않은 직선을, (b)는 최대 4×4로 구성된 곧지 않은 굵은 직선을, (c)는 잡음이 낀 곧은 직선을, (d)는 엇갈린 두 직선을 포함하는 영상이다. HT_0.5는 불필요하게 많은 직선을 검출하여 유효 직선을 선택하는 과정이 필요하다. HT_1.0은 유효 직선을 잘 검출하나 굵은 직선에서 불필요하게 많은 직선을 검출하고 있다. PCA는 앞의 실험에서 보여준 것처럼 정확한 직선을 검출하나 (c)와 (d)같이 잡음이나 다수의 직선이 있는 경우 영향을 받고 있다.
PPT Slide
Lager Image
임의 직선들에서 검출된 직선들 Fig. 8 Lines detected from any lines
주성분 분석을 이용한 알고리즘의 문제를 보완하기 위해 두 가지 기능이 추가된 개선된 알고리즘을 그림 9 에 보여주고 있다. 첫 번째 기능은 잡음의 영향을 제거하기 위한 것으로 직선 검출 후 고유값 λ 1 가 일정 크기(TH R ) 이상이면 순수한 직선이 아니라 판단하고 검출된 직선에 일정 거리 (TH D ) 이하인 유효 직선 화소만을 선택해 직선을 다시 검출하는 기능이다. 두 번째 기능은 다수의 직선들이 존재하는 경우에 개선하기 위한 것으로 영상을 겹치지 않는 블록으로 나누어 각 블록에서 직선을 검출하고 검출된 직선들에서 유사 직선을 묶어 후보 직선을 결정하고, 각 후보 직선에 대해 인접 화소를 선택하고 그 화소들에서 다시 직선을 검출한다.
PPT Slide
Lager Image
개선된 알고리즘
그림 10 11 은 개선된 알고리즘으로 검출된 직선이다. 그림 10 은 기능 1을 이용해 그림 8 (c)의 잡음을 제거해 완벽한 직선을 검출하는 것을 보여주고 있다. 그림 11 은 겹치지 않는 블록들로 나누어진 블록 영상과 기능 2를 이용해 검출된 후보 직선의 주변 화소들과 그들에 의해 정확하게 검출된 직선을 보여주고 있다. 그러나 제안된 개선 알고리즘을 위해서는 영상이 일정 크기 이상의 블록들로 나눌 수 있어야 되고 블록은 적은 잡음과 적은 직선의 다소 정제된 직선을 갖고 있어야 한다. 본 논문에서 유효 직선 화소들을 구분하기 위해 TH R 와 TH D 는 각각 2와 3을 사용하였다.
PPT Slide
Lager Image
그림 8(c)에서 검출된 직선 Fig. 10 Line detected from Fig. 8(c)
PPT Slide
Lager Image
그림 8(d)에서 검출된 직선들 Fig. 11 Lines detected from Fig. 8(d)
표 3 은 알고리즘간 계산량을 비교하고 있다. 직접적인 비교는 어렵지만 기존 알고리즘과 비교해 제안된 알고리즘에 블록 단위의 추가 계산량이 있지만 n 화소에 공통적으로 적용되는 계산량은 거의 무시되어 전체적인 계산량은 감소할 것이다. 표에서 tr ( C )과 det( C )는 각각 공분산 행렬 C의 trace와 determinant이다.
계산량 비교Table. 3 Computation comparison
PPT Slide
Lager Image
계산량 비교 Table. 3 Computation comparison
Ⅵ. 결 론
본 논문은 주성분 분석을 이용한 직선 검출 알고리즘을 분석하고 단순 알고리즘의 한계를 보완한 개선된 알고리즘을 제안한다. 제안된 알고리즘은 검출된 이상적이지 않은 직선에 대해 직선과 무관한 잡음성 화소를 제거하여 보다 정확한 직선을 검출하고, 다수의 직선을 포함하는 경우를 위해 영상을 겹치지 않는 블록들로 나누고 각 블록에서 검출된 직선들에서 후보 직선들 선택하고 각 후보 직선의 주변 화소들을 이용해 유효 직선을 검출하는 것이다. 제안된 알고리즘은 많은 잡음과 다수의 직선을 포함하는 복잡한 직선 영상에 적용하는 것은 한계가 있다. 이상적인 직선에 대해서는 적은 계산량으로 평균 검출 오차를 17%~81%를 줄이는 매우 정확한 직선검출을 수행하고 있고, 추가 기능은 다소 잡음이 있고 복수의 직선이 있는 영상에서 발생하는 문제를 해결하고 있다. 따라서 제안된 알고리즘은 다소 정제된 직선 영상에서 기존 알고리즘과 비교해 적은 계산량으로 직선을 매우 정확하게 검출할 수 있다.
BIO
오정수(Jeong-su Oh)
중앙대학교 대학원 전자공학과 공학석사
중앙대학교 첨단영상대학원 영상공학과 공학박사
현재 부경대학교 융합디스플레이공학과
※관심분야 : 디지털영상처리, 비디오영상처리, 적외선 신호처리
References
Gonzalez R. C. , Wood R. E. 2008 Digital Image Processing Prentice Hall
McAndrew A. 2004 Introduction to Digital Image Processing with MATLAB Course Technology
Hardzeyeu V. , Klefenz F. “On using the hough transform for driving assistance applications,” in Proc. 4th Int. Conf. Intell. Comput. Commun. Process. 2008 91 - 98
Duda R. O. , Hart P. E. 1972 "Use of the Hough transformation to detect lines and curves in pictures," Communications of the ACM 15 (1) 11 - 15    DOI : 10.1145/361237.361242
Guo S. , Pridmore T. , Kong Y. , Zhang X. 2009 “An improved Hough transform voting scheme utilizing surround suppression,” Pattern Recognition Letters 30 (13) 1241 - 1252    DOI : 10.1016/j.patrec.2009.05.003
Smith L. 2002 A Tutorial on Principal Components Analysis www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf
Shlens J. 2005 A tutorial on principal component analysis www.cs.cmu.edu/~elaw/papers/pca.pdf
Oh Ilsuk 2008 Pattern Recognition Kyobo Book
Han Hakyong 2009 Introduce to Pattern Recognition Hanbit Media