Main Page   Modules   Class Hierarchy   Compound List   File List   Compound Members   Related Pages   Examples  

DistanceTransform.cpp

00001 /* Copyright (c) 2001 C. Grigorescu */
00002 
00003 #include <stdio.h>
00004 #include <stdlib.h>
00005 #include <math.h>
00006 #include "misc.h"
00007 #include "DistanceTransform.h"
00008 
00009 int min(int x, int y) {  return(((x)<(y)) ? (x):(y)); }                                       
00010 
00011 void DistanceTransform(ByteImage &input, DM_TYPE dm_type, IntImage &output)
00012 {
00013   int weights[3]; 
00014   switch(dm_type) {
00015   case EUCLID:
00016     weights[0] = 5;
00017     weights[1] = 7;
00018     weights[2] = 11;
00019     break;
00020   case EUCLID_1:
00021     weights[0] = 3;
00022     weights[1] = 4;
00023     weights[2] = MAX_INT;
00024     break;
00025   case CITY_BLOCK:
00026     weights[0] = 1;
00027     weights[1] = MAX_INT;
00028     weights[2] = MAX_INT;
00029     break;
00030   case CHESSBOARD:
00031     weights[0] = 1;
00032     weights[1] = 1;
00033     weights[2] = MAX_INT;
00034     break;
00035   default: 
00036     cout << "Unknown distance map type " << endl;
00037   }
00038 
00039   int w = input.getWidth();
00040   int h = input.getHeight();
00041   output.makeImage(w,h);
00042   IntImage temp1, temp2;
00043   temp1.makeImage(w,h);
00044   for (int i=0;i<h;i++)
00045     for (int j=0;j<w;j++) 
00046       if (input[i][j] != ON) {
00047       temp1[i][j] = 0;
00048       output[i][j] = 0;
00049       }
00050       else {
00051       temp1[i][j] = MAX_INT;
00052       output[i][j] = MAX_INT;
00053       }
00054 
00055   //  forward scan
00056   int min1;
00057   for (int i=2;i<h;i++)
00058     for (int j=2;j<w-2;j++) {
00059       min1 = temp1[i][j];
00060       min1 = min(min1, (temp1[i][j-1]+weights[0]));
00061       min1 = min(min1, (temp1[i-1][j]+weights[0]));
00062       min1 = min(min1, (temp1[i-1][j-1]+weights[1]));
00063       min1 = min(min1, (temp1[i-1][j+1]+weights[1]));
00064       min1 = min(min1, (temp1[i-1][j-2]+weights[2]));
00065       min1 = min(min1, (temp1[i-2][j-1]+weights[2]));
00066       min1 = min(min1, (temp1[i-2][j+1]+weights[2]));
00067       min1 =  min(min1, (temp1[i-1][j+2]+weights[2]));
00068       temp1[i][j] = min1;
00069     }
00070   // backward scan
00071   for (int i=h-3;i>=0;i--)
00072     for (int j=w-3;j>=2;j--) {
00073       min1 = output[i][j];
00074       min1 = min(min1, (output[i][j+1]+weights[0]));
00075       min1 = min(min1, (output[i+1][j]+weights[0]));
00076       min1 = min(min1, (output[i+1][j+1]+weights[1]));
00077       min1 = min(min1, (output[i+1][j-1]+weights[1]));
00078       min1 = min(min1, (output[i+1][j+2]+weights[2]));
00079       min1 = min(min1, (output[i+2][j+1]+weights[2]));
00080       min1 = min(min1, (output[i+2][j-1]+weights[2]));
00081       min1 = min(min1, (output[i+1][j-2]+weights[2]));
00082       output[i][j] = min1;
00083     }
00084   for (int i=2;i<h-2;i++)
00085     for (int j=2;j<w-2;j++)
00086       output[i][j] = min(temp1[i][j],output[i][j]);
00087 }