ハウスドルフ距離
数学においてハウスドルフ距離（英: Hausdorff distance）とは距離空間の部分空間同士の隔たりを測る量の一種である。
ハウスドルフ距離は1914年に出版されたフェリックス・ハウスドルフの著書集合論基礎に現れている。だたし、1906年のモーリス・ルネ・フレシェの博士論文に書かれた三次元空間内の連続曲線全体からなる空間の研究に非常によく似た類似物が登場している。
目次
1 定義
2 性質
3 部分集合の空間
4 類似物
5 応用
6 注釈
7 出典
8 関連項目
定義
距離空間 (M ,d ) の空でない[注釈 1]部分集合全体 P×(M)displaystyle mathcal P^times (M)
- dH(X,Y):=maxsupx∈Xd(x,Y),supy∈Yd(y,X)displaystyle d_rm H(X,Y):=rm maxsup _xin Xd(x,Y),sup _yin Yd(y,X)
と定義する（ただし、X、Y は距離空間 (M , d )) の任意の空でない部分集合で、d(x,Y):=infy∈Yd(x,y)displaystyle d(x,Y):=inf _yin Yd(x,y)
これは次のように表現することも出来る。
- dH(X,Y)=infϵ>0:X⊆Nϵ(Y),Y⊆Nϵ(X)displaystyle d_rm H(X,Y)=infepsilon >0:Xsubseteq N_epsilon (Y),Ysubseteq N_epsilon (X)
ただし、Nε(X ) := p ∈M : d(p,X) < ε
dH(X ,Y ) = 0 ⇔ clM(X ) = clM(Y ) （ただし、clM(X ) は X の閉包 ）なので、空でない閉集合全体は擬距離 dH に関する同値類の完全代表系をなす。
更に、X、Y が有界集合なら明らかに dH(X ,Y ) は有限である。以上から dH は M 上の空でない有界閉集合全体 B×(M)displaystyle mathcal B^times (M)
自然な埋め込み ι:(M,d)→(B×(M),dH)displaystyle iota :(M,d)rightarrow (mathcal B^times (M),d_rm H)
ハウスドルフ距離は一様構造や粗構造といった距離構造の一般化にも自然に拡張できる。
性質
以下距離空間 M を固定。
p ∈M 、X , Y ⊆M のとき d (p, Y ) ≤ d (p, X ) + dH(X ,Y )。
X , Y ⊆M のとき dia(Y ) ≤ dia(X ) + 2·dH(X ,Y ) （ただし、dia(X ) は X の直径）。
X , Y ⊆M について X ∩Y の内部は空でないとする。このとき Z ⊆ M と X のハウスドルフ距離が十分小さければ、Z ∩Y ≠ ∅。
X , Y , Z ⊆M、dH(X ,Z ) ≤ a , dH(Z ,Y ) ≤ b とする。このとき Z ⊆ (⋂r > aNr (X ))∩(⋂r > bNr (Y )) であり、(⋂r > aNr (X ))∩(⋂r > bNr (Y )) は dH(X ,W ) ≤ a , dH(W ,Y ) ≤ b を満たす最大のW。
部分集合の空間
M を距離空間、B×(M)displaystyle mathcal B^times (M)
- 距離空間の空でない部分集合について、全有界であることと、ハウスドルフ距離の意味で有限集合の極限になることが同値（つまり Pfin×(M)¯=TB×(M)displaystyle overline mathcal P_rm fin^times (M)=mathcal TB^times (M)
）。
- 上からも明らかなように空でない全有界集合のハウスドルフ距離の意味での極限は全有界（つまり TB×(M)displaystyle mathcal TB^times (M)
M が完備なら B×(M)displaystyle mathcal B^times (M)
K×(M)displaystyle mathcal K^times (M)
以下 M は完備距離空間とする[注釈 2]。
| 空間＼性質 | 有界 | 固有 | コンパクト | 可分 | 弧長 | 測地 | 固有かつ測地 |
|---|---|---|---|---|---|---|---|
B×(M)displaystyle mathcal B^times (M) | ◯ | ◯ | ◯ | × | ◯ | × | ◯ |
K×(M)displaystyle mathcal K^times (M) | ◯ | ◯ | ◯ | ◯ | × | × | ◯ |
類似物
- 変換群による変形
M を距離空間、X ,Y ⊆ M を部分集合 G ⊆Iso(M ) を M の等長変換（の一部）からなる群とする。このとき
- dH,G(X,Y):=infγ∈GdH(X,γ(Y))displaystyle d_rm H,G(X,Y):=inf _gamma in Gd_rm H(X,gamma (Y))
は新たな（拡張擬）距離を定める。
空間内で位置や向きを調整してハウスドルフ距離を出来るだけ小さくした場合の極限がこれに当たる。これは下記のグロモフ・ハウスドルフ距離と元のハウスドルフ距離の中間的なものである。
- グロモフ・ハウスドルフ距離
上の場合は固定した空間内で位置や向きを調整したが背景となる空間そのものを取り替えることで、2つの図形の形状の差のみを取り出したものがグロモフ・ハウスドルフ距離である。
応用
ハウスドルフ距離（特に変換群による変形を施したもの）や関連する距離コンピュータビジョンにおいて与えられて画像から前もって用意された見本となる形状を見つけ出すのに使われている。そこでは、まず与えられた画像からエッジ検出により二値画像を出力し、見本をその画像内で調節することで2つのハウスドルフ距離が最小に（ないしそれに十分近く）なるような配置を見つけ出す。見本が配置された領域が形状が存在する最良の候補となる。
更にコンピュータグラフィックスでは三次元の物体の表現の間の差異を測るためにも使われている。
注釈
^ 空集合にも定義できるが空集合は孤立点となり、集合族が良い性質を満たさなくなる。
^ このとき K×(M)=TB×(M)displaystyle mathcal K^times (M)=mathcal TB^times (M)
出典
^ Martin R.Bridson and André Haefliger, Metric Spaces of Non-positive Curvature,Springer,1999,p70-71
関連項目
- グロモフ・ハウスドルフ収束
- フレシェ距離
- 半連続性
- 連続体 (位相空間論)
- シェイプ理論
- ワッサースタイン計量
- レヴィ–プロホロフ計量
