4. Morfologia Matemática binária · Introdução Metodologia: 1....

4.MorfologiaMatemáticabinária

Teoria elementar de conjuntos. Propriedades dos conjuntos. Propriedades dastransformações morfológicas. Noção de elemento estruturante. Transformaçãode vizinhança. Transformações morfológicas elementares. TransformaçõesTudo-ou-Nada. Adelgaçamento e Espessamento. Transformações geodésicas.Número de Euler (conectividade).

FernandoSoares

IntroduçãoOrigens:

• Trabalhos pioneiros de Georges Matheron e Jean Serra (década de 60, França).

• Criação do Centre de Morphologie Mathématique de Fontainebleau (1968).

Objectivo:

• A morfologia matemática baseia-se na teoria dos conjuntos, e pretendequantificar estruturas do ponto de vista geométrico.

FernandoSoares

IntroduçãoMetodologia:

1. Utiliza a noção de conjunto para representar estruturas.

2. Transformação dos conjuntos por forma a torná-los mensuráveis:

• Interacção do conjunto de objectos em estudo, com outro objecto comforma conhecida (elemento estruturante).

• A transformação do conjunto inicial, ao longo de sucessivas operações,evidencia as suas características estruturais, que são registadas ao longo dosnovos conjuntos gerados, o que implica que o conjunto transformado é maissimples que o conjunto original.

FernandoSoares

IntroduçãoMetodologia:

3. Realização de medidas sobre os conjuntos transformados.

FernandoSoares

T M

Medida:• Superfície• Forma• Perímetro• Etc.

IntroduçãoO processamento morfológico de imagem pode ser aplicado nos seguintescontextos:

• Morfologia binária: as imagens são binárias (mais frequente).

• Morfologia numérica: as imagens podem ser, ou de níveis de cinzento(monocromáticas), ou coloridas (policromáticas).

• Os termos «Morfologia» e «Matemática», associados (que constituem adesignação desta teoria), referem-se à utilização de conceitos de lógica deconjuntos e operações numéricas.

FernandoSoares

TeoriaelementardeconjuntosIntersecção

• Comutativa:

• Associativa:

• Idempotente:

FernandoSoares

𝑋 ∩ 𝑌 = 𝑥: 𝑥 ∈ 𝑋 ∧ 𝑥 ∈ 𝑌

𝑋 ∩ 𝑌 = 𝑌 ∩ 𝑋

𝑋 ∩ (𝑌 ∩ 𝑍) = (𝑌 ∩ 𝑋) ∩ 𝑍

𝑋 ∩ 𝑋 = 𝑋

TeoriaelementardeconjuntosReunião

• Comutativa:

• Associativa:

• Idempotente:

FernandoSoares

𝑋 ∪ 𝑌 = 𝑥: 𝑥 ∈ 𝑋 ∨ 𝑥 ∈ 𝑌

𝑋 ∪ 𝑌 = 𝑌 ∪ 𝑋

𝑋 ∪ (𝑌 ∪ 𝑍) = (𝑌 ∪ 𝑋) ∪ 𝑍

𝑋 ∪ 𝑋 = 𝑋

TeoriaelementardeconjuntosRelação entre a intersecção e a união (distributividade):

FernandoSoares

𝑋 ∩ (𝑌 ∪ 𝑍) = (𝑋 ∩ 𝑌) ∪ (𝑋 ∩ 𝑍)

𝑋 ∪ (𝑌 ∩ 𝑍) = (𝑋 ∪ 𝑌) ∩ (𝑋 ∪ 𝑍)

TeoriaelementardeconjuntosConjunto complementar

• Fórmulas de Morgan:

FernandoSoares

𝑋. / = 𝑥: 𝑥 ∈ 𝐸 ∧ 𝑥 ∉ 𝑋

X

E

(Xc)E(𝑋 ∩ 𝑌). / = 𝑋. / ∪ 𝑌. /

(𝑋 ∪ 𝑌). / = 𝑋. / ∩ 𝑌. /

E

TeoriaelementardeconjuntosDiferença lógica

ou

FernandoSoares

X Y

X-Y

𝑋 − 𝑌 = 𝑥: 𝑥 ∈ 𝑋 ∧ 𝑥 ∉ 𝑌

𝑋 − 𝑌 = 𝑋 ∩ 𝑋 ∩ 𝑌 .

PropriedadesdosconjuntosConexidade: um conjunto X diz-se conexo se, para quaisquer dois pontos P(xi,yi) eQ(xm,yn) nele incluídos, existe pelo menos um caminho que os une e que estátotalmente incluído em X.

A conexidade de um conjunto depende, no entanto, da forma como se encontradefinida a ligação entre os pixels numa malha digital (nas malhas digitais quadradascom conectividade-4 e conectividade-8, ou hexagonal com conectividade-6).

FernandoSoares

P

Q

XConexo

P Q

Xnãoconexo

PropriedadesdosconjuntosConvexidade: um conjunto X diz-se convexo se, qualquer que seja o par de pontosP(xi,yi) e Q(xm,yn) nele incluídos, o segmento de recta que os une está totalmenteincluído em X.

FernandoSoares

Xconvexo

PQ

Xnãoconvexo

P Q

PropriedadesdosconjuntosIsotropia: Um conjunto X diz-se isotrópico se está uniformemente espalhadosegundo todas as direções.

Predominando uma dada direcção, está-se perante um conjunto anisotrópico. Esteconceito está associado à estrutura espacial dos objetos.

FernandoSoares

XanisótropoXisótropo

PropriedadesdastransformaçõesmorfológicasSe φ é uma transformação morfológica então obedece a uma ou mais do que umadas seguintes propriedades:

• φ é extensiva se o conjunto resultante contém conjunto inicial X.

• φ é anti-extensiva se o conjunto resultante está contido no conjunto inicial X.

FernandoSoares

𝑋 ⊂ 𝜑(𝑋)

𝜑(𝑋) ⊂ 𝑋

• φ é crescente se a relação de inclusão entre os conjuntos inicial e resultante semantém.

• φ é idempotente se a sua aplicação sucessiva a X não o altera.

FernandoSoares

𝑌 ⊂ 𝑋 ⇒ 𝜑(𝑌) ⊂ 𝜑(𝑋)

𝜑(𝜑 𝑋 ) ≡ 𝑋

Propriedadesdastransformaçõesmorfológicas

• Duas transformações morfológicas φ1 e φ2 são duais se:

• Finalmente, uma transformação é dita homotópica se ela não modifica onúmero de conexidade E de um conjunto X, isto é:

FernandoSoares

𝜑7 𝑋 ≡ 𝜑8 𝑋.

𝐸 𝜑(𝑋) = 𝐸 𝑋

Propriedadesdastransformaçõesmorfológicas

NoçãodeelementoestruturanteElemento estruturante (B): É um caso particular de imagem binária, sendousualmente pequeno e simples (por exemplo B3×3 com todos os valores iguais aum).

Uma transformação morfológica só pode ser realizada com a definição prévia deum elemento estruturante.

Como o próprio nome indica, quando associado a uma certa transformaçãomorfológica, B percorre a imagem com o propósito de aferir se “encaixa” ou nãonos objectos nela presentes. No processo, pode modificar a forma e ascaracterísticas topológicas desses objectos (por exemplo, a conexidade ou aconvexidade).

FernandoSoares

NoçãodeelementoestruturanteA forma de B pode ser qualquer, sendo as mais comuns o quadrado, o disco, osegmento, o círculo, o par de pontos e o hexágono (na malha digital hexagonal),que são escolhidos de acordo com os objectivos pretendidos. Por exemplo:

• DISCO: determinação da distribuição de tamanho dos objectos (granulometria).

• SEGMENTO: detecção de alinhamentos preferenciais.

• PAR DE PONTOS: caracterização do estado de dispersão (covariância).

• CIRCUNFERÊNCIA: estudo da vizinhança de um ponto (transformação devizinhança).

FernandoSoares

Noçãodeelementoestruturante

FernandoSoares

Contém odisco

Não contém odisco

Contém osegmento

Não contém osegmento

Elementos estruturantes

Imagem binária inicial

NoçãodeelementoestruturanteO centro, ou pixel de referência de B é geralmente o seu centro geométrico,podendo contudo ser definido qualquer outro ponto para o efeito.

O centro de B marca a sua posição sobre a imagem inicial e, por conseguinte, aposição do pixel transformado.

A distribuição dos valores dos pixels no interior de B designa-se por configuraçãode vizinhança (V).

FernandoSoares

TransformaçãodevizinhançaUma transformação de vizinhança consiste na identificação/alteração de um pixelde uma imagem no caso de se verificar uma dada configuração de vizinhança V emredor desse pixel.

FernandoSoares

B

i) ii)

• Na figura, tem-se um quadrado elementar B quepercorrerá todos os pixels da imagem i).

• Em ii) estão marcadas as posições em que a configuraçãode vizinhança V(Bx) é idêntica à de B.

• Como transformações de vizinhança mais comuns têm-seo adelgaçamento e o espessamento.

TransformaçõesmorfológicaselementaresA transformação morfológica de erosão (e) de um dado conjunto X, por umelemento estruturante com a sua origem em x (Bx), define-se pela expressãoseguinte:

FernandoSoares

𝜀: 𝑋 = 𝑥: 𝐵< ⊂ 𝑋

𝜀:=(>×>) 𝑋 𝜀:=(@×@) 𝑋𝑋

TransformaçõesmorfológicaselementaresA transformação morfológica de dilatação (d) de um dado conjunto X, por umelemento estruturante com a sua origem em x (Bx), define-se pela expressãoseguinte:

FernandoSoares

𝛿: 𝑋 = 𝑥: 𝐵< ∩ 𝑋 ≠ ϕ

𝛿:=(>×>) 𝑋 𝛿:=(@×@) 𝑋𝑋

TransformaçõesmorfológicaselementaresA abertura (𝛾) de X consiste em executar a dilatação do resultado da erosão doconjunto X.

FernandoSoares

𝛾: 𝑋 = 𝛿: 𝜀:(𝑋)

𝑋𝜀:=(>×>) 𝑋 = 𝑌 𝛿:=(>×>) 𝑌 = 𝛾: 𝑋

TransformaçõesmorfológicaselementaresO fecho (𝜙) de X consiste em executar a erosão do resultado da dilatação doconjunto X.

FernandoSoares

𝜙: 𝑋 = 𝜀: 𝛿:(𝑋)

𝑋𝛿:=(>×>) 𝑋 = 𝑌 𝜀:=(>×>) 𝑌 = 𝜙: 𝑋

Transformaçõesmorfológicaselementares• Tabela de propriedades das transformações morfológicas elementares:

FernandoSoares

TransformaçãoTudo-ou-Nada(Hit-or-Miss)A transformação “Tudo-ou-Nada” (Hit-or-Miss transformation - HMT) aplicada a Xconsiste numa transformação de vizinhança que recorre a um elementoestruturante composto B = (B1,B2), com B1 ∩ B2 = φ, e que resulta da verificaçãosimultânea das seguintes condições: B1 coincide com X e B2 coincide com Xc.

• Os índices do elemento estruturante composto são geralmente três: “1” (∈domínio de B1), “-1” (∈domínio de B2) e “0” (é indiferente).

• A HMT é geralmente usada para encontrar configurações específicas em gruposde pixels ou objectos e determina-se pela intersecção entre as erosões de X porB1 e de Xc por B2 (como se verá em alguns exemplos a seguir).

FernandoSoares

𝐻𝑀𝑇: 𝑋 = 𝑥: 𝐵7 < ⊆ 𝑋 ∧ 𝐵8 < ⊆ 𝑋. 𝐻𝑀𝑇: 𝑋 = 𝜀:K(𝑋) ∩ 𝜀:L(𝑋.)

Transformações“Tudo-ou-Nada”(exemplos)Pontos isolados (pixels sem quaisquer outros pixels na sua vizinhança).

Desenham-se duas configurações (EE) B1 e B2, tal que, B1⊆ X e B2⊆ Xc.

Optando por um B composto tem-se a seguinte configuração:

FernandoSoares

1=pertence-1=pertenceaocomplementar0=indiferente.

Transformações“Tudo-ou-Nada”(exemplos)

FernandoSoares

𝜀:K(𝑋) = 𝑥: 𝐵7 ⊂ 𝑋

𝜀:L(𝑋.) = 𝑥: 𝐵8 ⊂ 𝑋.

𝑃𝑜𝑛𝑡𝑜𝑠𝑖𝑠𝑜𝑙𝑎𝑑𝑜𝑠 = 𝜀:K ∩ 𝜀:L

Transformações“Tudo-ou-Nada”(exemplos)Pontos extremos (pixels com um pixel no máximo na sua vizinhança próxima).

Usando B1 e B2:

Usando B composto:

FernandoSoares

𝐸𝑥𝑡𝑟𝑒𝑚𝑖𝑑𝑎𝑑𝑒𝑠

Transformações“Tudo-ou-Nada”(exemplos)Pontos múltiplos (pixels com mais do que dois pixels na sua vizinhança próxima).

Usando B1 e B2:

• Usando B composto:

FernandoSoares

𝑃𝑜𝑛𝑡𝑜𝑠𝑚ú𝑙𝑡𝑖𝑝𝑙𝑜𝑠

Transformações“Tudo-ou-Nada”(exemplos)Cantos rectos (pixels que formam um ângulo recto convexo).

Usando B1 e B2:

Usando B composto:

FernandoSoares

𝐶𝑎𝑛𝑡𝑜𝑠𝑟𝑒𝑐𝑡𝑜𝑠

Transformações“Tudo-ou-Nada”(exemplos)Contornos (pixels com pelo menos um pixel pertencente ao conjuntocomplementar na sua vizinhança próxima).

Usando B1 e B2:

Usando B composto:

FernandoSoares

𝑃𝑜𝑛𝑡𝑜𝑠𝑑𝑒𝑓𝑟𝑜𝑛𝑡𝑒𝑖𝑟𝑎

TransformaçãodeadelgaçamentoAdelgaçamento (THIN) de um conjunto X: consiste numa transformação devizinhança que retira a X todos pontos que correspondam a uma dada configuraçãode vizinhança V(Bx).

FernandoSoares

𝑇𝐻𝐼𝑁 𝑋, 𝐵 = 𝑋 ∩ 𝑁𝑂𝑇 𝐻𝑀𝑇(𝑋, 𝐵)

Visa remover pixels de regiões/objectos da imagem.

É aplicada apenas a imagens binárias e produz uma imagem binária comoresultado.

De forma geral, a operação de adelgaçamento é determinada por translação daorigem do elemento estruturante B, por todos os pixels da imagem, comparandoem cada um a sua configuração de vizinhança com a configuração doscorrespondentes pixels na imagem.

FernandoSoares

Transformaçãodeadelgaçamento

Havendo uma coincidência entre ambas as configurações, então ao pixel daimagem correspondente à posição do centro de B é atribuído o valor 0; casocontrário mantém-se inalterável.

A erosão e a abertura morfológicas são exemplos de transformações deadelgaçamento.

FernandoSoares

Transformaçãodeadelgaçamento

TransformaçãodeadelgaçamentoA “esqueletização” é um exemplo de um processo de adelgaçamento morfológicoque visa reduzir as regiões de uma imagem binária a uma estrutura mínima quepreserve a extensão e conectividade das regiões originais.

• É uma transformação usada frequentemente para “estreitar” resultados dedetecção de fronteiras, reduzindo a espessura das linhas a outras com apenasum pixel de espessura.

• Note-se que o esqueleto resultante é um conjunto conexo é igualmente umconjunto conexo.

FernandoSoares

TransformaçãodeadelgaçamentoO esqueleto de um conjunto pode ser determinado de diversas formas:

a) Localização dos centros de circunferências máximas bi-tangentes aos limites daregião considerada.

FernandoSoares

Transformaçãodeadelgaçamentob) Fórmula de Lantuéjoul: para uma imagem binária discreta X, o esqueleto S(X) é aunião de todos os subconjuntos Sk(X), com um elemento estruturante B dedimensão k.

FernandoSoares

𝑆 𝑋 =c𝑆d(𝑋)e

d

𝑆d 𝑋 = 𝜀d:(𝑋) ∩ 𝑁𝑂𝑇 𝛾:(𝜀d: 𝑋 )

TransformaçãodeadelgaçamentoO “escanhoamento” (prune) é também uma operação de adelgaçamento que visasuprimir sucessivamente os pontos extremos de um conjunto binário, até severificar a condição de idempotência.

FernandoSoares

TransformaçãodeespessamentoEspessamento (THICK) de um conjunto X: consiste numa transformação devizinhança que adiciona a X todos pontos que correspondam a uma determinadaconfiguração de vizinhança V(Bx).

FernandoSoares

𝑇𝐻𝐼𝐶𝐾 𝑋, 𝐵 = 𝑋 ∪ 𝐻𝑀𝑇(𝑋, 𝐵)

TransformaçãodeespessamentoVisa fazer crescer regiões/objectos adicionando pixels às mesmas.

É aplicada apenas a imagens binárias e produz uma imagem binária comoresultado.

É usada em diversas aplicações, entre as quais a determinação do espaço convexode um certo conjunto de pontos (convex hull), ou ainda na determinação do“esqueleto por zonas de influência” (SKIZ- Skeleton by Influence Zone).

FernandoSoares

TransformaçãodeespessamentoDe forma geral, a operação de espessamento é determinada por translação daorigem do elemento estruturante B, por todos os pixels da imagem, comparandoem cada um a sua configuração de vizinhança com a configuração doscorrespondentes pixels na imagem.

Se se verificar uma coincidência entre ambas as configurações, então no pixelcorrespondente à posição do centro de B é atribuído o valor 1; caso contráriomantém-se inalterável.

A dilatação e o fecho morfológicos são exemplos de transformações deespessamento.

FernandoSoares

TransformaçãodeespessamentoO “envelope convexo” (convex hull) determina-se por execução da transformaçãoHMT, para determinar concavidades nos objectos e consequente preenchimento. Aoperação é iterativa e continuará até atingir a idempotência.

FernandoSoares

Convex Hull

TransformaçãodeespessamentoO ”skeleton by influence zones” (SKIZ) é uma estrutura de esqueleto que divide umaimagem em regiões, cada qual contendo um objecto distinto da imagem.

• As fronteiras são definidas por forma a que todos os pontos interiores a cadaárea estejam mais próximos do correspondente objecto interior a essa área.

• É por vezes designada por Diagrama de Voronoi. A operação é iterativa econtinuará até atingir a idempotência.

FernandoSoares

TransformaçãodeespessamentoO SKIZ pode ser obtido por um processo métrico, calculando distâncias euclidianas,ou por processos morfológicos, envolvendo dilatações com elementosestruturantes de diferentes tamanhos.

FernandoSoares

Esqueletodobackground Escanhoamentodoesqueleto

TransformaçõesgeodésicasbináriasAs transformações geodésicas binárias são transformações morfológicas sobreuma imagem binária Y, condicionadas por uma determinada geodesia binária X.

• De entre estas transformações salientam-se:

1 - Reconstrução geodésica binária por dilatações geodésicas sucessivas.

2 - Reconstrução geodésica binária por erosões geodésicas sucessivas.

FernandoSoares

TransformaçõesgeodésicasbináriasDilatação geodésica: dilatação morfológica de um conjunto Y condicionada àgeodesia X.

FernandoSoares

Geodesia Marcador

𝛿g 𝑌 = 𝛿(𝑌) ∩ 𝑋

TransformaçõesgeodésicasbináriasReconstrução geodésica binária por dilatações geodésicas sucessivas:

FernandoSoares

𝑅g 𝑌 = 𝛿gi 𝑌 = limm→i

(𝛿g𝑜 …𝑜𝛿g) 𝑌 = 𝛿gm 𝛿gmp7 𝛿gmp8 … 𝛿g7 𝑌

TransformaçõesgeodésicasbináriasErosão geodésica: erosão morfológica de um conjunto Y condicionada à geodesiaX.

FernandoSoares

𝜀g 𝑌 = 𝜀(𝑌) ∪ 𝑋

TransformaçõesgeodésicasbináriasReconstrução geodésica binária por erosões geodésicas sucessivas:

FernandoSoares

𝑅g 𝑌 = 𝜀gi 𝑌 = limm→i

(𝜀g𝑜 …𝑜𝜀g) 𝑌 = 𝜀gm 𝜀gmp7 𝜀gmp8 … 𝜀g7 𝑌

Númerodeconectividade(nºdeEuler)De forma geral, o número de conexidade de uma superfície ou conjunto, outambém chamado número de Euler (E), é igual ao número de vértices v, menos onúmero de arestas a, mais o número de polígonos p, quando dividida a ditasuperfície em polígonos planos definidos pelas arestas e pelos vértices.

FernandoSoares

E =4- 5+2=1 E =8- 16+8=0 E =7- 14+7=0 E =11- 25+13=-1

E =v - a +p

Númerodeconectividade(nºdeEuler)• No domínio de representação de uma imagem digital, o valor de E determina-se

a partir do grafo de representação dos pixels. A seguir exemplifica-se adeterminação de E para o objecto binário sombreado.

FernandoSoares

Númerodepixels =11Númerodearestasdografo=15Númerodetriângulos=5E =11- 15+5=1

Númerodeobjectos =2Númerodeburacos=1

E =2-1=1

E =v - a +p