Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
cube_line_segmenter.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: cube_page_segmenter.cpp
3  * Description: Implementation of the Cube Page Segmenter Class
4  * Author: Ahmad Abdulkader
5  * Created: 2007
6  *
7  * (C) Copyright 2008, Google Inc.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  *
18  **********************************************************************/
19 
20 #include "cube_line_segmenter.h"
21 #include "ndminx.h"
22 
23 namespace tesseract {
24 // constants that worked for Arabic page segmenter
25 const int CubeLineSegmenter::kLineSepMorphMinHgt = 20;
26 const int CubeLineSegmenter::kHgtBins = 20;
27 const double CubeLineSegmenter::kMaxValidLineRatio = 3.2;
28 const int CubeLineSegmenter::kMaxConnCompHgt = 150;
29 const int CubeLineSegmenter::kMaxConnCompWid = 500;
30 const int CubeLineSegmenter::kMaxHorzAspectRatio = 50;
31 const int CubeLineSegmenter::kMaxVertAspectRatio = 20;
32 const int CubeLineSegmenter::kMinWid = 2;
33 const int CubeLineSegmenter::kMinHgt = 2;
34 const float CubeLineSegmenter::kMinValidLineHgtRatio = 2.5;
35 
37  cntxt_ = cntxt;
38  orig_img_ = img;
39  img_ = NULL;
40  lines_pixa_ = NULL;
41  init_ = false;
42  line_cnt_ = 0;
43  columns_ = NULL;
44  con_comps_ = NULL;
45  est_alef_hgt_ = 0.0;
46  est_dot_hgt_ = 0.0;
47 }
48 
50  if (img_ != NULL) {
51  pixDestroy(&img_);
52  img_ = NULL;
53  }
54 
55  if (lines_pixa_ != NULL) {
56  pixaDestroy(&lines_pixa_);
57  lines_pixa_ = NULL;
58  }
59 
60  if (con_comps_ != NULL) {
61  pixaDestroy(&con_comps_);
62  con_comps_ = NULL;
63  }
64 
65  if (columns_ != NULL) {
66  pixaaDestroy(&columns_);
67  columns_ = NULL;
68  }
69 }
70 
71 // compute validity ratio for a line
72 double CubeLineSegmenter::ValidityRatio(Pix *line_mask_pix, Box *line_box) {
73  return line_box->h / est_alef_hgt_;
74 }
75 
76 // validate line
77 bool CubeLineSegmenter::ValidLine(Pix *line_mask_pix, Box *line_box) {
78  double validity_ratio = ValidityRatio(line_mask_pix, line_box);
79 
80  return validity_ratio < kMaxValidLineRatio;
81 }
82 
83 // perform a vertical Closing with the specified threshold
84 // returning the resulting conn comps as a pixa
85 Pixa *CubeLineSegmenter::VerticalClosing(Pix *pix,
86  int threshold, Boxa **boxa) {
87  char sequence_str[16];
88 
89  // do the morphology
90  sprintf(sequence_str, "c100.%d", threshold);
91  Pix *morphed_pix = pixMorphCompSequence(pix, sequence_str, 0);
92  if (morphed_pix == NULL) {
93  return NULL;
94  }
95 
96  // get the resulting lines by computing concomps
97  Pixa *pixac;
98  (*boxa) = pixConnComp(morphed_pix, &pixac, 8);
99 
100  pixDestroy(&morphed_pix);
101 
102  if ((*boxa) == NULL) {
103  return NULL;
104  }
105 
106  return pixac;
107 }
108 
109 // do a desperate attempt at cracking lines
110 Pixa *CubeLineSegmenter::CrackLine(Pix *cracked_line_pix,
111  Box *cracked_line_box, int line_cnt) {
112  // create lines pixa array
113  Pixa **lines_pixa = new Pixa*[line_cnt];
114  if (lines_pixa == NULL) {
115  return NULL;
116  }
117 
118  memset(lines_pixa, 0, line_cnt * sizeof(*lines_pixa));
119 
120  // compute line conn comps
121  Pixa *line_con_comps_pix;
122  Boxa *line_con_comps = ComputeLineConComps(cracked_line_pix,
123  cracked_line_box, &line_con_comps_pix);
124 
125  if (line_con_comps == NULL) {
126  delete []lines_pixa;
127  return false;
128  }
129 
130  // assign each conn comp to the a line based on its centroid
131  for (int con = 0; con < line_con_comps->n; con++) {
132  Box *con_box = line_con_comps->box[con];
133  Pix *con_pix = line_con_comps_pix->pix[con];
134  int mid_y = (con_box->y - cracked_line_box->y) + (con_box->h / 2),
135  line_idx = MIN(line_cnt - 1,
136  (mid_y * line_cnt / cracked_line_box->h));
137 
138  // create the line if it has not been created?
139  if (lines_pixa[line_idx] == NULL) {
140  lines_pixa[line_idx] = pixaCreate(line_con_comps->n);
141  if (lines_pixa[line_idx] == NULL) {
142  delete []lines_pixa;
143  boxaDestroy(&line_con_comps);
144  pixaDestroy(&line_con_comps_pix);
145  return false;
146  }
147  }
148 
149  // add the concomp to the line
150  if (pixaAddPix(lines_pixa[line_idx], con_pix, L_CLONE) != 0 ||
151  pixaAddBox(lines_pixa[line_idx], con_box, L_CLONE)) {
152  delete []lines_pixa;
153  boxaDestroy(&line_con_comps);
154  pixaDestroy(&line_con_comps_pix);
155  }
156  }
157 
158  // create the lines pixa
159  Pixa *lines = pixaCreate(line_cnt);
160  bool success = true;
161 
162  // create and check the validity of the lines
163  for (int line = 0; line < line_cnt; line++) {
164  Pixa *line_pixa = lines_pixa[line];
165 
166  // skip invalid lines
167  if (line_pixa == NULL) {
168  continue;
169  }
170 
171  // merge the pix, check the validity of the line
172  // and add it to the lines pixa
173  Box *line_box;
174  Pix *line_pix = Pixa2Pix(line_pixa, &line_box);
175  if (line_pix == NULL ||
176  line_box == NULL ||
177  ValidLine(line_pix, line_box) == false ||
178  pixaAddPix(lines, line_pix, L_INSERT) != 0 ||
179  pixaAddBox(lines, line_box, L_INSERT) != 0) {
180  if (line_pix != NULL) {
181  pixDestroy(&line_pix);
182  }
183 
184  if (line_box != NULL) {
185  boxDestroy(&line_box);
186  }
187 
188  success = false;
189 
190  break;
191  }
192  }
193 
194  // cleanup
195  for (int line = 0; line < line_cnt; line++) {
196  if (lines_pixa[line] != NULL) {
197  pixaDestroy(&lines_pixa[line]);
198  }
199  }
200 
201  delete []lines_pixa;
202  boxaDestroy(&line_con_comps);
203  pixaDestroy(&line_con_comps_pix);
204 
205  if (success == false) {
206  pixaDestroy(&lines);
207  lines = NULL;
208  }
209 
210  return lines;
211 }
212 
213 // do a desperate attempt at cracking lines
214 Pixa *CubeLineSegmenter::CrackLine(Pix *cracked_line_pix,
215  Box *cracked_line_box) {
216  // estimate max line count
217  int max_line_cnt = static_cast<int>((cracked_line_box->h /
218  est_alef_hgt_) + 0.5);
219  if (max_line_cnt < 2) {
220  return NULL;
221  }
222 
223  for (int line_cnt = 2; line_cnt < max_line_cnt; line_cnt++) {
224  Pixa *lines = CrackLine(cracked_line_pix, cracked_line_box, line_cnt);
225  if (lines != NULL) {
226  return lines;
227  }
228  }
229 
230  return NULL;
231 }
232 
233 // split a line continously until valid or fail
234 Pixa *CubeLineSegmenter::SplitLine(Pix *line_mask_pix, Box *line_box) {
235  // clone the line mask
236  Pix *line_pix = pixClone(line_mask_pix);
237 
238  if (line_pix == NULL) {
239  return NULL;
240  }
241 
242  // AND with the image to get the actual line
243  pixRasterop(line_pix, 0, 0, line_pix->w, line_pix->h,
244  PIX_SRC & PIX_DST, img_, line_box->x, line_box->y);
245 
246  // continue to do rasterop morphology on the line until
247  // it splits to valid lines or we fail
248  int morph_hgt = kLineSepMorphMinHgt - 1,
249  best_threshold = kLineSepMorphMinHgt - 1,
250  max_valid_portion = 0;
251 
252  Boxa *boxa;
253  Pixa *pixac;
254 
255  do {
256  pixac = VerticalClosing(line_pix, morph_hgt, &boxa);
257 
258  // add the box offset to all the lines
259  // and check for the validity of each
260  int line,
261  valid_line_cnt = 0,
262  valid_portion = 0;
263 
264  for (line = 0; line < pixac->n; line++) {
265  boxa->box[line]->x += line_box->x;
266  boxa->box[line]->y += line_box->y;
267 
268  if (ValidLine(pixac->pix[line], boxa->box[line]) == true) {
269  // count valid lines
270  valid_line_cnt++;
271 
272  // and the valid portions
273  valid_portion += boxa->box[line]->h;
274  }
275  }
276 
277  // all the lines are valid
278  if (valid_line_cnt == pixac->n) {
279  boxaDestroy(&boxa);
280  pixDestroy(&line_pix);
281  return pixac;
282  }
283 
284  // a larger valid portion
285  if (valid_portion > max_valid_portion) {
286  max_valid_portion = valid_portion;
287  best_threshold = morph_hgt;
288  }
289 
290  boxaDestroy(&boxa);
291  pixaDestroy(&pixac);
292 
293  morph_hgt--;
294  }
295  while (morph_hgt > 0);
296 
297  // failed to break into valid lines
298  // attempt to crack the line
299  pixac = CrackLine(line_pix, line_box);
300  if (pixac != NULL) {
301  pixDestroy(&line_pix);
302  return pixac;
303  }
304 
305  // try to leverage any of the lines
306  // did the best threshold yield a non zero valid portion
307  if (max_valid_portion > 0) {
308  // use this threshold to break lines
309  pixac = VerticalClosing(line_pix, best_threshold, &boxa);
310 
311  // add the box offset to all the lines
312  // and check for the validity of each
313  for (int line = 0; line < pixac->n; line++) {
314  boxa->box[line]->x += line_box->x;
315  boxa->box[line]->y += line_box->y;
316 
317  // remove invalid lines from the pixa
318  if (ValidLine(pixac->pix[line], boxa->box[line]) == false) {
319  pixaRemovePix(pixac, line);
320  line--;
321  }
322  }
323 
324  boxaDestroy(&boxa);
325  pixDestroy(&line_pix);
326  return pixac;
327  }
328 
329  // last resort: attempt to crack the line
330  pixDestroy(&line_pix);
331 
332  return NULL;
333 }
334 
335 // Checks of a line is too small
336 bool CubeLineSegmenter::SmallLine(Box *line_box) {
337  return line_box->h <= (kMinValidLineHgtRatio * est_dot_hgt_);
338 }
339 
340 // Compute the connected components in a line
341 Boxa * CubeLineSegmenter::ComputeLineConComps(Pix *line_mask_pix,
342  Box *line_box,
343  Pixa **con_comps_pixa) {
344  // clone the line mask
345  Pix *line_pix = pixClone(line_mask_pix);
346 
347  if (line_pix == NULL) {
348  return NULL;
349  }
350 
351  // AND with the image to get the actual line
352  pixRasterop(line_pix, 0, 0, line_pix->w, line_pix->h,
353  PIX_SRC & PIX_DST, img_, line_box->x, line_box->y);
354 
355  // compute the connected components of the line to be merged
356  Boxa *line_con_comps = pixConnComp(line_pix, con_comps_pixa, 8);
357 
358  pixDestroy(&line_pix);
359 
360  // offset boxes by the bbox of the line
361  for (int con = 0; con < line_con_comps->n; con++) {
362  line_con_comps->box[con]->x += line_box->x;
363  line_con_comps->box[con]->y += line_box->y;
364  }
365 
366  return line_con_comps;
367 }
368 
369 // create a union of two arbitrary pix
370 Pix *CubeLineSegmenter::PixUnion(Pix *dest_pix, Box *dest_box,
371  Pix *src_pix, Box *src_box) {
372  // compute dimensions of union rect
373  BOX *union_box = boxBoundingRegion(src_box, dest_box);
374 
375  // create the union pix
376  Pix *union_pix = pixCreate(union_box->w, union_box->h, src_pix->d);
377  if (union_pix == NULL) {
378  return NULL;
379  }
380 
381  // blt the src and dest pix
382  pixRasterop(union_pix,
383  src_box->x - union_box->x, src_box->y - union_box->y,
384  src_box->w, src_box->h, PIX_SRC | PIX_DST, src_pix, 0, 0);
385 
386  pixRasterop(union_pix,
387  dest_box->x - union_box->x, dest_box->y - union_box->y,
388  dest_box->w, dest_box->h, PIX_SRC | PIX_DST, dest_pix, 0, 0);
389 
390  // replace the dest_box
391  *dest_box = *union_box;
392 
393  boxDestroy(&union_box);
394 
395  return union_pix;
396 }
397 
398 // create a union of a number of arbitrary pix
399 Pix *CubeLineSegmenter::Pixa2Pix(Pixa *pixa, Box **dest_box,
400  int start_pix, int pix_cnt) {
401  // compute union_box
402  int min_x = INT_MAX,
403  max_x = INT_MIN,
404  min_y = INT_MAX,
405  max_y = INT_MIN;
406 
407  for (int pix_idx = start_pix; pix_idx < (start_pix + pix_cnt); pix_idx++) {
408  Box *pix_box = pixa->boxa->box[pix_idx];
409 
410  UpdateRange(pix_box->x, pix_box->x + pix_box->w, &min_x, &max_x);
411  UpdateRange(pix_box->y, pix_box->y + pix_box->h, &min_y, &max_y);
412  }
413 
414  (*dest_box) = boxCreate(min_x, min_y, max_x - min_x, max_y - min_y);
415  if ((*dest_box) == NULL) {
416  return false;
417  }
418 
419  // create the union pix
420  Pix *union_pix = pixCreate((*dest_box)->w, (*dest_box)->h, img_->d);
421  if (union_pix == NULL) {
422  boxDestroy(dest_box);
423  return false;
424  }
425 
426  // create a pix corresponding to the union of all pixs
427  // blt the src and dest pix
428  for (int pix_idx = start_pix; pix_idx < (start_pix + pix_cnt); pix_idx++) {
429  Box *pix_box = pixa->boxa->box[pix_idx];
430  Pix *con_pix = pixa->pix[pix_idx];
431 
432  pixRasterop(union_pix,
433  pix_box->x - (*dest_box)->x, pix_box->y - (*dest_box)->y,
434  pix_box->w, pix_box->h, PIX_SRC | PIX_DST, con_pix, 0, 0);
435  }
436 
437  return union_pix;
438 }
439 
440 // create a union of a number of arbitrary pix
441 Pix *CubeLineSegmenter::Pixa2Pix(Pixa *pixa, Box **dest_box) {
442  return Pixa2Pix(pixa, dest_box, 0, pixa->n);
443 }
444 
445 // merges a number of lines into one line given a bounding box and a mask
446 bool CubeLineSegmenter::MergeLine(Pix *line_mask_pix, Box *line_box,
447  Pixa *lines, Boxaa *lines_con_comps) {
448  // compute the connected components of the lines to be merged
449  Pixa *small_con_comps_pix;
450  Boxa *small_line_con_comps = ComputeLineConComps(line_mask_pix,
451  line_box, &small_con_comps_pix);
452 
453  if (small_line_con_comps == NULL) {
454  return false;
455  }
456 
457  // for each connected component
458  for (int con = 0; con < small_line_con_comps->n; con++) {
459  Box *small_con_comp_box = small_line_con_comps->box[con];
460  int best_line = -1,
461  best_dist = INT_MAX,
462  small_box_right = small_con_comp_box->x + small_con_comp_box->w,
463  small_box_bottom = small_con_comp_box->y + small_con_comp_box->h;
464 
465  // for each valid line
466  for (int line = 0; line < lines->n; line++) {
467  if (SmallLine(lines->boxa->box[line]) == true) {
468  continue;
469  }
470 
471  // for all the connected components in the line
472  Boxa *line_con_comps = lines_con_comps->boxa[line];
473 
474  for (int lcon = 0; lcon < line_con_comps->n; lcon++) {
475  Box *con_comp_box = line_con_comps->box[lcon];
476  int xdist,
477  ydist,
478  box_right = con_comp_box->x + con_comp_box->w,
479  box_bottom = con_comp_box->y + con_comp_box->h;
480 
481  xdist = MAX(small_con_comp_box->x, con_comp_box->x) -
482  MIN(small_box_right, box_right);
483 
484  ydist = MAX(small_con_comp_box->y, con_comp_box->y) -
485  MIN(small_box_bottom, box_bottom);
486 
487  // if there is an overlap in x-direction
488  if (xdist <= 0) {
489  if (best_line == -1 || ydist < best_dist) {
490  best_dist = ydist;
491  best_line = line;
492  }
493  }
494  }
495  }
496 
497  // if the distance is too big, do not merged
498  if (best_line != -1 && best_dist < est_alef_hgt_) {
499  // add the pix to the best line
500  Pix *new_line = PixUnion(lines->pix[best_line],
501  lines->boxa->box[best_line],
502  small_con_comps_pix->pix[con], small_con_comp_box);
503 
504  if (new_line == NULL) {
505  return false;
506  }
507 
508  pixDestroy(&lines->pix[best_line]);
509  lines->pix[best_line] = new_line;
510  }
511  }
512 
513  pixaDestroy(&small_con_comps_pix);
514  boxaDestroy(&small_line_con_comps);
515 
516  return true;
517 }
518 
519 // Creates new set of lines from the computed columns
520 bool CubeLineSegmenter::AddLines(Pixa *lines) {
521  // create an array that will hold the bounding boxes
522  // of the concomps belonging to each line
523  Boxaa *lines_con_comps = boxaaCreate(lines->n);
524  if (lines_con_comps == NULL) {
525  return false;
526  }
527 
528  for (int line = 0; line < lines->n; line++) {
529  // if the line is not valid
530  if (ValidLine(lines->pix[line], lines->boxa->box[line]) == false) {
531  // split it
532  Pixa *split_lines = SplitLine(lines->pix[line],
533  lines->boxa->box[line]);
534 
535  // remove the old line
536  if (pixaRemovePix(lines, line) != 0) {
537  return false;
538  }
539 
540  line--;
541 
542  if (split_lines == NULL) {
543  continue;
544  }
545 
546  // add the split lines instead and move the pointer
547  for (int s_line = 0; s_line < split_lines->n; s_line++) {
548  Pix *sp_line = pixaGetPix(split_lines, s_line, L_CLONE);
549  Box *sp_box = boxaGetBox(split_lines->boxa, s_line, L_CLONE);
550 
551  if (sp_line == NULL || sp_box == NULL) {
552  return false;
553  }
554 
555  // insert the new line
556  if (pixaInsertPix(lines, ++line, sp_line, sp_box) != 0) {
557  return false;
558  }
559  }
560 
561  // remove the split lines
562  pixaDestroy(&split_lines);
563  }
564  }
565 
566  // compute the concomps bboxes of each line
567  for (int line = 0; line < lines->n; line++) {
568  Boxa *line_con_comps = ComputeLineConComps(lines->pix[line],
569  lines->boxa->box[line], NULL);
570 
571  if (line_con_comps == NULL) {
572  return false;
573  }
574 
575  // insert it into the boxaa array
576  if (boxaaAddBoxa(lines_con_comps, line_con_comps, L_INSERT) != 0) {
577  return false;
578  }
579  }
580 
581  // post process the lines:
582  // merge the contents of "small" lines info legitimate lines
583  for (int line = 0; line < lines->n; line++) {
584  // a small line detected
585  if (SmallLine(lines->boxa->box[line]) == true) {
586  // merge its components to one of the valid lines
587  if (MergeLine(lines->pix[line], lines->boxa->box[line],
588  lines, lines_con_comps) == true) {
589  // remove the small line
590  if (pixaRemovePix(lines, line) != 0) {
591  return false;
592  }
593 
594  if (boxaaRemoveBoxa(lines_con_comps, line) != 0) {
595  return false;
596  }
597 
598  line--;
599  }
600  }
601  }
602 
603  boxaaDestroy(&lines_con_comps);
604 
605  // add the pix masks
606  if (pixaaAddPixa(columns_, lines, L_INSERT) != 0) {
607  return false;
608  }
609 
610  return true;
611 }
612 
613 // Index the specific pixa using RTL reading order
614 int *CubeLineSegmenter::IndexRTL(Pixa *pixa) {
615  int *pix_index = new int[pixa->n];
616  if (pix_index == NULL) {
617  return NULL;
618  }
619 
620  for (int pix = 0; pix < pixa->n; pix++) {
621  pix_index[pix] = pix;
622  }
623 
624  for (int ipix = 0; ipix < pixa->n; ipix++) {
625  for (int jpix = ipix + 1; jpix < pixa->n; jpix++) {
626  Box *ipix_box = pixa->boxa->box[pix_index[ipix]],
627  *jpix_box = pixa->boxa->box[pix_index[jpix]];
628 
629  // swap?
630  if ((ipix_box->x + ipix_box->w) < (jpix_box->x + jpix_box->w)) {
631  int temp = pix_index[ipix];
632  pix_index[ipix] = pix_index[jpix];
633  pix_index[jpix] = temp;
634  }
635  }
636  }
637 
638  return pix_index;
639 }
640 
641 // Performs line segmentation
642 bool CubeLineSegmenter::LineSegment() {
643  // Use full image morphology to find columns
644  // This only works for simple layouts where each column
645  // of text extends the full height of the input image.
646  Pix *pix_temp1 = pixMorphCompSequence(img_, "c5.500", 0);
647  if (pix_temp1 == NULL) {
648  return false;
649  }
650 
651  // Mask with a single component over each column
652  Pixa *pixam;
653  Boxa *boxa = pixConnComp(pix_temp1, &pixam, 8);
654 
655  if (boxa == NULL) {
656  return false;
657  }
658 
659  int init_morph_min_hgt = kLineSepMorphMinHgt;
660  char sequence_str[16];
661  sprintf(sequence_str, "c100.%d", init_morph_min_hgt);
662 
663  // Use selective region-based morphology to get the textline mask.
664  Pixa *pixad = pixaMorphSequenceByRegion(img_, pixam, sequence_str, 0, 0);
665  if (pixad == NULL) {
666  return false;
667  }
668 
669  // for all columns
670  int col_cnt = boxaGetCount(boxa);
671 
672  // create columns
673  columns_ = pixaaCreate(col_cnt);
674  if (columns_ == NULL) {
675  return false;
676  }
677 
678  // index columns based on readind order (RTL)
679  int *col_order = IndexRTL(pixad);
680  if (col_order == NULL) {
681  return false;
682  }
683 
684  line_cnt_ = 0;
685 
686  for (int col_idx = 0; col_idx < col_cnt; col_idx++) {
687  int col = col_order[col_idx];
688 
689  // get the pix and box corresponding to the column
690  Pix *pixt3 = pixaGetPix(pixad, col, L_CLONE);
691  if (pixt3 == NULL) {
692  return false;
693  }
694 
695  Box *col_box = pixad->boxa->box[col];
696 
697  Pixa *pixac;
698  Boxa *boxa2 = pixConnComp(pixt3, &pixac, 8);
699  if (boxa2 == NULL) {
700  return false;
701  }
702 
703  // offset the boxes by the column box
704  for (int line = 0; line < pixac->n; line++) {
705  pixac->boxa->box[line]->x += col_box->x;
706  pixac->boxa->box[line]->y += col_box->y;
707  }
708 
709  // add the lines
710  if (AddLines(pixac) == true) {
711  if (pixaaAddBox(columns_, col_box, L_CLONE) != 0) {
712  return false;
713  }
714  }
715 
716  pixDestroy(&pixt3);
717  boxaDestroy(&boxa2);
718 
719  line_cnt_ += columns_->pixa[col_idx]->n;
720  }
721 
722  pixaDestroy(&pixam);
723  pixaDestroy(&pixad);
724  boxaDestroy(&boxa);
725 
726  delete []col_order;
727  pixDestroy(&pix_temp1);
728 
729  return true;
730 }
731 
732 // Estimate the paramters of the font(s) used in the page
733 bool CubeLineSegmenter::EstimateFontParams() {
734  int hgt_hist[kHgtBins];
735  int max_hgt;
736  double mean_hgt;
737 
738  // init hgt histogram of concomps
739  memset(hgt_hist, 0, sizeof(hgt_hist));
740 
741  // compute max hgt
742  max_hgt = 0;
743 
744  for (int con = 0; con < con_comps_->n; con++) {
745  // skip conn comps that are too long or too wide
746  if (con_comps_->boxa->box[con]->h > kMaxConnCompHgt ||
747  con_comps_->boxa->box[con]->w > kMaxConnCompWid) {
748  continue;
749  }
750 
751  max_hgt = MAX(max_hgt, con_comps_->boxa->box[con]->h);
752  }
753 
754  if (max_hgt <= 0) {
755  return false;
756  }
757 
758  // init hgt histogram of concomps
759  memset(hgt_hist, 0, sizeof(hgt_hist));
760 
761  // compute histogram
762  mean_hgt = 0.0;
763  for (int con = 0; con < con_comps_->n; con++) {
764  // skip conn comps that are too long or too wide
765  if (con_comps_->boxa->box[con]->h > kMaxConnCompHgt ||
766  con_comps_->boxa->box[con]->w > kMaxConnCompWid) {
767  continue;
768  }
769 
770  int bin = static_cast<int>(kHgtBins * con_comps_->boxa->box[con]->h /
771  max_hgt);
772  bin = MIN(bin, kHgtBins - 1);
773  hgt_hist[bin]++;
774  mean_hgt += con_comps_->boxa->box[con]->h;
775  }
776 
777  mean_hgt /= con_comps_->n;
778 
779  // find the top 2 bins
780  int idx[kHgtBins];
781 
782  for (int bin = 0; bin < kHgtBins; bin++) {
783  idx[bin] = bin;
784  }
785 
786  for (int ibin = 0; ibin < 2; ibin++) {
787  for (int jbin = ibin + 1; jbin < kHgtBins; jbin++) {
788  if (hgt_hist[idx[ibin]] < hgt_hist[idx[jbin]]) {
789  int swap = idx[ibin];
790  idx[ibin] = idx[jbin];
791  idx[jbin] = swap;
792  }
793  }
794  }
795 
796  // emperically, we found out that the 2 highest freq bins correspond
797  // respectively to the dot and alef
798  est_dot_hgt_ = (1.0 * (idx[0] + 1) * max_hgt / kHgtBins);
799  est_alef_hgt_ = (1.0 * (idx[1] + 1) * max_hgt / kHgtBins);
800 
801  // as a sanity check the dot hgt must be significanly lower than alef
802  if (est_alef_hgt_ < (est_dot_hgt_ * 2)) {
803  // use max_hgt to estimate instead
804  est_alef_hgt_ = mean_hgt * 1.5;
805  est_dot_hgt_ = est_alef_hgt_ / 5.0;
806  }
807 
808  est_alef_hgt_ = MAX(est_alef_hgt_, est_dot_hgt_ * 4.0);
809 
810  return true;
811 }
812 
813 // clean up the image
814 Pix *CubeLineSegmenter::CleanUp(Pix *orig_img) {
815  // get rid of long horizontal lines
816  Pix *pix_temp0 = pixMorphCompSequence(orig_img, "o300.2", 0);
817  pixXor(pix_temp0, pix_temp0, orig_img);
818 
819  // get rid of long vertical lines
820  Pix *pix_temp1 = pixMorphCompSequence(pix_temp0, "o2.300", 0);
821  pixXor(pix_temp1, pix_temp1, pix_temp0);
822 
823  pixDestroy(&pix_temp0);
824 
825  // detect connected components
826  Pixa *con_comps;
827  Boxa *boxa = pixConnComp(pix_temp1, &con_comps, 8);
828  if (boxa == NULL) {
829  return NULL;
830  }
831 
832  // detect and remove suspicious conn comps
833  for (int con = 0; con < con_comps->n; con++) {
834  Box *box = boxa->box[con];
835 
836  // remove if suspc. conn comp
837  if ((box->w > (box->h * kMaxHorzAspectRatio)) ||
838  (box->h > (box->w * kMaxVertAspectRatio)) ||
839  (box->w < kMinWid && box->h < kMinHgt)) {
840  pixRasterop(pix_temp1, box->x, box->y, box->w, box->h,
841  PIX_SRC ^ PIX_DST, con_comps->pix[con], 0, 0);
842  }
843  }
844 
845  pixaDestroy(&con_comps);
846  boxaDestroy(&boxa);
847 
848  return pix_temp1;
849 }
850 
851 // Init the page segmenter
852 bool CubeLineSegmenter::Init() {
853  if (init_ == true) {
854  return true;
855  }
856 
857  if (orig_img_ == NULL) {
858  return false;
859  }
860 
861  // call the internal line segmentation
862  return FindLines();
863 }
864 
865 // return the pix mask and box of a specific line
866 Pix *CubeLineSegmenter::Line(int line, Box **line_box) {
867  if (init_ == false && Init() == false) {
868  return NULL;
869  }
870 
871  if (line < 0 || line >= line_cnt_) {
872  return NULL;
873  }
874 
875  (*line_box) = lines_pixa_->boxa->box[line];
876  return lines_pixa_->pix[line];
877 }
878 
879 // Implements a basic rudimentary layout analysis based on Leptonica
880 // works OK for Arabic. For other languages, the function TesseractPageAnalysis
881 // should be called instead.
882 bool CubeLineSegmenter::FindLines() {
883  // convert the image to gray scale if necessary
884  Pix *gray_scale_img = NULL;
885  if (orig_img_->d != 2 && orig_img_->d != 8) {
886  gray_scale_img = pixConvertTo8(orig_img_, false);
887  if (gray_scale_img == NULL) {
888  return false;
889  }
890  } else {
891  gray_scale_img = orig_img_;
892  }
893 
894  // threshold image
895  Pix *thresholded_img;
896  thresholded_img = pixThresholdToBinary(gray_scale_img, 128);
897  // free the gray scale image if necessary
898  if (gray_scale_img != orig_img_) {
899  pixDestroy(&gray_scale_img);
900  }
901  // bail-out if thresholding failed
902  if (thresholded_img == NULL) {
903  return false;
904  }
905 
906  // deskew
907  Pix *deskew_img = pixDeskew(thresholded_img, 2);
908  if (deskew_img == NULL) {
909  return false;
910  }
911 
912  pixDestroy(&thresholded_img);
913 
914  img_ = CleanUp(deskew_img);
915  pixDestroy(&deskew_img);
916  if (img_ == NULL) {
917  return false;
918  }
919 
920  pixDestroy(&deskew_img);
921 
922  // compute connected components
923  Boxa *boxa = pixConnComp(img_, &con_comps_, 8);
924  if (boxa == NULL) {
925  return false;
926  }
927 
928  boxaDestroy(&boxa);
929 
930  // estimate dot and alef hgts
931  if (EstimateFontParams() == false) {
932  return false;
933  }
934 
935  // perform line segmentation
936  if (LineSegment() == false) {
937  return false;
938  }
939 
940  // success
941  init_ = true;
942  return true;
943 }
944 
945 }