Počítač zložil 9600-kusové puzzle len na základe obrazu
DSL.sk, 17.6.2012
Andrew Gallagher z Cornellovej univerzity pracujúci zároveň pre Eastman Kodak Research Laboratories tento týždeň zverejnil a budúci týždeň predstaví na konferencii CVPR 2012 nový algoritmus pre počítačové skladanie puzzle založený čisto na analýze obrazu.
Algoritmus podobne ako viaceré predchádzajúce pracuje s puzzle, ktoré majú všetky diely presne štvorcového tvaru a rovnakej veľkosti. Algoritmy sa tak nemôžu spoliehať na tvar dielikov, skladať musia len čisto na základe obrazových informácií.
Jeden dielik má typicky 28 x 28 pixelov.
Doterajšie algoritmy skladali puzzle so známym otočením dielikov, ich úlohou ich bolo len umiestniť na správnu pozíciu. Algoritmus Gallaghera, na ktorý upozornil New Scientist, funguje aj pre puzzle o otočenými dielikmi, pre ktoré nájde správnu orientáciu.
Nový algoritmus dosahuje podľa Gallaghera lepšie výsledky ako predchádzajúce a podarilo sa mu bezchybne zložiť puzzle s 9600 dielmi, doteraz najväčšie puzzle tohto typu zložené počítačovým algoritmom.
K zlepšeniu prišlo v dvoch hlavných oblastiach. Algoritmus vyhodnocuje podobnosť dvoch potenciálne susedných dielikov podobným spôsobom ako doterajšie algoritmy, ohodnotením farebnej podobnosti blízko okraju dielika. Na rozdiel od nich ale nový algoritmus dobre toleruje aj postupnú zmenu farby na hranici dielikov, nielen približne rovnakú farbu na oboch stranách hranice.
Na bežných obrázkoch dva dieliky označí správne ako susedné v závislosti na obrázku s pravdepodobnosťou cca 90% prípadne vyššou.
Skladanie 600-kusového puzzle algoritmom (video: Andrew Gallagher)
Lepší je aj algoritmus, ktorý na základe podobnosti hrán dielikov hľadá ich zloženie do celého obrázku.
Algoritmus nie je stopercentný a nie vždy poskladá puzzle úplne. Z bežnej testovacej sady dvadsať puzzle ale poskladal úplne dvanásť a jeho celková presnosť v podobe dobre zložených častí sa pohybuje v závislosti na puzzle na úrovni 90% až 93%.
Zamiešané a poskladané 9600-kusové puzzle riešené algoritmom, kliknite pre zväčšenie (foto: Andrew Gallagher)
9600-kusové puzzle zložil na bližšie nešpecifikovanom výkonnom osobnom počítači za 23.5 hodiny.
Praktickou aplikáciou podobnou algoritmickému skladaniu puzzle je skladanie skartovaných dokumentov. Takejto súťaže vyhlásenej organizáciou DARPA v minulom roku sa s algoritmom vychádzajúcim z algoritmu na riešenie puzzle zúčastnil aj Gallagher, skončil ale až na sedemnástom mieste.
Časť zadania najťažšej úlohy riešenej na súťaži DARPA (obrázok: DARPA)
Podľa vyjadrenia pre New Scientist sa výhody algoritmu plne neaplikovali, keďže naskenované útržky skartovaného papiera nedoliehali presne a často kúsky chýbali. Navyše skladané dokumenty boli iba dvojfarebné, s čiernym textom na žltom pozadí.
"Len" na zaklade obrazu? A podla coho ineho sa este da poskladat puzzle? Zaujimavy clanok by to pre mna bol, keby ten obraz nepoznal a casti puzzle by spajal na zaklade zhody na okrajoch a tym by ziskal obraz...
Tvar vedia a ktorykolvek kusok hranou zapadne kamkolvek (nemusi sediet farebne) Ale keby to bolo klasicke puzzle, tak moze testovat aj to ci dva rozne kusky zapadnu vystupkami.
Re: uplink je teply
Od: inštalatér
|
Pridané:
18.6.2012 2:12
Milá babka z Olešanoviec, prosím berte na vedomie, že tá vec čo fajčíte nebol tabak ale konope ktoré sa skôr hodí na vodovodárenske trubky ako na konzumáciu či fajčenie, preto Vás dôrazne prosím, nabudúce to z tej trubky neťahajte, za pochopenie vopred ďakujem.
bruteforce mozes robit, ked vies jednoznacne (a jednoducho) overit spravnost riesenia. Kedze v tomto pripade predloha nie je znama, nema zmysel hovorit o nejakom "bruteforce"
neprihlásený 
