Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 _MSC_VER
22 #pragma warning(disable:4244) // Conversion warnings
23 #endif
24 
25 #include "linefind.h"
26 #include "alignedblob.h"
27 #include "tabvector.h"
28 #include "blobbox.h"
29 #include "edgblob.h"
30 // This entire file is dependent upon leptonica. If you don't have it,
31 // then the code doesn't do anything useful.
32 #ifdef HAVE_CONFIG_H
33 #include "config_auto.h"
34 #endif
35 #include "allheaders.h"
36 
37 namespace tesseract {
38 
40 const int kThinLineFraction = 20;
42 const int kMinLineLengthFraction = 4;
44 const int kCrackSpacing = 100;
46 const int kLineFindGridSize = 50;
47 // Min width of a line in pixels to be considered thick.
48 const int kMinThickLineWidth = 12;
49 // Max size of line residue. (The pixels that fail the long thin opening, and
50 // therefore don't make it to the candidate line mask, but are nevertheless
51 // part of the line.)
52 const int kMaxLineResidue = 6;
53 // Min length in inches of a line segment that exceeds kMinThickLineWidth in
54 // thickness. (Such lines shouldn't break by simple image degradation.)
55 const double kThickLengthMultiple = 0.75;
56 // Max fraction of line box area that can be occupied by non-line pixels.
57 const double kMaxNonLineDensity = 0.25;
58 // Max height of a music stave in inches.
59 const double kMaxStaveHeight = 1.0;
60 // Minimum fraction of pixels in a music rectangle connected to the staves.
61 const double kMinMusicPixelFraction = 0.75;
62 
63 // Erases the unused blobs from the line_pix image, taking into account
64 // whether this was a horizontal or vertical line set.
65 static void RemoveUnusedLineSegments(bool horizontal_lines,
66  BLOBNBOX_LIST* line_bblobs,
67  Pix* line_pix) {
68  int height = pixGetHeight(line_pix);
69  BLOBNBOX_IT bbox_it(line_bblobs);
70  for (bbox_it.mark_cycle_pt(); !bbox_it.cycled_list(); bbox_it.forward()) {
71  BLOBNBOX* blob = bbox_it.data();
72  if (blob->left_tab_type() == TT_MAYBE_ALIGNED) {
73  const TBOX& box = blob->bounding_box();
74  Box* pixbox = NULL;
75  if (horizontal_lines) {
76  // Horizontal lines are in tess format and also have x and y flipped
77  // (to use FindVerticalAlignment) so we have to flip x and y and then
78  // convert to Leptonica by height - flipped x (ie the right edge).
79  // See GetLineBoxes for more explanation.
80  pixbox = boxCreate(box.bottom(), height - box.right(),
81  box.height(), box.width());
82 
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.
100 static 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(NULL, src_pix, non_line_pix);
106  // Dilate the lines so they touch the residue.
107  Pix* fat_line_pix = pixDilateBrick(NULL, 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.
118 static 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.
139 static int NumTouchingIntersections(Box* line_box, Pix* intersection_pix) {
140  if (intersection_pix == NULL) return 0;
141  Pix* rect_pix = pixClipRectangle(intersection_pix, line_box, NULL);
142  Boxa* boxa = pixConnComp(rect_pix, NULL, 8);
143  pixDestroy(&rect_pix);
144  if (boxa == NULL) 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.)
153 static 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 = MIN(pixGetHeight(nonline_pix), y + box_height + line_width);
160  y = MAX(0, y - line_width);
161  box_height = bottom - y;
162  } else {
163  // Vertical line.
164  int right = MIN(pixGetWidth(nonline_pix), x + box_width + line_width);
165  x = 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, NULL);
170  boxDestroy(&box);
171  l_int32 result;
172  pixCountPixels(rect_pix, &result, NULL);
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.
186 static 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 = NULL;
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 == NULL ||
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 != NULL, 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.
243 void 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 == NULL || vertical_x == NULL || vertical_y == NULL) {
249  tprintf("Error in parameters for LineFinder::FindAndRemoveLines\n");
250  return;
251  }
252  Pix* pix_vline = NULL;
253  Pix* pix_non_vline = NULL;
254  Pix* pix_hline = NULL;
255  Pix* pix_non_hline = NULL;
256  Pix* pix_intersections = NULL;
257  Pixa* pixa_display = debug ? pixaCreate(0) : NULL;
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 != NULL) {
265  // Recompute intersections and re-filter false positive h-lines.
266  if (pix_vline != NULL)
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 != NULL && pix_vline != NULL)
278  pixaAddPix(pixa_display, pix_vline, L_CLONE);
279  if (pixa_display != NULL && pix_hline != NULL)
280  pixaAddPix(pixa_display, pix_hline, L_CLONE);
281  if (pix_vline != NULL && pix_hline != NULL) {
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(NULL, 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 != NULL && *pix_music_mask != NULL) {
295  if (pixa_display != NULL)
296  pixaAddPix(pixa_display, *pix_music_mask, L_CLONE);
297  pixSubtract(pix, pix, *pix_music_mask);
298  }
299  if (pixa_display != NULL)
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 != NULL) {
308 #if LIBLEPT_MINOR_VERSION >= 69 || LIBLEPT_MAJOR_VERSION > 1
309  pixaConvertToPdf(pixa_display, resolution, 1.0f, 0, 0, "LineFinding",
310  "vhlinefinding.pdf");
311 #endif
312  pixaDestroy(&pixa_display);
313  }
314 }
315 
316 // Converts the Boxa array to a list of C_BLOB, getting rid of severely
317 // overlapping outlines and those that are children of a bigger one.
318 // The output is a list of C_BLOBs that are owned by the list.
319 // The C_OUTLINEs in the C_BLOBs contain no outline data - just empty
320 // bounding boxes. The Boxa is consumed and destroyed.
321 void LineFinder::ConvertBoxaToBlobs(int image_width, int image_height,
322  Boxa** boxes, C_BLOB_LIST* blobs) {
323  C_OUTLINE_LIST outlines;
324  C_OUTLINE_IT ol_it = &outlines;
325  // Iterate the boxes to convert to outlines.
326  int nboxes = boxaGetCount(*boxes);
327  for (int i = 0; i < nboxes; ++i) {
328  l_int32 x, y, width, height;
329  boxaGetBoxGeometry(*boxes, i, &x, &y, &width, &height);
330  // Make a C_OUTLINE from the leptonica box. This is a bit of a hack,
331  // as there is no outline, just a bounding box, but with some very
332  // small changes to coutln.cpp, it works nicely.
333  ICOORD top_left(x, y);
334  ICOORD bot_right(x + width, y + height);
335  CRACKEDGE startpt;
336  startpt.pos = top_left;
337  C_OUTLINE* outline = new C_OUTLINE(&startpt, top_left, bot_right, 0);
338  ol_it.add_after_then_move(outline);
339  }
340  // Use outlines_to_blobs to convert the outlines to blobs and find
341  // overlapping and contained objects. The output list of blobs in the block
342  // has all the bad ones filtered out and deleted.
343  BLOCK block;
344  ICOORD page_tl(0, 0);
345  ICOORD page_br(image_width, image_height);
346  outlines_to_blobs(&block, page_tl, page_br, &outlines);
347  // Transfer the created blobs to the output list.
348  C_BLOB_IT blob_it(blobs);
349  blob_it.add_list_after(block.blob_list());
350  // The boxes aren't needed any more.
351  boxaDestroy(boxes);
352 }
353 
354 // Finds vertical line objects in pix_vline and removes the from src_pix.
355 // Uses the given resolution to determine size thresholds instead of any
356 // that may be present in the pix.
357 // The output vertical_x and vertical_y contain a sum of the output vectors,
358 // thereby giving the mean vertical direction.
359 // The output vectors are owned by the list and Frozen (cannot refit) by
360 // having no boxes, as there is no need to refit or merge separator lines.
361 // If no good lines are found, pix_vline is destroyed.
362 // None of the input pointers may be NULL, and if *pix_vline is NULL then
363 // the function does nothing.
364 void LineFinder::FindAndRemoveVLines(int resolution,
365  Pix* pix_intersections,
366  int* vertical_x, int* vertical_y,
367  Pix** pix_vline, Pix* pix_non_vline,
368  Pix* src_pix, TabVector_LIST* vectors) {
369  if (pix_vline == NULL || *pix_vline == NULL) return;
370  C_BLOB_LIST line_cblobs;
371  BLOBNBOX_LIST line_bblobs;
372  GetLineBoxes(false, *pix_vline, pix_intersections,
373  &line_cblobs, &line_bblobs);
374  int width = pixGetWidth(src_pix);
375  int height = pixGetHeight(src_pix);
376  ICOORD bleft(0, 0);
377  ICOORD tright(width, height);
378  FindLineVectors(bleft, tright, &line_bblobs, vertical_x, vertical_y, vectors);
379  if (!vectors->empty()) {
380  RemoveUnusedLineSegments(false, &line_bblobs, *pix_vline);
381  SubtractLinesAndResidue(*pix_vline, pix_non_vline, resolution, src_pix);
382  ICOORD vertical;
383  vertical.set_with_shrink(*vertical_x, *vertical_y);
384  TabVector::MergeSimilarTabVectors(vertical, vectors, NULL);
385  } else {
386  pixDestroy(pix_vline);
387  }
388 }
389 
390 // Finds horizontal line objects in pix_hline and removes them from src_pix.
391 // Uses the given resolution to determine size thresholds instead of any
392 // that may be present in the pix.
393 // The output vertical_x and vertical_y contain a sum of the output vectors,
394 // thereby giving the mean vertical direction.
395 // The output vectors are owned by the list and Frozen (cannot refit) by
396 // having no boxes, as there is no need to refit or merge separator lines.
397 // If no good lines are found, pix_hline is destroyed.
398 // None of the input pointers may be NULL, and if *pix_hline is NULL then
399 // the function does nothing.
400 void LineFinder::FindAndRemoveHLines(int resolution,
401  Pix* pix_intersections,
402  int vertical_x, int vertical_y,
403  Pix** pix_hline, Pix* pix_non_hline,
404  Pix* src_pix, TabVector_LIST* vectors) {
405  if (pix_hline == NULL || *pix_hline == NULL) return;
406  C_BLOB_LIST line_cblobs;
407  BLOBNBOX_LIST line_bblobs;
408  GetLineBoxes(true, *pix_hline, pix_intersections, &line_cblobs, &line_bblobs);
409  int width = pixGetWidth(src_pix);
410  int height = pixGetHeight(src_pix);
411  ICOORD bleft(0, 0);
412  ICOORD tright(height, width);
413  FindLineVectors(bleft, tright, &line_bblobs, &vertical_x, &vertical_y,
414  vectors);
415  if (!vectors->empty()) {
416  RemoveUnusedLineSegments(true, &line_bblobs, *pix_hline);
417  SubtractLinesAndResidue(*pix_hline, pix_non_hline, resolution, src_pix);
418  ICOORD vertical;
419  vertical.set_with_shrink(vertical_x, vertical_y);
420  TabVector::MergeSimilarTabVectors(vertical, vectors, NULL);
421  // Iterate the vectors to flip them. x and y were flipped for horizontal
422  // lines, so FindLineVectors can work just with the vertical case.
423  // See GetLineBoxes for more on the flip.
424  TabVector_IT h_it(vectors);
425  for (h_it.mark_cycle_pt(); !h_it.cycled_list(); h_it.forward()) {
426  h_it.data()->XYFlip();
427  }
428  } else {
429  pixDestroy(pix_hline);
430  }
431 }
432 
433 // Finds vertical lines in the given list of BLOBNBOXes. bleft and tright
434 // are the bounds of the image on which the input line_bblobs were found.
435 // The input line_bblobs list is const really.
436 // The output vertical_x and vertical_y are the total of all the vectors.
437 // The output list of TabVector makes no reference to the input BLOBNBOXes.
438 void LineFinder::FindLineVectors(const ICOORD& bleft, const ICOORD& tright,
439  BLOBNBOX_LIST* line_bblobs,
440  int* vertical_x, int* vertical_y,
441  TabVector_LIST* vectors) {
442  BLOBNBOX_IT bbox_it(line_bblobs);
443  int b_count = 0;
444  // Put all the blobs into the grid to find the lines, and move the blobs
445  // to the output lists.
446  AlignedBlob blob_grid(kLineFindGridSize, bleft, tright);
447  for (bbox_it.mark_cycle_pt(); !bbox_it.cycled_list(); bbox_it.forward()) {
448  BLOBNBOX* bblob = bbox_it.data();
450  bblob->set_left_rule(bleft.x());
451  bblob->set_right_rule(tright.x());
452  bblob->set_left_crossing_rule(bleft.x());
453  bblob->set_right_crossing_rule(tright.x());
454  blob_grid.InsertBBox(false, true, bblob);
455  ++b_count;
456  }
457  if (b_count == 0)
458  return;
459 
460  // Search the entire grid, looking for vertical line vectors.
461  BlobGridSearch lsearch(&blob_grid);
462  BLOBNBOX* bbox;
463  TabVector_IT vector_it(vectors);
464  *vertical_x = 0;
465  *vertical_y = 1;
466  lsearch.StartFullSearch();
467  while ((bbox = lsearch.NextFullSearch()) != NULL) {
468  if (bbox->left_tab_type() == TT_MAYBE_ALIGNED) {
469  const TBOX& box = bbox->bounding_box();
470  if (AlignedBlob::WithinTestRegion(2, box.left(), box.bottom()))
471  tprintf("Finding line vector starting at bbox (%d,%d)\n",
472  box.left(), box.bottom());
473  AlignedBlobParams align_params(*vertical_x, *vertical_y, box.width());
474  TabVector* vector = blob_grid.FindVerticalAlignment(align_params, bbox,
475  vertical_x,
476  vertical_y);
477  if (vector != NULL) {
478  vector->Freeze();
479  vector_it.add_to_end(vector);
480  }
481  }
482  }
483 }
484 
485 // Returns a Pix music mask if music is detected.
486 // Any vertical line that has at least 5 intersections in sufficient density
487 // is taken to be a bar. Bars are used as a seed and the entire touching
488 // component is added to the output music mask and subtracted from the lines.
489 // Returns NULL and does minimal work if no music is found.
490 static Pix* FilterMusic(int resolution, Pix* pix_closed,
491  Pix* pix_vline, Pix* pix_hline,
492  l_int32* v_empty, l_int32* h_empty) {
493  int max_stave_height = static_cast<int>(resolution * kMaxStaveHeight);
494  Pix* intersection_pix = pixAnd(NULL, pix_vline, pix_hline);
495  Boxa* boxa = pixConnComp(pix_vline, NULL, 8);
496  // Iterate over the boxes to find music bars.
497  int nboxes = boxaGetCount(boxa);
498  Pix* music_mask = NULL;
499  for (int i = 0; i < nboxes; ++i) {
500  Box* box = boxaGetBox(boxa, i, L_CLONE);
501  l_int32 x, y, box_width, box_height;
502  boxGetGeometry(box, &x, &y, &box_width, &box_height);
503  int joins = NumTouchingIntersections(box, intersection_pix);
504  // Test for the join density being at least 5 per max_stave_height,
505  // ie (joins-1)/box_height >= (5-1)/max_stave_height.
506  if (joins >= 5 && (joins - 1) * max_stave_height >= 4 * box_height) {
507  // This is a music bar. Add to the mask.
508  if (music_mask == NULL)
509  music_mask = pixCreate(pixGetWidth(pix_vline), pixGetHeight(pix_vline),
510  1);
511  pixSetInRect(music_mask, box);
512  }
513  boxDestroy(&box);
514  }
515  boxaDestroy(&boxa);
516  pixDestroy(&intersection_pix);
517  if (music_mask != NULL) {
518  // The mask currently contains just the bars. Use the mask as a seed
519  // and the pix_closed as the mask for a seedfill to get all the
520  // intersecting staves.
521  pixSeedfillBinary(music_mask, music_mask, pix_closed, 8);
522  // Filter out false positives. CCs in the music_mask should be the vast
523  // majority of the pixels in their bounding boxes, as we expect just a
524  // tiny amount of text, a few phrase marks, and crescendo etc left.
525  Boxa* boxa = pixConnComp(music_mask, NULL, 8);
526  // Iterate over the boxes to find music components.
527  int nboxes = boxaGetCount(boxa);
528  for (int i = 0; i < nboxes; ++i) {
529  Box* box = boxaGetBox(boxa, i, L_CLONE);
530  Pix* rect_pix = pixClipRectangle(music_mask, box, NULL);
531  l_int32 music_pixels;
532  pixCountPixels(rect_pix, &music_pixels, NULL);
533  pixDestroy(&rect_pix);
534  rect_pix = pixClipRectangle(pix_closed, box, NULL);
535  l_int32 all_pixels;
536  pixCountPixels(rect_pix, &all_pixels, NULL);
537  pixDestroy(&rect_pix);
538  if (music_pixels < kMinMusicPixelFraction * all_pixels) {
539  // False positive. Delete from the music mask.
540  pixClearInRect(music_mask, box);
541  }
542  boxDestroy(&box);
543  }
544  l_int32 no_remaining_music;
545  boxaDestroy(&boxa);
546  pixZero(music_mask, &no_remaining_music);
547  if (no_remaining_music) {
548  pixDestroy(&music_mask);
549  } else {
550  pixSubtract(pix_vline, pix_vline, music_mask);
551  pixSubtract(pix_hline, pix_hline, music_mask);
552  // We may have deleted all the lines
553  pixZero(pix_vline, v_empty);
554  pixZero(pix_hline, h_empty);
555  }
556  }
557  return music_mask;
558 }
559 
560 // Most of the heavy lifting of line finding. Given src_pix and its separate
561 // resolution, returns image masks:
562 // pix_vline candidate vertical lines.
563 // pix_non_vline pixels that didn't look like vertical lines.
564 // pix_hline candidate horizontal lines.
565 // pix_non_hline pixels that didn't look like horizontal lines.
566 // pix_intersections pixels where vertical and horizontal lines meet.
567 // pix_music_mask candidate music staves.
568 // This function promises to initialize all the output (2nd level) pointers,
569 // but any of the returns that are empty will be NULL on output.
570 // None of the input (1st level) pointers may be NULL except pix_music_mask,
571 // which will disable music detection, and pixa_display.
572 void LineFinder::GetLineMasks(int resolution, Pix* src_pix,
573  Pix** pix_vline, Pix** pix_non_vline,
574  Pix** pix_hline, Pix** pix_non_hline,
575  Pix** pix_intersections, Pix** pix_music_mask,
576  Pixa* pixa_display) {
577  int max_line_width = resolution / kThinLineFraction;
578  int min_line_length = resolution / kMinLineLengthFraction;
579  if (pixa_display != NULL) {
580  tprintf("Image resolution = %d, max line width = %d, min length=%d\n",
581  resolution, max_line_width, min_line_length);
582  }
583  int closing_brick = max_line_width / 3;
584 
585  // Close up small holes, making it less likely that false alarms are found
586  // in thickened text (as it will become more solid) and also smoothing over
587  // some line breaks and nicks in the edges of the lines.
588  Pix* pix_closed = pixCloseBrick(NULL, src_pix, closing_brick, closing_brick);
589  if (pixa_display != NULL)
590  pixaAddPix(pixa_display, pix_closed, L_CLONE);
591  // Open up with a big box to detect solid areas, which can then be subtracted.
592  // This is very generous and will leave in even quite wide lines.
593  Pix* pix_solid = pixOpenBrick(NULL, pix_closed, max_line_width,
594  max_line_width);
595  if (pixa_display != NULL)
596  pixaAddPix(pixa_display, pix_solid, L_CLONE);
597  Pix* pix_hollow = pixSubtract(NULL, pix_closed, pix_solid);
598  pixDestroy(&pix_solid);
599  // Now open up in both directions independently to find lines of at least
600  // 1 inch/kMinLineLengthFraction in length.
601  if (pixa_display != NULL)
602  pixaAddPix(pixa_display, pix_hollow, L_CLONE);
603  *pix_vline = pixOpenBrick(NULL, pix_hollow, 1, min_line_length);
604  *pix_hline = pixOpenBrick(NULL, pix_hollow, min_line_length, 1);
605  pixDestroy(&pix_hollow);
606  // Lines are sufficiently rare, that it is worth checking for a zero image.
607  l_int32 v_empty = 0;
608  l_int32 h_empty = 0;
609  pixZero(*pix_vline, &v_empty);
610  pixZero(*pix_hline, &h_empty);
611  if (pix_music_mask != NULL) {
612  if (!v_empty && !h_empty) {
613  *pix_music_mask = FilterMusic(resolution, pix_closed,
614  *pix_vline, *pix_hline,
615  &v_empty, &h_empty);
616  } else {
617  *pix_music_mask = NULL;
618  }
619  }
620  pixDestroy(&pix_closed);
621  Pix* pix_nonlines = NULL;
622  *pix_intersections = NULL;
623  Pix* extra_non_hlines = NULL;
624  if (!v_empty) {
625  // Subtract both line candidates from the source to get definite non-lines.
626  pix_nonlines = pixSubtract(NULL, src_pix, *pix_vline);
627  if (!h_empty) {
628  pixSubtract(pix_nonlines, pix_nonlines, *pix_hline);
629  // Intersections are a useful indicator for likelihood of being a line.
630  *pix_intersections = pixAnd(NULL, *pix_vline, *pix_hline);
631  // Candidate vlines are not hlines (apart from the intersections)
632  // and vice versa.
633  extra_non_hlines = pixSubtract(NULL, *pix_vline, *pix_intersections);
634  }
635  *pix_non_vline = pixErodeBrick(NULL, pix_nonlines, kMaxLineResidue, 1);
636  pixSeedfillBinary(*pix_non_vline, *pix_non_vline, pix_nonlines, 8);
637  if (!h_empty) {
638  // Candidate hlines are not vlines.
639  pixOr(*pix_non_vline, *pix_non_vline, *pix_hline);
640  pixSubtract(*pix_non_vline, *pix_non_vline, *pix_intersections);
641  }
642  if (!FilterFalsePositives(resolution, *pix_non_vline, *pix_intersections,
643  *pix_vline))
644  pixDestroy(pix_vline); // No candidates left.
645  } else {
646  // No vertical lines.
647  pixDestroy(pix_vline);
648  *pix_non_vline = NULL;
649  if (!h_empty) {
650  pix_nonlines = pixSubtract(NULL, src_pix, *pix_hline);
651  }
652  }
653  if (h_empty) {
654  pixDestroy(pix_hline);
655  *pix_non_hline = NULL;
656  if (v_empty) {
657  return;
658  }
659  } else {
660  *pix_non_hline = pixErodeBrick(NULL, pix_nonlines, 1, kMaxLineResidue);
661  pixSeedfillBinary(*pix_non_hline, *pix_non_hline, pix_nonlines, 8);
662  if (extra_non_hlines != NULL) {
663  pixOr(*pix_non_hline, *pix_non_hline, extra_non_hlines);
664  pixDestroy(&extra_non_hlines);
665  }
666  if (!FilterFalsePositives(resolution, *pix_non_hline, *pix_intersections,
667  *pix_hline))
668  pixDestroy(pix_hline); // No candidates left.
669  }
670  if (pixa_display != NULL) {
671  if (*pix_vline != NULL) pixaAddPix(pixa_display, *pix_vline, L_CLONE);
672  if (*pix_hline != NULL) pixaAddPix(pixa_display, *pix_hline, L_CLONE);
673  if (pix_nonlines != NULL) pixaAddPix(pixa_display, pix_nonlines, L_CLONE);
674  if (*pix_non_vline != NULL)
675  pixaAddPix(pixa_display, *pix_non_vline, L_CLONE);
676  if (*pix_non_hline != NULL)
677  pixaAddPix(pixa_display, *pix_non_hline, L_CLONE);
678  if (*pix_intersections != NULL)
679  pixaAddPix(pixa_display, *pix_intersections, L_CLONE);
680  if (pix_music_mask != NULL && *pix_music_mask != NULL)
681  pixaAddPix(pixa_display, *pix_music_mask, L_CLONE);
682  }
683  pixDestroy(&pix_nonlines);
684 }
685 
686 // Returns a list of boxes corresponding to the candidate line segments. Sets
687 // the line_crossings member of the boxes so we can later determin the number
688 // of intersections touched by a full line.
689 void LineFinder::GetLineBoxes(bool horizontal_lines,
690  Pix* pix_lines, Pix* pix_intersections,
691  C_BLOB_LIST* line_cblobs,
692  BLOBNBOX_LIST* line_bblobs) {
693  // Put a single pixel crack in every line at an arbitrary spacing,
694  // so they break up and the bounding boxes can be used to get the
695  // direction accurately enough without needing outlines.
696  int wpl = pixGetWpl(pix_lines);
697  int width = pixGetWidth(pix_lines);
698  int height = pixGetHeight(pix_lines);
699  l_uint32* data = pixGetData(pix_lines);
700  if (horizontal_lines) {
701  for (int y = 0; y < height; ++y, data += wpl) {
702  for (int x = kCrackSpacing; x < width; x += kCrackSpacing) {
703  CLEAR_DATA_BIT(data, x);
704  }
705  }
706  } else {
707  for (int y = kCrackSpacing; y < height; y += kCrackSpacing) {
708  memset(data + wpl * y, 0, wpl * sizeof(*data));
709  }
710  }
711  // Get the individual connected components
712  Boxa* boxa = pixConnComp(pix_lines, NULL, 8);
713  ConvertBoxaToBlobs(width, height, &boxa, line_cblobs);
714  // Make the BLOBNBOXes from the C_BLOBs.
715  C_BLOB_IT blob_it(line_cblobs);
716  BLOBNBOX_IT bbox_it(line_bblobs);
717  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
718  C_BLOB* cblob = blob_it.data();
719  BLOBNBOX* bblob = new BLOBNBOX(cblob);
720  bbox_it.add_to_end(bblob);
721  // Determine whether the line segment touches two intersections.
722  const TBOX& bbox = bblob->bounding_box();
723  Box* box = boxCreate(bbox.left(), bbox.bottom(),
724  bbox.width(), bbox.height());
725  bblob->set_line_crossings(NumTouchingIntersections(box, pix_intersections));
726  boxDestroy(&box);
727  // Transform the bounding box prior to finding lines. To save writing
728  // two line finders, flip x and y for horizontal lines and re-use the
729  // tab-stop detection code. For vertical lines we still have to flip the
730  // y-coordinates to switch from leptonica coords to tesseract coords.
731  if (horizontal_lines) {
732  // Note that we have Leptonica coords stored in a Tesseract box, so that
733  // bbox.bottom(), being the MIN y coord, is actually the top, so to get
734  // back to Leptonica coords in RemoveUnusedLineSegments, we have to
735  // use height - box.right() as the top, which looks very odd.
736  TBOX new_box(height - bbox.top(), bbox.left(),
737  height - bbox.bottom(), bbox.right());
738  bblob->set_bounding_box(new_box);
739  } else {
740  TBOX new_box(bbox.left(), height - bbox.top(),
741  bbox.right(), height - bbox.bottom());
742  bblob->set_bounding_box(new_box);
743  }
744  }
745 }
746 
747 } // namespace tesseract.
748