Entrades amb l'etiqueta ‘algorismes eficients’

Les telereunions i els càlculs intel·ligents

dijous, 19/12/2013

TelepresenceFuchs.jpg Els telèfons, cada pocs anys ens donen una sorpresa. Fa trenta anys teníem telèfons fixos, a casa i a la feina. Desprès van venir els telèfons sense fil, els mòbils, els mòbils amb internet, els missatges gratuïts, i la possibilitat de parlar veient-se les cares amb sistemes com skype o hangouts. I ara, què? Què ens estan preparant, ara que ja estem curats d’espants?

El que ens arribarà d’aquí a uns anys (no molts) és la telepresència, les telereunions i les tele-trobades. La imatge que teniu aquí al costat és d’aquest vídeo, i mostra els primers resultats del projecte “BeingThere que estan desenvolupant investigadors de les Universitats de Carolina del Nord als USA i de la ETH de Zurich. La idea és ben simple. A casa o a la feina, tenim un parell o tres de televisors a la paret. Els televisors mostren una imatge en temps real dels nostres interlocutors i es converteixen en una finestra a una habitació virtual que ens sembla que és just a l’altra banda de la paret però que en realitat pot ser a molts quilometres de distància. Els altres veuen el mateix, em veuen a mi i el meu entorn per una finestra. Ens podria semblar que és com un “skype gegant“, però hi ha dues diferències fonamentals. La primera és que l’altra habitació no la veiem com una projecció en les pantalles de televisió, sinó que la veiem en profunditat. La pantalla desapareix, es converteix en una finestra i passem a veure el de l’altra banda, amb alguns objectes més a prop nostre i d’altres més llunyans. La segona és que ho veiem tot des de la nostra perspectiva. Si us fixeu en el vídeo de la imatge de de dalt, veureu que quan ens movem, anem veient l’habitació “del costat” des de diferents angles. Realment estem mirant els nostres amics per una finestra. Aquesta és la diferència essencial entre els sistemes actuals, tipus skype o hangouts, i els nous sistemes de telepresència. Mentre que, en skype, qui controla el que podem veure és el nostre interlocutor, en els sistemes de telepresència som nosaltres. L’inconvenient és que haurem d’anar més o menys presentables i que segurament haurem d’haver endreçat una mica l’habitació, perquè no podrem ajustar el que l’altre podrà veure, com fem ara. L’avantatge és que la sensació de proximitat i de connexió en aquestes tele-trobades serà molt més gran. I això ben segur que ho agrairem quan tinguem ganes de parlar i “estar” amb amics, fills i néts que siguin lluny. En el món professional, l’objectiu és el d’estalviar viatges i poder fer telereunions, reunions a distància que avui en dia encara són poc presencials, massa fredes i força esgotadores.

Què cal, per a poder fer telereunions? Cóm ho estan fent, els del projecte “BeingThere“? La part de poder veure en profunditat és la més fàcil. Podem utilitzar televisions 3d amb olleres de polarització o bé pantalles auto-estereoscòpiques que produeixen sensació de volum i profunditat sense necessitar olleres. Avui en dia encara tenen poca qualitat, però ben segur que d’aquí a pocs anys seran ja utilitzables. En canvi, el veritable problema és aconseguir veure l’altra habitació sempre des de la nostra perspectiva, quan ens anem movent. És un problema perquè no ho podem resoldre amb càmeres digitals convencionals. Cada càmera captura l’escena des d’una determinada perspectiva, i el més probable és que el nostre punt de vista no coincideixi amb el de cap de les càmeres que haurem repartit per l’habitació. Necessitaríem moltíssimes càmeres, hauríem d’enviar volums ingents d’informació per la xarxa, i així i tot tindríem salts quan canviéssim de càmera. Les càmeres no ens serveixen perquè hem de poder capturar en temps real tot el que passa en una habitació, fer-ho de manera compacta per a poder transmetre bé la informació a distància i aconseguir reconstruir, també en temps real, el que veuríem des de qualsevol punt de vista. El que necessitem és el veritable concepte de televisió tridimensional, amb càmeres de gravació que desconeixen els punts de vista i les perspectives que voldrà escollir el televident, de manera que aquest podrà inspeccionar l’entorn llunyà amb total llibertat i sense restriccions. És un bon problema d’enginyeria, oi?

El primer ingredient de la solució consisteix en tenir un model de l’altra habitació i de cada una de les persones que s’hi troben. No és cap idea estranya, perquè és el que fem tots cada dia. Tenim i utilitzem models mentals dels llocs que coneixem i dels nostres amics i companys. Quan som a la feina, recordem la cuina de casa i sabem on és la nevera i en quin calaix guardem les cassoles. I quan veiem un amic, el reconeixem i sabem que té una piga sota al costat dret del coll encara que només estiguem veient el seu perfil esquerre. Podem entendre l’espai i imaginar noves perspectives gràcies als nostres models mentals, i podem saber si coneixem una persona que trobem pel carrer perquè també tenim models mentals de tots els nostres familiars i amics. En els sistemes de telepresència no hem fet altra cosa que adaptar i traduir aquest recurs, utilitzant evidentment models digitals en comptes de models mentals. El sistema que gestionarà les telereunions disposarà de models digitals de l’entorn i de cada una de les persones que s’hi mouen, i també haurà de saber adaptar-se. De la mateixa manera que els nostres models mentals van evolucionant, els models digitals s’aniran ajustant al moviment de les persones. Recordem on hem deixat les claus avui, però no és clar que recordem on les vam deixar fa sis dies. Recordem cóm anava vestit l’amic amb qui acabem de parlar, però els records de la setmana passada es difuminen, i no ens és pas fàcil detectar si una persona que veiem cada dia s’està aprimant perquè els canvis quotidians són subtils. Els models mentals que elabora el nostre cervell es refinen i reforcen constantment amb la informació perceptual que arriba dels sentits.

Els sistemes de telepresència del projecte “BeingThere” construeixen els models digitals de l’entorn i de les persones a partir d’un cert nombre de càmeres de profunditat (vegeu la nota al final). Aquestes càmeres, 10 en total i fixades a les parets, són els ulls del sistema, els sensors que 30 vegades per segon detecten el que està passant. Un seguit d’algorismes que comentarem tot seguit, generen models digitals de l’entorn (habitació i mobiliari) i de les persones. A partir d’aquí tot ja és més fàcil, perquè l’únic que cal és enviar aquests models 3D per internet a l’altre interlocutor, i visualitzar-los a les pantalles de televisió que tenim a la pared. Tot plegat acaba essent realista i plausible perquè els models que enviem són còpies digitals i tridimensionals (amb geometria i color) del que les càmeres de profunditat han captat pocs mili-segons abans, i aquestes còpies o models digitals els podem veure des de qualsevol perspectiva. No enviem imatges, sinó veritables escultures digitals, maniquins que reprodueixen els moviments de les persones i que van vestits com elles. És com l’estàtua del David d’aquest vídeo. És un model digital. Per poder mirar-la des de qualsevol punt de vista, no n’hi ha prou amb fotografies. Cal un model digital 3D com el del David, que coneix les coordenades (x,y,z) de tots els punts de la seva superfície.

Aconseguir el model digital de l’entorn no és massa difícil, perquè és bàsicament estàtic. El que és realment complicat és generar i enviar el model digital de totes i cada una de les persones que s’hi troben. Cal captar el que “veuen” les deu càmeres de profunditat, generar maniquins digitals que evolucionen en el temps, enviar la informació per internet al lloc de destí, i tot plegat hem de fer-ho 30 vegades per segon. Per acabar-ho d’adobar, la informació que capten les deu càmeres és incompleta i aproximada. Encara que tinguem uns quants punts de vista, hi ha zones que no veu cap de les càmeres i sempre hi ha racons complexos que no es veuen bé i donen errors. Ho podeu veure en aquest vídeo, que mostra, en diverses escenes i a l’esquerra, el que podem inferir del que ens arriba de les càmeres. A la dreta, en canvi, podem veure el model o maniquí digital que l’algorisme acaba generant i enviant (si voleu podeu escoltar la banda sonora, però es pot obviar perquè és bastant tècnica).

Cóm podem generar aquests maniquins digitals que evolucionen en el temps? Hi ha molta gent que, en aquest problema i en d’altres de semblants, planteja solucions basades en mètodes d’optimització, lents, complexes i que no donen la interactivitat que necessitem en les telereunions i tele-trobades. El temps ens mata. No sabem cóm resoldre problemes tan difícils en menys d’un trentè de segon. I no podem tardar més temps si volem veure la gent de l’altra habitació movent-se suaument. La solució de Henry Fuchs i el seu equip en el marc del projecte “BeingThere“, és en canvi imaginativa i intel·ligent perquè donen la volta al problema. Fuchs diu que haver de calcular-ho tot en tan poc temps no és un inconvenient, sinó una avantatge perquè el maniquí digital que volem trobar serà quasi idèntic al que ja havíem calculat fa un trentè de segon. No es tracta de generar un nou model tridimensional, sinó només d’adaptar lleugerament el que ja teníem, en base al que ara ens estan dient les càmeres. Els càlculs poden ser senzills perquè l’adaptació que hem de fer del model és molt petita. L’algorisme recorda i utilitza la posició de fa un instant, de manera força semblant al que fa el nostre cervell quan observem els altres que es mouen. Gràcies a aquesta idea, en el projecte “BeingThere” poden construir els models digitals dinàmics de les persones en temps real i en ordinadors de sobretaula. Els càlculs intel·ligents dels seus algorismes aprofiten com una avantatge el que fins ara pensàvem que era un inconvenient.

Les telereunions i les tele-trobades són eines que aviat tindrem al nostre abast. Podem parlar i discutir sobre si ens interessen o no, però el cert és que és ben segur que ens arribaran i que les acabarem utilitzant, com ha acabat passant amb tot. Tindrem tot un ventall de possibilitats per a comunicar-nos, des dels telèfons per a parlar i enviar “whattsapps” fins “l’skype” i els sistemes de telepresència. Caldrà utilitzar-les adequadament, com totes les eines. Els missatges de text són i seran convenients quan volem dir quelcom curt sense interrompre l’altre, mentre que els sistemes com l’skype ens serviran per parlar i en certa manera “estar” amb els amics i familiars que són lluny. Els sistemes de telepresència ens ajudaran a copsar molt més la situació dels altres, el seu estat i el seu entorn perquè la nostra presència en el seu entorn 3D és ben segur que facilitarà la connexió emocional i l’empatia. Però, de la mateixa manera que no se’ns acudirà trucar per skype a un familiar per dir-li que estem arribant i que no tardarem gaire, tampoc farem una trobada amb telepresència per decidir si anem al teatre. I en tot cas, hem de confiar que els joves de les properes generacions també continuaran trobant-se a les terrasses per a prendre un cafè, gaudint de la companyia i badant i deixant passar el temps sense mirar els mòbils.

Per cert, l’Ada Colau diu que la llei sobreprotegeix els bancs i que és obligació moral desobeir les lleis injustes. Diu que per damunt la llei, hi ha els drets humans.

NOTA: Una càmera de profunditat és una càmera digital que obté imatges RGBZ. En d’altres paraules, cada píxel té informació del seu color (amb les seves tres components RGB de vermell, verd i blau) i de la distància Z entre l’objecte que estem capturant i la pròpia càmera. La distància Z es mesura habitualment en la direcció de l’eix central de visió de la càmera. Una de les opcions comercials més esteses actualment és la dels dispositius kinect, força coneguts en l’entorn dels jocs però que tenen una bona comunitat d’usuaris i desenvolupadors de software i aplicacions d’ús lliure. Els dispositius kinect contenen una càmera digital que fa les fotos RGB, junt amb una segona càmera d’infrarojos que captura els patrons de punts que va projectant el projector també d’infrarojos que inclou el dispositiu. La distància Z als objectes de l’escena es calcula per triangulació a partir dels angles de projecció i de visió/captura de cada un dels punts del patró. La càmera kinect captura 30 imatges RGBZ per segon amb una resolució de 640 per 480 pixels per als objectes que es troben a una distància d’entre 80 cm. i 3,5 metres del dispositiu. El seu preu és de l’ordre del d’una càmera digital convencional.

Els algorismes mandrosos

dimecres, 14/08/2013

GoogleMaps.jpg Hi ha moltes maneres de resoldre problemes. Pensem per exemple en l’alimentació, un dels problemes bàsics dels éssers vius. Hi ha animals que ataquen i salten sobre les seves preses, mentre que alguns insectes com les formigues van recollint constantment el que troben. Els uns han d’esmerçar molta energia mentre que els altres són lents i segurs. Finalment és clar que tots se’n acaben sortint, perquè el què observem és que les espècies no s’han extingit. Però les seves estratègies són ben diferents, oi?

Pensem ara en un problema d’aritmètica. Suposem que volem calcular la suma de tots els nombres entre l’1 i el 2000. Si ho fem de la manera més directa, amb el “conte de la vella”, anirem sumant un a un els nombres i al cap d’una estona veurem que el resultat és 2.001.000, si no ens hem equivocat. Però hi ha maneres molt més eficients, per a resoldre aquest problema. Coneixeu l’anècdota de Carl Friedrich Gauss? Quan Gauss tenia set anys i era a l’escola, el mestre els va posar un problema semblant (però sumant només tots els nombres entre l’1 i el 100) per tal de tenir-los entretinguts una estona. Els seus companys van començar a fer sumes, però Gauss, al cap de pocs segons, va dir que ja ho tenia. Havia trobat el resultat correcte: 5050. Gauss només va haver de pensar una mica per a trobar un bon algorisme, una estratègia sàvia i intel·ligent. De fet, aquest dia a l’escola, als set anys, Gauss va descobrir l’algorisme òptim per a sumar progressions aritmètiques. La seva idea va ser senzilla i elegant. Mentalment, va agrupar els nombres en parelles. En el nostre cas, agruparíem l’1 amb el 2000, el 2 amb el 1999, el 3 amb el 1998, i així successivament. La clau de tot plegat és que totes les parelles sumen el mateix: 1+2000=2001, 2+1999=2001, 3+1998=2001 etc. Només cal fer una suma, la de l’1 amb el 2000, i veure que tenim 1000 parelles. Multipliquem 2001 per 1000 i ja tenim el resultat, que fins i tot podem calcular mentalment (en el cas dels 100 primers nombres, tindríem 50 parelles i cada parella sumaria 101).

Podem sumar tots els nombres entre l’1 i el 2000 fent dues mil sumes, però podem obtenir el mateix resultat fent només una suma i una multiplicació. També podem utilitzar un ordinador, per a que sigui ell qui faci les dues mil sumes. El primer algorisme és lent i una pèrdua de temps, mentre que el segon és savi i eficient. La tercera solució és ràpida, però mata mosques a canonades. És la solució “quick and dirty“, com diuen els anglesos. Arribem a la solució sense pensar gaire i utilitzant més recursos i energia del que cal. Malauradament, ens hi trobem massa sovint. S’utilitzen grans recursos informàtics per a resoldre problemes que, pensant una mica, es podrien resoldre de manera eficient en ordinadors petits i domèstics.

Donat qualsevol problema, el podem resoldre ràpidament, amb potència informàtica i sense pensar gaire, o bé utilitzant la nostra matèria gris per descobrir algorismes que el podran resoldre bé en màquines molt més petites i gastant molta menys energia. Són els algorismes savis i eficients, els que fan cas a allò que diuen que val més manya que força. Però en alguns casos, sobretot en aplicacions interactives en dispositius petits i mòbils, els millors són els algorismes que ho fan ben fet i sense presses. Són els algorismes mandrosos, que són savis, eficients i lents.

Podríem dir, tot exagerant, que els algorismes mandrosos segueixen aquella dita Siciliana que diu “no facis avui el que puguis deixar per demà”. No és ben cert perquè de fet fan tot el que poden; però el que no tenen temps de fer avui, això sí que ho deixen per l’endemà. Aquesta pàgina web en dóna algun exemple en aplicacions específiques.

Cada cop hi ha més dades, a Internet. Tenim mapes i imatges de satèl·lit de tot el món. És molta informació, és allò que ara se’n diu “Big data“. Des de fa pocs anys, tenim la possibilitat de “navegar-hi” des d’el nostre telèfon mòbil. El problema de la navegació interactiva no és trivial. Però gràcies a la persistència de les imatges en la nostra retina, podem reduir-lo a un problema molt més concret: el de generar un mínim de 30 imatges per segon. Tot i així, el problema continua essent molt complex perquè volem aconseguir la màxima qualitat visual en ordinadors molt petits i en telèfons mòbils. L’usuari, amb el moviment dels seus dits sobre la pantalla, demana anar a una certa zona, apropar-s’hi fent “zoom“, saltar a un altre lloc. L’aplicació, constantment ha d’improvisar. Ha de demanar la zona desitjada del mapa al servidor, l’ha de rebre per la xarxa i l’ha de pintar amb bona qualitat visual, tot en menys d’un trentè de segon. Cal un algorisme que podríem anomenar de tipus “entrepà” perquè les dificultats li venen tant de dalt com de baix. En un temps limitat (els seus “dies” són trentès de segon) ha de cercar, trobar i rebre el trosset de mapa que interessa dins una biblioteca digital gegant de mapes de tot el món, i l’ha de pintar el millor possible en una màquina de visualització molt petita. És fàcil veure que es tracta d’una variant del clàssic problema de la motxilla. En aquest problema suposem que tenim molts objectes, cada un d’ells amb un valor determinat, i volem omplir una motxilla de manera que al final la suma de valors dels objectes que hi hem posat sigui màxima, sense sobrepassar la capacitat total de la motxilla (en el nostre cas, la capacitat de la motxilla és el trentè de segon, i el valor és la qualitat visual que obtenim). El problema de la motxilla és un dels 21 problemes NP-complets de Richard Karp, impossibles de resoldre en temps raonable – fins i tot en grans ordinadors – i exposats en el seu article de 1972. En casos com aquest, sabem que cal pensar en solucions bones però aproximades. I una bona solució per a la visualització interactiva en telèfons mòbils són els algorismes mandrosos i golafres. La idea és pintar primer els trossets de mapa més interessants, mentre tinguem temps i no acabem el trentè de segon. Quan se’ns acaba el temps, deixem la resta per a més endavant.

És com pintar un quadre. El nostre telèfon, quan estem navegant i mirant mapes, pinta quadres. Pinta un quadre cada dia, en una escala de temps en la que els seus dies són trentès de segon per a nosaltres. Cada dia ens pinta el que li demanem, i ho fa començant pel més important per tal d’assegurar que el resultat final sigui el millor possible. I quan acaba la jornada, deixa la resta per l’endemà. Si l’endemà veu que continuem demanant el mateix, posa més detalls en el quadre que tenia a mitges i el millora. Si s’adona que hem canviat d’opinió, el deixa inacabat i comença a pintar un nou quadre, el quadre de la nova zona del mapa que hem decidit investigar. Cada dia comença per les parts més interessants, fa la feina que pot, i deixa pendent la resta.

Tot plegat té una certa relació amb el desig d’immediatesa. Sembla que avui en dia, tot ho hem de resoldre i aconseguir ràpidament. Però la física ens diu que la reacció immediata és infinitament cara i necessita moltíssima energia. És clar que en alguns cassos de risc cal actuar ràpid i esmerçar tota l’energia que calgui. Però l’habitual és poder esperar. En molts casos podem arribar a solucions acceptables amb algorismes savis i més lents, amb algorismes mandrosos. És el moviment “slow” aplicat als algorismes i a la resolució de problemes. És el que fan (i fem) tots els animals quan arriba la nit i hem de descansar perquè ja hem gastat massa energia. El que no hem pogut fer, ho deixem per l’endemà. Els éssers vius optimitzen l’energia. Els algorismes mandrosos, també.

Per cert, i si ens indignem contra les retallades en ciència, recerca, educació i sanitat?