git.sesse.net Git - mlt/blob - src/modules/rotoscoping/filter_rotoscoping.c

   1 /*
   2  * rotoscoping.c -- keyframable vector based rotoscoping
   3  * Copyright (C) 2011 Till Theato <root@ttill.de>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software Foundation,
  17  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include <framework/mlt_filter.h>
  21 #include <framework/mlt_frame.h>
  22
  23 #include "cJSON.h"
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <math.h>
  28 #include <string.h>
  29
  30 #define MAX( x, y ) x > y ? x : y
  31 #define MIN( x, y ) x < y ? x : y
  32 #define SQR( x ) ( x ) * ( x )
  33
  34 /** x, y tuple with double precision */
  35 typedef struct PointF
  36 {
  37     double x;
  38     double y;
  39 } PointF;
  40
  41 typedef struct BPointF
  42 {
  43     struct PointF h1;
  44     struct PointF p;
  45     struct PointF h2;
  46 } BPointF;
  47
  48 enum MODES { MODE_RGB, MODE_ALPHA, MODE_MATTE };
  49 const char *MODESTR[3] = { "rgb", "alpha", "matte" };
  50
  51 enum ALPHAOPERATIONS { ALPHA_CLEAR, ALPHA_MAX, ALPHA_MIN, ALPHA_ADD, ALPHA_SUB };
  52 const char *ALPHAOPERATIONSTR[5] = { "clear", "max", "min", "add", "sub" };
  53
  54
  55 /** Returns the index of \param string in \param stringList.
  56  * Useful for assigning string parameters to enums. */
  57 int stringValue( const char *string, const char **stringList, int max )
  58 {
  59     int i;
  60     for ( i = 0; i < max; i++ )
  61         if ( strcmp( stringList[i], string ) == 0 )
  62             return i;
  63     return 0;
  64 }
  65
  66 /** Linear interp */
  67 void lerp( const PointF *a, const PointF *b, PointF *result, double t )
  68 {
  69     result->x = a->x + ( b->x - a->x ) * t;
  70     result->y = a->y + ( b->y - a->y ) * t;
  71 }
  72
  73 /** Linear interp. with t = 0.5
  74  * Speed gain? */
  75 void lerpHalf( const PointF *a, const PointF *b, PointF *result )
  76 {
  77     result->x = ( a->x + b->x ) * .5;
  78     result->y = ( a->y + b->y ) * .5;
  79 }
  80
  81 /** Helper for using qsort with an array of integers. */
  82 int ncompare( const void *a, const void *b )
  83 {
  84     return *(const int*)a - *(const int*)b;
  85 }
  86
  87 /** Turns a json array with two children into a point (x, y tuple). */
  88 void jsonGetPoint( cJSON *json, PointF *point )
  89 {
  90     if ( cJSON_GetArraySize( json ) == 2 )
  91     {
  92         point->x = json->child->valuedouble;
  93         point->y = json->child->next->valuedouble;
  94     }
  95 }
  96
  97 /**
  98  * Turns the array of json elements into an array of Bézier points.
  99  * \param array cJSON array. values have to be Bézier points: handle 1, point , handl2
 100  *              ( [ [ [h1x, h1y], [px, py], [h2x, h2y] ], ... ] )
 101  * \param points pointer to array of points. Will be allocated and filled with the points in \param array
 102  * \return number of points
 103  */
 104 int json2BCurves( cJSON *array, BPointF **points )
 105 {
 106     int count = cJSON_GetArraySize( array );
 107     cJSON *child = array->child;
 108     *points = mlt_pool_alloc( count * sizeof( BPointF ) );
 109
 110     int i = 0;
 111     do
 112     {
 113         if ( cJSON_GetArraySize( child ) == 3 )
 114         {
 115             jsonGetPoint( child->child , &(*points)[i].h1 );
 116             jsonGetPoint( child->child->next, &(*points)[i].p );
 117             jsonGetPoint( child->child->next->next, &(*points)[i].h2 );
 118             i++;
 119         }
 120     } while ( ( child = child->next ) );
 121
 122     if ( i < count )
 123         *points = mlt_pool_realloc( *points, i * sizeof( BPointF ) );
 124
 125     return i;
 126 }
 127
 128 /**
 129  * Determines which points are located in the polygon and sets their value in \param map to \param value
 130  * \param vertices points defining the polygon
 131  * \param count number of vertices
 132  * \param with x range
 133  * \param height y range
 134  * \param value value identifying points in the polygon
 135  * \param map array of integers of the dimension width * height.
 136  *            The map entries belonging to the points in the polygon will be set to \param set * 255 the others to !set * 255.
 137  */
 138 void fillMap( PointF *vertices, int count, int width, int height, uint8_t set, uint8_t *map )
 139 {
 140     int nodes, nodeX[1024], pixelY, i, j, offset;
 141
 142     memset( map, !set * 255, width * height );
 143     set *= 255;
 144
 145     // Loop through the rows of the image
 146     for ( pixelY = 0; pixelY < height; pixelY++ )
 147     {
 148         offset = width * pixelY;
 149         /*
 150          * Build a list of nodes.
 151          * nodes are located at the borders of the polygon
 152          * and therefore indicate a move from in to out or vice versa
 153          */
 154         nodes = 0;
 155         for ( i = 0, j = count - 1; i < count; j = i++ )
 156             if ( (vertices[i].y > (double)pixelY) != (vertices[j].y > (double)pixelY) )
 157                 nodeX[nodes++] = (int)(vertices[i].x + (pixelY - vertices[i].y) / (vertices[j].y - vertices[i].y) * (vertices[j].x - vertices[i].x) );
 158
 159         qsort( nodeX, nodes, sizeof( int ), ncompare );
 160
 161         // Set map values for points between the node pairs to 1
 162         for ( i = 0; i < nodes; i += 2 )
 163         {
 164             if ( nodeX[i] >= width )
 165                 break;
 166
 167             if ( nodeX[i+1] > 0 )
 168             {
 169                 nodeX[i] = MAX( 0, nodeX[i] );
 170                 nodeX[i+1] = MIN( nodeX[i+1], width );
 171                 for ( j = nodeX[i]; j <= nodeX[i+1]; j++ )
 172                     map[offset + j] = set;
 173             }
 174         }
 175     }
 176 }
 177
 178 /** Determines the point in the middle of the Bézier curve (t = 0.5) defined by \param p1 and \param p2
 179  * using De Casteljau's algorithm.
 180  */
 181 void deCasteljau( BPointF *p1, BPointF *p2, BPointF *mid )
 182 {
 183     struct PointF ab, bc, cd, abbc, bccd, final;
 184
 185     lerpHalf( &(p1->p), &(p1->h2), &ab );
 186     lerpHalf( &(p1->h2), &(p2->h1), &bc );
 187     lerpHalf( &(p2->h1), &(p2->p), &cd );
 188     lerpHalf( &ab, &bc, &abbc );
 189     lerpHalf( &bc, &cd, &bccd );
 190     lerpHalf( &abbc, &bccd, &final );
 191
 192     p1->h2 = ab;
 193     p2->h1 = cd;
 194     mid->h1 = abbc;
 195     mid->p = final;
 196     mid->h2 = bccd;
 197 }
 198
 199 /**
 200  * Calculates points for the cubic Bézier curve defined by \param p1 and \param p2.
 201  * Points are calculated until the squared distanced between neighbour points is smaller than \param errorSquared.
 202  * \param points Pointer to list of points. Will be allocted and filled with calculated points.
 203  * \param count Number of calculated points in \param points
 204  * \param size Allocated size of \param points (in elements not in bytes)
 205  */
 206 void curvePoints( BPointF p1, BPointF p2, PointF **points, int *count, int *size, const double *errorSquared )
 207 {
 208     double errorSqr = SQR( p1.p.x - p2.p.x ) + SQR( p1.p.y - p2.p.y );
 209
 210     if ( *size + 1 >= *count )
 211     {
 212         *size += (int)sqrt( errorSqr / *errorSquared );
 213         *points = mlt_pool_realloc( *points, *size * sizeof ( struct PointF ) );
 214     }
 215
 216     (*points)[(*count)++] = p1.p;
 217
 218     if ( errorSqr <= *errorSquared )
 219         return;
 220
 221     BPointF mid;
 222     deCasteljau( &p1, &p2, &mid );
 223
 224     curvePoints( p1, mid, points, count, size, errorSquared );
 225
 226     curvePoints( mid, p2, points, count, size, errorSquared );
 227
 228     (*points)[*(count)++] = p2.p;
 229 }
 230
 231 /** Do it :-).
 232 */
 233 static int filter_get_image( mlt_frame this, uint8_t **image, mlt_image_format *format, int *width, int *height, int writable )
 234 {
 235     mlt_properties properties = MLT_FRAME_PROPERTIES( this );
 236
 237     int mode = mlt_properties_get_int( properties, "mode" );
 238
 239     // Get the image
 240     if ( mode == MODE_RGB )
 241         *format = mlt_image_rgb24;
 242     int error = mlt_frame_get_image( this, image, format, width, height, 1 );
 243
 244     // Only process if we have no error and a valid colour space
 245     if ( !error )
 246     {
 247         BPointF *bpoints;
 248         struct PointF *points;
 249         int bcount, length, count, size, i, j;
 250         bpoints = mlt_properties_get_data( properties, "points", &length );
 251         bcount = length / sizeof( BPointF );
 252
 253         for ( i = 0; i < bcount; i++ )
 254         {
 255             // map to image dimensions
 256             bpoints[i].h1.x *= *width;
 257             bpoints[i].p.x  *= *width;
 258             bpoints[i].h2.x *= *width;
 259             bpoints[i].h1.y *= *height;
 260             bpoints[i].p.y  *= *height;
 261             bpoints[i].h2.y *= *height;
 262         }
 263
 264         double errorSqr = (double)SQR( mlt_properties_get_int( properties, "precision" ) );
 265         count = 0;
 266         size = 1;
 267         points = mlt_pool_alloc( size * sizeof( struct PointF ) );
 268         for ( i = 0; i < bcount; i++ )
 269         {
 270             j = (i + 1) % bcount;
 271             curvePoints( bpoints[i], bpoints[j], &points, &count, &size, &errorSqr );
 272         }
 273
 274         if ( count )
 275         {
 276             uint8_t *map = mlt_pool_alloc( *width * *height );
 277             uint8_t setPoint = !mlt_properties_get_int( properties, "invert" );
 278             fillMap( points, count, *width, *height, setPoint, map );
 279
 280             double bpp = 4;
 281             if ( mode != MODE_ALPHA )
 282             {
 283                 if ( *format == mlt_image_rgb24 )
 284                     bpp = 3;
 285                 else if ( *format == mlt_image_yuv422 )
 286                     bpp = 2;
 287                 else if ( *format == mlt_image_yuv420p )
 288                     bpp = 3 / 2.;
 289             }
 290
 291             i = 0;
 292             length = *width * *height;
 293
 294             uint8_t *p = *image;
 295             uint8_t *q = *image + (int)( length * bpp );
 296
 297             uint8_t *alpha;
 298
 299             switch ( mode )
 300             {
 301             case MODE_RGB:
 302                 // *format == mlt_image_rgb24
 303                 while ( p != q )
 304                 {
 305                     if ( !map[i++] )
 306                         p[0] = p[1] = p[2] = 0;
 307                     p += 3;
 308                 }
 309                 break;
 310             case MODE_MATTE:
 311                 switch ( *format )
 312                 {
 313                     case mlt_image_rgb24:
 314                     case mlt_image_rgb24a:
 315                     case mlt_image_opengl:
 316                         while ( p != q )
 317                         {
 318                             p[0] = p[1] = p[2] = map[i++];
 319                             p += (int)bpp;
 320                         }
 321                         break;
 322                     case mlt_image_yuv422:
 323                         while ( p != q )
 324                         {
 325                             p[0] = map[i++];
 326                             p[1] = 128;
 327                             p += 2;
 328                         }
 329                         break;
 330                     case mlt_image_yuv420p:
 331                         memcpy( p, map, length );
 332                         memset( p + length, 128, length / 2 );
 333                         break;
 334                     default:
 335                         break;
 336                 }
 337                 break;
 338             case MODE_ALPHA:
 339                 alpha = mlt_frame_get_alpha_mask( this );
 340                 switch ( mlt_properties_get_int( properties, "alpha_operation" ) )
 341                 {
 342                 case ALPHA_CLEAR:
 343                     memcpy( alpha, map, length );
 344                     break;
 345                 case ALPHA_MAX:
 346                     for ( ; i < length; i++, alpha++ )
 347                         *alpha = MAX( map[i], *alpha );
 348                     break;
 349                 case ALPHA_MIN:
 350                     for ( ; i < length; i++, alpha++ )
 351                         *alpha = MIN( map[i], *alpha );
 352                     break;
 353                 case ALPHA_ADD:
 354                     for ( ; i < length; i++, alpha++ )
 355                         *alpha = MIN( *alpha + map[i], 255 );
 356                     break;
 357                 case ALPHA_SUB:
 358                     for ( ; i < length; i++, alpha++ )
 359                         *alpha = MAX( *alpha - map[i], 0 );
 360                     break;
 361                 }
 362                 break;
 363             }
 364
 365             mlt_pool_release( map );
 366         }
 367
 368         mlt_pool_release( points );
 369     }
 370
 371     return error;
 372 }
 373
 374 /** Filter processing.
 375 */
 376 static mlt_frame filter_process( mlt_filter this, mlt_frame frame )
 377 {
 378     mlt_properties properties = MLT_FILTER_PROPERTIES( this );
 379     mlt_properties frameProperties = MLT_FRAME_PROPERTIES( frame );
 380     char *spline = mlt_properties_get( properties, "spline" );
 381     char *splineOld = mlt_properties_get( properties, "spline_old" );
 382     char *modeStr = mlt_properties_get( properties, "mode" );
 383
 384     cJSON *root;
 385     int newSpline = 1;
 386     if ( splineOld != NULL && strcmp( spline, splineOld ) == 0 ) {
 387         // the very same parameter was already parsed by json, use the saved json struct
 388         newSpline = 0;
 389         root = mlt_properties_get_data( properties, "spline_json", NULL );
 390     }
 391     else
 392     {
 393         root = cJSON_Parse( spline );
 394     }
 395
 396     if ( root == NULL )
 397         return frame;
 398
 399     BPointF *points;
 400     int count, i;
 401
 402     if ( root->type == cJSON_Array )
 403     {
 404         /*
 405          * constant (over time)
 406          */
 407         count = json2BCurves( root, &points );
 408     }
 409     else
 410     {
 411         /*
 412          * keyframes
 413          */
 414
 415         mlt_position time, pos1, pos2;
 416         time = mlt_frame_get_position( frame );
 417
 418         cJSON *keyframe = root->child;
 419         cJSON *keyframeOld = NULL;
 420         while ( atoi( keyframe->string ) < time && keyframe->next )
 421         {
 422             keyframeOld = keyframe;
 423             keyframe = keyframe->next;
 424         }
 425
 426         if ( keyframeOld == NULL ) {
 427             // parameter has only 1 keyframe or we are before the 1. keyframe
 428             keyframeOld = keyframe;
 429         }
 430
 431         if ( !keyframe )
 432         {
 433             if ( keyframeOld )
 434             {
 435                 // parameter malformed
 436                 keyframe = keyframeOld;
 437             }
 438             else if ( root->child )
 439             {
 440                 // parameter malformed
 441                 keyframe = root->child;
 442                 keyframeOld = keyframe;
 443             }
 444             else
 445             {
 446                 // json object has no children
 447                 cJSON_Delete( root );
 448                 return frame;
 449             }
 450         }
 451
 452         pos2 = atoi( keyframe->string );
 453         pos1 = atoi( keyframeOld->string );
 454
 455         if ( pos1 >= pos2 || time >= pos2 )
 456         {
 457             // keyframes in wrong order or after last keyframe
 458             count = json2BCurves( keyframe, &points );
 459         }
 460         else
 461         {
 462             /*
 463              * pos1 < time < pos2
 464              */
 465
 466             BPointF *p1, *p2;
 467             int c1, c2;
 468             c1 = json2BCurves( keyframeOld, &p1 );
 469             c2 = json2BCurves( keyframe, &p2 );
 470
 471             if ( c1 > c2 )
 472             {
 473                 // number of points decreasing from p1 to p2; we can't handle this yet
 474                 count = c2;
 475                 points = mlt_pool_alloc( count * sizeof( BPointF ) );
 476                 memcpy( points, p2, count * sizeof( BPointF ) );
 477                 mlt_pool_release( p1 );
 478                 mlt_pool_release( p2 );
 479             }
 480             else
 481             {
 482                 // range 0-1
 483                 double position = ( time - pos1 ) / (double)( pos2 - pos1 + 1 );
 484
 485                 count = c1;  // additional points in p2 are ignored
 486                 points = mlt_pool_alloc( count * sizeof( BPointF ) );
 487                 for ( i = 0; i < count; i++ )
 488                 {
 489                     lerp( &(p1[i].h1), &(p2[i].h1), &(points[i].h1), position );
 490                     lerp( &(p1[i].p), &(p2[i].p), &(points[i].p), position );
 491                     lerp( &(p1[i].h2), &(p2[i].h2), &(points[i].h2), position );
 492                 }
 493
 494                 mlt_pool_release( p1 );
 495                 mlt_pool_release( p2 );
 496             }
 497         }
 498     }
 499
 500     int length = count * sizeof( BPointF );
 501
 502     if ( newSpline )
 503     {
 504         mlt_properties_set_data( properties, "spline_json", root, 0, (mlt_destructor)cJSON_Delete, NULL );
 505         mlt_properties_set( properties, "spline_old", strdup( spline ) );
 506     }
 507
 508     mlt_properties_set_data( frameProperties, "points", points, length, (mlt_destructor)mlt_pool_release, NULL );
 509     mlt_properties_set_int( frameProperties, "mode", stringValue( modeStr, MODESTR, 3 ) );
 510     mlt_properties_set_int( frameProperties, "alpha_operation", stringValue( mlt_properties_get( properties, "alpha_operation" ), ALPHAOPERATIONSTR, 5 ) );
 511     mlt_properties_set_int( frameProperties, "invert", mlt_properties_get_int( properties, "invert" ) );
 512     mlt_properties_set_int( frameProperties, "precision", mlt_properties_get_int( properties, "precision" ) );
 513     mlt_frame_push_get_image( frame, filter_get_image );
 514
 515     return frame;
 516 }
 517
 518 /** Constructor for the filter.
 519 */
 520 mlt_filter filter_rotoscoping_init( mlt_profile profile, mlt_service_type type, const char *id, char *arg )
 521 {
 522         mlt_filter this = mlt_filter_new( );
 523         if ( this != NULL )
 524         {
 525                 this->process = filter_process;
 526                 mlt_properties_set( MLT_FILTER_PROPERTIES( this ), "mode", "rgb" );
 527                 mlt_properties_set( MLT_FILTER_PROPERTIES( this ), "alpha_operation", "clear" );
 528                 mlt_properties_set_int( MLT_FILTER_PROPERTIES( this ), "invert", 0 );
 529                 mlt_properties_set_int( MLT_FILTER_PROPERTIES( this ), "precision", 1 );
 530                 if ( arg != NULL )
 531                     mlt_properties_set( MLT_FILTER_PROPERTIES( this ), "spline", arg );
 532         }
 533         return this;
 534 }