1 # include "bitmapConfig.h"
2
3 # include <stdlib.h>
4 # include "bmSegments.h"
5 # include "bmintern.h"
6 # include <appDebugon.h>
7
8 /************************************************************************/
9 /* */
10 /* Build an administration of the 'segments' in an image. */
11 /* */
12 /* All pixels in a segment have the same color, and the segment is */
13 /* connected. */
14 /* */
15 /************************************************************************/
16
17 typedef struct LookUp
18 {
19 int luX0;
20 int luXp;
21 SegmentEdge * lu_edge;
22 SegmentNode * lu_node;
23 int lu_use;
24 int lu_compid;
25 } LookUp;
26
27 typedef struct CompIndex
28 {
29 BitmapSegment * ci_compo;
30 int ci_count;
31 } CompIndex;
32
33 # define LU_UNSPEC 1
34 # define LU_ENDED 2
35 # define LU_EXTENDED 3
36 # define LU_MERGED 4
37
38 /************************************************************************/
39 /* */
40 /* Insert a node in the administration of a segment. */
41 /* */
42 /************************************************************************/
43
bmRememberSegmentNode(BitmapSegment * bs,SegmentNode * sn)44 static int bmRememberSegmentNode( BitmapSegment * bs,
45 SegmentNode * sn )
46 {
47 SegmentNode ** nw;
48 int row= sn->snY0;
49
50 nw= (SegmentNode **)realloc( bs->bsNodes,
51 ( bs->bsNodeCount+ 1 )* sizeof(SegmentNode *) );
52
53 if ( ! nw )
54 { XDEB(nw); return -1; }
55
56 bs->bsNodes= nw;
57 nw[bs->bsNodeCount++]= sn;
58
59 if ( bs->bsNodeCount <= 1 )
60 { bs->bsRect.drY0= bs->bsRect.drY1= row; }
61 else{
62 if ( bs->bsRect.drY0 > row )
63 { bs->bsRect.drY0 = row; }
64 if ( bs->bsRect.drY1 < row )
65 { bs->bsRect.drY1 = row; }
66 }
67
68 return 0;
69 }
70
71 /************************************************************************/
72 /* */
73 /* Insert an edge in the administration of a segment. */
74 /* */
75 /************************************************************************/
76
bmRememberSegmentEdge(BitmapSegment * bs,SegmentEdge * se)77 static int bmRememberSegmentEdge( BitmapSegment * bs,
78 SegmentEdge * se )
79 {
80 SegmentEdge ** nw;
81 int i;
82 DataRun * dr;
83
84 nw= (SegmentEdge **)realloc( bs->bsEdges,
85 ( bs->bsEdgeCount+ 1 )* sizeof(SegmentEdge *) );
86
87 if ( ! nw )
88 { XDEB(nw); return -1; }
89
90 bs->bsEdges= nw;
91 nw[bs->bsEdgeCount++]= se;
92
93 dr= se->seRuns;
94 if ( bs->bsEdgeCount <= 1 )
95 {
96 bs->bsRect.drX0= dr->drX0;
97 bs->bsRect.drX1= dr->drXp- 1;
98 }
99
100 for ( i= 0; i < se->seRunCount; dr++, i++ )
101 {
102 if ( bs->bsRect.drX0 > dr->drX0 )
103 { bs->bsRect.drX0 = dr->drX0; }
104 if ( bs->bsRect.drX1 < dr->drXp- 1 )
105 { bs->bsRect.drX1 = dr->drXp- 1; }
106 }
107
108 /*
109 appDebug( "........ [%4d..%4d x %4d..%4d]\n",
110 bs->bsRect.drX0, bs->bsRect.drX1,
111 bs->bsRect.drY0, bs->bsRect.drY1 );
112 */
113
114 return 0;
115 }
116
117 /************************************************************************/
118 /* */
119 /* Allocate a fresh node. */
120 /* */
121 /************************************************************************/
122
bmSegmentNode(BitmapSegment * bs,int row)123 static SegmentNode * bmSegmentNode( BitmapSegment * bs,
124 int row )
125 {
126 SegmentNode * sn;
127
128 sn= (SegmentNode *)malloc( sizeof(SegmentNode) );
129
130 if ( ! sn )
131 { XDEB(sn); return sn; }
132
133 sn->snDownEdges= (SegmentEdge **)0;
134 sn->snUpEdges= (SegmentEdge **)0;
135 sn->snUpEdgeCount= 0;
136 sn->snDownEdgeCount= 0;
137 sn->snY0= row;
138
139 if ( bs && bmRememberSegmentNode( bs, sn ) )
140 { free( sn ); return (SegmentNode *)0; }
141
142 return sn;
143 }
144
145 /************************************************************************/
146 /* */
147 /* Insert a new edge into a node. */
148 /* */
149 /************************************************************************/
150
bmConnectSegmentEdgeToNode(SegmentNode * sn,SegmentEdge * se,int up)151 static int bmConnectSegmentEdgeToNode( SegmentNode * sn,
152 SegmentEdge * se,
153 int up )
154 {
155 short int * pcount;
156 SegmentEdge *** pold;
157
158 unsigned int sz;
159 SegmentEdge ** nw;
160
161 if ( up )
162 { pcount= &sn->snUpEdgeCount; pold= &sn->snUpEdges; }
163 else{ pcount= &sn->snDownEdgeCount; pold= &sn->snDownEdges; }
164
165 sz= ( *pcount+ 1 )* sizeof(SegmentEdge *);
166 nw= (SegmentEdge **)realloc( *pold, sz );
167
168 if ( ! nw )
169 { XDEB(nw); return -1; }
170 *pold= nw;
171 nw[(*pcount)++]= se;
172
173 if ( up )
174 { se->seTo= sn; }
175 else{ se->seFrom= sn; }
176
177 return 0;
178 }
179
180 /************************************************************************/
181 /* */
182 /* Allocate an edge. Insert the first run. */
183 /* */
184 /* 1) To help subsequent realloc()s a little, more space than needed */
185 /* is claimed for the runs. */
186 /* */
187 /************************************************************************/
188
bmSegmentEdge(BitmapSegment * bs,SegmentNode * from,int x0,int xp)189 static SegmentEdge * bmSegmentEdge( BitmapSegment * bs,
190 SegmentNode * from,
191 int x0,
192 int xp )
193 {
194 SegmentEdge * se;
195
196 se= (SegmentEdge *)malloc( sizeof(SegmentEdge) );
197
198 if ( ! se )
199 { XDEB(se); return se; }
200
201 se->seRuns= (DataRun *)malloc( 5* sizeof(DataRun) );
202 if ( ! se->seRuns )
203 { free( se ); return (SegmentEdge *)0; }
204
205 se->seRuns->drX0= x0;
206 se->seRuns->drXp= xp;
207 se->seRuns->drRepeatCount= 1;
208
209 se->seRunCount= 1;
210 se->seFrom= from;
211 se->seTo= (SegmentNode *)0;
212
213 if ( bmRememberSegmentEdge( bs, se ) )
214 {
215 free( se->seRuns ); free( se );
216 return (SegmentEdge *)0;
217 }
218
219 if ( from && bmConnectSegmentEdgeToNode( from, se, 0 ) )
220 {
221 free( se->seRuns ); free( se );
222
223 if ( bs )
224 { bs->bsEdgeCount--; }
225 return (SegmentEdge *)0;
226 }
227
228 return se;
229 }
230
231 /************************************************************************/
232 /* */
233 /* Insert a run into an edge. */
234 /* */
235 /* NOTE */
236 /* 1) That the first run has been inserted at creation time, so no */
237 /* initial allocation of the array of runs is necessary. */
238 /* 2) To help subsequent realloc()s a little, more space than needed */
239 /* is claimed for the runs. */
240 /* */
241 /************************************************************************/
242
bmAddRunToSegmentEdge(BitmapSegment * bs,SegmentEdge * se,int x0,int xp)243 static int bmAddRunToSegmentEdge( BitmapSegment * bs,
244 SegmentEdge * se,
245 int x0,
246 int xp )
247 {
248 DataRun * dr;
249 int nrun;
250 unsigned sz;
251
252 if ( se->seRunCount > 0 )
253 {
254 dr= se->seRuns+ se->seRunCount- 1;
255
256 if ( dr->drX0 == x0 && dr->drXp == xp )
257 { dr->drRepeatCount++; return 0; }
258 }
259
260 if ( se->seRunCount % 5 )
261 { nrun= se->seRunCount+ 1; }
262 else{ nrun= se->seRunCount+ 5; }
263
264 /* 2 */
265 sz= nrun* sizeof(DataRun);
266 dr= (DataRun *)realloc( se->seRuns, sz );
267 if ( ! dr )
268 { LDEB(dr); return -1; }
269
270 se->seRuns= dr;
271 dr += se->seRunCount++;
272
273 dr->drX0= x0;
274 dr->drXp= xp;
275 dr->drRepeatCount= 1;
276
277 if ( bs->bsRect.drX0 > x0 )
278 { bs->bsRect.drX0 = x0; }
279 if ( bs->bsRect.drX1 < xp- 1 )
280 { bs->bsRect.drX1 = xp- 1; }
281
282 /*
283 appDebug( "........ [%4d..%4d x %4d..%4d]\n",
284 bs->bsRect.drX0, bs->bsRect.drX1,
285 bs->bsRect.drY0, bs->bsRect.drY1 );
286 */
287
288 return 0;
289 }
290
291 /************************************************************************/
292 /* */
293 /* Destroy a segemnt. */
294 /* */
295 /************************************************************************/
296
bmFreeEdge(SegmentEdge * se)297 static void bmFreeEdge( SegmentEdge * se )
298 {
299 if ( se->seRuns )
300 { free( se->seRuns ); }
301
302 free( se );
303 }
304
bmFreeNode(SegmentNode * sn)305 static void bmFreeNode( SegmentNode * sn )
306 {
307 if ( sn->snUpEdges )
308 { free( sn->snUpEdges ); }
309 if ( sn->snDownEdges )
310 { free( sn->snDownEdges ); }
311
312 free( sn );
313 }
314
bmFreeSegment(BitmapSegment * bs)315 void bmFreeSegment( BitmapSegment * bs )
316 {
317 int i;
318
319 for ( i= 0; i < bs->bsEdgeCount; i++ )
320 {
321 if ( bs->bsEdges[i] )
322 { bmFreeEdge( bs->bsEdges[i] ); }
323 }
324
325 for ( i= 0; i < bs->bsNodeCount; i++ )
326 {
327 if ( bs->bsNodes[i] )
328 { bmFreeNode( bs->bsNodes[i] ); }
329 }
330
331 if ( bs->bsEdges )
332 { free( bs->bsEdges ); }
333
334 if ( bs->bsNodes )
335 { free( bs->bsNodes ); }
336
337 free( bs );
338
339 return;
340 }
341
342 /************************************************************************/
343 /* */
344 /* Construct a new component. */
345 /* */
346 /************************************************************************/
347
bmNewSegment(void)348 static BitmapSegment * bmNewSegment( void )
349 {
350 BitmapSegment * bs;
351
352 bs= (BitmapSegment *)malloc( sizeof(BitmapSegment) );
353
354 if ( ! bs )
355 { XDEB(bs); return bs; }
356
357 bs->bsEdges= (SegmentEdge **) malloc( sizeof(SegmentEdge *) );
358 bs->bsNodes= (SegmentNode **) malloc( sizeof(SegmentNode *) );
359
360 if ( ! bs->bsNodes ||
361 ! bs->bsEdges )
362 {
363 XXDEB(bs->bsEdges,bs->bsNodes); bmFreeSegment( bs );
364 return (BitmapSegment *)0;
365 }
366
367 bs->bsRect.drX0= bs->bsRect.drX1= bs->bsRect.drY0= bs->bsRect.drY1= -1;
368
369 bs->bsNodeCount= bs->bsEdgeCount= 0;
370
371 return bs;
372 }
373
374 /************************************************************************/
375 /* */
376 /* Copy everything in one component to another one. */
377 /* */
378 /************************************************************************/
379
bmMoveComponentContents(BitmapSegment * to,BitmapSegment * from)380 static int bmMoveComponentContents( BitmapSegment * to,
381 BitmapSegment * from )
382 {
383 int i;
384
385 for ( i= 0; i < from->bsNodeCount; i++ )
386 {
387 if ( bmRememberSegmentNode( to, from->bsNodes[i] ) )
388 { LDEB(i); return -1; }
389
390 from->bsNodes[i]= (SegmentNode *)0;
391 }
392
393 for ( i= 0; i < from->bsEdgeCount; i++ )
394 {
395 if ( bmRememberSegmentEdge( to, from->bsEdges[i] ) )
396 { LDEB(i); return -1; }
397
398 from->bsEdges[i]= (SegmentEdge *)0;
399 }
400
401 bmFreeSegment( from );
402
403 return 0;
404 }
405
406 /************************************************************************/
407 /* */
408 /* 1) Find the first '0' pixel on of after position 'col' in a row */
409 /* 2) Find the first '1' pixel on of after position 'col' in a row */
410 /* */
411 /************************************************************************/
412
413 /* 1 */
bmc0Run(const unsigned char * buf,int bytesPerRow,int xsz,const int col,int nfret)414 static int bmc0Run( const unsigned char * buf,
415 int bytesPerRow,
416 int xsz,
417 const int col,
418 int nfret )
419 {
420 int colbyte= col/ 8;
421 int bit= col- 8* colbyte;
422 int c;
423
424 while( colbyte < bytesPerRow )
425 {
426 if ( ( c= buf[colbyte] ) != 0xff )
427 {
428 while( bit < 8 )
429 {
430 if ( ! ( c & Bmc1Masks[bit] ) )
431 {
432 int rval= 8* colbyte+ bit;
433
434 if ( rval >= xsz )
435 { return nfret; }
436 else{ return rval; }
437 }
438 bit++;
439 }
440 }
441
442 colbyte++; bit= 0;
443 }
444
445 return nfret;
446 }
447
448 /* 2 */
bmc1Run(const unsigned char * buf,int bytesPerRow,int xsz,const int col,int nfret)449 static int bmc1Run( const unsigned char * buf,
450 int bytesPerRow,
451 int xsz,
452 const int col,
453 int nfret )
454 {
455 int colbyte= col/ 8;
456 int bit= col- 8* colbyte;
457 int c;
458
459 while( colbyte < bytesPerRow )
460 {
461 if ( ( c= buf[colbyte] ) != 0x00 )
462 {
463 while( bit < 8 )
464 {
465 if ( c & Bmc1Masks[bit] )
466 {
467 int rval= 8* colbyte+ bit;
468
469 if ( rval >= xsz )
470 { return nfret; }
471 else{ return rval; }
472 }
473 bit++;
474 }
475 }
476
477 colbyte++; bit= 0;
478 }
479
480 return nfret;
481 }
482
483 /************************************************************************/
484 /* */
485 /* Make 'sn' the terminating branch node */
486 /* */
487 /* 1) Make the new edge that branches off. */
488 /* 2) Insert the old edge as an up going edge in the node. */
489 /* 3) ? */
490 /* 4) Remove one run from the edge that came from above. */
491 /* 5) The new edge continues down at this location. */
492 /* */
493 /************************************************************************/
494
bcBranch(CompIndex * ci,LookUp * lu,SegmentNode * sn)495 static int bcBranch( CompIndex * ci,
496 LookUp * lu,
497 SegmentNode * sn )
498 {
499 SegmentEdge * se;
500 DataRun * dr;
501
502 /* 1 */
503 se= bmSegmentEdge( ci->ci_compo, sn, lu->luX0, lu->luXp );
504 if ( ! se )
505 { XDEB(se); return -1; }
506
507 /* 2 */
508 if ( bmConnectSegmentEdgeToNode( sn, lu->lu_edge, 1 ) )
509 { LDEB(1); return -1; }
510
511 /* 3 */
512 ci->ci_count++;
513
514 /* 4 */
515 dr= lu->lu_edge->seRuns+ lu->lu_edge->seRunCount- 1;
516 if ( dr->drRepeatCount > 1 )
517 { dr->drRepeatCount--; }
518 else{ lu->lu_edge->seRunCount--; }
519
520 /* 5 */
521 lu->lu_edge= se;
522
523 return 0;
524 }
525
526 /************************************************************************/
527 /* */
528 /* Create a new component. */
529 /* */
530 /* Memory management of the components is rudimentary. I think it will */
531 /* do for this application. */
532 /* */
533 /************************************************************************/
534
bmStartNewSegment(int * pnco,int * pmco,CompIndex ** pcomps,SegmentEdge ** pse,int x0,int xp,int row)535 static int bmStartNewSegment( int * pnco,
536 int * pmco,
537 CompIndex ** pcomps,
538 SegmentEdge ** pse,
539 int x0,
540 int xp,
541 int row )
542 {
543 int nco= *pnco;
544 int mco= *pmco;
545 CompIndex * comps= *pcomps;
546 BitmapSegment * bs;
547
548 SegmentNode * sn;
549 SegmentEdge * se;
550
551 bs= bmNewSegment();
552 if ( ! bs )
553 { XDEB(bs); return -1; }
554
555 if ( nco >= mco )
556 {
557 mco= ( 3* mco )/2+ 1;
558 comps= (CompIndex *)realloc( comps, mco* sizeof(CompIndex) );
559 if ( ! comps )
560 { return -1; }
561 }
562
563 comps[nco].ci_compo= bs;
564 comps[nco].ci_count= 1;
565
566 sn= bmSegmentNode( bs, row );
567 if ( ! sn )
568 { XDEB(sn); return -1; }
569 se= bmSegmentEdge( bs, sn, x0, xp );
570 if ( ! se )
571 { XDEB(se); return -1; }
572
573 *pcomps= comps;
574 *pnco= nco+ 1;
575 *pmco= mco;
576 *pse= se;
577
578 return nco;
579 }
580
581 /************************************************************************/
582 /* */
583 /* Get rid of a component because it has been merged with another one. */
584 /* Memory management of the components is rudimentary. I think it will */
585 /* do for this application. */
586 /* */
587 /************************************************************************/
588
bcMergeComp(CompIndex * comps,int * pnco,int newcomp,int oldcomp,LookUp * olu,int oLuCount,LookUp * nlu,int nLuCount)589 static int bcMergeComp( CompIndex * comps,
590 int * pnco,
591 int newcomp,
592 int oldcomp,
593 LookUp * olu,
594 int oLuCount,
595 LookUp * nlu,
596 int nLuCount )
597 {
598 int nco= *pnco;
599
600 if ( oldcomp == newcomp )
601 { comps[oldcomp].ci_count--; return 0; }
602
603 if ( comps[oldcomp].ci_compo )
604 {
605 if ( bmMoveComponentContents( comps[newcomp].ci_compo,
606 comps[oldcomp].ci_compo ) )
607 { LDEB(1); return -1; }
608
609 comps[oldcomp].ci_compo= (BitmapSegment *)0;
610 comps[oldcomp].ci_count= 0;
611
612 while( nco > 0 && ! comps[nco- 1].ci_compo )
613 { nco--; }
614
615 *pnco= nco;
616
617 while( --oLuCount >= 0 )
618 {
619 if ( olu->lu_compid == oldcomp )
620 { olu->lu_compid= newcomp; }
621 olu++;
622 }
623 while( --nLuCount >= 0 )
624 {
625 if ( nlu->lu_compid == oldcomp )
626 { nlu->lu_compid= newcomp; }
627 nlu++;
628 }
629 }
630
631 return 0;
632 }
633
634 /************************************************************************/
635 /* */
636 /* Refresh the count of newcomp */
637 /* */
638 /************************************************************************/
639
bcCountComp(CompIndex * comps,int newcomp,LookUp * olu,int oLuCount,LookUp * nlu,int nLuCount)640 static void bcCountComp( CompIndex * comps,
641 int newcomp,
642 LookUp * olu,
643 int oLuCount,
644 LookUp * nlu,
645 int nLuCount )
646 {
647 comps[newcomp].ci_count= 0;
648
649 while( --oLuCount >= 0 )
650 {
651 if ( olu->lu_use != LU_ENDED &&
652 olu->lu_compid == newcomp )
653 { comps[newcomp].ci_count++; }
654 olu++;
655 }
656
657 while( --nLuCount >= 0 )
658 {
659 if ( nlu->lu_compid == newcomp )
660 { comps[newcomp].ci_count++; }
661 nlu++;
662 }
663
664 return;
665 }
666
667 /************************************************************************/
668 /* */
669 /* Terminate an edge with a node. */
670 /* This destroys one reference to the component. */
671 /* */
672 /* 1) Make the end node. */
673 /* 2) Attach the edge to it. */
674 /* */
675 /************************************************************************/
676
bcTerminate(CompIndex * ci,LookUp * plu,int row)677 static int bcTerminate( CompIndex * ci,
678 LookUp * plu,
679 int row )
680 {
681 SegmentNode * sn;
682
683 /* 1 */
684 sn= bmSegmentNode( ci->ci_compo, row );
685 if ( ! sn )
686 { XDEB(sn); return -1; }
687
688 /* 2 */
689 if ( bmConnectSegmentEdgeToNode( sn, plu->lu_edge, 1 ) )
690 { LDEB(1); return -1; }
691
692 plu->lu_use= LU_ENDED;
693 plu->lu_node= sn;
694 ci->ci_count--;
695
696 return 0;
697 }
698
699 /************************************************************************/
700 /* */
701 /* If any segments from the previous row are found, continue/merge */
702 /* them. */
703 /* */
704 /* 1) If more than one run touch the current run, merge them in a */
705 /* node. */
706 /* 2) If the last one was already continued.. It is a split. */
707 /* */
708 /************************************************************************/
709
bcContinueSegments(int * pNLuCount,int * pNCo,LookUp * olu,const int oLuCount,LookUp * nlu,int nLuCount,int nco,CompIndex * comps,const int row,const int x0,const int xp,int beg,int end)710 static int bcContinueSegments( int * pNLuCount,
711 int * pNCo,
712 LookUp * olu,
713 const int oLuCount,
714 LookUp * nlu,
715 int nLuCount,
716 int nco,
717 CompIndex * comps,
718 const int row,
719 const int x0,
720 const int xp,
721 int beg,
722 int end )
723 {
724 int compid;
725
726 compid= olu[beg].lu_compid;
727
728 /* 1 */
729 if ( beg < end- 1 )
730 {
731 SegmentNode * sn;
732 SegmentEdge * se;
733
734 sn= bmSegmentNode( comps[compid].ci_compo, row );
735 if ( ! sn )
736 { XDEB(sn); return -1; }
737
738 while( beg < end- 1 )
739 {
740 /* appDebug( "-- %4d: MERGE\n", beg ); */
741
742 if ( bcMergeComp( comps, &nco, compid, olu[beg+1].lu_compid,
743 olu+ beg, oLuCount- beg, nlu, nLuCount ) )
744 { LDEB(1); return -1; }
745
746 if ( bmConnectSegmentEdgeToNode( sn, olu[beg].lu_edge, 1 ) )
747 { LDEB(1); return -1; }
748
749 olu[beg].lu_use= LU_MERGED;
750 olu[beg].lu_node= sn;
751 olu[beg].lu_compid= compid;
752 beg++;
753 }
754
755 bcCountComp( comps, compid, olu+beg, oLuCount-beg, nlu, nLuCount );
756
757 if ( bmConnectSegmentEdgeToNode( sn, olu[beg].lu_edge, 1 ) )
758 { LDEB(1); return -1; }
759 se= bmSegmentEdge( comps[compid].ci_compo, sn, x0, xp );
760 if ( ! se )
761 { XDEB(se); return -1; }
762 se->seRunCount= 0; /* Oups, against an extra row */
763 olu[beg].lu_node= sn;
764 olu[beg].lu_edge= se;
765 olu[beg].lu_compid= compid;
766
767 /* appDebug( "-- %4d: BELOW\n", beg ); */
768 }
769
770 /* 2 */
771 if ( olu[beg].lu_use != LU_UNSPEC )
772 {
773 SegmentNode * sn;
774 SegmentEdge * se;
775
776 /* appDebug( "-- %4d: SPLIT\n", beg ); */
777
778 sn= nlu[nLuCount-1].lu_node;
779 if ( ! sn )
780 {
781 sn= bmSegmentNode( comps[compid].ci_compo, row );
782 if ( ! sn )
783 { XDEB(sn); return -1; }
784 if ( bcBranch( comps+compid, nlu+ nLuCount- 1, sn ) )
785 { LDEB(1); return -1; }
786 nlu[nLuCount-1].lu_node= sn;
787 }
788 else{ comps[compid].ci_count++; }
789
790 se= bmSegmentEdge( comps[compid].ci_compo, sn, x0, xp );
791 if ( ! se )
792 { XDEB(se); return -1; }
793
794 /* olu[beg].lu_use= LU_EXTENDED; see above */
795 nlu[nLuCount].luX0= x0;
796 nlu[nLuCount].luXp= xp;
797 nlu[nLuCount].lu_edge= se;
798 nlu[nLuCount].lu_compid= compid;
799 nlu[nLuCount].lu_use= LU_UNSPEC;
800 nlu[nLuCount].lu_node= sn;
801 nLuCount++;
802 }
803 else{
804 /* 3 */
805
806 /* appDebug( "-- %4d: CONT \n", beg ); */
807
808 compid= olu[beg].lu_compid;
809
810 if ( bmAddRunToSegmentEdge( comps[compid].ci_compo,
811 olu[beg].lu_edge, x0, xp ) )
812 { LDEB(1); return -1; }
813
814 olu[beg].lu_use= LU_EXTENDED;
815 nlu[nLuCount].luX0= x0;
816 nlu[nLuCount].luXp= xp;
817 nlu[nLuCount].lu_edge= olu[beg].lu_edge;
818 nlu[nLuCount].lu_compid= compid;
819 nlu[nLuCount].lu_use= LU_UNSPEC;
820 nlu[nLuCount].lu_node= (SegmentNode *)0;
821 nLuCount++;
822 }
823
824 *pNLuCount= nLuCount;
825 *pNCo= nco;
826 return 0;
827 }
828
829 /************************************************************************/
830 /* */
831 /* Find the different black connected components on a page. */
832 /* For every successive scanline, the relationships of the runs of */
833 /* black with those on the previous one are determined. */
834 /* */
835 /* 3) For all rows in the image. */
836 /* 4) Loop over all runs of 'black' pixels. */
837 /* 5) Skip all segments from the previous row that end before the */
838 /* black run. Terminate them if necessary. */
839 /* 6) Find the first segment that begins after the black run. */
840 /* 7) If any segments from the previous row are found, continue/merge */
841 /* them. */
842 /* */
843 /************************************************************************/
844
bcComponents(BitmapSegment *** pSegments,int * pCount,const unsigned char * buffer,const BitmapDescription * bd)845 int bcComponents( BitmapSegment *** pSegments,
846 int * pCount,
847 const unsigned char * buffer,
848 const BitmapDescription * bd )
849 {
850 int row;
851
852 int pixelsWide= bd->bdPixelsWide;
853
854 int oLuCount;
855 int nLuCount;
856
857 int beg, end;
858 LookUp * lu1= (LookUp *)malloc( pixelsWide* sizeof(LookUp) );
859 LookUp * lu2= (LookUp *)malloc( pixelsWide* sizeof(LookUp) );
860 LookUp * olu= lu1;
861 LookUp * nlu= lu2;
862 LookUp * swap;
863
864 int x0, xp;
865
866 int nco= 0, mco= 30;
867 CompIndex * comps= (CompIndex *)malloc( mco* sizeof(CompIndex) );
868 int compid;
869 BitmapSegment ** retcomps= (BitmapSegment **)0;
870
871 int diagonals= 1;
872
873 int (*whiteRun)( const unsigned char * _buf,
874 int bytesPerRow,
875 int xsz,
876 const int col,
877 int nfret );
878 int (*blackRun)( const unsigned char * _buf,
879 int bytesPerRow,
880 int xsz,
881 const int col,
882 int nfret );
883
884 if ( ! lu1 || ! lu2 || ! comps )
885 { XXDEB(lu1,lu2); XDEB(comps); goto failure; }
886
887 switch( bd->bdColorEncoding )
888 {
889 case BMcoBLACKWHITE:
890 if ( bd->bdBitsPerPixel != 1 )
891 {
892 LLDEB(bd->bdColorEncoding,bd->bdBitsPerPixel);
893 goto failure;
894 }
895
896 whiteRun= bmc1Run;
897 blackRun= bmc0Run;
898 break;
899
900 case BMcoWHITEBLACK:
901 if ( bd->bdBitsPerPixel != 1 )
902 {
903 LLDEB(bd->bdColorEncoding,bd->bdBitsPerPixel);
904 goto failure;
905 }
906
907 whiteRun= bmc0Run;
908 blackRun= bmc1Run;
909 break;
910
911 default:
912 LDEB(bd->bdColorEncoding);
913 goto failure;
914 }
915
916
917 oLuCount= 0;
918
919 /* 3 */
920 for ( row= 0; row < bd->bdPixelsHigh; row++ )
921 {
922 x0= 0; nLuCount= 0; beg= end= 0;
923
924 /* appDebug( "======== ROW %4d\n", row ); */
925
926 /* 4 */
927 for (;;)
928 {
929 x0= (*whiteRun)( buffer+ row* bd->bdBytesPerRow,
930 bd->bdBytesPerRow, bd->bdPixelsWide, x0, -1 );
931
932 if ( x0 < 0 )
933 { break; }
934
935 xp= (*blackRun)( buffer+ row* bd->bdBytesPerRow,
936 bd->bdBytesPerRow, bd->bdPixelsWide,
937 x0+ 1, bd->bdPixelsWide );
938
939 /* appDebug( "++ %4d: FOUND %5d -| %5d\n", nLuCount, x0, xp ); */
940
941 /************************************************************/
942 /* Identify what kind of a run we found. */
943 /* 2) First one that does begin after x1. */
944 /************************************************************/
945 /* 5 */
946 while( beg < oLuCount )
947 {
948 compid= olu[beg].lu_compid;
949
950 if ( olu[beg].luXp > x0- diagonals )
951 { break; }
952 if ( olu[beg].lu_use == LU_UNSPEC )
953 {
954 if ( bcTerminate( comps+ compid, olu+ beg, row- 1 ) )
955 { goto failure; }
956
957 /* appDebug( "-- %4d: TERM \n", beg ); */
958 }
959 else{
960 /* appDebug( "-- %4d: CONT \n", beg ); */
961 }
962 beg++;
963 }
964 end= beg;
965
966 /* 6 */
967 while( end < oLuCount )
968 {
969 if ( olu[end].luX0 >= xp+ diagonals )
970 { break; }
971
972 /* appDebug( "-- %4d: PREV \n", end ); */
973 end++;
974 }
975
976 /* 7 */
977 if ( end > beg )
978 {
979 if ( bcContinueSegments( &nLuCount, &nco,
980 olu, oLuCount,
981 nlu, nLuCount,
982 nco, comps,
983 row, x0, xp,
984 beg, end ) )
985 { LDEB(1); goto failure; }
986
987 beg= end- 1;
988 }
989 else{
990 SegmentEdge * se;
991
992 compid= bmStartNewSegment( &nco, &mco, &comps, &se,
993 x0, xp, row );
994 if ( compid < 0 )
995 { LDEB(compid); goto failure; }
996 nlu[nLuCount].lu_compid= compid;
997 nlu[nLuCount].luX0= x0;
998 nlu[nLuCount].luXp= xp;
999 nlu[nLuCount].lu_edge= se;
1000 nlu[nLuCount].lu_node= (SegmentNode *)0;
1001 nlu[nLuCount].lu_use= LU_UNSPEC;
1002 nLuCount++;
1003
1004 /* appDebug( "-- %4d: NEW \n", nLuCount- 1 ); */
1005 }
1006
1007 x0= xp+ 1;
1008 }
1009
1010 while( beg < oLuCount )
1011 {
1012 compid= olu[beg].lu_compid;
1013
1014 if ( olu[beg].lu_use == LU_UNSPEC )
1015 {
1016 if ( bcTerminate( comps+ compid, olu+ beg, row- 1 ) )
1017 { goto failure; }
1018
1019 /* appDebug( "-- %4d: TERM \n", beg ); */
1020 }
1021 else{
1022 /* appDebug( "-- %4d: READY\n", beg ); */
1023 }
1024 beg++;
1025 }
1026
1027 swap= nlu; nlu= olu; olu= swap;
1028 oLuCount= nLuCount;
1029 }
1030
1031 /*
1032 APP_DEB(appDebug( "%-5d ROWS:\n", row ));
1033 */
1034 beg= 0;
1035 while( beg < oLuCount )
1036 {
1037 compid= olu[beg].lu_compid;
1038 if ( olu[beg].lu_use == LU_UNSPEC )
1039 {
1040 if ( bcTerminate( comps+ compid, olu+ beg, row- 1 ) )
1041 { goto failure; }
1042
1043 /* appDebug( "-- %4d: BOTTM\n", beg ); */
1044 }
1045 else{
1046 /* appDebug( "-- %4d: ERROR\n", beg ); */
1047 goto failure;
1048 }
1049 beg++;
1050 }
1051
1052 retcomps= (BitmapSegment **)malloc( nco* sizeof(BitmapSegment *) );
1053 if ( ! retcomps )
1054 { goto failure; }
1055 end= nco; nco= 0;
1056 for ( beg= 0; beg < end; beg++ )
1057 {
1058 double wide;
1059 double high;
1060 int rejected= 0;
1061
1062 if ( ! comps[beg].ci_compo )
1063 { continue; }
1064
1065 wide= comps[beg].ci_compo->bsRect.drX1- comps[beg].ci_compo->bsRect.drX0+ 1;
1066 high= comps[beg].ci_compo->bsRect.drY1- comps[beg].ci_compo->bsRect.drY0+ 1;
1067
1068 if ( wide < 5 && high < 5 )
1069 { rejected= 1; }
1070
1071 if ( wide >= bd->bdPixelsWide/ 10 ||
1072 high >= bd->bdPixelsHigh/ 10 )
1073 { rejected= 1; }
1074
1075 if ( wide > 15* high || high > 15* wide )
1076 { rejected= 1; }
1077
1078 if ( rejected )
1079 { bmFreeSegment( comps[beg].ci_compo ); continue; }
1080
1081 retcomps[nco++]= comps[beg].ci_compo;
1082 }
1083
1084 if ( lu1 )
1085 { free( lu1 ); }
1086 if ( lu2 )
1087 { free( lu2 ); }
1088 if ( comps )
1089 { free( comps ); }
1090
1091 *pCount= nco;
1092 *pSegments= retcomps;
1093
1094 return 0;
1095
1096 failure:
1097 if ( lu1 )
1098 { free( lu1 ); }
1099 if ( lu2 )
1100 { free( lu2 ); }
1101 if ( comps )
1102 {
1103 for ( beg= 0; beg < nco; beg++ )
1104 { bmFreeSegment( comps[beg].ci_compo ); }
1105
1106 free( comps );
1107 }
1108
1109 return -1;
1110 }
1111
bmcDrawComponent(const BitmapSegment * bs,unsigned char * buffer,int col0,int row0,int bytesPerRow,int colorEncoding)1112 int bmcDrawComponent( const BitmapSegment * bs,
1113 unsigned char * buffer,
1114 int col0,
1115 int row0,
1116 int bytesPerRow,
1117 int colorEncoding )
1118 {
1119 SegmentEdge ** se;
1120 int i, j;
1121
1122 # if 0
1123 bmDrawBox( buffer, bd,
1124 bs->bsRect.drX0- col0, row0,
1125 bs->bsRect.drX1- col0, row0+ bs->bsRect.drY1- bs->bsRect.drY0,
1126 1, colorEncoding );
1127 bmDrawLine( buffer, bd,
1128 bs->bsRect.drX0- col0, row0,
1129 bs->bsRect.drX1- col0, row0+ bs->bsRect.drY1- bs->bsRect.drY0,
1130 2 );
1131 bmDrawLine( buffer, bd,
1132 bs->bsRect.drX0- col0, row0+ bs->bsRect.drY1- bs->bsRect.drY0,
1133 bs->bsRect.drX1- col0, row0,
1134 2 );
1135
1136 return 0;
1137 # endif
1138
1139 se= bs->bsEdges;
1140 for ( i= 0; i < bs->bsEdgeCount; i++, se++ )
1141 {
1142 int row= se[0]->seFrom->snY0- bs->bsRect.drY0+ row0;
1143 DataRun * dr= se[0]->seRuns;
1144
1145 for ( j= 0; j < se[0]->seRunCount; j++, dr++ )
1146 {
1147 bmFillBlock( buffer,
1148 dr->drX0- col0, row,
1149 dr->drXp- col0, row+ dr->drRepeatCount,
1150 bytesPerRow );
1151
1152 row += dr->drRepeatCount;
1153 }
1154 }
1155
1156 return 0;
1157 }
1158
1159 /************************************************************************/
1160 /* */
1161 /* Return information on a component. If a buffer pointer is given, */
1162 /* a bitmap for the component is returned. */
1163 /* */
1164 /************************************************************************/
1165
bmComponentBitmap(unsigned char ** pBuffer,BitmapDescription * bdout,DocumentRectangle * drSel,const BitmapDescription * bdin,const void * voidbs)1166 int bmComponentBitmap( unsigned char ** pBuffer,
1167 BitmapDescription * bdout,
1168 DocumentRectangle * drSel,
1169 const BitmapDescription * bdin,
1170 const void * voidbs )
1171 {
1172 const BitmapSegment * bs= (const BitmapSegment *)voidbs;
1173 BitmapDescription resbd= *bdin;
1174 int byte= 8* resbd.bdBitsPerPixel;
1175 unsigned char * buffer;
1176
1177 int colorEncoding= bdin->bdColorEncoding;
1178
1179 resbd.bdPixelsWide= bs->bsRect.drX1- bs->bsRect.drX0+ 1;
1180 resbd.bdPixelsWide= ( ( resbd.bdPixelsWide+ byte- 1 )/ byte ) * byte;
1181 resbd.bdPixelsHigh= bs->bsRect.drY1- bs->bsRect.drY0+ 1;
1182
1183 resbd.bdBytesPerRow= resbd.bdPixelsWide/ byte;
1184
1185 resbd.bdBufferLength= resbd.bdBytesPerRow* resbd.bdPixelsHigh;
1186
1187 if ( pBuffer )
1188 {
1189 buffer= bmBackgroundBuffer( resbd.bdBufferLength, colorEncoding );
1190 if ( ! buffer )
1191 { LLDEB(resbd.bdBufferLength,buffer); return -1; }
1192
1193 if ( bmcDrawComponent( bs,
1194 buffer,
1195 bs->bsRect.drX0, 0,
1196 resbd.bdBytesPerRow,
1197 colorEncoding ) )
1198 { free( buffer ); return -1; }
1199
1200 *pBuffer= buffer;
1201 }
1202
1203 *bdout= resbd;
1204
1205 *drSel= bs->bsRect;
1206
1207 return 0;
1208 }
1209
1210 /************************************************************************/
1211 /* */
1212 /* Return information on the geometry of a component. */
1213 /* */
1214 /************************************************************************/
1215
bmcStatistics(const BitmapSegment * bs,int * pN,float * pSx,float * pSy,float * pSxx,float * pSyy,float * pSxy)1216 void bmcStatistics( const BitmapSegment * bs,
1217 int * pN,
1218 float * pSx,
1219 float * pSy,
1220 float * pSxx,
1221 float * pSyy,
1222 float * pSxy )
1223 {
1224 SegmentEdge ** se;
1225 int i, j;
1226
1227 *pN= 0;
1228 *pSx= 0;
1229 *pSy= 0;
1230 *pSxx= 0;
1231 *pSyy= 0;
1232 *pSxy= 0;
1233
1234 se= bs->bsEdges;
1235 for ( i= 0; i < bs->bsEdgeCount; i++, se++ )
1236 {
1237 DataRun * dr;
1238
1239 int y0= se[0]->seFrom->snY0;
1240
1241 dr= se[0]->seRuns;
1242 for ( j= 0; j < se[0]->seRunCount; j++, dr++ )
1243 {
1244 int x0= dr->drX0;
1245 int x1= dr->drXp+ 1;
1246 int xx0= x0* ( x0+ 1 );
1247 int xx1= x1* ( x1+ 1 );
1248 int sxx= xx1/2- xx0/2;
1249 double xxx0= xx0* ( 2.0* x0+ 1.0 );
1250 double xxx1= xx1* ( 2.0* x1+ 1.0 );
1251
1252 int y1= y0+ dr->drRepeatCount;
1253 int yy0= y0* ( y0+ 1 );
1254 int yy1= y1* ( y1+ 1 );
1255 int syy= yy1/2- yy0/2;
1256 double yyy0= yy0* ( 2.0* y0+ 1.0 );
1257 double yyy1= yy1* ( 2.0* y1+ 1.0 );
1258
1259 *pN += dr->drRepeatCount* ( x1- x0 );
1260 *pSx += dr->drRepeatCount* sxx;
1261 *pSy += ( x1- x0 )* syy;
1262 *pSxx += dr->drRepeatCount* ( xxx1/6- xxx0/6 );
1263 *pSyy += ( x1- x0 )* ( yyy1/6- yyy0/6 );
1264 *pSxy += sxx* syy;
1265
1266 y0 += dr->drRepeatCount;
1267 }
1268 }
1269
1270 return;
1271 }
1272
1273