00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "hough_transform.h"
00025
00026 #include <algorithm>
00027 #include <cstdio>
00028 #include <cstdlib>
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053 HoughTransform::HoughTransform(unsigned int num_dims)
00054 {
00055 __root = new Node(this, num_dims);
00056
00057 __num_dims = num_dims;
00058
00059 __reuse_head = new Node(this);
00060 __reuse_cur = __reuse_head;
00061 __reuse_tail = __reuse_head;
00062
00063 __max_count = 0;
00064 __max_values = new int[num_dims];
00065 }
00066
00067
00068 HoughTransform::~HoughTransform()
00069 {
00070 while (__reuse_head) {
00071 Node *n = __reuse_head;
00072 __reuse_head = __reuse_head->__reuse_next;
00073 delete n;
00074 }
00075
00076 delete[] __max_values;
00077 }
00078
00079
00080
00081
00082
00083
00084
00085
00086 void
00087 HoughTransform::process(int **values, unsigned int num_values)
00088 {
00089 for (unsigned int i = 0; i < num_values; ++i) {
00090 unsigned int count = __root->insert(values[i]);
00091 if (count > __max_count) {
00092 __max_count = count;
00093 for (unsigned int d = 0; d < __num_dims; ++d) {
00094 __max_values[d] = values[i][d];
00095 }
00096 }
00097 }
00098 }
00099
00100
00101
00102
00103
00104
00105
00106
00107 unsigned int
00108 HoughTransform::max(int *values) const
00109 {
00110 for (unsigned int d = 0; d < __num_dims; ++d) {
00111 values[d] = __max_values[d];
00112 }
00113 return __max_count;
00114 }
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126 unsigned int
00127 HoughTransform::filter(int **values, unsigned int min_count)
00128 {
00129 return __root->filter(values, min_count);
00130 }
00131
00132
00133
00134
00135
00136
00137 HoughTransform::Node *
00138 HoughTransform::root()
00139 {
00140 return __root;
00141 }
00142
00143
00144
00145 void
00146 HoughTransform::reset()
00147 {
00148 __reuse_cur = __reuse_head;
00149 __root = create_node(NULL, __num_dims);
00150 __max_count = 0;
00151 for (unsigned int d = 0; d < __num_dims; ++d) {
00152 __max_values[d] = 0;
00153 }
00154 }
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174 HoughTransform::Node::Node(HoughTransform *ht, unsigned int dims, int value)
00175 {
00176 __ht = ht;
00177 __dims = dims;
00178 __value = value;
00179 __count = 0;
00180 __parent = NULL;
00181 __left = __right = __dim_next = __filter_next = __reuse_next = 0;
00182 }
00183
00184
00185
00186
00187
00188
00189 HoughTransform::Node::Node(HoughTransform *ht,
00190 Node *parent, unsigned int dims, int value)
00191 {
00192 __ht = ht;
00193 __parent = parent;
00194 __dims = dims;
00195 __value = value;
00196 __count = 0;
00197 __left = __right = __dim_next = __filter_next = __reuse_next = 0;
00198 }
00199
00200
00201 HoughTransform::Node::Node(HoughTransform *ht)
00202 {
00203 __ht = ht;
00204 __dims = 1;
00205 __value = 0;
00206 __count = 0;
00207 __parent = NULL;
00208 __left = __right = __dim_next = __filter_next = __reuse_next = 0;
00209 }
00210
00211
00212 HoughTransform::Node::~Node()
00213 {
00214
00215 }
00216
00217
00218
00219
00220
00221
00222
00223 unsigned int
00224 HoughTransform::Node::insert(int *values)
00225 {
00226 if (values[0] == __value) {
00227 if ( __dims > 1) {
00228 if (! __dim_next) {
00229 __dim_next = __ht->create_node(this, __dims - 1, values[1]);
00230 }
00231
00232 return __dim_next->insert(&(values[1]));
00233 } else {
00234 return ++__count;
00235 }
00236 } else if (values[0] < __value) {
00237 if (! __left) {
00238 __left = __ht->create_node(__parent, __dims, values[0]);
00239 }
00240 return __left->insert(values);
00241 } else {
00242 if (! __right) {
00243 __right = __ht->create_node(__parent, __dims, values[0]);
00244 }
00245 return __right->insert(values);
00246 }
00247 }
00248
00249
00250
00251
00252
00253 unsigned int
00254 HoughTransform::Node::num_nodes()
00255 {
00256 unsigned int rv = 1;
00257 if (__left) rv += __left->num_nodes();
00258 if (__right) rv += __right->num_nodes();
00259 if (__dim_next) rv += __dim_next->num_nodes();
00260 return rv;
00261 }
00262
00263
00264
00265
00266
00267 unsigned int
00268 HoughTransform::Node::depth()
00269 {
00270 unsigned int d = 0;
00271 if (__left) d = std::max(d, __left->depth());
00272 if (__right) d = std::max(d, __right->depth());
00273 if (__dim_next) d = std::max(d, __dim_next->depth());
00274 return d + 1;
00275 }
00276
00277
00278
00279
00280
00281 unsigned int
00282 HoughTransform::Node::filtered_length()
00283 {
00284 Node *t = this;
00285
00286 unsigned int rv = 0;
00287 while (t->__filter_next) {
00288 ++rv;
00289 t = t->__filter_next;
00290 }
00291 return rv;
00292 }
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304 unsigned int
00305 HoughTransform::Node::filter(int **values, unsigned int min_count)
00306 {
00307 Node *filtered_root = new Node();
00308 filter(filtered_root, min_count);
00309 unsigned int flen = filtered_root->filtered_length();
00310
00311 int *fvals = (int *)calloc(flen, __dims * sizeof(int));
00312 Node *t = filtered_root;
00313 unsigned int f = 0;
00314 while ((t = t->__filter_next) != NULL) {
00315 Node *s = t;
00316 for (unsigned int i = 1; i <= __dims; ++i) {
00317 fvals[ __dims * (f + 1) - i ] = s->__value;
00318 s = s->__parent;
00319 }
00320 ++f;
00321 }
00322
00323 delete filtered_root;
00324
00325 *values = fvals;
00326 return flen;
00327 }
00328
00329
00330
00331
00332
00333
00334
00335 HoughTransform::Node *
00336 HoughTransform::Node::filter(Node *tail, unsigned int min_count)
00337 {
00338 if (__dims == 1) {
00339 if (__count >= min_count) {
00340
00341 this->__filter_next = NULL;
00342 tail->__filter_next = this;
00343 tail = this;
00344 }
00345 if (__left) tail = __left->filter(tail, min_count);
00346 if (__right) tail = __right->filter(tail, min_count);
00347
00348 } else {
00349 if (__dim_next) tail = __dim_next->filter(tail, min_count);
00350 if (__left) tail = __left->filter(tail, min_count);
00351 if (__right) tail = __right->filter(tail, min_count);
00352 }
00353
00354 return tail;
00355 }