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     {
 108         msg_Err( p_filter, "out of memory" );
 109         return VLC_ENOMEM;
 110     }
 111
 112     p_filter->p_sys->p_oldpix = NULL;
 113     p_filter->p_sys->p_buf = NULL;
 114
 115     vlc_mutex_init( &p_filter->p_sys->lock );
 116
 117     return VLC_SUCCESS;
 118 }
 119
 120 /*****************************************************************************
 121  * Destroy
 122  *****************************************************************************/
 123 static void Destroy( vlc_object_t *p_this )
 124 {
 125     filter_t *p_filter = (filter_t *)p_this;
 126
 127     free( p_filter->p_sys->p_oldpix );
 128     free( p_filter->p_sys->p_buf );
 129
 130     vlc_mutex_destroy( &p_filter->p_sys->lock );
 131
 132     free( p_filter->p_sys );
 133 }
 134
 135
 136 /*****************************************************************************
 137  * Filter YUV Planar
 138  *****************************************************************************/
 139 static picture_t *Filter( filter_t *p_filter, picture_t *p_inpic )
 140 {
 141     picture_t *p_outpic;
 142     filter_sys_t *p_sys = p_filter->p_sys;
 143
 144     const uint8_t *p_inpix = p_inpic->p[Y_PLANE].p_pixels;
 145     const int i_src_pitch = p_inpic->p[Y_PLANE].i_pitch;
 146     const int i_src_visible = p_inpic->p[Y_PLANE].i_visible_pitch;
 147     const int i_num_lines = p_inpic->p[Y_PLANE].i_visible_lines;
 148
 149     const uint8_t *p_inpix_u = p_inpic->p[U_PLANE].p_pixels;
 150     const uint8_t *p_inpix_v = p_inpic->p[V_PLANE].p_pixels;
 151     const int i_src_pitch_u = p_inpic->p[U_PLANE].i_pitch;
 152     const int i_num_lines_u = p_inpic->p[U_PLANE].i_visible_lines;
 153
 154     uint8_t *p_oldpix;
 155     uint8_t *p_oldpix_u;
 156     uint8_t *p_oldpix_v;
 157     uint8_t *p_outpix;
 158     uint32_t *p_buf;
 159     uint32_t *p_buf2;
 160
 161     int i,j;
 162     int last;
 163
 164     if( !p_inpic ) return NULL;
 165
 166     if( !p_sys->p_oldpix || !p_sys->p_buf )
 167     {
 168         free( p_sys->p_oldpix );
 169         free( p_sys->p_buf );
 170         p_sys->p_oldpix = malloc( i_src_pitch * i_num_lines );
 171         p_sys->p_oldpix_u = malloc( i_src_pitch_u * i_num_lines_u );
 172         p_sys->p_oldpix_v = malloc( i_src_pitch_u * i_num_lines_u );
 173         p_sys->p_buf = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines );
 174         p_sys->p_buf2 = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines);
 175         vlc_memcpy( p_sys->p_oldpix, p_inpix, i_src_pitch * i_num_lines );
 176         vlc_memcpy( p_sys->p_oldpix_u, p_inpix_u, i_src_pitch_u * i_num_lines_u );
 177         vlc_memcpy( p_sys->p_oldpix_v, p_inpix_v, i_src_pitch_u * i_num_lines_u );
 178         return p_inpic;
 179     }
 180     p_oldpix = p_sys->p_oldpix;
 181     p_oldpix_u = p_sys->p_oldpix_u;
 182     p_oldpix_v = p_sys->p_oldpix_v;
 183     p_buf = p_sys->p_buf;
 184     p_buf2 = p_sys->p_buf2;
 185
 186     p_outpic = p_filter->pf_vout_buffer_new( p_filter );
 187     if( !p_outpic )
 188     {
 189         msg_Warn( p_filter, "can't get output picture" );
 190         if( p_inpic->pf_release )
 191             p_inpic->pf_release( p_inpic );
 192         return NULL;
 193     }
 194
 195     p_outpix = p_outpic->p[Y_PLANE].p_pixels;
 196     vlc_memcpy( p_outpic->p[Y_PLANE].p_pixels, p_inpic->p[Y_PLANE].p_pixels,
 197         p_inpic->p[Y_PLANE].i_pitch * p_inpic->p[Y_PLANE].i_visible_lines );
 198     vlc_memcpy( p_outpic->p[U_PLANE].p_pixels, p_inpic->p[U_PLANE].p_pixels,
 199         p_inpic->p[U_PLANE].i_pitch * p_inpic->p[U_PLANE].i_visible_lines );
 200     vlc_memcpy( p_outpic->p[V_PLANE].p_pixels, p_inpic->p[V_PLANE].p_pixels,
 201         p_inpic->p[V_PLANE].i_pitch * p_inpic->p[V_PLANE].i_visible_lines );
 202
 203     vlc_mutex_lock( &p_filter->p_sys->lock );
 204
 205     /**
 206      * Substract Y planes
 207      */
 208     for( i = 0; i < i_src_pitch * i_num_lines; i++ )
 209     {
 210         if( p_inpix[i] > p_oldpix[i] )
 211         {
 212             p_buf2[i] = p_inpix[i] - p_oldpix[i];
 213         }
 214         else
 215         {
 216             p_buf2[i] = p_oldpix[i] - p_inpix[i];
 217         }
 218     }
 219     int line;
 220     int col;
 221     int format;
 222     switch( p_inpic->format.i_chroma )
 223     {
 224         case VLC_FOURCC('I','4','2','0'):
 225         case VLC_FOURCC('I','Y','U','V'):
 226         case VLC_FOURCC('J','4','2','0'):
 227         case VLC_FOURCC('Y','V','1','2'):
 228             format = 1;
 229             break;
 230
 231         case VLC_FOURCC('I','4','2','2'):
 232         case VLC_FOURCC('J','4','2','2'):
 233             format = 2;
 234             break;
 235
 236         default:
 237             format = 0;
 238             msg_Warn( p_filter, "Not taking chroma into account" );
 239             break;
 240     }
 241
 242     if( format )
 243     {
 244         for( line = 0; line < i_num_lines_u; line++ )
 245         {
 246             for( col = 0; col < i_src_pitch_u; col ++ )
 247             {
 248                 int diff;
 249                 i = line * i_src_pitch_u + col;
 250                 if( p_inpix_u[i] > p_oldpix_u[i] )
 251                 {
 252                     diff = p_inpix_u[i] - p_oldpix_u[i];
 253                 }
 254                 else
 255                 {
 256                     diff = p_oldpix_u[i] - p_inpix_u[i];
 257                 }
 258                 if( p_inpix_v[i] > p_oldpix_v[i] )
 259                 {
 260                     diff += p_inpix_v[i] - p_oldpix_v[i];
 261                 }
 262                 else
 263                 {
 264                     diff += p_oldpix_v[i] - p_inpix_v[i];
 265                 }
 266                 switch( format )
 267                 {
 268                     case 1:
 269                         p_buf2[2*line*i_src_pitch+2*col] += diff;
 270                         p_buf2[2*line*i_src_pitch+2*col+1] += diff;
 271                         p_buf2[(2*line+1)*i_src_pitch+2*col] += diff;
 272                         p_buf2[(2*line+1)*i_src_pitch+2*col+1] += diff;
 273                         break;
 274
 275                     case 2:
 276                         p_buf2[line*i_src_pitch+2*col] += diff;
 277                         p_buf2[line*i_src_pitch+2*col+1] += diff;
 278                         break;
 279                 }
 280             }
 281         }
 282     }
 283
 284     /**
 285      * Get the areas where movement was detected
 286      */
 287     int colors[NUM_COLORS];
 288     int color_x_min[NUM_COLORS];
 289     int color_x_max[NUM_COLORS];
 290     int color_y_min[NUM_COLORS];
 291     int color_y_max[NUM_COLORS];
 292
 293     last = FindShapes( p_buf2, p_buf, i_src_pitch, i_src_visible, i_num_lines,
 294                    colors, color_x_min, color_x_max, color_y_min, color_y_max );
 295
 296     /**
 297      * Count final number of shapes
 298      * Draw rectangles (there can be more than 1 moving shape in 1 rectangle)
 299      */
 300     j = 0;
 301     for( i = 1; i < last; i++ )
 302     {
 303         if( colors[i] == i && color_x_min[i] != -1 )
 304         {
 305             if( ( color_y_max[i] - color_y_min[i] ) * ( color_x_max[i] - color_x_min[i] ) < 16 ) continue;
 306             j++;
 307             int x, y;
 308             y = color_y_min[i];
 309             for( x = color_x_min[i]; x <= color_x_max[i]; x++ )
 310             {
 311                 p_outpix[y*i_src_pitch+x] = 0xff;
 312             }
 313             y = color_y_max[i];
 314             for( x = color_x_min[i]; x <= color_x_max[i]; x++ )
 315             {
 316                 p_outpix[y*i_src_pitch+x] = 0xff;
 317             }
 318             x = color_x_min[i];
 319             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 320             {
 321                 p_outpix[y*i_src_pitch+x] = 0xff;
 322             }
 323             x = color_x_max[i];
 324             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 325             {
 326                 p_outpix[y*i_src_pitch+x] = 0xff;
 327             }
 328         }
 329     }
 330     msg_Dbg( p_filter, "Counted %d moving shapes.", j);
 331
 332     /**
 333      * We're done. Lets keep a copy of the picture
 334      */
 335     vlc_memcpy( p_oldpix, p_inpix, i_src_pitch * i_num_lines );
 336     vlc_memcpy( p_oldpix_u, p_inpix_u, i_src_pitch_u * i_num_lines_u );
 337     vlc_memcpy( p_oldpix_v, p_inpix_v, i_src_pitch_u * i_num_lines_u );
 338
 339     vlc_mutex_unlock( &p_filter->p_sys->lock );
 340
 341     return CopyInfoAndRelease( p_outpic, p_inpic );
 342 }
 343
 344 /*****************************************************************************
 345  * Filter YUV Packed
 346  *****************************************************************************/
 347 static picture_t *FilterPacked( filter_t *p_filter, picture_t *p_inpic )
 348 {
 349     picture_t *p_outpic;
 350     filter_sys_t *p_sys = p_filter->p_sys;
 351
 352     int i_y_offset, i_u_offset, i_v_offset;
 353
 354     const uint8_t *p_inpix;
 355     const uint8_t *p_inpix_u;
 356     const uint8_t *p_inpix_v;
 357
 358     int i_src_pitch;
 359     int i_src_visible;
 360     int i_num_lines;
 361
 362     uint8_t *p_oldpix;
 363     uint8_t *p_oldpix_u;
 364     uint8_t *p_oldpix_v;
 365     uint8_t *p_outpix;
 366
 367     uint32_t *p_buf;
 368     uint32_t *p_buf2;
 369
 370     int i,j;
 371     int last;
 372
 373     if( GetPackedYuvOffsets( p_inpic->format.i_chroma, &i_y_offset,
 374                              &i_u_offset, &i_v_offset ) != VLC_SUCCESS )
 375     {
 376         msg_Warn( p_filter, "Unsupported input chroma (%4s)",
 377                   (char*)&(p_inpic->format.i_chroma) );
 378         if( p_inpic->pf_release )
 379             p_inpic->pf_release( p_inpic );
 380         return NULL;
 381     }
 382
 383     p_inpix = p_inpic->p->p_pixels+i_y_offset;
 384     p_inpix_u = p_inpic->p->p_pixels+i_u_offset;
 385     p_inpix_v = p_inpic->p->p_pixels+i_v_offset;
 386
 387     i_src_pitch = p_inpic->p->i_pitch;
 388     i_src_visible = p_inpic->p->i_visible_pitch;
 389     i_num_lines = p_inpic->p->i_visible_lines;
 390
 391     if( !p_sys->p_oldpix || !p_sys->p_buf )
 392     {
 393         free( p_sys->p_oldpix );
 394         free( p_sys->p_buf );
 395         p_sys->p_oldpix = malloc( i_src_pitch * i_num_lines );
 396         p_sys->p_buf = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines / 2 );
 397         p_sys->p_buf2 = malloc( sizeof( uint32_t ) * i_src_pitch * i_num_lines / 2 );
 398         vlc_memcpy( p_sys->p_oldpix, p_inpic->p->p_pixels,
 399                     i_src_pitch * i_num_lines );
 400         return p_inpic;
 401     }
 402
 403     p_outpic = p_filter->pf_vout_buffer_new( p_filter );
 404     if( !p_outpic )
 405     {
 406         msg_Warn( p_filter, "can't get output picture" );
 407         if( p_inpic->pf_release )
 408             p_inpic->pf_release( p_inpic );
 409         return NULL;
 410     }
 411
 412     p_outpix = p_outpic->p->p_pixels+i_y_offset;
 413     vlc_memcpy( p_outpic->p->p_pixels, p_inpic->p->p_pixels,
 414                 p_inpic->p->i_pitch * p_inpic->p->i_visible_lines );
 415
 416     p_oldpix = p_sys->p_oldpix+i_y_offset;
 417     p_oldpix_u = p_sys->p_oldpix+i_u_offset;
 418     p_oldpix_v = p_sys->p_oldpix+i_v_offset;
 419     p_buf = p_sys->p_buf;
 420     p_buf2 = p_sys->p_buf2;
 421
 422     vlc_mutex_lock( &p_filter->p_sys->lock );
 423
 424     /**
 425      * Substract Y planes
 426      */
 427     for( i = 0; i < i_src_pitch * i_num_lines; i+=2 )
 428     {
 429         if( p_inpix[i] > p_oldpix[i] )
 430         {
 431             p_buf2[i>>1] = p_inpix[i] - p_oldpix[i];
 432         }
 433         else
 434         {
 435             p_buf2[i>>1] = p_oldpix[i] - p_inpix[i];
 436         }
 437     }
 438
 439 #if 0
 440     for( i = 0; i < i_src_pitch * i_num_lines; i+=4 )
 441     {
 442         int diff;
 443         if( p_inpix_u[i] > p_oldpix_u[i] )
 444         {
 445             diff = p_inpix_u[i] - p_oldpix_u[i];
 446         }
 447         else
 448         {
 449             diff = p_oldpix_u[i] - p_inpix_u[i];
 450         }
 451         if( p_inpix_v[i] > p_oldpix_v[i] )
 452         {
 453             diff += p_inpix_v[i] - p_oldpix_v[i];
 454         }
 455         else
 456         {
 457             diff += p_oldpix_v[i] - p_inpix_v[i];
 458         }
 459
 460         p_buf2[(i>>2)<<1] += diff;
 461         p_buf2[((i>>2)<<1)+1] += diff;
 462     }
 463 #endif
 464
 465     /**
 466      * Get the areas where movement was detected
 467      */
 468     int colors[5000];
 469     int color_x_min[5000];
 470     int color_x_max[5000];
 471     int color_y_min[5000];
 472     int color_y_max[5000];
 473
 474     last = FindShapes( p_buf2, p_buf, i_src_pitch/2, i_src_visible/2,
 475                        i_num_lines, colors, color_x_min, color_x_max,
 476                        color_y_min, color_y_max );
 477
 478     /**
 479      * Count final number of shapes
 480      * Draw rectangles (there can be more than 1 moving shape in 1 rectangle)
 481      */
 482     j = 0;
 483     for( i = 1; i < last; i++ )
 484     {
 485         if( colors[i] == i && color_x_min[i] != -1 )
 486         {
 487             if( ( color_y_max[i] - color_y_min[i] ) * ( color_x_max[i] - color_x_min[i] ) < 16 ) continue;
 488             j++;
 489             printf("Shape: (%d,%d) (%d,%d)\n", color_y_max[i], color_y_min[i], color_x_max[i], color_x_min[i] );
 490             int x, y;
 491             y = color_y_min[i];
 492             for( x = color_x_min[i]*2; x <= color_x_max[i]*2; x+=2 )
 493             {
 494                 p_outpix[y*i_src_pitch+x] = 0xff;
 495             }
 496             y = color_y_max[i];
 497             for( x = color_x_min[i]*2; x <= color_x_max[i]*2; x+=2 )
 498             {
 499                 p_outpix[y*i_src_pitch+x] = 0xff;
 500             }
 501             x = color_x_min[i]*2;
 502             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 503             {
 504                 p_outpix[y*i_src_pitch+x] = 0xff;
 505             }
 506             x = color_x_max[i]*2;
 507             for( y = color_y_min[i]; y <= color_y_max[i]; y++ )
 508             {
 509                 p_outpix[y*i_src_pitch+x] = 0xff;
 510             }
 511         }
 512     }
 513     msg_Dbg( p_filter, "Counted %d moving shapes.", j);
 514
 515     /**
 516      * We're done. Lets keep a copy of the picture
 517      */
 518     vlc_memcpy( p_sys->p_oldpix, p_inpic->p->p_pixels, i_src_pitch * i_num_lines );
 519
 520     vlc_mutex_unlock( &p_filter->p_sys->lock );
 521
 522     return CopyInfoAndRelease( p_outpic, p_inpic );
 523 }
 524
 525
 526 /*****************************************************************************
 527  * Gaussian Convolution
 528  *****************************************************************************
 529  *    Gaussian convolution ( sigma == 1.4 )
 530  *
 531  *    |  2  4  5  4  2  |   |  2  4  4  4  2 |
 532  *    |  4  9 12  9  4  |   |  4  8 12  8  4 |
 533  *    |  5 12 15 12  5  | ~ |  4 12 16 12  4 |
 534  *    |  4  9 12  9  4  |   |  4  8 12  8  4 |
 535  *    |  2  4  5  4  2  |   |  2  4  4  4  2 |
 536  *****************************************************************************/
 537 static void GaussianConvolution( uint32_t *p_inpix, uint32_t *p_smooth,
 538                                  int i_src_pitch, int i_num_lines,
 539                                  int i_src_visible )
 540 {
 541     int x,y;
 542     for( y = 2; y < i_num_lines - 2; y++ )
 543     {
 544         for( x = 2; x < i_src_visible - 2; x++ )
 545         {
 546             p_smooth[y*i_src_visible+x] = (uint32_t)(
 547               /* 2 rows up */
 548                 ( p_inpix[(y-2)*i_src_pitch+x-2] )
 549               + ((p_inpix[(y-2)*i_src_pitch+x-1]
 550               +   p_inpix[(y-2)*i_src_pitch+x]
 551               +   p_inpix[(y-2)*i_src_pitch+x+1])<<1 )
 552               + ( p_inpix[(y-2)*i_src_pitch+x+2] )
 553               /* 1 row up */
 554               + ((p_inpix[(y-1)*i_src_pitch+x-2]
 555               + ( p_inpix[(y-1)*i_src_pitch+x-1]<<1 )
 556               + ( p_inpix[(y-1)*i_src_pitch+x]*3 )
 557               + ( p_inpix[(y-1)*i_src_pitch+x+1]<<1 )
 558               +   p_inpix[(y-1)*i_src_pitch+x+2]
 559               /* */
 560               +   p_inpix[y*i_src_pitch+x-2]
 561               + ( p_inpix[y*i_src_pitch+x-1]*3 )
 562               + ( p_inpix[y*i_src_pitch+x]<<2 )
 563               + ( p_inpix[y*i_src_pitch+x+1]*3 )
 564               +   p_inpix[y*i_src_pitch+x+2]
 565               /* 1 row down */
 566               +   p_inpix[(y+1)*i_src_pitch+x-2]
 567               + ( p_inpix[(y+1)*i_src_pitch+x-1]<<1 )
 568               + ( p_inpix[(y+1)*i_src_pitch+x]*3 )
 569               + ( p_inpix[(y+1)*i_src_pitch+x+1]<<1 )
 570               +   p_inpix[(y+1)*i_src_pitch+x+2] )<<1 )
 571               /* 2 rows down */
 572               + ( p_inpix[(y+2)*i_src_pitch+x-2] )
 573               + ((p_inpix[(y+2)*i_src_pitch+x-1]
 574               +   p_inpix[(y+2)*i_src_pitch+x]
 575               +   p_inpix[(y+2)*i_src_pitch+x+1])<<1 )
 576               + ( p_inpix[(y+2)*i_src_pitch+x+2] )
 577               ) >> 6 /* 115 */;
 578         }
 579     }
 580 }
 581
 582 /*****************************************************************************
 583  *
 584  *****************************************************************************/
 585 static int FindShapes( uint32_t *p_diff, uint32_t *p_smooth,
 586                        int i_pitch, int i_visible, int i_lines,
 587                        int *colors,
 588                        int *color_x_min, int *color_x_max,
 589                        int *color_y_min, int *color_y_max )
 590 {
 591     int last = 1;
 592     int i, j;
 593
 594     /**
 595      * Apply some smoothing to remove noise
 596      */
 597     GaussianConvolution( p_diff, p_smooth, i_pitch, i_visible, i_lines );
 598
 599     /**
 600      * Label the shapes and build the labels dependencies list
 601      */
 602     for( j = 0; j < i_pitch; j++ )
 603     {
 604         p_smooth[j] = 0;
 605         p_smooth[(i_lines-1)*i_pitch+j] = 0;
 606     }
 607     for( i = 1; i < i_lines-1; i++ )
 608     {
 609         p_smooth[i*i_pitch] = 0;
 610         for( j = 1; j < i_pitch-1; j++ )
 611         {
 612             if( p_smooth[i*i_pitch+j] > 15 )
 613             {
 614                 if( p_smooth[(i-1)*i_pitch+j-1] )
 615                 {
 616                     p_smooth[i*i_pitch+j] = p_smooth[(i-1)*i_pitch+j-1];
 617                 }
 618                 else if( p_smooth[(i-1)*i_pitch+j] )
 619                     p_smooth[i*i_pitch+j] = p_smooth[(i-1)*i_pitch+j];
 620                 else if( p_smooth[i*i_pitch+j-1] )
 621                     p_smooth[i*i_pitch+j] = p_smooth[i*i_pitch+j-1];
 622                 else
 623                 {
 624                     if( last < 5000 )
 625                     {
 626                         p_smooth[i*i_pitch+j] = last;
 627                         colors[last] = last;
 628                         last++;
 629                     }
 630                 }
 631                 #define CHECK( A ) \
 632                 if( p_smooth[A] && p_smooth[A] != p_smooth[i*i_pitch+j] ) \
 633                 { \
 634                     if( p_smooth[A] < p_smooth[i*i_pitch+j] ) \
 635                         colors[p_smooth[i*i_pitch+j]] = p_smooth[A]; \
 636                     else \
 637                         colors[p_smooth[A]] = p_smooth[i*i_pitch+j]; \
 638                 }
 639                 CHECK( i*i_pitch+j-1 );
 640                 CHECK( (i-1)*i_pitch+j-1 );
 641                 CHECK( (i-1)*i_pitch+j );
 642                 CHECK( (i-1)*i_pitch+j+1 );
 643                 #undef CHECK
 644             }
 645             else
 646             {
 647                 p_smooth[i*i_pitch+j] = 0;
 648             }
 649         }
 650         p_smooth[i*i_pitch+j] = 0;
 651     }
 652
 653     /**
 654      * Initialise empty rectangle list
 655      */
 656     for( i = 1; i < last; i++ )
 657     {
 658         color_x_min[i] = -1;
 659         color_x_max[i] = -1;
 660         color_y_min[i] = -1;
 661         color_y_max[i] = -1;
 662     }
 663
 664     /**
 665      * Compute rectangle coordinates
 666      */
 667     for( i = 0; i < i_pitch * i_lines; i++ )
 668     {
 669         if( p_smooth[i] )
 670         {
 671             while( colors[p_smooth[i]] != (int)p_smooth[i] )
 672                 p_smooth[i] = colors[p_smooth[i]];
 673             if( color_x_min[p_smooth[i]] == -1 )
 674             {
 675                 color_x_min[p_smooth[i]] =
 676                 color_x_max[p_smooth[i]] = i % i_pitch;
 677                 color_y_min[p_smooth[i]] =
 678                 color_y_max[p_smooth[i]] = i / i_pitch;
 679             }
 680             else
 681             {
 682                 int x = i % i_pitch, y = i / i_pitch;
 683                 if( x < color_x_min[p_smooth[i]] )
 684                     color_x_min[p_smooth[i]] = x;
 685                 if( x > color_x_max[p_smooth[i]] )
 686                     color_x_max[p_smooth[i]] = x;
 687                 if( y < color_y_min[p_smooth[i]] )
 688                     color_y_min[p_smooth[i]] = y;
 689                 if( y > color_y_max[p_smooth[i]] )
 690                     color_y_max[p_smooth[i]] = y;
 691             }
 692         }
 693     }
 694
 695     /**
 696      * Merge overlaping rectangles
 697      */
 698     for( i = 1; i < last; i++ )
 699     {
 700         if( colors[i] != i ) continue;
 701         if( color_x_min[i] == -1 ) continue;
 702         for( j = i+1; j < last; j++ )
 703         {
 704             if( colors[j] != j ) continue;
 705             if( color_x_min[j] == -1 ) continue;
 706             if( __MAX( color_x_min[i], color_x_min[j] ) < __MIN( color_x_max[i], color_x_max[j] ) &&
 707                 __MAX( color_y_min[i], color_y_min[j] ) < __MIN( color_y_max[i], color_y_max[j] ) )
 708             {
 709                 color_x_min[i] = __MIN( color_x_min[i], color_x_min[j] );
 710                 color_x_max[i] = __MAX( color_x_max[i], color_x_max[j] );
 711                 color_y_min[i] = __MIN( color_y_min[i], color_y_min[j] );
 712                 color_y_max[i] = __MAX( color_y_max[i], color_y_max[j] );
 713                 color_x_min[j] = -1;
 714                 j = 0;
 715             }
 716         }
 717     }
 718
 719     return last;
 720 }