This repository has been archived by the owner on Nov 29, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 314
/
SEDM.h
213 lines (175 loc) · 5.88 KB
/
SEDM.h
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
/*
Scan Tailor - Interactive post-processing tool for scanned pages.
Copyright (C) 2007-2009 Joseph Artsimovich <joseph_a@mail.ru>
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 3 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, see <http://www.gnu.org/licenses/>.
*/
#ifndef IMAGEPROC_SEDM_H_
#define IMAGEPROC_SEDM_H_
#include "foundation/FlagOps.h"
#include <vector>
#include <QSize>
#include <stdint.h>
namespace imageproc
{
class BinaryImage;
class ConnectivityMap;
/**
* \brief The squared euclidean distance map.
*
* For each pixel of the input image stores the squared euclidean
* (straight line) distance to either the nearest white or black pixel.
*
* The implementation is based on the following paper:\n
* Meijster, A., Roerdink, J., and Hesselink, W. 2000.
* A general algorithm for computing distance transforms in linear time.
* In Proceedings of the 5th International Conference on Mathematical
* Morphology and its Applications to Image and Signal Processing.
*/
class SEDM
{
public:
/**
* \brief The type of distance to compute.
*/
enum DistType {
/**
* For every black pixel, the distance to the nearest
* white one is computed.
*/
DIST_TO_WHITE,
/**
* For every white pixel, the distance to the nearest
* black one is computed.
*/
DIST_TO_BLACK
};
/**
* \brief Determines whether to compute the distance to borders.
*/
enum Borders {
DIST_TO_NO_BORDERS = 0,
DIST_TO_TOP_BORDER = 1,
DIST_TO_LEFT_BORDER = 2,
DIST_TO_RIGHT_BORDER = 4,
DIST_TO_BOTTOM_BORDER = 8,
DIST_TO_VERT_BORDERS = DIST_TO_LEFT_BORDER|DIST_TO_RIGHT_BORDER,
DIST_TO_HOR_BORDERS = DIST_TO_TOP_BORDER|DIST_TO_BOTTOM_BORDER,
DIST_TO_ALL_BORDERS = DIST_TO_HOR_BORDERS|DIST_TO_VERT_BORDERS
};
/**
* \brief The infinite distance.
*
* If the input image doesn't have any objects to compute
* distance to, and borders are to DIST_TO_NO_BORDERS,
* then the whole distance map will consist of these values.
*/
static uint32_t const INF_DIST;
/**
* \brief Constructs a null distance map.
*
* The data() method returns null on such maps.
*/
SEDM();
/**
* \brief Build a distance map from a binary image.
*
* For every black pixel in the image, the distance
* map will store the squared straight-line distance
* to the nearest white pixel. The distance between
* two pixels is the distance between their center points.
*
* \param image The image to compute the distance map from.
* \param dist_type Determines whether to compute distance
* to white or black pixels in the image.
* \param borders Determines whether to compute
* distance to particular borders. The borders
* are assumed to lie one pixel off the image area.
*/
explicit SEDM(
BinaryImage const& image, DistType dist_type = DIST_TO_WHITE,
Borders borders = DIST_TO_ALL_BORDERS);
/**
* \brief Build a distance map from a connectivity map.
*
* For every zero label in the connectivity map, the distance
* map will store the squared straight-line distance to the
* nearest non-zero label.
* \note Besides building a distance map, it will modify
* the connectivity map by overwriting zero labels
* with the nearest non-zero label. This applies to
* the padding areas of the connectivity map as well.
*/
explicit SEDM(ConnectivityMap& cmap);
SEDM(SEDM const& other);
SEDM& operator=(SEDM const& other);
void swap(SEDM& other);
/**
* \brief Return the dimensions of the distance map.
*/
QSize size() const { return m_size; }
/**
* \brief Return the number of 32bit words in a line.
*
* This value is going to be size().width() + 2.
*/
int stride() const { return m_stride; }
/**
* \brief Return a matrix of squared distances in row-major order.
*/
uint32_t* data() { return m_pData; }
/**
* \brief Return a matrix of squared distances in row-major order.
*/
uint32_t const* data() const { return m_pData; }
/**
* \brief Finds peaks on the distance map, altering it in the process.
*
* A peak region is a 4-connected group of cells having the same
* distance value, that doesn't have any neighbors with a higher
* distance value.
*
* Peaks on a Euclidean distance map are also known as ultimate
* eroded points.
*
* The Borders flags used to build this SEDM also affect the peaks
* on it. If the distance to a particular object was considered,
* that border was considered an object, so a peak may be found
* between this border and another object.
*
* Peaks are returned in a BinaryImage, and the distance
* map is altered in an uspecified way.
*/
BinaryImage findPeaksDestructive();
private:
static uint32_t distSq(int x1, int x2, uint32_t dy_sq);
void processColumns();
void processColumns(ConnectivityMap& cmap);
void processRows();
void processRows(ConnectivityMap& cmap);
BinaryImage findPeakCandidatesNonPadded() const;
BinaryImage buildEqualMapNonPadded(uint32_t const* src1, uint32_t const* src2) const;
void max3x3(uint32_t const* src, uint32_t* dst) const;
void max3x1(uint32_t const* src, uint32_t* dst) const;
void max1x3(uint32_t const* src, uint32_t* dst) const;
void incrementMaskedPadded(BinaryImage const& mask);
std::vector<uint32_t> m_data;
uint32_t* m_pData;
QSize m_size;
int m_stride;
};
inline void swap(SEDM& o1, SEDM& o2)
{
o1.swap(o2);
}
DEFINE_FLAG_OPS(SEDM::Borders)
} // namespace imageproc
#endif