algorithm hint needed. please.

This is a discussion on algorithm hint needed. please. within the C Programming forums, part of the General Programming Boards category; Hi all. Sorry if it does not fit here. But I am writing in C so I thought post it ...

  1. #1
    Banned
    Join Date
    Nov 2007
    Posts
    678

    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. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #6
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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!
    Last edited by manav; 01-10-2008 at 04:29 AM.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 01-10-2008 at 04:34 AM.

  8. #8
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by manav View Post
    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.
    Last edited by Adak; 01-10-2008 at 04:59 AM.

  11. #11
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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. #12
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by manav View Post
    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.
    Last edited by Adak; 01-10-2008 at 05:18 AM.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithm needed!
    By Warlax in forum C++ Programming
    Replies: 6
    Last Post: 05-11-2006, 12:42 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Algorithm needed
    By sean in forum C++ Programming
    Replies: 17
    Last Post: 08-22-2002, 07:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21