Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

phautoblob.c

Go to the documentation of this file.
00001 /* ---------------------------------------------------------------------------
00002     Phission :
00003         Realtime Vision Processing System
00004 
00005     Copyright (C) 2003-2006 Philip D.S. Thoren (pthoren@cs.uml.edu)
00006     University of Massachusetts at Lowell,
00007     Laboratory for Artificial Intelligence and Robotics
00008 
00009     This file is part of Phission.
00010 
00011     Phission is free software; you can redistribute it and/or modify
00012     it under the terms of the GNU Lesser General Public License as published by
00013     the Free Software Foundation; either version 2 of the License, or
00014     (at your option) any later version.
00015 
00016     Phission is distributed in the hope that it will be useful,
00017     but WITHOUT ANY WARRANTY; without even the implied warranty of
00018     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019     GNU Lesser General Public License for more details.
00020 
00021     You should have received a copy of the GNU Lesser General Public License
00022     along with Phission; if not, write to the Free Software
00023     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00024 
00025  ---------------------------------------------------------------------------*/
00026 #ifdef HAVE_CONFIG_H
00027     #include <phissionconfig.h>
00028 #endif
00029 
00030 #include <ImageGfx.h>
00031 #include <ImageUtil.h>
00032 #include <phautoblob.h>
00033 #include <phbase.h>
00034 
00035 /* ------------------------------------------------------------------------ */
00036 #define SET_MIN(a,b) if (a > b) a = b;
00037 #define SET_MAX(a,b) if (a < b) a = b;
00038 
00039 
00040 /* ---------------------------------------------------------------------- */
00041 #ifdef __cplusplus
00042 extern "C" {
00043 #endif
00044 
00045 /* ---------------------------------------------------------------------- */
00046 inline auto_line_segment *phautoblob_get_segment( const int32_t index,
00047                              auto_line_segment *const line_array);
00048 
00049 inline auto_line_segment *phautoblob_get_next_segment(const auto_line_segment *const segment,
00050                                  auto_line_segment *const line_array);
00051 
00052 inline phautoblob *phautoblob_get_next_blob(const phautoblob *const blob,
00053                               phautoblob *const blobs);
00054 
00055 inline int32_t ph_quicksort_partition(void         *arr,
00056                                       int32_t       low,
00057                                       int32_t       high,
00058                                       ph_compare_fn compare,
00059                                       ph_swap_fn    swap );
00060                                             
00061 inline void ph_quicksort(void          *arr, 
00062                          int32_t        low, 
00063                          int32_t        high,
00064                          ph_compare_fn  compare,
00065                          ph_swap_fn     swap );
00066                                 
00067 inline int32_t phautoblob_compare   ( void *arr, int32_t i, int32_t j );
00068 
00069 inline int32_t phautoblob_swap      ( void *arr, int32_t i, int32_t j );
00070 
00071 /* ---------------------------------------------------------------------- */
00072 inline auto_line_segment *phautoblob_get_segment( const int32_t index,
00073                              auto_line_segment *const line_array)
00074 {
00075     /* Get the line segment by indexing into the pool */
00076     if (index >= 0) 
00077         return &(line_array[index]);
00078     else 
00079         return NULL;
00080 }
00081 /* ---------------------------------------------------------------------- */
00082 inline auto_line_segment *phautoblob_get_next_segment(const auto_line_segment *const segment,
00083                                  auto_line_segment *const line_array)
00084 {
00085     int32_t next_index = segment->next_index;
00086     /* Get the line segment by indexing into the pool */
00087     if (next_index >= 0) 
00088         return &(line_array[next_index]);
00089     else 
00090         return NULL;
00091 }
00092  
00093 /* ---------------------------------------------------------------------- */
00094 inline phautoblob *phautoblob_get_next_blob(const phautoblob *const blob,
00095                               phautoblob *const blobs)
00096 {
00097     int32_t next_index = blob->next_index;
00098     /* Get the line segment by indexing into the pool */
00099     if (next_index >= 0) 
00100         return &(blobs[next_index]);
00101     else 
00102         return NULL;
00103 }
00104 
00105 /* ---------------------------------------------------------------------- */
00106 int phautoblob_data_new ( phautoblob_data **data )
00107 {
00108     phFUNCTION("phautoblob_data_new")
00109 
00110     if (data == NULL) return phFAIL;
00111 
00112     (*data) = (phautoblob_data *)phCalloc(1,sizeof(phautoblob_data));
00113     phCHECK_PTR(*data,"phCalloc", "phCalloc failed.");
00114     
00115     return phSUCCESS;
00116 error:
00117     return phFAIL;
00118 }
00119 
00120 /* ---------------------------------------------------------------------- */
00121 int phautoblob_data_init( phautoblob_data *data  )
00122 {
00123     phFUNCTION("phautoblob_data_init")
00124 
00125     if (data == NULL) return phFAIL;
00126 
00127     phMemset(data,0,sizeof(phautoblob_data));
00128     
00129     return phSUCCESS;
00130 }
00131 
00132 /* ---------------------------------------------------------------------- */
00133 int phautoblob_data_reset( phautoblob_data *data )
00134 {
00135     if (data == NULL) return phFAIL;
00136 
00137     phFree(data->lines);
00138     phFree(data->rows);
00139     phFree(data->rowindex);
00140     phFree(data->blobs);
00141     phMemset(data,0,sizeof(phautoblob_data));
00142     
00143     return phSUCCESS;
00144 }
00145 
00146 /* ---------------------------------------------------------------------- */
00147 int phautoblob_data_free( phautoblob_data **data )
00148 {
00149     phFUNCTION("phautoblob_data_free")
00150 
00151     if (data == NULL) return phFAIL;
00152 
00153     rc = phautoblob_data_reset( *data );
00154     phCHECK_RC(rc,NULL,"phautoblob_data_reset");
00155     
00156     phFree(*data);
00157     
00158     return phSUCCESS;
00159 error:
00160     return phFAIL;
00161 }
00162 
00163 /* ---------------------------------------------------------------------- */
00164 int phautoblob_data_copy( phautoblob_data *in,
00165                           phautoblob_data *out)
00166 {
00167     phFUNCTION("phAutoBlobData::setData")
00168 
00169     int32_t i = 0;
00170     int32_t index = 0;
00171     
00172     int32_t             total_lines;
00173     auto_line_segment  *line_array;
00174     int32_t             total_rows;
00175     auto_line_segment  **row_ptr_array;
00176     int32_t            *row_index_array;
00177     int32_t             total_blobs;
00178     phautoblob         *blob_array;
00179         
00180     /*----------------------------------------------------------------------*/
00181     /* Copy the line information and relink the pointers too */
00182     /*----------------------------------------------------------------------*/
00183     if (in->nlines > 0)
00184     {
00185         phDALLOC_RESIZE(out->lines,
00186                         out->lines_size,
00187                         in->nlines,
00188                         auto_line_segment );
00189     }
00190     
00191     out->nlines = in->nlines;
00192     
00193     if ((in->lines != NULL) && (in->nlines > 0))
00194     {
00195         phMemcpy(out->lines, in->lines, out->lines_size);
00196         
00197         /* relink the line segment ptrs to the addresses for the 
00198          * new array */
00199         rc = phautoblob_data_relink_line_ptrs( out );
00200         phPRINT_RC(rc,NULL,"relink_line_ptrs");
00201     }
00202     
00203     /*----------------------------------------------------------------------*/
00204     /* Copy the row data */
00205     /*----------------------------------------------------------------------*/
00206     if (in->nrows > 0)
00207     {
00208         phDALLOC_RESIZE(out->rows,     out->rows_size,
00209                         in->nrows,     auto_line_segment *);
00210         phDALLOC_RESIZE(out->rowindex, out->rowindex_size,
00211                         in->nrows,     int32_t);
00212     }
00213     
00214     out->nrows = in->nrows;
00215     
00216     if ((in->rowindex != NULL) && (out->nrows > 0))
00217     {
00218         phMemcpy(out->rowindex, in->rowindex, out->rowindex_size);
00219         
00220         /* Set the pointers to the appropriate ptr into the
00221          * line array */
00222         for (i = 0; i < in->nrows; i++)
00223         {
00224             index = out->rowindex[i];
00225             
00226             /* -1 == invalid */
00227             if (index >= 0) out->rows[i] = &(out->lines[index]);
00228         }
00229     }
00230     
00231     /*----------------------------------------------------------------------*/
00232     /* Copy the blob data */
00233     /*----------------------------------------------------------------------*/
00234     if (in->nblobs > 0)
00235     {
00236         phDALLOC_RESIZE(out->blobs,
00237                         out->blobs_size,
00238                         in->nblobs,
00239                         phautoblob );
00240     }
00241 
00242     out->nblobs = in->nblobs;
00243 
00244     if ((in->blobs != NULL) && (out->nblobs > 0))
00245     {
00246         phMemcpy(out->blobs, in->blobs, out->blobs_size );
00247         
00248         /* relink the ptrs to the line segments */
00249         for (i = 0; i < in->nblobs; i++ )
00250         {
00251             index = out->blobs[i].last_segment_index;
00252             if (index >= 0)
00253                 out->blobs[i].last_segment =
00254                     &(out->lines[index]);
00255             
00256             index = out->blobs[i].first_segment_index;
00257             if (index >= 0)
00258                 out->blobs[i].first_segment =
00259                     &(out->lines[index]);
00260             
00261             index = out->blobs[i].next_index;
00262             if (index >= 0)
00263                 out->blobs[i].next = &(out->blobs[index]);
00264             
00265             index = out->blobs[i].previous_index;
00266             if (index >= 0)
00267                 out->blobs[i].previous = &(out->blobs[index]);
00268         }
00269     }
00270 
00271     return phSUCCESS;
00272 error:
00273     return phFAIL;
00274 }
00275 
00276 /* ---------------------------------------------------------------------- */
00277 int phautoblob_data_relink_line_ptrs( phautoblob_data *data )
00278 {
00279     int32_t             i       = 0;
00280     uint32_t            nlines  = 0;
00281     uint32_t            j       = 0;
00282     int32_t             index   = 0;
00283     auto_line_segment  *lines   = NULL;
00284 
00285     if (data == NULL) return phFAIL;
00286 
00287     lines   = data->lines;
00288     nlines  = data->nlines;
00289     
00290     for (i = 0; i < nlines; i++ )
00291     {
00292         index = lines[i].next_index;
00293         if (index >= 0)
00294             lines[i].next = &(lines[index]);
00295         
00296         index = lines[i].previous_index;
00297         if (index >= 0)
00298             lines[i].previous = &(lines[index]);
00299         
00300         index = lines[i].first_up_index;
00301         if (index >= 0)
00302             lines[i].first_up = &(lines[index]);
00303         
00304         index = lines[i].first_down_index;
00305         if (index >= 0)
00306             lines[i].first_down = &(lines[index]);
00307         
00308         index = lines[i].last_up_index;
00309         if (index >= 0)
00310             lines[i].last_up = &(lines[index]);
00311         
00312         index = lines[i].last_down_index;
00313         if (index >= 0)
00314             lines[i].last_down = &(lines[index]);
00315         
00316         index = lines[i].left_index;
00317         if (index >= 0)
00318             lines[i].left = &(lines[index]);
00319         
00320         index = lines[i].right_index;
00321         if (index >= 0)
00322             lines[i].right = &(lines[index]);
00323 
00324         for (j = 0; j < phSEGMENT_CONNECTION_COUNT; j++)
00325         {
00326             index = lines[i].connection_index[j];
00327             if (index >= 0)
00328                 lines[i].connection[j] = &(lines[index]);
00329         }
00330     }
00331 
00332     return phSUCCESS;
00333 }
00334 
00335 /* ---------------------------------------------------------------------- */
00336 int phautoblob_find_line_segments_color(phautoblob_args *args,
00337                                         phautoblob_data *data )
00338 {
00339     phFUNCTION("phautoblob_find_line_segments_color")
00340 
00341     uint32_t i = 0;
00342     uint32_t j = 0;
00343     
00344     /* make local copies of these */
00345     uint8_t             *imgptr     = *(args->imgptr);
00346     uint32_t            width       = args->width;
00347     uint32_t            height      = args->height;
00348     uint8_t             depth       = args->depth;
00349     /* uint32_t            format      = args->format; */
00350     phColor             *incolors   = *args->incolor;
00351     phColor             *thresholds = *args->threshold;
00352     volatile uint32_t   nColors     = *args->nColors;
00353     phColor             incolor;
00354     phColor             threshold;
00355 
00356     auto_line_segment  *line_array          = (data->lines);
00357     uint32_t            line_array_size     = (data->lines_size);
00358     auto_line_segment **row_ptr_array       = (data->rows);
00359     uint32_t            row_ptr_array_size  = (data->rows_size);
00360     int32_t            *row_index_array     = (data->rowindex);
00361     uint32_t            row_index_array_size= (data->rowindex_size);
00362  
00363 
00364     /* Used for comparison in the search for a color and
00365      * whether it's within the giving threshold. */
00366     int32_t     diff[phCOLOR_MAXBYTES]  = {0}; 
00367     int32_t     diff_temp_1             = 0;
00368     int32_t     diff_temp_2             = 0;
00369     uint32_t    color_matches           = 0;
00370     uint32_t    matched                 = 0;
00371     uint32_t    k                       = 0;
00372     uint32_t    l                       = 0;
00373     /* max elements for a color */
00374     uint32_t max_compare = 1;
00375    
00376     /* Used in line segment discovery */
00377     int32_t             larray_index    = 0;
00378     auto_line_segment  *current_segment = NULL;
00379     auto_line_segment  *last_segment    = NULL;
00380 
00381     uint32_t half_npixels = ((width * height) + ((width * height) % 2)) / 2;
00382 
00383     /* 0.) Make sure we have enough memory and all variables are
00384      * initialized */
00385   
00386     /* A.) allocate the max number of segments possible for the image:
00387      * 
00388      * i.) the maximum number of lines is when every other pixel in a row
00389      * matches and is ((width * height) / 2) line segments,
00390      *  
00391      * ii.) the minimum number of lines when all the pixels match is height,
00392      */
00393     phDALLOC_GROW(line_array,
00394                   line_array_size,
00395                   half_npixels,
00396                   auto_line_segment);
00397     
00398     /* b.) row_ptr_array is used to store line segments within a row of the image */
00399     phDALLOC(row_ptr_array,
00400              row_ptr_array_size,
00401              height,
00402              auto_line_segment *);
00403 
00404     /* c.) row_index_array stores the index into the row_ptr_array array for 
00405      * the user can since a phMemcpy of the row_ptr_array/line_array 
00406      * invalidates the pointer values */
00407     phDALLOC(row_index_array,
00408              row_index_array_size,
00409              height,
00410              int32_t);
00411 
00412     if (incolors != NULL)
00413         max_compare = phColorDepth[incolors[0].type];
00414     
00415     for (i = 0; (i < height) && (max_compare > 0); i++)
00416     {
00417         /* -1 is the value used to denote no index */
00418         row_index_array[i] = -1;
00419         
00420         /* reset and initialize all the line variables */
00421         current_segment = NULL;
00422         last_segment = NULL;
00423         
00424         for (j = 0; j < width; j++)
00425         {
00426             /* just in case there are no colors being checked */
00427             for ( l = 0; (l < nColors) && (matched == 0); l++ )
00428             {
00429                 incolor = incolors[l];
00430                 threshold = thresholds[l];
00431                 
00432                 color_matches = 1;
00433                 for ( k = 0; 
00434                       (k < max_compare) && (color_matches > 0); 
00435                       k++ )
00436                 {
00437                     diff_temp_1 = incolor.array.v[k];
00438                     diff_temp_2 = imgptr[k];
00439                     /* Quicker than calling abs     ( ??? ) */
00440                     diff[k] = ((diff_temp_1 >= diff_temp_2) ?
00441                                (diff_temp_1 - diff_temp_2) : 
00442                                (diff_temp_2 - diff_temp_1));
00443                     if (diff[k] > threshold.array.v[k]) color_matches = 0;
00444                 }
00445                 matched = (color_matches) ? 1 : 0;
00446             }
00447             /* if the pixel color matches, ... */
00448             if (matched > 0)
00449             {
00450                 /* reset matched here, chances are, this happens less */
00451                 matched = 0;
00452                 /* create a new line_segment only if we don't have one */
00453                 if (current_segment == NULL)
00454                 {
00455                     /* there's always enough */
00456                     current_segment = &(line_array[larray_index]);
00457                     current_segment->index = larray_index++;
00458                     /* initialize all the memory to have all bits set */
00459                     current_segment->next_index = -1; /* no next */
00460                     current_segment->blob_index = -1; /* no blob */
00461                     current_segment->previous_index = -1; /* no previous */
00462                     current_segment->previous_visit_index = -1; /* no previous */
00463                     memset(current_segment->connection_index,
00464                            255,
00465                            phSEGMENT_CONNECTION_COUNT * sizeof(uint32_t));
00466                     
00467                     /* set the start point */
00468                     current_segment->a.y = current_segment->b.y = i;
00469                     current_segment->a.x = j;
00470                     
00471                     /* first segment for the row */
00472                     if (last_segment == NULL)
00473                     {
00474                         row_ptr_array[i] = current_segment;
00475                         row_index_array[i] = current_segment->index;
00476                     }
00477                     /* link segment to last segment */
00478                     else
00479                     {
00480                         current_segment->previous = last_segment;
00481                         current_segment->previous_index = last_segment->index;
00482                         
00483                         last_segment->next = current_segment;
00484                         last_segment->next_index = current_segment->index;
00485                     }
00486                 }
00487             }
00488             /* if the pixel doesn't match ... */
00489             /* ... and we've created a segment,
00490              * set the end point,
00491              * set the last segment to this segment,
00492              * reset the current segment to NULL,
00493              * 
00494              * this prepares for a search of another line segment */
00495             else if (current_segment != NULL)
00496             {
00497                 /* set the end point to the last valid pixel match*/
00498                 current_segment->b.x = j-1;
00499                 /* set the length - all lines in this routine
00500                  * will be horizontal, which makes the length calculation
00501                  * very easy:
00502                  *  b.x - a.x ; if a.x & b.x == 0, then length == 1; 
00503                  * this means we need to add 1 to every length */
00504                 current_segment->length = (current_segment->b.x - 
00505                                            current_segment->a.x) + 1;
00506 
00507                 if (current_segment->length > 0)
00508                     last_segment = current_segment;
00509                 else
00510                     larray_index--;
00511                 current_segment = NULL;
00512             }
00513 
00514             imgptr += depth;
00515         }
00516         /* make sure if the segment goes to the edge of 
00517          * the image that it's added */
00518         if (current_segment != NULL)
00519         {
00520             /* set the end point */
00521             /* we only get here when j == width,
00522              * the real endpoint is j - 1 */
00523             current_segment->b.x = j - 1;
00524             /* set the length - all lines in this routine
00525              * will be horizontal, which makes the length calculation
00526              * very easy. 
00527              * Again, if a.x == b.x, the length is 1 so we need to add +1
00528              * to every line segment */
00529             current_segment->length = (current_segment->b.x - 
00530                                        current_segment->a.x) + 1;
00531             
00532             last_segment = current_segment;
00533             current_segment = NULL;
00534         }
00535     }
00536     
00537     data->nlines        = larray_index;
00538     data->lines         = line_array;
00539     data->lines_size    = line_array_size;
00540     data->nrows         = height;
00541     data->rows          = row_ptr_array;
00542     data->rows_size     = row_ptr_array_size;
00543     data->rowindex      = row_index_array;
00544     data->rowindex_size = row_index_array_size;
00545     data->blob_method   = phBLOB_COLOR;
00546     data->nblobs        = 0;
00547 
00548     return phSUCCESS;
00549 error:
00550     return phFAIL;
00551 }
00552 
00553 /* ---------------------------------------------------------------------- */
00554 int phautoblob_find_line_segments_neighbor(phautoblob_args *args,
00555                                            phautoblob_data *data )
00556 {
00557     phFUNCTION("phautoblob_find_line_segments_neighbor")
00558 
00559     uint32_t    i   = 0;
00560     uint32_t    j   = 0;
00561     int         done= 0;
00562     
00563     /* make local copies of these */
00564     uint8_t  *imgptr    = *(args->imgptr);
00565     uint32_t  width     = args->width;
00566     uint32_t  height    = args->height;
00567     uint8_t   depth     = args->depth;
00568     uint32_t  format    = args->format;
00569 
00570     auto_line_segment  *line_array          = (data->lines);
00571     uint32_t            line_array_size     = (data->lines_size);
00572     auto_line_segment **row_ptr_array       = (data->rows);
00573     uint32_t            row_ptr_array_size  = (data->rows_size);
00574     int32_t            *row_index_array     = (data->rowindex);
00575     uint32_t            row_index_array_size= (data->rowindex_size);
00576  
00577 
00578     /* Used for comparison in the search for a color and
00579      * whether it's within the giving threshold. */
00580     uint32_t    matched                 = 0;
00581     uint32_t    k                       = 0;
00582     uint32_t    l                       = 0;
00583 
00584     uint32_t    have_value              = 0;
00585     int32_t     value_high              = 0;
00586     int32_t     value_low               = 0;
00587     int32_t     value                   = 0;
00588     int32_t     *lower_threshold        = (int32_t *)args->lower_threshold;
00589     int32_t     *upper_threshold        = (int32_t *)args->upper_threshold;
00590     int32_t     *loop_threshold         = (int32_t *)args->loop_threshold;
00591     int32_t     current_value[phCOLOR_MAXELEMS];
00592     int32_t     current_value_high[phCOLOR_MAXELEMS];
00593     int32_t     current_value_low[phCOLOR_MAXELEMS];
00594    
00595     /* Used in line segment discovery */
00596     int32_t             larray_index        = 0;
00597     auto_line_segment   *current_segment    = NULL;
00598     int32_t             last_segment_index  = -1;
00599 
00600     uint32_t npixels = ((width * height) + ((width * height) % 2));
00601 
00602     /* 0.) Make sure we have enough memory and all variables are
00603      * initialized */
00604   
00605     /* A.) allocate the max number of segments possible for the image:
00606      * 
00607      * i.) The maximum number of pixels when we're considering every pixel
00608      * is npixels;
00609      * 
00610      *  
00611      * ii.) the minimum number of lines when all the pixels match is height,
00612      */
00613 #if 0
00614     phDALLOC(line_array,
00615              line_array_size,
00616              npixels,
00617              auto_line_segment);
00618 #endif
00619        
00620     /* b.) row_ptr_array is used to store line segments within a row of the image */
00621     phDALLOC(row_ptr_array,
00622              row_ptr_array_size,
00623              height,
00624              auto_line_segment *);
00625 
00626     /* c.) row_index_array stores the index into the row_ptr_array array for 
00627      * the user can since a phMemcpy of the row_ptr_array/line_array 
00628      * invalidates the pointer values */
00629     phDALLOC(row_index_array,
00630              row_index_array_size,
00631              height,
00632              int32_t);
00633 #if 0
00634     phPRINT("lower: %3d %3d %3d %3d\n", lower_threshold[0], lower_threshold[1],
00635                                         lower_threshold[2], lower_threshold[3]);
00636     phPRINT("upper: %3d %3d %3d %3d\n", upper_threshold[0], upper_threshold[1],
00637                                         upper_threshold[2], upper_threshold[3]);
00638     phPRINT("loop : %3d %3d %3d %3d\n", loop_threshold[0], loop_threshold[1],
00639                                         loop_threshold[2], loop_threshold[3]);
00640 #endif
00641 
00642     phMemset(current_value,     0,phCOLOR_MAXELEMS*sizeof(int32_t));
00643     phMemset(current_value_low, 0,phCOLOR_MAXELEMS*sizeof(int32_t));
00644     phMemset(current_value_high,0,phCOLOR_MAXELEMS*sizeof(int32_t));
00645 
00646     for (i = 0; i < height; i++)
00647     {
00648         /* -1 is the value used to denote no index */
00649         row_index_array[i] = -1;
00650         row_ptr_array[i] = NULL;
00651         
00652         /* reset and initialize all the line variables */
00653         current_segment     = NULL;
00654         last_segment_index  = -1;
00655         have_value          = 0;
00656         
00657         j = 0;
00658         while (j < width)
00659         {
00660             if (have_value == 0)
00661             {
00662                 for (k = 0; k < depth; k++ )
00663                 {
00664                     current_value[k] = 
00665                         current_value_high[k] = 
00666                         current_value_low[k] = imgptr[k];
00667                 }
00668                 have_value = 1;
00669                 matched = 1;
00670             }
00671             else 
00672             {
00673                 for (k = 0; k < depth; k++ )
00674                 {
00675                     value       = imgptr[k];
00676                     value_high  = current_value[k] + upper_threshold[k];
00677                     value_low   = current_value[k] - lower_threshold[k];
00678 
00679                     if (loop_threshold[k])
00680                     {
00681                         value_high = value_high % 256;
00682                         if (value_low < 0) value_low = 255 + value_low + 1;
00683                     }
00684                     else
00685                     {
00686                         if (value_high > 255) value_high = 255;
00687                         if (value_low  <   0) value_low  =   0;
00688                     }
00689 
00690                     /* Check to see if the value threshold markers have looped
00691                      * around the highest value mark */
00692                     if (value_low <= value_high) 
00693                     {
00694                         if ((value >= value_low) && (value <= value_high))
00695                         {
00696                             matched++;
00697                         }
00698                     }
00699                     else 
00700                     {
00701                         if (loop_threshold[k] && 
00702                             ((value >= value_low) || (value <= value_high)))
00703                         {
00704                             matched++;
00705                         }
00706                     }
00707                 }
00708                 if (matched != depth) matched = 0;
00709             }
00710             
00711             /* if the pixel color matches, ... */
00712             if (matched > 0)
00713             {
00714                 /* reset matched here, chances are, this happens less */
00715                 matched = 0;
00716                 /* create a new line_segment only if we don't have one */
00717                 if (current_segment == NULL)
00718                 {
00719                     larray_index++;
00720                     phDALLOC_GROW(line_array,
00721                                   line_array_size,
00722                                   larray_index,
00723                                   auto_line_segment);
00724                     /* there's always enough */
00725                     current_segment         = &(line_array[larray_index-1]);
00726                     phMemset(current_segment,0,sizeof(auto_line_segment));
00727                     current_segment->index  = larray_index-1;
00728                     /* initialize all the memory to have all bits set */
00729                     current_segment->next_index             = -1; /* no next */
00730                     current_segment->blob_index             = -1; /* no blob */
00731                     current_segment->previous_index         = -1; /* no previous */
00732                     current_segment->previous_visit_index   = -1; /* no previous */
00733                     phMemset(current_segment->connection_index,
00734                              255,
00735                              phSEGMENT_CONNECTION_COUNT * sizeof(uint32_t));
00736 
00737                     /* Set the color information */
00738                     phMemcpy(current_segment->value,
00739                              current_value,
00740                              depth*sizeof(int32_t));
00741                     phMemcpy(current_segment->value_low,
00742                              current_value_low,
00743                              depth*sizeof(int32_t));
00744                     phMemcpy(current_segment->value_high,
00745                              current_value_high,
00746                              depth*sizeof(int32_t));
00747 #if 0
00748                     phPRINT("current: %3d %3d %3d %3d\n",
00749                             current_value[0],
00750                             current_value[1],
00751                             current_value[2],
00752                             current_value[3] );
00753                     phPRINT("low    : %3d %3d %3d %3d\n",
00754                             current_value_low[0],
00755                             current_value_low[1],
00756                             current_value_low[2],
00757                             current_value_low[3] );
00758                     phPRINT("high   : %3d %3d %3d %3d\n",
00759                             current_value_high[0],
00760                             current_value_high[1],
00761                             current_value_high[2],
00762                             current_value_high[3] );
00763 #endif
00764                     
00765                     /* set the start point */
00766                     current_segment->a.y = current_segment->b.y = i;
00767                     current_segment->a.x = j;
00768                     
00769                     /* first segment for the row */
00770                     if (last_segment_index < 0)
00771                     {
00772                         row_index_array[i] = current_segment->index;
00773                     }
00774                     /* link segment to last segment */
00775                     else
00776                     {
00777                         current_segment->previous_index = last_segment_index;
00778                         line_array[last_segment_index].next_index = 
00779                                                       current_segment->index;
00780                     }
00781                 }
00782                 else
00783                 {
00784                     for (k = 0; k < depth; k++ )
00785                     {
00786                         if (current_value_low[k] > imgptr[k])
00787                             current_value_low[k] = imgptr[k];
00788                         if (current_value_high[k] < imgptr[k])
00789                             current_value_high[k] = imgptr[k];
00790                         /* moving value */
00791 #if 1
00792                         current_value[k] = (current_value_high[k] + 
00793                                             current_value_low[k]) / 2;
00794 #endif
00795                     }
00796                 }
00797 
00798                 /* only increment when we've matched */
00799                 imgptr += depth;
00800 
00801                 /* because we're looking at every pixel as a different 
00802                  * potential start for a line segment, and not just whether
00803                  * it matches, we have to begin a new line segment the next
00804                  * time we loop; So, only increment j if we're matching; The
00805                  * next part of this if block ("else if (current_segment != NULL)"),
00806                  * Will reset the line segment information and the next 
00807                  * iteration of this loop will create a new 'matched' segment; 
00808                  * That leads us back here to incrementing 'j' and eventually
00809                  * getting to the end of the current line in the image */
00810                 j++;
00811             }
00812             /* if the pixel doesn't match ... */
00813             /* ... and we've created a segment,
00814              * set the end point,
00815              * set the last segment to this segment,
00816              * reset the current segment to NULL,
00817              * 
00818              * this prepares for a search of another line segment */
00819             else if (current_segment != NULL)
00820             {
00821                 /* set the end point */
00822                 /* The j here is the pixel that didn't match, so 
00823                  * we have to subtract 1 from j */
00824                 current_segment->b.x = j-1;
00825                 
00826                 /* set the length - all lines in this routine
00827                  * will be horizontal, which makes the length calculation
00828                  * very easy. */
00829                 current_segment->length = (current_segment->b.x - 
00830                                            current_segment->a.x)+1;
00831                 
00832                 if (current_segment->length > 0)
00833                     last_segment_index = current_segment->index;
00834                 else
00835                     larray_index--;
00836                 
00837                 phMemcpy(current_segment->value,
00838                          current_value,
00839                          depth*sizeof(int32_t));
00840                 phMemcpy(current_segment->value_low,
00841                          current_value_low,
00842                          depth*sizeof(int32_t));
00843                 phMemcpy(current_segment->value_high,
00844                          current_value_high,
00845                          depth*sizeof(int32_t));
00846                 
00847                 current_segment = NULL;
00848                 have_value      = 0;
00849             }
00850         }
00851         /* make sure if the segment goes to the edge of 
00852          * the image that it's added */
00853         if (current_segment != NULL)
00854         {
00855             /* set the end point */
00856             /* ... because we only get here when j == width,
00857              * the real end point is j - 1 */
00858             current_segment->b.x = j-1;
00859             /* set the length - all lines in this routine
00860              * will be horizontal, which makes the length calculation
00861              * very easy. */
00862             current_segment->length = (current_segment->b.x - 
00863                                        current_segment->a.x) + 1;
00864             
00865             last_segment_index = current_segment->index;
00866             current_segment = NULL;
00867         }
00868     }
00869 
00870     /* Because we're using phDALLOC_GROW, we need to set the pointers
00871      * after we've created all the line segments */
00872     for (i = 0; i < height; i++ )
00873     {
00874         if (row_index_array[i] >= 0)
00875         {
00876             current_segment = &(line_array[row_index_array[i]]);
00877             if (current_segment->index != row_index_array[i])
00878             {
00879                 phPROGRESS("!!! WARNING !!! %d != %d\n",
00880                             current_segment->index,
00881                             row_index_array[i]);
00882             }
00883             row_ptr_array[i] = current_segment;
00884             done = 0;
00885             
00886             do 
00887             {
00888                 /* Set the previous pointer */
00889                 if (current_segment->previous_index >= 0)
00890                 {
00891                     current_segment->previous = 
00892                         &(line_array[current_segment->previous_index]);
00893                 }
00894                 else
00895                 {
00896                     current_segment->previous = NULL;
00897                 }
00898                 /* set the next pointer */
00899                 if (current_segment->next_index >= 0)
00900                 {
00901                     current_segment = (current_segment->next = 
00902                         &(line_array[current_segment->next_index]));
00903                 }
00904                 else
00905                 {
00906                     current_segment->next = NULL;
00907                     done = 1;
00908                 }
00909             }
00910             while (!done);
00911         }
00912     }
00913      
00914     data->nlines        = larray_index;
00915     data->lines         = line_array;
00916     data->lines_size    = line_array_size;
00917     data->nrows         = height;
00918     data->rows          = row_ptr_array;
00919     data->rows_size     = row_ptr_array_size;
00920     data->rowindex      = row_index_array;
00921     data->rowindex_size = row_index_array_size;
00922     data->blob_method   = phBLOB_NEIGHBOR;
00923     data->nblobs        = 0;
00924 
00925     return phSUCCESS;
00926 error:
00927     return phFAIL;
00928 }
00929 
00930 /* ---------------------------------------------------------------------- */
00931 int phautoblob_link_line_segments( phautoblob_args *args,
00932                                    phautoblob_data *data )
00933 {
00934     phFUNCTION("link_line_segments");
00935 
00936     /* Used in line segment linking; ie forming the pointer links to
00937      * facilitate blob group identification */
00938     auto_line_segment *seg_row0 = NULL;
00939     auto_line_segment *seg_row1 = NULL;
00940     uint32_t ax0    = 0;
00941     uint32_t bx0    = 0;
00942     uint32_t ax1    = 0;
00943     uint32_t bx1    = 0;
00944     uint32_t new0   = 0;
00945     uint32_t new1   = 0;
00946     uint32_t connect= 0;
00947 
00948     int32_t value           = 0;
00949     int32_t value_low       = 0;
00950     int32_t value_high      = 0;
00951     int32_t color_matches   = 0;
00952 
00953     uint32_t i = 0;
00954     uint32_t j = 0;
00955     uint32_t k = 0;
00956     
00957     int      blob_neighbor;
00958     uint32_t height;
00959     uint32_t depth; 
00960     int32_t  lower_threshold[phCOLOR_MAXELEMS];
00961     int32_t  upper_threshold[phCOLOR_MAXELEMS];
00962     int32_t  loop_threshold [phCOLOR_MAXELEMS];
00963     auto_line_segment **row_ptr_array = NULL;
00964         
00965     if ((args == NULL) || (data == NULL) || (data->rows == NULL))
00966     {
00967         return phFAIL;
00968     }
00969 
00970     height  = args->height;
00971     depth   = args->depth;
00972 
00973     phMemcpy(lower_threshold,args->lower_threshold,
00974              phCOLOR_MAXELEMS*sizeof(int32_t));
00975     phMemcpy(upper_threshold,args->upper_threshold,
00976              phCOLOR_MAXELEMS*sizeof(int32_t));
00977     phMemcpy(loop_threshold,args->loop_threshold,
00978              phCOLOR_MAXELEMS*sizeof(int32_t));
00979 
00980     row_ptr_array   = data->rows;
00981     blob_neighbor   = data->blob_method == phBLOB_NEIGHBOR ? 1 : 0;
00982             
00983     for (i = 1; i < height; i++)
00984     {
00985         seg_row0 = row_ptr_array[i - 1];
00986         seg_row1 = row_ptr_array[i];
00987         
00988         if (seg_row0 != NULL)
00989         {
00990             ax0 = seg_row0->a.x;
00991             bx0 = seg_row0->b.x;
00992         }
00993         if (seg_row1 != NULL)
00994         {
00995             ax1 = seg_row1->a.x;
00996             bx1 = seg_row1->b.x;
00997         }
00998         
00999         while ((seg_row0 != NULL) && (seg_row1 != NULL))
01000         {
01001             if (blob_neighbor)
01002             {
01003                 color_matches = 0;
01004                 for (j = 0; (j < 2) && (color_matches < depth); j++)
01005                 {
01006                     /* only loop as high as depth, otherwise there will be
01007                      * indecies where all the values are 0 and the... */
01008                     for (k = 0; k < depth; k++ )
01009                     {
01010                         /* first compare seg_row1->value to seg_row0 */
01011                         if (j == 0)
01012                         {
01013                             value_low   = seg_row0->value_low[k];
01014                             value_high  = seg_row0->value_high[k];
01015                             value       = seg_row1->value[k];
01016                         }
01017                         /* then compare seg_row0->value to seg_row1 */
01018                         else
01019                         {
01020                             value_low   = seg_row1->value_low[k];
01021                             value_high  = seg_row1->value_high[k];
01022                             value       = seg_row0->value[k];
01023                         }
01024                         value_low = value_low - lower_threshold[k];
01025                         value_high= value_high + upper_threshold[k];
01026 
01027                         /* Make sure the value_low/high variables are within the range */
01028                         if (loop_threshold[k])
01029                         {
01030                             value_high = value_high % 256;
01031                             if (value_low < 0) value_low = 255 + value_low + 1;
01032                         }
01033                         else
01034                         {
01035                             if (value_high > 255) value_high = 255;
01036                             if (value_low  <   0) value_low  =   0;
01037                         }
01038                         /* if value_low is less than high, then check if the value is
01039                          * in between both values */
01040                         if (value_low <= value_high)
01041                         {
01042                             if ((value >= value_low) && (value <= value_high))
01043                             {
01044                                 color_matches++;
01045                             }
01046                         }
01047                         /* if we're looping the threshold around, then check to see
01048                          * if the value is greater than low or less than high */
01049                         else 
01050                         {
01051                             if (loop_threshold[k] && 
01052                                     ((value >= value_low) || (value <= value_high)))
01053                             {
01054                                 color_matches++;
01055                             }
01056                         }
01057                     }
01058                     if ((color_matches) && (color_matches < depth))
01059                     {
01060                         color_matches = 0;
01061                     }
01062                 }
01063             }
01064 
01065             /* beginning of 0 occurs before/at end of 1 */
01066             /* 
01067              * 0: a----------b
01068              * 1:    a--------b 
01069              *
01070              * 0:       a----------b
01071              * 1:    a--------b 
01072              *
01073              * 0:             a----------b
01074              * 1:    a--------b 
01075              */
01076             if (ax0 <= bx1)
01077             {
01078                 /* beginning of 0 occurs after/at beginning of 1 */
01079                 /* 
01080                  * 0: a----------b
01081                  * 1: a--------b 
01082                  *
01083                  * 0:      a----------b
01084                  * 1: a--------b 
01085                  */
01086                 if (ax0 >= ax1)
01087                 {
01088                     /* Case 3 : 0 partly within 1 */
01089                     /* connect */
01090                     if (color_matches) connect = 1;
01091                     else new0 = 1;
01092                 }
01093                 /* end of 0 occurs before beginning of 1 */
01094                 /* 0: a------b
01095                  * 1:         a--------b 
01096                  */
01097                 else if (bx0 < ax1)
01098                 {
01099                     /* Case 1 : 0 not partly within 1
01100                      * *          0 is wholey before 1 */
01101                     /* get next element in row 0 */
01102                     new0 = 1;
01103                 }
01104                 /* 0 overlaps with 1 */
01105                 /* 
01106                  * 0: a---------b
01107                  * 1:         a--------b 
01108                  */
01109                 else if (bx0 >= ax1)
01110                 {
01111                     /* Case 2: 0 partly overlaps with 1 on the
01112                      * *          ending section of 0 */
01113                     /* connect them */
01114                     if (color_matches) connect = 1;
01115                     else new1 = 1;
01116                 }
01117             }
01118             /* beginning of 0 occurs after 1 */
01119             /* 
01120              * 0:       a-------b
01121              * 1:  a---b
01122              */
01123             else
01124             {
01125                 /* Case 3: 0 not partly within 1
01126                  * *         0 occurs wholey after 1 */
01127                 /* get next element in row 1 */
01128                 new1 = 1;
01129             }
01130             
01131             if (connect)
01132             {
01133                 /* a.) First element found below */
01134                 if (seg_row0->first_down == NULL)
01135                 {
01136                     /* just set the first_down and last_down pointers */
01137                     seg_row0->first_down = 
01138                         (seg_row0->last_down = seg_row1);
01139                     seg_row0->first_down_index = 
01140                         (seg_row0->last_down_index = seg_row1->index);
01141                     
01142                     FIRST_DOWN_PTR(seg_row0) = 
01143                         (LAST_DOWN_PTR(seg_row0) = seg_row1);
01144                     FIRST_DOWN_INDEX(seg_row0) = 
01145                         (LAST_DOWN_INDEX(seg_row0) = seg_row1->index);
01146                 }
01147                 /* b.) other elements connected below */
01148                 else
01149                 {
01150                     /* i.) connect the two segments that both
01151                      * * overlap row0 from row1 together */
01152                     /* ii.)set the new last_down pointer */
01153                     /* iii.) Copy the index locations */
01154                     seg_row1->left = seg_row0->last_down;
01155                     seg_row1->left_index = seg_row0->last_down->index;
01156                     
01157                     seg_row0->last_down_index =
01158                         (seg_row0->last_down->right_index = seg_row1->index);
01159                     seg_row0->last_down =
01160                         (seg_row0->last_down->right = seg_row1);
01161                     
01162                     LEFT_PTR(seg_row1) = DOWN_PTR(seg_row0);
01163                     LEFT_INDEX(seg_row1) = DOWN_PTR(seg_row0)->index;
01164                     
01165                     DOWN_INDEX(seg_row0) = 
01166                         (RIGHT_INDEX(DOWN_PTR(seg_row0)) = seg_row1->index);
01167                     
01168                     RIGHT_PTR(DOWN_PTR(seg_row0)) = seg_row1;
01169                     DOWN_PTR(seg_row0) = seg_row1;
01170                 }
01171                 
01172                 /* c.) First element found above */
01173                 if (seg_row1->first_up == NULL)
01174                 {
01175                     /* just set the first_up and last_up pointers */
01176                     seg_row1->first_up = 
01177                         (seg_row1->last_up = seg_row0);
01178                     seg_row1->first_up_index = 
01179                         (seg_row1->last_up_index = seg_row0->index);
01180                     
01181                     FIRST_UP_PTR(seg_row1) = 
01182                         (LAST_UP_PTR(seg_row1) = seg_row0);
01183                     FIRST_UP_INDEX(seg_row1) = 
01184                         (LAST_UP_INDEX(seg_row1) = seg_row0->index);
01185                 }
01186                 /* d.) other elements connected above */
01187                 else
01188                 {
01189                     /* i.) connect the two segments that both overlap
01190                      * * in the row1 form row0 together */
01191                     /* ii.) Set the new last_up pointer, 
01192                      * * can only have one: the right most segment */
01193                     /* iii.) Adjust the indexes before adjusting
01194                      * * the pointers */
01195                     seg_row0->left = seg_row1->last_up;
01196                     seg_row0->left_index = seg_row1->last_up->index;
01197                     
01198                     seg_row1->last_up_index = 
01199                         (seg_row1->last_up->right_index = seg_row0->index);
01200                     
01201                     seg_row1->last_up = 
01202                         (seg_row1->last_up->right = seg_row0);
01203                     
01204                     /* if we're here, UP_PTR should not be NULL */
01205                     LEFT_PTR(seg_row0) = UP_PTR(seg_row1);
01206                     LEFT_INDEX(seg_row0) = UP_PTR(seg_row1)->index;
01207                     
01208                     UP_INDEX(seg_row1) = 
01209                         (RIGHT_INDEX(UP_PTR(seg_row1)) = seg_row0->index);
01210                     RIGHT_PTR(UP_PTR(seg_row1)) = seg_row0;
01211                     UP_PTR(seg_row1) = seg_row0;
01212                 }
01213                 
01214                 /* decide which "next" segment to get */
01215                 /* Case 2/3a: end of 0 occurs after end of 1 
01216                  * *      get a new segment from 1 */
01217                 if (bx0 > bx1)      new1 = 1;
01218                 /* Case 2/3b: end of 0 occurs before end of 1 
01219                  * *      get a new segment from 0*/
01220                 else if (bx0 < bx1) new0 = 1;
01221                 /* Case 2/3c: 0 and 1 end in the same place 
01222                  * *      get new segments from 0 and 1 */
01223                 else                new0 = new1 = 1;
01224 
01225 #if 0
01226                 for (k = 0; k < phCOLOR_MAXELEMS; k++)
01227                 {
01228                     if (seg_row0->value_low[k] < seg_row1->value_low[k])
01229                         seg_row1->value_low[k] = seg_row0->value_low[k];
01230                     else
01231                         seg_row0->value_low[k] = seg_row1->value_low[k];
01232                     
01233                     if (seg_row0->value_high[k] > seg_row1->value_high[k])
01234                         seg_row1->value_high[k] = seg_row0->value_high[k];
01235                     else
01236                         seg_row0->value_high[k] = seg_row1->value_high[k];
01237                     
01238 #if 1
01239                     seg_row0->value[k] = (seg_row0->value_high[k] + seg_row0->value_low[k]) / 2;
01240                     seg_row1->value[k] = (seg_row1->value_high[k] + seg_row1->value_low[k]) / 2;
01241 #endif
01242                 }
01243 #endif           
01244                 connect = 0;
01245             }
01246             if (new0)
01247             {
01248                 seg_row0 = seg_row0->next;
01249                 if (seg_row0 != NULL)
01250                 {
01251                     ax0 = seg_row0->a.x;
01252                     bx0 = seg_row0->b.x;
01253                 }
01254                 new0 = 0;
01255             }
01256             if (new1)
01257             {
01258 #if 0
01259                 if (i == (height - 1))
01260                 {
01261                     phPRINT("before:%p\n",seg_row1);
01262                 }
01263 #endif
01264                 seg_row1 = seg_row1->next;
01265                 if (seg_row1 != NULL)
01266                 {
01267                     ax1 = seg_row1->a.x;
01268                     bx1 = seg_row1->b.x;
01269                 }
01270 #if 0
01271                 if (i == (height - 1))
01272                 {
01273                     phPRINT("after:%p\n",seg_row1);
01274                 }
01275 #endif
01276                 new1 = 0;
01277             }
01278         }
01279     }
01280 
01281     return phSUCCESS;
01282 }
01283 /* ---------------------------------------------------------------------- */
01284 int phautoblob_draw_blob_rects( uint8_t         *imgptr,
01285                                 uint32_t        width,
01286                                 uint32_t        height,
01287                                 uint32_t        format,
01288                                 const phColor   *color,
01289                                 phautoblob_data *data,
01290                                 int32_t         index,
01291                                 uint32_t        min_size,
01292                                 uint32_t        flag )
01293 {
01294     phFUNCTION("phautoblob_draw_blob_rects")
01295     
01296     phSurface   surface;
01297     phautoblob *current_blob= NULL;
01298     phColor     outcolor;
01299     phautoblob *blobs       = data->blobs;
01300     uint32_t    nblobs      = data->nblobs;
01301 
01302     if (color == NULL) flag |= phBLOB_COLOR_BLACK;
01303     
01304     if ((flag & phBLOB_COLOR_BLACK) == phBLOB_COLOR_BLACK)
01305     {
01306         if ((format == (uint32_t)phImageYUV9) ||
01307             (format == (uint32_t)phImageNOFORMAT))
01308         {
01309             phCHECK_RC(-1,NULL,"Unsupported Image Format");
01310         }
01311         outcolor = phColor_new(phImageFormatToColorType(format));
01312     }
01313     else
01314     {
01315         outcolor = *color;
01316     }
01317 
01318     surface.pixels  = imgptr;
01319     surface.w       = width;
01320     surface.h       = height;
01321     surface.format  = format;
01322    
01323     if (((flag & phBLOB_DRAW_ALL) == phBLOB_DRAW_ALL) &&
01324         (nblobs > 0))
01325     {
01326         /* Highlight the first blob */
01327         current_blob = (&(blobs[0]));
01328         
01329         while (current_blob != NULL)
01330         {
01331             if (current_blob->mass > min_size)
01332             {
01333                 ph_draw_hollow_rect(&surface,
01334                                     outcolor,
01335                                     current_blob->x1,
01336                                     current_blob->y1,
01337                                     current_blob->x2,
01338                                     current_blob->y2 );
01339             }
01340             
01341             current_blob = phautoblob_get_next_blob( current_blob, blobs );
01342         }
01343     }
01344     if ((flag & phBLOB_DRAW_INDEX) == phBLOB_DRAW_INDEX)
01345     {
01346         if (index < nblobs)
01347         {
01348             current_blob = (&(blobs[index]));
01349             
01350             ph_draw_hollow_rect(&surface,
01351                              outcolor,
01352                              current_blob->x1,
01353                              current_blob->y1,
01354                              current_blob->x2,
01355                              current_blob->y2 );
01356         }
01357     }
01358     
01359     return phSUCCESS;
01360 error:
01361     return phFAIL;
01362 }
01363 
01364 /* ---------------------------------------------------------------------- */
01365 int phautoblob_color_lines(uint8_t             *imgptr,
01366                            uint32_t             width,
01367                            uint32_t             height,
01368                            uint32_t             format,
01369                            const phColor        *color,
01370                            phautoblob_data      *data,
01371                            uint32_t     blob_min_size,
01372                            uint32_t index, /* TODO */
01373                            uint32_t flag )
01374 {
01375     phFUNCTION("phautoblob_color_lines")
01376     
01377     uint32_t        i               = 0;
01378     uint32_t        j               = 0;
01379     uint32_t        k               = 0;
01380     uint32_t        blob_count      = 0;
01381     uint32_t        blob_index      = 0;
01382     uint32_t        irow            = 0;
01383     uint32_t        jpixel          = 0;
01384     uint8_t         depth           = 1;
01385     auto_line_segment   *current_segment = NULL;
01386     phColor         outcolor;
01387 
01388     uint32_t            nblobs      = data->nblobs;
01389     phautoblob          *blobs      = data->blobs;
01390     uint32_t            nrows       = data->nrows;
01391     auto_line_segment   **rows      = data->rows;
01392     int32_t             *rowindex   = data->rowindex;
01393     uint32_t            nlines      = data->nlines;
01394     auto_line_segment   *lines      = data->lines;
01395 
01396     uint32_t color_line = 0;
01397 
01398     if (color == NULL) flag |= phBLOB_COLOR_BLACK;
01399     
01400     /* set black if it's requested */
01401     if ((flag & phBLOB_COLOR_BLACK) == phBLOB_COLOR_BLACK)
01402     {
01403         if ((format == (uint32_t)phImageYUV9) ||
01404             (format == (uint32_t)phImageNOFORMAT))
01405         {
01406             phCHECK_RC(-1,NULL,"Unsupported Image Format");
01407         }
01408         outcolor = phColor_new(phImageFormatToColorType(format));
01409     }
01410     else
01411     {
01412         outcolor = *color;
01413     }
01414 
01415         
01416     if ((format == (uint32_t)phImageYUV9) ||
01417         (format == (uint32_t)phImageNOFORMAT))
01418     {
01419         phCHECK_RC(-1,NULL,"Unsupported Image Format");
01420     }
01421     /* Set the depth */
01422     else
01423     {
01424         depth = phImageFormatToDepth(format);
01425     }
01426 
01427     phMemset(imgptr,0,width*height*depth);
01428 
01429     if (blob_min_size > 0)
01430     {
01431         for (k = 0; (k < nblobs) && (blobs); k++ )
01432         {
01433             if (blobs[k].mass > blob_min_size) blob_count++;
01434         }
01435     }
01436     else
01437     {
01438         blob_count = nblobs;
01439     }
01440 
01441     /* don't color anything if no blobs were big enough */
01442     if (blob_count > 0)
01443     {
01444         for (i = 0; i < nrows; i++ )
01445         {
01446             irow = i * width;
01447             
01448             /* Get the index to the first line segment in the row */
01449             current_segment = phautoblob_get_segment( rowindex[i], lines );
01450 
01451             while (current_segment != NULL)
01452             {
01453 #if 0
01454             phPRINT("segment[%3d]:%3d ( %3d, %3d; %3d, %3d ) [ %3d | %3d | %3d ]\n",
01455                     current_segment->index,
01456                     current_segment->length,
01457                     current_segment->a.x,
01458                     current_segment->a.y,
01459                     current_segment->b.x,
01460                     current_segment->b.y,
01461                     current_segment->value[0],
01462                     current_segment->value[1],
01463                     current_segment->value[2]
01464                     );
01465 #endif       
01466                 blob_index = current_segment->blob_index;
01467 /* TODO: make coloring all the lines an option */
01468                 if ((blob_index >= 0) && 
01469                      ((blob_min_size == 0) ||
01470                      ((blob_index < nblobs) && 
01471                       (blobs[blob_index].mass >= blob_min_size))))
01472                 {
01473                     color_line = 1;
01474                 }
01475 
01476                 if (color_line)
01477                 {
01478                     if ((blob_index >= 0) && (blob_index < nblobs))
01479                     {
01480                         for (j = 0; j < depth; j++)
01481                             outcolor.array.v[j] = blobs[blob_index].value[j];
01482                     }
01483                     else
01484                     {
01485                         /* WHITE in HSV */
01486                         /* BLUE in RGB */
01487                         outcolor.array.v[0] = 0;
01488                         outcolor.array.v[1] = 0;
01489                         outcolor.array.v[2] = 127;
01490                         //outcolor.array.v[2] = 0;
01491                     }
01492                     for (j = 0; j < current_segment->length; j++)
01493                     {
01494                         jpixel = (irow + j + current_segment->a.x) * depth;
01495                         phMemcpy(&(imgptr[jpixel]),outcolor.array.v, depth);
01496                     }
01497                     color_line = 0;
01498                 }
01499                 
01500                 current_segment = phautoblob_get_next_segment(current_segment,
01501                                                               lines);
01502             }
01503         }
01504     }
01505 
01506     return phSUCCESS;
01507 error:
01508     return phFAIL;
01509 }
01510 
01511                                      
01512 /* ---------------------------------------------------------------------- */
01513 #define phTOTAL_DIRS 4
01514 const uint32_t opposite_dir_bit[phTOTAL_DIRS] = 
01515                                 {(1<<1),(1<<0),(1<<3),(1<<2)};
01516 
01517 /* ---------------------------------------------------------------------- */
01518 int phautoblob_create_blobs(uint32_t        width,
01519                             uint32_t        height,
01520                             phautoblob_data *data
01521                             )
01522 {
01523     phFUNCTION("phautoblob_create_blobs")
01524     
01525     uint32_t i = 0;
01526 
01527     /* Used in blob identification */
01528     auto_line_segment  *current_segment     = NULL;
01529     int32_t             blob_index          = 0;
01530     phautoblob         *current_blob        = NULL;
01531     phautoblob         *previous_blob       = NULL;
01532     uint32_t            visit_done          = 0;
01533     uint32_t            made_visit          = 0;
01534     uint32_t            dir                 = 0;
01535     auto_line_segment   *visit_segment       = NULL;
01536     auto_line_segment   *prospect_segment    = NULL;
01537 
01538     /* make local copies */
01539     uint32_t            blobs_size  = data->blobs_size;
01540     phautoblob          *blobs      = data->blobs;
01541     int32_t             nrows       = data->nrows;
01542     auto_line_segment   **rows      = data->rows;
01543     int32_t             *rowindex   = data->rowindex;
01544     auto_line_segment   *lines      = data->lines;
01545  
01546     uint32_t half_npixels = ((width * height) + ((width * height) % 2)) / 2;
01547     uint32_t npixels = ((width * height) + ((width * height) % 2));
01548     
01549     /* 0.) m_blob_array, this is an array that can hold the maximum number of
01550      *      blobs possible, ie half the number of pixels in the image.
01551      *      Each phautoblob has a mass, upper left and lower right value
01552      *      associated with it */
01553     //phDALLOC(blobs, blobs_size, half_npixels, phautoblob );
01554     phDALLOC(blobs, blobs_size, npixels, phautoblob );
01555 
01556     /* begin traverse algorithm */
01557     for (i = 0; i < height; i++ )
01558     {
01559         current_segment = phautoblob_get_segment( rowindex[i], lines );
01560 
01561         while (current_segment != NULL)
01562         {
01563             /* if the current segment doesn't belong to a 
01564              * blob group yet, start up a new blob 
01565              * member search */
01566             if (current_segment->blob_index < 0)
01567             {
01568                 visit_done = 0;
01569                 visit_segment = current_segment;
01570 
01571                 /* Setup a new blob */
01572                 previous_blob = current_blob;
01573                 current_blob = &(blobs[blob_index]);
01574                 /* init the blob */
01575                 current_segment->blob_index = 
01576                     current_blob->index = blob_index++;
01577                 current_blob->next_index = -1;
01578                 current_blob->previous_index = -1;
01579                 current_blob->first_segment = current_segment;
01580                 current_blob->first_segment_index = 
01581                                 current_segment->index;
01582                 current_blob->last_segment = visit_segment;
01583                 current_blob->last_segment_index = 
01584                                 visit_segment->index;
01585                 current_blob->mass = visit_segment->length;
01586                 current_blob->x1 = visit_segment->a.x;
01587                 current_blob->y1 = visit_segment->a.y;
01588                 current_blob->x2 = visit_segment->b.x;
01589                 current_blob->y2 = visit_segment->b.y;
01590                 current_blob->cx = 
01591                     (current_blob->x1 + current_blob->x2) / 2;
01592                 current_blob->cy = 
01593                     (current_blob->y1 + current_blob->y2) / 2;
01594                 current_blob->w = 
01595                     (current_blob->x2 - current_blob->x1)+1;
01596                 current_blob->h = 
01597                     (current_blob->y2 - current_blob->y1)+1;
01598 
01599                 phMemcpy(current_blob->value,
01600                          current_segment->value,
01601                          sizeof(int32_t)*phCOLOR_MAXELEMS);
01602                 phMemcpy(current_blob->value_low,
01603                          current_segment->value_low,
01604                          sizeof(int32_t)*phCOLOR_MAXELEMS);
01605                 phMemcpy(current_blob->value_high,
01606                          current_segment->value_high,
01607                          sizeof(int32_t)*phCOLOR_MAXELEMS);
01608                
01609                 if (previous_blob != NULL)
01610                 {
01611                     previous_blob->next = current_blob;
01612                     previous_blob->next_index = current_blob->index;
01613 
01614                     current_blob->previous = previous_blob;
01615                     current_blob->previous_index = previous_blob->index;
01616                 }
01617                 
01618                 while ((!visit_done) && (visit_segment != NULL))
01619                 {
01620                     /* used in backing up the traversal when no visits 
01621                      * are made */
01622                     made_visit = 0;
01623                     
01624                     for (dir = 0; 
01625                          (dir < phTOTAL_DIRS) && (made_visit == 0);
01626                          dir++ )
01627                     {
01628                         /* If dir hasn't been visited yet... */
01629                         if (!(visit_segment->visited & (1<<dir)))
01630                         {
01631                             made_visit = 1;
01632                             
01633                             visit_segment->visited |= (1<<dir);
01634                             prospect_segment = visit_segment->connection[dir];
01635                             
01636                             /* If direction isn't NULL... */
01637                             if (prospect_segment != NULL)
01638                             {
01639                                 /* If segment in current direction doen't 
01640                                  * already belong to the group...*/
01641                                 if (prospect_segment->blob_index < 0)
01642                                 {
01643                                     /* Setup reverse paths */
01644                                     prospect_segment->previous_visit_index = 
01645                                         visit_segment->index;
01646                                     prospect_segment->previous_visit =
01647                                         visit_segment;
01648                                     
01649                                     /* go in direction associated with value 'dir' */
01650                                     visit_segment = prospect_segment;
01651                                     visit_segment->blob_index = current_blob->index;
01652                                     
01653                                     /* Set the last segment visited */
01654                                     current_blob->last_segment = visit_segment;
01655                                     current_blob->last_segment_index = 
01656                                                         visit_segment->index;
01657                                     /* Add to the blob mass */
01658                                     current_blob->mass += visit_segment->length;
01659                                     /* Adjust the encompassing rect coords */
01660                                     SET_MIN(current_blob->x1,visit_segment->a.x);
01661                                     SET_MIN(current_blob->y1,visit_segment->a.y);
01662                                     SET_MAX(current_blob->x2,visit_segment->b.x);
01663                                     SET_MAX(current_blob->y2,visit_segment->b.y);
01664                                     
01665                                     /* prevents traversing in the direction 
01666                                      * of origin. this is a must */
01667                                     visit_segment->visited |= OPPOSITE_DIR_BIT(dir);
01668                                 }
01669                             }
01670                         }
01671                     }
01672                     /* Go back */
01673                     if (made_visit == 0)
01674                     {
01675                         if (visit_segment == current_segment)
01676                         {
01677                             visit_done = 1;
01678                         }
01679                         /* iterative pseudo pop from stack, go back,
01680                          * play that funky beat */
01681                         else
01682                         {
01683                             /* reset the visited variable, the blob_index
01684                              * value will prevent a revisit; this removes
01685                              * the need to retraverse the array to reset
01686                              * the visited variable; allows the line
01687                              * segments to be retraversed */
01688                             visit_segment->visited = 0;
01689                             visit_segment = visit_segment->previous_visit;
01690                         }
01691                     }
01692                 }
01693                 /* The blob is finished being created */
01694                 if (current_blob != NULL)
01695                 {
01696                     current_blob->cx = 
01697                         (current_blob->x1 + current_blob->x2) / 2;
01698                     current_blob->cy = 
01699                         (current_blob->y1 + current_blob->y2) / 2;
01700                     current_blob->w = 
01701                         (current_blob->x2 - current_blob->x1)+1;
01702                     current_blob->h = 
01703                         (current_blob->y2 - current_blob->y1)+1;
01704                 }
01705             }
01706             
01707             current_segment = phautoblob_get_next_segment(current_segment,
01708                                                           lines);
01709         }
01710     }
01711     data->nblobs    = blob_index;
01712     data->blobs_size= blobs_size;
01713     data->blobs     = blobs;
01714 
01715     return phSUCCESS;
01716 error:
01717     return phFAIL;
01718 }
01719 
01720 /* ---------------------------------------------------------------------- */
01721 inline int32_t ph_quicksort_partition(void *arr,
01722                                       int32_t low,
01723                                       int32_t high,
01724                                       ph_compare_fn compare,
01725                                       ph_swap_fn swap
01726                                       )
01727 {
01728     int32_t i = low - 1;
01729     int32_t j = high + 1;
01730     
01731     while (1)
01732     {
01733         do
01734         {
01735             j--;
01736         } 
01737         while ((compare(arr,j,low) > 0) && (j >= i));
01738         
01739         do
01740         {
01741             i++;
01742         } 
01743         while ((compare(arr,i,low) < 0) && (i <= j));
01744         
01745         if (i < j)
01746         {
01747             swap(arr,i,j);
01748         }
01749         else
01750         {
01751             return j;
01752         }
01753     }
01754 }
01755 
01756 /* ---------------------------------------------------------------------- */
01757 inline void ph_quicksort(void *arr, 
01758                          int32_t low, 
01759                          int32_t high,
01760                          ph_compare_fn compare,
01761                          ph_swap_fn swap )
01762 {
01763     if (low < high)
01764     {
01765         int32_t mid = ph_quicksort_partition(arr,low,high,compare,swap);
01766         ph_quicksort(arr,low,mid,compare,swap);
01767         ph_quicksort(arr,mid+1,high,compare,swap);
01768     }
01769 }
01770                        
01771 /* ---------------------------------------------------------------------- */
01772 inline int32_t phautoblob_compare(void *arr, int32_t i, int32_t j)
01773 {
01774     phautoblob *blobs = (phautoblob *)arr;
01775    
01776     phautoblob *b_one = &(blobs[i]);
01777     phautoblob *b_two = &(blobs[j]);
01778     const uint32_t m_one = b_one->mass;
01779     const uint32_t m_two = b_two->mass;
01780 
01781     /* Greater than : 1 */
01782     if (m_one > m_two)
01783         return 1;
01784     /* Less than : -1 */
01785     else if (m_one < m_two)
01786         return -1;
01787     /* Equal : 0 */
01788     else 
01789         return 0;
01790 }
01791 
01792 /* ---------------------------------------------------------------------- */
01793 inline int32_t phautoblob_swap(void *arr, int32_t i, int32_t j)
01794 {
01795     phautoblob *blobs = (phautoblob *)arr;
01796    
01797     phautoblob *b_one = &(blobs[i]);
01798     phautoblob b_one_copy = *b_one;
01799     
01800     phautoblob *b_two = &(blobs[j]);
01801     phautoblob b_two_copy = *b_two;
01802     
01803     /* Copy the actual data */
01804     *b_two = b_one_copy;
01805     *b_one = b_two_copy;
01806 
01807     return phSUCCESS;
01808 }
01809 
01810 /* ---------------------------------------------------------------------- */
01811 int phautoblob_sort_blobs( phautoblob_data *data/* returned */ )
01812 {
01813     phFUNCTION("phautoblob_sort_blobs")
01814     int32_t     i           = 0;
01815     int32_t     j           = 0;
01816     int32_t     prev_index  = 0;
01817     int32_t     next_index  = 0;
01818     phautoblob *next        = NULL;
01819     phautoblob *prev        = NULL;
01820     phautoblob  tempblob;
01821     uint32_t    nblobs      = data->nblobs;
01822     phautoblob *blobs       = data->blobs;
01823     
01824     if (nblobs == 0) return phSUCCESS;
01825     
01826     ph_quicksort(   blobs, 
01827                     0, 
01828                     nblobs - 1,
01829                     phautoblob_compare,
01830                     phautoblob_swap );
01831 
01832     j = nblobs - 1;
01833     for (i = 0; (i < j); i++ )
01834     {
01835         tempblob = blobs[i];
01836         blobs[i] = blobs[j];
01837         blobs[j] = tempblob;
01838         j--;
01839     }
01840    
01841     /* Redo all the indecies and pointers for next/previous */
01842     for (i = 0; i < nblobs; i++ )
01843     {
01844         prev_index = ((i - 1) < 0) ? -1 : i - 1;
01845         next_index = ((i + 1) == nblobs) ? -1 : i + 1;
01846         next = (next_index < 0) ? NULL :
01847                     &(blobs[next_index]);
01848         prev = (prev_index < 0) ? NULL :
01849                     &(blobs[prev_index]);
01850         
01851         blobs[i].index          = i;
01852         blobs[i].next           = next;
01853         blobs[i].next_index     = next_index;
01854         blobs[i].previous       = prev;
01855         blobs[i].previous_index = prev_index;
01856     }
01857     return phSUCCESS;
01858 /*
01859 error:
01860     return phFAIL;
01861 */
01862 }
01863 
01864 /* ---------------------------------------------------------------------- */
01865 #ifdef __cplusplus
01866 } /* extern "C" */
01867 #endif
01868 




Copyright (C) 2002 - 2007 Philip D.S. Thoren ( pthoren@users.sourceforge.net )
University Of Massachusetts at Lowell
Robotics Lab
SourceForge.net Logo

Generated on Sat Jun 16 02:44:06 2007 for phission by  doxygen 1.4.4