Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 "host.h"
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 != NULL) {
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 (DPPoint::*CostFunc)(const DPPoint* prev);
50
51 DPPoint()
52 : local_cost_(0), total_cost_(MAX_INT32), total_steps_(1), best_prev_(NULL),
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 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 cost, inT32 steps, const DPPoint* prev,
86 inT32 n, inT32 sig_x, inT64 sig_xsq);
87
88 inT32 local_cost_; // Cost of this point on its own.
89 inT32 total_cost_; // Sum of all costs in best path to here.
90 // During cost calculations local_cost is excluded.
91 inT32 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 n_; // Number of steps in best path to here for variance.
95 inT32 sig_x_; // Sum of step sizes for computing variance.
96 inT64 sig_xsq_; // Sum of squares of steps for computing variance.
97 };
98
99 } // namespace tesseract.
100
101 #endif // TESSERACT_CCSTRUCT_DPPOINT_H__
102