00001
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
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
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 }