tesseract v5.3.3.20231005
dppoint.h
Go to the documentation of this file.
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
25namespace 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;
44class DPPoint {
45public:
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 using CostFunc = int64_t (DPPoint::*)(const DPPoint *);
50
52 : local_cost_(0)
53 , total_cost_(INT32_MAX)
54 , total_steps_(1)
55 , best_prev_(nullptr)
56 , n_(0)
57 , sig_x_(0)
58 , sig_xsq_(0) {}
59
60 // Solve the dynamic programming problem for the given array of points, with
61 // the given size and cost function.
62 // Steps backwards are limited to being between min_step and max_step
63 // inclusive.
64 // The return value is the tail of the best path.
65 static DPPoint *Solve(int min_step, int max_step, bool debug, CostFunc cost_func, int size,
66 DPPoint *points);
67
68 // A CostFunc that takes the variance of step into account in the cost.
69 int64_t CostWithVariance(const DPPoint *prev);
70
71 // Accessors.
72 int total_cost() const {
73 return total_cost_;
74 }
75 int Pathlength() const {
76 return total_steps_;
77 }
78 const DPPoint *best_prev() const {
79 return best_prev_;
80 }
81 void AddLocalCost(int new_cost) {
82 local_cost_ += new_cost;
83 }
84
85private:
86 // Code common to different cost functions.
87
88 // Update the other members if the cost is lower.
89 void UpdateIfBetter(int64_t cost, int32_t steps, const DPPoint *prev, int32_t n, int32_t sig_x,
90 int64_t sig_xsq);
91
92 int32_t local_cost_; // Cost of this point on its own.
93 int32_t total_cost_; // Sum of all costs in best path to here.
94 // During cost calculations local_cost is excluded.
95 int32_t total_steps_; // Number of steps in best path to here.
96 const DPPoint *best_prev_; // Pointer to prev point in best path from here.
97 // Information for computing the variance part of the cost.
98 int32_t n_; // Number of steps in best path to here for variance.
99 int32_t sig_x_; // Sum of step sizes for computing variance.
100 int64_t sig_xsq_; // Sum of squares of steps for computing variance.
101};
102
103} // namespace tesseract.
104
105#endif // TESSERACT_CCSTRUCT_DPPOINT_H_
int total_cost() const
Definition: dppoint.h:72
int64_t(DPPoint::*)(const DPPoint *) CostFunc
Definition: dppoint.h:49
void AddLocalCost(int new_cost)
Definition: dppoint.h:81
static DPPoint * Solve(int min_step, int max_step, bool debug, CostFunc cost_func, int size, DPPoint *points)
Definition: dppoint.cpp:31
const DPPoint * best_prev() const
Definition: dppoint.h:78
int Pathlength() const
Definition: dppoint.h:75
int64_t CostWithVariance(const DPPoint *prev)
Definition: dppoint.cpp:70