1 // Copyright 2002, 2004, 2007 David Hilvert <dhilvert@auricle.dyndns.org>,
2 // <dhilvert@ugcs.caltech.edu>
4 /* This file is part of the Anti-Lamenessing Engine.
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.
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.
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
22 * trans_multi.h: Represent multiple transformations, affecting different
26 #ifndef __trans_multi_h__
27 #define __trans_multi_h__
29 #include "trans_abstract.h"
30 #include "trans_single.h"
32 struct trans_multi
: public trans_abstract
{
34 struct multi_coordinate
{
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
)
51 static ale_pos _multi_decomp
;
52 static ale_real _multi_improvement
;
54 typedef unsigned int index_t
;
56 std::vector
<trans_single
> trans_stack
;
57 std::vector
<multi_coordinate
> coord_stack
;
58 std::map
<multi_coordinate
, index_t
> coordinate_map
;
61 index_t current_element
;
63 index_t orig_ref_height
, orig_ref_width
;
64 index_t cur_ref_height
, cur_ref_width
;
68 index_t
*spatio_elem_map
;
69 index_t
*spatio_elem_map_r
;
72 assert (trans_stack
.size() > 0);
74 if (++current_element
== trans_stack
.size())
75 trans_stack
.push_back(trans_stack
.back());
78 trans_multi() : trans_stack() {
85 spatio_elem_map
= NULL
;
86 spatio_elem_map_r
= NULL
;
91 static void set_md(double d
) {
95 static void set_mi(double d
) {
96 _multi_improvement
= d
;
100 * Calculate euclidean identity transform for a given image.
102 static struct trans_multi
eu_identity(const image
*i
= NULL
, ale_pos scale_factor
= 1) {
103 struct trans_multi r
;
110 r
.input_width
= i
? i
->width() : 2;
111 r
.input_height
= i
? i
->height() : 2;
112 r
.scale_factor
= scale_factor
;
113 r
.trans_stack
.push_back(trans_single::eu_identity(i
, scale_factor
));
114 r
.coord_stack
.push_back(mc
);
115 r
.coordinate_map
[mc
] = r
.trans_stack
.size() - 1;
116 r
.current_element
= 0;
121 * Generate an array of identity transformations.
123 static trans_multi
*new_eu_identity_array(unsigned int size
) {
124 trans_multi
*result
= new trans_multi
[size
];
125 for (unsigned int i
= 0; i
< size
; i
++)
126 result
[i
] = eu_identity();
131 * Calculate projective transformation parameters from a euclidean
135 for (unsigned int t
= 0; t
< trans_stack
.size(); t
++)
136 trans_stack
[t
].eu_to_gpt();
140 * Calculate projective identity transform for a given image.
142 static trans_multi
gpt_identity(const image
*i
, ale_pos scale_factor
) {
143 struct trans_multi r
= eu_identity(i
, scale_factor
);
148 trans_multi
&operator=(const trans_multi
&tm
) {
149 this->trans_abstract::operator=(*((trans_abstract
*) &tm
));
151 trans_stack
= tm
.trans_stack
;
152 coord_stack
= tm
.coord_stack
;
153 coordinate_map
= tm
.coordinate_map
;
155 use_multi
= tm
.use_multi
;
156 current_element
= tm
.current_element
;
158 orig_ref_height
= tm
.orig_ref_height
;
159 orig_ref_width
= tm
.orig_ref_width
;
160 cur_ref_height
= tm
.cur_ref_height
;
161 cur_ref_width
= tm
.cur_ref_width
;
162 cur_offset
= tm
.cur_offset
;
163 orig_offset
= tm
.orig_offset
;
165 free(spatio_elem_map
);
166 free(spatio_elem_map_r
);
167 spatio_elem_map
= NULL
;
168 spatio_elem_map_r
= NULL
;
170 size_t cur_size
= cur_ref_width
* cur_ref_height
* sizeof(index_t
);
172 if (cur_size
> 0 && tm
.spatio_elem_map
) {
173 spatio_elem_map
= (index_t
*) malloc(cur_size
);
174 assert (spatio_elem_map
);
175 memcpy(spatio_elem_map
, tm
.spatio_elem_map
, cur_size
);
178 cur_size
= input_height
* input_width
* sizeof(index_t
);
179 if (cur_size
> 0 && tm
.spatio_elem_map_r
) {
180 spatio_elem_map_r
= (index_t
*) malloc(cur_size
);
181 assert (spatio_elem_map_r
);
182 memcpy(spatio_elem_map_r
, tm
.spatio_elem_map_r
, cur_size
);
188 trans_multi(const trans_multi
&tm
) : trans_stack() {
189 spatio_elem_map
= NULL
;
190 spatio_elem_map_r
= NULL
;
195 free(spatio_elem_map
);
196 free(spatio_elem_map_r
);
199 trans_single
get_element(index_t index
) const {
200 assert (index
< trans_stack
.size());
202 return trans_stack
[index
];
205 trans_single
get_element(multi_coordinate m
) {
206 assert(coordinate_map
.count(m
));
207 index_t index
= coordinate_map
[m
];
209 return get_element(index
);
212 index_t
get_index(multi_coordinate m
) {
213 assert(coordinate_map
.count(m
));
214 return coordinate_map
[m
];
217 int exists(multi_coordinate m
) {
218 return coordinate_map
.count(m
);
221 trans_single
get_current_element() const {
222 return get_element(current_element
);
225 void set_element(index_t index
, trans_single t
) {
226 assert (index
< trans_stack
.size());
228 trans_stack
[index
] = t
;
231 void set_current_element(trans_single t
) {
232 set_element(current_element
, t
);
235 void set_current_element(const trans_multi
&t
) {
236 set_element(current_element
, t
.get_current_element());
239 index_t
get_current_index() const {
240 return current_element
;
243 multi_coordinate
get_current_coordinate() const {
244 return coord_stack
[current_element
];
247 multi_coordinate
get_coordinate(index_t i
) const {
248 assert(i
< trans_stack
.size());
249 return coord_stack
[i
];
252 void set_current_index(index_t i
) {
253 assert (i
< trans_stack
.size());
258 * Set the bounds of the reference image after incorporation
259 * of the original frame.
261 void set_original_bounds(const image
*i
) {
262 assert (orig_ref_width
== 0);
263 assert (orig_ref_height
== 0);
265 orig_ref_height
= i
->height();
266 orig_ref_width
= i
->width();
267 orig_offset
= i
->offset();
269 assert (orig_ref_width
!= 0);
270 assert (orig_ref_height
!= 0);
273 static multi_coordinate
parent_mc(multi_coordinate mc
) {
274 multi_coordinate result
;
276 assert (mc
.degree
> 0);
278 if (mc
.degree
== 1) {
286 result
.degree
= mc
.degree
- 1;
287 result
.x
= (int) floor((double) mc
.x
/ (double) 2);
288 result
.y
= (int) floor((double) mc
.y
/ (double) 2);
293 index_t
parent_index(index_t i
) {
294 multi_coordinate mc
= coord_stack
[i
];
295 multi_coordinate mcp
= parent_mc(mc
);
296 index_t result
= coordinate_map
[mcp
];
302 * Set the bounds of the reference image after incorporation
303 * of the most recent frame.
305 void set_current_bounds(const image
*i
) {
307 free(spatio_elem_map
);
308 free(spatio_elem_map_r
);
309 spatio_elem_map
= NULL
;
310 spatio_elem_map_r
= NULL
;
312 cur_ref_height
= i
->height();
313 cur_ref_width
= i
->width();
314 cur_offset
= i
->offset();
318 orig_ref_height
/ div
>= _multi_decomp
319 && orig_ref_width
/ div
>= _multi_decomp
320 && _multi_decomp
> 0;
323 ale_pos height_scale
= orig_ref_height
/ div
;
324 ale_pos width_scale
= orig_ref_width
/ div
;
326 for (int i
= floor((cur_offset
[0] - orig_offset
[0]) / height_scale
);
327 i
< ceil((cur_offset
[0] - orig_offset
[0] + cur_ref_height
) / height_scale
);
329 for (int j
= floor((cur_offset
[1] - orig_offset
[1]) / width_scale
);
330 j
< ceil((cur_offset
[1] - orig_offset
[1] + cur_ref_width
) / width_scale
);
338 if (!coordinate_map
.count(c
)) {
339 multi_coordinate parent
= parent_mc(c
);
340 assert (coordinate_map
.count(parent
));
341 trans_stack
.push_back(trans_stack
[coordinate_map
[parent
]]);
342 coord_stack
.push_back(c
);
343 coordinate_map
[c
] = trans_stack
.size() - 1;
349 index_t
stack_depth() const {
350 return trans_stack
.size();
353 struct elem_bounds_int_t
{
354 unsigned int imin
, imax
, jmin
, jmax
;
356 int satisfies_min_dim(unsigned int min_dimension
) {
357 if (imax
- imin
< min_dimension
358 || jmax
- jmin
< min_dimension
)
365 struct elem_bounds_t
{
366 ale_pos imin
, imax
, jmin
, jmax
;
368 elem_bounds_int_t
scale_to_bounds(unsigned int height
, unsigned int width
) {
380 f
.imin
= (unsigned int) floor(e
.imin
);
384 f
.imax
= (unsigned int) ceil(e
.imax
);
388 f
.jmin
= (unsigned int) floor(e
.jmin
);
392 f
.jmax
= (unsigned int) ceil(e
.jmax
);
400 elem_bounds_t
elem_bounds() const {
401 elem_bounds_t result
;
403 result
.imin
= cur_offset
[0] - orig_offset
[0];
404 result
.imax
= result
.imin
+ cur_ref_height
;
405 result
.jmin
= cur_offset
[1] - orig_offset
[1];
406 result
.jmax
= result
.jmin
+ cur_ref_width
;
408 if (current_element
> 0) {
409 multi_coordinate mc
= coord_stack
[current_element
];
411 ale_pos height_scale
= orig_ref_height
/ pow(2, mc
.degree
);
412 ale_pos width_scale
= orig_ref_width
/ pow(2, mc
.degree
);
414 if (height_scale
* mc
.y
> result
.imin
)
415 result
.imin
= height_scale
* mc
.y
;
416 if (height_scale
* (mc
.y
+ 1) < result
.imax
)
417 result
.imax
= height_scale
* (mc
.y
+ 1);
418 if (width_scale
* mc
.x
> result
.jmin
)
419 result
.jmin
= width_scale
* mc
.x
;
420 if (width_scale
* (mc
.x
+ 1) < result
.jmax
)
421 result
.jmax
= width_scale
* (mc
.x
+ 1);
424 result
.imin
-= cur_offset
[0] - orig_offset
[0];
425 result
.imax
-= cur_offset
[0] - orig_offset
[0];
426 result
.jmin
-= cur_offset
[1] - orig_offset
[1];
427 result
.jmax
-= cur_offset
[1] - orig_offset
[1];
430 result
.imin
/= cur_ref_height
;
431 result
.imax
/= cur_ref_height
;
432 result
.jmin
/= cur_ref_width
;
433 result
.jmax
/= cur_ref_width
;
438 void set_multi(const image
*cur_ref
, const image
*input
) {
439 assert(use_multi
== 0);
440 assert(spatio_elem_map
== NULL
);
441 assert(spatio_elem_map_r
== NULL
);
444 spatio_elem_map
= (index_t
*) calloc(
445 cur_ref_height
* cur_ref_width
, sizeof(index_t
));
446 assert(spatio_elem_map
);
448 spatio_elem_map_r
= (index_t
*) calloc(
449 input_height
* input_width
, sizeof(index_t
));
450 assert(spatio_elem_map_r
);
452 for (unsigned int i
= 0; i
< cur_ref_height
; i
++)
453 for (unsigned int j
= 0; j
< cur_ref_width
; j
++) {
454 pixel rp
= cur_ref
->get_pixel(i
, j
);
456 for (d
= 1, div
= 2; ; d
++, div
*= 2) {
457 ale_pos height_scale
= orig_ref_height
/ div
;
458 ale_pos width_scale
= orig_ref_width
/ div
;
461 c
.y
= floor((cur_offset
[0] - orig_offset
[0] + i
) / height_scale
);
462 c
.x
= floor((cur_offset
[1] - orig_offset
[1] + j
) / width_scale
);
463 if (!coordinate_map
.count(c
))
465 index_t index
= coordinate_map
[c
];
466 trans_single t
= get_element(index
);
467 point p0
= point(cur_offset
[0] + i
, cur_offset
[1] + j
);
468 point p
= t
.scaled_inverse_transform(p0
);
469 if (!input
->in_bounds(p
))
472 trans_single s
= get_element(spatio_elem_map
[cur_ref_width
* i
+ j
]);
474 point q
= s
.scaled_inverse_transform(p0
);
476 pixel pt
= t
.get_tonal_multiplier(p0
);
477 pixel qt
= s
.get_tonal_multiplier(p0
);
479 if (input
->in_bounds(q
)) {
480 pixel ip1
= input
->get_bl(p
);
481 pixel ip0
= input
->get_bl(q
);
483 ale_real diff1
= (pt
* ip1
- rp
).norm();
484 ale_real diff0
= (qt
* ip0
- rp
).norm();
486 if (diff1
< diff0
* (1 - _multi_improvement
))
487 spatio_elem_map
[cur_ref_width
* i
+ j
] = index
;
493 if (ii
< 0 || (unsigned int) ii
>= input_height
494 || jj
< 0 || (unsigned int) jj
>= input_width
)
497 trans_single u
= get_element(spatio_elem_map_r
[input_width
* ii
+ jj
]);
498 point r
= u
.transform_scaled(p
);
500 pixel ut
= u
.get_tonal_multiplier(r
);
502 if (cur_ref
->in_bounds(r
- cur_offset
)) {
503 pixel ip1
= input
->get_bl(p
);
504 pixel rp0
= cur_ref
->get_bl(r
- cur_offset
);
506 ale_real diff1
= (pt
* ip1
- rp
).norm();
507 ale_real diff0
= (ut
* ip1
- rp0
).norm();
509 if (diff1
< diff0
* (1 - _multi_improvement
))
510 spatio_elem_map_r
[input_width
* ii
+ jj
] = index
;
517 * Returns non-zero if the transformation might be non-Euclidean.
519 int is_projective() const {
520 return trans_stack
[current_element
].is_projective();
524 * Projective/Euclidean transformations
526 struct point
pe(struct point p
) const {
528 return trans_stack
[current_element
].pe(p
);
533 if (ii
< 0 || (unsigned int) ii
>= input_height
534 || jj
< 0 || (unsigned int) jj
>= input_width
)
535 return trans_stack
[0].pe(p
);
537 return trans_stack
[spatio_elem_map_r
[input_width
* ii
+ jj
]].pe(p
);
541 * Inverse transformations
543 struct point
pei(struct point p
) const {
545 return trans_stack
[current_element
].pei(p
);
550 if (i
< 0 || (unsigned int) i
>= cur_ref_height
551 || j
< 0 || (unsigned int) j
>= cur_ref_width
)
552 return trans_stack
[0].pei(p
);
554 return trans_stack
[spatio_elem_map
[cur_ref_width
* i
+ j
]].pei(p
);
557 pixel
get_tonal_multiplier(struct point p
) const {
559 return trans_stack
[current_element
].get_tonal_multiplier(p
);
564 if (i
< 0 || (unsigned int) i
>= cur_ref_height
565 || j
< 0 || (unsigned int) j
>= cur_ref_width
)
566 return trans_stack
[0].get_tonal_multiplier(p
);
568 return trans_stack
[spatio_elem_map
[cur_ref_width
* i
+ j
]].get_tonal_multiplier(p
);
571 pixel
get_inverse_tonal_multiplier(struct point p
) const {
573 return trans_stack
[current_element
].get_inverse_tonal_multiplier(p
);
578 if (i
< 0 || (unsigned int) i
>= input_height
579 || j
< 0 || (unsigned int) j
>= input_width
)
580 return trans_stack
[0].get_inverse_tonal_multiplier(p
);
582 return trans_stack
[spatio_elem_map_r
[input_width
* i
+ j
]].get_inverse_tonal_multiplier(p
);
585 void set_tonal_multiplier(pixel p
) {
586 trans_stack
[current_element
].set_tonal_multiplier(p
);
590 * Modify a euclidean transform in the indicated manner.
592 void eu_modify(int i1
, ale_pos diff
) {
593 trans_stack
[current_element
].eu_modify(i1
, diff
);
597 * Rotate about a given point in the original reference frame.
599 void eu_rotate_about_scaled(point center
, ale_pos diff
) {
600 trans_stack
[current_element
].eu_rotate_about_scaled(center
, diff
);
604 * Modify all euclidean parameters at once.
606 void eu_set(ale_pos eu
[3]) {
607 trans_stack
[current_element
].eu_set(eu
);
611 * Get the specified euclidean parameter
613 ale_pos
eu_get(int param
) const {
614 return trans_stack
[current_element
].eu_get(param
);
618 * Modify a projective transform in the indicated manner.
620 void gpt_modify(int i1
, int i2
, ale_pos diff
) {
621 trans_stack
[current_element
].gpt_modify(i1
, i2
, diff
);
625 * Modify a projective transform according to the group operation.
627 void gr_modify(int i1
, int i2
, ale_pos diff
) {
628 trans_stack
[current_element
].gr_modify(i1
, i2
, diff
);
632 * Modify all projective parameters at once.
634 void gpt_set(point x
[4]) {
635 trans_stack
[current_element
].gpt_set(x
);
638 void gpt_set(point x1
, point x2
, point x3
, point x4
) {
639 trans_stack
[current_element
].gpt_set(x1
, x2
, x3
, x4
);
642 void snap(ale_pos interval
) {
643 trans_stack
[current_element
].snap(interval
);
647 * Get the specified projective parameter
649 point
gpt_get(int point
) const {
650 return trans_stack
[current_element
].gpt_get(point
);
654 * Get the specified projective parameter
656 ale_pos
gpt_get(int point
, int dim
) {
657 return trans_stack
[current_element
].gpt_get(point
, dim
);
661 * Translate by a given amount
663 void translate(point p
) {
664 trans_stack
[current_element
].translate(p
);
668 * Rotate by a given amount about a given point.
670 void rotate(point p
, ale_pos degrees
) {
671 trans_stack
[current_element
].rotate(p
, degrees
);
675 for (unsigned int t
= 0; t
< trans_stack
.size(); t
++)
676 trans_stack
[t
].reset_memos();
680 * Rescale a transform with a given factor.
682 void specific_rescale(ale_pos factor
) {
685 * Ensure that no maps exist.
688 assert (use_multi
== 0);
689 assert (spatio_elem_map
== NULL
);
690 assert (spatio_elem_map_r
== NULL
);
692 trans_stack
[current_element
].rescale(factor
);
696 * Set the dimensions of the image.
698 void specific_set_dimensions(const image
*im
) {
699 for (unsigned int t
= 0; t
< trans_stack
.size(); t
++)
700 trans_stack
[t
].set_dimensions(im
);
704 * Modify all projective parameters at once. Accommodate bugs in the
705 * version 0 transformation file handler (ALE versions 0.4.0p1 and
706 * earlier). This code is only called when using a transformation data
707 * file created with an old version of ALE.
709 void gpt_v0_set(point x
[4]) {
710 trans_stack
[current_element
].gpt_v0_set(x
);
714 * Modify all euclidean parameters at once. Accommodate bugs in the
715 * version 0 transformation file handler (ALE versions 0.4.0p1 and
716 * earlier). This code is only called when using a transformation data
717 * file created with an old version of ALE.
719 void eu_v0_set(ale_pos eu
[3]) {
720 trans_stack
[current_element
].eu_v0_set(eu
);
723 void debug_output() {
724 for (unsigned int t
= 0; t
< trans_stack
.size(); t
++)
725 trans_stack
[t
].debug_output();