chamfer34_s.c

The salience distance transform incorporates edge strength information into the distance transform.

/*
 * chamfer 3-4 distance transform
 *
 * CVGIP v34, pp344, 1986
 *
 * Paul Rosin 1/91
 * extended & improved 2/93
 * simplified serial version 7/94
 */

#include <stdio.h>

#ifndef FALSE
# define FALSE 0
# define TRUE (!FALSE)
#endif

#define MIN(a,b)     (((a) < (b)) ? (a) : (b))

#define MAX_SIZE 3000

#include "pgmio.h"

unsigned char image[MAX_SIZE][MAX_SIZE];
int image2[MAX_SIZE][MAX_SIZE];

int height,width,depth;

main(argc,argv)
int argc;
char *argv[];
{
    int i,j,x,y;
    int v[9];
    int min_val;
    char *infile,*outfile;

    infile = outfile = NULL;

    /* parse command line */
    for (i = 1; i < argc; i++) {
        if (argv[i][0] == '-') {
            switch(argv[i][1]) {
                case 'i':
                    i++;
                    infile = argv[i];
                    break;
                case 'o':
                    i++;
                    outfile = argv[i];
                    break;
                default:
                    printf("unknown option %s\n",argv[i]);
                    options(argv[0]);
            }
        }
        else {
            printf("unknown option %s\n",argv[i]);
            options(argv[0]);
        }
    }

    if ((infile == NULL || outfile == NULL))
        options(argv[0]);

    read_pgm(image,infile,&width,&height,&depth);

    /* copy to integer image */
    for (y = 0; y < height; y++)
        for (x = 0; x < width; x++)
            image2[x][y] = (unsigned char)image[x][y];

    /* forward pass */
    for (y = 1; y < height-1; y++) {
        for (x = 1; x < width-1; x++) {
            v[0] = image2[x-1][y-1] + 4;
            v[1] = image2[x  ][y-1] + 3;
            v[2] = image2[x+1][y-1] + 4;
            v[3] = image2[x-1][y  ] + 3;
            v[4] = image2[x  ][y  ];

            min_val = v[0];
            for (i = 1; i < 5; i++)
                if (v[i] < min_val)
                    min_val = v[i];
            image2[x][y] = min_val;
        }
    }

    /* backward pass */
    for (y = height-2; y >= 1; y--) {
        for (x = width-2; x >= 1; x--) {
            v[0] = image2[x-1][y+1] + 4;
            v[1] = image2[x  ][y+1] + 3;
            v[2] = image2[x+1][y+1] + 4;
            v[3] = image2[x+1][y  ] + 3;
            v[4] = image2[x  ][y  ];

            min_val = v[0];
            for (i = 1; i < 5; i++)
                if (v[i] < min_val)
                    min_val = v[i];
            image2[x][y] = min_val;
        }
    }

    /* set corners high for the time being */
    image2[0][0] = image2[0][height-1] = image2[width-1][0] = image2[width-1][height-1] = 255;

    /* do left edges too */
    x = 0;
    for (y = 1; y < height-1; y++) {
        v[0] = image2[x+1][y-1] + 4;
        v[1] = image2[x+1][y  ] + 3;
        v[2] = image2[x+1][y-1] + 4;

        min_val = 255;
        for (i = 0; i < 3; i++)
            if (v[i] < min_val)
                min_val = v[i];
        image2[x][y] = min_val;
    }

    /* do right edges too */
    x = width-1;
    for (y = 1; y < height-1; y++) {
        v[0] = image2[x-1][y-1] + 4;
        v[1] = image2[x-1][y  ] + 3;
        v[2] = image2[x-1][y-1] + 4;

        min_val = 255;
        for (i = 0; i < 3; i++)
            if (v[i] < min_val)
                min_val = v[i];
        image2[x][y] = min_val;
    }

    /* do top edges too */
    y = 0;
    for (x = 1; x < width-1; x++) {
        v[0] = image2[x-1][y+1] + 4;
        v[1] = image2[x  ][y+1] + 3;
        v[2] = image2[x+1][y+1] + 4;

        min_val = 255;
        for (i = 0; i < 3; i++)
            if (v[i] < min_val)
                min_val = v[i];
        image2[x][y] = min_val;
    }

    /* do bottom edges too */
    y = height-1;
    for (x = 1; x < width-1; x++) {
        v[0] = image2[x-1][y-1] + 4;
        v[1] = image2[x  ][y-1] + 3;
        v[2] = image2[x+1][y-1] + 4;

        min_val = 255;
        for (i = 0; i < 3; i++)
            if (v[i] < min_val)
                min_val = v[i];
        image2[x][y] = min_val;
    }

    /* clamp at 255 since output is 8 bit */
    for (y = 0; y < height; y++)
        for (x = 0; x < width; x++)
            image2[x][y] = MIN(255,image2[x][y]);

    /* copy back to unsigned char image */
    for (y = 0; y < height; y++)
        for (x = 0; x < width; x++)
            image[x][y] = (unsigned char)image2[x][y];

    write_pgm(image,outfile,width,height);
}

options(progname)
char *progname;
{
    printf("usage: %s [options]\n",progname);
    printf("     -i infile  binary edge map\n");
    printf("     -o outfile output distance map\n");
    exit(-1);
}