E = N M α= = [( pα I α x ) 2 ( α qα + y ) 2 ] α r α r α I α α p α = P X α + P 2 Y α + P 3 Z α + P 4, q α = P 2 X α + P 22 Y α + P 23 Z α + P 24 r α =

Size: px

Start display at page:

Download "E = N M α= = [( pα I α x ) 2 ( α qα + y ) 2 ] α r α r α I α α p α = P X α + P 2 Y α + P 3 Z α + P 4, q α = P 2 X α + P 22 Y α + P 23 Z α + P 24 r α ="

さやみのしま
5 years ago
Views:

1 undle Adjustment or 3-D Reconstruction: Implementation and Evaluation Yuuki Iwamoto, Yasuyuki Sugaya 2 and Kenichi Kanatani We describe in detail the algorithm o bundle adjustment or 3-D reconstruction rom multiple images based on our latest research results The main ocus o this paper is the handling o camera rotations and the eiciency o computation and memory space usage when the number o eature points and the number o rames are large An appropriate consideration o these is the core o the implementation o bundle adjustment Doing experiments o undamental matrix computation rom two images and 3-D reconstruction rom multiple images, we evaluate the perormance o bundle adjustment ),6),2),2) Department o omputer Science, Okayama University 2 Department o omputer Science and Engineering, Toyohashi University o Technolgy (X, Y, Z) (x, y) X x y A P Z A P 3 4 (u, v ) t R 4) P = KR / u / I t, K / v / A (2) I K 3) () P X + P 2 Y + P 3 Z + P 4 x = P 3 X + P 32 Y + P 33 Z + P, y = P 2 X + P 22 Y + P 23 Z + P (3) P 3 X + P 32 Y + P 33 Z + P 34 P (ij) P ij N (X α, Y α, Z α) M (x α, y α ) ( =,, M, α =,, N) P (3) Vol2-VIM-75 No9 2//2 x, y 3) = 6 c 2 Inormation Processing Society o Japan

2 E = N M α= = [( pα I α x ) 2 ( α qα + y ) 2 ] α r α r α I α α p α = P X α + P 2 Y α + P 3 Z α + P 4, q α = P 2 X α + P 22 Y α + P 23 Z α + P 24 r α = P 3 X α + P 32 Y α + P 33 Z α + P 34 (5) (x α, y α), α =,, N, =,, M (4) 3 (X α, Y α, Z α ) P 5),6),2),2) 3 3 (X α, Y α, Z α ) P (4) E 3 ( X α, Y α, Z α) P (2), (u, v ) t = (t, t 2, t 3) R,, u, v, t, t 2, t 3 R R 9 R R (4) = I 3 3 R 3 R 3 R R R R + R R = I R R = O ( R R ) = R R R R ω, ω 2, ω 3 ω 3 ω 2 R R ω 3 ω A (6) ω 2 ω 3 ω, ω 2, ω 3 3 SO(3) so(3) 6) a T a T a T 7) (6) ω = (ω, ω 2, ω 3) 6) I ω I (a I)b = a b, (a I)T = a T (6) R R = ω R (7) t t dr /dt ω (7) 7) 7),9) (7) 4 E X α, Y α, Z α, α =,, N,, t, t 2, t 3, u, v, ω, ω 2, ω 3, =,, M 3N + 9M ξ, ξ 2,, ξ 3N+9M ξ k ξ k 2 / ξ k (4) E E N [( )( ) I α pα = 2 xα p α r α r ξ k rα 2 α p α r α ξ k ξ k α= = ( qα + y )( )] α q α r α r α q α r α ξ k ξ k 9) 2 N 2 E ξ k ξ l = 2 α= = ( + I α r 4 α r α q α ξ k [( )( ) p α r α p α r α r α p α r α p α ξ k ξ k ξ l ξ l )] ξ l )( r α q α r α q α r α q α ξ k ξ l ξ k E E/ ξ k 2 2 E/ ξ k ξ l p α, q α, r α p α / ξ k, q α / ξ k, r α / ξ k Vol2-VIM-75 No9 2//2 (8) (9) 2 c 2 Inormation Processing Society o Japan

3 5 3 (5) p α, q α, r α (X β, Y β, Z β ) δ αβ p α, X β = δ αβ P q α X β = δ αβ P 2, r α X β = δ αβ P 3, p α, Y β = δ αβ P 2 q α 6 Y β = δ αβ P 22, r α Y β = δ αβ P 32, p α = δ αβ P 3 Z β q α Z β = δ αβ P 23 r α Z β = δ αβ P 33 () (2) P P AR I t AK KR I t A u v / AP = u v / AP / = P u P 3 / P 2 u P 32 / P 3 u P 33 / P 4 u P 34 P 2 v P 3 / P 22 v P 32 / P 23 v P 33 / P 24 v P 34 / A () p α, q α, r α λ p α = δ ( λ p α u ) q α r α, = δ ( λ q α v ) r α, λ λ 7 r α λ = (2) (2) P u ( ) ( ) P AR I t AK KR I t u A u v / AP = P 3 P 32 P 33 P A (3) / v ( ) P AR I t P v 3 P 32 P 33 P 34 A (4) p α, q α, r α (u λ, v λ ) p α = δ λr α q α r α, =, =, u λ u λ u λ p α q α =, = δ λr α r α, = (5) v λ v λ u λ 8 t (2) P 4 P 4 (R + u R 3 )t + (R 2 + u R 23 )t 2 + (R 3 + u R 33 )t P 24 A = KR t (R 2 + v R 3 )t + (R 22 + v R 23 )t 2 + (R 32 + v R 33 )t 3 A P 34 (R 3 t + R 23 t 2 + R 33 t 3 ) (6) P P t 24 A t 3 P 34 P P 24 P 34 A R + u R 3 R 2 + v R 3 R 3 R 3 + u R 33 R 32 + v R 33 R 33 t 2 P 4 P 24 P 34 A R 2 + u R 23 R 22 + v R 23 R 23 A A (7) (t λ, t λ2, t λ3 ) tλ (5) tλ p α = δ λ ( r + u r 3 ), tλ p α = δ λ ( r 2 + v r 3 ), tλ p α = δ λ r 3 r, r 2, r 3 r = R R 2 R 3 9, r 2 = R 2 R 22 R 32, r 3 = R 3 R 23 R 33 (2) P Vol2-VIM-75 No9 2//2 (8) (9) 3 c 2 Inormation Processing Society o Japan

4 P = K(ω R) ω 3 ω 2 ω 2 t 3 ω 3 t 2 I t = ω 3 ω ω 3 t ω t 3 A (2) ω 2 ω ω t 2 ω 2 t (ω R) = R (ω I) (ω I)t = ω t 7) P / ω, P / ω 2, P / ω 3 R P 3 u R 33 R 2 +u R 23 (t 2 R 3 t 3 R 2 )+u (t 2 R 33 t 3 R 23 ) R ω 32 v R 33 R 22 +v R 23 (t 2 R 32 t 3 R 22 )+v (t 2 R 33 t 3 R 23 ) A, R 33 R 23 (t 2 R 33 t 3 R 23 ) R P 3 +u R 33 R u R 3 (t 3 R t R 3 )+u (t 3 R 3 t R 33 ) R ω 32 +v R 33 R 2 v R 3 (t 3 R 2 t R 32 )+v (t 3 R 3 t R 33 ) A, 2 R 33 R 3 (t 3 R 3 t R 33 ) R P 2 u R 23 R +u R 3 (t R 2 t 2 R )+u (t R 23 t 2 R 3 ) R ω 22 v R 23 R 2 +v R 3 (t R 22 t 2 R 2 )+v (t R 23 t 2 R 3 ) A (2) 3 R 23 R 3 (t R 23 t 2 R 3 ) (ω λ, ω λ2, ω λ3 ) ωλ (5) ωλ p α = δ λ ( r + u r 3 ) (X α t ), ωλ q α = δ λ ( r 2 + v r 3 ) (X α t ), ωλ r α = δ λ r 3 (X α t ) (22) X α = (X α, Y α, Z α ) E 2 E (LM) 9) ( ) X α,, (u, v ), t, R E c = ( 2 ) 2 E/ ξ k, 2 E/ ξ k ξ l, k, l =,, 3N + 9M ( 3 ) ξ k, k =,, 3N + 9M ( + c) 2 E/ ξ 2 2 E/ ξ ξ 2 2 E/ ξ ξ 3N+9M 2 E/ ξ 2 ξ ( + c) 2 E/ ξ2 2 2 E/ ξ 2 ξ A 2 E/ ξ 3N+9M ξ 2 E/ ξ 3N+9M ξ 2 ( + c) 2 E/ ξ 3N+9M 2 ξ E/ ξ ξ 2 E/ ξ ξ 3N+9M = E/ ξ 3N+9M ( 4 ) X α,, (u, v ), t, R A (23) X α X α + X α, +, (ũ, ṽ ) (u, v ), t t + t, R R(ω )R (24) R(ω ) N [ω ] ω 8) ( 5 ) X α,, (ũ, ṽ ), t, R Ẽ Ẽ > E c c (3) ( 6 ) X α X α,, (u, v ) (ũ, ṽ ), t t, R R (25) Ẽ E δ δ E Ẽ, c c/ (2) (23) c = ξ k 3 R = I, t =, t 22 = (26) 3 2 Y t 2 = 2 Y X Z t 2 = t 23 = (23) ω, ω 2, ω 3, t, t 2, t 3, t 22 3N + 9M 7 (23) LM X α,, (u, v ), t, R (26) (26) X α, t, R X α, t, R X α = ) s R (X α t, R = R R, t = s R (t t ) (27) s = (j, R (t 2 t )) j = (,, ) Vol2-VIM-75 No9 2//2 exp(ω I) so(3) Lie SO(3) 6) 4 c 2 Inormation Processing Society o Japan

5 2 (8), (9) N MN α= = E/ ξ k (8) ξ k β X β () δ αβ N α= α = β ξ k λ λ, (u λ, v λ ), t λ R λ (2), (5), (8), (22) δ λ = = λ (8) N α= = α α α 2 E/ ξ k ξ l (9) ξ k, ξ l (9) N α= ξ k, ξ l (9) = ξ k, ξ l N α= = E/ ξ k, 2 E/ ξ k ξ l 2 2 E/ ξ k ξ l H(k, l) (3N + 9M 7) (3N + 9M 7) N, M 3N 3 E, 3N 9M F 9M 9 G E 2 E/ X 2 α, 2 E/ X α Y α 2 F 2 E/ X α, 2 E/ X α u 2 G 2 E/ 2, 2 E/ u 2 27NM + 9N + 8M H(k, l) (k, l) 3 3N +9M 7 (23) (3N +9M 7) (3N +9M 7) N, M LU 2) 2 27NM + 6N + 4M I α = 3 (23) (23) E (c) F ( ) ( ) ξ P d P E (c) N F N ξ F F F N G (c) ξ P ξ 3 3N ξ F 9M 7 d P, d F (23) 3N 9M 7 E (c) α, α =,, N α (X α, Y α, Z α) E (c) ( + c) F α α (X α, Y α, Z α ) α E 2 3 (9M 7) G (c) E 2 (9M 7) (9M 7) ( + c) (28) E (c) E (c) N ξ P + F F N = ξ F = d P, d F ( F (28) ) F N ξ P + G (c) ξ F = d F ξ P 2 ξ F 9M 7 ( N G (c) F α E α (c) F α ) ξ F = α= N α= F α E (c) α α E d F, α (29) E/ X α E/ Y α A (3) E/ Z α ξ F (29) 2 ξ P α X Y α A = E (c) α (F α ξ F + α E) (3) Z α 4 Vol2-VIM-75 No9 2//2 5 c 2 Inormation Processing Society o Japan

6 2 4) σ = LM ɛ LM δ δ = nɛ 2 / 2 n = N α= = Iα ɛ = = = 6 x, y (Hartley 8 3) ) 22),, ) (u, v ) (4) e N = 9 E e = (32) N 7 N 7 7 7) σ e 2 / 2 σ 2 N 7 χ 2 N 7 (32) e σ 4) 4) xyx y 3 4 EFNS 3) ) 22) 3 22) Oxord 2(a) P 5266 (23) (b) % P (u, v ) t R A 3 A2 n = N Iα 6432 (4) α= = (32) E e = 2n (3N + 9M 7) Vol2-VIM-75 No9 2//2 (33) 6 c 2 Inormation Processing Society o Japan

Vol2-VIM-75 No9 2//2 情報処理学会研究報告 4 まとめ本論文では多画像からの 3 次元形状復元を行うバンドル調整のアルゴリズムを最新の研究に基づいて詳細に記述した本論文で着目したのはカメラ回転の適切な取扱い方および特徴点と画像数が多いときの計算とメモリの効率化であるまず 2 画像からの基礎行列の計算に応用し金谷菅谷4) の方法と同じ解が得られ

684648452468 67536625569 66882949793228 6642848678532 6639324694876 65756935756945 (b) 回 4 4 42 43 44 45 46 47 48 49 (d) 通りに実装することは困難であるがここに述べた工夫によって実行できることを示した (c) 理論的にはバンドル調整は任意の 3

7 Vol2-VIM-75 No9 2//2 情報処理学会研究報告 4 まとめ本論文では多画像からの 3 次元形状復元を行うバンドル調整のアルゴリズムを最新の研究に基づいて詳細に記述した本論文で着目したのはカメラ回転の適切な取扱い方および特徴点と画像数が多いときの計算とメモリの効率化であるまず 2 画像からの基礎行列の計算に応用し金谷菅谷4) の方法と同じ解が得られ彼らの方法が最適であることを実証したただしバンドル調整は効率において彼らの方法に劣る次に英国 Oxord 大学の実測データを用いて 3 次元を行ったこれは特徴点数が非常に多くバンドル調整をその原理 (a) 回再投影誤差 (b) 回 (d) 通りに実装することは困難であるがここに述べた工夫によって実行できることを示した (c) 理論的にはバンドル調整は任意の 3 次元復元に適用できる万能手法であるが椋木ら9) 再投影誤差が検討したような単純な形状例えば球面と単純なカメラ配置例えば同心円上から出発して複雑な形状に収束させることには無理があり初めに精度のよい近似的な 3 次元復元を行うことが必要である近似的 3 次元復元の代表はアフィンカメラ近似による因子分解法2),5),),2) であるが透視投影モデルによる自己校正法),),8) のほうが精度が高いバンドル調整はそのような高精度の復元を行った後の最終的な補正を行う手段とみなすのがよいと思われる謝辞: バンドル調整についてご助言頂いた東北大学の岡谷貴之准教授に感謝します本研究の一部は文部科学省科学研究費基盤研究 ( 2572) の助成によった参 (e) 考文献 ) ハノアッカーマン, 新妻弘崇, 金谷健一, 自己校正法のための射影復元の計算量削減, 情報処理学会研究報告, 27-VIM-6- (27-9), ) 浅原清太郎, 金谷健一, 菅谷保之, ハノアッカーマン, 未校正因子分解法による 3 次元復元比較実験, 情報処理学会研究報告, 25-VIM-5-2 (25-), ) R I Hartley, In deense o the eight-point algorithm, IEEE Trans Patt Anal Mach Intell, 9-6 (997-6), ) R Hartley and A Zisserman, Multiple View Geometry in omputer Vision, 2nd ed, ambridge University Press, ambridge, UK, 24 5) 金出武雄, コンラッドポールマン, 森田俊彦, 因子分解法による物体形状とカメラ運動の復元電子情報通信学会論文誌 D-II, J74-D-II-8 (993-8), ) K Kanatani, Group-Theoretical Methods in Image Understanding, Springer, erlin, Germany, 99 7) K Kanatani, Statistical Optimization or Geometric omputation: Theory and Practice Elsevier, Amsterdam, the Netherlands, 996; reprinted, Dover, York, NY, USA, 25 8) 金谷健一, 形状 AD と図形の数学, 共立出版, 998 図 2 (a) 用いた 36 画像中の一つ (b) 点を抜き出した場合のヘッセ係数行列の非零パタン (c) 反復回数に対する再投影誤差 e のグラフ (d) 反復回数に対する再投影誤差 e の値 (e) 3 次元復元赤初期位置緑収束位置最小二乗法による初期復元の再投影誤差は e = 画素であったがバンドル調整の結果 e = 画素に低下した反復回数による e の変化を図 2(c) にその具体的な数値を図 2(d) に示す反復回数は 49 回であり実行時間は 2 分 5 秒であったただし ++言語を用い PU には Intel ore2duo E675, 266GHz 主メモリ 4G OS には Windows Vista を用いた図 2(e) は復元した各点の 3 次元位置をある方向から眺めたものである赤は最小二乗法による初期位置であり緑が最終的な復元位置である 7 2 Inormation Processing Society o Japan

8 9),,, 25 ) ( ),, 2,, 29, pp ),,,,,, 25-VIM-5-6 (25-9), ),,,, PRMU23-8 (23-), ),, FNS,, 27-VIM-58-4, (27-3), ) K Kanatani and Y Sugaya, ompact undamental matrix computation, IPSJ Trans omput Vis Appl 2 (2-3), ) M I A Lourakis and A A Argyros, Is Levenberg-Marquardt the most eicient optimization algorithm or implementing bundle adjustment?, Proc th Int on omput Vis, Vol 2, October 25, eijing, hina, pp ) M I A Lourakis and A A Argyros, SA: A sotware package or generic sparse bundle adjustment, AM Trans Math Sotware, 36- (29-3), 2: 3 7),,, 3,, 44- (23-), ),,, :,, 27-VIM-57-5 (27-), 9 6 9),,,,, 4-SIG3 (24-2), ),,, 29-VIM (29-6), 6 2) Triggs, P F McLauchlan, R I Hartley, and A Fitzgibbon, undle adjustment A modern synthesis, in Triggs, A Zisserman, and R Szeliski, (eds), Vision Algorithms: Theory and Practice, Springer, erlin, 2, pp ),,,, 3,, 29-VIM-68-5 (29-9), 8 A ( P = Q ) q P 3 3 Q 4 q () P det Q < Q q Q = ckr, q = ckr t (34) c t t = Q q (35) R R R = I (34) QQ = c 2 KR RK = c 2 KK (36) (QQ ) = c 2 (K ) (K ) (37) (QQ ) (QQ ) = (38) (37), (38) = c K = ck (39) (34) (39) Q = R (4) R R = (Q) (4) K (39) (3,3) A2 3 (3) xp 3 X + xp 32 Y + xp 33 Z + xp 34 = P X + P 2 Y + P 3 Z + P 4 yp 3 X + yp 32 Y + yp 33 Z + yp 34 = P 2 X + P 22 Y + P 23 Z + P 24 (42) p α n α (= I = α) p α 3 X α 2n α x α P 3 P x α P 32 P 2 x α P 33 y α P 3 P 2 y α P 32 P 22 y α P 33 P 23 P 3 X α Y α Z α x α P 34 P 4 = y α P 34 P 24 9) Vol2-VIM-75 No9 2//2 (43) 8 c 2 Inormation Processing Society o Japan

IPSJ SIG Technical Report Vol.2009-CVIM-168 No /9/ Latest Algorithm for 3-D Reconstruction from Two Views Kento Yamada, 1 Yasu

IPSJ SIG Technical Report Vol.2009-CVIM-168 No /9/ Latest Algorithm for 3-D Reconstruction from Two Views Kento Yamada, 1 Yasu 2 3 2 3 2 3 Latest Algorithm for 3-D Reconstruction from Two Views Kento Yamada, Yasushi Kanazawa, Kenichi Kanatani 2 and Yasuyuki Sugaya 3 This paper presents a new algorithm for reconstructing the 3-D