47 static inline long int random(
void)
54 return (2654435761 * x) >> 32;
66 # define M_PI 3.141592653589793238462643383279502884196 150 void fit_line(
struct line_fit_pt *lfps,
int sz,
int i0,
int i1,
double *lineparm,
double *err,
double *mse)
153 assert(i0 >= 0 && i1 >= 0 && i0 < sz && i1 < sz);
155 double Mx, My, Mxx, Myy, Mxy, W;
171 Mxx -= lfps[i0-1].
Mxx;
172 Mxy -= lfps[i0-1].
Mxy;
173 Myy -= lfps[i0-1].
Myy;
181 Mx = lfps[sz-1].
Mx - lfps[i0-1].
Mx;
182 My = lfps[sz-1].
My - lfps[i0-1].
My;
183 Mxx = lfps[sz-1].
Mxx - lfps[i0-1].
Mxx;
184 Mxy = lfps[sz-1].
Mxy - lfps[i0-1].
Mxy;
185 Myy = lfps[sz-1].
Myy - lfps[i0-1].
Myy;
186 W = lfps[sz-1].
W - lfps[i0-1].
W;
195 N = sz - i0 + i1 + 1;
202 double Cxx = Mxx / W - Ex*Ex;
203 double Cxy = Mxy / W - Ex*Ey;
204 double Cyy = Myy / W - Ey*Ey;
218 double eig_small = 0.5*(Cxx + Cyy - sqrtf((Cxx - Cyy)*(Cxx - Cyy) + 4*Cxy*Cxy));
224 double eig = 0.5*(Cxx + Cyy + sqrtf((Cxx - Cyy)*(Cxx - Cyy) + 4*Cxy*Cxy));
225 double nx1 = Cxx - eig;
227 double M1 = nx1*nx1 + ny1*ny1;
229 double ny2 = Cyy - eig;
230 double M2 = nx2*nx2 + ny2*ny2;
243 double length = sqrtf(M);
244 lineparm[2] = nx/length;
245 lineparm[3] = ny/length;
271 const double *a = _a;
272 const double *b = _b;
274 return ((*a) < (*b)) ? 1 : -1;
308 int ksz =
imin(20, sz / 12);
314 double *errs = malloc(
sizeof(
double)*sz);
316 for (
int i = 0; i < sz; i++) {
317 fit_line(lfps, sz, (i + sz - ksz) % sz, (i + ksz) % sz, NULL, &errs[i], NULL);
322 double *y = malloc(
sizeof(
double)*sz);
338 double cutoff = 0.05;
339 int fsz = sqrt(-log(cutoff)*2*sigma*sigma) + 1;
344 float *f = malloc(
sizeof(
float)*fsz);
346 for (
int i = 0; i < fsz; i++) {
348 f[i] = exp(-j*j/(2*sigma*sigma));
351 for (
int iy = 0; iy < sz; iy++) {
354 for (
int i = 0; i < fsz; i++) {
355 acc += errs[(iy + i - fsz / 2 + sz) % sz] * f[i];
360 memcpy(errs, y,
sizeof(
double)*sz);
365 int *maxima = malloc(
sizeof(
int)*sz);
366 double *maxima_errs = malloc(
sizeof(
double)*sz);
369 for (
int i = 0; i < sz; i++) {
370 if (errs[i] > errs[(i+1)%sz] && errs[i] > errs[(i+sz-1)%sz]) {
372 maxima_errs[nmaxima] = errs[i];
388 if (nmaxima > max_nmaxima) {
389 double *maxima_errs_copy = malloc(
sizeof(
double)*nmaxima);
390 memcpy(maxima_errs_copy, maxima_errs,
sizeof(
double)*nmaxima);
395 double maxima_thresh = maxima_errs_copy[max_nmaxima];
397 for (
int in = 0; in < nmaxima; in++) {
398 if (maxima_errs[in] <= maxima_thresh)
400 maxima[out++] = maxima[in];
403 free(maxima_errs_copy);
408 double best_error = HUGE_VALF;
410 double err01, err12, err23, err30;
411 double mse01, mse12, mse23, mse30;
412 double params01[4], params12[4], params23[4], params30[4];
417 for (
int m0 = 0; m0 < nmaxima - 3; m0++) {
420 for (
int m1 = m0+1; m1 < nmaxima - 2; m1++) {
423 fit_line(lfps, sz, i0, i1, params01, &err01, &mse01);
428 for (
int m2 = m1+1; m2 < nmaxima - 1; m2++) {
431 fit_line(lfps, sz, i1, i2, params12, &err12, &mse12);
435 double dot = params01[2]*params12[2] + params01[3]*params12[3];
436 if (fabs(dot) > max_dot)
439 for (
int m3 = m2+1; m3 < nmaxima; m3++) {
442 fit_line(lfps, sz, i2, i3, params23, &err23, &mse23);
446 fit_line(lfps, sz, i3, i0, params30, &err30, &mse30);
450 double err = err01 + err12 + err23 + err30;
451 if (err < best_error) {
453 best_indices[0] = i0;
454 best_indices[1] = i1;
455 best_indices[2] = i2;
456 best_indices[3] = i3;
465 if (best_error == HUGE_VALF)
468 for (
int i = 0; i < 4; i++)
469 indices[i] = best_indices[i];
471 if (best_error / sz < td->qtp.max_line_fit_mse)
490 int rvalloc_size = 3*sz;
496 for (
int i = 0; i < sz; i++) {
518 while (nvertices > 4) {
519 assert(rvalloc_pos < rvalloc_size);
576 for (
int i = 0;
i < sz;
i++) {
577 if (segs[
i].is_vertex) {
594 for (
int i = 0; i < sz; i++) {
599 memcpy(&lfps[i], &lfps[i-1],
sizeof(
struct line_fit_pt));
605 double x = p->
x * .5 + delta;
606 double y = p->
y * .5 + delta;
610 if (ix > 0 && ix+1 < im->
width && iy > 0 && iy+1 < im->
height) {
611 int grad_x = im->
buf[iy * im->
stride + ix + 1] -
614 int grad_y = im->
buf[(iy+1) * im->
stride + ix] -
618 W = sqrt(grad_x*grad_x + grad_y*grad_y) + 1;
621 double fx =
x, fy =
y;
622 lfps[i].
Mx += W * fx;
623 lfps[i].
My += W * fy;
624 lfps[i].
Mxx += W * fx * fx;
625 lfps[i].
Mxy += W * fx * fy;
626 lfps[i].
Myy += W * fy * fy;
635 #define MAYBE_SWAP(arr,apos,bpos) \ 636 if (pt_compare_angle(&(arr[apos]), &(arr[bpos])) > 0) { \ 637 tmp = arr[apos]; arr[apos] = arr[bpos]; arr[bpos] = tmp; \ 688 struct pt *tmp = malloc(
sizeof(
struct pt) * sz);
690 memcpy(tmp, pts,
sizeof(
struct pt) * sz);
695 struct pt *as = &tmp[0];
696 struct pt *bs = &tmp[asz];
701 #define MERGE(apos,bpos) \ 702 if (pt_compare_angle(&(as[apos]), &(bs[bpos])) < 0) \ 703 pts[outpos++] = as[apos++]; \ 705 pts[outpos++] = bs[bpos++]; 707 int apos = 0, bpos = 0, outpos = 0;
708 while (apos + 8 < asz && bpos + 8 < bsz) {
713 while (apos < asz && bpos < bsz) {
718 memcpy(&pts[outpos], &as[apos], (asz-apos)*
sizeof(
struct pt));
720 memcpy(&pts[outpos], &bs[bpos], (bsz-bpos)*
sizeof(
struct pt));
735 bool reversed_border) {
751 uint16_t xmax = p1->
x;
752 uint16_t xmin = p1->
x;
753 uint16_t ymax = p1->
y;
754 uint16_t ymin = p1->
y;
755 for (
int pidx = 1; pidx <
zarray_size(cluster); pidx++) {
761 }
else if (p->
x < xmin) {
767 }
else if (p->
y < ymin) {
772 if ((xmax - xmin)*(ymax - ymin) < tag_width) {
781 float cx = (xmin + xmax) * 0.5 + 0.05118;
782 float cy = (ymin + ymax) * 0.5 + -0.028581;
786 float quadrants[2][2] = {{-1*(2 << 15), 0}, {2*(2 << 15), 2 << 15}};
788 for (
int pidx = 0; pidx <
zarray_size(cluster); pidx++) {
792 float dx = p->
x - cx;
793 float dy = p->
y - cy;
795 dot += dx*p->
gx + dy*p->
gy;
797 float quadrant = quadrants[dy > 0][dx > 0];
808 p->
slope = quadrant + dy/dx;
823 ptsort((
struct pt*) cluster->
data, zarray_size(cluster));
832 for (
int i = 1; i < sz; i++) {
837 if (p->
x != last->
x || p->
y != last->
y) {
842 memcpy(out, p,
sizeof(
struct pt));
851 cluster->
size = outpos;
875 for (
int i = 0; i < 4; i++) {
877 int i1 = indices[(i+1)&3];
880 fit_line(lfps, sz, i0, i1, lines[i], NULL, &err);
888 for (
int i = 0; i < 4; i++) {
904 double A00 = lines[i][3], A01 = -lines[(i+1)&3][3];
905 double A10 = -lines[i][2], A11 = lines[(i+1)&3][2];
906 double B0 = -lines[i][0] + lines[(i+1)&3][0];
907 double B1 = -lines[i][1] + lines[(i+1)&3][1];
909 double det = A00 * A11 - A10 * A01;
912 double W00 = A11 / det, W01 = -A01 / det;
913 if (fabs(det) < 0.001) {
919 double L0 = W00*B0 + W01*B1;
922 quad->
p[i][0] = lines[i][0] + L0*A00;
923 quad->
p[i][1] = lines[i][1] + L0*A10;
934 for (
int i = 0; i < 3; i++) {
936 int idxb = (i+1) % 3;
937 length[i] = sqrt(
sq(quad->
p[idxb][0] - quad->
p[idxa][0]) +
938 sq(quad->
p[idxb][1] - quad->
p[idxa][1]));
940 p = (length[0] + length[1] + length[2]) / 2;
942 area += sqrt(p*(p-length[0])*(p-length[1])*(p-length[2]));
945 for (
int i = 0; i < 3; i++) {
946 int idxs[] = { 2, 3, 0, 2 };
948 int idxb = idxs[i+1];
949 length[i] = sqrt(
sq(quad->
p[idxb][0] - quad->
p[idxa][0]) +
950 sq(quad->
p[idxb][1] - quad->
p[idxa][1]));
952 p = (length[0] + length[1] + length[2]) / 2;
954 area += sqrt(p*(p-length[0])*(p-length[1])*(p-length[2]));
956 if (area < 0.95*tag_width*tag_width) {
964 for (
int i = 0; i < 4; i++) {
965 int i0 = i, i1 = (i+1)&3, i2 = (i+2)&3;
967 double dx1 = quad->
p[i1][0] - quad->
p[i0][0];
968 double dy1 = quad->
p[i1][1] - quad->
p[i0][1];
969 double dx2 = quad->
p[i2][0] - quad->
p[i1][0];
970 double dy2 = quad->
p[i2][1] - quad->
p[i1][1];
971 double cos_dtheta = (dx1*dx2 + dy1*dy2)/sqrt((dx1*dx1 + dy1*dy1)*(dx2*dx2 + dy2*dy2));
973 if ((cos_dtheta > td->
qtp.
cos_critical_rad || cos_dtheta < -td->qtp.cos_critical_rad) || dx1*dy2 < dy1*dx2) {
987 #define DO_UNIONFIND2(dx, dy) if (im->buf[(y + dy)*s + x + dx] == v) unionfind_connect(uf, y*w + x, (y + dy)*w + x + dx); 994 for (
int x = 1; x < w - 1; x++) {
995 v = im->
buf[y*s + x];
1009 uint8_t v_0_m1 = im->
buf[(y - 1)*s];
1010 uint8_t v_1_m1 = im->
buf[(y - 1)*s + 1];
1012 uint8_t v = im->
buf[y*s];
1014 for (
int x = 1; x < w - 1; x++) {
1017 v_1_m1 = im->
buf[(y - 1)*s + x + 1];
1019 v = im->
buf[y*s + x];
1029 if (x == 1 || !((v_m1_0 == v_m1_m1) && (v_m1_m1 == v_0_m1))) {
1034 if (x == 1 || !(v_m1_0 == v_m1_m1 || v_0_m1 == v_m1_m1) ) {
1037 if (!(v_0_m1 == v_1_m1)) {
1043 #undef DO_UNIONFIND2 1049 for (
int y = task->
y0; y < task->
y1; y++) {
1061 int w = task->
w,
h = task->
h;
1063 for (
int cidx = task->
cidx0; cidx < task->
cidx1; cidx++) {
1082 memset(&quad, 0,
sizeof(
struct quad));
1085 pthread_mutex_lock(&td->
mutex);
1087 pthread_mutex_unlock(&td->
mutex);
1099 assert(threshim->
stride == s);
1124 const int tilesz = 4;
1128 int tw = w / tilesz;
1129 int th = h / tilesz;
1131 uint8_t *im_max = calloc(tw*th,
sizeof(uint8_t));
1132 uint8_t *im_min = calloc(tw*th,
sizeof(uint8_t));
1135 for (
int ty = 0; ty < th; ty++) {
1136 for (
int tx = 0; tx < tw; tx++) {
1137 uint8_t
max = 0,
min = 255;
1139 for (
int dy = 0; dy < tilesz; dy++) {
1141 for (
int dx = 0; dx < tilesz; dx++) {
1143 uint8_t v = im->
buf[(ty*tilesz+dy)*s + tx*tilesz + dx];
1151 im_max[ty*tw+tx] =
max;
1152 im_min[ty*tw+tx] =
min;
1160 uint8_t *im_max_tmp = calloc(tw*th,
sizeof(uint8_t));
1161 uint8_t *im_min_tmp = calloc(tw*th,
sizeof(uint8_t));
1163 for (
int ty = 0; ty < th; ty++) {
1164 for (
int tx = 0; tx < tw; tx++) {
1165 uint8_t
max = 0,
min = 255;
1167 for (
int dy = -1; dy <= 1; dy++) {
1168 if (ty+dy < 0 || ty+dy >= th)
1170 for (
int dx = -1; dx <= 1; dx++) {
1171 if (tx+dx < 0 || tx+dx >= tw)
1174 uint8_t m = im_max[(ty+dy)*tw+tx+dx];
1177 m = im_min[(ty+dy)*tw+tx+dx];
1183 im_max_tmp[ty*tw + tx] =
max;
1184 im_min_tmp[ty*tw + tx] =
min;
1189 im_max = im_max_tmp;
1190 im_min = im_min_tmp;
1193 for (
int ty = 0; ty < th; ty++) {
1194 for (
int tx = 0; tx < tw; tx++) {
1196 int min = im_min[ty*tw + tx];
1197 int max = im_max[ty*tw + tx];
1200 if (max - min < td->qtp.min_white_black_diff) {
1201 for (
int dy = 0; dy < tilesz; dy++) {
1202 int y = ty*tilesz + dy;
1204 for (
int dx = 0; dx < tilesz; dx++) {
1205 int x = tx*tilesz + dx;
1207 threshim->
buf[y*s+x] = 127;
1217 uint8_t thresh = min + (max -
min) / 2;
1219 for (
int dy = 0; dy < tilesz; dy++) {
1220 int y = ty*tilesz + dy;
1222 for (
int dx = 0; dx < tilesz; dx++) {
1223 int x = tx*tilesz + dx;
1225 uint8_t v = im->
buf[y*s+x];
1227 threshim->
buf[y*s+x] = 255;
1229 threshim->
buf[y*s+x] = 0;
1237 for (
int y = 0; y < h; y++) {
1243 if (y >= th*tilesz) {
1250 int ty = y / tilesz;
1254 for (
int x = x0; x < w; x++) {
1255 int tx = x / tilesz;
1259 int max = im_max[ty*tw + tx];
1260 int min = im_min[ty*tw + tx];
1261 int thresh = min + (max -
min) / 2;
1263 uint8_t v = im->
buf[y*s+x];
1265 threshim->
buf[y*s+x] = 255;
1267 threshim->
buf[y*s+x] = 0;
1280 for (
int y = 1; y + 1 < h; y++) {
1281 for (
int x = 1; x + 1 < w; x++) {
1283 for (
int dy = -1; dy <= 1; dy++) {
1284 for (
int dx = -1; dx <= 1; dx++) {
1285 uint8_t v = threshim->
buf[(y+dy)*s + x + dx];
1294 for (
int y = 1; y + 1 < h; y++) {
1295 for (
int x = 1; x + 1 < w; x++) {
1297 for (
int dy = -1; dy <= 1; dy++) {
1298 for (
int dx = -1; dx <= 1; dx++) {
1299 uint8_t v = tmp->
buf[(y+dy)*s + x + dx];
1304 threshim->
buf[y*s+x] =
min;
1324 assert(threshim->
stride == s);
1327 assert((tilesz & 1) == 0);
1329 int tw = w/tilesz + 1;
1330 int th = h/tilesz + 1;
1332 uint8_t *im_max[4], *im_min[4];
1333 for (
int i = 0; i < 4; i++) {
1334 im_max[i] = calloc(tw*th,
sizeof(uint8_t));
1335 im_min[i] = calloc(tw*th,
sizeof(uint8_t));
1338 for (
int ty = 0; ty < th; ty++) {
1339 for (
int tx = 0; tx < tw; tx++) {
1341 uint8_t
max[4] = { 0, 0, 0, 0};
1342 uint8_t
min[4] = { 255, 255, 255, 255 };
1344 for (
int dy = 0; dy < tilesz; dy++) {
1345 if (ty*tilesz+dy >= h)
1348 for (
int dx = 0; dx < tilesz; dx++) {
1349 if (tx*tilesz+dx >= w)
1353 int idx = (2*(dy&1) + (dx&1));
1355 uint8_t v = im->
buf[(ty*tilesz+dy)*s + tx*tilesz + dx];
1363 for (
int i = 0; i < 4; i++) {
1364 im_max[i][ty*tw+tx] = max[i];
1365 im_min[i][ty*tw+tx] = min[i];
1370 for (
int ty = 0; ty < th; ty++) {
1371 for (
int tx = 0; tx < tw; tx++) {
1373 uint8_t
max[4] = { 0, 0, 0, 0};
1374 uint8_t
min[4] = { 255, 255, 255, 255 };
1376 for (
int dy = -1; dy <= 1; dy++) {
1377 if (ty+dy < 0 || ty+dy >= th)
1379 for (
int dx = -1; dx <= 1; dx++) {
1380 if (tx+dx < 0 || tx+dx >= tw)
1383 for (
int i = 0; i < 4; i++) {
1384 uint8_t m = im_max[i][(ty+dy)*tw+tx+dx];
1387 m = im_min[i][(ty+dy)*tw+tx+dx];
1401 for (
int i = 0; i < 4; i++) {
1402 thresh[i] = min[i] + (max[i] - min[i]) / 2;
1405 for (
int dy = 0; dy < tilesz; dy++) {
1406 int y = ty*tilesz + dy;
1410 for (
int dx = 0; dx < tilesz; dx++) {
1411 int x = tx*tilesz + dx;
1416 int idx = (2*(y&1) + (x&1));
1418 uint8_t v = im->
buf[y*s+x];
1419 threshim->
buf[y*s+x] = v > thresh[idx];
1425 for (
int i = 0; i < 4; i++) {
1440 for (
int y = 1; y < h; y++) {
1452 for (
int i = 1; i < sz; i += chunksize) {
1458 tasks[ntasks].
y0 = i;
1459 tasks[ntasks].
y1 =
imin(sz, i + chunksize - 1);
1460 tasks[ntasks].
h =
h;
1461 tasks[ntasks].
w =
w;
1462 tasks[ntasks].
s = ts;
1463 tasks[ntasks].
uf =
uf;
1464 tasks[ntasks].
im = threshim;
1473 for (
int i = 1; i < ntasks; i++) {
1485 int mem_chunk_size = 2048;
1487 int mem_pool_idx = 0;
1488 int mem_pool_loc = 0;
1491 for (
int y = y0; y < y1; y++) {
1492 for (
int x = 1; x < w-1; x++) {
1494 uint8_t v0 = threshim->
buf[y*ts + x];
1524 #define DO_CONN(dx, dy) \ 1526 uint8_t v1 = threshim->buf[(y + dy)*ts + x + dx]; \ 1528 if (v0 + v1 == 255) { \ 1529 uint64_t rep1 = unionfind_get_representative(uf, (y + dy)*w + x + dx); \ 1530 if (unionfind_get_set_size(uf, rep1) > 24) { \ 1531 uint64_t clusterid; \ 1533 clusterid = (rep1 << 32) + rep0; \ 1535 clusterid = (rep0 << 32) + rep1; \ 1538 uint32_t clustermap_bucket = u64hash_2(clusterid) % nclustermap; \ 1539 struct uint64_zarray_entry *entry = clustermap[clustermap_bucket]; \ 1540 while (entry && entry->id != clusterid) { \ 1541 entry = entry->next; \ 1545 if (mem_pool_loc == mem_chunk_size) { \ 1548 mem_pools[mem_pool_idx] = calloc(mem_chunk_size, sizeof(struct uint64_zarray_entry)); \ 1550 entry = mem_pools[mem_pool_idx] + mem_pool_loc; \ 1553 entry->id = clusterid; \ 1554 entry->cluster = zarray_create(sizeof(struct pt)); \ 1555 entry->next = clustermap[clustermap_bucket]; \ 1556 clustermap[clustermap_bucket] = entry; \ 1559 struct pt p = { .x = 2*x + dx, .y = 2*y + dy, .gx = dx*((int) v1-v0), .gy = dy*((int) v1-v0)}; \ 1560 zarray_add(entry->cluster, &p); \ 1576 for (
int i = 0; i < nclustermap; i++) {
1581 cluster_hash->
id = entry->id;
1582 cluster_hash->
data = entry->cluster;
1588 int n = end - start;
1589 for (
int j = 0; j < n - 1; j++) {
1590 for (
int k = 0; k < n - j - 1; k++) {
1595 if ((*hash1)->id > (*hash2)->id) {
1603 for (
int i = 0; i <= mem_pool_idx; i++) {
1628 while (i1 < l1 && i2 < l2) {
1634 if ((*h1)->hash == (*h2)->hash && (*h1)->id == (*h2)->id) {
1641 }
else if ((*h2)->hash < (*h1)->hash || ((*h2)->hash == (*h1)->hash && (*h2)->id < (*h1)->id)) {
1661 int nclustermap = 0.2*w*h;
1669 for (
int i = 1; i < sz; i += chunksize) {
1672 tasks[ntasks].
y0 = i;
1673 tasks[ntasks].
y1 =
imin(sz, i + chunksize);
1674 tasks[ntasks].
w =
w;
1675 tasks[ntasks].
s = ts;
1676 tasks[ntasks].
uf =
uf;
1677 tasks[ntasks].
im = threshim;
1678 tasks[ntasks].
nclustermap = nclustermap/(sz / chunksize + 1);
1688 for (
int i = 0; i < ntasks; i++) {
1689 clusters_list[i] = tasks[i].
clusters;
1692 int length = ntasks;
1693 while (length > 1) {
1695 for (
int i = 0; i < length - 1; i += 2) {
1696 clusters_list[write] =
merge_clusters(clusters_list[i], clusters_list[i + 1]);
1701 clusters_list[write] = clusters_list[length - 1];
1704 length = (length >> 1) + length % 2;
1709 for (
int i = 0; i <
zarray_size(clusters_list[0]); i++) {
1716 free(clusters_list);
1724 bool normal_border =
false;
1725 bool reversed_border =
false;
1726 int min_tag_width = 1000000;
1737 if (min_tag_width < 3) {
1746 for (
int i = 0; i < sz; i += chunksize) {
1747 tasks[ntasks].
td =
td;
1748 tasks[ntasks].
cidx0 = i;
1749 tasks[ntasks].
cidx1 =
imin(sz, i + chunksize);
1750 tasks[ntasks].
h =
h;
1751 tasks[ntasks].
w =
w;
1754 tasks[ntasks].
im =
im;
1755 tasks[ntasks].
tag_width = min_tag_width;
1778 int ts = threshim->
stride;
1792 uint32_t *colors = (uint32_t*) calloc(w*
h,
sizeof(*colors));
1794 for (
int y = 0; y <
h; y++) {
1795 for (
int x = 0; x <
w; x++) {
1801 uint32_t color = colors[v];
1802 uint8_t r = color >> 16,
1807 const int bias = 50;
1808 r = bias + (random() % (200-bias));
1809 g = bias + (random() % (200-bias));
1810 b = bias + (random() % (200-bias));
1811 colors[v] = (r << 16) | (g << 8) | b;
1841 const int bias = 50;
1842 r = bias + (random() % (200-bias));
1843 g = bias + (random() % (200-bias));
1844 b = bias + (random() % (200-bias));
1873 FILE *f = fopen(
"debug_lines.ps",
"w");
1874 fprintf(f,
"%%!PS\n\n");
1881 double scale = fmin(612.0/im->
width, 792.0/im2->
height);
1882 fprintf(f,
"%.15f %.15f scale\n", scale, scale);
1883 fprintf(f,
"0 %d translate\n", im2->
height);
1884 fprintf(f,
"1 -1 scale\n");
1897 for (
int j = 0; j < 3; j++)
1898 rgb[j] = bias + (random() % (255-bias));
1900 fprintf(f,
"%f %f %f setrgbcolor\n", rgb[0]/255.0f, rgb[1]/255.0f, rgb[2]/255.0f);
1901 fprintf(f,
"%.15f %.15f moveto %.15f %.15f lineto %.15f %.15f lineto %.15f %.15f lineto %.15f %.15f lineto stroke\n",
1902 q->
p[0][0], q->
p[0][1],
1903 q->
p[1][0], q->
p[1][1],
1904 q->
p[2][0], q->
p[2][1],
1905 q->
p[3][0], q->
p[3][1],
1906 q->
p[0][0], q->
p[0][1]);
static unionfind_t * unionfind_create(uint32_t maxid)
void workerpool_add_task(workerpool_t *wp, void(*f)(void *p), void *p)
#define APRILTAG_TASKS_PER_THREAD_TARGET
static void do_unionfind_task2(void *p)
static void zarray_get_volatile(const zarray_t *za, int idx, void *p)
int quad_segment_agg(apriltag_detector_t *td, zarray_t *cluster, struct line_fit_pt *lfps, int indices[4])
void image_u8_darken(image_u8_t *im)
static void timeprofile_stamp(timeprofile_t *tp, const char *name)
void zmaxheap_destroy(zmaxheap_t *heap)
static void do_unionfind_first_line(unionfind_t *uf, image_u8_t *im, int h, int w, int s)
struct line_fit_pt * compute_lfps(int sz, zarray_t *cluster, image_u8_t *im)
int fit_quad(apriltag_detector_t *td, image_u8_t *im, zarray_t *cluster, struct quad *quad, int tag_width, bool normal_border, bool reversed_border)
static void do_unionfind_line2(unionfind_t *uf, image_u8_t *im, int h, int w, int s, int y)
static int zarray_size(const zarray_t *za)
static uint32_t unionfind_get_representative(unionfind_t *uf, uint32_t id)
static void zarray_ensure_capacity(zarray_t *za, int capacity)
int image_u8x3_write_pnm(const image_u8x3_t *im, const char *path)
static void zarray_destroy(zarray_t *za)
image_u8_t * threshold_bayer(apriltag_detector_t *td, image_u8_t *im)
static void ptsort(struct pt *pts, int sz)
#define MAYBE_SWAP(arr, apos, bpos)
struct uint64_zarray_entry * next
image_u8_t * image_u8_copy(const image_u8_t *in)
static void zarray_add_range(zarray_t *dest, const zarray_t *source, int start, int end)
static uint32_t unionfind_get_set_size(unionfind_t *uf, uint32_t id)
image_u8_t * image_u8_create_alignment(unsigned int width, unsigned int height, unsigned int alignment)
static zarray_t * zarray_create(size_t el_sz)
#define MERGE(apos, bpos)
struct apriltag_quad_thresh_params qtp
zarray_t * apriltag_quad_thresh(apriltag_detector_t *td, image_u8_t *im)
image_u8x3_t * image_u8x3_create(unsigned int width, unsigned int height)
void workerpool_run(workerpool_t *wp)
int image_u8_write_pnm(const image_u8_t *im, const char *path)
static double sq(double v)
zmaxheap_t * zmaxheap_create(size_t el_sz)
static void do_quad_task(void *p)
static void unionfind_destroy(unionfind_t *uf)
static int imin(int a, int b)
#define DO_UNIONFIND2(dx, dy)
static void zarray_get(const zarray_t *za, int idx, void *p)
image_u8_t * image_u8_create(unsigned int width, unsigned int height)
static void do_cluster_task(void *p)
void image_u8_destroy(image_u8_t *im)
int quad_segment_maxima(apriltag_detector_t *td, zarray_t *cluster, struct line_fit_pt *lfps, int indices[4])
zarray_t * gradient_clusters(apriltag_detector_t *td, image_u8_t *threshim, int w, int h, int ts, unionfind_t *uf)
unionfind_t * connected_components(apriltag_detector_t *td, image_u8_t *threshim, int w, int h, int ts)
void zmaxheap_add(zmaxheap_t *heap, void *p, float v)
int err_compare_descending(const void *_a, const void *_b)
image_u8_t * threshold(apriltag_detector_t *td, image_u8_t *im)
void fit_line(struct line_fit_pt *lfps, int sz, int i0, int i1, double *lineparm, double *err, double *mse)
static void postscript_image(FILE *f, image_u8_t *im)
static uint32_t u64hash_2(uint64_t x)
int zmaxheap_remove_max(zmaxheap_t *heap, void *p, float *v)
zarray_t * do_gradient_clusters(image_u8_t *threshim, int ts, int y0, int y1, int w, int nclustermap, unionfind_t *uf, zarray_t *clusters)
zarray_t * merge_clusters(zarray_t *c1, zarray_t *c2)
void image_u8x3_destroy(image_u8x3_t *im)
float pt_compare_angle(struct pt *a, struct pt *b)
static void zarray_add(zarray_t *za, const void *p)
zarray_t * fit_quads(apriltag_detector_t *td, int w, int h, zarray_t *clusters, image_u8_t *im)