d2/trans_multi.h

   1 // Copyright 2002, 2004, 2007 David Hilvert <dhilvert@auricle.dyndns.org>,
   2 //                                          <dhilvert@ugcs.caltech.edu>
   3
   4 /*  This file is part of the Anti-Lamenessing Engine.
   5
   6     The Anti-Lamenessing Engine is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     The Anti-Lamenessing Engine is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with the Anti-Lamenessing Engine; if not, write to the Free Software
  18     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19 */
  20
  21 /*
  22  * trans_multi.h: Represent multiple transformations, affecting different
  23  * regions of a scene.
  24  */
  25
  26 #ifndef __trans_multi_h__
  27 #define __trans_multi_h__
  28
  29 #include "trans_abstract.h"
  30 #include "trans_single.h"
  31
  32 struct trans_multi : public trans_abstract {
  33 public:
  34         struct multi_coordinate {
  35                 int degree;
  36                 int x;
  37                 int y;
  38
  39         public:
  40                 int operator<(const multi_coordinate &mc) const {
  41                         if (degree < mc.degree
  42                          || degree == mc.degree && y < mc.y
  43                          || degree == mc.degree && y == mc.y && x < mc.x)
  44                                 return 1;
  45
  46                         return 0;
  47                 }
  48         };
  49
  50 private:
  51         static ale_pos _multi_decomp;
  52
  53         typedef unsigned int index_t;
  54
  55         std::vector<trans_single> trans_stack;
  56         std::vector<multi_coordinate> coord_stack;
  57         std::map<multi_coordinate, index_t> coordinate_map;
  58
  59         int use_multi;
  60         index_t current_element;
  61
  62         index_t orig_ref_height, orig_ref_width;
  63         index_t cur_ref_height, cur_ref_width;
  64         point cur_offset;
  65         point orig_offset;
  66
  67         index_t *spatio_elem_map;
  68         index_t *spatio_elem_map_r;
  69
  70         void push_element() {
  71                 assert (trans_stack.size() > 0);
  72
  73                 if (++current_element == trans_stack.size())
  74                         trans_stack.push_back(trans_stack.back());
  75         }
  76
  77         trans_multi() : trans_stack() {
  78                 use_multi = 0;
  79                 current_element = 0;
  80                 orig_ref_height = 0;
  81                 orig_ref_width = 0;
  82                 cur_ref_height = 0;
  83                 cur_ref_width = 0;
  84                 spatio_elem_map = NULL;
  85                 spatio_elem_map_r = NULL;
  86         }
  87
  88 public:
  89
  90         static void set_md(double d) {
  91                 _multi_decomp = d;
  92         }
  93
  94         /*
  95          * Calculate euclidean identity transform for a given image.
  96          */
  97         static struct trans_multi eu_identity(const image *i = NULL, ale_pos scale_factor = 1) {
  98                 struct trans_multi r;
  99                 multi_coordinate mc;
 100
 101                 mc.degree = 0;
 102                 mc.x = 0;
 103                 mc.y = 0;
 104
 105                 r.input_width = i ? i->width() : 2;
 106                 r.input_height = i ? i->height() : 2;
 107                 r.scale_factor = scale_factor;
 108                 r.trans_stack.push_back(trans_single::eu_identity(i, scale_factor));
 109                 r.coord_stack.push_back(mc);
 110                 r.coordinate_map[mc] = r.trans_stack.size() - 1;
 111                 r.current_element = 0;
 112                 return r;
 113         }
 114
 115         /*
 116          * Generate an array of identity transformations.
 117          */
 118         static trans_multi *new_eu_identity_array(unsigned int size) {
 119                 trans_multi *result = new trans_multi[size];
 120                 for (unsigned int i = 0; i < size; i++)
 121                         result[i] = eu_identity();
 122                 return result;
 123         }
 124
 125         /*
 126          * Calculate projective transformation parameters from a euclidean
 127          * transformation.
 128          */
 129         void eu_to_gpt() {
 130                 for (unsigned int t = 0; t < trans_stack.size(); t++)
 131                         trans_stack[t].eu_to_gpt();
 132         }
 133
 134         /*
 135          * Calculate projective identity transform for a given image.
 136          */
 137         static trans_multi gpt_identity(const image *i, ale_pos scale_factor) {
 138                 struct trans_multi r = eu_identity(i, scale_factor);
 139                 r.eu_to_gpt();
 140                 return r;
 141         }
 142
 143         trans_multi &operator=(const trans_multi &tm) {
 144                 this->trans_abstract::operator=(*((trans_abstract *) &tm));
 145
 146                 trans_stack = tm.trans_stack;
 147                 coord_stack = tm.coord_stack;
 148                 coordinate_map = tm.coordinate_map;
 149
 150                 use_multi = tm.use_multi;
 151                 current_element = tm.current_element;
 152
 153                 orig_ref_height = tm.orig_ref_height;
 154                 orig_ref_width = tm.orig_ref_width;
 155                 cur_ref_height = tm.cur_ref_height;
 156                 cur_ref_width = tm.cur_ref_width;
 157                 cur_offset = tm.cur_offset;
 158                 orig_offset = tm.orig_offset;
 159
 160                 free(spatio_elem_map);
 161                 free(spatio_elem_map_r);
 162                 spatio_elem_map = NULL;
 163                 spatio_elem_map_r = NULL;
 164
 165                 size_t cur_size = cur_ref_width * cur_ref_height * sizeof(index_t);
 166
 167                 if (cur_size > 0 && tm.spatio_elem_map) {
 168                         spatio_elem_map = (index_t *) malloc(cur_size);
 169                         assert (spatio_elem_map);
 170                         memcpy(spatio_elem_map, tm.spatio_elem_map, cur_size);
 171                 }
 172
 173                 cur_size = input_height * input_width * sizeof(index_t);
 174                 if (cur_size > 0 && tm.spatio_elem_map_r) {
 175                         spatio_elem_map_r = (index_t *) malloc(cur_size);
 176                         assert (spatio_elem_map_r);
 177                         memcpy(spatio_elem_map_r, tm.spatio_elem_map_r, cur_size);
 178                 }
 179
 180                 return *this;
 181         }
 182
 183         trans_multi(const trans_multi &tm) : trans_stack() {
 184                 spatio_elem_map = NULL;
 185                 spatio_elem_map_r = NULL;
 186                 operator=(tm);
 187         }
 188
 189         ~trans_multi() {
 190                 free(spatio_elem_map);
 191                 free(spatio_elem_map_r);
 192         }
 193
 194         trans_single get_element(index_t index) const {
 195                 assert (index < trans_stack.size());
 196
 197                 return trans_stack[index];
 198         }
 199
 200         trans_single get_element(multi_coordinate m) {
 201                 assert(coordinate_map.count(m));
 202                 index_t index = coordinate_map[m];
 203
 204                 return get_element(index);
 205         }
 206
 207         index_t get_index(multi_coordinate m) {
 208                 assert(coordinate_map.count(m));
 209                 return coordinate_map[m];
 210         }
 211
 212         int exists(multi_coordinate m) {
 213                 return coordinate_map.count(m);
 214         }
 215
 216         trans_single get_current_element() const {
 217                 return get_element(current_element);
 218         }
 219
 220         void set_element(index_t index, trans_single t) {
 221                 assert (index < trans_stack.size());
 222
 223                 trans_stack[index] = t;
 224         }
 225
 226         void set_current_element(trans_single t) {
 227                 set_element(current_element, t);
 228         }
 229
 230         void set_current_element(const trans_multi &t) {
 231                 set_element(current_element, t.get_current_element());
 232         }
 233
 234         index_t get_current_index() const {
 235                 return current_element;
 236         }
 237
 238         multi_coordinate get_current_coordinate() const {
 239                 return coord_stack[current_element];
 240         }
 241
 242         multi_coordinate get_coordinate(index_t i) const {
 243                 assert(i < trans_stack.size());
 244                 return coord_stack[i];
 245         }
 246
 247         void set_current_index(index_t i) {
 248                 assert (i < trans_stack.size());
 249                 current_element = i;
 250         }
 251
 252         /*
 253          * Set the bounds of the reference image after incorporation
 254          * of the original frame.
 255          */
 256         void set_original_bounds(const image *i) {
 257                 assert (orig_ref_width == 0);
 258                 assert (orig_ref_height == 0);
 259
 260                 orig_ref_height = i->height();
 261                 orig_ref_width = i->width();
 262                 orig_offset = i->offset();
 263
 264                 assert (orig_ref_width != 0);
 265                 assert (orig_ref_height != 0);
 266         }
 267
 268         static multi_coordinate parent_mc(multi_coordinate mc) {
 269                 multi_coordinate result;
 270
 271                 assert (mc.degree > 0);
 272
 273                 if (mc.degree == 1) {
 274                         result.degree = 0;
 275                         result.x = 0;
 276                         result.y = 0;
 277
 278                         return result;
 279                 }
 280
 281                 result.degree = mc.degree - 1;
 282                 result.x = (int) floor((double) mc.x / (double) 2);
 283                 result.y = (int) floor((double) mc.y / (double) 2);
 284
 285                 return result;
 286         }
 287
 288         index_t parent_index(index_t i) {
 289                 multi_coordinate mc = coord_stack[i];
 290                 multi_coordinate mcp = parent_mc(mc);
 291                 index_t result = coordinate_map[mcp];
 292
 293                 return result;
 294         }
 295
 296         /*
 297          * Set the bounds of the reference image after incorporation
 298          * of the most recent frame.
 299          */
 300         void set_current_bounds(const image *i) {
 301                 use_multi = 0;
 302                 free(spatio_elem_map);
 303                 free(spatio_elem_map_r);
 304                 spatio_elem_map = NULL;
 305                 spatio_elem_map_r = NULL;
 306
 307                 cur_ref_height = i->height();
 308                 cur_ref_width = i->width();
 309                 cur_offset = i->offset();
 310
 311                 int d; ale_pos div;
 312                 for (d = 1, div = 2;
 313                                 orig_ref_height / div >= _multi_decomp
 314                              && orig_ref_width  / div >= _multi_decomp
 315                              && _multi_decomp > 0;
 316                                 d++, div *= 2) {
 317
 318                         ale_pos height_scale = orig_ref_height / div;
 319                         ale_pos width_scale  = orig_ref_width  / div;
 320
 321                         for (int i = floor((cur_offset[0] - orig_offset[0]) / height_scale);
 322                                  i < ceil((cur_offset[0] - orig_offset[0] + cur_ref_height) / height_scale);
 323                                  i++)
 324                         for (int j = floor((cur_offset[1] - orig_offset[1]) / width_scale);
 325                                  j < ceil((cur_offset[1] - orig_offset[1] + cur_ref_width) / width_scale);
 326                                  j++) {
 327
 328                                  multi_coordinate c;
 329                                  c.degree = d;
 330                                  c.x = j;
 331                                  c.y = i;
 332
 333                                  if (!coordinate_map.count(c)) {
 334                                         multi_coordinate parent = parent_mc(c);
 335                                         assert (coordinate_map.count(parent));
 336                                         trans_stack.push_back(trans_stack[coordinate_map[parent]]);
 337                                         coord_stack.push_back(c);
 338                                         coordinate_map[c] = trans_stack.size() - 1;
 339                                 }
 340                         }
 341                 }
 342         }
 343
 344         index_t stack_depth() const {
 345                 return trans_stack.size();
 346         }
 347
 348         struct elem_bounds_t {
 349                 ale_pos imin, imax, jmin, jmax;
 350         };
 351
 352         elem_bounds_t elem_bounds() const {
 353                 elem_bounds_t result;
 354
 355                 result.imin = cur_offset[0] - orig_offset[0];
 356                 result.imax = result.imin + cur_ref_height;
 357                 result.jmin = cur_offset[1] - orig_offset[1];
 358                 result.jmax = result.jmin + cur_ref_width;
 359
 360                 if (current_element > 0) {
 361                         multi_coordinate mc = coord_stack[current_element];
 362
 363                         ale_pos height_scale = orig_ref_height / pow(2, mc.degree);
 364                         ale_pos width_scale  = orig_ref_width  / pow(2, mc.degree);
 365
 366                         if (height_scale * mc.y > result.imin)
 367                                 result.imin = height_scale * mc.y;
 368                         if (height_scale * (mc.y + 1) < result.imax)
 369                                 result.imax = height_scale * (mc.y + 1);
 370                         if (width_scale * mc.x > result.jmin)
 371                                 result.jmin = width_scale * mc.x;
 372                         if (width_scale * (mc.x + 1) < result.jmax)
 373                                 result.jmax = width_scale * (mc.x + 1);
 374                 }
 375
 376                 result.imin -= cur_offset[0] - orig_offset[0];
 377                 result.imax -= cur_offset[0] - orig_offset[0];
 378                 result.jmin -= cur_offset[1] - orig_offset[1];
 379                 result.jmax -= cur_offset[1] - orig_offset[1];
 380
 381
 382                 result.imin /= cur_ref_height;
 383                 result.imax /= cur_ref_height;
 384                 result.jmin /= cur_ref_width;
 385                 result.jmax /= cur_ref_width;
 386
 387                 return result;
 388         }
 389
 390         void set_multi(const image *cur_ref, const image *input) {
 391                 assert(use_multi == 0);
 392                 assert(spatio_elem_map == NULL);
 393                 assert(spatio_elem_map_r == NULL);
 394                 use_multi = 1;
 395
 396                 spatio_elem_map = (index_t *) calloc(
 397                                 cur_ref_height * cur_ref_width, sizeof(index_t));
 398                 assert(spatio_elem_map);
 399
 400                 spatio_elem_map_r = (index_t *) calloc(
 401                                 input_height * input_width, sizeof(index_t));
 402                 assert(spatio_elem_map_r);
 403
 404                 for (unsigned int i = 0; i < cur_ref_height; i++)
 405                 for (unsigned int j = 0; j < cur_ref_width;  j++) {
 406                         pixel rp = cur_ref->get_pixel(i, j);
 407                         int d; ale_pos div;
 408                         for (d = 1, div = 2; ; d++, div *= 2) {
 409                                 ale_pos height_scale = orig_ref_height / div;
 410                                 ale_pos width_scale = orig_ref_width / div;
 411                                 multi_coordinate c;
 412                                 c.degree = d;
 413                                 c.y = floor((cur_offset[0] - orig_offset[0] + i) / height_scale);
 414                                 c.x = floor((cur_offset[1] - orig_offset[1] + j) / width_scale);
 415                                 if (!coordinate_map.count(c))
 416                                         break;
 417                                 index_t index = coordinate_map[c];
 418                                 trans_single t = get_element(index);
 419                                 point p = t.scaled_inverse_transform(point(cur_offset[0] + i,
 420                                                                            cur_offset[1] + j));
 421                                 if (!input->in_bounds(p))
 422                                         continue;
 423
 424                                 trans_single s = get_element(spatio_elem_map[cur_ref_width * i + j]);
 425
 426                                 point q = s.scaled_inverse_transform(point(cur_offset[0] + i,
 427                                                                            cur_offset[1] + j));
 428
 429                                 if (input->in_bounds(q)) {
 430                                         pixel ip1 = input->get_bl(p);
 431                                         pixel ip0 = input->get_bl(q);
 432
 433                                         ale_real diff1 = (ip1 - rp).norm();
 434                                         ale_real diff0 = (ip0 - rp).norm();
 435
 436                                         if (diff1 < diff0)
 437                                                 spatio_elem_map[cur_ref_width * i + j] = index;
 438                                 }
 439
 440                                 int ii = (int) p[0];
 441                                 int jj = (int) p[1];
 442
 443                                 if (ii < 0 || (unsigned int) ii >= input_height
 444                                  || jj < 0 || (unsigned int) jj >= input_width)
 445                                         continue;
 446
 447                                 trans_single u = get_element(spatio_elem_map_r[input_width * ii + jj]);
 448                                 point r = u.transform_scaled(p);
 449
 450                                 if (cur_ref->in_bounds(r - cur_offset)) {
 451                                         pixel ip1 = input->get_bl(p);
 452                                         pixel rp0 = cur_ref->get_bl(r - cur_offset);
 453
 454                                         ale_real diff1 = (ip1 - rp).norm();
 455                                         ale_real diff0 = (ip1 - rp0).norm();
 456
 457                                         if (diff1 < diff0)
 458                                                 spatio_elem_map_r[input_width * ii + jj] = index;
 459                                 }
 460                         }
 461                 }
 462         }
 463
 464         /*
 465          * Returns non-zero if the transformation might be non-Euclidean.
 466          */
 467         int is_projective() const {
 468                 return trans_stack.front().is_projective();
 469         }
 470
 471         /*
 472          * Projective/Euclidean transformations
 473          */
 474         struct point pe(struct point p) const {
 475                 if (!use_multi)
 476                         return trans_stack.front().pe(p);
 477
 478                 int ii = (int) p[0];
 479                 int jj = (int) p[1];
 480
 481                 if (ii < 0 || (unsigned int) ii >= input_height
 482                  || jj < 0 || (unsigned int) jj >= input_width)
 483                         return trans_stack[0].pe(p);
 484
 485                 return trans_stack[spatio_elem_map_r[input_width * ii + jj]].pe(p);
 486         }
 487
 488         /*
 489          * Inverse transformations
 490          */
 491         struct point pei(struct point p) const {
 492                 if (!use_multi)
 493                         return trans_stack.front().pei(p);
 494
 495                 int i = (int) p[0];
 496                 int j = (int) p[1];
 497
 498                 if (i < 0 || (unsigned int) i >= cur_ref_height
 499                  || j < 0 || (unsigned int) j >= cur_ref_width)
 500                         return trans_stack[0].pei(p);
 501
 502                 return trans_stack[spatio_elem_map[cur_ref_width * i + j]].pei(p);
 503         }
 504
 505
 506         /*
 507          * Modify a euclidean transform in the indicated manner.
 508          */
 509         void eu_modify(int i1, ale_pos diff) {
 510                 trans_stack[current_element].eu_modify(i1, diff);
 511         }
 512
 513         /*
 514          * Rotate about a given point in the original reference frame.
 515          */
 516         void eu_rotate_about_scaled(point center, ale_pos diff) {
 517                 trans_stack[current_element].eu_rotate_about_scaled(center, diff);
 518         }
 519
 520         /*
 521          * Modify all euclidean parameters at once.
 522          */
 523         void eu_set(ale_pos eu[3]) {
 524                 trans_stack[current_element].eu_set(eu);
 525         }
 526
 527         /*
 528          * Get the specified euclidean parameter
 529          */
 530         ale_pos eu_get(int param) const {
 531                 return trans_stack[current_element].eu_get(param);
 532         }
 533
 534         /*
 535          * Modify a projective transform in the indicated manner.
 536          */
 537         void gpt_modify(int i1, int i2, ale_pos diff) {
 538                 trans_stack[current_element].gpt_modify(i1, i2, diff);
 539         }
 540
 541         /*
 542          * Modify a projective transform according to the group operation.
 543          */
 544         void gr_modify(int i1, int i2, ale_pos diff) {
 545                 trans_stack[current_element].gr_modify(i1, i2, diff);
 546         }
 547
 548         /*
 549          * Modify all projective parameters at once.
 550          */
 551         void gpt_set(point x[4]) {
 552                 trans_stack[current_element].gpt_set(x);
 553         }
 554
 555         void gpt_set(point x1, point x2, point x3, point x4) {
 556                 trans_stack[current_element].gpt_set(x1, x2, x3, x4);
 557         }
 558
 559         void snap(ale_pos interval) {
 560                 trans_stack[current_element].snap(interval);
 561         }
 562
 563         /*
 564          * Get the specified projective parameter
 565          */
 566         point gpt_get(int point) const {
 567                 return trans_stack[current_element].gpt_get(point);
 568         }
 569
 570         /*
 571          * Get the specified projective parameter
 572          */
 573         ale_pos gpt_get(int point, int dim) {
 574                 return trans_stack[current_element].gpt_get(point, dim);
 575         }
 576
 577         /*
 578          * Translate by a given amount
 579          */
 580         void translate(point p) {
 581                 trans_stack[current_element].translate(p);
 582         }
 583
 584         /*
 585          * Rotate by a given amount about a given point.
 586          */
 587         void rotate(point p, ale_pos degrees) {
 588                 trans_stack[current_element].rotate(p, degrees);
 589         }
 590
 591         void reset_memos() {
 592                 for (unsigned int t = 0; t < trans_stack.size(); t++)
 593                         trans_stack[t].reset_memos();
 594         }
 595
 596         /*
 597          * Rescale a transform with a given factor.
 598          */
 599         void specific_rescale(ale_pos factor) {
 600
 601                 /*
 602                  * Ensure that no maps exist.
 603                  */
 604
 605                 assert (use_multi == 0);
 606                 assert (spatio_elem_map == NULL);
 607                 assert (spatio_elem_map_r == NULL);
 608
 609                 trans_stack[current_element].rescale(factor);
 610         }
 611
 612         /*
 613          * Set the dimensions of the image.
 614          */
 615         void specific_set_dimensions(const image *im) {
 616                 for (unsigned int t = 0; t < trans_stack.size(); t++)
 617                         trans_stack[t].set_dimensions(im);
 618         }
 619
 620         /*
 621          * Modify all projective parameters at once.  Accommodate bugs in the
 622          * version 0 transformation file handler (ALE versions 0.4.0p1 and
 623          * earlier).  This code is only called when using a transformation data
 624          * file created with an old version of ALE.
 625          */
 626         void gpt_v0_set(point x[4]) {
 627                 trans_stack[current_element].gpt_v0_set(x);
 628         }
 629
 630         /*
 631          * Modify all euclidean parameters at once.  Accommodate bugs in the
 632          * version 0 transformation file handler (ALE versions 0.4.0p1 and
 633          * earlier).  This code is only called when using a transformation data
 634          * file created with an old version of ALE.
 635          */
 636         void eu_v0_set(ale_pos eu[3]) {
 637                 trans_stack[current_element].eu_v0_set(eu);
 638         }
 639
 640         void debug_output() {
 641                 for (unsigned int t = 0; t < trans_stack.size(); t++)
 642                         trans_stack[t].debug_output();
 643         }
 644 };
 645
 646 #endif