Segmentação de Imagens com K-Means e Aplicações em Visão Computacional

Visão computacional - k-means na modelagem e classificação de cores

As fontes pesquisadas (ver relação ao final), e organizadas pelo Notebook LM, exploram técnicas de quantização de cores e segmentação de imagens, frequentemente empregando o algoritmo k-means. Um documento discute o uso do k-means para reduzir o número de cores em imagens, apresentando uma variante otimizada chamada Weighted Sort-Means (WSM) para melhor eficiência e qualidade. Outra fonte propõe um método baseado em k-means para segmentação de imagens, visando melhorar a robustez contra ruído e a qualidade dos resultados, especialmente para imagens degradadas. Por fim, um artigo avalia a adequação de diferentes espaços de cores (RGB, HSV, YCbCr e CIELAB) para segmentação utilizando k-means, empregando métricas de validação de clusters para determinar o espaço mais eficaz em vários cenários.

Quais as principais aplicações da segmentação de imagens?

Com base nas fontes fornecidas, a segmentação de imagens é uma operação fundamental com diversas aplicações. Aqui estão as principais áreas de aplicação mencionadas:

• Pré-processamento para tarefas de processamento de imagem e gráficos: A quantização de cores, um processo frequentemente baseado em clustering que resulta na seleção de uma paleta de cores e mapeamento de pixels, é comumente utilizada como um passo de pré-processamento para várias tarefas de processamento de imagem e gráficos1.

•Compressão de imagem. A quantização de cores (CQ) é uma operação fundamental que visa reduzir o grande número de cores presentes em imagens de cor real (normalmente 24 bits, contendo milhares de cores) para um número menor de cores (K). Isso é crucial porque um número excessivo de cores pode tornar a exibição, armazenamento, transmissão e processamento de imagens problemáticos. A CQ, ao selecionar uma paleta de cores reduzida e mapear os pixels originais para as cores dessa paleta, simplifica a representação da imagem.

•Segmentação propriamente dita: A segmentação de imagens tem como objetivo dividir uma imagem de N pixels em K regiões com características semelhantes (bordas, intensidades, cores ou texturas). Muitos métodos de segmentação de imagens baseiam-se em modelos variacionais e métodos de clustering. Pode ser utilizada para determinar a cor mais apropriada para cada pixel.

• Detecção/localização de texto.

•Análise de cor-textura. As fontes indicam que esta aplicação se baseia em trabalhos como o de O. Sertel e colaboradores, focando em análise de imagens histopatológicas usando representações intermediárias baseadas em modelos e cor-textura.

Além disso, a segmentação de imagens em geral tem como objetivo dividir uma imagem em regiões com características semelhantes, que podem incluir cores ou texturas. Uma fonte menciona especificamente a segmentação não supervisionada de regiões de cor-textura.

Portanto, a análise de cor-textura é uma área de aplicação onde a quantização de cores e a segmentação de imagens desempenham um papel, sendo explicitamente mencionada no contexto de análise de imagens médicas, como a análise histopatológica

•Recuperação baseada em conteúdo: utiliza técnicas como a quantização e segmentação de cores (frequentemente empregando algoritmos de clustering) para extrair características visuais importantes que permitem buscar e recuperar imagens com base em seu conteúdo, sendo listada como uma aplicação relevante, inclusive no domínio médico.

•Detecção de objetos. A segmentação de cores pode ser empregada como um passo para a extração de características em sistemas de visão computacional. Em jogos de futebol de robôs, isso envolve a identificação de objetos coloridos como o campo, as linhas, a bola, robôs e traves. A segmentação, frequentemente realizada offline com o resultado armazenado em uma tabela de consulta (LUT) para classificação de cores em tempo real, permite mapear os pixels em classes de cores, o que auxilia na localização e identificação desses objetos.

Em modelos modernos como os Vision Transformers (ViTs), a análise por camadas revela que os conceitos evoluem de características básicas para classes mais complexas. Embora as camadas iniciais aprendam conceitos mais universais como cores e texturas, as camadas posteriores especializam-se em conceitos mais complexos e específicos, como objetos e elementos naturais. Isso sugere que a capacidade de detectar objetos complexos em sistemas de visão computacional, incluindo aqueles que utilizam arquiteturas baseadas em transformadores, baseia-se na representação construída progressivamente a partir de características de baixo nível, como cor e textura, muitas vezes isoladas ou agrupadas através de técnicas como quantização e segmentação de imagens.

•Diagnóstico médico: A segmentação de imagens é amplamente aplicada em campos como o diagnóstico médico A quantização de cores também tem várias aplicações na análise de imagens médicas, e métodos baseados em k-means podem ser utilizados para facilitar a detecção de bordas de lesões de pele, simplificando as imagens antes da segmentação. Também pode ser utilizada para determinar o número de cores dominantes em uma lesão de pele para fins de diagnóstico.

•Classificação de dados de alta dimensão e nuvens de pontos.

•Segmentação de imagens corrompidas por ruído: Estratégias como Smoothing, Lifting e Thresholding (SLaT) são propostas para segmentar imagens coloridas degradadas. Métodos baseados em modelos variacionais também visam reduzir o efeito de "staircase" (escada), especialmente para imagens ruidosas.

•Segmentação de imagens borradas com ruído Poisson ou Gamma multiplicativo16.

•

Extração de características (Feature Extraction: Em sistemas de visão computacional, a segmentação de cores é frequentemente empregada como um passo para a extração de características.

•Ambientes codificados por cores, como futebol de robôs: A segmentação de cores é crucial em ambientes onde características importantes são codificadas por cores, como no futebol de robôs.

•Classificação de cores em tempo real: O processo de segmentação de cores pode ser realizado offline, com o mapeamento resultante representado em uma tabela de consulta (LUT) para classificação de cores eficiente em tempo real. Pesquisas futuras incluem a automação da geração de LUTs para segmentação de imagens coloridas em tempo real.

•Documentação do patrimônio cultural: A extração de cores dominantes com K-means é proposta para a caracterização de câmeras na documentação do patrimônio cultural20. A segmentação de cores (agrupamento de pixels por similaridade de cor) pode ser considerada uma aplicação específica para extrair cores dominantes para a caracterização de câmeras. O objetivo é usar essas cores dominantes para selecionar amostras de treinamento ideais para a caracterização da câmera, a fim de registrar e documentar com precisão a cor de cenas de arte rupestre e, de forma mais ampla, objetos, monumentos e locais do patrimônio cultural.

Em resumo, a segmentação de imagens é uma ferramenta versátil utilizada em uma ampla gama de aplicações, desde o processamento básico de imagens até tarefas complexas em domínios específicos como medicina, patrimônio cultural e robótica, frequentemente empregando algoritmos de clustering como o k-means.

Aplicações do algoritmo K-Means em processamento de imagens

O algoritmo K-Means (KM) é amplamente utilizado em diversas tarefas de processamento de imagens. Uma aplicação proeminente é a quantização de cores, onde ele é usado para reduzir o número de cores distintas em uma imagem, agrupando cores semelhantes e representando cada grupo por uma cor central (centroid). Isso é crucial em aplicações como compressão de imagem, exibição em dispositivos com paletas de cores limitadas e análise de imagem. Além da quantização de cores, o K-Means também é empregado em segmentação de imagens para particionar uma imagem em regiões homogêneas com base nas características dos pixels, como cor e textura. Outras áreas incluem análise de formas em documentos digitalizados e reconhecimento de objetos.

Como o algoritmo K-Means realiza o agrupamento de dados?

O K-Means é um algoritmo de agrupamento partitivo que divide um conjunto de dados em K grupos (clusters) distintos e exaustivos. Dado um conjunto de dados, o objetivo é minimizar a Soma dos Erros Quadrados (SSE), que é a soma das distâncias quadradas de cada ponto de dado ao centroide de seu cluster atribuído. O algoritmo começa selecionando K centroides iniciais, geralmente escolhidos aleatoriamente dos pontos de dados. Em seguida, ele itera através de duas etapas principais: atribuição e atualização. Na etapa de atribuição, cada ponto de dado é atribuído ao centroide mais próximo, normalmente usando a distância Euclidiana. Na etapa de atualização, os centroides são recalculados como a média de todos os pontos de dados atribuídos a cada cluster. Essas duas etapas são repetidas até que um critério de término predefinido seja atendido, como um número máximo de iterações ou quando os centroides não se movem significativamente.

O K-Means (KM) no contexto de Visão computacional

Com base nas fontes estudadas, o algoritmo K-Means (KM) é um método de agrupamento de dados amplamente utilizado, fundamental para operações como a quantização e segmentação de imagens coloridas. Ele opera dividindo um conjunto de dados de N pontos em K grupos ou "clusters" distintos e exaustivos. No contexto de imagens coloridas, os "pontos de dados" são tipicamente os pixels da imagem, representados por seus valores de cor em um espaço tridimensional, como RGB ou CIELab*.

O principal objetivo do K-Means para agrupamento de cores é minimizar a Soma do Erro Quadrático (SSE). A SSE é definida como a soma dos quadrados das distâncias entre cada pixel e o centro do cluster ao qual foi atribuído. Matematicamente, isso é representado por:

\(\text{SSE} = \sum_{k=1}^{K} \sum_{x_i \in S_k} \|x_i - c_k\|^2\)

Onde:

K é o número de clusters desejado (ou seja, o número de cores finais).
S_k é o k-ésimo cluster, contendo um conjunto de pixels.
x_i é um pixel (ponto de dado) pertencente ao cluster S_k.
c_k é o centro (centroid) do cluster S_k, calculado como a média dos pixels nesse cluster.
|.|^2 denota o quadrado da norma Euclidiana (distância L2).

O algoritmo heuristicamente busca minimizar a SSE através de um procedimento iterativo, comumente conhecido como algoritmo de Lloyd:

Inicialização: O processo começa selecionando K centros iniciais para os clusters. Estes são frequentemente escolhidos aleatoriamente a partir dos pixels da imagem. A escolha da inicialização é conhecida por ser um fator importante, pois K-Means é sensível a ela e pode terminar em mínimos locais ruins ou resultar em clusters vazios ('dead units'). Métodos como K-means++ visam melhorar a velocidade e consistência da inicialização.
Etapa de Atribuição (Assignment): Cada pixel na imagem é atribuído ao centro de cluster mais próximo a ele, com base na distância Euclidiana.
Etapa de Atualização (Update): Para cada cluster, o seu centro é recalculado como a média de todos os pixels que foram atribuídos a esse cluster na etapa anterior.
Critério de Término: As etapas de Atribuição e Atualização são repetidas até que um critério de término predefinido seja atingido. Isso geralmente acontece quando os centros dos clusters não mudam significativamente entre as iterações. O algoritmo tem garantia de término.

Uma vez que o algoritmo converge, o resultado são os K centros de cluster finais (que formam a paleta de cores selecionada) e a atribuição de cada pixel a um desses centros. No contexto da quantização de cores, essa paleta reduz o número de cores únicas na imagem original para K, e cada pixel original é mapeado para a cor do centro do cluster ao qual foi atribuído. Para segmentação, isso significa que pixels com cores semelhantes são agrupados em regiões distintas, representadas pelos centros dos clusters.

Embora conceitualmente simples e versátil, o K-Means tradicional tem desvantagens para quantização de cores, incluindo altos requisitos computacionais (a fase de geração da paleta é cara devido à natureza iterativa) e a fase de mapeamento de pixels pode ser ineficiente. A complexidade de tempo por iteração é O(NK), onde N é o número de pontos (pixels), K é o número de clusters, e a dimensão D=3 para dados de cor. Para lidar com esses desafios, modificações como o Weighted Sort-Means (WSM) foram propostas, incorporando técnicas como redução de dados (subsampling), ponderação de amostras e busca acelerada pelo vizinho mais próximo. A aplicação do K-Means em grandes imagens também pode ser acelerada processando apenas um subconjunto de amostras de pixels.

Em aplicações como a documentação do patrimônio cultural, o K-Means é usado para extrair cores dominantes de amostras de imagens para caracterizar câmeras, permitindo uma seleção ótima de amostras de treinamento para garantir o registro preciso da cor das cenas. No contexto da segmentação de imagens, K-Means é frequentemente utilizado para determinar os limiares de cores na etapa de segmentação, especialmente em estratégias como Smoothing and Thresholding (SaT). Em sistemas de visão computacional, a segmentação de cores baseada em K-Means pode ser um passo crucial para a extração de características, como na identificação de objetos em ambientes codificados por cores, como futebol de robôs.

Quais são algumas das abordagens para inicializar os centroides no K-Means e como elas afetam o desempenho?

A escolha dos centroides iniciais pode ter um impacto significativo no resultado e no desempenho do algoritmo K-Means, pois o problema é conhecido por ser NP-difícil. Abordagens comuns de inicialização incluem:

Inicialização Aleatória: Escolher K pontos de dados aleatoriamente como centroides iniciais. Embora simples, pode levar a resultados subótimos.
Divisão (LBG): Começar com um único centroide (o centroide do conjunto de dados) e iterativamente dividi-lo em dois novos centroides, refinando-os com K-Means até obter K centroides.
Minmax (MMX): Selecionar o primeiro centroide aleatoriamente e os centroides subsequentes são escolhidos como o ponto com a maior distância mínima aos centroides já selecionados.
Baseada em Densidade (DEN): Particionar o espaço de dados uniformemente e escolher centroides aleatoriamente de células com um número proporcional de pontos.
Variância Máxima (VAR): Ordenar os dados pela dimensão com a maior variância e dividi-los em K grupos, usando os centroides desses grupos.
K-Means++ (KPP): Selecionar o primeiro centroide aleatoriamente. Para os centroides subsequentes, um ponto de dado é escolhido com uma probabilidade proporcional à distância quadrada mínima aos centroides já selecionados. Esta abordagem visa selecionar centroides iniciais que sejam bem espaçados. Diferentes esquemas de inicialização podem influenciar a qualidade do agrupamento (medida, por exemplo, pelo MSE) e o tempo de CPU necessário para convergir.

Como a qualidade de um método de quantização de cores baseado em K-Means pode ser avaliada?

A qualidade de um método de quantização de cores é frequentemente avaliada usando métricas que quantificam a diferença entre a imagem original e a imagem quantizada. Uma medida comumente usada é o Erro Quadrado Médio (MSE), que calcula a média das distâncias quadradas entre os valores de pixel correspondentes nas imagens original e quantizada. Um MSE menor indica uma menor distorção e, portanto, uma melhor qualidade de quantização. Outra métrica relacionada é a Peak Signal-to-Noise Ratio (PSNR), que é calculada a partir do MSE e é expressa em decibéis. Um PSNR maior indica uma melhor qualidade. Além dessas métricas objetivas, a avaliação visual das imagens quantizadas também é importante para avaliar a fidelidade perceptual das cores.

Quais são algumas modificações propostas para o algoritmo K-Means para melhorar o desempenho na quantização de cores?

Diversas modificações foram propostas para melhorar a eficiência e a qualidade do K-Means para quantização de cores. Algumas delas incluem:

Subamostragem: Reduzir o tamanho do conjunto de dados de entrada, selecionando um subconjunto de pixels para o agrupamento. Isso pode ser feito aleatoriamente ou usando métodos mais sofisticados. Uma variante envolve o uso de um histograma de cores ponderado para preservar a distribuição de cores original.
Ponderação de Amostras: Atribuir um peso a cada ponto de dado (pixel) que é proporcional à sua frequência na imagem original. O algoritmo K-Means é modificado para incorporar esses pesos no cálculo dos centroides (média ponderada). Isso ajuda a levar em conta a distribuição de cores mesmo ao usar subamostragem.
Algoritmo Sort-Means (SM): Reduzir o número de cálculos de distância na etapa de atribuição explorando a desigualdade triangular e pré-calculando as distâncias entre os centroides. O Sort-Means aprimora isso ordenando as distâncias dos centroides e pulando comparações desnecessárias. O Weighted Sort-Means (WSM) combina ponderação de amostras com a otimização do Sort-Means.

O modelo de Potts em processamento de imagens e como ele se relaciona com o K-Means

O modelo de Potts é uma formulação baseada no problema clássico de K-Means que adiciona um termo de regularização espacial para promover a homogeneidade da região na segmentação de imagens. Enquanto o K-Means clássico minimiza apenas a soma das distâncias quadradas dos pontos aos centroides, o modelo de Potts adiciona um termo de penalidade proporcional à soma dos perímetros das regiões segmentadas. Este termo de penalidade (controlado por um parâmetro λ) incentiva a formação de regiões compactas e conectadas, reduzindo o ruído e o efeito de "escada". O K-Means clássico pode ser visto como um caso especial do modelo de Potts sem o termo de penalização de perímetro. O modelo de Potts suavizado introduz um termo quadrático da primeira derivada para mitigar o efeito de escada.

Como diferentes espaços de cores afetam o desempenho do agrupamento K-Means para segmentação de imagens?

A escolha do espaço de cores tem um impacto significativo no desempenho do K-Means na segmentação de imagens. Espaços de cores como RGB, HSV, YCbCr e CIELAB representam as cores de maneiras diferentes, com diferentes níveis de correlação entre os canais e diferentes reflexos da percepção humana. Estudos mostram que espaços de cores que separam a informação de luminância (brilho) da informação de crominância (cor), como HSV, YCbCr e CIELAB, geralmente levam a clusters mais uniformes para cores semelhantes e são menos suscetíveis a variações de iluminação. O espaço YCbCr demonstrou bom desempenho, especialmente em imagens com níveis variados de ruído. A avaliação do desempenho do agrupamento em diferentes espaços de cores pode ser feita usando métricas de validação de clusters, como o índice de Dunn, que mede a compacidade e a separação dos clusters.

Quais são as vantagens e desvantagens de usar o índice de Dunn para validar clusters em espaços de cores?

O índice de Dunn é uma métrica de validação de clusters que avalia a qualidade de uma partição de clusters maximizando a distância mínima entre clusters e minimizando a distância máxima intra-cluster. Uma vantagem do índice de Dunn é que ele é conceitualmente simples e tem baixa complexidade computacional. Ele não assume formas ou tamanhos específicos para os clusters, o que o torna útil para avaliar o agrupamento em diferentes espaços de cores. No entanto, uma desvantagem significativa do índice de Dunn é sua sensibilidade a outliers. Como ele se baseia nas distâncias mínima inter-cluster e máxima intra-cluster, a presença de outliers pode afetar drasticamente o valor do índice, potencialmente levando a uma avaliação enganosa da qualidade do agrupamento. Portanto, é importante escolher funções de distância que minimizem o impacto do ruído e dos outliers ao usar o índice de Dunn.

Resumo:

O objetivo principal do algoritmo K-Means na quantização de cores é agrupar os pixels de uma imagem em um número predefinido de clusters, onde os centros dos clusters representam as cores quantizadas na paleta resultante. Isso reduz o número de cores na imagem original.
Em cada iteração, o algoritmo KM atribui cada ponto de dados ao centro de cluster mais próximo, geralmente usando a distância euclidiana (norma L2).
O algoritmo Sort-Means reduz os cálculos redundantes de distância ao pré-calcular as distâncias entre os centros dos clusters e usar a desigualdade triangular para pular alguns cálculos de distância durante a fase de atribuição.
A ponderação de amostras aborda a desvantagem da subamostragem que desconsidera a distribuição de cores da imagem original. Atribuir pesos proporcionais à frequência de cada cor na imagem original garante que as cores mais comuns tenham maior influência nos centros dos clusters.
O MSE é o erro médio entre a imagem original e a imagem quantizada, calculado como a soma dos erros quadráticos das diferenças de pixel dividida pelo número total de pixels. Ele é uma medida comum de avaliação para quantificar a distorção introduzida pela quantização.
O modelo Potts para segmentação de imagem minimiza a soma do erro quadrático entre os dados de imagem e os centros dos clusters, juntamente com uma penalidade para a soma do perímetro das regiões segmentadas. Isso promove a homogeneidade espacial nas regiões.
O parâmetro λ no modelo Potts controla o nível de regularização espacial. Um valor mais alto de λ penaliza mais fortemente os perímetros das regiões, levando a segmentos mais suaves e menos fragmentados.
O Dunn's index é um índice de validação de cluster interno usado para avaliar a qualidade das partições de cluster. Ele busca maximizar a distância mínima entre clusters (separação) enquanto minimiza a distância máxima dentro dos clusters (compactação).
A distância euclidiana é escolhida para consistência com a implementação do K-Means, pois o algoritmo K-Means minimiza a soma dos erros quadráticos, que é equivalente a minimizar a soma das distâncias euclidianas quadráticas dos pontos aos seus centros de cluster atribuídos.
O espaço de cores YCbCr demonstrou melhor desempenho para segmentação de cores usando K-Means em imagens com ruído cromático mais alto em comparação com RGB, HSV e CIELAB, provavelmente devido à sua separação da informação de luminância e crominância e à natureza linear de sua transformação de RGB.

Glossário de Termos Chave

Algoritmo K-Means (KM): Um algoritmo de clustering particional iterativo que visa particionar um conjunto de dados em um número predefinido (K) de clusters. Ele minimiza a soma dos erros quadráticos (SSE) ao atribuir cada ponto de dados ao centro de cluster mais próximo e recalcular os centros como as médias dos pontos atribuídos.
Quantização de Cores: O processo de redução do número de cores distintas usadas em uma imagem digital, geralmente para reduzir o tamanho do arquivo ou para exibição em dispositivos com paletas de cores limitadas.
Cluster: Um conjunto de pontos de dados que são agrupados com base em sua similaridade, geralmente definida pela proximidade no espaço dos dados.
Centro do Cluster (Centroid): O ponto médio ou centro geométrico de um cluster, calculado como a média dos pontos de dados pertencentes a esse cluster.
Soma dos Erros Quadráticos (SSE): Uma métrica usada no K-Means para medir a compactação dos clusters. É a soma das distâncias euclidianas quadráticas de cada ponto de dados ao centro do seu cluster atribuído. O K-Means busca minimizar o SSE.
Algoritmo de Lloyd: Um algoritmo heurístico comum para resolver o problema de K-Means. Ele envolve iterativamente a atribuição de pontos aos centros mais próximos e o recálculo dos centros até que um critério de terminação seja atendido.
Sort-Means (SM): Uma modificação do algoritmo K-Means que visa reduzir os cálculos de distância durante a fase de atribuição, pré-calculando as distâncias entre os centros dos clusters e utilizando a desigualdade triangular.
Weighted Sort-Means (WSM): Uma versão do Sort-Means que incorpora pesos de amostra, que são frequentemente proporcionais à frequência de cada cor na imagem original.
Espaço de Cores RGB: Um espaço de cores aditivo onde as cores são representadas por uma combinação de vermelho, verde e azul. É comum para representação digital de imagens.
Espaço de Cores HSV: Um espaço de cores que separa a informação de matiz (Hue), saturação (Saturation) e valor (Value). Frequentemente usado para segmentação de cores, pois a informação de cor é separada do brilho.
Espaço de Cores YCbCr: Um espaço de cores que separa a informação de luminância (Y) e crominância (Cb e Cr). Comumente usado em sistemas de vídeo digital e compressão.
Espaço de Cores CIELAB (CIE L*a*b*): Um espaço de cores projetado para ser perceptualmente uniforme, onde a diferença numérica entre duas cores corresponde mais de perto à diferença percebida pelos humanos. L* representa a leveza, e a* e b* representam as componentes de cor.
Erro Quadrático Médio (MSE): Uma métrica para avaliar a qualidade de uma imagem quantizada, calculada como o erro médio quadrático entre a imagem original e a quantizada. Um MSE mais baixo indica menor distorção.
Relação Sinal-Ruído de Pico (PSNR): Uma métrica de avaliação que está relacionada ao MSE e é frequentemente usada para medir a qualidade da reconstrução de imagens com perdas de compressão ou quantização. Um PSNR mais alto indica melhor qualidade.
Validação de Cluster: O processo de avaliação da qualidade de uma partição de cluster, geralmente usando métricas que quantificam a compactação dentro dos clusters e a separação entre os clusters.
Dunn's Index: Um índice de validação de cluster interno que avalia a qualidade de uma partição de cluster com base na proporção da distância mínima entre clusters e a distância máxima dentro dos clusters. Um valor mais alto do Dunn's index indica melhor clustering.
Distância Intercluster: Uma medida da separação entre dois clusters.
Distância Intracluster: Uma medida da compactação ou espalhamento dos pontos dentro de um único cluster.
Modelo Potts: Um modelo para segmentação de imagem que combina um termo de fidelidade aos dados (similar ao K-Means) com uma penalidade para o perímetro das regiões segmentadas para promover a homogeneidade espacial.
Regularização TV (Variação Total): Uma técnica de regularização usada em modelos de processamento de imagem, como o modelo Potts, que penaliza a variação total da imagem para preservar as bordas e reduzir o ruído e o efeito escada.
Problema NP-difícil: Uma classe de problemas computacionais para os quais se acredita que não existe um algoritmo eficiente (polinomial no tempo) para encontrar a solução ótima em todos os casos. O problema de K-Means é NP-difícil.
Esquemas de Inicialização: Diferentes métodos para escolher os centros dos clusters iniciais para o algoritmo K-Means. Exemplos incluem seleção aleatória, LBG (Splitting), Minmax (MMX), Density-based (DEN), Maximum variance (VAR) e K-Means++ (KPP).

Fontes consultadas:

1. Improving the Performance of K-Means for Color Quantization

M. Emre Celebi Department of Computer Science

Louisiana State University, Shreveport, LA, USA ecelebi@lsus.edu

2. Color image segmentation based on a convex K-means approach Tingting Wu1, Xiaoyu Gu1, Jinbo Shao1, Ruoxuan Zhou2, Zhi Li3

3. FROM COLORS TO CLASSES: EMERGENCE OF CONCEPTS IN VISION TRANSFORMERS

Teresa Dorszewski1 tksc@dtu.dk

Lenka Tětková1

lenhy@dtu.dk Robert Jenssen2,3,4

robert.jenssen@uit.no Lars Kai Hansen1

lkai@dtu.dk

Kristoffer Knutsen Wickstrøm2

kristoffer.k.wickstrom@uit.no

4. Color Quantization of Dermoscopy Images Using the K-Means Clustering Algorithm

M. Emre Celebi, Quan Wen, Sae Hwang, and Gerald Schaefer

5. Evaluation of Colour Models for Computer

Vision using Cluster Validation Techniques

David Budden, Shannon Fenn, Alexandre Mendes and Stephan Chalup

School of Electrical Engineering and Computer Science Faculty of Engineering and Built Environment

The University of Newcastle, Callaghan, NSW, 2308, Australia. `david.budden, shannon.fenn @uon.edu.au alexandre.mendes, stephan.chalup @newcastle.edu.au`

Dominant Color Extraction with K-Means for Camera Characterization in Cultural Heritage Documentation

Adolfo Molada-Tebar, Ángel Marqués-Mateu, José Luis Lerma, and Stephen Westland.