head	1.2;
access;
symbols;
locks; strict;
comment	@// @;


1.2
date	95.01.13.00.51.45;	author rjj;	state Exp;
branches;
next	1.1;

1.1
date	94.09.23.20.13.50;	author rjj;	state Exp;
branches;
next	;


desc
@Implementation file for the Sequential Component Labeling algorithm.
@


1.2
log
@Added standard error.
Reformated to have shorter lines for inclusion in other documents.
Corrected a bad error which incremented the entire image rather than
  just one point in the image.
@
text
@// sequential-component-labeling.c
//                      Section: 11.3, Sequential Component Labeling
//      Copyright 1994, Center for Computer Vision and Visualization,
//      University of Florida.  All rights reserved.

#include "sequential-component-labeling.h"
#include "shaped-pointset.h"
#include "PSIter.h"
#include "Nbh.h"


// For now we will define this function a returning a u_char valued
//   image.  This will allow labeling images with up to 255 connected
//   components.
// If this turns out to be too few, then returning an int valued
//   image is the solution.

IA_Image<IA_Point<int>,u_char>
sequential_component_labeling(
    const IA_Image<IA_Point<int>,IA_Bit> & a,
    const IA_Neighborhood<IA_Point<int>,
    IA_Point<int> > & nbhd )
{
    u_char  label = 0;
    IA_Image<IA_Point<int>,u_char>
	b = a, c = a, udi_a = a;

    IA_Point<int> p;  // Outer loop index var

    IA_PSIter<IA_Point<int> >
	psiter( a.domain() );

    // Now loop through the domain, looking for as yet unlabeled points.
    while( psiter( p ) ) {

	if ( b(p) == 1 ) {
	    // Found a new point that has not been labeled yet.
	    b[p] += ++label;
	}

	// Now propagate this label to the rest of the component
	//   based on the connectivity implicit in the neighborhood
	while( b != c ) {
	    c = b;
	    b = max( c, nbhd ) * udi_a;
	}
    }

    return  b - udi_a;
}



// Use 4-connected criterion
IA_Image<IA_Point<int>,u_char>
sequential_component_labeling_4(
    const IA_Image<IA_Point<int>,IA_Bit> & im )
{
    unsigned int dimen( im.domain().dim() );

    // Invoke the general function with the 4-connected neighborhood
    return
	sequential_component_labeling(
	    im,
	    IA_Neighborhood<IA_Point<int>,IA_Point<int> >(
		dimen, cross_hair( extend_to_point( 0, dimen ), 1 )
		) );
}


// Use 8-connected criterion
IA_Image<IA_Point<int>,u_char>
sequential_component_labeling_8( const IA_Image<IA_Point<int>,IA_Bit> & im )
{
    unsigned int dimen( im.domain().dim() );

    // Invoke the general function with the 8-connected neighborhood
    return
	sequential_component_labeling(
	    im,
	    IA_Neighborhood<IA_Point<int>,IA_Point<int> >(
		dimen, IA_boxy_pset( extend_to_point( -1, dimen ),
				     extend_to_point(  1, dimen ) )
		) );
}
@


1.1
log
@Initial revision
@
text
@d1 2
a2 1
// sequential-component-labeling.c  Section: 11.3
d13 1
a13 1
//   image.  This will allow labeling images with upto 255 connected
d19 4
a22 3
sequential_component_labeling( const IA_Image<IA_Point<int>,IA_Bit> & a,
			       const IA_Neighborhood<IA_Point<int>,
			                             IA_Point<int> > & nbhd )
d24 1
a24 1
    u_char  l = 0;
d26 1
a26 1
	b( a ), c( a ), udi_a( a );
d38 1
a38 1
	    b += ++l;
d54 1
a54 1
// Use 4-connected criteria
d56 2
a57 1
sequential_component_labeling_4( const IA_Image<IA_Point<int>,IA_Bit> & im )
d71 1
a71 1
// Use 8-connected criteria
@
