Re: [問卦] 用C語言排出張惠妹的臉很強嗎？

[jserv (松鼠)]

※ 引述《bike3905 (RKTxLeo)》之銘言：
: https://i.imgur.com/ntEbO56.jpeg
: 有人說對岸用無人機排出張惠妹的臉
: 只要給我足夠的時間
: 我能用C語言排出張惠妹的臉
: 這樣很強嗎？

我準備指派學生的作業時，想到上面的挑戰。以 128x128 畫素 RGB 來說，張惠妹
的臉部可用 776 位元組展現，簡單的編碼如下：

static const char *H =
    "4ZmQ;9Z5\\1k^QTkmJD@=gbeB[@alfNAZ?>3NaIB]d_I7h9;=Q8aM^M=@3JEeg^9UOi1"
    "eUBkjfK[`40\\IKQg?\\FR;CaFBaCe:ioATMIFmSUk^g05X4XRY3Xh4aoMFF8W`P7MRM"
    "Jnk9Y\\MBVZ1NK2=YUHF@O`9NmC93M31_a5h@g\\mmd7AoeAAgm:?Z37>ZIGQ>F0YdMe"
    "g?d]WWF@G`T=IKlV;KGbi8\\<5hmFS11A[]_Xf?B598nhd2anSoUVkDD`0Gm@fO]`B2L"
    "K<cn6Sm\\TL_U<8<WN>[ZWGXU1\\7WZf;PQZhneTe7BV?<_7_1RKXoBI;VQRc?GakMY9"
    "X7?FBcNm5LB>C7Bj<l>aaNoB@0k463f;IfPi5E@]DAeM00J=\\C901VlF035:>aCNTbT"
    "WO9DAVW@DPZc`0[BU??[5J7R>5h7AHkc7h8:XW\\=NF2iYKJM[mZld=WSU:YdMiSjQn"
    "\\k11:Kn>1WgW7_nKZWdmj23T3jZXBm]Wb[2f1R:i4VaD@LU:A1_9j`dA4eQ>WTXD>`m"
    "85B@48_RjCHk1gcn5meS:EU3R\\m1i[i20=L30GDa>^Q7420@hljIdUNfoT6g;_3;FDS"
    "C]cOXc=D97>^3Ko3C2IX1U21a9A];SU=QJK@XR]h^;:lHikZT8C]e1PL=NCVJhnA\\25"
    "CUM_NJb59AQOC?H^;K2]Zn6RE:bBT:N75jm9nDoHllZ5U>_0L:T`ieTC1f=Gf0fVe<^d"
    "eWZB2biMeY;kN7m70VWG?ANB92^K5JJ]AQD;6k9DO=L^76cmY^1ae8ojF3:F2GdGO2T6"
    "=NEFX\\UHOcgKlLVU:`7nM?2MBDLQ<_:fb51S<C=W:KP9ZVI;f@g::Zbn=OL;IW8;L\\"
    "GIYF;QO\\Pd<ZD_7W=MSG^W91GVEl?4`UQ2P;5=kV75SdL[;FY;WPjWo8>Nk>^4oKE\\"
    "_12jbO_FmPW3oG7=cBWk?blijB48`@3Q:_ef1g^@0PhUS721ejdBIhJ1EL2i5D[k[oIH"
    "G]@aL`;]HE\\6b:Yi9aK@4Aom1E4c765V40";

有效位元串流和完整的 C 語言影像解碼器程式碼可見:
    https://gist.github.com/jserv/221efc83f7b60b996dcf9c8b435980d5

編譯和測試方式: gcc -O2 amei.c -lm && ./a.out > amei.png
預期可見到天后的臉龐，影像資料取自 [1]，故意降低品質，避免侵權。

本方法改寫自 [2]，解碼器分為二層：
* 上層是有損 (lossy) 影像解碼：
  利用四元樹 (quadtree) 分割、預測 (prediction)、DCT 殘差 (residual)
* 下層是無損 (lossless) 熵編碼 (entropy coding)：
  利用二元算術編碼 (binary arithmetic coding) + 指數哥倫布編碼
  (exponential-Golomb coding)

資料流向：
位元串流 (bitstream) → 算術解碼 → 指數哥倫布解碼 → 係數 (coefficient)
重建 → IDCT → 預測補償 → 去方塊濾波 (deblocking filter) → 色彩空間
(color space) 轉換 → PNG 輸出

算術編碼是整個壓縮系統的基石，負責將位元串流無損還原為個別的位元和整數。算術
編碼將 [0, 1) 區間 (interval) 依據符號的機率 (probability) 遞迴分割。對二元
算術編碼而言，區間分成兩段，分別對應 0 和 1，大小正比於各自的預測機率。解碼
時，追蹤目前的分數 (fraction) 落入哪一段，即可還原對應的位元值。

壓縮資料不直接以 RGB 儲存，而用 YCgCo 色彩空間：
- Y：亮度 (luma)，攜帶絕大部分影像細節
- Cg：綠-品紅色度 (green-magenta chrominance)
- Co：橙-藍色度 (orange-blue chrominance)

YCgCo 將亮度與色度解相關 (decorrelate)，人眼對亮度遠比色度敏感，因此編碼器可
對色度通道使用較大的量化步長而不明顯損失視覺品質。解碼器不做色度次取樣
(chroma subsampling)，而是直接提高色度的量化係數。三個通道以平面格式 (planar
format) 分別儲存在記憶體中，最終從 YCgCo 轉回交錯格式 (interleaved format) 的
RGB 輸出。

函式 W() 是解碼的主體，以遞迴四元樹方式拆分影像:

static void W(int z, int l, int g)
{
    if (g > 5 || (g > 2 && t(g - 3))) {
        int c = 1 << --g;
        foreach (a, 4)
            W(z + a % 2 * c, l + a / 2 * c, g);
        return;
    }
    /* ... 葉節點解碼 ... */
}
```

- 區塊 (block) 大於 32x32 (即 g > 5): 強制分割
- 區塊為 4x4 (即 g == 2`): 不再分割
- 中間層級 (8x8, 16x16, 32x32): 解碼一個位元決定是否分割

分割時將區塊一分為四，按左上、右上、左下、右下順序遞迴處理。產生類似 Z-order
曲線的走訪順序，使空間相鄰的區塊在編碼串流中也相鄰，有利於壓縮效率。張惠妹臉部
的影像採用四元樹分割機制，細節豐富的區域 (如五官) 被切得更細，平坦區域 (如背景)
保持較大區塊。

到達四元樹的葉節點 (leaf node) 後，解碼器對 Y,Cg,Co 三個通道分別處理。首先解碼
預測模式 q，該值在 0-33 之間，三個通道共用。

if (!q) {
    int v = 0;
    foreach (a, c)
        v += (l ? o[-f + a] : 0) + (z ? o[a * f - 1] : 0);
    *i += z && l ? v / 2 : v;
}

擷取目前區塊正上方和正左方已解碼畫素的平均值，寫入 DCT 的 DC 係數。技巧是，
不必逐畫素填入預測值，只需修改 DC 係數，因為 DC 係數在 IDCT 後恰好對應整個區塊
的常數偏移 (constant offset)。

33 個方向性預測模式對應 HEVC 的 33 個影格內預測 (intra prediction) 方向，每個
模式以 1/8 畫素為步進定義一個斜率 (slope)，圍繞對角線 (模式 17) 對稱分布。

int C = q < 17, w = C ? 9 - q : q - 25;

- 模式 1-16 (C=1): 主要從左方畫素向右延伸
- 模式 17-33 (C=0): 主要從上方畫素向下延伸
- 模式 9: 水平複製左方畫素
- 模式 25: 垂直複製上方畫素
- 模式 17: 沿對角線方向

對於非整數位置 (sub-pixel position)，解碼器以 1/8 畫素精度在兩個相鄰參考畫素
間進行線性內插 (linear interpolation)，產生抗鋸齒 (anti-aliasing) 效果：

o[C ? j * f + a : a * f + j] +=
    (*i * (8 - J) + i[1] * J + 4) >> 3;

權重 J 介於 0-7，(8-J) 和 J 分別為兩個鄰近畫素的內插權重。

預測只是近似值。要還原實際影像，還需要加上殘差 (residual)。殘差以離散餘弦轉換
(Discrete Cosine Transform, DCT) 係數的形式儲存。對每個區塊的每個色彩通道
(color channel) 而言：

foreach (a, d) i[a] = 0;           /* 清零工作緩衝區 */
for (int a = 0; a < d; a++) {
    if (t(61 + g * 2 + I)) break;  /* 結束旗標 */
    a += n(5 + I * 10);            /* 零遊程長度 */
    int k = 1 - 2 * t(3);          /* 正負號 */
    if (a < d)
        i[a] = k * (n(25 + (I + (a < d / 8) * 2) * 10) + 1) * (B ? P : O);
}

流程類似 H.263 的 (LAST, RUN, LEVEL) 三元組 (triplet)：
1. 解碼一個位元判斷是否已到最後一個非零係數
2. 解碼零遊程 (run of zeros)——連續跳過多少個零係數
3. 解碼正負號 (sign bit)
4. 解碼量化等級 (quantized level)，乘以量化步長（亮度用 O，色度用 P）
   還原係數，此為均勻中踏量化 (mid-tread uniform quantization)，無死區 (dead
   zone)

係數按列主序 (row-major order) 排列，不同於 JPEG 的鋸齒形掃描 (zigzag scan)。
非零係數傾向集中於左上角 (低頻區域)，自然影像的 DCT 係數具有高度稀疏性
(sparsity)。

函式 R() 實作一維 IDCT，並藉由可分離性 (separability) 拆為二次呼叫，以完成
二維 IDCT：

R(i + d, 1, i, 1, c, c, 10);       /* 各列做一維 IDCT */
R(o, f, i + d, c, 1, c, 10 + g);   /* 各行做一維 IDCT，直接寫回影像平面 */

DCT 的本質是將區塊分解為一組正弦波基底圖樣 (basis pattern) 的加權和 (weighted
sum)。左上角的低頻 (low-frequency) 基底對應模糊的漸層，右下角的高頻
(high-frequency) 基底對應細節邊緣。量化 (quantization) 就是在此處引入失真
壓縮：除以量化步長並四捨五入，小係數歸零，減少需要編碼的資料量。

IDCT 是整個解碼器中唯一使用浮點運算之處 (cos() 和 lrint())，其餘全用定點數
(fixed-point) 或整數算術。餘弦值可預先計算為表格查詢 (lookup table)，如此
便能完全消除浮點運算。

[1] https://www.mirrormedia.mg/story/20251104edi024
[2] A Tour of the Tiny and Obfuscated Image Decoder
    http://eastfarthing.com/blog/

---

你不知不覺看到這裡了嗎？
我要廣告最近開發的專案: https://github.com/sysprog21/zhtw-mcp
zhtw-mcp 是針對繁體中文場景設計的 MCP 伺服器，目標在於讓 AI 在產生繁體中文內容
時，能夠符合臺灣的語言習慣、資訊科技術語與正式書寫規範。本專案不是單純的繁簡
字形轉換，而是讓 AI 代理人在理解語境後，選擇符合臺灣語境的詞彙與表達方式。在
許多現有工具中，所謂的繁簡轉換通常只處理字形層級，例如將「计算机」轉換為「計算
機」或「電腦」，卻忽略詞彙與語境的差異，如「程序／程式」、「線程／執行緒」、
「內存／記憶體」、「網絡／網路」等。對於技術文件、教材與研究資料而言，這些差異
不只是風格問題，而會影響專業語言的一致性與可讀性。zhtw-mcp 的設計理念正是回應
這個問題。系統並非以固定詞典逐字替換，而用 AI 代理人的語境理解能力，將整段文本
視為語意單位，再決定最適合的臺灣用語與書寫方式。

歡迎在 GitHub 打星、測試，和提交意見及程式碼。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.245.217 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1773653862.A.BF3.html
→ snow3804: 說中文好嗎
噓 yuluiloveyou: 太長了誰他媽看得完
推 ttucse: 黃教授有在逛八卦板噢？
推 GTR12534: 有 jserv 先推
→ jserv: @yuluiloveyou, 這主要給學生看，順便分享
推 ttucse: 你吃飯了嗎？成大附近你都吃什麼？
推 yoyodiy: 大神
→ jserv: @ttucse, 我喜歡大學路十八巷，但店家變少
推 whyhsu: id
推 Mood10207: 太專業了，這裡不適合
→ jserv: @Mood10207, 跪求有緣人一起寫程式
推 kingstongyu: 現在不都把解碼器做成IC?!
→ jserv: @kingstongyu, 這也是我授課主題之一
→ kingstongyu: 透過程式寫解碼器生成圖片的速度太慢
→ yydogyy: 請說中文，謝謝
→ kingstongyu: 這在竹科或聯發科有在做,一般都依
→ kingstongyu: IEEE協定把類比數位的轉換標準協定
推 ttucse: 教授，如果自學作業系統，讀Andrew Tanenb
→ ttucse: aum寫的，minix那本教科書，你覺得如何呢
→ ttucse: ？
推 victortang: 老師請問餐做好叫你取餐是不是中斷？
推 kingstongyu: 生成影像或音樂,現在都塞進南橋北橋
→ kingstongyu: 裡了,再更過分一點說不定INTEL會把南
→ jserv: @ttucse, 時間許可就看 AST 教授大作
→ kingstongyu: 橋北橋都做在X86架構處理器裡加焊死
推 kabukiryu: .....
→ kingstongyu: 在主機板上賣
→ jserv: @kingstongyu, 以前有 Medfield，但是...
推 kingstongyu: J大,貴校現在沒研究AI嗎?!全台大學
→ kingstongyu: 連電機系不都朝AI發展發PAPER嗎?!
→ jserv: @kingstongyu, 電機資訊簡稱 AI
推 seanflower: 圖呢
→ jserv: @seanflower, 執行程式就看得到
推 PeikangShin: 你確定文組的看得懂？
推 ericthree: 有神快拜
→ jserv: @PeikangShin, 養龍蝦後，個個都是天才
推 HowLeeHi: 釣到宅社夫了
推 crazysix: 這一篇文章值 332 Ptt幣
→ jserv: @crazysix, 我偷懶從作業描述貼上
→ jserv: @HowLeeHi, 我是資深鄉民
推 lunenera: 寫那麼長有跑出來的結果嗎
推 red0210: 神
推 rdplyr: 推大神
推 laowa: 太猛了XD
→ jserv: @lunenera, 有的，你可檢驗輸出的PNG檔案
推 rightbear: 推大神
推 rickphyman42: 朝聖推