Sum of Absolute Differences algorithm implementation

Question

Those unfamiliar with that algorithm can have a deeper look here, in a few words, there are two arrays where you subtract each element ar1[0][0]-ar2[0][0] and add that result using the absolute values. My implementation is this:

#include <stdio.h>
#include <stdlib.h>

#define LEN(arr) ((int) (sizeof (arr) / sizeof (arr)[0]))
int calSad(int templ[3][3], int image[3][3]);

int main()
{
    int tempImage[3][3] = {};

    int tem[3][3] = {
            {2, 5, 5},
            {4, 0, 7},
            {7, 5, 9}
    };

    int originalImage[3][5] = {
            {2, 7, 5, 8, 6},
            {1, 7, 4, 2, 7},
            {8, 4, 6, 8, 5}
    };

    int tempSad = 0, sad = 256, Xcoordinate = 0, Ycoordinate = 0;

    int originalImage_row_length = LEN(originalImage);
    int tempImage_row_length = LEN(tempImage);

    int originalImage_col_length = LEN(originalImage[0]);
    int tempImage_col_length = LEN(tempImage[0]);

    int tem_row_length = LEN(tem);
    int temp_col_length = LEN(tem[0]);

    int x, z, i, y, d = 0, q = 0;

    for (x = 0; x <= originalImage_row_length - tempImage_row_length; x++) {
        for (z = 0; z <= originalImage_col_length - tempImage_col_length; z++) {
            for (i = 0; i < tem_row_length; i++) {
                for (y = 0; y < temp_col_length; y++) {
                    tempImage[i][y] = originalImage[x+q][z+d];
                    d = d + 1;
                }
                q = q + 1;
                d = 0;
            }
            q = 0;
            tempSad = calSad(tem, tempImage);
            if (tempSad < sad) {
                sad = tempSad;
                Xcoordinate = x;
                Ycoordinate = z;
            }
        }
    }

    printf("SAD: %d\n", sad);
    printf("X: %d\n", Xcoordinate);
    printf("Y: %d\n", Ycoordinate);

    return 0;
}

int calSad(int templ[3][3], int image[3][3]) {
    int tempSad = 0;

    tempSad = (abs(templ[0][0] - image[0][0])+abs(templ[0][1] - image[0][1])+abs(templ[0][2] - image[0][2])+
               abs(templ[1][0] - image[1][0])+abs(templ[1][1] - image[1][1])+abs(templ[1][2] - image[1][2])+
               abs(templ[2][0] - image[2][0])+abs(templ[2][1] - image[2][1])+abs(templ[2][2] - image[2][2]));

    return tempSad;
}

The arrays are from the wikipedia link above, so I can duplicate the result and see if it works. It seems to work but I want your opinion if you see something wrong or if it doesn't work.

Answer 1

A more generic SAD function

Currently, your SAD function is hardcoded to work on a 3x3 area. Also, because it takes 3x3 arrays as inputs, you need to use a temporary array tempImage in order to copy a 3x3 area of the original image so that you can pass it to your function.

If you modified your function a bit, you could pass the original image into the function without making a copy. Here is how I would rewrite your function:

/**
 * Calculates sum of absolute differences between a pattern and an image.
 * The area of the image to be matched is at (imgX, imgY).
 */
int calSad(const int *pattern, int patWidth, int patHeight,
        const int *img, int imgX, int imgY, int imgWidth)
{
    int ret = 0;
    int x   = 0;
    int y   = 0;

    // Set img to point at &img[imgY][imgX].
    img = img + (imgWidth * imgY) + imgX;
    for (y = 0; y < patHeight; y++) {
        for (x = 0; x < patWidth; x++)
            ret += abs(pattern[x] - img[x]);
        pattern += patWidth;
        img     += imgWidth;
    }
    return ret;
}

Note that I used y to indicate row and x to indicate column, which is reverse of how you named your variables.

Your loop in main() would simplify to this:

for (x = 0; x <= originalImage_row_length - tempImage_row_length; x++) {
    for (z = 0; z <= originalImage_col_length - tempImage_col_length; z++) {
        tempSad = calSad(&tem[0][0], LEN(tem), LEN(tem[0]),
                        &originalImage[0][0], z, x, LEN(originalImage[0]));
        if (tempSad < sad) {
            sad = tempSad;
            Xcoordinate = x;
            Ycoordinate = z;
        }
    }
}