2画像間の特徴点対応の自動探索

シーンに関する知識を上手に使う

豊橋技術科学大学 岡山大学

金澤 靖 / 金谷 健一

画像間の特徴点の対応を決定することはコンピュータビジョンにおける基本的な処理である。その基本原理はテン プレートマッチングによる局所相関の探索であるが、それだけでは不十分であり、シーンに関するさまざまな知識を用 いなければ正しい対応は得られない。そこで本稿では、画像モザイク生成や画像からの

3

次元復元を想定して、シー ンに関する知識を利用した対応づけの手法の例を示す。

◎ はじめに

複数の画像間の特徴点の対応を定め ることはコンピュータビジョンの最も 基本的な処理の一つである。これは連 続ビデオ画像から隣接するフレームご とに対応を追跡する方法と、異なるカ メラで撮影した画像間の対応を直接的 に探索する方法とがある。本稿では後 者を考える。

対応する特徴点の近傍は互いに似 ているから、対応づけの基本はテン プレートマッチングによる局所的な 相関の探索である。まず

2

つの画像 から

Moravec

作用素

[1]

や

Harris

作 用素

[2]

などの特徴点抽出フィルタ

[3]

によって特徴点を抽出し、相関の高い

2

点を対応させる。これはビデオ画像 における隣接フレームのように、カメ ラのズームや回転、移動が少ない場合 に非常に有効である。

しかし異なるカメラで撮影した画像 では、視差のために対応する点の見え 方がかなり変わる。特にカメラの回転 やズーム変化があると正しい対応の局 所的な相関が低下するため、誤まった 対応が得られることが多い。そこで、

そのシーンに関する何らかの知識を利 用して対応づけの精度を高めることが 必要となる。そのような知識を「拘束

条件」と呼ぶ。

このような拘束条件は普通は各カメ ラのズーム量やカメラ間の相対的な位 置関係に依存し、一般にはこれら未知 である。したがって、その拘束条件の パラメータと正しい対応とを同時に推 定する必要がある。このような問題に 対して、RANSAC[4]や最小メジアン 法

[5]

と呼ばれるランダム投票がよく 用いられる。

これらの方法では、少数の対応候 補をランダムに選んで拘束条件のパ ラメータを計算し、その値の妥当性 を残りの対応候補から評価し、これ を繰り返す。しかし、これが有効であ るためには、選択する対応候補の中に 十分な数の正しい対応が存在しなけれ ばならない。そのため、対応候補の中 にいかにして正しい対応を多数残すか が重要となる。

これに対して、筆者らは次のよう な考え方を導入した。シーンに関す る知識として従来から用いられてい るのは、カメラの撮像の原理から「必 ず成り立つ」事実である（それらは

「幾何学的拘束条件」とも呼ばれる）。

これに対して筆者らは、実際の応用に 現れやすいシーンが「ほぼ満たす」と 思われる性質をも利用した。これは例

えば、シーンが滑らかである、ある程 度以上の奥行き変化がない、などであ り、本稿では「柔らかい拘束条件」と 呼ぶ。

このような拘束条件は必ずしも満た されるとは限らないので、満たされな いからといって排除することはせず、

複数の解の正しらしさの優先順位をつ けるために利用する。以下では画像モ ザイク生成および画像からの

3

次元復 元の応用に対して、このような知識の 活用によって対応づけの精度が向上す ることを示す。

◎ テンプレートマッチング

画像

I

の点

p(x, y)

に対応する画像

I

⁰ の点

q(x

⁰

, y

⁰

)

を求めることを考え る。対応候補点の近傍の類似度は、次 の画素値の差の二乗和で計算できる。

J

SSD

= X

K

i,j=−K

(I (x+i, y+j)−I

⁰

(x

⁰

+i, y

⁰

+j))

²

· · · · (1)

ただし

K

は近傍のサイズである。値

J

_SSDは「残差平方和」と呼ばれ、各 画素値が完全に一致したとき

0

とな る。したがって、JSSDが最小となる 点

(x

⁰

, y

⁰

)

を探せばよい。この他に「正

2

画像間の特徴点対応の自動探索

第

1

図 平面を異なる位置から撮影する

画像

I

レンズ

p

C

第

2

図 画像上の点とシーン中の位置と の関係

剛体運動 相似変換 アフィン変換

射影変換

並進

第

3

図 射影変換とその部分群

規化相関」も多く用いられる。

候補となる点は、それぞれの画像に 特徴抽出オペレータを適用して画像

I

から

M

個、画像

I

⁰から

N

個が得ら れたとする。このとき、画像

I

の点

p

から見て画像

I

⁰の点

q

との類似度 が最大でも、qから見ると

p

との類似 度が最大とは限らない。そこで、上記 の類似度を

M

行

N

列の表にまとめ て、表の中から最も類似度の高いもの を選ぶ。そして、その行および列を削 除した

M − 1

行

N − 1

列の表の中か ら同様の操作を繰り返せば、最終的に

min(M, N )

個の対応が決まる。これ

を対応の「1対

1

化」と呼ぶ

[6]。

このように決定した

min(M, N)

個 の対応はすべて正しいとは限らない。

誤った対応が含まれていると後のモザ イク生成や

3

次元復元に悪影響を与え るので、何らかの拘束条件を用いて 誤った対応を取り除く必要がある。

◎ ランダム投票

正しいデータと誤ったデータが混ざ り合った中から、正しいデータのみを 取り出す代表的な手法に

RANSAC[4]

と最小メジアン法

[5]

がある。これら はいずれも、全データから必要最低限 の個数のデータをランダムに選択し、

それから拘束条件のパラメータを計 算する。そして、残りのデータからそ の値の妥当性を評価し、これを十分多 数回行って最大の評価を得た値とそれ を支持したデータを取り出す。これに よって正しいパラメータと正しいデー

タの両方が同時に推定できる。

RANSAC

と最小メジアン法の違い

は、パラメータの妥当性の評価法の 違いである。RANSACでは計算した 値に対するデータの満足度にしきい値 を設けて、そのしきい値内のデータの 個数で評価するのに対し、最小メジア ン法では求めた値に対する満足度の全 データに対するメジアン（中央値）で 評価する。

これらを

2

画像間の対応づけに適 用するには、対応する点の満足すべ き条件が必要である。以下にこれを 解説する。

平面シーン

同じ平面を写した２画像

I、I

⁰ に 対して画像

I

の点

p(x, y)

が画像

I

⁰ の点

q(x

⁰

, y

⁰

)

に対応するとき、関係

x

⁰

= Ax + By + C P x + Qy + R y

⁰

= Dx + Ey + F

P x + Qy + R · · · · (2)

が成り立つ。これは「射影変換」と呼 ばれ（第

1

図）、シーンが十分な遠方 にある場合にも成立する

[7, 8]。

式

(2)

の分母を払って整理すれば

P xx

⁰

+Qyx

⁰

+ Rx

⁰

− Ax− By = C P xy

⁰

+ Qyy

⁰

+Ry

⁰

− Dx − Ey = F · · · (3)

と書ける。9個の係数

A ∼ R

に

0

で ない任意の数を掛けても式

(2)

は成り 立つから、射影変換を定めるには係数 間の比のみを求めればよい。

1

組の対応から

2

つの式が得られる

から、

4

組の対応があれば係数間の比 が定まる。したがって、

1

対

1

化した 対応候補から

4

組をランダムに選んで は係数

A ∼ R

を計算し、残りの対応 がどの程度よく式

(2)

を満たすか（す なわち、存在すべき位置からどの程度 ずれているか）を評価し、これを繰り 返す。

一般のシーン

画像

I

上の点

p

に対応するシーン中 の点は、点

p

とカメラのレンズ中心

C

を結ぶ直線上にある（第

2

図）。した がって、p(x, y)に対応する画像

I

⁰上 の点

q(x

⁰

, y

⁰

)

はシーン中の直線

Cp

を 画像

I

⁰に投影して得られる直線（こ れを「エピ極線」と呼ぶ）の上にある。

同じ関係が画像

I

上でも成り立つ。こ の関係は次のように表せる

[7, 9, 10]。

f

0

xx

⁰

+f

1

xy

⁰

+f

2

x+f

3

x

⁰

y+f

4

yy

⁰

+f

5

y+f

6

x

⁰

+f

7

y

⁰

+f

8

= 0 · · (4)

係数

f

0

∼ f

8は２台のカメラの配置と 各々のズーム量から決まる値である。

a

⁰

= f

0

x + f

3

y + f

6

b

⁰

= f

1

x + f

4

y + f

7

c

⁰

= f

2

x + f

5

y + f

8

· · · · (5)

とおくと、式

(4)

から画像

I

⁰上のエピ 極線の方程式が次のように得られる。

a

⁰

x

⁰

+ b

⁰

y

⁰

+ c

⁰

= 0 · · · · (6)

同様に、

a = f

0

x

⁰

+ f

1

y

⁰

+ f

2

b = f

3

x

⁰

+ f

4

y

⁰

+ f

5

c = f

6

x

⁰

+ f

7

y

⁰

+ f

8

· · · · (7)

画像ラボ 

2004.11

 

21

(e) (f) (g) (h)

第

4

図 段階的マッチングによる画像モザイク生成。

(a)

入力画像と抽出した特徴点。

(b)

テンプレートマッチングによる初期 対応。

(c)

並進を当てはめて得られる対応。

(d)

相似変換を当てはめて得られる対応。

(e)

アフィン変換を当てはめて得られる対 応。

(f )

射影変換を当てはめて得られる対応。

(g)

その対応から生成したパノラマ画像。

(h)

初期対応に射影変換を当てはめて得 られる対応。

とおくと、式

(4)

から画像

I

上のエピ 極線の方程式が次のように得られる。

ax + by + c = 0 · · · · (8)

したがって、係数

f

0

∼ f

8が分かれ ば、画像

I

中の点

p(x, y)

に対応する 点は画像

I

⁰ 中のエピ極線

(6)

上に限 定され、画像

I

⁰中の点

q(x

⁰

, y

⁰

)

に対 応する点は画像

I

中のエピ極線

(8)

上 に限定される。この事実を「エピ極線 拘束条件」と呼ぶ

[7, 9, 10]。

9

個の係数

f

0

∼ f

8に

0

でない任意 のを掛けても式

(4)

は成り立つので、

係数間の比のみを求めればよい。

1

組の対応から

1

つの式が得られる から、8組の対応があれば係数間の比 が定める。したがって、1対

1

化した 対応候補から

8

組をランダムに選ん では式

(4)

を満す係数

f

0

∼ f

8を計算 し、残りの対応がどの程度よく式

(4)

を満すか（すなわち、通るべきエピ極 線からどの程度離れているか）を評価 し、これを繰り返す。

◎ 柔らかい拘束条件

ランダム投票が有効であるために は、その前段階のテンプレートマッチ

ングで得られる対応候補ができるだけ 正しい必要がある。カメラがズームを 変えずにわずかに平行移動する場合に はテンプレートマッチングは極めて有 効であるが、ズームが変化したり、撮 影位置が大きく異なると、テンプレー トマッチングで得られる対応のほとん どが誤りとなることもある。

そこで、正しい対応が「ほぼ」満足 すると思われる「柔らかい」拘束条件 を導入する（これに対して式

(2), (4)

のように厳密に満足する条件を「硬 い」拘束条件と呼ぶ）[11]。以下、こ れを画像モザイク生成および画像から の

3

次元復元に適用した例を示す。

モザイク画像生成

カメラをシーン内の平面に平行に移 動すると、画像は単に「並進」する。

同時にカメラを光軸の周りに回転させ ると画像は「剛体運動」する。さらに ズームも変えれば画像の変換は「相似 変換」となり、傾いた面に対してカメ ラを横に移動すると「アフィン変換」

となる。これらはすべて式

(2)

の射影 変換の「部分群」であり、第

3

図の階 層性を持つ

[8]。

そこで、テンプレートマッチングで

得られた対応にいきなり式

(2)

の射影 変換を当てはめるのではなく、下位の 変換から順に当てはめる。まず、画像 の変換をおおざっぱに並進とみなして その大きさを計算する。そして、それ におおよそ合う対応に相似変換を当て はめる。次に、その相似変換におおよ そ合う対応にアフィン変換を当てはめ る。最後に、それにおおよそ合う対応 に射影変換を当てはめ、これによく合 う対応を選ぶ。このような「段階的な マッチング」によって高精度な対応付 けが可能となる

[12]。

この方法を用いた画像モザイク生成 の例を第

4

図に示す。

2

画像間の対応 は対応位置を線分で結んだ「オプティ カルフロー」で示している。変換が詳 細になるにつれて、正しい対応が増え ていることがわかる。同図

(h)

は初期 のテンプレートマッチングの結果から 直接に投票を行って得られる対応であ り、かなりの誤対応が残っている。

画像からの

3

次元復元

平面でないシーンでは前節のよう な変換の階層性が使えない。しかし、

シーンの

3

次元形状が極端に変則で ない限り、各対応を結んだ「オプティ

2

画像間の特徴点対応の自動探索

(a) (b) (c)

(d) (e) (f) (g)

第

5

図 柔らかい拘束条件を用いた一般シーンの対応づけ。

(a)

入力画像と抽出した特徴点。

(b)

テンプレートマッチングによ る初期対応。

(c)

空間相関を考慮して得られる対応。

(d)

さらに大域的整合性を考慮して得られる対応。

(e)

さらに

RANSAC

を行って得られる対応。

(f )

その対応から復元した

3

次元形状

(

上から見た図

)

。

(g)

初期対応から直接に

RANSAC

で推定した 対応。

カルフロー」の方向と大きさはある狭 い範囲に分布していると考えられる。

これを「空間相関条件」と呼ぶ。

さらに、シーンの多くの部分がほぼ 平面的にあるか、あるいはかなり遠方 にあると仮定すれば、画像間の変換は おおまかには射影変換で近似できる。

これを「大域的整合条件」と呼ぶ。

テンプレートマッチングによる類似 度と共にこれらの条件の充足度を比較 して優先順位をつけることによって、

より多くの正しい対応を得ることがで きる

[11]。

この方法を画像からの

3

次元復元に 適用した例を第

5

図に示す。条件を順 に課すことにより、対応の精度が向上 していることがわかる。同図

(g)

は、

初期のテンプレートマッチングの結果 から直接に投票を行って得られた対応 であり、得られる対応数が少ないだけ でなく、かなりの誤対応が残っている。

◎ おわりに

本稿では、2画像間の点対応を決定 するための手法を紹介した。その基本 原理はテンプレートマッチングによる 局所相関の探索であるが、それだけで は不十分であり、シーンに関するさま

ざまな知識を用いることによって対応 探索の精度が向上することを示した。

参考文献

[1] H.P. Moravec, “Towards automatic vi- sual obstacle avoidance,” Int. Joint Conf. Art. Intell., Cambridge, MA, USA, p.584, August 1977.

[2] C. Harris and M. Stephens, “A combined corner and edge detector,” Proc. 4th Alvey Vision Conf., pp.147–151, Manch- ester, U.K., August 1988.

[3] 金澤 靖,金谷健一,コンピュータビジョンのため の画像の特徴点抽出,電子情報通信学会誌, vol.

87, no. 12, pp.1043–1048, Dec. 2004.

[4] M. A. Fischler and R. C. Bolles, “Ran- dom sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,”

Commun. ACM, no.24, vol.6, pp.381–

395, June 1981.

[5] P.J. Rousseeuw and A.M. Leroy, Robust Regression and Outlier Detection, Wiley, New York, U.S.A., 1987.

[6] 金谷健一, 金澤靖, “テンプレートマッチング による対応探索の自動しきい値設定法,”電子 情報通信学会論文誌(A), vol.J86-A, no.12, pp.1502–1509, Dec. 2003.

[7] R. Hartley and A. Zisserman, Multiple View Geometry, Cambridge University Press, Cambridge, U.K., 2000.

[8] 金谷健一,形状ＣＡＤと図形の数学,共立出版, 1998.

[9] 金谷健一,画像理解—３次元認識の数理—,森 北出版, 1990.

[10] 金谷健一,空間データの数理—３次元コンピュー ティングに向けて—,朝倉書店, 1995.

[11] 金澤靖,金谷健一, “大域的な整合性を保証する ロバストな画像の対応づけ,”情報処理学会論文 誌: CVIM, vol. 44, no. Sig 17 (CVIM8), pp.70–77, Dec. 2003.

[12] 金澤靖, 金谷健一, “段階的マッチングによる 画像モザイク生成,”電子情報通信学会論文誌 (D-II), vol. J86-D-II, no.6, pp. 816–824, June 2003.

【筆者紹介】

  金澤 靖

（昭和

37

年

11

月

23

日生・

 群馬県出身

)

 豊橋技術科学大学知識情  報工学系

 〒

441-8580

豊橋市天伯  町雲雀ヶ丘

1–1

 

TEL: 0532-44-6888

 

FAX: 0532-44-6873

 

E-mail: [email protected]

〈主なる業務歴及び資格〉

 

1985

年豊橋技術科学大学工学部情 報工学課程卒業。

1987

年同大大学院 修士課程修了。富士電機

(

株

)

、群馬高 専講師を経て、現在、豊橋技科大知識 情報工学系助教授。博士（工学）。画 像処理、コンピュータビジョンの研究 に従事。

金谷健一

（昭和

22

年

8

月

12

日生・

 岡山県出身

)

 岡山大学工学部情報工学  科

 〒

700-8530

岡山市津島  中

3–1–1

 

TEL: 086-251-8173

 

FAX: 086-251-8173

 

E-mail: [email protected]

     

u.ac.jp

〈主なる業務歴及び資格〉

 

1972

年東京大学工学部計数工学科

（数理工学）卒業。

1979

年同大大学院 博士課程修了。工学博士。群馬大学工 学部情報工学科教授を経て、現在、岡 山大学工学部情報工学科教授。

IEEE

フェロー。

画像ラボ 

2004.11

 

23

テ ン プ レ ー ト マッチング

探そうとする画像の部分パタンをテンプレートと呼び、これを画像に重ねて移動しながら 比較し、最も類似した部分をみつけること。

Keyword

画 像 モ ザ イ ク 生成

写っているシーンに重複のある複数の画像を重なりに不連続がないように変形して張り合 わせ、大きな視野の画像（パノラマ画像と呼ぶ）を作ること。

オプティカルフ ロー

動画像上の各点の各瞬間の動きの速度場。