1. ## algorithm hint needed. please.

Hi all.
Sorry if it does not fit here. But I am writing in C so I thought post it here. Sorry.
I am writing a program in C that reads a grid of 5x5 in a 2D char array:
An example:
Code:
```o o o o o
. . o . .
. . o . .
. . o . .
. . o . .```
And then it reads some more grids of 5x5 size.
My objective is to tell if they match the first grid.
Now the problem is:
I should be able to match them even if they are rotated/flipped/mirrored!

I am not asking for a code or any such help. This is also not my home work.
I just want to now if it is a similar problem to some already solved problem?
Is there already an algorithm that will help me solve this problem?

2. 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

3. I wanted to do a brute force method.
I would store all rotations of the first input grid and later compare every other input grid with my own rotations.
While I was thinking about rotations only, it seemed to work fine.
But then I thought what if they are mirrored/flipped as well.
I guessed this brute force could be very unefficient. So I am looking for an algorithm which will help me doing this.
Easier and maybe more efficient.

4. 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

5. As a hobby programmer only, I've come up with just one way to do this.

1) Rotate the matrix all around, then flip it, then mirror it, while testing it at each position.

Sounds quite slow, but from experience, I know it's blindingly fast.

Matrix manipulations has been heavily studied. Just not by me!

6. Thanks matsp.
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!

7. 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.

8. 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 .
o . .
o . .
-----
o . .
o . .
o o .

. o o | o o .
. . o | o . .
. . o | o . .

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

9. 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

10. 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.

11. Thanks matsp.
Another example:
Code:
```Original:
o o .
o . .
o . .

Flipped:
o o . | . o o
o . . | . . o
o . . | . . o

Rotated - Clockwise:
. . .
. . o
o o o```

12. 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!

13. 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.

14. 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

15. In these images, are we assuming that the "back" of the image is actually the same as the "front"?

Because when I turn a photo over, I don't see the image any more. Are these bitmaps going to show a "front" even when we've flipped them over, to their back's side?