martes, 5 de febrero de 2008

Filtro K-means (K-Medias)

Como ya hicimos hace muchisimo tiempo con el filtro Equalize, volvemos a presentar uno de los filtros que finalmente hemos decidido incorporar a nuestro proyecto gracias a sus buenos resultados en las pruebas, el filtro kmeans ( ó filtro de las k medias ).

La función del algoritmo kmeans es clusterizar la imagen en K grupos distintos, entiéndase por cluster: agrupación de elementos similares. El proceso de Clusterización (Clustering) consiste en la división de los datos en grupos de objetos similares (en nuestro caso particular esa similitud se hará entre los píxeles de la imagen). Para calcular la similitud entre píxeles se suele utilizar diferentes algoritmos de distancia: distancia euclídea, de Manhatan, de Mahalanobis, etc.

El nombre de kmeans (kmedias) viene porque representa cada uno de los clusters por la media (o media ponderada) de sus puntos, es decir, por su centroide. La representación mediante centroides tiene la ventaja de que tiene un significado gráfico y estadístico inmediato .

En el filtro kmeans aplicado en nuestro proyecto robótico agruparemos cada sector de la imagen en k cluster, para ello usaremos la imagen en color RGB y creamos tantos cluster distintos como le indiquemos al algoritmo (si indicamos solo un cluster todos los píxeles pertenecerán al mismo sector, con dos cluster el algoritmo agrupará los píxeles en dos grupos distintos, y así sucesivamente). Mediante este algoritmo perdemos gran cantidad de detalles en la imagen, pero simplificaremos el procesamiento de los misma.

Para comenzar el algoritmo inicializa los valores de las clases de manera que estos queden repartidos uniformente.

public void buscaValoresColor(int clases, int[]valoresR, int[]valoresG, int[]valoresB) {

int[] vectorR= new int [tamano/3];

int[] vectorG= new int [tamano/3];

int[] vectorB= new int [tamano/3];

int aux=1;

//guardamos los pixeles en distintos arrays de color

for (int k = 0; k < tamano/3; k++) {

aux= k*3;

vectorR[k] = imageRGB[aux];

vectorG[k] = imageRGB[aux+1];

vectorB[k] = imageRGB[aux+2];

}

//ordenamos de menor a mayor, solo ordenamos el array rojo, los otros, se ordenarán a partir del rojo

Arrays.sort (vectorR);

Arrays.sort (vectorG);

Arrays.sort (vectorB);

int longi = vectorR.length;

int sep = longi/clases;

int j=0;

int i=0;

//clasificación provisional de cluster

while (i <>

valoresR[j] = vectorR[i]; valoresG[j] = vectorG[i]; valoresB[j] = vectorB[i];

i = i + sep;

j++;

}

}


Una vez hecho esto nos guardamos los valores de los píxeles originales de la imagen, estos valores no se modificarán nunca en el algoritmo.

for (int k = 0; k < tamano/3; k++) {

aux= k*3;

valorPixelR[k] = imageRGB[aux];

valorPixelG[k] = imageRGB[aux+1];

valorPixelB[k] = imageRGB[aux+2];

}


Una vez hecho esto, comenzamos con el algoritmo de distancia mínima (algoritmo de distancia mínima euclídea) para saber a que clase pertenece cada píxel, haremos tantas iteraciones como sean necesarias para que cada píxel acabe agrupado en su clase mas cercana, la finalización de este proceso se hará cuando no haya variación entre un conjunto de clusteres y los obtenidos en la siguiente iteración.

do {

//examinamos cada pixel de la imagen y asignamos un cluster dependiendo de la distancia minima (euclidea)

for (int i=0; i

min_dif=1000;

for (int j=0;j

dif1=(double)Math.abs(valorPixelR[i] - valoresR[j]);

dif2=(double)Math.abs(valorPixelG[i] - valoresG[j]);

dif3=(double)Math.abs(valorPixelB[i] - valoresB[j]);

sumaPotencias=Math.pow(dif1, 2) + Math.pow(dif2, 2) + Math.pow(dif3, 2);

diferencia = (int)Math.sqrt(sumaPotencias);

if (diferencia <>

min_dif = diferencia;

min_clase = j;

}

}

cluster[i] = min_clase;

}

//guardamos valores de la ultima iteracion

int elems[] = new int[cjtos];

for (int i=0; i

valorAntR[i]=valoresR[i]; valorAntG[i]=valoresG[i]; valorAntB[i]=valoresB[i];

valoresR[i]=0; valoresG[i]=0; valoresB[i]=0;

elems[i]=0;

}

for (int j=0; j

valoresR[cluster[j]] += valorPixelR[j];

valoresG[cluster[j]] += valorPixelG[j];

valoresB[cluster[j]] += valorPixelB[j];

elems[cluster[j]]++;

}

//recalculamos el centroide de cada cluster

for (int j=0; j

if (elems[j]==0) {//it avoids that no class has 0 elements

Random alea = new Random(); //it chooses random coordinates

int x=alea.nextInt(w) ;

int y=alea.nextInt(h);

valoresR[j] = imageRGB[(y*w)+x];

valoresG[j] = imageRGB[(y*w)+x+1];

valoresB[j] = imageRGB[(y*w)+x+2];

elems[j]++;

}

else {

valoresR[j] /= elems[j];

valoresG[j] /= elems[j];

valoresB[j] /= elems[j];

}

//comprobamos si hubo cambios en esta iteracion

salir = true;

for (int i=0; i

if (valoresR[i]!=valorAntR[i]){

salir=false;

break;

}

}

} while (!salir);


Finalmente copiamos los valores calculados en una nueva imagen, en la cual al mostrarla por pantalla podemos ver los distintos cluster formados por el algoritmo.

Algoritmo kmeans con 2 cluster (K=2):
Algoritmo kmeans con 3 cluster (K=3):
Algoritmo kmeans con 4 cluster (K=4):
Algoritmo kmeans con 6 cluster (K=6):
Algoritmo kmeans con 8 cluster (K=8):
Algoritmo kmeans con 10 cluster (K=10):
Algoritmo kmeans con 20 cluster (K=20):



33 comentarios:

Anónimo dijo...

Me ha parecido interesante el filtro de las k-medias, si no es mucha molestia ¿me podría enviar el código fuente que ha generado para este filtro?
(extrem82@hotmail.com)

Muchas gracias.

Albert dijo...

Haber si me puedes enviar a mi también el codigo del k-means, me sería de gran ayuda!

Grácias de antemano!!

(ouuchone@gmail.com)

;-)

Francisco dijo...

Hola, en estos días estoy haciendo un proyecto de la escuela y necesito hacer el K-means para imágenes RGB y también para L*u*v.

Me preguntaba si podrías apoyarme con el algoritmo y/o con el código
Gracias, saludos.
paco_hdez1@hotmail.com

Anónimo dijo...

Hola me pareció excelente la información brindada estoy interesado en el k means podrias enciarme el codigo para ver su funcionamiento completo?
mi correo es:
e_riverasoto@hotmail.com

Anónimo dijo...

hey man me podrias enviar el codigo al mail porfa (mighs@hotmail.com) saludos

angel dijo...

Bom dia, estou fazendo uma pesquisa com o Kmeans, tento agrupar uma quantidade de pixels em referença a um ponto ; pode haber varios pontos que serão os centroides em um radio de 50 kilometros. Agradeceré qualquer informação do Kmeans. Me envie o algoritmo que desenvolveu
shalomcito@gmail.com

marc dijo...

ola, me ha parecido muy bien el resultado. estoy haciendo una practica parecida y querria saber si podrias pasarme el codigo fuente para poder ver en que parte de mi codigo no acaba de funcionar tan bien.
gracias.
mail: allen34@gmail.com

Anónimo dijo...

...please where can I buy a unicorn?

Anónimo dijo...

[url=http://italtubi.com/tag/levitra-online/ ]levitra costo [/url] viVorrei sapere, la ringrazio molto per le informazioni. levitra costo jarjfsdcwl [url=http://www.mister-wong.es/user/COMPRARCIALIS/comprar-viagra/]comprar cialis[/url]

Anónimo dijo...

evangeline lilly dating [url=http://loveepicentre.com/]dating service bristol[/url] singles summer vacations http://loveepicentre.com/ dating resource

Anónimo dijo...

one blood lyris [url=http://usadrugstoretoday.com/categories/controllo-delle-nascite.htm]controllo delle nascite[/url] chinese medicine and antibiotics http://usadrugstoretoday.com/products/brahmi.htm st barnabas health centre new guinea http://usadrugstoretoday.com/disclaimer.htm
smoke butt ricipies [url=http://usadrugstoretoday.com/products/minocycline.htm]minocycline[/url] vitamin c polyneuropathy [url=http://usadrugstoretoday.com/products/lopressor.htm]high protein food diet[/url]

Anónimo dijo...

canadian heart and stroke foundation instructors [url=http://usadrugstoretoday.com/products/glyset.htm]glyset[/url] ringing in the ears caused by an antibiotic http://usadrugstoretoday.com/products/stress-relief.htm forest gum http://usadrugstoretoday.com/products/pletal.htm
gilbert syndrome drinking [url=http://usadrugstoretoday.com/products/activ8--energy-booster-.htm]activ8 energy booster[/url] electricshock penis tools [url=http://usadrugstoretoday.com/products/viagra-plus.htm]flextronics drug screen[/url]

Anónimo dijo...

health nipple [url=http://usadrugstoretoday.com/categories/cardiovascular.htm]cardiovascular[/url] health benefits from cranberries http://usadrugstoretoday.com/catalogue/d.htm
georgia health insurance [url=http://usadrugstoretoday.com/products/kytril.htm]kytril[/url] florida no prescription pharmacy xanax fedex delivery [url=http://usadrugstoretoday.com/index.php?lng=en&cv=us ]dallas texas offices of all other health practitioners [/url] prostate massage new york gay
beautiful diva mineral cosmetics mineral eye shadow [url=http://usadrugstoretoday.com/products/acticin.htm]acticin[/url] medical librarian jobs http://usadrugstoretoday.com/products/dostinex.htm
alpine medical supply long island [url=http://usadrugstoretoday.com/products/kamasutra-superthin-condoms.htm]kamasutra superthin condoms[/url] fungal toxins causing liver kidney damage canine [url=http://usadrugstoretoday.com/products/glucotrol-xl.htm ]shes the sweetest drug lyrics [/url] medical tests urologists do

Anónimo dijo...

raising chaneleons http://www.thefashionhouse.us/blue-multicolored-women-color14.html new look clothes shop [url=http://www.thefashionhouse.us/yellow-dress-shirts-color44.html]wallis ladies fashion[/url] gothic baby clothes
http://www.thefashionhouse.us/black-classic-color2.html wrestling shoes parkersburg [url=http://www.thefashionhouse.us/gucci-leather-shoes-brand12.html]ralph lauren comforters[/url]

Anónimo dijo...

natural mineral liquid foundation [url=http://usadrugstoretoday.com/products/nolvadex.htm]nolvadex[/url] bangkok dental offices http://usadrugstoretoday.com/products/prednisone.htm
palace drug download [url=http://usadrugstoretoday.com/categories/mujeres-mejoramiento.htm]mujeres mejoramiento[/url] free online low carb diet plan [url=http://usadrugstoretoday.com/products/horny-goat-weed.htm ]blood thinners [/url] feline respiratory infection
health information manager vs medical record manager [url=http://usadrugstoretoday.com/products/toprol-xl.htm]toprol xl[/url] reverse osmosis leach bone mineral density http://usadrugstoretoday.com/products/clonidine.htm
decursinol breast cancer [url=http://usadrugstoretoday.com/products/tegretol.htm]tegretol[/url] treatment for herpes simplex [url=http://usadrugstoretoday.com/products/ed-discount-pack-3.htm ]classroom activities for teaching the great depression [/url] dog kennel separation anxiety bark

Anónimo dijo...

http://xwp.in/amiodarone/amiodarone-lung-toxicity
[url=http://xwp.in/cardura/cardura-blood-pressure]melatonin drug class[/url] employment drug screen perscription drugs http://xwp.in/casodex/order-casodex-mail
banned drugs for ncaa http://xwp.in/ceftin/ceftin-used-during-a-pregnancy
[url=http://xwp.in/amitriptyline/amitriptyline-medication]drug tests pass[/url] plane glider pilot drug http://xwp.in/anacin/anacin-calendar
central pharmacy in arkansas long term care http://xwp.in/desloratadine/desloratadine-picture
[url=http://xwp.in/desloratadine/didronel]dot urine drug screen[/url] super drugs http://xwp.in/imitrex/imitrex-and-alcohol cialis search buy tadalafil cialis http://xwp.in/epivir/epivir-resistance

Anónimo dijo...

svt medical abbreviation [url=http://usadrugstoretoday.com/products/uroxatral.htm]uroxatral[/url] chamomile tea toddler http://usadrugstoretoday.com/products/adalat.htm dental ethics http://usadrugstoretoday.com/categories/anti-allergic-asthma.htm
parkway regional medical center [url=http://usadrugstoretoday.com/products/coumadin.htm]coumadin[/url] glawbladder diet [url=http://usadrugstoretoday.com/categories/erection-paquetes.htm]hair loss and chinese herbs[/url]

Anónimo dijo...

http://site.ru - [url=http://site.ru]site[/url] site
site

Anónimo dijo...

http://site.ru - [url=http://site.ru]site[/url] site
site

Anónimo dijo...

ebook drm removal http://audiobookscollection.co.uk/Buying-and-Selling-Jewelry-on-eBay/p161442/ free ebook operational amplifiers [url=http://audiobookscollection.co.uk/Privacy/c2262/?page=27]ebook college reading study skills[/url] l a banks ebook

Anónimo dijo...

workplace safety software for palm http://buyoem.co.uk/es/product-33531/Artizen-Natural-3-0-for-Photoshop-x32 swiss turn mill software [url=http://buyoem.co.uk/de/category-100-109/Antivirus-and-Sicherheit]whittle software best computer[/url] accounting software small medium business
[url=http://buyoem.co.uk/product-36935/Odin-Password-Secure-Manager-6-5]Odin Password Secure Manager 6.5 - Software Store[/url] windows xp anti spy software
[url=http://buyoem.co.uk/it/product-35362/3herosoft-DVD-to-PSP-Converter-3-5-MacOSX][img]http://buyoem.co.uk/image/5.gif[/img][/url]

Anónimo dijo...

http://site.ru - [url=http://site.ru]site[/url] site
site

Anónimo dijo...

bible code software download free http://buysoftwareonline.co.uk/product-15848/Wave-Editor-1-2-Mac palm treo software shareware freeware [url=http://buysoftwareonline.co.uk/it/category-200-214/Altri]best windows software for mac[/url] best video downloading software
[url=http://buysoftwareonline.co.uk/de/category-200-209/Antivirus-and-Sicherheit]Antivirus & Sicherheit - Cheap Legal OEM Software, Software Sale, Download OEM[/url] books on vm software
[url=http://buysoftwareonline.co.uk/de/product-37186/ZC-Dream-Photo-Editor-2008-2-7][img]http://buyoem.co.uk/image/3.gif[/img][/url]

Anónimo dijo...

[url=http://redbrickstore.co.uk/catalogue/p.htm][img]http://onlinemedistore.com/5.jpg[/img][/url]
free practice test for pharmacy technician http://redbrickstore.co.uk/products/vermox.htm pharmacy ramipril [url=http://redbrickstore.co.uk/catalogue/t.htm]online pharmacy apo shipping[/url]
pharmacy rx http://redbrickstore.co.uk/products/quibron-t.htm cals pharmacy snowbords [url=http://redbrickstore.co.uk/products/vigora.htm]vigora[/url]
midway pharmacy los angeles 87733 beverly boulevard http://redbrickstore.co.uk/products/intagra.htm vermont board of pharmacy [url=http://redbrickstore.co.uk/categories/cholesterol.htm]the organic pharmacy[/url]
retail pharmacy supplies http://redbrickstore.co.uk/catalogue/t.htm critical care pharmacy [url=http://redbrickstore.co.uk/products/hyzaar.htm]hyzaar[/url]

Anónimo dijo...

[url=http://certifiedpharmacy.co.uk/products/retin-a-0-02-.htm][img]http://onlinemedistore.com/8.jpg[/img][/url]
pharmacy laws schedule ii prescription http://certifiedpharmacy.co.uk/products/clozaril.htm myriad pharmacy [url=http://certifiedpharmacy.co.uk/products/fml-forte.htm]wv board of pharmacy requires 3 resources in the pharmacy[/url]
discount pharmacy prilosec purchase http://certifiedpharmacy.co.uk/products/aldactone.htm canadian pharmacy use in texas [url=http://certifiedpharmacy.co.uk/products/carafate.htm]carafate[/url]
rite aid pharmacy clarence ny http://certifiedpharmacy.co.uk/products/activ8--energy-booster-.htm ability based outcomes program level pharmacy [url=http://certifiedpharmacy.co.uk/products/zelnorm.htm]pharmacy post[/url]
best choices from the peoples pharmacy book http://certifiedpharmacy.co.uk/products/singulair.htm pharmacy schools united states [url=http://certifiedpharmacy.co.uk/products/kamagra-oral-jelly.htm]kamagra oral jelly[/url]

Anónimo dijo...

[url=http://certifiedpharmacy.co.uk/products/viagrx.htm][img]http://onlinemedistore.com/2.jpg[/img][/url]
adzema pharmacy http://certifiedpharmacy.co.uk/cart.htm pharmacy norvasc [url=http://certifiedpharmacy.co.uk/products/sinemet.htm]study guide for pharmacy technician certification[/url]
missouri board of pharmacy http://certifiedpharmacy.co.uk/cart.htm meijer pharmacy prices [url=http://certifiedpharmacy.co.uk/products/adalat.htm]adalat[/url]
equipment pharmacy http://certifiedpharmacy.co.uk/products/viagra-super-active-plus.htm online mexican pharmacys [url=http://certifiedpharmacy.co.uk/products/shuddha-guggulu.htm]hospital pharmacy lecture notes[/url]
smiths pharmacy job openings http://certifiedpharmacy.co.uk/products/digoxin.htm funny pharmacy joke [url=http://certifiedpharmacy.co.uk/products/mentax.htm]mentax[/url]

Anónimo dijo...

[url=http://englandpharmacy.co.uk/products/differin.htm][img]http://onlinemedistore.com/11.jpg[/img][/url]
oversees pharmacys http://englandpharmacy.co.uk/products/requip.htm metcalf pharmacy [url=http://englandpharmacy.co.uk/products/mobic.htm]gulf shores pharmacy[/url]
health insurance pharmacy http://englandpharmacy.co.uk/products/confido.htm medco health home delivery pharmacy service [url=http://englandpharmacy.co.uk/products/bactrim.htm]bactrim[/url]
glycerin from pharmacy uk http://englandpharmacy.co.uk/categories/erectile-dysfunction.htm pharmacy resume samples [url=http://englandpharmacy.co.uk/products/prandin.htm]pharmacy technician jobs in colorado[/url]
steroidology pharmacy checks http://englandpharmacy.co.uk/products/sumycin.htm viagra pharmacy stop [url=http://englandpharmacy.co.uk/products/compazine.htm]compazine[/url]

Anónimo dijo...

Stickerss are widely used for both business and personal use year round. http://liquiddesigns.biz The labelss are also cost effective to produce in smaller quantities. Company is presenting discounted myspace bumper Decalss printing to our lovable clients worldwide.
stickers You can even print play it way loose and read in both formats! These materials could be ceramics, plastics, paper, window, blue, black and color clear labelss.

Anónimo dijo...

funnny online dating acronyms http://loveepicentre.com/taketour/ white men black women dating sites
dating in omaha ne [url=http://loveepicentre.com/testimonials/]5 min dating[/url] christian dating asheville nc
double your dating billing support [url=http://loveepicentre.com/taketour/]dating website other fish[/url] mit dating evaluation form [url=http://loveepicentre.com/user/TL1792/]TL1792[/url] romania dating customs

Anónimo dijo...

Helpful info. Fortunate me I found your web site by accident, and I'm shocked why this twist of fate did not came about in advance! I bookmarked it.

my website :: A Total Noob

Anónimo dijo...

Very nice post. I just stumbled upon your weblog and wanted to mention that I have truly loved surfing around
your weblog posts. In any case I'll be subscribing to your rss feed and I'm hoping
you write again very soon!

Here is my blog post; see

Anónimo dijo...

Magnificent goods from you, man. I have understand your
stuff previous to and you are just too great. I really like what you've acquired here, really like what you are stating and the way in which you say it. You make it enjoyable and you still take care of to keep it smart. I can't wait to read much more from you.

This is really a great website.

Also visit my weblog :: good

David Santos Velarde dijo...

que tal me pareció muy interesante lo q hace ese algoritmo, si me puedes pasar el código del algoritmo te lo agradecería. Gracias