JPG學習筆記5（附完整代碼）

<style>#topics h2 { background: rgba(43, 102, 149, 1); border-radius: 6px; box-shadow: 0 0 1px rgba(95, 90, 75, 1), 1px 1px 6px 1px rgba(10, 10, 0, 0.5); color: rgba(255, 255, 255, 1); font-family: "微軟雅黑", "宋體", "黑體", Arial; font-size: 15px; font-weight: bold; height: 24px; line-height: 23px; margin: 12px 0 !important; padding: 5px 0 5px 10px; text-shadow: 2px 2px 3px rgba(34, 34, 34, 1) } #topics h1 span { font-weight: bold; line-height: 1.5; font-family: "Helvetica Neue", Helvetica, Verdana, Arial, sans-serif; text-decoration: underline; color: rgba(201, 27, 67, 1); text-shadow: 2px 2px 3px rgba(34, 34, 34, 1) }</style>

　　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處，前面有5個0，數值大小為3, magnitude value 為2，需要編碼的symbol為0x52;

以此類推：

唯一有的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,代碼如下

void JPG::huffmanCoding() {
    /*****************************************創建yDC_Table*********************************************/
    int lastYDC = 0;
    uint componentID = 1;
    //創建YDC_Table
    for (uint i = 0; i < mcuHeight; i++) {
        for (uint j = 0; j < mcuWidth; j++) {
            MCU& currentMCU = data[i * mcuWidth + j];
            //iterate over 每一個component Y, cb cr
            //遍歷block
            for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
                for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
                    Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
                    int difference = currentBlock[0] - lastYDC; //DC分量是encode difference
                    lastYDC = currentBlock[0];
                    byte symbol = getBinaryLengthByValue(difference); //Y的2進制的長度就是symbol的值
                    yDC.countOfSymbol[symbol]++;
                }
            }
        }
    }
    yDC.generateHuffmanCode(); 
     /*****************************************創建 yAC_Table*********************************************/
    for (uint i = 0; i < mcuHeight; i++) {
        for (uint j = 0; j < mcuWidth; j++) {
            MCU& currentMCU = data[i * mcuWidth + j];
            //遍歷block
            for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
                for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
                    Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
                    uint numZero = 0;
                    for(uint k = 1; k < 64; k++) {
                        if(currentBlock[ZIG_ZAG[k]] == 0) {
                            numZero++;
                            if(numZero == 16) {
                                if(isRemainingAllZero(currentBlock, k + 1)) {
                                    yAC.countOfSymbol[0x00]++;
                                    break;
                                } else {
                                    yAC.countOfSymbol[0xF0]++;//16個0
                                    numZero = 0;
                                }
                            }
                        } else {
                            byte lengthOfCoefficient = getBinaryLengthByValue(currentBlock[ZIG_ZAG[k]]);
                            byte symbol = (numZero << 4) + lengthOfCoefficient;
                            yAC.countOfSymbol[symbol]++;
                            numZero = 0;
                        }
                    }
                }
            }
        }
    }
    yAC.generateHuffmanCode();
    /*****************************************創建chromaDC_Table*********************************************/

    int lastChromaDC = 0;
    for(uint componentID = 2; componentID <=3; componentID++) {
        for (uint i = 0; i < mcuHeight; i++) {
            for (uint j = 0; j < mcuWidth; j++) {
                MCU& currentMCU = data[i * mcuWidth + j];
                //iterate over 每一個component Y, cb cr
                //遍歷block
                for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
                    for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
                        Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
                        int difference = currentBlock[0] - lastChromaDC; //DC分量是encode difference
                        lastChromaDC = currentBlock[0];
                        byte symbol = getBinaryLengthByValue(difference); //Y的2進制的長度就是symbol的值
                        chromaDC.countOfSymbol[symbol]++;
                    }
                }
            }
        }
    }
    chromaDC.generateHuffmanCode();
    /*****************************************創建chromaAC_Table*********************************************/
    for(uint componentID = 2; componentID <=3; componentID++) {
        for (uint i = 0; i < mcuHeight; i++) {
            for (uint j = 0; j < mcuWidth; j++) {
                MCU& currentMCU = data[i * mcuWidth + j];
                //遍歷block
                for(uint ii = 0; ii < getVerticalSamplingFrequency(componentID); ii++) {
                    for(uint jj = 0; jj < getHorizontalSamplingFrequency(componentID); jj++) {
                        Block& currentBlock = currentMCU[componentID][ii * getHorizontalSamplingFrequency(componentID) + jj];
                        uint numZero = 0;
                        for(uint k = 1; k < 64; k++) {
                            if(currentBlock[ZIG_ZAG[k]] == 0) {
                                numZero++;
                                if(numZero == 16) {
                                    if(isRemainingAllZero(currentBlock, k + 1)) {
                                        chromaAC.countOfSymbol[0x00]++;
                                        break;
                                    } else {
                                        chromaAC.countOfSymbol[0xF0]++;//16個0
                                        numZero = 0;
                                    }
                                }
                            } else {
                                byte lengthOfCoefficient = getBinaryLengthByValue(currentBlock[ZIG_ZAG[k]]);
                                byte symbol = (numZero << 4) + lengthOfCoefficient;
                                chromaAC.countOfSymbol[symbol]++;
                                numZero = 0;
                            }
                        }
                    }
                }
            }
        }
    }
    chromaAC.generateHuffmanCode();

}

 void generateHuffmanCode() {
        std::vector<LinkedSymbol> symbols;
        //遍歷每個出現的symbol， add to vectors
        for(uint symbol = 0; symbol < 256; symbol++) {
            if(countOfSymbol[symbol] == 0) 
                continue;
            Symbol* s = new Symbol(symbol, countOfSymbol[symbol], 0, nullptr);
            LinkedSymbol linkedSymbol;
            linkedSymbol.symbol = s;
            linkedSymbol.weight = s->weight;
            symbols.push_back(linkedSymbol);
        }
        
        
        // FF是一個不會出現的symbol,作為我們的dummy symbol 防止one bit stream 的出現  比如11111, 這樣就可以防止compressdata中出現FF的可能
        Symbol* dummySymbol = new Symbol(0xFF, 1, 0, nullptr); 
        LinkedSymbol dymmyLinkedSymbol;
        dymmyLinkedSymbol.symbol = dummySymbol;
        dymmyLinkedSymbol.weight = dummySymbol->weight;
        symbols.push_back(dymmyLinkedSymbol);
        
        

        //合并的程序
        while(symbols.size() != 1) {
            
            //leastWeight
            LinkedSymbol least = getLeastWeightLinkedSymbol(symbols);
            //second Least Weight
            LinkedSymbol second = getLeastWeightLinkedSymbol(symbols);
            //add two weights
            least.weight = least.weight + second.weight;

            //linked two linkedsymbols;
            Symbol* temp = second.symbol;
            while(temp->nextSymbol != nullptr)
                temp = temp->nextSymbol;
            temp->nextSymbol = least.symbol;
            least.symbol = second.symbol;
            //把每個symbol加1 codeLength,并且加入到 
            for(auto i = least.symbol; i != nullptr; i = i->nextSymbol) {
                i->codeLength++;
            }
            symbols.push_back(least);
        }

        //放入sortedSymbols
        for(Symbol* i = symbols[0].symbol; i != nullptr; i = i->nextSymbol) {
            sortedSymbol.push_back(*i);
        }

        //排序,并且把dummy symbol 放在最后面;
        std::sort(sortedSymbol.begin(), sortedSymbol.end(), comp);

        //釋放記憶體
        Symbol* temp = symbols[0].symbol;
        while(temp != nullptr) {
            auto t = temp->nextSymbol;
            delete temp;
            temp = t;
        }

        //長度為n的code的個數
        //生成codeLengthCount for each codeLength;
        for (auto it = sortedSymbol.cbegin(); it != sortedSymbol.cend(); it++) {
            codeCountOfLength[it->codeLength]++;
        }

        //規定codeLength不能大于16, 套用書上的方法實作了一下
        for(uint ii = 32; ii >= 17; ii--) {
            while(codeCountOfLength[ii] != 0) {
                uint jj = ii - 2;
                while(codeCountOfLength[jj] == 0)
                    jj--;
                codeCountOfLength[ii] = codeCountOfLength[ii] - 2;
                codeCountOfLength[ii - 1] = codeCountOfLength[ii - 1] + 1;
                codeCountOfLength[jj + 1] = codeCountOfLength[jj + 1] + 2;
                codeCountOfLength[jj] = codeCountOfLength[jj] - 1;
            }
        }

        uint index = 1; //codeLength賦值回去
        for (auto it = sortedSymbol.begin(); it != sortedSymbol.end(); it++) {
            if(codeCountOfLength[index] != 0) {
                it->codeLength = index;
                codeCountOfLength[index]--;
            } else {
                index++;
                it--;
            }
        }

        
        //生成huffmanCode for each symbol
        uint huffmanCode = 0;
        uint currentLength = 1;
        for (auto it = sortedSymbol.begin(); it != sortedSymbol.end(); it++) {
            if(currentLength == it->codeLength) {
                it->code = huffmanCode++;
                codeOfSymbol[it->symbol] = it->code;
                codeLengthOfSymbol[it->symbol] = it->codeLength;
            } else {
                huffmanCode = huffmanCode << 1;
                currentLength++;
                it--;
            }
        }
    }

 全部代碼在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

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/260879.html

標籤：其他

上一篇：美團一面：你既然寫過Mybatis插件，說說它底層是怎么加載一個自定義插件的

下一篇：云原生系列5 容器化日志之EFK