LCOV - code coverage report
Current view: top level - libavcodec - elbg.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 218 226 96.5 %
Date: 2017-12-11 20:48:03 Functions: 14 14 100.0 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (C) 2007 Vitor Sessak <vitor1001@gmail.com>
       3             :  *
       4             :  * This file is part of FFmpeg.
       5             :  *
       6             :  * FFmpeg is free software; you can redistribute it and/or
       7             :  * modify it under the terms of the GNU Lesser General Public
       8             :  * License as published by the Free Software Foundation; either
       9             :  * version 2.1 of the License, or (at your option) any later version.
      10             :  *
      11             :  * FFmpeg is distributed in the hope that it will be useful,
      12             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      14             :  * Lesser General Public License for more details.
      15             :  *
      16             :  * You should have received a copy of the GNU Lesser General Public
      17             :  * License along with FFmpeg; if not, write to the Free Software
      18             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      19             :  */
      20             : 
      21             : /**
      22             :  * @file
      23             :  * Codebook Generator using the ELBG algorithm
      24             :  */
      25             : 
      26             : #include <string.h>
      27             : 
      28             : #include "libavutil/avassert.h"
      29             : #include "libavutil/common.h"
      30             : #include "libavutil/lfg.h"
      31             : #include "elbg.h"
      32             : #include "avcodec.h"
      33             : 
      34             : #define DELTA_ERR_MAX 0.1  ///< Precision of the ELBG algorithm (as percentage error)
      35             : 
      36             : /**
      37             :  * In the ELBG jargon, a cell is the set of points that are closest to a
      38             :  * codebook entry. Not to be confused with a RoQ Video cell. */
      39             : typedef struct cell_s {
      40             :     int index;
      41             :     struct cell_s *next;
      42             : } cell;
      43             : 
      44             : /**
      45             :  * ELBG internal data
      46             :  */
      47             : typedef struct elbg_data {
      48             :     int error;
      49             :     int dim;
      50             :     int numCB;
      51             :     int *codebook;
      52             :     cell **cells;
      53             :     int *utility;
      54             :     int64_t *utility_inc;
      55             :     int *nearest_cb;
      56             :     int *points;
      57             :     AVLFG *rand_state;
      58             :     int *scratchbuf;
      59             : } elbg_data;
      60             : 
      61  2512940434 : static inline int distance_limited(int *a, int *b, int dim, int limit)
      62             : {
      63  2512940434 :     int i, dist=0;
      64  5371859070 :     for (i=0; i<dim; i++) {
      65  5028816911 :         dist += (a[i] - b[i])*(a[i] - b[i]);
      66  5028816911 :         if (dist > limit)
      67  2169898275 :             return INT_MAX;
      68             :     }
      69             : 
      70   343042159 :     return dist;
      71             : }
      72             : 
      73    17887608 : static inline void vect_division(int *res, int *vect, int div, int dim)
      74             : {
      75             :     int i;
      76    17887608 :     if (div > 1)
      77    69873730 :         for (i=0; i<dim; i++)
      78    56803470 :             res[i] = ROUNDED_DIV(vect[i],div);
      79     4817348 :     else if (res != vect)
      80      749779 :         memcpy(res, vect, dim*sizeof(int));
      81             : 
      82    17887608 : }
      83             : 
      84     2955954 : static int eval_error_cell(elbg_data *elbg, int *centroid, cell *cells)
      85             : {
      86     2955954 :     int error=0;
      87    28530259 :     for (; cells; cells=cells->next)
      88    25574305 :         error += distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX);
      89             : 
      90     2955954 :     return error;
      91             : }
      92             : 
      93     5909519 : static int get_closest_codebook(elbg_data *elbg, int index)
      94             : {
      95     5909519 :     int i, pick=0, diff, diff_min = INT_MAX;
      96   238648065 :     for (i=0; i<elbg->numCB; i++)
      97   232738546 :         if (i != index) {
      98   226829027 :             diff = distance_limited(elbg->codebook + i*elbg->dim, elbg->codebook + index*elbg->dim, elbg->dim, diff_min);
      99   226829027 :             if (diff < diff_min) {
     100    12118877 :                 pick = i;
     101    12118877 :                 diff_min = diff;
     102             :             }
     103             :         }
     104     5909519 :     return pick;
     105             : }
     106             : 
     107     5909519 : static int get_high_utility_cell(elbg_data *elbg)
     108             : {
     109     5909519 :     int i=0;
     110             :     /* Using linear search, do binary if it ever turns to be speed critical */
     111             :     uint64_t r;
     112             : 
     113     5909519 :     if (elbg->utility_inc[elbg->numCB-1] < INT_MAX) {
     114     5909519 :         r = av_lfg_get(elbg->rand_state) % (unsigned int)elbg->utility_inc[elbg->numCB-1] + 1;
     115             :     } else {
     116           0 :         r = av_lfg_get(elbg->rand_state);
     117           0 :         r = (av_lfg_get(elbg->rand_state) + (r<<32)) % elbg->utility_inc[elbg->numCB-1] + 1;
     118             :     }
     119             : 
     120   123909515 :     while (elbg->utility_inc[i] < r) {
     121   112090477 :         i++;
     122             :     }
     123             : 
     124             :     av_assert2(elbg->cells[i]);
     125             : 
     126     5909519 :     return i;
     127             : }
     128             : 
     129             : /**
     130             :  * Implementation of the simple LBG algorithm for just two codebooks
     131             :  */
     132     1477977 : static int simple_lbg(elbg_data *elbg,
     133             :                       int dim,
     134             :                       int *centroid[3],
     135             :                       int newutility[3],
     136             :                       int *points,
     137             :                       cell *cells)
     138             : {
     139             :     int i, idx;
     140     1477977 :     int numpoints[2] = {0,0};
     141     2955954 :     int *newcentroid[2] = {
     142     1477977 :         elbg->scratchbuf + 3*dim,
     143     1477977 :         elbg->scratchbuf + 4*dim
     144             :     };
     145             :     cell *tempcell;
     146             : 
     147     1477977 :     memset(newcentroid[0], 0, 2 * dim * sizeof(*newcentroid[0]));
     148             : 
     149     1477977 :     newutility[0] =
     150     1477977 :     newutility[1] = 0;
     151             : 
     152    21666058 :     for (tempcell = cells; tempcell; tempcell=tempcell->next) {
     153    40376162 :         idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>=
     154    20188081 :               distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX);
     155    20188081 :         numpoints[idx]++;
     156   144432511 :         for (i=0; i<dim; i++)
     157   124244430 :             newcentroid[idx][i] += points[tempcell->index*dim + i];
     158             :     }
     159             : 
     160     1477977 :     vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
     161     1477977 :     vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
     162             : 
     163    21666058 :     for (tempcell = cells; tempcell; tempcell=tempcell->next) {
     164    40376162 :         int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX),
     165    20188081 :                        distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)};
     166    20188081 :         int idx = dist[0] > dist[1];
     167    20188081 :         newutility[idx] += dist[idx];
     168             :     }
     169             : 
     170     1477977 :     return newutility[0] + newutility[1];
     171             : }
     172             : 
     173     1477977 : static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i,
     174             :                               int *newcentroid_p)
     175             : {
     176             :     cell *tempcell;
     177     1477977 :     int *min = newcentroid_i;
     178     1477977 :     int *max = newcentroid_p;
     179             :     int i;
     180             : 
     181    10535721 :     for (i=0; i< elbg->dim; i++) {
     182     9057744 :         min[i]=INT_MAX;
     183     9057744 :         max[i]=0;
     184             :     }
     185             : 
     186    21666058 :     for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next)
     187   144432511 :         for(i=0; i<elbg->dim; i++) {
     188   124244430 :             min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]);
     189   124244430 :             max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]);
     190             :         }
     191             : 
     192    10535721 :     for (i=0; i<elbg->dim; i++) {
     193     9057744 :         int ni = min[i] + (max[i] - min[i])/3;
     194     9057744 :         int np = min[i] + (2*(max[i] - min[i]))/3;
     195     9057744 :         newcentroid_i[i] = ni;
     196     9057744 :         newcentroid_p[i] = np;
     197             :     }
     198     1477977 : }
     199             : 
     200             : /**
     201             :  * Add the points in the low utility cell to its closest cell. Split the high
     202             :  * utility cell, putting the separated points in the (now empty) low utility
     203             :  * cell.
     204             :  *
     205             :  * @param elbg         Internal elbg data
     206             :  * @param indexes      {luc, huc, cluc}
     207             :  * @param newcentroid  A vector with the position of the new centroids
     208             :  */
     209      759468 : static void shift_codebook(elbg_data *elbg, int *indexes,
     210             :                            int *newcentroid[3])
     211             : {
     212             :     cell *tempdata;
     213      759468 :     cell **pp = &elbg->cells[indexes[2]];
     214             : 
     215     7562929 :     while(*pp)
     216     6043993 :         pp= &(*pp)->next;
     217             : 
     218      759468 :     *pp = elbg->cells[indexes[0]];
     219             : 
     220      759468 :     elbg->cells[indexes[0]] = NULL;
     221      759468 :     tempdata = elbg->cells[indexes[1]];
     222      759468 :     elbg->cells[indexes[1]] = NULL;
     223             : 
     224    10123260 :     while(tempdata) {
     225     8604324 :         cell *tempcell2 = tempdata->next;
     226    17208648 :         int idx = distance_limited(elbg->points + tempdata->index*elbg->dim,
     227     8604324 :                            newcentroid[0], elbg->dim, INT_MAX) >
     228    17208648 :                   distance_limited(elbg->points + tempdata->index*elbg->dim,
     229     8604324 :                            newcentroid[1], elbg->dim, INT_MAX);
     230             : 
     231     8604324 :         tempdata->next = elbg->cells[indexes[idx]];
     232     8604324 :         elbg->cells[indexes[idx]] = tempdata;
     233     8604324 :         tempdata = tempcell2;
     234             :     }
     235      759468 : }
     236             : 
     237     6589862 : static void evaluate_utility_inc(elbg_data *elbg)
     238             : {
     239             :     int i;
     240     6589862 :     int64_t inc=0;
     241             : 
     242   138541051 :     for (i=0; i < elbg->numCB; i++) {
     243   131951189 :         if (elbg->numCB*elbg->utility[i] > elbg->error)
     244    45667224 :             inc += elbg->utility[i];
     245   131951189 :         elbg->utility_inc[i] = inc;
     246             :     }
     247     6589862 : }
     248             : 
     249             : 
     250     2278404 : static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
     251             : {
     252             :     cell *tempcell;
     253             : 
     254     2278404 :     elbg->utility[idx] = newutility;
     255    21120685 :     for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next)
     256    18842281 :         elbg->nearest_cb[tempcell->index] = idx;
     257     2278404 : }
     258             : 
     259             : /**
     260             :  * Evaluate if a shift lower the error. If it does, call shift_codebooks
     261             :  * and update elbg->error, elbg->utility and elbg->nearest_cb.
     262             :  *
     263             :  * @param elbg  Internal elbg data
     264             :  * @param idx   {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
     265             :  */
     266     1477977 : static void try_shift_candidate(elbg_data *elbg, int idx[3])
     267             : {
     268     1477977 :     int j, k, olderror=0, newerror, cont=0;
     269             :     int newutility[3];
     270     4433931 :     int *newcentroid[3] = {
     271     1477977 :         elbg->scratchbuf,
     272     1477977 :         elbg->scratchbuf + elbg->dim,
     273     1477977 :         elbg->scratchbuf + 2*elbg->dim
     274             :     };
     275             :     cell *tempcell;
     276             : 
     277     5911908 :     for (j=0; j<3; j++)
     278     4433931 :         olderror += elbg->utility[idx[j]];
     279             : 
     280     1477977 :     memset(newcentroid[2], 0, elbg->dim*sizeof(int));
     281             : 
     282     4433931 :     for (k=0; k<2; k++)
     283    28530259 :         for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) {
     284    25574305 :             cont++;
     285   186440797 :             for (j=0; j<elbg->dim; j++)
     286   160866492 :                 newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j];
     287             :         }
     288             : 
     289     1477977 :     vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim);
     290             : 
     291     1477977 :     get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]);
     292             : 
     293     1477977 :     newutility[2]  = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]);
     294     1477977 :     newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]);
     295             : 
     296     1477977 :     newerror = newutility[2];
     297             : 
     298     1477977 :     newerror += simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points,
     299     1477977 :                            elbg->cells[idx[1]]);
     300             : 
     301     1477977 :     if (olderror > newerror) {
     302      759468 :         shift_codebook(elbg, idx, newcentroid);
     303             : 
     304      759468 :         elbg->error += newerror - olderror;
     305             : 
     306     3037872 :         for (j=0; j<3; j++)
     307     2278404 :             update_utility_and_n_cb(elbg, idx[j], newutility[j]);
     308             : 
     309      759468 :         evaluate_utility_inc(elbg);
     310             :     }
     311     1477977 :  }
     312             : 
     313             : /**
     314             :  * Implementation of the ELBG block
     315             :  */
     316     5830394 : static void do_shiftings(elbg_data *elbg)
     317             : {
     318             :     int idx[3];
     319             : 
     320     5830394 :     evaluate_utility_inc(elbg);
     321             : 
     322    19284071 :     for (idx[0]=0; idx[0] < elbg->numCB; idx[0]++)
     323    13453677 :         if (elbg->numCB*elbg->utility[idx[0]] < elbg->error) {
     324     5909519 :             if (elbg->utility_inc[elbg->numCB-1] == 0)
     325           0 :                 return;
     326             : 
     327     5909519 :             idx[1] = get_high_utility_cell(elbg);
     328     5909519 :             idx[2] = get_closest_codebook(elbg, idx[0]);
     329             : 
     330     5909519 :             if (idx[1] != idx[0] && idx[1] != idx[2])
     331     1477977 :                 try_shift_candidate(elbg, idx);
     332             :         }
     333             : }
     334             : 
     335             : #define BIG_PRIME 433494437LL
     336             : 
     337     5792078 : int avpriv_init_elbg(int *points, int dim, int numpoints, int *codebook,
     338             :                  int numCB, int max_steps, int *closest_cb,
     339             :                  AVLFG *rand_state)
     340             : {
     341     5792078 :     int i, k, ret = 0;
     342             : 
     343     5792078 :     if (numpoints > 24*numCB) {
     344             :         /* ELBG is very costly for a big number of points. So if we have a lot
     345             :            of them, get a good initial codebook to save on iterations       */
     346       31211 :         int *temp_points = av_malloc_array(dim, (numpoints/8)*sizeof(int));
     347       31211 :         if (!temp_points)
     348           0 :             return AVERROR(ENOMEM);
     349     1989867 :         for (i=0; i<numpoints/8; i++) {
     350     1958656 :             k = (i*BIG_PRIME) % numpoints;
     351     1958656 :             memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int));
     352             :         }
     353             : 
     354       31211 :         ret = avpriv_init_elbg(temp_points, dim, numpoints / 8, codebook,
     355             :                                numCB, 2 * max_steps, closest_cb, rand_state);
     356       31211 :         if (ret < 0) {
     357           0 :             av_freep(&temp_points);
     358           0 :             return ret;
     359             :         }
     360       31211 :         ret = avpriv_do_elbg(temp_points, dim, numpoints / 8, codebook,
     361             :                              numCB, 2 * max_steps, closest_cb, rand_state);
     362       31211 :         av_free(temp_points);
     363             : 
     364             :     } else  // If not, initialize the codebook with random positions
     365    18857953 :         for (i=0; i < numCB; i++)
     366    13097086 :             memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim,
     367             :                    dim*sizeof(int));
     368     5792078 :     return ret;
     369             : }
     370             : 
     371     5792078 : int avpriv_do_elbg(int *points, int dim, int numpoints, int *codebook,
     372             :                 int numCB, int max_steps, int *closest_cb,
     373             :                 AVLFG *rand_state)
     374             : {
     375             :     int dist;
     376             :     elbg_data elbg_d;
     377     5792078 :     elbg_data *elbg = &elbg_d;
     378     5792078 :     int i, j, k, last_error, steps = 0, ret = 0;
     379     5792078 :     int *dist_cb = av_malloc_array(numpoints, sizeof(int));
     380     5792078 :     int *size_part = av_malloc_array(numCB, sizeof(int));
     381     5792078 :     cell *list_buffer = av_malloc_array(numpoints, sizeof(cell));
     382             :     cell *free_cells;
     383     5792078 :     int best_dist, best_idx = 0;
     384             : 
     385     5792078 :     elbg->error = INT_MAX;
     386     5792078 :     elbg->dim = dim;
     387     5792078 :     elbg->numCB = numCB;
     388     5792078 :     elbg->codebook = codebook;
     389     5792078 :     elbg->cells = av_malloc_array(numCB, sizeof(cell *));
     390     5792078 :     elbg->utility = av_malloc_array(numCB, sizeof(int));
     391     5792078 :     elbg->nearest_cb = closest_cb;
     392     5792078 :     elbg->points = points;
     393     5792078 :     elbg->utility_inc = av_malloc_array(numCB, sizeof(*elbg->utility_inc));
     394     5792078 :     elbg->scratchbuf = av_malloc_array(5*dim, sizeof(int));
     395             : 
     396    11584156 :     if (!dist_cb || !size_part || !list_buffer || !elbg->cells ||
     397    11584156 :         !elbg->utility || !elbg->utility_inc || !elbg->scratchbuf) {
     398           0 :         ret = AVERROR(ENOMEM);
     399           0 :         goto out;
     400             :     }
     401             : 
     402     5792078 :     elbg->rand_state = rand_state;
     403             : 
     404             :     do {
     405     5830394 :         free_cells = list_buffer;
     406     5830394 :         last_error = elbg->error;
     407     5830394 :         steps++;
     408     5830394 :         memset(elbg->utility, 0, numCB*sizeof(int));
     409     5830394 :         memset(elbg->cells, 0, numCB*sizeof(cell *));
     410             : 
     411     5830394 :         elbg->error = 0;
     412             : 
     413             :         /* This loop evaluate the actual Voronoi partition. It is the most
     414             :            costly part of the algorithm. */
     415    83063239 :         for (i=0; i < numpoints; i++) {
     416    77232845 :             best_dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + best_idx*elbg->dim, dim, INT_MAX);
     417  2162576130 :             for (k=0; k < elbg->numCB; k++) {
     418  2085343285 :                 dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, best_dist);
     419  2085343285 :                 if (dist < best_dist) {
     420    66209922 :                     best_dist = dist;
     421    66209922 :                     best_idx = k;
     422             :                 }
     423             :             }
     424    77232845 :             elbg->nearest_cb[i] = best_idx;
     425    77232845 :             dist_cb[i] = best_dist;
     426    77232845 :             elbg->error += dist_cb[i];
     427    77232845 :             elbg->utility[elbg->nearest_cb[i]] += dist_cb[i];
     428    77232845 :             free_cells->index = i;
     429    77232845 :             free_cells->next = elbg->cells[elbg->nearest_cb[i]];
     430    77232845 :             elbg->cells[elbg->nearest_cb[i]] = free_cells;
     431    77232845 :             free_cells++;
     432             :         }
     433             : 
     434     5830394 :         do_shiftings(elbg);
     435             : 
     436     5830394 :         memset(size_part, 0, numCB*sizeof(int));
     437             : 
     438     5830394 :         memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int));
     439             : 
     440    83063239 :         for (i=0; i < numpoints; i++) {
     441    77232845 :             size_part[elbg->nearest_cb[i]]++;
     442   408122555 :             for (j=0; j < elbg->dim; j++)
     443   661779420 :                 elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] +=
     444   330889710 :                     elbg->points[i*elbg->dim + j];
     445             :         }
     446             : 
     447    19284071 :         for (i=0; i < elbg->numCB; i++)
     448    40361031 :             vect_division(elbg->codebook + i*elbg->dim,
     449    26907354 :                           elbg->codebook + i*elbg->dim, size_part[i], elbg->dim);
     450             : 
     451    11647999 :     } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
     452     5830394 :             (steps < max_steps));
     453             : 
     454     5792078 : out:
     455     5792078 :     av_free(dist_cb);
     456     5792078 :     av_free(size_part);
     457     5792078 :     av_free(elbg->utility);
     458     5792078 :     av_free(list_buffer);
     459     5792078 :     av_free(elbg->cells);
     460     5792078 :     av_free(elbg->utility_inc);
     461     5792078 :     av_free(elbg->scratchbuf);
     462     5792078 :     return ret;
     463             : }

Generated by: LCOV version 1.13