Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/classify/intfx.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 ** Filename: intfx.c
3 ** Purpose: Integer character normalization & feature extraction
4 ** Author: Robert Moss, rays@google.com (Ray Smith)
5 **
6 ** (c) Copyright Hewlett-Packard Company, 1988.
7 ** Licensed under the Apache License, Version 2.0 (the "License");
8 ** you may not use this file except in compliance with the License.
9 ** You may obtain a copy of the License at
10 ** http://www.apache.org/licenses/LICENSE-2.0
11 ** Unless required by applicable law or agreed to in writing, software
12 ** distributed under the License is distributed on an "AS IS" BASIS,
13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 ** See the License for the specific language governing permissions and
15 ** limitations under the License.
16 *****************************************************************************/
17 /**----------------------------------------------------------------------------
18 Include Files and Type Defines
19 ----------------------------------------------------------------------------**/
20
21 #define _USE_MATH_DEFINES // for M_PI
22
23 #include "intfx.h"
24
25 #include "classify.h"
26 #include "intmatcher.h"
27 #include "linlsq.h"
28 #include "normalis.h"
29 #include "statistc.h"
30 #include "trainingsample.h"
31
32 #include "helpers.h"
33
34 #include <allheaders.h>
35
36 #include <cmath> // for M_PI
37 #include <mutex> // for std::mutex
38
39 namespace tesseract {
40
41 /**----------------------------------------------------------------------------
42 Global Data Definitions and Declarations
43 ----------------------------------------------------------------------------**/
44 // Look up table for cos and sin to turn the intfx feature angle to a vector.
45 // Protected by atan_table_mutex.
46 // The entries are in binary degrees where a full circle is 256 binary degrees.
47 static float cos_table[INT_CHAR_NORM_RANGE];
48 static float sin_table[INT_CHAR_NORM_RANGE];
49
50 /**----------------------------------------------------------------------------
51 Public Code
52 ----------------------------------------------------------------------------**/
53
54 void InitIntegerFX() {
55 // Guards write access to AtanTable so we don't create it more than once.
56 static std::mutex atan_table_mutex;
57 static bool atan_table_init = false;
58 std::lock_guard<std::mutex> guard(atan_table_mutex);
59 if (!atan_table_init) {
60 for (int i = 0; i < INT_CHAR_NORM_RANGE; ++i) {
61 cos_table[i] = cos(i * 2 * M_PI / INT_CHAR_NORM_RANGE + M_PI);
62 sin_table[i] = sin(i * 2 * M_PI / INT_CHAR_NORM_RANGE + M_PI);
63 }
64 atan_table_init = true;
65 }
66 }
67
68 // Returns a vector representing the direction of a feature with the given
69 // theta direction in an INT_FEATURE_STRUCT.
70 FCOORD FeatureDirection(uint8_t theta) {
71 return FCOORD(cos_table[theta], sin_table[theta]);
72 }
73
74 // Generates a TrainingSample from a TBLOB. Extracts features and sets
75 // the bounding box, so classifiers that operate on the image can work.
76 // TODO(rays) Make BlobToTrainingSample a member of Classify now that
77 // the FlexFx and FeatureDescription code have been removed and LearnBlob
78 // is now a member of Classify.
79 TrainingSample *BlobToTrainingSample(const TBLOB &blob, bool nonlinear_norm,
80 INT_FX_RESULT_STRUCT *fx_info,
81 std::vector<INT_FEATURE_STRUCT> *bl_features) {
82 std::vector<INT_FEATURE_STRUCT> cn_features;
83 Classify::ExtractFeatures(blob, nonlinear_norm, bl_features, &cn_features, fx_info, nullptr);
84 // TODO(rays) Use blob->PreciseBoundingBox() instead.
85 TBOX box = blob.bounding_box();
86 TrainingSample *sample = nullptr;
87 int num_features = fx_info->NumCN;
88 if (num_features > 0) {
89 sample = TrainingSample::CopyFromFeatures(*fx_info, box, &cn_features[0], num_features);
90 }
91 if (sample != nullptr) {
92 // Set the bounding box (in original image coordinates) in the sample.
93 TPOINT topleft, botright;
94 topleft.x = box.left();
95 topleft.y = box.top();
96 botright.x = box.right();
97 botright.y = box.bottom();
98 TPOINT original_topleft, original_botright;
99 blob.denorm().DenormTransform(nullptr, topleft, &original_topleft);
100 blob.denorm().DenormTransform(nullptr, botright, &original_botright);
101 sample->set_bounding_box(
102 TBOX(original_topleft.x, original_botright.y, original_botright.x, original_topleft.y));
103 }
104 return sample;
105 }
106
107 // Computes the DENORMS for bl(baseline) and cn(character) normalization
108 // during feature extraction. The input denorm describes the current state
109 // of the blob, which is usually a baseline-normalized word.
110 // The Transforms setup are as follows:
111 // Baseline Normalized (bl) Output:
112 // We center the grapheme by aligning the x-coordinate of its centroid with
113 // x=128 and leaving the already-baseline-normalized y as-is.
114 //
115 // Character Normalized (cn) Output:
116 // We align the grapheme's centroid at the origin and scale it
117 // asymmetrically in x and y so that the 2nd moments are a standard value
118 // (51.2) ie the result is vaguely square.
119 // If classify_nonlinear_norm is true:
120 // A non-linear normalization is setup that attempts to evenly distribute
121 // edges across x and y.
122 //
123 // Some of the fields of fx_info are also setup:
124 // Length: Total length of outline.
125 // Rx: Rounded y second moment. (Reversed by convention.)
126 // Ry: rounded x second moment.
127 // Xmean: Rounded x center of mass of the blob.
128 // Ymean: Rounded y center of mass of the blob.
129 void Classify::SetupBLCNDenorms(const TBLOB &blob, bool nonlinear_norm, DENORM *bl_denorm,
130 DENORM *cn_denorm, INT_FX_RESULT_STRUCT *fx_info) {
131 // Compute 1st and 2nd moments of the original outline.
132 FCOORD center, second_moments;
133 int length = blob.ComputeMoments(&center, &second_moments);
134 if (fx_info != nullptr) {
135 fx_info->Length = length;
136 fx_info->Rx = IntCastRounded(second_moments.y());
137 fx_info->Ry = IntCastRounded(second_moments.x());
138
139 fx_info->Xmean = IntCastRounded(center.x());
140 fx_info->Ymean = IntCastRounded(center.y());
141 }
142 // Setup the denorm for Baseline normalization.
143 bl_denorm->SetupNormalization(nullptr, nullptr, &blob.denorm(), center.x(), 128.0f, 1.0f, 1.0f,
144 128.0f, 128.0f);
145 // Setup the denorm for character normalization.
146 if (nonlinear_norm) {
147 std::vector<std::vector<int>> x_coords;
148 std::vector<std::vector<int>> y_coords;
149 TBOX box;
150 blob.GetPreciseBoundingBox(&box);
151 box.pad(1, 1);
152 blob.GetEdgeCoords(box, x_coords, y_coords);
153 cn_denorm->SetupNonLinear(&blob.denorm(), box, UINT8_MAX, UINT8_MAX, 0.0f, 0.0f, x_coords,
154 y_coords);
155 } else {
156 cn_denorm->SetupNormalization(nullptr, nullptr, &blob.denorm(), center.x(), center.y(),
157 51.2f / second_moments.x(), 51.2f / second_moments.y(), 128.0f,
158 128.0f);
159 }
160 }
161
162 // Helper normalizes the direction, assuming that it is at the given
163 // unnormed_pos, using the given denorm, starting at the root_denorm.
164 static uint8_t NormalizeDirection(uint8_t dir, const FCOORD &unnormed_pos, const DENORM &denorm,
165 const DENORM *root_denorm) {
166 // Convert direction to a vector.
167 FCOORD unnormed_end;
168 unnormed_end.from_direction(dir);
169 unnormed_end += unnormed_pos;
170 FCOORD normed_pos, normed_end;
171 denorm.NormTransform(root_denorm, unnormed_pos, &normed_pos);
172 denorm.NormTransform(root_denorm, unnormed_end, &normed_end);
173 normed_end -= normed_pos;
174 return normed_end.to_direction();
175 }
176
177 // Helper returns the mean direction vector from the given stats. Use the
178 // mean direction from dirs if there is information available, otherwise, use
179 // the fit_vector from point_diffs.
180 static FCOORD MeanDirectionVector(const LLSQ &point_diffs, const LLSQ &dirs, const FCOORD &start_pt,
181 const FCOORD &end_pt) {
182 FCOORD fit_vector;
183 if (dirs.count() > 0) {
184 // There were directions, so use them. To avoid wrap-around problems, we
185 // have 2 accumulators in dirs: x for normal directions and y for
186 // directions offset by 128. We will use the one with the least variance.
187 FCOORD mean_pt = dirs.mean_point();
188 double mean_dir = 0.0;
189 if (dirs.x_variance() <= dirs.y_variance()) {
190 mean_dir = mean_pt.x();
191 } else {
192 mean_dir = mean_pt.y() + 128;
193 }
194 fit_vector.from_direction(Modulo(IntCastRounded(mean_dir), 256));
195 } else {
196 // There were no directions, so we rely on the vector_fit to the points.
197 // Since the vector_fit is 180 degrees ambiguous, we align with the
198 // supplied feature_dir by making the scalar product non-negative.
199 FCOORD feature_dir(end_pt - start_pt);
200 fit_vector = point_diffs.vector_fit();
201 if (fit_vector.x() == 0.0f && fit_vector.y() == 0.0f) {
202 // There was only a single point. Use feature_dir directly.
203 fit_vector = feature_dir;
204 } else {
205 // Sometimes the least mean squares fit is wrong, due to the small sample
206 // of points and scaling. Use a 90 degree rotated vector if that matches
207 // feature_dir better.
208 FCOORD fit_vector2 = !fit_vector;
209 // The fit_vector is 180 degrees ambiguous, so resolve the ambiguity by
210 // insisting that the scalar product with the feature_dir should be +ve.
211 if (fit_vector % feature_dir < 0.0) {
212 fit_vector = -fit_vector;
213 }
214 if (fit_vector2 % feature_dir < 0.0) {
215 fit_vector2 = -fit_vector2;
216 }
217 // Even though fit_vector2 has a higher mean squared error, it might be
218 // a better fit, so use it if the dot product with feature_dir is bigger.
219 if (fit_vector2 % feature_dir > fit_vector % feature_dir) {
220 fit_vector = fit_vector2;
221 }
222 }
223 }
224 return fit_vector;
225 }
226
227 // Helper computes one or more features corresponding to the given points.
228 // Emitted features are on the line defined by:
229 // start_pt + lambda * (end_pt - start_pt) for scalar lambda.
230 // Features are spaced at feature_length intervals.
231 static int ComputeFeatures(const FCOORD &start_pt, const FCOORD &end_pt, double feature_length,
232 std::vector<INT_FEATURE_STRUCT> *features) {
233 FCOORD feature_vector(end_pt - start_pt);
234 if (feature_vector.x() == 0.0f && feature_vector.y() == 0.0f) {
235 return 0;
236 }
237 // Compute theta for the feature based on its direction.
238 uint8_t theta = feature_vector.to_direction();
239 // Compute the number of features and lambda_step.
240 double target_length = feature_vector.length();
241 int num_features = IntCastRounded(target_length / feature_length);
242 if (num_features == 0) {
243 return 0;
244 }
245 // Divide the length evenly into num_features pieces.
246 double lambda_step = 1.0 / num_features;
247 double lambda = lambda_step / 2.0;
248 for (int f = 0; f < num_features; ++f, lambda += lambda_step) {
249 FCOORD feature_pt(start_pt);
250 feature_pt += feature_vector * lambda;
251 INT_FEATURE_STRUCT feature(feature_pt, theta);
252 features->push_back(feature);
253 }
254 return num_features;
255 }
256
257 // Gathers outline points and their directions from start_index into dirs by
258 // stepping along the outline and normalizing the coordinates until the
259 // required feature_length has been collected or end_index is reached.
260 // On input pos must point to the position corresponding to start_index and on
261 // return pos is updated to the current raw position, and pos_normed is set to
262 // the normed version of pos.
263 // Since directions wrap-around, they need special treatment to get the mean.
264 // Provided the cluster of directions doesn't straddle the wrap-around point,
265 // the simple mean works. If they do, then, unless the directions are wildly
266 // varying, the cluster rotated by 180 degrees will not straddle the wrap-
267 // around point, so mean(dir + 180 degrees) - 180 degrees will work. Since
268 // LLSQ conveniently stores the mean of 2 variables, we use it to store
269 // dir and dir+128 (128 is 180 degrees) and then use the resulting mean
270 // with the least variance.
271 static int GatherPoints(const C_OUTLINE *outline, double feature_length, const DENORM &denorm,
272 const DENORM *root_denorm, int start_index, int end_index, ICOORD *pos,
273 FCOORD *pos_normed, LLSQ *points, LLSQ *dirs) {
274 int step_length = outline->pathlength();
275 ICOORD step = outline->step(start_index % step_length);
276 // Prev_normed is the start point of this collection and will be set on the
277 // first iteration, and on later iterations used to determine the length
278 // that has been collected.
279 FCOORD prev_normed;
280 points->clear();
281 dirs->clear();
282 int num_points = 0;
283 int index;
284 for (index = start_index; index <= end_index; ++index, *pos += step) {
285 step = outline->step(index % step_length);
286 int edge_weight = outline->edge_strength_at_index(index % step_length);
287 if (edge_weight == 0) {
288 // This point has conflicting gradient and step direction, so ignore it.
289 continue;
290 }
291 // Get the sub-pixel precise location and normalize.
292 FCOORD f_pos = outline->sub_pixel_pos_at_index(*pos, index % step_length);
293 denorm.NormTransform(root_denorm, f_pos, pos_normed);
294 if (num_points == 0) {
295 // The start of this segment.
296 prev_normed = *pos_normed;
297 } else {
298 FCOORD offset = *pos_normed - prev_normed;
299 float length = offset.length();
300 if (length > feature_length) {
301 // We have gone far enough from the start. We will use this point in
302 // the next set so return what we have so far.
303 return index;
304 }
305 }
306 points->add(pos_normed->x(), pos_normed->y(), edge_weight);
307 int direction = outline->direction_at_index(index % step_length);
308 if (direction >= 0) {
309 direction = NormalizeDirection(direction, f_pos, denorm, root_denorm);
310 // Use both the direction and direction +128 so we are not trying to
311 // take the mean of something straddling the wrap-around point.
312 dirs->add(direction, Modulo(direction + 128, 256));
313 }
314 ++num_points;
315 }
316 return index;
317 }
318
319 // Extracts Tesseract features and appends them to the features vector.
320 // Startpt to lastpt, inclusive, MUST have the same src_outline member,
321 // which may be nullptr. The vector from lastpt to its next is included in
322 // the feature extraction. Hidden edges should be excluded by the caller.
323 // If force_poly is true, the features will be extracted from the polygonal
324 // approximation even if more accurate data is available.
325 static void ExtractFeaturesFromRun(const EDGEPT *startpt, const EDGEPT *lastpt,
326 const DENORM &denorm, double feature_length, bool force_poly,
327 std::vector<INT_FEATURE_STRUCT> *features) {
328 const EDGEPT *endpt = lastpt->next;
329 const C_OUTLINE *outline = startpt->src_outline;
330 if (outline != nullptr && !force_poly) {
331 // Detailed information is available. We have to normalize only from
332 // the root_denorm to denorm.
333 const DENORM *root_denorm = denorm.RootDenorm();
334 int total_features = 0;
335 // Get the features from the outline.
336 int step_length = outline->pathlength();
337 int start_index = startpt->start_step;
338 // pos is the integer coordinates of the binary image steps.
339 ICOORD pos = outline->position_at_index(start_index);
340 // We use an end_index that allows us to use a positive increment, but that
341 // may be beyond the bounds of the outline steps/ due to wrap-around, to
342 // so we use % step_length everywhere, except for start_index.
343 int end_index = lastpt->start_step + lastpt->step_count;
344 if (end_index <= start_index) {
345 end_index += step_length;
346 }
347 LLSQ prev_points;
348 LLSQ prev_dirs;
349 FCOORD prev_normed_pos = outline->sub_pixel_pos_at_index(pos, start_index);
350 denorm.NormTransform(root_denorm, prev_normed_pos, &prev_normed_pos);
351 LLSQ points;
352 LLSQ dirs;
353 FCOORD normed_pos(0.0f, 0.0f);
354 int index = GatherPoints(outline, feature_length, denorm, root_denorm, start_index, end_index,
355 &pos, &normed_pos, &points, &dirs);
356 while (index <= end_index) {
357 // At each iteration we nominally have 3 accumulated sets of points and
358 // dirs: prev_points/dirs, points/dirs, next_points/dirs and sum them
359 // into sum_points/dirs, but we don't necessarily get any features out,
360 // so if that is the case, we keep accumulating instead of rotating the
361 // accumulators.
362 LLSQ next_points;
363 LLSQ next_dirs;
364 FCOORD next_normed_pos(0.0f, 0.0f);
365 index = GatherPoints(outline, feature_length, denorm, root_denorm, index, end_index, &pos,
366 &next_normed_pos, &next_points, &next_dirs);
367 LLSQ sum_points(prev_points);
368 // TODO(rays) find out why it is better to use just dirs and next_dirs
369 // in sum_dirs, instead of using prev_dirs as well.
370 LLSQ sum_dirs(dirs);
371 sum_points.add(points);
372 sum_points.add(next_points);
373 sum_dirs.add(next_dirs);
374 bool made_features = false;
375 // If we have some points, we can try making some features.
376 if (sum_points.count() > 0) {
377 // We have gone far enough from the start. Make a feature and restart.
378 FCOORD fit_pt = sum_points.mean_point();
379 FCOORD fit_vector = MeanDirectionVector(sum_points, sum_dirs, prev_normed_pos, normed_pos);
380 // The segment to which we fit features is the line passing through
381 // fit_pt in direction of fit_vector that starts nearest to
382 // prev_normed_pos and ends nearest to normed_pos.
383 FCOORD start_pos = prev_normed_pos.nearest_pt_on_line(fit_pt, fit_vector);
384 FCOORD end_pos = normed_pos.nearest_pt_on_line(fit_pt, fit_vector);
385 // Possible correction to match the adjacent polygon segment.
386 if (total_features == 0 && startpt != endpt) {
387 FCOORD poly_pos(startpt->pos.x, startpt->pos.y);
388 denorm.LocalNormTransform(poly_pos, &start_pos);
389 }
390 if (index > end_index && startpt != endpt) {
391 FCOORD poly_pos(endpt->pos.x, endpt->pos.y);
392 denorm.LocalNormTransform(poly_pos, &end_pos);
393 }
394 int num_features = ComputeFeatures(start_pos, end_pos, feature_length, features);
395 if (num_features > 0) {
396 // We made some features so shuffle the accumulators.
397 prev_points = points;
398 prev_dirs = dirs;
399 prev_normed_pos = normed_pos;
400 points = next_points;
401 dirs = next_dirs;
402 made_features = true;
403 total_features += num_features;
404 }
405 // The end of the next set becomes the end next time around.
406 normed_pos = next_normed_pos;
407 }
408 if (!made_features) {
409 // We didn't make any features, so keep the prev accumulators and
410 // add the next ones into the current.
411 points.add(next_points);
412 dirs.add(next_dirs);
413 }
414 }
415 } else {
416 // There is no outline, so we are forced to use the polygonal approximation.
417 const EDGEPT *pt = startpt;
418 do {
419 FCOORD start_pos(pt->pos.x, pt->pos.y);
420 FCOORD end_pos(pt->next->pos.x, pt->next->pos.y);
421 denorm.LocalNormTransform(start_pos, &start_pos);
422 denorm.LocalNormTransform(end_pos, &end_pos);
423 ComputeFeatures(start_pos, end_pos, feature_length, features);
424 } while ((pt = pt->next) != endpt);
425 }
426 }
427
428 // Extracts sets of 3-D features of length kStandardFeatureLength (=12.8), as
429 // (x,y) position and angle as measured counterclockwise from the vector
430 // <-1, 0>, from blob using two normalizations defined by bl_denorm and
431 // cn_denorm. See SetpuBLCNDenorms for definitions.
432 // If outline_cn_counts is not nullptr, on return it contains the cumulative
433 // number of cn features generated for each outline in the blob (in order).
434 // Thus after the first outline, there were (*outline_cn_counts)[0] features,
435 // after the second outline, there were (*outline_cn_counts)[1] features etc.
436 void Classify::ExtractFeatures(const TBLOB &blob, bool nonlinear_norm,
437 std::vector<INT_FEATURE_STRUCT> *bl_features,
438 std::vector<INT_FEATURE_STRUCT> *cn_features,
439 INT_FX_RESULT_STRUCT *results,
440 std::vector<int> *outline_cn_counts) {
441 DENORM bl_denorm, cn_denorm;
442 tesseract::Classify::SetupBLCNDenorms(blob, nonlinear_norm, &bl_denorm, &cn_denorm, results);
443 if (outline_cn_counts != nullptr) {
444 outline_cn_counts->clear();
445 }
446 // Iterate the outlines.
447 for (TESSLINE *ol = blob.outlines; ol != nullptr; ol = ol->next) {
448 // Iterate the polygon.
449 EDGEPT *loop_pt = ol->FindBestStartPt();
450 EDGEPT *pt = loop_pt;
451 if (pt == nullptr) {
452 continue;
453 }
454 do {
455 if (pt->IsHidden()) {
456 continue;
457 }
458 // Find a run of equal src_outline.
459 EDGEPT *last_pt = pt;
460 do {
461 last_pt = last_pt->next;
462 } while (last_pt != loop_pt && !last_pt->IsHidden() &&
463 last_pt->src_outline == pt->src_outline);
464 last_pt = last_pt->prev;
465 // Until the adaptive classifier can be weaned off polygon segments,
466 // we have to force extraction from the polygon for the bl_features.
467 ExtractFeaturesFromRun(pt, last_pt, bl_denorm, kStandardFeatureLength, true, bl_features);
468 ExtractFeaturesFromRun(pt, last_pt, cn_denorm, kStandardFeatureLength, false, cn_features);
469 pt = last_pt;
470 } while ((pt = pt->next) != loop_pt);
471 if (outline_cn_counts != nullptr) {
472 outline_cn_counts->push_back(cn_features->size());
473 }
474 }
475 results->NumBL = bl_features->size();
476 results->NumCN = cn_features->size();
477 results->YBottom = blob.bounding_box().bottom();
478 results->YTop = blob.bounding_box().top();
479 results->Width = blob.bounding_box().width();
480 }
481
482 } // namespace tesseract