Co-occurrence Probability-based Template Matching(CPTM)

1. 概要
　Co-occurrence Probability-based Template Matching(CPTM)はテンプレートマッチングの高速化を目的として， 照合に用いる画素数をごく少数(全体の1%未満)に削減する手法です． 照合の信頼性の高い画素を選択するために， 複数画素の濃度共起発生確率によって， テンプレート画像において各画素がどの程度強くその画像を特徴づけることに寄与しているのかを算出し， 画像を強く特徴づける画素を選択します．


2. 濃度共起ヒストグラム
　画素の独自性を決定づける濃度共起発生確率は画素対の濃度共起ヒストグラムをもとに算出されます． 最も簡単な濃度共起ヒストグラムについて説明します．
　テンプレート画像において，始点pと変位ベクトルdだけ離れた終点qからなる画素対を考え， それぞれの画素値をインデクスとした2次元配列に，画像内での濃度値ペアの発生回数を記録します． この2次元配列が濃度共起ヒストグラムです．




3. 濃度共起ヒストグラムの性質
　変位ベクトルdが短い場合，例えばd(+1,0)のときは対角成分に頻度値が集中します． また，変位ベクトルが長くなることで，周辺部分への頻度値の分布が増加します．



　2値画像に近い画像では，頻度値が偏ります．例えば下の画像では， 高い画素値同士のペア(前景部分)と低い画素値同士のペア(背景部分)が共起ヒストグラム上で分離されます．




4. 濃度共起発生確率
　共起ヒストグラムの頻度値の各行ごとの総和を1になるように正規化することで画素対の濃度共起発生確率Pc(q|p)は計算されます． この画素対の発生確率を用いて，n画素で構成される画素パターンの濃度共起発生確率は， 画素Pが濃度値pという条件下でn-1個の終点画素Q₀,Q₁,Q₂,..., Q_n-2が同時にq₀,q₁,q₂,...,q_n-2をとる条件付き確率 Pc(q₀,q₁,q₂,...,q_n-2|p) によって計算できます．


5. 近似計算による低消費メモリな濃度共起発生確率計算
　n画素共起の画素パターンの発生確率の計算には，n次元の共起ヒストグラムを生成する必要があるため， 必要となるメモリ量が膨大です． そこで，n-2個の終点画素の画素値は独立であると仮定すると，この条件付き確率を，画素Pが濃度値pをとる 確率Ph₁(p)と，画素対の濃度共起発生確率Pc(q|p)を用いて以下のように近似表現します．

　以上の式では，n画素共起の画素パターンの発生確率の計算は，画素対の共起ヒストグラムから算出される発生確率のみで済むため， 必要となるメモリ量が大幅に削減されます． なお，終点画素の幾何学関係は変位ベクトルd₀,d₁,d₂,...,d_n-2 によって決定されます．


6. 参照画素選択
　テンプレート画素において濃度共起発生確率の低い画素はその画像を特徴づける独自性の高い画素とみなし， 所望の画素数を満たすまで，発生確率の低い画素から順に照合に用いる参照画素として選択します． このとき，似たような発生確率の画素が複数存在する場合はランダムに選択します．以下は，選択された参照画素の例です．