diff options
Diffstat (limited to 'tesseract/src/textord/pithsync.cpp')
| -rw-r--r-- | tesseract/src/textord/pithsync.cpp | 693 |
1 files changed, 693 insertions, 0 deletions
diff --git a/tesseract/src/textord/pithsync.cpp b/tesseract/src/textord/pithsync.cpp new file mode 100644 index 00000000..462f0b3c --- /dev/null +++ b/tesseract/src/textord/pithsync.cpp @@ -0,0 +1,693 @@ +/********************************************************************** + * File: pithsync.cpp (Formerly pitsync2.c) + * Description: Code to find the optimum fixed pitch segmentation of some blobs. + * Author: Ray Smith + * + * (C) Copyright 1992, Hewlett-Packard Ltd. + ** Licensed under the Apache License, Version 2.0 (the "License"); + ** you may not use this file except in compliance with the License. + ** You may obtain a copy of the License at + ** http://www.apache.org/licenses/LICENSE-2.0 + ** Unless required by applicable law or agreed to in writing, software + ** distributed under the License is distributed on an "AS IS" BASIS, + ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + ** See the License for the specific language governing permissions and + ** limitations under the License. + * + **********************************************************************/ + +#include "pithsync.h" + +#include "makerow.h" +#include "pitsync1.h" +#include "topitch.h" +#include "tprintf.h" + +#include <cmath> +#include <cfloat> // for FLT_MAX +#include <vector> // for std::vector + +namespace tesseract { + +/********************************************************************** + * FPCUTPT::setup + * + * Constructor to make a new FPCUTPT. + **********************************************************************/ + +void FPCUTPT::setup( //constructor + FPCUTPT *cutpts, //predecessors + int16_t array_origin, //start coord + STATS *projection, //vertical occupation + int16_t zero_count, //official zero + int16_t pitch, //proposed pitch + int16_t x, //position + int16_t offset //dist to gap + ) { + //half of pitch + int16_t half_pitch = pitch / 2 - 1; + uint32_t lead_flag; //new flag + int32_t ind; //current position + + if (half_pitch > 31) + half_pitch = 31; + else if (half_pitch < 0) + half_pitch = 0; + lead_flag = 1 << half_pitch; + + pred = nullptr; + mean_sum = 0; + sq_sum = offset * offset; + cost = sq_sum; + faked = false; + terminal = false; + fake_count = 0; + xpos = x; + region_index = 0; + mid_cuts = 0; + if (x == array_origin) { + back_balance = 0; + fwd_balance = 0; + for (ind = 0; ind <= half_pitch; ind++) { + fwd_balance >>= 1; + if (projection->pile_count (ind) > zero_count) + fwd_balance |= lead_flag; + } + } + else { + back_balance = cutpts[x - 1 - array_origin].back_balance << 1; + back_balance &= lead_flag + (lead_flag - 1); + if (projection->pile_count (x) > zero_count) + back_balance |= 1; + fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1; + if (projection->pile_count (x + half_pitch) > zero_count) + fwd_balance |= lead_flag; + } +} + + +/********************************************************************** + * FPCUTPT::assign + * + * Constructor to make a new FPCUTPT. + **********************************************************************/ + +void FPCUTPT::assign( //constructor + FPCUTPT* cutpts, //predecessors + int16_t array_origin, //start coord + int16_t x, //position + bool faking, //faking this one + bool mid_cut, //cheap cut. + int16_t offset, //dist to gap + STATS* projection, //vertical occupation + float projection_scale, //scaling + int16_t zero_count, //official zero + int16_t pitch, //proposed pitch + int16_t pitch_error //allowed tolerance +) { + int index; //test index + int balance_index; //for balance factor + int16_t balance_count; //ding factor + int16_t r_index; //test cut number + FPCUTPT *segpt; //segment point + int32_t dist; //from prev segment + double sq_dist; //squared distance + double mean; //mean pitch + double total; //total dists + double factor; //cost function + //half of pitch + int16_t half_pitch = pitch / 2 - 1; + uint32_t lead_flag; //new flag + + if (half_pitch > 31) + half_pitch = 31; + else if (half_pitch < 0) + half_pitch = 0; + lead_flag = 1 << half_pitch; + + back_balance = cutpts[x - 1 - array_origin].back_balance << 1; + back_balance &= lead_flag + (lead_flag - 1); + if (projection->pile_count (x) > zero_count) + back_balance |= 1; + fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1; + if (projection->pile_count (x + half_pitch) > zero_count) + fwd_balance |= lead_flag; + + xpos = x; + cost = FLT_MAX; + pred = nullptr; + faked = faking; + terminal = false; + region_index = 0; + fake_count = INT16_MAX; + for (index = x - pitch - pitch_error; index <= x - pitch + pitch_error; + index++) { + if (index >= array_origin) { + segpt = &cutpts[index - array_origin]; + dist = x - segpt->xpos; + if (!segpt->terminal && segpt->fake_count < INT16_MAX) { + balance_count = 0; + if (textord_balance_factor > 0) { + if (textord_fast_pitch_test) { + lead_flag = back_balance ^ segpt->fwd_balance; + balance_count = 0; + while (lead_flag != 0) { + balance_count++; + lead_flag &= lead_flag - 1; + } + } + else { + for (balance_index = 0; + index + balance_index < x - balance_index; + balance_index++) + balance_count += + (projection->pile_count (index + balance_index) <= + zero_count) ^ (projection->pile_count (x - + balance_index) + <= zero_count); + } + balance_count = + static_cast<int16_t>(balance_count * textord_balance_factor / + projection_scale); + } + r_index = segpt->region_index + 1; + total = segpt->mean_sum + dist; + balance_count += offset; + sq_dist = + dist * dist + segpt->sq_sum + balance_count * balance_count; + mean = total / r_index; + factor = mean - pitch; + factor *= factor; + factor += sq_dist / (r_index) - mean * mean; + if (factor < cost && segpt->fake_count + faked <= fake_count) { + cost = factor; //find least cost + pred = segpt; //save path + mean_sum = total; + sq_sum = sq_dist; + fake_count = segpt->fake_count + faked; + mid_cuts = segpt->mid_cuts + mid_cut; + region_index = r_index; + } + } + } + } +} + + +/********************************************************************** + * FPCUTPT::assign_cheap + * + * Constructor to make a new FPCUTPT on the cheap. + **********************************************************************/ + +void FPCUTPT::assign_cheap( //constructor + FPCUTPT *cutpts, //predecessors + int16_t array_origin, //start coord + int16_t x, //position + bool faking, //faking this one + bool mid_cut, //cheap cut. + int16_t offset, //dist to gap + STATS *projection, //vertical occupation + float projection_scale, //scaling + int16_t zero_count, //official zero + int16_t pitch, //proposed pitch + int16_t pitch_error //allowed tolerance + ) { + int index; //test index + int16_t balance_count; //ding factor + int16_t r_index; //test cut number + FPCUTPT *segpt; //segment point + int32_t dist; //from prev segment + double sq_dist; //squared distance + double mean; //mean pitch + double total; //total dists + double factor; //cost function + //half of pitch + int16_t half_pitch = pitch / 2 - 1; + uint32_t lead_flag; //new flag + + if (half_pitch > 31) + half_pitch = 31; + else if (half_pitch < 0) + half_pitch = 0; + lead_flag = 1 << half_pitch; + + back_balance = cutpts[x - 1 - array_origin].back_balance << 1; + back_balance &= lead_flag + (lead_flag - 1); + if (projection->pile_count (x) > zero_count) + back_balance |= 1; + fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1; + if (projection->pile_count (x + half_pitch) > zero_count) + fwd_balance |= lead_flag; + + xpos = x; + cost = FLT_MAX; + pred = nullptr; + faked = faking; + terminal = false; + region_index = 0; + fake_count = INT16_MAX; + index = x - pitch; + if (index >= array_origin) { + segpt = &cutpts[index - array_origin]; + dist = x - segpt->xpos; + if (!segpt->terminal && segpt->fake_count < INT16_MAX) { + balance_count = 0; + if (textord_balance_factor > 0) { + lead_flag = back_balance ^ segpt->fwd_balance; + balance_count = 0; + while (lead_flag != 0) { + balance_count++; + lead_flag &= lead_flag - 1; + } + balance_count = static_cast<int16_t>(balance_count * textord_balance_factor + / projection_scale); + } + r_index = segpt->region_index + 1; + total = segpt->mean_sum + dist; + balance_count += offset; + sq_dist = + dist * dist + segpt->sq_sum + balance_count * balance_count; + mean = total / r_index; + factor = mean - pitch; + factor *= factor; + factor += sq_dist / (r_index) - mean * mean; + cost = factor; //find least cost + pred = segpt; //save path + mean_sum = total; + sq_sum = sq_dist; + fake_count = segpt->fake_count + faked; + mid_cuts = segpt->mid_cuts + mid_cut; + region_index = r_index; + } + } +} + + +/********************************************************************** + * check_pitch_sync + * + * Construct the lattice of possible segmentation points and choose the + * optimal path. Return the optimal path only. + * The return value is a measure of goodness of the sync. + **********************************************************************/ + +double check_pitch_sync2( //find segmentation + BLOBNBOX_IT *blob_it, //blobs to do + int16_t blob_count, //no of blobs + int16_t pitch, //pitch estimate + int16_t pitch_error, //tolerance + STATS *projection, //vertical + int16_t projection_left, //edges //scale factor + int16_t projection_right, + float projection_scale, + int16_t &occupation_count, //no of occupied cells + FPSEGPT_LIST *seg_list, //output list + int16_t start, //start of good range + int16_t end //end of good range + ) { + bool faking; //illegal cut pt + bool mid_cut; //cheap cut pt. + int16_t x; //current coord + int16_t blob_index; //blob number + int16_t left_edge; //of word + int16_t right_edge; //of word + int16_t array_origin; //x coord of array + int16_t offset; //dist to legal area + int16_t zero_count; //projection zero + int16_t best_left_x = 0; //for equals + int16_t best_right_x = 0; //right edge + TBOX this_box; //bounding box + TBOX next_box; //box of next blob + FPSEGPT *segpt; //segment point + double best_cost; //best path + double mean_sum; //computes result + FPCUTPT *best_end; //end of best path + int16_t best_fake; //best fake level + int16_t best_count; //no of cuts + BLOBNBOX_IT this_it; //copy iterator + FPSEGPT_IT seg_it = seg_list; //output iterator + + // tprintf("Computing sync on word of %d blobs with pitch %d\n", + // blob_count, pitch); + // if (blob_count==8 && pitch==27) + // projection->print(stdout,true); + zero_count = 0; + if (pitch < 3) + pitch = 3; //nothing ludicrous + if ((pitch - 3) / 2 < pitch_error) + pitch_error = (pitch - 3) / 2; + this_it = *blob_it; + this_box = box_next (&this_it);//get box + // left_edge=this_box.left(); //left of word + // right_edge=this_box.right(); + // for (blob_index=1;blob_index<blob_count;blob_index++) + // { + // this_box=box_next(&this_it); + // if (this_box.right()>right_edge) + // right_edge=this_box.right(); + // } + for (left_edge = projection_left; projection->pile_count (left_edge) == 0 + && left_edge < projection_right; left_edge++); + for (right_edge = projection_right; projection->pile_count (right_edge) == 0 + && right_edge > left_edge; right_edge--); + ASSERT_HOST (right_edge >= left_edge); + if (pitsync_linear_version >= 4) + return check_pitch_sync3 (projection_left, projection_right, zero_count, + pitch, pitch_error, projection, + projection_scale, occupation_count, seg_list, + start, end); + array_origin = left_edge - pitch; + // array of points + std::vector<FPCUTPT> cutpts(right_edge - left_edge + pitch * 2 + 1); + for (x = array_origin; x < left_edge; x++) + //free cuts + cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection, + zero_count, pitch, x, 0); + for (offset = 0; offset <= pitch_error; offset++, x++) + //not quite free + cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection, + zero_count, pitch, x, offset); + + this_it = *blob_it; + best_cost = FLT_MAX; + best_end = nullptr; + this_box = box_next (&this_it);//first box + next_box = box_next (&this_it);//second box + blob_index = 1; + while (x < right_edge - pitch_error) { + if (x > this_box.right () + pitch_error && blob_index < blob_count) { + this_box = next_box; + next_box = box_next (&this_it); + blob_index++; + } + faking = false; + mid_cut = false; + if (x <= this_box.left ()) + offset = 0; + else if (x <= this_box.left () + pitch_error) + offset = x - this_box.left (); + else if (x >= this_box.right ()) + offset = 0; + else if (x >= next_box.left () && blob_index < blob_count) { + offset = x - next_box.left (); + if (this_box.right () - x < offset) + offset = this_box.right () - x; + } + else if (x >= this_box.right () - pitch_error) + offset = this_box.right () - x; + else if (x - this_box.left () > pitch * pitsync_joined_edge + && this_box.right () - x > pitch * pitsync_joined_edge) { + mid_cut = true; + offset = 0; + } + else { + faking = true; + offset = projection->pile_count (x); + } + cutpts[x - array_origin].assign (&cutpts[0], array_origin, x, + faking, mid_cut, offset, projection, + projection_scale, zero_count, pitch, + pitch_error); + x++; + } + + best_fake = INT16_MAX; + best_cost = INT32_MAX; + best_count = INT16_MAX; + while (x < right_edge + pitch) { + offset = x < right_edge ? right_edge - x : 0; + cutpts[x - array_origin].assign (&cutpts[0], array_origin, x, + false, false, offset, projection, + projection_scale, zero_count, pitch, + pitch_error); + cutpts[x - array_origin].terminal = true; + if (cutpts[x - array_origin].index () + + cutpts[x - array_origin].fake_count <= best_count + best_fake) { + if (cutpts[x - array_origin].fake_count < best_fake + || (cutpts[x - array_origin].fake_count == best_fake + && cutpts[x - array_origin].cost_function () < best_cost)) { + best_fake = cutpts[x - array_origin].fake_count; + best_cost = cutpts[x - array_origin].cost_function (); + best_left_x = x; + best_right_x = x; + best_count = cutpts[x - array_origin].index (); + } + else if (cutpts[x - array_origin].fake_count == best_fake + && x == best_right_x + 1 + && cutpts[x - array_origin].cost_function () == best_cost) { + //exactly equal + best_right_x = x; + } + } + x++; + } + ASSERT_HOST (best_fake < INT16_MAX); + + best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin]; + if (this_box.right () == textord_test_x + && this_box.top () == textord_test_y) { + for (x = left_edge - pitch; x < right_edge + pitch; x++) { + tprintf ("x=%d, C=%g, s=%g, sq=%g, prev=%d\n", + x, cutpts[x - array_origin].cost_function (), + cutpts[x - array_origin].sum (), + cutpts[x - array_origin].squares (), + cutpts[x - array_origin].previous ()->position ()); + } + } + occupation_count = -1; + do { + for (x = best_end->position () - pitch + pitch_error; + x < best_end->position () - pitch_error + && projection->pile_count (x) == 0; x++); + if (x < best_end->position () - pitch_error) + occupation_count++; + //copy it + segpt = new FPSEGPT (best_end); + seg_it.add_before_then_move (segpt); + best_end = best_end->previous (); + } + while (best_end != nullptr); + seg_it.move_to_last (); + mean_sum = seg_it.data ()->sum (); + mean_sum = mean_sum * mean_sum / best_count; + if (seg_it.data ()->squares () - mean_sum < 0) + tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n", + seg_it.data ()->squares (), seg_it.data ()->sum (), best_count); + // tprintf("blob_count=%d, pitch=%d, sync=%g, occ=%d\n", + // blob_count,pitch,seg_it.data()->squares()-mean_sum, + // occupation_count); + return seg_it.data ()->squares () - mean_sum; +} + + +/********************************************************************** + * check_pitch_sync + * + * Construct the lattice of possible segmentation points and choose the + * optimal path. Return the optimal path only. + * The return value is a measure of goodness of the sync. + **********************************************************************/ + +double check_pitch_sync3( //find segmentation + int16_t projection_left, //edges //to be considered 0 + int16_t projection_right, + int16_t zero_count, + int16_t pitch, //pitch estimate + int16_t pitch_error, //tolerance + STATS *projection, //vertical + float projection_scale, //scale factor + int16_t &occupation_count, //no of occupied cells + FPSEGPT_LIST *seg_list, //output list + int16_t start, //start of good range + int16_t end //end of good range + ) { + bool faking; //illegal cut pt + bool mid_cut; //cheap cut pt. + int16_t left_edge; //of word + int16_t right_edge; //of word + int16_t x; //current coord + int16_t array_origin; //x coord of array + int16_t offset; //dist to legal area + int16_t projection_offset; //from scaled projection + int16_t prev_zero; //previous zero dist + int16_t next_zero; //next zero dist + int16_t zero_offset; //scan window + int16_t best_left_x = 0; //for equals + int16_t best_right_x = 0; //right edge + FPSEGPT *segpt; //segment point + int minindex; //next input position + int test_index; //index to mins + double best_cost; //best path + double mean_sum; //computes result + FPCUTPT *best_end; //end of best path + int16_t best_fake; //best fake level + int16_t best_count; //no of cuts + FPSEGPT_IT seg_it = seg_list; //output iterator + + end = (end - start) % pitch; + if (pitch < 3) + pitch = 3; //nothing ludicrous + if ((pitch - 3) / 2 < pitch_error) + pitch_error = (pitch - 3) / 2; + //min dist of zero + zero_offset = static_cast<int16_t>(pitch * pitsync_joined_edge); + for (left_edge = projection_left; projection->pile_count (left_edge) == 0 + && left_edge < projection_right; left_edge++); + for (right_edge = projection_right; projection->pile_count (right_edge) == 0 + && right_edge > left_edge; right_edge--); + array_origin = left_edge - pitch; + // array of points + std::vector<FPCUTPT> cutpts(right_edge - left_edge + pitch * 2 + 1); + // local min results + std::vector<bool> mins(pitch_error * 2 + 1); + for (x = array_origin; x < left_edge; x++) + //free cuts + cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection, + zero_count, pitch, x, 0); + prev_zero = left_edge - 1; + for (offset = 0; offset <= pitch_error; offset++, x++) + //not quite free + cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection, + zero_count, pitch, x, offset); + + best_cost = FLT_MAX; + best_end = nullptr; + for (offset = -pitch_error, minindex = 0; offset < pitch_error; + offset++, minindex++) + mins[minindex] = projection->local_min (x + offset); + next_zero = x + zero_offset + 1; + for (offset = next_zero - 1; offset >= x; offset--) { + if (projection->pile_count (offset) <= zero_count) { + next_zero = offset; + break; + } + } + while (x < right_edge - pitch_error) { + mins[minindex] = projection->local_min (x + pitch_error); + minindex++; + if (minindex > pitch_error * 2) + minindex = 0; + faking = false; + mid_cut = false; + offset = 0; + if (projection->pile_count (x) <= zero_count) { + prev_zero = x; + } + else { + for (offset = 1; offset <= pitch_error; offset++) + if (projection->pile_count (x + offset) <= zero_count + || projection->pile_count (x - offset) <= zero_count) + break; + } + if (offset > pitch_error) { + if (x - prev_zero > zero_offset && next_zero - x > zero_offset) { + for (offset = 0; offset <= pitch_error; offset++) { + test_index = minindex + pitch_error + offset; + if (test_index > pitch_error * 2) + test_index -= pitch_error * 2 + 1; + if (mins[test_index]) + break; + test_index = minindex + pitch_error - offset; + if (test_index > pitch_error * 2) + test_index -= pitch_error * 2 + 1; + if (mins[test_index]) + break; + } + } + if (offset > pitch_error) { + offset = projection->pile_count (x); + faking = true; + } + else { + projection_offset = + static_cast<int16_t>(projection->pile_count (x) / projection_scale); + if (projection_offset > offset) + offset = projection_offset; + mid_cut = true; + } + } + if ((start == 0 && end == 0) + || !textord_fast_pitch_test + || (x - projection_left - start) % pitch <= end) + cutpts[x - array_origin].assign(&cutpts[0], array_origin, x, + faking, mid_cut, offset, projection, + projection_scale, zero_count, pitch, + pitch_error); + else + cutpts[x - array_origin].assign_cheap(&cutpts[0], array_origin, x, + faking, mid_cut, offset, + projection, projection_scale, + zero_count, pitch, + pitch_error); + x++; + if (next_zero < x || next_zero == x + zero_offset) + next_zero = x + zero_offset + 1; + if (projection->pile_count (x + zero_offset) <= zero_count) + next_zero = x + zero_offset; + } + + best_fake = INT16_MAX; + best_cost = INT32_MAX; + best_count = INT16_MAX; + while (x < right_edge + pitch) { + offset = x < right_edge ? right_edge - x : 0; + cutpts[x - array_origin].assign(&cutpts[0], array_origin, x, + false, false, offset, projection, + projection_scale, zero_count, pitch, + pitch_error); + cutpts[x - array_origin].terminal = true; + if (cutpts[x - array_origin].index () + + cutpts[x - array_origin].fake_count <= best_count + best_fake) { + if (cutpts[x - array_origin].fake_count < best_fake + || (cutpts[x - array_origin].fake_count == best_fake + && cutpts[x - array_origin].cost_function () < best_cost)) { + best_fake = cutpts[x - array_origin].fake_count; + best_cost = cutpts[x - array_origin].cost_function (); + best_left_x = x; + best_right_x = x; + best_count = cutpts[x - array_origin].index (); + } + else if (cutpts[x - array_origin].fake_count == best_fake + && x == best_right_x + 1 + && cutpts[x - array_origin].cost_function () == best_cost) { + //exactly equal + best_right_x = x; + } + } + x++; + } + ASSERT_HOST (best_fake < INT16_MAX); + + best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin]; + // for (x=left_edge-pitch;x<right_edge+pitch;x++) + // { + // tprintf("x=%d, C=%g, s=%g, sq=%g, prev=%d\n", + // x,cutpts[x-array_origin].cost_function(), + // cutpts[x-array_origin].sum(), + // cutpts[x-array_origin].squares(), + // cutpts[x-array_origin].previous()->position()); + // } + occupation_count = -1; + do { + for (x = best_end->position () - pitch + pitch_error; + x < best_end->position () - pitch_error + && projection->pile_count (x) == 0; x++); + if (x < best_end->position () - pitch_error) + occupation_count++; + //copy it + segpt = new FPSEGPT (best_end); + seg_it.add_before_then_move (segpt); + best_end = best_end->previous (); + } + while (best_end != nullptr); + seg_it.move_to_last (); + mean_sum = seg_it.data ()->sum (); + mean_sum = mean_sum * mean_sum / best_count; + if (seg_it.data ()->squares () - mean_sum < 0) + tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n", + seg_it.data ()->squares (), seg_it.data ()->sum (), best_count); + return seg_it.data ()->squares () - mean_sum; +} + +} // namespace tesseract |