2026年6月：テンプレートマッチング
2026年6月：テンプレートマッチング
今月は，私が初めて画像認識の研究に触れたとき，つまり文字認識の研究を行った時に使った「テンプレートマッチング」について，当時考えていたことを述べることにする．
大学の学部4年生で配属された研究室は文字認識の研究室であった．もともと計算機でプログラムを書くことは好きであったが，他人の論文をコツコツと読み勉強するのは好きではなかった．すでに文字認識などのパターン認識では，さまざまな理論的な研究は開発されていたが，そのような理論を勉強することなく実現できる直感的な手法としてテンプレートマッチングがあった．例えば手書きのカタカナ文字「ア」を認識するためには，「ア」の標準的なパターンつまりテンプレートと入力パターンを重ね合わせ，その重なりが大きければそれを「ア」とする手法で，直感的でわかりやすい手法である．しかし，手書き文字の場合には少し変形するだけで重なりが悪くなるために，高い性能はでない．
修士１年に進学した時に，同期の４年生で学部で卒業した学生が試していた複合類似度をテンプレートマッチングに導入した．複合類似度はテンプレートマッチングとの相性は非常によく，すぐに試すことはできたが，やはり手書き文字の大きな変形では性能は出ない．ちなみに複合類似度は変形の少ない活字文字認識では高い性能が出る手法である．変形を生成させて変形に対応させるなどの新たなアイデアは出し，テンプレートマッチングベースの手法でも性能は向上したものの，当時の最先端の手法に比較すると性能は高くなかった．
現在の論文の採択の状況では，共通のデータベースを用いたベンチマークで最先端の手法と同等以上の性能がでなければ評価されないという厳しい状況であるが，当時のパターン認識分野の状況では，アイデアが面白ければ，部分的であっても性能が向上すれば論文に採択される時代であった．そのために，幸いにもこの変形を生成してマッチングを行うという手法は論文として採択された．当時の指導教員の多大なる支援のおかげでもあるが，これが私の最初の雑誌論文[1]となった．現在のパターン認識分野の論文評価がなぜこんなに厳しくなっているかという理由は，非常に多数の研究者が同じ分野で研究していて差別化が難しい分野となっているためかもしれない．一方，当時のパターン認識はまだ発展途上で研究者の数も少なく，分野を盛り上げたいという考え方が互いにあったためだと思う．新しい研究分野を開拓することがいかに大切かということを改めて感じる．
またシンプルな手法は直感的にわかりやすく実装もしやすいが，高い性能はなかなか出せないことも感じた．世の中そんなに甘くはないのである．但し，後述することになるが，シンプルで直感的な手法は適用範囲が広いことが多く，この時の苦労した経験は後で大いに参考になった．詳細については後日書くことにする．
[1] 村瀬 洋, 木村 文隆, 吉村 ミツ, 三宅 康二, "パターン整合法における特性核の改良とその手書き平仮名文字認識への応用," 電子情報通信学会論文誌, J64-D, No.3, pp.276-283, 1981/03/01
前回述べたテンプレートマッチングについてさらに深堀してみる．シンプルなテンプレートマッチングは直感的にわかりやすいが，様々な問題点がある．手書き文字認識をテンプレートマッチングで実現することを考えたときに，手書きなどにより変形した形状（入力文字）と標準的な形状（テンプレート）との画像的な重なりをよくする必要があるが，それを実現するには2種類の方法が考えられる．
第１の手法は，前処理として入力文字の変形を正規化する方法である．入力文字のサイズの変動や，縦横比などのアスペクトの変動，位置の微妙な変動は，サイズ，アスペクト比，位置などを一定値にするアフィン変換などで比較的に簡単に正規化できる．しかし，もう少し本質的な手書き特有の非線形な変形を正規化するためには，文字のクラスを変えないレベルの変形を実現するモデルが必要となり，そのモデルは複雑であり，手書き変形を吸収して正規化することは極めて困難である．
第２の手法は，テンプレート側を様々に変形させて入力文字と画像的な重なりが良くなるようにすることである．つまりテンプレートをもとのテンプレートから複数生成することである．ここでもやはり，文字のクラスを変えないレベルの変形を実現するモデルがなければ，テンプレートの生成は困難である．
第１の手法と第２の手法は，どちらも複雑な変形のモデルが必要であり，本質的には両者は同じことかもしれない．しかしながら，テンプレートマッチングという直感的な手法を考える上では少し異なる．もともと画像は画素から構成されていて，その画像の自由度は非常に大きい．一方で，その自由度に比較して文字のクラスは極めて少ない．つまり広大な画像の空間の中で意味のある文字は非常に局在していることになる．テンプレートを様々に変形した場合に，多くの変形は文字としては不自然なものになったとしても，別の文字のクラスにはならない．その多数の変形の中でどれか一つでも入力文字と画像の重なりが良くなれば良いと考えることは，直感的に納得しやすい．逆に，手書きにより変形した入力文字を更に様々に変形させ，さまざまに正規化すればどれかが重なるかもしれないと考えれば，同じ操作を行っているともいえる．しかし，直感的には手書きにより変形した入力文字をさらに変形させて，これが正規化になるとするのは，直感的な納得性は低い．
整理すると，文字の大きさや位置などを前処理として正規化することは直感的に受け入れやすい．一方で，変形した入力文字を更に複雑な変形により正規化することと，テンプレートを変形させることは，本質的には同じであるが，標準的なテンプレートを変形させて新しいテンプレートを生成するほうが，直感的には納得性が高いと思われる．直感的に納得性のある手法のほうが，さらにそこに工夫を積み上げていくことがしやすいために，総合的に考えるとテンプレートを生成する手法のほうが優れているように思える．
前回は，テンプレートマッチングの際に，入力パターンが変形するときの対応について述べた．その対応の一つとして，テンプレートを変形させることによりテンプレートを複数生成する手法を述べた．その結果として，入力パターンを複数のテンプレートと照合する必要が発生する．特に，テンプレートの生成数を多くし，それら全てと照合すると，処理量が膨大になり，計算時間が長くなり好ましくない．多数の学習サンプルをもちいて少数の識別関数を学習するというアプローチも考えられるが，ここでは，より直感的でシンプルなテンプレートとの照合を考えている．
一つの入力パターンとあるクラスの多数のテンプレートを照合するときには２つの考え方が存在する．照合の程度を類似度という数値で表現すると，第１の考え方は１つでも高い類似度があればそれをそのクラスとの類似度とする手法であり，第２の考え方はすべてのテンプレートとの類似度の平均値をそのクラスとの類似度とする手法である．つまり，各テンプレートとの類似度の最大値を最終的なそのクラスとの類似度とする手法と，各テンプレートとの類似度の平均値をそのクラスとの類似度とする手法であり，それぞれメリットとデメリットが存在する．入力画像の広大な空間の中で局所的に存在する文字パターンのようなクラスを認識する場合には，最大値が好ましいと考えられる．このような特徴空間の中では，それは文字とは異なるようなパターンを雑に生成しても最大値の場合は問題ないが，平均値とするとそれが悪さをする可能性があるからである．
文字認識における複合類似度の式は，固有ベクトルと，固有値から構成されていて，多数のテンプレートにはかくして固有ベクトルの数が少なければ処理は高速化されることになる．また，その式を変形すると，複数のテンプレートとの類似度の二乗平均と一致する．一方で複合類似度法と類似した手法に部分空間法がある．部分空間法では固有値を使用せずに，少数の固有部ベクトルが作る空間に入ればそのクラスとする手法である．この両者を比較すると，直感的には，複合類似度は複数のテンプレートとの照合の平均的な尺度であり，部分空間法は複数のテンプレートとの類似度の最大値をそのクラスとの類似度とする手法に類似している．文字認識においては部分空間法のほうが高い性能が出ると思われる理由は，前に述べたとおりである．
関連して，多数のテンプレートと照合する場合の統計的な定石は，主成分分析などのように近似的に低次元の空間に変換し，その中で照合すれば高速になる．テンプレートの低次元化は認識のたびに行う必要はなく，事前に１回低次元化しておけば良いからである．これらの３つの手法の関係を，式の変形で追ってみると複数のテンプレートとの照合の問題の意味が，直感的により明確になると思う．
多数のテンプレートとの照合を効率的に行う手法として複合類似度と部分空間法がある．ここでいう多数のテンプレートとは多数の学習パターンのことと考えても良い．どちらの手法も多数のテンプレートを少数のベクトル（固有ベクトル）が作る部分空間で表現している．前回説明したように複合類似度は等価的に入力パターンと複数のテンプレートとの類似度の二乗平均になるし，部分空間法は入力パターンがその部分空間にどの程度含まれるかを示しているが，これは多数のテンプレートとの類似度の最大値を最終的な類似度にする手法に近いものがある．
どちらの手法もメリットやデメリットがあるとしたら，ここで考えられるのは両者の中間的な類似尺度があっても良いのではないかということである．ここで式を見てみると，複合類似度は書く固有ベクトルに固有値の重みを掛けているのに対し，部分空間法は重みが全て１ということである．つまり，部分空間法を表現する各ベクトルの重みをもう少し柔軟に変更すれば両者の良いところを合わせたような類似尺度ができるのではないかということである．
重みを様々に変化させる実験を行ったところ，文字認識のような対象では，部分空間法では各重みが1になっているのを少し変更し，重みを少し制限すると性能が上がる結果が得られた．実験の詳細は，文献[2]を参照して欲しい．物理的な意味は少し不明確になるが，別の観点から見て，形式的に２つの手法の中間の式を構成することにより，2つの手法の中間的な特性を得るアプローチもあるということを感じた．
[2]村瀬 洋, 杉浦 光, 吉村 ミツ, 三宅 康二, "手書き平仮名文字認識における複合類似度的手法の応用効果," 昭和53年度電気関係学会東海支部連合大会講演予稿集, p.378, 1978