Distância de Hausdorff

Em matemática , e mais precisamente em geometria , a distância de Hausdorff é uma ferramenta topológica que mede a distância de dois subconjuntos de um espaço métrico subjacente.

Essa distância aparece em dois contextos muito diferentes. Para o processamento de imagens , é uma ferramenta com múltiplas propriedades, fonte de inúmeros algoritmos. Indica se duas formas são iguais e, se forem diferentes, a distância quantifica essas dissimilaridades. Na dimensão 2, a distância de Hausdorff permite digitalizar uma imagem ou reconhecer uma forma. Essa ferramenta, derivada da matemática pura , nem sempre é adequada para processamento industrial. Por exemplo, duas formas com contornos de comprimentos diferentes podem estar próximas, no sentido dessa distância. Por essas razões, às vezes variantes são usadas, como a distância de Hausdorff modificada .

Para o matemático puro, essa distância é para a geometria o que a norma da convergência uniforme é para a análise . A convergência uniforme, na análise funcional , procede de uma abordagem que consiste em trabalhar um novo conjunto. Não estudamos mais o comportamento dos números, reais ou complexos, nos quais a função é definida, mas o de um conjunto de funções. Normalmente, tentamos resolver uma questão por meio de uma série de funções, que são vistas como pontos de um vasto espaço e que convergem para a solução. A série de Fourier parte de uma abordagem dessa natureza. É tentador abordar um problema de geometria da mesma maneira. Um ponto no espaço torna-se sólido, tentamos encontrar uma solução usando uma série de sólidos convergindo para a solução. A noção de convergência requer uma topologia, que induzida pela distância de Hausdorff oferece uma resposta.

Um exemplo de aplicação é o problema isoperimétrico no plano euclidiano. A questão é saber qual é a superfície de maior área possível, para um determinado perímetro, a resposta é o disco . Um método consiste em construir uma sequência, por exemplo de polígonos, que converge para a solução.

As primeiras questões que surgem são, de certa forma, da mesma natureza que as da análise funcional. Nesse caso o espaço está completo , quais são os compactos , temos aplicações contínuas, existem subespaços densos e facilmente manipuláveis , um pouco como polinômios? As respostas são positivas o suficiente para que o processo seja frutífero. Se o espaço subjacente estiver completo, também estará o espaço usando a distância de Hausdorff. Os compactos, se o espaço métrico é euclidiano, são os conjuntos fechados e limitados , os polígonos formam um conjunto denso e, finalmente, a soma de Minkowski é contínua.

Nesse campo, o trabalho matemático tem um efeito direto no desenvolvimento de algoritmos que atendem especificamente às necessidades da indústria.

Construção de distância

Abordagem intuitiva

A ideia intuitiva de Hausdorff é definir a distância entre dois conjuntos C e D como mostrado na figura à direita. C representa o quadrado vermelho e D o disco azul com a mesma área e o mesmo centro. Onde as duas figuras coincidem, a cor é roxa, caso contrário, é azul ou vermelho. As diferenças entre as duas figuras se materializam na forma de 4 lúnulas azuis e 4 triângulos quase vermelhos.

Consideramos o ponto do quadrado mais afastado do disco, é um vértice do quadrado, a uma distância a do disco. Em seguida, consideramos o ponto do disco mais afastado do quadrado, é o topo da lúnula e sua distância ao quadrado é observada b . A distância de Hausdorff é a maior das duas, neste caso a , para o exemplo escolhido. Os uma e b valores são por vezes referido como a distância Hausdorff relativa .

A distância de Hausdorff, para o engenheiro de imagem, é um indicador de semelhança entre duas formas geométricas, razão pela qual é útil.

Para que esta distância possa verificar o primeiro axioma, ou seja, aquele que indica que a distância entre duas figuras distintas nunca é zero, não podemos considerar todos os conjuntos. Duas bolas , uma aberta e outra fechada , com o mesmo centro e o mesmo raio seriam dois conjuntos diferentes a uma distância zero. Outro motivo leva a limitar os conjuntos considerados. A distância entre uma linha e uma bola seria infinita, o que não é possível de acordo com os axiomas da distância. Por esta razão, Hausdorff limita o conjunto aos limitados . Essa distância é frequentemente usada para estudar geometrias próximas às de um espaço dimensional finito , por esse motivo, os conjuntos às vezes precisam ser compactos. Finalmente, não é possível dar um significado à distância entre um conjunto fechado com limite arbitrário e o conjunto vazio  ; por este motivo, o conjunto vazio não é considerado.

Formulações de distância

Existem diferentes maneiras de expressar a distância d ( X , Y ) entre dois conjuntos fechados não-vazios limitados X e Y de um espaço métrico ( E , δ). O primeiro corresponde à definição do parágrafo anterior:

d(X,Y): =max{e aíy∈Yδ(X,y),e aíx∈Xδ(x,Y)}=max{e aíy∈Yinfx∈Xδ(x,y),e aíx∈Xinfy∈Yδ(x,y)}.{\ displaystyle d (X, Y): = \ max \; \ {\ sup _ {y \ in Y} \ delta (X, y), \ quad \ sup _ {x \ in X} \ delta (x, Y) \} = \ max \; \ {\ sup _ {y \ in Y} \ inf _ {x \ in X} \ delta (x, y), \ quad \ sup _ {x \ in X} \ inf _ {y \ em Y} \ delta (x, y) \}.}

Outra formulação consiste em considerar os conjuntos X r e Y r , onde r é um real positivo. Aqui, X r (resp. Y r ) denota o conjunto de pontos de E a uma distância menor ou igual a r de X (resp. Y ). A distância assume a seguinte forma:

d(X,Y)=min{r∈R+∣X⊂YreY⊂Xr}.{\ displaystyle d (X, Y) = \ min \ {r \ in \ mathbb {R} _ {+} \ mid X \ subconjunto Y_ {r} \ quad {\ text {e}} \ quad Y \ subconjunto X_ {r} \}.}

Definição formal

Seja ( E , δ) um espaço métrica e E H são todos não vazio limitado fechado de E . A distância de Hausdorff d em E H é o mapa d , de E H × E H em ℝ + , definido pela fórmula acima.

Essas notações são usadas no restante do artigo.

Nota  : a distância δ se aplica a dois pontos, ou a um ponto e uma parte, enquanto a distância de Hausdorff d se aplica a duas partes (fechada, limitada e não vazia). Por exemplo em ℝ:

δ(0,[-1,1])=0ed({0},[-1,1])=1{\ displaystyle \ delta (0, [- 1,1]) = 0 \ quad {\ text {e}} \ quad d (\ {0 \}, [- 1,1]) = 1.}

Se a distância em E é limitada, a distância de Hausdorff é definida em todos os fechados não vazios de E (todos são limitados). Caso contrário, a "distância" estendida para fechado ilimitado pode assumir valores infinitos.

Também é possível definir a distância de Hausdorff entre dois subconjuntos não fechados de E como a distância de Hausdorff entre suas aderências . Assim, fornecemos ao conjunto de subconjuntos de E um desvio (uma vez que dois subconjuntos distintos, mas compartilhando a mesma adesão, terão uma distância de Hausdorff zero).

Exemplo

A distância de Hausdorff entre um triângulo e sua borda é igual à distância entre o centro do círculo inscrito no triângulo e um dos lados. A aplicação ao cálculo da distância de Hausdorff entre duas iterações sucessivas da série clássica de compactos convergindo para o triângulo de Sierpinski é imediata e pode ajudar a entender o conceito de distância de Hausdorff. Com efeito, ainda que o mesmo exercício aparentemente, no âmbito do estudo do tapete de Sierpinski , seja trivial, a pesquisa no caso do triângulo obriga a manipular de forma sutil as noções de máximo e mínimo presentes na definição. a distância de Hausdorff entre dois compactos. Além disso, este exemplo relaciona a noção introduzida por Felix Hausdorff aos fractais , mais precisamente a sistemas de funções iteradas , onde esta noção é amplamente utilizada.

Continuidade

Conjunto denso

A existência de conjuntos densos interessa tanto ao matemático quanto ao engenheiro de processamento de imagens. Para o engenheiro, um subconjunto denso permite aproximar qualquer ponto de E H (o termo ponto designa um elemento do conjunto estudado, aqui figuras geométricas). E F H é densa em E H quando, por qualquer ponto X de E H e para qualquer número ε verdadeiro estritamente positivo, existe um ponto Y de F H a uma distância inferior a ε de X .

O conjunto denso é escolhido menor para que possa ser trabalhado de forma mais conveniente. A figura à direita ilustra dois conjuntos densos, se E for um espaço euclidiano , como o plano de processamento de imagens. O primeiro exemplo corresponde a pixels . O espaço é quadrado por um conjunto de linhas (hiperplanos em qualquer dimensão) cujas direções são todas ortogonais a um vetor de base ortonormal e as linhas paralelas entre si são regularmente espaçadas. Esta grade define um conjunto de pequenos quadrados (de hipercubos se a dimensão for arbitrária), o primeiro conjunto denso é aquele formado por um conjunto finito de pequenos quadrados desta natureza. Engenheiros falam sobre imagens raster

Em matemática, muitas vezes escolhe-se o passo da grade igual a 1/2 n , onde n é qualquer número inteiro, há uma infinidade de possíveis “tamanhos de grade”, cada vez mais precisos à medida que n aumenta. Uma forma, por exemplo o círculo roxo na figura à direita, é aproximada por esses pequenos quadrados. Um algoritmo consiste em selecionar um pequeno quadrado se ele tiver uma interseção não vazia com a figura que deve aproximar.

Um segundo método consiste em escolher como conjunto denso os polígonos , ou mesmo os poliedros no caso de qualquer dimensão. Para um engenheiro, muito menos informações são necessárias para descrever uma figura geométrica com este método. Essa abordagem permite economizar tempo ou aumentar a precisão. A segunda figura à direita é uma aproximação poligonal, também chamada de imagem vetorial . Para o matemático, os poliedros formam um conjunto que contém estritamente o anterior, por isso é natural que também seja denso.

Às vezes, é útil para manter a convexidade , novamente, convexo poliedros formar um conjunto denso entre o convexo E H .

Demonstração

Aqui, E denota um espaço euclidiano de dimensão d . Aqui, G H designa todos os hipercubos fechados na grade e as arestas de comprimento 2 n e X denota um E H fechado limitado . A demonstração é um pouco mais rica do que a anunciada no parágrafo.

• Existe uma sequência de polígonos ( P n ), decrescendo para inclusão, de modo que P n contenha X e de forma que a distância entre X e P n seja menor que (d / 2 2n ) 1/2  :

Consideramos o conjunto de hipercubos de G n tendo uma interseção diferente de zero com X , a união dos elementos deste conjunto é denotada por P n . Dois dos conjuntos são mostrados na figura à direita. A Figura X é um polígono com uma borda desenhada em preto. O primeiro conjunto ilustrado corresponde aos quadrados azuis, o segundo, duas vezes mais fino e que oculta parcialmente os quadrados azuis, é ilustrado pela cor vermelha.

A diminuição da sequência, bem como o fato de P n conter X, são garantidos por construção.

A maior distância possível é obtida se X intersecta um hipercubo apenas em um vértice, o vértice mais distante é o ponto de P n mais distante de X , a distância é a da maior diagonal, igual a (d / 2 2n ) 1/2 .

A distância entre P n e X tende para 0, por definição do limite , 4 X é de fato a da série de polígonos.

• Se X for convexo, a sequência de envelopes convexos ( K n ) dos polígonos P n é uma sequência decrescente para inclusão, de modo que Q n contém X e tal que a distância entre X e Q n é menor que (d / 2 2n- 2 ) 1/2  :

O raciocínio é o mesmo do anterior, basta notar que a adição de uma camada de pequenos cubos constrói uma figura que contém o envelope convexo K n .

Funções contínuas

Se uma função é contínua, o que ela representa é bem preservado por pequenas modificações. Um exemplo essencial é a soma de Minkowski . Dois conjuntos de X e Y , que associam o conjunto de vectores de forma a x + y , onde x é um elemento de X e Y de Y . Na imagem, somar uma figura com um pequeno disco permite atenuar os contornos. Em matemática pura, a soma de Minkowski está envolvida em muitos teoremas isoperimétricos . O fato de C ser um compacto convexo implica na igualdade C + C = 2 C (o que não é óbvio, a primeira parte correspondendo a uma soma de Minkowski e a segunda a uma dilatação de razão 2). Este é um elemento chave na prova do teorema de Minkowski , usado na teoria algébrica dos números .

Um segundo exemplo é dado pela função de medida , se E for um espaço euclidiano. A medida de Lebesgue associa a uma figura seu volume . Tem uma forma de continuidade para a distância de Hausdorff, é semi-contínua acima . Isso indica que, se um algoritmo constrói uma figura usando aproximações cada vez mais precisos, o valor final tem uma medida que não saltar para baixo. Matematicamente, é modelado por uma sequência ( X n ) de figuras que convergem para uma figura X , no sentido de Hausdorff. O volume da figura X não é muito menor que o de X n , se n for grande. Se μ denota a medida de Lebesgue, ou seja, a função que associa seu volume a uma figura:

lim supnão→∞µ(Xnão)≤µ(X).{\ displaystyle \ limsup _ {n \ to \ infty} \ mu (X_ {n}) \ leq \ mu (X).}

Se não houver possibilidade de pular para baixo, pode haver uma para cima. Podemos perceber isso construindo uma imagem usando etapas sucessivas, denotadas ( X n ). Presume-se que a imagem é composta de pixels muito pequenos para serem visíveis. A cada passo, o algoritmo adiciona alguns pontos isolados em uma área C . Como estão isoladas, as imagens X n não contêm nada visível em C , desde que n permaneça pequeno. Por outro lado, se n ficar muito alto, podemos ver aparecer uma superfície visível em C , de medida diferente de zero, que muitas vezes é um artefato indesejável. Matematicamente, isso decorre do fato de que existe um conjunto contável de pontos, cada um dos quais forma um conjunto de medida zero, cuja adesão não é de medida zero. Podemos tomar por exemplo os pontos de C com coordenadas racionais.

Ao contrário do volume, a função de perímetro , ou mais precisamente a medida da borda, não tem continuidade. É possível construir duas figuras muito próximas, no sentido de Hausdorff, e de perímetros tão distantes quanto desejado. Usando a curva de Koch , é possível construir uma série convergente de figuras geométricas, cujos perímetros sucessivos divergem. Essa descontinuidade, para o engenheiro, significa que um algoritmo baseado apenas na distância de Hausdorff corre o risco de não respeitar os contornos com precisão. Esta é uma das razões para usar distâncias modificadas .

Manifestações

Aqui, E denota um espaço euclidiano.

• A soma de Minkowski é contínua:

Ou X e Y dois elementos E H . O objetivo é mostrar que a soma de Minkowski é contínua em ( X , Y ), ou seja:∀ϵ>0∃η>0∀X1,Y2∈EHd(X,X1)≤ηed(Y,Y1)≤η⇒d(X+Y,X1+Y1)≤ϵ{\ displaystyle \ forall \ epsilon> 0 \ quad \ exists \ eta> 0 \ quad \ forall X_ {1}, Y_ {2} \ in E_ {H} \ quad d (X, X_ {1}) \ leq \ eta \ quad {\ text {et}} \ quad d (Y, Y_ {1}) \ leq \ eta \; \ Rightarrow \; d (X + Y, X_ {1} + Y_ {1}) \ leq \ épsilon} Escolhemos η igual a ε / 2. Deixe que x + y ponto um de X + Y . Existe um ponto x 1 (resp. Y 1 ) de X 1 (resp. Y 1 ) a uma distância menor que ε / 2 de X (resp. Y). O ponto x 1 + y um de X 1 + Y 1 é necessariamente a uma distância inferior a ε de X + Y . Mostramos também que qualquer ponto de X 1 + Y 1 está a uma distância menor de ε do que X + Y , o que mostra a proposição.

Antes de estudar a continuidade da medida de Lebesgue, duas proposições intermediárias simplificam a prova.

• Uma sequência fechada limitada ( X n ) de E H , diminuindo no sentido de inclusão, é convergente no sentido de Hausdorff. O limite é a interseção dos elementos da sequência:

Seja X a interseção dos elementos da sequência. O conjunto X é limitado porque está incluído em um conjunto limitado, por exemplo X 1 . O conjunto é fechado porque a interseção do fechado é fechada.Resta apenas mostrar que se ε é um real estritamente positivo, existe um inteiro N tal que para qualquer n maior que N , um elemento de X n nunca está a uma distância maior de X do que ε. Por contraposição, isso equivale a mostrar que qualquer elemento y que está a uma distância maior de X do que ε não está em qualquer X n , se n for maior do que n , ou simplesmente que y não está em Y n . Como y não está em X e X é a interseção dos diferentes X n , pelo menos um desses conjuntos não o contém. Denote por X N , um destes, se n for maior que N , X n está incluído em X N e não pode conter y . Deduzimos que X contém o limite da sequência ( X n ). Por outro lado, o limite contém necessariamente X , que está incluído em cada X n .

Uma vez conhecido o comportamento de uma sequência decrescente para inclusão, podemos demonstrar a convergência de sua medida.

• Let Ser uma seqüência fechada limitada ( X n ) de elementos mensuráveis ​​de E H , decrescente no sentido de inclusão. O limite X é mensurável e a medida de X é o limite da série de medidas de X n  :

X é uma interseção contável de conjuntos mensuráveis, é um conjunto mensurável. Considere a sequência de funções (χ n ) de E para R , onde χ n é a função que associa 0 com x , se x não for um elemento de X 1 ou se x for um elemento de X n e 1 caso contrário. É uma sequência de funções crescentes positivas que simplesmente convergem para uma função χ. O teorema da convergência monotônica mostra que:limnão→∞∫Eχnão=∫Eχ{\ displaystyle \ lim _ {n \ to \ infty} \ int _ {E} \ chi _ {n} = \ int _ {E} \ chi} Que, em termos de medição definida assume a seguinte forma e comprova a proposição:limnão→∞µ(X1)-µ(Xnão)=µ(X1)-µ(X){\ displaystyle \ lim _ {n \ to \ infty} \ mu (X_ {1}) - \ mu (X_ {n}) = \ mu (X_ {1}) - \ mu (X) \;}

As duas proposições intermediárias nos permitem concluir. Para mostrar a semi-continuidade da medição, que é suficiente para mostrar que, se uma sequência de X n valores mensuráveis E H convergem no sentido de uma figura X , de modo que o limite superior de medições X n não excede a de X . Este é o método usado na demonstração.

• A medida de Lebesgue é semicontínua acima:

Começamos construindo uma sequência na qual é possível aplicar os dois lemas. Seja Y n a adesão da união de todos os X p para p maior que n . A sequência ( Y n ) é de fato uma sequência decrescente de fechada. Resta mostrar que ele é limitado e seu limite é a figura X . A partir de um determinado posto, qualquer elemento da sequência X p é incluído em X + B , onde B denota a bola unitária. A união de X p , se p exceder essa classificação, é limitada porque X é. O conjunto Y n é uma união finita de conjuntos limitados, o primeiro X p e de outro conjunto limitado, a união de X p , quando p ultrapassa o posto anterior, Y n é bem limitado.Mostram que o limite de ( Y n ) é X . Seja x um elemento de X e ε um real estritamente positivo. Como x é um elemento do conjunto X , existe um N tal que para qualquer n maior que N a bola com centro xe raio ε encontra X n . Deduzimos que essa bola intercepta todos os elementos da sequência Y n . Esta propriedade é verdadeira para todo ε, o que mostra que x está na aderência de todas essas uniões, e necessariamente em cada Y n , o que significa que pertence ao limite definido. Suponha agora que há não está em X , não é em seu poder desde X está fechada, há um verdadeiro ε como centro a bola lá e raio 2ε não atende X . Em outras palavras, a bola com centro y e raio ε não encontra nenhum membro de uma seção final da sequência ( X n ). Isso mostra que a partir de um determinado posto, y não está na aderência da união desta seção final e não está em qualquer Y n , se n for suficientemente alto.Vamos finalizar a demonstração. Tentamos provar que, se ε é um real estritamente positivo, existe um inteiro N tal que se n for um inteiro maior que N , então a medida de X n não excede a soma da medida de X e de ε. Na sequência das medidas de Y n é uma sequência decrescente que tende a medir X . A partir de um determinado posto N , não excede a soma da medida de X e ε. No entanto, nenhuma medida de X n excede a de Y N, o que termina a prova:∀não≥NÃOµ(Xnão)≤µ(YNÃO)≤µ(X)+ϵelim supnão→∞µ(Xnão)≤µ(X){\ displaystyle \ forall n \ geq N \ quad \ mu (X_ {n}) \ leq \ mu (Y_ {N}) \ leq \ mu (X) + \ epsilon \ quad {\ text {e}} \ quad \ limsup _ {n \ a \ infty} \ mu (X_ {n}) \ leq \ mu (X)}  

Propriedades

A distância Hausdorff em E define uma distância em todos os K ( E ) compacto não-vazia para E . K ( E ) é, então, um espaço métrico e sua topologia depende a de E .

Se E é um espaço completo , então K ( E ) está completo. O teorema do ponto fixo de Banach, portanto, se aplica. A aplicação do teorema do ponto fixo a K (E) é a base do estudo de um sistema de funções iteradas . Também deduzimos o teorema da ligação.

Se E é um espaço compacto , então K ( E ) é compacto.

Consequentemente, qualquer sequência de conjuntos de K ( E ) decrescentes no sentido de inclusão admite um limite no sentido de distância de Hausdorff, a saber(NOnão)não∈NÃO{\ displaystyle (A_ {n}) _ {n \ in \ mathbb {N}}}⋂não∈NÃONOnão.{\ displaystyle \ bigcap _ {n \ in \ mathbb {N}} {A_ {n}}.}

Propriedade

O Hausdorff distância D H ( S , T ) é zero se e somente se S = T e aumenta com diferenças cada vez mais importante aparecer entre S e T .

O cálculo da distância de Hausdorff pode ser feito usando um mapa de distância .

Comparação de esqueleto

De acordo com Choi e Seidel  (de) , a distância de Hausdorff conforme definida não é adequada para a comparação de formas por seu esqueleto ponderado . Na verdade, a esqueletização é uma transformação muito sensível às perturbações que aparecem nas formas. Mesmo que a distância de Hausdorff de duas formas seja muito pequena (as formas são muito semelhantes), seus respectivos esqueletos podem ser muito diferentes. Assim, a distância de Hausdorff entre os esqueletos pode não corresponder à semelhança de suas formas originais.

Para resolver este problema, Choi e Seidel propuseram substituir a distância euclidiana pela distância hiperbólica no cálculo da distância de Hausdorff.

Notas e referências

1. Também conhecido de distância de Hausdorff-Pompeiu , por exemplo (em) R. Tyrrell Rockafellar e Roger JB Wets, Variational analysis , Springer Verlag 1998 ( ISBN  9783540627722 ) lido online .
2. (in) W. Rucklidge, Efficient Visual Recognition Using the Hausdorff Distance , LNCS 1173, Berlin, Springer, 1996 ( ISBN  978-3-540-61993-2 ) .
3. A escolha da compactação nem sempre é feita, então aceitamos todos os limites fechados: (en) J. Henrikson, "  Completeness and Total Boundedness of the Hausdorff Metric  " [PDF] , MIT Undergraduate Journal of Mathematics , vol. 1, 1999, p.  69-79 .
4. Por exemplo, em um espaço vetorial normalizado , o conjunto X r é a soma de Minkowski de X e rB , onde B denota a bola unitária fechada.
5. As duas últimas expressões são usadas, por exemplo, em (en) Andrejs Treibergs, Inequalities that Imply the Isoperimetric Inequality , University of Utah , 2002.
6. Um exemplo dessa natureza é dado em É. Baudrier et al. , “  Um método de comparação de imagens…  ”, Simpósio GRETSI, 11 a 14 de setembro de 2007, Troyes , p.  1309-1312 .
7. (em) Sung Woo Choi e Hans-Peter Seidel, "Hyperbolic Hausdorff distance for medial axis transform  " Graphics Models , vol. 63, n o  5, 2001, p.  369-384 .

Veja também

Artigos relacionados

• Convergência Gromov-Hausdorff
• Lista de fractais por dimensão de Hausdorff
• Dimensão de Hausdorff

Bibliografia

• (pt) Herbert Federer , Teoria da Medida Geométrica , Springer, cana. 1996 ( ISBN  978-3-540-60656-7 )
• (en) James Munkres , Topologia; A First Course , Prentice Hall , 2 e impr. 1997 ( ISBN  978-9-81307682-2 )

Link externo

(pt) Distância de Hausdorff entre polígonos convexos

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">