Gelijksoortige plaatjes vergelijken

[Gomez12]

Weet er iemand wat de makkelijkste manier is om in een dbase een soort van similar images te zetten?

Ik heb iets van 470.000 artikelen + images in een db staan, nu wil ik als ik 1 artikel bekijk iets van lijkt op dit artikel op basis van images doen ( op tekstuele basis is al geregeld ).

Nu doe ik op de tekst van een leverancier binnen een categorie al een levensteihn calculatie zodat ik soortgelijke artikelen etc kan vinden ( zit een iets uitgebreider algoritme achter wat rekening houdt met waar de gebruiker op zocht, wat de gebruiker veelal aanklikt etc ), dit levert in de huidige setup een n:n koppeltabel met ratings op van 378 miljoen entries en enkel id's. Qua gebruik werkt dit perfect en qua aanmaken is het ook niet echt zwaar.

Nu wil ik eigenlijk iets soortgelijks gaan opbouwen voor images, qua n:n tabel kom ik dan uit op 198 miljoen entries ( dubbele plaatjes etc zijn eruit gehaald ).

Alleen hoe kan ik die onderling snel vergelijken?

Huidig probeerseltje was de volgende code :

code:

$cmd='convert "' . $afb1 . '" "' . $afb2 . '" -compose difference -composite -colorspace gray miff:- | identify -verbose - | sed -n \'/^.*Mean: */{s//scale=2;/;s/(.*)//;s/$/*100\/32768/;p;q;}\' | bc';

Wat opzich perfect werkt, ik krijg gewoon een score qua gelijkheid. Alleen dit ding verwerkt er maar ongeveer 1000 per minuut. Qua eerste aanzet is dit geen probleem ( er is een 2e server voor dit soort dingen aanwezig die gewoon 2 weken kan stampen ).
Maar als een leverancier er op een dag 100 plaatjes bijzet ( meeste leveranciers leveren batchgewijs aan, dus 100 leveranciers die 50 plaatjes aanleveren op de 1e vd maand is geen uitzondering ) dan wordt het uiteraard wel problematisch.

Ik had zelf al zitten denken om een extreem kleine thumbnail te maken ( momenteel loopt bovenstaande code op een 80x80 8-bits plaatje ) en die dan onder te verdelen naar pre-dominant color, maar dit verhoogt de snelheid niet significant ( getest met 40x40 4-bits plaatjes ) maar de mis-rate gaat gigantisch omhoog ( door het onderscheid in dominant color ga ik gelijksoortige producten missen als de achtergrond net iets anders is qua kleur / belichting etc )

Mijn google-skills laten me even compleet in de steek qua programmatuur die dit zou kunnen doen ( ik gok dat een dedicated app dit tig x sneller / beter kan dan wat grappen met imagemagick maarja, roeien met de riemen die je hebt )
Iemand die me wat tips oid kan geven hoe dit wel te doen is?

P.s. voor er mensen komen met al te specifieke tools / tips, aan alleen een dedicated image comparer heb ik imho weinig, het is onderdeel van een totaal algoritme wat weer samenhangt met rechten en rollen / geschiedenis / categorie waar iemand in zit etc etc. Als ik blind de 250 meest gelijkende images terug zou krijgen dan kan daar best alles uit geelimineerd worden op basis van andere parameters van het algoritme.

[pedorus]

Gomez12 schreef op maandag 22 februari 2010 @ 22:15:
Wat opzich perfect werkt, ik krijg gewoon een score qua gelijkheid. Alleen dit ding verwerkt er maar ongeveer 1000 per minuut. Qua eerste aanzet is dit geen probleem ( er is een 2e server voor dit soort dingen aanwezig die gewoon 2 weken kan stampen ).
Maar als een leverancier er op een dag 100 plaatjes bijzet ( meeste leveranciers leveren batchgewijs aan, dus 100 leveranciers die 50 plaatjes aanleveren op de 1e vd maand is geen uitzondering ) dan wordt het uiteraard wel problematisch.

Hoezo is dat een probleem dan? Het lijkt me dat dit ook rustig op de achtergrond kan draaien. En anders is php(?)->convert->sed->bc natuurlijk niet zo snel, dat kan inderdaad beter in 1 programma. Dat scheelt denk ik een stuk meer dan die 8-bit enzo..

Volgens dit artikel heb je al de beste aanpak (van de geteste methodes) als je 1 object per foto hebt door naar de pixelwaardes te kijken. Ik weet enkel niet zeker welke vergelijkingsmethode je precies gebruikt. Als het echt te zwaar is zou je naar locale properties moeten gaan kijken ofzo, maar dat kost meer implementatiewerk en de performance is ook iets slechter. Misschien dat je iets met deze code kan waar dat in geimplementeerd is.

[ Voor 26% gewijzigd door pedorus op 22-02-2010 23:23 . Reden: verkeerde stuk gequote ]

[NMe]

Dit is toch per definitie iets dat je in een cronjob om 3 uur 's nachts kan laten draaien? Of desnoods elke minuut één image, mits er een queue is? Score opslaan in een database, alles waarvan je nog geen score berekend hebt is onderdeel van de queue. Lijkt me relatief simpel te bakken?

[BCC]

Mechanical Turk? https://www.mturk.com/mturk/welcome Is this image similar ?

[Gomez12]

pedorus schreef op maandag 22 februari 2010 @ 23:14:
[...]
Hoezo is dat een probleem dan? Het lijkt me dat dit ook rustig op de achtergrond kan draaien.

1 nieuwe image kan als het binnen een groep van 2500 images valt leiden tot 2500 vergelijkingen , 2e image leidt weer tot 2501 vergelijkingen. 2 nieuwe plaatjes betekent 5001 vergelijkingen.
A 1000 vergelijkingen per minuut loopt dit hard op.
Idealiter is het streven ongeacht de omstandigheden ( ultra extremen als 5000 plaatjes per dag uitgezonderd ) om binnen 4 uur per dag klaar te zijn ( backup moet er ook nog overheen etc ).

Marketingtechnisch is het niet al te handig om te moeten zeggen dat nieuwe plaatjes pas 2 of 3 dagen later geindexeerd zijn

Volgens dit artikel heb je al de beste aanpak (van de geteste methodes) als je 1 object per foto hebt door naar de pixelwaardes te kijken. Ik weet enkel niet zeker welke vergelijkingsmethode je precies gebruikt. Als het echt te zwaar is zou je naar locale properties moeten gaan kijken ofzo, maar dat kost meer implementatiewerk en de performance is ook iets slechter. Misschien dat je iets met deze code kan waar dat in geimplementeerd is.

Oeh leesvoer, zal ik morgen even naar kijken ....
Maar blijkbaar is er geen universele methode die ik verkeerd aanpak oid, het is blijkbaar gewoon een server die veel moet ploeteren en dan is er blijkbaar wel iets qua performance te doen maar de algemene aanpak is juist?

NMe schreef op maandag 22 februari 2010 @ 23:20:
Dit is toch per definitie iets dat je in een cronjob om 3 uur 's nachts kan laten draaien? Of desnoods elke minuut één image, mits er een queue is? Score opslaan in een database, alles waarvan je nog geen score berekend hebt is onderdeel van de queue. Lijkt me relatief simpel te bakken?

Per minuut 1 image? Zoveel minuten zitten er echt niet in 1 dag
Daarom is er al een losse rekenserver naastgezet, die construeert nu al een x aantal zoekindexen terwijl de main-db aan het backuppen is ( en overdag staat dat ding weer te backuppen naar een tape-robot )

Het mogelijke ( theoretische ) probleem wat ik zie is dat als je 1 categorie hebt waarbinnen 1 leverancier 5000 plaatjes hebt, dat 1 toegevoegd plaatje 5000 vergelijkingen in de queue stopt en daarmee de hele queue even vastzet voor andere leveranciers ( valt wel iets op te verzinnen qua randomizen van de queue / prioritizen van de queue maar dat soort dingen is sub-optimaal denk ik dan maar )

Ik zat me gewoon even af te vragen of ik wel juist zat met het brute-forcen van alle plaatjes ( binnen een leverancier en daarbinnen weer binnen een categorie maar toch )

BCC schreef op maandag 22 februari 2010 @ 23:21:
Mechanical Turk? https://www.mturk.com/mturk/welcome Is this image similar ?

Zie ik zo snel even geen toepassing voor, ik zie het nou niet echt zitten om vandaag 500 opdrachten te betalen omdat een leverancier 1 plaatje toegevoegd heeft en morgen 501 opdrachten te betalen omdat de leverancier nog een plaatje toegevoegd heeft.
Economisch niet echt verantwoord zeg maar....

[BCC]

Waarom maak je niet eerst op basis van je full-text search een set grove matches van zeg 1000, en ga je die picture by picture bekijken?

[Matis]

Wat mij het makkelijkste lijkt is dat je bij het invoeren van de afbeelding een soort van hash maakt van je afbeelding, wanneer je dan een soortgelijke afbeelding wilt zoeken, hoef je alleen maar de hamming distance van de hashes te berekenen.

[ThinkPad]

www.tineye.com kan het in ieder geval dus het principe bestaat wel

[ Voor 26% gewijzigd door ThinkPad op 23-02-2010 00:02 ]

[BCC]

Matis schreef op maandag 22 februari 2010 @ 23:57:
Wat mij het makkelijkste lijkt is dat je bij het invoeren van de afbeelding een soort van hash maakt van je afbeelding, wanneer je dan een soortgelijke afbeelding wilt zoeken, hoef je alleen maar de hamming distance van de hashes te berekenen.

Eigenlijk doet de TS dat al, alleen wat jij voorstelt zou dan een grofmazigere check zijn. Probleem blijft dat je veel moet vergelijken + ik denk dat je nogal grote groepen krijgt, zoals: foto's met een product in het midden met een witte achtergrond.

[ Voor 41% gewijzigd door BCC op 23-02-2010 00:02 ]

[NMe]

Gomez12 schreef op maandag 22 februari 2010 @ 23:49:
[...]

1 nieuwe image kan als het binnen een groep van 2500 images valt leiden tot 2500 vergelijkingen , 2e image leidt weer tot 2501 vergelijkingen. 2 nieuwe plaatjes betekent 5001 vergelijkingen.
A 1000 vergelijkingen per minuut loopt dit hard op.

Als plaatje 1 bijna gelijk is aan plaatje 2, en plaatje 2 is weer bijna gelijk aan plaatje 3, dan zitten plaatje 1 en 3 ook vrij dicht bij elkaar. Da's al een verkorting die je kan overwegen, al zit daar natuurlijk wel een steeds ruimere foutmarge op.

Per minuut 1 image? Zoveel minuten zitten er echt niet in 1 dag
Daarom is er al een losse rekenserver naastgezet, die construeert nu al een x aantal zoekindexen terwijl de main-db aan het backuppen is ( en overdag staat dat ding weer te backuppen naar een tape-robot )

Je hoeft natuurlijk niet alle images te vergelijken. Ik neem aan dat er ook andere data is waaraan je kan zien of een vergelijking al dan niet zin heeft. Iets in de categorie levensmiddelen vergelijken met iets uit de categorie power tools heeft natuurlijk niet zo gek veel zin, uitgaande van het bestaan van categorieën. Images vergelijken kost zoals je gemerkt hebt nogal wat rekenkracht, doe dat dan ook alleen daar waar je vooraf kan bepalen dat het mogelijk zin heeft.

Iets anders waar je aan kan denken: zelf een tooltje schrijven of een tooltje zoeken dat gebruik maakt van CUDA (of een vergelijkbare techniek) om die vergelijkingen te doen. Dan gebruik je de GPU in plaats van/in samenwerking met de CPU en dat is ook een stukje winst.

[Matis]

NMe schreef op dinsdag 23 februari 2010 @ 00:06:
Iets anders waar je aan kan denken: zelf een tooltje schrijven of een tooltje zoeken dat gebruik maakt van CUDA (of een vergelijkbare techniek) om die vergelijkingen te doen. Dan gebruik je de GPU in plaats van/in samenwerking met de CPU en dat is ook een stukje winst.

Dat is precies hetgeen wat ik op mijn stage gedaan heb, echter keken we bij de afbeeldingen alleen naar de luminantie van de afbeelding om zo te kunnen detecteren of afbeeldingen overeen kwamen of niet (scene-overgang in video).

[Gomez12]

BCC schreef op maandag 22 februari 2010 @ 23:54:
Waarom maak je niet eerst op basis van je full-text search een set grove matches van zeg 1000, en ga je die picture by picture bekijken?

Doe ik nu idd deels al op basis van leverancier en categorie. Dit valt nog wel enigszins te verfijnen, maar dit wil ik ook niet al te veel verfijnen omdat het ook niet werkt als 40% geen gelijkende images meer heeft omdat ik de voorselectie te veel verfijnt heb.

Huidige methodiek is : als een leverancier meer dan 100 images heeft dan trek ik de categorie erbij.
Categorieen is een boom met 6 niveaus.
Heeft een categorie minder dan 25 items van dezelfde leverancier dan trek ik het bovenliggende niveau ( en dus ook alle onderliggende categorieen ) erbij. Dit stukje is nog ietwat experimenteel omdat dit soms leidt tot een explosieve toename ( nivo 6 voor dit artikel heeft maar 2 artikelen, ander nivo 6 wat onder hetzelfde nivo 5 hangt heeft wel 2000 artikelen, dat is een oeps....)

Matis schreef op maandag 22 februari 2010 @ 23:57:
Wat mij het makkelijkste lijkt is dat je bij het invoeren van de afbeelding een soort van hash maakt van je afbeelding, wanneer je dan een soortgelijke afbeelding wilt zoeken, hoef je alleen maar de hamming distance van de hashes te berekenen.

Ik zou het graag doen, maar qua afbeeldingen kan ik geen hashing methodiek vinden die werkt...
2 plaatjes waarbij maar 1 pixel afwijkt leveren compleet andere hashes op afaik terwijl ik ze voor 99,999999999% gelijk vind. Zal nog wel even kijken naar hamming distance, dat zegt mij dan weer niets.

NMe schreef op dinsdag 23 februari 2010 @ 00:06:
[...]
Als plaatje 1 bijna gelijk is aan plaatje 2, en plaatje 2 is weer bijna gelijk aan plaatje 3, dan zitten plaatje 1 en 3 ook vrij dicht bij elkaar. Da's al een verkorting die je kan overwegen, al zit daar natuurlijk wel een steeds ruimere foutmarge op.

Goede shortcut, alhoewel ik hem dan waarschijnlijk andersom ga implementeren.
Lijkt plaatje 1 totaal niet op plaatje 2, lijkt plaatje 2 wel op plaatje 3 dan is plaatje 3 niet meer relevant om te vergelijken met plaatje 1.
Het gaat me qua gelijkende plaatjes juist om de getallen achter de komma zogezegd. Lijkt plaatje 3 nou meer of minder dan plaatje 2 op plaatje 1...

[...]
Iets in de categorie levensmiddelen vergelijken met iets uit de categorie power tools heeft natuurlijk niet zo gek veel zin, uitgaande van het bestaan van categorieën.

Grappig genoeg heeft dit juist veel zin qua totaal vergelijken. De 1e doe maar een gooi actie van random 10.000 images ongeacht iets om te zien of het principe werkte heeft "veel" verkeerd gecatagoriseerde artikelen aangetoond.
Qua rekenkracht etc willen we de huidige dagelijkse case wel beperken tot enkele plaatjes vergelijken.
Maar er staat nu wel ergens in de planning om een workstation 1x per x tijd alles te laten vergelijken om de artikelen in foutieve categorieeen "beter" op te kunnen sporen.

Iets anders waar je aan kan denken: zelf een tooltje schrijven of een tooltje zoeken dat gebruik maakt van CUDA (of een vergelijkbare techniek) om die vergelijkingen te doen. Dan gebruik je de GPU in plaats van/in samenwerking met de CPU en dat is ook een stukje winst.

Om de een of andere reden vermoed ik dat de directie eerst wat cijfers wil zien voordat we de servers uit mogen rusten met de beste vid-kaarten om crysis op te mogen spelen

Maar qua idee vind ik het een leuke, ik dacht ergens iets gelezen te hebben van GPU 800x sneller dan CPU, als het in ons geval 50x sneller is dan is het nog een gigantische goedkope winst

[NMe]

Gomez12 schreef op dinsdag 23 februari 2010 @ 00:40:
[...]

Goede shortcut, alhoewel ik hem dan waarschijnlijk andersom ga implementeren.
Lijkt plaatje 1 totaal niet op plaatje 2, lijkt plaatje 2 wel op plaatje 3 dan is plaatje 3 niet meer relevant om te vergelijken met plaatje 1.

Dat klinkt inderdaad zinniger dan wat ik zei, maar de foutmarge die je feitelijk "vermenigvuldigt" is natuurlijk gelijk. Nog steeds nuttig om naar te kijken though, mits je niet meer dan een paar "niveau's" diep gaat.

Grappig genoeg heeft dit juist veel zin qua totaal vergelijken. De 1e doe maar een gooi actie van random 10.000 images ongeacht iets om te zien of het principe werkte heeft "veel" verkeerd gecatagoriseerde artikelen aangetoond.

Ik ken je exacte scenario natuurlijk niet en misschien liggen jouw categorieën wat dichter bij elkaar dan het voorbeeld dat ik noemde. Idealiter zou het alsnog een goeie shortcut zijn, eventueel in samenwerking met andere meta-informatie die je mogelijk hebt.

Om de een of andere reden vermoed ik dat de directie eerst wat cijfers wil zien voordat we de servers uit mogen rusten met de beste vid-kaarten om crysis op te mogen spelen

Maar qua idee vind ik het een leuke, ik dacht ergens iets gelezen te hebben van GPU 800x sneller dan CPU, als het in ons geval 50x sneller is dan is het nog een gigantische goedkope winst

800x weet ik niet. Ik weet wel dat een bepaald bedrijf dat bezig is met het maken van echo's en hardware die die echo's maakt bezig is met het overstappen van een kast van 50x50x150cm tsjokvol aan hardware naar een veredelde pc door gebruik te maken van CUDA.

Zo'n kaartje heb je al voor rond de 70 euro trouwens, je hebt niet per se top-notch hardware nodig om CUDA te kunnen draaien. En devtijd gaat er hoe dan ook wel in zitten, kun je het net zo goed meteen goed doen.

[Matis]

Ik heb bij het ontwikkelen van mijn CUDA-applicatie (nu ongeveer 1 jaar geleden) gebruik gemaakt van de pricewatch: Asus EN9800GTX+ DK TOP/HTDI/512M welke op dat moment al bijna 50 keer sneller was dan mijn quadcore Xeon-processor.

Dat kaartje kostte toen ongeveer 100 euro, nu worden ze zelfs al niet meer geleverd/verkocht, maar met het kaartje van NMe kun je al prima uit de voeten. Is het alleen maar om te proberen.

@NMe, jij doelt op de Fastra en/of Fastra 2 van de Universiteit van Antwerpen voor het laminograferen van medicinale-scans.

[NMe]

offtopic:
Nee, ik doel op een ander bedrijf dat destijds nog aan het experimenteren was met verscheidene technieken en ik weet niet hoeveel ze naar buiten willen brengen over dit onderzoek, dus ik noem even geen naam.