Blog
ブログ

2024年12月22日

JPEGエンコーダーをつくろう(3) – SOHOBB AI/BI Advent Calendar 2024

はじめに

　こんにちは。この記事はSOHOBB AI/BI Advent Calender 2024の22日目の記事となります。
私の担当記事では、「JPEGエンコーダーをつくろう」と題して画像圧縮符号化における基礎的な技術についてPython実装を交えながら紹介しています。

　前回は、JPEGエンコーダーにおけるDCTと量子化について紹介しました。DCTでは画像のYCbCr信号をコサイン基底を用いた周波数領域での表現に変換し、空間的な冗長性を取り除きました。また、人間の視覚が高周波の変化に鈍感である特性を利用し、周波数に応じて量子化幅を変えていました。

　今回は、量子化されたDCT係数を符号化し最終的なJPEGファイルに出力する内容について紹介したいと思います。

情報量とは

　JPEGエンコーダーの役割は、画像をより小さくコンパクトに圧縮することでした。コンピューターにおいては、画像をピクセル単位で表現しますが、実際にファイルとして蓄積する際には元のピクセルを一意に復号可能な符号を割り当てられた符号列で蓄積します。
前回まで取り扱ってきた情報量の削減とは異なり、符号化の前後で得られる情報量に差異はありません。
　ここで、情報量とはシャノンの情報理論における情報量を指します。情報量は、その具体的な意味や内容とは無関係に、事象の起こりにくさによって決定されます。たとえば、事象Eの起こる確率をP(E)とすると、Eの情報量は以下の式で表されます。

このときの情報量を事象Eの自己情報量と呼び、各事象の自己情報量の期待値を平均情報量(エントロピー)と呼びます。

　平均情報量は、事象ごとの確率に偏りが少ないほど(次にどの事象が起こるか不確実性が高いほど)大きくなります。また、符号化においては、平均情報量はある情報源を符号化した際のシンボルが平均で持つ情報量を表しているといえ、いかなる符号化方式であっても情報源の平均情報量を下回ることはないといえます。
そうです、画像を圧縮するうえでDFTやDSTと比較してエネルギー圧縮で優位なDCTが用いられる場合が多いのは、係数の平均情報量を小さくするための工夫でもあります。

Huffman符号

　Huffman符号は、シャノンの平均情報量にもとづき効率的な符号割り当てを行うエントロピー符号化の一種です。出現頻度の高いデータに対して短い符号を割り当て、出現頻度の低い符号に長い符号を割り当てることで全体の符号列長が短くなるよう工夫されています。

　JPEGでは、DC/AC成分それぞれを中間表現に変換した後Huffman符号によって符号を割り当てています。具体的には、DC成分についてはDPCM、AC成分についてはRLEを適用しています。

DPCM

　DC成分については、そのブロックの平均輝度を表していました。各ブロックのDC成分の大きさは画像によってまちまち(暗い画像から明るい画像まで)ですが、画像の空間的な相関を考えると、隣接するブロック間でのDC成分の差は小さくなる場合が多いです。

そこで、JPEGではDC成分をラスタスキャン順に並べて差分をとるDifferential Pulse Code modulation(DPCM)を適用して符号化対象の範囲を小さくしています。

RLE

　AC成分では、DCTによって低周波数成分にエネルギーが集中する性質がありました。また、DCT係数の量子化においても高周波数成分ほど粗く量子化していました。このため、高周波数成分ほど量子化後の係数がゼロである確率が高くなる傾向があります。

そこで、JPEGではAC成分をZig-Zagスキャン(低周波数成分から高周波数成分)順に並び変え、Run-Length Encoding(RLE)を適用しています。低周波数成分から高周波数成分に並べることで、AC成分列には高い確率でゼロが連続するゼロランが出現するため効率的に符号化することができるようになります。

JPEGエンコーダーをつくろう(Huffman符号)

　さて、DC/AC成分の符号化器を実装しましょう。

実際のJPEGでは、セグメントと呼ばれるいくつかの領域に分けて情報を記録しています。各セグメントの識別子やデコードの都合から予約されたコードや制約が設けられていますが、これまでのペースで言及すると非常に長くなりそうだったので割愛します。

Python 
ZIGZAG_ORDER = np.array([
    0,  1,  8, 16,  9,  2,  3, 10, 
    17, 24, 32, 25, 18, 11,  4,  5,
    12, 19, 26, 33, 40, 48, 41, 34, 
    27, 20, 13,  6,  7, 14, 21, 28,
    35, 42, 49, 56, 57, 50, 43, 36, 
    29, 22, 15, 23, 30, 37, 44, 51,
    58, 59, 52, 45, 38, 31, 39, 46, 
    53, 60, 61, 54, 47, 55, 62, 63])


def dpcm(coeffs: npt.NDArray):
    r, c = coeffs.shape[:2]
    # DC成分を抽出
    dcs = coeffs[:, :, 0, 0].reshape(-1)

    # DPCM
    dc_diff = np.diff(dcs, prepend=0)

    # size と additional bitsのペアに変換
    symbols = []
    for v in dc_diff:
        s = __cvt_to_size_and_bits(int(v))
        symbols.append(s)
    symbols = [symbols[i : i + c] for i in range(0, len(symbols), c)]
    return symbols


def rle(coeffs: npt.NDArray):
    r, c = coeffs.shape[:2]
    symbols = []
    for row in coeffs:
        for block in row:
            # ZigZagスキャン順に
            zz = block.reshape(-1)[ZIGZAG_ORDER]

            # EOBを求める
            eob = np.max(np.nonzero(zz))

            # RLE
            rl = 0
            symbol = []
            for v in zz[1:-eob] if eob > 0 else zz[1:]:
                if v == 0:
                    rl += 1
                    # ゼロランが16続いたらZRL
                    if rl == 16:
                        symbol.append((int(0xF0), None))
                        rl = 0
                else:
                    s, b = __cvt_to_size_and_bits(int(v))
                    print(rl, v, s, b, (rl << 4) + s)
                    symbol.append(((rl << 4) + s, b))
                    rl = 0
            if eob > 0:
                symbol.append((int(0x00), None))
            symbols.append(symbol)
    symbols = [symbols[i : i + c] for i in range(0, len(symbols), c)]
    return symbols
    
    
  def huffman_coding(symbols: list[tuple[int, bitarray.bitarray | None]]):
      RESERVE = 2048
      counts = Counter([_[0] for _ in symbols])
  
      # 予約された符号のためにダミーを追加
      counts[RESERVE] = 0
  
      # Huffmanテーブルを構築
      ht = bitarray.util.canonical_huffman(counts)[0]
  
      ht.pop(RESERVE)
  
      return ht

おわりに

　おつかれさまでした。
今回をもって、アドベントカレンダーにおけるJPEGエンコーダーをつくろうシリーズは終了となります。
全3本の記事すべてが、あまりに取り留めのない形になっており、普段からアウトプットをすることの重要さを痛感しました。つくろうシリーズと呼ぶにはあまりにも断片的になってしまいましたが、もし画像や符号化、JPEGファイルの構造について少しでも興味を持っていただけたなら、ぜひとも調べていただき、記事にしていただけるととても嬉しいです。
それでは、ここまでお付き合いいただきありがとうございました。

 

このページの先頭へ