tesseract
5.0.0-alpha-619-ge9db
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
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
using
CostFunc
= int64_t (
DPPoint
::*)(
const
DPPoint
*);
50
51
DPPoint
()
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,
66
CostFunc
cost_func,
int
size,
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
85
private
:
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,
90
int32_t n, int32_t sig_x, 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_
tesseract::DPPoint::DPPoint
DPPoint()
Definition:
dppoint.h:82
tesseract::DPPoint::AddLocalCost
void AddLocalCost(int new_cost)
Definition:
dppoint.h:112
tesseract::DPPoint
Definition:
dppoint.h:59
tesseract::DPPoint::CostWithVariance
int64_t CostWithVariance(const DPPoint *prev)
Definition:
dppoint.cpp:85
tesseract::DPPoint::Solve
static DPPoint * Solve(int min_step, int max_step, bool debug, CostFunc cost_func, int size, DPPoint *points)
Definition:
dppoint.cpp:47
tesseract::DPPoint::CostFunc
int64_t(DPPoint::*)(const DPPoint *) CostFunc
Definition:
dppoint.h:80
tesseract
Definition:
baseapi.h:65
tesseract::DPPoint::best_prev
const DPPoint * best_prev() const
Definition:
dppoint.h:109
tesseract::DPPoint::Pathlength
int Pathlength() const
Definition:
dppoint.h:106
tesseract::DPPoint::total_cost
int total_cost() const
Definition:
dppoint.h:103
src
ccstruct
dppoint.h
Generated on Thu Jan 30 2020 14:22:20 for tesseract by
1.8.16