« 原因の原因のそのまた原因 | トップページ | Let's モーションキャプチャ »

2012年7月19日 (木)ICEを使ってみる 第6回 多元連立一時方程式

おはようございます、本日の当番モーションデザイナーのY.Nです。

連日暑いですね。暑い時には、アイス!
ってことで、強引ですが本日もICEです。

今回は、前回のブログで説明を端折っていた部分をやっていくことにします。

具体的には、
前回内容の2番「参照点4点の変換前後の座標からホモグラフィを求める」
多元連立一次方程式を解くノードの説明を文章だけだったところを
図付きでもう少し詳しく説明しようと思います。

まずは結果から。
2012_0718_01

これだけだと地味かつ、意味不明ですね。
何をやっているかというと、

0 x X1 + 3 x X2 + 2 x X3 + 0 x X4 + 0 x X5 = 12
2 x X1 + 4 x X2 + 0 x X3 + 0 x X4 + 0 x X5 = 10
3 x X1 + 1 x X2 + 5 x X3 + 6 x X4 + 0 x X5 = 20
1 x X1 + 0 x X2 + 2 x X3 + 4 x X4 + 1 x X5 =  5
2 x X1 + 1 x X2 + 3 x X3 + 0 x X4 + 6 x X5 = -10


この連立一次方程式の解が下記の通り出ているということを示しています。

X1= 0.2,
X2= 2.4,
X3= 2.4,
X4= 0.8333
X5=-3.3333



下図のピンクのやつがこの計算をやってます。
2012_0718_02_5


今日はこのノードの中身を展開して見ていくことにします。

今回取り扱っている事柄
・ループ処理
・連立一次方程式の解法(掃き出し法)

以下、結果を得るまでの流れです。
1.n元連立一次方程式の計算方法設定
2.前進消去
3.後退代入




■1.n元連立一次方程式の計算方法設定
以前に書いたとおり、ICEにはn次行列を扱うノードは無いので作る必要がありま
す。たぶん。

さて、どんな形にするかですが、
入力が係数行列の配列と定数項の配列、
出力結果が解の配列になるようなものを目指すことにします。
また解き方は、掃き出し法を使うことにします。

最初の方程式から係数行列と定数項を取り出してみます

・係数行列(comatrix)
0 3 2 0 0
2 4 0 0 0
3 1 5 6 0
1 0 2 4 1
2 1 3 0 6


・定数項(constant)
12
10
20
 5
-10


係数行列は行ごとに1配列ずつ割り当てて
それら配列を順番にくっつけたもので割り当てることにしましょう。
最初のツリー図でBuild Arrayノード使っているところがそれに当たります。

係数行列を配列に入れると一繋がりの数列になってしまって一見不便そうです。
けれど、列数と行数から行番号と列番号、全体のインデックスの配列を作れば
一通り計算には困らなくなります。
たとえば係数行列を行番号や列番号、全体インデックスの配列に置き換えると

●行番号   ●列番号   ●インデックス
0 0 0 0 0  0 1 2 3 4   0 1 2 3 4
1 1 1 1 1  0 1 2 3 4   5 6 7 8 9
2 2 2 2 2  0 1 2 3 4  10 11 12 13 14
3 3 3 3 3  0 1 2 3 4  15 16 17 18 19
4 4 4 4 4  0 1 2 3 4  20 21 22 23 24


上のようになるので、この配列を使えばx行目やy列目を簡単に抜き出せます。
また、インデックスの配列の各行の後ろ、5.10,15,20,25番目に定数項を
追加してやることで拡大係数行列ができます。

・拡大係数行列
0 3 2 0 0 12
2 4 0 0 0 10
3 1 5 6 0 20
1 0 2 4 1  5
2 1 3 0 6 -10


以後はこの拡大係数行列に対していろいろ操作していくことになるので、
この行列で先ほどの行番号や列番号、全体インデックスの行列を作っておけば、
拡大係数行列をいろいろ操作できます。

先ほどのノードの展開図を見てみますと、
そういったことをやっているのが下図の赤枠部分です。
2012_0718_03_6


■2.前進消去
枢軸を選択して、掃き出していきます。

計算誤差を抑えるため、各列の値の中で絶対値が最大のものを枢軸に設定します。
たとえば左端の列の枢軸は列番号0番の枢軸は値に3が入っている真ん中の行です。
これで掃き出しをする場合、2行目の値は

2  → 2 - 2 / 3 * 3 =   0
4 → 4 - 2 / 3 * 1 = 10/3
0 → 0 - 2 / 3 * 5 = -10/3
0 → 0 - 2 / 3 * 6 =  -4
0 → 0 - 2 / 3 * 0 =   0


みたいに全部2/3を枢軸の値に掛けて引くような計算をします。
こんな計算を枢軸以外の全部の行に対して行います。
そんなことをやっているのが下図の辺りです。
2012_0718_04_4

上図の右側のピンクのノード、Repeat Arrayは下図のような働きをしています。
1,2二つの数を指定回数、指定方式で繰り返すノードです。
2012_0718_05_5

上の図の計算を列数分繰り返すことで、係数行列の列数分繰り返すことで
上三角行列が出来上がります。
2012_0718_06_3


1  0.33 1.66 2   0   6.66
0  1  -1  -1.2  0   -1
0  0   1   0.72 0   3
0  0   0   1  -1.66  6.38
0  0   0   0   1   -3.33



■3.後退代入
解をX1,X2,X3,X4,X5とすると
上三角行列の一番下が5つ目の解X5になっています。
この解と下から2番目の行を使うと4つ目の解X4が出てきます。
それをやっているのが下図です。
2012_0718_07_2

全体図は以下。
2012_0718_08_2

以上、わかりにくい図ばかりで申し訳ないですが
今回はこの辺で。

follow us in feedly
result = encodeURIComponent( "http://www.accessgames-blog.com/blog/2012/07/post-9725.html" );document.write( "result = " , result );&media=https%3A%2F%2Ffarm8.staticflickr.com%2F7027%2F6851755809_df5b2051c9_z.jpg&description=Next%20stop%3A%20Pinterest">

| | コメント (0) | トラックバック (0)

« 原因の原因のそのまた原因 | トップページ | Let's モーションキャプチャ »

モーションデザイナー」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック


この記事へのトラックバック一覧です: ICEを使ってみる 第6回 多元連立一時方程式:

« 原因の原因のそのまた原因 | トップページ | Let's モーションキャプチャ »