導入
数学、より正確には幾何学において、ハウスドルフ距離は、基礎となる計量空間の 2 つの部分集合間の距離を測定する位相幾何学的ツールです。
この距離は、2 つのまったく異なる文脈で現れます。画像処理に関しては、多数のアルゴリズムのソースとなる複数のプロパティを備えたツールです。これは 2 つの形状が同じかどうかを示し、異なる場合は距離によって相違点が定量化されます。次元2 では、ハウスドルフ距離により、画像をデジタル化したり、形状を認識したりすることが可能になります。このツールは純粋数学から派生したものであり、必ずしも工業的な処理に適しているわけではありません。たとえば、長さの異なる輪郭を持つ 2 つの形状は、この距離という意味で近いものになる可能性があります。これらの理由から、修正ハウスドルフ距離などのバリエーションが使用されることがあります。
純粋な数学者にとって、この距離は幾何学に対するものであり、一様収束の標準が解析に対するものに相当します。関数解析における均一収束は、新しいセットに取り組むアプローチから生まれます。私たちはもはや、関数が定義される実数または複素数の動作を研究するのではなく、関数のセットの動作を研究します。通常、私たちは一連の関数を使用して問題を解決しようとします。これらの関数は広大な空間の点として見なされ、解決に向かって収束します。フーリエ級数はこの性質のアプローチに従っています。幾何学の問題にも同じように取り組みたくなるものです。空間内の点が固体になり、解決に向かって収束する一連の固体を使用して解決策を見つけようとします。収束の概念にはトポロジーが必要であり、ハウスドルフ距離によって引き起こされるトポロジーが答えを提供します。
応用例としては、ユークリッド平面における等周問題があります。問題は、与えられた周囲長に対して、可能な最大面積の表面は何かを知ることです。答えは円板です。 1 つの方法は、解に向かって収束するシーケンス (たとえばポリゴン) を構築することから構成されます。
最初に生じる疑問は、機能分析の疑問と似た性質のものです。どの場合に空間は完全ですか、コンパクトなものは何ですか、連続アプリケーションはありますか、多項式に似た、簡単に操作できる高密度の部分空間はありますか?反応は、このアプローチが実を結ぶのに十分肯定的なものでした。基礎となる空間が完全であれば、ハウスドルフ距離を使用する空間も完全です。距離空間がユークリッドである場合、コンパクトは閉じた有界集合であり、多角形は密な集合を形成し、最終的にミンコフスキー和は連続的になります。
豊富な定理は、業界のニーズに特化したアルゴリズムを開発するための資産です。
距離施工
直感的なアプローチ
ハウスドルフの直観的なアイデアは、右の図に示すように、2 つの集合CとDの間の距離を定義することです。 C は赤い正方形を表し、 D は同じ表面と同じ中心を持つ青い円盤を表します。 2 つの数字が一致する場合、色は紫になり、一致しない場合は青または赤になります。 2 つの図の違いは、4 つの青い月と 4 つの赤いほぼ三角形の形で現れます。
円盤から最も遠い正方形の点を考えます。それは、円盤から距離aにある正方形の頂点です。次に、正方形から最も遠い円盤の点を検討します。それは月の頂点であり、その二乗距離はb と表されます。ハウスドルフ距離は、選択した例の 2 つの値のうち大きい方の値 (この場合はa ) です。値aとb は、相対ハウスドルフ距離と呼ばれることもあります。
画像技術者にとって、ハウスドルフ距離は 2 つの幾何学的形状間の類似性の指標であり、これがまさにその有用性の理由です。
この距離で最初の公理、つまり 2 つの異なる図形間の距離が決してゼロではないことを示す公理を検証するには、すべての集合を考慮することはできません。同じ中心と同じ半径を持つ 2 つのボール、1 つは開いていて、もう 1 つは閉じています。距離がゼロの場合、2 つの異なるセットになります。別の理由により、考慮するセットを制限する必要があります。ラインとボールの間の距離は無限大になりますが、距離の公理によればそれは不可能です。この理由から、ハウスドルフはセットを有界に制限します。この距離は、有限次元空間の形状に近い形状を研究するためによく使用されます。このため、セットがコンパクトであることが必要になる場合があります。最後に、閉じた有界と空のセットの間の距離を理解することはできません。このため、空のセットは考慮されません。
距離の処方
計量空間 ( E , δ) の 2 つの閉じた空でない有界集合XとYの間の距離 d( X , Y ) を表す方法はいくつかあります。 1 つ目は、前の段落の定義に対応します。
別の定式化は、集合X rおよびY r を考慮することから構成されます。ここで、 r は正の実数です。ここで、 X r (またはY r ) は、 X (またはY ) からr以下の距離にあるEの点のセットを指定します。距離は次の形式になります。
最後に、 B が閉じた単位球を指定する場合、集合X r はXとrBのミンコフスキー和に対応することがわかります。
正式な定義
( E , δ) を計量空間、 E H をEの空でない有界閉空間のセットとする。 E Hのハウスドルフ距離d は、次のように定義されるR +におけるE H x E Hの適用です。
これらの表記は、記事の残りの部分全体で使用されます。
注:距離d をδ の距離から明確に分離すると便利です。実際、ゼロベクトルとBの間の距離は 0 に等しいのに対し、ゼロ ベクトル シングルトンとBの間のハウスドルフ距離は 1 に等しいことがわかります。
E上の距離が制限されている場合、ハウスドルフ距離はEの閉じた (必ずしもコンパクトではない) 部分空間のセットまで拡張することもできます。それ以外の場合、このように定義された「距離」は無限の値をとる可能性があります。
Eの 2 つの非閉じたサブセット間のハウスドルフ距離を、それらの接着間のハウスドルフ距離として定義することもできます。したがって、 Eのすべてのサブセットに擬似計量を提供します (同じ接着を共有する 2 つの異なるサブセットのハウスドルフ距離はゼロになるため)。