gap_map.cpp

Go to the documentation of this file.

// 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 "gap_map.h"
 
#include "statistc.h"
 
namespace tesseract {
 
BOOL_VAR(gapmap_debug, false, "Say which blocks have tables");
BOOL_VAR(gapmap_use_ends, false, "Use large space at start and end of rows");
BOOL_VAR(gapmap_no_isolated_quanta, false, "Ensure gaps not less than 2quanta wide");
double_VAR(gapmap_big_gaps, 1.75, "xht multiplier");
 
/*************************************************************************
 * A block gap map is a quantised histogram of whitespace regions in the
 * block. It is a vertical projection of wide gaps WITHIN lines
 *
 * The map is held as an array of counts of rows which have a wide gap
 * covering that region of the row. Each bucket in the map represents a width
 * of about half an xheight - (The median of the xhts in the rows is used.)
 *
 * The block is considered RECTANGULAR - delimited by the left and right
 * extremes of the rows in the block. However, ONLY wide gaps WITHIN a row are
 * counted.
 *
 *************************************************************************/
 
GAPMAP::GAPMAP(     // Constructor
    TO_BLOCK *block // block
) {
  TO_ROW *row;         // current row
  BLOBNBOX_IT blob_it; // iterator
  TBOX blob_box;
  TBOX prev_blob_box;
  int16_t gap_width;
  int16_t start_of_row;
  int16_t end_of_row;
  STATS xht_stats(0, 127);
  int16_t min_quantum;
  int16_t max_quantum;
  int16_t i;
 
  /*
  Find left and right extremes and bucket size
*/
  map = nullptr;
  min_left = INT16_MAX;
  max_right = -INT16_MAX;
  total_rows = 0;
  any_tabs = false;
 
  // row iterator
  TO_ROW_IT row_it(block->get_rows());
  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
    row = row_it.data();
    if (!row->blob_list()->empty()) {
      total_rows++;
      xht_stats.add(static_cast<int16_t>(floor(row->xheight + 0.5)), 1);
      blob_it.set_to_list(row->blob_list());
      start_of_row = blob_it.data()->bounding_box().left();
      end_of_row = blob_it.data_relative(-1)->bounding_box().right();
      if (min_left > start_of_row) {
        min_left = start_of_row;
      }
      if (max_right < end_of_row) {
        max_right = end_of_row;
      }
    }
  }
  if ((total_rows < 3) || (min_left >= max_right)) {
    bucket_size = 0;
    map_max = 0;
    total_rows = 0;
    min_left = max_right = 0;
    return;
  }
  bucket_size = static_cast<int16_t>(floor(xht_stats.median() + 0.5)) / 2;
  map_max = (max_right - min_left) / bucket_size;
  map = new int16_t[map_max + 1];
  for (i = 0; i <= map_max; i++) {
    map[i] = 0;
  }
 
  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
    row = row_it.data();
    if (!row->blob_list()->empty()) {
      blob_it.set_to_list(row->blob_list());
      blob_it.mark_cycle_pt();
      blob_box = box_next(&blob_it);
      prev_blob_box = blob_box;
      if (gapmap_use_ends) {
        /* Leading space */
        gap_width = blob_box.left() - min_left;
        if ((gap_width > gapmap_big_gaps * row->xheight) && gap_width > 2) {
          max_quantum = (blob_box.left() - min_left) / bucket_size;
          if (max_quantum > map_max) {
            max_quantum = map_max;
          }
          for (i = 0; i <= max_quantum; i++) {
            map[i]++;
          }
        }
      }
      while (!blob_it.cycled_list()) {
        blob_box = box_next(&blob_it);
        gap_width = blob_box.left() - prev_blob_box.right();
        if ((gap_width > gapmap_big_gaps * row->xheight) && gap_width > 2) {
          min_quantum = (prev_blob_box.right() - min_left) / bucket_size;
          max_quantum = (blob_box.left() - min_left) / bucket_size;
          if (max_quantum > map_max) {
            max_quantum = map_max;
          }
          for (i = min_quantum; i <= max_quantum; i++) {
            map[i]++;
          }
        }
        prev_blob_box = blob_box;
      }
      if (gapmap_use_ends) {
        /* Trailing space */
        gap_width = max_right - prev_blob_box.right();
        if ((gap_width > gapmap_big_gaps * row->xheight) && gap_width > 2) {
          min_quantum = (prev_blob_box.right() - min_left) / bucket_size;
          if (min_quantum < 0) {
            min_quantum = 0;
          }
          for (i = min_quantum; i <= map_max; i++) {
            map[i]++;
          }
        }
      }
    }
  }
  for (i = 0; i <= map_max; i++) {
    if (map[i] > total_rows / 2) {
      if (gapmap_no_isolated_quanta &&
          (((i == 0) && (map[i + 1] <= total_rows / 2)) ||
           ((i == map_max) && (map[i - 1] <= total_rows / 2)) ||
           ((i > 0) && (i < map_max) && (map[i - 1] <= total_rows / 2) &&
            (map[i + 1] <= total_rows / 2)))) {
        map[i] = 0; // prevent isolated quantum
      } else {
        any_tabs = true;
      }
    }
  }
  if (gapmap_debug && any_tabs) {
    tprintf("Table found\n");
  }
}
 
/*************************************************************************
 * GAPMAP::table_gap()
 * Is there a bucket in the specified range where more than half the rows in the
 * block have a wide gap?
 *************************************************************************/
 
bool GAPMAP::table_gap( // Is gap a table?
    int16_t left,       // From here
    int16_t right       // To here
) {
  int16_t min_quantum;
  int16_t max_quantum;
  int16_t i;
  bool tab_found = false;
 
  if (!any_tabs) {
    return false;
  }
 
  min_quantum = (left - min_left) / bucket_size;
  max_quantum = (right - min_left) / bucket_size;
  // Clip to the bounds of the array. In some circumstances (big blob followed
  // by small blob) max_quantum can exceed the map_max bounds, but we clip
  // here instead, as it provides better long-term safety.
  if (min_quantum < 0) {
    min_quantum = 0;
  }
  if (max_quantum > map_max) {
    max_quantum = map_max;
  }
  for (i = min_quantum; (!tab_found && (i <= max_quantum)); i++) {
    if (map[i] > total_rows / 2) {
      tab_found = true;
    }
  }
  return tab_found;
}
 
} // namespace tesseract