背景 6 枚を 480×270・16 色に落とす。色は Maximum Coverage と k-means、網は 2×2 の Bayer の閾値で置いた
Six backgrounds reduced to 480×270 and 16 colors: Maximum Coverage and k-means for color, a 2×2 Bayer threshold for dithering
D31-3-T61-color-quantization-16-colors・技術・日本語入力でプレイする仕組み
第一章の 6 か所の背景は、どれも 480×270 の 16 色です。
元は 1672×941 の生成した絵で、色を選ぶのも網を置くのも、決まった計算でやっています。
宿の潮見荘、食堂の番屋、港、駐在所、防波堤、岬の高台。
一人で全部の場所を同じ調子にそろえるために、どの絵にも同じ制約と同じ手順を当てています。
この回は、その落とし方です。
この回の位置と、前後の回#
区切り: T58〜T64 作り方と周辺（7 回のうち 4 回目）
先に読むとよい回: なし（この回だけで読めます）
次に読む回: T62（声つきのプレイ動画を台本から作る）
名前 — color quantization#
- 正式名
- color quantization（色の量子化・減色）
- 初出
- Paul Heckbert, "Color Image Quantization for Frame Buffer Display", ACM SIGGRAPH Computer Graphics 16(3), 1982（SIGGRAPH '82）。median cut はこの論文の方法
- 色を磨く側
- k-means（k 平均法）。J. B. MacQueen, "Some methods for classification and analysis of multivariate observations", Fifth Berkeley Symposium, 1967
- 色の候補を選ぶ側
- Pillow の Maximum Coverage。中身は farthest-first traversal（いちばん遠い点を順に選ぶ）の形で、その名前で知られる早い例は T. F. Gonzalez, "Clustering to minimize the maximum intercluster distance", Theoretical Computer Science 38, 1985
- 網
- ordered dithering（組織的ディザ）と Bayer matrix。B. E. Bayer, "An Optimum Method for Two-Level Rendition of Continuous-Tone Pictures", IEEE International Conference on Communications, 1973
- 拡大
- nearest-neighbor（最近傍）の整数倍
減色とは#
フルカラーの絵を、決まった数の色だけで描き直すことです。
Heckbert は、これを 4 つの段に分けて書いています。
- 絵の色の統計をとる
- 色の表（パレット）を選ぶ
- 画素ごとに、表のいちばん近い色へ写す
- 必要なら、ディザをかけて描き直す
難しいのは 2 です。
16 色で何万色を代表させるとき、どの 16 色を選ぶかで、絵の印象が決まります。
代表的な選び方は三つです。
- popularity: 多く出る色から順に選ぶ。単純だが、面積の小さい目立つ色（灯り、信号の赤）が消える
- median cut: 色の空間を箱で包み、いちばん長い軸で、画素の数が半分になる所で切る。これを 16 個の箱になるまで繰り返し、箱の中の平均を色にする
- k-means: 色を k 個の群に分け、「各画素をいちばん近い中心へ割り当てる」「中心を群の平均に動かす」を繰り返す。誤差（二乗の和）は反復ごとに下がるが、出発点しだいで局所解に止まる
k-means は、ほかの方法で作った表を出発点にして磨く使い方がよくあります。
3 の「いちばん近い色」は、ふつう RGB の二乗距離です。
人の目に合わせるなら Lab などの色空間で測りますが、16 色程度では RGB で済ませることが多い。
4 のディザは、表に無い中間の色を、2 色を細かく混ぜて見せる方法です。
大きく二つあります。
- ordered dithering: 決まった閾値の表を絵の上に敷き詰め、画素ごとに表の値と比べて 2 色のどちらにするかを決める。Bayer の表が定番で、4×4 なら 16 段の濃さが出せる。速く、画素ごとに独立で、同じ入力なら必ず同じ模様になる。弱点は、格子の模様がはっきり見えること
- error diffusion: 写したときの誤差を、まだ処理していない隣の画素へ配る。Floyd–Steinberg が有名。模様は自然だが、一画素の違いが後ろへ伝わり、細い線の近くに粒が散る
うちの工程 — color quantization#
道具は、手元の Python とブラウザの制作室です（名前は PC98 Painter／Atelier v2.3）。
画像の処理は Pillow と NumPy だけで、手引きは Docs/Guides/Working/pc98-painter-production-guide.md にあります。
1 枚の流れは 6 段です。
① 取り込み
元の絵を読み、ハッシュを付けて保全します。
EXIF の向きを直し、透過は白の上に重ねます。
② 切り抜きと縮小
1672×941 を、端を切り落とさずに全画面で使います（crop: [0, 0, 1672, 941]）。
厳密な 16:9 との差は、縮小で吸収します。
縮小は Lanczos で、480×270 へ。
def crop_image(im, p):
x, y, w, h = p['crop']
return im.resize((480, 270), Image.Resampling.LANCZOS, box=(x, y, x+w, y+h))
③ 16 色を選ぶ
縮小した 480×270 から、Pillow の quantize で 16 色を作ります。
def make_palette(im, method='maximum_coverage', kmeans=8):
reduced = im.convert('RGB').quantize(colors=16, method=METHODS[method],
kmeans=kmeans, dither=Image.Dither.NONE)
raw = reduced.getpalette()
colors = [raw[i3:i3+3] for _, i in reduced.getcolors()]
colors.sort(key=lambda c: (sum(c), c))
colors += [colors[-1]] * (16 - len(colors))
return ['#%02x%02x%02x' % tuple(c) for c in colors]
dither=Image.Dither.NONE を明示しているのは、Pillow の quantize の既定が Floyd–Steinberg だからです。
色を選ぶ段では、まだ網を入れません。
16 色は明るさ（RGB の和）の順に並べ、色番号 0 がいちばん暗い色です。
④ 下地を作る
480×270 の画素ごとに、16 色のうち RGB の二乗距離（R・G・B の重みは同じ）がいちばん小さい色を選びます。
平滑化なし（smooth=1）、明るさの倍率なし（gain=1）、全体のディザなし（dither=0）。
ここまでで、網の無い「16 色の下地」ができます。
⑤ 網を置く（次の節）
⑥ 4 倍にして納品
480×270 を最近傍で 4 倍にし、1920×1080 のパレット画像で保存します。
1 画素が 4×4 画素になるだけで、新しい色は出ません。
納品台帳には baked: true と apply_runtime_filter: false を書き、ゲームの側では重ねて加工しません。
16 色の選び方: Maximum Coverage と kmeans 8#
手引きの基準は「Maximum Coverage＋K-means 8、等重み RGB」です。
名前だけ見ると「8 色の k-means」に読めますが、そうではありません。
Pillow の C のソース（libImaging/Quant.c）を読むと、こうなっています。
Maximum Coverage（方式 1）は、
- 絵の中の色を、重複を除いた集合にする
- 全画素の平均の色を出し、そこからいちばん遠い色を 1 色目にする
- 以後は、すでに選んだ色のどれからも遠い（いちばん近い選択済みの色までの距離が最大の）色を、16 色になるまで足していく
画素の数は選び方に効きません。
1 画素しかない色でも、ほかから離れていれば選ばれます。
クラスタリングで言えば farthest-first traversal（Gonzalez の貪欲な k-center）と同じ形です。
暗い窓枠の黒や、灯りの明るい黄色のような端の色を取りこぼさない代わりに、面積の大きい中間の階調には色が足りなくなります。
そこで k-means で磨きます。
kmeans の引数は、群の数でも反復の回数でもありません。
Pillow は kmeans−1 を閾値として渡し、1 回の反復で属する色が変わった画素の数がその閾値以下になるまで繰り返します。
kmeans=8 は「入れ替わる画素が 7 以下になったら止める」です。
群の数は 16 のままです。
効き目を、今日測りました。
元の絵を同じ手順で 480×270 に縮め、網を置く前の 16 色の下地の誤差（RGB の二乗平均の平方根・0〜255 の目盛り）を比べたものです。2026-10-29 に測った値です。
港 縮めた絵 34,010 色 → median cut 6.84／Maximum Coverage 14.29／＋kmeans 8 5.73
防波堤 21,359 色 → 5.43／11.35／4.65
岬の高台 30,792 色 → 7.73／11.60／5.62
駐在所 38,287 色 → 8.97／16.44／7.35
番屋 58,995 色 → 13.88／16.51／8.69
潮見荘 44,441 色 → 13.11／16.79／7.31
Maximum Coverage だけでは、6 枚とも median cut より悪い。
磨くと、6 枚とも median cut より良くなります。
差が大きいのは番屋と潮見荘で、どちらも木と照明の暖かい色の階調が広い絵です。
1 枚あたりの時間は 0.17〜0.59 秒でした。
もう一つ確かめたこと。
今日、同じ手順で 16 色を作り直すと、6 枚とも完成の画像の 16 色と一致しました。
保存した改訂には、そのときの Pillow と NumPy の版（12.2.0・2.2.5）と、描いたコードの写しが入っています。
同じ版なら、同じ 16 色が出ます。
網の置き方: 2×2 の閾値の表#
下地のままだと、空や床の広い面が平らな色の帯になります。
そこに網を置きます。
第一章の 6 枚で使ったのは、design_local_halftone.py の 2×2 の網です。
条件は 4 つで、全部満たした画素だけを網の候補にします。
- 画像ごとに決めた矩形の中（480×270 の座標・端を含む）
- 縮めた元の絵で、上下左右の隣との差（RGB の各成分の差の最大）が 10 以下。輪郭の画素は網にしない
- その画素にいちばん近い 2 色の、成分の差の最大が 48 以下
- 2 色が同じ系統の色。各色から RGB の平均を引いたベクトルのコサインが 0.94 以上、またはどちらも無彩色（そのベクトルの長さが 12 未満）
候補の画素で、元の色を 2 色を結ぶ線に射影し、2 色目へどれだけ寄っているか（0〜0.5 に制限）を出します。
その値を、2×2 の閾値の表と比べます。
tile = np.array([[.125, .625], [.875, .375]])
changed = eligible & (tile[yy % 2, xx % 2] < fraction) & (second != before)
表の値は、2×2 の Bayer の表 [[0, 2], [3, 1]] を (i+0.5)/4 にしたものと同じです。
つまり ordered dithering そのもので、閾値の表が 2×2、使う 2 色が「その画素にいちばん近い 2 色」です。
寄り方が 0.5 までに制限されているので、使われるのは 0.125 と 0.375 の 2 か所だけで、2 色目は最大で 4 画素中 2 画素（市松）までです。
矩形は、画像ごとに制作の計画に書いてあります。
港 (0,0)–(479,70)・(60,150)–(420,225) 船・索具・倉庫の輪郭を保持。空と水面の階調
防波堤 (0,0)–(479,140) 灯台と防波堤の輪郭を保持。空と海の階調
岬の高台 (0,0)–(479,160) 雪の青灰色と海の光を保持。空と遠景の階調
駐在所 (100,175)–(479,269) 窓の寒色とストーブの暖色を保持。床の陰影
番屋 (0,0)–(479,35)・(0,190)–(479,269) 窓の寒色と木・照明の暖色を保持。天井と床の陰影
潮見荘 (0,0)–(479,30)・(80,170)–(440,269) 木と照明の暖色を保持。天井と床の階調
網を置いた画素の数（全 129,600 画素のうち）は、
潮見荘 4,356・番屋 5,896・港 4,568・駐在所 4,299・防波堤 11,026・岬の高台 9,721。
どれも、条件を満たした画素の 23.7〜26.2% です。
空の広い防波堤と高台で多く、室内は天井と床だけです。
置いた網は、色番号ごとの点の命令（pixels・幅 1）として、独立した層に保存します。
層を消せば、網の前に戻せます。
保存の前に、二つを機械で確かめています。
候補の外の画素が 1 つも変わっていないこと。
16 色の表が変わっていないこと。
一人でそろえるために決めたこと#
480×270・16 色という枠は、6 か所を同じ調子に見せるための制約として選びました。
絵ごとに描き手の癖を合わせる代わりに、
- 同じ解像度に縮める
- 同じ方法で 16 色を選ぶ
- 同じ規則で網を置く
- 最近傍の整数倍で戻す
の 4 つを全部の絵に当てます。
16 色は絵ごとに違います。
港・防波堤・高台は青みの灰が 16 段並び、潮見荘と番屋は茶と橙が中心です。
制作の計画は、画像ごとに残す色を書いています（潮見荘は「木と照明の暖色を保持」、高台は「雪の青灰色と海の光を保持」）。
共通なのは色の数と選び方で、色そのものではありません。
完成の条件も、手引きに表で決めてあります。
原寸 480×270・実際に使う色 16 以下・4 倍が 1920×1080・4 倍が原寸の最近傍と画素で一致・再読込して描き直すと保存の画像と一致。
今日、ゲームの Game/adv/bg/ にある 6 枚で確かめると、どれも 16 色で、4 画素おきに取った 480×270 を 4 倍にすると全画素が一致しました。
ファイルは 1 枚 37〜60 KB です。
美術としての採用は、別の行です。
制作室の記録では、6 枚とも状態は review のまま、担当の目視の評価欄は未記録です。
台帳の「検証 passed」は、上の機械の条件を通ったという意味で、絵として良いという意味ではありません。
名前どおりでない所 — color quantization#
一つ目、手引きの言葉と中身がずれています。
手引きは「自動ディザ」と「2 色網掛け」を書いています。
自動ディザは、16 色を写す段に強さ（0〜1）を付けて 4×4 の Bayer をかける機能で、実装はあります（2 色の選び方と 0.5 の制限は上と同じ）。
2 色網掛けは、制作室で人が範囲を指定して 25／50／75% のタイルを置く道具です。
けれど第一章の 6 枚では、自動ディザは 0、手の網掛けと手の仕上げは 0 命令でした。
網は全部、スクリプトが条件で選んだ画素に、2×2 の表で置いたものです。
この連載の T02 の表と計画書は「自動ディザと手の網掛けを分けて使う」と書いていましたが、この 6 枚についてはそうなっていません。
二つ目、ordered dithering の使い方が狭い。
ふつうは絵の全面に敷きます。
うちは矩形の中の、輪郭でも色の境目でもない画素だけです。
しかも 2 色の差が 48 以下の近い色どうしにしか使わないので、Bayer の表で表せる 5 段の濃さのうち、使っているのは 3 段（0・25%・50%）です。
誤差を減らすための網ではなく、平らな面に手触りを足すための網です。
実際、網を置くと RGB の誤差は少し上がります（港 5.73 → 5.88、防波堤 4.65 → 5.02）。
三つ目、Maximum Coverage という名前。
Pillow の名前で、論文の名前ではありません。
中身は farthest-first traversal の形ですが、Pillow がそう名乗っているわけではなく、そう読んだのはこちらです。
起点を平均の色にする所も、Gonzalez の方法（起点は任意の 1 点）とは違います。
四つ目、k-means の止め方。
kmeans=8 の 8 は、群の数でも反復の回数でもなく、止めるときの閾値です。
手引きの「K-means 8」を「8 色」と読まないでください。
五つ目、寒色の 16 色、とは言えない。
計画書と T02 は「寒色の 16 色」と書いていますが、16 色は絵ごとに選んでいて、宿と食堂は暖色が中心です。
弱点と、採らなかった案 — color quantization#
弱点の一つ目は、色を RGB の距離で測っていることです。
人の目には、同じ距離でも暗い所の差が大きく、青の差が小さく見えます。
Lab や Oklab で測れば選ぶ色が変わるはずですが、試していません。
道具の側には、輝度に寄せた重み（0.25・0.6・0.15）で測る形も残っていますが、6 枚では等重みを選んでいます。
二つ目、網の条件の数（10・48・0.94・12）と矩形は、手で決めた値です。
条件を変えれば網の量は変わり、どれが良いかは目で見るしかありません。
機械が確かめているのは「条件の外を変えていない」ことだけです。
三つ目、元の絵が変われば、全部作り直しです。
16 色を選ぶ段が絵全体の色の統計に依存するので、一部を描き直しても、16 色ごと変わることがあります。
仕上げ（色番号に依存する命令）のある改訂の上では、16 色を作り直せないように止めてあります。
採らなかった案は四つです。
どれも、採らなかった理由が記録に書いてあるわけではありません。ソースが選んでいる形と、手引きの決まりから読める理由です。
error diffusion（Floyd–Steinberg）。
Pillow の既定で、最初に試すならこれです。
ソースは、色を選ぶ段でも写す段でも、これをわざわざ外しています（dither=Image.Dither.NONE）。
誤差を隣へ配る方法は、細い線（索具、窓枠、灯台）のまわりに粒を散らしやすく、1 画素の違いが後ろへ伝わるので、決めた矩形の中だけにかけるのにも向きません。
決めた範囲だけに、毎回同じ模様を置ける ordered dithering の方が、この工程の「条件の外は 1 画素も変えない」という確かめ方と合います。
全部の絵に共通の 16 色。
絵どうしの調子はそろいやすくなります。
ただ、手引きは「画像ごとに配色・形・網掛けを調整する」と決めていて、16 色は絵ごとに選ぶ前提です。
宿と食堂の暖色と、港と高台の青灰を同じ 16 色で持つと、どちらの階調も減ります。
ゲームの中で毎回かけるフィルタ。
同じ絵を何度でも直せますが、何を見せたかが表示の側の設定に依存します。
手引きは、加工済みの PNG を納品して、ゲームの側では重ねて加工しない、と決めています。
16 色を 1 色ずつ手で選ぶこと。
いちばん絵になるのは、たぶんこれです。
けれど 1 人で全部の場所をそろえる、という目的とは逆向きです。
手引きの順番は「初回の自動減色を完成扱いせず、画像ごとに評価して、足りない所を直す」で、手で触るのは自動の結果を見た後です（特徴の色を 1 つ確保して、いちばん誤差の小さい枠と入れ替える命令もあります）。
検索語#
color image quantization median cut Heckbert
k-means color quantization
ordered dithering Bayer matrix
farthest-first traversal
『霧走町 流氷に眠る』の第一章の 6 か所は、ブラウザ版でそのまま見て、入力して回れます。無料で、プロフィールのリンクから。