tesseract 4.1.1
Loading...
Searching...
No Matches
linefind.cpp
Go to the documentation of this file.
1
2// File: linefind.cpp
3// Description: Class to find vertical lines in an image and create
4// a corresponding list of empty blobs.
5// Author: Ray Smith
6// Created: Thu Mar 20 09:49:01 PDT 2008
7//
8// (C) Copyright 2008, Google Inc.
9// Licensed under the Apache License, Version 2.0 (the "License");
10// you may not use this file except in compliance with the License.
11// You may obtain a copy of the License at
12// http://www.apache.org/licenses/LICENSE-2.0
13// Unless required by applicable law or agreed to in writing, software
14// distributed under the License is distributed on an "AS IS" BASIS,
15// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16// See the License for the specific language governing permissions and
17// limitations under the License.
18//
20
21#ifdef HAVE_CONFIG_H
22#include "config_auto.h"
23#endif
24
25#include "linefind.h"
26#include "alignedblob.h"
27#include "tabvector.h"
28#include "blobbox.h"
29#include "edgblob.h"
30#if defined(USE_OPENCL)
31#include "openclwrapper.h" // for OpenclDevice
32#endif
33
34#include "allheaders.h"
35
36#include <algorithm>
37
38namespace tesseract {
39
41const int kThinLineFraction = 20;
45const int kCrackSpacing = 100;
47const int kLineFindGridSize = 50;
48// Min width of a line in pixels to be considered thick.
49const int kMinThickLineWidth = 12;
50// Max size of line residue. (The pixels that fail the long thin opening, and
51// therefore don't make it to the candidate line mask, but are nevertheless
52// part of the line.)
53const int kMaxLineResidue = 6;
54// Min length in inches of a line segment that exceeds kMinThickLineWidth in
55// thickness. (Such lines shouldn't break by simple image degradation.)
56const double kThickLengthMultiple = 0.75;
57// Max fraction of line box area that can be occupied by non-line pixels.
58const double kMaxNonLineDensity = 0.25;
59// Max height of a music stave in inches.
60const double kMaxStaveHeight = 1.0;
61// Minimum fraction of pixels in a music rectangle connected to the staves.
62const double kMinMusicPixelFraction = 0.75;
63
64// Erases the unused blobs from the line_pix image, taking into account
65// whether this was a horizontal or vertical line set.
66static void RemoveUnusedLineSegments(bool horizontal_lines,
67 BLOBNBOX_LIST* line_bblobs,
68 Pix* line_pix) {
69 int height = pixGetHeight(line_pix);
70 BLOBNBOX_IT bbox_it(line_bblobs);
71 for (bbox_it.mark_cycle_pt(); !bbox_it.cycled_list(); bbox_it.forward()) {
72 BLOBNBOX* blob = bbox_it.data();
73 if (blob->left_tab_type() != TT_VLINE) {
74 const TBOX& box = blob->bounding_box();
75 Box* pixbox = nullptr;
76 if (horizontal_lines) {
77 // Horizontal lines are in tess format and also have x and y flipped
78 // (to use FindVerticalAlignment) so we have to flip x and y and then
79 // convert to Leptonica by height - flipped x (ie the right edge).
80 // See GetLineBoxes for more explanation.
81 pixbox = boxCreate(box.bottom(), height - box.right(),
82 box.height(), box.width());
83 } else {
84 // For vertical lines, just flip upside-down to convert to Leptonica.
85 // The y position of the box in Leptonica terms is the distance from
86 // the top of the image to the top of the box.
87 pixbox = boxCreate(box.left(), height - box.top(),
88 box.width(), box.height());
89 }
90 pixClearInRect(line_pix, pixbox);
91 boxDestroy(&pixbox);
92 }
93 }
94}
95
96// Helper subtracts the line_pix image from the src_pix, and removes residue
97// as well by removing components that touch the line, but are not in the
98// non_line_pix mask. It is assumed that the non_line_pix mask has already
99// been prepared to required accuracy.
100static void SubtractLinesAndResidue(Pix* line_pix, Pix* non_line_pix,
101 int resolution, Pix* src_pix) {
102 // First remove the lines themselves.
103 pixSubtract(src_pix, src_pix, line_pix);
104 // Subtract the non-lines from the image to get the residue.
105 Pix* residue_pix = pixSubtract(nullptr, src_pix, non_line_pix);
106 // Dilate the lines so they touch the residue.
107 Pix* fat_line_pix = pixDilateBrick(nullptr, line_pix, 3, 3);
108 // Seed fill the fat lines to get all the residue.
109 pixSeedfillBinary(fat_line_pix, fat_line_pix, residue_pix, 8);
110 // Subtract the residue from the original image.
111 pixSubtract(src_pix, src_pix, fat_line_pix);
112 pixDestroy(&fat_line_pix);
113 pixDestroy(&residue_pix);
114}
115
116// Returns the maximum strokewidth in the given binary image by doubling
117// the maximum of the distance function.
118static int MaxStrokeWidth(Pix* pix) {
119 Pix* dist_pix = pixDistanceFunction(pix, 4, 8, L_BOUNDARY_BG);
120 int width = pixGetWidth(dist_pix);
121 int height = pixGetHeight(dist_pix);
122 int wpl = pixGetWpl(dist_pix);
123 l_uint32* data = pixGetData(dist_pix);
124 // Find the maximum value in the distance image.
125 int max_dist = 0;
126 for (int y = 0; y < height; ++y) {
127 for (int x = 0; x < width; ++x) {
128 int pixel = GET_DATA_BYTE(data, x);
129 if (pixel > max_dist)
130 max_dist = pixel;
131 }
132 data += wpl;
133 }
134 pixDestroy(&dist_pix);
135 return max_dist * 2;
136}
137
138// Returns the number of components in the intersection_pix touched by line_box.
139static int NumTouchingIntersections(Box* line_box, Pix* intersection_pix) {
140 if (intersection_pix == nullptr) return 0;
141 Pix* rect_pix = pixClipRectangle(intersection_pix, line_box, nullptr);
142 Boxa* boxa = pixConnComp(rect_pix, nullptr, 8);
143 pixDestroy(&rect_pix);
144 if (boxa == nullptr) return false;
145 int result = boxaGetCount(boxa);
146 boxaDestroy(&boxa);
147 return result;
148}
149
150// Returns the number of black pixels found in the box made by adding the line
151// width to both sides of the line bounding box. (Increasing the smallest
152// dimension of the bounding box.)
153static int CountPixelsAdjacentToLine(int line_width, Box* line_box,
154 Pix* nonline_pix) {
155 l_int32 x, y, box_width, box_height;
156 boxGetGeometry(line_box, &x, &y, &box_width, &box_height);
157 if (box_width > box_height) {
158 // horizontal line.
159 int bottom = std::min(pixGetHeight(nonline_pix), y + box_height + line_width);
160 y = std::max(0, y - line_width);
161 box_height = bottom - y;
162 } else {
163 // Vertical line.
164 int right = std::min(pixGetWidth(nonline_pix), x + box_width + line_width);
165 x = std::max(0, x - line_width);
166 box_width = right - x;
167 }
168 Box* box = boxCreate(x, y, box_width, box_height);
169 Pix* rect_pix = pixClipRectangle(nonline_pix, box, nullptr);
170 boxDestroy(&box);
171 l_int32 result;
172 pixCountPixels(rect_pix, &result, nullptr);
173 pixDestroy(&rect_pix);
174 return result;
175}
176
177// Helper erases false-positive line segments from the input/output line_pix.
178// 1. Since thick lines shouldn't really break up, we can eliminate some false
179// positives by marking segments that are at least kMinThickLineWidth
180// thickness, yet have a length less than min_thick_length.
181// 2. Lines that don't have at least 2 intersections with other lines and have
182// a lot of neighbouring non-lines are probably not lines (perhaps arabic
183// or Hindi words, or underlines.)
184// Bad line components are erased from line_pix.
185// Returns the number of remaining connected components.
186static int FilterFalsePositives(int resolution, Pix* nonline_pix,
187 Pix* intersection_pix, Pix* line_pix) {
188 int min_thick_length = static_cast<int>(resolution * kThickLengthMultiple);
189 Pixa* pixa = nullptr;
190 Boxa* boxa = pixConnComp(line_pix, &pixa, 8);
191 // Iterate over the boxes to remove false positives.
192 int nboxes = boxaGetCount(boxa);
193 int remaining_boxes = nboxes;
194 for (int i = 0; i < nboxes; ++i) {
195 Box* box = boxaGetBox(boxa, i, L_CLONE);
196 l_int32 x, y, box_width, box_height;
197 boxGetGeometry(box, &x, &y, &box_width, &box_height);
198 Pix* comp_pix = pixaGetPix(pixa, i, L_CLONE);
199 int max_width = MaxStrokeWidth(comp_pix);
200 pixDestroy(&comp_pix);
201 bool bad_line = false;
202 // If the length is too short to stand-alone as a line, and the box width
203 // is thick enough, and the stroke width is thick enough it is bad.
204 if (box_width >= kMinThickLineWidth && box_height >= kMinThickLineWidth &&
205 box_width < min_thick_length && box_height < min_thick_length &&
206 max_width > kMinThickLineWidth) {
207 // Too thick for the length.
208 bad_line = true;
209 }
210 if (!bad_line &&
211 (intersection_pix == nullptr ||
212 NumTouchingIntersections(box, intersection_pix) < 2)) {
213 // Test non-line density near the line.
214 int nonline_count = CountPixelsAdjacentToLine(max_width, box,
215 nonline_pix);
216 if (nonline_count > box_height * box_width * kMaxNonLineDensity)
217 bad_line = true;
218 }
219 if (bad_line) {
220 // Not a good line.
221 pixClearInRect(line_pix, box);
222 --remaining_boxes;
223 }
224 boxDestroy(&box);
225 }
226 pixaDestroy(&pixa);
227 boxaDestroy(&boxa);
228 return remaining_boxes;
229}
230
231// Finds vertical and horizontal line objects in the given pix.
232// Uses the given resolution to determine size thresholds instead of any
233// that may be present in the pix.
234// The output vertical_x and vertical_y contain a sum of the output vectors,
235// thereby giving the mean vertical direction.
236// If pix_music_mask != nullptr, and music is detected, a mask of the staves
237// and anything that is connected (bars, notes etc.) will be returned in
238// pix_music_mask, the mask subtracted from pix, and the lines will not
239// appear in v_lines or h_lines.
240// The output vectors are owned by the list and Frozen (cannot refit) by
241// having no boxes, as there is no need to refit or merge separator lines.
242// The detected lines are removed from the pix.
243void LineFinder::FindAndRemoveLines(int resolution, bool debug, Pix* pix,
244 int* vertical_x, int* vertical_y,
245 Pix** pix_music_mask,
246 TabVector_LIST* v_lines,
247 TabVector_LIST* h_lines) {
248 if (pix == nullptr || vertical_x == nullptr || vertical_y == nullptr) {
249 tprintf("Error in parameters for LineFinder::FindAndRemoveLines\n");
250 return;
251 }
252 Pix* pix_vline = nullptr;
253 Pix* pix_non_vline = nullptr;
254 Pix* pix_hline = nullptr;
255 Pix* pix_non_hline = nullptr;
256 Pix* pix_intersections = nullptr;
257 Pixa* pixa_display = debug ? pixaCreate(0) : nullptr;
258 GetLineMasks(resolution, pix, &pix_vline, &pix_non_vline, &pix_hline,
259 &pix_non_hline, &pix_intersections, pix_music_mask,
260 pixa_display);
261 // Find lines, convert to TabVector_LIST and remove those that are used.
262 FindAndRemoveVLines(resolution, pix_intersections, vertical_x, vertical_y,
263 &pix_vline, pix_non_vline, pix, v_lines);
264 if (pix_hline != nullptr) {
265 // Recompute intersections and re-filter false positive h-lines.
266 if (pix_vline != nullptr)
267 pixAnd(pix_intersections, pix_vline, pix_hline);
268 else
269 pixDestroy(&pix_intersections);
270 if (!FilterFalsePositives(resolution, pix_non_hline, pix_intersections,
271 pix_hline)) {
272 pixDestroy(&pix_hline);
273 }
274 }
275 FindAndRemoveHLines(resolution, pix_intersections, *vertical_x, *vertical_y,
276 &pix_hline, pix_non_hline, pix, h_lines);
277 if (pixa_display != nullptr && pix_vline != nullptr)
278 pixaAddPix(pixa_display, pix_vline, L_CLONE);
279 if (pixa_display != nullptr && pix_hline != nullptr)
280 pixaAddPix(pixa_display, pix_hline, L_CLONE);
281 if (pix_vline != nullptr && pix_hline != nullptr) {
282 // Remove joins (intersections) where lines cross, and the residue.
283 // Recalculate the intersections, since some lines have been deleted.
284 pixAnd(pix_intersections, pix_vline, pix_hline);
285 // Fatten up the intersections and seed-fill to get the intersection
286 // residue.
287 Pix* pix_join_residue = pixDilateBrick(nullptr, pix_intersections, 5, 5);
288 pixSeedfillBinary(pix_join_residue, pix_join_residue, pix, 8);
289 // Now remove the intersection residue.
290 pixSubtract(pix, pix, pix_join_residue);
291 pixDestroy(&pix_join_residue);
292 }
293 // Remove any detected music.
294 if (pix_music_mask != nullptr && *pix_music_mask != nullptr) {
295 if (pixa_display != nullptr)
296 pixaAddPix(pixa_display, *pix_music_mask, L_CLONE);
297 pixSubtract(pix, pix, *pix_music_mask);
298 }
299 if (pixa_display != nullptr)
300 pixaAddPix(pixa_display, pix, L_CLONE);
301
302 pixDestroy(&pix_vline);
303 pixDestroy(&pix_non_vline);
304 pixDestroy(&pix_hline);
305 pixDestroy(&pix_non_hline);
306 pixDestroy(&pix_intersections);
307 if (pixa_display != nullptr) {
308 pixaConvertToPdf(pixa_display, resolution, 1.0f, 0, 0, "LineFinding",
309 "vhlinefinding.pdf");
310 pixaDestroy(&pixa_display);
311 }
312}
313
314// Converts the Boxa array to a list of C_BLOB, getting rid of severely
315// overlapping outlines and those that are children of a bigger one.
316// The output is a list of C_BLOBs that are owned by the list.
317// The C_OUTLINEs in the C_BLOBs contain no outline data - just empty
318// bounding boxes. The Boxa is consumed and destroyed.
319void LineFinder::ConvertBoxaToBlobs(int image_width, int image_height,
320 Boxa** boxes, C_BLOB_LIST* blobs) {
321 C_OUTLINE_LIST outlines;
322 C_OUTLINE_IT ol_it = &outlines;
323 // Iterate the boxes to convert to outlines.
324 int nboxes = boxaGetCount(*boxes);
325 for (int i = 0; i < nboxes; ++i) {
326 l_int32 x, y, width, height;
327 boxaGetBoxGeometry(*boxes, i, &x, &y, &width, &height);
328 // Make a C_OUTLINE from the leptonica box. This is a bit of a hack,
329 // as there is no outline, just a bounding box, but with some very
330 // small changes to coutln.cpp, it works nicely.
331 ICOORD top_left(x, y);
332 ICOORD bot_right(x + width, y + height);
333 CRACKEDGE startpt;
334 startpt.pos = top_left;
335 auto* outline = new C_OUTLINE(&startpt, top_left, bot_right, 0);
336 ol_it.add_after_then_move(outline);
337 }
338 // Use outlines_to_blobs to convert the outlines to blobs and find
339 // overlapping and contained objects. The output list of blobs in the block
340 // has all the bad ones filtered out and deleted.
341 BLOCK block;
342 ICOORD page_tl(0, 0);
343 ICOORD page_br(image_width, image_height);
344 outlines_to_blobs(&block, page_tl, page_br, &outlines);
345 // Transfer the created blobs to the output list.
346 C_BLOB_IT blob_it(blobs);
347 blob_it.add_list_after(block.blob_list());
348 // The boxes aren't needed any more.
349 boxaDestroy(boxes);
350}
351
352// Finds vertical line objects in pix_vline and removes the from src_pix.
353// Uses the given resolution to determine size thresholds instead of any
354// that may be present in the pix.
355// The output vertical_x and vertical_y contain a sum of the output vectors,
356// thereby giving the mean vertical direction.
357// The output vectors are owned by the list and Frozen (cannot refit) by
358// having no boxes, as there is no need to refit or merge separator lines.
359// If no good lines are found, pix_vline is destroyed.
360// None of the input pointers may be nullptr, and if *pix_vline is nullptr then
361// the function does nothing.
362void LineFinder::FindAndRemoveVLines(int resolution,
363 Pix* pix_intersections,
364 int* vertical_x, int* vertical_y,
365 Pix** pix_vline, Pix* pix_non_vline,
366 Pix* src_pix, TabVector_LIST* vectors) {
367 if (pix_vline == nullptr || *pix_vline == nullptr) return;
368 C_BLOB_LIST line_cblobs;
369 BLOBNBOX_LIST line_bblobs;
370 GetLineBoxes(false, *pix_vline, pix_intersections,
371 &line_cblobs, &line_bblobs);
372 int width = pixGetWidth(src_pix);
373 int height = pixGetHeight(src_pix);
374 ICOORD bleft(0, 0);
375 ICOORD tright(width, height);
376 FindLineVectors(bleft, tright, &line_bblobs, vertical_x, vertical_y, vectors);
377 if (!vectors->empty()) {
378 RemoveUnusedLineSegments(false, &line_bblobs, *pix_vline);
379 SubtractLinesAndResidue(*pix_vline, pix_non_vline, resolution, src_pix);
380 ICOORD vertical;
381 vertical.set_with_shrink(*vertical_x, *vertical_y);
382 TabVector::MergeSimilarTabVectors(vertical, vectors, nullptr);
383 } else {
384 pixDestroy(pix_vline);
385 }
386}
387
388// Finds horizontal line objects in pix_hline and removes them from src_pix.
389// Uses the given resolution to determine size thresholds instead of any
390// that may be present in the pix.
391// The output vertical_x and vertical_y contain a sum of the output vectors,
392// thereby giving the mean vertical direction.
393// The output vectors are owned by the list and Frozen (cannot refit) by
394// having no boxes, as there is no need to refit or merge separator lines.
395// If no good lines are found, pix_hline is destroyed.
396// None of the input pointers may be nullptr, and if *pix_hline is nullptr then
397// the function does nothing.
398void LineFinder::FindAndRemoveHLines(int resolution,
399 Pix* pix_intersections,
400 int vertical_x, int vertical_y,
401 Pix** pix_hline, Pix* pix_non_hline,
402 Pix* src_pix, TabVector_LIST* vectors) {
403 if (pix_hline == nullptr || *pix_hline == nullptr) return;
404 C_BLOB_LIST line_cblobs;
405 BLOBNBOX_LIST line_bblobs;
406 GetLineBoxes(true, *pix_hline, pix_intersections, &line_cblobs, &line_bblobs);
407 int width = pixGetWidth(src_pix);
408 int height = pixGetHeight(src_pix);
409 ICOORD bleft(0, 0);
410 ICOORD tright(height, width);
411 FindLineVectors(bleft, tright, &line_bblobs, &vertical_x, &vertical_y,
412 vectors);
413 if (!vectors->empty()) {
414 RemoveUnusedLineSegments(true, &line_bblobs, *pix_hline);
415 SubtractLinesAndResidue(*pix_hline, pix_non_hline, resolution, src_pix);
416 ICOORD vertical;
417 vertical.set_with_shrink(vertical_x, vertical_y);
418 TabVector::MergeSimilarTabVectors(vertical, vectors, nullptr);
419 // Iterate the vectors to flip them. x and y were flipped for horizontal
420 // lines, so FindLineVectors can work just with the vertical case.
421 // See GetLineBoxes for more on the flip.
422 TabVector_IT h_it(vectors);
423 for (h_it.mark_cycle_pt(); !h_it.cycled_list(); h_it.forward()) {
424 h_it.data()->XYFlip();
425 }
426 } else {
427 pixDestroy(pix_hline);
428 }
429}
430
431// Finds vertical lines in the given list of BLOBNBOXes. bleft and tright
432// are the bounds of the image on which the input line_bblobs were found.
433// The input line_bblobs list is const really.
434// The output vertical_x and vertical_y are the total of all the vectors.
435// The output list of TabVector makes no reference to the input BLOBNBOXes.
436void LineFinder::FindLineVectors(const ICOORD& bleft, const ICOORD& tright,
437 BLOBNBOX_LIST* line_bblobs,
438 int* vertical_x, int* vertical_y,
439 TabVector_LIST* vectors) {
440 BLOBNBOX_IT bbox_it(line_bblobs);
441 int b_count = 0;
442 // Put all the blobs into the grid to find the lines, and move the blobs
443 // to the output lists.
444 AlignedBlob blob_grid(kLineFindGridSize, bleft, tright);
445 for (bbox_it.mark_cycle_pt(); !bbox_it.cycled_list(); bbox_it.forward()) {
446 BLOBNBOX* bblob = bbox_it.data();
448 bblob->set_left_rule(bleft.x());
449 bblob->set_right_rule(tright.x());
450 bblob->set_left_crossing_rule(bleft.x());
451 bblob->set_right_crossing_rule(tright.x());
452 blob_grid.InsertBBox(false, true, bblob);
453 ++b_count;
454 }
455 if (b_count == 0)
456 return;
457
458 // Search the entire grid, looking for vertical line vectors.
459 BlobGridSearch lsearch(&blob_grid);
460 BLOBNBOX* bbox;
461 TabVector_IT vector_it(vectors);
462 *vertical_x = 0;
463 *vertical_y = 1;
464 lsearch.StartFullSearch();
465 while ((bbox = lsearch.NextFullSearch()) != nullptr) {
466 if (bbox->left_tab_type() == TT_MAYBE_ALIGNED) {
467 const TBOX& box = bbox->bounding_box();
468 if (AlignedBlob::WithinTestRegion(2, box.left(), box.bottom()))
469 tprintf("Finding line vector starting at bbox (%d,%d)\n",
470 box.left(), box.bottom());
471 AlignedBlobParams align_params(*vertical_x, *vertical_y, box.width());
472 TabVector* vector = blob_grid.FindVerticalAlignment(align_params, bbox,
473 vertical_x,
474 vertical_y);
475 if (vector != nullptr) {
476 vector->Freeze();
477 vector_it.add_to_end(vector);
478 }
479 }
480 }
481}
482
483// Returns a Pix music mask if music is detected.
484// Any vertical line that has at least 5 intersections in sufficient density
485// is taken to be a bar. Bars are used as a seed and the entire touching
486// component is added to the output music mask and subtracted from the lines.
487// Returns nullptr and does minimal work if no music is found.
488static Pix* FilterMusic(int resolution, Pix* pix_closed,
489 Pix* pix_vline, Pix* pix_hline,
490 l_int32* v_empty, l_int32* h_empty) {
491 int max_stave_height = static_cast<int>(resolution * kMaxStaveHeight);
492 Pix* intersection_pix = pixAnd(nullptr, pix_vline, pix_hline);
493 Boxa* boxa = pixConnComp(pix_vline, nullptr, 8);
494 // Iterate over the boxes to find music bars.
495 int nboxes = boxaGetCount(boxa);
496 Pix* music_mask = nullptr;
497 for (int i = 0; i < nboxes; ++i) {
498 Box* box = boxaGetBox(boxa, i, L_CLONE);
499 l_int32 x, y, box_width, box_height;
500 boxGetGeometry(box, &x, &y, &box_width, &box_height);
501 int joins = NumTouchingIntersections(box, intersection_pix);
502 // Test for the join density being at least 5 per max_stave_height,
503 // ie (joins-1)/box_height >= (5-1)/max_stave_height.
504 if (joins >= 5 && (joins - 1) * max_stave_height >= 4 * box_height) {
505 // This is a music bar. Add to the mask.
506 if (music_mask == nullptr)
507 music_mask = pixCreate(pixGetWidth(pix_vline), pixGetHeight(pix_vline),
508 1);
509 pixSetInRect(music_mask, box);
510 }
511 boxDestroy(&box);
512 }
513 boxaDestroy(&boxa);
514 pixDestroy(&intersection_pix);
515 if (music_mask != nullptr) {
516 // The mask currently contains just the bars. Use the mask as a seed
517 // and the pix_closed as the mask for a seedfill to get all the
518 // intersecting staves.
519 pixSeedfillBinary(music_mask, music_mask, pix_closed, 8);
520 // Filter out false positives. CCs in the music_mask should be the vast
521 // majority of the pixels in their bounding boxes, as we expect just a
522 // tiny amount of text, a few phrase marks, and crescendo etc left.
523 Boxa* boxa = pixConnComp(music_mask, nullptr, 8);
524 // Iterate over the boxes to find music components.
525 int nboxes = boxaGetCount(boxa);
526 for (int i = 0; i < nboxes; ++i) {
527 Box* box = boxaGetBox(boxa, i, L_CLONE);
528 Pix* rect_pix = pixClipRectangle(music_mask, box, nullptr);
529 l_int32 music_pixels;
530 pixCountPixels(rect_pix, &music_pixels, nullptr);
531 pixDestroy(&rect_pix);
532 rect_pix = pixClipRectangle(pix_closed, box, nullptr);
533 l_int32 all_pixels;
534 pixCountPixels(rect_pix, &all_pixels, nullptr);
535 pixDestroy(&rect_pix);
536 if (music_pixels < kMinMusicPixelFraction * all_pixels) {
537 // False positive. Delete from the music mask.
538 pixClearInRect(music_mask, box);
539 }
540 boxDestroy(&box);
541 }
542 l_int32 no_remaining_music;
543 boxaDestroy(&boxa);
544 pixZero(music_mask, &no_remaining_music);
545 if (no_remaining_music) {
546 pixDestroy(&music_mask);
547 } else {
548 pixSubtract(pix_vline, pix_vline, music_mask);
549 pixSubtract(pix_hline, pix_hline, music_mask);
550 // We may have deleted all the lines
551 pixZero(pix_vline, v_empty);
552 pixZero(pix_hline, h_empty);
553 }
554 }
555 return music_mask;
556}
557
558// Most of the heavy lifting of line finding. Given src_pix and its separate
559// resolution, returns image masks:
560// pix_vline candidate vertical lines.
561// pix_non_vline pixels that didn't look like vertical lines.
562// pix_hline candidate horizontal lines.
563// pix_non_hline pixels that didn't look like horizontal lines.
564// pix_intersections pixels where vertical and horizontal lines meet.
565// pix_music_mask candidate music staves.
566// This function promises to initialize all the output (2nd level) pointers,
567// but any of the returns that are empty will be nullptr on output.
568// None of the input (1st level) pointers may be nullptr except pix_music_mask,
569// which will disable music detection, and pixa_display.
570void LineFinder::GetLineMasks(int resolution, Pix* src_pix,
571 Pix** pix_vline, Pix** pix_non_vline,
572 Pix** pix_hline, Pix** pix_non_hline,
573 Pix** pix_intersections, Pix** pix_music_mask,
574 Pixa* pixa_display) {
575 Pix* pix_closed = nullptr;
576 Pix* pix_hollow = nullptr;
577
578 int max_line_width = resolution / kThinLineFraction;
579 int min_line_length = resolution / kMinLineLengthFraction;
580 if (pixa_display != nullptr) {
581 tprintf("Image resolution = %d, max line width = %d, min length=%d\n",
582 resolution, max_line_width, min_line_length);
583 }
584 int closing_brick = max_line_width / 3;
585
586// only use opencl if compiled w/ OpenCL and selected device is opencl
587#ifdef USE_OPENCL
588 if (OpenclDevice::selectedDeviceIsOpenCL()) {
589 // OpenCL pixGetLines Operation
590 int clStatus = OpenclDevice::initMorphCLAllocations(pixGetWpl(src_pix),
591 pixGetHeight(src_pix),
592 src_pix);
593 bool getpixclosed = pix_music_mask != nullptr;
594 OpenclDevice::pixGetLinesCL(nullptr, src_pix, pix_vline, pix_hline,
595 &pix_closed, getpixclosed, closing_brick,
596 closing_brick, max_line_width, max_line_width,
597 min_line_length, min_line_length);
598 } else {
599#endif
600 // Close up small holes, making it less likely that false alarms are found
601 // in thickened text (as it will become more solid) and also smoothing over
602 // some line breaks and nicks in the edges of the lines.
603 pix_closed = pixCloseBrick(nullptr, src_pix, closing_brick, closing_brick);
604 if (pixa_display != nullptr)
605 pixaAddPix(pixa_display, pix_closed, L_CLONE);
606 // Open up with a big box to detect solid areas, which can then be subtracted.
607 // This is very generous and will leave in even quite wide lines.
608 Pix* pix_solid = pixOpenBrick(nullptr, pix_closed, max_line_width,
609 max_line_width);
610 if (pixa_display != nullptr)
611 pixaAddPix(pixa_display, pix_solid, L_CLONE);
612 pix_hollow = pixSubtract(nullptr, pix_closed, pix_solid);
613
614 pixDestroy(&pix_solid);
615
616 // Now open up in both directions independently to find lines of at least
617 // 1 inch/kMinLineLengthFraction in length.
618 if (pixa_display != nullptr)
619 pixaAddPix(pixa_display, pix_hollow, L_CLONE);
620 *pix_vline = pixOpenBrick(nullptr, pix_hollow, 1, min_line_length);
621 *pix_hline = pixOpenBrick(nullptr, pix_hollow, min_line_length, 1);
622
623 pixDestroy(&pix_hollow);
624#ifdef USE_OPENCL
625 }
626#endif
627
628 // Lines are sufficiently rare, that it is worth checking for a zero image.
629 l_int32 v_empty = 0;
630 l_int32 h_empty = 0;
631 pixZero(*pix_vline, &v_empty);
632 pixZero(*pix_hline, &h_empty);
633 if (pix_music_mask != nullptr) {
634 if (!v_empty && !h_empty) {
635 *pix_music_mask = FilterMusic(resolution, pix_closed,
636 *pix_vline, *pix_hline,
637 &v_empty, &h_empty);
638 } else {
639 *pix_music_mask = nullptr;
640 }
641 }
642 pixDestroy(&pix_closed);
643 Pix* pix_nonlines = nullptr;
644 *pix_intersections = nullptr;
645 Pix* extra_non_hlines = nullptr;
646 if (!v_empty) {
647 // Subtract both line candidates from the source to get definite non-lines.
648 pix_nonlines = pixSubtract(nullptr, src_pix, *pix_vline);
649 if (!h_empty) {
650 pixSubtract(pix_nonlines, pix_nonlines, *pix_hline);
651 // Intersections are a useful indicator for likelihood of being a line.
652 *pix_intersections = pixAnd(nullptr, *pix_vline, *pix_hline);
653 // Candidate vlines are not hlines (apart from the intersections)
654 // and vice versa.
655 extra_non_hlines = pixSubtract(nullptr, *pix_vline, *pix_intersections);
656 }
657 *pix_non_vline = pixErodeBrick(nullptr, pix_nonlines, kMaxLineResidue, 1);
658 pixSeedfillBinary(*pix_non_vline, *pix_non_vline, pix_nonlines, 8);
659 if (!h_empty) {
660 // Candidate hlines are not vlines.
661 pixOr(*pix_non_vline, *pix_non_vline, *pix_hline);
662 pixSubtract(*pix_non_vline, *pix_non_vline, *pix_intersections);
663 }
664 if (!FilterFalsePositives(resolution, *pix_non_vline, *pix_intersections,
665 *pix_vline))
666 pixDestroy(pix_vline); // No candidates left.
667 } else {
668 // No vertical lines.
669 pixDestroy(pix_vline);
670 *pix_non_vline = nullptr;
671 if (!h_empty) {
672 pix_nonlines = pixSubtract(nullptr, src_pix, *pix_hline);
673 }
674 }
675 if (h_empty) {
676 pixDestroy(pix_hline);
677 *pix_non_hline = nullptr;
678 if (v_empty) {
679 return;
680 }
681 } else {
682 *pix_non_hline = pixErodeBrick(nullptr, pix_nonlines, 1, kMaxLineResidue);
683 pixSeedfillBinary(*pix_non_hline, *pix_non_hline, pix_nonlines, 8);
684 if (extra_non_hlines != nullptr) {
685 pixOr(*pix_non_hline, *pix_non_hline, extra_non_hlines);
686 pixDestroy(&extra_non_hlines);
687 }
688 if (!FilterFalsePositives(resolution, *pix_non_hline, *pix_intersections,
689 *pix_hline))
690 pixDestroy(pix_hline); // No candidates left.
691 }
692 if (pixa_display != nullptr) {
693 if (*pix_vline != nullptr) pixaAddPix(pixa_display, *pix_vline, L_CLONE);
694 if (*pix_hline != nullptr) pixaAddPix(pixa_display, *pix_hline, L_CLONE);
695 if (pix_nonlines != nullptr) pixaAddPix(pixa_display, pix_nonlines, L_CLONE);
696 if (*pix_non_vline != nullptr)
697 pixaAddPix(pixa_display, *pix_non_vline, L_CLONE);
698 if (*pix_non_hline != nullptr)
699 pixaAddPix(pixa_display, *pix_non_hline, L_CLONE);
700 if (*pix_intersections != nullptr)
701 pixaAddPix(pixa_display, *pix_intersections, L_CLONE);
702 if (pix_music_mask != nullptr && *pix_music_mask != nullptr)
703 pixaAddPix(pixa_display, *pix_music_mask, L_CLONE);
704 }
705 pixDestroy(&pix_nonlines);
706}
707
708// Returns a list of boxes corresponding to the candidate line segments. Sets
709// the line_crossings member of the boxes so we can later determine the number
710// of intersections touched by a full line.
711void LineFinder::GetLineBoxes(bool horizontal_lines,
712 Pix* pix_lines, Pix* pix_intersections,
713 C_BLOB_LIST* line_cblobs,
714 BLOBNBOX_LIST* line_bblobs) {
715 // Put a single pixel crack in every line at an arbitrary spacing,
716 // so they break up and the bounding boxes can be used to get the
717 // direction accurately enough without needing outlines.
718 int wpl = pixGetWpl(pix_lines);
719 int width = pixGetWidth(pix_lines);
720 int height = pixGetHeight(pix_lines);
721 l_uint32* data = pixGetData(pix_lines);
722 if (horizontal_lines) {
723 for (int y = 0; y < height; ++y, data += wpl) {
724 for (int x = kCrackSpacing; x < width; x += kCrackSpacing) {
725 CLEAR_DATA_BIT(data, x);
726 }
727 }
728 } else {
729 for (int y = kCrackSpacing; y < height; y += kCrackSpacing) {
730 memset(data + wpl * y, 0, wpl * sizeof(*data));
731 }
732 }
733 // Get the individual connected components
734 Boxa* boxa = pixConnComp(pix_lines, nullptr, 8);
735 ConvertBoxaToBlobs(width, height, &boxa, line_cblobs);
736 // Make the BLOBNBOXes from the C_BLOBs.
737 C_BLOB_IT blob_it(line_cblobs);
738 BLOBNBOX_IT bbox_it(line_bblobs);
739 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
740 C_BLOB* cblob = blob_it.data();
741 auto* bblob = new BLOBNBOX(cblob);
742 bbox_it.add_to_end(bblob);
743 // Determine whether the line segment touches two intersections.
744 const TBOX& bbox = bblob->bounding_box();
745 Box* box = boxCreate(bbox.left(), bbox.bottom(),
746 bbox.width(), bbox.height());
747 bblob->set_line_crossings(NumTouchingIntersections(box, pix_intersections));
748 boxDestroy(&box);
749 // Transform the bounding box prior to finding lines. To save writing
750 // two line finders, flip x and y for horizontal lines and re-use the
751 // tab-stop detection code. For vertical lines we still have to flip the
752 // y-coordinates to switch from leptonica coords to tesseract coords.
753 if (horizontal_lines) {
754 // Note that we have Leptonica coords stored in a Tesseract box, so that
755 // bbox.bottom(), being the MIN y coord, is actually the top, so to get
756 // back to Leptonica coords in RemoveUnusedLineSegments, we have to
757 // use height - box.right() as the top, which looks very odd.
758 TBOX new_box(height - bbox.top(), bbox.left(),
759 height - bbox.bottom(), bbox.right());
760 bblob->set_bounding_box(new_box);
761 } else {
762 TBOX new_box(bbox.left(), height - bbox.top(),
763 bbox.right(), height - bbox.bottom());
764 bblob->set_bounding_box(new_box);
765 }
766 }
767}
768
769} // namespace tesseract.
@ TT_VLINE
Definition: blobbox.h:65
@ TT_MAYBE_ALIGNED
Definition: blobbox.h:63
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
void outlines_to_blobs(BLOCK *block, ICOORD bleft, ICOORD tright, C_OUTLINE_LIST *outlines)
Definition: edgblob.cpp:349
const double kMinMusicPixelFraction
Definition: linefind.cpp:62
const double kMaxStaveHeight
Definition: linefind.cpp:60
const int kCrackSpacing
Spacing of cracks across the page to break up tall vertical lines.
Definition: linefind.cpp:45
const double kThickLengthMultiple
Definition: linefind.cpp:56
const int kMinThickLineWidth
Definition: linefind.cpp:49
const double kMaxNonLineDensity
Definition: linefind.cpp:58
const int kMinLineLengthFraction
Denominator of resolution makes min pixels to demand line lengths to be.
Definition: linefind.cpp:43
const int kMaxLineResidue
Definition: linefind.cpp:53
const int kLineFindGridSize
Grid size used by line finder. Not very critical.
Definition: linefind.cpp:47
const int kThinLineFraction
Denominator of resolution makes max pixel width to allow thin lines.
Definition: linefind.cpp:41
GridSearch< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > BlobGridSearch
Definition: blobgrid.h:31
void set_left_tab_type(TabType new_type)
Definition: blobbox.h:274
void set_right_crossing_rule(int new_right)
Definition: blobbox.h:334
void set_left_rule(int new_left)
Definition: blobbox.h:316
void set_line_crossings(int value)
Definition: blobbox.h:395
TabType left_tab_type() const
Definition: blobbox.h:271
void set_bounding_box(const TBOX &new_box)
Definition: blobbox.h:235
const TBOX & bounding_box() const
Definition: blobbox.h:230
void set_right_rule(int new_right)
Definition: blobbox.h:322
void set_left_crossing_rule(int new_left)
Definition: blobbox.h:328
ICOORD pos
Definition: crakedge.h:30
Definition: ocrblock.h:31
C_BLOB_LIST * blob_list()
get blobs
Definition: ocrblock.h:128
integer coordinate
Definition: points.h:32
void set_with_shrink(int x, int y)
Set from the given x,y, shrinking the vector to fit if needed.
Definition: points.cpp:41
int16_t x() const
access function
Definition: points.h:52
Definition: rect.h:34
int16_t top() const
Definition: rect.h:58
int16_t width() const
Definition: rect.h:115
int16_t height() const
Definition: rect.h:108
int16_t left() const
Definition: rect.h:72
int16_t bottom() const
Definition: rect.h:65
int16_t right() const
Definition: rect.h:79
static bool WithinTestRegion(int detail_level, int x, int y)
static void FindAndRemoveLines(int resolution, bool debug, Pix *pix, int *vertical_x, int *vertical_y, Pix **pix_music_mask, TabVector_LIST *v_lines, TabVector_LIST *h_lines)
Definition: linefind.cpp:243
static void ConvertBoxaToBlobs(int image_width, int image_height, Boxa **boxes, C_BLOB_LIST *blobs)
Definition: linefind.cpp:319
static void MergeSimilarTabVectors(const ICOORD &vertical, TabVector_LIST *vectors, BlobGrid *grid)
Definition: tabvector.cpp:353