Tesseract  3.02
tesseract-ocr/ccstruct/dppoint.cpp
Go to the documentation of this file.
```00001 /**********************************************************************
00002  * File:        dppoint.cpp
00003  * Description: Simple generic dynamic programming class.
00004  * Author:      Ray Smith
00005  * Created:     Wed Mar 25 19:08:01 PDT 2009
00006  *
00007  * (C) Copyright 2009, Google Inc.
00008  ** Licensed under the Apache License, Version 2.0 (the "License");
00009  ** you may not use this file except in compliance with the License.
00010  ** You may obtain a copy of the License at
00011  ** http://www.apache.org/licenses/LICENSE-2.0
00012  ** Unless required by applicable law or agreed to in writing, software
00013  ** distributed under the License is distributed on an "AS IS" BASIS,
00014  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00015  ** See the License for the specific language governing permissions and
00016  ** limitations under the License.
00017  *
00018  **********************************************************************/
00019
00020 #include "dppoint.h"
00021 #include "tprintf.h"
00022
00023 namespace tesseract {
00024
00025 // Solve the dynamic programming problem for the given array of points, with
00026 // the given size and cost function.
00027 // Steps backwards are limited to being between min_step and max_step
00028 // inclusive.
00029 // The return value is the tail of the best path.
00030 DPPoint* DPPoint::Solve(int min_step, int max_step, bool debug,
00031                         CostFunc cost_func, int size, DPPoint* points) {
00032   if (size <= 0 || max_step < min_step || min_step >= size)
00033     return NULL;  // Degenerate, but not necessarily an error.
00034   ASSERT_HOST(min_step > 0);  // Infinite loop possible if this is not true.
00035   if (debug)
00036     tprintf("min = %d, max=%d\n",
00037             min_step, max_step);
00038   // Evaluate the total cost at each point.
00039   for (int i = 0; i < size; ++i) {
00040     for (int offset = min_step; offset <= max_step; ++offset) {
00041       DPPoint* prev = offset <= i ? points + i - offset : NULL;
00042       inT64 new_cost = (points[i].*cost_func)(prev);
00043       if (points[i].best_prev_ != NULL && offset > min_step * 2 &&
00044           new_cost > points[i].total_cost_)
00045         break;  // Find only the first minimum if going over twice the min.
00046     }
00047     points[i].total_cost_ += points[i].local_cost_;
00048     if (debug) {
00049       tprintf("At point %d, local cost=%d, total_cost=%d, steps=%d\n",
00050               i, points[i].local_cost_, points[i].total_cost_,
00051               points[i].total_steps_);
00052     }
00053   }
00054   // Now find the end of the best path and return it.
00055   int best_cost = points[size - 1].total_cost_;
00056   int best_end = size - 1;
00057   for (int end = best_end - 1; end >= size - min_step; --end) {
00058     int cost = points[end].total_cost_;
00059     if (cost < best_cost) {
00060       best_cost = cost;
00061       best_end = end;
00062     }
00063   }
00064   return points + best_end;
00065 }
00066
00067 // A CostFunc that takes the variance of step into account in the cost.
00068 inT64 DPPoint::CostWithVariance(const DPPoint* prev) {
00069   if (prev == NULL || prev == this) {
00070     UpdateIfBetter(0, 1, NULL, 0, 0, 0);
00071     return 0;
00072   }
00073
00074   int delta = this - prev;
00075   inT32 n = prev->n_ + 1;
00076   inT32 sig_x = prev->sig_x_ + delta;
00077   inT64 sig_xsq = prev->sig_xsq_ + delta * delta;
00078   inT64 cost = (sig_xsq - sig_x * sig_x / n) / n;
00079   cost += prev->total_cost_;
00080   UpdateIfBetter(cost, prev->total_steps_ + 1, prev, n, sig_x, sig_xsq);
00081   return cost;
00082 }
00083
00084 // Update the other members if the cost is lower.
00085 void DPPoint::UpdateIfBetter(inT64 cost, inT32 steps, const DPPoint* prev,
00086                              inT32 n, inT32 sig_x, inT64 sig_xsq) {
00087   if (cost < total_cost_) {
00088     total_cost_ = cost;
00089     total_steps_ = steps;
00090     best_prev_ = prev;
00091     n_ = n;
00092     sig_x_ = sig_x;
00093     sig_xsq_ = sig_xsq;
00094   }
00095 }
00096
00097 }  // namespace tesseract.
00098
```