2 * Copyright 2002, 2004, 2005, 2006, 2007, 2008, 2009 David Hilvert <dhilvert@gmail.com>
4 * This file is part of libale.
6 * libale is free software: you can redistribute it and/or modify it under the
7 * terms of the GNU Affero General Public License as published by the Free
8 * Software Foundation, either version 3 of the License, or (at your option)
11 * libale is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for
16 * You should have received a copy of the GNU Affero General Public License
17 * along with libale. If not, see <http://www.gnu.org/licenses/>.
27 * Types for scale clusters.
33 * Experimental non-linear scaling approach.
36 struct nl_scale_cluster
{
39 ale_image certainty_max
;
40 ale_image certainty_min
;
41 ale_image aweight_max
;
42 ale_image aweight_min
;
43 ale_exclusion_list ax_parameters
;
46 ale_image input_certainty_max
;
47 ale_image input_certainty_min
;
53 struct scale_cluster
{
57 ale_exclusion_list ax_parameters
;
60 ale_image input_certainty
;
64 nl_scale_cluster
*nl_scale_clusters
;
69 static struct scale_cluster
*init_clusters(ale_context ac
, int frame
, ale_pos scale_factor
,
70 ale_image input_frame
, ale_image reference_image
,
71 unsigned int steps
, ale_exclusion_list ax
) {
74 * Allocate memory for the array.
77 struct scale_cluster
*scale_clusters
=
78 (struct scale_cluster
*) malloc(steps
* sizeof(struct scale_cluster
));
84 * Prepare images and exclusion regions for the highest level
88 scale_clusters
[0].accum
= reference_image
;
90 ale_context_signal(ac
, "ui_constructing_lod_clusters", 0.0);
92 scale_clusters
[0].input_scale
= scale_factor
;
93 if (scale_factor
< 1.0 && interpolant
== NULL
)
94 scale_clusters
[0].input
= input_frame
->scale(scale_factor
, "alignment");
96 scale_clusters
[0].input
= input_frame
;
98 scale_clusters
[0].certainty
= reference_defined
;
99 scale_clusters
[0].aweight
= alignment_weights
;
100 scale_clusters
[0].ax_parameters
= filter_ax_parameters(frame
, local_ax_count
);
103 * Allocate and determine input frame certainty.
106 if (scale_clusters
[0].input
->get_bayer() != IMAGE_BAYER_NONE
) {
107 scale_clusters
[0].input_certainty
= new_image_bayer_ale_real(
108 scale_clusters
[0].input
->height(),
109 scale_clusters
[0].input
->width(),
110 scale_clusters
[0].input
->depth(),
111 scale_clusters
[0].input
->get_bayer());
113 scale_clusters
[0].input_certainty
= scale_clusters
[0].input
->clone("certainty");
116 for (unsigned int i
= 0; i
< scale_clusters
[0].input_certainty
->height(); i
++)
117 for (unsigned int j
= 0; j
< scale_clusters
[0].input_certainty
->width(); j
++)
118 for (unsigned int k
= 0; k
< 3; k
++)
119 if (scale_clusters
[0].input
->get_channels(i
, j
) & (1 << k
))
120 ((image
*) scale_clusters
[0].input_certainty
)->set_chan(i
, j
, k
,
121 scale_clusters
[0].input
->
122 exp().confidence(scale_clusters
[0].input
->get_pixel(i
, j
))[k
]);
124 scale_ax_parameters(*local_ax_count
, scale_clusters
[0].ax_parameters
, scale_factor
,
125 (scale_factor
< 1.0 && interpolant
== NULL
) ? scale_factor
: (ale_pos
) 1);
127 init_nl_cluster(&(scale_clusters
[0]));
130 * Prepare reduced-detail images and exclusion
134 for (unsigned int step
= 1; step
< steps
; step
++) {
135 ui::get()->constructing_lod_clusters(step
);
136 scale_clusters
[step
].accum
= prepare_lod(scale_clusters
[step
- 1].accum
);
137 scale_clusters
[step
].certainty
= prepare_lod_def(scale_clusters
[step
- 1].certainty
);
138 scale_clusters
[step
].aweight
= prepare_lod_def(scale_clusters
[step
- 1].aweight
);
139 scale_clusters
[step
].ax_parameters
140 = copy_ax_parameters(*local_ax_count
, scale_clusters
[step
- 1].ax_parameters
);
142 double sf
= scale_clusters
[step
- 1].input_scale
/ 2;
143 scale_clusters
[step
].input_scale
= sf
;
145 if (sf
>= 1.0 || interpolant
!= NULL
) {
146 scale_clusters
[step
].input
= scale_clusters
[step
- 1].input
;
147 scale_clusters
[step
].input_certainty
= scale_clusters
[step
- 1].input_certainty
;
148 scale_ax_parameters(*local_ax_count
, scale_clusters
[step
].ax_parameters
, 0.5, 1);
149 } else if (sf
> 0.5) {
150 scale_clusters
[step
].input
= scale_clusters
[step
- 1].input
->scale(sf
, "alignment");
151 scale_clusters
[step
].input_certainty
= scale_clusters
[step
- 1].input
->scale(sf
, "alignment", 1);
152 scale_ax_parameters(*local_ax_count
, scale_clusters
[step
].ax_parameters
, 0.5, sf
);
154 scale_clusters
[step
].input
= scale_clusters
[step
- 1].input
->scale(0.5, "alignment");
155 scale_clusters
[step
].input_certainty
= scale_clusters
[step
- 1].input_certainty
->scale(0.5, "alignment", 1);
156 scale_ax_parameters(*local_ax_count
, scale_clusters
[step
].ax_parameters
, 0.5, 0.5);
159 init_nl_cluster(&(scale_clusters
[step
]));
162 return scale_clusters
;
165 static diff_stat_t
_align_element(ale_pos perturb
, ale_pos local_lower
,
166 scale_cluster
*scale_clusters
, diff_stat_t here
,
167 ale_pos adj_p
, ale_pos adj_o
, ale_pos adj_b
,
168 ale_pos
*current_bd
, ale_pos
*modified_bd
,
169 astate_t
*astate
, int lod
, scale_cluster si
) {
172 * Run initial tests to get perturbation multipliers and error
176 std::vector
<d2::trans_single
> t_set
;
178 here
.get_perturb_set(&t_set
, adj_p
, adj_o
, adj_b
, current_bd
, modified_bd
);
180 int stable_count
= 0;
182 while (perturb
>= local_lower
) {
184 ui::get()->alignment_dims(scale_clusters
[lod
].accum
->height(), scale_clusters
[lod
].accum
->width(),
185 scale_clusters
[lod
].input
->height(), scale_clusters
[lod
].input
->width());
188 * Orientational adjustment value in degrees.
190 * Since rotational perturbation is now specified as an
191 * arclength, we have to convert.
194 ale_pos adj_o
= 2 * (double) perturb
195 / sqrt(pow(scale_clusters
[0].input
->height(), 2)
196 + pow(scale_clusters
[0].input
->width(), 2))
201 * Barrel distortion adjustment value
204 ale_pos adj_b
= perturb
* bda_mult
;
206 trans_single old_offset
= here
.get_offset();
208 here
.perturb_test(perturb
, adj_p
, adj_o
, adj_b
, current_bd
, modified_bd
,
211 if (here
.get_offset() == old_offset
)
216 if (stable_count
== 3) {
223 && lod
> lrint(log(perturb
) / log(2)) - lod_preferred
) {
226 * Work with images twice as large
230 si
= scale_clusters
[lod
];
233 * Rescale the transforms.
236 ale_pos rescale_factor
= (double) scale_factor
237 / (double) pow(2, lod
)
238 / (double) here
.get_offset().scale();
240 here
.rescale(rescale_factor
, si
);
243 adj_p
= perturb
/ pow(2, lod
);
250 ui::get()->alignment_perturbation_level(perturb
, lod
);
253 ui::get()->set_match(here
.get_error());
254 ui::get()->set_offset(here
.get_offset());
258 ale_pos rescale_factor
= (double) scale_factor
259 / (double) here
.get_offset().scale();
261 here
.rescale(rescale_factor
, scale_clusters
[0]);
268 * Align frame m against the reference.
270 * XXX: the transformation class currently combines ordinary
271 * transformations with scaling. This is somewhat convenient for
272 * some things, but can also be confusing. This method, _align(), is
273 * one case where special care must be taken to ensure that the scale
274 * is always set correctly (by using the 'rescale' method).
276 static diff_stat_multi
_align(int m
, int local_gs
, astate_t
*astate
) {
278 ale_image input_frame
= astate
->get_input_frame();
281 * Local upper/lower data, possibly dependent on image
285 ale_pos local_lower
, local_upper
;
286 ale_accum local_gs_mo
;
289 * Select the minimum dimension as the reference.
292 ale_pos reference_size
= input_frame
->height();
293 if (input_frame
->width() < reference_size
)
294 reference_size
= input_frame
->width();
295 ale_accum reference_area
= input_frame
->height()
296 * input_frame
->width();
298 if (perturb_lower_percent
)
299 local_lower
= (double) perturb_lower
300 * (double) reference_size
302 * (double) scale_factor
;
304 local_lower
= perturb_lower
;
306 if (perturb_upper_percent
)
307 local_upper
= (double) perturb_upper
308 * (double) reference_size
310 * (double) scale_factor
;
312 local_upper
= perturb_upper
;
314 local_upper
= pow(2, floor(log(local_upper
) / log(2)));
317 local_gs_mo
= (double) _gs_mo
318 * (double) reference_area
320 * (double) scale_factor
;
322 local_gs_mo
= _gs_mo
;
325 * Logarithms aren't exact, so we divide repeatedly to discover
326 * how many steps will occur, and pass this information to the
331 double step_variable
= local_upper
;
332 while (step_variable
>= local_lower
) {
337 ale_pos perturb
= local_upper
;
340 kept_t
[latest
] = latest_t
;
341 kept_ok
[latest
] = latest_ok
;
345 * Determine how many levels of detail should be prepared, by
346 * calculating the initial (largest) value for the
347 * level-of-detail variable.
350 int lod
= lrint(log(perturb
) / log(2)) - lod_preferred
;
355 while (lod
> 0 && (reference_image
->width() < pow(2, lod
) * min_dimension
356 || reference_image
->height() < pow(2, lod
) * min_dimension
))
359 unsigned int steps
= (unsigned int) lod
+ 1;
362 * Prepare multiple levels of detail.
366 struct scale_cluster
*scale_clusters
= init_clusters(m
,
367 scale_factor
, input_frame
, steps
,
370 #error add check for non-NULL return
373 * Initialize the default initial transform
376 astate
->init_default();
379 * Set the default transformation.
382 transformation offset
= astate
->get_default();
385 * Establish boundaries
388 offset
.set_current_bounds(reference_image
);
390 ui::get()->alignment_degree_max(offset
.get_coordinate(offset
.stack_depth() - 1).degree
);
392 if (offset
.stack_depth() == 1) {
393 ui::get()->set_steps(step_count
, 0);
395 ui::get()->set_steps(offset
.get_coordinate(offset
.stack_depth() - 1).degree
+ 1, 1);
399 * Load any file-specified transformations
402 for (unsigned int index
= 0; index
< offset
.stack_depth(); index
++) {
404 unsigned int index_2
;
405 offset
.set_current_index(index
);
407 offset
= tload_next(tload
, alignment_class
== 2,
409 &is_default
, offset
.get_current_index() == 0);
411 index_2
= offset
.get_current_index();
413 if (index_2
> index
) {
414 for (unsigned int index_3
= index
; index_3
< index_2
; index_3
++)
415 astate
->set_is_default(index_3
, 1);
420 astate
->set_is_default(index
, is_default
);
423 offset
.set_current_index(0);
425 astate
->init_frame_alignment_primary(&offset
, lod
, perturb
);
428 * Control point alignment
433 transformation o
= offset
;
436 * Determine centroid data
439 point current
, previous
;
440 centroids(m
, ¤t
, &previous
);
442 if (current
.defined() && previous
.defined()) {
444 o
.set_dimensions(input_frame
);
445 o
.translate((previous
- current
) * o
.scale());
450 * Determine rotation for alignment classes other than translation.
453 ale_pos lowest_error
= cp_rms_error(m
, o
);
455 ale_pos rot_lower
= 2 * (double) local_lower
456 / sqrt(pow(scale_clusters
[0].input
->height(), 2)
457 + pow(scale_clusters
[0].input
->width(), 2))
461 if (alignment_class
> 0)
462 for (double rot
= 30; rot
> rot_lower
; rot
/= 2)
463 for (double srot
= -rot
; srot
< rot
* 1.5; srot
+= rot
* 2) {
465 while (is_improved
) {
467 transformation test_t
= o
;
469 * XXX: is this right?
471 test_t
.rotate(current
* o
.scale(), srot
);
472 ale_pos test_v
= cp_rms_error(m
, test_t
);
474 if (test_v
< lowest_error
) {
475 lowest_error
= test_v
;
484 * Determine projective parameters through a local
488 if (alignment_class
== 2) {
489 ale_pos adj_p
= lowest_error
;
491 if (adj_p
< local_lower
)
494 while (adj_p
>= local_lower
) {
495 transformation test_t
= o
;
500 while (is_improved
) {
503 for (int i
= 0; i
< 4; i
++)
504 for (int j
= 0; j
< 2; j
++)
505 for (adj_s
= -adj_p
; adj_s
<= adj_p
; adj_s
+= 2 * adj_p
) {
509 if (perturb_type
== 0)
510 test_t
.gpt_modify(j
, i
, adj_s
);
511 else if (perturb_type
== 1)
512 test_t
.gr_modify(j
, i
, adj_s
);
516 test_v
= cp_rms_error(m
, test_t
);
518 if (test_v
< lowest_error
) {
519 lowest_error
= test_v
;
532 * Pre-alignment exposure adjustment
536 ui::get()->exposure_1();
537 set_exposure_ratio(m
, scale_clusters
[0], offset
, local_ax_count
, 0);
541 * Scale transform for lod
544 for (int lod_
= 0; lod_
< lod
; lod_
++) {
545 transformation s
= offset
;
546 transformation t
= offset
;
548 t
.rescale(1 / (double) 2);
550 if (!(t
.scaled_height() > 0 && t
.scaled_height() < s
.scaled_height())
551 || !(t
.scaled_width() > 0 && t
.scaled_width() < s
.scaled_width())) {
552 perturb
/= pow(2, lod
- lod_
);
560 ui::get()->set_offset(offset
);
562 struct scale_cluster si
= scale_clusters
[lod
];
565 * Projective adjustment value
568 ale_pos adj_p
= perturb
/ pow(2, lod
);
571 * Orientational adjustment value in degrees.
573 * Since rotational perturbation is now specified as an
574 * arclength, we have to convert.
577 ale_pos adj_o
= (double) 2 * (double) perturb
578 / sqrt(pow((double) scale_clusters
[0].input
->height(), (double) 2)
579 + pow((double) scale_clusters
[0].input
->width(), (double) 2))
584 * Barrel distortion adjustment value
587 ale_pos adj_b
= perturb
* bda_mult
;
590 * Global search overlap requirements.
593 local_gs_mo
= (double) local_gs_mo
/ pow(pow(2, lod
), 2);
596 * Alignment statistics.
599 diff_stat_t
here(offset
.elem_bounds());
602 * Current difference (error) value
605 ui::get()->prematching();
606 here
.diff(si
, offset
.get_current_element(), local_ax_count
, m
);
607 ui::get()->set_match(here
.get_error());
610 * Current and modified barrel distortion parameters
613 ale_pos current_bd
[BARREL_DEGREE
];
614 ale_pos modified_bd
[BARREL_DEGREE
];
615 offset
.bd_get(current_bd
);
616 offset
.bd_get(modified_bd
);
619 * Translational global search step
622 if (perturb
>= local_lower
&& local_gs
!= 0 && local_gs
!= 5
623 && (local_gs
!= 6 || astate
->get_is_default(0))) {
625 ui::get()->global_alignment(perturb
, lod
);
626 ui::get()->gs_mo(local_gs_mo
);
628 test_globals(&here
, si
, offset
, local_gs
, adj_p
,
629 local_ax_count
, m
, local_gs_mo
, perturb
);
631 ui::get()->set_match(here
.get_error());
632 ui::get()->set_offset(here
.get_offset());
636 * Perturbation adjustment loop.
639 offset
.set_current_element(here
.get_offset());
641 for (unsigned int i
= 0; i
< offset
.stack_depth(); i
++) {
643 ui::get()->aligning_element(i
, offset
.stack_depth());
645 offset
.set_current_index(i
);
647 ui::get()->start_multi_alignment_element(offset
);
649 ui::get()->set_offset(offset
);
652 astate
->init_frame_alignment_nonprimary(&offset
, lod
, perturb
, i
);
654 if (_exp_register
== 1) {
655 ui::get()->exposure_1();
656 pixel_accum
asum(0, 0, 0), bsum(0, 0, 0);
657 exposure_ratio_iterate
eri(&asum
, &bsum
, scale_clusters
[0], offset
, local_ax_count
, 0,
658 offset
.elem_bounds().scale_to_bounds(scale_clusters
[0].accum
->height(),
659 scale_clusters
[0].accum
->width()));
662 pixel_accum tr
= asum
/ bsum
;
663 ui::get()->exp_multiplier(tr
[0], tr
[1], tr
[2]);
664 offset
.set_tonal_multiplier(tr
);
669 int e_div
= offset
.get_current_coordinate().degree
;
670 ale_pos e_perturb
= perturb
;
671 ale_pos e_adj_p
= adj_p
;
672 ale_pos e_adj_b
= adj_b
;
674 for (int d
= 0; d
< e_div
; d
++) {
686 d2::trans_multi::elem_bounds_t b
= offset
.elem_bounds();
688 for (int dim_satisfied
= 0; e_lod
> 0 && !dim_satisfied
; ) {
689 int height
= scale_clusters
[e_lod
].accum
->height();
690 int width
= scale_clusters
[e_lod
].accum
->width();
692 d2::trans_multi::elem_bounds_int_t bi
= b
.scale_to_bounds(height
, width
);
694 dim_satisfied
= bi
.satisfies_min_dim(min_dimension
);
696 if (!dim_satisfied
) {
703 * Scale transform for lod
706 for (int lod_
= 0; lod_
< e_lod
; lod_
++) {
707 trans_single s
= offset
.get_element(i
);
708 trans_single t
= offset
.get_element(i
);
710 t
.rescale(1 / (double) 2);
712 if (!(t
.scaled_height() > 0 && t
.scaled_height() < s
.scaled_height())
713 || !(t
.scaled_width() > 0 && t
.scaled_width() < s
.scaled_width())) {
714 e_perturb
/= pow(2, e_lod
- lod_
);
718 offset
.set_element(i
, t
);
722 ui::get()->set_offset(offset
);
726 * Announce perturbation size
729 ui::get()->aligning(e_perturb
, e_lod
);
731 si
= scale_clusters
[e_lod
];
733 here
.set_elem_bounds(offset
.elem_bounds());
735 here
.diff(si
, offset
.get_current_element(), local_ax_count
, m
);
739 here
= check_ancestor_path(offset
, si
, here
, local_ax_count
, m
);
741 here
= _align_element(e_perturb
, local_lower
, scale_clusters
,
742 here
, e_adj_p
, adj_o
, e_adj_b
, current_bd
, modified_bd
,
745 offset
.rescale(here
.get_offset().scale() / offset
.scale());
747 offset
.set_current_element(here
.get_offset());
749 if (i
> 0 && _exp_register
== 1) {
750 if (ma_cert_satisfied(scale_clusters
[0], offset
, i
)) {
751 ui::get()->exposure_2();
752 pixel_accum
asum(0, 0, 0), bsum(0, 0, 0);
753 exposure_ratio_iterate
eri(&asum
, &bsum
, scale_clusters
[0], offset
, local_ax_count
, 1,
754 offset
.elem_bounds().scale_to_bounds(scale_clusters
[0].accum
->height(),
755 scale_clusters
[0].accum
->width()));
758 pixel_accum tr
= asum
/ bsum
;
759 ui::get()->exp_multiplier(tr
[0], tr
[1], tr
[2]);
760 offset
.set_tonal_multiplier(tr
);
762 offset
.set_tonal_multiplier(offset
.get_element(offset
.parent_index(i
)).get_tonal_multiplier(point(0, 0)));
764 } else if (_exp_register
== 1) {
765 ui::get()->exposure_2();
766 set_exposure_ratio(m
, scale_clusters
[0], offset
, local_ax_count
, 1);
769 ui::get()->set_offset(offset
);
771 if (i
+ 1 == offset
.stack_depth())
772 ui::get()->alignment_degree_complete(offset
.get_coordinate(i
).degree
);
773 else if (offset
.get_coordinate(i
).degree
!= offset
.get_coordinate(i
+ 1).degree
)
774 ui::get()->alignment_degree_complete(offset
.get_coordinate(i
+ 1).degree
);
777 offset
.set_current_index(0);
780 offset
.set_multi(reference_image
, input_frame
);
783 * Recalculate error on whole frame.
786 ui::get()->postmatching();
787 diff_stat_generic
<transformation
> multi_here(offset
.elem_bounds());
788 multi_here
.diff(scale_clusters
[0], offset
, local_ax_count
, m
);
789 ui::get()->set_match(multi_here
.get_error());
792 * Free the level-of-detail structures
795 final_clusters(scale_clusters
, scale_factor
, steps
);
798 * Ensure that the match meets the threshold.
801 if (threshold_ok(multi_here
.get_error())) {
803 * Update alignment variables
806 astate
->set_default(offset
);
807 astate
->set_final(offset
);
808 ui::get()->alignment_match_ok();
809 } else if (local_gs
== 4) {
812 * Align with outer starting points.
816 * XXX: This probably isn't exactly the right thing to do,
817 * since variables like old_initial_value have been overwritten.
820 diff_stat_multi nested_result
= _align(m
, -1, astate
);
822 if (threshold_ok(nested_result
.get_error())) {
823 return nested_result
;
824 } else if (nested_result
.get_error() < multi_here
.get_error()) {
825 multi_here
= nested_result
;
829 offset
= astate
->get_default();
831 ui::get()->set_match(multi_here
.get_error());
832 ui::get()->alignment_no_match();
834 } else if (local_gs
== -1) {
842 offset
= astate
->get_default();
844 ui::get()->alignment_no_match();
848 * Write the tonal registration multiplier as a comment.
851 pixel trm
= image_rw::exp(m
).get_multiplier();
852 tsave_trm(tsave
, trm
[0], trm
[1], trm
[2]);
855 * Save the transformation information
858 for (unsigned int index
= 0; index
< offset
.stack_depth(); index
++) {
859 offset
.set_current_index(index
);
861 tsave_next(tsave
, offset
, alignment_class
== 2,
862 offset
.get_current_index() == 0);
865 offset
.set_current_index(0);
868 * Update match statistics.
871 match_sum
+= (1 - multi_here
.get_error()) * (ale_accum
) 100;
879 int ale_align(ale_context ac
, ale_image a
, ale_image b
, ale_trans start
,
880 ale_align_properties align_properties
, ale_trans result
) {
881 #warning function unfinished.