Disclaimer: статья эта написана по просьбе почтеннейшей публики. Сам я не хотел выкладывать результаты, которые недостаточно «отполированы» для передачи их широкому кругу, и вот почему.
Неверная технология может увлечь людей по неверному пути, принеся вред, превышающий её пользу. Если пользоваться аналогиями, то это поданное нищему яблочко, оказавшееся ядовитым и убившее его. Бесплатность никогда не бывает оправданием для плохого софта, в конце концов, то яблоко тоже было бесплатным. «Ядовитые решения» не только бьют по пользователю, но и обесценивают труд остальных людей, вкладывавших его в тот же проект (зачастую они работают на энтузиазме, а их награда — востребованность решения; более распространённый случай, когда человек выкладывает решение бесплатно, чтобы кто‑то в него что‑то добавил в его интересах, впрочем, тоже находится под ударом, потому что для этого всё‑таки необходима популярность, а «отравивший» его проект мимопроходил этой популярности мешает). Сейчас, пока я это набираю, я смотрю на пятую попытку поставить Firefox через новенький‑моднявенький Snap на слабом, постоянно рвущемся соединении, и мне очень хочется, чтобы апофигеты Snap'а оказались сейчас передо мной, привязанными к дереву.
Сделав двухмерную версию JPEG и глянув его обычным вьюером, я обнаружил дичайшие артефакты. Как оказалось, я неверно выбрал знаменатель, к которому нужно приводить веса гармоник. Оно вроде бы как работает — но стандарт работает «в миллиметрах», а моё поделие — «в дюймах». Если всё нижеперечисленное расползётся по проектам и приведёт к появлению двух несовместимых систем кодирования — я никогда не прощу себе, что пошёл на поводу у этой кучи плюсиков под комментариями и выложил то, что выкладываю сейчас. Пожалуйста, не подводите старпёра и добейтесь максимального реюза существующих стандартов, и не только его. «Дьявол кроется в мелочах», убить проект — проще простого, а ещё проще сделать его «ядовитым». Ну, и психологический момент — теперь я чувствую, что переложил работу на плечи желающих продолжить и дальше как будто бы можно уже и не продолжать... это тоже некоторое время сдерживало меня от написания этой статьи.
Я себе вижу продолжение как‑то так:
Обкорнать третье измерение и сделать полностью совместимый со стандартом компрессор JPEG.
Посмотреть, что в нём сделано не так, как сделано у меня.
Подумать, чем руководствовался Joint Photographic Experts Group и осознанно понять, что из этого относится к 3D‑JPEG, а что — таки нет.
Правильно выбрать способ хранения гармоник. Вероятно, учесть вылезшие за годы недостатки JPEG. Например (ни к чему не подталкиваю!) — сначала хранить все DC‑компоненты, а затем — гармоники. Если не успели подгрузить гармоники — перескакиваем на следующий чанк (длина известна из его тэга, потому что в GIF каждый чанк данных предваряется тэгом), на экране мелькнут артефакты 8×8, но это лучше, чем ничего. Повторюсь, это только «мысли вслух» (это было бы круто с JPEG «по умолчанию», без специальных костылей в виде «Progressive JPEG», но не факт, что будет круто в 3D‑JPEG).
Правильно выбрать варианты хранения цветности. Понижать ли разрешение по оси времени? Что при этом делать с наличием двух чанков яркости на чанк цветности? А может быть, хранить в одном чанке больше 8 кадров? А как в JPEG стандартизирован канал яркости — как среднее арифметическое или как визуально корректное чёрно‑белое (с учётом чувствительности глаза)?
Правильно выбрать расширения для GIF (в том числе кастомные номера для тэгов, которыми мы снабдим чанки 3D‑JPEG). Я себе это вижу как чанк таблицы Хаффмана, чанк таблицы квантования и чанки, собственно, самих данных, в тэгах которых мы не забыли упомянуть, сколько миллисекунд на кадр у нас отводится (может быть, взять совместимую с AVI простую дробь?) Если характер данных резко поменялся — снова вставляем чанки Хаффмана и/или квантования, дальше чанки данных идут соответствующие (ну, как палитру на лету меняют в обычном AniGIF).
JPEG умеет работать с 10 битами на канал, если я не ошибаюсь. Одноканальный 10-битный — это уже, в принципе, вещь относительно самодостаточная, потому что палитру из 1024 цветов уже реально сделать «непрерывно перетекающей между тонами» (в 256 мне это впихнуть не удалось). Да, только для ограниченного круга рисованной анимации с определёнными стилями, но реально. А тэг для чанка с палитрой у GIF и так уже есть готовенький.
А тащить ли вообще в GIF такую часть JPEG, как сжатие Хаффмана? У GIF уже есть своё, LZW. Как оно себя покажет на квантованных коэффициентах, в основном сводящихся к нулям?
Этот пункт я в любом случае сам бы за всю жизнь не сделал, поэтому и не собирался изначально: подобрать оптимальную таблицу квантования! К счастью, она, в лучших традициях JPEG, прямо в файле и хранится. Тут мы не делаем ничего необратимого — всегда можно улучшать сложившиеся на практике таблицы ещё и ещё.
И это только касательно GIF, к которому математика готова «здесь и сейчас». «Взрослые» кодеки могут потребовать более высокой скорости распаковки — ну, а GIF обычно имеет невысокое разрешение и предназначен для компактных, коротких видео без звука, а особенность 3D‑JPEG как раз в том, что чем выше степень сжатия, тем меньше нагрузка на процессор при распаковке (то есть компактные, сильно пережатые «анигифки» идеально подходят).
Теперь о цифрах. Я тестировал алгоритм на чёрно‑белом (о цвете вообще пока не думал) видео в 584 кадра 640×360 каждый (вполне нормальный размер для анигифки).
Сырой размер: 134 553 600.
Размер в 7-zip: 4 533 514.
Хаффман, конечно, сожмёт не так сильно, но, думаю, разительных отличий, стоящих того, чтобы LZMA туда тащить — мы не встретим. Опять же, мы ещё не видели в деле LZW.
Характер видео: различные движения как кадра целиком, так и отдельных предметов в кадре.
Таблица квантования: от фонаря, то есть доработанная напильником традиционная 2D.
Почему же столь примитивная вещь, как «MJPEG на стероидах», наступает на пятки «взрослым» кодекам? А дело в том, что косинусное преобразование по шкале времени позволяет реализовать самую сильную сторону таких кодеков, то есть выделение движущихся областей и передачу их из кадра в кадр с сохранением только тех небольших изменений, которые эти области претерпевают, плюс самого факта их движения. Основное содержимое таблицы коэффициентов по шкале времени — нули. Но только без интеллектуального анализа, всё получается «само собой», самыми примитивными средствами. Что же касается артефактов, которыми приходится платить за такое сжатие — я выбрал кадры, где движется и фон, и объект, и собрал из них две обычные гифки чудовищного веса (на одной было нагляднее, но не влезло в хабралимит). На них всё можно оценить «как есть», потому что применительно к монохромным 256-цветным изображениям обычный GIF ведь, по сути, lossless‑формат!
Боже мой, сержант, эти гифки ползут прямо на нас! Нас сейчас раздавит!!!
Ну, а теперь код, которым это было получено.
Я обещаю прочитать спецификации GIF и JPEG и подумать на шаг вперёд прежде, чем что-то делать «для широкой публики» на основе этого кода!
//Собирается OpenWatcom 1.9 как Win32 текстовое консольное приложение.
#include <fstream.h>
#include <math.h>
#include <malloc.h>
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
//double Stat2D[8][8]={0}, Stat3D[8][8][8]={0};
//int Count2D=0, Count3D=0;
double CosFreq[8][8] = {
1, 1, 1, 1, 1, 1, 1, 1,
0.980785, 0.83147, 0.55557, 0.19509, -0.19509, -0.55557, -0.83147, -0.980785,
0.92388, 0.382683, -0.382683, -0.92388, -0.92388, -0.382683, 0.382683, 0.92388,
0.83147, -0.19509, -0.980785, -0.55557, 0.55557, 0.980785, 0.19509, -0.83147,
0.707107, -0.707107, -0.707107, 0.707107, 0.707107, -0.707107, -0.707107, 0.707107,
0.55557, -0.980785, 0.19509, 0.83147, -0.83147, -0.19509, 0.980785, -0.55557,
0.382683, -0.92388, 0.92388, -0.382683, -0.382683, 0.92388, -0.92388, 0.382683,
0.19509, -0.55557, 0.83147, -0.980785, 0.980785, -0.83147, 0.55557, -0.19509 };
double AlphaNorm[8] = {1.4142135623730950488016887242097, 1, 1, 1, 1, 1, 1, 1};
static double PreCalcCoeffs[512][512];
double round (double FuckinWatcomLibrary)
{
if (FuckinWatcomLibrary<0) return ceil (FuckinWatcomLibrary - .5);
return floor (FuckinWatcomLibrary + .5);
}
char* ReadBMP (char *Name, int *XSize, int *YSize, void *Colormap, int Restrictions)
{
#pragma pack(push)
#pragma pack(0)
struct
{
short Id;
long FSize, Ver, DataOffset, Unused, Width, Height;
short WTF, BPP;
long Compr; //0 for uncompressed, 1,2 for RLE
long DataSize, XRes, YRes, PalSize, Unused2;
// char Palette[256][4];
char Palette[2][4];
} BmpHeader;
#pragma pack(pop)
fstream f;
char *Raw, *P;
int line, netto, brutto;
f.open (Name, ios::in|ios::binary);
if (f.fail()) return NULL;
f.read ((char*)&BmpHeader, sizeof (BmpHeader));
if (f.fail()) {f.close(); return NULL;}
if (BmpHeader.Id!=0x4D42) {f.close(); return NULL;} //Wrong BMP id!
if (BmpHeader.Compr) {f.close(); return NULL;} //Compressed files are not supported
*XSize = BmpHeader.Width;
*YSize = BmpHeader.Height;
f.seekg(BmpHeader.DataOffset);
switch (BmpHeader.BPP)
{
case 24:
netto = BmpHeader.Width*3;
brutto = (netto + 3) & ~3;
Raw = (char*)malloc(BmpHeader.Height*netto);
if (!Raw) {f.close(); return NULL;}
for (line=0,P=Raw; line<BmpHeader.Height; line++,P+=netto)
{
f.read (P, netto);
if (f.fail()) {f.close(); free(Raw); return NULL;}
f.seekg (brutto-netto, ios::cur);
}
break;
default:
f.close();
return NULL; //ToDo
}
f.close();
return Raw;
}
/*
void Get2DStat (double Flat[8][8])
{
int u, v, x, y;
double DCT[8][8];
for (v=0; v<8; v++) for (u=0; u<8; u++)
{
DCT[v][u]=0;
for (y=0; y<8; y++) for (x=0; x<8; x++) DCT[v][u]+=CosFreq[u][x] * CosFreq[v][y] * (Flat[y][x] - 128.0);
DCT[v][u]/=4.0; // *=sqrt(2/8)*sqrt(2/8)
if (!u) DCT[v][u]/=sqrt(2.0);
if (!v) DCT[v][u]/=sqrt(2.0);
}
for (v=0; v<8; v++) for (u=0; u<8; u++) Stat2D[v][u]+=fabs(DCT[v][u]);
Count2D++;
}
*/
void CompressCube (double Cube[8][8][8])
{
int u, v, w, x, y, z;
double DCT[8][8][8];
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Cube[z][y][x]-=128;
for (w=0; w<8; w++) for (v=0; v<8; v++) for (u=0; u<8; u++)
{
DCT[w][v][u]=0;
// for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) DCT[w][v][u]+=cos( (2*x+1)*u*3.1415926536/16.0 ) * cos( (2*y+1)*v*3.1415926536/16.0 ) * cos( (2*z+1)*w*3.1415926536/16.0 ) * Cube[z][y][x];
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) DCT[w][v][u]+=CosFreq[u][x] * CosFreq[v][y] * CosFreq[w][z] * Cube[z][y][x];
DCT[w][v][u]/=8.0; // *=sqrt(2/8)*sqrt(2/8)*sqrt(2/8)
if (!u) DCT[w][v][u]/=sqrt(2.0);
if (!v) DCT[w][v][u]/=sqrt(2.0);
if (!w) DCT[w][v][u]/=sqrt(2.0);
}
memcpy (Cube, DCT, sizeof(double)*8*8*8);
}
void ExpandCube (double DCT[8][8][8])
{
int u, v, w, x, y, z;
double Cube[8][8][8];
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++)
{
Cube[z][y][x]=0;
for (w=0; w<8; w++) for (v=0; v<8; v++) for (u=0; u<8; u++) Cube[z][y][x] += CosFreq[u][x] * CosFreq[v][y] * CosFreq[w][z] * DCT[w][v][u] / AlphaNorm[u] / AlphaNorm[v] / AlphaNorm[w];
Cube[z][y][x]/=8.0; // *=sqrt(2/8)*sqrt(2/8)*sqrt(2/8)
}
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) DCT[z][y][x]=min(255.0,max(Cube[z][y][x]+128,0.0));
}
void InitFastExpand()
{
int u, v, w, x, y, z;
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++)
for (w=0; w<8; w++) for (v=0; v<8; v++) for (u=0; u<8; u++) PreCalcCoeffs[w*64+v*8+u][z*64+y*8+x] = CosFreq[u][x] * CosFreq[v][y] * CosFreq[w][z] / AlphaNorm[u] / AlphaNorm[v] / AlphaNorm[w] / 8.0;
}
void ExpandCubeFast (double DCT[512])
{
int Coeff, Pixel;
double Cube[512] = {0};
for (Coeff=0; Coeff<512; Coeff++)
if (DCT[Coeff])
for (Pixel=0; Pixel<512; Pixel++)
Cube[Pixel] += PreCalcCoeffs[Coeff][Pixel] * DCT[Coeff]; //Still a bottleneck!!!
for (Pixel=0; Pixel<512; Pixel++) DCT[Pixel]=min(255.0,max(Cube[Pixel]+128,0.0));
}
void main (void)
{
int FrNum, XSize, YSize;
char Name[]="FramXXXX.bmp";
char OutName[]="TestXXXX.raw";
char *Frame[8]={0};
int x, y, z, xx, yy;
double CoeffsQ2D[8][8]={
16, 11, 10, 16, 24, 40, 51, 61,
12, 12, 14, 19, 26, 58, 60, 55,
14, 13, 16, 24, 40, 57, 69, 56,
14, 17, 22, 29, 51, 87, 80, 62,
18, 22, 37, 56, 68,109,103, 77,
24, 35, 55, 64, 81,104,113, 92,
49, 64, 78, 87,103,121,120,101,
72, 92, 95, 98,112,100,103, 99},
CoeffFactor, //pityful attempts (until I have no actual Coeffs3D).
Pixels3D[8][8][8],
Waves3D[8][8][8];
fstream Log;
Log.open ("Log.hex",ios::out|ios::binary);
for (int i=0; i<64; i++) CoeffsQ2D[0][i]*=2;
InitFastExpand();
for (FrNum=0;FrNum<10000;FrNum++)
{
Name[4]='0'+FrNum/1000;
Name[5]='0'+FrNum/100%10;
Name[6]='0'+FrNum/10%10;
Name[7]='0'+FrNum%10;
cout<<"Reading "<<Name<<endl;
Frame[FrNum%8]=ReadBMP(Name, &XSize, &YSize, NULL, 0/*BMP_OPEN_RGB_ONLY*/);
if (!Frame[FrNum%8]) {cout<<"Couldn't open!"<<endl; break;} //No more BMPs!
if (XSize%8 || YSize%8) break; //Wrong size!
if (FrNum%8 && (xx!=XSize || yy!=YSize)) break; //Sizes differ from first!
xx=XSize;
yy=YSize;
if (FrNum%8 == 7)
{
cout<<"Encoding eight "<<XSize<<" x "<<YSize<<endl;
for (yy=0; yy<YSize; yy+=8) for (xx=0; xx<XSize; xx+=8)
{
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Pixels3D[z][y][x]=(Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 ]+Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 + 1]+Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 + 2])/3.0;
// for (z=0; z<8; z++) Get2DStat(Pixels3D[z]);
CompressCube(Pixels3D);
// for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Stat3D[z][y][x]+=fabs(Pixels3D[z][y][x]);
// Count3D++;
for (z=0,CoeffFactor=1; z<8; z++,CoeffFactor*=1.1) for (y=0; y<8; y++) for (x=0; x<8; x++) Pixels3D[z][y][x] = round(Pixels3D[z][y][x]/(CoeffsQ2D[y][x]*CoeffFactor))+128.001;
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) if ((int)(Pixels3D[z][y][x])<0 || (int)(Pixels3D[z][y][x])>255) cout<<"Quant. error: "<<Pixels3D[z][y][x]<<" is out of range!"<<endl;
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 ] = Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 + 1] = Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 + 2] = Pixels3D[z][y][x];
}
cout<<"Saving integer data"<<endl;
for (yy=0; yy<YSize; yy+=8) for (xx=0; xx<XSize; xx+=8)
{
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Log.write (&(Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 ]), 1);
}
cout<<"Decoding"<<endl;
for (yy=0; yy<YSize; yy+=8) for (xx=0; xx<XSize; xx+=8)
{
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Pixels3D[z][y][x]=(double)( Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 ] )-128.0;
for (z=0,CoeffFactor=1; z<8; z++,CoeffFactor*=1.1) for (y=0; y<8; y++) for (x=0; x<8; x++) Pixels3D[z][y][x] *= CoeffsQ2D[y][x]*CoeffFactor;
// ExpandCube(Pixels3D);
ExpandCubeFast(Pixels3D[0][0]);
for (z=0; z<8; z++) for (y=0; y<8; y++) for (x=0; x<8; x++) Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 ] = Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 + 1] = Frame[z][ (yy+y)*XSize*3 + (xx+x)*3 + 2] = Pixels3D[z][y][x];
}
for (z=0; z<8; z++)
{
OutName[4]='0'+((FrNum&~7)+z)/1000;
OutName[5]='0'+((FrNum&~7)+z)/100%10;
OutName[6]='0'+((FrNum&~7)+z)/10%10;
OutName[7]='0'+((FrNum&~7)+z)%10;
cout<<"Writing "<<OutName<<endl;
fstream f;
f.open(OutName, ios::out|ios::binary);
f.write(Frame[z],XSize*YSize*3);
f.close();
free (Frame[z]);
}
/*
cout<<"Gathered so far (2D):"<<endl;
for (y=0; y<8; y++,cout<<endl) for (x=0; x<8; x++) cout<<Stat2D[y][x]/Count2D<<" ";
cout<<"Gathered so far (3D):"<<endl;
for (z=0; z<8; z++,cout<<endl) for (y=0; y<8; y++,cout<<endl) for (x=0; x<8; x++) cout<<Stat3D[z][y][x]/Count3D<<" ";
*/
}
}
Log.close();
}
Также напоминаю, что в помощи народа всё ещё нуждается вот этот проект. Нужно найти хорошую таблицу частотности букв и буквосочетаний и, главное, большим количеством CUDA-карт оптимизировать цепочку — по косвенным признакам, я к оптимуму и на пушечный выстрел не подошёл.
