1 /*
2 * zoom.c - resize an image to an arbitrary size with filtering
3 * Based on "Filtered Image Rescaling" by Dale Schumacher (public domain).
4 *
5 * This file is part of transcode, a video stream processing tool.
6 * transcode is free software, distributable under the terms of the GNU
7 * General Public License (version 2 or later). See the file COPYING
8 * for details.
9 */
10
11 #include "tcvideo.h"
12 #include "zoom.h"
13
14 #include "src/transcode.h"
15 #include <math.h>
16
17 /*************************************************************************/
18
19 /* Data structures for holding resizing data (used internally). */
20
21 /* A contributor to a single pixel */
22 struct contrib {
23 int pixel;
24 double weight;
25 };
26
27 /* List of all contributors to a single pixel */
28 struct clist {
29 int n; /* Number of contributors */
30 struct contrib *list; /* Pointer to list of contributors */
31 };
32
33 /* Data for a resize operation */
34 struct zoominfo {
35 int old_w, old_h; /* Original width and height */
36 int new_w, new_h; /* New width and height */
37 int Bpp; /* Bytes per pixel */
38 int old_stride; /* Bytes per line (original image) */
39 int new_stride; /* Bytes per line (new image) */
40 double (*filter)(double); /* Filter function */
41 double fwidth; /* Filter width */
42 int32_t *x_contrib; /* Contributors in the horizontal direction */
43 int32_t *y_contrib; /* Contributors in the vertical direction */
44 uint8_t *tmpimage; /* Temporary buffer */
45 };
46
47 /* Convert a double to a 16.16 fixed-point value */
48 #define DOUBLE_TO_FIXED(v) ((int32_t)((v)*65536))
49
50 /* Convert a 16.16 fixed-point value to an integer */
51 #define FIXED_TO_INT(v) ((v)>>16)
52
53 /*************************************************************************/
54
55 /* FIXME: use a static table for every data related to a filter,
56 * accessed by filter_id;
57 * typedef struct tcvzoomdata_ TCVZoomData;
58 * struct tcvzoom_data {
59 * const char *name;
60 * double support;
61 * double (*filter)(double t);
62 * };
63 */
64
65 /**
66 * tcv_zoom_filter_to_string:
67 * return the human-readable name of a given filter, as string.
68 *
69 * Parameters:
70 * filter: Filter identifier (TCV_ZOOM_*).
71 * Return value:
72 * name of the given filter. DO NOT free() it.
73 * NULL if the filter is unknown/unsupported.
74 */
tcv_zoom_filter_to_string(TCVZoomFilter filter)75 const char *tcv_zoom_filter_to_string(TCVZoomFilter filter)
76 {
77 const char *name = NULL;
78 if (filter == TCV_ZOOM_BELL) {
79 name = "Bell";
80 } else if (filter == TCV_ZOOM_BOX) {
81 name = "Box";
82 } else if (filter == TCV_ZOOM_B_SPLINE) {
83 name = "B_spline";
84 } else if (filter == TCV_ZOOM_HERMITE) {
85 name = "Hermite";
86 } else if (filter == TCV_ZOOM_LANCZOS3) {
87 name = "Lanczos3";
88 } else if (filter == TCV_ZOOM_MITCHELL) {
89 name = "Mitchell";
90 } else if (filter == TCV_ZOOM_TRIANGLE) {
91 name = "Triangle";
92 } else if (filter == TCV_ZOOM_CUBIC_KEYS4) {
93 name = "Cubic_Keys4";
94 } else if (filter == TCV_ZOOM_SINC8) {
95 name = "Sinc8";
96 } else if (filter == TCV_ZOOM_DEFAULT) {
97 name = "Lanczos3";
98 } else {
99 name = NULL;
100 }
101 return name;
102 }
103
104 /**
105 * tcv_zoom_filter_from_string:
106 * return the filter id given its human-readable name, as string.
107 * case insensitive.
108 *
109 * Parameters:
110 * name: name fo the given filter.
111 * Return value:
112 * the corrisponding identifier of the given name.
113 * TCV_ZOOM_NULL if the filter is unknown/unsupported.
114 */
tcv_zoom_filter_from_string(const char * name)115 TCVZoomFilter tcv_zoom_filter_from_string(const char *name)
116 {
117 TCVZoomFilter filter = TCV_ZOOM_NULL;
118 if (strcasecmp(name, "bell") == 0) {
119 filter = TCV_ZOOM_BELL;
120 } else if (strcasecmp(name, "box") == 0) {
121 filter = TCV_ZOOM_BOX;
122 } else if (strcasecmp(name, "b_spline") == 0) {
123 filter = TCV_ZOOM_B_SPLINE;
124 } else if (strcasecmp(name, "hermite") == 0) {
125 filter = TCV_ZOOM_HERMITE;
126 } else if (strcasecmp(name, "lanczos3") == 0) {
127 filter = TCV_ZOOM_LANCZOS3;
128 } else if (strcasecmp(name, "mitchell") == 0) {
129 filter = TCV_ZOOM_MITCHELL;
130 } else if (strcasecmp(name, "triangle") == 0) {
131 filter = TCV_ZOOM_TRIANGLE;
132 } else if (strcasecmp(name, "cubic_keys4") == 0) {
133 filter = TCV_ZOOM_CUBIC_KEYS4;
134 } else if (strcasecmp(name, "sinc8") == 0) {
135 filter = TCV_ZOOM_SINC8;
136 } else if (strcasecmp(name, "default") == 0) {
137 filter = TCV_ZOOM_LANCZOS3;
138 } else {
139 filter = TCV_ZOOM_NULL;
140 }
141 return filter;
142 }
143
144 /*************************************************************************/
145 /*************************************************************************/
146
147 /**
148 * *_filter: Filter functions for resizing.
149 *
150 * Parameters:
151 * t: Filter parameter.
152 * Return value:
153 * Filter result.
154 * Postconditions: 0 <= t && t <= 1
155 */
156
157 /************************************/
158
159 static const double hermite_support = 1.0;
160
hermite_filter(double t)161 static double hermite_filter(double t)
162 {
163 /* f(t) = 2|t|^3 - 3|t|^2 + 1, -1 <= t <= 1 */
164 if (t < 0.0)
165 t = -t;
166 if (t < 1.0)
167 return (2.0 * t - 3.0) * t * t + 1.0;
168 return 0.0;
169 }
170
171 /************************************/
172
173 static const double box_support = 0.5;
174
box_filter(double t)175 static double box_filter(double t)
176 {
177 if ((t > -0.5) && (t <= 0.5))
178 return 1.0;
179 return 0.0;
180 }
181
182 /************************************/
183
184 static const double triangle_support = 1.0;
185
triangle_filter(double t)186 static double triangle_filter(double t)
187 {
188 if (t < 0.0)
189 t = -t;
190 if (t < 1.0)
191 return 1.0 - t;
192 return 0.0;
193 }
194
195 /************************************/
196
197 static const double bell_support = 1.5;
198
bell_filter(double t)199 static double bell_filter(double t)
200 {
201 if (t < 0)
202 t = -t;
203 if (t < .5)
204 return .75 - (t * t);
205 if (t < 1.5) {
206 t = (t - 1.5);
207 return .5 * (t * t);
208 }
209 return 0.0;
210 }
211
212 /************************************/
213
214 static const double B_spline_support = 2.0;
215
B_spline_filter(double t)216 static double B_spline_filter(double t)
217 {
218 double tt;
219
220 if (t < 0)
221 t = -t;
222 if (t < 1) {
223 tt = t * t;
224 return (.5 * tt * t) - tt + (2.0 / 3.0);
225 } else if (t < 2) {
226 t = 2 - t;
227 return (1.0 / 6.0) * (t * t * t);
228 }
229 return 0.0;
230 }
231
232 /************************************/
233
234 static const double lanczos3_support = 3.0;
235
236 #ifndef PI
237 # define PI 3.14159265358979323846264338327950
238 #endif
239 #define SINC(x) ((x) != 0 ? sin((x)*PI) / ((x)*PI) : 1.0)
240
lanczos3_filter(double t)241 static double lanczos3_filter(double t)
242 {
243 if (t < 0)
244 t = -t;
245 if (t < 3.0)
246 return SINC(t) * SINC(t/3.0);
247 return 0.0;
248 }
249
250 #undef SINC
251
252 /************************************/
253
254 static const double mitchell_support = 2.0;
255
256 #define B (1.0 / 3.0)
257 #define C (1.0 / 3.0)
258
mitchell_filter(double t)259 static double mitchell_filter(double t)
260 {
261 double tt;
262
263 tt = t * t;
264 if (t < 0)
265 t = -t;
266 if (t < 1.0) {
267 t = (((12.0 - 9.0 * B - 6.0 * C) * (t * tt))
268 + ((-18.0 + 12.0 * B + 6.0 * C) * tt)
269 + (6.0 - 2 * B));
270 return t / 6.0;
271 } else if (t < 2.0) {
272 t = (((-1.0 * B - 6.0 * C) * (t * tt))
273 + ((6.0 * B + 30.0 * C) * tt)
274 + ((-12.0 * B - 48.0 * C) * t)
275 + (8.0 * B + 24 * C));
276 return t / 6.0;
277 }
278 return 0.0;
279 }
280
281 #undef B
282 #undef C
283
284 /************************************/
285 /* Keys 4th-order Cubic */
286
287 static const double cubic_keys4_support = 3.0;
288
cubic_keys4_filter(double t)289 static double cubic_keys4_filter(double t)
290 {
291 if (t < 0.0)
292 t = -t;
293 if (t < 1.0)
294 return (3.0 + (t * t * (-7.0 + (t * 4.0)))) / 3.0;
295 if (t < 2.0)
296 return (30.0 + (t * (-59.0 + (t * (36.0 + (t * -7.0)))))) / 12.0;
297 if (t < 3.0)
298 return (-18.0 + (t * (21.0 + (t * (-8.0 + t))))) / 12.0;
299 return 0.0;
300 }
301
302 /************************************/
303 /* Sinc with Lanczos window, 8 cycles */
304
305 static const double sinc8_support = 8.0;
306
sinc8_filter(double t)307 static double sinc8_filter(double t)
308 {
309 if (t < 0.0)
310 t = -t;
311 if (t == 0.0) {
312 return 1.0;
313 } else if (t < 8.0) {
314 double w = sin(PI*t / 8.0) / (PI*t / 8.0);
315 return w * sin(t*PI) / (t*PI);
316 } else {
317 return 0.0;
318 }
319 }
320
321 /*************************************************************************/
322
323 /**
324 * gen_contrib: Helper function to generate the list of contributors to
325 * each resized pixel in one direction (horizontal or vertical).
326 *
327 * Parameters:
328 * oldsize: Size of original image in the direction for which
329 * contributors are being generated.
330 * newsize: Size of resized image in the direction for which
331 * contributors are being generated.
332 * stride: Number of bytes between adjacent pixels in the direction
333 * for which contributors are being generated.
334 * filter: As for zoom_process().
335 * fwidth: As for zoom_process().
336 * Return value:
337 * A pointer to a `newsize'-element array of `struct clist' elements,
338 * or NULL on error (out of memory).
339 * Preconditions:
340 * oldsize > 0
341 * newsize > 0
342 * stride > 0
343 * filter != NULL
344 * fwidth > 0
345 */
346
gen_contrib(int oldsize,int newsize,int stride,double (* filter)(double),double fwidth)347 static struct clist *gen_contrib(int oldsize, int newsize, int stride,
348 double (*filter)(double), double fwidth)
349 {
350 struct clist *contrib;
351 double scale = (double)newsize / (double)oldsize;
352 double new_fwidth, fscale;
353 int i, j;
354
355 contrib = tc_zalloc(newsize * sizeof(struct clist));
356
357 if (scale < 1.0) {
358 fscale = 1.0 / scale;
359 } else {
360 fscale = 1.0;
361 }
362 new_fwidth = fwidth * fscale;
363 for (i = 0; i < newsize; ++i) {
364 double center = (double) i / scale;
365 int left = ceil(center - new_fwidth);
366 int right = floor(center + new_fwidth);
367 contrib[i].n = 0;
368 contrib[i].list = tc_zalloc((right-left+1) * sizeof(struct contrib));
369 for (j = left; j <= right; ++j) {
370 int k, n;
371 double weight = center - (double) j;
372 weight = (*filter)(weight / fscale) / fscale;
373 if (j < 0) {
374 n = -j;
375 } else if (j >= oldsize) {
376 n = (oldsize - j) + oldsize - 1;
377 } else {
378 n = j;
379 }
380 k = contrib[i].n++;
381 contrib[i].list[k].pixel = n*stride;
382 contrib[i].list[k].weight = weight;
383 }
384 }
385
386 return contrib;
387 }
388
389 /*************************************************************************/
390 /*************************************************************************/
391
392 /* External interface. */
393
394 /*************************************************************************/
395
396 /**
397 * zoom_init: Allocate, initialize, and return a ZoomInfo structure for
398 * use in subsequent zoom_process() calls. The structure should be freed
399 * with zoom_free() when no longer needed.
400 *
401 * Parameters:
402 * old_w: Width of original image.
403 * old_h: Height of original image.
404 * new_w: Width of resized image.
405 * new_h: Height of resized image.
406 * Bpp: Bytes (not bits!) per pixel.
407 * old_stride: Bytes per line of original image.
408 * new_stride: Bytes per line of resized image.
409 * filter: Filter identifier (TCV_ZOOM_*).
410 * Return value:
411 * A pointer to a newly allocated ZoomInfo structure, or NULL on error
412 * (invalid parameters or out of memory).
413 */
414
zoom_init(int old_w,int old_h,int new_w,int new_h,int Bpp,int old_stride,int new_stride,TCVZoomFilter filter)415 ZoomInfo *zoom_init(int old_w, int old_h, int new_w, int new_h, int Bpp,
416 int old_stride, int new_stride, TCVZoomFilter filter)
417 {
418 ZoomInfo *zi;
419 struct clist *x_contrib = NULL, *y_contrib = NULL;
420
421 /* Sanity check */
422 if (old_w <= 0 || old_h <= 0 || new_w <= 0 || new_h <= 0 || Bpp <= 0
423 || old_stride <= 0 || new_stride <= 0)
424 return NULL;
425
426 /* Allocate structure */
427 zi = tc_malloc(sizeof(*zi));
428 if (!zi)
429 return NULL;
430
431 /* Set up scalar members, and check filter value */
432 zi->old_w = old_w;
433 zi->old_h = old_h;
434 zi->new_w = new_w;
435 zi->new_h = new_h;
436 zi->Bpp = Bpp;
437 zi->old_stride = old_stride;
438 zi->new_stride = new_stride;
439 switch (filter) {
440 case TCV_ZOOM_BOX:
441 zi->filter = box_filter;
442 zi->fwidth = box_support;
443 break;
444 case TCV_ZOOM_TRIANGLE:
445 zi->filter = triangle_filter;
446 zi->fwidth = triangle_support;
447 break;
448 case TCV_ZOOM_HERMITE:
449 zi->filter = hermite_filter;
450 zi->fwidth = hermite_support;
451 break;
452 case TCV_ZOOM_BELL:
453 zi->filter = bell_filter;
454 zi->fwidth = bell_support;
455 break;
456 case TCV_ZOOM_B_SPLINE:
457 zi->filter = B_spline_filter;
458 zi->fwidth = B_spline_support;
459 break;
460 case TCV_ZOOM_MITCHELL:
461 zi->filter = mitchell_filter;
462 zi->fwidth = mitchell_support;
463 break;
464 case TCV_ZOOM_LANCZOS3:
465 zi->filter = lanczos3_filter;
466 zi->fwidth = lanczos3_support;
467 break;
468 case TCV_ZOOM_CUBIC_KEYS4:
469 zi->filter = cubic_keys4_filter;
470 zi->fwidth = cubic_keys4_support;
471 break;
472 case TCV_ZOOM_SINC8:
473 zi->filter = sinc8_filter;
474 zi->fwidth = sinc8_support;
475 break;
476 default:
477 free(zi);
478 return NULL;
479 }
480
481 /* Generate contributor lists and allocate temporary image buffer */
482 zi->x_contrib = NULL;
483 zi->y_contrib = NULL;
484 zi->tmpimage = tc_malloc(new_w * old_h * Bpp);
485 if (!zi->tmpimage)
486 goto error_out;
487 if (old_w != new_w) {
488 x_contrib = gen_contrib(old_w, new_w, Bpp, zi->filter, zi->fwidth);
489 if (!x_contrib)
490 goto error_out;
491 }
492 if (old_h != new_h) {
493 /* Calculate the correct stride--if the width isn't changing,
494 * this will just be old_stride */
495 int stride = (old_w==new_w) ? old_stride : Bpp*new_w;
496 y_contrib = gen_contrib(old_h, new_h, stride, zi->filter,
497 zi->fwidth);
498 if (!y_contrib)
499 goto error_out;
500 }
501
502 /* Convert contributor lists into flat arrays and fixed-point values.
503 * The flat array consists of a contributor count plus two values per
504 * contributor (index and fixed-point weight) for each output pixel.
505 * Note that for the horizontal direction, we make `Bpp' copies of the
506 * contributors, adjusting the offset for each byte of the pixel. */
507
508 if (x_contrib) {
509 int count = 0, i;
510 int32_t *ptr;
511
512 for (i = 0; i < new_w; i++)
513 count += 1 + 2 * x_contrib[i].n;
514 zi->x_contrib = tc_malloc(sizeof(int32_t) * count * Bpp);
515 if (!zi->x_contrib)
516 goto error_out;
517 for (ptr = zi->x_contrib, i = 0; i < new_w * Bpp; i++) {
518 int j;
519 *ptr++ = x_contrib[i/Bpp].n;
520 for (j = 0; j < x_contrib[i/Bpp].n; j++) {
521 *ptr++ = x_contrib[i/Bpp].list[j].pixel + i%Bpp;
522 *ptr++ = DOUBLE_TO_FIXED(x_contrib[i/Bpp].list[j].weight);
523 }
524 }
525 /* Free original contributor list */
526 for (i = 0; i < new_w; i++)
527 free(x_contrib[i].list);
528 free(x_contrib);
529 x_contrib = NULL;
530 }
531
532 if (y_contrib) {
533 int count = 0, i;
534 int32_t *ptr;
535
536 for (i = 0; i < new_h; i++)
537 count += 1 + 2 * y_contrib[i].n;
538 zi->y_contrib = tc_malloc(sizeof(int32_t) * count);
539 if (!zi->y_contrib)
540 goto error_out;
541 for (ptr = zi->y_contrib, i = 0; i < new_h; i++) {
542 int j;
543 *ptr++ = y_contrib[i].n;
544 for (j = 0; j < y_contrib[i].n; j++) {
545 *ptr++ = y_contrib[i].list[j].pixel;
546 *ptr++ = DOUBLE_TO_FIXED(y_contrib[i].list[j].weight);
547 }
548 }
549 for (i = 0; i < new_h; i++)
550 free(y_contrib[i].list);
551 free(y_contrib);
552 y_contrib = NULL;
553 }
554
555 /* Done */
556 return zi;
557
558 error_out:
559 {
560 if (x_contrib) {
561 int i;
562 for (i = 0; i < new_w; i++)
563 free(x_contrib[i].list);
564 free(x_contrib);
565 }
566 if (y_contrib) {
567 int i;
568 for (i = 0; i < new_w; i++)
569 free(x_contrib[i].list);
570 free(x_contrib);
571 }
572 zoom_free(zi);
573 return NULL;
574 }
575 }
576
577 /*************************************************************************/
578
579 /**
580 * zoom_process: Image resizing core.
581 *
582 * Parameters:
583 * zi: ZoomInfo structure allocated by zoom_init().
584 * src: Source data plane.
585 * dest: Destination data plane.
586 * Return value: None.
587 * Preconditions:
588 * zi was allocated by zoom_init()
589 * src != NULL
590 * dest != NULL
591 * src and dest do not overlap
592 */
593
594 /* clamp the input to the specified range */
595 #define CLAMP(v,l,h) ((v)<(l) ? (l) : (v) > (h) ? (h) : (v))
596
zoom_process(const ZoomInfo * zi,const uint8_t * src,uint8_t * dest)597 void zoom_process(const ZoomInfo *zi, const uint8_t *src, uint8_t *dest)
598 {
599 int from_stride, to_stride;
600 const uint8_t *from;
601 uint8_t *to;
602
603 from = src;
604 from_stride = zi->old_stride;
605
606 /* Apply filter to zoom horizontally from src to tmp (if necessary) */
607 if (zi->x_contrib) {
608 int y;
609 to = zi->tmpimage;
610 to_stride = zi->new_w * zi->Bpp;
611 for (y = 0; y < zi->old_h; y++, from += from_stride, to += to_stride) {
612 int32_t *contrib = zi->x_contrib;
613 int x;
614 for (x = 0; x < zi->new_w * zi->Bpp; x++) {
615 int32_t weight = DOUBLE_TO_FIXED(0.5);
616 int n = *contrib++, i;
617 for (i = 0; i < n; i++) {
618 int pixel = *contrib++;
619 weight += from[pixel] * (*contrib++);
620 }
621 to[x] = CLAMP(FIXED_TO_INT(weight), 0, 255);
622 }
623 }
624 from = zi->tmpimage;
625 from_stride = to_stride;
626 }
627
628 /* Apply filter to zoom vertically from tmp (or src) to dest */
629 /* Use Y as the outside loop to avoid cache thrashing on output buffer */
630 to = dest;
631 to_stride = zi->new_stride;
632 if (zi->y_contrib) {
633 int32_t *contrib = zi->y_contrib;
634 int y;
635 for (y = 0; y < zi->new_h; y++, to += to_stride) {
636 int n = *contrib++, x;
637 for (x = 0; x < zi->new_w * zi->Bpp; x++) {
638 int32_t weight = DOUBLE_TO_FIXED(0.5);
639 int i;
640 for (i = 0; i < n; i++) {
641 int pixel = contrib[i*2];
642 weight += from[x+pixel] * contrib[i*2+1];
643 }
644 to[x] = CLAMP(FIXED_TO_INT(weight), 0, 255);
645 }
646 contrib += 2*n;
647 }
648 } else {
649 /* No zooming necessary, just copy */
650 if (from_stride == zi->new_w*zi->Bpp
651 && to_stride == zi->new_w*zi->Bpp
652 ) {
653 /* We can copy the whole frame at once */
654 ac_memcpy(to, from, to_stride * zi->new_h);
655 } else {
656 /* Copy one row at a time */
657 int y;
658 for (y = 0; y < zi->new_h; y++) {
659 ac_memcpy(to + y*to_stride, from + y*from_stride,
660 zi->new_w * zi->Bpp);
661 }
662 }
663 }
664 }
665
666 /*************************************************************************/
667
668 /**
669 * zoom_free(): Free a ZoomInfo structure.
670 *
671 * Parameters:
672 * zi: ZoomInfo structure allocated by zoom_init().
673 * Return value:
674 * None.
675 * Preconditions:
676 * zi was allocated by zoom_init()
677 * Postconditions:
678 * zi is freed
679 */
zoom_free(ZoomInfo * zi)680 void zoom_free(ZoomInfo *zi)
681 {
682 free(zi->x_contrib);
683 free(zi->y_contrib);
684 free(zi->tmpimage);
685 free(zi);
686 }
687
688 /*************************************************************************/
689
690 /*
691 * Local variables:
692 * c-file-style: "stroustrup"
693 * c-file-offsets: ((case-label . *) (statement-case-intro . *))
694 * indent-tabs-mode: nil
695 * End:
696 *
697 * vim: expandtab shiftwidth=4:
698 */
699