제 14권 제 1 호 2009년 2월 pp. 10-17
최단거리 최소제곱법을 이용한 측정점군으로부터의 곡면 자동탐색
안 성 준*
Surface Type Detection and Parameter Estimation in Point Cloud by Using Orthogonal Distance Fitting
Sung Joon Ahn*
ABSTRACT
Surface detection and parameter estimation in point cloud is a relevant subject in CAD/CAM, reverse engineering, computer vision, coordinate metrology and digital factory. In this paper we present a soft- ware for a fully automatic surface detection and parameter estimation in unordered, incomplete and error-contaminated point cloud with a large number of data points. The software consists of three algo- rithmic modules each for object identification, point segmentation, and model fitting, which work inter- actively. Our newly developed algorithms for orthogonal distance fitting (ODF) play a fundamental role in each of the three modules. The ODF algorithms estimate the model parameters by minimizing the square sum of the shortest distances between the model feature and the measurement points. We dem- onstrate the performance of the software on a variety of point clouds generated by laser radar, com- puter tomography, and stripe-projection method.
Key words : point cloud, segmentation, object recognition, orthogonal distance fitting, automation
1. 서 론
최근에이루어진 3차원측정기술의발전은측정정 밀도와측정속도를여러응용분야에서요구되는수 준으로향상시킴과동시에측정가능대상물의크기,
재질, 주변환경의다양성을증가시켰다. 예를들면,
측정장비시장에서구입가능한레이저레이더는한 측정위치에서반경수십미터의주변환경으로부터수 천만측정점을 1-2분내에추출하는성능을보유하고 있다[6].
반면에, 측정점들로부터미지의측정물의형상을자 동적으로탐색하고그들의형상계수들을효율적이면
서도정확히추정하는과제는 CAD/CAM, 역공학, 로
봇공학, 컴퓨터비전등의다양한분야에서조속한해
결이요구되는것임에도불구하고, 이를위한효율적
이면서도일반적으로동작하는소프트웨어기술은현
재우리의가용지식을수단으로하여단시일내에개 발될것이라고기대되지않는다. 더욱이, 대용량이지 만측정물의일부만덮으며오차를포함하는측정점 들은문제의난이도를한층배가시킨다[4].
다행스럽게도, 주변환경특히공장환경내에존재 하는대부분의인조물은평면, 구, 원기둥, 원뿔, 그리 고원환체로서조합구성될수있다는사실에근거하 면, 그리고이들형상들을측정점들로부터자동적으 로탐색및추출하고이들의형상계수들을정확히추 정할수있다면, 현존하는산업기술수요의상당부분 이충족될수있겠다[7]. 특히, 인공건조물(artifact) 표 면의대부분은평면또는원기둥의일부라는사실을 우리는주변을둘러봄으로써쉽게확인할수있다.
따라서본논문에서는오차를포함하는측정작업에 의하여복수의측정물을대상으로획득되었으며불규 칙하게배열되어있으며대용량이지만측정물표면의 일부분만을덮는측정점군(point cloud)으로부터이들
다섯가지의형상들을신속히그리고안정적이면서도 정확히인지하고이들의형상계수들을자동적으로추 정하는이론과기술을소개한다. 아울러, 해당소프트
*종신회원, 성균관대학교정보통신공학부
-논문투고일: 2008. 11. 04 -논문수정일: 2008. 11. 14 -심사완료일: 2008. 11. 17
웨어를다양한 3차원측정법에의하여생성된측정점
군들을대상으로적용하여구한결과를제시한다. 2. 측정물, 측정점군, 형상모델
측정점들로부터측정물의형상모델을추정함(Fig.
1)에있어무엇보다도명심할것은, 첫째, 모든측정은
오차를동반하며[1,5,8], 둘째, 측정물형상모델은측정
물의참형상을근사적으로표현[7]할뿐이라는사실이 다. 즉, 측정물점들의참좌표값과측정물의참형상은 알수없는것으로서다만추정될뿐이다[5]. 따라서 측정물, 측정점군, 그리고측정물형상모델삼자사이 의근사적대리표현관계를고려하여, 본논문에서다 루고자하는형상추정과제를해결함에요구되는소 프트웨어의속성을규정하고자한다[4].
2.1측정물형상모델
측정물의형상을근사적으로표현하는형상모델로 서는점(point cloud) 모델, 다면체(polygonal) 모델,
해석학적(analytic) 모델을들수있다. 점모델은측
정물형상을점의집합으로서표현하며, 그와측정점 군사이의상사성을확인하는정보처리과정의한방 법인정합(point-to-point matching, registration) 외로 는현실적으로응용범위의한계를갖는다. 다면체모 델은측정물형상을다면체의집합으로서표현하며,
측정물형상의가시화와리소그래피등의용도로는 충분하나, 앞의점모델의경우와마찬가지로측정물
에대한크기, 모양, 위치및자세에대한정보를직
접제공하지못한다는단점이있다. 본논문에서는수
학식을표현수단으로사용하는해석학적형상모델에 주안점을두고측정물의형상모델을추정하는방법에 대한설명을전개하고자한다.
2.1.1 형상모델의 표준형
일반적으로, 임의의복잡한자연물형상을효율적 이면서도정확히표현할수있는해석학적방법이현 실적으로존재하지않는다고인정된다. 다만, 대부분 의인조물들은그들의생산비용을최소화하기위하여
직선또는원형요소로구성되는자연현상또는공구 와장비의모양과운동궤적을최대한활용하여가공 되기에, 그들의형상은평면, 구, 원기둥, 원뿔, 그리고 원환체의부분또는전체들의조합구성으로서비교적 단순히표현될수있다.
측정물의형상을해석학적으로표현하는수단으로 서는외재(explicit) 함수식, 내재(implicit) 함수식, 매
개변수(parametric) 함수가존재한다. 특히, 이들중에
서내재함수식(Fig. 2a)
(1)
과매개변수함수(Fig. 2b)
(2)
는측정물의형상을해석학적으로표현함에다양성과 편리성을제공한다. 예로서, 타원체는축길이a, b, c
로서 그의 크기와 모양이 결정되며 그의 표준형
(standard or canonical form)은
(3)
와같이내재함수식으로, 또는
와같이매개변수함수로표현될수있다.
정보처리소프트웨어가측정물의형상모델을내재 함수식또는/그리고매개변수함수로표현하여처리할 수있다면다양한응용과제의해결에있어유력한수 단으로서사용될수있다.
f a( g,x)=0
x a( g,u)
f a b c x( , , , ) x≡ 2/a2+y2/b2+z2/c2–1=0
x a b c u( , , , )=(acosucosv b, sinucosv c, sinv)T
Fig. 1. Parametric model recovery.
Fig. 2. The minimum distance point on the standard surface defined in moving (model) frame xyz from the measurement point Xi in reference (machine) frame XYZ. (a) Implicit and (b) parametric surface.
xi′
2.1.2 형상모델의 강체운동
한편, 공간내에서측정물은임의의위치에임의의 자세로존재할수있기에이를표현할필요가있다.
위의식 (1), (2)로서모델좌표계 xyz 내에서정의된
형상모델의절대좌표계 XYZ 내에서의강체운동은
(4)
와같이, 또는
(5)
와같이표현된다(Fig. 2).
식 (1), (2)와식 (4), (5)를재음미하면형상모델의
크기와모양은형태계수(form parameter) ag를포함하
는식 (1) 또는식 (2)로써표현되며강체운동에대하
여불변인형상모델의고유속성이다. 형상모델의강
체운동은위치계수(position parameter) ap=(Xo,Yo,Zo)T
와회전계수(rotation parameter) ar=(ω,φ,κ)T을포함
하는식 (4) 또는식 (5)로써표현된다. 여기서, 우리
는형상모델의형상정보를각각의의미에따라내향 성(intrinsic)과 외향성(extrinsic)으로 구분하여, ag는 내향계수로, ap와ar은외향계수로분류한다[2].
식 (1), (2)와식 (4), (5)가결합됨으로써, 형상모델
은절대좌표계 XYZ 내에서내재함수식으로는
와같이, 매개변수함수로는
와같이표현된다.
2.1.3 형상모델 추정의 응용
앞절에서와같이측정물의형상정보가내향계수와 외향계수로구분될경우, 다양한응용과제에있어서
장점을보유한다. 무엇보다도, 움직이는측정물을수
시로변하는위치와자세에관계없이그의내향계수 를분석함으로써인식및분류할수있다는장점이존 재한다. 다른예로서는, 로봇의장애물회피, 가공물 파지에있어서대상물의형상정보가크기, 모양, 위 치, 자세로구분되어표현된다면, 다양한응용과제들 이보다간단히해결될수있다. 또한, 컴퓨터내에서 측정물의 형상모델을 변형시킴에 있어내향계수와 외향계수의구분은작업의효율성과목적성을증가 시킨다.
따라서주어진측정점군으로부터그에포함된측정 물의형상정보를추출하는소프트웨어가이들정보를 내향계수와외향계수로구분하여제공한다면다양한 응용에있어서장점을보유함이명확하다.
2.2측정점군의특징
현존하는다양한 3차원측정기술에의하여생성되 는측정점군은측정물과측정원리의다양성과속성을
전수한다(Fig. 3). 본절에서는측정장비의물리적성
능인측정속도는제외하고측정점군이갖는특징을 살펴본다.
2.2.1 측정점 수
광학식으로대표되는비접촉식 3차원측정법에의 하여생성되는측정점군은흔히 10만점이상의측정 점을갖는대용량이라는특징을나타내며, 경우에따 라서는측정물에대한정보의유일한공급원이다(Fig.
3). 이와같은대용량정보임에도불구하고이들이측
정물의부분상세를표현하기에는턱없이부족하다는 현실이형상정보처리에있어서의고민사항이다. 따
라서정보공급원인측정점을낭비함이없도록그들 모두를사용하여측정물에대한정보를획득할수있 는전제조건으로서, 측정점의개수에단순비례하는계 산량을소요함이정보처리소프트웨어의특성으로서 요구된다.
2.2.2 측정물 종류와 수
측정점군에포함된측정물의종류와개수는궁극적 X R= ω ϕ κ, , x X+ o
x R= ω ϕ κ–1, , (X X– o)
aT≡(agT, ,apT arT)=(a1, , , , , , , ,… al Xo YoZoω ϕ κ)
F a X( , ) f a≡ ( g,Rω ϕ κ–1, , (X X– o))=0
X a u( , ) R= ω ϕ κ, , x a( g,u) X+ o
Fig. 3. Point cloud taken from a factory facility by laser radar.
으로추정되어야할정보로간주된다. 특정측정물에
소속되는부분측정점군(inlier)을제외한나머지측정
점군들은특정측정물의형상을추정함에있어서외
란(outlier)으로서작용한다. 따라서이두부분점집합
의구분(segmentation)을강건히수행하는특성이정
보처리소프트웨어에게요구된다.
2.2.3 측정물 공간크기
정보처리소프트웨어내부에고차다항식계산과정 이존재한다면, 계산결과의신뢰도는측정점의좌표 값크기에불필요하게영향을받는다. 따라서측정물 형상모델의수학적표현과알고리듬설계에있어서,
이와같은불편한상황을방지하는고려가있어야한 다. 예로서, 식 (3)과다음의내재함수식
은동일한타원체를해석학적으로표현하지만, 식 (3)
은계산실제에있어서비슷한크기의숫자가서로나 누어짐으로써근사적으로 0차다항식과같은행동을
보이기에위에서언급한계산결과의신뢰도측면에서 장점을보유한다.
2.2.4 측정 정확도
앞에서언급하였듯이오차를동반하지않는측정은 존재하지않는다. 한편, 측정점을확률통계학적으로 해석하면측정점은그로부터의최단거리에위치하는 미지의측정물점에대한관측값으로서간주된다[1,5,7,8].
그리고이와같은최단거리는측정오차로서추정된 다. 따라서측정물의형상계수를최소제곱법에의하 여추정하고자한다면, 측정점과형상모델사이의최 단거리를오차로설정하는것이가장자연스럽고도 올바른형상계수추정법이다[1,7,8] (제 3장참조).
아울러, 측정조건과측정물형상모델로서는설명되
지않는측정점들인열외자(outlier)를제거하여, 안정
적인형상모델의 추정을보장하는효과적인방법이 요구된다. 마지막으로, 형상계수추정과정후에구해
지는표준잔차(rms residual)의크기와사용된측정장
비의측정정확도사이의비교를통하여, 모델설정의
적합성과모델추정결과의신뢰성을판정할수있다.
2.2.5 측정점 정열순서
광학식또는접촉식측정법에의하여생성되는인
접한측정점들사이에는주사(scanning)순서가존재하
며, 이들정보는특히매개변수함수로표현되는형상 모델을추정함에있어활용될수있다. 그러나이와
같은정보조차도필요로하지않는측정물형상모델 추정법이보다광범위한적용성을갖는다.
2.2.6 측정 면적비
광학식또는접촉식측정법은측정물로의접근성에 제한을받기에, 일반적인경우한측정위치에서측정 가능한측정물의면적비는절반을넘지못한다. 반면 에, 컴퓨터단층촬영법에있어서는측정물로의접근 성제한이존재하지않기에측정물전체면의측정이 가능하다. 측정면부분에대한다수의측정점군들을 정합에의하여결합함으로써결과적으로는높은측정 면적비를얻을수도있다.
측정면적비가낮아측정면일부에대한측정점들 만이제공되었더라도측정물형상모델을안정적으로 추정할수있는소프트웨어의성능이요구된다. 반면
에, 측정면적비가높을경우, 추정대상형상모델주
위에인접하여전방위로산재하는이웃측정면에속 한측정점들이추정대상형상모델에대하여서는열외 자로작용한다. 이러한환경아래에서도추정대상형
상모델에속하는측정점들만을추출하여형상계수를 추정할수있는소프트웨어의성능이요구된다.
3. 최단거리 최소제곱법
앞서제 2.2.4절에서언급하였듯이측정물의형상계
수를최소제곱법에의하여추정하고자한다면, 형상 모델과측정점들사이의최단거리의제곱합을줄이는 최소제곱법이가장기대되는문제접근법이다. 흔히최 소제곱법은직선과측정점사이의좌표축기준수직 오차의제곱합을최소화하는직선회귀법으로대표되 는통상적최소제곱법(ordinary least-squares method)
을뜻한다. 반면에, 최단거리제곱법(ODF: Orthogonal
Distance Fitting)은통상적최소제곱법과는대비되는
것으로서, 특히공간측정점들을처리함에있어서월
등한장점을보인다. 단점으로서는상대적으로큰계
산량이요구된다는것이다. 본장에서는최단거리최
소제곱법에대한핵심적인내용을소개하고자한다.
보다자세한내용은관련문헌들에서술되어있다[2-4].
3.1문제정의와그의해법
최소제곱법에의한형상모델추정은측정점과형상 모델사이에존재하는오차의제곱합을최소화하는 형상계수들을구하는것이라고할수있다. 측정점과
형상모델사이의기하학적거리(geometric distance)를
오차로선택정의하면, 최소화목적함수(cost function)
f a b c x( , , , ) bcx≡( )2+(cay)2+(abz)2–(abc)2=0
는다음과같이두가지방법으로써표현될수있다: (6)
또는,
(7)
여기서, X는측정점좌표값으로채워진열벡터, X'는 형상모델에속하는대응점들의좌표값으로채워진열 벡터이고, d는이들측정점과대응점사이의거리값 으로써채워진열벡터이다. PTP는측정오차에대한가 중치행렬을나타낸다. 식 (6)을최소화하는최소제곱 법을거리기반법(distance-based algorithm), 식 (7)의 최소화방법을좌표기반법(coordinate-based algorithm)
이라고부른다[2].
식 (6), (7)의최소화문제는일반적으로비선형문제
이며 Fig. 4에서와같이에너지최소화문제로설명될
수있다. 이문제는, 형상계수a를구하는것을하나
의과제로, 그리고, 측정점들X와형상모델사이의거
리를최소화하는대응점들X'을구하는것을또하나 의과제로하는, 두개의단위문제로구성된다. 이들 두개의단위문제를하나의되풀이(iteration) 틀내에
서동시에푸는방법을통합법(total method), 두겹의
되풀이틀을이용하여번갈아가며푸는방법을분리 법(variable-separation method)이라고부른다. 따라서
두가지의목적함수식 (6), (7)과두가지의되풀이법
사이에총네가지의조합이가능하겠으나, 거리기반 법과통합법의조합은불충분선형연립방정식으로귀 결되기에, 현실적으로는, 최단거리최소제곱법을위한 총 3종류의범용알고리듬들이존재할수있음이최
근에밝혀졌다[3,4]. 이에따르면, 과거에문헌을통하여
발표된최단거리최소제곱법알고리듬들또한위의 세가지의종류로분류될수있다.
본논문의저자에의하여새로이개발된총네가 지의개별알고리듬들은목적함수식 (6), (7)을분리
법으로써최소화하되, 내재함수식[2]또는매개변수함
수[3]로표현가능한곡선/곡면의형상계수를제 2장에
서설명한바있는형태, 위치, 회전계수로구분하여
추정한다. 이들새로운알고리듬들은측정점수에단 순비례하는기억장소크기와계산량을요구하기에대 용량의측정점군을처리하기에최적이다.
3.2 형상모델추정과정중의주의사항
본절에서는, 최단거리최소제곱법을적용하여측 정점들로부터측정물의형상모델을추정함에있어고 려되어야할몇가지의실제적주의사항을살펴본다[4].
3.2.1 형상계수의 경계성
형상계수중의일부에게는허용범위가주어진다. 예 로서, 구의반지름은항상양의실수이어야한다. 그 렇지않을경우, 형상모델은실제로존재하지않는형
상을나타내게된다(imaginary feature). 되풀이에의
한계수추정과정중에형상계수가허용범위를준수 하는지의여부를항시 확인하여필요하다면적절한 조치를취하여야한다.
3.2.2 형상계수의 다중성
형상계수중의일부에게는복수의값이허용된다.
예로서, 원통의경우, 그의축이반대방향을향하여도
공간내에서외형(instance)적으로동일한원통이기에
식 (6), (7)의값에변화가발생하지않는다. 또한, 모
든회전계수값에 2π가가감되더라도형상모델의외 형은동일하다. 공간직선, 평면, 원뿔, 원환체등에서 도유사한경우를확인할수있다. 필요하다면, 선택 가능한여러값들중에서특정한값을일관된기준에 따라선택하는것이응용문제의해결에있어요구된다.
3.2.3 형상계수의 상대성
형상계수중의일부는정해진크기순서에따라배 열될필요가응용과제에있어발생한다. 예로서, 공간
내에존재하는타원체의자세확인및인식과제는축 길이의크기순서에대한정보를요구한다. 이럴경
우, 축길이의크기를주어진순서에맞추어배열함과
동시에타원체의회전계수를조정한다, 즉, 자세를확
인한다.
3.2.4 형상계수의 자유성
형상계수중의일부는적당한구속이가해지지않 으면임의의값을소유하게된다. 예로서, 원통의위 치가축을따라이동하여도원통은공간내에서동일 한외형을나타낸다. 따라서원통의위치를축의특정 점으로구속할필요가있다(constrained minimization).
σ02≡dTPTPd
σ02≡(X X′– )TPTP X X′( – )
Fig. 4. Orthogonal distance fitting task is illustrated as an energy minimization problem. The spring constants ki correspond to the diagonal elements of the weighting matrix PTP in (6)-(7).
보통은, 측정점들의무게중심으로부터가장가까운축
상의점을원통의위치로선택구속한다. 4. 곡면 자동탐색 및 형상계수 추정
앞의제 2장에서는측정물의형상모델과측정점군 의특성에대하여, 제 3장에서는주어진측정점들로 부터측정물의형상계수를추정하는수단인최단거리 최소제곱법에대하여살펴보았다. 본장에서는, 측정 점군내에존재하는측정물의형상모델후보를자동 탐색및인식하고, 그에소속되는측정점들을측정점 군내에서분류하여그들로부터측정물의형상계수를
추정하는구체적인과정을설명한다(Fig. 5).
4.1곡면자동탐색과인식
측정점들에의곡면맞춤(surface fitting)의일반적전 제조건으로서, 이들측정점들중에열외자(outlier)가 존재하지않거나존재하더라도상대적으로극히일부 일것이요구된다. 즉, 맞춤대상곡면에잠재적으로속
하는내부자(inlier)들만이적당한방법을통하여전체
측정점군으로부터 분리구분(segmentation)되어 미리 준비되어있어야한다는것이다. 역으로, 측정점의분 리구분과정은맞춤대상곡면에대한형상정보를필 요로한다. 이와같은곡면맞춤과분리구분과정사이
의정보요청교착상태(deadlock)는“닭이먼저냐? 달
걀이먼저냐?”문제의예라고할수있다. 따라서, 우
리는제 3의접근방법을통하여이들양측이필요로
하는초기정보를제공하여야한다.
본논문의저자에의하여개발된소프트웨어에서는 측정점군속에잠재하는곡면의탐색과인식이아래 와같은단계적과정을통하여이루어진다.
1. 무작위로선택된임의의측정점주변의작은범
위(탐색대상이될측정물의크기가고려되어결정) 내
에존재하는측정점들을추출한다 (Fig. 5의‘touch’).
2. 추출된 측정점들에 대한 2차 곡면(quadric)을
ODF를적용하여구한다.
3. 추출된측정점들의무게중심으로부터제 2단계 에서 구해진 곡면으로의 최단거리 디딤점(footing point)을구한다.
4. 최단거리디딤점에서의곡면곡률반경을주곡률 의역수로서계산한다(r1=1/k1 and r2=1/k2)
5. 곡률반경의부호와절대값크기를분석함으로써
측정물의형상모델후보를결정한다(Fig. 6).
6. 최단거리디딤점의좌표값, 곡면법선벡터, 곡률
반경, 곡률반경의축방향을분석하여형상모델의초 기형상계수값을계산한다(Fig. 5의 ‘initial model’).
예로서, 2개의곡률반경r1, r2의절대값이측정물기 대곡률반경보다상당히클경우(예로서, 5~20배) 측
정물의형상은평면으로서 추정된다. 또다른예로
서, 2개중 1개의곡률반경은측정물기대곡률반경
범위에속하지만다른하나가클경우, 측정물의형상
은원통으로서추정된다. 원통의축방향은주곡률방
향을전해받으며, 원통의위치즉축이지나는점은
제 3단계에서구하여진디딤점에서곡면법선벡터방 향으로곡률반경만큼떨어진위치를갖는다.
결과적으로, 형상모델에잠재적으로속하는내부자 측정점들을전체측정점군으로부터분리구분함에사 용될형상모델에대한초기정보가제공되었다.
4.2 측정점분리및열외자제거
제 2.2.4절에서언급하였듯이측정점과형상모델사
이의최단거리는형상모델을 추정함에있어오차에 대한가장적합한정의로서간주된다. 따라서형상모 델에대한열외자를제거함에있어서최단거리의크 기가판단의근거로사용되어야할것이다. 그러나최 단거리의계산은상대적으로높은계산량을요구하기 에, 모든측정점들을대상으로최단거리를구하는것 은계산비용관점에서지극히비효율적이다. 따라서 Fig. 5. Fully automatic surface detection and parameter
estimation in point cloud.
Fig. 6. Classification of local surface types according to the signs of the two principal curvatures k1 and k2. Flat for plane; Elliptic for sphere and torus;
Parabolic for cylinder and cone; Hyperbolic for torus.
