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