投影距離法( Projection distance method )

投影距離法とは

分類するためのアルゴリズムで、例えばある文字はどこのクラスに属しているかなどOCRの分野で使われたりします。画像処理のパターン認識では部分空間法という方法に属する方法です。

投影距離法は意外と知られていません。なかなか面白いアルゴリズムです。実際に手書き文字などのフィールドでは加重方向指数ヒストグラム法と本学習方法を利用して、精度がとても話題になりました。(蛇足ですが加重方向指数ヒストグラム法はHoGというアルゴリズムに酷似していて、個人的にはもっと有名に慣れたのになぁという事を覚えています。機会がこの特徴量はご紹介します。)

さて、投影距離法は感覚的にどういうものかを簡単に説明すると、

「一度ある空間に写像してやる、そのなかで距離が最も近かったものをそのクラスとする」

というものです。

投影距離法理解のため、まずは単純投影距離法を説明し、そのあとに投影距離法を説明します。改良投影距離法というものがありますが、投影距離法の改良版ですので投影距離法さえ押さえておけばあとは比較的スムースに入っていけます。まず、単純投影距離法について簡単に説明します。

単純投影距離法

各クラスの平均と比較して、距離が近いものをそのクラスに属する事にするという方法です。詳しくご説明します。

今クラスが2つあったとして、それぞれのクラスの平均を求めます。それぞれをM1, M2とします。

そして、未知の点Xがあったとして、このクラスがどちらの点に属するのかというのを決めたいとして、それを知るには、XとM1、XとM2の距離のうち短い距離で決定するというものが、単純距離法です。数式で表すと以下になります。

min( abs( X – M1 ), abs( X – M2 ) )

すごい簡単です。各集合(各クラス)の平均値との距離を求めればいいだけですし、直感的にわかり易いと思います。

■投影距離法とは

あるクラスの空間において、そのクラスの空間にある超平面との距離を求め、最小のものそのクラスに属するとする方法です。

具体的にはクラス毎にPCAを行います。例えばクラスが10個あれば10回PCAを行い、各クラス毎に固有ベクトルが求めます。(その際の固有ベクトルの数は任意で、通常寄与率等で決めます。PCAについては、別途参考資料を作成します。)

例えば、あるクラス(C1)において複数の固有ベクトルを得たと仮定します。一つの固有ベクトル(E1)を取り出します。固有ベクトルE1で張られる軸と直交している超平面と、Xの距離、これを投影距離と呼びます。今、超平面の式はわからないので、ある点を超平面を構成している点(A)として仮定し、点Aはクラス全体の平均の点にします。超平面を構成している点Aがあれば、 X と超平面までの距離がわかるのです。(この超平面はE1と直交していることをお忘れずに)

超平面までの距離は三平方の定理により求まります。

まず、AからXまでのベクトル(V1)を求めます。

続いて、V1ベクトルを固有ベクトルで変換し、その超平面上に射影してベクトルV2を求めます。固有ベクトルはその空間を構成している軸(基底ベクトル)ですので、その固有ベクトルの転置とV1かけるだけでと、V2が求まります。(とても説明が難しい。。。)

この2つが出たら、V1とV2のベクトルがあるので、超平面までのベクトルV3が求まります。V3の長さが超平面までの距離となります。まさに三平方の定理です。

このように、空間に変換して求める方法を一般的に部分空間法と呼びます。Projection Distance Methodは一種の部分空間法となります。部分空間法は利点もあれば、欠点もあります。例えばクラスを追加しやすかったり、判定が高速におこなえます。欠点もあり、固有ベクトルで変換したのが必ずしも最適なのか、というそもそも論も言われます。

参考文献

C. -L. Liu, K. Nakashima, H. Sako, and H. Fujisawa, “Handwritten digit
recognition: benchmarking of state-of-the-art techniques,” Pattern
Recognition, vol. 36, pp. 2271-2285, 2003.

おすすめの記事

投稿者: 等々力 康弘

画像処理エンジニア。組み込みソフト出身。 株式会社モルフォにてR&D部門、主に機械学習業務に携わり、顔認識&顔検出のアルゴリズム開発に従事。国内特許数件、国際特許1件。 モルフォ社退社後、株式会社Dynaptico創業(CEO)。アメリカ人、スウェーデン人と3名とフードデリバリーサイトmaishoku.comを立ち上げる。社長業の他、開発業務においてバックグラウンド関連全般(Djangoを用いいたバックエンドサーバ&APIサーバーの作成、 リバースプロキシなどの負荷分散サーバ関連、OCRプログラムの作成、CISCOルータの管理, 、seleniumを用いたテストサーバーの構築、Androidアプリの開発等々)に携わる。 2019年DynapticoのCEOを辞職。 2020年2月にComputer Scienceに特化した株式会社OctOpt創業。 OSはUbuntu。Appleが苦手。Swiftのバージョンアップ対応とか死ぬほど嫌い。 Python/C++/C Twitter: @rocky_house シフト自動調整スケジュールサイトをVue.js+graphene djangoで構築. https://www.allshifter.com

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です