~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina6/tina-libs/tina/geometry/geomEdge_link.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**********
  2  * 
  3  * This file is part of the TINA Open Source Image Analysis Environment
  4  * henceforth known as TINA
  5  *
  6  * TINA is free software; you can redistribute it and/or modify
  7  * it under the terms of the GNU General Public License as 
  8  * published by the Free Software Foundation.
  9  *
 10  * TINA is distributed in the hope that it will be useful,
 11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 13  * GNU General Public License for more details.
 14  *
 15  * You should have received a copy of the GNU General Public License
 16  * along with TINA; if not, write to the Free Software Foundation, Inc., 
 17  * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18  *
 19  * ANY users of TINA who require exemption from the existing licence must
 20  * negotiate a new licence with Dr. Neil.A.Thacker, the sole agent for
 21  * the University of Manchester.
 22  *
 23  **********
 24  * 
 25  * Program :    TINA
 26  * File    :  $Source: /home/tina/cvs/tina-libs/tina/geometry/geomEdge_link.c,v $
 27  * Date    :  $Date: 2009/03/19 18:36:26 $
 28  * Version :  $Revision: 1.6 $
 29  * CVS Id  :  $Id: geomEdge_link.c,v 1.6 2009/03/19 18:36:26 paul Exp $
 30  *
 31  * Author  : Legacy TINA
 32  *
 33  * Notes : 
 34  *
 35  * functions to connect edge strings
 36  * 
 37  * rewriten to use static variables rather than property list for data
 38  * manipulation
 39  * 
 40  * now modified to make use of orienation information NAT 12/12/08
 41  *
 42  *********
 43 */
 44 
 45 #include "geomEdge_link.h"
 46 
 47 #if HAVE_CONFIG_H
 48   #include <config.h>
 49 #endif
 50 
 51 #include <math.h>
 52 #include <tina/sys/sysDef.h>
 53 #include <tina/sys/sysPro.h>
 54 #include <tina/math/mathDef.h>
 55 #include <tina/math/mathPro.h>
 56 #include <tina/image/imgDef.h>
 57 #include <tina/image/imgPro.h>
 58 #include <tina/geometry/geomDef.h>
 59 #include <tina/geometry/geom_EdgeDef.h>
 60 #include <tina/geometry/geomEdge_gen.h>
 61 #include <tina/geometry/geomEdge_rect.h>
 62 
 63 /* The edge linking process is very fragile due to the nature of the data
 64  * structures involved. In particular, the forward and backward linking between
 65  * edges must be self consistent in order to avoid loops and multiple indexing
 66  * of edges in strings. Error messages have therefore been added during the process
 67  * of recent modifications in order to catch broken data structures should they 
 68  * occur due to these or any future modicifatons. 
 69  *
 70  * Algorithm proceeds by linking everything, breaking bad orientations, simplifying 
 71  * junctions and finally relinking consistent end junctions, like a 1D split and merge.
 72  * It is expected that the majority of strings (> 80%) will be correctly (semantically) 
 73  * linked, but there is one last chance to fix faulty curves during the 2D fitting process. 
 74    NAT 12/12/08 
 75  * edge detection found to scale very badly for larger images so routines re-written
 76  * to eliminate quadratic dependency on edge count resultng in > 100x faster execution
 77  * for mega-pixel images. 
 78  * NAT 2/7/11 
 79  * */
 80 
 81 /* control parameters which determine edge grouping and linkage */
 82 #define CROSSMATCH 236
 83 #define MAX_GAP 8
 84 #define COSCONT 0.4
 85 #define OR_DIFF 0.5
 86 #define ABSDIFFOR  0.4
 87 #define SPUR_LENGTH_THRES 3
 88 #define TEE_ORIENTATION_THRES 1.0 
 89 
 90 /* lists of special edge points and strings manipulated by linking
 91  * functions */
 92 
 93 static List *junc_list = NULL;          /* static data! */
 94 static List *term_list = NULL;          /* static data! */
 95 static List *string_list = NULL;        /* static data! */
 96 
 97 static void edge_set_conn_type_on(Edgel * edge)
 98 {
 99     edge->type &= EDGE_SET_CONN_MASK;
100     edge->type |= EDGE_CONN;
101 }
102 
103 #if 0
104 static void edge_set_conn_type_off(Edgel * edge)
105 {
106     edge->type &= EDGE_SET_CONN_MASK;
107 }
108 
109 #endif
110 
111 /* set up edge type for display with structure integrity checking NAT 12/12/08 */
112 static void edge_set_conn_type(Edgel * edge)
113 {
114     Edge_conn *econn;
115 
116     if (edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
117         return;
118 
119     edge->type &= EDGE_SET_CONN_MASK;
120     econn = (Edge_conn *) prop_get(edge->props, EDGE_CONN);
121     if (econn == NULL)
122     {
123         edge->type |= EDGE_NOLINK;
124         return;
125     }
126 
127     if ((econn->c1 == NULL && econn->c2 == NULL && econn->conns == NULL ))
128     {
129         if (econn->count!=0) 
130              format("wrong count 0 \n");
131         econn->count = 0;
132     }
133 
134     if ((econn->c1 != NULL && econn->c2 != NULL && econn->conns == NULL ))
135     {
136         if (econn->count!=2) 
137              format("wrong count 2 \n");
138         econn->count = 2;
139     }
140     if ((econn->c1 == NULL && econn->c2 == NULL && econn->conns != NULL ))
141     {
142         if (econn->count==2)
143               format("wrong count %d \n", econn->count);
144     }
145 
146     switch (econn->count)
147     {
148     case 0:
149         edge->type |= EDGE_NOLINK;
150         break;
151     case 1:
152         edge->type |= EDGE_TERMIN;
153         break;
154     case 2:
155         edge->type |= EDGE_CONN;
156         break;
157     default:
158         edge->type |= EDGE_JUNC;
159         break;
160     }
161 }
162 
163 /* test for orinetation consistency NAT */
164 static double absdifforient(double e1, double e2)
165 {
166      double   absordif;
167 
168      absordif = sin(e1 - e2);
169      return(fabs(absordif));
170 }
171 
172 /* set up initial linkage data structures and global junc and term lists with
173    built in NSEW bias to achieve consistent connetivity                     NAT */ 
174 static void edge_set_conns(Edgel * edge, int type, Imrect * er, int i, int j)
175 {
176     Edgel  *eptr;
177     Edge_conn *econn;
178     int     n = 0, e = 0, w = 0, s = 0;
179     double orient;
180 
181     if (er == NULL || edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
182         return;
183 
184     if ((econn = (Edge_conn *) prop_get(edge->props, EDGE_CONN)) == NULL)
185     {
186         econn = econn_alloc();
187         edge->props = proplist_add(edge->props, (void *) econn, EDGE_CONN, econn_free);
188     }
189     econn->c1 = NULL;
190     econn->c2 = NULL;
191     list_rm_links(econn->conns);
192     econn->conns = NULL;
193     econn->count = 0;
194     orient = edge->orient;
195 
196     if ((eptr = er_get_edge(er, i - 1, j)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
197     {
198         n = 1;
199         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
200         econn->count++;
201     }
202     if ((eptr = er_get_edge(er, i + 1, j)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
203     {
204         s = 1;
205         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
206         econn->count++;
207     }
208     if ((eptr = er_get_edge(er, i, j - 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
209     {
210         e = 1;
211         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
212         econn->count++;
213     }
214     if ((eptr = er_get_edge(er, i, j + 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
215     {
216         w = 1;
217         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
218         econn->count++;
219     }
220     if (!n && !w && (eptr = er_get_edge(er, i - 1, j + 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
221     {
222         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
223         econn->count++;
224     }
225     if (!n && !e && (eptr = er_get_edge(er, i - 1, j - 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
226     {
227         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
228         econn->count++;
229     }
230     if (!s && !w && (eptr = er_get_edge(er, i + 1, j + 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
231     {
232         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
233         econn->count++;
234     }
235     if (!s && !e && (eptr = er_get_edge(er, i + 1, j - 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
236     {
237         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
238         econn->count++;
239     }
240     switch (econn->count)
241     {
242     case 0:
243         econn->back = NULL;
244         break;
245     case 1:                     /* termination point: add to termination list */
246         term_list = ref_addtostart((List *) term_list, (void *) edge, EDGE);
247         econn->back = term_list;
248         break;
249     case 2:                     /* standard connect */
250         econn->c1 = (Edgel *) econn->conns->to;
251         econn->c2 = (Edgel *) econn->conns->next->to;
252         list_rm_links(econn->conns);
253         econn->conns = NULL;
254         econn->back = NULL;
255         break;
256     default:                    /* cases 3 and 4 potential junction: add to junction list */
257         {
258             junc_list = ref_addtostart((List *) junc_list, (void *) edge, EDGE);
259             econn->back = junc_list;
260             break;
261         }
262     }
263 }
264 
265 /* generic function to remove eptr from nptr->nconn data structure whilst maintaining
266 term_list and junc_list, generally must be called 2 times for consistent removal
267 NAT 12/12/08 */
268 static void editjunc(Edgel  *eptr, Edgel *nptr)
269 {
270     Edge_conn *nconn;
271     List *listindex;
272 
273     nconn = (Edge_conn *) prop_get(nptr->props, EDGE_CONN);
274     switch (nconn->count)
275     {
276         case 1:
277         {
278               rfree((void *) nconn->conns);
279               nconn->conns = NULL;
280               nconn->count = 0;
281  
282               /* remove slow search for ptr NAT 2/7/11
283               listindex = dd_link_get_by_ref(term_list, nptr);
284               if (listindex != nconn->back)
285                       printf("inconsistent pointer \n");
286                       */
287               term_list = dd_list_rm_el(term_list, nconn->back, NULL);
288               nconn->back = NULL;
289               break;
290          }
291          case 2:
292          {
293               Edgel  *keep = (nconn->c1 == eptr) ? nconn->c2 : nconn->c1;
294 
295               nconn->conns = link_alloc((void *) keep, EDGE);
296               nconn->count = 1;
297               nconn->c1 = NULL;
298               nconn->c2 = NULL;
299               term_list = ref_addtostart((List *) term_list, (void *) nptr, EDGE);
300               nconn->back = term_list;
301               break;
302          }
303          case 3:
304          {
305               nconn->conns = list_rm_ref(nconn->conns, (void *) eptr, (void (*) ()) NULL);
306               nconn->c1 = (Edgel *) nconn->conns->to;
307               nconn->c2 = (Edgel *) nconn->conns->next->to;
308               nconn->count = 2;
309               list_rm_links(nconn->conns);
310               nconn->conns = NULL;
311               /* remove slow search for ptr NAT 2/7/11
312               listindex = dd_link_get_by_ref(junc_list, nptr);
313               if (listindex != nconn->back)
314                       printf("inconsistent pointer \n");
315                       */
316               junc_list = dd_list_rm_el(junc_list, nconn->back, NULL);
317               nconn->back = NULL;
318               break;
319          }
320          case 4:
321          {
322               nconn->conns = list_rm_ref(nconn->conns, (void *) eptr, (void (*) ()) NULL);
323               nconn->count = 3;
324               break;
325          }
326          default:
327               break;    
328      }
329 }
330 
331 /* initial pruning, test for orientation consistency and remove poor links NAT 12/12/08 */
332 static void edge_break_conns(Edgel * edge, int type, Imrect * er, int i, int j)
333 {
334     Edgel *nptr1, *nptr2, *nptr3;
335     Edge_conn *econn;
336     double orient;
337 
338     if (er == NULL || edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
339         return;
340 
341     if ((econn = (Edge_conn *) prop_get(edge->props, EDGE_CONN)) == NULL)
342         return;
343 
344     orient = edge->orient;
345 
346     switch (econn->count)
347     {
348         case 1:
349         nptr1  = (Edgel *) econn->conns->to;
350         if (absdifforient(orient,nptr1->orient)>ABSDIFFOR)
351         {
352            editjunc(edge, nptr1);
353            editjunc(nptr1, edge);
354         }
355         break;
356 
357         case 2:
358         nptr1 = econn->c1;
359         nptr2 = econn->c2;
360         if (absdifforient(orient,nptr1->orient)>ABSDIFFOR)
361         {
362             editjunc(edge, nptr1);
363             editjunc(nptr1, edge);
364         }
365         if (absdifforient(orient,nptr2->orient)>ABSDIFFOR)
366         {
367            editjunc(edge, nptr2);
368            editjunc(nptr2, edge);
369         }
370         break;
371        
372         case 3:
373         nptr1  = (Edgel *) econn->conns->to;
374         nptr2  = (Edgel *) econn->conns->next->to;
375         nptr3  = (Edgel *) econn->conns->next->next->to;
376 
377         if (absdifforient(orient,nptr1->orient)>ABSDIFFOR)
378         {
379             editjunc(edge, nptr1);
380             editjunc(nptr1, edge);
381         }
382         if (absdifforient(orient,nptr2->orient)>ABSDIFFOR)
383         {
384            editjunc(edge, nptr2);
385            editjunc(nptr2, edge);
386         }
387         if (absdifforient(orient,nptr3->orient)>ABSDIFFOR)
388         {
389            editjunc(edge, nptr3);
390            editjunc(nptr3, edge);
391         }
392         break;
393     }
394 }
395 
396 /* test a candidate linkage using orientation and directionality, returns
397    value retated to perpendicular distance NAT 1/12/08 */
398 static double elink_con(Edgel *edge1, Edgel * edge2)
399 {
400     Edge_conn *conn1;
401     Edge_conn *conn2;
402     Edgel  *prev;
403     double  orient1, orient2;
404     Vec2    v1 = {Vec2_id}, v1c = {Vec2_id};
405     Vec2    v2 = {Vec2_id}, v2c = {Vec2_id};
406     Vec2    v = {Vec2_id};
407     double  diff, delta;
408     double dx, dy;
409 
410     dx = edge2->pos.el[0] - edge1->pos.el[0];
411 
412     if (fabs(dx)  > MAX_GAP)
413               return(MAX_GAP);
414     dy = edge2->pos.el[1] - edge1->pos.el[1];
415     if (fabs(dy)  > MAX_GAP)
416               return(MAX_GAP);
417 
418     orient1 = edge1->orient;
419     orient2 = edge2->orient;
420     delta = absdifforient(orient1,orient2);
421     if (delta > OR_DIFF) 
422               return(MAX_GAP);
423 
424     v = vec2_diff(edge2->pos, edge1->pos);
425     diff = vec2_mod(v);
426     if (diff > MAX_GAP)
427               return(MAX_GAP);
428 
429 
430     v = vec2_unit(v);
431 
432     conn1 = (Edge_conn *) prop_get(edge1->props, EDGE_CONN);
433     prev = (Edgel *) (conn1->conns->to);
434     if (prev != NULL) 
435     {
436        v1c = vec2_diff(edge1->pos, prev->pos);
437        v1c = vec2_unit(v1c);
438        if (vec2_dot(v1c, v) < COSCONT)  
439               return(MAX_GAP);
440     }
441 
442     conn2 = (Edge_conn *) prop_get(edge2->props, EDGE_CONN);
443     prev = (Edgel *) (conn2->conns->to);
444     if (prev != NULL) 
445     {
446        v2c = vec2_diff(edge2->pos, prev->pos);
447        v2c = vec2_unit(v2c);
448        if (vec2_dot(v2c, v) > -COSCONT) 
449               return(MAX_GAP);
450     }
451 
452     v1 = vec2(cos(orient1),-sin(orient1));
453     v2 = vec2(cos(orient2),-sin(orient2));
454 
455     diff *= sqrt(1.0 - fabs(vec2_dot(v,v1)*vec2_dot(v,v2)));
456   
457     return(diff);
458 }
459 
460 static int shortspur(Edgel * spur, Edgel * last, int thres, int count)
461 {
462     Edgel  *next;
463     Edge_conn *conn;
464 
465     if (spur == NULL) return(count);
466     conn = (Edge_conn *) prop_get(spur->props, EDGE_CONN);
467     if (count > thres || conn->count > 2 )      /* another junction */
468         return (0);
469 
470     if (conn->count == 1)       /* a termination */
471         return (count);
472 
473     next = (conn->c1 == last) ? conn->c2 : conn->c1;
474 
475     return (shortspur(next, spur, thres, count + 1));
476 }
477 
478 static List *prunespurs(List * juncs)
479 {
480     List   *jptr;
481     List   *listindex;
482     int     count;
483 
484     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
485     {
486         Edgel  *eptr = (Edgel *) jptr->to;
487         Edge_conn *econn;
488         List   *cptr;
489         List   *short_spurs = NULL;
490 
491         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
492 
493         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
494         {
495             Edgel  *spur = (Edgel *) cptr->to;
496             List   *lptr;
497             List   *link;
498             int     spur_len;
499 
500             if ((spur_len = shortspur(spur, eptr, SPUR_LENGTH_THRES, 1)))       /* short */
501             {
502                 link = link_alloc((void *) cptr, spur_len);
503                 if (short_spurs == NULL || spur_len < short_spurs->type)
504                     short_spurs = link_addtostart((List *) short_spurs, link);
505                 else
506                 {
507                     for (lptr = short_spurs; lptr->next != NULL; lptr = lptr->next)
508                         if (spur_len < lptr->next->type)
509                             break;
510                     link_addafter(lptr, link);
511                 }
512             }
513         }
514 
515         if (short_spurs == NULL)
516             continue;
517 
518         for (cptr = short_spurs, count = econn->count; cptr != NULL; cptr = cptr->next)
519         {
520             Edge_conn *sconn;
521             Edgel  *spur = (Edgel *) ((List *) cptr->to)->to;
522 
523             sconn = (Edge_conn *) prop_get(spur->props, EDGE_CONN);
524 
525             if (sconn->count == 1)      /* terminal */
526             {
527                 list_rm_links(sconn->conns);
528                 sconn->conns = NULL;
529                 sconn->count = 0;
530 
531                 /* remove slow search for ptr NAT 2/7/11
532                 listindex = dd_link_get_by_ref(term_list, spur);
533                 if (listindex != sconn->back)
534                       printf("inconsistent pointer \n");
535                       */
536                 term_list = dd_list_rm_el(term_list, sconn->back, NULL);
537                 sconn->back = NULL;
538 
539             } else
540             {
541                 /* sconn->count==2 */
542                 if (sconn->c1 == eptr)
543                     sconn->conns = link_alloc((void *) sconn->c2, EDGE);
544                 else
545                     sconn->conns = link_alloc((void *) sconn->c1, EDGE);
546                 sconn->c1 = sconn->c2 = NULL;
547                 sconn->count = 1;
548                 term_list = ref_addtostart((List *) term_list, (void *) spur, EDGE);
549                 sconn->back = term_list;
550             }
551             ((List *) cptr->to)->type = REMOVE_ME;
552             if (--count == 2)   /* simple connection */
553                 break;
554         }
555         list_rm_links(short_spurs);
556         econn->conns = list_rm_links_on_type(econn->conns, REMOVE_ME);
557     }
558 
559     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
560     {
561         Edgel  *eptr = (Edgel *) jptr->to;
562         Edge_conn *econn;
563         List   *cptr;
564 
565         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
566         econn->count = 0;
567         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
568             ++econn->count;
569 
570         switch (econn->count)
571         {
572         case 0:
573             jptr->type = REMOVE_ME;
574             break;
575         case 1:
576             term_list = ref_addtostart((List *) term_list, (void *) eptr, EDGE);
577             econn->back = term_list;
578             jptr->type = REMOVE_ME;
579             break;
580         case 2:
581             econn->c1 = (Edgel *) econn->conns->to;
582             econn->c2 = (Edgel *) econn->conns->next->to;
583             list_rm_links(econn->conns);
584             econn->conns = NULL;
585             jptr->type = REMOVE_ME;
586             break;
587         default:
588             break;
589         }
590     }
591     return (list_rm_links_on_type(juncs, REMOVE_ME));
592 }
593 
594 /* identify the linkage across short gaps which which minimises the orientation and projection 
595 differences, test all candidates and keep the best only if it is consistent NAT */ 
596 static List *bridge_small_gaps(Imrect* er, List * terms)
597 /* list of termination points */
598 {
599     List   *lptr1;
600     List   *lptr2;
601     List   *lmin;
602     Edgel  *edge1;
603     Edgel  *edge2;
604     Edgel  *etest;
605     Edge_conn *conn1;
606     Edge_conn *conn2;
607     double  min_diff, diff;
608     Imrect *er2;
609     Imregion er2reg;
610     int iy, ix;
611 
612     if (terms == NULL || terms->next == NULL)
613         return (terms);
614 
615     er2reg.lx = er->region->lx-MAX_GAP;
616     er2reg.ux = er->region->ux+MAX_GAP;
617     er2reg.ly = er->region->ly-MAX_GAP;
618     er2reg.uy = er->region->uy+MAX_GAP;
619 
620     er2 = (Imrect *) im_alloc(er->height, er->width, &er2reg, er->vtype);
621     for (lptr1 = terms; lptr1->next != NULL; lptr1 = lptr1->next)
622     {
623         edge1 = (Edgel *) lptr1->to;
624         ((void ***)(er2)->data)[tina_int(edge1->pos.el[1])][tina_int(edge1->pos.el[0])] = lptr1;
625     }
626 
627     for (lptr1 = terms; lptr1->next != NULL; lptr1 = lptr1->next)
628     {
629         if (lptr1->type == REMOVE_ME)
630             continue;
631 
632         edge1 = (Edgel *) lptr1->to;
633         conn1 = (Edge_conn *) prop_get(edge1->props, EDGE_CONN);
634         lmin = NULL;
635         min_diff = MAX_GAP;
636 
637         /* scales poorly with large images NAT 2/7/11
638         for (lptr2 = terms; lptr2 != NULL; lptr2 = lptr2->next)
639         */
640         for ( iy = (tina_int(edge1->pos.el[1]) - MAX_GAP); iy < (tina_int(edge1->pos.el[1]) + MAX_GAP) ;iy++)
641         {
642         for ( ix = (tina_int(edge1->pos.el[0]) - MAX_GAP); ix < (tina_int(edge1->pos.el[0]) + MAX_GAP) ;ix++)
643         {
644             lptr2 = ((List ***) (er2)->data)[iy][ix];
645             if (lptr2 == NULL || lptr2->type == REMOVE_ME)
646                 continue;
647             if (lptr2 == lptr1) 
648                     continue;
649 
650             edge2 = (Edgel *) lptr2->to;
651 
652             diff = elink_con(edge1,  edge2);
653 
654             if (diff < MAX_GAP && diff < min_diff)
655             {
656                lmin = lptr2;
657                min_diff = diff;
658             }
659         }
660         }
661         if (lmin == NULL)
662             continue;
663         edge1->props = proplist_add(edge1->props, (void *)lmin, CROSSMATCH, NULL);
664     }
665 
666     im_free(er2);
667     for (lptr1 = terms; lptr1->next != NULL; lptr1 = lptr1->next)
668     {
669         if (lptr1->type == REMOVE_ME)
670             continue;
671         edge1 = (Edgel *) lptr1->to;
672         lmin = prop_get(edge1->props, CROSSMATCH);
673         etest = NULL;
674 
675         if (lmin == NULL || lmin->type == REMOVE_ME)
676             continue;
677 
678         edge2 = lmin->to;
679         lptr2 = prop_get(edge2->props, CROSSMATCH);
680         if (lptr2 !=NULL) etest = lptr2->to;
681 
682         if ( etest!=NULL && etest == edge1)
683         {
684             conn1 = (Edge_conn *) prop_get(edge1->props, EDGE_CONN);
685             conn2 = (Edge_conn *) prop_get(edge2->props, EDGE_CONN);
686             conn1->c1 = conn1->conns->to;
687             conn2->c1 = conn2->conns->to;
688             conn1->c2 = edge2;
689             conn2->c2 = edge1;
690             list_rm_links(conn1->conns);
691             list_rm_links(conn2->conns);
692             conn1->conns = NULL;
693             conn2->conns = NULL;
694             if (conn1->count != 1 || conn2->count !=1)
695                  format("bad connections in termlst \n");
696             conn1->count = 2;
697             conn2->count = 2;
698             lptr1->type = REMOVE_ME;
699             lmin->type = REMOVE_ME;
700             edge2->props = proplist_rm(edge2->props, CROSSMATCH); 
701         }
702         edge1->props = proplist_rm(edge1->props, CROSSMATCH); 
703     }
704     return (list_rm_links_on_type(terms, REMOVE_ME));
705 }
706 
707 /* finished with junctions.. delete what is left NAT 12/12/08 */
708 static void rmjuncs(List * juncs)
709 {
710     List   *jptr;
711 
712     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
713     {
714         Edgel  *eptr = (Edgel *) jptr->to;
715         Edge_conn *econn;
716         List   *cptr;
717 
718         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
719 
720         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
721         {
722             Edgel  *nptr = (Edgel *) cptr->to;
723             editjunc(eptr, nptr);
724         }
725         list_rm_links(econn->conns);
726         econn->conns = NULL;
727         econn->count = 0;
728         edge_set_type_remove_me(eptr);
729     }
730 }
731 
732 /* break all links between adjacent junctions */
733 static List *prunejuncs(List * juncs)
734 {
735     List   *jptr;
736 
737     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
738     {
739         Edgel  *eptr = (Edgel *) jptr->to;
740         Edge_conn *econn;
741         List   *cptr;
742 
743         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
744 
745         for (cptr = econn->conns; cptr != NULL; )
746         {
747             Edgel  *nptr = (Edgel *) cptr->to;
748             Edge_conn *nconn;
749 
750             nconn = (Edge_conn *) prop_get(nptr->props, EDGE_CONN);
751             if (nconn->count > 2)       /* a neighbouring junction */
752             {
753                 cptr->type = REMOVE_ME;
754             }
755             cptr = cptr->next;
756         }
757         econn->conns = list_rm_links_on_type(econn->conns, REMOVE_ME);
758     }
759 
760     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
761     {
762         Edgel  *eptr = (Edgel *) jptr->to;
763         Edge_conn *econn;
764         List   *cptr;
765 
766         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
767 
768         econn->count = 0;
769         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
770             ++econn->count;
771 
772         switch (econn->count)
773         {
774         case 0:
775             jptr->type = REMOVE_ME;
776             econn->c1 = NULL;
777             econn->c2 = NULL;
778             break;
779         case 1:
780             term_list = ref_addtostart((List *) term_list, (void *) eptr, EDGE);
781             econn->back = term_list;
782             econn->c1 = NULL;
783             econn->c2 = NULL;
784             jptr->type = REMOVE_ME;
785             break;
786         case 2:
787             econn->c1 = (Edgel *) econn->conns->to;
788             econn->c2 = (Edgel *) econn->conns->next->to;
789             list_rm_links(econn->conns);
790             econn->conns = NULL;
791             jptr->type = REMOVE_ME;
792         default:
793             break;
794         }
795     }
796     return (list_rm_links_on_type(juncs, REMOVE_ME));
797 }
798 
799 static List *prunetees(List * juncs)
800 {
801     List   *jptr;
802 
803     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
804     {
805         Edgel  *eptr = (Edgel *) jptr->to;
806         Edgel  *links[3];
807         Edge_conn *econn;
808         Edge_conn *lconn[3];
809         int     i, j;
810         int     c1 = 0, c2 = 0, c3;
811         float   mindif = TEE_ORIENTATION_THRES;
812 
813         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
814 
815         if (econn->count != 3)  /* not a three way junction */
816             continue;
817 
818         links[0] = (Edgel *) econn->conns->to;
819         links[1] = (Edgel *) econn->conns->next->to;
820         links[2] = (Edgel *) econn->conns->next->next->to;
821 
822         for (i = 0; i < 3; ++i)
823         {
824             lconn[i] = (Edge_conn *) prop_get(links[i]->props, EDGE_CONN);
825             if (lconn[i]->count != 2)   /* not a simple continue */
826                 break;
827         }
828         if (i < 3)
829             continue;
830 
831         for (i = 0; i < 2; ++i)
832             for (j = i + 1; j < 3; ++j)
833             {
834                 double absordif;
835                 absordif = absdifforient(links[i]->orient, links[j]->orient);
836 
837                 if (absordif < mindif)
838                 {
839                     c1 = i;
840                     c2 = j;
841                     mindif = absordif;
842                 }
843             }
844 
845         if (mindif >= TEE_ORIENTATION_THRES)
846             continue;
847 
848         econn->c1 = links[c1];
849         econn->c2 = links[c2];
850 
851         list_rm_links(econn->conns);
852         econn->conns = NULL;
853         econn->count = 2;
854 
855         jptr->type = REMOVE_ME;
856 
857         c3 = 3 - c1 - c2;
858         econn = lconn[c3];      /* Edge_conn of the remaining edge */
859         econn->conns = link_alloc((void *)
860                  ((econn->c1 == eptr) ? econn->c2 : econn->c1), EDGE);
861         econn->c1 = econn->c2 = NULL;
862         econn->count = 1;
863         term_list = ref_addtostart((List *) term_list, (void *) links[c3], EDGE);       /* new term */
864         econn->back = term_list;
865     }
866     return (list_rm_links_on_type(juncs, REMOVE_ME));
867 }
868 
869 static Tstring *edge_getloop(Edgel * edge)
870 {
871     List *start = NULL;
872     List *end = NULL;
873     Edge_conn *cptr;
874     Edgel  *eptr;
875     Edgel  *from;
876 
877     if (edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
878         return (NULL);
879 
880     cptr = (Edge_conn *) prop_get(edge->props, EDGE_CONN);
881     if (cptr->count != 2)
882         return (NULL);
883     start = end = dd_link_alloc((void *) edge, EDGE);
884     from = edge;
885     edge->type |= EDGE_LOOP;
886 
887     for (eptr = cptr->c1; eptr != edge && eptr!=NULL; eptr = cptr->c1)
888     {
889         cptr = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
890         if (cptr->c2 != from && cptr->c1 == from)
891             SWAP(Edgel *, cptr->c1, cptr->c2)
892         if (cptr->count == 2 && cptr->c2 != from)
893         {
894             printf("broken list in getloop \n");
895             return(str_make(STRING, start, end));
896         }
897         eptr->type |= EDGE_LOOP;
898         end = dd_link_addtoend(end, dd_link_alloc((void *) eptr, EDGE));
899         from = eptr;
900     }
901 
902     start->last = end;          /* to complete the loop */
903     end->next = start;
904 
905     return (str_make(LOOP, start, end));
906 }
907 
908 static void edge_find_loops(Edgel * edge)
909 {
910     Tstring *string;
911 
912     if (edge == NULL || edge->type & EDGE_GET_LOOP_MASK ||
913         (edge->type & EDGE_GET_CONN_MASK) != EDGE_CONN)
914         return;
915 
916     string = edge_getloop(edge);
917     if (string != NULL)
918         string_list = ref_addtostart((List *) string_list, (void *) string, STRING);
919 }
920 
921 /* lift connected strings out of edge pointer data structure */
922 static Tstring *edge_getstring(Edgel * term)
923 {
924     List *start = NULL;
925     List *end = NULL;
926     Edge_conn *cptr;
927     Edgel  *eptr;
928     Edgel  *from;
929     Tstring *string = NULL;
930 
931 
932     if (term == NULL)
933         return (NULL);
934 
935     cptr = (Edge_conn *) prop_get(term->props, EDGE_CONN);
936     if (cptr->count != 1)
937         return (NULL);
938     start = end = dd_link_alloc((void *) term, EDGE);
939     from = term;
940     term->type |= EDGE_NOT_LOOP;
941 
942     for (eptr = (Edgel *) cptr->conns->to; eptr!=NULL; eptr = cptr->c1)
943     {
944         cptr = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
945         if (cptr->c2 != from )
946             SWAP(Edgel *, cptr->c1, cptr->c2) ;
947 
948         if (cptr->count == 0 || (cptr->count >= 2 && cptr->c2 != from))
949         {
950             printf("broken list in getstring %d\n", cptr->count);
951             break;
952         }
953         eptr->type |= EDGE_NOT_LOOP;
954         end = dd_link_addtoend(end, dd_link_alloc((void *) eptr, EDGE));
955 
956         from = eptr;
957 
958     }
959     string = str_make(STRING, start, end);
960 
961     return (string);
962 }
963 
964 static List *findstrings(List * terms)
965 {
966     List   *tptr;
967     List   *strings = NULL;
968     List   *listindex;
969     Edgel  *endedge;
970 
971     for (tptr = terms; tptr!=NULL; tptr = tptr->next)
972     {
973         Edgel  *startedge = (Edgel *) tptr->to;
974         Tstring *sptr = edge_getstring(startedge);
975         startedge->type |= EDGE_TERMIN;
976     }
977 
978     for (tptr = terms; tptr!=NULL; tptr = tptr->next)
979     {
980         Edgel  *startedge = (Edgel *) tptr->to;
981         Tstring *sptr = edge_getstring(startedge);
982 
983         if ((startedge->type & EDGE_TERMIN))
984         {
985              strings = link_addtostart((List *) strings, link_alloc((void *) sptr, STRING));
986         }
987         startedge->type &= EDGE_SET_CONN_MASK;
988         endedge = (Edgel *)sptr->end->to;
989         endedge->type &= EDGE_SET_CONN_MASK;
990     }
991 
992     for (tptr = terms; tptr!=NULL; tptr = tptr->next)
993     {
994         Edgel  *startedge = (Edgel *) tptr->to;
995         Tstring *sptr = edge_getstring(startedge);
996         startedge->type |= EDGE_TERMIN;
997     }
998 
999     return (strings);
1000 }
1001 
1002 /* old slow version of above NAT 2/7/11 */
1003 static List *findstrings2(List * terms)
1004 {
1005     List   *tptr;
1006     List   *strings = NULL;
1007 
1008     terms = list_copy(terms, (void *(*) ()) NULL, NULL);
1009 
1010     tptr = terms;
1011     while (tptr != NULL)
1012     {
1013        Tstring *sptr = edge_getstring((Edgel *) tptr->to);
1014 
1015        strings = link_addtostart((List *) strings, link_alloc((void *) sptr, STRING));
1016        (void) list_rm_ref(tptr, sptr->end->to, (void (*) ()) NULL);
1017        tptr = link_rm_el(tptr);
1018     }
1019 
1020     return (strings);
1021 }
1022 
1023 
1024 /* process the raw edge rect to determine a sensible connectivity */
1025 void    er_find_edge_strings(Imrect * er)
1026 {
1027     if (er == NULL)
1028         return;
1029 
1030 /* first set conn field of edge type to allow all possible connections */
1031     er_apply_to_all_edges(er, edge_set_conn_type_on, NULL);
1032     er_apply_to_all_edges(er, edge_set_conns, (void *) er);
1033 /* now remove poor orientations */
1034     er_apply_to_all_edges(er, edge_break_conns, (void *) er);
1035 
1036 /*  prune the junctions to simplify linkage */   
1037     junc_list = prunetees(junc_list);
1038     junc_list = prunejuncs(junc_list);
1039     junc_list = prunespurs(junc_list);
1040 /* throw away what we can't deal with */
1041     rmjuncs(junc_list);
1042     list_rm_links(junc_list);
1043 
1044 /* re-connect short gaps minimising orientation differences */
1045     term_list = bridge_small_gaps(er, term_list);
1046 
1047 /* extract initial strings */
1048     string_list = findstrings(term_list);
1049     list_rm_links(term_list);
1050     junc_list = term_list = NULL;
1051 
1052 /* finally set up edge types for data display */
1053     er_apply_to_all_edges(er, edge_set_conn_type, NULL);
1054 /* mop up data which was not linked to termination points */
1055     er_apply_to_all_edges(er, edge_find_loops, NULL);   
1056 
1057     er->props = proplist_addifnp(er->props, (void *) string_list, STRING, str_rm_list, false);
1058 }
1059 
1060 void    er_find_simple_edge_strings(Imrect * er)
1061 /* edge rect */
1062 {
1063     if (er == NULL)
1064         return;
1065 
1066     /* first set conn field of edge type to allow all possible
1067      * connections */
1068     er_apply_to_all_edges(er, edge_set_conn_type_on, NULL);
1069     er_apply_to_all_edges(er, edge_set_conns, (void *) er);
1070 
1071     junc_list = prunespurs(junc_list);
1072     rmjuncs(junc_list);
1073     list_rm_links(junc_list);
1074 
1075     string_list = findstrings(term_list);
1076     list_rm_links(term_list);
1077     junc_list = term_list = NULL;
1078 
1079     er_apply_to_all_edges(er, edge_set_conn_type, NULL);
1080     er_apply_to_all_edges(er, edge_find_loops, NULL);   /* adds to string_list */
1081 
1082     er->props = proplist_addifnp(er->props, (void *) string_list, STRING, str_rm_list, false);
1083 }
1084 
1085 List   *er_specific_edge_strings(Imrect * er, void (*func) ( /* ??? */ ), void *data)
1086 /* edge rect */
1087 {
1088     if (er == NULL)
1089         return ((List *) NULL);
1090 
1091     /* first set conn field using function */
1092     er_apply_to_all_edges(er, func, (void *) data);
1093     er_apply_to_all_edges(er, edge_set_conns, (void *) er);
1094 
1095     junc_list = prunespurs(junc_list);
1096     rmjuncs(junc_list);
1097     list_rm_links(junc_list);
1098 
1099     string_list = findstrings(term_list);
1100     list_rm_links(term_list);
1101     junc_list = term_list = NULL;
1102 
1103     er_apply_to_all_edges(er, edge_set_conn_type, NULL);
1104     er_apply_to_all_edges(er, edge_find_loops, NULL);   /* adds to string_list */
1105 
1106     return (string_list);
1107 }
1108 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.