Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccstruct/dppoint.cpp @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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, CostFunc cost_func, int size,
32 DPPoint *points) {
33 if (size <= 0 || max_step < min_step || min_step >= size) {
34 return nullptr; // Degenerate, but not necessarily an error.
35 }
36 ASSERT_HOST(min_step > 0); // Infinite loop possible if this is not true.
37 if (debug) {
38 tprintf("min = %d, max=%d\n", min_step, max_step);
39 }
40 // Evaluate the total cost at each point.
41 for (int i = 0; i < size; ++i) {
42 for (int offset = min_step; offset <= max_step; ++offset) {
43 DPPoint *prev = offset <= i ? points + i - offset : nullptr;
44 int64_t new_cost = (points[i].*cost_func)(prev);
45 if (points[i].best_prev_ != nullptr && offset > min_step * 2 &&
46 new_cost > points[i].total_cost_) {
47 break; // Find only the first minimum if going over twice the min.
48 }
49 }
50 points[i].total_cost_ += points[i].local_cost_;
51 if (debug) {
52 tprintf("At point %d, local cost=%d, total_cost=%d, steps=%d\n", i, points[i].local_cost_,
53 points[i].total_cost_, points[i].total_steps_);
54 }
55 }
56 // Now find the end of the best path and return it.
57 int best_cost = points[size - 1].total_cost_;
58 int best_end = size - 1;
59 for (int end = best_end - 1; end >= size - min_step; --end) {
60 int cost = points[end].total_cost_;
61 if (cost < best_cost) {
62 best_cost = cost;
63 best_end = end;
64 }
65 }
66 return points + best_end;
67 }
68
69 // A CostFunc that takes the variance of step into account in the cost.
70 int64_t DPPoint::CostWithVariance(const DPPoint *prev) {
71 if (prev == nullptr || prev == this) {
72 UpdateIfBetter(0, 1, nullptr, 0, 0, 0);
73 return 0;
74 }
75
76 int delta = this - prev;
77 int32_t n = prev->n_ + 1;
78 int32_t sig_x = prev->sig_x_ + delta;
79 int64_t sig_xsq = prev->sig_xsq_ + static_cast<int64_t>(delta) * delta;
80 int64_t cost = (sig_xsq - sig_x * sig_x / n) / n;
81 cost += prev->total_cost_;
82 UpdateIfBetter(cost, prev->total_steps_ + 1, prev, n, sig_x, sig_xsq);
83 return cost;
84 }
85
86 // Update the other members if the cost is lower.
87 void DPPoint::UpdateIfBetter(int64_t cost, int32_t steps, const DPPoint *prev, int32_t n,
88 int32_t sig_x, int64_t sig_xsq) {
89 if (cost < total_cost_) {
90 total_cost_ = cost;
91 total_steps_ = steps;
92 best_prev_ = prev;
93 n_ = n;
94 sig_x_ = sig_x;
95 sig_xsq_ = sig_xsq;
96 }
97 }
98
99 } // namespace tesseract.