tesseract  5.0.0-alpha-619-ge9db
ocrblock.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: ocrblock.cpp (Formerly block.c)
3  * Description: BLOCK member functions and iterator functions.
4  * Author: Ray Smith
5  *
6  * (C) Copyright 1991, Hewlett-Packard Ltd.
7  ** Licensed under the Apache License, Version 2.0 (the "License");
8  ** you may not use this file except in compliance with the License.
9  ** You may obtain a copy of the License at
10  ** http://www.apache.org/licenses/LICENSE-2.0
11  ** Unless required by applicable law or agreed to in writing, software
12  ** distributed under the License is distributed on an "AS IS" BASIS,
13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  ** See the License for the specific language governing permissions and
15  ** limitations under the License.
16  *
17  **********************************************************************/
18 
19 #include "ocrblock.h"
20 #include <cstdlib>
21 #include <memory> // std::unique_ptr
22 #include "stepblob.h"
23 #include "tprintf.h"
24 
31 BLOCK::BLOCK(const char *name,
32  bool prop,
33  int16_t kern,
34  int16_t space,
35  int16_t xmin,
36  int16_t ymin, int16_t xmax,
37  int16_t ymax)
38  : pdblk(xmin, ymin, xmax, ymax),
39  filename(name),
40  re_rotation_(1.0f, 0.0f),
41  classify_rotation_(1.0f, 0.0f),
42  skew_(1.0f, 0.0f) {
43  ICOORDELT_IT left_it = &pdblk.leftside;
44  ICOORDELT_IT right_it = &pdblk.rightside;
45 
46  proportional = prop;
47  kerning = kern;
48  spacing = space;
49  font_class = -1; //not assigned
50  cell_over_xheight_ = 2.0f;
51  pdblk.hand_poly = nullptr;
52  left_it.set_to_list (&pdblk.leftside);
53  right_it.set_to_list (&pdblk.rightside);
54  //make default box
55  left_it.add_to_end (new ICOORDELT (xmin, ymin));
56  left_it.add_to_end (new ICOORDELT (xmin, ymax));
57  right_it.add_to_end (new ICOORDELT (xmax, ymin));
58  right_it.add_to_end (new ICOORDELT (xmax, ymax));
59 }
60 
67 static int decreasing_top_order(const void *row1, const void *row2) {
68  return (*reinterpret_cast<ROW* const*>(row2))->bounding_box().top() -
69  (*reinterpret_cast<ROW* const*>(row1))->bounding_box().top();
70 }
71 
72 
78 void BLOCK::rotate(const FCOORD& rotation) {
79  pdblk.poly_block()->rotate(rotation);
81 }
82 
83 // Returns the bounding box including the desired combination of upper and
84 // lower noise/diacritic elements.
85 TBOX BLOCK::restricted_bounding_box(bool upper_dots, bool lower_dots) const {
86  TBOX box;
87  // This is a read-only iteration of the rows in the block.
88  ROW_IT it(const_cast<ROW_LIST*>(&rows));
89  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
90  box += it.data()->restricted_bounding_box(upper_dots, lower_dots);
91  }
92  return box;
93 }
94 
104 }
105 
112 void BLOCK::sort_rows() { // order on "top"
113  ROW_IT row_it(&rows);
114 
115  row_it.sort (decreasing_top_order);
116 }
117 
118 
126 void BLOCK::compress() { // squash it up
127  #define ROW_SPACING 5
128 
129  ROW_IT row_it(&rows);
130  ROW *row;
131  ICOORD row_spacing (0, ROW_SPACING);
132 
133  ICOORDELT_IT icoordelt_it;
134 
135  sort_rows();
136 
139  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
140  row = row_it.data ();
141  row->move (pdblk.box.botleft () - row_spacing -
142  row->bounding_box ().topleft ());
143  pdblk.box += row->bounding_box ();
144  }
145 
146  pdblk.leftside.clear ();
147  icoordelt_it.set_to_list (&pdblk.leftside);
148  icoordelt_it.add_to_end (new ICOORDELT (pdblk.box.left (), pdblk.box.bottom ()));
149  icoordelt_it.add_to_end (new ICOORDELT (pdblk.box.left (), pdblk.box.top ()));
150  pdblk.rightside.clear ();
151  icoordelt_it.set_to_list (&pdblk.rightside);
152  icoordelt_it.add_to_end (new ICOORDELT (pdblk.box.right (), pdblk.box.bottom ()));
153  icoordelt_it.add_to_end (new ICOORDELT (pdblk.box.right (), pdblk.box.top ()));
154 }
155 
156 
164 void BLOCK::check_pitch() { // check prop
165  // tprintf("Missing FFT fixed pitch stuff!\n");
166  pitch = -1;
167 }
168 
169 
176 void BLOCK::compress( // squash it up
177  const ICOORD vec // and move
178  ) {
179  pdblk.box.move (vec);
180  compress();
181 }
182 
183 
190 void BLOCK::print( //print list of sides
191  FILE*,
192  bool dump
193 ) {
194  ICOORDELT_IT it = &pdblk.leftside; //iterator
195 
196  pdblk.box.print ();
197  tprintf ("Proportional= %s\n", proportional ? "TRUE" : "FALSE");
198  tprintf ("Kerning= %d\n", kerning);
199  tprintf ("Spacing= %d\n", spacing);
200  tprintf ("Fixed_pitch=%d\n", pitch);
201  tprintf ("Filename= %s\n", filename.c_str ());
202 
203  if (dump) {
204  tprintf ("Left side coords are:\n");
205  for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
206  tprintf ("(%d,%d) ", it.data ()->x (), it.data ()->y ());
207  tprintf ("\n");
208  tprintf ("Right side coords are:\n");
209  it.set_to_list (&pdblk.rightside);
210  for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
211  tprintf ("(%d,%d) ", it.data ()->x (), it.data ()->y ());
212  tprintf ("\n");
213  }
214 }
215 
222 BLOCK & BLOCK::operator= ( //assignment
223 const BLOCK & source //from this
224 ) {
225  this->ELIST_LINK::operator= (source);
226  pdblk = source.pdblk;
227  proportional = source.proportional;
228  kerning = source.kerning;
229  spacing = source.spacing;
230  filename = source.filename; //STRINGs assign ok
231  if (!rows.empty ())
232  rows.clear ();
233  re_rotation_ = source.re_rotation_;
234  classify_rotation_ = source.classify_rotation_;
235  skew_ = source.skew_;
236  return *this;
237 }
238 
239 // This function is for finding the approximate (horizontal) distance from
240 // the x-coordinate of the left edge of a symbol to the left edge of the
241 // text block which contains it. We are passed:
242 // segments - output of PB_LINE_IT::get_line() which contains x-coordinate
243 // intervals for the scan line going through the symbol's y-coordinate.
244 // Each element of segments is of the form (x()=start_x, y()=length).
245 // x - the x coordinate of the symbol we're interested in.
246 // margin - return value, the distance from x,y to the left margin of the
247 // block containing it.
248 // If all segments were to the right of x, we return false and 0.
249 static bool LeftMargin(ICOORDELT_LIST *segments, int x, int *margin) {
250  bool found = false;
251  *margin = 0;
252  if (segments->empty())
253  return found;
254  ICOORDELT_IT seg_it(segments);
255  for (seg_it.mark_cycle_pt(); !seg_it.cycled_list(); seg_it.forward()) {
256  int cur_margin = x - seg_it.data()->x();
257  if (cur_margin >= 0) {
258  if (!found) {
259  *margin = cur_margin;
260  } else if (cur_margin < *margin) {
261  *margin = cur_margin;
262  }
263  found = true;
264  }
265  }
266  return found;
267 }
268 
269 // This function is for finding the approximate (horizontal) distance from
270 // the x-coordinate of the right edge of a symbol to the right edge of the
271 // text block which contains it. We are passed:
272 // segments - output of PB_LINE_IT::get_line() which contains x-coordinate
273 // intervals for the scan line going through the symbol's y-coordinate.
274 // Each element of segments is of the form (x()=start_x, y()=length).
275 // x - the x coordinate of the symbol we're interested in.
276 // margin - return value, the distance from x,y to the right margin of the
277 // block containing it.
278 // If all segments were to the left of x, we return false and 0.
279 static bool RightMargin(ICOORDELT_LIST *segments, int x, int *margin) {
280  bool found = false;
281  *margin = 0;
282  if (segments->empty())
283  return found;
284  ICOORDELT_IT seg_it(segments);
285  for (seg_it.mark_cycle_pt(); !seg_it.cycled_list(); seg_it.forward()) {
286  int cur_margin = seg_it.data()->x() + seg_it.data()->y() - x;
287  if (cur_margin >= 0) {
288  if (!found) {
289  *margin = cur_margin;
290  } else if (cur_margin < *margin) {
291  *margin = cur_margin;
292  }
293  found = true;
294  }
295  }
296  return found;
297 }
298 
299 // Compute the distance from the left and right ends of each row to the
300 // left and right edges of the block's polyblock. Illustration:
301 // ____________________________ _______________________
302 // | Howdy neighbor! | |rectangular blocks look|
303 // | This text is written to| |more like stacked pizza|
304 // |illustrate how useful poly- |boxes. |
305 // |blobs are in ----------- ------ The polyblob|
306 // |dealing with| _________ |for a BLOCK rec-|
307 // |harder layout| /===========\ |ords the possibly|
308 // |issues. | | _ _ | |skewed pseudo-|
309 // | You see this| | |_| \|_| | |rectangular |
310 // |text is flowed| | } | |boundary that|
311 // |around a mid-| \ ____ | |forms the ideal-|
312 // |cloumn portrait._____ \ / __|ized text margin|
313 // | Polyblobs exist| \ / |from which we should|
314 // |to account for insets| | | |measure paragraph|
315 // |which make otherwise| ----- |indentation. |
316 // ----------------------- ----------------------
317 //
318 // If we identify a drop-cap, we measure the left margin for the lines
319 // below the first line relative to one space past the drop cap. The
320 // first line's margin and those past the drop cap area are measured
321 // relative to the enclosing polyblock.
322 //
323 // TODO(rays): Before this will work well, we'll need to adjust the
324 // polyblob tighter around the text near images, as in:
325 // UNLV_AUTO:mag.3G0 page 2
326 // UNLV_AUTO:mag.3G4 page 16
328  if (row_list()->empty() || row_list()->singleton()) {
329  return;
330  }
331 
332  // If Layout analysis was not called, default to this.
334  POLY_BLOCK *pblock = &rect_block;
335  if (pdblk.poly_block() != nullptr) {
336  pblock = pdblk.poly_block();
337  }
338 
339  // Step One: Determine if there is a drop-cap.
340  // TODO(eger): Fix up drop cap code for RTL languages.
341  ROW_IT r_it(row_list());
342  ROW *first_row = r_it.data();
343  ROW *second_row = r_it.data_relative(1);
344 
345  // initialize the bottom of a fictitious drop cap far above the first line.
346  int drop_cap_bottom = first_row->bounding_box().top() +
347  first_row->bounding_box().height();
348  int drop_cap_right = first_row->bounding_box().left();
349  int mid_second_line = second_row->bounding_box().top() -
350  second_row->bounding_box().height() / 2;
351  WERD_IT werd_it(r_it.data()->word_list()); // words of line one
352  if (!werd_it.empty()) {
353  C_BLOB_IT cblob_it(werd_it.data()->cblob_list());
354  for (cblob_it.mark_cycle_pt(); !cblob_it.cycled_list();
355  cblob_it.forward()) {
356  TBOX bbox = cblob_it.data()->bounding_box();
357  if (bbox.bottom() <= mid_second_line) {
358  // we found a real drop cap
359  first_row->set_has_drop_cap(true);
360  if (drop_cap_bottom > bbox.bottom())
361  drop_cap_bottom = bbox.bottom();
362  if (drop_cap_right < bbox.right())
363  drop_cap_right = bbox.right();
364  }
365  }
366  }
367 
368  // Step Two: Calculate the margin from the text of each row to the block
369  // (or drop-cap) boundaries.
370  PB_LINE_IT lines(pblock);
371  r_it.set_to_list(row_list());
372  for (r_it.mark_cycle_pt(); !r_it.cycled_list(); r_it.forward()) {
373  ROW *row = r_it.data();
374  TBOX row_box = row->bounding_box();
375  int left_y = row->base_line(row_box.left()) + row->x_height();
376  int left_margin;
377  const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments_left(
378  lines.get_line(left_y));
379  LeftMargin(segments_left.get(), row_box.left(), &left_margin);
380 
381  if (row_box.top() >= drop_cap_bottom) {
382  int drop_cap_distance = row_box.left() - row->space() - drop_cap_right;
383  if (drop_cap_distance < 0)
384  drop_cap_distance = 0;
385  if (drop_cap_distance < left_margin)
386  left_margin = drop_cap_distance;
387  }
388 
389  int right_y = row->base_line(row_box.right()) + row->x_height();
390  int right_margin;
391  const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments_right(
392  lines.get_line(right_y));
393  RightMargin(segments_right.get(), row_box.right(), &right_margin);
394  row->set_lmargin(left_margin);
395  row->set_rmargin(right_margin);
396  }
397 }
398 
399 /**********************************************************************
400  * PrintSegmentationStats
401  *
402  * Prints segmentation stats for the given block list.
403  **********************************************************************/
404 
405 void PrintSegmentationStats(BLOCK_LIST* block_list) {
406  int num_blocks = 0;
407  int num_rows = 0;
408  int num_words = 0;
409  int num_blobs = 0;
410  BLOCK_IT block_it(block_list);
411  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
412  BLOCK* block = block_it.data();
413  ++num_blocks;
414  ROW_IT row_it(block->row_list());
415  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
416  ++num_rows;
417  ROW* row = row_it.data();
418  // Iterate over all werds in the row.
419  WERD_IT werd_it(row->word_list());
420  for (werd_it.mark_cycle_pt(); !werd_it.cycled_list(); werd_it.forward()) {
421  WERD* werd = werd_it.data();
422  ++num_words;
423  num_blobs += werd->cblob_list()->length();
424  }
425  }
426  }
427  tprintf("Block list stats:\nBlocks = %d\nRows = %d\nWords = %d\nBlobs = %d\n",
428  num_blocks, num_rows, num_words, num_blobs);
429 }
430 
431 /**********************************************************************
432  * ExtractBlobsFromSegmentation
433  *
434  * Extracts blobs from the given block list and adds them to the output list.
435  * The block list must have been created by performing a page segmentation.
436  **********************************************************************/
437 
438 void ExtractBlobsFromSegmentation(BLOCK_LIST* blocks,
439  C_BLOB_LIST* output_blob_list) {
440  C_BLOB_IT return_list_it(output_blob_list);
441  BLOCK_IT block_it(blocks);
442  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
443  BLOCK* block = block_it.data();
444  ROW_IT row_it(block->row_list());
445  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
446  ROW* row = row_it.data();
447  // Iterate over all werds in the row.
448  WERD_IT werd_it(row->word_list());
449  for (werd_it.mark_cycle_pt(); !werd_it.cycled_list(); werd_it.forward()) {
450  WERD* werd = werd_it.data();
451  return_list_it.move_to_last();
452  return_list_it.add_list_after(werd->cblob_list());
453  return_list_it.move_to_last();
454  return_list_it.add_list_after(werd->rej_cblob_list());
455  }
456  }
457  }
458 }
459 
460 /**********************************************************************
461  * RefreshWordBlobsFromNewBlobs()
462  *
463  * Refreshes the words in the block_list by using blobs in the
464  * new_blobs list.
465  * Block list must have word segmentation in it.
466  * It consumes the blobs provided in the new_blobs list. The blobs leftover in
467  * the new_blobs list after the call weren't matched to any blobs of the words
468  * in block list.
469  * The output not_found_blobs is a list of blobs from the original segmentation
470  * in the block_list for which no corresponding new blobs were found.
471  **********************************************************************/
472 
473 void RefreshWordBlobsFromNewBlobs(BLOCK_LIST* block_list,
474  C_BLOB_LIST* new_blobs,
475  C_BLOB_LIST* not_found_blobs) {
476  // Now iterate over all the blobs in the segmentation_block_list_, and just
477  // replace the corresponding c-blobs inside the werds.
478  BLOCK_IT block_it(block_list);
479  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
480  BLOCK* block = block_it.data();
481  if (block->pdblk.poly_block() != nullptr && !block->pdblk.poly_block()->IsText())
482  continue; // Don't touch non-text blocks.
483  // Iterate over all rows in the block.
484  ROW_IT row_it(block->row_list());
485  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
486  ROW* row = row_it.data();
487  // Iterate over all werds in the row.
488  WERD_IT werd_it(row->word_list());
489  WERD_LIST new_words;
490  WERD_IT new_words_it(&new_words);
491  for (werd_it.mark_cycle_pt(); !werd_it.cycled_list(); werd_it.forward()) {
492  WERD* werd = werd_it.extract();
493  WERD* new_werd = werd->ConstructWerdWithNewBlobs(new_blobs,
494  not_found_blobs);
495  if (new_werd) {
496  // Insert this new werd into the actual row's werd-list. Remove the
497  // existing one.
498  new_words_it.add_after_then_move(new_werd);
499  delete werd;
500  } else {
501  // Reinsert the older word back, for lack of better options.
502  // This is critical since dropping the words messes up segmentation:
503  // eg. 1st word in the row might otherwise have W_FUZZY_NON turned on.
504  new_words_it.add_after_then_move(werd);
505  }
506  }
507  // Get rid of the old word list & replace it with the new one.
508  row->word_list()->clear();
509  werd_it.move_to_first();
510  werd_it.add_list_after(&new_words);
511  }
512  }
513 }
TBOX
Definition: cleanapi_test.cc:19
TBOX::move
void move(const ICOORD vec)
Definition: rect.h:156
ROW::base_line
float base_line(float xpos) const
Definition: ocrrow.h:58
ROW::set_has_drop_cap
void set_has_drop_cap(bool has)
Definition: ocrrow.h:107
BLOCK::check_pitch
void check_pitch()
check proportional
Definition: ocrblock.cpp:163
PDBLK::bounding_box
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
Definition: pdblock.h:58
ROW::set_rmargin
void set_rmargin(int16_t rmargin)
Definition: ocrrow.h:97
POLY_BLOCK::IsText
bool IsText() const
Definition: polyblk.h:62
BLOCK::row_list
ROW_LIST * row_list()
get rows
Definition: ocrblock.h:115
ICOORD
integer coordinate
Definition: points.h:30
BLOCK::sort_rows
void sort_rows()
decreasing y order
Definition: ocrblock.cpp:111
TBOX::print
void print() const
Definition: rect.h:277
TBOX::top
int16_t top() const
Definition: rect.h:57
PB_LINE_IT
Definition: polyblk.h:90
WERD::ConstructWerdWithNewBlobs
WERD * ConstructWerdWithNewBlobs(C_BLOB_LIST *all_blobs, C_BLOB_LIST *orphan_blobs)
Definition: werd.cpp:387
BLOCK::compute_row_margins
void compute_row_margins()
Definition: ocrblock.cpp:326
BLOCK::compress
void compress()
shrink white space
Definition: ocrblock.cpp:125
PDBLK::rightside
ICOORDELT_LIST rightside
right side vertices
Definition: pdblock.h:96
TBOX::topleft
ICOORD topleft() const
Definition: rect.h:99
FCOORD
Definition: points.h:187
PDBLK::leftside
ICOORDELT_LIST leftside
left side vertices
Definition: pdblock.h:95
BLOCK::operator=
BLOCK & operator=(const BLOCK &source)
Definition: ocrblock.cpp:221
ROW_SPACING
#define ROW_SPACING
TBOX::height
int16_t height() const
Definition: rect.h:107
WERD::cblob_list
C_BLOB_LIST * cblob_list()
Definition: werd.h:94
POLY_BLOCK::rotate
void rotate(FCOORD rotation)
Definition: polyblk.cpp:183
BLOCK::print
void print(FILE *fp, bool dump)
dump whole table
Definition: ocrblock.cpp:189
BLOCK
Definition: ocrblock.h:28
BLOCK::pdblk
PDBLK pdblk
Page Description Block.
Definition: ocrblock.h:189
ROW::x_height
float x_height() const
Definition: ocrrow.h:63
ROW::space
int32_t space() const
Definition: ocrrow.h:78
STRING::c_str
const char * c_str() const
Definition: strngs.cpp:192
BLOCK::reflect_polygon_in_y_axis
void reflect_polygon_in_y_axis()
Definition: ocrblock.cpp:100
PDBLK::poly_block
POLY_BLOCK * poly_block() const
Definition: pdblock.h:54
BLOCK::BLOCK
BLOCK()
Definition: ocrblock.h:33
stepblob.h
TBOX::move_bottom_edge
void move_bottom_edge(const int16_t y)
Definition: rect.h:136
TBOX::bottom
int16_t bottom() const
Definition: rect.h:64
ROW::bounding_box
TBOX bounding_box() const
Definition: ocrrow.h:87
BLOCK::restricted_bounding_box
TBOX restricted_bounding_box(bool upper_dots, bool lower_dots) const
Definition: ocrblock.cpp:84
ExtractBlobsFromSegmentation
void ExtractBlobsFromSegmentation(BLOCK_LIST *blocks, C_BLOB_LIST *output_blob_list)
Definition: ocrblock.cpp:435
ELIST_LINK::operator=
void operator=(const ELIST_LINK &)
Definition: elst.h:134
TBOX::botleft
const ICOORD & botleft() const
Definition: rect.h:91
tprintf.h
ROW::move
void move(const ICOORD vec)
Definition: ocrrow.cpp:142
ROW::set_lmargin
void set_lmargin(int16_t lmargin)
Definition: ocrrow.h:94
BLOCK::rotate
void rotate(const FCOORD &rotation)
Definition: ocrblock.cpp:77
POLY_BLOCK::bounding_box
TBOX * bounding_box()
Definition: polyblk.h:48
PrintSegmentationStats
void PrintSegmentationStats(BLOCK_LIST *block_list)
Definition: ocrblock.cpp:403
PDBLK::box
TBOX box
bounding box
Definition: pdblock.h:97
RefreshWordBlobsFromNewBlobs
void RefreshWordBlobsFromNewBlobs(BLOCK_LIST *block_list, C_BLOB_LIST *new_blobs, C_BLOB_LIST *not_found_blobs)
Definition: ocrblock.cpp:469
WERD
Definition: werd.h:55
TBOX::left
int16_t left() const
Definition: rect.h:71
ROW
Definition: ocrrow.h:35
ocrblock.h
PT_FLOWING_TEXT
Definition: capi.h:109
TBOX::right
int16_t right() const
Definition: rect.h:78
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:34
POLY_BLOCK
Definition: polyblk.h:26
PB_LINE_IT::get_line
ICOORDELT_LIST * get_line(int16_t y)
Definition: polyblk.cpp:341
ICOORDELT
Definition: points.h:160
ROW::word_list
WERD_LIST * word_list()
Definition: ocrrow.h:54
WERD::rej_cblob_list
C_BLOB_LIST * rej_cblob_list()
Definition: werd.h:89
ELISTIZE
#define ELISTIZE(CLASSNAME)
Definition: elst.h:919
POLY_BLOCK::reflect_in_y_axis
void reflect_in_y_axis()
Definition: polyblk.cpp:207
TBOX
Definition: rect.h:33