00001
00020 #include "mfcpch.h"
00021 #ifdef __UNIX__
00022 #include <assert.h>
00023 #endif
00024 #include <math.h>
00025 #include "memry.h"
00026 #include "pitsync1.h"
00027
00028 #include "notdll.h"
00029
00030 ELISTIZE (FPSEGPT) CLISTIZE (FPSEGPT_LIST)
00031 #define EXTERN
00032
00033 EXTERN INT_VAR (pitsync_linear_version, 6, "Use new fast algorithm");
00034 EXTERN double_VAR (pitsync_joined_edge, 0.75,
00035 "Dist inside big blob for chopping");
00036 EXTERN double_VAR (pitsync_offset_freecut_fraction, 0.25,
00037 "Fraction of cut for free cuts");
00038 EXTERN INT_VAR (pitsync_fake_depth, 1, "Max advance fake generation");
00039
00044 FPSEGPT::FPSEGPT(
00045 FPCUTPT *cutpt
00046 ) {
00047 pred = NULL;
00048 mean_sum = cutpt->sum ();
00049 sq_sum = cutpt->squares ();
00050 cost = cutpt->cost_function ();
00051 faked = cutpt->faked;
00052 terminal = cutpt->terminal;
00053 fake_count = cutpt->fake_count;
00054 xpos = cutpt->position ();
00055 mid_cuts = cutpt->cheap_cuts ();
00056 }
00057
00058
00062 FPSEGPT::FPSEGPT (
00063 INT16 x
00064 ):xpos (x) {
00065 pred = NULL;
00066 mean_sum = 0;
00067 sq_sum = 0;
00068 cost = 0;
00069 faked = FALSE;
00070 terminal = FALSE;
00071 fake_count = 0;
00072 mid_cuts = 0;
00073 }
00074
00075
00079 FPSEGPT::FPSEGPT (
00080 INT16 x,
00081 BOOL8 faking,
00082 INT16 offset,
00083 INT16 region_index,
00084 INT16 pitch,
00085 INT16 pitch_error,
00086 FPSEGPT_LIST * prev_list
00087 ):xpos (x) {
00088 INT16 best_fake;
00089 FPSEGPT *segpt;
00090 INT32 dist;
00091 double sq_dist;
00092 double mean;
00093 double total;
00094 double factor;
00095 FPSEGPT_IT pred_it = prev_list;
00096
00097 cost = MAX_FLOAT32;
00098 pred = NULL;
00099 faked = faking;
00100 terminal = FALSE;
00101 best_fake = MAX_INT16;
00102 mid_cuts = 0;
00103 for (pred_it.mark_cycle_pt (); !pred_it.cycled_list (); pred_it.forward ()) {
00104 segpt = pred_it.data ();
00105 if (segpt->fake_count < best_fake)
00106 best_fake = segpt->fake_count;
00107 dist = x - segpt->xpos;
00108 if (dist >= pitch - pitch_error && dist <= pitch + pitch_error
00109 && !segpt->terminal) {
00110 total = segpt->mean_sum + dist;
00111 sq_dist = dist * dist + segpt->sq_sum + offset * offset;
00112
00113 mean = total / region_index;
00114 factor = mean - pitch;
00115 factor *= factor;
00116 factor += sq_dist / (region_index) - mean * mean;
00117 if (factor < cost) {
00118 cost = factor;
00119 pred = segpt;
00120 mean_sum = total;
00121 sq_sum = sq_dist;
00122 fake_count = segpt->fake_count + faked;
00123 }
00124 }
00125 }
00126 if (fake_count > best_fake + 1)
00127 pred = NULL;
00128 }
00129
00130
00139 double check_pitch_sync(
00140 BLOBNBOX_IT *blob_it,
00141 INT16 blob_count,
00142 INT16 pitch,
00143 INT16 pitch_error,
00144 STATS *projection,
00145 FPSEGPT_LIST *seg_list
00146 ) {
00147 INT16 x;
00148 INT16 min_index;
00149 INT16 max_index;
00150 INT16 left_edge;
00151 INT16 right_edge;
00152 INT16 right_max;
00153 INT16 min_x;
00154 INT16 max_x;
00155 INT16 region_index;
00156 INT16 best_region_index = 0;
00157 INT16 offset;
00158 INT16 left_best_x;
00159 INT16 right_best_x;
00160 BOX min_box;
00161 BOX max_box;
00162 BOX next_box;
00163 FPSEGPT *segpt;
00164 FPSEGPT_LIST *segpts;
00165 double best_cost;
00166 double mean_sum;
00167 FPSEGPT *best_end;
00168 BLOBNBOX_IT min_it;
00169 BLOBNBOX_IT max_it;
00170 FPSEGPT_IT segpt_it;
00171
00172 FPSEGPT_IT outseg_it = seg_list;
00173 FPSEGPT_LIST_CLIST lattice;
00174
00175 FPSEGPT_LIST_C_IT lattice_it = &lattice;
00176
00177
00178
00179
00180
00181 if (pitch < 3)
00182 pitch = 3;
00183 if ((pitch - 3) / 2 < pitch_error)
00184 pitch_error = (pitch - 3) / 2;
00185 min_it = *blob_it;
00186 min_box = box_next (&min_it);
00187
00188
00189
00190
00191
00192 left_edge = min_box.left () + pitch_error;
00193 for (min_index = 1; min_index < blob_count; min_index++) {
00194 min_box = box_next (&min_it);
00195
00196
00197
00198
00199 }
00200 right_edge = min_box.right ();
00201 max_x = left_edge;
00202
00203 min_x = max_x - pitch + pitch_error * 2 + 1;
00204 right_max = right_edge + pitch - pitch_error - 1;
00205 segpts = new FPSEGPT_LIST;
00206 segpt_it.set_to_list (segpts);
00207 for (x = min_x; x <= max_x; x++) {
00208 segpt = new FPSEGPT (x);
00209
00210 segpt_it.add_after_then_move (segpt);
00211 }
00212
00213 lattice_it.add_before_then_move (segpts);
00214 min_index = 0;
00215 region_index = 1;
00216 best_cost = MAX_FLOAT32;
00217 best_end = NULL;
00218 min_it = *blob_it;
00219 min_box = box_next (&min_it);
00220 do {
00221 left_best_x = -1;
00222 right_best_x = -1;
00223 segpts = new FPSEGPT_LIST;
00224 segpt_it.set_to_list (segpts);
00225 min_x += pitch - pitch_error;
00226 max_x += pitch + pitch_error;
00227 while (min_box.right () < min_x && min_index < blob_count) {
00228 min_index++;
00229 min_box = box_next (&min_it);
00230 }
00231 max_it = min_it;
00232 max_index = min_index;
00233 max_box = min_box;
00234 next_box = box_next (&max_it);
00235 for (x = min_x; x <= max_x && x <= right_max; x++) {
00236 while (x < right_edge && max_index < blob_count
00237 && x > max_box.right ()) {
00238 max_index++;
00239 max_box = next_box;
00240 next_box = box_next (&max_it);
00241 }
00242 if (x <= max_box.left () + pitch_error
00243 || x >= max_box.right () - pitch_error || x >= right_edge
00244 || max_index < blob_count - 1 && x >= next_box.left ()
00245 || x - max_box.left () > pitch * pitsync_joined_edge
00246 && max_box.right () - x > pitch * pitsync_joined_edge) {
00247
00248 if (x - max_box.left () > 0
00249 && x - max_box.left () <= pitch_error)
00250
00251 offset = x - max_box.left ();
00252 else if (max_box.right () - x > 0
00253 && max_box.right () - x <= pitch_error
00254 && (max_index >= blob_count - 1
00255 || x < next_box.left ()))
00256 offset = max_box.right () - x;
00257 else
00258 offset = 0;
00259
00260 segpt = new FPSEGPT (x, FALSE, offset, region_index,
00261 pitch, pitch_error, lattice_it.data ());
00262 }
00263 else {
00264 offset = projection->pile_count (x);
00265 segpt = new FPSEGPT (x, TRUE, offset, region_index,
00266 pitch, pitch_error, lattice_it.data ());
00267 }
00268 if (segpt->previous () != NULL) {
00269 segpt_it.add_after_then_move (segpt);
00270 if (x >= right_edge - pitch_error) {
00271 segpt->terminal = TRUE;
00272 if (segpt->cost_function () < best_cost) {
00273 best_cost = segpt->cost_function ();
00274
00275 best_end = segpt;
00276 best_region_index = region_index;
00277 left_best_x = x;
00278 right_best_x = x;
00279 }
00280 else if (segpt->cost_function () == best_cost
00281 && right_best_x == x - 1)
00282 right_best_x = x;
00283 }
00284 }
00285 else {
00286 delete segpt;
00287 }
00288 }
00289 if (segpts->empty ()) {
00290 if (best_end != NULL)
00291 break;
00292 make_illegal_segment (lattice_it.data (), min_box, min_it,
00293 region_index, pitch, pitch_error, segpts);
00294 }
00295 else {
00296 if (right_best_x > left_best_x + 1) {
00297 left_best_x = (left_best_x + right_best_x + 1) / 2;
00298 for (segpt_it.mark_cycle_pt (); !segpt_it.cycled_list ()
00299 && segpt_it.data ()->position () != left_best_x;
00300 segpt_it.forward ());
00301 if (segpt_it.data ()->position () == left_best_x)
00302
00303 best_end = segpt_it.data ();
00304 }
00305 }
00306
00307 lattice_it.add_before_then_move (segpts);
00308 region_index++;
00309 }
00310 while (min_x < right_edge);
00311 ASSERT_HOST (best_end != NULL);
00312
00313 for (lattice_it.mark_cycle_pt (); !lattice_it.cycled_list ();
00314 lattice_it.forward ()) {
00315 segpts = lattice_it.data ();
00316 segpt_it.set_to_list (segpts);
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328 for (segpt_it.mark_cycle_pt (); !segpt_it.cycled_list ()
00329 && segpt_it.data () != best_end; segpt_it.forward ());
00330 if (segpt_it.data () == best_end) {
00331
00332 segpt = segpt_it.extract ();
00333 outseg_it.add_before_then_move (segpt);
00334 best_end = segpt->previous ();
00335 }
00336 }
00337 ASSERT_HOST (best_end == NULL);
00338 ASSERT_HOST (!outseg_it.empty ());
00339 outseg_it.move_to_last ();
00340 mean_sum = outseg_it.data ()->sum ();
00341 mean_sum = mean_sum * mean_sum / best_region_index;
00342 if (outseg_it.data ()->squares () - mean_sum < 0)
00343 tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
00344 outseg_it.data ()->squares (), outseg_it.data ()->sum (),
00345 best_region_index);
00346 lattice.deep_clear ();
00347 return outseg_it.data ()->squares () - mean_sum;
00348 }
00349
00350
00356 void make_illegal_segment(
00357 FPSEGPT_LIST *prev_list,
00358 BOX blob_box,
00359 BLOBNBOX_IT blob_it,
00360 INT16 region_index,
00361 INT16 pitch,
00362 INT16 pitch_error,
00363 FPSEGPT_LIST *seg_list
00364 ) {
00365 INT16 x;
00366 INT16 min_x = 0;
00367 INT16 max_x = 0;
00368 INT16 offset;
00369 FPSEGPT *segpt;
00370 FPSEGPT *prevpt;
00371 float best_cost;
00372 FPSEGPT_IT segpt_it = seg_list;
00373
00374 FPSEGPT_IT prevpt_it = prev_list;
00375
00376 best_cost = MAX_FLOAT32;
00377 for (prevpt_it.mark_cycle_pt (); !prevpt_it.cycled_list ();
00378 prevpt_it.forward ()) {
00379 prevpt = prevpt_it.data ();
00380 if (prevpt->cost_function () < best_cost) {
00381
00382 best_cost = prevpt->cost_function ();
00383 min_x = prevpt->position ();
00384 max_x = min_x;
00385 }
00386 else if (prevpt->cost_function () == best_cost) {
00387 max_x = prevpt->position ();
00388 }
00389 }
00390 min_x += pitch - pitch_error;
00391 max_x += pitch + pitch_error;
00392 for (x = min_x; x <= max_x; x++) {
00393 while (x > blob_box.right ()) {
00394 blob_box = box_next (&blob_it);
00395 }
00396 offset = x - blob_box.left ();
00397 if (blob_box.right () - x < offset)
00398 offset = blob_box.right () - x;
00399 segpt = new FPSEGPT (x, FALSE, offset,
00400 region_index, pitch, pitch_error, prev_list);
00401 if (segpt->previous () != NULL) {
00402 ASSERT_HOST (offset >= 0);
00403 fprintf (stderr, "made fake at %d\n", x);
00404
00405 segpt_it.add_after_then_move (segpt);
00406 segpt->faked = TRUE;
00407 segpt->fake_count++;
00408 }
00409 else
00410 delete segpt;
00411 }
00412 }