经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
JPG学习笔记5(附完整代码)
来源:cnblogs  作者:哇哩顾得  时间:2021/2/18 23:25:01  对本文有异议

  JPG压缩的第4步是哈夫曼编码。下面主要介绍JPEG是如果进行哈夫曼编码的。

图片引用自"Compressed Image File Formats JPEG, PNG, GIF, XBM, BMP - John Miano"[1]

1.AC数据的哈夫曼Symbol.

对于AC数据而言,需要编码的前4位代表这个数据之前有多少个0,后4位代表当前值的Magnitude Value。

 AC数据的编码是以ZigZag的顺序进行的。

如下图为例,从1开始前面有0个0, 数值大小为1, magnitude value为1,需要编码的symbol为0x01;

接着走到3处,前面有4个0,数值大小为3, magnitude value 为2,需要编码的symbol为0x42;

以此类推:

唯一有的2个额外的情况

0x00代表后面的数据都为0

0xF0代表16个0

 

 

  总共的symbol数量 = (为0的个数)16 * 10(不同的maginitude) + 2 (特殊情况) = 162。 

2.DC数据的哈夫曼Symbol

  DC数据存的是difference,即当前Block的DC值减去上一个Block的DC值。

  如下可知DC symbol总共有12个

 

3.JPEG默认哈夫曼编码

JPEG提供了默认的huffmanTable(emprically good)[2],如下

 

 

 

 

 

 

 引用"https://www.impulseadventure.com/photo/optimized-jpeg.html"

 也可以自己根据图片生成huffmanCode,代码如下

  1. void JPG::huffmanCoding() {
  2. /*****************************************创建yDC_Table*********************************************/
  3. int lastYDC = 0;
  4. uint componentID = 1;
  5. //创建YDC_Table
  6. for (uint i = 0; i < mcuHeight; i++) {
  7. for (uint j = 0; j < mcuWidth; j++) {
  8. MCU& currentMCU = data[i * mcuWidth + j];
  9. //iterate over 每一个component Y, cb cr
  10. //遍历block
  11. for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
  12. for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
  13. Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
  14. int difference = currentBlock[0] - lastYDC; //DC分量是encode difference
  15. lastYDC = currentBlock[0];
  16. byte symbol = getBinaryLengthByValue(difference); //Y的2进制的长度就是symbol的值
  17. yDC.countOfSymbol[symbol]++;
  18. }
  19. }
  20. }
  21. }
  22. yDC.generateHuffmanCode();
  23. /*****************************************创建 yAC_Table*********************************************/
  24. for (uint i = 0; i < mcuHeight; i++) {
  25. for (uint j = 0; j < mcuWidth; j++) {
  26. MCU& currentMCU = data[i * mcuWidth + j];
  27. //遍历block
  28. for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
  29. for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
  30. Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
  31. uint numZero = 0;
  32. for(uint k = 1; k < 64; k++) {
  33. if(currentBlock[ZIG_ZAG[k]] == 0) {
  34. numZero++;
  35. if(numZero == 16) {
  36. if(isRemainingAllZero(currentBlock, k + 1)) {
  37. yAC.countOfSymbol[0x00]++;
  38. break;
  39. } else {
  40. yAC.countOfSymbol[0xF0]++;//16个0
  41. numZero = 0;
  42. }
  43. }
  44. } else {
  45. byte lengthOfCoefficient = getBinaryLengthByValue(currentBlock[ZIG_ZAG[k]]);
  46. byte symbol = (numZero << 4) + lengthOfCoefficient;
  47. yAC.countOfSymbol[symbol]++;
  48. numZero = 0;
  49. }
  50. }
  51. }
  52. }
  53. }
  54. }
  55. yAC.generateHuffmanCode();
  56. /*****************************************创建chromaDC_Table*********************************************/
  57.  
  58. int lastChromaDC = 0;
  59. for(uint componentID = 2; componentID <=3; componentID++) {
  60. for (uint i = 0; i < mcuHeight; i++) {
  61. for (uint j = 0; j < mcuWidth; j++) {
  62. MCU& currentMCU = data[i * mcuWidth + j];
  63. //iterate over 每一个component Y, cb cr
  64. //遍历block
  65. for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
  66. for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
  67. Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
  68. int difference = currentBlock[0] - lastChromaDC; //DC分量是encode difference
  69. lastChromaDC = currentBlock[0];
  70. byte symbol = getBinaryLengthByValue(difference); //Y的2进制的长度就是symbol的值
  71. chromaDC.countOfSymbol[symbol]++;
  72. }
  73. }
  74. }
  75. }
  76. }
  77. chromaDC.generateHuffmanCode();
  78. /*****************************************创建chromaAC_Table*********************************************/
  79. for(uint componentID = 2; componentID <=3; componentID++) {
  80. for (uint i = 0; i < mcuHeight; i++) {
  81. for (uint j = 0; j < mcuWidth; j++) {
  82. MCU& currentMCU = data[i * mcuWidth + j];
  83. //遍历block
  84. for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
  85. for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
  86. Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
  87. uint numZero = 0;
  88. for(uint k = 1; k < 64; k++) {
  89. if(currentBlock[ZIG_ZAG[k]] == 0) {
  90. numZero++;
  91. if(numZero == 16) {
  92. if(isRemainingAllZero(currentBlock, k + 1)) {
  93. chromaAC.countOfSymbol[0x00]++;
  94. break;
  95. } else {
  96. chromaAC.countOfSymbol[0xF0]++;//16个0
  97. numZero = 0;
  98. }
  99. }
  100. } else {
  101. byte lengthOfCoefficient = getBinaryLengthByValue(currentBlock[ZIG_ZAG[k]]);
  102. byte symbol = (numZero << 4) + lengthOfCoefficient;
  103. chromaAC.countOfSymbol[symbol]++;
  104. numZero = 0;
  105. }
  106. }
  107. }
  108. }
  109. }
  110. }
  111. }
  112. chromaAC.generateHuffmanCode();
  113. }
  1. void generateHuffmanCode() {
  2. std::vector<LinkedSymbol> symbols;
  3. //遍历每个出现的symbol, add to vectors
  4. for(uint symbol = 0; symbol < 256; symbol++) {
  5. if(countOfSymbol[symbol] == 0)
  6. continue;
  7. Symbol* s = new Symbol(symbol, countOfSymbol[symbol], 0, nullptr);
  8. LinkedSymbol linkedSymbol;
  9. linkedSymbol.symbol = s;
  10. linkedSymbol.weight = s->weight;
  11. symbols.push_back(linkedSymbol);
  12. }
  13. // FF是一个不会出现的symbol,作为我们的dummy symbol 防止one bit stream 的出现 比如11111, 这样就可以防止compressdata中出现FF的可能
  14. Symbol* dummySymbol = new Symbol(0xFF, 1, 0, nullptr);
  15. LinkedSymbol dymmyLinkedSymbol;
  16. dymmyLinkedSymbol.symbol = dummySymbol;
  17. dymmyLinkedSymbol.weight = dummySymbol->weight;
  18. symbols.push_back(dymmyLinkedSymbol);
  19. //合并的过程
  20. while(symbols.size() != 1) {
  21. //leastWeight
  22. LinkedSymbol least = getLeastWeightLinkedSymbol(symbols);
  23. //second Least Weight
  24. LinkedSymbol second = getLeastWeightLinkedSymbol(symbols);
  25. //add two weights
  26. least.weight = least.weight + second.weight;
  27. //linked two linkedsymbols;
  28. Symbol* temp = second.symbol;
  29. while(temp->nextSymbol != nullptr)
  30. temp = temp->nextSymbol;
  31. temp->nextSymbol = least.symbol;
  32. least.symbol = second.symbol;
  33. //把每个symbol加1 codeLength,并且加入到
  34. for(auto i = least.symbol; i != nullptr; i = i->nextSymbol) {
  35. i->codeLength++;
  36. }
  37. symbols.push_back(least);
  38. }
  39. //放入sortedSymbols
  40. for(Symbol* i = symbols[0].symbol; i != nullptr; i = i->nextSymbol) {
  41. sortedSymbol.push_back(*i);
  42. }
  43. //排序,并且把dummy symbol 放在最后面;
  44. std::sort(sortedSymbol.begin(), sortedSymbol.end(), comp);
  45. //释放内存
  46. Symbol* temp = symbols[0].symbol;
  47. while(temp != nullptr) {
  48. auto t = temp->nextSymbol;
  49. delete temp;
  50. temp = t;
  51. }
  52. //长度为n的code的个数
  53. //生成codeLengthCount for each codeLength;
  54. for (auto it = sortedSymbol.cbegin(); it != sortedSymbol.cend(); it++) {
  55. codeCountOfLength[it->codeLength]++;
  56. }
  57. //规定codeLength不能大于16, 套用书上的方法实现了一下
  58. for(uint ii = 32; ii >= 17; ii--) {
  59. while(codeCountOfLength[ii] != 0) {
  60. uint jj = ii - 2;
  61. while(codeCountOfLength[jj] == 0)
  62. jj--;
  63. codeCountOfLength[ii] = codeCountOfLength[ii] - 2;
  64. codeCountOfLength[ii - 1] = codeCountOfLength[ii - 1] + 1;
  65. codeCountOfLength[jj + 1] = codeCountOfLength[jj + 1] + 2;
  66. codeCountOfLength[jj] = codeCountOfLength[jj] - 1;
  67. }
  68. }
  69. uint index = 1; //codeLength赋值回去
  70. for (auto it = sortedSymbol.begin(); it != sortedSymbol.end(); it++) {
  71. if(codeCountOfLength[index] != 0) {
  72. it->codeLength = index;
  73. codeCountOfLength[index]--;
  74. } else {
  75. index++;
  76. it--;
  77. }
  78. }
  79. //生成huffmanCode for each symbol
  80. uint huffmanCode = 0;
  81. uint currentLength = 1;
  82. for (auto it = sortedSymbol.begin(); it != sortedSymbol.end(); it++) {
  83. if(currentLength == it->codeLength) {
  84. it->code = huffmanCode++;
  85. codeOfSymbol[it->symbol] = it->code;
  86. codeLengthOfSymbol[it->symbol] = it->codeLength;
  87. } else {
  88. huffmanCode = huffmanCode << 1;
  89. currentLength++;
  90. it--;
  91. }
  92. }
  93. }

 全部代码在https://github.com/Cheemion/JPEG_COMPRESS/tree/main/Day5

 完结

 Thanks for reading.

                                                                                                                                                                                                                                                                                >>>> JPG学习笔记6


 

参考资料

[1]https://github.com/Cheemion/JPEG_COMPRESS/blob/main/resource/Compressed%20Image%20File%20Formats%20JPEG%2C%20PNG%2C%20GIF%2C%20XBM%2C%20BMP%20-%20John%20Miano.pdf

[2]https://www.impulseadventure.com/photo/optimized-jpeg.html

原文链接:http://www.cnblogs.com/robsann/p/14399453.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号