Distância de Hausdorff - Hausdorff distance

Em matemática , a distância de Hausdorff , ou métrica de Hausdorff , também chamada de distância de Pompeiu-Hausdorff , mede a distância entre dois subconjuntos de um espaço métrico . Ele transforma o conjunto de subconjuntos compactos não vazios de um espaço métrico em um espaço métrico por si só. Recebeu o nome de Felix Hausdorff e Dimitrie Pompeiu .

Informalmente, dois conjuntos estão próximos na distância de Hausdorff se cada ponto de um dos conjuntos estiver próximo a algum ponto do outro conjunto. A distância de Hausdorff é a maior distância que você pode ser forçado a percorrer por um adversário que escolhe um ponto em um dos dois sets, de onde você deve viajar para o outro set. Em outras palavras, é a maior de todas as distâncias de um ponto em um conjunto ao ponto mais próximo no outro conjunto.

Essa distância foi introduzida pela primeira vez por Hausdorff em seu livro Grundzüge der Mengenlehre , publicado pela primeira vez em 1914, embora um parente muito próximo tenha aparecido na tese de doutorado de Maurice Fréchet em 1906, em seu estudo do espaço de todas as curvas contínuas de .

Definição

Componentes do cálculo da distância entre a linha de Hausdorff verde X e a linha azul Y .

Sejam X e Y dois subconjuntos não vazios de um espaço métrico . Definimos a distância de Hausdorff por

onde sup representa o supremo , inf o infimo e onde quantifica a distância de um ponto ao subconjunto .

Equivalentemente,

Onde

ou seja, o conjunto de todos os pontos dentro do conjunto (às vezes chamado de -fattening ou uma bola de raio generalizada ao redor ).

Equivalentemente,

ou seja, onde é a distância do ponto ao conjunto .

Observação

Não é verdade para subconjuntos arbitrários que implica

Por exemplo, considere o espaço métrico dos números reais com a métrica usual induzida pelo valor absoluto,

Toma

Então . No entanto , porque , mas .

Mas é verdade que e  ; em particular, é verdade se estiverem fechadas.

Propriedades

  • Em geral, pode ser infinito. Se X e Y são limitados , é garantido que sejam finitos.
  • se e somente se X e Y têm o mesmo fechamento.
  • Para cada ponto x de M e quaisquer conjuntos não vazios Y , Z de M : d ( x , Y ) ≤ d ( x , Z ) + d H ( Y , Z ), onde d ( x , Y ) é a distância entre o ponto X e o ponto mais próximo em conjunto Y .
  • Diâmetro ( Y ) -diâmetro ( X ) | ≤ 2 d H ( X , Y ).
  • Se a intersecção X  ∩  Y tem um interior não vazio, então existe uma constante r  > 0, de tal modo que cada conjunto X ' cuja distância Hausdorff de X é menor do que R também intersecta Y .
  • No conjunto de todos os subconjuntos de M , d H produz uma pseudométrica estendida .
  • No conjunto F ( M ) de todos os subconjuntos compactos não vazios de M , d H é uma métrica.
    • Se M estiver completo , então F ( M ) também estará .
    • Se M é compacto, então F ( M ) também é.
    • A topologia de F ( M ) depende apenas da topologia de M , não da métrica d .

Motivação

A definição da distância de Hausdorff pode ser derivada por uma série de extensões naturais da função de distância no espaço métrico M subjacente , como segue:

  • Defina uma função de distância entre qualquer ponto x de M e qualquer conjunto não vazio Y de M por:
Por exemplo, d (1, {3,6}) = 2 e d (7, {3,6}) = 1.
  • Defina uma função de "distância" (não necessariamente simétrica) entre quaisquer dois conjuntos não vazios X e Y de M por:
Por exemplo,
  • Se X e Y são compactos, então d ( X , Y ) será finito; d ( X , X ) = 0; e d herda o triângulo desigualdade propriedade da função de distância em M . Tal como está, d ( X , Y ) não é uma métrica porque d ( X , Y ) nem sempre é simétrico e d ( X , Y ) = 0 não implica que X = Y (implica isso ). Por exemplo, d ({1,3,6,7}, {3,6}) = 2 , mas d ({3,6}, {1,3,6,7}) = 0 . No entanto, podemos criar uma métrica definindo a distância de Hausdorff como:

Formulários

Na visão computacional , a distância de Hausdorff pode ser usada para encontrar um determinado modelo em uma imagem alvo arbitrária. O modelo e a imagem são frequentemente pré-processados ​​por meio de um detector de bordas que fornece uma imagem binária . Em seguida, cada ponto 1 (ativado) na imagem binária do modelo é tratado como um ponto em um conjunto, a "forma" do modelo. Da mesma forma, uma área da imagem binária de destino é tratada como um conjunto de pontos. O algoritmo então tenta minimizar a distância de Hausdorff entre o modelo e alguma área da imagem alvo. A área na imagem do alvo com a distância mínima de Hausdorff ao modelo pode ser considerada a melhor candidata para localizar o modelo no alvo. Em computação gráfica, a distância de Hausdorff é usada para medir a diferença entre duas representações diferentes do mesmo objeto 3D, particularmente ao gerar nível de detalhe para exibição eficiente de modelos 3D complexos.

Conceitos relacionados

Uma medida para a dissimilaridade de duas formas é dada por Hausdorff distância até isometría , denotado D H . A saber, sejam X e Y duas figuras compactas em um espaço métrico M (geralmente um espaço euclidiano ); então D H ( X , Y ) é o ínfimo de d H ( I ( X ), Y ) ao longo de todas as isometrias I do espaço métrico M para si mesmo. Essa distância mede o quanto as formas X e Y estão longe de serem isométricas.

A convergência Gromov-Hausdorff é uma ideia relacionada: medimos a distância de dois espaços métricos M e N , tomando o ínfimo de ao longo de todos mergulhos isométricos e em algum espaço métrico comum L .

Veja também

Referências

links externos