J of the Korean Sensors Society Vol 9, No 2 (200) pp 99 š 3D x d l š w NCC š» w Á«*Á y**á z*á A hardware architecture based on the NCC algorithm for fast disparity estimation in 3D shape measurement systems Kyeong-ryeol Bae, Soon Kwon*, Yong-Hwan Lee**, Jong-Hun Lee*, and Byungin Moon Abstract This paper proposes an efficient hardware architecture to estimate disparities between 2D images for generating 3D depth images in a stereo vision system Stereo matching methods are classified into global and local methods The local matching method uses the cost functions based on pixel windows such as SAD(sum of absolute difference), SSD(sum of squared difference) and NCC(normalized cross correlation) The NCC-based cost function is less susceptible to differences in noise and lighting condition between left and right images than the subtraction-based functions such as SAD and SSD, and for this reason, the NCC is preferred to the other functions However, software-based implementations are not adequate for the NCC-based real-time stereo matching, due to its numerous complex operations Therefore, we propose a fast pipelined hardware architecture suitable for real-time operations of the NCC function By adopting a block-based box-filtering scheme to perform NCC operations in parallel, the proposed architecture improves processing speed compared with the previous researches In this architecture, it takes almost the same number of cycles to process all the pixels, irrespective of the window size Also, the simulation results show that its disparity estimation has low error rate Key Words : NCC, disparity, stereo matching, block-based, box filtering š 3D x z w l j 3D e, TOF(time-of-flight) w l l w l ù (Fig ) w l ù y q w x w [], d y ƒ ù ƒ šƒ š d ƒ w w ƒ» l l w l ƒ z w z ful» w š mw 3D y w w y ù l x wš, l» w 3D x d l Fig 2 w w»fulw (School of Electrical Engineering & Computer Science, Kyungpook National University) * w» (Daegu Gyeongbuk Institute of Science & Technology) ** œ w œw (School of Electronic Engineering, Kumoh National Institute of Technology) Corresponding author : bihmoon@knuackr (Received : October 27, 2009, Revised : January 25, 200 Accepted : March 8, 200) Fig Sensor systems for 3D distance measurement 99
34 Á«Á yá zá Fig 2 Distance estimation model of the stereo vision œ w s (image plane) y (pixel) (disparity) wš, w w [2] w l w ful ƒ, j w(global matching) w(local matching) w [3,4] l d l r w w w SAD(sum of absolute difference) SSD(sum of squared difference) w (difference)» w w w» l l w [2,5-7] ù w l w w e û w» w k» l w» w w z w p w» Census transform, NCC(normalized cross correlation)» w š ƒ w z w» NCC» w y (lighting condition) (noise) w, ƒ p ƒ š,» NCC š» w š v w y mw w w L Di Stefano BPC(bounded partial correlation)» w v w NCC y w š[8-0], Shou-Der Wei winner update» (multilevel) w, v w NCC y w [], D M Tsai NCC ƒ v w w t(sum table) w w [2] ù w» w x d š w, w m w x w w w ƒ š l l x w, NCC» y w ûš w, w ƒ w q v xk FNCC(fast NCC) w w 2 NCC š w r, 3 w»» (block-based) vl (box filtering) w q v w w 4 FNCC w l w» wš, 5 2 NCC» l w š l w Fig 3 (rectification and calibration [3] ) e w w vs (epipolar line) k e z w ƒ ƒ w w y ƒ» w (correlation)» w ù» w SAD SSD š,» w NC(normalized correlation), NCC, Census transform» w y w ƒ wù, w» w,» w w y w ù» v w» w» w w w w NCC» w wz 9«2y, 200 00
( )υari, (, ) š 3D x d l š w NCC š» w 35 Fig 3 Stereo matching of left and right images l w x» yù š w p NCC š NCC d Coυ I L ( xy) I R x d y [,, ( +, )] ( ) = ------------------------------------------------------- υari L xy x+ d y R () NCC š () Á y œ (covariance) wš ƒ y t r (standard deviation) w t r (variance) w mw» y (brightness correlation) w ƒ ƒ j» l w () w vs w [0,d] w ƒƒ NCC w NCC [-,] ƒ ù l w w [0,] w ZNCC d ZNCC d N M j = i = Rx ( + d+ iy, + j) µ Rx+ dy, [ ( ( ))] ( ) = ------------------------------------------------------------------------------------------ N M j = i = Rx ( + d+ iy, + j) µ Rx+ dy, [ ( ( ))] 2 Lx ( + iy, + j) µ Lxy, [ ( ( ))] -------------------------------------------------------------------------------- N M j = i = N Lx ( + iy, + j) µ Lxy, [ ( ( ))] 2 M j = i = Rx ( + d+ iy, + j) Lx+ iy, + j ( ) ( ) = ---------------------------------------------------------------------------------------------------------- N M j = i = R 2 ( x+ d+ i, y+ j) M N µ Rx+ dy, M N µ ( Rx ( + dy, )) µ Lxy, (2) ( ( )) 2 ( ( )) ------------------------------------------------------------------------------------------------ N M j = i = L 2 ( x+ i, y+ j) M N µ Lxy, ( ( )) 2 (3) NCC š w y w y s³ w (2) ZNCC(zero-mean NCC) š w [4]» x, y t wš d, L R ƒƒ, y w š M N ƒ, ¼ w µ s³ ùkü š (2) w t (3) [5] (3) y ZNCC w w IL w w IR w 3» vl w ZNCC q v w ZNCC l w wš ƒ w» vl» w w, w q v xk ZNCC w w w 3 ZNCC l (3) ZNCC w w (numerator) w š w L, R w w(squared sum), š w w (denominator) š ƒ ³y w L R w s³ ƒ Fig 4 y ZNCC w ùkü L R s³ w, L, R w( w R L), L, R w w, w, š ù ù w xw w v w w w š óù L, R ü w j» w ƒ ƒ ƒ z (reference) ƒ x, j» j ƒ» ƒƒ w (searching) ƒ j» ( ƒ ¼ ) ( ¼ ) ( ) j z ƒ ¼ ù e l 0 J Kor Sensors Soc, Vol 9, No 2, 200
36 Á«Á yá zá Fig 4 A basic system structure for ZNCC calculation v ZNCC mw w» w» v w ƒ w (3) w» vl wš q v w ƒ w w 32» vl (3) y y w w š, w w š ƒ s³ w w j» ù w, j»ƒ w ƒ j»ƒ j y ƒ w w w w w» w 2D l w j» w j» š w vl» [6] w, wù y ƒ y w w y w Fig 5 w M N y w M N wù ùküš š Fig 6 2D l w ùkü w (K L) (M N) wù w M N Fig 5 Basic example of block-based box filtering Fig 6 Block-based box filtering applied to a 2D data array w j w» vl» w wz 9«2y, 200 02
š 3D x d l š w NCC š» w 37 Fig 7 Block-based box-filtering: (a) calculation of the first block, (b) horizontal movement of the first block, (c) vertical block movement, (d) horizontal block movement in the other area»», w w ƒ» w ƒ y wš, ùƒ y w w, j» (K +M ) (L+N ) ƒƒ ƒ w d wš ƒ w w w d w 32 (Fig 7-(a)) Fig 7» vl» w (, d) w ƒ w(h), w(s) w w ƒ ƒ w w z w ƒ w w w w w w ƒ w (4) w w w = i+ M+ K H ij, P kj, k = i+ M (4) i y, j w y ùkü 2M l (M+K) ¾ y œm w w mw w z w y ƒ w w w w M (L+N ) ƒ w (5) w w w = j+ N+ L S ij, H il, l= j+ N ƒ 2N l (N +L) ¾ y w mw w z w (5) 322 ƒ (Fig 7-(b)) ƒ k M N y w óû ƒ 03 J Kor Sensors Soc, Vol 9, No 2, 200
38 Á«Á yá zá Fig 8 Proposed hardware architecture based on the blockbased box-filtering for ZNCC and disparity calculation M j k k w» ƒ (K ) j», ƒ Mw j ùš Mw j ùƒ ¼ w w» w (6) w ƒ w ƒ j y w š ù j y ƒ w w w ƒ w (5) mw w w w i+ M i+ K+ M P kj, H ij, = + P kj, H i M, j k i k = i+ K = (6) 323 (Fig 7-(c)) ƒ óùš k ƒ w, ƒ w w N j j w» (L-) j Fig 9 Hardware architecture of the average module» ƒ y ƒ w (4) w wš (7) w w w w w w j+ N j+ L+ N H il, H il, S ij, = + S ij, N l j l= j+ L = (7) 324 ù ƒ (Fig 7-(d)) ƒ (6) (7) w ƒ, w w ƒ w» w w wz 9«2y, 200 04
š 3D x d l š w NCC š» w 39 Fig Hardware architecture of the R L sum module Fig 0 Hardware architecture of the square sum module 33» vl w ZNCC q v w Fig 8» vl w ZNCC q v w ù kü 8 q v w j N w ZNCC w s³ w, w w, R L w, w NCC wš w, 4 ù Fig 9 s³ ùkü, Fig 0 w, Fig R L w ùkü š Fig 2 ZNCC w ùkü z w l ùkü R L w, w, s³ Fig 2 Hardware architecture of the module to calculate ZNCC results and find the disparities of matching points 05 J Kor Sensors Soc, Vol 9, No 2, 200
40 Á«Á yá zá wé w ƒ ( w : ) s³ wš ƒ j ( w : ) s³, š w wù w j w ( +) z e s³ w» w vl w w w wš w w w š w w, R L w w ƒ vl w w» vl w ƒ v w w w š ƒ w x w» vl w» w w w ƒ v w s³ w w» vl w j R L ƒ w w» vl w» w j ƒ v w» ƒ» vl w š w, ƒ w d ü w w ƒ ¼ (K + M ) j j j v wš ù w ƒ y w M j j v w ƒ w d j k ƒw s³ w j N s³ w (K + M )j z (K + M ) N s³ wš w j M N s³ w š j M N s³ s³ w ƒ w R L l wš j R L w N w w (K + M) j z (K + M ) N w w š j M N w w š w s³ w, R L w Fig 3 Input images(a) and ground-truth disparity maps of input images(b) Table Detailed information of input images j» f 384 288 6 6 2 434 383 32 8 3 284 26 32 8 4 434 380 32 8 w NCC wš w j N NCC w 4 l 4 l w w C w ƒ w 4 y w w x mw w ƒ š û w x x w w w Fig 3 Middlebury w [7] œw l w w l p» (ground-truth) ùküš ƒ y f w 0-255 ü» yw tx Table ƒ ùküš x ùkü» j ƒ ƒ ùkü Table j» ƒ j» ùküš, f y (gray) ùkü wz 9«2y, 200 06
고밀도 형상 계측 시스템에서의 고속 시차 추정을 위한 3D NCC 알고리즘 기반 하드웨어 구조 4 하게 되어 특정 화소들의 특성이 잘 드러나지 않게 된 다 에서는 결과를 비트로 하였을 경우 윈도우 크기에 따른 시차 오차율을 보여준다 시차 오차율이란 기준 시차맵과의 비교 결과 시차가 이상 나는 화소 들의 비율을 의미한다 각 이미지 마다 최적의 윈도우 크기가 다 다른 듯 보이지만 에서 보는 것처럼 윈도우 크기가 작 으면 작을수록 잡음이 많고 윈도우가 크면 클수록 그 림이 일그러지는 것을 볼 수 있다 본 논문에서 제안한 구조에서는 잡음의 영향과 일그러짐 현상모두를 고려 하여 크기를 사용하였다 Fig 4 8 Table 2 Fig 4 Disparity error rates depending on the window size 2 422 2 최종 ZNCC 결과 값의 비트 수 결정 제안된 하드웨어 모듈의 시차추정 오차 본 절에서 언급할 내용은 최종 결과 값의 비 율 평가 트 수 결정을 위한 각 비트 수 별 시차 오차율 제곱근 본 절에서는 제안된 구조의 윈도우 크기 결정 세부 계산을 위한 참조 표의 입출력 비트 수 결정에 대한 내 용을 언급한다 앞에서 언급한 바와 같이 본 논문에서 적인 정밀도 결정을 위한 오차율을 분석한다 제안한 구조의 값은 항상 에서 사이의 값을 윈도우 크기에 따른 오차율 비교 가진다 이 값의 범위의 설정은 성능 및 비용의 상반관 에 큰 영향을 미친다 제안한 구조에서 최 윈도우 크기는 대표하는 화소의 특징을 나타내기 위 계 결과 값의 비트 수에 따른 해 얼마만큼의 주변 화소들까지 계산에 포함시킬 것인 종적으로 출력되는 로 나타내었다 가를 나타내는 중요한 요소이다 크기가 작으면 연산 시차 오차율을 량은 줄어들지만 잡음에 쉽게 영향을 받고 크기가 크 분석 결과를 보면 비트 수가 증가하면서 오차율의 면 연산 량도 늘어날 뿐더러 너무 넓은 범위를 다 고려 감소정도도 점점 줄어드는 것을 알 수 있다 비트 이 42 ZNCC ZNCC,, ZNCC 42 0 (trade off) ZNCC Fig 5 8 Output images for different window sizes 3 3 5 5 7 7 이미지 Table 2 5 5 2 2 35 35 2 3 4 07 J Kor Sensors Soc, Vol 9, No 2, 200
42 Á«Á yá zá Fig 5 Disparity error rates depending on the bit width of ZNCC results yƒ w 8 p w û p l txw l ƒ w 423 t j» w w t (look-up table) w w t j» w š w w w p ƒ ƒ f š ƒ j j ƒ t j»ƒ f 0 p, 8 p ƒ t w 0 p x š 3 ¾ txw w w ƒ w w 3 ¾ txw š t j» x ƒ w j» w w Table 3 t w t Table 3 t t w w ZNCC s³ ùkü š t w š w ZNCC s³ ùkü š ZNCC (8) w w s³ ü ( ) ( ) --------------------------------------------------------------------------------------------------- 00 ( ) (8) Table 4 t w w, Table 3 ZNCC average values and average ZNCC error rates when using the look-up table with a 0-bit input and an 8-bit output t s³ ZNCC r s³ ZNCC s³ ZNCC 27 2 068% 2 89 804 09% 3 222 27 032% 4 779 77 082% Table 4 Disparity error rates: (a) disparity error rates with the look-up table, (b) disparity error rates without the look-up table, (c) disparity error rates between the two disparity maps (a) (b) (c) 9% 9% % 2 4% 3% 0% 3 20% 20% 0% 4 5% 5% 0% Table 5 Disparity maps with and without the look-up table t t 2 3 4 wz 9«2y, 200 08
š 3D x d l š w NCC š» w 43 Fig 6 Required clock frequency for 30-fps processing according to the image size and the maximum disparity š w š Table 5 ùkü t ƒ š w û l, t w» w t, ZNCC š w t w 43 d w w ƒ j j w w w»» vl w v l w» ZNCC ƒ w w vl w š w y ZNCC w ( [2] )» vl» vl w ( 2) [6] w» vl w ( 3) j» w wù w ww w y w j» 2 2, 6 wù wš 8 p w š t w w š w j w š ƒ w Fig 6 j» ƒ q w 30 frame w q ùkü 20, 2 7 VGA(640 480) j» 64 30 MHz û q 30 v y w 5 l» w š 3D x d l ƒ w ZNCC» w š w w» wš w w q v» w w C» w w w š, d d w sƒ w p w mw p ƒ ú w y wš p w š, j» w mw j»ƒ w š j»ƒ j p y p ù š x ù y w, j» w w q l w m w w t j» w d d sƒ w w x ƒ w ƒ { p ùkü ZNCC» vl» w j» w w š w» y w w w g w l y» w l» w»» š w w 09 J Kor Sensors Soc, Vol 9, No 2, 200
44 š x [] ½, k 3 d w PSD, wz, 7«, 2y, pp 06-3, 2008 [2] S Perri, D Colonna, P Zicari, and P Corsonello, SAD-based stereo matching circuit for FPGAs, Proc of the 3th IEEE International Conference on Electronics, Circuits, and Systems, pp 846-849, Nice, France, 2006 [3] L Di Stefano, M Marchionni, and S Mattoccia A fast area-based stereo matchng algorithm, Image and Visioin Computing, vol 22, no 2, pp 983-005, 2004 [4] D Scharstein and R Szeliski, A taxonomy and evaluation of dense two-frame stereo correspondence algorithms, International Journal of Computer Vision, vol 47 (April-June), pp 7-42, 2002 [5] C Geogoulas, L Kotoulas, G Ch Sirakoulis, I Andreadis, and A Gasteratos, Real-time disparity map computation module, Microprocessors and Microsystems, vol 32, no 3, pp 59-70, 2008 [6] M Hariyama, N Yokoyama, and M Kameyama, FPGA implementation of a stereo matching processor based on window-parallel-and-pixel-parallel architecture, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol E88-A, no 2 pp 356-3522, 2005 [7] M Hariyama, T Takeuchi, and M Kameyama, VLSI processor for reliable stereo matching based on adaptive window-size selection, Proc of the 200 IEEE International Conference on Robotics & Automation, pp 68-73, Seoul, Korea, 200 [8] L Di Stefano and S Mattoccia, Fast template matching using bounded partial correlation, Machine Vision and Applications, vol 3, no 4, pp Á«Á yá zá 23-22, 2003 [9] L Di Stefano, S Mattoccia, and M Mola, An efficient algorithm for exhaustive template matching based on normalized cross correlation, Proc of the 2th International Conference on Image Analysis and Processing, pp 322-327, Mantova, Italy, 2003 [0] S Mattoccia, F Tombari, and L Di Stefano, Fast full-search equivalent template matching by enhanced bounded correlation, IEEE Transactions on Image Processing, vol 7, no 4, pp 528-538, 2008 [] Shou-Der Wei and Shang-Hong Lai, Fast template matching based on normalized cross correlation with adaptive multilevel winner update, IEEE Transactions on Image Processing, vol 7, no, pp 2227-2235, 2008 [2] D M Tsai and C T Lin, Fast normalized cross correlation for defect detection, Pattern Recognition Letters, vol 24, no 5, pp 2625-263, 2003 [3] k,, y, 3 ed w l e l œ w, wz, 7«, 6y, pp 48-425, 998 [4] L Di Stefano and S Mattoccia, A sufficient condition based on the Cauchy-Schwarz inequality for efficient template matching, Proc of the 2003 International Conference on Image Processing, pp I - 269-272, Barcelona, Spain, 2003 [5] L Di Stefano, Ss Mattoccia, and F Tombari, ZNCC-based template matching using bounded partial correlation, Pattern Recognition Letters, vol 26, no 4, 229-234, 2005 [6] M J McDonnell, Box-filtering techniques, Computer Graphics and Image Processing, vol 7, pp 65-70, 98 [7] http://wwwmiddleburyedu/stereo 2009 2 w»ful w (œw ) 2009 3 ~x w» fulw :SoC, Stereo Vision, ful «2003 8 š w œw w 2006 2 w œw 2006 2 ~x DGIST : l, DSP architecture wz 9«2y, 200 0
š 3D x d l š w NCC š» w 45 y 993 2 w œw (œw ) 999 2 w œw (PhD) 999 ~2002 w 2003 ~2004 2004 ~x œ w œw :SoC, l vp, j v z 996 2 ³ w œw œw 998 2 ³ w» fulœw œw 2002 2 ³ w» fulœw œw 2002 ~2005 7 m 2005 7 ~x w» (DGIST) / 2007 3 ~x û w œw : / w y,, lidar, V2V, V2Im 995 2 w œw (œw ) 997 2 w œw (œw ) 2002 2 w» œw (œw ) 2002 ~2004 w 2004 ~2005 w 2005 ~x w»fu lw :SoC, l VLSI, ful J Kor Sensors Soc, Vol 9, No 2, 200