有赞零售小票打印图片二值化方案
作者：王前
一、背景
小票打印是零售商家的基础功能，在小票信息中，必然会存在一些相关店铺的信息。比如，logo 、店铺二维码等。对于商家来说，上传 logo 及店铺二维码时，基本都是彩图，但是小票打印机基本都是只支持黑白二值图打印。为了商家的服务体验，我们没有对商家上传的图片进行要求，商家可以根据实际情况上传自己的个性化图片，因此就需要我们对商家的图片进行二值图处理后进行打印。
这次文章是对《有赞零售小票打印跨平台解决方案》中的图片的二值图处理部分的解决方案的说明。
二、图像二值化处理流程
图像二值化就是将图像上的像素点的灰度值（如果是 RGB 彩图，则需要先将像素点的 RGB 转成灰度值）设置为 0 或 255 ，也就是将整个图像呈现出明显的黑白效果的过程。
其中划分 0 和 255 的中间阈值 T 是二值化的核心，一个准确的阈值可以得到一个较好的二值图。
二值化整体流程图：
从上面的流程图中可以看出，获取灰度图和计算阈值 T 是二值化的核心步骤。
三、以前的解决方案
以前使用的方案是，首先将图像处理成灰度图，然后再基于 OTSU（大津法、最大类间方差法）算法求出分割 0 和 255 的阈值 T ，然后根据 T 对灰度值进行二值化处理，得到二值图像。
我们的所有算法都有使用 C 语言实现，目的为了跨平台通用性。
流程图：
灰度算法：
对于 RGB 彩色转灰度，有一个很著名的公式：
Gray = R * 0.299 + G * 0.587 + B * 0.114
这种算法叫做 Luminosity，也就是亮度算法。目前这种算法是最常用的，里面的三个数据都是经验值或者说是实验值。由来请参见 wiki 。
然而实际应用时，大家都希望避免低速的浮点运算，为了提高效率将上述公式变形成整数运算和移位运算。这里将采用移位运算公式：
Gray = (R * 38 + G * 75 + B * 15) >> 7
如果想了解具体由来，可以自行了解，这里不做过多解释。
具体实现算法如下：
/**
获取灰度图
@param bit_map 图像像素数组地址（ ARGB 格式）
@param width 图像宽
@param height 图像高
@return 灰度图像素数组地址
*/
int * gray_image(int *bit_map, int width, int height) {
double pixel_total = width * height; // 像素总数
if (pixel_total == 0) return NULL;
// 灰度像素点存储
int *gray_pixels = (int *)malloc(pixel_total * sizeof(int));
memset(gray_pixels, 0, pixel_total * sizeof(int));
int *p = bit_map;
for (u_int i = 0; i < pixel_total; i++, p++) {
// 分离三原色及透明度
u_char alpha = ((*p & 0xFF000000) >> 24);
u_char red = ((*p & 0xFF0000) >> 16);
u_char green = ((*p & 0x00FF00) >> 8);
u_char blue = (*p & 0x0000FF);
u_char gray = (red*38 + green*75 + blue*15) >> 7;
if (alpha == 0 && gray == 0) {
gray = 0xFF;
}
gray_pixels[i] = gray;
}
return gray_pixels;
}
该算法中，主要是为了统一各平台的兼容性，入参要求传入 ARGB 格式的 bitmap 。为什么使用 int 而不是用 unsigned int，是因为在 java 中没有无符号数据类型，使用 int 具有通用性。
OTSU 算法：
OTSU 算法也称最大类间差法，有时也称之为大津算法，由大津于 1979 年提出，被认为是图像分割中阈值选取的最佳算法，计算简单，不受图像亮度和对比度的影响，因此在数字图像处理上得到了广泛的应用。它是按图像的灰度特性，将图像分成背景和前景两部分。因方差是灰度分布均匀性的一种度量，背景和前景之间的类间方差越大，说明构成图像的两部分的差别越大，当部分前景错分为背景或部分背景错分为前景都会导致两部分差别变小。因此，使类间方差最大的分割意味着错分概率最小。
原理：
对于图像 I (x , y) ，前景（即目标）和背景的分割阈值记作 T ，属于前景的像素点数占整幅图像的比例记为 ω0 ，其平均灰度 μ0 ；背景像素点数占整幅图像的比例为 ω1 ，其平均灰度为 μ1 。图像的总平均灰度记为 μ ，类间方差记为 g 。
假设图像的背景较暗，并且图像的大小为 M × N ，图像中像素的灰度值小于阈值 T 的像素个数记作 N0 ，像素灰度大于等于阈值 T 的像素个数记作 N1 ，则有：
ω0 = N0 / M × N (1)
ω1 = N1 / M × N (2)
N0 + N1 = M × N (3)
ω0 + ω1 = 1 (4)
μ = ω0 * μ0 + ω1 * μ1 (5)
g = ω0 * (μ0 - μ)^2 + ω1 * (μ1 - μ)^2 (6)
将式 (5) 代入式 (6) ，得到等价公式：
g = ω0 * ω1 * (μ0 - μ1)^2 (7)
公式 (7) 就是类间方差计算公式，采用遍历的方法得到使类间方差 g 最大的阈值 T ，即为所求。
因为 OTSU 算法求阈值的基础是灰度直方图数据，所以使用 OTSU 算法的前两步：
1、获取原图像的灰度图
2、灰度直方统计
这里需要多次对图像进行遍历处理，如果每一步都单独处理，会增加不少遍历次数，所以这里做了步骤整合处理，减少不必要的遍历，提高性能。
具体实现算法如下：
/**
OTSU 算法获取二值图
@param bit_map 图像像素数组地址（ ARGB 格式）
@param width 图像宽
@param height 图像高
@param T 存储计算得出的阈值
@return 二值图像素数组地址
*/
int * binary_image_with_otsu_threshold_alg(int *bit_map, int width, int height, int *T) {
double pixel_total = width * height; // 像素总数
if (pixel_total == 0) return NULL;
unsigned long sum1 = 0; // 总灰度值
unsigned long sumB = 0; // 背景总灰度值
double wB = 0.0; // 背景像素点比例
double wF = 0.0; // 前景像素点比例
double mB = 0.0; // 背景平均灰度值
double mF = 0.0; // 前景平均灰度值
double max_g = 0.0; // 最大类间方差
double g = 0.0; // 类间方差
u_char threshold = 0; // 阈值
double histogram[256] = {0}; // 灰度直方图，下标是灰度值，保存内容是灰度值对应的像素点总数
// 获取灰度直方图和总灰度
int *gray_pixels = (int *)malloc(pixel_total * sizeof(int));
memset(gray_pixels, 0, pixel_total * sizeof(int));
int *p = bit_map;
for (u_int i = 0; i < pixel_total; i++, p++) {
// 分离三原色及透明度
u_char alpha = ((*p & 0xFF000000) >> 24);
u_char red = ((*p & 0xFF0000) >> 16);
u_char green = ((*p & 0x00FF00) >> 8);
u_char blue = (*p & 0x0000FF);
u_char gray = (red*38 + green*75 + blue*15) >> 7;
if (alpha == 0 && gray == 0) {
gray = 0xFF;
}
gray_pixels[i] = gray;
// 计算灰度直方图分布，Histogram 数组下标是灰度值，保存内容是灰度值对应像素点数
histogram[gray]++;
sum1 += gray;
}
// OTSU 算法
for (u_int i = 0; i < 256; i++)
{
wB = wB + histogram[i]; // 这里不算比例，减少运算，不会影响求 T
wF = pixel_total - wB;
if (wB == 0 || wF == 0)
{
continue;
}
sumB = sumB + i * histogram[i];
mB = sumB / wB;
mF = (sum1 - sumB) / wF;
g = wB * wF * (mB - mF) * (mB - mF);
if (g >= max_g)
{
threshold = i;
max_g = g;
}
}
for (u_int i = 0; i < pixel_total; i++) {
gray_pixels[i] = gray_pixels[i] <= threshold ? 0xFF000000:0xFFFFFFFF;
}
if (T) {
*T = threshold; // OTSU 算法阈值
}
return gray_pixels;
}
测试执行时间数据：
iPhone 6: imageSize：260, 260； OTSU 使用时间：0.005254； 5 次异步处理使用时间：0.029240
iPhone 6: imageSize：620, 284； OTSU 使用时间：0.029476； 5 次异步处理使用时间：0.050313
iPhone 6: imageSize：2560,1440； OTSU 使用时间：0.200595； 5 次异步处理使用时间：0.684509
经过测试，该算法处理时间都是毫秒级别的，而且一般我们的图片大小都不大，所以性能没问题。
处理后的效果：
经过 OTSU 算法处理过的二值图基本可以满足大部分商家 logo 。
不过对于实际场景来说还有些不足，比如商家的 logo 颜色差别比较大的时候，可能打印出来的图片会和商家意愿的不太一致。比如如下 logo ：
上面 logo 对于算法来说，黄色的灰度值比阈值小，所以二值化变成了白色，但是对于商家来说，logo 上红色框内信息缺失了一部分，可能不能满足商家需求。
- 存在问题总结
- 算法单一，对于不同图片处理结果可能与预期不一致
- 每次打印都对图片进行处理，没有缓存机制
四、新的解决方案
针对以前使用的方案中存在的两个问题，新的方案中加入了具体优化。
4.1 问题一 （算法单一，对于不同图片处理结果可能与预期不一致）
加入多算法求阈值 T ，然后根据每个算法得出的二值图和原图的灰度图进行对比，相识度比较高的作为最优阈值 T 。
流程图：
整个流程当中会并行三个算法进行二值图处理，同时获取二值图的图片指纹 hashCode ，与原图图片指纹 hashCode 进行对比，获取与原图最为相近的二值图作为最优二值图。
其中的 OTSU 算法上面已经说明，这次针对平均灰度算法和双峰平均值算法进行解析。
平均灰度算法：
平均灰度算法其实很简单，就是将图片灰度处理后，求一下灰度图的平均灰度。假设总灰度为 sum ，总像素点为 pixel_total ，则阈值 T ：
T = sum / pixel_total
具体实现算法如下：
/**
平均灰度算法获取二值图
@param bit_map 图像像素数组地址（ ARGB 格式）
@param width 图像宽
@param height 图像高
@param T 存储计算得出的阈值
@return 二值图像素数组地址
*/
int * binary_image_with_average_gray_threshold_alg(int *bit_map, int width, int height, int *T) {
double pixel_total = width * height; // 像素总数
if (pixel_total == 0) return NULL;
unsigned long sum = 0; // 总灰度
u_char threshold = 0; // 阈值
int *gray_pixels = (int *)malloc(pixel_total * sizeof(int));
memset(gray_pixels, 0, pixel_total * sizeof(int));
int *p = bit_map;
for (u_int i = 0; i < pixel_total; i++, p++) {
// 分离三原色及透明度
u_char alpha = ((*p & 0xFF000000) >> 24);
u_char red = ((*p & 0xFF0000) >> 16);
u_char green = ((*p & 0x00FF00) >> 8);
u_char blue = (*p & 0x0000FF);
u_char gray = (red*38 + green*75 + blue*15) >> 7;
if (alpha == 0 && gray == 0) {
gray = 0xFF;
}
gray_pixels[i] = gray;
sum += gray;
}
// 计算平均灰度
threshold = sum / pixel_total;
for (u_int i = 0; i < pixel_total; i++) {
gray_pixels[i] = gray_pixels[i] <= threshold ? 0xFF000000:0xFFFFFFFF;
}
if (T) {
*T = threshold;
}
return gray_pixels;
}
双峰平均值算法：
此方法实用于具有明显双峰直方图的图像，其寻找双峰的谷底作为阈值，但是该方法不一定能获得阈值，对于那些具有平坦的直方图或单峰图像，该方法不合适。该函数的实现是一个迭代的过程，每次处理前对直方图数据进行判断，看其是否已经是一个双峰的直方图，如果不是，则对直方图数据进行半径为 1（窗口大小为 3 ）的平滑，如果迭代了一定的数量比如 1000 次后仍未获得一个双峰的直方图，则函数执行失败，如成功获得，则最终阈值取双峰的平均值作为阈值。因此实现该算法应有的步骤：
1、获取原图像的灰度图
2、灰度直方统计
3、平滑直方图
4、求双峰平均值作为阈值 T
其中第三步平滑直方图的过程是一个迭代过程，具体流程图：
具体实现算法如下：
// 判断是否是双峰直方图
int is_double_peak(double *histogram) {
// 判断直方图是存在双峰
int peak_count = 0;
for (int i = 1; i < 255; i++) {
if (histogram[i - 1] < histogram[i] && histogram[i + 1] < histogram[i]) {
peak_count++;
if (peak_count > 2) return 0;
}
}
return peak_count == 2;
}
/**
双峰平均值算法获取二值图
@param bit_map 图像像素数组地址（ ARGB 格式）
@param width 图像宽
@param height 图像高
@param T 存储计算得出的阈值
@return 二值图像素数组地址
*/
int * binary_image_with_average_peak_threshold_alg(int *bit_map, int width, int height, int *T) {
double pixel_total = width * height; // 像素总数
if (pixel_total == 0) return NULL;
// 灰度直方图，下标是灰度值，保存内容是灰度值对应的像素点总数
double histogram1[256] = {0};
double histogram2[256] = {0}; // 求均值的过程会破坏前面的数据，因此需要两份数据
u_char threshold = 0; // 阈值
// 获取灰度直方图
int *gray_pixels = (int *)malloc(pixel_total * sizeof(int));
memset(gray_pixels, 0, pixel_total * sizeof(int));
int *p = bit_map;
for (u_int i = 0; i < pixel_total; i++, p++) {
// 分离三原色及透明度
u_char alpha = ((*p & 0xFF000000) >> 24);
u_char red = ((*p & 0xFF0000) >> 16);
u_char green = ((*p & 0x00FF00) >> 8);
u_char blue = (*p & 0x0000FF);
u_char gray = (red*38 + green*75 + blue*15) >> 7;
if (alpha == 0 && gray == 0) {
gray = 0xFF;
}
gray_pixels[i] = gray;
// 计算灰度直方图分布，Histogram数组下标是灰度值，保存内容是灰度值对应像素点数
histogram1[gray]++;
histogram2[gray]++;
}
// 如果不是双峰，则通过三点求均值来平滑直方图
int times = 0;
while (!is_double_peak(histogram2)) {
times++;
if (times > 1000) { // 这里使用 1000 次，考虑到过多次循环可能会存在性能问题
return NULL; // 似乎直方图无法平滑为双峰的，返回错误代码
}
histogram2[0] = (histogram1[0] + histogram1[0] + histogram1[1]) / 3; // 第一点
for (int i = 1; i < 255; i++) {
histogram2[i] = (histogram1[i - 1] + histogram1[i] + histogram1[i + 1]) / 3; // 中间的点
}
histogram2[255] = (histogram1[254] + histogram1[255] + histogram1[255]) / 3; // 最后一点
memcpy(histogram1, histogram2, 256 * sizeof(double)); // 备份数据，为下一次迭代做准备
}
// 求阈值T
int peak[2] = {0};
for (int i = 1, y = 0; i < 255; i++) {
if (histogram2[i - 1] < histogram2[i] && histogram2[i + 1] < histogram2[i]) {
peak[y++] = i;
}
}
threshold = (peak[0] + peak[1]) / 2;
for (u_int i = 0; i < pixel_total; i++) {
gray_pixels[i] = gray_pixels[i] <= threshold ? 0xFF000000:0xFFFFFFFF;
}
if (T) {
*T = threshold;
}
return gray_pixels;
}
测试执行时间数据：
iPhone 6: imageSize：260, 260； average_peak 使用时间：0.035254
iPhone 6: imageSize：800, 800； average_peak 使用时间：0.101282
经过测试，该算法在图片比较小的时候，还算可以，如果图片比较大会存在较大性能消耗，而且根据图片色彩分布不同也可能造成多次循环平滑，也会影响性能。对于 logo 来说，我们处理的时候做了压缩，一般都是很大，所以处理时间也在可以接受返回内，而且进行处理和对比时，是在异步线程中，不会影响主流程。
图片指纹 hashCode ：
图片指纹 hashCode ，可以理解为图片的唯一标识。一个简单的图片指纹生成步骤需要以下几步：
1、图片缩小尺寸一般缩小到 8 * 8 ，一共 64 个像素点。
2、将缩小的图片转换成灰度图。
3、计算灰度图的平均灰度。
4、灰度图的每个像素点的灰度与平均灰度比较。大于平均灰度，记为 1 ；小于平均灰度，记为 0。
5、计算哈希值，第 4 步的结果可以构成一个 64 为的整数，这个 64 位的整数就是该图片的指纹 hashCode 。
6、对比不同图片生成的指纹 hashCode ，计算两个 hashCode 的 64 位中有多少位不一样，即“汉明距离”，差异越少图片约相近。
由于使用该算法生成的图片指纹具有差异性比较大，因为对于 logo 来说处理后的二值图压缩到 8 * 8 后的相似性很大，所以使用 8 * 8 生成 hashCode 误差性比较大，经过试验，确实如此。所以，在此基础上，对上述中的 1、5、6 步进行了改良，改良后的这几步为：
1、图片缩小尺寸可自定义（必须是整数），但是最小像素数要为 64 个，也就是 width * height >= 64 。建议为 64 的倍数，为了减少误差。
5、哈希值不是一个 64 位的整数，而是一个存储 64 位整数的数组，数组的长度就是像素点数量对 64 的倍数（取最大的整数倍）。这样每生成一个 64 位的 hashCode 就加入到数组中，该数组就是图片指纹。
6、对比不同指纹时，遍历数组，对每一个 64 为整数进行对比不同位数，最终结果为，每一个 64 位整数的不同位数总和。
在我们对商家 logo 测试实践中发现，采用 128 * 128 的压缩，可以得到比较满意的结果。
最优算法为 OTSU 算法例子：
最优算法为平均灰度算法例子：
最优算法为双峰均值算法例子：
实际实验中，发现真是中选择双峰均值的概率比较低，也就是绝大多数的 logo 都是在 OTSU 和平均灰度两个算法之间选择的。所以，后续可以考虑加入选择统计，如果双峰均值概率确实特别低且结果与其他两种差不多大，那就可以去掉该方法。
4.2 问题二 （每次打印都对图片进行处理，没有缓存机制）
加入缓存机制，一般店铺的 logo 和店铺二维码都是固定的，很少会更换，所以，在进入店铺和修改店铺二维码时可以对其进行预处理，并缓存处理后的图片打印指令，后续打印时直接拿缓存使用即可。
由于缓存的内容是处理后的打印指令字符串，所以使用 NSUserDefaults 进行存储。
缓存策略流程图：
这里面为什么只有修改店铺二维码，而没有店铺 logo ？因为在我们 app 中，logo 是不可修改的，只能在 pc 后台修改，而登录店铺后，本地就可以直接拿到店铺信息；店铺二维码是在小票模板设置里自行上传的图片，所以商家在 app 中是可以自行修改店铺二维码的。
打印时图片处理流程图：
在新流程中，如果缓存中没有查到，则会走老方案去处理图片。原因是考虑到，这时候是商家实时打印小票，如果选用新方案处理，恐怕时间会加长，使用户体验降低。老方案已经在线上跑了很久，所以使用老的方案处理也问题不大。
五、未来期望与规划
在后续规划中加入几点优化：
- 添加新流程处理统计，对商家 logo 和店铺二维码处理后的最优算法进行统计，为后续优化做数据准备。
- 处理后的结果如果商家不满意，商家可以自主选择处理二值图的阈值 T ，达到满意为止。
- 图片更新不及时问题，PC 后台修改了图片无法及时更新本地缓存。
- 图片精细化处理，针对二维码可以采用分块处理算法。
其中第二点，商家自主选择阈值 T ，预览效果如下：
#参考链接
- 灰度计算公式, by zyl910
- 大津算法, by wiki
- 图像处理算法, by laviewpbt