tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
dppoint.h
1 /**********************************************************************
2  * File: dppoint.h
3  * Description: Simple generic dynamic programming class.
4  * Author: Ray Smith
5  * Created: Wed Mar 25 18:57:01 PDT 2009
6  *
7  * (C) Copyright 2009, Google Inc.
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 #ifndef TESSERACT_CCSTRUCT_DPPOINT_H_
21 #define TESSERACT_CCSTRUCT_DPPOINT_H_
22 
23 #include <cstdint>
24 
25 namespace tesseract {
26 
27 // A simple class to provide a dynamic programming solution to a class of
28 // 1st-order problems in which the cost is dependent only on the current
29 // step and the best cost to that step, with a possible special case
30 // of using the variance of the steps, and only the top choice is required.
31 // Useful for problems such as finding the optimal cut points in a fixed-pitch
32 // (vertical or horizontal) situation.
33 // Skeletal Example:
34 // DPPoint* array = new DPPoint[width];
35 // for (int i = 0; i < width; i++) {
36 // array[i].AddLocalCost(cost_at_i)
37 // }
38 // DPPoint* best_end = DPPoint::Solve(..., array);
39 // while (best_end != nullptr) {
40 // int cut_index = best_end - array;
41 // best_end = best_end->best_prev();
42 // }
43 // delete [] array;
44 class DPPoint {
45  public:
46  // The cost function evaluates the total cost at this (excluding this's
47  // local_cost) and if it beats this's total_cost, then
48  // replace the appropriate values in this.
49  typedef int64_t (DPPoint::*CostFunc)(const DPPoint* prev);
50 
52  : local_cost_(0), total_cost_(INT32_MAX), total_steps_(1), best_prev_(nullptr),
53  n_(0), sig_x_(0), sig_xsq_(0) {
54  }
55 
56  // Solve the dynamic programming problem for the given array of points, with
57  // the given size and cost function.
58  // Steps backwards are limited to being between min_step and max_step
59  // inclusive.
60  // The return value is the tail of the best path.
61  static DPPoint* Solve(int min_step, int max_step, bool debug,
62  CostFunc cost_func, int size, DPPoint* points);
63 
64  // A CostFunc that takes the variance of step into account in the cost.
65  int64_t CostWithVariance(const DPPoint* prev);
66 
67  // Accessors.
68  int total_cost() const {
69  return total_cost_;
70  }
71  int Pathlength() const {
72  return total_steps_;
73  }
74  const DPPoint* best_prev() const {
75  return best_prev_;
76  }
77  void AddLocalCost(int new_cost) {
78  local_cost_ += new_cost;
79  }
80 
81  private:
82  // Code common to different cost functions.
83 
84  // Update the other members if the cost is lower.
85  void UpdateIfBetter(int64_t cost, int32_t steps, const DPPoint* prev,
86  int32_t n, int32_t sig_x, int64_t sig_xsq);
87 
88  int32_t local_cost_; // Cost of this point on its own.
89  int32_t total_cost_; // Sum of all costs in best path to here.
90  // During cost calculations local_cost is excluded.
91  int32_t total_steps_; // Number of steps in best path to here.
92  const DPPoint* best_prev_; // Pointer to prev point in best path from here.
93  // Information for computing the variance part of the cost.
94  int32_t n_; // Number of steps in best path to here for variance.
95  int32_t sig_x_; // Sum of step sizes for computing variance.
96  int64_t sig_xsq_; // Sum of squares of steps for computing variance.
97 };
98 
99 } // namespace tesseract.
100 
101 #endif // TESSERACT_CCSTRUCT_DPPOINT_H_
int32_t total_cost_
Definition: dppoint.h:89
void UpdateIfBetter(int64_t cost, int32_t steps, const DPPoint *prev, int32_t n, int32_t sig_x, int64_t sig_xsq)
Definition: dppoint.cpp:86
int total_cost() const
Definition: dppoint.h:68
int64_t(DPPoint::* CostFunc)(const DPPoint *prev)
Definition: dppoint.h:49
int64_t sig_xsq_
Definition: dppoint.h:96
int32_t sig_x_
Definition: dppoint.h:95
int32_t total_steps_
Definition: dppoint.h:91
int Pathlength() const
Definition: dppoint.h:71
Definition: baseapi.cpp:94
Definition: dppoint.h:44
const DPPoint * best_prev_
Definition: dppoint.h:92
int32_t n_
Definition: dppoint.h:94
const DPPoint * best_prev() const
Definition: dppoint.h:74
int32_t local_cost_
Definition: dppoint.h:88
static DPPoint * Solve(int min_step, int max_step, bool debug, CostFunc cost_func, int size, DPPoint *points)
Definition: dppoint.cpp:31
void AddLocalCost(int new_cost)
Definition: dppoint.h:77
int64_t CostWithVariance(const DPPoint *prev)
Definition: dppoint.cpp:69
DPPoint()
Definition: dppoint.h:51