Diskuze: Machr na algoritmy - Podobné obrázky

Java Java Machr na algoritmy - Podobné obrázky

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Ahoj, v týdenní minisoutěži o modrou placku Machr na algoritmy a samolepky si zkusíme zas nějaké grafické algoritmy. Tentokrát půjde o porovnávání obrázků. Zkuste vymyslet algoritmus, který dokáže přibližně zjistit, zda jsou si 2 obrázky podobné. Vašim programům poté zkusím zadat několik obrázků a autor programu, který se bude nejméně plést, získá placku a nálepky :) Ukázky podobných obrázků viz níže. Program nemá řešit velikost obrázku a měl by asi pracovat na principu rozeznání ploch a jejich barev.

Deadline si dejme v neděli 8.9. v 18:00

Odpovědět 2.9.2013 19:27
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

Jak má člověk stíhat dělat hru do Magického léta, když dáváš takový zajímavý úkoly? :D

Nahoru Odpovědět  +4 2.9.2013 20:29
:)
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
martinsakra:

jako správný programátor, málo spánku, spoustu kódu :D

Editováno 2.9.2013 21:44
Nahoru Odpovědět  +2 2.9.2013 21:44
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Michal Žůrek (misaz):

a ty jako nám dáš otestovat zelené jablko a červené jablko a my ti máme napsat že jsou podobné?

Nahoru Odpovědět 3.9.2013 6:17
Nesnáším {}, proto se jim vyhýbám.
Avatar
David Hynek
Redaktor
Avatar
David Hynek:

Zkusím vzkřísit princip, který jsem použil v Pascalu... :)

Nahoru Odpovědět 3.9.2013 7:29
Čím víc vím, tím víc věcí nevím.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Michal Žůrek (misaz)
David Čápka:

To by bylo moc těžké, pozná to jen jablka co mají podobný tvar a barvu. Zelené a červené budeme brát jako 2 jiné obrázky.

Nahoru Odpovědět 3.9.2013 8:10
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

Já bych klidně nechal zelené a červené jablko jako podobný obrázek :)

Nahoru Odpovědět  +1 3.9.2013 10:03
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

To už by bylo těžší :) Já bych to dělal asi tak, že bych si ořezal barvy na nějakou velmi základní škálu a potom obrázky rozpixeloval na nějaké velmi hrubé rozlišení (10x10 pixelů?). Výsledky bych potom porovnal asi ještě s nějakou tolerancí.

Nahoru Odpovědět  +1 3.9.2013 10:05
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
martinsakra:

záleží co je učelem, jestli pokud dostanu obrázek se zeleným jablkem tak najít jablko, nebo třeba mísu s ovovcem co obsahuje zelený jablko? (nebo obje já vím :D )

Nahoru Odpovědět 3.9.2013 16:39
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Odpovídá na martinsakra
Luboš Běhounek (Satik):

Mísa s ovocem už by byla příliš složitá, na poměry devbooku nejspíš i "neřešitelná" :)

Ale poznat, že červené jablko je podobné zelenému se ještě nějak dá, pokud jsou jinak podobná a jsou třeba umístěná na stejném místě v obraze a mají podobnou velikost.

Nahoru Odpovědět 3.9.2013 18:07
:)
Avatar
David Hynek
Redaktor
Avatar
Odpovídá na David Čápka
David Hynek:

10x10px je moc málo. V Pascalu jsem porovnával velikosti 32x24px (4:3). Ale v té době bylo obrázky max 640x480px :)

Nahoru Odpovědět  +1 3.9.2013 20:53
Čím víc vím, tím víc věcí nevím.
Avatar
Fredep
Redaktor
Avatar
Fredep:

Napadlo mě, budou se brát jako "totožná jablka", že na jednom obrázku bude jablko v levém horním rohu a v druhém obrázku zase v pravém dolním?

Nahoru Odpovědět 4.9.2013 18:28
Týmová práce je důležitá proto, aby bylo možno obvinit z neúspěchu někoho jiného.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Fredep
David Čápka:

Asi ne, stačí to opravdu jen jednoduché.

Nahoru Odpovědět 4.9.2013 18:30
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

Jaké formáty to má umět? (PNG, JPG...)

 
Nahoru Odpovědět 4.9.2013 19:04
Avatar
Odpovídá na David Čápka
Michael Olšavský:

V čem si přesně obrázky mají být podobné? Barva, tvar i barva(malé rozdíly), pouze tvary...

 
Nahoru Odpovědět 4.9.2013 20:56
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Michael Olšavský
David Čápka:

PNG nebo JPEG, ideálně obojí. Podobné jsou si barvou a tvarem.

Nahoru Odpovědět 5.9.2013 9:30
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Michael Olšavský:

Tak už se na to někdo vrhnul? Já to mám skoro hotové, jen vychytat ty odchylky. Snad to do zítra stihnu, jelikož teď nebudu mít moc přístup k pc.

 
Nahoru Odpovědět 7.9.2013 11:05
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Michael Olšavský
martinsakra:

No já jsem zatim v tomhle stavu, a musím ještě vychytat pár errorů co mi tam skáčou, a naučit to pracovat se 2 soubory jinýho rozlišení.

Nahoru Odpovědět  +1 7.9.2013 12:45
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Odpovídá na martinsakra
Michael Olšavský:

Já jsem na tom nějak podobně. Jen mě nenapadlo jak ukázat zda jsou nebo nejsou podobné. Ta procenta jsou chytré řešení. Ještě jsem aplikoval filtr pro vyhledávání hran. Snad to trochu ulehčí vyhledávání. Ještě jsem ale ještě nepřišel jak ho nejlépe využít.

 
Nahoru Odpovědět 7.9.2013 14:24
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Michael Olšavský
martinsakra:

no to řešim taky, doted jsem nevyřešil jak třeba bále pozadí s obejtem levo nahoře a víle pozadí s objektem (stejným) vpravo dole, zatim jsem jen ve stavu, toho obrázku co jsem ukazoval

Nahoru Odpovědět 7.9.2013 14:43
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
martinsakra
Redaktor
Avatar
martinsakra:

Takže zde přidávám svůj výtvor. Už na to nebudu mít dneska ani zítra čas, i když by si to možná zasloužilo. Jinak program je docela pomalý, (zvlášť pokud obrázek obsahuje velké plochy stejné barvy). Jsou tam i zdrojáky tak se můžete podívat,ale moc z toho asi nevyčtete :D
Jinak , myslím že kdybych místo porovnávání obrázků udělal nějaký pěkný náhodný generátor čísel tak by to bylo skoro stejný

https://mega.co.nz/#!CQdGQQLD!Ke8XMQJjCAZ-MW7fj3Wi0VHu_PUdvHSJfW9pOLPZCwk
Nahoru Odpovědět 7.9.2013 18:45
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Odpovídá na martinsakra
Michael Olšavský:

Nejak mi to nefunguje. zasekne se to u prepare

 
Nahoru Odpovědět 7.9.2013 20:08
Avatar
Odpovídá na Michael Olšavský
Michael Olšavský:

Už je to v pořádku. Jen je to opravdu příšerně pomalé. To moje je proti tomu opravdu rychlík :D ale funguje to celkem dobře. Já mám zatím udělanou geometrickou detekci. Barva ještě nějak nefunguje.

 
Nahoru Odpovědět 7.9.2013 20:20
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Michael Olšavský
martinsakra:

je to kvuli tomu že to dělá prohledávání do šířky :D a to třeba na 1024x720 není žádná sranda :D , ale co nadělám, bez té části by to nefungovalo pořádně a nic lepšího mě nenapadlo

s tím že jde samozřejme v kodu celej krok prepare vyhodit,ale tím padem se zhorší detekce a stene se podle mě víc nepřesnou

Editováno 7.9.2013 20:22
Nahoru Odpovědět 7.9.2013 20:22
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Odpovídá na martinsakra
Michael Olšavský:

Já to nahrubo předělávám do 1000 x 1000

 
Nahoru Odpovědět 7.9.2013 20:22
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Michael Olšavský
Jan Vargovský:

Vyhledávat podobné obrázky na googlu, pár let bych si asi počkal :)

 
Nahoru Odpovědět 7.9.2013 20:28
Avatar
Odpovídá na Jan Vargovský
Michael Olšavský:

:D To asi ano. Ale oni to mají předhashované. Tzn. že to neprohledává vždy znovu ;-)

 
Nahoru Odpovědět 7.9.2013 20:30
Avatar
Odpovídá na David Čápka
Michael Olšavský:

Zde je moje verze. Vše by mělo fungovat bez problému.

 
Nahoru Odpovědět 7.9.2013 22:00
Avatar
Luboš Běhounek (Satik):

Hm, až teď jsem se dostal k PC, tak to se už do ničeho pouštět nebudu :)

Nahoru Odpovědět 8.9.2013 17:00
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Tak, snažil jsem se to testovat jak to šlo, ale výsledky jsou bohužel hrozně mimo a to u všech zúčastněných:

brisingr002
apple1 a apple2 - 80%
elephant1 a elephant2 - 65%
nemo1 a nemo2 - 93%
windows1 a windows2 - 90%
apple2 a elephant1 - 59%
nemo2 a windows2 - 80%
app1 a app2 - 94%

martinsakra
apple1 a apple2 - 39%
elephant1 a elephant2 - 30%
nemo1 a nemo2 - 55%
windows1 a windows2 - 28% (mimo)
apple2 a elephant1 - 9%
nemo2 a windows2 - 33%
app1 a app2 - 53%

p4koo
apple1 a apple2 - 83%
elephant1 a elephant2 - 77%
nemo1 a nemo2 - 100%
windows1 a windows2 - 83%
apple2 a elephant1 - 71% (mimo)
nemo2 a windows2 - 79%
app1 a app2 - 92%

Testované obrázky viz níže nebo zde: https://dl.dropboxusercontent.com/…pobrazky.zip Nevím, jestli jsem zvolil moc složitou úlohu nebo je problém v implementacích. Nejblíže mi přijde brisingr002, ale je to jen o chlup, takže dneska asi bez placky :(

Nahoru Odpovědět 8.9.2013 19:20
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na David Čápka
Jan Vargovský:

Problém je v bilé ploše => každý kdo to dělal pixel po pixelu mu potom vyšly takové nesmyslné čísla :)

 
Nahoru Odpovědět 8.9.2013 19:27
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Pořád na to koukám a nevím si opravdu rady. Jestli má komunita nějaký nápad, tak sem s ním :)

Nahoru Odpovědět 8.9.2013 19:28
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Jan Vargovský
David Čápka:

Zkusím ještě něco bez bílé plochy.

Nahoru Odpovědět 8.9.2013 19:29
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Tak jsem to ještě trápil, ale pořád stejné výsledky, není to ani tou bílou barvou. Dal jsem třeba teď les a moře, výsledek byla shoda 80%. Dáme příště zas něco lehčího no :)

Nahoru Odpovědět 8.9.2013 19:44
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

Hm, asi si to cvicne zkusim taky, jestli dopadnu lip :D

Nahoru Odpovědět  +2 8.9.2013 20:29
:)
Avatar
David Hynek
Redaktor
Avatar
Odpovídá na David Čápka
David Hynek:

úloha je to zajímavá. Teď jsem bohužel v jednom kole a neměl jsem čas. Časem sem přidám své řešení. Třebas i bez placky :o)

Nahoru Odpovědět 8.9.2013 20:43
Čím víc vím, tím víc věcí nevím.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Je to opravdu hodně těžká úloha, která se nedá dělat pixel po pixelu.

Nahoru Odpovědět  +1 8.9.2013 20:44
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

Takže musím si obhájit své výsledky :-D

  • je to velmi specifická úloha, která nemá přesně specifikovaný výsledek a ten je velmi subjektivní. Samozřejmě, že slon není stejný jako logo apple, ale zase musíme v úvahu brát podobnou barvu a pozadí. Jak rozeznat slona od pozadí? Proto jsem použil filtr, aby to co nejvíce zpřesnil. Ale ani tak se nevyhnu pixel per pixel řešení. Dají se snad porovnávat obrázky jinak? Ano, mohu vytvořit hash, ale ten nevznikne z ničeho jiného. Každý obrázek má nějakou podobnost s jiným....
  • druhý důvod: zabralo mi to hodně času :DDD. Ne jsem rád, že jsem se naučil pracovat s těmi filtry. :-)

Byla to zajímavá úloha, ale neměla přesné řešení. Pouze šlo napodobit tvoje chápání kontextu.
Těším se na příští soutěž :-)

 
Nahoru Odpovědět  +3 8.9.2013 20:59
Avatar
Odpovídá na Michael Olšavský
Michal Žůrek (misaz):

něco nového ses naučil, to je jenom dobře.

Nahoru Odpovědět  +2 8.9.2013 21:14
Nesnáším {}, proto se jim vyhýbám.
Avatar
Odpovídá na Michal Žůrek (misaz)
Michael Olšavský:

Aaaaaaaaaaaaaaa. Z tebe se stal snad učitel ne? :D Ale souhlasím.

 
Nahoru Odpovědět 8.9.2013 21:17
Avatar
Kit
Redaktor
Avatar
Odpovídá na Michael Olšavský
Kit:

Spíš z něj za chvíli bude Kvantový počítač :)

Nahoru Odpovědět  +3 8.9.2013 21:21
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Nahoru Odpovědět  +2 8.9.2013 21:23
Nesnáším {}, proto se jim vyhýbám.
Avatar
Odpovídá na Kit
Michael Olšavský:

No jo :D Sakra ten to teda rozjel...

 
Nahoru Odpovědět 8.9.2013 21:32
Avatar
Nahoru Odpovědět  +1 8.9.2013 21:33
Nesnáším {}, proto se jim vyhýbám.
Avatar
Odpovídá na Michal Žůrek (misaz)
Michael Olšavský:

To bych taky mohl zkusit. Třeba do nějakého neznámého jazyka :D (D, D++, F#...) Ještě kdybych je uměl. :`

 
Nahoru Odpovědět 8.9.2013 21:34
Avatar
Odpovídá na Michael Olšavský
Michal Žůrek (misaz):

jo třeba F# vypadá zajímavě, ten bych se i naučil. Protože není objektový tak by mě nikdo nebuzeroval za kód :D

Nahoru Odpovědět  +1 8.9.2013 21:36
Nesnáším {}, proto se jim vyhýbám.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Michal Žůrek (misaz)
Kit:

Je funkcionální, takže pro buzeraci je tam prostoru dost :)

Nahoru Odpovědět  +2 8.9.2013 21:40
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Michael Olšavský
Kit:

Zkus XSLT. Všechny proměnné tam jsou immutable. Pro céčkaře téměř nepřekonatelný problém.

Nahoru Odpovědět 8.9.2013 21:45
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Panda38
Redaktor
Avatar
Panda38:

Když jsem řešil něco podobného - vyhledávání objektu v obraze - tak shodnost obrazů vyhodnocuji jako součet absolutních hodnot rozdílů barev (korelační koeficient). Nejdříve takto porovnávám obrazy velmi silně pixelované (na hrubé rozlišení), s tím že je vůči sobě posouvám, otáčím a měním velikost (hrubě). Pokud je někde zajímavější shoda, zvýším přesnost rozlišení a jemnost posunů a zkouším najít přesnější shodu ... a tak postupně až do nejvyššího rozlišení. Před hledáním může být nutné obrazy znormalizovat - vyrovnat jasy ploch.

 
Nahoru Odpovědět  +1 9.9.2013 16:35
Avatar
Odpovídá na Panda38
Michael Olšavský:

To je celkem chytré. Něco jako moje implentace s backtrackingem. To by mě nenapadlo :-)

 
Nahoru Odpovědět 9.9.2013 19:22
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 51 zpráv z 51.