• R/O
  • SSH
  • HTTPS

jyeipegyuu: 提交


Commit MetaInfo

修订版16 (tree)
时间2009-09-12 05:24:41
作者berupon

Log Message

DC成分をPaeth予測するのではなくLOCO-I予測での処理に変更。
DC成分の数が少ない場合はRangeCoderではなくGolomb-Rice符号を使うように変更。

更改概述

差异

--- misc.h (revision 15)
+++ misc.h (revision 16)
@@ -47,6 +47,19 @@
4747 }
4848 }
4949
50+int LOCO_IPredictor(int left, int above, int upperLeft)
51+{
52+ int minLeftAbove = std::min(left, above);
53+ int maxLeftAbove = std::max(left, above);
54+ if (upperLeft > maxLeftAbove) {
55+ return minLeftAbove;
56+ }else if (upperLeft < minLeftAbove) {
57+ return maxLeftAbove;
58+ }else {
59+ return left + above - upperLeft;
60+ }
61+}
62+
5063 class BitWriter
5164 {
5265 public:
@@ -110,11 +123,52 @@
110123 const unsigned char* initialSrc_;
111124 };
112125
126+class RiceCoder
127+{
128+public:
129+ RiceCoder(size_t shift)
130+ :
131+ shift_(shift)
132+ {
133+ }
134+
135+ void Encode(size_t value, BitWriter& writer)
136+ {
137+ size_t p = value >> shift_;
138+ for (size_t i=0; i<p; ++i) {
139+ writer.putBit(false);
140+ }
141+ writer.putBit(true);
142+ int v = 1;
143+ for (size_t i=0; i<shift_; ++i) {
144+ writer.putBit(value & v);
145+ v <<= 1;
146+ }
147+ }
148+
149+ size_t Decode(BitReader& reader)
150+ {
151+ size_t q = 0;
152+ while (!reader.getBit()) ++q;
153+ size_t ret = q << shift_;
154+ for (size_t i=0; i<shift_; ++i) {
155+ if (reader.getBit()) {
156+ ret += 1 << i;
157+ }
158+ }
159+ return ret;
160+ }
161+
162+private:
163+ size_t shift_;
164+};
165+
113166 void findZeroOneInfos(
114167 size_t hBlockCount,
115168 size_t vBlockCount,
116169 const int* src,
117170 int* dst,
171+ int* dst2,
118172 size_t limit
119173 )
120174 {
@@ -125,6 +179,7 @@
125179 from += totalBlockCount;
126180
127181 std::fill(dst, dst+totalBlockCount, 1);
182+ std::fill(dst2, dst2+totalBlockCount*8, 0);
128183
129184 for (size_t i=1; i<8; ++i) {
130185 unsigned char blockSize = 1 + i*2;
@@ -132,17 +187,29 @@
132187 from += blockSize * totalBlockCount;
133188 continue;
134189 }
190+ int* arr = dst2 + totalBlockCount * i;
135191 for (size_t j=0; j<totalBlockCount; ++j) {
136192 for (size_t k=0; k<blockSize; ++k) {
137193 int v = abs(from[k]);
138194 if (v > 1) {
139195 dst[j] = 0;
196+ arr[j] = -1;
140197 break;
141198 }
142199 }
143200 from += blockSize;
144201 }
202+ int hoge = 0;
145203 }
204+
205+ for (size_t i=0; i<totalBlockCount; ++i) {
206+ int sum = 0;
207+ for (size_t j=1; j<8; ++j) {
208+ sum |= std::abs(dst2[j*totalBlockCount + i]) << (j-limit);
209+ }
210+ dst2[i] = sum;
211+ }
212+ int hoge = 0;
146213 }
147214
148215 struct CompressInfo
@@ -165,9 +232,12 @@
165232 size_t totalLen;
166233 };
167234
235+static const size_t DC_BLOCKCOUNT_BORDER = 8192;
236+
168237 size_t compressSub(
169238 int* src,
170239 const int* pZeroOneInfos,
240+ size_t zeroOneFlag,
171241 size_t blockCount, size_t blockSize,
172242 unsigned char* dest, size_t destLen,
173243 unsigned char* tmp,
@@ -189,62 +259,158 @@
189259 int* phists = cinfo.phists;
190260 int* mhists = cinfo.mhists;
191261
192- int initialCompressedLen = srcCount * 4;
193- Encode(src, srcCount, max, 0, tmp, initialCompressedLen);
262+ int initialCompressedLen = 0;
263+
264+ // DC成分の記録数が少ない場合はRangeCoderではなくGolomb-Rice符号を使う
265+ //(成分数が少ない場合にRangeCoderの方が圧縮率が低いのは、エントロピの記録に容量を食ってしまう為かも)
266+ if (blockSize == 1 && blockCount < DC_BLOCKCOUNT_BORDER) {
267+ int b = 0;
194268
195- int encodedValueSizes[2];
196- int* from = src;
197- if (pZeroOneInfos) {
198- std::vector<int> values;
269+ if (max > 2048) {
270+ b = 7;
271+ }else if (max > 1024) {
272+ b = 6;
273+ }else if (max > 512) {
274+ b = 5;
275+ }else if (max > 256) {
276+ b = 4;
277+ }else if (max > 128+64) {
278+ b = 3;
279+ }else if (max > 96) {
280+ b = 2;
281+ }else if (max > 32) {
282+ b = 1;
283+ }else {
284+ b = 0;
285+ }
286+
287+ BitWriter bitWriter(tmp);
288+ RiceCoder riceCoder(b);
289+ int* from = src;
199290 for (size_t i=0; i<blockCount; ++i) {
200- if (pZeroOneInfos[i]) {
201- for (size_t j=0; j<blockSize; ++j) {
202- int val = src[i*blockSize+j];
203- cinfo.zeroOneOnlyAreaHist[val]++;
204- values.push_back(val);
205- }
291+ for (size_t j=0; j<blockSize; ++j) {
292+ riceCoder.Encode(*from++, bitWriter);
206293 }
207- }
208- encodedValueSizes[0] = blockCount*blockSize;
209- Encode(&values[0], values.size(), 1, 0, tmp2, encodedValueSizes[0]);
294+ }
295+ initialCompressedLen = bitWriter.nBytes();
210296
211- values.clear();
212- int maxV = 0;
213- for (size_t i=0; i<blockCount; ++i) {
214- if (!pZeroOneInfos[i]) {
215- for (size_t j=0; j<blockSize; ++j) {
216- int val = src[i*blockSize+j];
217- maxV = std::max(maxV, val);
218- cinfo.nonZeroOneOnlyAreaHist[val]++;
219- values.push_back(val);
297+ *dest++ = 0;
298+ *dest++ = b;
299+ memcpy(dest+4, tmp, initialCompressedLen);
300+ *((size_t*)dest) = initialCompressedLen;
301+ dest += 4;
302+ dest += initialCompressedLen;
303+
304+ }else {
305+ initialCompressedLen = srcCount * 4;
306+ Encode(src, srcCount, max, 0, tmp, initialCompressedLen);
307+
308+ int encodedValueSizes[2];
309+ int* from = src;
310+ if (pZeroOneInfos) {
311+ std::vector<int> values;
312+ for (size_t i=0; i<blockCount; ++i) {
313+ // if (!(pZeroOneInfos[i] & zeroOneFlag)) {
314+ if (pZeroOneInfos[i]) {
315+ for (size_t j=0; j<blockSize; ++j) {
316+ int val = src[i*blockSize+j];
317+ assert(val < 2);
318+ cinfo.zeroOneOnlyAreaHist[val]++;
319+ values.push_back(val);
320+ }
220321 }
221322 }
222- }
223- encodedValueSizes[1] = blockCount*blockSize;
224- Encode(&values[0], values.size(), maxV, 0, tmp3, encodedValueSizes[1]);
225-
226- int totalSize = encodedValueSizes[0] + encodedValueSizes[1];
227- size_t len = 0;
228- if (totalSize <= initialCompressedLen) {
229- *dest++ = 3;
323+ encodedValueSizes[0] = blockCount*blockSize;
324+ Encode(&values[0], values.size(), 1, 0, tmp2, encodedValueSizes[0]);
230325
231- for (size_t i=0; i<2; ++i) {
232- *((size_t*)dest) = encodedValueSizes[i];
233- dest += 4;
234- memcpy(dest, ((i==0)?tmp2:tmp3), encodedValueSizes[i]);
235- dest += encodedValueSizes[i];
326+ values.clear();
327+ int maxV = 0;
328+ for (size_t i=0; i<blockCount; ++i) {
329+ // if ((pZeroOneInfos[i] & zeroOneFlag)) {
330+ if (!pZeroOneInfos[i]) {
331+ for (size_t j=0; j<blockSize; ++j) {
332+ int val = src[i*blockSize+j];
333+ maxV = std::max(maxV, val);
334+ cinfo.nonZeroOneOnlyAreaHist[val]++;
335+ values.push_back(val);
336+ }
337+ }
236338 }
339+ encodedValueSizes[1] = blockCount*blockSize;
340+ Encode(&values[0], values.size(), maxV, 0, tmp3, encodedValueSizes[1]);
341+ /*
342+ {
343+ int zeroRepeat = 0;
344+ int zeroRepeatHist[1024] = {0};
345+ int repeatMax = 0;
346+ int val = 0;
347+ int valMax = 0;
348+ std::vector<int> zeroRepeatRecs;
349+ std::vector<int> nonZeroRecs;
350+ for (size_t i=0; i<values.size(); ++i) {
351+ val = values[i];
352+ if (val == 0) {
353+ ++zeroRepeat;
354+ }else {
355+ zeroRepeatRecs.push_back(zeroRepeat);
356+ ++zeroRepeatHist[zeroRepeat];
357+ repeatMax = std::max(repeatMax, zeroRepeat);
358+ zeroRepeat = 0;
359+ nonZeroRecs.push_back(val);
360+ valMax = std::max(valMax, val);
361+ }
362+ }
363+ if (zeroRepeat) {
364+ zeroRepeatRecs.push_back(zeroRepeat);
365+ ++zeroRepeatHist[zeroRepeat];
366+ repeatMax = std::max(repeatMax, zeroRepeat);
367+ zeroRepeat = 0;
368+ nonZeroRecs.push_back(val);
369+ valMax = std::max(valMax, val);
370+ }
371+ std::vector<int> newRecs;
372+ int nonZeroRefPos = 0;
373+ for (size_t i=0; i<zeroRepeatRecs.size(); ++i) {
374+ int v = zeroRepeatRecs[i];
375+ if (v) {
376+ newRecs.push_back(v);
377+ }
378+ newRecs.push_back(repeatMax + nonZeroRecs[nonZeroRefPos++]);
379+ }
380+ int encodedSize1 = blockCount*blockSize;
381+ int encodedSize2 = blockCount*blockSize;
382+ std::vector<unsigned char> recbuff(encodedSize1);
383+ Encode(&zeroRepeatRecs[0], zeroRepeatRecs.size(), repeatMax, 0, &recbuff[0], encodedSize1);
384+ Encode(&nonZeroRecs[0], nonZeroRecs.size(), maxV, 1, &recbuff[0], encodedSize2);
385+ int hoget = 0;
386+ }
387+ */
237388
238- goto label_end;
389+ int totalSize = encodedValueSizes[0] + encodedValueSizes[1];
390+ size_t len = 0;
391+ if (totalSize <= initialCompressedLen) {
392+ *dest++ = 3;
393+
394+ for (size_t i=0; i<2; ++i) {
395+ *((size_t*)dest) = encodedValueSizes[i];
396+ dest += 4;
397+ memcpy(dest, ((i==0)?tmp2:tmp3), encodedValueSizes[i]);
398+ dest += encodedValueSizes[i];
399+ }
400+
401+ goto label_end;
402+ }
403+
239404 }
240-
405+
406+ *dest++ = 1;
407+ memcpy(dest+4, tmp, initialCompressedLen);
408+ *((size_t*)dest) = initialCompressedLen;
409+ dest += 4;
410+ dest += initialCompressedLen;
411+
241412 }
242- *dest++ = 1;
243- memcpy(dest+4, tmp, initialCompressedLen);
244- *((size_t*)dest) = initialCompressedLen;
245- dest += 4;
246- dest += initialCompressedLen;
247-
413+
248414 label_end:
249415 size_t destDiff = dest - initialDest;
250416
@@ -258,7 +424,7 @@
258424 return destDiff;
259425 }
260426
261-void paethPredictEncode(
427+void predictEncode(
262428 size_t hBlockCount,
263429 size_t vBlockCount,
264430 int* src,
@@ -295,7 +461,7 @@
295461 for (size_t x=1; x<hBlockCount; ++x) {
296462 above = from[fromPos];
297463 cur = *to;
298- *to = cur - paethPredictor(left, above, upperLeft);
464+ *to = cur - LOCO_IPredictor(left, above, upperLeft);
299465 ++to;
300466 left = cur;
301467 upperLeft = above;
@@ -306,7 +472,7 @@
306472 std::copy(tmp, tmp+totalBlockCount, src);
307473 }
308474
309-void paethPredictDecode(
475+void predictDecode(
310476 size_t hBlockCount,
311477 size_t vBlockCount,
312478 int* src,
@@ -334,11 +500,11 @@
334500 ++writePos;
335501 }
336502 int toLineOffset = hBlockCount;
337- int paeth = 0;
503+ int diff = 0;
338504 for (size_t y=1; y<vBlockCount; ++y) {
339505 above = to[toLineOffset - hBlockCount];
340- paeth = to[toLineOffset];
341- cur = paeth + paethPredictor(0, above, 0);
506+ diff = to[toLineOffset];
507+ cur = diff + above;
342508 to[toLineOffset] = cur;
343509 writePos = toLineOffset + 1;
344510 left = cur;
@@ -345,8 +511,8 @@
345511 upperLeft = above;
346512 for (size_t x=1; x<hBlockCount; ++x) {
347513 above = to[writePos - hBlockCount];
348- paeth = to[writePos];
349- cur = paeth + paethPredictor(left, above, upperLeft);
514+ diff = to[writePos];
515+ cur = diff + LOCO_IPredictor(left, above, upperLeft);
350516 to[writePos] = cur;
351517 left = cur;
352518 upperLeft = above;
@@ -436,7 +602,7 @@
436602 for (size_t i=0; i<8; ++i) {
437603 const int* p01 = (i < zeroOneLimit) ? 0 : pZeroOneInfos;
438604 size_t blockSize = 1 + i * 2;
439- progress += compressSub(from, p01, totalBlockCount, blockSize, dest+progress, destLen-progress, tmp1, tmp2, tmp3, compressInfos[i]);
605+ progress += compressSub(from, p01, 1<<(i-zeroOneLimit), totalBlockCount, blockSize, dest+progress, destLen-progress, tmp1, tmp2, tmp3, compressInfos[i]);
440606 from += totalBlockCount * blockSize;
441607 }
442608
@@ -458,55 +624,72 @@
458624
459625 unsigned char compressFlag = *src++;
460626
461- if (compressFlag != 3) {
627+ if (blockSize == 1 && totalBlockCount < DC_BLOCKCOUNT_BORDER) {
628+ unsigned char b = *src++;
629+
462630 size_t len = *(size_t*)src;
463631 src += 4;
464632
465- int len2 = 0;
466- switch (compressFlag) {
467- case 1:
468- len2 = destLen*4;
469- Decode((unsigned char*)src, len, (int*)dest, len2);
470- break;
471- default:
472- assert(false);
633+ RiceCoder riceCoder(b);
634+ BitReader bitReader(src);
635+ for (size_t i=0; i<destLen; ++i) {
636+ dest[i] = riceCoder.Decode(bitReader);
473637 }
638+
639+ assert(len == bitReader.nBytes());
474640 src += len;
641+
475642 }else {
476- size_t sizes[2] = {0};
477- int resultSize = destLen * 4;
478-
479- sizes[0] = *(size_t*)src;
480- src += 4;
481- memcpy(tmp, src, sizes[0]);
482- src += sizes[0];
483- Decode(tmp, sizes[0], tmp2, resultSize);
484-
485- size_t count = 0;
486- for (size_t i=0; i<totalBlockCount; ++i) {
487- if (pZeroOneInfos[i]) {
488- for (size_t j=0; j<blockSize; ++j) {
489- dest[i*blockSize+j] = tmp2[count++];
490- }
643+ if (compressFlag != 3) {
644+ size_t len = *(size_t*)src;
645+ src += 4;
646+
647+ int len2 = 0;
648+ switch (compressFlag) {
649+ case 1:
650+ len2 = destLen*4;
651+ Decode((unsigned char*)src, len, (int*)dest, len2);
652+ break;
653+ default:
654+ assert(false);
491655 }
656+ src += len;
657+ }else {
658+ size_t sizes[2] = {0};
659+ int resultSize = destLen * 4;
660+
661+ sizes[0] = *(size_t*)src;
662+ src += 4;
663+ memcpy(tmp, src, sizes[0]);
664+ src += sizes[0];
665+ Decode(tmp, sizes[0], tmp2, resultSize);
666+
667+ size_t count = 0;
668+ for (size_t i=0; i<totalBlockCount; ++i) {
669+ if (pZeroOneInfos[i]) {
670+ for (size_t j=0; j<blockSize; ++j) {
671+ dest[i*blockSize+j] = tmp2[count++];
672+ }
673+ }
674+ }
675+
676+ sizes[1] = *(size_t*)src;
677+ src += 4;
678+ memcpy(tmp, src, sizes[1]);
679+ src += sizes[1];
680+ Decode(tmp, sizes[1], tmp2, resultSize);
681+
682+ count = 0;
683+ for (size_t i=0; i<totalBlockCount; ++i) {
684+ if (!pZeroOneInfos[i]) {
685+ for (size_t j=0; j<blockSize; ++j) {
686+ dest[i*blockSize+j] = tmp2[count++];
687+ }
688+ }
689+ }
690+
492691 }
493-
494- sizes[1] = *(size_t*)src;
495- src += 4;
496- memcpy(tmp, src, sizes[1]);
497- src += sizes[1];
498- Decode(tmp, sizes[1], tmp2, resultSize);
499-
500- count = 0;
501- for (size_t i=0; i<totalBlockCount; ++i) {
502- if (!pZeroOneInfos[i]) {
503- for (size_t j=0; j<blockSize; ++j) {
504- dest[i*blockSize+j] = tmp2[count++];
505- }
506- }
507- }
508-
509- }
692+ }
510693 return src - initialSrc;
511694 }
512695
--- main.cpp (revision 15)
+++ main.cpp (revision 16)
@@ -91,7 +91,7 @@
9191 unsigned char enablePaethPrediction = 1;
9292 *dest++ = enablePaethPrediction;
9393 if (enablePaethPrediction) {
94- paethPredictEncode(hBlockCount, vBlockCount, pWork2, pWork);
94+ predictEncode(hBlockCount, vBlockCount, pWork2, pWork);
9595 }
9696
9797 std::vector<unsigned char> signFlags(totalBlockCount*64);
@@ -100,12 +100,14 @@
100100
101101 size_t zeroOneLimit = 2;
102102 std::vector<int> zeroOneInfos(totalBlockCount);
103+ std::vector<int> allZeroOneInfos(totalBlockCount * 8);
103104 int* pZeroOneInfos = &zeroOneInfos[0];
105+ int* pAllZeroOneInfos = &allZeroOneInfos[0];
104106
105107 // quantizing zero one flags
106108 *dest++ = zeroOneLimit;
107109 if (zeroOneLimit != 0) {
108- findZeroOneInfos(hBlockCount, vBlockCount, pWork2, pZeroOneInfos, zeroOneLimit);
110+ findZeroOneInfos(hBlockCount, vBlockCount, pWork2, pZeroOneInfos, pAllZeroOneInfos, zeroOneLimit);
109111 int encodedSize = totalBlockCount/4;
110112 Encode(pZeroOneInfos, totalBlockCount, 1, 0, &work3[0], encodedSize);
111113 *((uint32_t*)dest) = encodedSize;
@@ -112,6 +114,14 @@
112114 dest += 4;
113115 memcpy(dest, &work3[0], encodedSize);
114116 dest += encodedSize;
117+
118+ //encodedSize = totalBlockCount;
119+ //Encode(pAllZeroOneInfos, totalBlockCount, (256>>zeroOneLimit)-1, 0, &work3[0], encodedSize);
120+ //*((uint32_t*)dest) = encodedSize;
121+ //dest += 4;
122+ //memcpy(dest, &work3[0], encodedSize);
123+ //dest += encodedSize;
124+
115125 }else {
116126 pZeroOneInfos = 0;
117127 }
@@ -184,7 +194,7 @@
184194 }
185195
186196 if (enablePaethPrediction) {
187- paethPredictDecode(hBlockCount, vBlockCount, pWork2, pWork);
197+ predictDecode(hBlockCount, vBlockCount, pWork2, pWork);
188198 }
189199
190200 reorderByPosition(hBlockCount, vBlockCount, pWork2, pWork);
Show on old repository browser