画像の弾性マッチングーパターン認識と画像工学の一接点

全文

(1)2005−AVM−50（1） 2005／10／7. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 画像の弾性マッチング. パターン認識と画像工学の一接点内田誠一. 九州大学大学院システム情報科学研究院〒福岡市東区箱崎

(2) あらまし. 本チュートリアルでは，画像の弾性マッチング法について解説する．弾性マッチングは，画像. 工学やパターン認識の分野における基本技術である．例えば，画像工学の分野においては動画像圧縮時の動き補償に利用される．一方，パターン認識の分野においては，画像間の類似度を評価する際に利用される．弾性マッチングは，ゴム膜マッチングとも呼ばれ，直感的には，一方の画像を変形させながらもう一方の画像に近づける方法である．数学的には，画像間の画素対応関係を定める次元次元写像関数の最適化問題として定式化される．この写像関数については様々なモデルが提案されている．これらモデルを概観すると共に，その最適化問題がどのように解かれるかについて解説する．.

(3)

(4)

(5) .

(6)

(7)

(8) . .

(9) !" ! ! !

(10) "

(11) !# !" !# $ % & $ # & & '()(*

(12) . .

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23) ! "

(24)

(25) #

(26)

(27) $

(28)

(29)

(30) %

(31) & &

(32)

(33) $

(34)

(35) .

(36) $

(37) % . . やオプティカルフロー ' + も同様に弾性マッチング手. まえがき. 法と考えることができる．一方，パターン認識の分本チュートリアルでは，弾性マッチング法について. 解説する．弾性マッチングは，画像工学やパターン認. 野では，画像間の類似度を評価する際に弾性マッチングが利用される '-0+．. 識の分野における基本技術である '(( () (*+．例え. ゴム膜マッチングとも呼ばれることからも判るよ. ば，画像工学の分野では，動画像圧縮において利用さ. うに，弾性マッチングは直感的には一方の画像を変. れる動き補償方式 ', -.+ が弾性マッチングの一種と. 形させながらもう一方の画像に近づける方法である．. して挙げられる．他にもステレオ対応付け '- / ).+. 数学的には，画像間の画素対応関係を定める. ( −1−. 次.

(38) 元次元写像関数の最適化問題として定式化される．を用いれば，なるべく平滑なワープ関数を求めるここの写像関数については様々なモデルが提案されて. とができる．. いる．以下本稿では，これらモデルを概観すると共. 動き推定法であるオプティカルフローも，時間的. を求め. に，その最適化問題がどのように解かれるかについ. に連続した画像間の各画素対応すなわち. て解説する．. るという意味で一種の弾性マッチング法であると言. . える．ただし，オプティカルフローの場合，2(3 の目的関数の最小化問題としてではなく，オプティカル. 弾性マッチングの定式化. . . を求. フロー拘束式と呼ばれる方程式を解くことで. . 1 と 1 を考える．ここで，は画像の第 2 3 画素の特徴量，は画像の第 2 3 画素の特徴量とする．このとき， 4 2 3 2 3 をからへの次元次元写像関数とする．写像関数はワープ関数とも呼ばれ，画像間の画素対応を定める．弾性マッチングは，次の目的関数 2 3 のワープ関数に関する最小化問題として一般に定式化される． 2 3 1 2 3 2(3. 2 3 を最小化する 6 ワープ関数が画像を基準とした際の画像の変形を表現するためである．例えば，が時間的に連続した画像であれば， 6 は動きを表すことになる．またがステレオ画像対であれば， 6 は. ここで，. 視差を表す．さらに. つの. 画像. . . . . . . . . . はであり，すなわちを通しである．また，2 3 は，つの画像 . て見た画像. 3 と. の !単純" マッチング距離である．例えば， 2. める．. . 弾性マッチングは画像間の変動 2変形3 解析に利. 2 3 1. . . . . . 2 3. . となる．このようにして評価した小化は. 2 3 はワープ関数を介. 画像の最適整合を図ることに相当. する．式 2(3 の目的関数はの最小化に際しては，様々な制約条件が課されることが多い．この制約条件とワープ関数. の定義の両者によって，実際に可能な画素. 対応付けの範囲が規定される．. . . が入 6 力画像パターンであったとすれば，は入力画像パ. が標準画像パターン，. . ターンに生じた幾何歪みを表す．画像間の類似度評価にも利用. される．すなわち弾性マッチングによって与えられる距離. . . 画像間の距離であり，従ってその最. により. . . . . 弾性マッチングは. . . 用される．これは，目的関数. してユークリッド距離を用いた場合，. . 弾性マッチングの利用先. 2. 3 1 . は，ワープ関数の. 画像. . 2 3 1 26 3

(39). によりを極力. に近づけた後. 間の距離であるためである．すなわ. ち，弾性マッチング距離は画像パターン変形を. 2)3. に生じた. によって補償した後での間の距離に. 相当する．従ってある種の変形不変距離となる．弾. も併せた目的関数が用いら. 性マッチング距離は，パターン認識における識別関. 2 3 1 2 3 5 2 3 2-3 正則化項 2 3 は，求まるワープ関数に何らかの望. 扱う手書き文字認識の分野においては，様々な弾性. 次のように正則化項れることも多い． . ましい性質を与えるためのものである．制約条件と異なり，ワープ関数. の範囲を厳密に規定すること. 数としてよく用いられる．例えば変形の多い対象をマッチングが利用されている '-0+．. . にはならないが，求まる最適ワープ関数に所望の傾. . 弾性マッチングの種類前述のように，弾性マッチングの性質は，ワープ. と制約条件に依存する．特に，ワープ関数に. 向を与えることができる．例えば， 2 3 としてワー. 関数. プ関数. ついては，パラメトリックなものとノンパラメトリッ. の. 次微分の大きさの総和 . . . . 5. . . . 5. . . . . クなものの，およびそれら両者の混合系，の - 種に大別される． −2−.

(40) . パラメトリックなワープ関数に基づく件がある．弾性マッチング問題の場合，この条件はそのまま解ける形にはならない．そこでワープ関数手法を. パラメトリックなワープ関数とは，少数のパラメー. を表す．アフィン変換 '-/+ な次元正弦波の加重和によるの. について離散化して非線形連立方程式を定め，. それを解くことになる ' (+．なおこの場合，23 あ. タで規定される関数. くまで

(41) 8 条件の離散近似条件である，. どの線形変換や，. 表現 '(7+ はその一種である．なお後者については重. 23

(42) 8 条件は最適解の必要条件であり十分条件ではない，23 非整数座標における画素値. みがパラメータとなる．このパラメータを制御変数. が必要になる，23 非線形連立方程式は数値的な手. として目的関数. 法で解くしかない，といった問題があるため，実用の. を最小化することになる．. 前述のようにパラメータは一般に少ないので，こ. 際には妥当な解を得るための工夫が必要となる．例. を導入した目的関数 2-3 を利用した. の最小化は後述するノンパラメトリックな場合に比. えば正則化項. べて計算量的に少なくて済む場合が多い．しかしな. り，粗密探索の援用などが行なわれる '. がら，. の自由度は低くなる．例えばアフィン変換. の場合には，パラメータ数は 0 個で済むが，局所的な変形に対応できない．目的関数の最小化問題は，たとえワープ関数が線形変換であっても，非線形最適化問題となる．これ. -*+．オプティカルフローも，ノンパラメトリックかつ連続的なワープ関数を用いた弾性マッチング法の一種と言える．オプティカルフローの場合，前述のように，2(3 の目的関数の最小化問題としてではなく，. に内包されているため. オプティカルフロー拘束式と呼ばれる方程式を解く. である．従って，最小二乗問題のような閉じた解を. 近似を行なったり，また正則化を採用する点 '(-+ な. は，制御変数が非線形関数. 求めるのは一般に不可能である．このため

(43) 展開 ' *+ や反復解法 '-/+ などの近似解法を利用して解くことが多い．また文献 '(.+ の手法では，各画素 2ブ. 3 が，2 3 に対応した際の誤差を. ロック32. 次ま. ことで. を求める．ただし，解を求める際に，離散. ど，上述の変分ベースの方法との共通点も多い．. 離散的な場合. での

(44) 展開近似を用いてモデル化しておき，そ. 離散的なワープ関数を用いた場合，ワープ関数は. れを用いて画像全体としての最適なアフィン変換パ. 画素の離散的な対応関係そのものとなり，目的関数. ラメータを陽に求めている．. の最小化問題はワープ関数を表現する. . 22 3

(45)

(46)

(47) 2. . . . 個の変数. 33 の最適化問題に. 帰着する．ディジタル画像を対象とする場合，こう. ノンパラメトリックなワープ関数に基した離散的なワープ関数を用いるのは，ある意味合づく手法. 3 に. 理的である．. 3 の間に制約条件が無ければ，2(3 の. 変数 2. ノンパラメトリックなワープ関数とは，各 2 おける. 3

(48)

(49)

(50) 2 . . の値 2すなわち 2 3 の対応点 2 33 を直. . 最小化問題は，. 接制御可能な関数である．幾つかのパラメータを用. . . いて間接的に関数形状を制御する )( の手法と異な. . . . . 1. . . . . . . 273 ち，より「柔らかな」弾性マッチング法を実現できる．のように各 2 3 独立の最適化問題になる．すなわこのノンパラメトリックなワープ関数は，以下のち上の各画素 2 3 毎に，最も適合する上の画ように連続的なものと離散的なものに細分される．素を探索する問題になる．この場合の弾性マッチングは摂動法と呼ばれることもある．この方法は広くり，非常に自由度の高い制御が可能である．すなわ. .

(51). 検討されているが，多くの場合，誤対応を防ぐため. 連続的な場合. に，粗密探索手法や高次元画素特徴などが援用され. 連続的かつノンパラメトリックなワープ関数を用いた場合，2(3 の最小化問題は. を変関数とする変. ている ') , -,+．. 3 の間に制約があると，問題. 一方，変数 2. . . 分問題となる．変分問題には，通常の最大最小問題. は一気に難しくなる．厳密な最適解 6 を求めようと. の極値条件にあたるものとして，

(52) 8 条. しても，上のように各変数毎の独立な最適化を行な. −3−.

(53) うことはできない ' .+．特に，. を同相写像とすべ. パラメトリックなワープ関数のもつ自由度を. く，上下左右の画素間に次のような単調連続性 '--+. より利用しながら，少数のパラメータ. の制約. 行なえる．. . . . (. (. を課すると，目的関数. . 203. の最小化問題は 9: 問. 題になり '(0+，厳密解を求めるのは事実上不可能にな. ( 行の対応関係を制約条件として第行の対応関係を定め，次にその行の対応関係を制約条件として第 5 ( 行の対応関係を定めるといっ. る．このため，第. た逐次的な近似解法が採られる '7 * 7 0 -( -)+．. 上ですべて同じ行内に対応付けられるといった制約を用いると，は疑似 . また，. の行の画素は. . . . . に. で最適化が. まとめ画像工学やパターン認識の分野における基本技術. である画像の弾性マッチング法について概観した．弾性マッチングの実体である. 画像間の画素対応を定. める次元次元写像 2ワープ関数3 について着目し，ワープ関数がパラメトリック表現されるか，ノンパラメトリック表現されるかによって，従来の弾性マッチング法を分類した．その際，こうしたワープ関数の表現に応じて，その最適化手法 2アルゴリズム3 に違いがあることも指摘した．. 次元的なものとなるが，計算量的には相当軽減された問題に帰着できる '( 0 / ( (/+．. . 弾性マッチングでは結果として，23 最適化されたワープ関数すなわち画素対関係，および 23 最小化された目的関数すなわち弾性マッチング距離，の. パラメトリックとノンパラメトリックつが求まる．前者は画像間の変動 2変形3 解析に利用される．後者はパターン認識において変形不変なの混合系識別関数として利用される．. 動画像圧縮の動き補償で採用されるブロックマッ. 本チュートリアルでは，弾性マッチングの具体的. チングは，ブロックを画素のように見るとノンパラ. な応用例については触れていない．応用に際しては，. メトリックなワープ関数を摂動法で最適化している. マッチングの対象の性質に応じてワープ関数や制約. 方法になる．一方，１ブロックに着目すると平行移. 条件ならびに目的関数をチューニングすることが重動のみであり，これは線形ワープ関数である．従っ要である．また応用に応じて計算量的に妥当な手法て，ブロックマッチングはパラメトリックとノンパを選ぶことも肝要と思われる．ラメトリックの混合系であると言える．メッシュベースの動き補償 '- + でも同様に混合系が使用される．すなわち，メッシュを構成する三角. 参考文献. 形パッチの頂点に着目すると摂動法的かつ逐次的に最適化されるされるノンパラメトリックなワープ関数であり，パッチ内に着目するとアフィン変換すなわち線形ワープ関数である ' - )+．なお，同様の手法は顔画像マッチングにも適用されている '(,+．. '(+ ; < %% = > 8 ? : !@

(54) A

(55) " : @<==: B((-C((0 (**-. パターン認識の分野では，こうした局所分割以外の混合系も提案されている．文献 '-7+ の手法では，学習フェーズとして，あるカテゴリの複数の学習パターンについてそれぞれノンパラメトリックなワープ関. ' + = = D E 8 D. !

(56) F " <@A @ =

(57) / - )--C)0/ (**7. 数を最適化し，そうして得られた最適ワープからそのカテゴリに発生しやすいワープ関数. .

(58)

(59)

(60) . . . '-+ A G D & D H & I . を統計的に推定しておく．実際にマッチングを図る. を線形和. 際には，. . . . として定義し，. . を. パラメータとして最適化する．この方法では，ノン. ) −4−. !<

(61) " : <

(62) A

(63)

(64)

(65) 7 , **-(.., ..-.

(66) ')+ & E D. !<

(67) '()+ < > E M G A : & " @ H J : E

(68)

(69) !&

(70)

(71)

(72) 4 <

(73) (7 (. C(( (*,( " =

(74) :

(75) /( (.*C( * (**, '7+ A @ @ < 9 K

(76)

(77) E !A %

(78) '(7+ < > E M G = 8 !;N

(79)

(80)

(81)

(82)

(83) " : <

(84) A "

(85)

(86)

(87) (, - 0/C /, (**0 :

(88) * / (()7C((7/ ... '(0+ & > K L !

(89) 9:

(90) " : ? '0+ K @ =K 8 E I > !A

(91) 8

(92) ) (- ))7C)7- ..- A

(93) " : ?

(94) , '(/+ = > ; < %% !> ( (*)(C(*7- (**7

(95) & A

(96) " : '/+ E @ = 8 I = D ? <

(97) A

(98)

(99)

(100) (0 , ,) C,), D A A !<

(101)

(102) (**)

(103) " @ B J L '(,+ A 8 E @ B E D

(104) 0- - 7) C70/ (**0 E 8 @ A

(105) : : K % ',+ & A !A K > !& N

(106) B4

(107) " " :

(108) ,- 0 @

(109) ) - -..C-(( ,7,,/0 (**7 (**- '*+ I & I

(110)

(111) !A

(112) '(*+ I 8 = ? <. !< .

(113)

(114)

(115) " : ?

(116) - ( ( *C H $

(117) " : ()* (*** <

(118) A

(119)

(120)

(121) * (0 -*C77 (*,/ ' .+ 8 ? : !&

(122)

(123) . " '(.+ A !:

(124) 4 : @<==: ()*C(7 (** " : @:?

(125) ( , C ,7 (**,. ' (+ ? A !@

(126) % " : ? 8 '((+ @ < H

(127) > B A !<

(128) , (,(C(,/ (*,, " E <

(129) = ' + M A% !< @

(130) 7 (77C(/( (**, . .

(131) '( + 原学内田誠一迫江博昭 !画素を単位とした

(132)

(133) 視差補償に基づくステレオ画像圧縮の検討" 情 " : ? 8

(134) (* / 報処理学会研究報告 ..)<BA)02(3 (C/ 7*7C0.) (**, ..) ' -+ M 9 I I !A '(-+ D > : I D H = !&

(135) F " < $

(136)

(137)

(138)

(139) (/ (C- (,7C .- (*,( 7 −5−.

(140) " @ = B

(141)

(142) ) - --*-70 (**).

(143) ' )+ E 9O

(144) H @

(145)

(146) : I '-)+ = L I = !<

(147) !<

(148)

(149) " @

(150)

(151) J =

(152) ,-& ( (.*C " @

(153) ((( ...

(154) -* - ()((7. (**- '-7+ 内田誠一迫江博昭 !カテゴリ固有変形の線形結合モデルに基づく弾性マッチング法" 信学論 ' 7+ H A PQ !

(155)

(156) . 2&3

(157) E,/& 0-*0), ..)

(158) F " : @<==: )* 7 (** . '-0+ = L I = !<

(159) ' 0+ < 8 ? K 8 H . " @ J = K A K

(160)

(161) !;N

(162)

(163)

(164) ,,& , (/,(C(/*. ..7 %

(165) " : @B:? 0-)C0). (**, '-/+ K M > < !<Æ

(166) ' /+ < ? I E D !@

(167)

(168) Æ . " .

(169) " : <

(170) A =

(171) : A

(172) (0 - *C)0

(173)

(174)

(175) - ) -,)C-*7 ..( (*** ' ,+ M = 8 > !L '-,+ 山田博三斉藤泰一森俊二 !類似度法の一改良 C ずらし類似度 C" 信学論

(176) E0)& (.

(177)

(178) */.*/0 (*,(

(179)

(180) $

(181) " : <

(182) A

(183)

(184)

(185) . * **) '-*+ 9 M !& (.(. (**,

(186)

(187) " : @:

(188) ( - (-C (/ (**) ' *+ : M = M 8 @ E = & D B . !< Æ

(189)

(190) ').+ 9 M = A > !:

(191) $ " : 4 @:?

(192) 07(C077 (** " @ =

(193) , & - 7 --- (*** '-.+ @ =

(194)

(195) E > ! " = : A

(196) (0 ) /.*( (*** '-(+ 杉村昌彦，飯国洋二，足立紀彦 !ツェルニケモーメントを特徴量とする次元動的計画法を用いたイメージマッチング" 信学論 2&3

(197) E,.. & ( (.(C(., (**/ '- + < A

(198) : B D @

(199) D HR

(200) !

(201)

(202) N #

(203)

(204) " :

(205) ,0 0 (. *7( (**, '--+ 内田誠一迫江博昭 !動的計画法に基づく単調連続次元ワープ法の検討" 信学論 2&3

(206) E,(& 0 ( 7(( 7, (**, 0 −6−.

(207)