3次元空間に与えられた2次元集合間のマッチングについて
スポンサーリンク
概要
- 論文の詳細を見る
画像理解,画像認識,ロボットビジョンなどで,カメラから得られた2つのシーン間のマッチングを求めることは,画像がどのような物体を表しているか,カメラがどんな速度で移動しているか, などを求める際の重要な問題とされている.このマッチングの対象となる2つのシーンを点集合にモデル化した問題は,点パターンマッチングという名で研究されているが,多くの場合マッチングの度合の定義に最小自乗法(対応が得られた2点間のEuclid距離の2乗の総和を最小)を用いている.しかし,自動実装における産業部品の位置決めの様な許容誤差を持つ場合に最小自乗法のマッチングを適用すると,実際の距離ではなく最小自乗距離でマッチングが求まってしまう.そのため,実際の距離が許容誤差以内であるのにマッチング不可の場合や,許容誤差以上であるのにマッチングするといったような不都合が生じる可能性がある.著者らは,ミニマックス近似の観点から距離の最大値を最小にすることでマッチングを定義し,2次元平面上に存在する,対応が与えられた2つのn点集合間のマッチングがO(n^2)の手間で解けることを示した.この方法では実際の距離を用いているため,上記のような不都合は起こらない.但し,効率の点とアルゴリズムの実現性を考慮して,距離にはEuclid距離ではなく距離の座標成分の最大値をとるL_∞距離を用いている.本稿では,点集合が3次元空間内に存在する場合に対して,[2]のアルゴリズムの概念を拡張することを考える.3次元空間上に存在する,対応を与えられた2つのn点集合のマッチングが,平行移動・回転移動を用いる場合がO(n^2 log n+k)の手間で,平行移動・拡大縮小を用いる場合がO(n)の手間で求められることを示す.但し,最悪の場合K=O(n^4)となる.
- 一般社団法人情報処理学会の論文
- 1989-10-16
著者
関連論文
- 利用者インターフェースとしての文字自動配置機能(計算アルゴリズムと計算量の基礎理論)
- 3次元の点集合のL_1平面近似問題に対する線形時間アルゴリズム
- 既存のCADシステムに対する設計データベース機能の追加について
- 3次元空間に与えられた2次元集合間のマッチングについて
- 拡大縮小を考慮した点集合の正方格子度を求めるアルゴリズム
- 球面上のミニマクス施設配置問題の計算複雑度
- 平行移動する複数の点集合または線分集合に対するVoronoi図の複数さと文字配置への応用
- 重み付きL_∞距離Voronoi図の構成と文字配置問題
- 連結性を考慮した近似折れ線による曲線の階層管理
- 線形計画問題に対する乗法的罰金関数法について(線形計画法の最近の発展)