1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
/* dt - dt.h
*
* Copyright (C) 2006 Pedro Felzenszwalb
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/* distance transform */
#ifndef DT_H
#define DT_H
#include <algorithm>
#include "image.h"
#define INF 1E20
/* dt of 1d function using squared distance */
static float *dt(float *f, int n) {
float *d = new float[n];
int *v = new int[n];
float *z = new float[n+1];
int k = 0;
v[0] = 0;
z[0] = -INF;
z[1] = +INF;
for (int q = 1; q <= n-1; q++) {
float s = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);
while (s <= z[k]) {
k--;
s = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);
}
k++;
v[k] = q;
z[k] = s;
z[k+1] = +INF;
}
k = 0;
for (int q = 0; q <= n-1; q++) {
while (z[k+1] < q)
k++;
d[q] = square(q-v[k]) + f[v[k]];
}
delete [] v;
delete [] z;
return d;
}
/* dt of 2d function using squared distance */
static void dt(image<float> *im) {
int width = im->width();
int height = im->height();
float *f = new float[std::max(width,height)];
// transform along columns
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
f[y] = imRef(im, x, y);
}
float *d = dt(f, height);
for (int y = 0; y < height; y++) {
imRef(im, x, y) = d[y];
}
delete [] d;
}
// transform along rows
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
f[x] = imRef(im, x, y);
}
float *d = dt(f, width);
for (int x = 0; x < width; x++) {
imRef(im, x, y) = d[x];
}
delete [] d;
}
delete f;
}
/* dt of binary image using squared distance */
static image<float> *dt(image<uchar> *im, uchar on = 1) {
int width = im->width();
int height = im->height();
image<float> *out = new image<float>(width, height, false);
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (imRef(im, x, y) == on)
imRef(out, x, y) = 0;
else
imRef(out, x, y) = INF;
}
}
dt(out);
return out;
}
#endif
|
