The Hough transform (HT), that is a typical algorithm for detecting lines in images, needs considerable computational costs and easily detects pseudo-lines on the real world images, because of the large amount of features generated by their complex background or noise. This paper proposes an improved HT that add a preprocessing to estimate the validity of features to the conventional HT. The feature estimation can remove a lot of inessential features for the line detection using a pattern of 3×3 block features. Experiments using various images show that the proposed algorithm saves computational costs by removing 14%~58% of features depending on images and besides it is superior to the conventional HT in valid line detection.
영상 내에 존재하는 직선은 영역이나 물체를 구분하는 중요한 정보로 영상분석, 컴퓨터 비젼 등 영상처리의 전 영역에서 활용되고 있고, 부품 검사기를 위한 부품 영역 검출, 도로 영상의 차선 검출 등은 직선을 정보로 활용한 대표적인 예이다[1-3]. 허프변환 (hough transform)은 영상 내 직선을 추출하기 위해 사용되는 대표적인 알고리즘으로 에지로 구성된 특징점 영상을 대상으로 수행된다. 허프변환은 에지로 표현된
허프변환이 갖는 문제를 해결하기 위해 변형된 형태의 허프변환들이 연구되어 왔다[6-9]. 그러나 이들은 문제 발생의 원인인 직선 검출에 불필요한 특징점들에 대한 고려 없이 개선된 허프변환들이다. 본 논문은 기존 알고리즘과 달리 허프변환의 근본 문제인 직선 검출에 불필요한 특징점들을 제거하는 것을 목적으로 특징점의 유효성을 평가하는 전처리을 추가한 개선된 허프변환을 제안하고 있다. 제안된 특징점 평가는 직선 형태의 유효 특징점들이 일정한 방향성을 갖고 길게 이어지는 것과 달리 복잡한 배경과 잡음에 의해 생성된 불필요한 특징점들은 방향성이 수시로 변하는 곡선 형태로 짧게 이어지는 형태적인 차이를 이용한다. 특징점 평가는 기존 알고리즘에서 검출된 특징점들을 대상으로 3×3 주변 블록 특징점들의 패턴을 이용해 에지 방향성이 다르고, 연속성이 떨어지는 특징점들을 제거하고 있다. 또한 제안된 특징점 평가는 기존 알고리즘들의 전처리로 활용할 수 있다.
복잡한 배경과 잡음을 포함하는 다양한 영상을 대상으로 한 실험들에서 제안된 알고리즘의 특징점 평가는 직선 검출에 필수적이지 않은 많은 특징점들을 제거해 기존 알고리즘과 비교해 계산량을 크게 줄여주는 것은 물론 유효 직선 검출에서도 우수함을 보일 것이다.
허프변환은 영상 내 직선을 식별하기 위해 사용되는 알고리즘으로 직선 정보를 포함하고 있는 에지를 특징점으로 한 영상을 대상으로 수행된다. 특징점들로 표현되는 직선은 식 (1)과 같이 극 좌표계를 사용하여 표현할 수 있다.
여기서
허프변환은 단순히 직선으로만 특징점들을 생성하는 영상에서 이상적 알고리즘이지만 실세계 영상처럼 복잡한 배경이나 잡음에 의해 지나치게 많은 특징점들을 생성하는 영상에서는 문제를 갖고 있다. 첫 번째 문제는 특징점 개수의 증가에 의해 계산량이 크게 증가하는 것이다. 허프변환은 모든 특징점들에서 발생하는 모든 직선들을 고려해야 하는데 이는 모든 특징점들에서 사전에 정의된 모든
여기서
두 번째 문제는 수많은 특징점들에 의해 우연히 많은 특징점들이 한 직선 상에 위치하여 의사직선을 생성하는 것이다. 그림 3은 복잡한 배경과 잡음이 있는 영상에서 실제 직선보다 많은 보팅을 갖는 의사직선을 보여주고 있다. 첫 번째 영상은 도로 영상으로 나무와 인도의 복잡한 배경에 의해 생성된 특징점들에 의해 5 번째로 검출된 의사직선이고, 두 번째 영상은 잡음에 의해 2 번째로 검출된 의사직선이다.
그림 3에 보이는 것처럼 복잡한 배경이나 잡음에 의해 생성된 특징점들은 직선과 달리 같은 방향으로 이어지는 특징점들의 연속성이 짧고 수시로 방향이 변하는 굴곡점이 많이 가지고 있다. 연속성이 떨어지는 특징점과 주변 특징점과 다른 에지 방향을 갖는 특징점들은 직선 검출에 큰 영향을 주지 않는다. 이런 불필요한 특징점들을 제거하는 특징점 평가가 추가된 제안된 알고리즘이 그림 4에 보여주고 있다.
Feature Image는 기존 알고리즘의 특징점 영상으로 주로 사용되는 캐니 에지 검출기의 결과 영상이다. Ang(
N_F(
Feature Estimation는 직선 검출에 영향이 적은 직선의 끝과 곡선의 굴곡점을 화소 단위로 제거하기 때문에 효율성을 높이기 위해서는 반복적인 수행이 필요하다. 그러나 반복 횟수가 많아지면 직선도 작아지므로 제한적으로 사용할 필요가 있다. 본 논문에서는 2회만 수행하고 있다. 그림 6은 그림 2의 잡음 특징점에 제안된 유효 특징점 평가를 수행한 결과를 보여주고 있다. 첫 번째 그림은 원 특징점들에서 제거된 특징점들을 밝게 보여주고 있고, 두 번째 그림은 유효 특징점들만 보여주고 있다. 직선을 유지하면서도 잡음에 의한 불필요한 특징점들을 많이 제거하고 있다. 기존 특징점들의 45%에서만 허프변환이 이루어진다.
성능 평가를 위해 제안된 알고리즘 (PRO)은 그림 7과 같이 복잡한 배경과 잡음을 포함하는 다양한 영상들에 적용되어 기존 알고리즘 (CONV)과 비교하고 있다. 영상 #4는 비교적 덜 복잡하고 잡음이 없는 영상이고 영상 #8은 인위적으로 생성된 잡음이 많은 영상이다. 영상 #7과 #9은 같은 영상인데 특징점 검출 조건이 다르다.
그림 8은 제안된 유효 특징점 검출의 영향을 비교하고 있다. #7은 다른 영상과 같은 조건으로 특징점을 검출하여 수많은 특징점들이 검출되었고 #9은 많은 시행착오를 거쳐 최적의 특징점들을 검출하였다. 최적 조건의 특징점들은 직선 검출이 용이하나 최적 조건이 영상의 해상도나 내용에 따라 다르기 때문에 실시간 영상 처리에 적용하는 것은 불가능하다.
표 1은 특징점 개수의 비를 비교하고 있다. PRO_1과 PRO_2는 각각 제안된 알고리즘에서 1회와 2회의 유효 특징점 평가를 수행할 때의 결과이고 허프변환은 PRO_2에서 이루어진다. 비교적 직선만 잘 검출된 깨끗한 영상 #4와 #9은 14%와 20% 정도만 줄었지만 나머지 영상은 최소 32%에서 최대 58%를 줄여주고 있다.
특징점 개수의 비율
그림 8과 표 1은 어떤 특징점 영상에서든 특징점 평가는 비록 직선 검출에 영향을 주지 않을 정도의 직선 끊김이 있지만 불필요한 특징점들을 크게 줄이는 것을 보여주고 있다.
표 2와 그림 9와 10은 영상마다 20개 직선을 검출한 결과를 비교하고 있다. 보팅이 많은 직선을 우선 검출하고 검출된 직선에 인접한 직선은 무시하였다. 표 2는 두 알고리즘이 공통적으로 검출한 직선과 그렇지 않은 직선을 구분하여 검출된 직선의 유효성을 비교하고 있다. 직선만 잘 검출된 영상 #4와 #9는 공통 검출 직선이 많으면서 오류가 적다. 복잡한 배경이나 잡음이 많은 영상에서는 비공통 검출 직선이 많고 검출된 직선도 오류가 많다. 영상 #1을 제외하고 모든 영상에서 제안된 알고리즘이 동등하거나 오류가 적다.
검출된 직선의 평가
그림 9는 직선 검출 순위별 유효 검출율을 보여주고 있다. 상위 순위에 검출된 직선일수록 유효 검출율이 높은 것은 열악한 환경에서도 보팅의 문턱치를 잘 조절하면 의미있는 직선만을 잘 검출할 수 있음 보여주는 것이고 전 영역에서 기존 알고리즘과 비교해 제안된 알고리즘의 유효 검출율이 높은 것을 보여주고 있다.
그림 10은 그림 8에 보여준 영상 #7의 특징점을 이용해 검출된 15개의 직선을 보여주고 있다. 잘못된 특징점들에 의해 생성된 직선을 보여주기 위해 떨어진 직선 요소를 이어주기 때문에 실제 직선보다 길게 보여주고 있다. 직선에 붙은 수는 검출 순위이고 실선은 적절하게 검출된 직선이고 점선은 잘못 검출된 직선이다. 그림 8에 보인 건물 벽의 적절하지 못한 많은 특징점들에 의해 검출 오류가 기존 알고리즘에서는 7개 발생하지만 제안된 알고리즘에서는 3개만 발생한다.
영상 내 직선을 검출하는 대표적이 알고리즘인 허프변환은 직선 형태의 특징점들만 생성하는 영상들에서는 이상적으로 동작하지만 실세계 영상처럼 복잡한 배경이나 잡음을 포함한 영상에서는 큰 계산량이 요구되고 의사직선이 쉽게 검출된다. 제안된 허프변환의 특징점 유효성 평가는 3×3 주변 블록에서 연속성이 떨어지고 에지 방향이 다른 불필요한 특징점들을 제거하여 기존 허프변환을 개선하였다. 제안된 알고리즘은 전처리 과정이 추가되었지만 다양한 영상을 대상으로 한 실험들에서 많은 불필요한 특징점들을 제거하여 계산량 측면에서는 직선 특징점들을 잘 검출하는 영상에서는 약 20%, 복잡하고 잡음이 있는 영상에서는 최대 60%까지 줄여주고 있다. 그리고 직선 검출 성능 면에서는 기존 허프변환과 비교하여 유효 직선이 상위 순위에 더 많이 위치하고 모든 순위에서 유효 직선이 더 많이 검출되고 있다.