2.1 개선된 적분 히스토그램

적분 히스토그램은 이미지를 일반화할 수 있지만 계산 양이 많아 처리속도에 영향을 준다. 이러한 단점을 보완하기 위해 개선된 적분 히스토그램을 제안한다. 기존의 적분 히스토그램은 마스크 안에 각 픽셀 값들을 더하여 새로운 히스토그램 생성한다. 그러나 이 방법은 마스크가 이동할 때마다 마스크 내부의 픽셀 값들을 모두 계산해야 하므로 마스크의 크기에 비례하여 처리시간이 길어진다. 이러한 단점을 극복하기 위하여 개선된 적분 히스토그램은 마스크의 크기를 제한하여 히스토그램 계산을 빠르게 한다. 이 방식에서 $P_{j}$를 번째 마스크의 내부 픽셀 값의 합이라고 할 때, $P_{j+1}$은 다음과 같이 나타낼 수 있다.

여기서 $k$는 마스크의 최대 크기이며, $A_{i}$는 각각 마스크 내부의 첫 픽셀 값이고 $A_{f}$는 한 픽셀 이동한 마스크의 마지막 픽셀 값이며, $f=i+k$가 성립한다. 이를 근거로 그림 2는 개선된 적분 히스토그램을 나타낸다.

움직이지 않은 초기 마스크 안의 히스토그램 값은 $P_{j}$이며 마스크가 움직이지 않았으므로 처음 $A_{i}$는 0이다. 마스크의 위치가 이동한다면 마스크 안의 픽셀 값들을 일일이 더하지 않고 마스크가 움직이기 전 히스토그램 값 $P_{j}$에서 두 픽셀, $A_{i}$와 $A_{f}$을 가지고 다음 히스토그램 $P_{j+1}$을 계산한다.

이와 같이 개선된 알고리즘은 이미지 센서의 데드 픽셀 (dead pixel)이나 성능이 저하된 구간에 이미지 평탄화에 적용할 수 있다. 그리고 RGB 또는 YCbCr (밝기, 색차정보) 시스템에서 해당 픽셀을 디지털화된 값을 이용하여 특정 색상 (구간)을 검출할 수 있고, 실제로 FPGA에서 에지 검출에 적용할 수 있다.

그림. 2. 개선된 적분 히스토그램

Fig. 2. Improved integral histogram

본 논문에서 제안하는 히스토그램 알고리즘은 기본적으로 원형 정합(Template Matching)방법의 속도를 개선한 적분 히스토그램 방법과 투영 히스토그램 방법을 적용하므로, 해당 이미지를 $x$축(수평) 투영 히스토그램 및 $y$축(수직) 투영 히스토그램으로 짝을 지어서 진행한다.

2.2 이미지 오픈 및 좌표 찾기

본 논문에서 이미지 오픈 단계는 실제 카메라에서 지원하는 이미지 규격에 맞추어 FPGA에 저장하는 단계이며, 실제 이미지는 8 bit Gray Scale의 규격 이미지를 사용한다. 카메라 규격으로 저장한 데이터는 픽셀 단위로 주소 값에 따라 FPGA 메모리에 저장되어 있으며 FPGA에서 Static RAM 방식 및 카운터를 사용하여 이미지 픽셀 주소를 순차적으로 증가시키면서 제어한다.

이미지 오픈 이후 FPGA에 저장 및 읽기가 가능해지면 좌표 검색을 시작한다. 이미지는 회전이 되어있으며 이미지에 포함된 특정한 패턴 또한 동시에 회전하게 된다. 즉 좌표 값이 달라진다. 이러한 현상을 보상해주기 위해 첫 픽셀의 좌표를 보정해주는 CORDIC (COordinate Rotation DIgital Computer) 기능을 구현한다. 이는 회전 시 얻어지는 최대 픽셀을 구할 때 요구되는 삼각함수, 초월함수, 지수함수, 로그함수, 제곱근, 나눗셈 등을 bit-shift와 가산기의 단순한 구조로 구현 가능하도록 하여 곱셈기가 필요 없는 하드웨어에 최적화된 알고리즘이다. 본 논문에서는 특별한 계산이 필요 없이 LUT (Look Up Table)을 이용하여 변환되게 설계하였다. CORDIC을 이용하여 COS, SIN 함수를 적용시키려면 기존의 Degree를 Radian으로 바꾸어야 한다. 또한, floating point 방식의 형태로 나타내어 소수점과 부호를 결정 해주어야 한다. 정확한 정확도를 위하여 충분히 큰 16 비트 길이의 부동소수점 상수를 사용하며 최상위 비트는 부호, 15, 14번째 비트는 지수, 하위 13개 비트는 분수를 표현한다.

2.3 히스토그램 구현

본 논문에서는 PC 환경보다 빠르게 이미지를 판별하기 위해 FPGA 상에서 히스토그램 알고리즘을 구현한다. 알고리즘 상에서 자주 사용되는 적분 히스토그램은 이미지의 픽셀 값에 마스크를 지정하여 마스크 내부에서 누적시켜가면서 그 값들을 좌표에 맞게 계산하는 알고리즘이라 할 수 있다. 그러나 하드웨어의 히스토그램 계산 알고리즘 특성상 가산기 및 누적기가 많이 필요해지며 반복문이 자주 사용된다. 이를 기존의 CPU로 처리를 한다면 처리속도 저하를 초래할 수 있으며 이를 방지하기 위하여 FPGA를 이용하여 설계한다. FPGA 내부에서 설계 시 가장 중요한 요소는 해당 하드웨어의 용량이며 이러한 요소들은 최댓값이 정해져 있다. 즉, 목표 FPGA의 최대 용량 내에서 설계할 수 있는 프로그래밍 기술이 필요하다. 본 논문에서 사용한 FPGA는 Xilinx Spartan6 LX100이며 최대 Flip-Flop 및 Slice를 초과하지 않는 선에서 설계한다.

실제 적분 히스토그램을 FPGA에서 구현하려면 반복문을 자주 사용해야 하지만 FPGA 내부에서 반복문을 많이 사용하면 지연이 심해 성능이 떨어질 뿐만 아니라 실제 하드웨어 구현 효율이 나쁠 수 있다. 이를 피하기 위해 반복문을 카운터 방식으로 대체하여 제어하도록 한다.

카메라에서 FPGA로 들어오는 이미지를 마스크의 범위와 이미지의 폭, 높이를 산정하여 카운터로 제어하며, 히스토그램을 구하는 알고리즘 흐름도는 그림 3과 같다. 마스크의 최대 크기는 특정 패턴의 히스토그램 넓이와 크기가 같으며 마스크의 크기가 정해지면 첫 픽셀 값부터 마스크 내부에 있는 모든 픽셀 값을 더하여 초깃값으로 저장한다. 마스크의 이동 시 초깃값과 이동 전의 첫 픽셀, 이동 후 마지막 픽셀을 가지고 (1)과 같이 계산한다. 마스크의 개수가 이미지의 넓이보다 커질 때까지 계속하여 반복하며, 만약 마스크의 개수가 이미지의 넓이보다 커진다면 히스토그램 계산을 중단한다.

FPGA 상에서 HDL (Hardware Description Language)을 사용하여 구현한 히스토그램을 구하는 하드웨어 구성은 그림 4, 5와 같다. 그림 4는 히스토그램의 초깃값을 구하는 하드웨어의 구조이며 주소를 제어하는 MUX와 RAM, 마스크 내부의 값들을 더해주는 가산기 및 누적을 하기 위해 잠시 값을 저장해 두는 Flip-Flop 등으로 구성이 되며, 그림 5는 첫 히스토그램 계산 후 개선된 히스토그램을 구하는 하드웨어 구조이며 가산기와 감산기 및 Flip-Flop, MUX로 구성된다.

그림. 3. 히스토그램을 얻기 위한 흐름도

Fig. 3. Flow chart to obtain a histogram

그림. 4. 첫 히스토그램의 하드웨어 구조

Fig. 4. H/W architecture of the first histogram

그림. 5. 개선된 히스토그램의 하드웨어 구조

Fig. 5. H/W architecture of the improved histogram

2.4 유사도 및 클러스터링

유사도를 계산하기 위하여 본 논문에서는 원형 정합(Template Matching) 방법을 적용한다. 원형 정합이란 어떠한 사물의 표준 모델(Standard Model)을 하나 만들고 비교해야 할 사물과 미리 준비된 표준 모델의 비교를 통해 사물을 판단하는 일종의 패턴 인식 방법이다. 원형 정합 방법에는 여러 가지가 있을 수 있지만, 여기서는 히스토그램으로 사물을 일반화하여 새로운 데이터를 만들어 비교하는 방법을 사용한다.

유사도를 판단하려면 특정한 패턴과 원형 정합을 통해 비교해야 하며 특정한 패턴은 카메라 이미지에서 회전된 특별한 부분을 의미한다. 이미지 회전 시 특정 부분 또한 같이 회전되며, 이는 적분 히스토그램 및 투영 히스토그램에 변화를 줄 것이다. 그림 6은 Lenna 이미지⁽⁹⁾ 회전 시 패턴이 같이 회전하는 모양을 나타내며, 이러한 패턴 히스토그램을 가지고 앞서 구하였던 히스토그램과 차이를 구하여 유사도를 구한다. 101 개의 패턴 히스토그램들에 대하여 차이를 구하며 원형 정합을 위해 $x$축 및 $y$축으로 이루어지는 유사도 히스토그램을 계산한다.

그림. 6. 회전된 패턴: (a) 0° (b) +5° (c) -5°

Fig. 6. Rotated pattern: (a) 0° (b) +5° (c) -5°

유사도 계산 이후 계산된 값을 가지고 비교를 하며 가장 유사도가 높은 구간만 따로 후보로 지정하여 저장한다. 이를 “후보 선택” 이라 한다. 후보 선택 과정 후 후보들의 분포들을 살펴보면 그림 7과 같은 모양의 분포를 가진다. 이미지를 일반화하여 비교하는 적분 히스토그램 기반의 원형 정합 방법은 이미지의 일반화 때문에 패턴 근처에서 비슷한 유사도를 가지는 히스토그램이 분포하는 경향이 있다. 이러한 현상은 그림 7과 같이 나타나며 이를 후보군이라 한다. 유사도를 비교할 시 후보군 내부의 후보들을 모두 비교한다면 처리시간이 증가하기 때문에 대표 후보를 정하는 과정을 적용한다. 이를 “클러스터링”이라 한다. 그림 8은 실제 시뮬레이션 결과 후보군의 형태를 보여준다.

그림. 7. 후보와 후보 클러스터링

Fig. 7. Candidate and its clustering

그림. 8. 후보군의 시뮬레이션 결과

Fig. 8. Simulation result of candidates

본 논문에서는 클러스터링 중 Leader-Follower 클러스터링을 응용한 방법을 사용하였다⁽¹⁰⁾. 논문에서 사용한 클러스터링은 본래 좌표 평면에서 직선거리인 $\sqrt{x^{2}+y^{2}}$를 사용해야 하지만 FPGA의 하드웨어 특성상 루트 계산 및 곱셈기를 사용하면 동작속도가 매우 떨어지는 경향이 있으므로 $x+y$로 대체하여 계산한다. 클러스터링은 $x$축 거리와 $y$축 거리를 계산 후 임계값보다 작으면 같은 후보군으로 포함시키고, 임계값보다 크면 서로 다른 후보군으로 배정하는 방법을 사용한다.

2.5 유사도 결정

클러스터링 이후 최종 선별된 유사도 후보들은 각각의 유사도를 포함하고 있다. 각각의 유사도는 클러스터링 과정과 투영 히스토그램 계산으로 $x$축 및 $y$축에 대한 좌표 정보를 가지고 있다. 최종 선별된 유사도 후보들 중에 가장 높은 유사도를 선택하여 최종 결과를 도출한다. 그림 9는 최종 선별된 유사도들 중 가장 높은 유사도를 선출하는 과정을 보여준다. 최초 비교 유사도를 기준으로 모든 유사도들을 차례대로 비교하여 가장 높은 유사도를 선택한다.

그림. 9. 최종 유사도 판정

Fig. 9. Decision of final similarity

3.1 구현 검증

그림 10은 최종적으로 구현된 시작품이다. 인식 알고리즘을 HDL로 설계하였으며, 적용한 FPGA는 Xilinx Spartan6 LX100으로써, 로직 셀의 수가 십만 개 정도이고, Flip-Flop이 12만개 내장되며, 합성 툴은 Xilinx의 ISE(Integrated Software Environ- ment)를 사용하였다. 사용된 카메라는 640×480의 VGA 규격이며, 초당 프레임 수는 (FPS, Frame Per Second)는 15와 30을 설정할 수 있다.

그림. 10. 구현된 시작품

Fig. 10. Implemented prototype

앞서 언급하였던 알고리즘 특성상 FPGA의 하드웨어 용량을 많이 사용하기 때문에 최적화되지 않으면, 해당 FPGA의 용량 초과될 수 있다. 하드웨어 합성과 동작이 원활해지기 위해서는 전체 용량의 70% 정도의 사용량을 권장하지만 LUT 부분으로 말미암아 용량이 초과할 가능성이 높다. 이는 알고리즘 특성상 내부 실시간 처리를 위해 LUT와 동시에 많은 MUX의 사용함이 원인이며 이러한 원인을 해결하기 위해 FPGA 내부 RAM을 이용하여 Flip-Flop을 주로 이용하고 조건문을 최대한 CASE문으로 대치하여 중첩 MUX를 제한하였다. 그 결과 제한된 용량 내에서 합성이 가능함을 확인하였다.

합성된 결과의 RTL (Register Transfer Level) 회로도를 보면 그림 4와 5가 그림 11과 그림 12와 같이 실제로 합성이 되는 것을 볼 수 있다.

그림. 11. 첫 히스토그램의 RTL 회로도

Fig. 11. RTL schematic of the first histogram

그림. 12. 개선된 적분 히스토그램의 RTL 회로도

Fig. 12. RTL schematic of improved integral histogram

그림 13은 -5도(입력 이미지 xh_0)에서 +5도(입력 이미지 xh_9)에 이르기까지 1도 간격으로 회전된 10 개의 이미지 (0도는 제외)에 대한 히스토그램 값을 얻은 것이다. 이 결과를 얻기 위하여 그림 12의 회로를 동작시켰고, 실제 동작결과를 논리분석기(Xilinx Chipscope Pro Analyzer)를 이용하여 검증한 결과이다. 얻어진 값은 Hex 4073 ~ 41FA 사이이며, 이것은 PC에서 시뮬레이션 된 결과⁽¹¹⁾와 동일한 결과를 이므로, 개선된 히스토그램 계산 알고리즘이 FPGA 내부에서 정상 동작하는 것을 확인할 수 있다.

그림. 13. 개선된 히스토그램의 동작 결과

Fig. 13. Operation results of the improved histogram

3.2 성능 분석

지금까지 기술한 내용의 성능을 분석하는 과정은 다음과 같다.

∙ 카메라 규격에 맞는 이미지를 오픈한다.

∙ 회전된 101 장의 참조 패턴을 오픈한다.

∙ 테스트 데이터를 FPGA에 저장한다.

∙ FPGA 동작속도를 62.5 MHz로 설정한다.

∙ 논리분석기 (Xilinx Chipscope)를 통해 분석한다.

그림 14는 위 환경의 알고리즘 결과 값을 나타낸다. 특정 패턴의 이미지는 시계방향으로 3도 회전한 이미지이며 이를 101장의 참조 패턴과 원형 정합을 통하여 찾아낸다. 결괏값으로 동작을 마치기까지의 소요된 카운터 값과 해당 이미지의 각도 및 유사도를 검출한다.

그림. 14. 얼라인먼트 마커 인식 알고리즘의 최종 결과

Fig. 14. Final result of the proposed alignment marker recognition algorithm

첫 항목인 count_result에는 소모된 카운터의 값이 나타나며 카운터의 값 33AA59(Hex)를 동작속도인 62.5 MHz로 나누어 처리속도 54 ms를 얻었다. 두 번째 항목인 degree_result에는 정확히 3도의 값이 검출되었으며 세 번째 항목과 네 번째 항목에는 해당 이미지의 유사도와 해당 이미지를 제외한 나머지 이미지 중 가장 높은 유사도를 검출한다.

표 1 은 대표적인 각도들의 입력 이미지에 따른 논리분석기의 출력을 나타낸 것이다. 처리속도는 최소 44.1 ms (Hex 2A1B29의 십진 값인 2,759,465를 62.5 MHz로 나눈 값), 최대 71 ms (Hex 43C94A의 십진 값인 2,759,465를 62.5 MHz로 나눈 값)이며, 이는 PC를 이용하여 연산한 결과를⁽¹¹⁾ 훨씬 뛰어넘는 것으로 목표 처리속도인 80 ms를 달성한 수치이며 출력 각도 또한 정확하게 나오는 것을 확인할 수 있다.