tesseract  5.0.0-alpha-619-ge9db
scanedg.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: scanedg.cpp (Formerly scanedge.c)
3  * Description: Raster scanning crack based edge extractor.
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 "scanedg.h"
20 
21 #include <memory> // std::unique_ptr
22 
23 #include "allheaders.h"
24 #include "edgloop.h"
25 
26 #define WHITE_PIX 1 /*thresholded colours */
27 #define BLACK_PIX 0
28 // Flips between WHITE_PIX and BLACK_PIX.
29 #define FLIP_COLOUR(pix) (1-(pix))
30 
31 /**********************************************************************
32  * block_edges
33  *
34  * Extract edges from a PDBLK.
35  **********************************************************************/
36 
37 void block_edges(Pix *t_pix, // thresholded image
38  PDBLK *block, // block in image
39  C_OUTLINE_IT* outline_it) {
40  ICOORD bleft; // bounding box
41  ICOORD tright;
42  BLOCK_LINE_IT line_it = block; // line iterator
43 
44  int width = pixGetWidth(t_pix);
45  int height = pixGetHeight(t_pix);
46  int wpl = pixGetWpl(t_pix);
47  // lines in progress
48  std::unique_ptr<CRACKEDGE*[]> ptrline(new CRACKEDGE*[width + 1]);
49  CRACKEDGE *free_cracks = nullptr;
50 
51  block->bounding_box(bleft, tright); // block box
52  ASSERT_HOST(tright.x() <= width);
53  ASSERT_HOST(tright.y() <= height);
54  int block_width = tright.x() - bleft.x();
55  for (int x = block_width; x >= 0; x--)
56  ptrline[x] = nullptr; // no lines in progress
57 
58  std::unique_ptr<uint8_t[]> bwline(new uint8_t[width]);
59 
60  const uint8_t margin = WHITE_PIX;
61 
62  for (int y = tright.y() - 1; y >= bleft.y() - 1; y--) {
63  if (y >= bleft.y() && y < tright.y()) {
64  // Get the binary pixels from the image.
65  l_uint32* line = pixGetData(t_pix) + wpl * (height - 1 - y);
66  for (int x = 0; x < block_width; ++x) {
67  bwline[x] = GET_DATA_BIT(line, x + bleft.x()) ^ 1;
68  }
69  make_margins(block, &line_it, bwline.get(), margin, bleft.x(), tright.x(), y);
70  } else {
71  memset(bwline.get(), margin, block_width * sizeof(bwline[0]));
72  }
73  line_edges(bleft.x(), y, block_width,
74  margin, bwline.get(), ptrline.get(), &free_cracks, outline_it);
75  }
76 
77  free_crackedges(free_cracks); // really free them
78 }
79 
80 
81 /**********************************************************************
82  * make_margins
83  *
84  * Get an image line and set to margin non-text pixels.
85  **********************************************************************/
86 
87 void make_margins( //get a line
88  PDBLK *block, //block in image
89  BLOCK_LINE_IT *line_it, //for old style
90  uint8_t *pixels, //pixels to strip
91  uint8_t margin, //white-out pixel
92  int16_t left, //block edges
93  int16_t right,
94  int16_t y //line coord
95  ) {
96  ICOORDELT_IT seg_it;
97  int32_t start; //of segment
98  int16_t xext; //of segment
99  int xindex; //index to pixel
100 
101  if (block->poly_block () != nullptr) {
102  std::unique_ptr<PB_LINE_IT> lines(new PB_LINE_IT (block->poly_block ()));
103  const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments(
104  lines->get_line(y));
105  if (!segments->empty ()) {
106  seg_it.set_to_list(segments.get());
107  seg_it.mark_cycle_pt ();
108  start = seg_it.data ()->x ();
109  xext = seg_it.data ()->y ();
110  for (xindex = left; xindex < right; xindex++) {
111  if (xindex >= start && !seg_it.cycled_list ()) {
112  xindex = start + xext - 1;
113  seg_it.forward ();
114  start = seg_it.data ()->x ();
115  xext = seg_it.data ()->y ();
116  }
117  else
118  pixels[xindex - left] = margin;
119  }
120  }
121  else {
122  for (xindex = left; xindex < right; xindex++)
123  pixels[xindex - left] = margin;
124  }
125  }
126  else {
127  start = line_it->get_line (y, xext);
128  for (xindex = left; xindex < start; xindex++)
129  pixels[xindex - left] = margin;
130  for (xindex = start + xext; xindex < right; xindex++)
131  pixels[xindex - left] = margin;
132  }
133 }
134 
135 /**********************************************************************
136  * line_edges
137  *
138  * Scan a line for edges and update the edges in progress.
139  * When edges close into loops, send them for approximation.
140  **********************************************************************/
141 
142 void line_edges(int16_t x, // coord of line start
143  int16_t y, // coord of line
144  int16_t xext, // width of line
145  uint8_t uppercolour, // start of prev line
146  uint8_t * bwpos, // thresholded line
147  CRACKEDGE ** prevline, // edges in progress
148  CRACKEDGE **free_cracks,
149  C_OUTLINE_IT* outline_it) {
150  CrackPos pos = {free_cracks, x, y };
151  int xmax; // max x coord
152  int prevcolour; // of previous pixel
153  CRACKEDGE *current; // current h edge
154  CRACKEDGE *newcurrent; // new h edge
155 
156  xmax = x + xext; // max allowable coord
157  prevcolour = uppercolour; // forced plain margin
158  current = nullptr; // nothing yet
159 
160  // do each pixel
161  for (; pos.x < xmax; pos.x++, prevline++) {
162  const int colour = *bwpos++; // current pixel
163  if (*prevline != nullptr) {
164  // changed above
165  // change colour
166  uppercolour = FLIP_COLOUR(uppercolour);
167  if (colour == prevcolour) {
168  if (colour == uppercolour) {
169  // finish a line
170  join_edges(current, *prevline, free_cracks, outline_it);
171  current = nullptr; // no edge now
172  } else {
173  // new horiz edge
174  current = h_edge(uppercolour - colour, *prevline, &pos);
175  }
176  *prevline = nullptr; // no change this time
177  } else {
178  if (colour == uppercolour)
179  *prevline = v_edge(colour - prevcolour, *prevline, &pos);
180  // 8 vs 4 connection
181  else if (colour == WHITE_PIX) {
182  join_edges(current, *prevline, free_cracks, outline_it);
183  current = h_edge(uppercolour - colour, nullptr, &pos);
184  *prevline = v_edge(colour - prevcolour, current, &pos);
185  } else {
186  newcurrent = h_edge(uppercolour - colour, *prevline, &pos);
187  *prevline = v_edge(colour - prevcolour, current, &pos);
188  current = newcurrent; // right going h edge
189  }
190  prevcolour = colour; // remember new colour
191  }
192  } else {
193  if (colour != prevcolour) {
194  *prevline = current = v_edge(colour - prevcolour, current, &pos);
195  prevcolour = colour;
196  }
197  if (colour != uppercolour)
198  current = h_edge(uppercolour - colour, current, &pos);
199  else
200  current = nullptr; // no edge now
201  }
202  }
203  if (current != nullptr) {
204  // out of block
205  if (*prevline != nullptr) { // got one to join to?
206  join_edges(current, *prevline, free_cracks, outline_it);
207  *prevline = nullptr; // tidy now
208  } else {
209  // fake vertical
210  *prevline = v_edge(FLIP_COLOUR(prevcolour)-prevcolour, current, &pos);
211  }
212  } else if (*prevline != nullptr) {
213  //continue fake
214  *prevline = v_edge(FLIP_COLOUR(prevcolour)-prevcolour, *prevline, &pos);
215  }
216 }
217 
218 
219 /**********************************************************************
220  * h_edge
221  *
222  * Create a new horizontal CRACKEDGE and join it to the given edge.
223  **********************************************************************/
224 
225 CRACKEDGE *h_edge(int sign, // sign of edge
226  CRACKEDGE* join, // edge to join to
227  CrackPos* pos) {
228  CRACKEDGE *newpt; // return value
229 
230  if (*pos->free_cracks != nullptr) {
231  newpt = *pos->free_cracks;
232  *pos->free_cracks = newpt->next; // get one fast
233  } else {
234  newpt = new CRACKEDGE;
235  }
236  newpt->pos.set_y(pos->y + 1); // coords of pt
237  newpt->stepy = 0; // edge is horizontal
238 
239  if (sign > 0) {
240  newpt->pos.set_x(pos->x + 1); // start location
241  newpt->stepx = -1;
242  newpt->stepdir = 0;
243  } else {
244  newpt->pos.set_x(pos->x); // start location
245  newpt->stepx = 1;
246  newpt->stepdir = 2;
247  }
248 
249  if (join == nullptr) {
250  newpt->next = newpt; // ptrs to other ends
251  newpt->prev = newpt;
252  } else {
253  if (newpt->pos.x() + newpt->stepx == join->pos.x()
254  && newpt->pos.y() == join->pos.y()) {
255  newpt->prev = join->prev; // update other ends
256  newpt->prev->next = newpt;
257  newpt->next = join; // join up
258  join->prev = newpt;
259  } else {
260  newpt->next = join->next; // update other ends
261  newpt->next->prev = newpt;
262  newpt->prev = join; // join up
263  join->next = newpt;
264  }
265  }
266  return newpt;
267 }
268 
269 
270 /**********************************************************************
271  * v_edge
272  *
273  * Create a new vertical CRACKEDGE and join it to the given edge.
274  **********************************************************************/
275 
276 CRACKEDGE *v_edge(int sign, // sign of edge
277  CRACKEDGE* join,
278  CrackPos* pos) {
279  CRACKEDGE *newpt; // return value
280 
281  if (*pos->free_cracks != nullptr) {
282  newpt = *pos->free_cracks;
283  *pos->free_cracks = newpt->next; // get one fast
284  } else {
285  newpt = new CRACKEDGE;
286  }
287  newpt->pos.set_x(pos->x); // coords of pt
288  newpt->stepx = 0; // edge is vertical
289 
290  if (sign > 0) {
291  newpt->pos.set_y(pos->y); // start location
292  newpt->stepy = 1;
293  newpt->stepdir = 3;
294  } else {
295  newpt->pos.set_y(pos->y + 1); // start location
296  newpt->stepy = -1;
297  newpt->stepdir = 1;
298  }
299 
300  if (join == nullptr) {
301  newpt->next = newpt; //ptrs to other ends
302  newpt->prev = newpt;
303  } else {
304  if (newpt->pos.x() == join->pos.x()
305  && newpt->pos.y() + newpt->stepy == join->pos.y()) {
306  newpt->prev = join->prev; // update other ends
307  newpt->prev->next = newpt;
308  newpt->next = join; // join up
309  join->prev = newpt;
310  } else {
311  newpt->next = join->next; // update other ends
312  newpt->next->prev = newpt;
313  newpt->prev = join; // join up
314  join->next = newpt;
315  }
316  }
317  return newpt;
318 }
319 
320 
321 /**********************************************************************
322  * join_edges
323  *
324  * Join 2 edges together. Send the outline for approximation when a
325  * closed loop is formed.
326  **********************************************************************/
327 
328 void join_edges(CRACKEDGE *edge1, // edges to join
329  CRACKEDGE *edge2, // no specific order
330  CRACKEDGE **free_cracks,
331  C_OUTLINE_IT* outline_it) {
332  if (edge1->pos.x() + edge1->stepx != edge2->pos.x()
333  || edge1->pos.y() + edge1->stepy != edge2->pos.y()) {
334  CRACKEDGE *tempedge = edge1;
335  edge1 = edge2; // swap around
336  edge2 = tempedge;
337  }
338 
339  if (edge1->next == edge2) {
340  // already closed
341  complete_edge(edge1, outline_it);
342  // attach freelist to end
343  edge1->prev->next = *free_cracks;
344  *free_cracks = edge1; // and free list
345  } else {
346  // update opposite ends
347  edge2->prev->next = edge1->next;
348  edge1->next->prev = edge2->prev;
349  edge1->next = edge2; // make joins
350  edge2->prev = edge1;
351  }
352 }
353 
354 
355 /**********************************************************************
356  * free_crackedges
357  *
358  * Really free the CRACKEDGEs by giving them back to delete.
359  **********************************************************************/
360 
361 void free_crackedges(CRACKEDGE *start) {
362  CRACKEDGE *current; // current edge to free
363  CRACKEDGE *next; // next one to free
364 
365  for (current = start; current != nullptr; current = next) {
366  next = current->next;
367  delete current; // delete them all
368  }
369 }
ICOORD::set_x
void set_x(int16_t xin)
rewrite function
Definition: points.h:60
CRACKEDGE::next
CRACKEDGE * next
Definition: crakedge.h:50
WHITE_PIX
#define WHITE_PIX
Definition: scanedg.cpp:25
PDBLK::bounding_box
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
Definition: pdblock.h:58
line_edges
void line_edges(int16_t x, int16_t y, int16_t xext, uint8_t uppercolour, uint8_t *bwpos, CRACKEDGE **prevline, CRACKEDGE **free_cracks, C_OUTLINE_IT *outline_it)
Definition: scanedg.cpp:138
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
v_edge
CRACKEDGE * v_edge(int sign, CRACKEDGE *join, CrackPos *pos)
Definition: scanedg.cpp:270
ICOORD
integer coordinate
Definition: points.h:30
CrackPos::x
int x
Definition: scanedg.h:30
BLOCK_LINE_IT::get_line
int16_t get_line(int16_t y, int16_t &xext)
Definition: pdblock.cpp:335
PB_LINE_IT
Definition: polyblk.h:90
free_crackedges
void free_crackedges(CRACKEDGE *start)
Definition: scanedg.cpp:353
CrackPos
Definition: scanedg.h:28
complete_edge
void complete_edge(CRACKEDGE *start, C_OUTLINE_IT *outline_it)
Definition: edgloop.cpp:33
FLIP_COLOUR
#define FLIP_COLOUR(pix)
Definition: scanedg.cpp:28
ICOORD::x
int16_t x() const
access function
Definition: points.h:51
ICOORD::set_y
void set_y(int16_t yin)
rewrite function
Definition: points.h:64
BLOCK_LINE_IT
rectangle iterator
Definition: pdblock.h:143
CRACKEDGE::stepx
int8_t stepx
Definition: crakedge.h:46
scanedg.h
PDBLK::poly_block
POLY_BLOCK * poly_block() const
Definition: pdblock.h:54
h_edge
CRACKEDGE * h_edge(int sign, CRACKEDGE *join, CrackPos *pos)
Definition: scanedg.cpp:220
make_margins
void make_margins(PDBLK *block, BLOCK_LINE_IT *line_it, uint8_t *pixels, uint8_t margin, int16_t left, int16_t right, int16_t y)
Definition: scanedg.cpp:84
block_edges
void block_edges(Pix *t_pix, PDBLK *block, C_OUTLINE_IT *outline_it)
Definition: scanedg.cpp:35
CRACKEDGE::pos
ICOORD pos
Definition: crakedge.h:45
PDBLK
page block
Definition: pdblock.h:30
CRACKEDGE::stepdir
int8_t stepdir
Definition: crakedge.h:48
CRACKEDGE
Definition: crakedge.h:25
CRACKEDGE::prev
CRACKEDGE * prev
Definition: crakedge.h:49
CrackPos::y
int y
Definition: scanedg.h:31
CRACKEDGE::stepy
int8_t stepy
Definition: crakedge.h:47
PB_LINE_IT::get_line
ICOORDELT_LIST * get_line(int16_t y)
Definition: polyblk.cpp:341
join_edges
void join_edges(CRACKEDGE *edge1, CRACKEDGE *edge2, CRACKEDGE **free_cracks, C_OUTLINE_IT *outline_it)
Definition: scanedg.cpp:321
edgloop.h
CrackPos::free_cracks
CRACKEDGE ** free_cracks
Definition: scanedg.h:29
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55