///////////////////////////////////////////////////////////////////////

// File:        tablerecog.h

// Description: Functions to detect structure of tables.

// Author:      Nicholas Beato

//

// (C) Copyright 2010, Google Inc.

// 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.

//

///////////////////////////////////////////////////////////////////////

#ifndef TABLERECOG_H_

#define TABLERECOG_H_

#include "colpartitiongrid.h"

namespace tesseract {

// There are 2 classes in this file. They have 2 different purposes.

//  - StructuredTable contains the methods to find the structure given

//    a specific bounding box and grow that structure.

//  - TableRecognizer contains the methods to adjust the possible positions

//    of a table without worrying about structure.

//

// To use these classes, the assumption is that the TableFinder will

// have a guess of the location of a table (or possibly over/undersegmented

// tables). The TableRecognizer is responsible for finding the table boundaries

// at a high level. The StructuredTable class is responsible for determining

// the structure of the table and trying to maximize its bounds while retaining

// the structure.

// (The latter part is not implemented yet, but that was the goal).

//

// While on the boundary discussion, keep in mind that this is a first pass.

// There should eventually be some things like internal structure checks,

// and, more importantly, surrounding text flow checks.

//

// Usage:

// The StructuredTable class contains methods to query a potential table.

// It has functions to find structure, count rows, find ColPartitions that

// intersect gridlines, etc. It is not meant to blindly find a table. It

// is meant to start with a known table location and enhance it.

// Usage:

//    ColPartitionGrid text_grid, line_grid;  // init

//    TBOX table_box;  // known location of table location

//

//    StructuredTable table;

//    table.Init();  // construction code

//    table.set_text_grid(/* text */);  // These 2 grids can be the same!

//    table.set_line_grid(/* lines */);

//    table.set_min_text_height(10);    // Filter vertical and tall text.

//    // IMPORTANT! The table needs to be told where it is!

//    table.set_bounding_box(table_box);  // Set initial table location.

//    if (table.FindWhitespacedStructure()) {

//      // process table

//      table.column_count();  // number of columns

//      table.row_count();     // number of rows

//      table.cells_count();   // number of cells

//      table.bounding_box();  // updated bounding box

//      // etc.

//    }

//

class TESS_API StructuredTable {

public:

  StructuredTable();

  ~StructuredTable() = default;

  // Initialization code. Must be called after the constructor.

  void Init();

  // Sets the grids used by the table. These can be changed between

  // calls to Recognize. They are treated as read-only data.

  void set_text_grid(ColPartitionGrid *text);

  void set_line_grid(ColPartitionGrid *lines);

  // Filters text partitions that are ridiculously tall to prevent

  // merging rows.

  void set_max_text_height(int height);

  // Basic accessors. Some are treated as attributes despite having indirect

  // representation.

  bool is_lined() const;

  unsigned row_count() const;

  unsigned column_count() const;

  unsigned cell_count() const;

  void set_bounding_box(const TBOX &box);

  const TBOX &bounding_box() const;

  int median_cell_height();

  int median_cell_width();

  int row_height(unsigned row) const;

  int column_width(unsigned column) const;

  int space_above() const;

  int space_below() const;

  // Given enough horizontal and vertical lines in a region, create this table

  // based on the structure given by the lines. Return true if it worked out.

  // Code assumes the lines exist. It is the caller's responsibility to check

  // for lines and find an appropriate bounding box.

  bool FindLinedStructure();

  // The main subroutine for finding generic table structure. The function

  // finds the grid structure in the given box. Returns true if a good grid

  // exists, implying that "this" table is valid.

  bool FindWhitespacedStructure();

  ////////

  //////// Functions to query table info.

  ////////

  // Returns true if inserting part into the table does not cause any

  // cell merges.

  bool DoesPartitionFit(const ColPartition &part) const;

  // Checks if a sub-table has multiple data cells filled.

  int CountFilledCells();

  int CountFilledCellsInRow(int row);

  int CountFilledCellsInColumn(int column);

  int CountFilledCells(unsigned row_start, unsigned row_end, unsigned column_start, unsigned column_end);

  // Makes sure that at least one cell in a row has substantial area filled.

  // This can filter out large whitespace caused by growing tables too far

  // and page numbers.

  // (currently bugged for some reason).

  bool VerifyRowFilled(int row);

  // Finds the filled area in a cell.

  double CalculateCellFilledPercentage(unsigned row, unsigned column);

  // Debug display, draws the table in the given color. If the table is not

  // valid, the table and "best" grid lines are still drawn in the given color.

  void Display(ScrollView *window, ScrollView::Color color);

protected:

  // Clear the structure information.

  void ClearStructure();

  ////////

  //////// Lined tables

  ////////

  // Verifies the lines do not intersect partitions. This happens when

  // the lines are in column boundaries and extend the full page. As a result,

  // the grid lines go through column text. The condition is detectable.

  bool VerifyLinedTableCells();

  ////////

  //////// Tables with whitespace

  ////////

  // This is the function to change if you want to filter resulting tables

  // better. Right now it just checks for a minimum cell count and such.

  // You could add things like maximum number of ColPartitions per cell or

  // similar.

  bool VerifyWhitespacedTable();

  // Find the columns of a table using whitespace.

  void FindWhitespacedColumns();

  // Find the rows of a table using whitespace.

  void FindWhitespacedRows();

  ////////

  //////// Functions to provide information about the table.

  ////////

  // Calculates the whitespace around the table using the table boundary and

  // the supplied grids (set_text_grid and set_line_grid).

  void CalculateMargins();

  // Update the table margins with the supplied grid. This is

  // only called by calculate margins to use multiple grid sources.

  void UpdateMargins(ColPartitionGrid *grid);

  int FindVerticalMargin(ColPartitionGrid *grid, int start_x, bool decrease) const;

  int FindHorizontalMargin(ColPartitionGrid *grid, int start_y, bool decrease) const;

  // Calculates stats on the table, namely the median cell height and width.

  void CalculateStats();

  ////////

  //////// Functions to try to "fix" some table errors.

  ////////

  // Given a whitespaced table, this looks for bordering lines that might

  // be page layout boxes around the table. It is necessary to get the margins

  // correct on the table. If the lines are not joined, the margins will be

  // the distance to the line, which is not right.

  void AbsorbNearbyLines();

  // Nice utility function for finding partition gaps. You feed it a sorted

  // list of all of the mins/maxes of the partitions in the table, and it gives

  // you the gaps (middle). This works for both vertical and horizontal

  // gaps.

  //

  // If you want to allow slight overlap in the division and the partitions,

  // just scale down the partitions before inserting them in the list.

  // Likewise, you can force at least some space between partitions.

  // This trick is how the horizontal partitions are done (since the page

  // skew could make it hard to find splits in the text).

  //

  // As a result, "0 distance" between closest partitions causes a gap.

  // This is not a programmatic assumption. It is intentional and simplifies

  // things.

  //

  // "max_merged" indicates both the minimum number of stacked partitions

  // to cause a cell (add 1 to it), and the maximum number of partitions that

  // a grid line can intersect. For example, if max_merged is 0, then lines

  // are inserted wherever space exists between partitions. If it is 2,

  // lines may intersect 2 partitions at most, but you also need at least

  // 2 partitions to generate a line.

  static void FindCellSplitLocations(const std::vector<int> &min_list,

                                     const std::vector<int> &max_list, int max_merged,

                                     std::vector<int> *locations);

  ////////

  //////// Utility function for table queries

  ////////

  // Counts the number of ColPartitions that intersect vertical cell

  // division at this x value. Used by VerifyLinedTable.

  int CountVerticalIntersections(int x);

  int CountHorizontalIntersections(int y);

  // Counts how many text partitions are in this box.

  int CountPartitions(const TBOX &box);

  ////////

  //////// Data members.

  ////////

  // Input data, used as read only data to make decisions.

  ColPartitionGrid *text_grid_; // Text ColPartitions

  ColPartitionGrid *line_grid_; // Line ColPartitions

  // Table structure.

  // bounding box is a convenient external representation.

  // cell_x_ and cell_y_ indicate the grid lines.

  TBOX bounding_box_;         // Bounding box

  std::vector<int> cell_x_; // Locations of vertical divisions (sorted)

  std::vector<int> cell_y_; // Locations of horizontal divisions (sorted)

  bool is_lined_;             // Is the table backed up by a line structure

  // Table margins, set via CalculateMargins

  int space_above_;

  int space_below_;

  int space_left_;

  int space_right_;

  int median_cell_height_;

  int median_cell_width_;

  // Filters, used to prevent awkward partitions from destroying structure.

  int max_text_height_;

};

class TESS_API TableRecognizer {

public:

  TableRecognizer() = default;

  ~TableRecognizer() = default;

  // Initialization code. Must be called after the constructor.

  void Init();

  ////////

  //////// Pre-recognize methods to initial table constraints.

  ////////

  // Sets the grids used by the table. These can be changed between

  // calls to Recognize. They are treated as read-only data.

  void set_text_grid(ColPartitionGrid *text);

  void set_line_grid(ColPartitionGrid *lines);

  // Sets some additional constraints on the table.

  void set_min_height(int height);

  void set_min_width(int width);

  // Filters text partitions that are ridiculously tall to prevent

  // merging rows. Note that "filters" refers to allowing horizontal

  // cells to slice through them on the premise that they were

  // merged text rows during previous layout.

  void set_max_text_height(int height);

  // Given a guess location, the RecognizeTable function will try to find a

  // structured grid in the area. On success, it will return a new

  // StructuredTable (and assumes you will delete it). Otherwise,

  // nullptr is returned.

  //

  // Keep in mind, this may "overgrow" or "undergrow" the size of guess.

  // Ideally, there is either a one-to-one correspondence between

  // the guess and table or no table at all. This is not the best of

  // assumptions right now, but was made to try to keep things simple in

  // the first pass.

  //

  // If a line structure is available on the page in the given region,

  // the table will use the linear structure as it is.

  // Otherwise, it will try to maximize the whitespace around it while keeping

  // a grid structure. This is somewhat working.

  //

  // Since the combination of adjustments can get high, effort was

  // originally made to keep the number of adjustments linear in the number

  // of partitions. The underlying structure finding code used to be

  // much more complex. I don't know how necessary this constraint is anymore.

  // The evaluation of a possible table is kept within O(nlogn) in the size of

  // the table (where size is the number of partitions in the table).

  // As a result, the algorithm is capable of O(n^2 log n). Depending

  // on the grid search size, it may be higher.

  //

  // Last note: it is possible to just try all partition boundaries at a high

  // level O(n^4) and do a verification scheme (at least O(nlogn)). If there

  // area 200 partitions on a page, this could be too costly. Effort could go

  // into pruning the search, but I opted for something quicker. I'm confident

  // that the independent adjustments can get similar results and keep the

  // complextiy down. However, the other approach could work without using

  // TableFinder at all if it is fast enough.  It comes down to properly

  // deciding what is a table. The code currently relies on TableFinder's

  // guess to the location of a table for that.

  StructuredTable *RecognizeTable(const TBOX &guess_box);

protected:

  ////////

  //////// Lined tables

  ////////

  // Returns true if the given box has a lined table within it. The

  // table argument will be updated with the table if the table exists.

  bool RecognizeLinedTable(const TBOX &guess_box, StructuredTable *table);

  // Returns true if the given box has a large number of horizontal and

  // vertical lines present. If so, we assume the extent of these lines

  // uniquely defines a table and find that table via SolveLinedTable.

  bool HasSignificantLines(const TBOX &guess);

  // Given enough horizontal and vertical lines in a region, find a bounding

  // box that encloses all of them (as well as newly introduced lines).

  // The bounding box is the smallest box that encloses the lines in guess

  // without having any lines sticking out of it.

  // bounding_box is an in/out parameter.

  // On input, it in the extents of the box to search.

  // On output, it is the resulting bounding box.

  bool FindLinesBoundingBox(TBOX *bounding_box);

  // Iteration in above search.

  // bounding_box is an in/out parameter.

  // On input, it in the extents of the box to search.

  // On output, it is the resulting bounding box.

  bool FindLinesBoundingBoxIteration(TBOX *bounding_box);

  ////////

  //////// Generic "whitespaced" tables

  ////////

  // Returns true if the given box has a whitespaced table within it. The

  // table argument will be updated if the table exists. Also note

  // that this method will fail if the guess_box center is not

  // mostly within the table.

  bool RecognizeWhitespacedTable(const TBOX &guess_box, StructuredTable *table);

  // Finds the location of a horizontal split relative to y.

  // This function is mostly unused now. If the SolveWhitespacedTable

  // changes much, it can be removed. Note, it isn't really as reliable

  // as I thought. I went with alternatives for most of the other uses.

  int NextHorizontalSplit(int left, int right, int y, bool top_to_bottom);

  // Input data, used as read only data to make decisions.

  ColPartitionGrid *text_grid_ = nullptr; // Text ColPartitions

  ColPartitionGrid *line_grid_ = nullptr; // Line ColPartitions

  // Table constraints, a "good" table must satisfy these.

  int min_height_ = 0;

  int min_width_ = 0;

  // Filters, used to prevent awkward partitions from destroying structure.

  int max_text_height_ = INT32_MAX; // Horizontal lines may intersect taller text.

};

} // namespace tesseract

#endif /* TABLERECOG_H_ */