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.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: dppoint.cpp
3 * Description: Simple generic dynamic programming class.
4 * Author: Ray Smith
5 * Created: Wed Mar 25 19:08: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 #include "dppoint.h"
21 #include "tprintf.h"
22
23 namespace tesseract {
24
25 // Solve the dynamic programming problem for the given array of points, with
26 // the given size and cost function.
27 // Steps backwards are limited to being between min_step and max_step
28 // inclusive.
29 // The return value is the tail of the best path.
30 DPPoint* DPPoint::Solve(int min_step, int max_step, bool debug,
31 CostFunc cost_func, int size, DPPoint* points) {
32 if (size <= 0 || max_step < min_step || min_step >= size)
33 return NULL; // Degenerate, but not necessarily an error.
34 ASSERT_HOST(min_step > 0); // Infinite loop possible if this is not true.
35 if (debug)
36 tprintf("min = %d, max=%d\n",
37 min_step, max_step);
38 // Evaluate the total cost at each point.
39 for (int i = 0; i < size; ++i) {
40 for (int offset = min_step; offset <= max_step; ++offset) {
41 DPPoint* prev = offset <= i ? points + i - offset : NULL;
42 inT64 new_cost = (points[i].*cost_func)(prev);
43 if (points[i].best_prev_ != NULL && offset > min_step * 2 &&
44 new_cost > points[i].total_cost_)
45 break; // Find only the first minimum if going over twice the min.
46 }
47 points[i].total_cost_ += points[i].local_cost_;
48 if (debug) {
49 tprintf("At point %d, local cost=%d, total_cost=%d, steps=%d\n",
50 i, points[i].local_cost_, points[i].total_cost_,
51 points[i].total_steps_);
52 }
53 }
54 // Now find the end of the best path and return it.
55 int best_cost = points[size - 1].total_cost_;
56 int best_end = size - 1;
57 for (int end = best_end - 1; end >= size - min_step; --end) {
58 int cost = points[end].total_cost_;
59 if (cost < best_cost) {
60 best_cost = cost;
61 best_end = end;
62 }
63 }
64 return points + best_end;
65 }
66
67 // A CostFunc that takes the variance of step into account in the cost.
68 inT64 DPPoint::CostWithVariance(const DPPoint* prev) {
69 if (prev == NULL || prev == this) {
70 UpdateIfBetter(0, 1, NULL, 0, 0, 0);
71 return 0;
72 }
73
74 int delta = this - prev;
75 inT32 n = prev->n_ + 1;
76 inT32 sig_x = prev->sig_x_ + delta;
77 inT64 sig_xsq = prev->sig_xsq_ + delta * delta;
78 inT64 cost = (sig_xsq - sig_x * sig_x / n) / n;
79 cost += prev->total_cost_;
80 UpdateIfBetter(cost, prev->total_steps_ + 1, prev, n, sig_x, sig_xsq);
81 return cost;
82 }
83
84 // Update the other members if the cost is lower.
85 void DPPoint::UpdateIfBetter(inT64 cost, inT32 steps, const DPPoint* prev,
86 inT32 n, inT32 sig_x, inT64 sig_xsq) {
87 if (cost < total_cost_) {
88 total_cost_ = cost;
89 total_steps_ = steps;
90 best_prev_ = prev;
91 n_ = n;
92 sig_x_ = sig_x;
93 sig_xsq_ = sig_xsq;
94 }
95 }
96
97 } // namespace tesseract.
98