ハウスドルフ距離

数学において、ハウスドルフ距離、またはハウスドルフ計量、またはポンペイウ・ハウスドルフ距離^{[1] [2]は}、距離空間の2つの部分集合が互いにどれだけ離れているかを測定する。これは、距離空間の空でないコンパクト部分集合の集合を、それ自体が距離空間になるよう変換する。これは、フェリックス・ハウスドルフとディミトリ・ポンペイウにちなんで名付けられた。

非公式には、いずれかの集合のすべての点がもう一方の集合のどこかの点に近い場合、2 つの集合はハウスドルフ距離で近いと言えます。ハウスドルフ距離とは、2 つの集合のどちらかの点を選択した敵が、そこからもう一方の集合まで移動しなければならない最長距離です。言い換えれば、一方の集合の点からもう一方の集合の最も近い点までのすべての距離の中で最大の距離です。

この距離は、ハウスドルフが 1914 年に最初に出版した著書「人文理論の基礎」で初めて導入されましたが、これに非常に近いものが、 からのすべての連続曲線の空間に関する研究で 1906 年にモーリス・フレシェが博士論文に発表しました。 ${\displaystyle [0,1]\to \mathbb {R} ^{3}}$

を距離空間とする。空でない部分集合の各ペアとに対して、との間のハウスドルフ距離は次のように定義される。 ${\displaystyle (M,d)}$${\displaystyle X\subset M}$${\displaystyle Y\subset M}$${\displaystyle X}$${\displaystyle Y}$

$${\displaystyle d_{\mathrm {H} }(X,Y):=\max \left\{\,\sup _{x\in X}d(x,Y),\ \sup _{y\in Y}d(X,y)\,\right\},}$$

ここで、 は上限演算子、下限演算子を表し、 は点からサブセットまでの距離を定量化します。 ${\displaystyle \operatorname {sup} }$${\displaystyle \operatorname {inf} }$${\displaystyle d(a,B):=\inf _{b\in B}d(a,b)}$${\displaystyle a\in X}$${\displaystyle B\subseteq X}$

同等の定義は以下の通りである。^[3]各集合 に対して、を 内のすべての点の集合（の -fatteningまたはの周りの半径の一般化された球体と呼ばれることもある ）とする。すると、との間のハウスドルフ距離は次のように定義される 。${\displaystyle X\subset M,}$$${\displaystyle X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\mid d(z,x)\leq \varepsilon \},}$$${\displaystyle \epsilon }$${\displaystyle X}$${\displaystyle \epsilon }$${\displaystyle X}$${\displaystyle \epsilon }$${\displaystyle X}$${\displaystyle X}$${\displaystyle Y}$$${\displaystyle d_{H}(X,Y):=\inf\{\varepsilon \geq 0\mid X\subseteq Y_{\varepsilon }{\text{ かつ }}Y\subseteq X_{\varepsilon }\}.}$$

同様に、^[1] は点から集合までの最小距離です。 $${\displaystyle {\begin{aligned}d_{H}(X,Y)&=\sup _{w\in M}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\&=\sup _{w\in X\cup Y}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\&=\sup _{w\in M}|d(w,X)-d(w,Y)|,\end{aligned}}}$$${\displaystyle d(w,X):=\inf _{x\in X}d(w,x)}$${\displaystyle w}$${\displaystyle X}$

任意の部分集合については当てはまら ないので、${\displaystyle X,Y\subset M}$${\displaystyle d_{\mathrm {H} }(X,Y)=\varepsilon }$

${\displaystyle X\subseteq Y_{\varepsilon }\ {\mbox{and}}\ Y\subseteq X_{\varepsilon }.}$

例えば、絶対値によって誘導される 通常の計量を持つ実数の計量空間を考えてみましょう。${\displaystyle \mathbb {R} }$${\displaystyle d}$

${\displaystyle d(x,y):=|yx|,\quad x,y\in \mathbb {R} .}$

取る

${\displaystyle X:=(0,1]\quad {\mbox{and}}\quad Y:=[-1,0).}$

すると。しかし、なぜなら、しかし。 ${\displaystyle d_{\mathrm {H} }(X,Y)=1\ }$${\displaystyle X\nsubseteq Y_{1}}$${\displaystyle Y_{1}=[-2,1)\ }$${\displaystyle 1\in X}$

しかし、および は真であり 、特にが閉じている場合は真です。 ${\displaystyle X\subseteq {\overline {Y_{\varepsilon}}}}$${\displaystyle Y\subseteq {\overline {X_{\varepsilon}}}}$${\displaystyle X,Y}$

• 一般に、は無限大になる可能性があります。XとY の両方が有界である場合、は有限であることが保証されます。${\displaystyle d_{\mathrm {H} }(X,Y)}$${\displaystyle d_{\mathrm {H} }(X,Y)}$
• ${\displaystyle d_{\mathrm {H} }(X,Y)=0}$XとY が同じ閉包を持つ場合に限ります。
• Mのすべての点xとMの空でない集合Y、Zについて、d ( x、Y ) ≤ d ( x、Z ) + d _H ( Y、Z ) が成立します。ここで、 d ( x、Y ) は点xと集合Y内の最も近い点の間の距離です。
• |直径( Y )-直径( X )|≤2dH ( X , Y )_である。^[4]
• 交差点X∩Yの内部が空でない場合、 定数 r> 0が存在し、Xからのハウスドルフ距離がr未満の すべての集合X′はYとも交差します。^[5]
• Mのすべての部分集合の集合上で、 d _{H は}拡張擬距離を与える。
• Mの空でないコンパクト部分集合全体の集合F ( M ) 上で、d _{H は}距離です。
  • Mが完全ならばF ( M )も完全である。^[6]
  • Mがコンパクトであれば、 F ( M )もコンパクトです。
  • F ( M )の位相はMの位相にのみ依存し、メトリックdには依存しません。

ハウスドルフ距離の定義は、次のように、基礎となる計量空間Mにおける距離関数の一連の自然な拡張によって導くことができる。^[7]${\displaystyle d(x,y)}$

• Mの任意の点xとMの任意の空でない集合Yの間の距離関数を次のように定義します。

${\displaystyle d(x,Y)=\inf\{d(x,y)\mid y\in Y\}.\ }$

たとえば、d (1, {3,6}) = 2、d (7, {3,6}) = 1 です。

• Mの任意の 2 つの空でない集合XとY間の (必ずしも対称ではない)「距離」関数を次のように定義します。

${\displaystyle d(X,Y)=\sup\{d(x,Y)\mid x\in X\}.\ }$

例えば、${\textstyle d(\{1,7\},\{3,6\})=\sup\{d(1,\{3,6\}),d(7,\{3,6\} )\}=\sup\{d(1,3),d(7,6)\}=2.}$

• XとYがコンパクトな場合、 d ( X , Y ) は有限になります。つまり、 d ( X , X )=0 となり、d はMの距離関数から三角不等式の特性を引き継ぎます。現状では、 d ( X , Y ) は常に対称であるとは限らず、d ( X , Y ) = 0 は X = Y を意味しない ( を意味する) ため、 d ( X , Y )はメトリックではありません 。たとえば、 d ( { 1,3,6,7 } , {3,6}) = 2ですが、d ({3,6}, {1,3,6,7}) = 0 です。ただし、ハウスドルフ距離を次のように定義することでメトリックを作成できます。${\displaystyle X\subseteq {\overline {Y}}}$

${\displaystyle d_{\mathrm {H} }(X,Y)=\max\{d(X,Y),d(Y,X)\}\,.}$

コンピュータビジョンでは、ハウスドルフ距離を使用して、任意のターゲット画像から特定のテンプレートを見つけることができます。テンプレートと画像は、多くの場合、エッジ検出器を介して前処理され、バイナリ画像が生成されます。次に、テンプレートのバイナリ画像内の各 1 つの (アクティブ化された) ポイントは、テンプレートの「形状」であるセット内のポイントとして扱われます。同様に、バイナリターゲット画像の領域は、ポイントのセットとして扱われます。次に、アルゴリズムは、テンプレートとターゲット画像のある領域との間のハウスドルフ距離を最小化しようとします。テンプレートへのハウスドルフ距離が最小となるターゲット画像内の領域は、ターゲット内でテンプレートを見つけるための最良の候補と見なすことができます。コンピュータグラフィックスでは、ハウスドルフ距離は、同じ 3D オブジェクトの 2 つの異なる表現の違いを測定するために使用されます^{[8] 。特に、複雑な 3D モデルを効率的に表示するための}詳細レベルを生成する場合に使用されます。

が地球の表面で、が地球の陸地の表面である場合、点 Nemo を見つけることによって、約 2,704.8 km であることが わかります。${\displaystyle X}$${\displaystyle Y}$${\displaystyle d_{H}(X,Y)}$

2 つの図形の非類似度の尺度は、等長変換までのハウスドルフ距離で与えられ、D _Hと表記されます。つまり、XとY を距離空間M (通常はユークリッド空間) 内の 2 つのコンパクトな図形とすると、D _H ( X , Y ) は、距離空間Mとその空間自体のすべての等長変換Iの間でのd _H ( I ( X ), Y )の最小値です。この距離は、図形Xと図形 Yが等長変換からどれだけ離れているかを測ります。

グロモフ・ハウスドルフ収束は関連する考え方です。これは、すべての等長埋め込みと共通の計量空間Lの間の最小値を取ることによって、2つの計量空間MとNの距離を測定するものです。 ${\displaystyle d_{\mathrm {H} }(I(M),J(N))}$${\displaystyle I\colon M\to L}$${\displaystyle J\colon N\to L}$

• ウィズマン収束
• クラトフスキー収束
• 半連続性
• フレシェ距離
• ハイパートポロジー

• 凸多角形間のハウスドルフ距離。
• MeshLab を使用して 2 つのサーフェス間の差を測定する オープン ソース ツールMeshLabを使用して、2 つの三角形化された 3D サーフェス間のハウスドルフ距離を計算し、視覚化する方法に関する短いチュートリアルです。
• ハウスドルフ距離のMATLABコード: [1]