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
mnt
data
src
tesseract-ocr
ccstruct
dppoint.h
Generated on Thu Nov 1 2012 20:19:44 for Tesseract by
1.8.1