저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할

Transcription

1 저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제 배포 전송 전시 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할수없습니다. 변경금지. 귀하는이저작물을개작 변형또는가공할수없습니다. 귀하는 이저작물의재이용이나배포의경우 이저작물에적용된이용허락조건을명확하게나타내어야합니다. 저작권자로부터별도의허가를받으면이러한조건들은적용되지않습니다. 저작권법에따른이용자의권리는위의내용에의하여영향을받지않습니다. 이것은이용허락규약 Lega Code 을이해하기쉽게요약한것입니다. Discaime

2 工學碩士學位請求論文 GPU 를사용한 Pane-conveging Beief Poagation 기반의고속스테레오매칭 Fast steeo matching based on Pane-conveging Beief Poagation using GPU 2011 年 8 月 仁荷大學校大學院 情報工學科 鄭溶漢

3 工學碩士學位請求論文 GPU 를사용한 Pane-conveging Beief Poagation 기반의고속스테레오매칭 Fast steeo matching based on Pane-conveging Beief Poagation using GPU 2011 年 8 月 指導敎授金學一 이論文을工學碩士學位請求論文으로提出함. 仁荷大學校大學院 情報工學科 鄭溶漢

4 이論文을鄭溶漢의碩士學位論文으로認定함 2011 年 8 月日 主審 印 副審 印 委員 印

5 요약 Robot vision 과같은 Comute vision 시스템에서물체까지의거리정보를획득 하는 Steeo matching 연구는다양한관점에서진행되어왔다. 특히 Steeo camea 를이용한거리정보획득방식은레이저를이용한방식에비해물체의 색상 모양 텍스처정보등을이용할수있어많은연구가진행되었다. 지금까지 의연구는상대적으로낮은정확도를개선하기위해 Adative suot weight[1] Gah-cut[2][3] Dnamic ogamming[4][5] Beief oagation[6][7][8] 등계산 이복잡한알고리즘위주의연구가주로진행되었다. 실제 Steeo matching 알 고리즘을비교연구하는 Middebu[9] 에서는 matching 알고리즘의정확도에따 른성능평가만이루어졌을뿐속도에대한비교는이루어지지않는다. 그러나 로봇 감시카메라및무인자동차시스템과같은실환경어플리케이션에거리정 보획득을위해계산량이많은기존의고성능알고리즘을적용하기에는부적합 하다. 이러한문제를해결하기위해 Fezenszwab[8] 는고성능 Steeo matching 알고리즘중하나인 Beief oagation 을다양한크기의데이터로나누어계산 하는 muti-gid 방식을적용한 Hieachica Beief Poagation 제안하였다. 그러 나 Hieachica Beief Poagation 도여전히계산량이많아서실제어플리케이 i

6 션에적용하기에는부적합하다. 따라서본연구에서는 Steeo matching 의계산 속도를개선하기위해 Beief Poagation 의수렴여부를이용한 Paneconveging Beief Poagation 을제안한다. 이방법은전역적으로데이터를업 데이트하는 Beief oagation 의단점인계산속도를개선하기위해데이터의 수렴여부를판단하고비수렴구간에서만업데이트를진행하여기존의 Beief oagation 과비슷한성능을가지고계산속도는절반으로줄였다. 또한 GPU 를이용한병렬처리방법 [14] 을사용하여실제어플리케이션에적합한고속 steeo matching 시스템을구현하였다. ii

7 목차 요약... i 목차... iii 그림목차... iv 표목차...v 1 Intoduction Singe camea mode Etinsic aamete Intinsic aamete Eioa Geomet Essentia mati Fundamenta mati Standad steeo sstem Steeo matching stuctue Matching cost Cost aggegation Disait comutation Disait Refinement Steeo matching methods Beief Poagation Hieachica Beief Poagation Pane-conveging Beief oagation Message ma Robust message ma Paae ocessing using GPU Eeimenta Resuts Concusion Refeence iii

8 그림목차 Figue 1. Human visua sstem... 2 Figue 2. Steeo matching mechanism... 3 Figue 3. Pin-hoe camea coodinate sstem... 8 Figue 4. Image and Camea coodinates Figue 5. Eioa geomet Figue 6. Standad steeo sstem Figue 7. Dua fame steeo cameaeft and Singe fame steeo cameaight. 21 Figue 8. Stuctue of steeo matching agoithm Figue 9. Sum of Absoute Diffeence Figue 10. Message udate Figue 11. Muti-scae method a Muti-gid method b Figue 12. Hieachica mode Figue 13. Hieachica BP fow chat Figue 14. Hieachica Beief Poagation Resut Image Figue 15. Pane-conveging BP fow chat Figue 16. Inut image eft & Message ma ight Figue 17. Message ma in Pane-conveging BP eft & Figue 18. Sstem achitectue of Pane conveging BP Figue 19. Message assing ocedue CPU and GPU Figue 20. Pane-conveging BP sstem on GPU Figue 21. Test Image and Gound Tuth Figue 22. Hieachica BP and Pane-conveging BP Resut Image iv

9 표목차 Tabe 1. Matching measue Tabe 2. Hieachica Beief Poagation Pocessing time & Eo ate Tabe 3. Eeimenta sstem hadwae Tabe 4. Test image oeties Tabe 5. Hieachica BP and Pane-conveging BP Resut Tabe 6. Pane-conveging BP CPU and GPU Resut v

10 1 Intoduction 스테레오매칭은두카메라로부터입력된영상의차이를이용하여각물체가 가진거리정보를구성하는연구분야로기본메커니즘은사람이좌우양안의 시각정보차이를이용하여물체의거리정보를파악하는 human visua sstem HVS[15] 와유사하다. 사람의두눈은약 6.5cm 떨어져있기때문에같은 물체를바라볼때왼쪽과오른쪽에서받아들이는영상이차이가있다. 일반적으로먼곳에있는물체일수록그차이가적으며 가까이있는물체는 위치적 형태적으로많은차이가생긴다. 이러한물체의위치에따라 [Figue 1] 에서보이는것처럼완전히안보이는영역 occusion 과한쪽에서만보이는 영역 haf occusion 이존재한다. 1

11 Figue 1. Human visua sstem 스테레오매칭은 HVS 와유사하게사람의눈대신좌우의카메라로부터얻은 이미지를이용한다. 물체의이미지를얻게되면두카메라의떨어진간격 때문에두이미지는약간다르게보인다. 즉 HVS 처럼가까이있는물체는두 이미지에서많이움직인것처럼보이고멀리있는물체는거의동일한위치에 있는것처럼보인다. HVS 에서는이러한차이를사람의뇌에서자동적으로 인지하여물체와의거리를판단하지만 스테레오시스템에서는이러한차이를 판단하기위해여러가지매칭알고리즘을사용하여물체와카메라의상대적 위치를계산하게된다. 일반적으로이러한매칭알고리즘은계산량이많으며 2

12 많은오류를포함한다. 이러한문제를해결하기위해스테레오매칭의계산 속도를줄이고 정확도를높이는연구가지금도활발하게진행되고있으며 middebu 대학의 vision 사이트 [9] 에서는이러한스테레오매칭알고리즘의 정량적평가결과를공개하여스테레오매칭연구에많은도움을주고있다. 스테레오매칭으로부터얻은거리정보는물체인식 장애물회피 물체추적 등과같은어플리케이션으로구성되어지능로봇 [10][11] 감시카메라 [12] 자동차 주행보조 [13] 등여러분야에사용된다. 다음 [Figue 2] 은스테레오매칭의대략적인메커니즘을보인다. Figue 2. Steeo matching mechanism 스테레오매칭에있어핵심은 3 차원공간에놓여있는물체에대한거리 정보를얼마나잘표현하는가에있다. 이러한스테레오매칭의방식은깊이 3

13 정보를나타내는 disait ma 을어떻게표현하는가에따라크게 dense 방식과 sase 방식으로나뉜다. 거의대부분스테레오매칭에서사용되는 dense 방식은모든픽셀이가지는 deth 를표현하는것으로입력영상의모든 부분의 deth 를나타내기때문에여러어플리케이션에서유용하게사용된다. 반면에 sase 방식은입력영상의특정한점 주로코너 엣지와같은 특징점 에서만 deth 를구하는방식으로 dense 방식에비해속도는빠르지만 연속적이지못하고부분적인 deth 정보만을나타내기때문에사용되는 어플리케이션이한정된다 [16]. 스테레오매칭방법은매칭값의계산을얻는방식에따라 oca 방식과 goba 방식으로구분할수도있다. Loca 방식은픽셀의특정위치주변의 정보만을사용하여 disait 를계산하는것으로대표적인방법으로는 aeabasedwindow-based 방법과 featue-based 방법등이있다. 이러한 oca 방식은일반적으로 goba 방식에비해속도는빠르지만많은에러를포함한다. 반면에 goba 방식은 disait 계산을위해영상의모든픽셀값을사용하는 것으로대표적인방법으로는 beief oagation dnamic ogamming gahcut 등이있으며 일반적으로정확도는높은편이나계산량이많아속도가느린 편이다. 이러한스테레오알고리즘중 Beief PoagationBP 은 Makov andom fiedmrf 을기반으로한훌륭한근사법으로스테레오나이미지복구같은 문제를해결했다. 이러한접근방법이정밀한결과를도출하는데유용하지만 4

14 상당히많은계산량을요구한다. 이는 BP 가반복적인계산으로에너지최소화를 구성하기때문이다. 그럼에도불구하고 BP 알고리즘은우수한성능가지기 때문에 segmentation[17] sub-ie anasis[18] 등의기술과융합되어사용되고 있다. 그러나이러한기술들은스테레오의성능을높이기위한기술로개발되어 우수한성능을가지지만여전히많은계산량을가진다. 본논문에서는여러알고리즘에기반이되는 BP 알고리즘의속도를개선하기 위해일정한값으로수렴한데이터값을제외하고나머지부분에서만최적화를 진행하여계산량을줄이는 Pane-conveging BP 알고리즘을제안하였다. Paneconveging BP 알고리즘은 muti-gid 방식을사용하여데이터를여러크기의 계층으로줄이고각계층에서수렴여부를판단하는메시지 ma 을생성한다. 이후생성된메시지 ma 을이용하여비수렴구간에서메시지패싱을이용하여 데이터의신뢰도를높이게된다. Pane-conveging BP 는기존의알고리즘에 비해 2 배이상의속도향상을보였고이를 CUDA 로적용하여고속으로 처리됨을증명하였다. 본논문은다음과같이구성되어있다. 2 장에서는스테레오비전시스템을 구성하고있는카메라의특성에대해설명하고 3 장에서는스테레오알고리즘을 설명하기위한 eioa geomet 에대해설명한다. 4 장에서는일반적인 스테레오시스템을언급하고 5 장에서는스테레오매칭의구성에대해서 설명한다. 6 장에서는기본적인 BP 알고리즘과 Hieachica BP 알고리즘을 설명하고이를개선하여크게반복성을줄인 Pane-conveging BP 알고리즘을 5

15 제안한다. 7 장에서는 Pane-conveging BP 알고리즘을 GPU 를사용하여병렬화 하였음을보인다. 8 장에서는제안한알고리즘과기존알고리즘과의비교를통한 성능평가를하였고 마지막으로 9 장에서는결과분석과향후개선사항에대해 논의한다. 6

16 2 Singe camea mode 스테레오시스템은일반적으로두대의카메라로구성된다. 따라서카메라의 특성에대해알아볼필요가있다. 여기서는간단한카메라모델인핀홀카메라 모델에서 3 차원공간상의물체와이미지평면상의관계를알아본다 [19]. 카메라가물체를보게되면물체는카메라의이미지평면상에투영된다. 공간 상의물체는 3 차원에존재하고 이미지평면상물체는 2 차원에서존재하기때문 에각각의좌표계에대한이해가필요하다. 여기서공간좌표계 wod coodinate 는카메라의특성및위치에독립적이며공간상물체의좌표를나타 내는데사용된다. 또한카메라좌표계 camea coodinate 는이미지평면상물체 의위치를나타내기위해사용하는좌표계로이두좌표계는이동 tansation T 과회전 otation R 을이용하여서로변환가능하다. 다음 [Figue 3] 과같은핀홀카메라모델을가정하자. 여기서카메라는공간 상의점 P 를보고있으며점 P 는어떤좌표계를선택하느냐에따라다르게표 현될수있다. 공간좌표계에서는 PW 이며카메라좌표계에서는 PC 이다. 카메 라좌표계에서점 P 는이미지평면 Π 에점 로서나타난다. 카메라중심점 OC 에서평면 Π 을지나는선중평면에수직인직선과평면이만나는점이주 점 incia oint o 이며이주점과중심점 OC 과의거리가초점거리 f 이다. 7

17 Figue 3. Pin-hoe camea coodinate sstem 카메라좌표계에서점 P 와점 는다음과같이정의된다. T T P = [ X Y Z] = [ z] 1 광축 otica ais 은이미지평면에수직이므로 와 C C 는닮은 o O C O PO 꼴이다. 또한 z = f 이므로우리는다음과같은식을얻을수있다. X Y = f = f z = Z Z f 2 위의식 2 는핀홀카메라모델의기초를구성한다. 8

18 2.1 Etinsic aamete 공간상의물체를이미지평면상에수학적으로표현하는것은카메라좌표계를 사용하는것으로간단히해결된다. 그러나카메라가여럿일경우각카메라의 정확한위치에따른수학적관계를정의해야한다. 카메라좌표계 C 를외부의공간좌표계 W 로변환하는것은이동 T 과회전 R 으로가능하다. T 는좌표계의중심 OC 와 OW 를바꾸는것이고 R 는다른 좌표계의축으로방향을맞추는것이다. 공간상의점 P 를카메라좌표계 C 와공간좌표계 W 의관계로표현하면다음과같이된다. P = W R P T C 3 위의식 3 을사용하여공간상의점 P 를이미지평면상에표현한 PC 는공간 좌표계의 PW 로변환할수있으며반대도가능하다. 따라서행렬 R 과 T 를 카메라의 etinsic aamete 라고한다. 2.2 Intinsic aamete 앞서언급한 etinsic aamete 가공간상좌표와카메라의이미지평면 좌표의관계를나타낸다면 intinsic aamete 는카메라이미지평면좌표와 실제 CCD 를통해서나온이미지좌표와의관계를나타낸다. 우리가가정한핀홀 모델에서확장하여카메라렌즈로부터물체를받아들여 CCD 로읽어이미지로 9

19 나타내는모델을생각해보자. 핀홀모델의경우이미지평면의중심점을 원점으로사용하지만 실제이미지의경우에는왼쪽상단이이미지의원점이다. Figue 4. Image and Camea coodinates 카메라좌표의점 를이미지좌표의점 로변환하기위해 우선크기를맞추어야한다. 여기서사용되는 scae facto s s s 는이미지의 픽셀크기에의존하는상수이다. s s s = 0 0 s 4 10

20 카메라좌표에서사용하는원점은주점을사용하고이미지좌표에서사용하는 원점은일반적으로왼쪽상단코너의점을사용하므로크기변환된 를이미지좌표로변환된주점의위치 o o o s s s 한다. 만큼이동시켜야 = s = s o o 5 따라서전체적인변환식은다음과같다. s 0 o = = 0 s o = M 여기서 M 은카메라좌표상의점 를이미지좌표상 로변환시켜주는 intinsic 행렬이다. 앞서설명한 intinsic aamete 는실제카메라환경중 CCD 의특성을 고려한것이다. 하지만실제카메라시스템에서는이와같은기본적인특성 외에도광학적요소에따른비선형적수차가생긴다 [20]. 이런수차는구형 표면의렌즈에서렌즈의광축에평행하게입사한광선이한점으로모이지않는 구면수차 Sheica abeation 빛의파장에따라유리의굴절률이달라져 11

21 초점이달라지는색수차 Chomatic abeation 렌즈의광축에서벗어난 지점에위치한광원에의하여광축에서멀어지는혜성과같은이미지가 형성되는코마수차 Coma 주축에서떨어져있는물체의상이완전한점이 되지않고고리모양또는방사형으로흐릿해지는비점수차 Astigmatism 평면상의광원에의한이미지의초점면이곡면이되는만곡수차 Cuvatue of fied 렌즈의기하구조또는결함에의하여이미지가왜곡되는왜곡 수차 Distotion 가있다. 이러한수차는대부분렌즈제작시제거되며렌즈에 따라 1~2 개의수차가존재하게된다. 12

22 3 Eioa Geomet 다음 [Figue 5] 는스테레오매칭의기하학적모델 eioa geomet[21] 을 표현한것으로두개의핀홀카메라모델을기반으로구성되었다. 이러한핀홀 카메라모델은각각투영중심점 O k 을가지는투영평면 Π k 여기서 k 는 왼쪽에서는 오른쪽에서는 로바뀐다 을구성한다. 점 Ok 를지나고평면 Π k 에수직인직선에서평면 Π k 위의점을주점 incia oint 이라한다. 이 점과중심점 Ok 까지의거리가초점거리 f 이다. 중심점 O 와 O 를이은선 OO 를 base ine 이라고하며이때 base ine 과평면 Π k 가만나는점을 eioa ointeioe ek 이라한다. Figue 5. Eioa geomet 13

23 3차원공간상에서주어지는점 P 와중심점 O 와 O 에의해구성된평면을 eioa ane Π e 라한다. Eioa ane Π e 는이미지평면 Π Π 과 직선으로교차하며그교차되는선을 eioa ine u i 이라고한다. 예를들어 3차원공간상 P 의이미지 를분석한다고하자. 중심점 O 과왼쪽이미지 상의점 에의해선 O 이형성되고이것으로 3차원공간상점 P 는점 뿐만아니라 O 에놓인다른점또한나타내고있음을알수있다. 이것으로 점 P 에대한위치적특성은알수있으나공간적특성을알기엔부족하다. 이러한공간적특성을파악하기위해다른위치에서본두번째이미지가 필요하다. 중심점 O 에서점 P 를본다면평면 Π 에이미지 가생성된다. 이렇게생성된선 O 는선 O 과점 P 에서교차되고 이교차점은각 이미지평면 Π Π 위의 eioa ine 상에존재하게된다. 이로서다음의 제약이성립한다. 공간상점 P 를나타내는이미지평면위의점 P k 는상응하는 eioa ine 에만존재한다. 위의제약으로인하여 이미지에서공간적특성을모르는점을찾을때 eioa ine 상에서만검색하는것이가능하게된다. 일반적으로이러한 eioa ine 의위치는사전에알수없지만 caibation 된스테레오카메라 같이특정한카메라환경상에서는정해져있다. 14

24 3.1 Essentia mati 스테레오카메라시스템에서각카메라는독립된좌표계를가지며이중 Z 축은카메라의광축과일치한다. 각좌표계에서벡터 P = [ X Y Z ] T 과 T P = [ X Y Z ] 는 3차원공간상의점 P 를나타내며이는각이미지 평면상에점 = [ z ] T 과 = [ z ] T 로나타난다. 여기서각 카메라는외적인파라메터 etinsic aamete 에의해외부좌표계 etena coodinato 로표현가능하다. 이좌표계는이동 tansation T = O O 과 회전 otation R 을사용하여하나의좌표계에서다른좌표계로전환이 가능하다. 따라서공간상의점 P 를나타내는두벡터 P 과 P 는다음처럼 표현된다. P = R P T 7 왼쪽카메라좌표계에서 eioa ane Π e 은두벡터 T 와 P 에걸쳐 san 있다. 따라서벡터 P T 는이평면에속한다. 이를결합하여내적을구하면 0 이된다. T T P = 0 P 8 15

25 16 위의식에서외적부분은행렬 A 와 P 의곱으로나타낼수있다. P P P T T T T T T T P P T T P P T P T P T P T T P P T T P P T P T P P P T T T AP k j i k j i P T = = = = = 여기서 T T T 1] 0 [0 0] 1 [0 0] 0 1 [ = = = k j i 는단위 unit 벡터이며 A 는반대칭 skew smmetic 매트릭스이다. 식 7 과식 9 을식 8 에대입하면 0 1 = T P AP R 10 이식을정리하면다음과같이된다. = 0 T AP P 11 = 0 T EP P 12 여기서행렬 E 는

26 E = RA 13 이며이것을 essentia 행렬라부른다. 3.2 Fundamenta mati 앞서언급한식 2 에의해 P 와 그리고 P 와 는교환가능하고 식 12 는다음과식 14 과같이쓰일수있다. T E = 0 14 대응되는점은대응되는 eioa ine 에만놓여있기때문에 식 14 의 E 는 점 를통과하는오른쪽이미지평면상의 eioa ine 의식이된다. 따라서 두 eioa ine 은다음과같이표현된다. u = E 15 T u = E 16 주어진점 k 를이미지좌표에서찾기위해식 6 을사용하면 17

27 M ik k = 17 k 여기서 Mik 은좌우이미지에서의 intinsic 행렬이고 k 는카메라 좌표계의점이며 k 는이미지좌표계의점이다. 식 17 을식 14 에적용하면 1 T 1 EM = 0 M 18 i i T T 1 M EM = 0 19 i i 결국 위의식 19 는다음과같이된다. T F = 0 20 여기서행렬는 fundamenta 행렬이라하며다음과같이표기한다. F 21 1 = M T EM i i 18

28 4 Standad steeo sstem 다음 [Figue 6] 과같은카메라의 Eioa ine 이수평으로일치하는표준 스테레오시스템을가정하자. 이러한시스템은이미지평면 Π Π 이 수평적으로존재하며가장흔히사용되는스테레오시스템이다. 여기서 oo 과 PXO 그리고 oo 과 PXO 는닮은꼴삼각형이다. 따라서우리는두점 과 에대한수평 disait D 의공식을 얻을수있다. D = = = bf Z 22 여기서점 T T = [ ] = [ ] 는 3차원공간상의점 P 가 이미지평면상에나타내는점이고 b 는카메라사이거리 f 는카메라초점 거리 Z 는 base ine 과점 P 의거리이다. bf / Z 가양수이기때문에 이다. 이때문에 eioa ine 에서검색범위는일정수준으로제한되며매칭 알고리즘을단순해진다. 19

29 Figue 6. Standad steeo sstem 위의식 22 와마찬가지로우리는다음과같은수평 disait 에대한정의를 내릴수있다. D = 0 23 = 하지만이미지평면이수평적존재하게되어두이미지평면의 eioa ine 이일치하므로 D 는 0 이된다. 위의식 22 와 23 에서보이는것처럼한쪽이미지평면의점의좌표는다른 이미지평면에서점의좌표와차이가발생할수있다. 이러한차이로인하여 20

30 물체와의거리 Z 에대한정보를얻을수있게된다. 이러한표준스테레오시스템에서카메라는다음 [Figue 7] 과같은모델이 사용된다. 독립적인두대의카메라를사용하는 dua fame steeo camea 의 경우이미지평면을수평으로설정하기위해 intinsic aamete 를동일하게 구성해야하며 etinsic aamete 의경우 축과 z 축의위치를동일하게만든 상태에서 축의위치만을변형시킨모델로구성해야하기때문에초기설정에 시간과노력이많이들어간다. 하지만카메라설정이자유롭다는장점이있다. 반면에 intinsic aamete 와 etinsic aamete 의설정이끝난 singe fame steeo camea 의경우초기설정이필요없다는장점이있지만 구성변경이 불가능하다. 스테레오시스템에서 base ine 의길이는측정할수있는 deth 를 결정하기때문에이러한카메라시스템에서는측정가능한거리의제한이 존재하게된다. Figue 7. Dua fame steeo cameaeft and Singe fame steeo cameaight 21

31 5 Steeo matching stuctue 본절에서는스테레오매칭의구성에대하여알아볼것이다. 일반적으로 스테레오매칭알고리즘은다음 [Figue 8] 과같은 4 단계과정을거쳐 수행된다 [22]. 이러한과정은알고리즘에따라생략되기도하고통합되기도하며 변형되기도한다. Figue 8. Stuctue of steeo matching agoithm 22

32 5.1 Matching cost 스테레오매칭에있어서매칭값을결정하는것은매우중요한과정이다. 왼 쪽이미지와오른쪽이미지의매칭정도를판단하기위해여러가지방법이사 용되지만가장일반적으로사용되는것은픽셀간의차이를이용하는방법이다. 스테레오매칭방법중하나인 aea-based 방식에서는입력된좌우이미지에서 eioa ine 을따라상응하는픽셀주변의값들을비교하여일치하는지점을 찾는다. 이러한 aea-based 방식중하나인 SADSum of absoute diffeence 를 예를들어보자. 왼쪽이미지 I 에서좌표 에해당하는픽셀주변값 I i j 과이에상응하는오른쪽이미지의픽셀주변값 I i j 은서로일치할수있지만다를수도있다 여기서 j i 는 aea 의크기 N 에따라결정된다. 이는앞서설명한대로 3 차원공간상위치에따라 왼쪽과오른쪽이미지에서물체의위치가달라지기때문인데 이를극복하기위 해 eioa ine 상에서매칭값이가장유사한픽셀의위치를찾게된다. SAD 는가장유사한매칭값을찾기위해오른쪽이미지를 d d 만큼움직인뒤왼 쪽이미지주변픽셀값들과오른쪽이미지주변픽셀의값차이의절대값을더 하여해당위치에서매칭값을계산한다. 이렇게구한매칭값들중가장작은 값을유사한값이라가정하여해당픽셀의거리 왼쪽이미지와오른쪽이미지가 일치하는점까지거리 를구한다. 여기서표준스테레오방식을사용하면 d 는 왼쪽과오른쪽이미지의 eioa ine 은수평으로일치하므로무시할수있다. SAD 의대략적개념도는 [Figue 9] 와같다. 또한이와유사한 ZSADzeo mean 23

33 sum of absoute diffeence 방식은 aea 의평균값 I 과픽셀주변값 I i j 의차이를이용하여 SAD 를적용한방식이다. 매칭값을구하는 대표적인방법은다음 [Tabe 1] 와같은방식이사용된다 [15]. Figue 9. Sum of Absoute Diffeence 24

34 25 Tabe 1. Matching measue Matching measue Sum of absoute diffeence = N j i SAD j d i d I j i I D Zeo mean sum of absoute diffeence = N j i ZSAD d d I j d i d I I j i I D Sum of squaed diffeence 2 = N j i SSD j d i d I j i I D Zeo mean sum of squaed diffeence 2 = N j i ZSSD d d I j d i d I I j i I D Nomaized sum of squaed diffeence 2 2 = N j i N j i NSSD j d i d I j i I j d i d I j i I D Zeo mean nomaized sum of squaed diffeence 2 2 = N j i N j i ZNSSD d d I j d i d I I j i I d d I j d i d I I j i I D

35 5.2 Cost aggegation 스테레오이미지에서매칭값의계산은대부분스테레오 coeation 으로구 성되어있다. 그러나단지밝기값만을사용하는것은많은한계가있다. 그첫 번째는실제적으로밝기값은제한된값으로만 보통 0~255 표현된다는것이다. 그렇기때문에식별성이제한되게된다. 그다음문제는밝기값에노이즈가포 함되어있다는것이다. 다른종류의노이즈가더해져매칭값에추가적인에러 가발생하게된다. 이러한문제를해결하기위해이미지처리또는적합한측정 방식이사용된다. 일반적인방식은하나의밝기값을사용하기보다는픽셀주 변의이웃픽셀값으로부터얻은밝기값을사용하는것이다. 가장일반적인사 전처리단계는밝기를 nonaametic 공간으로변환시키는것이다. 여기서픽셀 은인접한주변픽셀의관계로설명된다. 비선형변환의다른예로는 Log-oa 변환이있다. 두번째가능성은계산하는이미지영역에서몇몇의밝기변화를 설명하는측정방법을사용하는것이다. 이방법은각매칭된픽셀에서계산하는 이미지영역의평균값을빼주는것이다. 이방법또한하나의픽셀보다넓은 영역에서얻은값을사용한다. 하나의픽셀만을가지고비교하는것은식별성이제한되기때문에연관된이 웃픽셀의정보를사용할필요가있다. 이처럼매칭하는픽셀과관계된지원영 역내의주변픽셀의값을이용하는것을매칭값통합이라한다. 가장간단한통합절차는지원영역내에서 ow-ass 필터링을하는것이다. 이것은 unifombo fite binomia Gaussian 또는 convoution 커널등을이용한 26

36 convoution 에의해수행될수있다. 이것은또한이미지내용에맞추어지원 영역을조정하는형태가될수도있다. 가장간단한방법은각위치에서다른 크기의지원영역을사용하는것이다. 이것은약간씩다른위치에서다양한크 기의윈도우를조정하여구성된다. 분리된그룹은통합과정을위한반복적분 산방식을적용하는방법으로여겨진다. 5.3 Disait comutation 이단계에서는 disait 를결정하며이는크게지역적인방법과전역적인방 법으로구분된다. Disait 는두이미지 I I 의밝기 색상값 기하학적관계 등을이용하여앞서언급한 matching cost 로결정된다. 지역적최적화에서 disait 값은해당픽셀주변의값 window 으로계산된다. 즉통합값은지역매칭영역내의값만을포함하게된다. 지역영역은가장우 수한매칭값을찾기위해사전정의된범위내에서움직여진다. 이렇게찾아진 가장우수한매칭점까지움직인값이 disait 가된다. 그러므로이런전략은 흔히 winne-takes-awta[23] 접근이라고알려져있다. 이러한접근의문제점 은매칭점이여러위치에서매칭될수있음에도불구하고입력이미지부터매 칭의유일성이획득된다는것이다. 이러한문제는 coss-check[24] 절차에의해 해결될수있다. 간혹가장우수하다고선택한매칭값이문제투성이일수있기 때문에 coss-check 에서는매칭값함수내에서적합한하나의값만을선택하지 않는다. 27

37 전역적최적화는 disait 값을찾기위해모든지역매칭값과다른제약들 을동시에가질수있기때문에일반적으로지역적최적화에비해강력한기술 이다. 때문에모든매칭값은최적화작업에포함되고통합단계는일반적으로 생략된다. 전역적최적화처리를형성하기위한일반적인접근은 disait 함수 를포함하는에너지함수로설계하는것이다. 스테레오매칭을위한에너지함 수는다음과같이표현된다. E θ E data θ E θ = 24 smooth 여기서 θ 는에너지값에영향을주는파라메터로정의된다. E θ data 는매칭 된픽셀값을가지는 disait 값과관계있다. 이것은지역적매칭값의합처럼 표현될수있다. E data = θ 25 S D I 여기서 S D 는매칭값으로정의된다. 보다일반적으로 E θ 는 θ 와입력된관측데이터사이불일치정도를나타낸다. data Esmooth θ 는결과의 smoothness 를부과하기위한부분이다. 즉 결과 disait ma 에추가적인제약부분이다. 이것은보통 disait 의함수이나 28

38 간혹추가적으로이미지밝기의함수와연관된다. 즉이것은다음과같이표현 된다. E θ = Φ D 26 smooth I 여기서 Φ D 는 disait gadient 의함수이다. 위의식은 Schastein and Szeisk[25] 에의해다음과같이표현되었다. E smooth = θ 27 f D D 1 f D D 1 I 여기서 f 는단조증가함수이다. f 의선택은 disait ma 의결과정확 도에영향을미친다. 즉 f 가 2 차함수라면 disait 는물체의외곽에서부드 럽게될것이다. 5.4 Disait Refinement 이단계는앞서언급한단계들에의해출력된 disait ma 을개선하는단계 이다. 여기에는몇가지방법이사용된다. Subie anasis 해당픽셀과주변픽셀의매칭값이불연속이기때 문에이를해결하기위해보간법 inteoation 을사용하여 disait 29

39 의 subie 을보정한다. Disait veification disait 값을결정하는데있어 matching 되는 값은일반적으로하나이상일또는몇개의후보값을가지게된다. 이러한값들중좀더정확한값을결정하기위해 coss check 와같 은방법이사용되게된다. Fiteing of disait vaues 출력된 disait 값은여러가지 noise 들에의해그값이정확하지않게된다. 이러한이유로잘못된매칭 결과가나오게되는데이러한값들중어느한부분에서높게나오거 나낮게나오는값들을 median fite 등을사용해서줄인다. 30

40 6 Steeo matching methods 스테레오매칭알고리즘은크게지역적방식과전역적방식으로나뉜다. 지역 적방식은각픽셀에서 bock 또는 window 를통하여최적의값을가지는 disait 를선택하는것으로 Nomaized coss-coeation[26] Rank tansfom[27] 등의 Aea-based 방법이일반적이며수행속도는빠른편이나희 미한영역과물체의외곽과같은영역에서노이즈를발생시키는문제가있다. 전역적스테레오매칭은해당픽셀과주변값을이용하는 oca steeo matching 과달리 disait 값을결정하기위해주어진데이터의값의주변값 을이용하여에러를줄이는업데이트과정을거치고주변값은다시그값의주 변값에의해데이터가업데이트된다. 즉하나의데이터를업데이트하기위해 주어진데이터를전역적으로이용하는방법이다. 이러한전역적방법은 Gahcut[2][3] DPDnamic ogamming[4][5] BPBeief oagation 등의알고리즘 을사용한다. 일반적으로전역적방법은반복적계산을통해에러를줄여가므로 oca steeo matching 에비해계산량이많고복잡하다. 본절에서는전역적스 테레오매칭기법중 Beief oagation 을이용한스테레오매칭에대해여알 아본다. 6.1 Beief Poagation BPBeief Poagation[6] 알고리즘은현재픽셀과주변픽셀의연속성을업데 이트하기위해이웃픽셀의정보를통합하고전역에너지의최소화에도달하기 31

41 위해연속성을반복적으로업데이트하여최적화하는알고리즘이다. 이를위해 에너지함수적인측면으로접근한 MRFMakov andom fied 모델에기반하여구 성되었으며이는수식적으로앞서언급한식 24 와유사하게표현된다. E f E f E f = 28 data smooth 여기서라벨 f 는픽셀이가지는데이터값의확률값이며위식 28 은 f 에 서데이터부분 E data f 과연속성부분 f E smooth 으로나뉘며이는다음식 29 과같이표현될수있다. P E f = D f V f f 29 q N q 여기서 P 는픽셀들의집합이고 는 P 에속하는픽셀 f 는픽셀 에해 당하는라벨 N 은픽셀 의 4 방향이웃픽셀이다. 앞의식 29 에서데이터부분 D f 는상응하는픽셀의밝기차이로나타 내며다음식 30 과같이표현된다. D f = λ min I I f τ 30 i 32

42 여기서 I I 는각각왼쪽과오른쪽입력이미지이며 는픽셀좌표 λ 는 데이터의크기를결정하는 Scae facto 이고 τ 는데이터값을제한하는 q tuncate 상수이다. 연속성부분 V f f 는주변픽셀의라벨값차이를이 용하여 disait 의연속성및불연속성을나타내며여기서는식 31 과같은 tuncated inea mode 을사용한다. V f f = min f f d 31 q q 여기서 d 는라벨값을제한하는 tuncate 상수이다. BP 알고리즘은식 29 의에너지함수를최소화하는라벨값을구하기위해 주변픽셀들간의연속성을고려한메시지를구성하여전달하고업데이트를반 복함으로써라벨값들에대한신뢰도를향상시킨다. 메시지는주어진라벨의인접 4 방향픽셀에대해구성되며최대 disait k 에의해주어지는차원의벡터이다. t m q 는픽셀 에서이웃하는픽셀 q 로 t 번반복해서보내는메시지를나타내며각메시지의초기값 0 m q 는 0 으로 초기화된다. 각반복에서계산되는메시지는다음식 32 와같다. m t q t 1 f q = min V f f q D f ms f 32 s N \ q 33

43 여기서 N \ q 는 q 를제외한 의이웃픽셀이다. Figue 10. Message udate 이러한메시지의전달을통한업데이트는 [Figue 10] 과같이수행된다. 반복 t 에 에서 q 로보내지는메시지 m 는이전반복 t 1 에서 q 를제외한 t q 주변픽셀로부터받은메시지값 m 1 t s 을이용하여현재상태를업데이트한뒤 메시지를 q 로보내게된다. 이러한과정을통해해당픽셀 에대한차원벡터 k 를구성한뒤각요소의값을통합하여픽셀 에서의최소에너지를추정 한다. 6.2 Hieachica Beief Poagation BP 알고리즘은성능이우수하나반복적인메시지전달과업데이트로인하여 34

44 수행시간이많이소요된다. Fezenszwab[8] 은기존의 BP 알고리즘의속도개선 을위해 Muti-gid 방식을이용한계층간영상에서메시지를업데이트를수행하 여주목할만한속도향상을이루었다. 여기서사용되는 Muti-gid 방식은컴퓨터비전에서일반적으로속도개선을 위해사용하는 Muti-Scae 방법같이이미지의해상도를낮추지않는다. 단순히 이미지의해상도를낮추게되면구별가능한 disait 또한줄어들기때문에계 층적 BP 알고리즘에서는다음 [Figue 11] 와같이이웃하는픽셀의라벨의값을 더하여구성한다. 이러한방식을통하여계층적 BP 알고리즘은데이터의손실 없이여러개의계층을구현하게된다. 35

45 Figue 11. Muti-scae method a Muti-gid method b 계층적 BP 알고리즘은주어진입력영상에서픽셀간의밝기차를이용하여 Initia disait 즉데이터부분 Data tem 을구한다. Data tem 의값을기반으로 중심픽셀과주변의픽셀 상 하 좌 우 을이용하여 data 를반복적으로업데이트하 게된다. 이것이일반적인 Beief Poagation 알고리즘을적용한스테레오매칭 기법이다. 그러나이러한방법은계산량이많아서고속스테레오매칭에는적합 하지않다. 따라서 Hieachica BP 에서는이러한속도문제를해결하기위해 36

46 muti-gid 방식을사용하였다. 이방법은입력데이터를여러단계로순차적으 로줄여계산하기때문에계산속도의향상을가져온다. 이를위해 initia disait 를 0 번째계층으로구성하고이렇게구성된 0 번째계층을이용하여 1 에서 4 까지의계층으로구현한뒤최상위계층 eve 4 에서의메시지업데이트를 반복실행하여연속적부분의값 smooth tem 을구한다. 그다음하위계층으 로크기를확장시켜메시지업데이트를반복한다. 0 번째계층에서메시지업데 이트가끝난후데이터부분과연속성부분의값을통합하여 disait ma 을 얻는다. 이렇게구성된계층은다음 [Figue 12] 과같고계층적 BP 의순서도는 다음 [Figue 13] 과같다. Figue 12. Hieachica mode 37

47 Figue 13. Hieachica BP fow chat 앞의 [Figue 13] 에서보이듯이계층적 BP 알고리즘은크게초기데이터계산 과정 E data f 과메시지패싱과정 f E smooth 으로구분된다. 초기데이터계산 과정은입력받은이미지 I I 로부터 matching cost 를계산하는과정으로 이를초기데이터값으로규정하고기본적인확률값으로삼는다. 이를 이용하여주변픽셀에메시지값을전달하고업데이트하는과정이메시지패싱 과정이며이과정을반복하여각픽셀이가지는라벨데이터의신뢰도를높인다. 위의순서도중메시지패싱앞에 muti-gid 방법을이용한 data educing 과 메시지패싱이후 data etending 과정은 BP 를계층적으로구성하여전역적 38

48 스테레오매칭방식에서문제가되는계산속도를줄이게된다. 다음 [Figue 14] 는계층적 BP 의결과영상이며 [Tabe 2] 는수행속도와 에러율을나타낸다. Figue 14. Hieachica Beief Poagation Resut Image Tabe 2. Hieachica Beief Poagation Pocessing time & Eo ate 6.3 Pane-conveging Beief oagation 계층적 BP 알고리즘은기존의 BP 알고리즘의계산시간을크게줄였으나 Inte Coe 2 Quad 시스템에서 크기의이미지 Tsukuba 에대한 수행시간이약 1.6 초로고속어플리케이션에적용하기에는적합하지않다. BP 알고리즘은메시지를반복적으로업데이트하면서각라벨에할당된 39

49 에너지를최소화시킨다. 이렇게최소화된값은일정수준의반복이후 수렴하여더이상변하지않게된다. 그러나일반적인 BP 알고리즘에서는 이러한수렴여부와는상관없이전역적으로메시지를업데이트하여불필요한 계산을하게된다. 이러한문제를해결하기위해본논문에서는계층적 BP 알고리즘에서사용된 Muti-gid 방법을이용하여각계층에서의수렴구간을 메시지 ma 으로나타내고 이 ma 을이용하여불필요한계산을줄이는 Pane-conveging BP 방법을사용하여반복적인계산량을크게줄였다. Muti-gid 방법을이용하여구성한각계층에서각라벨이가지는에너지 값을 E L f 라하자. 여기서 L 은계층값이다. 각계층에서의라벨의데이터 부분과연속성부분으로나타내는에너지함수는다음식 33 처럼표현된다. E f E f E L L data L smooth f = 33 Hieachica BP 방법은위식 33 을이용하여최상위계층에서메시지패싱을 통한에너지최적화를하고이값을하위계층으로확장하여다시하위 계층에서메시지패싱을통한최적화를진행하게된다. 그러나이렇게진행해 가면서일부라벨에서의에너지는수렴하게된다. 3 번째계층에서라벨 f 가 가지는에너지값을 E f L3 라하고 2 번째계층에서가지는에너지값을 E f L2 라하자. Hieachica BP 에서는각계층에서에너지최적화를위해 메시지패싱과정을 5번반복한다. 그런데이반복을계속해서진행하게 40

50 되면 t 다음식 34 과같은일정한수렴값 α 에도달하게될것이다. im L3 f =α t E 34 여기서 t 는각계층에서메시지패싱반복횟수이다. 위식 34 처럼라벨 f 가일정한값으로수렴하게되면이후계층에서는몇 번의메시지패싱과정을거쳐도값이변하지않게된다. if E E L3 L2 f f = α = E L3 f 35 이방법을이용하여수렴이된라벨을찾아내고그부분에서의메시지 패싱과정을생략하게되면보다더효율적인계산이된다. 그러나실제적으로 수렴값을얻기위해메시지패싱을계속해서반복할수는없다. 마찬가지로 많은수의반복을한다고할때 계산량이너무많아져서비효율적이다. 따라서 본연구에서는메시지패싱횟수를일정수준으로고정하고각계층에서중간 결과값을추출하였다. 이렇게추출된계층간결과값을비교하여차이가 없다면해당라벨 f 는수렴한다고가정하였다. Pane-conveging BP 방법은식 35 을이용하여상위계층에서중간결과를 추출하고차상위계층에서의중간결과와비교하여비수렴구간을나타내는 41

51 메시지 ma 을만든다. 이후비수렴구간주변의라벨까지메시지패싱을하는 강화한메시지 ma 을생성한뒤 ma 정보를하위계층수준으로확장하여 하위계층에서의메시지업데이트과정에적용함으로계산량을줄인다. 이에 대한순서도는다음 [Figue 15] 과같다. Figue 15. Pane-conveging BP fow chat 42

52 6.3.1 Message ma 식 35 에서와같이라벨에할당된에너지값이수렴하게되면이후의반복적 메시지업데이트과정을수행하여도그값이변하지않는다. if E E L4 L4 f f = E = E L3 L3 f f = E L2 f = E L1 f = E L0 f 36 따라서각라벨 f 에서의수렴여부를판단하는메시지 ma M f L43 은각 계층에서의중간결과값들의차이를이용하여구성된다. M f EL4 f EL3 f = 37 L43 식 37 에의해계층 4 에서라벨이가지는에너지값과계층 3 에서가지는 에너지값이같지않다면이는수렴하지않았다고가정하여계층 2 에서메시지 패싱을통한에너지최적화과정에들어간다. 식 37 을이용하여계층 4 와계층 3 의메시지 ma 을구성하여계층 2 에서에너지최적화에적용하고이렇게 구한계층 2 에서의결과와이전에구한계층 3 에서의결과를이용하여계층 1 에서의에너지최적화에적용한다. 이러한방식을최하위계층까지적용하여 수렴하지않는부분에서만메시지패싱과정을적용함으로써계산량을줄였다. 43

53 다음 [Figue 16] 는식 37 을이용하여계층 3 과계층 2 에서의중간결과 값으로구성한메시지 ma 이다. Figue 16. Inut image eft & Message ma ight [Figue 16] 에서검정색으로표현된부분은수렴구간이고하얀색으로표현된 부분은비수렴구간이다. 메시지 ma 을보면알수있듯이하얀색으로표현된 데이터의비수렴구간은입력영상에서물체의외곽선부분에집중되어있음을 알수있다. 이는스테레오영상의특성상물체의연속성이물체의외곽선 부분에서나뉘기때문이다. 따라서이러한부분에서의에러를줄이기위해 구성된메시지 ma 을하위계층크기로확장하여적용함으로써불연속 부분에서의계산을진행하고수렴된부분에서의계산을제한한다. 그러나이러한방법은상위계층에서만들어진메시지 ma 을바탕으로하위 계층의메시지업데이트를진행하기때문에놓치는부분이생겨원래의 BP 알고리즘에비해에러가증가하게된다. 44

54 6.3.2 Robust message ma 전역적으로메시지업데이트를진행한 Hieachica BP 의메시지 ma 과 비수렴구간에서만업데이트를진행하는 Pane-conveging BP 의메시지 ma 은다음 [Figue 17] 처럼약간의차이가존재한다. Figue 17. Message ma in Pane-conveging BP eft & Message ma in Hieachica BP ight 이는 Pane-conveging BP 에서메시지 ma 을이용할때계층간의픽셀 크기가달라하위계층에서물체의외곽선이새롭게나타나거나 [Figue 17] 에서 점선부분 상위계층에는존재하지않던희미한영역이하위계층에서 나타나기 [Figue 17] 에서실선부분 때문이다. 상위계층메시지 ma 에서계층간의차이로인하여생긴비수렴구간을 45

55 놓치게되면하위계층의메시지 ma 에서는그차이가커지며많은에러를 동반하게된다. 이러한에러를줄이기위해메시지 ma 을구성한이후해당 라벨 f 뿐만아니라주변라벨 fq 까지도비수렴구간으로확장하여적용한다. 이렇게강화된메시지 ma 은다음하위계층으로크기를확장하여도놓치는 부분이줄어들게된다. 따라서 Pane-conveging BP 는기존의 BP 와유사한 결과를가지면서절반정도의수행시간을가지게된다. 다음 [Figue 18] 는 전반적인 Pane-conveging BP 의구성을나타낸다. Figue 18. Sstem achitectue of Pane conveging BP 46

56 7 Paae ocessing using GPU 본절에서는앞서소개한 Pane-conveging BP 알고리즘을최신 GPGPUGenea Puose Comutation on GPU 로각광받고있는 CUDA 로 구현하고성능을비교하여본다. CUDA 는 Nvidia 에서개발한범용병렬컴퓨팅 아키텍처로많은계산량을 GPU 를이용하여고속처리가능하게한다 [14]. CUDA 에서는최대 512 개의스레드를이용하여블록을만들며다수의블록을 그리드로만들어멀티프로세서가동시에실행하여병렬처리를하게된다. 따라서동시에많은스레드가실행될수있도록멀티프로세서에블록들을 할당하고실행하게하는커널디자인에따라어플리케이션의고속화가결정된다. Nvidia 의 GPU 에서는효율적인데이터접근을위해프로그램명령이 실행되는동안여러종류의메모리에접근한다. 각스레드에할당된독립적인 oca 메모리와동일한블록내의스레드만접근가능한 shaed 메모리그리고 모든스레드가접근가능한 goba 메모리가있다. 이외에추가적으로읽기만 가능하지만고속의접근이가능한 constant 메모리와 tetue 메모리가있다. 여기서는이러한메모리중모든스레드에서접근가능하면서이미지와같은 데이터처리에특화된 tetue 메모리를주로사용하고부가적으로 shaed 메모리를사용하였다. 우선블록당스레드의개수는최상위계층의크기 Tsukuba 영상의경우 2418 즉 432 개 에맞추어진다. 따라서블록은최상위계층에서 1 개다음계층에서 4 개 다음계층에서 16 개로증가하며 256 개까지증가하게 된다. 만약최상위계층의크기가 512 를넘어갈경우두개혹은세개의 47

57 블록으로나누어구성하게된다. 이렇게구성된블록에따라스레드를할당한 뒤데이터를 tetue 메모리로옮기고각함수를실행시킨뒤 goba 메모리에 저장된결과를다시 tetue 메모리로옮겨다음함수를실행하는방식으로 구성하였다. Shaed 메모리는데이터의공유가블록내의스레드로제한되고최대 이용가능한메모리량이 16KB 이므로부분적으로변수를할당하여사용하였다. 이미지데이터를 CPU 메모리로부터업로드받아 GPU 의 goba 메모리에 저장된다. 이후 tetue 메모리에데이터를옮겨초기데이터값을구하고그 결과를 5 개의계층으로줄인다. 이후최상위계층에서부터반복적으로메시지 전달과정을수행한다. 메시지전달과정의경우 CPU 에서는각계층의라벨값하나하나마다이웃 값에대해업데이트를실행하였으나. GPU 에서는분기 banch 를줄이고 프로그램의병렬성을최대화하기위해각방향마다의업데이트를따로 구성하여다수의블록으로나누고 tetue 메모리에업로드하여여러개의 블록을동시에처리하여진행하였다. CPU 와 GPU 의메시지전달방식의차이에 대한구성도는 [Figue 19] 과같다. 48

58 Figue 19. Message assing ocedue CPU and GPU 메시지전달과정이후결과는 tetue 메모리에업로드되어통합되고해당 계층의중간결과값을출력하게된다. 이렇게출력된계층간의결과값들을 이용하여메시지 ma 을만들고강화한다. 그리고하위계층크기로확장한뒤 tetue 메모리로구성하여해당계층의메시지전달과정에사용한다. 이에 49

59 따른 GPU 시스템의구성도는 [Figue 20] 과같다. Figue 20. Pane-conveging BP sstem on GPU 50

60 8 Eeimenta Resuts 본절에서는앞서언급한 Hieachica BP 와 Pane-conveging BP 의결과값을 비교해보고실시간계산을위한 GPU 시스템에적용한결과를보인다실험에 사용한환경은다음 [Tabe 3] 와같다. Tabe 3. Eeimenta sstem hadwae 실험에사용된영상은스테레오매칭연구에많이사용되는 middebu coege 의 Steeo eseach age[9] 에서제공하는영상을사용하였다. 사용된 테스트영상은다음 [Figue 21] 과같고크기및검색범위는다음 [Tabe 4] 과 같다. 51

61 Figue 21. Test Image and Gound Tuth 52

62 Tabe 4. Test image oeties 알고리즘의성능은추출된 disait ma 과실제 disait magound tuth 의차이를이용하여계산한전체영역의에러율과각알고리즘의평균수행 시간을이용하였다. 에러율의계산은다음식 38 를이용한다. 1 B = dc dt > δ d 38 N 여기서 N 은전체픽셀의개수 는픽셀좌표 dc 는추출된 disait ma dt 는실제 disait magound tuth 이고 δ d 는허용오차로여기서는 1.0 으로둔다. 다음 [Tabe 5] 는 Hieachica BP 알고리즘과 Pane-conveging BP 알고리즘의성능비교결과이고 [Tabe 6] 는 Pane-conveging BP 의 CPU 와 GPU 에서의성능비교이다. 결과영상은 [Figue 22] 와같다. 53

63 Tabe 5. Hieachica BP and Pane-conveging BP Resut Tabe 6. Pane-conveging BP CPU and GPU Resut 54

64 Figue 22. Hieachica BP and Pane-conveging BP Resut Image 55

65 9 Concusion 로봇및운전자보조시스템 생산자동화시스템등에서물체의위치정보를 영상적으로분석하고이용하기위해스테레오비전을사용하는연구가많이 진행되고있다. 우수한성능을나타내는알고리즘중하나인 Beief Poagation 알고리즘은각라벨에서의에너지최적화를위해주변라벨의값을이용하는 메시지패싱과정을반복하게된다. 이러한방법은 SAD SSD NCC 와같은 Aeabased 방식과달리우수한성능을보장하지만계산량이많다. 이러한문제를 해결하고자라벨의데이터를여러계층으로나누어계산하는 Hieachica BP 방식이제안되었지만이방법또한계산량이많다따라서본연구에서는각 계층에서의수렴값을이용한 Pane-conveging BP 방식을사용하여알고리즘이 가지는계산량을줄였고 CUDA 를이용한병렬처리로계산속도를고속화 하였다. Pane-conveging BP 알고리즘은각계층간결과를미리도출하여그결과 값의비교를통해수렴여부를판단하는메시지 ma 을생성한다. 이렇게 생성된메시지 ma 을이용하여이후계층에서의계산을생략함으로써 계산량을줄였다. 또한이렇게구성된메시지 ma 이데이터 scae 및 tetueess 영역으로인한에러를줄이기위해메시지 ma 을강화하여 적용함으로써기존알고리즘과유사한결과를가지게되었다. 또한이렇게 구성된 Pane-conveging BP 를 CUDA 를이용한병렬처리를진행하여고속 어플리케이션에사용될수있는시스템을구성하였다. 56

66 제안된 Pane-conveging BP 알고리즘을 Hieachica BP 알고리즘과비교하여 검증한결과에러율은거의차이가없고속도는알고리즘의개선을통해약 2 배 이상의성능을보임을증명하였다. 또한이를 GPU 로구성한결과는 CPU 로 구성한결과보다최대 15 배정도의속도개선을하였음을보였다. 속도적인측면에서 Pane-conveging BP 는우수한성능을보였으나결과 영상의에러율을다른알고리즘과비교해보았을때많은개선이필요하다. Middebu[9] 에서공개한최상위알고리즘들의에러율과비교해보면그 차이는보다명확해진다. 그러나 Beief Poagation 알고리즘이독립적으로 사용되기보다다른알고리즘과융합되어사용되는것을감안하면 Paneconveging BP 알고리즘또한다른알고리즘과의융합을통해이러한차이를 줄일수있을것이라예측된다. 향후물체의희미한영역이가지는에러와 물체의외곽선에서발생하는에러를줄이기위해 matching cost 계산방식을 개선하여접근하는방식을사용하거나효율적인 segmentation 을이용한 방식을사용하여보완한다면 state-of-ats 와유사한성능을내면서고속의 계산이가능한알고리즘으로발전할수있을것이다. 57

67 Refeence [1] K. Yoon and I. Kweon Adative suot-weight aoach fo coesondence seach IEEE Tans. Patten Anasis and Machine Inteigence vo. 28 no A [2] V. Komogoov and R. Zabih Comuting Visua Coesondence with Occusions using Gah Cuts ICCV vo [3] V. Komogoov and R. Zabih Muti-camea scene econstuction via gah cuts ECCV vo [4] O. Vekse Steeo coesondence b dnamic ogamming on a tee IEEE CVPR vo [5] Y. Deng and X.Lin A fast ine segment based dense steeo agoithm using tee dnamic ogamming ECCV vo [6] J. Yedidia W. Feeman Y. Weiss Geneaized Beief Poagation Adv. In Neua Infomation Pocessing Sstems [7] J. Sun N. N. Zheng H. Y. Shum Steeo Matching using Beief Poagation PAMI vo. 25 no [8] P. F. Fezenszwab and D. P. Huttenoche Efficient Beief Poagation fo Ea Vision CVPR vo [9] Middebu Steeo Vision Reseach Page htt://vision.middebu.edu/steeo [10] K. Konoige M. Agawa R. C. Boes Outdoo Maing and Navigation using Steeo Vision Singe vo [11] K. Sabe M. Fukuchi J. S. Gutmann T. Ohashi K. Kawamoto T. Yoshiqahaa Obstace avoidance and ath anning fo humanoid obots using steeo vision Robotics and Automation vo [12] S. Bahadoi L. Iocchi G. R. Leone Rea time eoe ocaization and tacking though fied steeo vision Aied Inteigence vo [13] J. Coado C. Hiaio M. Amingo Sef-caibation of an on-boad steeo-vision sstem fo dive assistance sstems IEEE Inte. Veh. Sm [14] NVIDIA CUDA ogamming Guide v htt:// [15] B. Cganek J. Siebet An Intoduction to 3D Comute Vision Techniques and 58

68 Agoithms John Wie & Sons [16] S.D. Cochan and G. Medioni 3D Suface descition fom binocua steeo IEEE Tans. PAMI vo. 14 no [17] A. Kaus M. Somann K. Kane Segment-based steeo matching using beief oagation and sef-adating dissimiait measue ICPR vo [18] Q. Yang R. Yang J. Davis D. Niste Satia-deth sue esoution fo ange images CVPR [19] R. Hate A. Zisseman Mutie view geomet in comute vision Cambidge Univesit Pess [20] E. Hecht Otics 4 th edn Addison Wese [21] Y.Ma S.Soatto J. Kosecka S. Sast An invitation to 3D vision fom images to geometic mode Singe [22] D. Schastein and R. Szeiski A taonom and evauation of dense two-fame steeo coesondence agoithms Intenationa Jouna of Comute Vision vo. 47 no A [23] D. Schastein View snthesis using steeo vision LNCS vo [24] S. Bichfied C Tomasi Deth discontinuities b ie-to-ie steeo Intenationa Jouna of Comute Vision vo [25] D. Schastein and R. Szeiski Steeo matching with Noninea Diffusion IEEE CVPR [26] J. P. Lewis Fast nomaized coss-coeation Vision Inteface [27] J. Banks M. Bennamoun Reiabiit anasis of the ank tansfom fo steeo matching Sstems Man and Cbenetics vo