tesseract 4.1.1
Loading...
Searching...
No Matches
detlinefit.h
Go to the documentation of this file.
1
2// File: detlinefit.h
3// Description: Deterministic least upper-quartile squares line fitting.
4// Author: Ray Smith
5// Created: Thu Feb 28 14:35:01 PDT 2008
6//
7// (C) Copyright 2008, 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//
19
20#ifndef TESSERACT_CCSTRUCT_DETLINEFIT_H_
21#define TESSERACT_CCSTRUCT_DETLINEFIT_H_
22
23#include "genericvector.h"
24#include "kdpair.h"
25#include "points.h"
26
27namespace tesseract {
28
29// This class fits a line to a set of ICOORD points.
30// There is no restriction on the direction of the line, as it
31// uses a vector method, ie no concern over infinite gradients.
32// The fitted line has the least upper quartile of squares of perpendicular
33// distances of all source points from the line, subject to the constraint
34// that the line is made from one of the pairs of [{p1,p2,p3},{pn-2, pn-1, pn}]
35// i.e. the 9 combinations of one of the first 3 and last 3 points.
36// A fundamental assumption of this algorithm is that one of the first 3 and
37// one of the last 3 points are near the best line fit.
38// The points must be Added in line order for the algorithm to work properly.
39// No floating point calculations are needed* to make an accurate fit,
40// and no random numbers are needed** so the algorithm is deterministic,
41// architecture-stable, and compiler-stable as well as stable to minor
42// changes in the input.
43// *A single floating point division is used to compute each line's distance.
44// This is unlikely to result in choice of a different line, but if it does,
45// it would be easy to replace with a 64 bit integer calculation.
46// **Random numbers are used in the nth_item function, but the worst
47// non-determinism that can result is picking a different result among equals,
48// and that wouldn't make any difference to the end-result distance, so the
49// randomness does not affect the determinism of the algorithm. The random
50// numbers are only there to guarantee average linear time.
51// Fitting time is linear, but with a high constant, as it tries 9 different
52// lines and computes the distance of all points each time.
53// This class is aimed at replacing the LLSQ (linear least squares) and
54// LMS (least median of squares) classes that are currently used for most
55// of the line fitting in Tesseract.
57 public:
58 DetLineFit();
59 ~DetLineFit() = default;
60
61 // Delete all Added points.
62 void Clear();
63
64 // Adds a new point. Takes a copy - the pt doesn't need to stay in scope.
65 // Add must be called on points in sequence along the line.
66 void Add(const ICOORD& pt);
67 // Associates a half-width with the given point if a point overlaps the
68 // previous point by more than half the width, and its distance is further
69 // than the previous point, then the more distant point is ignored in the
70 // distance calculation. Useful for ignoring i dots and other diacritics.
71 void Add(const ICOORD& pt, int halfwidth);
72
73 // Fits a line to the points, returning the fitted line as a pair of
74 // points, and the upper quartile error.
75 double Fit(ICOORD* pt1, ICOORD* pt2) {
76 return Fit(0, 0, pt1, pt2);
77 }
78 // Fits a line to the points, ignoring the skip_first initial points and the
79 // skip_last final points, returning the fitted line as a pair of points,
80 // and the upper quartile error.
81 double Fit(int skip_first, int skip_last, ICOORD* pt1, ICOORD* pt2);
82
83 // Constrained fit with a supplied direction vector. Finds the best line_pt,
84 // that is one of the supplied points having the median cross product with
85 // direction, ignoring points that have a cross product outside of the range
86 // [min_dist, max_dist]. Returns the resulting error metric using the same
87 // reduced set of points.
88 // *Makes use of floating point arithmetic*
89 double ConstrainedFit(const FCOORD& direction,
90 double min_dist, double max_dist,
91 bool debug, ICOORD* line_pt);
92
93 // Returns true if there were enough points at the last call to Fit or
94 // ConstrainedFit for the fitted points to be used on a badly fitted line.
96
97 // Backwards compatible fit returning a gradient and constant.
98 // Deprecated. Prefer Fit(ICOORD*, ICOORD*) where possible, but use this
99 // function in preference to the LMS class.
100 double Fit(float* m, float* c);
101
102 // Backwards compatible constrained fit with a supplied gradient.
103 // Deprecated. Use ConstrainedFit(const FCOORD& direction) where possible
104 // to avoid potential difficulties with infinite gradients.
105 double ConstrainedFit(double m, float* c);
106
107 private:
108 // Simple struct to hold an ICOORD point and a halfwidth representing half
109 // the "width" (supposedly approximately parallel to the direction of the
110 // line) of each point, such that distant points can be discarded when they
111 // overlap nearer points. (Think i dot and other diacritics or noise.)
112 struct PointWidth {
113 PointWidth() : pt(ICOORD(0, 0)), halfwidth(0) {}
114 PointWidth(const ICOORD& pt0, int halfwidth0)
115 : pt(pt0), halfwidth(halfwidth0) {}
116
117 ICOORD pt;
118 int halfwidth;
119 };
120 // Type holds the distance of each point from the fitted line and the point
121 // itself. Use of double allows integer distances from ICOORDs to be stored
122 // exactly, and also the floating point results from ConstrainedFit.
123 using DistPointPair = KDPairInc<double, ICOORD>;
124
125 // Computes and returns the squared evaluation metric for a line fit.
126 double EvaluateLineFit();
127
128 // Computes the absolute values of the precomputed distances_,
129 // and returns the squared upper-quartile error distance.
130 double ComputeUpperQuartileError();
131
132 // Returns the number of sample points that have an error more than threshold.
133 int NumberOfMisfittedPoints(double threshold) const;
134
135 // Computes all the cross product distances of the points from the line,
136 // storing the actual (signed) cross products in distances_.
137 // Ignores distances of points that are further away than the previous point,
138 // and overlaps the previous point by at least half.
139 void ComputeDistances(const ICOORD& start, const ICOORD& end);
140
141 // Computes all the cross product distances of the points perpendicular to
142 // the given direction, ignoring distances outside of the give distance range,
143 // storing the actual (signed) cross products in distances_.
144 void ComputeConstrainedDistances(const FCOORD& direction,
145 double min_dist, double max_dist);
146
147 // Stores all the source points in the order they were given and their
148 // halfwidths, if any.
150 // Stores the computed perpendicular distances of (some of) the pts_ from a
151 // given vector (assuming it goes through the origin, making it a line).
152 // Since the distances may be a subset of the input points, and get
153 // re-ordered by the nth_item function, the original point is stored
154 // along side the distance.
155 GenericVector<DistPointPair> distances_; // Distances of points.
156 // The squared length of the vector used to compute distances_.
157 double square_length_;
158};
159
160} // namespace tesseract.
161
162#endif // TESSERACT_CCSTRUCT_DETLINEFIT_H_
void Add(const ICOORD &pt)
Definition: detlinefit.cpp:51
double ConstrainedFit(const FCOORD &direction, double min_dist, double max_dist, bool debug, ICOORD *line_pt)
Definition: detlinefit.cpp:130
double Fit(ICOORD *pt1, ICOORD *pt2)
Definition: detlinefit.h:75
bool SufficientPointsForIndependentFit() const
Definition: detlinefit.cpp:162
integer coordinate
Definition: points.h:32
Definition: points.h:189