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