1. 서 론

허프 공간(Hough space)은 영상 공간에서의 직선을 하나의 점으로 표현할 수 있는 변수 공간으로, 이러한 변환을 허프 변환(Hough Transform)이라고 한다⁽¹⁾. 허프 변환은 컴퓨터 비전, 자율주행 자동차⁽²⁾ 등 다양한 분야에서 응용되며, 효율적인 하드웨어로 설계하기 위해서는 실시간 처리 여부가 중요하다. 허프 변환은 영상의 중심부에서 직선까지의 거리 $\rho$와 x축과 이루는 각도 $\theta$를 이용하여 이차원 배열에 가중치를 저장하고 이를 바탕으로 영상에 포함된 직선을 추출한다.

표준 허프 변환(SHT, Standard Hough Transform)의 처리성능과 메모리 구조를 보완하는 다양한 알고리즘이 제안되었다⁽³⁾. Satzoda 등은 영상을 여러 계층으로 나누고 계층 간의 덧셈이 가능한 성질(additive property)을 이용하여 처리 복잡도를 낮출 수 있는 HAHT(Hierarchical Additive Hough Transform) 알고리즘을 제안하였다⁽⁴⁾. Zhe 등은 ROI 기반에서 개선된 PPHT(Progressive Probabilistic Hough Transform)을 적용하여 그림자, 반사, 조도, 차선 훼손 등 다양한 환경에서 강인한 알고리즘을 제안하였다⁽⁵⁾. Zhou 등은 영상으로부터 기울기 정보를 추출하여 직선을 검출할 수 있는 GHT(Gradient-based Hough Transform)알고리즘을 제안하여 복잡도가 개선되었다⁽⁶⁾. 또한 Karabernou 등은 기울기 기반의 알고리즘에 CORDIC 알고리즘을 적용하여 시프트 등의 단순한 연산자를 사용함으로써 처리성능을 개선하였다⁽⁶⁾.

실시간 처리가 가능한 허프 변환 시스템을 설계하기 위해서는 에지 검출, 기울기 검출 등의 영상 전처리, 해당 픽셀에 대한 가중치 연산, 보팅 메모리(voting memory) 구조 및 처리방법 등을 고려해야 한다. 지금까지 실시간 허프 변환 시스템 설계에 많은 연구가 진행되어 왔다^(6-14). 기울기 정보를 바탕으로 논문 ⁽⁵⁾에서는 성능 개선을 위하여 해당 각도를 중심으로 일정 변위만을 병렬로 처리하였고 local maxima 과정에 파이프라인을 적용하였다. Epstein 등은 n-차원 특징 공간을 2차원으로 줄이는 데 있어서 n-좌표 변환을 시스톨릭 배열을 이용하여 허프 변환 프로세서를 구현하였다⁽⁸⁾. 프로세서는 32개의 병렬 입력을 처리하며 512개의 프로그램 가능한 처리장치로 구성되며 확장이 가능하다⁽⁸⁾. Lu 등이 제안한 병렬 허프 변환(PHT) 구조에서는 다계층의 병렬 파이프라인으로 설계하였고 개선된 비최대 억제조건(non-maximum suppression condition)을 적용하여 유효한 에지만을 검출하였다⁽⁹⁾. 논문 ⁽¹⁰⁾에서는 다른 각도에 대한 직선 매개변수 계산과 누적을 병렬로 수행하는 어레이 프로세서를 제안하였다. Guan 등은 보팅 과정을 병렬화한 실시간 허프 변환 시스템을 제안하였다⁽¹¹⁾. 삼각함수를 위한 LUT(Look-up Table)를 파이프라인 처리하였으며 허프 공간에서 투표처리 과정을 병렬화 하였으며 간단한 로직을 추가하여 직선 추출과정을 효과적으로 처리하였다. 논문 ⁽¹²⁾에서는 픽셀 수준, 각도 수준의 병렬 처리를 적용하였으며 병렬 처리로 인한 메모리 증가는 없다. 불필요한 계산과 효율적인 메모리 접근을 위하여 run-length 인코딩을 적용하였다. Hajjouji 등은 3차원을 2차원으로 매핑 시 발생하는 왜곡을 줄이기 위하여 차선 방향을 매개변수화 하였으며, 이는 허프 역변환을 단순화하고 복잡도를 줄일 수 있다⁽¹³⁾.

제안한 구조는 기울기 기반 허프 변환 알고리즘을 적용하여 전처리 과정 없이 기울기 각도를 중심으로 (–4 ~ +4) 범위의 점들만 고려하였고 그 중에 중심 픽셀에 가장 높은 가중치를 적용함으로써 정확도를 높였다. 계산의 복잡도를 낮추기 위하여 곱셈, 나눗셈 등의 연산을 시프트로 대체하였고 2의 제곱수의 가중치를 적용하여 효율적으로 메모리를 활용하였다. 성능을 개선하기 위하여 $\sin\theta$, $\cos\theta$ 등을 위한 LUT와 가중치 값을 위한 보팅 메모리를 주소 영역별로 9개로 분할하여 동시에 처리함으로써 직선 검출 속도를 개선하였고 local maxima 진행시에는 인접한 9개의 $(\rho ,\:\theta)$ 단위로 병렬처리하였다.

본 논문의 2장에서는 기울기 기반 허프 변환 알고리즘에 관해 설명하고 3장에서는 제안한 전체 시스템 구조와 메모리 분할 및 병렬 구조에 대하여 설명한다. 4장에서는 하드웨어 결과 분석 및 다른 허프 변환 시스템 구조와의 비교·분석하며 5장에서는 결론을 맺는다.

2. 기울기 기반 허프 변환 알고리즘

직선 방정식 $y=ax+b$는 어떤 점 $(x_{i},\:y_{i})$을 지나는 직선이다. 이 방정식을 만족시키는 a, b의 값은 무수히 많다. 이 방정식을 $b=-x_{i}a+y_{i}$로 쓰면 고정된 점 $(x_{i},\:y_{i})$에 대해 직선의 방정식을 만드는 변수 공간(parameter space)이 된다. 즉, $(X,\:Y)$ 공간에서 $y=a'x+b'$을 만족시키는 무수히 많은 점들은 $(A,\:B)$ 변수 공간에서 한 점 $(a_{i},\:b_{i})$로 표현된다.

그러나 직선의 기울기$(a_{i})$와 절편$(b_{i})$의 범위는 무한대라는 문제점이 있으며, 이 문제를 해결하기 위해 직선의 방정식을 식 (1)로 표현할 수 있다.

$\rho$는 원점에서 직선까지의 거리를, $\theta$는 x축으로부터의 각도를 의미한다. 따라서 그림 1처럼 $(X,\:Y)$ 공간의 직선을 $(P ,\:\Theta)$ 공간에서 하나의 점으로 표현할 수 있고, 좌표계의 값 모두 영상의 크기에 따라 유한한 값으로 표현할 수 있다. 허프 변환의 원리를 이용하여 $(X,\:Y)$ 공간에서의 직선은 $(P ,\:\Theta)$ 2차원 배열의 해당하는 좌표에 +1 증가시켜 주며 과정이 모두 끝난 뒤 배열에 저장된 값 중 특정 임계값(threshold)을 넘은 점 $(\rho ,\:\theta)$를 직선으로 인식한다.

허프 변환은 잡음에 강하다는 장점이 있으나 큰 메모리가 필요하고 계산이 복잡하며 전처리 과정이 필요하다는 단점이 있어 다양한 개선된 알고리즘들이 제안되었다.

기울기를 이용한 허프 변환은 중심 픽셀 주변으로만 가중치를 더해주기 때문에 기존의 일반적인 허프 변환보다 가중치가 분산되지 않고 중요한 픽셀에만 그 값을 부여할 수 있다. 또한 가중치를 더해 줘야 하는 픽셀의 수가 현저히 줄어들기 때문에 계산 속도 개선에도 도움이 된다.

Sobel filter를 이용하여 영상의 수직, 수평 변화량을 구한다⁽⁶⁾⁽⁷⁾. 식 (2)는 Sobel filter의 커널을 보여주며 3×3 크기의 입력 영상 I와 필터를 각각 컨볼루션(⨂)하여 수평, 수직 변화량 Gx, Gy를 구한다.

두 결과값을 식 (3)에 대입하여 기울기 크기(G)를 구하고, 식 (4)를 통해 x축과 이루는 각도($\theta$)를 구할 수 있다.

식 (4)로 얻은 기울기 값 $\theta^{'}$를 중심으로 [-λ, +λ]의 범위에 있는 각도 $\theta$에 대하여 식 (5)의 가중치를 차등 적용한다. 본 연구에서는 λ=4의 값을 채택하였고 이때 가중치는 효율적인 메모리 사용을 위하여 2의 거듭제곱을 이용한다. 기울기 기반 허프 변환 알고리즘은 다음과 같다.

[기울기 기반 허프 변환]

for all $(x_{i},\:y_{i})$ in $(X,\:Y)$, compute G and $\theta^{'}$

for $\theta$ in $(\theta^{'}-\lambda)$ ~ $(\theta^{'}+\lambda)$

begin

if $\theta < 0$ then $\theta ←\theta +180$

$\rho ← x\cos\theta +y\sin\theta$

$vote[\rho][\theta] ← vote[\rho][\theta]+ G×w(\theta -\theta^{'})$

end

기울기 기반 허프 변환은 중심 픽셀의 각도 $\theta^{'}$와 해당 각도 $\theta$의 차이에 반비례하는 가중치 $G\times w(\theta -\theta^{'})$를 사용함으로써 더 정확한 결과를 얻을 수 있다.

3. 제안한 허프 변환 시스템 구조

그림 2는 제안한 시스템의 전체 구조를 나타낸다. 먼저 Sobel filter에서 변화량(G)과 기울기($\theta$΄)를 계산하며 이때 얻은 각도를 이용하여 rho 모듈에서는 ($\theta^{'}$-4) ~ ($\theta^{'}$+4)의 9개의 각도에 해당하는 각각의 직선의 거리($\rho$)를 구하고 weight 모듈에서는 각도($\theta$)와 가중치(w)를 병렬로 구한다.

rho 모듈과 weight 모듈에서 나오는 9개의 거리, 가중치, 각도 쌍이 vm 모듈로 각각 입력된다. 입력된 거리와 각도를 이용하여 메모리의 주소를 구하고, 해당하는 메모리 주소의 저장값(voting value)과 입력받은 가중치가 더해져 메모리값이 갱신된다. 이때 9개 쌍을 동시에 저장하기 위하여 하나의 메모리를 9조각으로 나누어 병렬로 처리하였다. 영상 전체 픽셀에 대한 저장값 계산이 완료되면 local maxima 모듈을 통해 최종적으로 직선에 해당하는 거리와 각도가 출력된다.

그림 3은 식 (2)와 같이 3×3 Sobel filter를 이용하여 윈도우 내의 픽셀값에 대한 x축, y축 변화량 Gx, Gy를 계산하는 모듈이다. 식 (3)의 유클리드 거리(Euclidean distance) 계산방식은 연산의 복잡도를 높이기 때문에 맨해튼 거리(Manhattan distance)를 이용하여 변화량을 구하였다.

그림 4는 Gx, Gy를 이용하여 각도를 구하는 angle 모듈이다. 식 (4)에서 각도 $\theta$의 범위는 (0≤$\theta$≤179)이며 각도의 범위가 넓으면 이후 사용할 LUT의 크기가 커지므로 Gx, Gy의 절댓값 중 작은 수에서 큰 수를 나누어주면 각도의 범위가 (0≤$\theta$≤45)으로 한정된다. 나눗셈기는 non-restoring divider 구조를 이용하여 설계하였고 소수점 아래 10자리 나눗셈을 진행하였다. 나눗셈의 결과에 곱셈기 대신 시프트를 이용하여 곱셈기의 복잡성을 개선할 수 있다. 시프트 연산으로 100을 곱하고 소수점 아

래를 반올림하여 정수로 만들어줌으로써 LUT의 주소로 사용되는 $\tan^{-1}(x)$ 값을 만들 수 있다.

LUT에서 불러온 각도는 Gx, Gy의 절댓값을 이용하여 작은 수에서 큰 수를 나눠 만든 값이므로 식 (4)와 같게 값을 변경해주어야 한다. 표 1은 각도를 변환하는 조건을 나타낸다. 조건 1에서 $\left | G_{x}\right | >\left | G_{y}\right |$의 경우에는 식 (4)와 같게 계산하지만, $\left | G_{x}\right | <\left | G_{y}\right |$이면 각도를 (90-$\theta$΄)로 수정한다. 조건 2에서 Gx와 Gy의 부호가 서로 같으면 값이 변하지 않지만, 부호가 다를 경우 각도를 (180-$\theta$΄)로 수정한다. 조건 1, 2를 모두 고려하여 최종 각도를 결정한다.

그림 5는 rho 모듈을 나타내며 이전 모듈에서 구한 각도를 이용하여 거리($\rho$)를 구한다. 효율적인 처리를 위하여 LUT와 rho calc 과정을 ($\theta^{'}$-4) ~ ($\theta^{'}$+4)의 9개로 분할하여 병렬로 연산한다. 거리는 식 (1)로 구하는데, x와 y의 범위가 각각 (0 ~ +x), (0 ~ +y)이므로 이미지의 중앙을 원점으로 맞추기 위해서 모든 좌표에 식 (6)의 값을 빼 x와 y의 범위를 $\left(-\dfrac{x}{2}\right)\sim\left(+\dfrac{x}{2}\right),\:\left(-\dfrac{y}{2}\right)\sim\left(+\dfrac{y}{2}\right)$로 조정한다. 모든 픽셀에 대하여 새로운 좌표 x΄, y΄와 cos, sin 모듈에서 출력된 $\sin\theta$, $\cos\theta$ 값을 이용하여 각각의 각도에 해당하는 거리를 계산한다. $\sin\theta$, $\cos\theta$ 값은 소수점 아래 6자리까지 표현하며 곱셈 결과와 $x\cos\theta$, $y\sin\theta$의 값을 이용하여 거리($\rho$)를 구한다.

기존의 거리는 (-$\rho$ ~ +$\rho$)의 범위지만 메모리 저장을 위하여 식 (7)의 상수 d를 더하여 (0 ~ +2$\rho$)로 변환한다. 그림 6은 ($\theta^{'}$-4) ~ ($\theta^{'}$+4)의 각도에 해당하는 $\cos\theta$ 값을 출력하는 모듈이다.

식 (8)에 따라 rowAddr 모듈에서 임시 주소를 만든다. cos0o ~ cos89o의 값은 나머지 i에 따라 모듈 LUT_cos0부터 LUT_cos8까지에 나누어 저장되며 90° 이상일 때는 $\cos\theta$의 대칭성을 이용하여 구할 수 있다. 이때 $\theta$의 나머지가 i(i≠0)일 때 (180-θ)의 나머지가 (9-i)의 규칙성으로 대치되므로 mux를 이용하여 조건에 맞게 최종값을 출력한다. sin 모듈도 cos 모듈과 유사한 방법으로 동작한다.

그림 7은 식 (5)를 이용하여 해당 각도 별로 가중치를 구하는 모듈이다. (w-4) ~ (w+4)까지의 모듈은 ($\theta^{'}$-4) ~ ($\theta^{'}$+4)까지의 각도에 따라 변화량을 계산하며 중심 각도인 $\theta^{'}$에 가장 큰 가중치가 적용되며 중심에서 멀어질수록 작은 가중치가 적용된다. 여기에서 중심과 가까울수록 큰 수를 곱하여 가중치를 조정할 수 있는데, 곱해주는 수를 2의 제곱수로 설정함으로써 곱셈기의 사용 대신 시프트 연산자로 곱셈을 대체할 수 있다. 유사한 이유로 나눗셈은 시프트 연산자를 이용하여 계산을 단순화하였다.

각도를 $\theta^{'}$+i (-4≤i≤4, i∈Z)까지의 범위로 조정하는 과정에서 0°보다 작아지거나 180°보다 커지는 경우가 발생한다. (-4≤i≤-1, i∈Z)의 범위에서 각도는 mux를 이용하여 ($\theta^{'}$+i)와 (180+($\theta^{'}$+i)) 중 0보다 크거나 같은 양수인 값을 선택한다. (1≤i≤4, i∈Z)의 범위에서는 ($\theta^{'}$+i)와 (($\theta^{'}$+i)-180) 중 180보다 작은 값을 선택한다. 인덱스가 (w+i)인 모듈의 출력값은 9개로 나누어진 메모리에 저장하기 위해 나머지 값에 따라 재정렬된다. 중심각 $\theta^{'}$의 나머지 값 i 하나로 주변값을 모두 정렬할 수 있으므로 입력값은 표 2의 규칙에 따라 각각 재배치된다. 표 2의 상단에 있는 w는 weight를, a는 angle을 뜻한다. 표 내부의 이름은 그림 7에서 w_와 a_ 뒤에 오는 명칭으로 작성하였다.

그림 8은 local maxima 모듈의 구조를 보여주며 $(P ,\:\Theta)$ 공간의 한 점을 중심으로 9×9 영역의 저장값을 비교하여 직선에 해당하는 점 $(\rho ,\:\theta)$을 출력한다. $(P ,\:\Theta)$ 공간에서 점 $(\rho ,\:\theta)$을 중심으로 거리 (0~2$\rho$), 각도 (0°~179°)의 범위에 대하여 비교를 진행한다. 하나의 점 $(\rho ,\:\theta)$을 중심으로 9×9 영역은 한 행씩 처리되어 총 9개의 행이 처리되는데, 먼저 중심값과 임계값의 대소 여부를 판단한다.

중심값 $(\rho ,\:\theta)$는 memaddr_generator 모듈의 입력으로 들어가 식 (9)를 통해 9×9 영역의 중심값 주소를 계산한다. 구한 주소를 이용하여 표 3의 addr rotator를 통해 하나의 행의 전체 주소값을 구한 후 9개의 메모리에서 동시에 저장값을 출력하여 9×9 영역의 중심값을 임계값과 비교한다. 이때 임계값보다 작으면 다른 값과 비교 없이 다음 $(\rho ,\:\theta)$로 넘어가고, 크면 중심값의 저장값과 각 행의 9개의 저장값을 비교한다. 이때 중심값보다 큰 값이 있다면 9개의 행에 대해 모두 비교를 진행할 필요 없이 다음 $(\rho ,\:\theta)$로 진행하여 계산 과정을 줄일 수 있다.

9×9 영역을 비교하면서 거리값이 (0~2$\rho$)의 정해진 범위를 넘어가는 경우 메모리 내에서 주소가 존재하지 않으므로 해당 행에 대해 값을 0으로 출력한다. 각도는 (0°~179°)의 범위 내에서 순환하기 때문에 표 3의 방법으로 값을 변환한다.

9×9 영역의 비교 순서는 중심값이 있는 5행을 가장 먼저 비교한 후, 9행부터 위로 올라가며 진행한다. 일반적으로 다음 행으로 바뀐다는 것은 거리가 1만큼 커진다는 뜻이므로 이전 행의 주소에 20을 더하여 주소를 구한다. 그러나 5행을 가장 먼저 진행한 후 9행부터 차례로 진행하기 때문에 이 경우 5행의 주소에서 80을 뺀다. 또한, 6행의 비교를 진행한 후 5행을 다시 비교할 필요가 없으므로 바로 4행으로 바꿔주기 위해 40을 더한다. 9×9 영역의 비교과정이 모두 끝난 뒤 81개의 저장값 중 가장 큰 값이 중심 픽셀의 저장값과 같다면 해당 점 $(\rho ,\:\theta)$가 직선으로 출력된다.

표 3은 addr rotator 모듈의 동작을 나타낸 것이다. 예외상황은 $(P ,\:\Theta)$ 공간에서 9×9 영역을 비교할 때 중심 픽셀의 각도가 (0°~3°), (176°~179°)에 해당하는 경우로, $(P ,\:\Theta)$ 공간에서 각도 일부가 정해진 범위를 넘어간다. 각도가 (0°~3°)의 범위인 경우(addr%20=0)는 i가 (0~3)의 범위일 때 음수로 값의 범위를 넘어가기 때문에 최소 1개에서 최대 4개까지 (176°~179°)의 각으로 변환된다. 이 경우 변환된 각도의 주소는 addr에서 19를 더하여 구한다. 각도가 (176°~179°)의 범위인 경우(addr%20=19)는 i가 (5~8)의 범위일 때 179°를 초과하여 값의 범위를 넘어가기 때문에 최소 1개에서 최대 4개까지 각도 (0°~3°)의 각으로 변환되므로 addr에서 19를 뺀다.

일반적인 상황은 $(P ,\:\Theta)$ 공간에서 9×9 영역을 비교할 때 중심 픽셀의 각도가 (4°~175°)의 범위에 해당하는 경우이다. i가 (0~3)의 범위일 때는 최소 1개에서 최대 4개까지 바로 아래 주소를 이용하기 때문에 addr에서 1을 빼주고, i가 (5~8)의 범위일 때는 최소 1개에서 최대 4개까지 바로 위 주소를 이용하기 때문에 addr에서 1을 더하여 addr 값을 구한다.

그림 9는 메모리 구조를 보여주며 각도를 9로 나눴을 때의 나머지 값을 이용하여 메모리를 나누고 해당 메모리에 가중치를 저장한다. 각 메모리의 이름에 명시된 숫자가 나머지 값을 의미한다. 각각의 메모리 내에서 거리의 범위는 (0~2$\rho$)이고, 하나의 거리값마다 20개의 각도가 존재하기 때문에 식 (9)로 메모리의 주소를 구할 수 있다. 9개의 메모리를 이용하여 메모리에서 값을 읽을 때 메모리가 겹치지 않고 9개의 값을 동시에 읽거나 쓸 수 있어 처리성능(throughput)을 개선할 수 있다. LUT 또한 메모리 분할과 같은 원리로 90개의 각을 9로 나눈 나머지를 바탕으로 9개의 LUT로 분할하여 sin, cos 값을 저장하였다.

4. 성능 분석

제안한 실시간 차선 검출 시스템은 VerilogHDL로 설계되어 동부하이텍 110nm 표준셀 라이브러리로 합성하였다. 합성 결과 전체 시스템은 2-input NAND 게이트를 기준으로 15k의 게이트가 필요하다. local maxima에 사용되는 윈도우 크기는 9×9이며 처리되는 영상 사이즈는 1920×1080이다. $\tan^{-1}\theta$ 함수를 위한 LUT는 0.606Kb이며 $\sin\theta$, $\cos\theta$ 함수를 위한 LUT는 각각 0.637Kb로 총 1.88Kb의 LUT가 필요하며 가중치를 저장하기 위한 9개의 메모리는 5,948Kb가 필요하다. 최대 동작 주파수는 210Mhz이고 이때 처리성능은 73fps으로 실시간 처리성능으로 충분하다.

본 논문에서는 연산의 단순화를 위해 LUT와 맨해튼 거리 계산법을 적용하였다. 표 4의 lane4 영상에 대하여 LUT를 적용할 때와 $\sin\theta$, $\cos\theta$의 함수를 적용할 때를 비교하면 $\theta$는 오차가 없었으며 $\rho$는 1% 이내의 오차가 발생하나 표 4에서와 같이 직선 검출에는 문제가 없었다. 또한 두 점 사이의 거리를 맨해튼 거리와 유클리드 거리를 이용하여 직선을 검출할 경우를 정량적으로 비교하였을 때 연산법의 차이 때문에 두 방법에서 저장, 누적된 값이 다르긴 하지만 해당 값들의 상대적인 크기를 비교하기 때문에 표 4의 다양한 영상들의 직선을 검출하는 데에는 문제가 없음을 확인할 수 있다.

표 4는 제안한 시스템을 이용하여 샘플 영상의 직선을 검출한 결과다. 결과 영상에서 볼 수 있듯이 점선, 실선, 야간 등 다양한 상황에서 차선을 올바르게 검출하고 있음을 보여준다. 표 5에서는 제안한 기울기 기반 허프 변환 시스템의 하드웨어 성능을 보여주고, 표 6에서는 각 서브 모듈별 게이트 수를 나타낸다. 본 연구와 비교할 수 있는 적절한 ASIC 구현사례가 없어서 FPGA 사례와 비교하였다. 제품마다 차이는 있지만 하나의 slice는 20개 내외의 게이트로 구성되어 있으므로 이를 바탕으로 비교하였을 때 최적화도가 낮은 FPGA의 특성을 고려하더라도 본 연구의 결과는 낮은 하드웨어 복잡도를 갖는다고 할 수 있다. Voting memory 용량은 영상의 대각선 길이에 비례하여 증가하므로 가장 큰 영상을 처리하는 본 연구의 결과에서 소폭 증가하였다.

처리성능에서는 110nm의 제조 공정을 사용하여 최신 공정을 사용한 다른 결과들과 비교하였을 때 불리한 지연특성을 갖지만, 계산의 대부분이 각도에 대한 거리와 가중치 계산 및 local maxima 모듈에서 중심값 비교 계산이라는 점을 고려했을 때 계산 과정에서 메모리를 분할하지 않는 경우는 9개의 거리와 가중치를 하나씩 처리해야 하는 반면에 메모리 분할을 이용하는 경우는 9개의 거리와 가중치를 동시에 처리 가능하여 약 9배의 속도를 개선할 수 있어 처리성능에 가장 크게 기여함으로써 픽셀 당 처리 속도에서 좋은 결과를 나타내었다. 더욱이 최신 FPGA들에 내장되어 있는 DSP 블록이나 embedded multiplier 등은 사용하지 않았다. 본 연구결과에서 충분한 크기의 1920×1080의 영상을 적용하였을 때 73fps의 실시간 처리성능을 보여주었다.

5. 결 론

제안된 실시간 허프 변환 시스템은 전처리 과정 없이 기울기를 이용한 가중치와 메모리 병렬 처리를 통해 기존 알고리즘에 비해 높은 정확도와 하드웨어 효율성을 보여준다. 기존 허프 변환과 달리 기울기를 이용하여 가중치를 부여하고, 메모리를 효율적으로 사용하기 위하여 가중치 적용방식을 2의 제곱수로 곱해주었다. LUT와 메모리를 9개로 분리하여 거리, 각도, 가중치에 대한 값을 동시에 처리하며 local maxima 모듈을 진행하는 과정에서 저장값을 동시에 입·출력함으로써 처리성능을 개선하였다. 제안한 구조는 동부하이텍 110nm 표준셀 라이브러리로 합성하여 1920×1080 영상 기준 최대 동작 주파수 210Mhz(73fps)를 보이며 2-input NAND 기준 15K의 게이트와 5,950Kb의 메모리를 사용한다.