Use filter helpers.
[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     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 }