...

View Full Version : PHP script to match images doesn't work



Macmee
03-11-2010, 08:19 PM
For example, I might have an image here:
http://macmee.com/screenshots/cartoon_house_st5-20100309-204125.png

And I might be looking for the smaller image:
http://macmee.com/screenshots/Screen_shot_2010-03-09_at_8.41.46_PM-20100309-204225.png

within that bigger image. I want to get the x,y coordinates to where that image is in the large one. Here's the source code I have to do this:


<?php
//small image
$im2 = ImageCreateFromPNG("SMALL IMAGE.png");
$width = imagesx($im2);
$height = imagesy($im2);
$size2 = $width * $height;
$cw = 0;
$ch = 0;
$image2 = "|";
for($i = 0; $i < $size2; $i++)
{
$image2 .= imagecolorat($im2, $cw, $ch)."|";
if($cw == ($width - 1))
{
$cw = 0;
$ch++;
}else{
$cw++;
}
}



//large image
$im = ImageCreateFromPNG("BIG IMAGE.png");
$width = imagesx($im);
$height = imagesy($im);
$size2 = $width * $height;
$cw = 0;
$ch = 0;
$image = "";

for($i = 0; $i < $size2; $i++)
{
$image .= imagecolorat($im, $cw, $ch)."|";
if($cw == ($width - 1))
{
$cw = 0;
$ch++;
}else{
$cw++;
}
}


//finding position of patch in strings
$find = explode($image2,$image);
$coordinate = substr_count($find[0], '|');


//converting position from string to x y coordinates
$width = imagesx($im);
$check = $coordinate / $width;
$check = explode(".",$check);
$y = $check[0] + 1;
$x = $coordinate % $width;
if(($coordinate % $width) == 0)
{
$x = $width;
$y--;
}


//printing result
echo "x: {$x}<br>y: {$y}";




?>

I tested each individual component of that manually and they all worked, but when put together it doesn't find the proper coordinates, just bogus ones. If someone could shed some light on this I would really appreciate it :)

Thank you,
Dave Z

mlseim
03-11-2010, 08:41 PM
So you're saying that is compares every pixel in the small image to every pixel
in the large image to figure out where all of the pixels match?

bacterozoid
03-11-2010, 08:53 PM
Dude, your algorithm needs some work. Instead of storing everything in a massive string like that and then using explode, try this:

Load up both your large and small images

Use a loop (two levels deep) to go through every pixel in your large image. If the pixel you are at in your large image matches the top left pixel of your small image, then step into a verify subroutine

The verify subroutine would then check the other pixels to see if they are a match. You could probably get away with checking a fairly low percentage of pixels - maybe check a grid with 10px in between each. This would depend on the desired size of your small image, but you should be able to get pretty good results (and much more efficiently)

bacterozoid
03-11-2010, 09:26 PM
Because I thought the problem to be interesting and because you already tried yourself, here's one way to do it:


<?php

// Large Image
$big = ImageCreateFromPNG("big.png");
$big_w = imagesx($big);
$big_h = imagesy($big);

// Small Image
$small = ImageCreateFromPNG("small.png");

// Loop over every pixel in the large image
for($cy = 0; $cy < $big_h; $cy++) { // This loops over vertically
for($cx = 0; $cx < $big_w; $cx++) { // This loops over horizontally
if(imagecolorat($big, $cx, $cy) == imagecolorat($small, 0, 0)) { // See if the current pixel in the large image matches the top left pixel in the small one
if(verify($cx, $cy, $big, $small)) { // If there is a potential match, verify if it is a full match
die("X=$cx, Y=$cy"); // If it is a full match, stop doing work and output the result
}
}
}
}
echo "Not Found"; // No match found

// Check and see if the given cx, cy position is a match
function verify($cx, $cy, &$big, &$small) { // The & passes by reference...basically just saves you memory
$small_w = imagesx($small);
$small_h = imagesy($small);

// Use the threshhold to prevent checking every single pixel. It can be assumed that if you
// have a spaced out grid of matches, you are pretty close
$threshhold = 20;
for($sy = 0; $sy < $small_h; $sy+=$threshhold) {
for($sx = 0; $sx < $small_w; $sx+=$threshhold) {
if(imagecolorat($small, $sx, $sy) != imagecolorat($big, $cx + $sx, $cy + $sy)) {
return false;
}
}
}
return true;
}

?>

Macmee
03-12-2010, 12:47 AM
Because I thought the problem to be interesting and because you already tried yourself, here's one way to do it:


<?php

// Large Image
$big = ImageCreateFromPNG("big.png");
$big_w = imagesx($big);
$big_h = imagesy($big);

// Small Image
$small = ImageCreateFromPNG("small.png");

// Loop over every pixel in the large image
for($cy = 0; $cy < $big_h; $cy++) { // This loops over vertically
for($cx = 0; $cx < $big_w; $cx++) { // This loops over horizontally
if(imagecolorat($big, $cx, $cy) == imagecolorat($small, 0, 0)) { // See if the current pixel in the large image matches the top left pixel in the small one
if(verify($cx, $cy, $big, $small)) { // If there is a potential match, verify if it is a full match
die("X=$cx, Y=$cy"); // If it is a full match, stop doing work and output the result
}
}
}
}
echo "Not Found"; // No match found

// Check and see if the given cx, cy position is a match
function verify($cx, $cy, &$big, &$small) { // The & passes by reference...basically just saves you memory
$small_w = imagesx($small);
$small_h = imagesy($small);

// Use the threshhold to prevent checking every single pixel. It can be assumed that if you
// have a spaced out grid of matches, you are pretty close
$threshhold = 20;
for($sy = 0; $sy < $small_h; $sy+=$threshhold) {
for($sx = 0; $sx < $small_w; $sx+=$threshhold) {
if(imagecolorat($small, $sx, $sy) != imagecolorat($big, $cx + $sx, $cy + $sy)) {
return false;
}
}
}
return true;
}

?>

That works beautifully, thank you :) The only part I don't understand is in your for statement in the verify function where you put +=


Dude, your algorithm needs some work. Instead of storing everything in a massive string like that and then using explode, try this:

Load up both your large and small images

Use a loop (two levels deep) to go through every pixel in your large image. If the pixel you are at in your large image matches the top left pixel of your small image, then step into a verify subroutine

The verify subroutine would then check the other pixels to see if they are a match. You could probably get away with checking a fairly low percentage of pixels - maybe check a grid with 10px in between each. This would depend on the desired size of your small image, but you should be able to get pretty good results (and much more efficiently)

Thanks, I never thought of doing it like that :D

mlseim
03-12-2010, 12:52 AM
This:
$sy += $threshhold;

Is shorthand for this:
$sy = $sy + $threshhold;

Macmee
03-12-2010, 01:04 AM
This:
$sy += $threshhold;

Is shorthand for this:
$sy = $sy + $threshhold;

Ooh ok. So when it's verifying it's actually moving 20 pixels across and 20 pixels down to continue each pixel check?

bacterozoid
03-12-2010, 03:18 AM
Yep. This way you're not checking every single pixel - your script will complete quicker and use less resources.

Skipping every 20px (at least on an image this size) should generally be good enough to detect a match, as the likliehood of that happening anywhere else in the image is pretty low. If you have problems, just decrease that threshold value.



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum