Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
polyaprx.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: polyaprx.cpp (Formerly polygon.c)
3  * Description: Code for polygonal approximation from old edgeprog.
4  * Author: Ray Smith
5  * Created: Thu Nov 25 11:42:04 GMT 1993
6  *
7  * (C) Copyright 1993, Hewlett-Packard Ltd.
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 "mfcpch.h"
21 #include <stdio.h>
22 #ifdef __UNIX__
23 #include <assert.h>
24 #endif
25 #define FASTEDGELENGTH 256
26 #include "polyaprx.h"
27 #include "params.h"
28 #include "tprintf.h"
29 
30 #define EXTERN
31 
32 EXTERN BOOL_VAR (poly_debug, FALSE, "Debug old poly");
34 "More accurate approx on wide things");
35 
36 
37 #define FIXED 4 /*OUTLINE point is fixed */
38 
39 #define RUNLENGTH 1 /*length of run */
40 
41 #define DIR 2 /*direction of run */
42 
43 #define FLAGS 0
44 
45 #define fixed_dist 20 //really an int_variable
46 #define approx_dist 15 //really an int_variable
47 
48 const int par1 = 4500 / (approx_dist * approx_dist);
49 const int par2 = 6750 / (approx_dist * approx_dist);
50 
51 
52 /**********************************************************************
53  * tesspoly_outline
54  *
55  * Approximate an outline from chain codes form using the old tess algorithm.
56  **********************************************************************/
57 
58 
60  EDGEPT *edgept; // converted steps
61  TBOX loop_box; // bounding box
62  inT32 area; // loop area
63  EDGEPT stack_edgepts[FASTEDGELENGTH]; // converted path
64  EDGEPT* edgepts = stack_edgepts;
65 
66  // Use heap memory if the stack buffer is not big enough.
67  if (c_outline->pathlength() > FASTEDGELENGTH)
68  edgepts = new EDGEPT[c_outline->pathlength()];
69 
70  loop_box = c_outline->bounding_box();
71  area = loop_box.height();
72  if (!poly_wide_objects_better && loop_box.width() > area)
73  area = loop_box.width();
74  area *= area;
75  edgept = edgesteps_to_edgepts(c_outline, edgepts);
76  fix2(edgepts, area);
77  edgept = poly2 (edgepts, area); // 2nd approximation.
78  EDGEPT* startpt = edgept;
79  EDGEPT* result = NULL;
80  EDGEPT* prev_result = NULL;
81  do {
82  EDGEPT* new_pt = new EDGEPT;
83  new_pt->pos = edgept->pos;
84  new_pt->prev = prev_result;
85  if (prev_result == NULL) {
86  result = new_pt;
87  } else {
88  prev_result->next = new_pt;
89  new_pt->prev = prev_result;
90  }
91  prev_result = new_pt;
92  edgept = edgept->next;
93  }
94  while (edgept != startpt);
95  prev_result->next = result;
96  result->prev = prev_result;
97  if (edgepts != stack_edgepts)
98  delete [] edgepts;
99  return TESSLINE::BuildFromOutlineList(result);
100 }
101 
102 
103 /**********************************************************************
104  * edgesteps_to_edgepts
105  *
106  * Convert a C_OUTLINE to EDGEPTs.
107  **********************************************************************/
108 
109 EDGEPT *
110 edgesteps_to_edgepts ( //convert outline
111 C_OUTLINE * c_outline, //input
112 EDGEPT edgepts[] //output is array
113 ) {
114  inT32 length; //steps in path
115  ICOORD pos; //current coords
116  inT32 stepindex; //current step
117  inT32 stepinc; //increment
118  inT32 epindex; //current EDGEPT
119  inT32 count; //repeated steps
120  ICOORD vec; //for this 8 step
121  ICOORD prev_vec;
122  inT8 epdir; //of this step
123  DIR128 prevdir; //prvious dir
124  DIR128 dir; //of this step
125 
126  pos = c_outline->start_pos (); //start of loop
127  length = c_outline->pathlength ();
128  stepindex = 0;
129  epindex = 0;
130  prevdir = -1;
131  count = 0;
132  do {
133  dir = c_outline->step_dir (stepindex);
134  vec = c_outline->step (stepindex);
135  if (stepindex < length - 1
136  && c_outline->step_dir (stepindex + 1) - dir == -32) {
137  dir += 128 - 16;
138  vec += c_outline->step (stepindex + 1);
139  stepinc = 2;
140  }
141  else
142  stepinc = 1;
143  if (count == 0) {
144  prevdir = dir;
145  prev_vec = vec;
146  }
147  if (prevdir.get_dir () != dir.get_dir ()) {
148  edgepts[epindex].pos.x = pos.x ();
149  edgepts[epindex].pos.y = pos.y ();
150  prev_vec *= count;
151  edgepts[epindex].vec.x = prev_vec.x ();
152  edgepts[epindex].vec.y = prev_vec.y ();
153  pos += prev_vec;
154  edgepts[epindex].flags[RUNLENGTH] = count;
155  edgepts[epindex].prev = &edgepts[epindex - 1];
156  edgepts[epindex].flags[FLAGS] = 0;
157  edgepts[epindex].next = &edgepts[epindex + 1];
158  prevdir += 64;
159  epdir = (DIR128) 0 - prevdir;
160  epdir >>= 4;
161  epdir &= 7;
162  edgepts[epindex].flags[DIR] = epdir;
163  epindex++;
164  prevdir = dir;
165  prev_vec = vec;
166  count = 1;
167  }
168  else
169  count++;
170  stepindex += stepinc;
171  }
172  while (stepindex < length);
173  edgepts[epindex].pos.x = pos.x ();
174  edgepts[epindex].pos.y = pos.y ();
175  prev_vec *= count;
176  edgepts[epindex].vec.x = prev_vec.x ();
177  edgepts[epindex].vec.y = prev_vec.y ();
178  pos += prev_vec;
179  edgepts[epindex].flags[RUNLENGTH] = count;
180  edgepts[epindex].flags[FLAGS] = 0;
181  edgepts[epindex].prev = &edgepts[epindex - 1];
182  edgepts[epindex].next = &edgepts[0];
183  prevdir += 64;
184  epdir = (DIR128) 0 - prevdir;
185  epdir >>= 4;
186  epdir &= 7;
187  edgepts[epindex].flags[DIR] = epdir;
188  edgepts[0].prev = &edgepts[epindex];
189  ASSERT_HOST (pos.x () == c_outline->start_pos ().x ()
190  && pos.y () == c_outline->start_pos ().y ());
191  return &edgepts[0];
192 }
193 
194 
195 /**********************************************************************
196  *fix2(start,area) fixes points on the outline according to a trial method*
197  **********************************************************************/
198 
199 //#pragma OPT_LEVEL 1 /*stop compiler bugs*/
200 
201 void fix2( //polygonal approx
202  EDGEPT *start, /*loop to approimate */
203  int area) {
204  register EDGEPT *edgept; /*current point */
205  register EDGEPT *edgept1;
206  register EDGEPT *loopstart; /*modified start of loop */
207  register EDGEPT *linestart; /*start of line segment */
208  register int dir1, dir2; /*directions of line */
209  register int sum1, sum2; /*lengths in dir1,dir2 */
210  int stopped; /*completed flag */
211  int fixed_count; //no of fixed points
212  int d01, d12, d23, gapmin;
213  TPOINT d01vec, d12vec, d23vec;
214  register EDGEPT *edgefix, *startfix;
215  register EDGEPT *edgefix0, *edgefix1, *edgefix2, *edgefix3;
216 
217  edgept = start; /*start of loop */
218  while (((edgept->flags[DIR] - edgept->prev->flags[DIR] + 1) & 7) < 3
219  && (dir1 =
220  (edgept->prev->flags[DIR] - edgept->next->flags[DIR]) & 7) != 2
221  && dir1 != 6)
222  edgept = edgept->next; /*find suitable start */
223  loopstart = edgept; /*remember start */
224 
225  stopped = 0; /*not finished yet */
226  edgept->flags[FLAGS] |= FIXED; /*fix it */
227  do {
228  linestart = edgept; /*possible start of line */
229  dir1 = edgept->flags[DIR]; /*first direction */
230  /*length of dir1 */
231  sum1 = edgept->flags[RUNLENGTH];
232  edgept = edgept->next;
233  dir2 = edgept->flags[DIR]; /*2nd direction */
234  /*length in dir2 */
235  sum2 = edgept->flags[RUNLENGTH];
236  if (((dir1 - dir2 + 1) & 7) < 3) {
237  while (edgept->prev->flags[DIR] == edgept->next->flags[DIR]) {
238  edgept = edgept->next; /*look at next */
239  if (edgept->flags[DIR] == dir1)
240  /*sum lengths */
241  sum1 += edgept->flags[RUNLENGTH];
242  else
243  sum2 += edgept->flags[RUNLENGTH];
244  }
245 
246  if (edgept == loopstart)
247  stopped = 1; /*finished */
248  if (sum2 + sum1 > 2
249  && linestart->prev->flags[DIR] == dir2
250  && (linestart->prev->flags[RUNLENGTH] >
251  linestart->flags[RUNLENGTH] || sum2 > sum1)) {
252  /*start is back one */
253  linestart = linestart->prev;
254  linestart->flags[FLAGS] |= FIXED;
255  }
256 
257  if (((edgept->next->flags[DIR] - edgept->flags[DIR] + 1) & 7) >= 3
258  || (edgept->flags[DIR] == dir1 && sum1 >= sum2)
259  || ((edgept->prev->flags[RUNLENGTH] < edgept->flags[RUNLENGTH]
260  || (edgept->flags[DIR] == dir2 && sum2 >= sum1))
261  && linestart->next != edgept))
262  edgept = edgept->next;
263  }
264  /*sharp bend */
265  edgept->flags[FLAGS] |= FIXED;
266  }
267  /*do whole loop */
268  while (edgept != loopstart && !stopped);
269 
270  edgept = start;
271  do {
272  if (((edgept->flags[RUNLENGTH] >= 8) &&
273  (edgept->flags[DIR] != 2) && (edgept->flags[DIR] != 6)) ||
274  ((edgept->flags[RUNLENGTH] >= 8) &&
275  ((edgept->flags[DIR] == 2) || (edgept->flags[DIR] == 6)))) {
276  edgept->flags[FLAGS] |= FIXED;
277  edgept1 = edgept->next;
278  edgept1->flags[FLAGS] |= FIXED;
279  }
280  edgept = edgept->next;
281  }
282  while (edgept != start);
283 
284  edgept = start;
285  do {
286  /*single fixed step */
287  if (edgept->flags[FLAGS] & FIXED && edgept->flags[RUNLENGTH] == 1
288  /*and neighours free */
289  && edgept->next->flags[FLAGS] & FIXED && (edgept->prev->flags[FLAGS] & FIXED) == 0
290  /*same pair of dirs */
291  && (edgept->next->next->flags[FLAGS] & FIXED) == 0 && edgept->prev->flags[DIR] == edgept->next->flags[DIR] && edgept->prev->prev->flags[DIR] == edgept->next->next->flags[DIR]
292  && ((edgept->prev->flags[DIR] - edgept->flags[DIR] + 1) & 7) < 3) {
293  /*unfix it */
294  edgept->flags[FLAGS] &= ~FIXED;
295  edgept->next->flags[FLAGS] &= ~FIXED;
296  }
297  edgept = edgept->next; /*do all points */
298  }
299  while (edgept != start); /*until finished */
300 
301  stopped = 0;
302  if (area < 450)
303  area = 450;
304 
305  gapmin = area * fixed_dist * fixed_dist / 44000;
306 
307  edgept = start;
308  fixed_count = 0;
309  do {
310  if (edgept->flags[FLAGS] & FIXED)
311  fixed_count++;
312  edgept = edgept->next;
313  }
314  while (edgept != start);
315  while ((edgept->flags[FLAGS] & FIXED) == 0)
316  edgept = edgept->next;
317  edgefix0 = edgept;
318 
319  edgept = edgept->next;
320  while ((edgept->flags[FLAGS] & FIXED) == 0)
321  edgept = edgept->next;
322  edgefix1 = edgept;
323 
324  edgept = edgept->next;
325  while ((edgept->flags[FLAGS] & FIXED) == 0)
326  edgept = edgept->next;
327  edgefix2 = edgept;
328 
329  edgept = edgept->next;
330  while ((edgept->flags[FLAGS] & FIXED) == 0)
331  edgept = edgept->next;
332  edgefix3 = edgept;
333 
334  startfix = edgefix2;
335 
336  do {
337  if (fixed_count <= 3)
338  break; //already too few
339  point_diff (d12vec, edgefix1->pos, edgefix2->pos);
340  d12 = LENGTH (d12vec);
341  // TODO(rays) investigate this change:
342  // Only unfix a point if it is part of a low-curvature section
343  // of outline and the total angle change of the outlines is
344  // less than 90 degrees, ie the scalar product is positive.
345  // if (d12 <= gapmin && SCALAR(edgefix0->vec, edgefix2->vec) > 0) {
346  if (d12 <= gapmin) {
347  point_diff (d01vec, edgefix0->pos, edgefix1->pos);
348  d01 = LENGTH (d01vec);
349  point_diff (d23vec, edgefix2->pos, edgefix3->pos);
350  d23 = LENGTH (d23vec);
351  if (d01 > d23) {
352  edgefix2->flags[FLAGS] &= ~FIXED;
353  fixed_count--;
354  }
355  else {
356  edgefix1->flags[FLAGS] &= ~FIXED;
357  fixed_count--;
358  edgefix1 = edgefix2;
359  }
360  }
361  else {
362  edgefix0 = edgefix1;
363  edgefix1 = edgefix2;
364  }
365  edgefix2 = edgefix3;
366  edgept = edgept->next;
367  while ((edgept->flags[FLAGS] & FIXED) == 0) {
368  if (edgept == startfix)
369  stopped = 1;
370  edgept = edgept->next;
371  }
372  edgefix3 = edgept;
373  edgefix = edgefix2;
374  }
375  while ((edgefix != startfix) && (!stopped));
376 }
377 
378 
379 //#pragma OPT_LEVEL 2 /*stop compiler bugs*/
380 
381 /**********************************************************************
382  *poly2(startpt,area,path) applies a second approximation to the outline
383  *using the points which have been fixed by the first approximation*
384  **********************************************************************/
385 
386 EDGEPT *poly2( //second poly
387  EDGEPT *startpt, /*start of loop */
388  int area /*area of blob box */
389  ) {
390  register EDGEPT *edgept; /*current outline point */
391  EDGEPT *loopstart; /*starting point */
392  register EDGEPT *linestart; /*start of line */
393  register int edgesum; /*correction count */
394 
395  if (area < 1200)
396  area = 1200; /*minimum value */
397 
398  loopstart = NULL; /*not found it yet */
399  edgept = startpt; /*start of loop */
400 
401  do {
402  /*current point fixed */
403  if (edgept->flags[FLAGS] & FIXED
404  /*and next not */
405  && (edgept->next->flags[FLAGS] & FIXED) == 0) {
406  loopstart = edgept; /*start of repoly */
407  break;
408  }
409  edgept = edgept->next; /*next point */
410  }
411  while (edgept != startpt); /*until found or finished */
412 
413  if (loopstart == NULL && (startpt->flags[FLAGS] & FIXED) == 0) {
414  /*fixed start of loop */
415  startpt->flags[FLAGS] |= FIXED;
416  loopstart = startpt; /*or start of loop */
417  }
418  if (loopstart) {
419  do {
420  edgept = loopstart; /*first to do */
421  do {
422  linestart = edgept;
423  edgesum = 0; /*sum of lengths */
424  do {
425  /*sum lengths */
426  edgesum += edgept->flags[RUNLENGTH];
427  edgept = edgept->next; /*move on */
428  }
429  while ((edgept->flags[FLAGS] & FIXED) == 0
430  && edgept != loopstart && edgesum < 126);
431  if (poly_debug)
432  tprintf
433  ("Poly2:starting at (%d,%d)+%d=(%d,%d),%d to (%d,%d)\n",
434  linestart->pos.x, linestart->pos.y, linestart->flags[DIR],
435  linestart->vec.x, linestart->vec.y, edgesum, edgept->pos.x,
436  edgept->pos.y);
437  /*reapproximate */
438  cutline(linestart, edgept, area);
439 
440  while ((edgept->next->flags[FLAGS] & FIXED)
441  && edgept != loopstart)
442  edgept = edgept->next; /*look for next non-fixed */
443  }
444  /*do all the loop */
445  while (edgept != loopstart);
446  edgesum = 0;
447  do {
448  if (edgept->flags[FLAGS] & FIXED)
449  edgesum++;
450  edgept = edgept->next;
451  }
452  //count fixed pts
453  while (edgept != loopstart);
454  if (edgesum < 3)
455  area /= 2; //must have 3 pts
456  }
457  while (edgesum < 3);
458  do {
459  linestart = edgept;
460  do {
461  edgept = edgept->next;
462  }
463  while ((edgept->flags[FLAGS] & FIXED) == 0);
464  linestart->next = edgept;
465  edgept->prev = linestart;
466  linestart->vec.x = edgept->pos.x - linestart->pos.x;
467  linestart->vec.y = edgept->pos.y - linestart->pos.y;
468  }
469  while (edgept != loopstart);
470  }
471  else
472  edgept = startpt; /*start of loop */
473 
474  loopstart = edgept; /*new start */
475  return loopstart; /*correct exit */
476 }
477 
478 
479 /**********************************************************************
480  *cutline(first,last,area) straightens out a line by partitioning
481  *and joining the ends by a straight line*
482  **********************************************************************/
483 
484 void cutline( //recursive refine
485  EDGEPT *first, /*ends of line */
486  EDGEPT *last,
487  int area /*area of object */
488  ) {
489  register EDGEPT *edge; /*current edge */
490  TPOINT vecsum; /*vector sum */
491  int vlen; /*approx length of vecsum */
492  TPOINT vec; /*accumulated vector */
493  EDGEPT *maxpoint; /*worst point */
494  int maxperp; /*max deviation */
495  register int perp; /*perp distance */
496  int ptcount; /*no of points */
497  int squaresum; /*sum of perps */
498 
499  edge = first; /*start of line */
500  if (edge->next == last)
501  return; /*simple line */
502 
503  /*vector sum */
504  vecsum.x = last->pos.x - edge->pos.x;
505  vecsum.y = last->pos.y - edge->pos.y;
506  if (vecsum.x == 0 && vecsum.y == 0) {
507  /*special case */
508  vecsum.x = -edge->prev->vec.x;
509  vecsum.y = -edge->prev->vec.y;
510  }
511  /*absolute value */
512  vlen = vecsum.x > 0 ? vecsum.x : -vecsum.x;
513  if (vecsum.y > vlen)
514  vlen = vecsum.y; /*maximum */
515  else if (-vecsum.y > vlen)
516  vlen = -vecsum.y; /*absolute value */
517 
518  vec.x = edge->vec.x; /*accumulated vector */
519  vec.y = edge->vec.y;
520  maxperp = 0; /*none yet */
521  squaresum = ptcount = 0;
522  edge = edge->next; /*move to actual point */
523  maxpoint = edge; /*in case there isn't one */
524  do {
525  perp = CROSS (vec, vecsum); /*get perp distance */
526  if (perp != 0) {
527  perp *= perp; /*squared deviation */
528  }
529  squaresum += perp; /*sum squares */
530  ptcount++; /*count points */
531  if (poly_debug)
532  tprintf ("Cutline:Final perp=%d\n", perp);
533  if (perp > maxperp) {
534  maxperp = perp;
535  maxpoint = edge; /*find greatest deviation */
536  }
537  vec.x += edge->vec.x; /*accumulate vectors */
538  vec.y += edge->vec.y;
539  edge = edge->next;
540  }
541  while (edge != last); /*test all line */
542 
543  perp = LENGTH (vecsum);
544  ASSERT_HOST (perp != 0);
545 
546  if (maxperp < 256 * MAX_INT16) {
547  maxperp <<= 8;
548  maxperp /= perp; /*true max perp */
549  }
550  else {
551  maxperp /= perp;
552  maxperp <<= 8; /*avoid overflow */
553  }
554  if (squaresum < 256 * MAX_INT16)
555  /*mean squared perp */
556  perp = (squaresum << 8) / (perp * ptcount);
557  else
558  /*avoid overflow */
559  perp = (squaresum / perp << 8) / ptcount;
560 
561  if (poly_debug)
562  tprintf ("Cutline:A=%d, max=%.2f(%.2f%%), msd=%.2f(%.2f%%)\n",
563  area, maxperp / 256.0, maxperp * 200.0 / area,
564  perp / 256.0, perp * 300.0 / area);
565  if (maxperp * par1 >= 10 * area || perp * par2 >= 10 * area || vlen >= 126) {
566  maxpoint->flags[FLAGS] |= FIXED;
567  /*partitions */
568  cutline(first, maxpoint, area);
569  cutline(maxpoint, last, area);
570  }
571 }