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-карт оптимизировать цепочку — по косвенным признакам, я к оптимуму и на пушечный выстрел не подошёл.
