phblob.c

Go to the documentation of this file.

/* ---------------------------------------------------------------------------
    Phission :
        Realtime Vision Processing System

    Copyright (C) 2003-2006 Philip D.S. Thoren (pthoren@cs.uml.edu)
    University of Massachusetts at Lowell,
    Laboratory for Artificial Intelligence and Robotics

    This file is part of Phission.

    Phission is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    Phission is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with Phission; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 ---------------------------------------------------------------------------*/
#ifdef HAVE_CONFIG_H
    #include <phissionconfig.h>
#endif

#include <phStandard.h>

#include <ImageGfx.h>
#include <ImageUtil.h>

#include <phQuicksort.h>
#include <phblob.h>

#include <phError.h>
#include <phMemory.h>
#include <phPrint.h>

/* ---------------------------------------------------------------------- */
#ifdef __cplusplus
extern "C" {
#endif

/* ---------------------------------------------------------------------- */
__inline__ phblob_line_segment *phblob_get_segment( const int32_t index,
                                                    phblob_line_segment *const line_array);

__inline__ phblob_line_segment *phblob_get_next_segment(const phblob_line_segment *const seg,
                                                              phblob_line_segment *const line_array);

__inline__ phblob *phblob_get_next_blob(const phblob *const blob,
                                              phblob *const blobs);

__inline__ int32_t phblob_compare   ( const void *_one, const void *_two );

/* ---------------------------------------------------------------------- */
__inline__ phblob_line_segment *phblob_get_segment( const int32_t index,
                                                    phblob_line_segment *const line_array)
{
    /* Get the line segment by indexing into the pool */
    if (index >= 0) 
        return &(line_array[index]);
    else 
        return NULL;
}
/* ---------------------------------------------------------------------- */
__inline__ phblob_line_segment *phblob_get_next_segment(const phblob_line_segment *const seg,
                                                              phblob_line_segment *const line_array )
{
    int32_t next_index = seg->next_index;
    /* Get the line segment by indexing into the pool */
    if (next_index >= 0) 
        return &(line_array[next_index]);
    else 
        return NULL;
}
 
/* ---------------------------------------------------------------------- */
__inline__ phblob *phblob_get_next_blob( const phblob *const blob,
                                               phblob *const blobs )
{
    int32_t next_index = blob->next_index;
    /* Get the line segment by indexing into the pool */
    if (next_index >= 0) 
        return &(blobs[next_index]);
    else 
        return NULL;
}

/* ---------------------------------------------------------------------- */
int phblob_data_new ( phblob_data **data )
{
    phFUNCTION("phblob_data_new")

    if (data == NULL) return phFAIL;

    (*data) = (phblob_data *)phCalloc(1,sizeof(phblob_data));
    phCHECK_PTR(*data,"phCalloc", "phCalloc failed.");
    
    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
int phblob_data_init( phblob_data *data  )
{
    phFUNCTION("phblob_data_init")

    if (data == NULL) return phFAIL;

    phMemset(data,0,sizeof(phblob_data));
    
    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
int phblob_data_reset( phblob_data *data )
{
    if (data == NULL) return phFAIL;

    phFree(data->lines);
    phFree(data->rows);
    phFree(data->rowindex);
    phFree(data->blobs);
    phMemset(data,0,sizeof(phblob_data));
    
    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
int phblob_data_free( phblob_data **data )
{
    phFUNCTION("phblob_data_free")

    if (data == NULL) return phFAIL;

    rc = phblob_data_reset( *data );
    phCHECK_RC(rc,NULL,"phblob_data_reset");
    
    phFree(*data);
    
    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
int phblob_data_copy( phblob_data *in,
                      phblob_data *out)
{
    phFUNCTION("phblob_data_copy")

    #if 0
    int32_t i = 0;
    int32_t index = 0;
    
    int32_t             total_lines     = 0;
    phblob_line_segment *line_array     = NULL;
    int32_t             total_rows      = 0;
    phblob_line_segment **row_ptr_array = NULL;
    int32_t             *row_index_array= NULL;
    int32_t             total_blobs     = 0;
    phblob              *blob_array     = NULL;
    #endif
        
    #if 0
    /*----------------------------------------------------------------------*/
    /* Copy the line information and relink the pointers too */
    /*----------------------------------------------------------------------*/
    if (in->nlines > 0)
    {
        phDALLOC_RESIZE(out->lines,
                        out->lines_size,
                        in->nlines,
                        phblob_line_segment );
    }
    
    out->nlines = in->nlines;
    
    if ((in->lines != NULL) && (in->nlines > 0))
    {
        phMemcpy(out->lines, in->lines, out->lines_size);
        
        /* relink the line segment ptrs to the addresses for the 
         * new array */
        rc = phblob_data_relink_line_ptrs( out );
        phPRINT_RC(rc,NULL,"relink_line_ptrs");
    }
    
    /*----------------------------------------------------------------------*/
    /* Copy the row data */
    /*----------------------------------------------------------------------*/
    if (in->nrows > 0)
    {
        phDALLOC_RESIZE(out->rows,     out->rows_size,
                        in->nrows,     phblob_line_segment *);
        phDALLOC_RESIZE(out->rowindex, out->rowindex_size,
                        in->nrows,     int32_t);
    }
    
    out->nrows = in->nrows;
    
    if ((in->rowindex != NULL) && (out->nrows > 0))
    {
        phMemcpy(out->rowindex, in->rowindex, out->rowindex_size);
        
        /* Set the pointers to the appropriate ptr into the
         * line array */
        for (i = 0; i < in->nrows; i++)
        {
            index = out->rowindex[i];
            
            /* -1 == invalid */
            if (index >= 0) out->rows[i] = &(out->lines[index]);
        }
    }
    #endif
    /*----------------------------------------------------------------------*/
    /* Copy the blob data */
    /*----------------------------------------------------------------------*/
    if (in->nblobs > 0)
    {
        phDALLOC_RESIZE(out->blobs,
                        out->blobs_size,
                        in->nblobs,
                        phblob );
    }

    out->nblobs = in->nblobs;

    if ((in->blobs != NULL) && (out->nblobs > 0))
    {
        phMemcpy(out->blobs, in->blobs, out->blobs_size );
        
        #if 0
        /* relink the ptrs to the line segments */
        for (i = 0; i < in->nblobs; i++ )
        {
            index = out->blobs[i].last_segment_index;
            if (index >= 0)
                out->blobs[i].last_segment =
                    &(out->lines[index]);
            
            index = out->blobs[i].first_segment_index;
            if (index >= 0)
                out->blobs[i].first_segment =
                    &(out->lines[index]);
            
            index = out->blobs[i].next_index;
            if (index >= 0)
                out->blobs[i].next = &(out->blobs[index]);
            
            index = out->blobs[i].previous_index;
            if (index >= 0)
                out->blobs[i].previous = &(out->blobs[index]);
        }
        #endif
    }

    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
int phblob_data_relink_line_ptrs( phblob_data *data )
{
    uint32_t            i       = 0;
    uint32_t            nlines  = 0;
    uint32_t            j       = 0;
    int32_t             index   = 0;
    phblob_line_segment *lines  = NULL;

    if (data == NULL) return phFAIL;

    lines   = data->lines;
    nlines  = data->nlines;
    
    for (i = 0; i < nlines; i++ )
    {
        index = lines[i].next_index;
        if (index >= 0)
            lines[i].next = &(lines[index]);
        
        index = lines[i].previous_index;
        if (index >= 0)
            lines[i].previous = &(lines[index]);
        
        index = lines[i].first_up_index;
        if (index >= 0)
            lines[i].first_up = &(lines[index]);
        
        index = lines[i].first_down_index;
        if (index >= 0)
            lines[i].first_down = &(lines[index]);
        
        index = lines[i].last_up_index;
        if (index >= 0)
            lines[i].last_up = &(lines[index]);
        
        index = lines[i].last_down_index;
        if (index >= 0)
            lines[i].last_down = &(lines[index]);
        
        index = lines[i].left_index;
        if (index >= 0)
            lines[i].left = &(lines[index]);
        
        index = lines[i].right_index;
        if (index >= 0)
            lines[i].right = &(lines[index]);

        for (j = 0; j < phSEGMENT_CONNECTION_COUNT; j++)
        {
            index = lines[i].connection_index[j];
            if (index >= 0)
                lines[i].connection[j] = &(lines[index]);
        }
    }

    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
int phblob_find_line_segments_color(phblob_args *args,
                                    phblob_data *data )
{
    phFUNCTION("phblob_find_line_segments_color")

    uint32_t i = 0;
    uint32_t j = 0;
    
    /* make local copies of these */
    uint8_t             *imgptr     = *(args->imgptr);
    uint32_t            width       = args->width;
    uint32_t            height      = args->height;
    uint8_t             depth       = args->depth;
    /* uint32_t            format      = args->format; */
    phColor             *incolors   = *args->incolor;
    phColor             *thresholds = *args->threshold;
    volatile uint32_t   nColors     = *args->nColors;
    phColor             incolor;
    phColor             threshold;

    phblob_line_segment *line_array          = (data->lines);
    uint32_t            line_array_size      = (data->lines_size);
    phblob_line_segment **row_ptr_array      = (data->rows);
    uint32_t            row_ptr_array_size   = (data->rows_size);
    int32_t             *row_index_array     = (data->rowindex);
    uint32_t            row_index_array_size = (data->rowindex_size);
 

    /* Used for comparison in the search for a color and
     * whether it's within the giving threshold. */
    int32_t     diff[phCOLOR_MAXBYTES]  = {0}; 
    int32_t     diff_temp_1             = 0;
    int32_t     diff_temp_2             = 0;
    uint32_t    color_matches           = 0;
    uint32_t    matched                 = 0;
    uint32_t    k                       = 0;
    uint32_t    l                       = 0;
    /* max elements for a color */
    uint32_t    max_compare = 1;
   
    /* Used in line segment discovery */
    int32_t             larray_index        = 0;
    phblob_line_segment *current_segment    = NULL;
    phblob_line_segment *last_segment       = NULL;

    uint32_t half_npixels = ((width * height) + ((width * height) % 2)) / 2;

    /* 0.) Make sure we have enough memory and all variables are
     * initialized */
  
    /* A.) allocate the max number of segments possible for the image:
     * 
     * i.) the maximum number of lines is when every other pixel in a row
     * matches and is ((width * height) / 2) line segments,
     *  
     * ii.) the minimum number of lines when all the pixels match is height,
     */
    phDALLOC(line_array,
                  line_array_size,
                  half_npixels,
                  phblob_line_segment);

    /* b.) row_ptr_array is used to store line segments within a row of the image */
    phDALLOC(row_ptr_array,
             row_ptr_array_size,
             height,
             phblob_line_segment *);

    /* c.) row_index_array stores the index into the row_ptr_array array for 
     * the user can since a phMemcpy of the row_ptr_array/line_array 
     * invalidates the pointer values */
    phDALLOC(row_index_array,
             row_index_array_size,
             height,
             int32_t);

    if (incolors != NULL)
        max_compare = phColorDepth[incolors[0].type];
    
    for (i = 0; (i < height) && (max_compare > 0); i++)
    {
        /* -1 is the value used to denote no index */
        row_index_array[i] = -1;
        
        /* reset and initialize all the line variables */
        current_segment = NULL;
        last_segment = NULL;
        
        for (j = 0; j < width; j++)
        {
            /* just in case there are no colors being checked */
            for ( l = 0; (l < nColors) && (matched == 0); l++ )
            {
                incolor = incolors[l];
                threshold = thresholds[l];
                
                color_matches = 1;
                for ( k = 0; 
                      (k < max_compare) && (color_matches > 0); 
                      k++ )
                {
                    diff_temp_1 = incolor.array.v[k];
                    diff_temp_2 = imgptr[k];
                    /* Quicker than calling abs     ( ??? ) */
                    diff[k] = ((diff_temp_1 >= diff_temp_2) ?
                               (diff_temp_1 - diff_temp_2) : 
                               (diff_temp_2 - diff_temp_1));
                    if (diff[k] > threshold.array.v[k]) color_matches = 0;
                }
                matched = (color_matches) ? 1 : 0;
            }
            /* if the pixel color matches, ... */
            if (matched > 0)
            {
                /* reset matched here, chances are, this happens less */
                matched = 0;
                /* create a new phblob_line_segment only if we don't have one */
                if (current_segment == NULL)
                {
                    /* there's always enough */
                    current_segment = &(line_array[larray_index]);
                    current_segment->index = larray_index++;
                    /* initialize all the memory to have all bits set */
                    current_segment->next_index = -1; /* no next */
                    current_segment->blob_index = -1; /* no blob */
                    current_segment->previous_index = -1; /* no previous */
                    current_segment->previous_visit_index = -1; /* no previous */
                    phMemset(current_segment->connection_index,
                           255,
                           phSEGMENT_CONNECTION_COUNT * sizeof(uint32_t));
                    
                    /* set the start point */
                    current_segment->a.y = current_segment->b.y = i;
                    current_segment->a.x = j;
                    
                    /* first segment for the row */
                    if (last_segment == NULL)
                    {
                        row_ptr_array[i] = current_segment;
                        row_index_array[i] = current_segment->index;
                    }
                    /* link segment to last segment */
                    else
                    {
                        current_segment->previous = last_segment;
                        current_segment->previous_index = last_segment->index;
                        
                        last_segment->next = current_segment;
                        last_segment->next_index = current_segment->index;
                    }
                }
            }
            /* if the pixel doesn't match ... */
            /* ... and we've created a segment,
             * set the end point,
             * set the last segment to this segment,
             * reset the current segment to NULL,
             * 
             * this prepares for a search of another line segment */
            else if (current_segment != NULL)
            {
                /* set the end point to the last valid pixel match*/
                current_segment->b.x = j-1;
                /* set the length - all lines in this routine
                 * will be horizontal, which makes the length calculation
                 * very easy:
                 *  b.x - a.x ; if a.x & b.x == 0, then length == 1; 
                 * this means we need to add 1 to every length */
                current_segment->length = (current_segment->b.x - 
                                           current_segment->a.x) + 1;

                if (current_segment->length > 0)
                    last_segment = current_segment;
                else
                    larray_index--;
                current_segment = NULL;
            }

            imgptr += depth;
        }
        /* make sure if the segment goes to the edge of 
         * the image that it's added */
        if (current_segment != NULL)
        {
            /* set the end point */
            /* we only get here when j == width,
             * the real endpoint is j - 1 */
            current_segment->b.x = j - 1;
            /* set the length - all lines in this routine
             * will be horizontal, which makes the length calculation
             * very easy. 
             * Again, if a.x == b.x, the length is 1 so we need to add +1
             * to every line segment */
            current_segment->length = (current_segment->b.x - 
                                       current_segment->a.x) + 1;
            
            last_segment = current_segment;
            current_segment = NULL;
        }
    }
    
    data->nlines        = larray_index;
    data->lines         = line_array;
    data->lines_size    = line_array_size;
    data->nrows         = height;
    data->rows          = row_ptr_array;
    data->rows_size     = row_ptr_array_size;
    data->rowindex      = row_index_array;
    data->rowindex_size = row_index_array_size;
    data->blob_method   = phBLOB_COLOR;
    data->nblobs        = 0;

    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
int phblob_find_line_segments_neighbor(phblob_args *args,
                                       phblob_data *data )
{
    phFUNCTION("phblob_find_line_segments_neighbor")

    uint32_t    i   = 0;
    uint32_t    j   = 0;
    int         done= 0;
    
    /* make local copies of these */
    uint8_t  *imgptr    = *(args->imgptr);
    uint32_t  width     = args->width;
    uint32_t  height    = args->height;
    uint8_t   depth     = args->depth;
    //uint32_t  format    = args->format;

    phblob_line_segment *line_array          = (data->lines);
    uint32_t            line_array_size     = (data->lines_size);
    phblob_line_segment **row_ptr_array       = (data->rows);
    uint32_t            row_ptr_array_size  = (data->rows_size);
    int32_t            *row_index_array     = (data->rowindex);
    uint32_t            row_index_array_size= (data->rowindex_size);
 

    /* Used for comparison in the search for a color and
     * whether it's within the giving threshold. */
    uint32_t    matched                 = 0;
    uint32_t    k                       = 0;
    //uint32_t    l                       = 0;

    uint32_t    have_value              = 0;
    int32_t     value_high              = 0;
    int32_t     value_low               = 0;
    int32_t     value                   = 0;
    int32_t     *lower_threshold        = (int32_t *)args->lower_threshold;
    int32_t     *upper_threshold        = (int32_t *)args->upper_threshold;
    int32_t     *loop_threshold         = (int32_t *)args->loop_threshold;
    int32_t     current_value[phCOLOR_MAXELEMS];
    int32_t     current_value_high[phCOLOR_MAXELEMS];
    int32_t     current_value_low[phCOLOR_MAXELEMS];
   
    /* Used in line segment discovery */
    int32_t             larray_index        = 0;
    phblob_line_segment *current_segment    = NULL;
    int32_t             last_segment_index  = -1;

    //uint32_t npixels = ((width * height) + ((width * height) % 2));

    /* 0.) Make sure we have enough memory and all variables are
     * initialized */
  
    /* A.) allocate the max number of segments possible for the image:
     * 
     * i.) The maximum number of pixels when we're considering every pixel
     * is npixels;
     * 
     *  
     * ii.) the minimum number of lines when all the pixels match is height,
     */
#if 0
    phDALLOC(line_array,
             line_array_size,
             npixels,
             phblob_line_segment);
#endif
       
    /* b.) row_ptr_array is used to store line segments within a row of the image */
    phDALLOC(row_ptr_array,
             row_ptr_array_size,
             height,
             phblob_line_segment *);

    /* c.) row_index_array stores the index into the row_ptr_array array for 
     * the user can since a phMemcpy of the row_ptr_array/line_array 
     * invalidates the pointer values */
    phDALLOC(row_index_array,
             row_index_array_size,
             height,
             int32_t);
#if 0
    phPRINT("lower: %3d %3d %3d %3d\n", lower_threshold[0], lower_threshold[1],
                                        lower_threshold[2], lower_threshold[3]);
    phPRINT("upper: %3d %3d %3d %3d\n", upper_threshold[0], upper_threshold[1],
                                        upper_threshold[2], upper_threshold[3]);
    phPRINT("loop : %3d %3d %3d %3d\n", loop_threshold[0], loop_threshold[1],
                                        loop_threshold[2], loop_threshold[3]);
#endif

    phMemset(current_value,     0,phCOLOR_MAXELEMS*sizeof(int32_t));
    phMemset(current_value_low, 0,phCOLOR_MAXELEMS*sizeof(int32_t));
    phMemset(current_value_high,0,phCOLOR_MAXELEMS*sizeof(int32_t));

    for (i = 0; i < height; i++)
    {
        /* -1 is the value used to denote no index */
        row_index_array[i] = -1;
        row_ptr_array[i] = NULL;
        
        /* reset and initialize all the line variables */
        current_segment     = NULL;
        last_segment_index  = -1;
        have_value          = 0;
        
        j = 0;
        while (j < width)
        {
            if (have_value == 0)
            {
                for (k = 0; k < depth; k++ )
                {
                    current_value[k] = 
                        current_value_high[k] = 
                        current_value_low[k] = imgptr[k];
                }
                have_value = 1;
                matched = 1;
            }
            else 
            {
                for (k = 0; k < depth; k++ )
                {
                    value       = imgptr[k];
                    value_high  = current_value[k] + upper_threshold[k];
                    value_low   = current_value[k] - lower_threshold[k];

                    if (loop_threshold[k])
                    {
                        value_high = value_high % 256;
                        if (value_low < 0) value_low = 255 + value_low + 1;
                    }
                    else
                    {
                        if (value_high > 255) value_high = 255;
                        if (value_low  <   0) value_low  =   0;
                    }

                    /* Check to see if the value threshold markers have looped
                     * around the highest value mark */
                    if (value_low <= value_high) 
                    {
                        if ((value >= value_low) && (value <= value_high))
                        {
                            matched++;
                        }
                    }
                    else 
                    {
                        if (loop_threshold[k] && 
                            ((value >= value_low) || (value <= value_high)))
                        {
                            matched++;
                        }
                    }
                }
                if (matched != depth) matched = 0;
            }
            
            /* if the pixel color matches, ... */
            if (matched > 0)
            {
                /* reset matched here, chances are, this happens less */
                matched = 0;
                /* create a new line_segment only if we don't have one */
                if (current_segment == NULL)
                {
                    larray_index++;
                    phDALLOC_GROW(line_array,
                                  line_array_size,
                                  larray_index,
                                  phblob_line_segment);
                    /* there's always enough */
                    current_segment         = &(line_array[larray_index-1]);
                    phMemset(current_segment,0,sizeof(phblob_line_segment));
                    current_segment->index  = larray_index-1;
                    /* initialize all the memory to have all bits set */
                    current_segment->next_index             = -1; /* no next */
                    current_segment->blob_index             = -1; /* no blob */
                    current_segment->previous_index         = -1; /* no previous */
                    current_segment->previous_visit_index   = -1; /* no previous */
                    phMemset(current_segment->connection_index,
                             255,
                             phSEGMENT_CONNECTION_COUNT * sizeof(uint32_t));

                    /* Set the color information */
                    phMemcpy(current_segment->value,
                             current_value,
                             depth*sizeof(int32_t));
                    phMemcpy(current_segment->value_low,
                             current_value_low,
                             depth*sizeof(int32_t));
                    phMemcpy(current_segment->value_high,
                             current_value_high,
                             depth*sizeof(int32_t));
#if 0
                    phPRINT("current: %3d %3d %3d %3d\n",
                            current_value[0],
                            current_value[1],
                            current_value[2],
                            current_value[3] );
                    phPRINT("low    : %3d %3d %3d %3d\n",
                            current_value_low[0],
                            current_value_low[1],
                            current_value_low[2],
                            current_value_low[3] );
                    phPRINT("high   : %3d %3d %3d %3d\n",
                            current_value_high[0],
                            current_value_high[1],
                            current_value_high[2],
                            current_value_high[3] );
#endif
                    
                    /* set the start point */
                    current_segment->a.y = current_segment->b.y = i;
                    current_segment->a.x = j;
                    
                    /* first segment for the row */
                    if (last_segment_index < 0)
                    {
                        row_index_array[i] = current_segment->index;
                    }
                    /* link segment to last segment */
                    else
                    {
                        current_segment->previous_index = last_segment_index;
                        line_array[last_segment_index].next_index = 
                                                      current_segment->index;
                    }
                }
                else
                {
                    for (k = 0; k < depth; k++ )
                    {
                        if (current_value_low[k] > imgptr[k])
                            current_value_low[k] = imgptr[k];
                        if (current_value_high[k] < imgptr[k])
                            current_value_high[k] = imgptr[k];
                        /* moving value */
#if 1
                        current_value[k] = (current_value_high[k] + 
                                            current_value_low[k]) / 2;
#endif
                    }
                }

                /* only increment when we've matched */
                imgptr += depth;

                /* because we're looking at every pixel as a different 
                 * potential start for a line segment, and not just whether
                 * it matches, we have to begin a new line segment the next
                 * time we loop; So, only increment j if we're matching; The
                 * next part of this if block ("else if (current_segment != NULL)"),
                 * Will reset the line segment information and the next 
                 * iteration of this loop will create a new 'matched' segment; 
                 * That leads us back here to incrementing 'j' and eventually
                 * getting to the end of the current line in the image */
                j++;
            }
            /* if the pixel doesn't match ... */
            /* ... and we've created a segment,
             * set the end point,
             * set the last segment to this segment,
             * reset the current segment to NULL,
             * 
             * this prepares for a search of another line segment */
            else if (current_segment != NULL)
            {
                /* set the end point */
                /* The j here is the pixel that didn't match, so 
                 * we have to subtract 1 from j */
                current_segment->b.x = j-1;
                
                /* set the length - all lines in this routine
                 * will be horizontal, which makes the length calculation
                 * very easy. */
                current_segment->length = (current_segment->b.x - 
                                           current_segment->a.x)+1;
                
                if (current_segment->length > 0)
                    last_segment_index = current_segment->index;
                else
                    larray_index--;
                
                phMemcpy(current_segment->value,
                         current_value,
                         depth*sizeof(int32_t));
                phMemcpy(current_segment->value_low,
                         current_value_low,
                         depth*sizeof(int32_t));
                phMemcpy(current_segment->value_high,
                         current_value_high,
                         depth*sizeof(int32_t));
                
                current_segment = NULL;
                have_value      = 0;
            }
        }
        /* make sure if the segment goes to the edge of 
         * the image that it's added */
        if (current_segment != NULL)
        {
            /* set the end point */
            /* ... because we only get here when j == width,
             * the real end point is j - 1 */
            current_segment->b.x = j-1;
            /* set the length - all lines in this routine
             * will be horizontal, which makes the length calculation
             * very easy. */
            current_segment->length = (current_segment->b.x - 
                                       current_segment->a.x) + 1;
            
            last_segment_index = current_segment->index;
            current_segment = NULL;
        }
    }

    /* Because we're using phDALLOC_GROW, we need to set the pointers
     * after we've created all the line segments */
    for (i = 0; i < height; i++ )
    {
        if (row_index_array[i] >= 0)
        {
            current_segment = &(line_array[row_index_array[i]]);
            if (current_segment->index != row_index_array[i])
            {
                phPROGRESS("!!! WARNING !!! %d != %d\n",
                            current_segment->index,
                            row_index_array[i]);
            }
            row_ptr_array[i] = current_segment;
            done = 0;
            
            do 
            {
                /* Set the previous pointer */
                if (current_segment->previous_index >= 0)
                {
                    current_segment->previous = 
                        &(line_array[current_segment->previous_index]);
                }
                else
                {
                    current_segment->previous = NULL;
                }
                /* set the next pointer */
                if (current_segment->next_index >= 0)
                {
                    current_segment = (current_segment->next = 
                        &(line_array[current_segment->next_index]));
                }
                else
                {
                    current_segment->next = NULL;
                    done = 1;
                }
            }
            while (!done);
        }
    }
     
    data->nlines        = larray_index;
    data->lines         = line_array;
    data->lines_size    = line_array_size;
    data->nrows         = height;
    data->rows          = row_ptr_array;
    data->rows_size     = row_ptr_array_size;
    data->rowindex      = row_index_array;
    data->rowindex_size = row_index_array_size;
    data->blob_method   = phBLOB_NEIGHBOR;
    data->nblobs        = 0;

    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
int phblob_link_line_segments( phblob_args *args,
                               phblob_data *data )
{
    phFUNCTION("phblob_link_line_segments")

    /* Used in line segment linking; ie forming the pointer links to
     * facilitate blob group identification */
    phblob_line_segment *seg_row0 = NULL;
    phblob_line_segment *seg_row1 = NULL;
    uint32_t ax0    = 0;
    uint32_t bx0    = 0;
    uint32_t ax1    = 0;
    uint32_t bx1    = 0;
    uint32_t new0   = 0;
    uint32_t new1   = 0;
    uint32_t connect= 0;

    int32_t value           = 0;
    int32_t value_low       = 0;
    int32_t value_high      = 0;
    uint32_t color_matches   = 1;

    uint32_t i = 0;
    uint32_t j = 0;
    uint32_t k = 0;
    
    int      blob_neighbor;
    uint32_t height;
    uint32_t depth; 
    int32_t  lower_threshold[phCOLOR_MAXELEMS];
    int32_t  upper_threshold[phCOLOR_MAXELEMS];
    int32_t  loop_threshold [phCOLOR_MAXELEMS];
    phblob_line_segment **row_ptr_array = NULL;
        
    if ((args == NULL) || (data == NULL) || (data->rows == NULL))
    {
        return phFAIL;
    }

    height  = args->height;
    depth   = args->depth;

    phMemcpy(lower_threshold,args->lower_threshold,
             phCOLOR_MAXELEMS*sizeof(int32_t));
    phMemcpy(upper_threshold,args->upper_threshold,
             phCOLOR_MAXELEMS*sizeof(int32_t));
    phMemcpy(loop_threshold,args->loop_threshold,
             phCOLOR_MAXELEMS*sizeof(int32_t));

    row_ptr_array   = data->rows;
    blob_neighbor   = data->blob_method == phBLOB_NEIGHBOR ? 1 : 0;
            
    for (i = 1; i < height; i++)
    {
        seg_row0 = row_ptr_array[i - 1];
        seg_row1 = row_ptr_array[i];
        
        if (seg_row0 != NULL)
        {
            ax0 = seg_row0->a.x;
            bx0 = seg_row0->b.x;
        }
        if (seg_row1 != NULL)
        {
            ax1 = seg_row1->a.x;
            bx1 = seg_row1->b.x;
        }
        
        while ((seg_row0 != NULL) && (seg_row1 != NULL))
        {
            if (blob_neighbor)
            {
                color_matches = 0;
                for (j = 0; (j < 2) && (color_matches < depth); j++)
                {
                    /* only loop as high as depth, otherwise there will be
                     * indecies where all the values are 0 and the... */
                    for (k = 0; k < depth; k++ )
                    {
                        /* first compare seg_row1->value to seg_row0 */
                        if (j == 0)
                        {
                            value_low   = seg_row0->value_low[k];
                            value_high  = seg_row0->value_high[k];
                            value       = seg_row1->value[k];
                        }
                        /* then compare seg_row0->value to seg_row1 */
                        else
                        {
                            value_low   = seg_row1->value_low[k];
                            value_high  = seg_row1->value_high[k];
                            value       = seg_row0->value[k];
                        }
                        value_low = value_low - lower_threshold[k];
                        value_high= value_high + upper_threshold[k];

                        /* Make sure the value_low/high variables are within the range */
                        if (loop_threshold[k])
                        {
                            value_high = value_high % 256;
                            if (value_low < 0) value_low = 255 + value_low + 1;
                        }
                        else
                        {
                            if (value_high > 255) value_high = 255;
                            if (value_low  <   0) value_low  =   0;
                        }
                        /* if value_low is less than high, then check if the value is
                         * in between both values */
                        if (value_low <= value_high)
                        {
                            if ((value >= value_low) && (value <= value_high))
                            {
                                color_matches++;
                            }
                        }
                        /* if we're looping the threshold around, then check to see
                         * if the value is greater than low or less than high */
                        else 
                        {
                            if (loop_threshold[k] && 
                                    ((value >= value_low) || (value <= value_high)))
                            {
                                color_matches++;
                            }
                        }
                    }
                    if ((color_matches) && (color_matches < depth))
                    {
                        color_matches = 0;
                    }
                }
            }

            /* beginning of 0 occurs before/at end of 1 */
            /* 
             * 0: a----------b
             * 1:    a--------b 
             *
             * 0:       a----------b
             * 1:    a--------b 
             *
             * 0:             a----------b
             * 1:    a--------b 
             */
            if (ax0 <= bx1)
            {
                /* beginning of 0 occurs after/at beginning of 1 */
                /* 
                 * 0: a----------b
                 * 1: a--------b 
                 *
                 * 0:      a----------b
                 * 1: a--------b 
                 */
                if (ax0 >= ax1)
                {
                    /* Case 3 : 0 partly within 1 */
                    /* connect */
                    if (color_matches) connect = 1;
                    else new0 = 1;
                }
                /* end of 0 occurs before beginning of 1 */
                /* 0: a------b
                 * 1:         a--------b 
                 */
                else if (bx0 < ax1)
                {
                    /* Case 1 : 0 not partly within 1
                     * *          0 is wholey before 1 */
                    /* get next element in row 0 */
                    new0 = 1;
                }
                /* 0 overlaps with 1 */
                /* 
                 * 0: a---------b
                 * 1:         a--------b 
                 */
                else if (bx0 >= ax1)
                {
                    /* Case 2: 0 partly overlaps with 1 on the
                     * *          ending section of 0 */
                    /* connect them */
                    if (color_matches) connect = 1;
                    else new1 = 1;
                }
            }
            /* beginning of 0 occurs after 1 */
            /* 
             * 0:       a-------b
             * 1:  a---b
             */
            else
            {
                /* Case 3: 0 not partly within 1
                 * *         0 occurs wholey after 1 */
                /* get next element in row 1 */
                new1 = 1;
            }
            
            if (connect)
            {
                /* a.) First element found below */
                if (seg_row0->first_down == NULL)
                {
                    /* just set the first_down and last_down pointers */
                    seg_row0->first_down = 
                        (seg_row0->last_down = seg_row1);
                    seg_row0->first_down_index = 
                        (seg_row0->last_down_index = seg_row1->index);
                    
                    FIRST_DOWN_PTR(seg_row0) = 
                        (LAST_DOWN_PTR(seg_row0) = seg_row1);
                    FIRST_DOWN_INDEX(seg_row0) = 
                        (LAST_DOWN_INDEX(seg_row0) = seg_row1->index);
                }
                /* b.) other elements connected below */
                else
                {
                    /* i.) connect the two segments that both
                     * * overlap row0 from row1 together */
                    /* ii.)set the new last_down pointer */
                    /* iii.) Copy the index locations */
                    seg_row1->left = seg_row0->last_down;
                    seg_row1->left_index = seg_row0->last_down->index;
                    
                    seg_row0->last_down_index =
                        (seg_row0->last_down->right_index = seg_row1->index);
                    seg_row0->last_down =
                        (seg_row0->last_down->right = seg_row1);
                    
                    LEFT_PTR(seg_row1) = DOWN_PTR(seg_row0);
                    LEFT_INDEX(seg_row1) = DOWN_PTR(seg_row0)->index;
                    
                    DOWN_INDEX(seg_row0) = 
                        (RIGHT_INDEX(DOWN_PTR(seg_row0)) = seg_row1->index);
                    
                    RIGHT_PTR(DOWN_PTR(seg_row0)) = seg_row1;
                    DOWN_PTR(seg_row0) = seg_row1;
                }
                
                /* c.) First element found above */
                if (seg_row1->first_up == NULL)
                {
                    /* just set the first_up and last_up pointers */
                    seg_row1->first_up = 
                        (seg_row1->last_up = seg_row0);
                    seg_row1->first_up_index = 
                        (seg_row1->last_up_index = seg_row0->index);
                    
                    FIRST_UP_PTR(seg_row1) = 
                        (LAST_UP_PTR(seg_row1) = seg_row0);
                    FIRST_UP_INDEX(seg_row1) = 
                        (LAST_UP_INDEX(seg_row1) = seg_row0->index);
                }
                /* d.) other elements connected above */
                else
                {
                    /* i.) connect the two segments that both overlap
                     * * in the row1 form row0 together */
                    /* ii.) Set the new last_up pointer, 
                     * * can only have one: the right most segment */
                    /* iii.) Adjust the indexes before adjusting
                     * * the pointers */
                    seg_row0->left = seg_row1->last_up;
                    seg_row0->left_index = seg_row1->last_up->index;
                    
                    seg_row1->last_up_index = 
                        (seg_row1->last_up->right_index = seg_row0->index);
                    
                    seg_row1->last_up = 
                        (seg_row1->last_up->right = seg_row0);
                    
                    /* if we're here, UP_PTR should not be NULL */
                    LEFT_PTR(seg_row0) = UP_PTR(seg_row1);
                    LEFT_INDEX(seg_row0) = UP_PTR(seg_row1)->index;
                    
                    UP_INDEX(seg_row1) = 
                        (RIGHT_INDEX(UP_PTR(seg_row1)) = seg_row0->index);
                    RIGHT_PTR(UP_PTR(seg_row1)) = seg_row0;
                    UP_PTR(seg_row1) = seg_row0;
                }
                
                /* decide which "next" segment to get */
                /* Case 2/3a: end of 0 occurs after end of 1 
                 * *      get a new segment from 1 */
                if (bx0 > bx1)      new1 = 1;
                /* Case 2/3b: end of 0 occurs before end of 1 
                 * *      get a new segment from 0*/
                else if (bx0 < bx1) new0 = 1;
                /* Case 2/3c: 0 and 1 end in the same place 
                 * *      get new segments from 0 and 1 */
                else                new0 = new1 = 1;

#if 0
                for (k = 0; k < phCOLOR_MAXELEMS; k++)
                {
                    if (seg_row0->value_low[k] < seg_row1->value_low[k])
                        seg_row1->value_low[k] = seg_row0->value_low[k];
                    else
                        seg_row0->value_low[k] = seg_row1->value_low[k];
                    
                    if (seg_row0->value_high[k] > seg_row1->value_high[k])
                        seg_row1->value_high[k] = seg_row0->value_high[k];
                    else
                        seg_row0->value_high[k] = seg_row1->value_high[k];
                    
#if 1
                    seg_row0->value[k] = (seg_row0->value_high[k] + seg_row0->value_low[k]) / 2;
                    seg_row1->value[k] = (seg_row1->value_high[k] + seg_row1->value_low[k]) / 2;
#endif
                }
#endif           
                connect = 0;
            }
            if (new0)
            {
                seg_row0 = seg_row0->next;
                if (seg_row0 != NULL)
                {
                    ax0 = seg_row0->a.x;
                    bx0 = seg_row0->b.x;
                }
                new0 = 0;
            }
            if (new1)
            {
#if 0
                if (i == (height - 1))
                {
                    phPRINT("before:%p\n",seg_row1);
                }
#endif
                seg_row1 = seg_row1->next;
                if (seg_row1 != NULL)
                {
                    ax1 = seg_row1->a.x;
                    bx1 = seg_row1->b.x;
                }
#if 0
                if (i == (height - 1))
                {
                    phPRINT("after:%p\n",seg_row1);
                }
#endif
                new1 = 0;
            }
        }
    }

    return phSUCCESS;
}
/* ---------------------------------------------------------------------- */
int phblob_draw_blob_rects( uint8_t         *imgptr,
                            uint32_t        width,
                            uint32_t        height,
                            uint32_t        format,
                            const phColor   *color,
                            phblob_data     *data,
                            uint32_t        index,
                            uint32_t        min_size,
                            uint32_t        flag )
{
    phFUNCTION("phblob_draw_blob_rects")
    
    phImageSurface  surface;
    phblob         *current_blob = NULL;
    phColor         outcolor;
    phblob         *blobs       = data->blobs;
    uint32_t        nblobs      = data->nblobs;

    if (color == NULL) flag |= phBLOB_COLOR_BLACK;
    
    if ((flag & phBLOB_COLOR_BLACK) == phBLOB_COLOR_BLACK)
    {
        if ((format == (uint32_t)phImageYUV9) ||
            (format == (uint32_t)phImageNOFORMAT))
        {
            phCHECK_RC(-1,NULL,"Unsupported Image Format");
        }
        outcolor = phColor_new(phImageFormatToColorType(format));
    }
    else
    {
        outcolor = *color;
    }

    surface.p = imgptr;
    surface.w = width;
    surface.h = height;
    surface.f = format;
    surface.d = phImageFormatToDepth(format);
   
    if (((flag & phBLOB_DRAW_ALL) == phBLOB_DRAW_ALL) &&
        (nblobs > 0))
    {
        /* Highlight the first blob */
        current_blob = (&(blobs[0]));
        
        while (current_blob != NULL)
        {
            if (current_blob->mass > min_size)
            {
                ph_draw_hollow_rect(&surface,
                                    outcolor,
                                    0,
                                    current_blob->x1,
                                    current_blob->y1,
                                    current_blob->x2,
                                    current_blob->y2 );
            }
            
            current_blob = phblob_get_next_blob( current_blob, blobs );
        }
    }
    if ((flag & phBLOB_DRAW_INDEX) == phBLOB_DRAW_INDEX)
    {
        if (index < nblobs)
        {
            current_blob = (&(blobs[index]));
            
            ph_draw_hollow_rect(&surface,
                             outcolor,
                             0,
                             current_blob->x1,
                             current_blob->y1,
                             current_blob->x2,
                             current_blob->y2 );
        }
    }
    
    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
int phblob_color_lines(uint8_t         *imgptr,
                       uint32_t         width,
                       uint32_t         height,
                       uint32_t         format,
                       const phColor   *color,
                       phblob_data     *data,
                       uint32_t         blob_min_size,
                       uint32_t         index, /* TODO */
                       uint32_t         flag )
{
    phFUNCTION("phblob_color_lines")
    
    uint32_t        i               = 0;
    uint32_t        j               = 0;
    uint32_t        k               = 0;
    uint32_t        blob_count      = 0;
    int32_t         blob_index      = 0;
    uint32_t        irow            = 0;
    uint8_t         depth           = 1;
    phblob_line_segment   *current_segment = NULL;
    phColor         outcolor;

    uint32_t                nblobs  = data->nblobs;
    phblob                 *blobs   = data->blobs;
    uint32_t                nrows   = data->nrows;
    //phblob_line_segment   **rows    = data->rows;
    int32_t                *rowindex= data->rowindex;
    //uint32_t                nlines  = data->nlines;
    phblob_line_segment    *lines   = data->lines;
    uint8_t                *ptr     = NULL;

    //uint32_t color_line = 0;

    if (color == NULL) flag |= phBLOB_COLOR_BLACK;
    
    /* set black if it's requested */
    if ((flag & phBLOB_COLOR_BLACK) == phBLOB_COLOR_BLACK)
    {
        if ((format == (uint32_t)phImageYUV9) ||
            (format == (uint32_t)phImageNOFORMAT))
        {
            phCHECK_RC(-1,NULL,"Unsupported Image Format");
        }
        outcolor = phColor_new(phImageFormatToColorType(format));
    }
    else
    {
        outcolor = *color;
    }

        
    if ((format == (uint32_t)phImageYUV9) ||
        (format == (uint32_t)phImageNOFORMAT))
    {
        phCHECK_RC(-1,NULL,"Unsupported Image Format");
    }
    /* Set the depth */
    else
    {
        depth = phImageFormatToDepth(format);
    }

    if ((flag & phBLOB_CLEAR_IMG) == phBLOB_CLEAR_IMG)
    {
        phMemset(imgptr,0,width*height*depth);
    }

    if (blob_min_size > 0)
    {
        for (k = 0; (k < nblobs) && (blobs); k++ )
        {
            if (blobs[k].mass > blob_min_size) blob_count++;
        }
    }
    else
    {
        blob_count = nblobs;
    }

    /* don't color anything if no blobs were big enough */
    if (blob_count > 0)
    {
        for (i = 0; i < nrows; i++ )
        {
            irow = i * width;
            
            /* Get the index to the first line segment in the row */
            current_segment = phblob_get_segment( rowindex[i], lines );
            
            while (current_segment != NULL)
            {
#if 0
                phPRINT("segment[%3d]:%3d ( %3d, %3d; %3d, %3d ) [ %3d | %3d | %3d ]\n",
                    current_segment->index, current_segment->length,
                    current_segment->a.x,   current_segment->a.y,
                    current_segment->b.x,   current_segment->b.y,
                    current_segment->value[0],  current_segment->value[1],
                    current_segment->value[2]
                    );
#endif       
                blob_index = current_segment->blob_index;
/* TODO: make coloring all the lines an option */
                if ((blob_index >= 0) && 
                    (((uint32_t)blob_index) < nblobs) &&
                    ((blob_min_size            == 0) ||                      
                     (blobs[blob_index].mass   >= blob_min_size)))
                {
                    if (data->blob_method == phBLOB_NEIGHBOR)
                    {
                        for (j = 0; j < depth; j++)
                            outcolor.array.v[j] = blobs[blob_index].value[j];
                    }
#if 0
                    else
                    {
                        /* WHITE in HSV */
                        /* BLUE in RGB */
                        outcolor.array.v[0] = 0;
                        outcolor.array.v[1] = 0;
                        outcolor.array.v[2] = 127;
                        //outcolor.array.v[2] = 0;
                    }
#endif
                    for (j = 0, 
                         ptr = &(imgptr[(irow + current_segment->a.x) * depth]); 
                             
                         j < current_segment->length; 
                         
                         j++, ptr += depth)
                    {
                        phMemcpy(ptr,outcolor.array.v, depth);
                    }
                }
                
                current_segment = phblob_get_next_segment(current_segment,
                                                          lines);
            }
        }
    }

    return phSUCCESS;
error:
    return phFAIL;
}

                                     
/* ---------------------------------------------------------------------- */
#define phTOTAL_DIRS 4
const uint32_t opposite_dir_bit[phTOTAL_DIRS] = 
                                {(1<<1),(1<<0),(1<<3),(1<<2)};

/* ---------------------------------------------------------------------- */
int phblob_create_blobs(uint32_t        width,
                        uint32_t        height,
                        phblob_data    *data   )
{
    phFUNCTION("phblob_create_blobs")
    
    uint32_t i = 0;

    /* Used in blob identification */
    phblob_line_segment    *current_segment     = NULL;
    int32_t                 blob_index          = 0;
    phblob                 *current_blob        = NULL;
    phblob                 *previous_blob       = NULL;
    uint32_t                visit_done          = 0;
    uint32_t                made_visit          = 0;
    uint32_t                dir                 = 0;
    phblob_line_segment    *visit_segment       = NULL;
    phblob_line_segment    *prospect_segment    = NULL;

    /* make local copies */
    uint32_t            blobs_size  = data->blobs_size;
    phblob             *blobs       = data->blobs;
    //int32_t             nrows       = data->nrows;
    //phblob_line_segment **rows      = data->rows;
    int32_t             *rowindex   = data->rowindex;
    phblob_line_segment *lines      = data->lines;
 
    //uint32_t half_npixels = ((width * height) + ((width * height) % 2)) / 2;
    uint32_t npixels = ((width * height) + ((width * height) % 2));
    
    /* 0.) m_blob_array, this is an array that can hold the maximum number of
     *      blobs possible, ie half the number of pixels in the image.
     *      Each phblob has a mass, upper left and lower right value
     *      associated with it */
    //phDALLOC(blobs, blobs_size, half_npixels, phblob );
    phDALLOC(blobs, blobs_size, npixels, phblob );

    /* begin traverse algorithm */
    for (i = 0; i < height; i++ )
    {
        current_segment = phblob_get_segment( rowindex[i], lines );

        while (current_segment != NULL)
        {
            /* if the current segment doesn't belong to a 
             * blob group yet, start up a new blob 
             * member search */
            if (current_segment->blob_index < 0)
            {
                visit_done = 0;
                visit_segment = current_segment;

                /* Setup a new blob */
                previous_blob = current_blob;
                current_blob = &(blobs[blob_index]);
                /* init the blob */
                current_segment->blob_index = 
                    current_blob->index = blob_index++;
                current_blob->next_index = -1;
                current_blob->previous_index = -1;
                current_blob->first_segment = current_segment;
                current_blob->first_segment_index = 
                                current_segment->index;
                current_blob->last_segment = visit_segment;
                current_blob->last_segment_index = 
                                visit_segment->index;
                current_blob->mass = visit_segment->length;
                current_blob->x1 = visit_segment->a.x;
                current_blob->y1 = visit_segment->a.y;
                current_blob->x2 = visit_segment->b.x;
                current_blob->y2 = visit_segment->b.y;
                current_blob->cx = 
                    (current_blob->x1 + current_blob->x2) / 2;
                current_blob->cy = 
                    (current_blob->y1 + current_blob->y2) / 2;
                current_blob->w = 
                    (current_blob->x2 - current_blob->x1)+1;
                current_blob->h = 
                    (current_blob->y2 - current_blob->y1)+1;

                phMemcpy(current_blob->value,
                         current_segment->value,
                         sizeof(int32_t)*phCOLOR_MAXELEMS);
                phMemcpy(current_blob->value_low,
                         current_segment->value_low,
                         sizeof(int32_t)*phCOLOR_MAXELEMS);
                phMemcpy(current_blob->value_high,
                         current_segment->value_high,
                         sizeof(int32_t)*phCOLOR_MAXELEMS);
               
                if (previous_blob != NULL)
                {
                    previous_blob->next = current_blob;
                    previous_blob->next_index = current_blob->index;

                    current_blob->previous = previous_blob;
                    current_blob->previous_index = previous_blob->index;
                }
                
                while ((!visit_done) && (visit_segment != NULL))
                {
                    /* used in backing up the traversal when no visits 
                     * are made */
                    made_visit = 0;
                    
                    for (dir = 0; 
                         (dir < phTOTAL_DIRS) && (made_visit == 0);
                         dir++ )
                    {
                        /* If dir hasn't been visited yet... */
                        if (!(visit_segment->visited & (1<<dir)))
                        {
                            made_visit = 1;
                            
                            visit_segment->visited |= (1<<dir);
                            prospect_segment = visit_segment->connection[dir];
                            
                            /* If direction isn't NULL... */
                            if (prospect_segment != NULL)
                            {
                                /* If segment in current direction doen't 
                                 * already belong to the group...*/
                                if (prospect_segment->blob_index < 0)
                                {
                                    /* Setup reverse paths */
                                    prospect_segment->previous_visit_index = 
                                        visit_segment->index;
                                    prospect_segment->previous_visit =
                                        visit_segment;
                                    
                                    /* go in direction associated with value 'dir' */
                                    visit_segment = prospect_segment;
                                    visit_segment->blob_index = current_blob->index;
                                    
                                    /* Set the last segment visited */
                                    current_blob->last_segment = visit_segment;
                                    current_blob->last_segment_index = 
                                                        visit_segment->index;
                                    /* Add to the blob mass */
                                    current_blob->mass += visit_segment->length;
                                    /* Adjust the encompassing rect coords */
                                    phSET_MIN(current_blob->x1,visit_segment->a.x);
                                    phSET_MIN(current_blob->y1,visit_segment->a.y);
                                    phSET_MAX(current_blob->x2,visit_segment->b.x);
                                    phSET_MAX(current_blob->y2,visit_segment->b.y);
                                    
                                    /* prevents traversing in the direction 
                                     * of origin. this is a must */
                                    visit_segment->visited |= OPPOSITE_DIR_BIT(dir);
                                }
                            }
                        }
                    }
                    /* Go back */
                    if (made_visit == 0)
                    {
                        if (visit_segment == current_segment)
                        {
                            visit_done = 1;
                        }
                        /* iterative pseudo pop from stack, go back,
                         * play that funky beat */
                        else
                        {
                            /* reset the visited variable, the blob_index
                             * value will prevent a revisit; this removes
                             * the need to retraverse the array to reset
                             * the visited variable; allows the line
                             * segments to be retraversed */
                            visit_segment->visited = 0;
                            visit_segment = visit_segment->previous_visit;
                        }
                    }
                }
                /* The blob is finished being created */
                if (current_blob != NULL)
                {
                    current_blob->cx = 
                        (current_blob->x1 + current_blob->x2) / 2;
                    current_blob->cy = 
                        (current_blob->y1 + current_blob->y2) / 2;
                    current_blob->w = 
                        (current_blob->x2 - current_blob->x1)+1;
                    current_blob->h = 
                        (current_blob->y2 - current_blob->y1)+1;
                }
            }
            
            current_segment = phblob_get_next_segment(current_segment,
                                                      lines);
        }
    }
    data->nblobs    = blob_index;
    data->blobs_size= blobs_size;
    data->blobs     = blobs;

    return phSUCCESS;
error:
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
__inline__ int32_t phblob_compare( const void *_one, const void *_two )
{
    phblob *b_one = (phblob *)_one;
    phblob *b_two = (phblob *)_two;
    const uint32_t m_one = b_one->mass;
    const uint32_t m_two = b_two->mass;

    //phPROGRESS("mass (%p ? %p )\n",b_one,b_two);
    /* Greater than : 1 */
    if (m_one > m_two)
        return 1;
    /* Less than : -1 */
    else if (m_one < m_two)
        return -1;
    
    //phPROGRESS("cx\n");
    /* Compare cx: center of blob mass x-coord */
    if (b_one->cx > b_two->cx)
        return 1;
    else if (b_one->cx < b_two->cx)
        return -1;

    //phPROGRESS("cy\n");
    /* Compare cy: center of blob mass y-coord */
    if (b_one->cy > b_two->cy)
        return 1;
    else if (b_one->cy < b_two->cy)
        return -1;

    //phPROGRESS("x1\n");
    /* Compare x1: top-left x-coord */
    if (b_one->x1 > b_two->x1)
        return 1;
    else if (b_one->x1 < b_two->x1)
        return -1;

    //phPROGRESS("x2\n");
    /* Compare x2: bottom-right x-coord */
    if (b_one->x2 > b_two->x2)
        return 1;
    else if (b_one->x2 < b_two->x2)
        return -1;

    //phPROGRESS("y1\n");
    /* Compare y1: top-left y-coord */
    if (b_one->y1 > b_two->y1)
        return 1;
    else if (b_one->y1 < b_two->y1)
        return -1;

    //phPROGRESS("y2\n");
    /* Compare y2: bottom-right y-coord */
    if (b_one->y2 > b_two->y2)
        return 1;
    else if (b_one->y2 < b_two->y2)
        return -1;
        
    //phPROGRESS("height\n");
    /* Compare h: height of blob */
    if (b_one->h > b_two->h)
        return 1;
    else if (b_one->h < b_two->h)
        return -1;
            
    //phPROGRESS("width\n");
    /* Compare w: width of blob */
    if (b_one->w > b_two->w)
        return 1;
    else if (b_one->w < b_two->w)
        return -1;

    //phPROGRESS("%p == %p\n", b_one, b_two);
    /* Equal : 0 */
    return 0;
}

/* ---------------------------------------------------------------------- */
int phblob_sort_blobs( phblob_data *data  /* returned */,
                       uint32_t    method /* 0: recursive; 1:iterative */ )
{
    phFUNCTION("phblob_sort_blobs")
    int32_t     i           = 0;
    int32_t     j           = 0;
    int32_t     k           = 0;
    int32_t     prev_index  = 0;
    int32_t     next_index  = 0;
    phblob     *next        = NULL;
    phblob     *prev        = NULL;
    phblob      tempblob;
    uint8_t    *tempbuf     = NULL;
    uint32_t    nblobs      = data->nblobs;
    phblob     *blobs       = data->blobs;
    
    if (nblobs == 0) return phSUCCESS;
    
    tempbuf = (uint8_t *)phMalloc(sizeof(phblob));
    phCHECK_PTR(tempbuf,"phMalloc","phMalloc failed to allocate temp buf");
    
    if (method)
    {
        ph_quicksort_iterative( blobs, 
                                0, 
                                nblobs - 1,
                                sizeof(phblob),
                                tempbuf,
                                phblob_compare );
    }
    else
    {
        ph_quicksort_recursive( blobs, 
                                0, 
                                nblobs - 1,
                                sizeof(phblob),
                                tempbuf,
                                phblob_compare );
    }
    /* Reverse the list */
    j = nblobs - 1;
    for (i = 0; (i < j); i++ )
    {
        tempblob = blobs[i];
        blobs[i] = blobs[j];
        blobs[j] = tempblob;
        j--;
    }
   
    /* Redo all the indecies and pointers for next/previous */
    for (k = 0; k < nblobs; k++ )
    {
        prev_index = ((k - 1) < 0) ? -1 : k - 1;
        next_index = ((k + 1) == nblobs) ? -1 : k + 1;
        next = (next_index < 0) ? NULL :
                    &(blobs[next_index]);
        prev = (prev_index < 0) ? NULL :
                    &(blobs[prev_index]);
        
        blobs[k].index         = k;
        blobs[k].next          = next;
        blobs[k].next_index    = next_index;
        blobs[k].previous      = prev;
        blobs[k].previous_index= prev_index;
    }

    phFree(tempbuf);
    return phSUCCESS;
error:
    phFree(tempbuf);
    return phFAIL;
}

/* ---------------------------------------------------------------------- */
#ifdef __cplusplus
} /* extern "C" */
#endif

Copyright (C) 2002 - 2007

Philip D.S. Thoren ( pthoren@users.sourceforge.net ) University Of Massachusetts at Lowell Robotics Lab

---