As-Rigid-As-Possible Surface Modeling

내 맘대로 Introduction

registration에서 무조건 사용하는 non-rigid ICP의 핵심 원리가 나와있는 논문. ARAP이라고 불리기도 하는데, 2007년 논문이다. 이젠 15년도 더 된 논문인데 아직까지 사용되고, 이것만 한게 없다고 하는 논문. 임팩트가 참 좋은 것 같다. 논문도 깔끔함.

 

mesh deformation 시에 mesh가 stretching, shear같은 non-linear deformation을 당연히 겪게 되는데 이를 그냥 열린 문제로 최적화하면 형상이 일그러진다. 핵심 아이디어는 stretching, shear가 발생하더라도 국소적으로 face와 그 주변 face들만 보면 rigid하게 움직인다는 것이다. 마치 자전거 체인이 각 분절은 쇠라서 고정되어 있지만 전체는 부드러운 것과 같은 느낌.

 

이런 컨셉을 녹여서 최적화하는 기법을 소개한다.

 

메모

국소적으로 rigid하다. 라고 가정할 때 "국소적"의 범위는 vertex와 그 주변 1-ring neighbor다.  이 1-ring neighbor 단위로 rigid하는 constraint를 걸고, 전체를 최적화하는 것.  자전거 체인의 한 분절이 1-ring neighbor가 되는 셈이다.

수식(3)이 논문 전체에서 핵심이다. 한 줄 요약과 같음. 1-ring neighbor가 rigid하다고 가정한다면, 1-ring neighbor 간의 edge 변형은 SO3 transformation으로 표현이 가능하다고 본다. 만약 non-rigid였다면 edge 길이가 바뀌었기 때문에 R|t가 필요하겠지만, rigid하고 가정한다면 edge 길이는 일정하므로, R만 있으면 된다.  실제로는 edge 길이가 일정하지 않겠지만, 이렇게 가정하고 R만 찾도록 강제하면서 최적화를 하면 edge 길이가 "최대한" 일정하게 유지되게 된다.  --------------- R을 구하는 것은 최적화로 풀어도 되지만, 전개를 해보면 closed form으로 나오기 때문에 빠르게 풀 수 있다.  edge 길이만 알고 있다면 바로 수식(5)를 SVD에 집어넣어 풀 수 있다.

수식(5)에서 R은 그렇게 구하면 된다고 치는데, 각 edge 별로 weight는 어떻게 구하는가? 단순히 모든 edge의 가중치를 1로 통일해서 처리하면 위 그림처럼 의도한 변형이 안된다. face가 정렬된 방향에 따라 bias가 생긴다. 이를 해결하는 방법은 edge를 가운데에 두고 바라보고 있는 2개의 각도 cotangent를 이용하는 방법이다. 말이 어려운데 위 그림에서 보이는 2개의 각이다. ---------------------- 이렇게 edge weight를 계산하면, 두 개의 각도가 간접적으로 edge가 관여하는 2개의 face 면적에 비례하므로, face arean weighting 효과도 있다.  이 효과의 파생 효과로 또, edge가 아닌 vertex weight를 1로 통일해도 된다.  edge weight에 face 면적 비례가 녹아들어있기 때문에 굳이 vertex에서는 추가 weighting을 하지 않아도 되는 것. 따라서 수식(7)처럼 vertex 별 weight는 무시하고 수식(3)에만 집중하면 되는 문제로 그대로 남게 된다.

실제 활용은 어떻게 하는가?  위에서는 변형 전,후의 edge를 둘 다 알고 있을 경우, R을 찾는 문제였는데 실제에서는 R도 모르고 변형 후의 edge도 일부는 모를 것이다.  e' 과 R을 모르는 문제. --------------------- 이 때는 문제를 나눠서 푼다. 현재 상태에서 알고 있는 edge로 하여금, R을 먼저 푼다.  그리고 구한 R을 고정하고 다시 변형 후 edge를 푼다. -> 이걸 ICP에 적용해서 생각해보면 -> 현 상태에서 Cloest point 찾아서 edge mathicng 후 R 계산 -> R 고정하고 edge 업데이트 (vertex 업데이트) -> 다시 반복

R은 아까 closed form으로 풀린댔고, 변형 후 edge는 최적화로 풀어야 한다. 당연히 gradient descent(LM) 최적화로 풀 것. 수식(3)에 대한 jacobian을 계산해보면 왼쪽과 같이 나온다.  이 때 R은 먼저 풀어서 알고 있다고 (constant라고 가정한다면

gradient는 0이 되어야 하므로 이항 정리하여 수식(8)과 같이 쓸 수 있다.  이 형태는 마치 Ax=b 형태처럼 정리되므로 문제가 쉬워짐. Ax = b 를 푸는 solver는 이미 많고 빠르게 구현할 수도 있으므로, 기존 최적화 파이프라인을 태우면 된다.  여기서 A에 해당하는 L은 symmetric PSD matrix여서 choleskfy factorization까지 사용할 수 있으므로 연산량 O도 더 줄일 수 있다.