4b80c7a6096003c98fc817cf81493c5889db4214
[vlc.git] / 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 }