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