git.sesse.net Git - mlt/blob - src/modules/plusgpl/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_LUMA };
  49 const char *MODESTR[3] = { "rgb", "alpha", "luma" };
  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 static 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 /** Sets "spline_is_dirty" to 1 if property "spline" was changed.
  67  * We then know when to parse the json stored in "spline" */
  68 static void rotoPropertyChanged( mlt_service owner, mlt_filter this, char *name )
  69 {
  70     if ( !strcmp( name, "spline" ) )
  71         mlt_properties_set_int( MLT_FILTER_PROPERTIES( this ), "_spline_is_dirty", 1 );
  72 }
  73
  74 /** Linear interp */
  75 static inline void lerp( const PointF *a, const PointF *b, PointF *result, double t )
  76 {
  77     result->x = a->x + ( b->x - a->x ) * t;
  78     result->y = a->y + ( b->y - a->y ) * t;
  79 }
  80
  81 /** Linear interp. with t = 0.5
  82  * Speed gain? */
  83 static inline void lerpHalf( const PointF *a, const PointF *b, PointF *result )
  84 {
  85     result->x = ( a->x + b->x ) * .5;
  86     result->y = ( a->y + b->y ) * .5;
  87 }
  88
  89 /** Helper for using qsort with an array of integers. */
  90 int ncompare( const void *a, const void *b )
  91 {
  92     return *(const int*)a - *(const int*)b;
  93 }
  94
  95 /** Turns a json array with two children into a point (x, y tuple). */
  96 static void jsonGetPoint( cJSON *json, PointF *point )
  97 {
  98     if ( cJSON_GetArraySize( json ) == 2 )
  99     {
 100         point->x = json->child->valuedouble;
 101         point->y = json->child->next->valuedouble;
 102     }
 103 }
 104
 105 /**
 106  * Turns the array of json elements into an array of Bézier points.
 107  * \param array cJSON array. values have to be Bézier points: handle 1, point , handl2
 108  *              ( [ [ [h1x, h1y], [px, py], [h2x, h2y] ], ... ] )
 109  * \param points pointer to array of points. Will be allocated and filled with the points in \param array
 110  * \return number of points
 111  */
 112 static int json2BCurves( cJSON *array, BPointF **points )
 113 {
 114     int count = cJSON_GetArraySize( array );
 115     cJSON *child = array->child;
 116     *points = mlt_pool_alloc( count * sizeof( BPointF ) );
 117
 118     int i = 0;
 119     do
 120     {
 121         if ( child && cJSON_GetArraySize( child ) == 3 )
 122         {
 123             jsonGetPoint( child->child , &(*points)[i].h1 );
 124             jsonGetPoint( child->child->next, &(*points)[i].p );
 125             jsonGetPoint( child->child->next->next, &(*points)[i].h2 );
 126             i++;
 127         }
 128     } while ( child && ( child = child->next ) );
 129
 130     if ( i < count )
 131         *points = mlt_pool_realloc( *points, i * sizeof( BPointF ) );
 132
 133     return i;
 134 }
 135
 136 /** Blurs \param src horizontally. \See funtion blur. */
 137 static void blurHorizontal( uint8_t *src, uint8_t *dst, int width, int height, int radius)
 138 {
 139     int x, y, kx, yOff, total, amount, amountInit;
 140     amountInit = radius * 2 + 1;
 141     for (y = 0; y < height; ++y)
 142     {
 143         total = 0;
 144         yOff = y * width;
 145         // Process entire window for first pixel
 146         int size = MIN(radius + 1, width);
 147         for ( kx = 0; kx < size; ++kx )
 148             total += src[yOff + kx];
 149         dst[yOff] = total / ( radius + 1 );
 150         // Subsequent pixels just update window total
 151         for ( x = 1; x < width; ++x )
 152         {
 153             amount = amountInit;
 154             // Subtract pixel leaving window
 155             if ( x - radius - 1 >= 0 )
 156                 total -= src[yOff + x - radius - 1];
 157             else
 158                 amount -= radius - x;
 159             // Add pixel entering window
 160             if ( x + radius < width )
 161                 total += src[yOff + x + radius];
 162             else
 163                 amount -= radius - width + x;
 164             dst[yOff + x] = total / amount;
 165         }
 166     }
 167 }
 168
 169 /** Blurs \param src vertically. \See funtion blur. */
 170 static void blurVertical( uint8_t *src, uint8_t *dst, int width, int height, int radius)
 171 {
 172     int x, y, ky, total, amount, amountInit;
 173     amountInit = radius * 2 + 1;
 174     for (x = 0; x < width; ++x)
 175     {
 176         total = 0;
 177         int size = MIN(radius + 1, height);
 178         for ( ky = 0; ky < size; ++ky )
 179             total += src[x + ky * width];
 180         dst[x] = total / ( radius + 1 );
 181         for ( y = 1; y < height; ++y )
 182         {
 183             amount = amountInit;
 184             if ( y - radius - 1 >= 0 )
 185                 total -= src[( y - radius - 1 ) * width + x];
 186             else
 187                 amount -= radius - y;
 188             if ( y + radius < height )
 189                 total += src[( y + radius ) * width + x];
 190             else
 191                 amount -= radius - height + y;
 192             dst[y * width + x] = total / amount;
 193         }
 194     }
 195 }
 196
 197 /**
 198  * Blurs the \param map using a simple "average" blur.
 199  * \param map Will be blured; 1bpp
 200  * \param width x dimension of channel stored in \param map
 201  * \param height y dimension of channel stored in \param map
 202  * \param radius blur radius
 203  * \param passes blur passes
 204  */
 205 static void blur( uint8_t *map, int width, int height, int radius, int passes )
 206 {
 207     uint8_t *src = mlt_pool_alloc( width * height );
 208     uint8_t *tmp = mlt_pool_alloc( width * height );
 209
 210     int i;
 211     for ( i = 0; i < passes; ++i )
 212     {
 213         memcpy( src, map, width * height );
 214         blurHorizontal( src, tmp, width, height, radius );
 215         blurVertical( tmp, map, width, height, radius );
 216     }
 217
 218     mlt_pool_release(src);
 219     mlt_pool_release(tmp);
 220 }
 221
 222 /**
 223  * Determines which points are located in the polygon and sets their value in \param map to \param value
 224  * \param vertices points defining the polygon
 225  * \param count number of vertices
 226  * \param with x range
 227  * \param height y range
 228  * \param value value identifying points in the polygon
 229  * \param map array of integers of the dimension width * height.
 230  *            The map entries belonging to the points in the polygon will be set to \param set * 255 the others to !set * 255.
 231  */
 232 static void fillMap( PointF *vertices, int count, int width, int height, int invert, uint8_t *map )
 233 {
 234     int nodes, nodeX[1024], pixelY, i, j, value;
 235
 236     value = !invert * 255;
 237     memset( map, invert * 255, width * height );
 238
 239     // Loop through the rows of the image
 240     for ( pixelY = 0; pixelY < height; pixelY++ )
 241     {
 242         /*
 243          * Build a list of nodes.
 244          * nodes are located at the borders of the polygon
 245          * and therefore indicate a move from in to out or vice versa
 246          */
 247         nodes = 0;
 248         for ( i = 0, j = count - 1; i < count; j = i++ )
 249             if ( (vertices[i].y > (double)pixelY) != (vertices[j].y > (double)pixelY) )
 250                 nodeX[nodes++] = (int)(vertices[i].x + (pixelY - vertices[i].y) / (vertices[j].y - vertices[i].y) * (vertices[j].x - vertices[i].x) );
 251
 252         qsort( nodeX, nodes, sizeof( int ), ncompare );
 253
 254         // Set map values for points between the node pairs to 1
 255         for ( i = 0; i < nodes; i += 2 )
 256         {
 257             if ( nodeX[i] >= width )
 258                 break;
 259
 260             if ( nodeX[i+1] > 0 )
 261             {
 262                 nodeX[i] = MAX( 0, nodeX[i] );
 263                 nodeX[i+1] = MIN( nodeX[i+1], width );
 264                 memset( map + width * pixelY + nodeX[i], value, nodeX[i+1] - nodeX[i] );
 265             }
 266         }
 267     }
 268 }
 269
 270 /** Determines the point in the middle of the Bézier curve (t = 0.5) defined by \param p1 and \param p2
 271  * using De Casteljau's algorithm.
 272  */
 273 static void deCasteljau( BPointF *p1, BPointF *p2, BPointF *mid )
 274 {
 275     struct PointF ab, bc, cd;
 276
 277     lerpHalf( &(p1->p), &(p1->h2), &ab );
 278     lerpHalf( &(p1->h2), &(p2->h1), &bc );
 279     lerpHalf( &(p2->h1), &(p2->p), &cd );
 280     lerpHalf( &ab, &bc, &(mid->h1) ); // mid->h1 = abbc
 281     lerpHalf( &bc, &cd, &(mid->h2) ); // mid->h2 = bccd
 282     lerpHalf( &(mid->h1), &(mid->h2), &(mid->p) );
 283
 284     p1->h2 = ab;
 285     p2->h1 = cd;
 286 }
 287
 288 /**
 289  * Calculates points for the cubic Bézier curve defined by \param p1 and \param p2.
 290  * Points are calculated until the squared distanced between neighbour points is smaller than 2.
 291  * \param points Pointer to list of points. Will be allocted and filled with calculated points.
 292  * \param count Number of calculated points in \param points
 293  * \param size Allocated size of \param points (in elements not in bytes)
 294  */
 295 static void curvePoints( BPointF p1, BPointF p2, PointF **points, int *count, int *size )
 296 {
 297     double errorSqr = SQR( p1.p.x - p2.p.x ) + SQR( p1.p.y - p2.p.y );
 298
 299     if ( *size + 1 >= *count )
 300     {
 301         *size += (int)sqrt( errorSqr / 2 );
 302         *points = mlt_pool_realloc( *points, *size * sizeof ( struct PointF ) );
 303     }
 304
 305     (*points)[(*count)++] = p1.p;
 306
 307     if ( errorSqr <= 2 )
 308         return;
 309
 310     BPointF mid;
 311     deCasteljau( &p1, &p2, &mid );
 312
 313     curvePoints( p1, mid, points, count, size );
 314
 315     curvePoints( mid, p2, points, count, size );
 316
 317     (*points)[*(count)++] = p2.p;
 318 }
 319
 320 /** Do it :-).
 321 */
 322 static int filter_get_image( mlt_frame frame, uint8_t **image, mlt_image_format *format, int *width, int *height, int writable )
 323 {
 324     mlt_properties unique = mlt_frame_pop_service( frame );
 325
 326     int mode = mlt_properties_get_int( unique, "mode" );
 327
 328     // Get the image
 329     if ( mode == MODE_RGB )
 330         *format = mlt_image_rgb24;
 331     int error = mlt_frame_get_image( frame, image, format, width, height, writable );
 332
 333     // Only process if we have no error and a valid colour space
 334     if ( !error )
 335     {
 336         BPointF *bpoints;
 337         struct PointF *points;
 338         int bcount, length, count, size, i, j;
 339         bpoints = mlt_properties_get_data( unique, "points", &length );
 340         bcount = length / sizeof( BPointF );
 341
 342         for ( i = 0; i < bcount; i++ )
 343         {
 344             // map to image dimensions
 345             bpoints[i].h1.x *= *width;
 346             bpoints[i].p.x  *= *width;
 347             bpoints[i].h2.x *= *width;
 348             bpoints[i].h1.y *= *height;
 349             bpoints[i].p.y  *= *height;
 350             bpoints[i].h2.y *= *height;
 351         }
 352
 353         count = 0;
 354         size = 1;
 355         points = mlt_pool_alloc( size * sizeof( struct PointF ) );
 356         for ( i = 0; i < bcount; i++ )
 357         {
 358             j = (i + 1) % bcount;
 359             curvePoints( bpoints[i], bpoints[j], &points, &count, &size );
 360         }
 361
 362         if ( count )
 363         {
 364             length = *width * *height;
 365             uint8_t *map = mlt_pool_alloc( length );
 366             int invert = mlt_properties_get_int( unique, "invert" );
 367             fillMap( points, count, *width, *height, invert, map );
 368
 369             int feather = mlt_properties_get_int( unique, "feather" );
 370             if ( feather && mode != MODE_RGB )
 371                 blur( map, *width, *height, feather, mlt_properties_get_int( unique, "feather_passes" ) );
 372
 373             int bpp;
 374             size = mlt_image_format_size( *format, *width, *height, &bpp );
 375             uint8_t *p = *image;
 376             uint8_t *q = *image + size;
 377
 378             i = 0;
 379             uint8_t *alpha;
 380
 381             switch ( mode )
 382             {
 383             case MODE_RGB:
 384                 // *format == mlt_image_rgb24
 385                 while ( p != q )
 386                 {
 387                     if ( !map[i++] )
 388                         p[0] = p[1] = p[2] = 0;
 389                     p += 3;
 390                 }
 391                 break;
 392             case MODE_LUMA:
 393                 switch ( *format )
 394                 {
 395                     case mlt_image_rgb24:
 396                     case mlt_image_rgb24a:
 397                     case mlt_image_opengl:
 398                         while ( p != q )
 399                         {
 400                             p[0] = p[1] = p[2] = map[i++];
 401                             p += bpp;
 402                         }
 403                         break;
 404                     case mlt_image_yuv422:
 405                         while ( p != q )
 406                         {
 407                             p[0] = map[i++];
 408                             p[1] = 128;
 409                             p += 2;
 410                         }
 411                         break;
 412                     case mlt_image_yuv420p:
 413                         memcpy( p, map, length );
 414                         memset( p + length, 128, length / 2 );
 415                         break;
 416                     default:
 417                         break;
 418                 }
 419                 break;
 420             case MODE_ALPHA:
 421                 switch ( *format )
 422                 {
 423                 case mlt_image_rgb24a:
 424                 case mlt_image_opengl:
 425                     switch ( mlt_properties_get_int( unique, "alpha_operation" ) )
 426                     {
 427                     case ALPHA_CLEAR:
 428                         while ( p != q )
 429                         {
 430                             p[3] = map[i++];
 431                             p += 4;
 432                         }
 433                         break;
 434                     case ALPHA_MAX:
 435                         while ( p != q )
 436                         {
 437                             p[3] = MAX( p[3], map[i] );
 438                             p += 4;
 439                             i++;
 440                         }
 441                         break;
 442                     case ALPHA_MIN:
 443                         while ( p != q )
 444                         {
 445                             p[3] = MIN( p[3], map[i] );
 446                             p += 4;
 447                             i++;
 448                         }
 449                         break;
 450                     case ALPHA_ADD:
 451                         while ( p != q )
 452                         {
 453                             p[3] = MIN( p[3] + map[i], 255 );
 454                             p += 4;
 455                             i++;
 456                         }
 457                         break;
 458                     case ALPHA_SUB:
 459                         while ( p != q )
 460                         {
 461                             p[3] = MAX( p[3] - map[i], 0 );
 462                             p += 4;
 463                             i++;
 464                         }
 465                         break;
 466                     }
 467                     break;
 468                 default:
 469                     alpha = mlt_frame_get_alpha_mask( frame );
 470                     switch ( mlt_properties_get_int( unique, "alpha_operation" ) )
 471                     {
 472                     case ALPHA_CLEAR:
 473                         memcpy( alpha, map, length );
 474                         break;
 475                     case ALPHA_MAX:
 476                         for ( ; i < length; i++, alpha++ )
 477                             *alpha = MAX( map[i], *alpha );
 478                         break;
 479                     case ALPHA_MIN:
 480                         for ( ; i < length; i++, alpha++ )
 481                             *alpha = MIN( map[i], *alpha );
 482                         break;
 483                     case ALPHA_ADD:
 484                         for ( ; i < length; i++, alpha++ )
 485                             *alpha = MIN( *alpha + map[i], 255 );
 486                         break;
 487                     case ALPHA_SUB:
 488                         for ( ; i < length; i++, alpha++ )
 489                             *alpha = MAX( *alpha - map[i], 0 );
 490                         break;
 491                     }
 492                     break;
 493                 }
 494                 break;
 495             }
 496
 497             mlt_pool_release( map );
 498         }
 499
 500         mlt_pool_release( points );
 501     }
 502
 503     return error;
 504 }
 505
 506 /** Filter processing.
 507 */
 508 static mlt_frame filter_process( mlt_filter filter, mlt_frame frame )
 509 {
 510     mlt_properties properties = MLT_FILTER_PROPERTIES( filter );
 511     int splineIsDirty = mlt_properties_get_int( properties, "_spline_is_dirty" );
 512     char *modeStr = mlt_properties_get( properties, "mode" );
 513     cJSON *root = mlt_properties_get_data( properties, "_spline_parsed", NULL );
 514
 515     if ( splineIsDirty || root == NULL )
 516     {
 517         // we need to (re-)parse
 518         char *spline = mlt_properties_get( properties, "spline" );
 519         root = cJSON_Parse( spline );
 520         mlt_properties_set_data( properties, "_spline_parsed", root, 0, (mlt_destructor)cJSON_Delete, NULL );
 521         mlt_properties_set_int( properties, "_spline_is_dirty", 0 );
 522     }
 523
 524     if ( root == NULL )
 525         return frame;
 526
 527     BPointF *points;
 528     int count, i;
 529
 530     if ( root->type == cJSON_Array )
 531     {
 532         /*
 533          * constant
 534          */
 535         count = json2BCurves( root, &points );
 536     }
 537     else if ( root->type == cJSON_Object )
 538     {
 539         /*
 540          * keyframes
 541          */
 542
 543         mlt_position time, pos1, pos2;
 544         time = mlt_frame_get_position( frame );
 545
 546         cJSON *keyframe = root->child;
 547         cJSON *keyframeOld = keyframe;
 548
 549         if ( !keyframe )
 550             return frame;
 551
 552         while ( atoi( keyframe->string ) < time && keyframe->next )
 553         {
 554             keyframeOld = keyframe;
 555             keyframe = keyframe->next;
 556         }
 557
 558         pos1 = atoi( keyframeOld->string );
 559         pos2 = atoi( keyframe->string );
 560
 561         if ( pos1 >= pos2 || time >= pos2 )
 562         {
 563             // keyframes in wrong order or before first / after last keyframe
 564             count = json2BCurves( keyframe, &points );
 565         }
 566         else
 567         {
 568             /*
 569              * pos1 < time < pos2
 570              */
 571
 572             BPointF *p1, *p2;
 573             int c1 = json2BCurves( keyframeOld, &p1 );
 574             int c2 = json2BCurves( keyframe, &p2 );
 575
 576             // range 0-1
 577             double position = ( time - pos1 ) / (double)( pos2 - pos1 + 1 );
 578
 579             count = MIN( c1, c2 );  // additional points are ignored
 580             points = mlt_pool_alloc( count * sizeof( BPointF ) );
 581             for ( i = 0; i < count; i++ )
 582             {
 583                 lerp( &(p1[i].h1), &(p2[i].h1), &(points[i].h1), position );
 584                 lerp( &(p1[i].p), &(p2[i].p), &(points[i].p), position );
 585                 lerp( &(p1[i].h2), &(p2[i].h2), &(points[i].h2), position );
 586             }
 587
 588             mlt_pool_release( p1 );
 589             mlt_pool_release( p2 );
 590         }
 591     }
 592     else
 593     {
 594         return frame;
 595     }
 596
 597     mlt_properties unique = mlt_frame_unique_properties( frame, MLT_FILTER_SERVICE( filter ) );
 598     mlt_properties_set_data( unique, "points", points, count * sizeof( BPointF ), (mlt_destructor)mlt_pool_release, NULL );
 599     mlt_properties_set_int( unique, "mode", stringValue( modeStr, MODESTR, 3 ) );
 600     mlt_properties_set_int( unique, "alpha_operation", stringValue( mlt_properties_get( properties, "alpha_operation" ), ALPHAOPERATIONSTR, 5 ) );
 601     mlt_properties_set_int( unique, "invert", mlt_properties_get_int( properties, "invert" ) );
 602     mlt_properties_set_int( unique, "feather", mlt_properties_get_int( properties, "feather" ) );
 603     mlt_properties_set_int( unique, "feather_passes", mlt_properties_get_int( properties, "feather_passes" ) );
 604     mlt_frame_push_service( frame, unique );
 605     mlt_frame_push_get_image( frame, filter_get_image );
 606
 607     return frame;
 608 }
 609
 610 /** Constructor for the filter.
 611 */
 612 mlt_filter filter_rotoscoping_init( mlt_profile profile, mlt_service_type type, const char *id, char *arg )
 613 {
 614         mlt_filter filter = mlt_filter_new( );
 615         if ( filter )
 616         {
 617                 filter->process = filter_process;
 618                 mlt_properties properties = MLT_FILTER_PROPERTIES( filter );
 619                 mlt_properties_set( properties, "mode", "alpha" );
 620                 mlt_properties_set( properties, "alpha_operation", "clear" );
 621                 mlt_properties_set_int( properties, "invert", 0 );
 622                 mlt_properties_set_int( properties, "feather", 0 );
 623                 mlt_properties_set_int( properties, "feather_passes", 1 );
 624                 if ( arg )
 625                     mlt_properties_set( properties, "spline", arg );
 626
 627                 mlt_events_listen( properties, filter, "property-changed", (mlt_listener)rotoPropertyChanged );
 628         }
 629         return filter;
 630 }