形状コンテキスト

このアプローチでは、物体の形状は、物体の内部または外部の輪郭上の有限個の点のサブセットによって本質的に捉えられると仮定しています。これらは、Cannyエッジ検出器を使用してエッジからランダムな点のセットを選択することで簡単に取得できます。これらの点は、曲率の最大値や変曲点などのキーポイントに対応する必要はなく、一般的には対応しません。形状をほぼ均一な間隔でサンプリングすることが望ましいですが、必須ではありません。^{[ 2 ]}

この手順については、理論のセクションで詳しく説明されています。

正規化されたKビンヒストグラム (つまり形状コンテキスト) g ( k ) とh ( k )を持つ2 つの点pとqを考えます。形状コンテキストはヒストグラムとして表現される分布であるため、2 つの点をマッチングする際の「形状コンテキストコスト」としてχ ²検定統計量を使用するのが自然です。

${\displaystyle C_{S}={\frac {1}{2}}\sum _{k=1}^{K}{\frac {[g(k)-h(k)]^{2}}{g(k)+h(k)}}}$

この値の範囲は0から1です。^{[ 1 ]} 形状コンテキストコストに加えて、外観に基づく追加コストを追加できます。たとえば、接線角度の類似性の尺度（特に数字認識で有用）などが考えられます。

${\displaystyle C_{A}={\frac {1}{2}}{\begin{Vmatrix}{\dbinom {\cos(\theta _{1})}{\sin(\theta _{1})}}-{\dbinom {\cos(\theta _{2})}{\sin(\theta _{2})}}\end{Vmatrix}}}$

これは、角度を持つ単位ベクトル間の単位円内の弦の長さの半分です。$\displaystyle \theta _{1}}$そして$\displaystyle \theta _{2}}$その値も0から1の範囲をとります。2つの点をマッチングさせる総コストは、2つのコストの加重和で表すことができます。

${\displaystyle C=(1-\beta )C_{S}+\beta C_{A}\!\,}$

次に、最初の形状上の各点p _iと、2 番目の形状上の各点q _jについて、上記のようにコストを計算し、それをC _{i , j}とします。これがコスト行列です。

さあ、1対1のマッチング${\displaystyle \pi (i)}$形状 1 上の各点p _iと形状 2 上のq _jをマッチングし、マッチングの総コストを最小化する。

${\displaystyle H(\pi )=\sum _{i}C\left(p_{i},q_{\pi (i)}\right)}$

が必要です。これは、${\displaystyle O(N^{3})}$ハンガリー法では時間がかかりますが、より効率的なアルゴリズムもあります。^{[ 6 ]} 外れ値を頑健に処理するには、コスト行列に、一定だが妥当な大きさのマッチングコストを持つ「ダミー」ノードを追加できます。これにより、実際のマッチングがない場合、マッチングアルゴリズムは外れ値を「ダミー」にマッチングします。

2 つの形状上の有限個の点間の対応関係の集合が与えられた場合、変換${\displaystyle T:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}$任意の点を一方の形状から他方の形状にマッピングするように推定することができます。この変換にはいくつかの選択肢があり、以下に説明します。

さて、2つの形状間の形状距離${\displaystyle P\!}$そして${\displaystyle Q\!}$この距離は、以下の3つの項の加重和になります。

形状コンテキスト距離：これは、最適なマッチングポイントにおける形状コンテキストマッチングコストの対称的な合計です。

${\displaystyle D_{sc}(P,Q)={\frac {1}{n}}\sum _{p\in P}\arg {\underset {q\in Q}{\min }}C(p,T(q))+{\frac {1}{m}}\sum _{q\in Q}\arg {\underset {p\in P}{\min }}C(p,T(q))}$

ここで、T (·) はQの点をPの点にマッピングする推定 TPS 変換です。

外観コスト：画像の対応関係を確立し、一方の画像を適切に歪ませてもう一方の画像に一致させた後、対応する画像点の周囲のガウス窓における輝度差の二乗の合計として外観コストを定義できます。

${\displaystyle D_{ac}(P,Q)={\frac {1}{n}}\sum _{i=1}^{n}\sum _{\Delta \in Z^{2}}G(\Delta )\left[I_{P}(p_{i}+\Delta )-I_{Q}(T(q_{\pi (i)})+\Delta )\right]^{2}}$

どこ${\displaystyle I_{P}\!}$そして${\displaystyle I_{Q}\!}$グレースケール画像（${\displaystyle I_{Q}\!}$（歪み後の画像）${\displaystyle G\!}$これはガウス窓関数です。

変換コスト：最終コスト${\displaystyle D_{be}(P,Q)\!\,}$これは、2つの画像を位置合わせするために必要な変換量を測定するものです。TPSの場合、これは曲げエネルギーとして割り当てられます。

2つの形状間の距離を計算する方法がわかったので、ここで計算した形状間の距離を距離として定義した最近傍分類器（k-NN）を使用できます。これをさまざまな状況に適用した結果は、次のセクションで示します。

著者であるSerge BelongieとJitendra Malikは、MNISTデータベースでこの手法をテストしました。現在までに、50以上のアルゴリズムがこのデータベースでテストされています。このデータベースには、60,000の例からなるトレーニングセットと、10,000の例からなるテストセットがあります。この手法のエラー率は、20,000のトレーニング例と3-NNを使用して0.63%でした。発表当時、このエラー率は最低でした。現在、最低エラー率は0.18%です。^{[ 10 ]}

著者らは、類似性に基づく検索の性能を測定するコア実験CE-Shape-1パートBを実施し、MPEG-7形状シルエットデータベースで実験を行った。^{[ 11 ]}このデータベースには70の形状カテゴリがあり、形状カテゴリごとに20枚の画像がある。検索スキームの性能は、各画像をクエリとして使用し、上位40件の一致における正しい画像の数を数えることでテストされる。この実験では、著者らは各形状からサンプリングされる点の数を増やした。また、データベース内の形状は回転または反転されている場合があるため、著者らは参照形状とクエリ形状間の距離を、クエリ形状と、変更されていない参照、垂直反転、または水平反転のいずれかとの間の最小形状距離として定義した。^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}これらの変更により、2002年当時最高の76.45%の検索率を達成した。

形状コンテキストに関する次の実験では、コロンビアオブジェクトイメージライブラリ（COIL-20）にある20種類の一般的な家庭用品を使用しました。各オブジェクトはデータベースに72のビューがあります。この実験では、各オブジェクトについて等間隔のビューでメソッドをトレーニングし、残りのビューをテストに使用しました。1-NN分類器を使用しました。著者らはまた、形状コンテキストの類似性とk-メドイドクラスタリングに基づく編集アルゴリズムを開発し、パフォーマンスを向上させました。^{[ 4 ]}

形状コンテキストを使用して、データベースからクエリ商標に最も近い一致する商標を取得しました（商標侵害の検出に役立ちます）。アルゴリズムによって視覚的に類似した商標が見落とされることはありませんでした（著者が手動で確認）。^{[ 2 ]}