9 replies to this topic

[brownhead]

I'm trying to create a function that will tell me if two monochrome (black and white) bitmaps are similar. By similar, I mean that one of the bitmaps can be a rotated or scaled version of the other. But any scaling that occurs will have a 1:1 ratio.

My first idea was to essentially create a circle that encompasses the entire image, and then draw a straight line from one end of the circle, through the center, to another end, and count the number of pixels it encounters. Once it gets that number, it divides the number by the maximum possible (the distance between the top left corner and the bottom right corner of the image). Then repeat the process 360 times. Then do this again for the other image and compare the two arrays of numbers. Then it's a matter of comparing the arrays by offsetting one of them 360 times and I figured that one of the comparisons should return true. But it isn't, the method doesn't seem to be working how I thought it would.

Does anybody know of a better way to do this? The code I have at the moment is below.

#include <math.h>

#include <iostream>


unsigned char* cluster::getRotationBuffer()

{

    unsigned char* hash = (unsigned char*)calloc(180, sizeof(unsigned char));


    for (double i = 0; i < 360; i += 2)

    {

        double x = cos(i) + 1;

    	double y = sin(i) + 1;

    	//x += (x < 0 ? -1 : 1);

    	//y += (y < 0 ? -1 : 1);


    	onyxNumber counter = 0;


    	for (double iy = height / 2.0, ix = width / 2.0; iy < height && ix < width && iy > 0.0 && ix > 0.0; iy += y, ix += x)

    	{

            if (getBit((int)round(ix), (int)round(iy))) ++counter;

    	}


        for (double iy = height / 2.0, ix = width / 2.0; iy < height && ix < width && iy > 0.0 && ix > 0.0; iy -= y, ix -= x)

    	{

            if (getBit((int)round(ix), (int)round(iy))) ++counter;

    	}


    	hash[(int)i / 2] = (unsigned char)((counter / (double)sqrt(width * width + height * height)) * 100.0);

    }


    for (int i = 0; i < 180; ++i)

    {

    	std::cout << (int)hash[i] << ", ";

    }

    std::cout << "\n\n";


    return hash;

}


bool cluster::compare(cluster zvalue)

{

    unsigned char* hash = getRotationBuffer();

    unsigned char* hash2 = zvalue.getRotationBuffer();


    for (onyxNumber j = 0; j < 180; ++j)

    {

  	    onyxNumber counter = 0;

        for (onyxNumber i = 0; i < 180; ++i)

        {

            if (abs((int)hash[i] - (int)hash2[(i + j) % 180]) > 5) ++counter;

        }


        if (counter < 30) std::cout << "Matching at offset " << j << ". Counter = " << counter << "\n"; else std::cout << j << " - Counter = " << counter << "\n";

    }


    free(hash);

    free(hash2);

    return false;

}

[BlaineSch]

Hey Brownhead, not seeing you too much on the forums anymore haha

Anyway, if you can get the pixel color, black or white, and add basically "same" and "different" then just find a good ratio of what is "similiar"

Not done too much of comparing images like this besides md5 lol

I would be very interested in knowing how you did it though =)

[WingedPanther]

Maybe I'm looking at this too simply, but are you allowing something besides a rotation of 90, 180, or 270 degrees?

Also, a scaling of 1:1 means no scaling, doesn't it?

[brownhead]

Hi Blaine, I've been really busy with work :(, just recently I've had some time for my pet project. And MD5 wouldn't work in this case, but a different hashing algorithm could, I wouldn't know how to write it though.. It'd have to be specially made for monochrome bitmaps (or it could work even if it was meant for regular bitmaps, but it depends).

And WingedPanther, I'm allowing for any degree of rotation, or at least trying to. And as for scaling, by a 1:1 ratio I mean that if you had a 25x25 image and you scaled it, it'd be something like 100x100, or 125x125. 1:1, both width and height were multiplied by the same number.

Thanks for your replies guys, I hope I can get this figured out.

[WingedPanther]

If you assign every pixel a coordinate from the center, you can use matrix multiplication to get a scaled, rotated pixel location.
Transformation matrix - Wikipedia, the free encyclopedia

[brownhead]

If I'm understanding you correctly your suggesting rotating the image 360 times and doing a simple bit to bit comparison of the second image. There's a couple problems I was thinking I'd run into if I tried that though. The first would be a time constraint, rotating an image 360 times and running 360 comparisons would be time consuming. Second, I'm not sure how I would account for any scaling.

Thanks for the reply.

[WingedPanther]

Unfortunately, the problem is non-trivial to begin with :(

[brownhead]

Indeed :(. I can't seem to wrap my head around it.

[brownhead]

Well it seems that in my infinite wisdom I made a simple math mistake. I had added 1 to both the x and y offset, which does not do what I meant it to do. I was also giving sin() and cos() degree values as degrees when they expected radians. I think that's the 100th time I've done that in my code -_-. But I've managed to fix it and it works well :). Below is the code, it should be portable to anyones project (as long as you replace getBit with your function). Thanks for your help everyone :)!

unsigned char* cluster::getRotationBuffer()
{
    // PI divided by 180. Needed to convert between degrees and radians
    const double pi180 = 3.14159265 / 180.0;

    unsigned char* hash = (unsigned char*)malloc(180 * sizeof(unsigned char));

    for (double i = 0; i < 180; i += 1)
    {
        // The x and y offsets
        double ox = sin(i * pi180) * 2;
    	double oy = cos(i * pi180) * 2;

        // Holds the number of times a set bit is encountered
    	onyxNumber counter = 0;

        // Scan half of the diameter
    	for (double iy = height / 2.0, ix = width / 2.0; iy < height && ix < width && iy > 0.0 && ix > 0.0; iy += oy, ix += ox)
            if (getBit((int)round(ix), (int)round(iy))) ++counter;

        // Scan the other half
        for (double iy = height / 2.0, ix = width / 2.0; iy < height && ix < width && iy > 0.0 && ix > 0.0; iy -= oy, ix -= ox)
            if (getBit((int)round(ix), (int)round(iy))) ++counter;

        // Add it to the list
    	hash[(int)i] = (unsigned char)((counter / ((double)sqrt(width * width + height * height) / 2)) * 100.0);
    }

    return hash;
}

bool cluster::compare(cluster zvalue)
{
    // Get the rotation buffers
    unsigned char* hash = getRotationBuffer();
    unsigned char* hash2 = zvalue.getRotationBuffer();

    // Holds the mots likely match
    onyxNumber min = onyxNumberMax;
    onyxNumber minDegree = 0;

    // Loop through the two buffers to compare them with eachother with every possible offset
    for (onyxNumber j = 0; j < 180; ++j)
    {
        // Holds the number of mismatches
  	    onyxNumber counter = 0;

  	    // Loop through the two arrays with the current offset and count the number of mismatches
        for (onyxNumber i = 0; i < 180; ++i)
            if (abs((int)hash[i] - (int)hash2[(i + j) % 180]) > 10) ++counter;

        // If we have a new min value, set it
        if (counter < min)
        {
            min = counter;
            minDegree = j;
        }
    }

    // Free our data
    free(hash);
    free(hash2);

    // 30 might not be a good threshold, if results are erronous, look here first
    return (min < 30);
}

Edited by brownhead, 14 August 2009 - 04:12 PM.

[WingedPanther]

Cool! I'm glad you got it working :)