[PHP] Afbeeldingen vergelijken

[S_tef]

Ik vroeg mij af hoe / of het mogelijk is om in PHP, 2 (externe) afbeeldingen met elkaar te vergelijken (dus qua uiterlijk).

Zelf kwam ik op het idee om met GD elke pixel te vergelijken Maarja dat is natuurlijk een vrij zwaar proces.
Maar je zit ook met het probleem als 2 dezelfde afbeeldingen in een andere kwaliteit / programma zijn opgeslagen, misschien dat je hiervoor dan een tollerantie kunt gebruiken?

Op google zag ik veel non PHP based oplossingen.

Wellicht dat iemand me op goede ideeen kan brengen?

[Matis]

Ik weet niet hoeveel 1000en afbeeldingen je wilt vergelijken, maar pixel voor pixel is echt peanuts voor een beetje degelijke server.

Je oplossing lijkt imo prima, ware het niet dat sommige bedrijven/websites het niet zo fijn vinden als je vanaf een externe bron hun afbeeldingen benaderen.

[S_tef]

Zijn er zon 30.000. Maargoed dit kan natuurlijk in stappen.
Niet gedacht dat het geen slecht idee was... Heb je toevallig ook een idee voor de kwaliteitsverschillen?

[Kwastie]

Je bedoelt met elkaar vergelijken en kijken of hij gelijk is? (dus op de pixel nauwkeurig)

Je kunt dan op beide bestanden een sha1_file() uitvoeren en kijken of de sha-hashes hetzelfde zijn. Maar als 1px een andere kleur heeft is de afbeelding al niet meer hetzelfde, dus de sha-hash niet meer hetzelfde.

Andere oplossingen zullen waarschijnlijk erg complex. En dan zul je waarschijnlijk moeten kijken of de kleuren van de pixel ongeveer gelijk zijn.

[_Sunnyboy_]

Waarom zou je dit in php willen doen?

In any case, je bent niet de enige, want Google brengt ons: New Image Compare Class for PHP

[mithras]

Tja, het ligt er natuurlijk ook aan wat je wil met vergelijken. Als ik twee foto's los achter elkaar neem, wil je die dan kunnen vergelijken en concluderen dat ze "gelijk" zijn? Of als ik een n * m bitmap maak waarin alle pixels een waarde hebben en ze daarbij bitwise vergelijken?

Het uberhaupt willen vergelijken stelt weinig voor: ga je ze vergelijken op bestandsgrootte, naam, aantal pixels? Ik zou iets specifieker zijn

[S_tef]

Oke op die fiets.
Het is namelijk zo. Ik haal informatie uit verschillende rss feeds, in deze rss feeds staan foto's.
In 2 verschillende rss feeds kan hetzelfde product staan, echter met andere (of dezelfde dus) foto's. Ik wil dus de fotos die in feed 1 staan en in feed 2 weggooien (ik wil alle fotos opslaan behalve de dubbele).

De fotos zijn puur te herleiden aan hoe ze uit zien.

[Delusion]

mithras schreef op donderdag 20 augustus 2009 @ 20:58:
Tja, het ligt er natuurlijk ook aan wat je wil met vergelijken. Als ik twee foto's los achter elkaar neem, wil je die dan kunnen vergelijken en concluderen dat ze "gelijk" zijn? Of als ik een n * m bitmap maak waarin alle pixels een waarde hebben en ze daarbij bitwise vergelijken?

Het uberhaupt willen vergelijken stelt weinig voor: ga je ze vergelijken op bestandsgrootte, naam, aantal pixels? Ik zou iets specifieker zijn

Ik vroeg mij af hoe / of het mogelijk is om in PHP, 2 (externe) afbeeldingen met elkaar te vergelijken (dus qua uiterlijk).

[ProperChaos]

Je kunt beide images in arrays zetten, en dan gewoon de R, G, en B channels vergelijken. Stel je hebt bijvoorbeeld bij de eerste image, 120,152,242 en bij de 2e 121,154,246 en je hebt de tolerance op 2, dan is de pixel gelijk, zijn alle pixels gelijk, dan is het hetzelfde plaatje. Eventueel bouw je ook nog een tolerance in voor het aantal foute/gelijke pixels.

Je kan ook de gemiddelde kleur pakken van beide images, maar dat is minder nauwkeurig.

EDIT: Je kan ook zoeken naar pattern recognition (http://www.catenary.com/howto/findmark.html) bijvoorbeeld, als de ene image een crop is van de ander.

[ Voor 14% gewijzigd door ProperChaos op 20-08-2009 21:04 ]

[mithras]

S_tef schreef op donderdag 20 augustus 2009 @ 21:00:
Oke op die fiets.
Het is namelijk zo. Ik haal informatie uit verschillende rss feeds, in deze rss feeds staan foto's.
In 2 verschillende rss feeds kan hetzelfde product staan, echter met andere (of dezelfde dus) foto's. Ik wil dus de fotos die in feed 1 staan en in feed 2 weggooien (ik wil alle fotos opslaan behalve de dubbele).

De fotos zijn puur te herleiden aan hoe ze uit zien.

Kunnen de foto's verschillen van formaat (jpeg/png) en/of geresized zijn?

De eerste check kan natuurlijk eenvoudig: als de bestandsgrootte exact hetzelfde is, bereken je een hash van de images en vergelijk je die. Dat is de meest snelle optie en sluit je direct het meest eenvoudige geval uit.

Daarna kan je beginnen met het vergelijken van uiterlijk op basis van bijv. rgb gegevens. Je kan ook al een hoop info halen uit de Fourier getransformeerde afbeelding. Maar misschien is het handig om om de afbeelding in een 10 x 10 rooster te snijden en daarbij de gemiddelde kleur van dat vak te bepalen. Met een foutmarge van 10% vergelijk je dan vak voor vak. Als alle vakken afzonderlijk binnen de foutmarge gelijk zijn, kan je zeggen dat ze gelijk zijn.

Er zijn nog wel veel meer opties mogelijk, maar zoals ik jouw case lees is een kort-foor-de-bocht methode met meest gemakkelijk omdat hier de kans op false positives niet heel erg groot is.

@Delusion: oeps my fault

[Hydra]

Je kunt ook als de images even groot zijn elke 4e pixel ofzo vergelijken in plaats van elke pixel. Scheelt een hoop tijd, en het effect is hetzelfde.

[roy-t]

als het exact dezelfde afbeeldingen zijn en alleen de filename anders is kun je dan niet gewoon de checksums vergelijken?

[HuHu]

Ik zou het niet in PHP doen en ook niet zelf gaan maken. PHP is niet echt een handige keuze hiervoor en zelf maken is alleen maar veel werk op je hals halen.

Je hebt een prachtig programma, genaamd ImageMagick, dat een optie "compare" biedt. Installeer ImageMagick op je server, roep vanuit PHP het compare commando aan en je krijgt je resultaat vanzelf terug.

Weinig moeite, efficiënt geïmplementeerd en waarschijnlijk ook beter dan je het zelf zou doen.

[HuHu]

Ow, je vindt het dus hier: http://www.imagemagick.org/script/compare.php

[Verwijderd]

eeuuhh md5je van trekken en vergelijken? of ben ik nu dom bezig. het lijkt me denk ik sneller dan pixel voor pixel vergelijken.

[RobIII]

Verwijderd schreef op vrijdag 21 augustus 2009 @ 22:11:
eeuuhh md5je van trekken en vergelijken? of ben ik nu dom bezig. het lijkt me denk ik sneller dan pixel voor pixel vergelijken.

Een MD5 ragt ook over elke byte heen en laat er ook nog eens een berekening op los; links met rechts comparen is dus gewoon goedkoper en sneller.

Maar dan heb je dus een bit-voor-bit vergelijking; als je "op het oog gelijke afbeeldingen" wil vergelijken dan kom je niet zo makkelijk ermee weg

[HuHu]

Goedkoper en sneller hoeft niet per se hoor. Als je links met rechts gaat vergelijken moet je beide afbeeldingen in het geheugen houden en pointers naar de huidige pixel in beide afbeeldingen. Bij een MD5 heb je maar 1 afbeelding tegelijk in het geheugen en kun je sequentieel door de afbeelding heen lopen.

Bij het vergelijken van pixel-met-pixel moet je steeds eerst de ene en dan de andere opvragen. Dat is voor het geheugen minder efficiënt, zowel voor het steeds heen-en-weer springen als het gelijktijdig in het geheugen hebben van beide afbeeldingen.

Verder kun je een MD5 ook makkelijk opslaan voor hergebruik. Dus als je 100 afbeeldingen hebt die je allemaal met elkaar wilt vergelijken, of 1 afbeelding die je wilt zoeken in een set van 100, dan is het handig als je alle hashes al voorhanden hebt en je niet steeds de vergelijking op de afbeelding opnieuw hoeft te doen.

Aangezien S_tef aangeeft afbeeldingen via een feed binnen te krijgen ga ik er vanuit dat hij steeds 1 afbeelding zoekt in een set. Dan zou ik gaan voor het opslaan van features of een hash in een database, zodat je daar snel in kunt zoeken.

[roy-t]

Verwijderd schreef op vrijdag 21 augustus 2009 @ 22:11:
eeuuhh md5je van trekken en vergelijken? of ben ik nu dom bezig. het lijkt me denk ik sneller dan pixel voor pixel vergelijken.

kijk eens ietjes hoger

*Oops *

[ Voor 3% gewijzigd door roy-t op 22-08-2009 19:14 ]

[mithras]

roy-t schreef op zaterdag 22 augustus 2009 @ 16:28:
[...]


kijk eens ietjes hoger

Had ji ook wel even kunnen doen

Maar om er nog iets nuttigs van te kunnen maken: is de TS hier nu bij geholpen? Er zijn veel oplossingen aangedragen maar TS is verdwenen

[Data-base]

Uit de losse pols, dus bind me er neit op vast:

- Pak het kleinste plaatje van de twee.
- Ga deze pixel voor pixel af
- Zoek per pixel de "bijbehorende" pixels (d.m.v. grootte-verhouding) in de grote foto *
- Bereken daar de gemiddelde kleur van
- Vergelijk de gemiddelde kleur met de kleur van de pixel uit de kleinere foto (evt met bepaalde tolerantie)

* Stel ene foto1 is 50x50px breed en foto2 is 100x100px breed, dan hoort bij pixel (0,0) op foto1 de pixels (0,0),(0,1),(1,0),(1,1). Simpel gezegd omdat iedere pixel in foto 1 door 2 keer zoveel pixels wordt voorgesteld.

Vraag blijft nog wel waarom je dit idd in php zou doen. Het feit dat je php kán misbruiken voor dit soort dingen wil niet zeggen dat je dat moet doen
Doe het in je favo "native" taal (c(++), c#, vb, java, delphi) en het is een factor 10 sneller (als het niet meer is).

[ Voor 18% gewijzigd door Data-base op 22-08-2009 19:22 ]

[doeternietoe]

Data-base schreef op zaterdag 22 augustus 2009 @ 19:20:
Doe het in je favo "native" taal (c(++), c#, vb, java, delphi) en het is een factor 10 sneller (als het niet meer is).

Allereerst is het nog maar de vraag hoe "native" talen zoals c#, vb en java zijn. Als tweede heeft niet iedereen een favo "native" taal, veel mensen leren nooit zo'n taal. Als derde, als het toch al niet meer in PHP moet gebeuren gebruik dan gelijk een goede externe library/tool. Er zijn voor dit soort problemen professionals geweest die er veel langer en dieper over hebben kunnen nadenken dan je je als hobbyist kunt veroorloven.

To the point:
Voor het geval het in PHP moet, zie ik overigens wel een probleem. Als je 30 000 afbeeldingen allemaal stuk voor stuk met elkaar gaat vergelijken zijn dat heel veel vergelijkingen. Om precies te zijn 0,5 * 30000^2 + 0,5 * 30000 = 449 905 000 vergelijkingen. Zelfs als een dubbele is gevonden kun je de vergelijkingen niet afbreken, omdat er een afbeelding driedubbel in kan zitten.

Krap een half miljard keer twee afbeeldingen pixel voor pixel vergelijken in de taal PHP kun je wel vergeten. In een native taal zal het overigens ook niet snel genoeg zijn. Een wat globalere vergelijking op basis van de gemiddelde kleur van een vlak van bijvoorbeeld 50*50 pixels is al wat sneller, maar waarschijnlijk nog niet snel genoeg.

Het enige werkbare algoritme dat ik me kan bedenken is een soort top-down-processing. Je genereert van 30 000 afbeeldingen de gemiddelde kleur over de gehele afbeelding en bewaart deze. Je groepeert afbeeldingen waarvan de gemiddelde kleur zeer dicht bij elkaar ligt. (uiteraard mogen/moeten deze groepen overlappen) Binnen deze groepen kun je een wat meer gedetailleerder vergelijking toepassen.

Aangezien de gemiddelde kleur over een gehele afbeelding waarschijnlijk een bepaalde grijstint is en er mogelijk maar heel weinig variatie per afbeelding bestaat kun je ook een bepaalde, willekeurige uitsnede nemen.

Maar overweeg om een externe tool te gebruiken, want een snel algoritme voor dit soort problemen heb je niet één twee drie en het maken ervan kun je waarschijnlijk beter overlaten aan mensen die er echt goed in zijn en in de juiste taal kunnen programmeren.

[ Voor 5% gewijzigd door doeternietoe op 22-08-2009 23:37 ]

[S_tef]

Bedankt voor de reacties.
Ik zie veel imo goede ideeen met veel leesvoer. Ikzelf wist niet hoe ik hier aan moest beginnen maar ik zal sowieso zo minst geavanceerd mogelijk beginnen.

Echter zal het in PHP moeten, de afbeeldingen zullen niet veel van elkaar verschillen (alleen kwaliteitsverschil) en kunnen inderdaad een crop zijn van de andere...

[Janoz]

Dat ze niet veel van elkaar verschillen maakt het inderdaad een stuk makkelijker, maar dat ze gecropped kunnen zijn maakt het eigenlijk met de gegeven aantallen en de beperking tot php zo goed als onmogelijk.

[roeleboel]

vermits je hier per se met php wil/moet werken, en je dus met de bijhorende beperkingen zit, kan je het misschien op deze wijze implementeren:
- maak een gesorteerde lijst van je afbeeldingen
neem afbeelding 1, match tegen alles wat er achter komt in de lijst, als ge een match vindt: opslaan & lijst verder afwerkern
neem nu afbeelding 2, ...

voordeel: altijd maximum 2 afbeeldingen in het geheugen geladen, dus de meeste web-servers gaan daardoor al niet plat.
nadeel: dit is een manier die extreem lang zal duren... (dus zie dat ge de timeout voor php-scripts op quasi oneindig zet :-) Met name n! als ik me niet vergis.
Bijkomend iets: je kan, omdat je toch 'maar' 2 afbeeldingen tegelijk ingeladen hebt meerdere instanties van het script tegelijk opstarten. (de eerste doet de eerste 100, 2e de volgende 100, etc etc).

[frickY]

Converteer de afbeelding naar een bestandformaat welke de data per pixel opslaat, zoals bijvoorbeeld BMP, en gooi daar een str_compare overheen?

[Gomez12]

Tsja, mits ze geen watermarks etc bevatten zou ik zelf gewoon in een 1e slag van alle 4 de hoeken 1 pixel en in het midden 1 pixel pakken, deze kleurwaardes sla je in je dbase op.

Met elke nieuwe afbeelding pak je dezelfde pixels en dan zoek je alle bestaande afbeeldingen ( binnen tolerantie waarden ) met dezelfde kleurwaardes op en enkel hiermee ga je vergelijken.

Dit limiteert je aantal vergelijkingen drastisch.
Sampleset kan je uiteraard zo groot / klein maken als je zelf wilt ( vooral de pixel in het midden is tricky, bij een gecropte image kan het midden net iets anders uitkomen )

Het voornaamste is imho om je aantal te vergelijken afbeeldingen zo snel zo klein mogelijk te krijgen

[Hydra]

S_tef schreef op zondag 23 augustus 2009 @ 07:23:
Echter zal het in PHP moeten, de afbeeldingen zullen niet veel van elkaar verschillen (alleen kwaliteitsverschil) en kunnen inderdaad een crop zijn van de andere...

Oh, crops zijn al een stuk lastiger. Puur verkleiningen zijn best aardig te doen omdat je ze voor 't vergelijken terug kan scalen, maar in het geval van crops moet je eerst de kleinere afbeelding opzoeken in de grotere. Da's lastig

frickY schreef op zondag 23 augustus 2009 @ 11:46:
Converteer de afbeelding naar een bestandformaat welke de data per pixel opslaat, zoals bijvoorbeeld BMP, en gooi daar een str_compare overheen?

Heel grappig. Not.

[S_tef]

Hydra schreef op maandag 24 augustus 2009 @ 10:59:
Oh, crops zijn al een stuk lastiger. Puur verkleiningen zijn best aardig te doen omdat je ze voor 't vergelijken terug kan scalen, maar in het geval van crops moet je eerst de kleinere afbeelding opzoeken in de grotere. Da's lastig

Mmm bedacht me net, het zijn inderdaad geen crops maar verkleiningen .
Dus dan zou het efficiëntste zijn als ik alles terug scale naar het kleinste formaat per item en deze dan pixel voor pixel vergelijken met een tolerantie?

[Janoz]

Niet gecroppde afbeeldingen maakt het alvast weer een stuk makkelijker


Hoe ik het zou aanpakken:

Uit je verhaal begrijp ik dat er steeds meer afbeeldingen bijkomen. Ikzelf zou dan ook bij het binnenkomen de check loslaten. Het voordeel is dan dat je niet alles met alles vergelijkt, maar 1 met alles.

Het vergelijken zou ik, zoals ook al eerder aangegeven, doen met een controle waarmee je heel snel ongelijke afbeeldingen kunt negeren. Ikzelf zou alle afbeeldingen herschalen naar 16x16 (dus met verlies van aspect ratio!) grijswaarde plaatje. In dat geval heb je dus 256 bytes die een ruwe weergave van het plaatje zijn. Door het herschalen maakt de afmeting van de afbeelding niet uit, en doordat je er een heel klein grijswaarden plaatje van maakt heb je ook al je fouttollerntie geregeld. Deze 256 bytes zet je gewoon in de database en deze gebruik je om te zoeken naar plaatjes die op het gegeven plaatje lijken. De plaatjes die je nu terugkrijgt kun je vervolgens gebruiken voor een wat uitgebreidere vergelijking (eventueel zet je er nog een stap tussen waarbij je een 256x256 variant opslaat.


Wanneer je ook nog plaatjes wilt kunnen herkennen waar de intensiteit van aangepast is (donkerder of lichter gemaakt) dan zou je je 16x16 plaatje nog kunnen equalizeren.

[Janoz]

Hydra schreef op maandag 24 augustus 2009 @ 10:59:
[...]


Oh, crops zijn al een stuk lastiger. Puur verkleiningen zijn best aardig te doen omdat je ze voor 't vergelijken terug kan scalen, maar in het geval van crops moet je eerst de kleinere afbeelding opzoeken in de grotere. Da's lastig

En dan heb je het nog niet eens over de mogelijkheid dat de gecroppte variant ook nog eens geherschaald zou kunnen zijn.

Heel grappig. Not.

Ja, maar je begrijpt toch wel dat een string compare onmetelijk veel efficienter is dan bytes vergelijken

[ Voor 24% gewijzigd door Janoz op 24-08-2009 14:03 ]

[Hydra]

S_tef schreef op maandag 24 augustus 2009 @ 13:44:
Mmm bedacht me net, het zijn inderdaad geen crops maar verkleiningen .
Dus dan zou het efficiëntste zijn als ik alles terug scale naar het kleinste formaat per item en deze dan pixel voor pixel vergelijken met een tolerantie?

Ik zou de kleinste pakken en deze 'opschalen' naar de grootste. Dus gewoon de pixel x/y vermenigvuldigen met de vergrotingsfactor. Het heeft sowieso geen zin om het andersom te doen, want dan moet je meer pixels bekijken.

Verder zou ik even wat tests maken. Dus even een groot plaatje naar kleiner resizen, met een flinke zware JPG compressie, en kijken hoe hoog de tolerantie moet worden ingesteld. Door zware JPG compressie kunnen artefacten behoorlijke verschillen opleveren.

Janoz schreef op maandag 24 augustus 2009 @ 14:02:
Ja, maar je begrijpt toch wel dat een string compare onmetelijk veel efficienter is dan bytes vergelijken

Precies. Een string-compare is maar 1 call, in plaats van al die duizenden bytes die je moet vergelijken.

[ Voor 16% gewijzigd door Hydra op 24-08-2009 14:05 ]