Changeset 2664


Ignore:
Timestamp:
Aug 3, 2008, 8:36:26 PM (14 years ago)
Author:
Sam Hocevar
Message:
  • dbs.c: optimise DBS by ignoring 16x16 cells that had no pixel changes for the last two iterations.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • libpipi/trunk/pipi/dither/dbs.c

    r2663 r2664  
    2020#include "common.h"
    2121
     22#include <string.h>
     23#include <stdlib.h>
     24
    2225#include <math.h>
    2326
    2427#include "pipi.h"
    2528#include "pipi_internals.h"
     29
     30#define CELL 16
    2631
    2732#define N 7
     
    3742    pipi_image_t *dst, *tmp1, *tmp2;
    3843    pipi_pixels_t *srcp, *dstp, *tmp1p, *tmp2p;
     44    int *changelist;
    3945    float *srcdata, *dstdata, *tmp1data, *tmp2data;
    40     int i, j, w, h;
    41 
     46    int i, j, x, y, w, h, cw, ch;
     47
     48    /* Build our human visual system kernel. */
    4249    for(j = 0; j < NN; j++)
    4350        for(i = 0; i < NN; i++)
     
    4653            double b = (double)(j - N);
    4754            kernel[j * NN + i] =
    48                     1.0 * exp(-(a * a + b * b) / (2. * 1.5 * 1.5))
    49                   + 0.1 * exp(-(a * a + b * b) / (2. * 0.6 * 0.6));
     55                    exp(-(a * a + b * b) / (2. * 1.6 * 1.6))
     56                  + exp(-(a * a + b * b) / (2. * 0.6 * 0.6));
    5057            t += kernel[j * NN + i];
    5158        }
     
    5764    w = src->w;
    5865    h = src->h;
     66
     67    cw = (w + CELL - 1) / CELL;
     68    ch = (h + CELL - 1) / CELL;
     69    changelist = malloc(cw * ch * sizeof(int));
     70    memset(changelist, 0, cw * ch * sizeof(int));
    5971
    6072    srcp = pipi_getpixels(src, PIPI_PIXELS_Y_F);
     
    7284    dstdata = (float *)dstp->pixels;
    7385
     86    for(y = 0; y < h; y++)
     87        for(x = 0; x < w; x++)
     88            dstdata[y * w + x] = srcdata[y * w + x] > 0.5 ? 1.0 : 0.0;
     89
    7490    tmp2 = pipi_convolution(dst, NN, NN, kernel);
    7591    tmp2p = pipi_getpixels(tmp2, PIPI_PIXELS_Y_F);
     
    7894    for(;;)
    7995    {
    80         int changes = 0;
    81         int x, y, n;
    82 
    83         for(y = 0; y < h; y++)
    84         for(x = 0; x < w; x++)
     96        int cx, cy, n;
     97        int allchanges = 0;
     98
     99        for(cy = 0; cy < ch; cy++)
     100        for(cx = 0; cx < cw; cx++)
    85101        {
    86             double d, d2, e, best = 0.;
    87             int opx = -1, opy = -1;
    88 
    89             d = dstdata[y * w + x];
    90 
    91             /* Compute the effect of a toggle */
    92             e = 0.;
    93             for(j = -N; j < N + 1; j++)
     102            int changes = 0;
     103
     104            if(changelist[cy * cw + cx] >= 2)
     105                continue;
     106
     107            for(y = cy * CELL; y < (cy + 1) * CELL; y++)
     108            for(x = cx * CELL; x < (cx + 1) * CELL; x++)
    94109            {
    95                 if(y + j < 0 || y + j >= h)
    96                     continue;
    97 
    98                 for(i = -N; i < N + 1; i++)
    99                 {
    100                     double m, p, q1, q2;
    101 
    102                     if(x + i < 0 || x + i >= w)
    103                         continue;
    104 
    105                     m = kernel[(j + N) * NN + i + N];
    106                     p = tmp1data[(y + j) * w + x + i];
    107                     q1 = tmp2data[(y + j) * w + x + i];
    108                     q2 = q1 - m * d + m * (1. - d);
    109                     e += (q1 - p) * (q1 - p) - (q2 - p) * (q2 - p);
    110                 }
    111             }
    112             if(e > best)
    113             {
    114                 best = e;
    115                 opx = opy = 0;
    116             }
    117 
    118             /* Compute the effect of swaps */
    119             for(n = 0; n < 8; n++)
    120             {
    121                 static int const step[] =
    122                     { 0, 1, 0, -1, -1, 0, 1, 0, -1, -1, -1, 1, 1, -1, 1, 1 };
    123                 int idx = step[n * 2], idy = step[n * 2 + 1];
    124                 if(y + idy < 0 || y + idy >= h
    125                      || x + idx < 0 || x + idx >= w)
    126                     continue;
    127                 d2 = dstdata[(y + idy) * w + x + idx];
    128                 if(d2 == d)
    129                     continue;
     110                double d, d2, e, best = 0.;
     111                int opx = -1, opy = -1;
     112
     113                d = dstdata[y * w + x];
     114
     115                /* Compute the effect of a toggle */
    130116                e = 0.;
    131117                for(j = -N; j < N + 1; j++)
     
    133119                    if(y + j < 0 || y + j >= h)
    134120                        continue;
    135                     if(j - idy + N < 0 || j - idy + N >= NN)
    136                         continue;
     121
    137122                    for(i = -N; i < N + 1; i++)
    138123                    {
    139                         double ma, mb, p, q1, q2;
     124                        double m, p, q1, q2;
     125
    140126                        if(x + i < 0 || x + i >= w)
    141127                            continue;
    142                         if(i - idx + N < 0 || i - idx + N >= NN)
    143                             continue;
    144                         ma = kernel[(j + N) * NN + i + N];
    145                         mb = kernel[(j - idy + N) * NN + i - idx + N];
     128
     129                        m = kernel[(j + N) * NN + i + N];
    146130                        p = tmp1data[(y + j) * w + x + i];
    147131                        q1 = tmp2data[(y + j) * w + x + i];
    148                         q2 = q1 - ma * d + ma * d2 - mb * d2 + mb * d;
     132                        q2 = q1 - m * d + m * (1. - d);
    149133                        e += (q1 - p) * (q1 - p) - (q2 - p) * (q2 - p);
    150134                    }
     
    153137                {
    154138                    best = e;
    155                     opx = idx;
    156                     opy = idy;
    157                 }
     139                    opx = opy = 0;
     140                }
     141
     142                /* Compute the effect of swaps */
     143                for(n = 0; n < 8; n++)
     144                {
     145                    static int const step[] =
     146                      { 0, 1, 0, -1, -1, 0, 1, 0, -1, -1, -1, 1, 1, -1, 1, 1 };
     147                    int idx = step[n * 2], idy = step[n * 2 + 1];
     148                    if(y + idy < 0 || y + idy >= h
     149                         || x + idx < 0 || x + idx >= w)
     150                        continue;
     151                    d2 = dstdata[(y + idy) * w + x + idx];
     152                    if(d2 == d)
     153                        continue;
     154                    e = 0.;
     155                    for(j = -N; j < N + 1; j++)
     156                    {
     157                        if(y + j < 0 || y + j >= h)
     158                            continue;
     159                        if(j - idy + N < 0 || j - idy + N >= NN)
     160                            continue;
     161                        for(i = -N; i < N + 1; i++)
     162                        {
     163                            double ma, mb, p, q1, q2;
     164                            if(x + i < 0 || x + i >= w)
     165                                continue;
     166                            if(i - idx + N < 0 || i - idx + N >= NN)
     167                                continue;
     168                            ma = kernel[(j + N) * NN + i + N];
     169                            mb = kernel[(j - idy + N) * NN + i - idx + N];
     170                            p = tmp1data[(y + j) * w + x + i];
     171                            q1 = tmp2data[(y + j) * w + x + i];
     172                            q2 = q1 - ma * d + ma * d2 - mb * d2 + mb * d;
     173                            e += (q1 - p) * (q1 - p) - (q2 - p) * (q2 - p);
     174                        }
     175                    }
     176                    if(e > best)
     177                    {
     178                        best = e;
     179                        opx = idx;
     180                        opy = idy;
     181                    }
     182                }
     183
     184                /* Apply the change if interesting */
     185                if(best <= 0.)
     186                    continue;
     187                if(opx || opy)
     188                {
     189                    d2 = dstdata[(y + opy) * w + x + opx];
     190                    dstdata[(y + opy) * w + x + opx] = d;
     191                }
     192                else
     193                    d2 = 1. - d;
     194                dstdata[y * w + x] = d2;
     195                for(j = -N; j < N + 1; j++)
     196                for(i = -N; i < N + 1; i++)
     197                {
     198                    double m = kernel[(j + N) * NN + i + N];
     199                    if(y + j >= 0 && y + j < h
     200                        && x + i >= 0 && x + i < w)
     201                    {
     202                        t = tmp2data[(y + j) * w + x + i];
     203                        tmp2data[(y + j) * w + x + i] = t + m * (d2 - d);
     204                    }
     205                    if((opx || opy) && y + opy + j >= 0 && y + opy + j < h
     206                                    && x + opx + i >= 0 && x + opx + i < w)
     207                    {
     208                        t = tmp2data[(y + opy + j) * w + x + opx + i];
     209                        tmp2data[(y + opy + j) * w + x + opx + i]
     210                                = t + m * (d - d2);
     211                    }
     212                }
     213
     214                changes++;
    158215            }
    159216
    160             /* Apply the change if interesting */
    161             if(best <= 0.)
    162                 continue;
    163             if(opx || opy)
    164             {
    165                 d2 = dstdata[(y + opy) * w + x + opx];
    166                 dstdata[(y + opy) * w + x + opx] = d;
    167             }
    168             else
    169                 d2 = 1. - d;
    170             dstdata[y * w + x] = d2;
    171             for(j = -N; j < N + 1; j++)
    172             for(i = -N; i < N + 1; i++)
    173             {
    174                 double m = kernel[(j + N) * NN + i + N];
    175                 if(y + j >= 0 && y + j < h
    176                     && x + i >= 0 && x + i < w)
    177                 {
    178                     t = tmp2data[(y + j) * w + x + i];
    179                     tmp2data[(y + j) * w + x + i] = t + m * (d2 - d);
    180                 }
    181                 if((opx || opy) && y + opy + j >= 0 && y + opy + j < h
    182                                 && x + opx + i >= 0 && x + opx + i < w)
    183                 {
    184                     t = tmp2data[(y + opy + j) * w + x + opx + i];
    185                     tmp2data[(y + opy + j) * w + x + opx + i]
    186                             = t + m * (d - d2);
    187                 }
    188             }
    189 
    190             changes++;
     217            if(changes == 0)
     218                changelist[cy * cw + cx]++;
     219
     220            allchanges += changes;
    191221        }
    192222
    193         if(changes == 0)
     223        if(allchanges == 0)
    194224            break;
    195225    }
    196226
     227    free(changelist);
     228
    197229    pipi_free(tmp1);
    198230    pipi_free(tmp2);
Note: See TracChangeset for help on using the changeset viewer.