Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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");
33 EXTERN BOOL_VAR (poly_wide_objects_better, TRUE,
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
59 TESSLINE* ApproximateOutline(C_OUTLINE* c_outline) {
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 }