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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#include <math.h>
#include "DistanceMatrix.hh"
class QueueElement
{
public:
int x;
int y;
unsigned int xdiff;
unsigned int ydiff;
QueueElement(unsigned int i_x, unsigned int i_y)
{
x=i_x;
y=i_y;
xdiff=0;
ydiff=0;
}
QueueElement(const QueueElement& e, int direction)
{
switch (direction) {
case 0:
x=e.x-1;
y=e.y;
xdiff=e.xdiff-1;
ydiff=e.ydiff;
break;
case 1:
x=e.x;
y=e.y-1;
xdiff=e.xdiff;
ydiff=e.ydiff-1;
break;
case 2:
x=e.x+1;
y=e.y;
xdiff=e.xdiff+1;
ydiff=e.ydiff;
break;
default:
x=e.x;
y=e.y+1;
xdiff=e.xdiff;
ydiff=e.ydiff+1;
}
}
unsigned int Value() const
{
return ((xdiff*xdiff) + (ydiff*ydiff));
}
};
DistanceMatrix::DistanceMatrix(Image& image, unsigned int fg_threshold)
: DataMatrix<unsigned int>(image.w, image.h)
{
Queue queue;
Init(queue);
int line=0, row=0;
Image::iterator i=image.begin();
Image::iterator end=image.end();
for (; i!=end ; ++i) {
if ((*i).getL() < fg_threshold) {
queue.push_back(QueueElement(row, line));
data[row][line]=0;
}
if (++row == image.w) {
line++;
row=0;
}
}
RunBFS(queue);
}
DistanceMatrix::DistanceMatrix(const FGMatrix& image)
: DataMatrix<unsigned int>(image.w, image.h)
{
Queue queue;
Init(queue);
for (unsigned int x=0; x<w; x++)
for (unsigned int y=0; y<h ; y++)
if (image(x,y)) {
queue.push_back(QueueElement(x, y));
data[x][y]=0;
}
RunBFS(queue);
}
void DistanceMatrix::Init(Queue& queue)
{
for (unsigned int x=0; x<w; x++)
for (unsigned int y=0; y<h; y++)
data[x][y]=undefined_dist;
queue.reserve(4*w*h);
}
void DistanceMatrix::RunBFS(Queue& queue)
{
unsigned int pos=0;
while (pos < queue.size()) {
for (unsigned int direction=0; direction<4; direction++) {
queue.push_back(QueueElement(queue[pos],direction));
QueueElement& last=queue.back();
unsigned int value=last.Value();
if (last.x < 0 || last.x >= (int)w || last.y < 0 || last.y >= (int)h || value >= data[last.x][last.y])
queue.pop_back();
else
data[last.x][last.y]=value;
}
pos++;
}
for (unsigned int x=0; x<w; x++)
for (unsigned int y=0; y<h; y++)
data[x][y]=(unsigned int) sqrt((double) (data[x][y] << 2*precission_shift));
queue.clear();
}
DistanceMatrix::DistanceMatrix(const DistanceMatrix& source, unsigned int x, unsigned int y, unsigned int w, unsigned int h)
: DataMatrix<unsigned int>(source, x,y,w,h)
{
}
DistanceMatrix::~DistanceMatrix()
{
}
|
