Thread: algorithm hint needed. please.

So what are your thoughts? How would you compare a flipped [upside down or left to right] image with one that is "unflipped"?

I can think of two immediate approaches, but there are probably some others too.

--
Mats

How efficient does it have to be? How many of these images do you have to compare?

By the way, if we assume that the . and o are zero and one respectively, you could use a single 32-bit integer to store the values, as a 5 x 5 matrix is only 25 bits. So the actual compare will be one 32-bit compare. Rotations will still be somewhat complicated no matter how you store the data tho, and I'm not sure it's more efficient to use a single integer than to compare an array of 5 x 5 values.

--
Mats

Thanks matsp.
My fault! I admit!
I used a 5x5 grid since it could fit in my post
Actually I wanted to compare large bitmaps which will obviously have much bigger dimensions.
Also I don't have a mathematician's brain. So can't tell how many grids will I get if I do all possible
rotations/flips/mirrors to cover up every case!
And then compare them all with my next input grid to check for a match

Edit:
Thanks Adak, I am not sure how many such combinations will be there!

There are four rotations (3 plus the original), + 1 (more) vertical positions, + 1 (more) mirrored position.

I'm thinking that the 180 degree rotation, will be the same image as the vertical flip position, however.

So 5.

The biggest gain in efficiency would surely be to quit the comparison the first moment that it shows you do not have
a match. That will save a TON of work.

So how large are your grids, and how many do you need to compare, and how long is it allowed to take?

There are obviously 4 rotations [well, three plus the current one], so you have:
Rotate 0 degrees
Rotate 90 degrees
Rotate 180 degrees
Rotate 270 degrees

Mirror/flip types:
Not mirrored
Mirrored vertical
Mirrored horizontal
Mirrored horizontal and vertical

So you have 4 * 4 => 16 different variants [and of course, on average, you should only have to compare half of those if the images are of random distribution of rotation].

If you know that they are more likely to be some particular rotation/flip variant, then perhaps you should make sure that's the first one you compare.

If this is a large project with a long runtime, it may be good to track the hit rate for each rotation alternative, and if you have multiple "standard" images, which ones are more likely to occur - e.g if you compare letters in English, "e","s","a", "t" and "r" are more likely than most others, so should be compared before you go on comparing with "k" or some such [the value in Scrabble is a good guide for how common words are with those letters].

--
Mats

Originally Posted by manav

Code:

Rotations - Clockwise

o o .
o . .
o . .

o o o
. . o
. . .

. . o
. . o
. o o

. . .
o . .
o o o

Mirrors
o o . | . o o
o . . | . . o
o . . | . . o

o o . duplicate of #1
o . .
o . .
-----
o . .  OK, my error - vertical flip is valid, so increase possible positions to 6
o . .
o o .

. o o | o o . These are a repeat of Mirrors, not valid.
. . o | o . .
. . o | o . .

o . .  This is a repeat of vertical flip, above.
o . .
o o .
-----
o o . This is a repeat of the original
o . .
o . .

And what if they are rotated and then mirrored and so on . . .
I mean multiple operations!

You're thinking too hard! You have duplicate positions up there. There are now just 6 positions. You can flip and mirror to your heart's content. The possible positions won't change once we've nailed down the correct number.

OK, got two more positions: since the vertical flip is valid, two angled flips should be valid, as well.

1) Along a 2:30 o'clock ray (bottom left corner to upper right corner).
2) Along a 10:30 o'clock ray (bottom right corner to upper left corner)

Both the above are both vertical and horizontal turns.

So we're up to 8 possible positions.

Originally Posted by manav

You are right Adak. May be I am thinking too hard!

But how to visualize all combinations. The example shown in post contained a simple bitmap with only 3x3 size.
What if the bitmap was bigger and more complex?
For a simple example:
H will remain same in vertical flip, horizontal flip, only two possible orientations by rotating.
But same is not true for Q.
And what if the bitmap contained a really complex image of some not so symmetrical structure!

I believe you can visualize any solid 2D object, like the 2D array. Say, a piece of square wood. Now mark it up, and move it all around. How many different ways can it be moved, and still show the top side (with the markings), face up?

It doesn't matter how many times you flip it - vertical, horizontal, by the diagonal corners, rotating it, etc., there are a small number of ways that it can be done so as to be a unique face as you look at it's top surface markings.

An irregular shaped 2D array can only be moved / flipped / rotated, in the same ways as a regular shaped 2D array. It still only has 2D's.

I'm sure you won't be able to use the reduced positions of "H" shapes, to your advantage. That's just because our grid's here, are very small. On larger grids, it just wouldn't be worth it to start "fishing" for some odd shape, imo.

As the grid's get larger, I'd think about doing a part of the grid at a time (so it could all fit nicely into memory and not require a swap file). Since most images have their subject within a "Golden Rectangle" of the center of the image, it might be good to start in that area of the image.

I wouldn't worry (right now) about the possibility that the flipped image is the same as the unflipped one. H will match a flipped H, but you never get there [I'm assuming you don't need to compare the rest of the possible positions if you have a match].

I'm also assuming that we KNOW that the image is only rotated/flipped in right-angles, or possibly a 45 degree angle [both left/right and up/down flip]. Of coruse, if you can flip around an arbitrary axis, or rotate it an arbitrary amount, then you have an infinite number of possibilities.

What difference does it make if the image is more complex - you are still just comparing 16 variants of rotation of the image.

--
Mats