git.sesse.net Git - vlc/blob - modules/video_filter/motiondetect.c

   1 /*****************************************************************************
   2  * motiondetec.c : Second version of a motion detection plugin.
   3  *****************************************************************************
   4  * Copyright (C) 2000-2008 the VideoLAN team
   5  * $Id$
   6  *
   7  * Authors: Antoine Cellerier <dionoea -at- videolan -dot- org>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  22  *****************************************************************************/
  23
  24 /*****************************************************************************
  25  * Preamble
  26  *****************************************************************************/
  27
  28 #ifdef HAVE_CONFIG_H
  29 # include "config.h"
  30 #endif
  31
  32 #include <vlc_common.h>
  33 #include <vlc_plugin.h>
  34 #include <vlc_sout.h>
  35 #include <vlc_vout.h>
  36
  37 #include "vlc_filter.h"
  38 #include "filter_picture.h"
  39
  40 /*****************************************************************************
  41  * Local prototypes
  42  *****************************************************************************/
  43 static int  Create    ( vlc_object_t * );
  44 static void Destroy   ( vlc_object_t * );
  45
  46 static picture_t *Filter( filter_t *, picture_t * );
  47 static picture_t *FilterPacked( filter_t *, picture_t * );
  48 static void GaussianConvolution( uint32_t *, uint32_t *, int, int, int );
  49 static int FindShapes( uint32_t *, uint32_t *, int, int, int,
  50                        int *, int *, int *, int *, int *);
  51
  52 #define NUM_COLORS 5000
  53
  54 /*****************************************************************************
  55  * Module descriptor
  56  *****************************************************************************/
  57
  58 #define FILTER_PREFIX "motiondetect-"
  59
  60 vlc_module_begin();
  61     set_description( N_("Motion detect video filter") );
  62     set_shortname( N_( "Motion Detect" ));
  63     set_capability( "video filter2", 0 );
  64     set_category( CAT_VIDEO );
  65     set_subcategory( SUBCAT_VIDEO_VFILTER );
  66
  67     add_shortcut( "motion" );
  68     set_callbacks( Create, Destroy );
  69 vlc_module_end();
  70
  71 struct filter_sys_t
  72 {
  73     uint8_t *p_oldpix;
  74     uint8_t *p_oldpix_u;
  75     uint8_t *p_oldpix_v;
  76     uint32_t *p_buf;
  77     uint32_t *p_buf2;
  78     vlc_mutex_t lock;
  79 };
  80
  81 /*****************************************************************************
  82  * Create
  83  *****************************************************************************/
  84 static int Create( vlc_object_t *p_this )
  85 {
  86     filter_t *p_filter = (filter_t *)p_this;
  87
  88     switch( p_filter->fmt_in.video.i_chroma )
  89     {
  90         CASE_PLANAR_YUV
  91             p_filter->pf_video_filter = Filter;
  92             break;
  93
  94         CASE_PACKED_YUV_422
  95             p_filter->pf_video_filter = FilterPacked;
  96             break;
  97
  98         default:
  99             msg_Err( p_filter, "Unsupported input chroma (%4s)",
 100                      (char*)&(p_filter->fmt_in.video.i_chroma) );
 101             return VLC_EGENERIC;
 102     }
 103
 104     /* Allocate structure */
 105     p_filter->p_sys = malloc( sizeof( filter_sys_t ) );
 106     if( p_filter->p_sys == NULL )
 107         return VLC_ENOMEM;
 108
 109     p_filter->p_sys->p_oldpix = NULL;
 110     p_filter->p_sys->p_buf = NULL;
 111
 112     vlc_mutex_init( &p_filter->p_sys->lock );
 113
 114     return VLC_SUCCESS;
 115 }
 116
 117 /*****************************************************************************
 118  * Destroy
 119  *****************************************************************************/
 120 static void Destroy( vlc_object_t *p_this )
 121 {
 122     filter_t *p_filter = (filter_t *)p_this;
 123
 124     free( p_filter->p_sys->p_oldpix );
 125     free( p_filter->p_sys->p_buf );
 126
 127     vlc_mutex_destroy( &p_filter->p_sys->lock );
 128
 129     free( p_filter->p_sys );
 130 }
 131
 132
 133 /*****************************************************************************
 134  * Filter YUV Planar
 135  *****************************************************************************/
 136 static picture_t *Filter( filter_t *p_filter, picture_t *p_inpic )
 137 {
 138     picture_t *p_outpic;
 139     filter_sys_t *p_sys = p_filter->p_sys;
 140
 141     const uint8_t *p_inpix = p_inpic->p[Y_PLANE].p_pixels;
 142     const int i_src_pitch = p_inpic->p[Y_PLANE].i_pitch;
 143     const int i_src_visible = p_inpic->p[Y_PLANE].i_visible_pitch;
 144     const int i_num_lines = p_inpic->p[Y_PLANE].i_visible_lines;
 145
 146     const uint8_t *p_inpix_u = p_inpic->p[U_PLANE].p_pixels;
 147     const uint8_t *p_inpix_v = p_inpic->p[V_PLANE].p_pixels;
 148     const int i_src_pitch_u = p_inpic->p[U_PLANE].i_pitch;
 149     const int i_num_lines_u = p_inpic->p[U_PLANE].i_visible_lines;
 150
 151     uint8_t *p_oldpix;
 152     uint8_t *p_oldpix_u;
 153     uint8_t *p_oldpix_v;
 154     uint8_t *p_outpix;
 155     uint32_t *p_buf;
 156     uint32_t *p_buf2;
 157
 158     int i,j;
 159     int last;
 160
 161     if( !p_inpic ) return NULL;
 162
 163     if( !p_sys->p_oldpix || !p_sys->p_buf )
 164     {
 165         free( p_sys->p_oldpix );
 166         free( p_sys->p_buf );
 167         p_sys->p_oldpix = malloc( i_src_pitch * i_num_lines );
 168         p_sys->p_oldpix_u = malloc( i_src_pitch_u * i_num_lines_u );
 169         p_sys->p_oldpix_v = malloc( i_src_pitch_u * i_num_lines_u );
 170         p_sys->p_buf = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines );
 171         p_sys->p_buf2 = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines);
 172         vlc_memcpy( p_sys->p_oldpix, p_inpix, i_src_pitch * i_num_lines );
 173         vlc_memcpy( p_sys->p_oldpix_u, p_inpix_u, i_src_pitch_u * i_num_lines_u );
 174         vlc_memcpy( p_sys->p_oldpix_v, p_inpix_v, i_src_pitch_u * i_num_lines_u );
 175         return p_inpic;
 176     }
 177     p_oldpix = p_sys->p_oldpix;
 178     p_oldpix_u = p_sys->p_oldpix_u;
 179     p_oldpix_v = p_sys->p_oldpix_v;
 180     p_buf = p_sys->p_buf;
 181     p_buf2 = p_sys->p_buf2;
 182
 183     p_outpic = p_filter->pf_vout_buffer_new( p_filter );
 184     if( !p_outpic )
 185     {
 186         msg_Warn( p_filter, "can't get output picture" );
 187         picture_Release( p_inpic );
 188         return NULL;
 189     }
 190
 191     p_outpix = p_outpic->p[Y_PLANE].p_pixels;
 192     vlc_memcpy( p_outpic->p[Y_PLANE].p_pixels, p_inpic->p[Y_PLANE].p_pixels,
 193         p_inpic->p[Y_PLANE].i_pitch * p_inpic->p[Y_PLANE].i_visible_lines );
 194     vlc_memcpy( p_outpic->p[U_PLANE].p_pixels, p_inpic->p[U_PLANE].p_pixels,
 195         p_inpic->p[U_PLANE].i_pitch * p_inpic->p[U_PLANE].i_visible_lines );
 196     vlc_memcpy( p_outpic->p[V_PLANE].p_pixels, p_inpic->p[V_PLANE].p_pixels,
 197         p_inpic->p[V_PLANE].i_pitch * p_inpic->p[V_PLANE].i_visible_lines );
 198
 199     vlc_mutex_lock( &p_filter->p_sys->lock );
 200
 201     /**
 202      * Substract Y planes
 203      */
 204     for( i = 0; i < i_src_pitch * i_num_lines; i++ )
 205     {
 206         if( p_inpix[i] > p_oldpix[i] )
 207         {
 208             p_buf2[i] = p_inpix[i] - p_oldpix[i];
 209         }
 210         else
 211         {
 212             p_buf2[i] = p_oldpix[i] - p_inpix[i];
 213         }
 214     }
 215     int line;
 216     int col;
 217     int format;
 218     switch( p_inpic->format.i_chroma )
 219     {
 220         case VLC_FOURCC('I','4','2','0'):
 221         case VLC_FOURCC('I','Y','U','V'):
 222         case VLC_FOURCC('J','4','2','0'):
 223         case VLC_FOURCC('Y','V','1','2'):
 224             format = 1;
 225             break;
 226
 227         case VLC_FOURCC('I','4','2','2'):
 228         case VLC_FOURCC('J','4','2','2'):
 229             format = 2;
 230             break;
 231
 232         default:
 233             format = 0;
 234             msg_Warn( p_filter, "Not taking chroma into account" );
 235             break;
 236     }
 237
 238     if( format )
 239     {
 240         for( line = 0; line < i_num_lines_u; line++ )
 241         {
 242             for( col = 0; col < i_src_pitch_u; col ++ )
 243             {
 244                 int diff;
 245                 i = line * i_src_pitch_u + col;
 246                 if( p_inpix_u[i] > p_oldpix_u[i] )
 247                 {
 248                     diff = p_inpix_u[i] - p_oldpix_u[i];
 249                 }
 250                 else
 251                 {
 252                     diff = p_oldpix_u[i] - p_inpix_u[i];
 253                 }
 254                 if( p_inpix_v[i] > p_oldpix_v[i] )
 255                 {
 256                     diff += p_inpix_v[i] - p_oldpix_v[i];
 257                 }
 258                 else
 259                 {
 260                     diff += p_oldpix_v[i] - p_inpix_v[i];
 261                 }
 262                 switch( format )
 263                 {
 264                     case 1:
 265                         p_buf2[2*line*i_src_pitch+2*col] += diff;
 266                         p_buf2[2*line*i_src_pitch+2*col+1] += diff;
 267                         p_buf2[(2*line+1)*i_src_pitch+2*col] += diff;
 268                         p_buf2[(2*line+1)*i_src_pitch+2*col+1] += diff;
 269                         break;
 270
 271                     case 2:
 272                         p_buf2[line*i_src_pitch+2*col] += diff;
 273                         p_buf2[line*i_src_pitch+2*col+1] += diff;
 274                         break;
 275                 }
 276             }
 277         }
 278     }
 279
 280     /**
 281      * Get the areas where movement was detected
 282      */
 283     int colors[NUM_COLORS];
 284     int color_x_min[NUM_COLORS];
 285     int color_x_max[NUM_COLORS];
 286     int color_y_min[NUM_COLORS];
 287     int color_y_max[NUM_COLORS];
 288
 289     last = FindShapes( p_buf2, p_buf, i_src_pitch, i_src_visible, i_num_lines,
 290                    colors, color_x_min, color_x_max, color_y_min, color_y_max );
 291
 292     /**
 293      * Count final number of shapes
 294      * Draw rectangles (there can be more than 1 moving shape in 1 rectangle)
 295      */
 296     j = 0;
 297     for( i = 1; i < last; i++ )
 298     {
 299         if( colors[i] == i && color_x_min[i] != -1 )
 300         {
 301             if( ( color_y_max[i] - color_y_min[i] ) * ( color_x_max[i] - color_x_min[i] ) < 16 ) continue;
 302             j++;
 303             int x, y;
 304             y = color_y_min[i];
 305             for( x = color_x_min[i]; x <= color_x_max[i]; x++ )
 306             {
 307                 p_outpix[y*i_src_pitch+x] = 0xff;
 308             }
 309             y = color_y_max[i];
 310             for( x = color_x_min[i]; x <= color_x_max[i]; x++ )
 311             {
 312                 p_outpix[y*i_src_pitch+x] = 0xff;
 313             }
 314             x = color_x_min[i];
 315             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 316             {
 317                 p_outpix[y*i_src_pitch+x] = 0xff;
 318             }
 319             x = color_x_max[i];
 320             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 321             {
 322                 p_outpix[y*i_src_pitch+x] = 0xff;
 323             }
 324         }
 325     }
 326     msg_Dbg( p_filter, "Counted %d moving shapes.", j);
 327
 328     /**
 329      * We're done. Lets keep a copy of the picture
 330      */
 331     vlc_memcpy( p_oldpix, p_inpix, i_src_pitch * i_num_lines );
 332     vlc_memcpy( p_oldpix_u, p_inpix_u, i_src_pitch_u * i_num_lines_u );
 333     vlc_memcpy( p_oldpix_v, p_inpix_v, i_src_pitch_u * i_num_lines_u );
 334
 335     vlc_mutex_unlock( &p_filter->p_sys->lock );
 336
 337     return CopyInfoAndRelease( p_outpic, p_inpic );
 338 }
 339
 340 /*****************************************************************************
 341  * Filter YUV Packed
 342  *****************************************************************************/
 343 static picture_t *FilterPacked( filter_t *p_filter, picture_t *p_inpic )
 344 {
 345     picture_t *p_outpic;
 346     filter_sys_t *p_sys = p_filter->p_sys;
 347
 348     int i_y_offset, i_u_offset, i_v_offset;
 349
 350     const uint8_t *p_inpix;
 351     const uint8_t *p_inpix_u;
 352     const uint8_t *p_inpix_v;
 353
 354     int i_src_pitch;
 355     int i_src_visible;
 356     int i_num_lines;
 357
 358     uint8_t *p_oldpix;
 359     uint8_t *p_oldpix_u;
 360     uint8_t *p_oldpix_v;
 361     uint8_t *p_outpix;
 362
 363     uint32_t *p_buf;
 364     uint32_t *p_buf2;
 365
 366     int i,j;
 367     int last;
 368
 369     if( GetPackedYuvOffsets( p_inpic->format.i_chroma, &i_y_offset,
 370                              &i_u_offset, &i_v_offset ) != VLC_SUCCESS )
 371     {
 372         msg_Warn( p_filter, "Unsupported input chroma (%4s)",
 373                   (char*)&(p_inpic->format.i_chroma) );
 374         picture_Release( p_inpic );
 375         return NULL;
 376     }
 377
 378     p_inpix = p_inpic->p->p_pixels+i_y_offset;
 379     p_inpix_u = p_inpic->p->p_pixels+i_u_offset;
 380     p_inpix_v = p_inpic->p->p_pixels+i_v_offset;
 381
 382     i_src_pitch = p_inpic->p->i_pitch;
 383     i_src_visible = p_inpic->p->i_visible_pitch;
 384     i_num_lines = p_inpic->p->i_visible_lines;
 385
 386     if( !p_sys->p_oldpix || !p_sys->p_buf )
 387     {
 388         free( p_sys->p_oldpix );
 389         free( p_sys->p_buf );
 390         p_sys->p_oldpix = malloc( i_src_pitch * i_num_lines );
 391         p_sys->p_buf = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines / 2 );
 392         p_sys->p_buf2 = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines / 2 );
 393         vlc_memcpy( p_sys->p_oldpix, p_inpic->p->p_pixels,
 394                     i_src_pitch * i_num_lines );
 395         return p_inpic;
 396     }
 397
 398     p_outpic = p_filter->pf_vout_buffer_new( p_filter );
 399     if( !p_outpic )
 400     {
 401         msg_Warn( p_filter, "can't get output picture" );
 402         picture_Release( p_inpic );
 403         return NULL;
 404     }
 405
 406     p_outpix = p_outpic->p->p_pixels+i_y_offset;
 407     vlc_memcpy( p_outpic->p->p_pixels, p_inpic->p->p_pixels,
 408                 p_inpic->p->i_pitch * p_inpic->p->i_visible_lines );
 409
 410     p_oldpix = p_sys->p_oldpix+i_y_offset;
 411     p_oldpix_u = p_sys->p_oldpix+i_u_offset;
 412     p_oldpix_v = p_sys->p_oldpix+i_v_offset;
 413     p_buf = p_sys->p_buf;
 414     p_buf2 = p_sys->p_buf2;
 415
 416     vlc_mutex_lock( &p_filter->p_sys->lock );
 417
 418     /**
 419      * Substract Y planes
 420      */
 421     for( i = 0; i < i_src_pitch * i_num_lines; i+=2 )
 422     {
 423         if( p_inpix[i] > p_oldpix[i] )
 424         {
 425             p_buf2[i>>1] = p_inpix[i] - p_oldpix[i];
 426         }
 427         else
 428         {
 429             p_buf2[i>>1] = p_oldpix[i] - p_inpix[i];
 430         }
 431     }
 432
 433 #if 0
 434     for( i = 0; i < i_src_pitch * i_num_lines; i+=4 )
 435     {
 436         int diff;
 437         if( p_inpix_u[i] > p_oldpix_u[i] )
 438         {
 439             diff = p_inpix_u[i] - p_oldpix_u[i];
 440         }
 441         else
 442         {
 443             diff = p_oldpix_u[i] - p_inpix_u[i];
 444         }
 445         if( p_inpix_v[i] > p_oldpix_v[i] )
 446         {
 447             diff += p_inpix_v[i] - p_oldpix_v[i];
 448         }
 449         else
 450         {
 451             diff += p_oldpix_v[i] - p_inpix_v[i];
 452         }
 453
 454         p_buf2[(i>>2)<<1] += diff;
 455         p_buf2[((i>>2)<<1)+1] += diff;
 456     }
 457 #endif
 458
 459     /**
 460      * Get the areas where movement was detected
 461      */
 462     int colors[5000];
 463     int color_x_min[5000];
 464     int color_x_max[5000];
 465     int color_y_min[5000];
 466     int color_y_max[5000];
 467
 468     last = FindShapes( p_buf2, p_buf, i_src_pitch/2, i_src_visible/2,
 469                        i_num_lines, colors, color_x_min, color_x_max,
 470                        color_y_min, color_y_max );
 471
 472     /**
 473      * Count final number of shapes
 474      * Draw rectangles (there can be more than 1 moving shape in 1 rectangle)
 475      */
 476     j = 0;
 477     for( i = 1; i < last; i++ )
 478     {
 479         if( colors[i] == i && color_x_min[i] != -1 )
 480         {
 481             if( ( color_y_max[i] - color_y_min[i] ) * ( color_x_max[i] - color_x_min[i] ) < 16 ) continue;
 482             j++;
 483             printf("Shape: (%d,%d) (%d,%d)\n", color_y_max[i], color_y_min[i], color_x_max[i], color_x_min[i] );
 484             int x, y;
 485             y = color_y_min[i];
 486             for( x = color_x_min[i]*2; x <= color_x_max[i]*2; x+=2 )
 487             {
 488                 p_outpix[y*i_src_pitch+x] = 0xff;
 489             }
 490             y = color_y_max[i];
 491             for( x = color_x_min[i]*2; x <= color_x_max[i]*2; x+=2 )
 492             {
 493                 p_outpix[y*i_src_pitch+x] = 0xff;
 494             }
 495             x = color_x_min[i]*2;
 496             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 497             {
 498                 p_outpix[y*i_src_pitch+x] = 0xff;
 499             }
 500             x = color_x_max[i]*2;
 501             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 502             {
 503                 p_outpix[y*i_src_pitch+x] = 0xff;
 504             }
 505         }
 506     }
 507     msg_Dbg( p_filter, "Counted %d moving shapes.", j);
 508
 509     /**
 510      * We're done. Lets keep a copy of the picture
 511      */
 512     vlc_memcpy( p_sys->p_oldpix, p_inpic->p->p_pixels, i_src_pitch * i_num_lines );
 513
 514     vlc_mutex_unlock( &p_filter->p_sys->lock );
 515
 516     return CopyInfoAndRelease( p_outpic, p_inpic );
 517 }
 518
 519
 520 /*****************************************************************************
 521  * Gaussian Convolution
 522  *****************************************************************************
 523  *    Gaussian convolution ( sigma == 1.4 )
 524  *
 525  *    |  2  4  5  4  2  |   |  2  4  4  4  2 |
 526  *    |  4  9 12  9  4  |   |  4  8 12  8  4 |
 527  *    |  5 12 15 12  5  | ~ |  4 12 16 12  4 |
 528  *    |  4  9 12  9  4  |   |  4  8 12  8  4 |
 529  *    |  2  4  5  4  2  |   |  2  4  4  4  2 |
 530  *****************************************************************************/
 531 static void GaussianConvolution( uint32_t *p_inpix, uint32_t *p_smooth,
 532                                  int i_src_pitch, int i_num_lines,
 533                                  int i_src_visible )
 534 {
 535     int x,y;
 536     for( y = 2; y < i_num_lines - 2; y++ )
 537     {
 538         for( x = 2; x < i_src_visible - 2; x++ )
 539         {
 540             p_smooth[y*i_src_visible+x] = (uint32_t)(
 541               /* 2 rows up */
 542                 ( p_inpix[(y-2)*i_src_pitch+x-2] )
 543               + ((p_inpix[(y-2)*i_src_pitch+x-1]
 544               +   p_inpix[(y-2)*i_src_pitch+x]
 545               +   p_inpix[(y-2)*i_src_pitch+x+1])<<1 )
 546               + ( p_inpix[(y-2)*i_src_pitch+x+2] )
 547               /* 1 row up */
 548               + ((p_inpix[(y-1)*i_src_pitch+x-2]
 549               + ( p_inpix[(y-1)*i_src_pitch+x-1]<<1 )
 550               + ( p_inpix[(y-1)*i_src_pitch+x]*3 )
 551               + ( p_inpix[(y-1)*i_src_pitch+x+1]<<1 )
 552               +   p_inpix[(y-1)*i_src_pitch+x+2]
 553               /* */
 554               +   p_inpix[y*i_src_pitch+x-2]
 555               + ( p_inpix[y*i_src_pitch+x-1]*3 )
 556               + ( p_inpix[y*i_src_pitch+x]<<2 )
 557               + ( p_inpix[y*i_src_pitch+x+1]*3 )
 558               +   p_inpix[y*i_src_pitch+x+2]
 559               /* 1 row down */
 560               +   p_inpix[(y+1)*i_src_pitch+x-2]
 561               + ( p_inpix[(y+1)*i_src_pitch+x-1]<<1 )
 562               + ( p_inpix[(y+1)*i_src_pitch+x]*3 )
 563               + ( p_inpix[(y+1)*i_src_pitch+x+1]<<1 )
 564               +   p_inpix[(y+1)*i_src_pitch+x+2] )<<1 )
 565               /* 2 rows down */
 566               + ( p_inpix[(y+2)*i_src_pitch+x-2] )
 567               + ((p_inpix[(y+2)*i_src_pitch+x-1]
 568               +   p_inpix[(y+2)*i_src_pitch+x]
 569               +   p_inpix[(y+2)*i_src_pitch+x+1])<<1 )
 570               + ( p_inpix[(y+2)*i_src_pitch+x+2] )
 571               ) >> 6 /* 115 */;
 572         }
 573     }
 574 }
 575
 576 /*****************************************************************************
 577  *
 578  *****************************************************************************/
 579 static int FindShapes( uint32_t *p_diff, uint32_t *p_smooth,
 580                        int i_pitch, int i_visible, int i_lines,
 581                        int *colors,
 582                        int *color_x_min, int *color_x_max,
 583                        int *color_y_min, int *color_y_max )
 584 {
 585     int last = 1;
 586     int i, j;
 587
 588     /**
 589      * Apply some smoothing to remove noise
 590      */
 591     GaussianConvolution( p_diff, p_smooth, i_pitch, i_visible, i_lines );
 592
 593     /**
 594      * Label the shapes and build the labels dependencies list
 595      */
 596     for( j = 0; j < i_pitch; j++ )
 597     {
 598         p_smooth[j] = 0;
 599         p_smooth[(i_lines-1)*i_pitch+j] = 0;
 600     }
 601     for( i = 1; i < i_lines-1; i++ )
 602     {
 603         p_smooth[i*i_pitch] = 0;
 604         for( j = 1; j < i_pitch-1; j++ )
 605         {
 606             if( p_smooth[i*i_pitch+j] > 15 )
 607             {
 608                 if( p_smooth[(i-1)*i_pitch+j-1] )
 609                 {
 610                     p_smooth[i*i_pitch+j] = p_smooth[(i-1)*i_pitch+j-1];
 611                 }
 612                 else if( p_smooth[(i-1)*i_pitch+j] )
 613                     p_smooth[i*i_pitch+j] = p_smooth[(i-1)*i_pitch+j];
 614                 else if( p_smooth[i*i_pitch+j-1] )
 615                     p_smooth[i*i_pitch+j] = p_smooth[i*i_pitch+j-1];
 616                 else
 617                 {
 618                     if( last < 5000 )
 619                     {
 620                         p_smooth[i*i_pitch+j] = last;
 621                         colors[last] = last;
 622                         last++;
 623                     }
 624                 }
 625                 #define CHECK( A ) \
 626                 if( p_smooth[A] && p_smooth[A] != p_smooth[i*i_pitch+j] ) \
 627                 { \
 628                     if( p_smooth[A] < p_smooth[i*i_pitch+j] ) \
 629                         colors[p_smooth[i*i_pitch+j]] = p_smooth[A]; \
 630                     else \
 631                         colors[p_smooth[A]] = p_smooth[i*i_pitch+j]; \
 632                 }
 633                 CHECK( i*i_pitch+j-1 );
 634                 CHECK( (i-1)*i_pitch+j-1 );
 635                 CHECK( (i-1)*i_pitch+j );
 636                 CHECK( (i-1)*i_pitch+j+1 );
 637                 #undef CHECK
 638             }
 639             else
 640             {
 641                 p_smooth[i*i_pitch+j] = 0;
 642             }
 643         }
 644         p_smooth[i*i_pitch+j] = 0;
 645     }
 646
 647     /**
 648      * Initialise empty rectangle list
 649      */
 650     for( i = 1; i < last; i++ )
 651     {
 652         color_x_min[i] = -1;
 653         color_x_max[i] = -1;
 654         color_y_min[i] = -1;
 655         color_y_max[i] = -1;
 656     }
 657
 658     /**
 659      * Compute rectangle coordinates
 660      */
 661     for( i = 0; i < i_pitch * i_lines; i++ )
 662     {
 663         if( p_smooth[i] )
 664         {
 665             while( colors[p_smooth[i]] != (int)p_smooth[i] )
 666                 p_smooth[i] = colors[p_smooth[i]];
 667             if( color_x_min[p_smooth[i]] == -1 )
 668             {
 669                 color_x_min[p_smooth[i]] =
 670                 color_x_max[p_smooth[i]] = i % i_pitch;
 671                 color_y_min[p_smooth[i]] =
 672                 color_y_max[p_smooth[i]] = i / i_pitch;
 673             }
 674             else
 675             {
 676                 int x = i % i_pitch, y = i / i_pitch;
 677                 if( x < color_x_min[p_smooth[i]] )
 678                     color_x_min[p_smooth[i]] = x;
 679                 if( x > color_x_max[p_smooth[i]] )
 680                     color_x_max[p_smooth[i]] = x;
 681                 if( y < color_y_min[p_smooth[i]] )
 682                     color_y_min[p_smooth[i]] = y;
 683                 if( y > color_y_max[p_smooth[i]] )
 684                     color_y_max[p_smooth[i]] = y;
 685             }
 686         }
 687     }
 688
 689     /**
 690      * Merge overlaping rectangles
 691      */
 692     for( i = 1; i < last; i++ )
 693     {
 694         if( colors[i] != i ) continue;
 695         if( color_x_min[i] == -1 ) continue;
 696         for( j = i+1; j < last; j++ )
 697         {
 698             if( colors[j] != j ) continue;
 699             if( color_x_min[j] == -1 ) continue;
 700             if( __MAX( color_x_min[i], color_x_min[j] ) < __MIN( color_x_max[i], color_x_max[j] ) &&
 701                 __MAX( color_y_min[i], color_y_min[j] ) < __MIN( color_y_max[i], color_y_max[j] ) )
 702             {
 703                 color_x_min[i] = __MIN( color_x_min[i], color_x_min[j] );
 704                 color_x_max[i] = __MAX( color_x_max[i], color_x_max[j] );
 705                 color_y_min[i] = __MIN( color_y_min[i], color_y_min[j] );
 706                 color_y_max[i] = __MAX( color_y_max[i], color_y_max[j] );
 707                 color_x_min[j] = -1;
 708                 j = 0;
 709             }
 710         }
 711     }
 712
 713     return last;
 714 }