2013年12月27日

ヤコビ行列を使ったIKについて その3

冬休みですね。土日が重なって長めですが、だらだらせずに何か作りたいものです。

前回、次回は3軸回転に、と書きましたが、角度制限などは1軸の間にやっておいた方がわかりやすいかなと思い、そちらを先にすることにしました。参考文献はこれまでと同様です。
[1]の方はヤコビIKだけでなく、Particle-IKやCCD-IKについても説明されており、この3つの手法の比較などもされていますので、大変参考になります。

jacobi_006.png
今回の実験パラメータとして、片足をイメージして下記のような設定にしてみました。
jacobi_007.png

実行結果

角度制限等なし

今回の式


制限なしだと自由に動きますが、角度制限をつければそれっぽくはなっている気もします。
ただ、制限が強いのか場所によってはたまに振動したりします。

この回転のしやすさとか角度制限などの設定が面倒なので、既存のVMDファイル等から各関節の取りうる角度の確率密度関数を推定して自動で決められれば面白そうですが、できるんでしょうかね。

とりあえず次こそ3軸回転ですかね。

[1] 三谷純 他 共著,「Computer Graphics Gems JP 2012」,ボーンデジタル,2012
[2] 広瀬茂雄 著,「ロボット工学」,裳華房,2008年改訂第19版
web拍手 by FC2
posted by シンドラー at 15:25 | Comment(0) | TrackBack(0) | OpenGL & Metasequoia | このブログの読者になる | 更新情報をチェックする

2013年12月26日

ヤコビ行列を使ったIKについて その2

続きです。前回は2リンク前提で先端位置を数式で計算してから微分してヤコビ行列を作っていましたが、Nリンクのときのリンク先の座標をいちいち数式で表すのは大変すぎますので、参考文献[1]の方法に変更します。
参考文献の方はDirectX系の行列計算でしたので、その辺りもOpenGL用に変更しています。

jacobi_004.png

jacobi_005.png

実行結果
4リンクアーム(Z軸回転のみ)を試してみました。

前回は微小変位といいながらマウス座標と先端座標の差をそのまま使っていましたので、ある一定以上離れていれば大きさを制限するように変更しました。

本来繰り返し計算して目的座標に到達させるべきですが、今回は1フレームに1回更新にしていますので到達まである程度時間がかかっています。

後、擬似逆行列の計算はEigenを使って特異値分解しています。



一応これでZ軸回転のみですがNリンクアームができるようになったので、RjをXYZオイラー回転にすれば3自由度IKにもすぐできると思います。

後は、ヤコビ行列であれば回転のし易さや角度制限なども調整できるみたいですので、その辺りも試してみたいと思います。

web拍手 by FC2
posted by シンドラー at 20:17 | Comment(0) | TrackBack(0) | OpenGL & Metasequoia | このブログの読者になる | 更新情報をチェックする

2013年12月24日

ヤコビ行列を使ったIKについて

昔はさっぱり意味が分かりませんでしたが、微分や線形代数の勉強をしてやっと何となくイメージは掴めるようになってきたので、3連休中にヤコビ行列を試してみました[1][2]。

まずは簡単な例題として、3自由度の2リンクアーム(Z軸周りの回転のみ)を考えてみます。

jacobi_001.png

jacobi_002.png

jacobi_003.png

実行結果
マウスでクリックした座標を目標座標として、ヤコビ行列を使ってIK計算しています。
今回は通常の逆行列計算で、+λIなどして計算しています。



次回は特異値分解を使ったり、Z軸周りだけではなく、XYZ軸回転などを試してみたいと思います。

[1] 三谷純 他 共著,「Computer Graphics Gems JP 2012」,ボーンデジタル,2012
[2] 広瀬茂雄 著,「ロボット工学」,裳華房,2008年改訂第19版

web拍手 by FC2
posted by シンドラー at 22:17 | Comment(0) | TrackBack(0) | OpenGL & Metasequoia | このブログの読者になる | 更新情報をチェックする

2013年12月19日

特異値分解を用いた連立一次方程式の計算

連立一次方程式を解くとき、逆行列を計算するのではなく、特異値分解をする方が良い、というのをどこかで見た気がしますので、試してみることにします。

今回例題として、高さマップから局所的な2次曲面を計算してみます。
高さ情報をz座標と見立てて、3次元の座標F(x,y,z)=0となる等値面と考えると、
3変数の2次曲面の方程式は、以下のように表すことができます。

svd_007.png

これは2次形式で表現するのが普通なのだと思いますが、とりあえず連立方程式の
形にしてみます。
ある注目画素を中心とするMxMの近傍画素の座標を、 x,y,zそれぞれ-1〜1の範囲に
変換します。そうすると、N=MxM個の連立方程式を作ることができます。

svd_008.png

これを行列の形で表すと、Ax=0の形になります。

svd_009.png

今回は、それぞれの行をノルム1に正規化したものを行列Aとします。
(正規化したほうが近似精度が上がったため)

svd_011.png

この場合、前回のホモグラフィ行列のときにも用いましたが、特異値分解して
特異値が最も小さい特異ベクトルが誤差の二乗が最小になる解になるらしいです。

svd_010.png

Eigenを用いた場合、最小特異値を持つ特異ベクトルは、Vの一番右端に
来ているようですので、そのベクトルがa,b,…,jの値となります。

これで10個のパラメータが求まりましたので、画像上ではx,yを決めてzを求める方法、
3次元空間上では視点とレイを決めて、レイと2次曲面の衝突判定をすることで、
計算した2次曲面で近似した場合の結果を得ることができます。

後、たまに近傍と大きく異なる推定結果の点が出てきましたので、10個のパラメータを
画素ごとに求めて、5x5のガウスフィルタをかけてパラメータの平均化?をしました。

実行結果
各画素における2次曲面を、近傍5x5の高さ情報から計算する、ということをやっています。
画像の拡大とか勾配・法線ベクトルの計算などを試してみないとこの結果だけでは特に意味は無いと思います。
(特異値分解で連立一次方程式を解くテストという意味合いしかありません)

2次曲面の特性上、エッジがはっきりしているようなものは近似しにくいと思いましたので、
入力画像には5x5のガウスフィルタを1回掛けてあります。

1. 円内が1.0、それ以外が0.0の高さを持つマップを近似した結果は以下のようになりました。
近傍5x5の25x10の行列を作って、2次曲面の係数10個を計算しました。
パラメータのガウスフィルタ0回適用です。

svd_002.png svd_014.png
     原画像         近似画像

PSNRが66ぐらいで、エッジ周辺にノイズがみられます。

2. 高さマップを近似した結果は以下のようになりました。
近傍5x5、ガウスフィルタ2回適用です。

svd_004.png svd_013.png
     原画像         近似画像

PSNRが101ぐらいで、かなり再現できています。エッジが少ないからでしょうか。

3. おまけとして、Lenna画像をグレースケール化したものを試してみました。
こちらも近傍5x5で、ガウスフィルタ1回適用です。

svd_006.png svd_012.png
     原画像         近似画像

PSNRが84ぐらいで、まずまずですが、やはりエッジ付近にノイズがみられます。
ベジエ曲面やスプライン曲面ならうまくいくのでしょうか。

次はKinectで取得した点群データをこの2次曲面近似してみようかなと思います。
Kinect持ってないですが。
どこかにKinectで取得した点群データのデータベースとかないんでしょうかね。

web拍手 by FC2
posted by シンドラー at 22:44 | Comment(0) | TrackBack(0) | Image Processing | このブログの読者になる | 更新情報をチェックする

2013年12月11日

台形補正のテスト

いつのまにか年末とか信じられませんね。
今回は、[1]などを元に色々画像処理系のことを試してみて、最終的に台形補正をしてみました。

全体の流れは以下のような感じです。
1.歪んでいる画像と、歪んでいない画像を準備
2.Harrisのコーナー検出でコーナー点を検出
3.コーナー点の強度?の大きい順に、指定した範囲以上の間隔でサンプリング
4.ICP(Iterative Closest Point)アルゴリズムを用いて対応点とホモグラフィ行列を推定
(対応点の距離にはユークリッド距離と正規化相互相関(NCC)[1][4]を使用)
5.推定したホモグラフィ行列で台形補正

ひとつずつもう少し詳しく書いておきます。

1.歪んでいる画像と、歪んでいない画像を準備

GIMP2で歪んでいる画像を作りました。

trapezoid_000.png trapezoid_001.png

2.Harrisのコーナー検出でコーナー点を検出

[1]を参考に実装しました。エッジ検出フィルタを掛けて、勾配の共分散行列を計算してその固有値から判定する感じでしょうか。
エッジ検出に5x5のSobelフィルタ、勾配値の共分散行列の平均計算に5x5のガウスフィルタを使用しました。

trapezoid_002.png trapezoid_003.png

歪ませた方はジャギーが原因で等間隔にコーナー点が出てしまっていますね…。

3.コーナー点の強度?の大きい順に、指定した範囲以上の間隔でサンプリング

強度が0より大きい点は512x512の画像で約20万点ぐらいあり、今回は20ピクセル以上離れている点という条件で上位60個をサンプリングしました。
ちょっと見えづらいですが、赤い×印がサンプリングした点です。
微妙に違う点が選ばれてしまっていますね。

trapezoid_004.png trapezoid_005.png

4.ICP(Iterative Closest Point)アルゴリズムを用いて対応点とホモグラフィ行列を推定
(対応点の距離にはユークリッド距離と正規化相互相関(NCC)を使用)

ある点は、ある点に3x3のホモグラフィ行列Hが掛けられることで得られたと考えて、AH=0の行列を特異値分解で解いてホモグラフィ行列を計算することになります[1][2]。

ただ、対応点が分かっていればそれを並べて行列Aを作ることができるのですが、今回それぞれの画像で個別に特徴点を計算しているため、特徴点ごとの対応を決める必要があります。これは、特徴点同士の距離(誤差)を計算する必要があると思われますので、今回は単純なユークリッド距離と、点の近傍5x5の(1.0−NCC)を重みづけして足し合わせたものを特徴点間の距離と定義しました。

これで特徴点間の距離の計算はできるようになりましたが、どの対応点の組み合わせが最も良いのかはわかりませんので、ICPアルゴリズムを使用して対応点を決めることにしました[3]。ICPの使い方がこれで合っているのかどうかはちょっとよくわかりません。

4.1. 3.で選んだ60点を、ランダムに5点×12グループに分けて、グループ毎にホモグラフィ行列Hiを計算
(今回、特異値分解の計算には行列計算ライブラリEigenを使用しました。)
4.2. 各Hiで各特徴量の最近傍点のペアを作成し、総距離Eiを計算
4.3. Eiがこれまでの最小距離Eminより小さければ、そのグループのホモグラフィ行列HiをHminとして保持
4.4. 500回ぐらい4.1.〜4.3.を繰返す。すべての回数が終わった時のHminが台形補正のためのホモグラフィ行列になっているはず。

本当はRANSACというものを使ってはずれ点を除去していくべきらしいです。
後、Eigenで特異値分解をしたときの注意点として、8x9の行列を特異値分解した場合、ComputeThinVにしているとVは8x9の行列、ComputeFullVにしていると9x9の行列になって、特異値が最小の特異ベクトル?は9番目になるため、ComputeFullVで計算しないとホモグラフィ行列が出てこなくて困りました。

5.推定したホモグラフィ行列で台形補正

Hが求まれば、X'=HXで変換後の座標は計算できますので、それを使って補正します。

trapezoid_001.png → trapezoid_006.png

4隅を手動で指定して得られた正解のホモグラフィ行列が左で、今回の手法で得られた行列が右です。
4点マウスでクリックして1回ホモグラフィ行列を計算すれば終わるので、どう考えても手動でやった方が高速で高精度ですよね。

[ 1.312542 0.074179 -27.6734 ] [ 1.101552 -0.05357 8.442439 ]
[ 0.107716 1.354367 -48.4918 ] [ 0.062449 1.004017 -35.8303 ]
[ 0.000365 0.000347 1.000000 ] [ 0.000292 -0.00028 1.000000]

平行移動のところとか割と違ってる気がするんですが大丈夫なんでしょうかね。
まぁ自動(といって正解の歪んでいない画像を使っていますが)でもそれなりにうまくいっているのでしょうか。
ランダムに選ぶ5点によって毎回結果が変わるのでうまくいかない場合もあります。
Harrisの特徴点より、おそらくSIFT特徴量などを使った方が精度が上がるのではないかとは思います。

[1] Jan Erik Solem 著、相川 愛三 訳,「実践コンピュータビジョン」,オライリー・ジャパン
[2] ホモグラフィ行列を求める:http://www.kimura-lab.net/wikimura/index.php/%E3%83%9B%E3%83%A2%E3%82%B0%E3%83%A9%E3%83%95%E3%82%A3%E8%A1%8C%E5%88%97%E3%82%92%E6%B1%82%E3%82%81%E3%82%8B
[3] http://www.mm.media.kyoto-u.ac.jp/research/thesis/2011/b/nakai/nakai.pdf
[4] http://navi.cs.kumamoto-u.ac.jp/~koutaki/pukiwiki/index.php?%C0%B5%B5%AC%B2%BD%C1%EA%B8%DF%C1%EA%B4%D8%A5%DE%A5%C3%A5%C1%A5%F3%A5%B0

web拍手 by FC2
posted by シンドラー at 00:29 | Comment(0) | TrackBack(0) | Image Processing | このブログの読者になる | 更新情報をチェックする