Quantização de Imagens, utilizando algoritmo K-means
02/12/2013 00:00
Autores: Renzo Magno e Felipe Miertschink
Professor: Tiago Paixão
Ciência da Computação - UFES 2013/2
Importância: O procedimento de quantização é utilizado em diversas aéreas. Desde a física moderna até a medicina. Procedimentos médicos, como exames oftamológicos a utilizam em grande escala para o tratamento de imagens da retina, córnea etc. Na física, por exemplo, um elétron ao orbitar um núcleo de hidrogênio assume a energia de -13,6eV, mas ao ser aquecido, este elétron poderá se elevar ao nível seguinte (-3,4eV, no entanto não poderá assumir valores intermediarios, nesse caso é dito que a energia esta quantizada.
Em computação sua importância e utilização é dissertada em inúmeros artigos e pesquisas. De fato, é através de algoritmos de quantização que muitos tratamentos a imagems são gerados. Este algoritmo apresentado, além de utilizar técnicas de quantização, explora o desempenho do algoritmo k-means como seletor de cores, de forma a otimizar a compressão de dados.
Código fonte:
# By : Felipe Mierstchink, Renzo Magno
# bibliotecas utilizadas:
import numpy as np
import scipy as sp
import pylab as pl
from sklearn import cluster
# n_clusters = número de clusters para a divisão da imagem no K_means = número de cores para a quantização da imagem
n_clusters = 8
np.random.seed(0)
#tenta achar lena na lib
try:
lena = sp.lena()
except AttributeError:
from scipy import misc
lena = misc.lena()
x, y = lena.shape # pega o tamanho da lena
X = lena.reshape((-1, 1)) # array(n_sample, n_feature)
k_means = cluster.KMeans( n_clusters, n_init = 4) #inicia k_means com n_cluster divisões
k_means.fit(X)
values = k_means.cluster_centers_.squeeze()
labels = k_means.labels_
print 'cores da lena quantizada:'
print values
print ' '
# cordenadas minimas e maximas da lena
vmin = lena.min()
vmax = lena.max()
# apos quantização com k_means cria 3 figuras
# figura 1: lena normal
pl.figure(1, figsize=(5, 4))
pl.imshow(lena, cmap=pl.cm.gray, vmin=vmin, vmax=256)
# figura 2: quantiza lena (com 'n_clusters' cores que são: as 'values' cores)
regular_lena = np.choose(labels.ravel(), values)
regular_lena.shape = lena.shape
pl.figure(2, figsize=(5, 4))
pl.imshow(regular_lena, cmap=pl.cm.gray, vmin=vmin, vmax=vmax)
# figura 3: plota histograma (cinza = figura 1, linhas azuis = cores da figura 2)
pl.figure(3, figsize=(5, 4))
pl.clf()
pl.axes([.01, .01, .98, .98])
pl.hist(X, bins=256, color='.5', edgecolor='.5') #histograma figura 1
pl.yticks(())
pl.xticks(values)
values = np.sort(values)
for x in range(n_clusters): #plota as linhas das cores da figura 2 em azul
pl.axvline(values[x])
# função quadratica
soma = 0
for i in range(lena.shape[0]):
for j in range(lena.shape[1]):
soma += int((lena[i][j] - regular_lena[i][j])**2)
m = (1./(lena.shape[0]*lena.shape[1]))*soma
print ('mse: ')
print m
pl.show()
Resultados:
Quantização com 2 cores
Quantização com 4 cores
Quantização com 8 cores
Quantização com 16 cores
Quantização com 30 cores (limite de 32 choices da biblioteca numpy em np.choose do python 2.6 para windows)
MSE:
Fórmula:
| Colors | MSE |
| 2 | 688,418 |
| 4 | 161,596 |
| 8 | 40,562 |
| 16 | 11,003 |
| 30 | 2,914 |
Conclusão:
O algoritmo que é baseado no k_means se utiliza da biblioteca numpy para fazer a clusterização da imagem e divisão das cores. Porém, infelizmente não está trabalhando com mais de 32 cores. Devido a limitação ocasionada por um bug da versão mais nova do numpy (https://stackoverflow.com/questions/11570157/numpy-choose-32-choice-limitation) . Em breve estaremos corrigindo em uma versão mais antiga desta biblioteca, o que exigirá a implementação no SO Linux (antigas versões da numpy so foram achadas funcionando corretamente para linux). Apesar da limitação, o algoritmo se mostrou rápido em relação a outros códigos e pode ser mellhorado muito mais.
Referêcias:
https://algolist.manual.ru/graphics/quant/qoverview.php
https://mail.scipy.org/pipermail/numpy-discussion/2011-June/056867.html
https://docs.scipy.org/doc/numpy/reference/generated/numpy.choose.html
https://weblog.benjaminsommer.com/blog/2012/05/25/histogram-equalization/
Descritor de bordas e quantização espacial flexível aplicados a categorização de objetos - Câmara Arnaldo