This paper analyzes the straight line detection using the principal component analysis (PCA) and proposes its improved algorithm to which two new functions are added. The first function removes invalid pixels through the detected straight line and detects a line again. The second function detects lines from non-overlapped blocks, selects valid line candidates, and detects a valid line from pixels adjacent to each line candidate. The proposed algorithm detects a more accurate straight line with a low computation in comparison with the conventional algorithm in an image with somewhat refined lines.
직선 검출은 영역 분할을 필요로 하는 디지털 영상처리 영역에서 필수적인 기술이다. 자동 부품 검사기를 위한 부품 영역 검출, 도로 영상의 차선 검출, 3차원 영상 분석을 위한 소실점 검출 등이 직선 검출이 사용되는 예들이다[1-4]. 직선 검출을 위해 가장 보편적으로 사용되는 허프변환(hough transform)은 에지 화소들에서 발생 가능한 모든 직선들의 매개변수들을 매개변수 공간으로 대응시켜 보팅(voting)하는 알고리즘으로 계산적 부담이 있고 정밀한 직선 검출이 어렵다[3-5].
본 논문은 주성분 분석(PCA)을 이용한 직선 검출 알고리즘을 제안한다. 주성분 분석[6-9]은 다차원 데이터 집합에서 데이터간 분산을 최대로 하는 새로운 주성분들을 찾는 알고리즘으로 영상처리 영역에서 자주 사용되고 있다. 직선은 일렬로 모여 있는 데이터들의 집합이므로 특정 방향에 대해 매우 큰 분산을 갖고, 직교 방향에 대해 매우 작은 분산을 갖는다. 따라서 제안된 알고리즘은 에지 화소들을 데이터 집합으로 한 주성분 분석에서 최대 고유값 (eigen value)을 갖는 주성분의 고유 벡터 (eigen vector)로부터 직선 기울기를 구하고 다른 성분의 고유값으로 직선의 신뢰성을 평가하여 직선을 검출한다. 그리나 제안된 알고리즘은 잡음이나 다수의 직선을 포함하는 영상에서 잘못된 직선을 검출할 수 있다. 이를 보완하기 위해 유효 직선 화소만으로 직선 검출을 수행하는 알고리즘과 영상을 블록으로 나누어 먼저 직선 후보를 검출하고 이들을 근거로 유효 직선을 검출하는 개선된 알고리즘도 제안하고 있다.
제안된 알고리즘을 평가하기 위해 먼저 직선 생성 방법을 제시하여 분석하고, 생성된 직선과 임의의 직선에서 기존 알고리즘과 제안된 알고리즘으로 직선 검출하여 성능을 분석한다. 제안된 알고리즘은 다소 정제된 직선을 포함하는 영상에서는 적은 계산으로도 보다 정확한 직선을 검출할 수 있는 것을 보여줄 것이다.
주성분 분석은 다차원 데이터 집합을 최대 제곱 오차 관점에서 데이터 정보를 더 잘 나타낼 수 있는 주성분들의 데이터 집합으로 변환하는 기법이다[6-9]. 예를 들어 그림 1과 같이 데이터 집합 A가 주어질 때 xy 공간에 표현된 데이터 집합을 E1E2 공간으로 변환하면 E2 축의 분산을 최대화하여 데이터들 더 잘 표현할 수 있다. 또한 모든 데이터가 E2 축 위에 투영되어 서로 겹치지 않으면 E1 축을 줄일 수 있다. 따라서 주성분 분석에 의해 찾은 E1E2 공간은 데이터 집합의 정보를 잘 나타낼 수 있을 뿐만 아니라 일부 주성분들만 유지시켜 저차원 데이터 집합으로 변환할 수 있다. 주성분의 비교, 축소 등은 영상 인식, 압축, 잡음 제거 등 영상처리 영역에서 활용되고 있다. 또한 주성분 E2를 활용하여 직선 근사 알고리즘으로도 사용되고 있다.
영상은 격자 모양의 작은 화소들로 구성되어 있어 직선을 실제 모습 그대로 표현할 수 없다. 그래서 효율적인 직선 검출을 위해 영상에서 직선 표현에 대한 분석은 필요하다. 직선 표현 능력을 분석하기 위해 그림 2와 같이 주어진 한 화소 굵기의 수평 직선을 직선 중심을 축으로 회전하여 다양한 직선들을 생성하고 있다. 여기서
회전은 직선을 구성하는 화소를 개별적으로 회전하는 방식(PR)과 영상 자체를 회전하는 방식(IR)을 사용하여 비교한다. 격자 형태의 화소로 이루어진 직선은 그림 2에서 1도 간격으로 회전시킬 때 변화가 없을 수 있다. 그림 3은 주어진 직선을 180회 회전시킬 때 생성되는 서로 다른 직선의 수를 보여주고 있다. 직선 길이가 짧을수록 서로 다른 직선의 수가 적고, 직선 길이가 59 화소 이상이 되어야 180개의 서로 다른 직선을 만들어 낸다. 그리고 PR과 IR을 비교할 때 직선 길이가 33 화소이상에서는 같은 성능을 보이지만 33 화소보다 작을 때 IR이 더 많은 직선을 생성하고 있다. 이는 PR은 화소단위로 일대일 회전 이동하는 반면 IR은 회전된 화소가 화소들 사이에 이동할 때 화소 수를 증가시켜 더 다양하게 표현하기 때문이다. 이후 실험은 IR 회전을 사용한다.
그림 4는 일부 직선에 대해 기울기를 변화시킬 때 직선이 유지하는 수(NofUL)를 보여주고 있다. 예를 들어 직선 길이 7인 2점 쇄선의 경우 81~99도의 19개 직선 기울기에 대해 같은 직선으로 표현되어 그들의 NofUL이 19인 것을 보여주고 있다. 이는 하나의 작은 직선이 19 개의 다른 직선이 될 수 있음 나타내기도 한다. 또한 최대 NofUL는 수직 직선과 수평 직선에서 발생하고 다음 크기의 NofUL는 70/110도와 45/135도 주변에서 발생하고 있는 것을 보여주고 있고, 이들에서 검출되는 직선은 신뢰도가 떨어질 수 있음을 나타낸다. 그림 4에서 직선 길이가 길수록 NofUL가 작아지다 59 이상에서 NofUL가 1로 모든 기울기에서 다른 직선을 생성하고 있는 것을 보여주고 있다. 따라서 직선 길이와 검출된 기울기를 통해 실제 직선을 예상할 수 있다.
주성분들은 데이터 집합의 공분산 (covariance) 행렬로부터 계산된 고유값 (eigen value)과 고유벡터 (eigen vector)에서 얻을 수 있다. 여기서 고유값과 고유벡터는 각각 주성분들의 중요도(분산)와 방향을 나타낸다. 2차원 공간 특징인 에지 화소를 데이터 집합으로 직선을 검출하고 있으므로 데이터 집합은 2차원이고, 이들의 고유값 (Evalue)과 고유벡터 (Evector)는 식 (1)과 같이 표현할 수 있다.
여기서 최대 고유값이 λ2이면 고유벡터 E2가 최대 주성분으로 직선의 방향 벡터가 되고, λ1는 E1에 대한 분산으로 직선의 굵기를 나타낸다. 이때 직선의 기울기
성능 평가를 위해 그림 2에서 생성된 직선들에 대해 허프변환 알고리즘과 제안된 알고리즘을 이용해 직선 검출을 수행하고 결과를 비교하였다. 그림 5는 주어진 직선에서 기울기가 1~180도인 입력 직선에 대해 출력되어야 할 최적의 직선 기울기를 보여주고 있다.
표 1은 주어진 직선에서 기울기가 1~180도인 직선들에 대해 검출된 직선 기울기와 최적의 직선 기울기의 평균 오차를 보여주고 있다. HT_1.0과 HT_0.5는 각각 1과 0.5도의 기울기 검출 해상도인 허프변환 알고리즘이고 PCA는 주성분 분석을 이용한 알고리즘이다. 허프 변환 알고리즘은 변환 영역에서 최대 빈도를 갖는 직선을 선택하였다. 두 허프변환 알고리즘은 거의 성능 차이가 없으나 PCA는 허프변환 알고리즘의 평균 오차를 17%~81%를 줄여주고 있다.
평균 오차(˚)
그림 6은 길이 59인 직선에서 직선 기울기에 따른 오차를 보여주고 있다. 허프변환 알고리즘에서 직선 기울기 45도 전후에서 2도의 검출 오차가 발생하는데 이는 기울기 43도와 47도인 직선 영상이 기울기 45도인 직선 영상에 몇 화소가 추가되어 생성되면서 기울기 45도인 직선으로 검출되어 발생한다. 그러나 PCA는 수평 직선과 수직 직선의 전후 기울기에서만 0.8도의 검출 오차를 갖고 나머지 기울기에서 0.2도 이하의 작은 검출 오차를 갖는다. 직선 길이를 증가시키면서 실험을 재수행한 결과 허프변환 알고리즘은 직선 길이가 118이상에서 정확한 직선을 검출하였는데 PCA는 65이상에서 정확한 직선을 검출하였다. 여기서 정확한 직선 검출은 모든 직선의 검출 오차가 0.5도 이하인 경우이다.
표 2는 최적으로 생성된 직선 영상에서 주성분 분석으로 검출된 직선의 한 특징인 고유값 λ1의 최대와 평균을 보여주고 있다. 이상적 직선에서 λ1은 직선 길이에 의존적이지만 0.2미만이다. 이는 주성분 분석에 의해 검출된 직선의 유효성을 판단하는 근거가 될 수 있다.
평균 고유값 λ1
그림 7는
검출된 직선 기울기는 각각 (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)같이 잡음이나 다수의 직선이 있는 경우 영향을 받고 있다.
주성분 분석을 이용한 알고리즘의 문제를 보완하기 위해 두 가지 기능이 추가된 개선된 알고리즘을 그림 9에 보여주고 있다. 첫 번째 기능은 잡음의 영향을 제거하기 위한 것으로 직선 검출 후 고유값 λ1가 일정 크기(THR) 이상이면 순수한 직선이 아니라 판단하고 검출된 직선에 일정 거리 (THD) 이하인 유효 직선 화소만을 선택해 직선을 다시 검출하는 기능이다. 두 번째 기능은 다수의 직선들이 존재하는 경우에 개선하기 위한 것으로 영상을 겹치지 않는 블록으로 나누어 각 블록에서 직선을 검출하고 검출된 직선들에서 유사 직선을 묶어 후보 직선을 결정하고, 각 후보 직선에 대해 인접 화소를 선택하고 그 화소들에서 다시 직선을 검출한다.
그림 10과 11은 개선된 알고리즘으로 검출된 직선이다. 그림 10은 기능 1을 이용해 그림 8(c)의 잡음을 제거해 완벽한 직선을 검출하는 것을 보여주고 있다. 그림 11은 겹치지 않는 블록들로 나누어진 블록 영상과 기능 2를 이용해 검출된 후보 직선의 주변 화소들과 그들에 의해 정확하게 검출된 직선을 보여주고 있다. 그러나 제안된 개선 알고리즘을 위해서는 영상이 일정 크기 이상의 블록들로 나눌 수 있어야 되고 블록은 적은 잡음과 적은 직선의 다소 정제된 직선을 갖고 있어야 한다. 본 논문에서 유효 직선 화소들을 구분하기 위해 THR와 THD는 각각 2와 3을 사용하였다.
표 3은 알고리즘간 계산량을 비교하고 있다. 직접적인 비교는 어렵지만 기존 알고리즘과 비교해 제안된 알고리즘에 블록 단위의 추가 계산량이 있지만 n 화소에 공통적으로 적용되는 계산량은 거의 무시되어 전체적인 계산량은 감소할 것이다. 표에서
계산량 비교
본 논문은 주성분 분석을 이용한 직선 검출 알고리즘을 분석하고 단순 알고리즘의 한계를 보완한 개선된 알고리즘을 제안한다. 제안된 알고리즘은 검출된 이상적이지 않은 직선에 대해 직선과 무관한 잡음성 화소를 제거하여 보다 정확한 직선을 검출하고, 다수의 직선을 포함하는 경우를 위해 영상을 겹치지 않는 블록들로 나누고 각 블록에서 검출된 직선들에서 후보 직선들 선택하고 각 후보 직선의 주변 화소들을 이용해 유효 직선을 검출하는 것이다. 제안된 알고리즘은 많은 잡음과 다수의 직선을 포함하는 복잡한 직선 영상에 적용하는 것은 한계가 있다. 이상적인 직선에 대해서는 적은 계산량으로 평균 검출 오차를 17%~81%를 줄이는 매우 정확한 직선검출을 수행하고 있고, 추가 기능은 다소 잡음이 있고 복수의 직선이 있는 영상에서 발생하는 문제를 해결하고 있다. 따라서 제안된 알고리즘은 다소 정제된 직선 영상에서 기존 알고리즘과 비교해 적은 계산량으로 직선을 매우 정확하게 검출할 수 있다.
