幾何ハッシングは、コンピュータビジョンとパターン認識において、シーン内の物体を識別するために、その幾何学的特徴を事前計算されたデータベースと照合する手法である。1980年代後半にYehezkel LamdanとHaim J. Wolfsonによって開発され、モデルベース物体認識の分野に影響を与えた。この手法は、部分的な遮蔽を扱う能力と、一般的な幾何学的変換に対する不変性で知られ、初期のテンプレートマッチング手法に代わる堅牢な選択肢となった。
幾何ハッシングの核となる考え方は、各物体モデルを特徴点（角、エッジ、関心点など）の集合として表現し、その空間的関係をハッシュテーブルに符号化することである。認識時には、クエリシーンから特徴点を抽出し、ハッシュテーブルを用いて候補モデルに投票する。この投票プロセスにより、物体の特徴の一部しか見えない場合でも、システムはどのモデルが存在するかを迅速に仮説立てることができる。
歴史的発展
幾何ハッシングは、1980年代の計算幾何学とコンピュータビジョンの研究から生まれた。LamdanとWolfsonは、1988年の論文「Geometric Hashing: A General and Efficient Model-Based Recognition Scheme」でこの概念を紹介し、IEEE国際コンピュータビジョン会議で発表した。このアプローチは、ハッシングと幾何学的マッチングに関する初期の研究に基づいていたが、モデル特徴を索引付けする新しい方法を導入し、認識を高速かつノイズに耐性のあるものにした。
この手法は1990年代に注目を集め、特に産業部品検査、ロボティクス、医療画像処理などの応用で用いられた。また、分子生物学におけるタンパク質構造比較にも適応され、異なる分子間で原子や残基の幾何学的配置を照合することができた。2020年代初頭の時点で、幾何ハッシングはコンピュータビジョンの基礎概念として残っているが、多くの実用的応用では深層学習ベースの手法にほぼ取って代わられている。
アルゴリズム概要
幾何ハッシングアルゴリズムは、前処理と認識の2つのフェーズで動作する。前処理フェーズでは、データベース内の各モデルについて、特徴点の集合が抽出される。各順序付き点ペア（または基底、通常は座標系を定義する2点）について、アルゴリズムはその基底に対する他のすべての点の相対座標を計算する。これらの相対座標はハッシュテーブルに格納され、基底とモデル識別子が関連付けられた値となる。
認識時には、シーンの特徴点が抽出され、アルゴリズムはランダムな点ペアを候補基底として選択する。この基底を用いて残りのシーン点の相対座標を計算し、ハッシュテーブルで照合する。各一致は対応するモデルと基底への投票を増加させる。すべての可能な基底（またはサンプリングされた部分集合）を処理した後、投票数が最も多いモデルが最良の一致として選択される。アルゴリズムはその後、モデルをシーンに整列させて整合性を確認することで一致を検証する。
このアプローチは、相対座標が正規化された座標系で計算されるため、平行移動、回転、均一スケーリングに対して不変である。また、十分な投票が蓄積されるためにはモデルの特徴の一部だけがシーンに存在すればよいため、部分的な遮蔽も処理できる。
コンピュータビジョンにおける応用
幾何ハッシングは、堅牢な物体認識が必要とされるいくつかの分野で応用されてきた。産業オートメーションでは、基準に対して回転またはスケーリングされた部品をコンベアベルト上で位置特定するために使用された。ロボティクスでは、ロボットが散らかった環境で物体を識別し把持するのに役立った。この手法の遮蔽耐性は、山積みされた部分的に隠れた物体を認識するタスクに適していた。
医療画像処理では、幾何ハッシングはX線やMRI画像内の解剖学的構造を整列させるために使用され、画像レジストレーションや手術計画などのタスクに役立った。分子生物学では、タンパク質の3D構造比較を促進し、アミノ酸配列の変異にもかかわらず類似した折りたたみパターンを見つけることを目的とした。これらの応用は、個々の点間の明示的な対応を必要とせずに幾何学的構成を照合するこの手法の能力を活用した。
現代の手法との比較
2010年代のMachine learningとDeep learningの台頭により、幾何ハッシングは主流のコンピュータビジョンではあまり目立たなくなった。Neural networkアーキテクチャ、特にConvolutional neural network（明示的にリストされていないが、概念は暗示されている）とTransformer (architecture)モデルに基づく手法は、大規模な認識タスクでより高い精度を達成している。これらの現代的な手法はデータから直接特徴表現を学習するのに対し、幾何ハッシングは手作りの幾何学的特徴と明示的な空間索引付けに依存している。
しかし、幾何ハッシングは特定のシナリオでは依然として利点を提供する。大量のトレーニングデータを必要としないため、物体の例が少数しか利用できない場合に有用である。また、投票プロセスが認識に寄与した特徴を明らかにするため、解釈可能なマッチング結果を提供する。対照的に、深層学習モデルはしばしばブラックボックスとして動作する。2020年代半ばの時点で、特徴抽出のために幾何ハッシングとMachine learningを組み合わせたハイブリッドアプローチが探求されているが、ニッチなままである。
限界と拡張
幾何ハッシングの限界の1つは、特徴点抽出の品質に対する感度である。特徴検出器がノイズの多いまたは一貫性のない点を生成する場合、ハッシュテーブルの照合は信頼性を失う。アルゴリズムはモデル数に対してスケーリングが悪く、ハッシュテーブルが大きくなりメモリ集約的になる可能性がある。これに対処するため、ランダム化基底や階層的ハッシングを使用して探索空間を減らす拡張が提案されている。
もう1つの拡張は、類似変換だけでなくアフィン変換や射影変換を使用することで、適用可能なシナリオの範囲を広げる。一部の変種は、識別を改善するために幾何学的特徴とともに色やテクスチャ情報を組み込む。これらの強化にもかかわらず、速度と堅牢性の間の根本的なトレードオフは依然として課題であり、この手法は現代のシステムにおけるData Augmentationベースのトレーニングなど、他の方法と組み合わせて使用されることが多い。
遺産と影響
幾何ハッシングは、コンピュータビジョンにおけるその後の発展、例えば大規模画像検索でのハッシングの使用やSIFT（スケール不変特徴変換）などの局所特徴記述子の設計に影響を与えた。幾何学的不変量をハッシュテーブルに索引付けするという考え方は、その後の多くのアルゴリズムに見られる。また、幾何学的推論を計算システムで効率的に実装できることを示すことで、Artificial intelligenceのより広い分野にも貢献した。
今日、幾何ハッシングはコンピュータビジョンのコースでモデルベース認識の古典的な例として教えられている。その原理は、点群での3D物体認識やコンピュータ支援設計での形状マッチングなどの専門的な応用で今も関連性がある。もはやこの分野を支配してはいないが、その概念的な貢献はArtificial intelligenceとパターン認識の歴史の重要な部分であり続けている。