Mathematical Morphology in Machine Learning

Resumo Técnico: Morfologia Matemática em Aprendizado de Máquina

Definição do Problema
Embora a Morfologia Matemática (MM) seja uma teoria estabelecida na computação visual para analisar objetos gráficos com base em forma, tamanho e convexidade, sua aplicação no aprendizado de máquina permanece subutilizada. As técnicas de aprendizado de máquina existentes frequentemente falham em explorar suficientemente as informações de forma e densidade. Além disso, os métodos atuais de agrupamento (clustering) e classificação ou dependem de heurísticas que não aderem totalmente aos princípios da MM, ou carecem da capacidade de modelar simultaneamente informações fractais, forma e densidade. Adicionalmente, em ambientes discretos (como o processamento baseado em GPU), as métricas de distância padrão apresentam compensações (trade-offs): a distância Euclidiana é computacionalmente dispendiosa e requer quantização, enquanto as distâncias de Chebyshev e Manhattan são rápidas, mas de natureza "quadrada", falhando em aproximar efetivamente a iteração circular da distância Euclidiana.

Metodologia
O artigo propõe um framework que integra a morfologia matemática ao aprendizado de máquina através de três componentes primários:

1. Algoritmo de Agrupamento k-Morphological Sets (k-MS):

   • Este algoritmo utiliza a reconstrução morfológica em vez de operações binárias (ao contrário dos algoritmos anteriores de Agrupamento de Morfologia Binária).
   • Ele opera em uma grade onde as instâncias de dados são mapeadas. Um elemento estruturante $B$ (inicialmente contendo zeros) e uma máscara $M$ são usados para realizar a reconstrução.
   • O algoritmo emprega uma variável interna $\delta$ para controlar o tamanho do elemento estruturante. Ele aumenta iterativamente $\delta$ para expandir os clusters até que um estado idempotente seja alcançado ou um número pré-definido de clusters ($k$) seja aproximado.
   • Se o número de índices de cluster únicos exceder $k$, $\delta$ é incrementado; se a reconstrução tornar-se não-idempotente (os clusters se fundem), $\delta$ retorna a 1 e o processo se repete.
   • O método segmenta intrinsecamente o ruído em pequenos clusters independentes sem custos de processamento adicionais.

2. Nova Métrica de Distância:

   • Para otimizar a iteração de vizinhança em espaços discretos (especificamente para implementação em GPU), uma nova métrica de distância é proposta.
   • Esta métrica é uma combinação ponderada da distância de Chebyshev e da distância de Minkowski (Equação 1: $d_{R^p}(x,y) = w_1 \sum |x_i - y_i|^p + w_2 \max |x_i - y_i|$).
   • Ao ajustar os pesos $w_1$ e $w_2$ e o parâmetro $p$, a métrica pode convergir para comportamentos de Chebyshev ou Minkowski.
   • Em 2D ($R^2$), esta distância produz uma forma octogonal, que é geometricamente mais próxima da distância Euclidiana circular do que as formas quadradas produzidas pelas distâncias de Manhattan ou Chebyshev.

3. Classificadores Morfológicos:

   • Os autores propõem classificadores que expandem instâncias de treinamento usando dilatações para cobrir o espaço não rotulado.
   • Estes classificadores são implementados em Unidades de Processamento Gráfico (GPUs) para explorar o processamento paralelo, onde as células da grade crescem simultaneamente.
   • Quando ocorrem interseções durante o crescimento, um esquema de votação determina o rótulo.

Principais Contribuições

• Algoritmo k-MS: Uma técnica de agrupamento que preserva a forma e a densidade, oferece um senso intrínseco do número máximo de clusters criáveis (independentemente de $k$) e remove o ruído sem sobrecarga computacional adicional.
• Métrica de Distância Híbrida: Uma nova métrica que combina as distâncias de Chebyshev e Minkowski, oferecendo um equilíbrio entre a eficiência computacional das distâncias "quadradas" e a precisão geométrica da distância Euclidiana.
• Implementação Otimizada para GPU: O desenvolvimento de classificadores morfológicos e cálculos de distância especificamente adaptados para ambientes de baixo nível de GPU, evitando acessos lentos a kernels e tamanhos de kernel indefinidos.
• Avaliação Abrangente: Testes extensivos da métrica de distância proposta utilizando o classificador k-Nearest Neighbors (k-NN) em 33 conjuntos de dados da UCI.

Resultados

• Eficiência de Agrupamento: O algoritmo k-MS mostrou-se mais rápido do que as técnicas de agrupamento baseadas em densidade de última geração, ao mesmo tempo em que fornece características únicas como remoção de ruído e preservação de forma. Em comparações de análise de tempo contra o k-Means paralelo (CPU), o k-MS demonstrou desempenho competitivo ou superior, particularmente conforme o número de clusters aumentava devido às otimizações de interrupção precoce (early-break).
• Desempenho da Métrica de Distância:
  • Velocidade: Em tarefas de iteração de vizinhança discreta em $Z^2$, a distância proposta foi aproximadamente 1,3 vezes mais rápida que a distância de Manhattan e 329,5 vezes mais rápida que a Euclidiana.
  • Precisão: Quando avaliada com k-NN em 33 conjuntos de dados da UCI, a distância proposta alcançou acurácias superiores à média de 14 outras distâncias em 26 de 33 casos. Alcançou a melhor acurácia individual em 9 de 33 casos.
• Agrupamento Visual: Em conjuntos de dados ruidosos, o k-MS segregou com sucesso clusters genuínos e outliers, enquanto outros algoritmos (como o Chameleon) por vezes agrupavam outliers com clusters genuínos, e outros (como o Mitosis) falharam em separar o ruído.

Significância e Alegações
Os autores afirmam que este trabalho representa a primeira proposta de técnicas de classificação e agrupamento que dependem inteiramente de técnicas de morfologia matemática, indo além de conexões heurísticas. O artigo afirma que nenhum outro classificador na literatura atual consegue modelar adequadamente forma, densidade e informação fractal simultaneamente.

A significância do trabalho reside em preencher a lacuna entre a teoria da computação visual e o aprendizado de máquina, fornecendo ferramentas que não são apenas teoricamente sólidas quanto à forma e densidade, mas também computacionalmente eficientes para o hardware moderno (GPUs). A métrica de distância proposta é destacada como uma solução prática para ambientes de computação de alto desempenho onde a distância Euclidiana é muito lenta e as distâncias de Manhattan/Chebyshev carecem de fidelidade geométrica suficiente. Os autores observam que estas contribuições já resultaram em múltiplas publicações em periódicos conceituados, como Pattern Recognition e Pattern Recognition Letters.