Help with a 2D array algorithm

Question

I'm working on a program that combines two images together in the best possible way. Let's say I have two 2D arrays containing "pixel" structures that make up these two images.

I have already written the algorithm that determines where to join the images together relative to the larger of the two images in terms of "x" and "y", where x is the column and y is the row of the larger image's 2D array. The point in which they should be joined is encapsulated in a "match" structure, which looks like this:

typedef struct {
    int overlap;       // used in algorithm to determine where to combine
    int x;             // column of larger image
    int y;             // row of larger image
    int overlapWidth;  // width of the overlap between the two images
    int overlapHeight; // height of the overlap between the two images
} match;

Note that the matching point could be negative (x, y, or both) relative to the larger image.

The pixels contained in the overlap are averaged and any pixels outside of the two images (but still within the new dimensions) are white.

Example

 +---+---+ image1
 |   |   |
 +---+---+---+ image2
 |   | X |   |
 +---+---+---+
     |   |   |    
     +---+---+

X represents the match point for these two images, so its state looks like this:

x = 1
y = 1
overlapWidth = 1
overlapHeight = 1

The new image for this case would be 3x3.

Assuming, then, that I have the "match" in which to join the two images together, the calculated new width and height of the resulting image, and an allocated 2D array for the resulting image based on these new dimensions, I'm wondering how I could put the appropriate pixels into the new image. Below is some pseudocode that represents what I'm trying to do.

Pseudocode

FOREACH row in new_height
    FOREACH col in new_width
        IF larger_image AND smaller_image do not contain (row,col)
            add white pixel
        ELSE IF overlap contains (row,col)
            add average of pixels
        ELSE IF only larger_image contains (row,col)
            add larger_image pixel
        ELSE
            add smaller_image pixel

I'm having a hard time coming up with a way to do this. I'm not necessarily looking for code, I'm just looking for ideas on how I could do what I'm talking about. Any thoughts would be appreciated.

Markus Jarderot · Accepted Answer · 2011-02-27 03:50:44Z

To check which image(s) (row,col) belongs to, you could use this algorithm. I needed to have the sizes of the big and small images; Thus the extra parameters.

INPUT: row, col, match, big, small
if match.x < 0 then
    // offset of big image, in case small one is to the left
    offsetx <- -match.x
if match.y < 0 then
    // offset of big image, in case small one is above
    offsety <- -match.y
if offsetx <= col and col < offsetx + big.width then
    if offsety <= row and row < offsety + big.height then
        hitBig <- true
        coordBig <- (col - offsetx, row - offsety)
if offsetx + match.x <= col and col < offsetx + match.x + small.width then
    if offsety + match.y <= row and row < offsety + match.y + small.height then
        hitSmall <- true
        coordSmall <- (col - offsetx - match.x, row - offsety - match.y)
return hitBig, coordBig, hitSmall, coordSmall

All coordinates is relative to the new image. If the small image is above and to the left, it will be at (0,0) in the new image, and the big image is pushed down and right.

mgiuca · Accepted Answer · 2011-02-27 01:51:38Z

Your pseudocode looks correct. Are you just having trouble translating it into C?

Firstly, your pseudocode uses the word "add" which implies that the pixel is being put into some new array, but it doesn't specify where this array comes from. So allow me to expand your pseudocode a bit:

Create a new_image
FOREACH row in new_height
    FOREACH col in new_width
        IF larger_image AND smaller_image do not contain (row,col)
            in new_image, set (row,col) to white pixel
        ELSE IF overlap contains (row,col)
            in new_image, set (row,col) to average of pixels
        ELSE IF only larger_image contains (row,col)
            in new_image, set (row,col) to larger_image pixel
        ELSE
            in new_image, set (row,col) to smaller_image pixel

Now the problem is this "do not contain (row,col)". What does it mean for an image to not contain a particular coordinate? It means that the (row,col) coordinate lies outside the space in the source image. I think it would help if you wrote a function which takes an image (the large or the small) and a match struct, and a (row,col) coord in the new image space, and returns either the corresponding pixel from the source image, or indicates that the pixel is not in that image. (In C, you can do this by having the function return an int, 1 if there is a pixel there and 0 if there isn't, and have an argument which is a pointer to a pixel which you fill in if you are returning 1.)

Now you can ask this function whether the large_image and small_image contain (row,col), and also get the pixel from each, if they do, and apply your four different cases.

Collectives™ on Stack Overflow

Help with a 2D array algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related