Changeset 3754


Ignore:
Timestamp:
Jan 2, 2015, 2:45:00 AM (7 years ago)
Author:
sam
Message:

image: improve the DBS dithering implementation by avoiding lots of tests.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/image/dither/dbs.cpp

    r3577 r3754  
    22// Lol Engine
    33//
    4 // Copyright: (c) 2004-2014 Sam Hocevar <sam@hocevar.net>
     4// Copyright: (c) 2004-2015 Sam Hocevar <sam@hocevar.net>
    55//   This program is free software; you can redistribute it and/or
    66//   modify it under the terms of the Do What The Fuck You Want To
     
    4848    /* A list of cells in our picture. If no change is done to a cell
    4949     * for two iterations, we stop considering changes to it. */
    50     ivec2 csize = (size + ivec2(CELL - 1)) / CELL;
    51     array2d<int> changelist;
    52     changelist.SetSize(csize);
     50    ivec2 const csize = (size + ivec2(CELL - 1)) / CELL;
     51    array2d<int> changelist(csize);
    5352    memset(changelist.Data(), 0, changelist.Bytes());
    5453
     
    5756
    5857    Image tmp1 = dst.Convolution(kernel);
    59     float *tmp1data = tmp1.Lock<PixelFormat::Y_F32>();
     58    array2d<float> &tmp1data = tmp1.Lock2D<PixelFormat::Y_F32>();
    6059
    6160    dst = dst.DitherRandom();
    62     float *dstdata = dst.Lock<PixelFormat::Y_F32>();
     61    array2d<float> &dstdata = dst.Lock2D<PixelFormat::Y_F32>();
    6362
    6463    Image tmp2 = dst.Convolution(kernel);
    65     float *tmp2data = tmp2.Lock<PixelFormat::Y_F32>();
     64    array2d<float> &tmp2data = tmp2.Lock2D<PixelFormat::Y_F32>();
    6665
    67     for (;;)
     66    for (int run = 0, last_change = 0; ; ++run)
    6867    {
    69         int allchanges = 0;
     68        int const cell = run % (csize.x * csize.y);
     69        int const cx = cell % csize.x;
     70        int const cy = cell / csize.x;
    7071
    71         for (int cy = 0; cy < csize.y; ++cy)
    72         for (int cx = 0; cx < csize.x; ++cx)
     72        /* Bail out if no change was done for the last full image run */
     73        if (run > last_change + csize.x * csize.y)
     74            break;
     75
     76        /* Skip cell if it was already ignored twice */
     77        if (changelist[cx][cy] >= 2)
     78            continue;
     79
     80        int changes = 0;
     81
     82        for (int pixel = 0; pixel < CELL * CELL; ++pixel)
    7383        {
    74             int changes = 0;
     84            ivec2 const pos(cx * CELL + pixel % CELL,
     85                            cy * CELL + pixel / CELL);
    7586
    76             if (changelist[cx][cy] >= 2)
     87            if (!(pos >= ivec2(0)) || !(pos < size))
    7788                continue;
    7889
    79             for (int y = cy * CELL; y < (cy + 1) * CELL; ++y)
    80             for (int x = cx * CELL; x < (cx + 1) * CELL; ++x)
     90            /* The best operation we can do */
     91            ivec2 best_op(0);
     92            float best_error = 0.f;
     93
     94            float d = dstdata[pos];
     95
     96            /* Compute the effect of all possible toggle and swaps */
     97            static ivec2 const op_list[] =
    8198            {
    82                 int opx = -1, opy = -1;
     99                { 0, 0 },
     100                { 0, 1 },   { 0, -1 }, { -1, 0 }, { 1, 0 },
     101                { -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 },
     102            };
    83103
    84                 float d = dstdata[y * size.x + x];
    85                 float d2;
     104            for (ivec2 const op : op_list)
     105            {
     106                if (!(pos + op >= ivec2(0)) || !(pos + op < size))
     107                    continue;
    86108
    87                 /* Compute the effect of a toggle */
    88                 float e = 0.f, best = 0.f;
    89                 for (int j = -N; j < N + 1; j++)
     109                bool flip = (op == ivec2(0));
     110
     111                float d2 = flip ? 1 - d : dstdata[pos + op];
     112
     113                if (!flip && d2 == d)
     114                    continue;
     115
     116                /* TODO: implement min/max for 3+ arguments */
     117                int imin = max(max(-N, op.x - N), -pos.x);
     118                int imax = min(min(N + 1, op.x + NN - N), size.x - pos.x);
     119                int jmin = max(max(-N, op.y - N), -pos.y);
     120                int jmax = min(min(N + 1, op.y + NN - N), size.y - pos.y);
     121
     122                float error = 0.f;
     123                for (int j = jmin; j < jmax; j++)
     124                for (int i = imin; i < imax; i++)
    90125                {
    91                     if (y + j < 0 || y + j >= size.y)
    92                         continue;
     126                    ivec2 pos2 = pos + ivec2(i, j);
    93127
    94                     for (int i = -N; i < N + 1; i++)
    95                     {
    96                         if (x + i < 0 || x + i >= size.x)
    97                             continue;
    98 
    99                         float m = kernel[i + N][j + N];
    100                         float p = tmp1data[(y + j) * size.x + x + i];
    101                         float q1 = tmp2data[(y + j) * size.x + x + i];
    102                         float q2 = q1 - m * d + m * (1. - d);
    103                         e += (q1 - p) * (q1 - p) - (q2 - p) * (q2 - p);
    104                     }
     128                    float m = kernel[i + N][j + N];
     129                    if (!flip)
     130                        m -= kernel[i - op.x + N][j - op.y + N];
     131                    float p = tmp1data[pos2];
     132                    float q1 = tmp2data[pos2];
     133                    float q2 = q1 + m * (d2 - d);
     134                    error += sq(q1 - p) - sq(q2 - p);
    105135                }
    106136
    107                 if (e > best)
     137                if (error > best_error)
    108138                {
    109                     best = e;
    110                     opx = opy = 0;
     139                    best_error = error;
     140                    best_op = op;
     141                }
     142            }
     143
     144            /* Only apply the change if interesting */
     145            if (best_error > 0.f)
     146            {
     147                bool flip = (best_op == ivec2(0));
     148
     149                float d2 = flip ? 1 - d : dstdata[pos + best_op];
     150                dstdata[pos + best_op] = d;
     151                dstdata[pos] = d2;
     152
     153                for (int j = -N; j <= N; j++)
     154                for (int i = -N; i <= N; i++)
     155                {
     156                    ivec2 off(i, j);
     157                    float delta = (d2 - d) * kernel[i + N][j + N];
     158
     159                    if (pos + off >= ivec2(0) && pos + off < size)
     160                        tmp2data[pos + off] += delta;
     161
     162                    if (!flip && pos + off + best_op >= ivec2(0)
     163                         && pos + off + best_op < size)
     164                        tmp2data[pos + off + best_op] -= delta;
    111165                }
    112166
    113                 /* Compute the effect of swaps */
    114                 for (int n = 0; n < 8; n++)
    115                 {
    116                     static int const step[] =
    117                       { 0, 1, 0, -1, -1, 0, 1, 0, -1, -1, -1, 1, 1, -1, 1, 1 };
    118                     int idx = step[n * 2], idy = step[n * 2 + 1];
    119                     if (y + idy < 0 || y + idy >= size.y
    120                          || x + idx < 0 || x + idx >= size.x)
    121                         continue;
    122                     d2 = dstdata[(y + idy) * size.x + x + idx];
    123                     if (d2 == d)
    124                         continue;
    125                     e = 0.;
    126                     for (int j = -N; j < N + 1; j++)
    127                     {
    128                         if (y + j < 0 || y + j >= size.y)
    129                             continue;
    130                         if (j - idy + N < 0 || j - idy + N >= NN)
    131                             continue;
    132                         for (int i = -N; i < N + 1; i++)
    133                         {
    134                             if (x + i < 0 || x + i >= size.x)
    135                                 continue;
    136                             if (i - idx + N < 0 || i - idx + N >= NN)
    137                                 continue;
    138                             float ma = kernel[i + N][j + N];
    139                             float mb = kernel[i - idx + N][j - idy + N];
    140                             float p = tmp1data[(y + j) * size.x + x + i];
    141                             float q1 = tmp2data[(y + j) * size.x + x + i];
    142                             float q2 = q1 - ma * d + ma * d2 - mb * d2 + mb * d;
    143                             e += (q1 - p) * (q1 - p) - (q2 - p) * (q2 - p);
    144                         }
    145                     }
    146 
    147                     if (e > best)
    148                     {
    149                         best = e;
    150                         opx = idx;
    151                         opy = idy;
    152                     }
    153                 }
    154 
    155                 /* Apply the change if interesting */
    156                 if (best <= 0.f)
    157                     continue;
    158 
    159                 if (opx || opy)
    160                 {
    161                     d2 = dstdata[(y + opy) * size.x + x + opx];
    162                     dstdata[(y + opy) * size.x + x + opx] = d;
    163                 }
    164                 else
    165                     d2 = 1. - d;
    166                 dstdata[y * size.x + x] = d2;
    167 
    168                 for (int j = -N; j < N + 1; j++)
    169                 for (int i = -N; i < N + 1; i++)
    170                 {
    171                     float m = kernel[i + N][j + N];
    172                     if (y + j >= 0 && y + j < size.y
    173                          && x + i >= 0 && x + i < size.x)
    174                     {
    175                         t = tmp2data[(y + j) * size.x + x + i];
    176                         tmp2data[(y + j) * size.x + x + i] = t + m * (d2 - d);
    177                     }
    178                     if ((opx || opy) && y + opy + j >= 0 && y + opy + j < size.y
    179                                     && x + opx + i >= 0 && x + opx + i < size.x)
    180                     {
    181                         t = tmp2data[(y + opy + j) * size.x + x + opx + i];
    182                         tmp2data[(y + opy + j) * size.x + x + opx + i]
    183                                 = t + m * (d - d2);
    184                     }
    185                 }
    186 
    187                 changes++;
     167                ++changes;
     168                last_change = run;
    188169            }
    189 
    190             if (changes == 0)
    191                 ++changelist[cx][cy];
    192 
    193             allchanges += changes;
    194170        }
    195171
    196         if (allchanges == 0)
    197             break;
     172        if (changes == 0)
     173            ++changelist[cx][cy];
    198174    }
    199175
    200     tmp1.Unlock(tmp1data);
    201     tmp2.Unlock(tmp2data);
    202     dst.Unlock(dstdata);
     176    tmp1.Unlock2D(tmp1data);
     177    tmp2.Unlock2D(tmp2data);
     178    dst.Unlock2D(dstdata);
    203179
    204180    return dst;
Note: See TracChangeset for help on using the changeset viewer.