幾何学的ハッシュ: 画像の認識とマッチングのための効率的なアルゴリズム

By Fouad Sabry

幾何学的ハッシュとは何ですか

コンピューター サイエンスでは、幾何学的ハッシュは、アフィン変換を受けた離散点によって表される 2 次元オブジェクトを効率的に見つけるための方法ですが、他のオブジェクト表現や変換に対する拡張機能も存在します。 オフライン ステップでは、点の各ペアを幾何学的な基礎として扱うことによって、オブジェクトがエンコードされます。 残りの点は、2 つのパラメーターを使用して、この基底に関して不変の方法で表現できます。 各点について、その量子化された変換座標がキーとしてハッシュ テーブルに格納され、基底点のインデックスが値として格納されます。 次に、新しい基点のペアが選択され、プロセスが繰り返されます。 オンライン (認識) ステップでは、ランダムに選択されたデータ ポイントのペアが候補ベースとして考慮されます。 各候補基底について、残りのデータ ポイントが基底に従ってエンコードされ、オブジェクトからの可能な対応関係が以前に構築されたテーブルで見つかります。 十分に多数のデータポイントが一貫したオブジェクト基底をインデックス化する場合、候補基底は受け入れられます。

どのようなメリットがあるのか

(I) 以下のトピックに関する洞察と検証:

第 1 章: 幾何学的ハッシュ

第 2 章: 解析幾何学

第 3 章: デカルト座標系

第 4 章: 2 寸法 コンピュータ グラフィックス

第 5 章: 座標系

第 6 章: 変換 (幾何学)

第 7 章: ハフ変換

第 8 章: スケール不変特徴量変換

第 9 章: ホモグラフィー

第 10 章: 幾何学的特徴の学習

(II) 幾何学的ハッシュに関する一般のよくある質問に答える。

(III) 多くの分野で幾何学的ハッシュを使用する実際の例。

この本は誰に向けたものなのか

専門家、学部生、大学院生、愛好家、趣味人、およびあらゆる種類の幾何学的ハッシュに関する基本的な知識や情報を超えたいと考えている人。

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: May 11, 2024

Book preview

第 1 章: 幾何学的ハッシュ

さまざまなオブジェクトの表現と変換に拡張がありますが、コンピューター サイエンスでは、幾何学的ハッシュを使用して、アフィン変換を受けた離散点で表される 2 次元のオブジェクトを効率的に配置します。オフラインでは、ポイントの各ペアがオブジェクトをエンコードするための幾何学的基礎として使用されます。2 つのパラメーターにより、残りの点の基底不変量表現が可能になります。ハッシュ テーブルは、各キーの基底点のインデックスと、各値の量子化された変換された座標のペアを保持します。その後、この手順が繰り返され、今回は異なるベーシスポイントのセットが使用されます。オンライン(認識)フェーズでは、データポイントの任意の組み合わせが潜在的な基盤として評価されます。オブジェクトと各候補基底の間の実行可能な対応関係を見つけるために、残りのデータポイントは基底に従ってエンコードされます。データポイントの十分に大きな割合が定数オブジェクト基底を指している場合、候補基底が受け入れられます。

コンピュータビジョンでは、幾何学的ハッシュは、2Dおよび3Dオブジェクト認識、幾何学的ハッシュを使用したオブジェクト認識のために最初に提案されました。

入力画像にモデル画像が見えるかどうかを確認したいとします。

幾何学的ハッシュは、これを実現するために使用できる方法です。

この手法は、データベース内の多数のオブジェクトの中から 1 つのオブジェクトを識別するために使用できます。 このシナリオでは、ハッシュ テーブルは、オブジェクト モデルの姿勢データと基本インデックスの両方を追跡する必要があります。

例をわかりやすくするために、いくつかの点特性を使用し、それらの記述が座標のみから来ると仮定します(実際には、SIFTなどのローカル記述子をインデックス作成に使用できます)。

モデルの定義特性を学習します。

5つの特徴点が座標を持つモデル画像にあると仮定し (12,17); (45,13); (40,46); (20,35); (35,25) ます。

特徴点の座標を記述するための基礎を提供します。

2 次元空間での相似変換の基礎となる 2 つの点。

始点は、2つの点(P1、P2)を結ぶ線の中間に位置し、ケーススタディのP4では、 x' 軸はそのうちの1つに向けられ、直 y' 交して原点を通過します。

スケールは、 x' 両方のベーシスポイントの絶対値が1になるように選択されます。

その基盤に関連して物事がどこにあるかを説明してください。

新しい座標軸への変換を計算します。

ノイズに対する認識の回復力を高めるには、座標を離散化する必要があり、0.25 単位のビンが使用されます。

したがって、座標を取得します (-0.75,-1.25); (1.00,0.00); (-0.50,1.25); (-1.00,0.00); (0.00,0.25)

フィーチャをインデックスとしてハッシュ テーブルを使用して、基盤を格納します (この場合は変換された座標のみ)。照合する項目が 2 つ以上ある場合に、基底ペアで格納する項目の数。

新しい基底ペアに切り替えて、そこから続行します(ステップ2)。オクルージョンに対処するには、これが不可欠です。線形でないすべてのペアが理想的にリストされている必要があります。ペア(P1、P3)が選択された2回の反復の後、ハッシュテーブルを提示します。

ハッシュテーブル:

ほとんどのハッシュテーブルでは、重複するキーを別々の値に関連付けることはできません。

したがって、実際には、基底キー (1.0, 0.0) と (-1.0, (ハッシュテーブル、値 0) はエンコードされません。

与えられた画像で視覚的にアピールできるポイントを見つけます。

ランダムな開始点を選択します。入力画像は、ターゲットアイテムが存在するかどうかを判断するための適切な任意の基盤がない場合、ターゲットアイテムを含まない可能性があります。

新しい座標系の特徴点の位置を詳細に記述します。結果の座標の従来の量子化を実行します。

入力画像の変換されたポイント フィーチャをハッシュ テーブルと照合します。ポイント フィーチャが同じか非常に類似している場合は、関連する基準のカウント (およびオブジェクトのタイプ (存在する場合) ) を上げる必要があります。

ある基底のカウントが閾値よりも大きい場合、この基底はステップ2で選択した画像基底に対応する可能性が高い。これを行うには、まず画像の座標系をモデルの座標系(架空のオブジェクトの場合)に変換します。正常に動作する場合、アイテムは検索されます。そうでない場合は、前の手順に戻ります。

このアプローチで処理できる変換は、サイズ、位置、および向きの変換のみであるように思われます。ただし、項目は、ミラー イメージ形式で提供されたイメージに既に存在している可能性があります。したがって、オブジェクトは幾何学的ハッシュによっても検出可能である必要があります。ミラー化されたオブジェクトは、2 つの異なる方法で識別できます。

ベクトルグラフの左側を正にし、右側を負にします。x を掛けたときに同じ結果を得るには、-1 を加算するだけです。

トライアドを出発点として使用します。これにより、反射(またはオブジェクト)を識別できます。幾何学的ハッシュの別の方法は、その基礎として3つの点のセットを使用します。

ハッシュは、上記のように、高次元データに対しても同様に機能します。3次元データの基礎には3つのポイントが必要です。X 軸は最初の 2 つの点で定義され、Y 軸は 3 番目の点 (最初の点を含む) で定義されます。右手の法則を使用して、軸を作成し、z軸はそれに垂直になります。結果の基底は、ポイントが入力される順序の影響を受けます。

{チャプター1終了}

第 2 章: 解析幾何学

解析幾何学は、しばしば座標幾何学またはデカルト幾何学と呼ばれ、デカルトの観点から幾何学の研究に関係する数学の一分野です。合成幾何学はこれの反対です。

物理学、工学、航空、ロケット工学、宇宙科学、宇宙旅行はすべて解析幾何学を利用しています。これは、代数幾何学、微分幾何学、離散幾何学、計算幾何学など、現代の幾何学のいくつかの分野の基礎です。

平面、直線、円を含む方程式を扱う場合、通常、直交座標系が使用されます。幾何学では、2次元ユークリッド平面と3次元ユークリッド空間が研究されます。解析幾何学は、通常、教科書で定義および教えられているように、数値的な意味で幾何学的形状を作成および表現し、これらの表現から数値情報を抽出することに関係しています。カントール・デデキント公理は、線形連続体の幾何学における計算が実数の代数のみを使用して実行できることを保証します。

ギリシャの数学者メナエクモスが解析幾何学を開発したのは、問題を解決して定理を証明するための座標の使用に似た手法を使用したためであると主張されてきました。

11世紀のペルシャの数学者オマル・ハイヤームは、幾何学と代数学の間に強い関係があることに気づき、数値代数と幾何代数のギャップを埋めるのを助けたとき、正しい方向に進んでいました:248

解析幾何学は、ルネ・デカルトとピエール・ド・フェルマーによって独立して発明され、解析幾何学の代名詞であるデカルト幾何学はデカルトの名前を冠しています。

デカルトは、1637年に出版された『理性を正しく方向づけ、科学における真理を探究する方法に関する言説』の付録である『幾何学』と題するエッセイで、方法論を大きく進歩させました。

彼の母国語であるフランス語、その理論的基礎などで完全に構成されたLa Geometrieは、ヨーロッパにおける微積分学の発展の基礎を築きました。

この作品は当初、懐疑的な目で見られたが、その理由の一つは、議論の多くの穴と数学のもつれが原因でした。

デカルトの傑作は、1649年にファン・スホーテンがラテン語に翻訳し、注釈を加えた後(そして彼がその作業を続けた後)まで、それが何であるかを認識していませんでした。

この取り組みの結果、デカルトはより複雑な方程式を解くことを任され、より高度な多項式方程式を処理するための技術を洗練させる必要がありました。

レオンハルト・オイラーは、座標法を用いて空間の曲線と曲面を体系的に調査した最初の人物です。

解析幾何学では、平面に座標系が導入され、各点に 2 つの実数が割り当てられます。ユークリッド空間の各点にも 3 つの座標が割り当てられます。座標の有意性は、選択した参照点によって決まります。座標系にはさまざまな種類がありますが、最も一般的な座標系は次のとおりです。

デカルト座標は、各点が水平位置を表すx座標と垂直位置を表すy座標を持ち、最も広く使用されている座標系です。これらは通常、ペア式 (x, y) として表されます。3次元ユークリッド空間のすべての点は、この方法を使用して、順序付けられた3つの座標(x、y、z)で表すことができます。

極表記では、平面のすべての点は原点からの距離 r と角度 θ で表され、θ  は通常、正の x 軸から反時計回りに測定されます。

この表記は、点のペアの標準的な表記が (r), θ) の場合に使用されます。

2次元のデカルト座標は、次の式を使用して極座標に変換できます。

{\displaystyle x=r\,\cos \theta ,\,y=r\,\sin \theta ;\,r={\sqrt {x^{2}+y^{2}}},\,\theta =\arctan(y/x).}

円柱座標または球座標を使用して、この座標系を 3 次元に拡張できます。

円柱状の参照フレームを使用して、空間内の任意の位置のz高さ、z軸からの半径r、およびxy平面への投影が水平軸に対して行う角度θを識別するために使用されます。

球を基準として使用すると、空間内のすべての点は、原点からの距離 ρ、xy 平面への投影が水平軸に対して行う角度 θ、および z 軸に対する角度φによって表されます。

物理学では、角度の名前を入れ替えるのが一般的です。

解析幾何学、任意の座標方程式は、平面の領域、特に方程式の解のグループ、または軌跡を定義します。

たとえば、x 座標と y 座標が等しい場合の平面上のすべての点は、方程式 y = x に対応する座標のセットで表されます。

これらの点によって形成される線は、この線が式y=xを有すると考えられる。

一般に、線はxとyの線形方程式で記述され、二次方程式を使用して円錐断面を定義でき、さらに、より複雑な方程式が複雑な図を特徴付けます。

方程式 x2 + y2 = r2 は、原点 (0、A 円 (中心 0、半径 r) を中心とする任意の円の方程式です。

代数的線形方程式は、デカルト平面上の線、またはより一般的にはアフィン座標で線を記述するために使用できます。傾き切片形式は、2次元の非垂直線の方程式の一般的な表現です。

{\displaystyle y=mx+b}

どこ：

m の値は、線の勾配を表します。

b はラインの y 切片です。

方程式y = fでは、xは自由パラメータ(x)です。

平面を3次元で記述する場合、平面上の点とそれに直交するベクトル(法線ベクトル)を使用して平面の「傾き」を表すのが一般的であり、2次元の線を方程式に点-傾き形式で記述する方法と同様です。

具体的には、 \mathbf {r} _{0} をある点の位置ベクトルとし、 P_{0}=(x_{0},y_{0},z_{0}) を非ゼロのベクトル \mathbf {n} =(a,b,c) とします。

この点とベクトルによって決定される平面は、 P から描画されたベクトルが \mathbf {r} に垂直になるような P_{0} 位置ベクトル P