Advanced
An Improved Hough Transform Using Valid Features
An Improved Hough Transform Using Valid Features
Journal of the Korea Institute of Information and Communication Engineering. 2014. Sep, 18(9): 2203-2208
Copyright © 2014, The Korea 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 : May 16, 2014
  • Accepted : June 23, 2014
  • Published : September 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
정수 오
ojs@pknu.ac.kr

Abstract
영상 내 직선을 검출하는 대표적인 알고리즘인 허프변환은 실세계 영상들에 적용할 때 그들의 복잡한 배경이나 잡음에 의해 생성되는 방대한 특징점들 때문에 상당한 계산량을 필요로 하고 쉽게 의사 직선을 검출한다. 본 논문은 기존 허프변환에 특징점의 유효성을 평가하는 전처리를 추가한 개선된 허프변환을 제안한다. 특징점 평가는 3×3블록 특징점들의 패턴을 이용해 직선 검출에 필수적이지 않은 많은 특징점들을 제거할 수 있다. 다양한 영상을 대상으로 한 실험들에서 제안된 알고리즘은 영상에 따라 특징점들의 14%~58%를 제거하여 계산량을 줄여줄 뿐만 아니라 유효 직선 검출에서도 기존 알고리즘보다 우수함을 보여준다.
Keywords
Ⅰ. 서 론
영상 내에 존재하는 직선은 영역이나 물체를 구분하는 중요한 정보로 영상분석, 컴퓨터 비젼 등 영상처리의 전 영역에서 활용되고 있고, 부품 검사기를 위한 부품 영역 검출, 도로 영상의 차선 검출 등은 직선을 정보로 활용한 대표적인 예이다 [1 - 3] . 허프변환 (hough transform)은 영상 내 직선을 추출하기 위해 사용되는 대표적인 알고리즘으로 에지로 구성된 특징점 영상을 대상으로 수행된다. 허프변환은 에지로 표현된 x y 공간의 각 특징점에서 발생 가능한 모든 직선의 매개변수들을 매개변수 공간인 ρ θ 공간으로 대응시켜 매개변수의 발생 빈도를 기록한다 [4] . 일정 빈도 이상 발생하는 매개변수에 의해 의미있는 직선이 검출된다. 허프변환은 직선 형태의 특징점들만 생성하는 단순한 영상들에서는 이상적인 알고리즘이다. 그러나 실세계의 영상들은 복잡한 배경이나 잡음을 쉽게 포함하고 있고 이들은 직선뿐만 아니라 불규칙한 특징점들을 지나치게 많이 생성한다. 수많은 불규칙한 특징점들은 허프변환의 계산량을 크게 증가시키고 직선이 아닌 의사직선 (pseudo-line)을 쉽게 생성하는 문제를 갖는다 [5 , 6] .
허프변환이 갖는 문제를 해결하기 위해 변형된 형태의 허프변환들이 연구되어 왔다 [6 - 9] . 그러나 이들은 문제 발생의 원인인 직선 검출에 불필요한 특징점들에 대한 고려 없이 개선된 허프변환들이다. 본 논문은 기존 알고리즘과 달리 허프변환의 근본 문제인 직선 검출에 불필요한 특징점들을 제거하는 것을 목적으로 특징점의 유효성을 평가하는 전처리을 추가한 개선된 허프변환을 제안하고 있다. 제안된 특징점 평가는 직선 형태의 유효 특징점들이 일정한 방향성을 갖고 길게 이어지는 것과 달리 복잡한 배경과 잡음에 의해 생성된 불필요한 특징점들은 방향성이 수시로 변하는 곡선 형태로 짧게 이어지는 형태적인 차이를 이용한다. 특징점 평가는 기존 알고리즘에서 검출된 특징점들을 대상으로 3×3 주변 블록 특징점들의 패턴을 이용해 에지 방향성이 다르고, 연속성이 떨어지는 특징점들을 제거하고 있다. 또한 제안된 특징점 평가는 기존 알고리즘들의 전처리로 활용할 수 있다.
복잡한 배경과 잡음을 포함하는 다양한 영상을 대상으로 한 실험들에서 제안된 알고리즘의 특징점 평가는 직선 검출에 필수적이지 않은 많은 특징점들을 제거해 기존 알고리즘과 비교해 계산량을 크게 줄여주는 것은 물론 유효 직선 검출에서도 우수함을 보일 것이다.
Ⅱ. 허프변환
- 2.1. 허프변환
허프변환은 영상 내 직선을 식별하기 위해 사용되는 알고리즘으로 직선 정보를 포함하고 있는 에지를 특징점으로 한 영상을 대상으로 수행된다. 특징점들로 표현되는 직선은 식 (1)과 같이 극 좌표계를 사용하여 표현할 수 있다.
PPT Slide
Lager Image
여기서 ρ θ 그림 1 에 보여주는 것처럼 각각 원점 O 와 직선 l 사이의 거리와 수직선과 y 축 사이의 각이다. 식 (1)을 이용한 허프변환은 특징점 p ( x , y ) 를 지나는 모든 직선에 대해 즉, 특징점에서 θ 를 변화시켜 생기는 모든 직선에 대해 ρ 를 계산하여 매개변수 공간인 ρ θ 공간의 요소에 대응시켜 대응 횟수를 기록하는 보팅을 수행한다. 그 결과 그림처럼 x y 공간의 한 점 p ( x , y )는 ρ θ 공간에 곡선으로 그려지고, 직선 l 위의 점들은 ρ θ 공간의 한 점 ( ρl, θl )에서 겹친다. n 개의 특징점들로 구성된 직선은 ρ θ 공간의 한 점에 n번의 보팅이 이루어진다. 실제로는 직선과 관련이 없는 특징점들이 직선의 연장선에 위치하여 보팅이 추가되기도 한다. 의미 있는 직선들은 일정 보팅 이상을 갖는 ( ρ , θ )들을 선택함으로 검출된다.
PPT Slide
Lager Image
허프변환 Fig. 1 Hough transform
- 2.2. 허프변환의 문제점
허프변환은 단순히 직선으로만 특징점들을 생성하는 영상에서 이상적 알고리즘이지만 실세계 영상처럼 복잡한 배경이나 잡음에 의해 지나치게 많은 특징점들을 생성하는 영상에서는 문제를 갖고 있다. 첫 번째 문제는 특징점 개수의 증가에 의해 계산량이 크게 증가하는 것이다. 허프변환은 모든 특징점들에서 발생하는 모든 직선들을 고려해야 하는데 이는 모든 특징점들에서 사전에 정의된 모든 θ 들에 대해 식 (1)을 수행함을 의미한다. 따라서 한 영상에서 식 (1)의 사용한 횟수 (NgenL)는 식 (2)과 같다.
PPT Slide
Lager Image
여기서 Nf 은 영상에서 특징점 개수이고, θ min , θ max , 는 각각 θ 로 고려된 최소, 최대, 변화량으로 본 연구에서는 0[°], 180[°], 1[°]를 사용한다. 따라서 한 특징점이 증가하면 식 (1)의 사용 횟수가 180 증가한다. 식 (2)에서 각에 대한 변수는 실험에 앞서 적절하게 고정되나 Nf 은 입력 영상의 내용이나 특징점 생성 방법에 의해 결정된다. 특징점 증가는 실시간 영상처리에 허프변환의 적용을 어렵게 한다. 그림 2 는 126×126인 영상에서 상황에 따라 검출된 특징점들을 보여주고 있다. 괄호안의 수는 특징점의 개수이다. 같은 영상에 대해 소벨 마스크 (Sobel mask)를 사용하는 경우 캐니 에지(Canny edge)를 사용하는 것보다 2.5배 이상의 계산 횟수가 필요하다. 잡음은 원영상에 인위적으로 잡음을 더한 영상에서 검출된 특징점들로 캐니 에지 보다 12배 정도 더 많은 계산 횟수가 필요하다. 복잡한 배경을 갖는 영상에서도 잡음 영상의 특징점들과 같은 모습을 보여준다.
PPT Slide
Lager Image
특징점 영상들 Fig. 2 Feature images
두 번째 문제는 수많은 특징점들에 의해 우연히 많은 특징점들이 한 직선 상에 위치하여 의사직선을 생성하는 것이다. 그림 3 은 복잡한 배경과 잡음이 있는 영상에서 실제 직선보다 많은 보팅을 갖는 의사직선을 보여주고 있다. 첫 번째 영상은 도로 영상으로 나무와 인도의 복잡한 배경에 의해 생성된 특징점들에 의해 5 번째로 검출된 의사직선이고, 두 번째 영상은 잡음에 의해 2 번째로 검출된 의사직선이다.
PPT Slide
Lager Image
의사 직선들 Fig. 3 Pseudo-lines
Ⅲ. 제안된 허프변환
그림 3 에 보이는 것처럼 복잡한 배경이나 잡음에 의해 생성된 특징점들은 직선과 달리 같은 방향으로 이어지는 특징점들의 연속성이 짧고 수시로 방향이 변하는 굴곡점이 많이 가지고 있다. 연속성이 떨어지는 특징점과 주변 특징점과 다른 에지 방향을 갖는 특징점들은 직선 검출에 큰 영향을 주지 않는다. 이런 불필요한 특징점들을 제거하는 특징점 평가가 추가된 제안된 알고리즘이 그림 4 에 보여주고 있다.
PPT Slide
Lager Image
제안된 알고리즘 Fig. 4 Proposed algorithm
Feature Image는 기존 알고리즘의 특징점 영상으로 주로 사용되는 캐니 에지 검출기의 결과 영상이다. Ang( x , y )는 ( x , y )에서 에지의 기울기로 x y 방향의 그래디언트( gX , gY )를 사용하여 식 (3)로 계산된다.
PPT Slide
Lager Image
N_F( x , y )는 ( x , y ) 주변 3×3 블록 내의 특징점의 개수이다. Feature Estimation에서 N_F에 따라 현 특징점의 유효성을 그림 5 와 같이 무효 패턴을 이용해 평가한다. N_F가 1인 경우는 고립된 특징점이고, 2인 경우는 직선 혹은 의미 없는 곡선의 끝으로 직선 검출에 중요하지 않다. N_F가 6~9인 경우는 캐니 에지 검출기를 사용하여 드물게 나타나는 경우로 선들이 겹치는 영역으로 역시 직선 검출에 중요하지 않다. N_F가 3~5인 경우가 주로 직선을 구성하는데 그림에서는 직선이 아닌 패턴을 보여주고 있다. N_F가 3인 경우는 그림의 예와 같이 외곽의 2 특징점들이 연속하거나 한 화소 건너는 형태의 모든 패턴들과 N_F가 4인 경우는 외곽의 3 특징점들이 연속하는 모든 패턴들은 연속성이 떨어져 직선 검출에 중요하지 않다. N_F가 5인 경우는 모두 직선 혹은 곡선을 구성해 모두 유효 특징점으로 고려되지만 곡선은 불필요하므로 첫 번째 유효 특징점 평가 단계에서 주변 특징점들이 관심 특징점과 20[°] 이하의 유사 에지 방향을 가질 때만 주변 특징점으로 사용한다.
PPT Slide
Lager Image
패턴을 이용한 특징점 평가 Fig. 5 Feature estimation using pattern
Feature Estimation는 직선 검출에 영향이 적은 직선의 끝과 곡선의 굴곡점을 화소 단위로 제거하기 때문에 효율성을 높이기 위해서는 반복적인 수행이 필요하다. 그러나 반복 횟수가 많아지면 직선도 작아지므로 제한적으로 사용할 필요가 있다. 본 논문에서는 2회만 수행하고 있다. 그림 6 그림 2 의 잡음 특징점에 제안된 유효 특징점 평가를 수행한 결과를 보여주고 있다. 첫 번째 그림은 원 특징점들에서 제거된 특징점들을 밝게 보여주고 있고, 두 번째 그림은 유효 특징점들만 보여주고 있다. 직선을 유지하면서도 잡음에 의한 불필요한 특징점들을 많이 제거하고 있다. 기존 특징점들의 45%에서만 허프변환이 이루어진다.
PPT Slide
Lager Image
유효 특징점 Fig. 6 Valid feature
Ⅳ. 실험 결과
성능 평가를 위해 제안된 알고리즘 (PRO)은 그림 7 과 같이 복잡한 배경과 잡음을 포함하는 다양한 영상들에 적용되어 기존 알고리즘 (CONV)과 비교하고 있다. 영상 #4는 비교적 덜 복잡하고 잡음이 없는 영상이고 영상 #8은 인위적으로 생성된 잡음이 많은 영상이다. 영상 #7과 #9은 같은 영상인데 특징점 검출 조건이 다르다.
PPT Slide
Lager Image
실험 영상들 Fig. 7 Experiment images
그림 8 은 제안된 유효 특징점 검출의 영향을 비교하고 있다. #7은 다른 영상과 같은 조건으로 특징점을 검출하여 수많은 특징점들이 검출되었고 #9은 많은 시행착오를 거쳐 최적의 특징점들을 검출하였다. 최적 조건의 특징점들은 직선 검출이 용이하나 최적 조건이 영상의 해상도나 내용에 따라 다르기 때문에 실시간 영상 처리에 적용하는 것은 불가능하다.
PPT Slide
Lager Image
검출된 특징점 영상들 Fig. 8 Detected feature images
표 1 은 특징점 개수의 비를 비교하고 있다. PRO_1과 PRO_2는 각각 제안된 알고리즘에서 1회와 2회의 유효 특징점 평가를 수행할 때의 결과이고 허프변환은 PRO_2에서 이루어진다. 비교적 직선만 잘 검출된 깨끗한 영상 #4와 #9은 14%와 20% 정도만 줄었지만 나머지 영상은 최소 32%에서 최대 58%를 줄여주고 있다.
특징점 개수의 비율Table. 1Rate of the number of features
PPT Slide
Lager Image
특징점 개수의 비율 Table. 1 Rate of the number of features
그림 8 표 1 은 어떤 특징점 영상에서든 특징점 평가는 비록 직선 검출에 영향을 주지 않을 정도의 직선 끊김이 있지만 불필요한 특징점들을 크게 줄이는 것을 보여주고 있다.
표 2 그림 9 10 은 영상마다 20개 직선을 검출한 결과를 비교하고 있다. 보팅이 많은 직선을 우선 검출하고 검출된 직선에 인접한 직선은 무시하였다. 표 2 는 두 알고리즘이 공통적으로 검출한 직선과 그렇지 않은 직선을 구분하여 검출된 직선의 유효성을 비교하고 있다. 직선만 잘 검출된 영상 #4와 #9는 공통 검출 직선이 많으면서 오류가 적다. 복잡한 배경이나 잡음이 많은 영상에서는 비공통 검출 직선이 많고 검출된 직선도 오류가 많다. 영상 #1을 제외하고 모든 영상에서 제안된 알고리즘이 동등하거나 오류가 적다.
검출된 직선의 평가Table. 2Estimation of the detected lines
PPT Slide
Lager Image
검출된 직선의 평가 Table. 2 Estimation of the detected lines
PPT Slide
Lager Image
각 순위에서 유효 직선의 비율 Fig. 9 Ratio of valid lines at each ranking
PPT Slide
Lager Image
영상 #7에서 검출된 직선들 Fig. 10 Detected lines on the image #7
그림 9 는 직선 검출 순위별 유효 검출율을 보여주고 있다. 상위 순위에 검출된 직선일수록 유효 검출율이 높은 것은 열악한 환경에서도 보팅의 문턱치를 잘 조절하면 의미있는 직선만을 잘 검출할 수 있음 보여주는 것이고 전 영역에서 기존 알고리즘과 비교해 제안된 알고리즘의 유효 검출율이 높은 것을 보여주고 있다.
그림 10 그림 8 에 보여준 영상 #7의 특징점을 이용해 검출된 15개의 직선을 보여주고 있다. 잘못된 특징점들에 의해 생성된 직선을 보여주기 위해 떨어진 직선 요소를 이어주기 때문에 실제 직선보다 길게 보여주고 있다. 직선에 붙은 수는 검출 순위이고 실선은 적절하게 검출된 직선이고 점선은 잘못 검출된 직선이다. 그림 8 에 보인 건물 벽의 적절하지 못한 많은 특징점들에 의해 검출 오류가 기존 알고리즘에서는 7개 발생하지만 제안된 알고리즘에서는 3개만 발생한다.
Ⅴ. 결 론
영상 내 직선을 검출하는 대표적이 알고리즘인 허프변환은 직선 형태의 특징점들만 생성하는 영상들에서는 이상적으로 동작하지만 실세계 영상처럼 복잡한 배경이나 잡음을 포함한 영상에서는 큰 계산량이 요구되고 의사직선이 쉽게 검출된다. 제안된 허프변환의 특징점 유효성 평가는 3×3 주변 블록에서 연속성이 떨어지고 에지 방향이 다른 불필요한 특징점들을 제거하여 기존 허프변환을 개선하였다. 제안된 알고리즘은 전처리 과정이 추가되었지만 다양한 영상을 대상으로 한 실험들에서 많은 불필요한 특징점들을 제거하여 계산량 측면에서는 직선 특징점들을 잘 검출하는 영상에서는 약 20%, 복잡하고 잡음이 있는 영상에서는 최대 60%까지 줄여주고 있다. 그리고 직선 검출 성능 면에서는 기존 허프변환과 비교하여 유효 직선이 상위 순위에 더 많이 위치하고 모든 순위에서 유효 직선이 더 많이 검출되고 있다.
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. 2008 “On using the hough transform for driving assistance applications,” in Proc. 4th Int. Conf. Intell. Comput. Commun. Process. 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
Yang M.C. , Lee J.S. , Lien C.C. , Huang C.L. 1997 “Hough transform modified by line connectivity and line thickness,” IEEE Transactions on PAMI 19 (8) 905 - 910    DOI : 10.1109/34.608293
Kim Jeongtea 2007 “A Novel Line Detection Method Using Gradient Direction Based Hough Transform,” The Transaction of The Koean Institute of Electrical Engineers 56 (1) 197 - 205
O’Gorman F. , Clowes M.B. 1976 “Finding picture edges through collinearity of feature points IEEE Trans. Comput. 25 (4) 449 - 456
Atiquuaman M. 1992 "Multiresolution Hough Transform-An Ef ficient Method of Detecting Patterns in Images." IEEE Transactions on PAMI 14 (11)
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