Подскажите реализацию алгоритма растягивания и сжатия изображений в памяти на С/С++.
Скорость работы важнее точности и качества. Желательно (хотя и не обязательно) все в целочисленных вычислениях. Чем проще тем лучше, в алгоритм придется встраиваться и делать там нестандартные вещи — поэтому простота кода и отсутствие зависимостей также является важным критерием.

Здравствуйте, a9000, Вы писали:

A>Подскажите реализацию алгоритма растягивания и сжатия изображений в памяти на С/С++.

lycon?

Здравствуйте, a9000, Вы писали:

A>Подскажите реализацию алгоритма растягивания и сжатия изображений в памяти на С/С++.
A>Скорость работы важнее точности и качества. Желательно (хотя и не обязательно) все в целочисленных вычислениях. Чем проще тем лучше, в алгоритм придется встраиваться и делать там нестандартные вещи — поэтому простота кода и отсутствие зависимостей также является важным критерием.

IPP?

Здравствуйте, a9000, Вы писали:

A>Подскажите реализацию алгоритма растягивания и сжатия изображений в памяти на С/С++.
A>Скорость работы важнее точности и качества. Желательно (хотя и не обязательно) все в целочисленных вычислениях. Чем проще тем лучше, в алгоритм придется встраиваться и делать там нестандартные вещи — поэтому простота кода и отсутствие зависимостей также является важным критерием.

Псевдо код примерно такой

typedef int int32;
typedef long long int64;
typedef int32 fixed;

fixed fixed_muldiv(int32 a,int32 b,int32 c) { return (fixed)((int64)a*b/c); }

struct stretch_blit1_t {
    int x1,y1,x2,y2; // dst rect
    fixed sx1,sy1,dsx,dsy; // src left,top point and steps
    int32 color; // default color
};

struct bitmap_t {
    int32 *data; // 32bit color pixels
    int w,h; // width and height in pixels
    int bpl; // byte per line (may be negative)
};

void stretch_blit1(bitmap_t *dst,bitmap_t *src,stretch_blit1_t *bs) {
    fixed sy=bs->sy1; int32 color=bs->color;
    for(int y=bs->y1;y<bs->y2;y++) {
        int32 *d=(int32*)((char*)dst->data+dst->bpl*y);
        fixed sx=bs->sx1;
        int isy=sy>>16;
        if ((unsigned)isy>=(unsigned)src->h) {
            for(int x=bs->x1;x<bs->x2;x++) d[x]=color;
        } else {
            int32 *s=(int32*)((char*)src->data+src->bpl*isy);
            for(int x=bs->x1;x<bs->x2;x++) {
                int isx=sx>>16;
                d[x]=((unsigned)isx>=(unsigned)src->w) ? color : s[isx];
                sx+=bs->dsx;
            }
        }
        sy+=bs->dsy;
    }
}

void stretch_blit(bitmap_t *dst,int x1,int y1,int x2,int y2,bitmap_t *src,int sx1,int sy1,int sx2,int sy2,int color=0) {
    stretch_blit1_t bs[1];
    bs->color=color;
    if (y2>dst->h) y2=dst->h; if (y1>=y2) return;
    if (x2>dst->w) x2=dst->h; if (x1>=x2) return;
    bs->sx1=sx1*65536+32768;
    bs->sy1=sy1*65536+32768;
    bs->dsx=fixed_muldiv(sx2-sx1,65536,x2-x1);
    bs->dsy=fixed_muldiv(sy2-sy1,65536,y2-y1);
    if (x1<0) { bs->sx1-=bs->dsx*x1; x1=0; if (x1>=x2) return; }
    if (y1<0) { bs->sy1-=bs->dsy*y1; y1=0; if (y1>=y2) return; }
    bs->x1=x1; bs->y1=y1; bs->x2=x2; bs->y2=y2;
    stretch_blit1(dst,src,bs);
}

Здравствуйте, a9000, Вы писали:

A>Подскажите реализацию алгоритма растягивания и сжатия изображений в памяти на С/С++.

Можно например так:

typedef struct {
    int *colors;
    int stride, width, height;
} RasBuf;

void Resize (RasBuf dst, RasBuf src)
{
    int len;
    int cx, cy;
    int bx, dx, dbx;
    int by, dy, dby;
    if (
        (dst.width > 0) && (dst.height > 0) &&
        (src.width > 0) && (src.height > 0)
    ) {
        cx = dst.width;
        cy = dst.height;
        dx =             src.width /cx ; dbx = src.width %cx;
        dy = src.stride*(src.height/cy); dby = src.height%cy;
        for (by = 0; dst.height > 0; dst.height--) {
            for (bx = 0, len = dst.width; len > 0; len--) {
                *dst.colors = *src.colors;
                src.colors += dx; bx += dbx; if (bx >= cx) {src.colors++; bx -= cx;}
                dst.colors++;
            }
            src.colors += dy - src.width;
            by += dby; if (by >= cy) {src.colors += src.stride; by -= cy;}
            dst.colors += dst.stride - dst.width;
        }
    }
}

Только целочисленные операции, умножение и деление в цикле не используется. Основная идея в использовании дробей с общим знаменателем.
stride означает сколько нужно прибавить к указателю colors, чтобы перейти с следующей строке, для обычного двухмерного массива равен width. Цвета 32-х битные.

Здравствуйте, kov_serg, Вы писали:

_>Псевдо код примерно такой

По поводу fixed point на x86 — рекомендую ещё почитать про inner loop аффинного текстурирования, предельно разжёвано в доке fatmap.txt от финского программиста Mats Byggmastar (MRI) более 20 лет назад.

Для 8 и 16 битных систем может быть выгоднее использовать не fixed point а Брезенхема. Тогда делаем 2 цикла: один на растяжение (дублирование пикселя) другой на сжатие (пропуск пикселей). И идём по текстуре используя накопление и перенос.

Здравствуйте, IID, Вы писали:

IID>Здравствуйте, kov_serg, Вы писали:

_>>Псевдо код примерно такой

IID>По поводу fixed point на x86 — рекомендую ещё почитать про inner loop аффинного текстурирования, предельно разжёвано в доке fatmap.txt от финского программиста Mats Byggmastar (MRI) более 20 лет назад.
Это все прочитано еще во времена doom-а

IID>Для 8 и 16 битных систем может быть выгоднее использовать не fixed point а Брезенхема. Тогда делаем 2 цикла: один на растяжение (дублирование пикселя) другой на сжатие (пропуск пикселей). И идём по текстуре используя накопление и перенос.
Сейчас на float point быстрее работает чем таким способом. Более того для дальнейшей обработки неплохо надо знать координаты и размеры области которрая проектируется в результирующий пиксел.

Здравствуйте, kov_serg, Вы писали:

IID>>По поводу fixed point на x86 — рекомендую ещё почитать про inner loop аффинного текстурирования, предельно разжёвано в доке fatmap.txt от финского программиста Mats Byggmastar (MRI) более 20 лет назад.
_>Это все прочитано еще во времена doom-а

ТС-ом точно не был прочитан

Кстати, во времена дума дока ещё не вышла
Это были времена Quake/Quake2/Unreal, и самый разгар Soft-Render 3D в демомейкинге, до начала шествия хардварной акселерации.

IID>>Для 8 и 16 битных систем может быть выгоднее использовать не fixed point а Брезенхема. Тогда делаем 2 цикла: один на растяжение (дублирование пикселя) другой на сжатие (пропуск пикселей). И идём по текстуре используя накопление и перенос.
_>Сейчас

Дык я специально про старые системы оговорился. В них переходы были бесплатными или почти бесплатными, деления/умножения зачастую не было вовсе (или были дорогими), плюс затраты на арифметику нескольких регистров вместо одного.

_>на float point быстрее работает чем таким способом.

На CPU ?
А можно иннер-луп на плавучке посмотреть ?

Здравствуйте, a9000, Вы писали:

A>Подскажите реализацию алгоритма растягивания и сжатия изображений в памяти на С/С++.
A>Скорость работы важнее точности и качества. Желательно (хотя и не обязательно) все в целочисленных вычислениях. Чем проще тем лучше, в алгоритм придется встраиваться и делать там нестандартные вещи — поэтому простота кода и отсутствие зависимостей также является важным критерием.

https://blog.uploadcare.com/the-fastest-production-ready-image-resize-out-there-part-0-7c974d520ad9

Автор утверждает, что его реализация быстрее IPP.