从直接填格子到筛选图案：头像生成这部分是怎样改过来的—— gdenticon 重构日志（三）

从直接填格子到筛选图案：头像生成这部分是怎样改过来的——gdenticon重构日志（三）

上一期对比 v1 和 v2 时，改动最明显的是生成、编码和保存的边界。头像内部的算法却不是到了 v2 才突然换了一套。哈希熵流、镜像网格、图案筛选和对比度配色在 v1 已经存在，v2 主要是把它们从model.Image和WritePNG那条固定链路里重新接出来。

不过，这不等于头像生成从一开始就是现在这样。更早的实现基本是摘要有一位，网格就填一格；颜色也只是从一个固定亮度区间里取值。它能稳定生成头像，但一批结果放在一起时，问题很直观：有些图案挤成大色块，有些散成很多小块，浅色在白底上也不够清楚。

所以这一部分实际经历了两段变化：先把早期的直接映射补成一条带筛选和视觉约束的生成链路，再在 v2 中保留这套核心，把它放回更清楚的架构边界里。

单纯把哈希里的 0 和 1 依次填进格子，其实已经能生成头像。早期实现就是这样做的。问题是哈希只负责把比特分布开，并不知道哪一张图看起来舒服。它可能刚好给出一大片色块，也可能把前景拆成许多互不相连的小点。

现在的balanced模式没有换掉这套基础，而是在它外面加了一层确定性的候选筛选。代码里做的事情可以概括成一句话：把摘要当作一条可以继续延伸的熵流，依次生成镜像网格，遇到太空、太满或太碎的结果就继续取下一张，直到找到合适的候选。

这里的筛选会改变图案分布，但不会引入随机数。只要输入和选项不变，候选顺序、最终选中的网格和颜色都会保持一致。

没有改掉的基础：摘要和镜像网格

Generate会先用选定的摘要函数处理原始字符串。默认是 MD5，也可以换成 SHA-256 等其他实现：

digestFunc:=opts.DigestifdigestFunc==nil{digestFunc=MD5}digest:=digestFunc(id)

这里使用摘要不是为了保存密码，也不依赖 MD5 的抗碰撞安全性。我需要的是把任意长度的输入稳定地变成一组分布较均匀的字节。同一个id得到相同摘要，头像也就有了可重复生成的起点。

网格小时，一份摘要通常够用。可一旦网格变大，或者后来的balanced连续丢掉几个候选，固定长度的摘要迟早会读完。直接从头循环会让后面的图案重复，所以熵流用一个计数器继续派生新的数据块：

func(e*entropy)extend(){e.counter++varc[8]bytebinary.BigEndian.PutUint64(c[:],e.counter)h:=sha256.New()h.Write(e.seed)h.Write(c[:])e.block=h.Sum(nil)e.bit=0}

第一块直接使用原始摘要，读完后再计算SHA-256(seed || counter)。计数器按大端序写入 8 个字节，因此扩展过程没有依赖平台字节序。它不是真正的随机数生成器，也不需要是；它只要为同一份种子稳定地产生足够多的后续比特。

每次取值时，代码用位移和掩码从高位开始读取：

b:=e.block[e.bit/8]shift:=7-uint(e.bit%8)e.bit++returnb>>shift&1==1

这一位为 1 就填充格子，为 0 就留作背景。到这里还没有图片尺寸，也没有 PNG 或 SVG，只有逻辑网格需要的布尔值。

镜像网格也不是 v2 才加入的。v1 已经只读取左半边，再把结果写到右侧对应位置：

identicon 常见的对称感来自水平镜像。实现时没必要先生成完整网格再翻转一遍，只需要为每行读取左半边，再把结果写到对应的右侧位置：

cols:=sizeifmirror{cols=(size+1)/2}forrow:=rangesize{forcol:=rangecols{if!e.Bool(){continue}cells[row*size+col]=truecells[row*size+size-1-col]=true}}

(size + 1) / 2同时处理奇数和偶数网格。以 5×5 为例，每行只读取 3 位；中间列映射到自己，不会多消耗一次熵。关闭镜像后，代码会读取完整的size × size个格子，其他流程不变。

镜像能让图案更容易形成轮廓，却不能保证结果一定好看。连续很多个 1 仍然会铺成大色块，零散的 1 也可能彼此完全断开。这个问题不在渲染阶段，放大、换颜色或者改成 SVG 都不会改变格子本身。

第一次真正改变效果：从直接接受到筛选候选

早期生成一张网格就直接使用，没有好坏判断。后面没有删掉这种行为，而是把它保留成classic：摘要位怎样排列，网格就怎样落下来。它消耗的比特少，也不会为了视觉结果重试。

新加的balanced才会检查候选。它先处理两个极端情况：全空和全满直接放弃。对于 3×3 及以上的网格，填充比例还要落在 32% 到 68% 之间。

filled:=filledCells(cells)iffilled==0||filled==len(cells){returntrue}ifsize>=minBandSize{permille:=filled*1000/len(cells)ifpermille<minDensityPermille||permille>maxDensityPermille{returntrue}}

代码用千分比和整数计算，不需要为了两个阈值引入浮点数。32% 和 68% 也不是一条放之四海皆准的审美标准，只是当前实现给默认效果划出的范围。后面如果调整它，应该用固定样本和测试来比较，而不是只凭某几张图的感觉。

只看密度还不够。两个网格都填了四成，第一张可能连成一片，第二张却散成七八个小岛。于是筛选还会计算前景格子的四连通块：只有上下左右相邻才算连在一起，对角接触不算。

实现里用栈遍历每个尚未访问的前景格子。找到一个新的起点，连通块数量就加一，再把与它相连的格子全部标记掉。这部分本质上是一次深度优先搜索。

当前的碎片规则相对克制：连通块至少有 4 个，并且平均每块不到 2 个前景格子，才把候选判为过碎。这样不会因为图案里正常出现两三个独立部分就全部重画。

blocks:=blocks(cells,size)returnblocks>=4&&blocks*2>filled

不是一直重画：拒绝采样需要兜底

如果候选不合格，balanced会继续从同一条熵流读取比特，生成下一张。因为熵流的扩展过程是确定的，这里的重试仍然可复现。这种做法可以看成有上限的拒绝采样：不符合接受条件就拒绝，再看下一份样本。

不过，不能为了等一张合格的图无限循环。当前上限是 32 次：

forattempt:=rangeattempts{cells:=grid(e,size,mirror)if!degenerate(cells,size){returncells}ifpenalty:=visualPenalty(cells,size);attempt==0||penalty<bestPenalty{best,bestPenalty=cells,penalty}}returnbest

这里有个容易被忽略的小问题：32 次都没通过时，直接返回最后一张并不合理，最后一次只是碰巧排在末尾，不代表它更接近接受范围。所以每次拒绝时还会计算惩罚值，最终保留其中问题最少的一张。

惩罚分成两部分：填充比例超出 32%–68% 的距离，以及碎片程度超出规则的幅度。全空或全满直接给一个较大的固定值。这个分数只用于失败后的兜底排序，不参与已经合格候选之间的选美；第一张过关就会立即返回。

我比较在意这一点。筛选的目标是挡掉明显极端的结果，不是把所有头像都压成同一种轮廓。如果评分参与每一次候选竞争，最后很可能总是偏向某类规整图案，输入之间的差异反而被磨平了。

第二个变化：颜色不再直接使用固定亮度区间

网格只决定哪些位置填充，还没有决定填什么颜色。早期实现已经没有直接把三个摘要字节当作 RGB，而是从独立种子中计算 HSL。不过当时的亮度仍由摘要在 0.58 到 0.72 之间直接选择：

lightness:=0.58+0.14*float64(seed[3])/255

这段代码简单，也能让颜色保持稳定，问题是相同 HSL 亮度并不等于人眼看到的亮度相同。黄色会比蓝色、紫色亮很多。结果就是某些颜色在白底上很清楚，有些则容易发虚。

gdenticon没有让颜色和网格继续共用同一段比特，而是先从原始摘要派生一份专门用于配色的种子：

consttagColor=0x50funcderive(seed[]byte,tagbyte)[]byte{h:=sha256.New()h.Write(seed)h.Write([]byte{tag})returnh.Sum(nil)}

这一步属于域分离。原始摘要相同，但在末尾加上用途标记后重新计算，就能得到一条独立的颜色数据。以后如果还要从同一摘要派生其他参数，也可以给它另一个标记，不需要和网格争抢固定位置的字节。

颜色使用 HSL 表示。前两个字节决定色相，第三个字节把饱和度限制在 45% 到 63% 左右：

seed:=derive(digest,tagColor)hue:=float64(binary.BigEndian.Uint16(seed))/65536saturation:=0.45+0.18*float64(seed[2])/255want:=minContrast+(maxContrast-minContrast)*float64(seed[3])/255

改进后的实现不再让摘要直接决定亮度。

所以第四个字节决定的不是 HSL 亮度，而是目标对比度。当前范围是 3.0 到 4.5，再根据色相和饱和度反过来求合适的亮度。

从固定亮度改成求目标对比度

这里采用的是 WCAG 相对亮度和对比度公式。白色背景的相对亮度固定，前景色越暗，两者的对比度越高。对于已经确定的色相和饱和度，可以在 0 到 1 的亮度范围里做二分查找：

funclightnessAt(hue,saturation,targetfloat64,abovebool)float64{background:=luminance(DefaultBackground)lo,hi:=0.0,1.0forrange12{mid:=(lo+hi)/2ifcontrastOf(colourLuminance(hue,saturation,mid),background)>target{lo=mid}else{hi=mid}}ifabove{returnlo}returnhi}

二分 12 次不是为了追求一个理论上的无限精度。最终图片只保存 8 位颜色通道，继续细分也不会产生同样数量的新颜色。更重要的是，对比度计算使用的是已经量化成 8 位 RGB 后的结果，而不是量化前的 HSL 浮点数。这样测试约束的颜色和真正写进图片的颜色是一回事。

量化会让对比度随亮度变化的曲线出现台阶。有时刚跨过目标值，实际颜色仍可能超过上限，所以代码会再检查一次；高于 4.5 时，从另一侧寻找不超过上限的颜色。

自动配色解决的是默认白底上的可读性，不代表所有背景都能直接套用这组结果。调用方如果传入自定义背景，也可以同时传入固定前景色。当前HueColor的求解仍然以DefaultBackground为参照，这算是现阶段明确存在的边界。

第三个变化：小尺寸图片不能只做整数截断

得到Icon时，里面保存的仍然是GridSize × GridSize个布尔值。以 5×5 网格为例，它只知道第几个格子应该填色，并不知道一张 17×17 或 256×256 的图片里每个格子占多少像素。

为了留出大约半个格子的边距，早期实现用size / (gridSize + 1)计算格子宽度：

cell:=size/(gridSize+1)

默认 256 像素下看不出太大问题，但尺寸变小时，整数截断少掉的一个像素会被每个格子重复放大。以 16 像素画布和 5×5 网格为例，每格只能拿到 2 像素，整块图案宽 10 像素，只占画布的 62.5%。这不是生成算法的问题，而是网格落到像素时缩得太多。

现在的计算改成整数四舍五入：

cell:=(2*size+gridSize+1)/(2*(gridSize+1))ifroom:=size/gridSize;cell>room{cell=room}

room还会保证极小图片里所有格子仍然放得下。

还有一个更隐蔽的问题：图片尺寸不一定能被网格整除。左右两边如果各自做一次整数除法，原本对称的逻辑网格可能落成相差一个像素的矩形。现在右半边的边界不重新计算，而是直接由左侧对应边界反推：

funcedge(size,gridSize,iint)int{ifi>gridSize/2{returnsize-edge(size,gridSize,gridSize-i)}// 计算左半边边界}

例如左侧某条网格线位于x，对应的右侧网格线就是size - x。这样无论输出是 17、255 还是 256 像素，只要逻辑图案镜像，最终像素也会保持镜像。

同一个edge同时供栅格渲染和 SVG 使用。PNG、JPEG 等格式会把前景格子画到image.NRGBA，SVG 则直接把同样的边界写成<rect>。因此两种输出不会各自维护一套位置算法。

v1 到 v2：算法保留，周围的接口换了

到 v1.0.0 时，前面这些主要能力已经齐了：可扩展熵流、镜像网格、classic与balanced、密度和四连通块筛选、对比度配色，以及对称的像素边界。v2 没有把它们包装成一套新算法，也没有为了版本升级强行改变同一输入的图案。

真正变化的是它们周围的接口。v1 的Generate接收混合了生成与输出参数的model.Image，返回model.Icon；PNG 入口再从原始id重新调用Generate：

// v1funcGenerate(idstring,img model.Image)(model.Icon,error)funcWritePNG(w io.Writer,idstring,img model.Image)error

v2 把配置换成GenerateOptions，把Icon作为明确的中间结果交给统一的Write：

// v2funcGenerate(idstring,opts GenerateOptions)(Icon,error)funcWrite(w io.Writer,icon Icon,opts WriteOptions)error

因此，头像内部仍然按同样的顺序工作：字符串变成摘要，摘要生成并筛选镜像网格，独立种子决定颜色，逻辑格子再落到像素或 SVG 矩形。不同的是，这条算法不再被某一个 PNG 保存入口包在里面。

这个对比对我来说比单纯列出当前有多少函数更重要。早期到 v1，解决的是生成效果和小尺寸渲染；v1 到 v2，解决的是同一套能力怎样被 CLI、多格式和不同输出目标复用。两次改动碰的不是同一个问题。

它还不是一套已经没有问题的实现。balanced最坏会生成并检查 32 个候选，每次四连通块检查都会分配seen和遍历栈；自动配色以默认白底为目标，自定义背景仍需要调用方自己处理前景色。这些限制先留在这里，后面有了 benchmark 和更完整的样本，再决定该先减少计算，还是调整规则本身。

下一篇

下一篇会继续拆balanced这条链路，但重点不再是图案怎样生成，而是一次生成到底做了多少重复工作。当前代码在候选不合格时，会先在degenerate中统计填充数量和四连通块，随后又在visualPenalty中重新统计一次；每个候选还会新建网格、seen和遍历栈。

我会先补 benchmark，把classic与balanced分开测清楚，再记录候选通常需要尝试几次、时间主要花在哪、每次生成产生多少分配。数据出来以后，再决定是合并候选分析、复用临时缓冲区，还是保留现在更直白的实现。没有测量结果之前，这些都只算重构目标，不提前写成性能提升。

项目地址：

• GitHub：hourinX/gdenticon
• Gitee：hourinX/gdenticon