tesseract  5.0.0
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 
21 #include "stepblob.h"
22 #include "tprintf.h"
23 
24 #include <cstdlib>
25 #include <memory> // std::unique_ptr
26 
27 namespace tesseract {
28 
34 BLOCK::BLOCK(const char *name,
35  bool prop,
36  int16_t kern,
37  int16_t space,
38  TDimension xmin,
39  TDimension ymin,
40  TDimension xmax,
41  TDimension ymax)
42  : pdblk(xmin, ymin, xmax, ymax)
43  , filename(name)
44  , re_rotation_(1.0f, 0.0f)
45  , classify_rotation_(1.0f, 0.0f)
46  , skew_(1.0f, 0.0f) {
47  ICOORDELT_IT left_it = &pdblk.leftside;
48  ICOORDELT_IT right_it = &pdblk.rightside;
49 
50  proportional = prop;
51  kerning = kern;
52  spacing = space;
53  font_class = -1; // not assigned
54  cell_over_xheight_ = 2.0f;
55  pdblk.hand_poly = nullptr;
56  left_it.set_to_list(&pdblk.leftside);
57  right_it.set_to_list(&pdblk.rightside);
58  // make default box
59  left_it.add_to_end(new ICOORDELT(xmin, ymin));
60  left_it.add_to_end(new ICOORDELT(xmin, ymax));
61  right_it.add_to_end(new ICOORDELT(xmax, ymin));
62  right_it.add_to_end(new ICOORDELT(xmax, ymax));
63 }
64 
71 static int decreasing_top_order(const void *row1, const void *row2) {
72  return (*reinterpret_cast<ROW *const *>(row2))->bounding_box().top() -
73  (*reinterpret_cast<ROW *const *>(row1))->bounding_box().top();
74 }
75 
81 void BLOCK::rotate(const FCOORD &rotation) {
82  pdblk.poly_block()->rotate(rotation);
84 }
85 
86 // Returns the bounding box including the desired combination of upper and
87 // lower noise/diacritic elements.
88 TBOX BLOCK::restricted_bounding_box(bool upper_dots, bool lower_dots) const {
89  TBOX box;
90  // This is a read-only iteration of the rows in the block.
91  ROW_IT it(const_cast<ROW_LIST *>(&rows));
92  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
93  box += it.data()->restricted_bounding_box(upper_dots, lower_dots);
94  }
95  return box;
96 }
97 
107 }
108 
115 void BLOCK::sort_rows() { // order on "top"
116  ROW_IT row_it(&rows);
117 
118  row_it.sort(decreasing_top_order);
119 }
120 
128 void BLOCK::compress() { // squash it up
129 #define ROW_SPACING 5
130 
131  ROW_IT row_it(&rows);
132  ROW *row;
133  ICOORD row_spacing(0, ROW_SPACING);
134 
135  ICOORDELT_IT icoordelt_it;
136 
137  sort_rows();
138 
141  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
142  row = row_it.data();
143  row->move(pdblk.box.botleft() - row_spacing - row->bounding_box().topleft());
144  pdblk.box += row->bounding_box();
145  }
146 
147  pdblk.leftside.clear();
148  icoordelt_it.set_to_list(&pdblk.leftside);
149  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.left(), pdblk.box.bottom()));
150  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.left(), pdblk.box.top()));
151  pdblk.rightside.clear();
152  icoordelt_it.set_to_list(&pdblk.rightside);
153  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.right(), pdblk.box.bottom()));
154  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.right(), pdblk.box.top()));
155 }
156 
164 void BLOCK::check_pitch() { // check prop
165  // tprintf("Missing FFT fixed pitch stuff!\n");
166  pitch = -1;
167 }
168 
175 void BLOCK::compress( // squash it up
176  const ICOORD vec // and move
177 ) {
178  pdblk.box.move(vec);
179  compress();
180 }
181 
188 void BLOCK::print( // print list of sides
189  FILE *,
190  bool dump
191 ) {
192  ICOORDELT_IT it = &pdblk.leftside; // iterator
193 
194  pdblk.box.print();
195  tprintf("Proportional= %s\n", proportional ? "TRUE" : "FALSE");
196  tprintf("Kerning= %d\n", kerning);
197  tprintf("Spacing= %d\n", spacing);
198  tprintf("Fixed_pitch=%d\n", pitch);
199  tprintf("Filename= %s\n", filename.c_str());
200 
201  if (dump) {
202  tprintf("Left side coords are:\n");
203  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
204  tprintf("(%d,%d) ", it.data()->x(), it.data()->y());
205  }
206  tprintf("\n");
207  tprintf("Right side coords are:\n");
208  it.set_to_list(&pdblk.rightside);
209  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
210  tprintf("(%d,%d) ", it.data()->x(), it.data()->y());
211  }
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  }
234  re_rotation_ = source.re_rotation_;
235  classify_rotation_ = source.classify_rotation_;
236  skew_ = source.skew_;
237  return *this;
238 }
239 
240 // This function is for finding the approximate (horizontal) distance from
241 // the x-coordinate of the left edge of a symbol to the left edge of the
242 // text block which contains it. We are passed:
243 // segments - output of PB_LINE_IT::get_line() which contains x-coordinate
244 // intervals for the scan line going through the symbol's y-coordinate.
245 // Each element of segments is of the form (x()=start_x, y()=length).
246 // x - the x coordinate of the symbol we're interested in.
247 // margin - return value, the distance from x,y to the left margin of the
248 // block containing it.
249 // If all segments were to the right of x, we return false and 0.
250 static bool LeftMargin(ICOORDELT_LIST *segments, int x, int *margin) {
251  bool found = false;
252  *margin = 0;
253  if (segments->empty()) {
254  return found;
255  }
256  ICOORDELT_IT seg_it(segments);
257  for (seg_it.mark_cycle_pt(); !seg_it.cycled_list(); seg_it.forward()) {
258  int cur_margin = x - seg_it.data()->x();
259  if (cur_margin >= 0) {
260  if (!found) {
261  *margin = cur_margin;
262  } else if (cur_margin < *margin) {
263  *margin = cur_margin;
264  }
265  found = true;
266  }
267  }
268  return found;
269 }
270 
271 // This function is for finding the approximate (horizontal) distance from
272 // the x-coordinate of the right edge of a symbol to the right edge of the
273 // text block which contains it. We are passed:
274 // segments - output of PB_LINE_IT::get_line() which contains x-coordinate
275 // intervals for the scan line going through the symbol's y-coordinate.
276 // Each element of segments is of the form (x()=start_x, y()=length).
277 // x - the x coordinate of the symbol we're interested in.
278 // margin - return value, the distance from x,y to the right margin of the
279 // block containing it.
280 // If all segments were to the left of x, we return false and 0.
281 static bool RightMargin(ICOORDELT_LIST *segments, int x, int *margin) {
282  bool found = false;
283  *margin = 0;
284  if (segments->empty()) {
285  return found;
286  }
287  ICOORDELT_IT seg_it(segments);
288  for (seg_it.mark_cycle_pt(); !seg_it.cycled_list(); seg_it.forward()) {
289  int cur_margin = seg_it.data()->x() + seg_it.data()->y() - x;
290  if (cur_margin >= 0) {
291  if (!found) {
292  *margin = cur_margin;
293  } else if (cur_margin < *margin) {
294  *margin = cur_margin;
295  }
296  found = true;
297  }
298  }
299  return found;
300 }
301 
302 // Compute the distance from the left and right ends of each row to the
303 // left and right edges of the block's polyblock. Illustration:
304 // ____________________________ _______________________
305 // | Howdy neighbor! | |rectangular blocks look|
306 // | This text is written to| |more like stacked pizza|
307 // |illustrate how useful poly- |boxes. |
308 // |blobs are in ----------- ------ The polyblob|
309 // |dealing with| _________ |for a BLOCK rec-|
310 // |harder layout| /===========\ |ords the possibly|
311 // |issues. | | _ _ | |skewed pseudo-|
312 // | You see this| | |_| \|_| | |rectangular |
313 // |text is flowed| | } | |boundary that|
314 // |around a mid-| \ ____ | |forms the ideal-|
315 // |cloumn portrait._____ \ / __|ized text margin|
316 // | Polyblobs exist| \ / |from which we should|
317 // |to account for insets| | | |measure paragraph|
318 // |which make otherwise| ----- |indentation. |
319 // ----------------------- ----------------------
320 //
321 // If we identify a drop-cap, we measure the left margin for the lines
322 // below the first line relative to one space past the drop cap. The
323 // first line's margin and those past the drop cap area are measured
324 // relative to the enclosing polyblock.
325 //
326 // TODO(rays): Before this will work well, we'll need to adjust the
327 // polyblob tighter around the text near images, as in:
328 // UNLV_AUTO:mag.3G0 page 2
329 // UNLV_AUTO:mag.3G4 page 16
331  if (row_list()->empty() || row_list()->singleton()) {
332  return;
333  }
334 
335  // If Layout analysis was not called, default to this.
337  POLY_BLOCK *pblock = &rect_block;
338  if (pdblk.poly_block() != nullptr) {
339  pblock = pdblk.poly_block();
340  }
341 
342  // Step One: Determine if there is a drop-cap.
343  // TODO(eger): Fix up drop cap code for RTL languages.
344  ROW_IT r_it(row_list());
345  ROW *first_row = r_it.data();
346  ROW *second_row = r_it.data_relative(1);
347 
348  // initialize the bottom of a fictitious drop cap far above the first line.
349  int drop_cap_bottom = first_row->bounding_box().top() + first_row->bounding_box().height();
350  int drop_cap_right = first_row->bounding_box().left();
351  int mid_second_line = second_row->bounding_box().top() - second_row->bounding_box().height() / 2;
352  WERD_IT werd_it(r_it.data()->word_list()); // words of line one
353  if (!werd_it.empty()) {
354  C_BLOB_IT cblob_it(werd_it.data()->cblob_list());
355  for (cblob_it.mark_cycle_pt(); !cblob_it.cycled_list(); 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  }
363  if (drop_cap_right < bbox.right()) {
364  drop_cap_right = bbox.right();
365  }
366  }
367  }
368  }
369 
370  // Step Two: Calculate the margin from the text of each row to the block
371  // (or drop-cap) boundaries.
372  PB_LINE_IT lines(pblock);
373  r_it.set_to_list(row_list());
374  for (r_it.mark_cycle_pt(); !r_it.cycled_list(); r_it.forward()) {
375  ROW *row = r_it.data();
376  TBOX row_box = row->bounding_box();
377  int left_y = row->base_line(row_box.left()) + row->x_height();
378  int left_margin;
379  const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments_left(lines.get_line(left_y));
380  LeftMargin(segments_left.get(), row_box.left(), &left_margin);
381 
382  if (row_box.top() >= drop_cap_bottom) {
383  int drop_cap_distance = row_box.left() - row->space() - drop_cap_right;
384  if (drop_cap_distance < 0) {
385  drop_cap_distance = 0;
386  }
387  if (drop_cap_distance < left_margin) {
388  left_margin = drop_cap_distance;
389  }
390  }
391 
392  int right_y = row->base_line(row_box.right()) + row->x_height();
393  int right_margin;
394  const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments_right(lines.get_line(right_y));
395  RightMargin(segments_right.get(), row_box.right(), &right_margin);
396  row->set_lmargin(left_margin);
397  row->set_rmargin(right_margin);
398  }
399 }
400 
401 /**********************************************************************
402  * PrintSegmentationStats
403  *
404  * Prints segmentation stats for the given block list.
405  **********************************************************************/
406 
407 void PrintSegmentationStats(BLOCK_LIST *block_list) {
408  int num_blocks = 0;
409  int num_rows = 0;
410  int num_words = 0;
411  int num_blobs = 0;
412  BLOCK_IT block_it(block_list);
413  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
414  BLOCK *block = block_it.data();
415  ++num_blocks;
416  ROW_IT row_it(block->row_list());
417  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
418  ++num_rows;
419  ROW *row = row_it.data();
420  // Iterate over all werds in the row.
421  WERD_IT werd_it(row->word_list());
422  for (werd_it.mark_cycle_pt(); !werd_it.cycled_list(); werd_it.forward()) {
423  WERD *werd = werd_it.data();
424  ++num_words;
425  num_blobs += werd->cblob_list()->length();
426  }
427  }
428  }
429  tprintf("Block list stats:\nBlocks = %d\nRows = %d\nWords = %d\nBlobs = %d\n", num_blocks,
430  num_rows, num_words, num_blobs);
431 }
432 
433 /**********************************************************************
434  * ExtractBlobsFromSegmentation
435  *
436  * Extracts blobs from the given block list and adds them to the output list.
437  * The block list must have been created by performing a page segmentation.
438  **********************************************************************/
439 
440 void ExtractBlobsFromSegmentation(BLOCK_LIST *blocks, C_BLOB_LIST *output_blob_list) {
441  C_BLOB_IT return_list_it(output_blob_list);
442  BLOCK_IT block_it(blocks);
443  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
444  BLOCK *block = block_it.data();
445  ROW_IT row_it(block->row_list());
446  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
447  ROW *row = row_it.data();
448  // Iterate over all werds in the row.
449  WERD_IT werd_it(row->word_list());
450  for (werd_it.mark_cycle_pt(); !werd_it.cycled_list(); werd_it.forward()) {
451  WERD *werd = werd_it.data();
452  return_list_it.move_to_last();
453  return_list_it.add_list_after(werd->cblob_list());
454  return_list_it.move_to_last();
455  return_list_it.add_list_after(werd->rej_cblob_list());
456  }
457  }
458  }
459 }
460 
461 /**********************************************************************
462  * RefreshWordBlobsFromNewBlobs()
463  *
464  * Refreshes the words in the block_list by using blobs in the
465  * new_blobs list.
466  * Block list must have word segmentation in it.
467  * It consumes the blobs provided in the new_blobs list. The blobs leftover in
468  * the new_blobs list after the call weren't matched to any blobs of the words
469  * in block list.
470  * The output not_found_blobs is a list of blobs from the original segmentation
471  * in the block_list for which no corresponding new blobs were found.
472  **********************************************************************/
473 
474 void RefreshWordBlobsFromNewBlobs(BLOCK_LIST *block_list, 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  }
484  // Iterate over all rows in the block.
485  ROW_IT row_it(block->row_list());
486  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
487  ROW *row = row_it.data();
488  // Iterate over all werds in the row.
489  WERD_IT werd_it(row->word_list());
490  WERD_LIST new_words;
491  WERD_IT new_words_it(&new_words);
492  for (werd_it.mark_cycle_pt(); !werd_it.cycled_list(); werd_it.forward()) {
493  WERD *werd = werd_it.extract();
494  WERD *new_werd = werd->ConstructWerdWithNewBlobs(new_blobs, 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 }
514 
515 } // namespace tesseract
#define ROW_SPACING
@ TBOX
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
void RefreshWordBlobsFromNewBlobs(BLOCK_LIST *block_list, C_BLOB_LIST *new_blobs, C_BLOB_LIST *not_found_blobs)
Definition: ocrblock.cpp:474
void PrintSegmentationStats(BLOCK_LIST *block_list)
Definition: ocrblock.cpp:407
int16_t TDimension
Definition: tesstypes.h:32
@ PT_FLOWING_TEXT
Definition: publictypes.h:55
void ExtractBlobsFromSegmentation(BLOCK_LIST *blocks, C_BLOB_LIST *output_blob_list)
Definition: ocrblock.cpp:440
void print(FILE *fp, bool dump)
dump whole table
Definition: ocrblock.cpp:188
void rotate(const FCOORD &rotation)
Definition: ocrblock.cpp:81
BLOCK & operator=(const BLOCK &source)
Definition: ocrblock.cpp:222
void check_pitch()
check proportional
Definition: ocrblock.cpp:164
void reflect_polygon_in_y_axis()
Definition: ocrblock.cpp:104
void compute_row_margins()
Definition: ocrblock.cpp:330
PDBLK pdblk
Page Description Block.
Definition: ocrblock.h:185
bool prop() const
return proportional
Definition: ocrblock.h:71
void compress()
shrink white space
Definition: ocrblock.cpp:128
int16_t kern() const
return kerning
Definition: ocrblock.h:85
void compress(const ICOORD vec)
shrink white space and move by vector
Definition: ocrblock.cpp:175
TBOX restricted_bounding_box(bool upper_dots, bool lower_dots) const
Definition: ocrblock.cpp:88
int16_t space() const
return spacing
Definition: ocrblock.h:93
ROW_LIST * row_list()
get rows
Definition: ocrblock.h:111
void sort_rows()
decreasing y order
Definition: ocrblock.cpp:115
void set_lmargin(int16_t lmargin)
Definition: ocrrow.h:97
void move(const ICOORD vec)
Definition: ocrrow.cpp:148
WERD_LIST * word_list()
Definition: ocrrow.h:57
void set_rmargin(int16_t rmargin)
Definition: ocrrow.h:100
void set_has_drop_cap(bool has)
Definition: ocrrow.h:110
float x_height() const
Definition: ocrrow.h:66
float base_line(float xpos) const
Definition: ocrrow.h:61
TBOX bounding_box() const
Definition: ocrrow.h:90
int32_t space() const
Definition: ocrrow.h:81
ICOORDELT_LIST rightside
right side vertices
Definition: pdblock.h:111
POLY_BLOCK * poly_block() const
Definition: pdblock.h:59
TBOX box
bounding box
Definition: pdblock.h:112
POLY_BLOCK * hand_poly
weird as well
Definition: pdblock.h:109
ICOORDELT_LIST leftside
left side vertices
Definition: pdblock.h:110
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
Definition: pdblock.h:67
integer coordinate
Definition: points.h:36
TBOX * bounding_box()
Definition: polyblk.h:38
void rotate(FCOORD rotation)
Definition: polyblk.cpp:191
bool IsText() const
Definition: polyblk.h:52
ICOORDELT_LIST * get_line(TDimension y)
Definition: polyblk.cpp:337
TDimension left() const
Definition: rect.h:82
TDimension height() const
Definition: rect.h:118
void move(const ICOORD vec)
Definition: rect.h:170
const ICOORD & botleft() const
Definition: rect.h:102
void move_bottom_edge(const TDimension y)
Definition: rect.h:150
TDimension top() const
Definition: rect.h:68
ICOORD topleft() const
Definition: rect.h:110
void print() const
Definition: rect.h:289
TDimension right() const
Definition: rect.h:89
TDimension bottom() const
Definition: rect.h:75
C_BLOB_LIST * cblob_list()
Definition: werd.h:96
WERD * ConstructWerdWithNewBlobs(C_BLOB_LIST *all_blobs, C_BLOB_LIST *orphan_blobs)
Definition: werd.cpp:395
C_BLOB_LIST * rej_cblob_list()
Definition: werd.h:91
void operator=(const ELIST_LINK &)
Definition: elst.h:100