22#include "config_auto.h"
30#if defined(USE_OPENCL)
34#include "allheaders.h"
66static void RemoveUnusedLineSegments(
bool horizontal_lines,
67 BLOBNBOX_LIST* line_bblobs,
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()) {
75 Box* pixbox =
nullptr;
76 if (horizontal_lines) {
81 pixbox = boxCreate(box.
bottom(), height - box.
right(),
87 pixbox = boxCreate(box.
left(), height - box.
top(),
90 pixClearInRect(line_pix, pixbox);
100static void SubtractLinesAndResidue(Pix* line_pix, Pix* non_line_pix,
101 int resolution, Pix* src_pix) {
103 pixSubtract(src_pix, src_pix, line_pix);
105 Pix* residue_pix = pixSubtract(
nullptr, src_pix, non_line_pix);
107 Pix* fat_line_pix = pixDilateBrick(
nullptr, line_pix, 3, 3);
109 pixSeedfillBinary(fat_line_pix, fat_line_pix, residue_pix, 8);
111 pixSubtract(src_pix, src_pix, fat_line_pix);
112 pixDestroy(&fat_line_pix);
113 pixDestroy(&residue_pix);
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);
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)
134 pixDestroy(&dist_pix);
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);
153static int CountPixelsAdjacentToLine(
int line_width, Box* line_box,
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) {
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;
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;
168 Box* box = boxCreate(x, y, box_width, box_height);
169 Pix* rect_pix = pixClipRectangle(nonline_pix, box,
nullptr);
172 pixCountPixels(rect_pix, &result,
nullptr);
173 pixDestroy(&rect_pix);
186static int FilterFalsePositives(
int resolution, Pix* nonline_pix,
187 Pix* intersection_pix, Pix* line_pix) {
189 Pixa* pixa =
nullptr;
190 Boxa* boxa = pixConnComp(line_pix, &pixa, 8);
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;
205 box_width < min_thick_length && box_height < min_thick_length &&
211 (intersection_pix ==
nullptr ||
212 NumTouchingIntersections(box, intersection_pix) < 2)) {
214 int nonline_count = CountPixelsAdjacentToLine(max_width, box,
221 pixClearInRect(line_pix, box);
228 return remaining_boxes;
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");
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,
262 FindAndRemoveVLines(resolution, pix_intersections, vertical_x, vertical_y,
263 &pix_vline, pix_non_vline, pix, v_lines);
264 if (pix_hline !=
nullptr) {
266 if (pix_vline !=
nullptr)
267 pixAnd(pix_intersections, pix_vline, pix_hline);
269 pixDestroy(&pix_intersections);
270 if (!FilterFalsePositives(resolution, pix_non_hline, pix_intersections,
272 pixDestroy(&pix_hline);
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) {
284 pixAnd(pix_intersections, pix_vline, pix_hline);
287 Pix* pix_join_residue = pixDilateBrick(
nullptr, pix_intersections, 5, 5);
288 pixSeedfillBinary(pix_join_residue, pix_join_residue, pix, 8);
290 pixSubtract(pix, pix, pix_join_residue);
291 pixDestroy(&pix_join_residue);
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);
299 if (pixa_display !=
nullptr)
300 pixaAddPix(pixa_display, pix, L_CLONE);
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);
320 Boxa** boxes, C_BLOB_LIST* blobs) {
321 C_OUTLINE_LIST outlines;
322 C_OUTLINE_IT ol_it = &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);
332 ICOORD bot_right(x + width, y + height);
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);
343 ICOORD page_br(image_width, image_height);
346 C_BLOB_IT blob_it(blobs);
347 blob_it.add_list_after(block.
blob_list());
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);
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);
384 pixDestroy(pix_vline);
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);
410 ICOORD tright(height, width);
411 FindLineVectors(bleft, tright, &line_bblobs, &vertical_x, &vertical_y,
413 if (!vectors->empty()) {
414 RemoveUnusedLineSegments(
true, &line_bblobs, *pix_hline);
415 SubtractLinesAndResidue(*pix_hline, pix_non_hline, resolution, src_pix);
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();
427 pixDestroy(pix_hline);
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);
445 for (bbox_it.mark_cycle_pt(); !bbox_it.cycled_list(); bbox_it.forward()) {
452 blob_grid.InsertBBox(
false,
true, bblob);
461 TabVector_IT vector_it(vectors);
464 lsearch.StartFullSearch();
465 while ((bbox = lsearch.NextFullSearch()) !=
nullptr) {
469 tprintf(
"Finding line vector starting at bbox (%d,%d)\n",
471 AlignedBlobParams align_params(*vertical_x, *vertical_y, box.
width());
472 TabVector* vector = blob_grid.FindVerticalAlignment(align_params, bbox,
475 if (vector !=
nullptr) {
477 vector_it.add_to_end(vector);
488static Pix* FilterMusic(
int resolution, Pix* pix_closed,
489 Pix* pix_vline, Pix* pix_hline,
490 l_int32* v_empty, l_int32* h_empty) {
492 Pix* intersection_pix = pixAnd(
nullptr, pix_vline, pix_hline);
493 Boxa* boxa = pixConnComp(pix_vline,
nullptr, 8);
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);
504 if (joins >= 5 && (joins - 1) * max_stave_height >= 4 * box_height) {
506 if (music_mask ==
nullptr)
507 music_mask = pixCreate(pixGetWidth(pix_vline), pixGetHeight(pix_vline),
509 pixSetInRect(music_mask, box);
514 pixDestroy(&intersection_pix);
515 if (music_mask !=
nullptr) {
519 pixSeedfillBinary(music_mask, music_mask, pix_closed, 8);
523 Boxa* boxa = pixConnComp(music_mask,
nullptr, 8);
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);
534 pixCountPixels(rect_pix, &all_pixels,
nullptr);
535 pixDestroy(&rect_pix);
538 pixClearInRect(music_mask, box);
542 l_int32 no_remaining_music;
544 pixZero(music_mask, &no_remaining_music);
545 if (no_remaining_music) {
546 pixDestroy(&music_mask);
548 pixSubtract(pix_vline, pix_vline, music_mask);
549 pixSubtract(pix_hline, pix_hline, music_mask);
551 pixZero(pix_vline, v_empty);
552 pixZero(pix_hline, h_empty);
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;
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);
584 int closing_brick = max_line_width / 3;
588 if (OpenclDevice::selectedDeviceIsOpenCL()) {
590 int clStatus = OpenclDevice::initMorphCLAllocations(pixGetWpl(src_pix),
591 pixGetHeight(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);
603 pix_closed = pixCloseBrick(
nullptr, src_pix, closing_brick, closing_brick);
604 if (pixa_display !=
nullptr)
605 pixaAddPix(pixa_display, pix_closed, L_CLONE);
608 Pix* pix_solid = pixOpenBrick(
nullptr, pix_closed, 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);
614 pixDestroy(&pix_solid);
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);
623 pixDestroy(&pix_hollow);
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,
639 *pix_music_mask =
nullptr;
642 pixDestroy(&pix_closed);
643 Pix* pix_nonlines =
nullptr;
644 *pix_intersections =
nullptr;
645 Pix* extra_non_hlines =
nullptr;
648 pix_nonlines = pixSubtract(
nullptr, src_pix, *pix_vline);
650 pixSubtract(pix_nonlines, pix_nonlines, *pix_hline);
652 *pix_intersections = pixAnd(
nullptr, *pix_vline, *pix_hline);
655 extra_non_hlines = pixSubtract(
nullptr, *pix_vline, *pix_intersections);
657 *pix_non_vline = pixErodeBrick(
nullptr, pix_nonlines,
kMaxLineResidue, 1);
658 pixSeedfillBinary(*pix_non_vline, *pix_non_vline, pix_nonlines, 8);
661 pixOr(*pix_non_vline, *pix_non_vline, *pix_hline);
662 pixSubtract(*pix_non_vline, *pix_non_vline, *pix_intersections);
664 if (!FilterFalsePositives(resolution, *pix_non_vline, *pix_intersections,
666 pixDestroy(pix_vline);
669 pixDestroy(pix_vline);
670 *pix_non_vline =
nullptr;
672 pix_nonlines = pixSubtract(
nullptr, src_pix, *pix_hline);
676 pixDestroy(pix_hline);
677 *pix_non_hline =
nullptr;
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);
688 if (!FilterFalsePositives(resolution, *pix_non_hline, *pix_intersections,
690 pixDestroy(pix_hline);
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);
705 pixDestroy(&pix_nonlines);
711void LineFinder::GetLineBoxes(
bool horizontal_lines,
712 Pix* pix_lines, Pix* pix_intersections,
713 C_BLOB_LIST* line_cblobs,
714 BLOBNBOX_LIST* line_bblobs) {
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) {
725 CLEAR_DATA_BIT(data, x);
730 memset(data + wpl * y, 0, wpl *
sizeof(*data));
734 Boxa* boxa = pixConnComp(pix_lines,
nullptr, 8);
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();
742 bbox_it.add_to_end(bblob);
745 Box* box = boxCreate(bbox.
left(), bbox.
bottom(),
753 if (horizontal_lines) {
DLLSYM void tprintf(const char *format,...)
void outlines_to_blobs(BLOCK *block, ICOORD bleft, ICOORD tright, C_OUTLINE_LIST *outlines)
const double kMinMusicPixelFraction
const double kMaxStaveHeight
const int kCrackSpacing
Spacing of cracks across the page to break up tall vertical lines.
const double kThickLengthMultiple
const int kMinThickLineWidth
const double kMaxNonLineDensity
const int kMinLineLengthFraction
Denominator of resolution makes min pixels to demand line lengths to be.
const int kMaxLineResidue
const int kLineFindGridSize
Grid size used by line finder. Not very critical.
const int kThinLineFraction
Denominator of resolution makes max pixel width to allow thin lines.
GridSearch< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > BlobGridSearch
void set_left_tab_type(TabType new_type)
void set_right_crossing_rule(int new_right)
void set_left_rule(int new_left)
void set_line_crossings(int value)
TabType left_tab_type() const
void set_bounding_box(const TBOX &new_box)
const TBOX & bounding_box() const
void set_right_rule(int new_right)
void set_left_crossing_rule(int new_left)
C_BLOB_LIST * blob_list()
get blobs
void set_with_shrink(int x, int y)
Set from the given x,y, shrinking the vector to fit if needed.
int16_t x() const
access function
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)
static void ConvertBoxaToBlobs(int image_width, int image_height, Boxa **boxes, C_BLOB_LIST *blobs)
static void MergeSimilarTabVectors(const ICOORD &vertical, TabVector_LIST *vectors, BlobGrid *grid)