Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pithsync.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: pithsync.cpp (Formerly pitsync2.c)
3  * Description: Code to find the optimum fixed pitch segmentation of some blobs.
4  * Author: Ray Smith
5  * Created: Thu Nov 19 11:48:05 GMT 1992
6  *
7  * (C) Copyright 1992, Hewlett-Packard Ltd.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  *
18  **********************************************************************/
19 
20 #include "mfcpch.h"
21 #ifdef __UNIX__
22 #include <assert.h>
23 #endif
24 #include <math.h>
25 #include "memry.h"
26 #include "makerow.h"
27 #include "pitsync1.h"
28 #include "topitch.h"
29 #include "pithsync.h"
30 #include "tprintf.h"
31 
32 #define PROJECTION_MARGIN 10 //arbitrary
33 
34 #define EXTERN
35 
36 /**********************************************************************
37  * FPCUTPT::setup
38  *
39  * Constructor to make a new FPCUTPT.
40  **********************************************************************/
41 
42 void FPCUTPT::setup( //constructor
43  FPCUTPT *cutpts, //predecessors
44  inT16 array_origin, //start coord
45  STATS *projection, //vertical occupation
46  inT16 zero_count, //official zero
47  inT16 pitch, //proposed pitch
48  inT16 x, //position
49  inT16 offset //dist to gap
50  ) {
51  //half of pitch
52  inT16 half_pitch = pitch / 2 - 1;
53  uinT32 lead_flag; //new flag
54  inT32 ind; //current position
55 
56  if (half_pitch > 31)
57  half_pitch = 31;
58  else if (half_pitch < 0)
59  half_pitch = 0;
60  lead_flag = 1 << half_pitch;
61 
62  pred = NULL;
63  mean_sum = 0;
64  sq_sum = offset * offset;
65  cost = sq_sum;
66  faked = FALSE;
67  terminal = FALSE;
68  fake_count = 0;
69  xpos = x;
70  region_index = 0;
71  mid_cuts = 0;
72  if (x == array_origin) {
73  back_balance = 0;
74  fwd_balance = 0;
75  for (ind = 0; ind <= half_pitch; ind++) {
76  fwd_balance >>= 1;
77  if (projection->pile_count (ind) > zero_count)
78  fwd_balance |= lead_flag;
79  }
80  }
81  else {
82  back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
83  back_balance &= lead_flag + lead_flag - 1;
84  if (projection->pile_count (x) > zero_count)
85  back_balance |= 1;
86  fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
87  if (projection->pile_count (x + half_pitch) > zero_count)
88  fwd_balance |= lead_flag;
89  }
90 }
91 
92 
93 /**********************************************************************
94  * FPCUTPT::assign
95  *
96  * Constructor to make a new FPCUTPT.
97  **********************************************************************/
98 
99 void FPCUTPT::assign( //constructor
100  FPCUTPT *cutpts, //predecessors
101  inT16 array_origin, //start coord
102  inT16 x, //position
103  BOOL8 faking, //faking this one
104  BOOL8 mid_cut, //cheap cut.
105  inT16 offset, //dist to gap
106  STATS *projection, //vertical occupation
107  float projection_scale, //scaling
108  inT16 zero_count, //official zero
109  inT16 pitch, //proposed pitch
110  inT16 pitch_error //allowed tolerance
111  ) {
112  int index; //test index
113  int balance_index; //for balance factor
114  inT16 balance_count; //ding factor
115  inT16 r_index; //test cut number
116  FPCUTPT *segpt; //segment point
117  inT32 dist; //from prev segment
118  double sq_dist; //squared distance
119  double mean; //mean pitch
120  double total; //total dists
121  double factor; //cost function
122  //half of pitch
123  inT16 half_pitch = pitch / 2 - 1;
124  uinT32 lead_flag; //new flag
125 
126  if (half_pitch > 31)
127  half_pitch = 31;
128  else if (half_pitch < 0)
129  half_pitch = 0;
130  lead_flag = 1 << half_pitch;
131 
132  back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
133  back_balance &= lead_flag + lead_flag - 1;
134  if (projection->pile_count (x) > zero_count)
135  back_balance |= 1;
136  fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
137  if (projection->pile_count (x + half_pitch) > zero_count)
138  fwd_balance |= lead_flag;
139 
140  xpos = x;
141  cost = MAX_FLOAT32;
142  pred = NULL;
143  faked = faking;
144  terminal = FALSE;
145  region_index = 0;
147  for (index = x - pitch - pitch_error; index <= x - pitch + pitch_error;
148  index++) {
149  if (index >= array_origin) {
150  segpt = &cutpts[index - array_origin];
151  dist = x - segpt->xpos;
152  if (!segpt->terminal && segpt->fake_count < MAX_INT16) {
153  balance_count = 0;
154  if (textord_balance_factor > 0) {
156  lead_flag = back_balance ^ segpt->fwd_balance;
157  balance_count = 0;
158  while (lead_flag != 0) {
159  balance_count++;
160  lead_flag &= lead_flag - 1;
161  }
162  }
163  else {
164  for (balance_index = 0;
165  index + balance_index < x - balance_index;
166  balance_index++)
167  balance_count +=
168  (projection->pile_count (index + balance_index) <=
169  zero_count) ^ (projection->pile_count (x -
170  balance_index)
171  <= zero_count);
172  }
173  balance_count =
174  (inT16) (balance_count * textord_balance_factor /
175  projection_scale);
176  }
177  r_index = segpt->region_index + 1;
178  total = segpt->mean_sum + dist;
179  balance_count += offset;
180  sq_dist =
181  dist * dist + segpt->sq_sum + balance_count * balance_count;
182  mean = total / r_index;
183  factor = mean - pitch;
184  factor *= factor;
185  factor += sq_dist / (r_index) - mean * mean;
186  if (factor < cost && segpt->fake_count + faked <= fake_count) {
187  cost = factor; //find least cost
188  pred = segpt; //save path
189  mean_sum = total;
190  sq_sum = sq_dist;
191  fake_count = segpt->fake_count + faked;
192  mid_cuts = segpt->mid_cuts + mid_cut;
193  region_index = r_index;
194  }
195  }
196  }
197  }
198 }
199 
200 
201 /**********************************************************************
202  * FPCUTPT::assign_cheap
203  *
204  * Constructor to make a new FPCUTPT on the cheap.
205  **********************************************************************/
206 
207 void FPCUTPT::assign_cheap( //constructor
208  FPCUTPT *cutpts, //predecessors
209  inT16 array_origin, //start coord
210  inT16 x, //position
211  BOOL8 faking, //faking this one
212  BOOL8 mid_cut, //cheap cut.
213  inT16 offset, //dist to gap
214  STATS *projection, //vertical occupation
215  float projection_scale, //scaling
216  inT16 zero_count, //official zero
217  inT16 pitch, //proposed pitch
218  inT16 pitch_error //allowed tolerance
219  ) {
220  int index; //test index
221  inT16 balance_count; //ding factor
222  inT16 r_index; //test cut number
223  FPCUTPT *segpt; //segment point
224  inT32 dist; //from prev segment
225  double sq_dist; //squared distance
226  double mean; //mean pitch
227  double total; //total dists
228  double factor; //cost function
229  //half of pitch
230  inT16 half_pitch = pitch / 2 - 1;
231  uinT32 lead_flag; //new flag
232 
233  if (half_pitch > 31)
234  half_pitch = 31;
235  else if (half_pitch < 0)
236  half_pitch = 0;
237  lead_flag = 1 << half_pitch;
238 
239  back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
240  back_balance &= lead_flag + lead_flag - 1;
241  if (projection->pile_count (x) > zero_count)
242  back_balance |= 1;
243  fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
244  if (projection->pile_count (x + half_pitch) > zero_count)
245  fwd_balance |= lead_flag;
246 
247  xpos = x;
248  cost = MAX_FLOAT32;
249  pred = NULL;
250  faked = faking;
251  terminal = FALSE;
252  region_index = 0;
254  index = x - pitch;
255  if (index >= array_origin) {
256  segpt = &cutpts[index - array_origin];
257  dist = x - segpt->xpos;
258  if (!segpt->terminal && segpt->fake_count < MAX_INT16) {
259  balance_count = 0;
260  if (textord_balance_factor > 0) {
261  lead_flag = back_balance ^ segpt->fwd_balance;
262  balance_count = 0;
263  while (lead_flag != 0) {
264  balance_count++;
265  lead_flag &= lead_flag - 1;
266  }
267  balance_count = (inT16) (balance_count * textord_balance_factor
268  / projection_scale);
269  }
270  r_index = segpt->region_index + 1;
271  total = segpt->mean_sum + dist;
272  balance_count += offset;
273  sq_dist =
274  dist * dist + segpt->sq_sum + balance_count * balance_count;
275  mean = total / r_index;
276  factor = mean - pitch;
277  factor *= factor;
278  factor += sq_dist / (r_index) - mean * mean;
279  cost = factor; //find least cost
280  pred = segpt; //save path
281  mean_sum = total;
282  sq_sum = sq_dist;
283  fake_count = segpt->fake_count + faked;
284  mid_cuts = segpt->mid_cuts + mid_cut;
285  region_index = r_index;
286  }
287  }
288 }
289 
290 
291 /**********************************************************************
292  * check_pitch_sync
293  *
294  * Construct the lattice of possible segmentation points and choose the
295  * optimal path. Return the optimal path only.
296  * The return value is a measure of goodness of the sync.
297  **********************************************************************/
298 
299 double check_pitch_sync2( //find segmentation
300  BLOBNBOX_IT *blob_it, //blobs to do
301  inT16 blob_count, //no of blobs
302  inT16 pitch, //pitch estimate
303  inT16 pitch_error, //tolerance
304  STATS *projection, //vertical
305  inT16 projection_left, //edges //scale factor
306  inT16 projection_right,
307  float projection_scale,
308  inT16 &occupation_count, //no of occupied cells
309  FPSEGPT_LIST *seg_list, //output list
310  inT16 start, //start of good range
311  inT16 end //end of good range
312  ) {
313  BOOL8 faking; //illegal cut pt
314  BOOL8 mid_cut; //cheap cut pt.
315  inT16 x; //current coord
316  inT16 blob_index; //blob number
317  inT16 left_edge; //of word
318  inT16 right_edge; //of word
319  inT16 array_origin; //x coord of array
320  inT16 offset; //dist to legal area
321  inT16 zero_count; //projection zero
322  inT16 best_left_x = 0; //for equals
323  inT16 best_right_x = 0; //right edge
324  TBOX this_box; //bounding box
325  TBOX next_box; //box of next blob
326  FPSEGPT *segpt; //segment point
327  FPCUTPT *cutpts; //array of points
328  double best_cost; //best path
329  double mean_sum; //computes result
330  FPCUTPT *best_end; //end of best path
331  inT16 best_fake; //best fake level
332  inT16 best_count; //no of cuts
333  BLOBNBOX_IT this_it; //copy iterator
334  FPSEGPT_IT seg_it = seg_list; //output iterator
335 
336  // tprintf("Computing sync on word of %d blobs with pitch %d\n",
337  // blob_count, pitch);
338  // if (blob_count==8 && pitch==27)
339  // projection->print(stdout,TRUE);
340  zero_count = 0;
341  if (pitch < 3)
342  pitch = 3; //nothing ludicrous
343  if ((pitch - 3) / 2 < pitch_error)
344  pitch_error = (pitch - 3) / 2;
345  this_it = *blob_it;
346  this_box = box_next (&this_it);//get box
347  // left_edge=this_box.left(); //left of word
348  // right_edge=this_box.right();
349  // for (blob_index=1;blob_index<blob_count;blob_index++)
350  // {
351  // this_box=box_next(&this_it);
352  // if (this_box.right()>right_edge)
353  // right_edge=this_box.right();
354  // }
355  for (left_edge = projection_left; projection->pile_count (left_edge) == 0
356  && left_edge < projection_right; left_edge++);
357  for (right_edge = projection_right; projection->pile_count (right_edge) == 0
358  && right_edge > left_edge; right_edge--);
359  ASSERT_HOST (right_edge >= left_edge);
360  if (pitsync_linear_version >= 4)
361  return check_pitch_sync3 (projection_left, projection_right, zero_count,
362  pitch, pitch_error, projection,
363  projection_scale, occupation_count, seg_list,
364  start, end);
365  array_origin = left_edge - pitch;
366  cutpts = (FPCUTPT *) alloc_mem ((right_edge - left_edge + pitch * 2 + 1)
367  * sizeof (FPCUTPT));
368  for (x = array_origin; x < left_edge; x++)
369  //free cuts
370  cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, 0);
371  for (offset = 0; offset <= pitch_error; offset++, x++)
372  //not quite free
373  cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, offset);
374 
375  this_it = *blob_it;
376  best_cost = MAX_FLOAT32;
377  best_end = NULL;
378  this_box = box_next (&this_it);//first box
379  next_box = box_next (&this_it);//second box
380  blob_index = 1;
381  while (x < right_edge - pitch_error) {
382  if (x > this_box.right () + pitch_error && blob_index < blob_count) {
383  this_box = next_box;
384  next_box = box_next (&this_it);
385  blob_index++;
386  }
387  faking = FALSE;
388  mid_cut = FALSE;
389  if (x <= this_box.left ())
390  offset = 0;
391  else if (x <= this_box.left () + pitch_error)
392  offset = x - this_box.left ();
393  else if (x >= this_box.right ())
394  offset = 0;
395  else if (x >= next_box.left () && blob_index < blob_count) {
396  offset = x - next_box.left ();
397  if (this_box.right () - x < offset)
398  offset = this_box.right () - x;
399  }
400  else if (x >= this_box.right () - pitch_error)
401  offset = this_box.right () - x;
402  else if (x - this_box.left () > pitch * pitsync_joined_edge
403  && this_box.right () - x > pitch * pitsync_joined_edge) {
404  mid_cut = TRUE;
405  offset = 0;
406  }
407  else {
408  faking = TRUE;
409  offset = projection->pile_count (x);
410  }
411  cutpts[x - array_origin].assign (cutpts, array_origin, x,
412  faking, mid_cut, offset, projection,
413  projection_scale, zero_count, pitch,
414  pitch_error);
415  x++;
416  }
417 
418  best_fake = MAX_INT16;
419  best_cost = MAX_INT32;
420  best_count = MAX_INT16;
421  while (x < right_edge + pitch) {
422  offset = x < right_edge ? right_edge - x : 0;
423  cutpts[x - array_origin].assign (cutpts, array_origin, x,
424  FALSE, FALSE, offset, projection,
425  projection_scale, zero_count, pitch,
426  pitch_error);
427  cutpts[x - array_origin].terminal = TRUE;
428  if (cutpts[x - array_origin].index () +
429  cutpts[x - array_origin].fake_count <= best_count + best_fake) {
430  if (cutpts[x - array_origin].fake_count < best_fake
431  || (cutpts[x - array_origin].fake_count == best_fake
432  && cutpts[x - array_origin].cost_function () < best_cost)) {
433  best_fake = cutpts[x - array_origin].fake_count;
434  best_cost = cutpts[x - array_origin].cost_function ();
435  best_left_x = x;
436  best_right_x = x;
437  best_count = cutpts[x - array_origin].index ();
438  }
439  else if (cutpts[x - array_origin].fake_count == best_fake
440  && x == best_right_x + 1
441  && cutpts[x - array_origin].cost_function () == best_cost) {
442  //exactly equal
443  best_right_x = x;
444  }
445  }
446  x++;
447  }
448  ASSERT_HOST (best_fake < MAX_INT16);
449 
450  best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
451  if (this_box.right () == textord_test_x
452  && this_box.top () == textord_test_y) {
453  for (x = left_edge - pitch; x < right_edge + pitch; x++) {
454  tprintf ("x=%d, C=%g, s=%g, sq=%g, prev=%d\n",
455  x, cutpts[x - array_origin].cost_function (),
456  cutpts[x - array_origin].sum (),
457  cutpts[x - array_origin].squares (),
458  cutpts[x - array_origin].previous ()->position ());
459  }
460  }
461  occupation_count = -1;
462  do {
463  for (x = best_end->position () - pitch + pitch_error;
464  x < best_end->position () - pitch_error
465  && projection->pile_count (x) == 0; x++);
466  if (x < best_end->position () - pitch_error)
467  occupation_count++;
468  //copy it
469  segpt = new FPSEGPT (best_end);
470  seg_it.add_before_then_move (segpt);
471  best_end = best_end->previous ();
472  }
473  while (best_end != NULL);
474  seg_it.move_to_last ();
475  mean_sum = seg_it.data ()->sum ();
476  mean_sum = mean_sum * mean_sum / best_count;
477  if (seg_it.data ()->squares () - mean_sum < 0)
478  tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
479  seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
480  free_mem(cutpts);
481  // tprintf("blob_count=%d, pitch=%d, sync=%g, occ=%d\n",
482  // blob_count,pitch,seg_it.data()->squares()-mean_sum,
483  // occupation_count);
484  return seg_it.data ()->squares () - mean_sum;
485 }
486 
487 
488 /**********************************************************************
489  * check_pitch_sync
490  *
491  * Construct the lattice of possible segmentation points and choose the
492  * optimal path. Return the optimal path only.
493  * The return value is a measure of goodness of the sync.
494  **********************************************************************/
495 
496 double check_pitch_sync3( //find segmentation
497  inT16 projection_left, //edges //to be considered 0
498  inT16 projection_right,
499  inT16 zero_count,
500  inT16 pitch, //pitch estimate
501  inT16 pitch_error, //tolerance
502  STATS *projection, //vertical
503  float projection_scale, //scale factor
504  inT16 &occupation_count, //no of occupied cells
505  FPSEGPT_LIST *seg_list, //output list
506  inT16 start, //start of good range
507  inT16 end //end of good range
508  ) {
509  BOOL8 faking; //illegal cut pt
510  BOOL8 mid_cut; //cheap cut pt.
511  inT16 left_edge; //of word
512  inT16 right_edge; //of word
513  inT16 x; //current coord
514  inT16 array_origin; //x coord of array
515  inT16 offset; //dist to legal area
516  inT16 projection_offset; //from scaled projection
517  inT16 prev_zero; //previous zero dist
518  inT16 next_zero; //next zero dist
519  inT16 zero_offset; //scan window
520  inT16 best_left_x = 0; //for equals
521  inT16 best_right_x = 0; //right edge
522  FPSEGPT *segpt; //segment point
523  FPCUTPT *cutpts; //array of points
524  BOOL8 *mins; //local min results
525  int minindex; //next input position
526  int test_index; //index to mins
527  double best_cost; //best path
528  double mean_sum; //computes result
529  FPCUTPT *best_end; //end of best path
530  inT16 best_fake; //best fake level
531  inT16 best_count; //no of cuts
532  FPSEGPT_IT seg_it = seg_list; //output iterator
533 
534  end = (end - start) % pitch;
535  if (pitch < 3)
536  pitch = 3; //nothing ludicrous
537  if ((pitch - 3) / 2 < pitch_error)
538  pitch_error = (pitch - 3) / 2;
539  //min dist of zero
540  zero_offset = (inT16) (pitch * pitsync_joined_edge);
541  for (left_edge = projection_left; projection->pile_count (left_edge) == 0
542  && left_edge < projection_right; left_edge++);
543  for (right_edge = projection_right; projection->pile_count (right_edge) == 0
544  && right_edge > left_edge; right_edge--);
545  array_origin = left_edge - pitch;
546  cutpts = (FPCUTPT *) alloc_mem ((right_edge - left_edge + pitch * 2 + 1)
547  * sizeof (FPCUTPT));
548  mins = (BOOL8 *) alloc_mem ((pitch_error * 2 + 1) * sizeof (BOOL8));
549  for (x = array_origin; x < left_edge; x++)
550  //free cuts
551  cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, 0);
552  prev_zero = left_edge - 1;
553  for (offset = 0; offset <= pitch_error; offset++, x++)
554  //not quite free
555  cutpts[x - array_origin].setup (cutpts, array_origin, projection, zero_count, pitch, x, offset);
556 
557  best_cost = MAX_FLOAT32;
558  best_end = NULL;
559  for (offset = -pitch_error, minindex = 0; offset < pitch_error;
560  offset++, minindex++)
561  mins[minindex] = projection->local_min (x + offset);
562  next_zero = x + zero_offset + 1;
563  for (offset = next_zero - 1; offset >= x; offset--) {
564  if (projection->pile_count (offset) <= zero_count) {
565  next_zero = offset;
566  break;
567  }
568  }
569  while (x < right_edge - pitch_error) {
570  mins[minindex] = projection->local_min (x + pitch_error);
571  minindex++;
572  if (minindex > pitch_error * 2)
573  minindex = 0;
574  faking = FALSE;
575  mid_cut = FALSE;
576  offset = 0;
577  if (projection->pile_count (x) <= zero_count) {
578  prev_zero = x;
579  }
580  else {
581  for (offset = 1; offset <= pitch_error; offset++)
582  if (projection->pile_count (x + offset) <= zero_count
583  || projection->pile_count (x - offset) <= zero_count)
584  break;
585  }
586  if (offset > pitch_error) {
587  if (x - prev_zero > zero_offset && next_zero - x > zero_offset) {
588  for (offset = 0; offset <= pitch_error; offset++) {
589  test_index = minindex + pitch_error + offset;
590  if (test_index > pitch_error * 2)
591  test_index -= pitch_error * 2 + 1;
592  if (mins[test_index])
593  break;
594  test_index = minindex + pitch_error - offset;
595  if (test_index > pitch_error * 2)
596  test_index -= pitch_error * 2 + 1;
597  if (mins[test_index])
598  break;
599  }
600  }
601  if (offset > pitch_error) {
602  offset = projection->pile_count (x);
603  faking = TRUE;
604  }
605  else {
606  projection_offset =
607  (inT16) (projection->pile_count (x) / projection_scale);
608  if (projection_offset > offset)
609  offset = projection_offset;
610  mid_cut = TRUE;
611  }
612  }
613  if ((start == 0 && end == 0)
615  || (x - projection_left - start) % pitch <= end)
616  cutpts[x - array_origin].assign (cutpts, array_origin, x,
617  faking, mid_cut, offset, projection,
618  projection_scale, zero_count, pitch,
619  pitch_error);
620  else
621  cutpts[x - array_origin].assign_cheap (cutpts, array_origin, x,
622  faking, mid_cut, offset,
623  projection, projection_scale,
624  zero_count, pitch,
625  pitch_error);
626  x++;
627  if (next_zero < x || next_zero == x + zero_offset)
628  next_zero = x + zero_offset + 1;
629  if (projection->pile_count (x + zero_offset) <= zero_count)
630  next_zero = x + zero_offset;
631  }
632 
633  best_fake = MAX_INT16;
634  best_cost = MAX_INT32;
635  best_count = MAX_INT16;
636  while (x < right_edge + pitch) {
637  offset = x < right_edge ? right_edge - x : 0;
638  cutpts[x - array_origin].assign (cutpts, array_origin, x,
639  FALSE, FALSE, offset, projection,
640  projection_scale, zero_count, pitch,
641  pitch_error);
642  cutpts[x - array_origin].terminal = TRUE;
643  if (cutpts[x - array_origin].index () +
644  cutpts[x - array_origin].fake_count <= best_count + best_fake) {
645  if (cutpts[x - array_origin].fake_count < best_fake
646  || (cutpts[x - array_origin].fake_count == best_fake
647  && cutpts[x - array_origin].cost_function () < best_cost)) {
648  best_fake = cutpts[x - array_origin].fake_count;
649  best_cost = cutpts[x - array_origin].cost_function ();
650  best_left_x = x;
651  best_right_x = x;
652  best_count = cutpts[x - array_origin].index ();
653  }
654  else if (cutpts[x - array_origin].fake_count == best_fake
655  && x == best_right_x + 1
656  && cutpts[x - array_origin].cost_function () == best_cost) {
657  //exactly equal
658  best_right_x = x;
659  }
660  }
661  x++;
662  }
663  ASSERT_HOST (best_fake < MAX_INT16);
664 
665  best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
666  // for (x=left_edge-pitch;x<right_edge+pitch;x++)
667  // {
668  // tprintf("x=%d, C=%g, s=%g, sq=%g, prev=%d\n",
669  // x,cutpts[x-array_origin].cost_function(),
670  // cutpts[x-array_origin].sum(),
671  // cutpts[x-array_origin].squares(),
672  // cutpts[x-array_origin].previous()->position());
673  // }
674  occupation_count = -1;
675  do {
676  for (x = best_end->position () - pitch + pitch_error;
677  x < best_end->position () - pitch_error
678  && projection->pile_count (x) == 0; x++);
679  if (x < best_end->position () - pitch_error)
680  occupation_count++;
681  //copy it
682  segpt = new FPSEGPT (best_end);
683  seg_it.add_before_then_move (segpt);
684  best_end = best_end->previous ();
685  }
686  while (best_end != NULL);
687  seg_it.move_to_last ();
688  mean_sum = seg_it.data ()->sum ();
689  mean_sum = mean_sum * mean_sum / best_count;
690  if (seg_it.data ()->squares () - mean_sum < 0)
691  tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
692  seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
693  free_mem(mins);
694  free_mem(cutpts);
695  return seg_it.data ()->squares () - mean_sum;
696 }