tesseract  4.0.0-1-g2a2b
linefind.cpp
Go to the documentation of this file.
1 // 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 #include "openclwrapper.h"
31 
32 #include "allheaders.h"
33 
34 #include <algorithm>
35 
36 namespace tesseract {
37 
39 const int kThinLineFraction = 20;
41 const int kMinLineLengthFraction = 4;
43 const int kCrackSpacing = 100;
45 const int kLineFindGridSize = 50;
46 // Min width of a line in pixels to be considered thick.
47 const int kMinThickLineWidth = 12;
48 // Max size of line residue. (The pixels that fail the long thin opening, and
49 // therefore don't make it to the candidate line mask, but are nevertheless
50 // part of the line.)
51 const int kMaxLineResidue = 6;
52 // Min length in inches of a line segment that exceeds kMinThickLineWidth in
53 // thickness. (Such lines shouldn't break by simple image degradation.)
54 const double kThickLengthMultiple = 0.75;
55 // Max fraction of line box area that can be occupied by non-line pixels.
56 const double kMaxNonLineDensity = 0.25;
57 // Max height of a music stave in inches.
58 const double kMaxStaveHeight = 1.0;
59 // Minimum fraction of pixels in a music rectangle connected to the staves.
60 const double kMinMusicPixelFraction = 0.75;
61 
62 // Erases the unused blobs from the line_pix image, taking into account
63 // whether this was a horizontal or vertical line set.
64 static void RemoveUnusedLineSegments(bool horizontal_lines,
65  BLOBNBOX_LIST* line_bblobs,
66  Pix* line_pix) {
67  int height = pixGetHeight(line_pix);
68  BLOBNBOX_IT bbox_it(line_bblobs);
69  for (bbox_it.mark_cycle_pt(); !bbox_it.cycled_list(); bbox_it.forward()) {
70  BLOBNBOX* blob = bbox_it.data();
71  if (blob->left_tab_type() != TT_VLINE) {
72  const TBOX& box = blob->bounding_box();
73  Box* pixbox = nullptr;
74  if (horizontal_lines) {
75  // Horizontal lines are in tess format and also have x and y flipped
76  // (to use FindVerticalAlignment) so we have to flip x and y and then
77  // convert to Leptonica by height - flipped x (ie the right edge).
78  // See GetLineBoxes for more explanation.
79  pixbox = boxCreate(box.bottom(), height - box.right(),
80  box.height(), box.width());
81  } else {
82  // For vertical lines, just flip upside-down to convert to Leptonica.
83  // The y position of the box in Leptonica terms is the distance from
84  // the top of the image to the top of the box.
85  pixbox = boxCreate(box.left(), height - box.top(),
86  box.width(), box.height());
87  }
88  pixClearInRect(line_pix, pixbox);
89  boxDestroy(&pixbox);
90  }
91  }
92 }
93 
94 // Helper subtracts the line_pix image from the src_pix, and removes residue
95 // as well by removing components that touch the line, but are not in the
96 // non_line_pix mask. It is assumed that the non_line_pix mask has already
97 // been prepared to required accuracy.
98 static void SubtractLinesAndResidue(Pix* line_pix, Pix* non_line_pix,
99  int resolution, Pix* src_pix) {
100  // First remove the lines themselves.
101  pixSubtract(src_pix, src_pix, line_pix);
102  // Subtract the non-lines from the image to get the residue.
103  Pix* residue_pix = pixSubtract(nullptr, src_pix, non_line_pix);
104  // Dilate the lines so they touch the residue.
105  Pix* fat_line_pix = pixDilateBrick(nullptr, line_pix, 3, 3);
106  // Seed fill the fat lines to get all the residue.
107  pixSeedfillBinary(fat_line_pix, fat_line_pix, residue_pix, 8);
108  // Subtract the residue from the original image.
109  pixSubtract(src_pix, src_pix, fat_line_pix);
110  pixDestroy(&fat_line_pix);
111  pixDestroy(&residue_pix);
112 }
113 
114 // Returns the maximum strokewidth in the given binary image by doubling
115 // the maximum of the distance function.
116 static int MaxStrokeWidth(Pix* pix) {
117  Pix* dist_pix = pixDistanceFunction(pix, 4, 8, L_BOUNDARY_BG);
118  int width = pixGetWidth(dist_pix);
119  int height = pixGetHeight(dist_pix);
120  int wpl = pixGetWpl(dist_pix);
121  l_uint32* data = pixGetData(dist_pix);
122  // Find the maximum value in the distance image.
123  int max_dist = 0;
124  for (int y = 0; y < height; ++y) {
125  for (int x = 0; x < width; ++x) {
126  int pixel = GET_DATA_BYTE(data, x);
127  if (pixel > max_dist)
128  max_dist = pixel;
129  }
130  data += wpl;
131  }
132  pixDestroy(&dist_pix);
133  return max_dist * 2;
134 }
135 
136 // Returns the number of components in the intersection_pix touched by line_box.
137 static int NumTouchingIntersections(Box* line_box, Pix* intersection_pix) {
138  if (intersection_pix == nullptr) return 0;
139  Pix* rect_pix = pixClipRectangle(intersection_pix, line_box, nullptr);
140  Boxa* boxa = pixConnComp(rect_pix, nullptr, 8);
141  pixDestroy(&rect_pix);
142  if (boxa == nullptr) return false;
143  int result = boxaGetCount(boxa);
144  boxaDestroy(&boxa);
145  return result;
146 }
147 
148 // Returns the number of black pixels found in the box made by adding the line
149 // width to both sides of the line bounding box. (Increasing the smallest
150 // dimension of the bounding box.)
151 static int CountPixelsAdjacentToLine(int line_width, Box* line_box,
152  Pix* nonline_pix) {
153  l_int32 x, y, box_width, box_height;
154  boxGetGeometry(line_box, &x, &y, &box_width, &box_height);
155  if (box_width > box_height) {
156  // horizontal line.
157  int bottom = std::min(pixGetHeight(nonline_pix), y + box_height + line_width);
158  y = std::max(0, y - line_width);
159  box_height = bottom - y;
160  } else {
161  // Vertical line.
162  int right = std::min(pixGetWidth(nonline_pix), x + box_width + line_width);
163  x = std::max(0, x - line_width);
164  box_width = right - x;
165  }
166  Box* box = boxCreate(x, y, box_width, box_height);
167  Pix* rect_pix = pixClipRectangle(nonline_pix, box, nullptr);
168  boxDestroy(&box);
169  l_int32 result;
170  pixCountPixels(rect_pix, &result, nullptr);
171  pixDestroy(&rect_pix);
172  return result;
173 }
174 
175 // Helper erases false-positive line segments from the input/output line_pix.
176 // 1. Since thick lines shouldn't really break up, we can eliminate some false
177 // positives by marking segments that are at least kMinThickLineWidth
178 // thickness, yet have a length less than min_thick_length.
179 // 2. Lines that don't have at least 2 intersections with other lines and have
180 // a lot of neighbouring non-lines are probably not lines (perhaps arabic
181 // or Hindi words, or underlines.)
182 // Bad line components are erased from line_pix.
183 // Returns the number of remaining connected components.
184 static int FilterFalsePositives(int resolution, Pix* nonline_pix,
185  Pix* intersection_pix, Pix* line_pix) {
186  int min_thick_length = static_cast<int>(resolution * kThickLengthMultiple);
187  Pixa* pixa = nullptr;
188  Boxa* boxa = pixConnComp(line_pix, &pixa, 8);
189  // Iterate over the boxes to remove false positives.
190  int nboxes = boxaGetCount(boxa);
191  int remaining_boxes = nboxes;
192  for (int i = 0; i < nboxes; ++i) {
193  Box* box = boxaGetBox(boxa, i, L_CLONE);
194  l_int32 x, y, box_width, box_height;
195  boxGetGeometry(box, &x, &y, &box_width, &box_height);
196  Pix* comp_pix = pixaGetPix(pixa, i, L_CLONE);
197  int max_width = MaxStrokeWidth(comp_pix);
198  pixDestroy(&comp_pix);
199  bool bad_line = false;
200  // If the length is too short to stand-alone as a line, and the box width
201  // is thick enough, and the stroke width is thick enough it is bad.
202  if (box_width >= kMinThickLineWidth && box_height >= kMinThickLineWidth &&
203  box_width < min_thick_length && box_height < min_thick_length &&
204  max_width > kMinThickLineWidth) {
205  // Too thick for the length.
206  bad_line = true;
207  }
208  if (!bad_line &&
209  (intersection_pix == nullptr ||
210  NumTouchingIntersections(box, intersection_pix) < 2)) {
211  // Test non-line density near the line.
212  int nonline_count = CountPixelsAdjacentToLine(max_width, box,
213  nonline_pix);
214  if (nonline_count > box_height * box_width * kMaxNonLineDensity)
215  bad_line = true;
216  }
217  if (bad_line) {
218  // Not a good line.
219  pixClearInRect(line_pix, box);
220  --remaining_boxes;
221  }
222  boxDestroy(&box);
223  }
224  pixaDestroy(&pixa);
225  boxaDestroy(&boxa);
226  return remaining_boxes;
227 }
228 
229 // Finds vertical and horizontal line objects in the given pix.
230 // Uses the given resolution to determine size thresholds instead of any
231 // that may be present in the pix.
232 // The output vertical_x and vertical_y contain a sum of the output vectors,
233 // thereby giving the mean vertical direction.
234 // If pix_music_mask != nullptr, and music is detected, a mask of the staves
235 // and anything that is connected (bars, notes etc.) will be returned in
236 // pix_music_mask, the mask subtracted from pix, and the lines will not
237 // appear in v_lines or h_lines.
238 // The output vectors are owned by the list and Frozen (cannot refit) by
239 // having no boxes, as there is no need to refit or merge separator lines.
240 // The detected lines are removed from the pix.
241 void LineFinder::FindAndRemoveLines(int resolution, bool debug, Pix* pix,
242  int* vertical_x, int* vertical_y,
243  Pix** pix_music_mask,
244  TabVector_LIST* v_lines,
245  TabVector_LIST* h_lines) {
246  PERF_COUNT_START("FindAndRemoveLines")
247  if (pix == nullptr || vertical_x == nullptr || vertical_y == nullptr) {
248  tprintf("Error in parameters for LineFinder::FindAndRemoveLines\n");
249  return;
250  }
251  Pix* pix_vline = nullptr;
252  Pix* pix_non_vline = nullptr;
253  Pix* pix_hline = nullptr;
254  Pix* pix_non_hline = nullptr;
255  Pix* pix_intersections = nullptr;
256  Pixa* pixa_display = debug ? pixaCreate(0) : nullptr;
257  GetLineMasks(resolution, pix, &pix_vline, &pix_non_vline, &pix_hline,
258  &pix_non_hline, &pix_intersections, pix_music_mask,
259  pixa_display);
260  // Find lines, convert to TabVector_LIST and remove those that are used.
261  FindAndRemoveVLines(resolution, pix_intersections, vertical_x, vertical_y,
262  &pix_vline, pix_non_vline, pix, v_lines);
263  if (pix_hline != nullptr) {
264  // Recompute intersections and re-filter false positive h-lines.
265  if (pix_vline != nullptr)
266  pixAnd(pix_intersections, pix_vline, pix_hline);
267  else
268  pixDestroy(&pix_intersections);
269  if (!FilterFalsePositives(resolution, pix_non_hline, pix_intersections,
270  pix_hline)) {
271  pixDestroy(&pix_hline);
272  }
273  }
274  FindAndRemoveHLines(resolution, pix_intersections, *vertical_x, *vertical_y,
275  &pix_hline, pix_non_hline, pix, h_lines);
276  if (pixa_display != nullptr && pix_vline != nullptr)
277  pixaAddPix(pixa_display, pix_vline, L_CLONE);
278  if (pixa_display != nullptr && pix_hline != nullptr)
279  pixaAddPix(pixa_display, pix_hline, L_CLONE);
280  if (pix_vline != nullptr && pix_hline != nullptr) {
281  // Remove joins (intersections) where lines cross, and the residue.
282  // Recalculate the intersections, since some lines have been deleted.
283  pixAnd(pix_intersections, pix_vline, pix_hline);
284  // Fatten up the intersections and seed-fill to get the intersection
285  // residue.
286  Pix* pix_join_residue = pixDilateBrick(nullptr, pix_intersections, 5, 5);
287  pixSeedfillBinary(pix_join_residue, pix_join_residue, pix, 8);
288  // Now remove the intersection residue.
289  pixSubtract(pix, pix, pix_join_residue);
290  pixDestroy(&pix_join_residue);
291  }
292  // Remove any detected music.
293  if (pix_music_mask != nullptr && *pix_music_mask != nullptr) {
294  if (pixa_display != nullptr)
295  pixaAddPix(pixa_display, *pix_music_mask, L_CLONE);
296  pixSubtract(pix, pix, *pix_music_mask);
297  }
298  if (pixa_display != nullptr)
299  pixaAddPix(pixa_display, pix, L_CLONE);
300 
301  pixDestroy(&pix_vline);
302  pixDestroy(&pix_non_vline);
303  pixDestroy(&pix_hline);
304  pixDestroy(&pix_non_hline);
305  pixDestroy(&pix_intersections);
306  if (pixa_display != nullptr) {
307  pixaConvertToPdf(pixa_display, resolution, 1.0f, 0, 0, "LineFinding",
308  "vhlinefinding.pdf");
309  pixaDestroy(&pixa_display);
310  }
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.
319 void 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  C_OUTLINE* 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.
362 void 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.
398 void 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.
436 void 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.
488 static 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.
570 void 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  PERF_COUNT_START("GetLineMasksMorph")
587 // only use opencl if compiled w/ OpenCL and selected device is opencl
588 #ifdef USE_OPENCL
589  if (OpenclDevice::selectedDeviceIsOpenCL()) {
590  // OpenCL pixGetLines Operation
591  int clStatus = OpenclDevice::initMorphCLAllocations(pixGetWpl(src_pix),
592  pixGetHeight(src_pix),
593  src_pix);
594  bool getpixclosed = pix_music_mask != nullptr;
595  OpenclDevice::pixGetLinesCL(nullptr, src_pix, pix_vline, pix_hline,
596  &pix_closed, getpixclosed, closing_brick,
597  closing_brick, max_line_width, max_line_width,
598  min_line_length, min_line_length);
599  } else {
600 #endif
601  // Close up small holes, making it less likely that false alarms are found
602  // in thickened text (as it will become more solid) and also smoothing over
603  // some line breaks and nicks in the edges of the lines.
604  pix_closed = pixCloseBrick(nullptr, src_pix, closing_brick, closing_brick);
605  if (pixa_display != nullptr)
606  pixaAddPix(pixa_display, pix_closed, L_CLONE);
607  // Open up with a big box to detect solid areas, which can then be subtracted.
608  // This is very generous and will leave in even quite wide lines.
609  Pix* pix_solid = pixOpenBrick(nullptr, pix_closed, max_line_width,
610  max_line_width);
611  if (pixa_display != nullptr)
612  pixaAddPix(pixa_display, pix_solid, L_CLONE);
613  pix_hollow = pixSubtract(nullptr, pix_closed, pix_solid);
614 
615  pixDestroy(&pix_solid);
616 
617  // Now open up in both directions independently to find lines of at least
618  // 1 inch/kMinLineLengthFraction in length.
619  if (pixa_display != nullptr)
620  pixaAddPix(pixa_display, pix_hollow, L_CLONE);
621  *pix_vline = pixOpenBrick(nullptr, pix_hollow, 1, min_line_length);
622  *pix_hline = pixOpenBrick(nullptr, pix_hollow, min_line_length, 1);
623 
624  pixDestroy(&pix_hollow);
625 #ifdef USE_OPENCL
626  }
627 #endif
629 
630  // Lines are sufficiently rare, that it is worth checking for a zero image.
631  l_int32 v_empty = 0;
632  l_int32 h_empty = 0;
633  pixZero(*pix_vline, &v_empty);
634  pixZero(*pix_hline, &h_empty);
635  if (pix_music_mask != nullptr) {
636  if (!v_empty && !h_empty) {
637  *pix_music_mask = FilterMusic(resolution, pix_closed,
638  *pix_vline, *pix_hline,
639  &v_empty, &h_empty);
640  } else {
641  *pix_music_mask = nullptr;
642  }
643  }
644  pixDestroy(&pix_closed);
645  Pix* pix_nonlines = nullptr;
646  *pix_intersections = nullptr;
647  Pix* extra_non_hlines = nullptr;
648  if (!v_empty) {
649  // Subtract both line candidates from the source to get definite non-lines.
650  pix_nonlines = pixSubtract(nullptr, src_pix, *pix_vline);
651  if (!h_empty) {
652  pixSubtract(pix_nonlines, pix_nonlines, *pix_hline);
653  // Intersections are a useful indicator for likelihood of being a line.
654  *pix_intersections = pixAnd(nullptr, *pix_vline, *pix_hline);
655  // Candidate vlines are not hlines (apart from the intersections)
656  // and vice versa.
657  extra_non_hlines = pixSubtract(nullptr, *pix_vline, *pix_intersections);
658  }
659  *pix_non_vline = pixErodeBrick(nullptr, pix_nonlines, kMaxLineResidue, 1);
660  pixSeedfillBinary(*pix_non_vline, *pix_non_vline, pix_nonlines, 8);
661  if (!h_empty) {
662  // Candidate hlines are not vlines.
663  pixOr(*pix_non_vline, *pix_non_vline, *pix_hline);
664  pixSubtract(*pix_non_vline, *pix_non_vline, *pix_intersections);
665  }
666  if (!FilterFalsePositives(resolution, *pix_non_vline, *pix_intersections,
667  *pix_vline))
668  pixDestroy(pix_vline); // No candidates left.
669  } else {
670  // No vertical lines.
671  pixDestroy(pix_vline);
672  *pix_non_vline = nullptr;
673  if (!h_empty) {
674  pix_nonlines = pixSubtract(nullptr, src_pix, *pix_hline);
675  }
676  }
677  if (h_empty) {
678  pixDestroy(pix_hline);
679  *pix_non_hline = nullptr;
680  if (v_empty) {
681  return;
682  }
683  } else {
684  *pix_non_hline = pixErodeBrick(nullptr, pix_nonlines, 1, kMaxLineResidue);
685  pixSeedfillBinary(*pix_non_hline, *pix_non_hline, pix_nonlines, 8);
686  if (extra_non_hlines != nullptr) {
687  pixOr(*pix_non_hline, *pix_non_hline, extra_non_hlines);
688  pixDestroy(&extra_non_hlines);
689  }
690  if (!FilterFalsePositives(resolution, *pix_non_hline, *pix_intersections,
691  *pix_hline))
692  pixDestroy(pix_hline); // No candidates left.
693  }
694  if (pixa_display != nullptr) {
695  if (*pix_vline != nullptr) pixaAddPix(pixa_display, *pix_vline, L_CLONE);
696  if (*pix_hline != nullptr) pixaAddPix(pixa_display, *pix_hline, L_CLONE);
697  if (pix_nonlines != nullptr) pixaAddPix(pixa_display, pix_nonlines, L_CLONE);
698  if (*pix_non_vline != nullptr)
699  pixaAddPix(pixa_display, *pix_non_vline, L_CLONE);
700  if (*pix_non_hline != nullptr)
701  pixaAddPix(pixa_display, *pix_non_hline, L_CLONE);
702  if (*pix_intersections != nullptr)
703  pixaAddPix(pixa_display, *pix_intersections, L_CLONE);
704  if (pix_music_mask != nullptr && *pix_music_mask != nullptr)
705  pixaAddPix(pixa_display, *pix_music_mask, L_CLONE);
706  }
707  pixDestroy(&pix_nonlines);
708 }
709 
710 // Returns a list of boxes corresponding to the candidate line segments. Sets
711 // the line_crossings member of the boxes so we can later determine the number
712 // of intersections touched by a full line.
713 void LineFinder::GetLineBoxes(bool horizontal_lines,
714  Pix* pix_lines, Pix* pix_intersections,
715  C_BLOB_LIST* line_cblobs,
716  BLOBNBOX_LIST* line_bblobs) {
717  // Put a single pixel crack in every line at an arbitrary spacing,
718  // so they break up and the bounding boxes can be used to get the
719  // direction accurately enough without needing outlines.
720  int wpl = pixGetWpl(pix_lines);
721  int width = pixGetWidth(pix_lines);
722  int height = pixGetHeight(pix_lines);
723  l_uint32* data = pixGetData(pix_lines);
724  if (horizontal_lines) {
725  for (int y = 0; y < height; ++y, data += wpl) {
726  for (int x = kCrackSpacing; x < width; x += kCrackSpacing) {
727  CLEAR_DATA_BIT(data, x);
728  }
729  }
730  } else {
731  for (int y = kCrackSpacing; y < height; y += kCrackSpacing) {
732  memset(data + wpl * y, 0, wpl * sizeof(*data));
733  }
734  }
735  // Get the individual connected components
736  Boxa* boxa = pixConnComp(pix_lines, nullptr, 8);
737  ConvertBoxaToBlobs(width, height, &boxa, line_cblobs);
738  // Make the BLOBNBOXes from the C_BLOBs.
739  C_BLOB_IT blob_it(line_cblobs);
740  BLOBNBOX_IT bbox_it(line_bblobs);
741  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
742  C_BLOB* cblob = blob_it.data();
743  BLOBNBOX* bblob = new BLOBNBOX(cblob);
744  bbox_it.add_to_end(bblob);
745  // Determine whether the line segment touches two intersections.
746  const TBOX& bbox = bblob->bounding_box();
747  Box* box = boxCreate(bbox.left(), bbox.bottom(),
748  bbox.width(), bbox.height());
749  bblob->set_line_crossings(NumTouchingIntersections(box, pix_intersections));
750  boxDestroy(&box);
751  // Transform the bounding box prior to finding lines. To save writing
752  // two line finders, flip x and y for horizontal lines and re-use the
753  // tab-stop detection code. For vertical lines we still have to flip the
754  // y-coordinates to switch from leptonica coords to tesseract coords.
755  if (horizontal_lines) {
756  // Note that we have Leptonica coords stored in a Tesseract box, so that
757  // bbox.bottom(), being the MIN y coord, is actually the top, so to get
758  // back to Leptonica coords in RemoveUnusedLineSegments, we have to
759  // use height - box.right() as the top, which looks very odd.
760  TBOX new_box(height - bbox.top(), bbox.left(),
761  height - bbox.bottom(), bbox.right());
762  bblob->set_bounding_box(new_box);
763  } else {
764  TBOX new_box(bbox.left(), height - bbox.top(),
765  bbox.right(), height - bbox.bottom());
766  bblob->set_bounding_box(new_box);
767  }
768  }
769 }
770 
771 } // namespace tesseract.
void set_with_shrink(int x, int y)
Set from the given x,y, shrinking the vector to fit if needed.
Definition: points.cpp:43
const int kMinLineLengthFraction
Denominator of resolution makes min pixels to demand line lengths to be.
Definition: linefind.cpp:41
const int kCrackSpacing
Spacing of cracks across the page to break up tall vertical lines.
Definition: linefind.cpp:43
void outlines_to_blobs(BLOCK *block, ICOORD bleft, ICOORD tright, C_OUTLINE_LIST *outlines)
Definition: edgblob.cpp:354
Definition: rect.h:34
const double kThickLengthMultiple
Definition: linefind.cpp:54
const int kThinLineFraction
Denominator of resolution makes max pixel width to allow thin lines.
Definition: linefind.cpp:39
static bool WithinTestRegion(int detail_level, int x, int y)
C_BLOB_LIST * blob_list()
get blobs
Definition: ocrblock.h:130
#define PERF_COUNT_START(FUNCT_NAME)
void set_left_rule(int new_left)
Definition: blobbox.h:317
const int kLineFindGridSize
Grid size used by line finder. Not very critical.
Definition: linefind.cpp:45
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:241
void set_left_crossing_rule(int new_left)
Definition: blobbox.h:329
const double kMinMusicPixelFraction
Definition: linefind.cpp:60
int16_t width() const
Definition: rect.h:115
void set_right_rule(int new_right)
Definition: blobbox.h:323
const int kMaxLineResidue
Definition: linefind.cpp:51
int16_t left() const
Definition: rect.h:72
const int kMinThickLineWidth
Definition: linefind.cpp:47
void set_bounding_box(const TBOX &new_box)
Definition: blobbox.h:236
int16_t top() const
Definition: rect.h:58
integer coordinate
Definition: points.h:32
int16_t x() const
access function
Definition: points.h:53
ICOORD pos
Definition: crakedge.h:30
TabType left_tab_type() const
Definition: blobbox.h:272
GridSearch< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > BlobGridSearch
Definition: blobgrid.h:31
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:37
Definition: ocrblock.h:30
static void MergeSimilarTabVectors(const ICOORD &vertical, TabVector_LIST *vectors, BlobGrid *grid)
Definition: tabvector.cpp:356
const TBOX & bounding_box() const
Definition: blobbox.h:231
int16_t right() const
Definition: rect.h:79
static void ConvertBoxaToBlobs(int image_width, int image_height, Boxa **boxes, C_BLOB_LIST *blobs)
Definition: linefind.cpp:319
#define PERF_COUNT_END
class DLLSYM C_OUTLINE
Definition: coutln.h:68
const double kMaxNonLineDensity
Definition: linefind.cpp:56
int16_t bottom() const
Definition: rect.h:65
void set_left_tab_type(TabType new_type)
Definition: blobbox.h:275
void set_right_crossing_rule(int new_right)
Definition: blobbox.h:335
int16_t height() const
Definition: rect.h:108
const double kMaxStaveHeight
Definition: linefind.cpp:58
void set_line_crossings(int value)
Definition: blobbox.h:396