match.c

A salient-boundary extraction software package based on the paper: S. Wang, T. Kubota, J. M. Siskind

    ei = PNODE(n)->edg_list;
    e = PEDGE(ei/2);

    if (e->nod1 == n) {
        v = PNODE(e->orig_nod1); 
    } else {
        v = PNODE(e->orig_nod2);
    }

    sum = v->pi;
    while (v->blossom_parent != -1) {
        v = PNODE(v->blossom_parent);
        sum += v->pi;
    }

    return sum;
}

#ifdef CC_PROTOTYPE_ANSI
extern int parity_correction (graph *G, stats *scount)
#else
extern int parity_correction (G, scount)
graph *G;
stats *scount;
#endif
{
    nodeptr *np, *npprev = (nodeptr *) NULL;
    int hitme = 0;
    nodeptr *roots = G->roots;
    nodeptr *rstop = G->roots - 1;

#if PRINT_LEVEL
    printf ("   parity_correction ...\n"); 
    fflush (stdout);
#endif

    np = roots + G->unmatched;
    while (np->status != UNMATCHED)  
        np = roots + np->next;
    G->unmatched = np - roots;

    while (np != rstop) {
        if (np->status != UNMATCHED) {
            npprev->next = np->next;
        } else {
            if (np->sum % 2) {
                hitme = 1;
                scount->dualchange_count++;
                if (apply_dual_change (G, PNODE(np->surf), 1)) {
                    fprintf (stderr, "apply_dual_change failed\n");
                    return -1;
                }
                np->sum += 1; 
            }
            npprev = np;
        }
        np = roots + np->next;
    }
    return hitme;
}

#ifdef CC_PROTOTYPE_ANSI
extern int make_dual_change_forest (graph *G, stats *scount)
#else
extern int make_dual_change_forest (G, scount)
graph *G;
stats *scount;
#endif
{
    nodeptr *np;
    int t;
    int delta;
    nodeptr *roots = G->roots;
    nodeptr *rstop = G->roots - 1;

#if PRINT_LEVEL
    printf ("\n   make_dual_change_forest ...\n");
    fflush (stdout);
#endif

    if (parity_correction (G, scount) == -1) {
        fprintf (stderr, "parity_correction failed\n");
        return -1;
    }

    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) 
        np->dad = -1;     /*  Set dad for all trees to -1 */

    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) 
        set_vereinigung (G, PNODE(np->surf));

    /* Set roots to point to theirselves */
    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
        if (np->dad < 0) {
            np->dad = np - roots;
            np->delta = INTEGER_MAX; 
        }
    }

    /* Set others to point to root */
    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
        t = np - roots;
        while (roots[t].dad != t)
            t = roots[t].dad;
        np->dad = t;
    }

#ifdef GREEDY_DUAL_CHANGE
    {
        int npnext;
        int glist = -1;

        /* order the unmatched nodes so that each union appears consecutively */

        for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
            np->tree_processed = 0;
            if (np->dad == np - roots) {
                np->gnext = glist;
                glist = np - roots;
            }
        }

        for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
            if (np->dad != np - roots) {
                np->gnext = roots[np->dad].gnext;
                roots[np->dad].gnext = np - roots;
            }
        }

        for (np = roots + G->unmatched; np != rstop; np = roots + npnext) {
            npnext = np->next;
            np->next = np->gnext;
        }
        G->unmatched = glist;
    }
#endif

    /* Set delta for all vereinigung trees */
    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
	delta = find_dual_change_forest (G, PNODE(np->surf));
	if (delta < roots[np->dad].delta)
	    roots[np->dad].delta = delta;
#ifdef GREEDY_DUAL_CHANGE
        np->tree_processed = 1;
#endif
    } 

    /* Apply_dual_change for all vereinigung trees */
    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
	delta = roots[np->dad].delta;
        scount->dualchange_count++;
        if (delta == 0) {
            scount->dualzero_count++;
        } else {
            if (apply_dual_change (G, PNODE(np->surf), delta)) {
                fprintf (stderr, "apply_dual_change failed\n");
                return -1;
            }
        }
        np->sum += delta; 
    }

    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int match_main_frac (graph *G, stats *scount, srkstuff *srk)
#else
extern int match_main_frac (G, scount, srk)
graph *G;
stats *scount;
srkstuff *srk;
#endif
{
    node *n;
    int i, delta;
    int found_aug = 0;

    /* Just work with one tree   */

    for (i = 0, n = G->nodelist; i < G->nnodes; i++, n++) {
        if (n->status == UNMATCHED) {
	    init_tree (G, n);
            if (grow_tree (G, n, 1, scount, srk, &found_aug)) {
                fprintf (stderr, "grow_tree failed\n");
                return 1;
            }
            while (!found_aug) {
                scount->dualchange_count++;
                delta = find_single_dual_change (G, n);
                if (delta != 0) {
                    if (apply_dual_change (G, n, delta)) {
                        fprintf (stderr, "apply_dual_change failed\n");
                        return 1;
                    }
                } else {
                    scount->dualzero_count++;
                }
                if (grow_tree (G, n, 1, scount, srk, &found_aug)) {
                    fprintf (stderr, "grow_tree failed\n");
                    return 1;
                }
	    }
#if PRINT_LEVEL
            printf ("."); fflush (stdout);
#endif
        }
    }
/*    printf (" %i Dual Changes, %i with delta=0 ",
             scount->dualchange_count, scount->dualzero_count);
    fflush (stdout); */
    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int match_main_more_in_forest (graph *G, stats *scount, srkstuff *srk)
#else
extern int match_main_more_in_forest (G, scount, srk)
graph *G;
stats *scount;
srkstuff *srk;
#endif
{
    nodeptr *np;
    node *n;
    int i, ni, ninext;
    int grow_status_forest;
    int found_aug = 0;
    nodeptr *roots, *rstop;

    /* The unmatched surface nodes should be linked using the mark  */
    /* fields, with G->unmatched pointing to the start of the list. */
    /* G->umatched is assumed to be accurate.                       */

    if (G->unmatched_count == 0) 
	return 0;

    /* ********************************* */
    /* First init all forests            */
    /* ********************************* */

    G->roots = CC_SAFE_MALLOC (G->unmatched_count, nodeptr);
    if (!G->roots) {
        fprintf (stderr, "out of memory in match_main_more_in_forest\n");
        return 1;
    }
    roots = G->roots;
    rstop = G->roots - 1;

    for (i = 0, ni = G->unmatched; ni != -1; ni = ninext, i++) {
        n = PNODE(ni);
        ninext = n->mark;
        n->mark = 0;
        roots[i].status = UNMATCHED;
        roots[i].surf = ni;
        roots[i].sum = find_parity_sum (G, ni);
        roots[i].next = i+1;
        init_tree (G, n);
        n->tree_root = i;
    }
    roots[i - 1].next = -1;
    G->unmatched = 0;

/*    printf ("\nTry to grow the trees in the forest directly\n");
    fflush (stdout);  */

    /* ************************************ */
    /* Try to grow all forests directly     */
    /* ************************************ */

    for (np = roots + G->unmatched; np != rstop; np = roots + np->next) {
        n = PNODE(np->surf);
        if (np->status == UNMATCHED) {
            if (grow_tree (G, n, 0, scount, srk, &found_aug)) {
                fprintf (stderr, "grow_tree failed\n");
                return 1;
            }
            if (found_aug) {	 
/*                printf ("."); fflush (stdout);  */
                if (G->unmatched_count == 0) {
                    return 0;
                }
	    }
        }
    }

    /* *************************** */
    /* Work with tree-vereinigung  */
    /* *************************** */

/*    printf ("\nNow work on tree-vereinigung in a forest (%i points)\n",
                        G->unmatched_count / 2);
    fflush (stdout); */

    /* first make sure that all trees have the correct parity */

    if (parity_correction (G, scount) == -1) {
        fprintf (stderr, "parity_correction failed\n");
        return 1;
    }

    while (G->unmatched_count > 0) {
        if (make_dual_change_forest (G, scount) == -1) {
            fprintf (stderr, "make_dual_change_forest failed\n");
            return 1;
        }
        do {
	    grow_status_forest = 0;
            for (np = roots + G->unmatched; np != rstop; np = roots+np->next) {
		n = PNODE(np->surf);
                if (np->status == UNMATCHED) {
		    if (grow_tree (G, n, 0, scount, srk, &found_aug)) {
                        fprintf (stderr, "grow_tree failed\n");
                        return 1;
                    }
		    if (found_aug) { 
/*		        printf ("."); fflush (stdout);  */
		        if (G->unmatched_count == 0) {
                            goto DONE;
		        }
		        grow_status_forest = 1;
		    }
	        }
            }
	} while (grow_status_forest);
    }

DONE:

    G->unmatched = -1;
    CC_IFFREE (G->roots, nodeptr);

/*    printf ("\n %i Dual Changes, %i with delta=0 ",
	       scount->dualchange_count, scount->dualzero_count);
    printf ("| %i Expands ", scount->expand_count);
    printf ("| %i Shrinks ", scount->shrink_count);
    fflush (stdout);  */

    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int match_main_forest (graph *G, stats *scount, srkstuff *srk)
#else
extern int match_main_forest (G, scount, srk)
graph *G;
stats *scount;
srkstuff *srk;
#endif
{
    nodeptr *np;
    node *n;
    int i, ni, ninext;
    int grow_status_forest;
    int found_aug = 0;
    int delta, delta2;
    int do_parity = 1;
    nodeptr *roots, *rstop;

/*    printf ("match_main_forest (%d points)\n", G->unmatched_count / 2);
    fflush (stdout);  */

    if (G->unmatched_count == 0) {
	return 0;
    }

    /* ********************************* */
    /* First init all forests            */
    /* ********************************* */

    G->roots = CC_SAFE_MALLOC (G->unmatched_count, nodeptr);
    if (!G->roots) {
        fprintf (stderr, "out of memory in match_main_more_in_forest\n");
        return 1;
    }
    roots = G->roots;
    rstop = G->roots - 1;

    for (i = 0, ni = G->unmatched; ni != -1; ni = ninext, i++) {
        n = PNODE(ni);
        ninext = n->mark;
        n->mark = 0;
        roots[i].status = UNMATCHED;
        roots[i].surf = ni;
        roots[i].sum = find_parity_sum (G, ni);
        roots[i].next = i+1;
        init_tree (G, n);
        n->tree_root = i;
    }
    roots[i - 1].next = -1;
    G->unmatched = 0;

    /* ********************************* */
    /* Work with a forest                */
    /* ********************************* */

    while (G->unmatched_count > 0) {
        do {
	    grow_status_forest = 0;
            for (np = roots + G->unmatched; np != rstop; np = roots+np->next) {
		n = PNODE(np->surf);
                if (np->status == UNMATCHED) {
		    if (grow_tree (G, n, 0, scount, srk, &found_aug)) {
                        fprintf (stderr, "grow_tree failed\n");
                        return 1;
                    }
		    if (found_aug) {
/*		        printf ("."); fflush (stdout);  */
		        if (G->unmatched_count == 0) {
                            goto DONE;
                        }
		        grow_status_forest = 1;
                    }
		}
	    }
	} while (grow_status_forest);

        if (G->unmatched_count > 0 && do_parity) {
            if (parity_correction (G, scount) == -1) {
                fprintf (stderr, "parity_correction failed\n");
                return 1;
            }
            do_parity = 0;
        }
    
	if (G->unmatched_count > 0 && !do_parity) {
	    delta = INTEGER_MAX;
	    scount->dualchange_count++;
            for (np = roots + G->unmatched; np != rstop; np = roots+np->next) {
		n = PNODE(np->surf);
                if (np->status == UNMATCHED) {
		    delta2 = find_single_dual_change (G, n);
		    if (delta2 < delta) {
		        delta = delta2;
                    }
                }
	    } 

	    if (delta == 0) {
		scount->dualzero_count++;
            } else {
                for (np = roots+G->unmatched; np!=rstop; np = roots+np->next) {
		    n = PNODE(np->surf);
                    if (np->status == UNMATCHED) {
		        if (apply_dual_change (G, n, delta)) {
                            fprintf (stderr, "apply_dual_change failed\n");
                            return 1;
                        }
                        np->sum += delta; 
                    }
		}
	    }
	}
    }

DONE:

    G->unmatched = -1;
    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int match_main_tree (graph *G, stats *scount, srkstuff *srk)
#else
extern int match_main_tree (G, scount, srk)
graph *G;
stats *scount;
srkstuff *srk;
#endif
{
    nodeptr *np;
    node *n;
    int i, ni, ninext;
    int found_aug = 0;
    int delta;
    nodeptr *roots, *rstop;

/*    printf ("match_main_tree (%d points)\n", G->unmatched_count / 2);
    fflush (stdout);  */

    if (G->unmatched_count == 0) {
	return 0;
    }

    /* ********************************* */
    /* First init all forests            */
    /* ********************************* */

    G->roots