【第2198期】前端图片主题色提取

前言

这期【第2197期】如何为多元化的产品场景选择完美的色彩组合？ 谈到的智能取色场景，现在来谈谈如何通过前端技术来实现这个功能。今日前端早读课文章由腾讯QQ音乐@jordiawang授权分享。

正文从这开始~~

图片主题色在图片所占比例较大的页面中，能够配合图片起到很好视觉效果，给人一种和谐、一致的感觉。同时也可用在图像分类，搜索识别等方面。通常主题色的提取都是在后端完成的，前端将需要处理的图片以链接或id的形式提供给后端，后端通过运行相应的算法来提取出主题色后，再返回相应的结果。

这样可以满足大多数展示类的场景，但对于需要根据用户“定制”、“生成”的图片，这样的方式就有了一个上传图片---->后端计算---->返回结果的时间，等待时间也许就比较长了。由此，我尝试着利用 canvas在前端进行图片主题色的提取。

一、主题色算法

目前比较常用的主题色提取算法有：最小差值法、中位切分法、八叉树算法、聚类、色彩建模法等。其中聚类和色彩建模法需要对提取函数和样本、特征变量等进行调参和回归计算，用到 python的数值计算库 numpy和机器学习库 scikit-learn，用 python来实现相对比较简单，而目前这两种都没有成熟的js库，并且js本身也不擅长回归计算这种比较复杂的计算。我也就没有深入的研究，而主要将目光放在了前面的几个颜色量化算法上。

而最小差值法是在给定给定调色板的情况下找到与色差最小的颜色，使用的场景比较小，所以我主要看了中位切分法和八叉树算法，并进行了实践。

中位切分法

中位切分法通常是在图像处理中降低图像位元深度的算法，可用来将高位的图转换位低位的图，如将24bit的图转换为8bit的图。我们也可以用来提取图片的主题色，其原理是是将图像每个像素颜色看作是以R、G、B为坐标轴的一个三维空间中的点，由于三个颜色的取值范围为0~255，所以图像中的颜色都分布在这个颜色立方体内，如下图所示。

之后将RGB中最长的一边从颜色统计的中位数一切为二，使得到的两个长方体所包含的像素数量相同，如下图所示

重复这个过程直到切出长方体数量等于主题色数量为止，最后取每个长方体的中点即可。

在实际使用中如果只是按照中点进行切割，会出现有些长方体的体积很大但是像素数量很少的情况。解决的办法是在切割前对长方体进行优先级排序，排序的系数为体积 * 像素数。这样就可以基本解决此类问题了。

八叉树算法

八叉树算法也是在颜色量化中比较常见的，主要思路是将R、G、B通道的数值做二进制转换后逐行放下，可得到八列数字。如 #FF7880转换后为

1. R: 1111 1111

2. G: 0111 1000

3. B: 0000 0000

再将RGB通道逐列粘合，可以得到8个数字，即为该颜色在八叉树中的位置，如图。

在将所有颜色插入之后，再进行合并运算，直到得到所需要的颜色数量为止。

在实际操作中，由于需要对图像像素进行遍历后插入八叉树中，并且插入过程有较多的递归操作，所以比中位切分法要消耗更长的时间。

二、中位切分法实践

根据之前的介绍和网上的相关资料，此处贴上我自己理解实现的中位切分法代码，并且找了几张图片将结果与QQ音乐已有的魔法色相关算法进行比较，图一为中位切分法结果，图二为后台cgi返回结果

图一

图二

可以看到有一定的差异，但是差值相对都还比较小的，处理速度在pc上面还是比较快的，三张图分别在70ms,100ms,130ms左右。这里贴上代码，待后续批量处理进行对比之后再分析。

1. (function () {

2. /**

3. * 颜色盒子类

4. *

5. * @param {Array} colorRange [[rMin, rMax],[gMin, gMax], [bMin, bMax]] 颜色范围

6. * @param {any} total 像素总数, imageData / 4

7. * @param {any} data 像素数据集合

8. */

9. function ColorBox(colorRange, total, data) {

10. this.colorRange = colorRange;

11. this.total = total;

12. this.data = data;

13. this.volume = (colorRange[0][1] - colorRange[0][0]) * (colorRange[1][1] - colorRange[1][0]) * (colorRange[2][1] - colorRange[2][0]);

14. this.rank = this.total * (this.volume);

15. }

16. ColorBox.prototype.getColor = function () {

17. var total = this.total;

18. var data = this.data;

19. var redCount = 0,

20. greenCount = 0,

21. blueCount = 0;

22. for (var i = 0; i < total; i++) {

23. redCount += data[i * 4];

24. greenCount += data[i * 4 + 1];

25. blueCount += data[i * 4 + 2];

26. }

27. return [parseInt(redCount / total), parseInt(greenCount / total), parseInt(blueCount / total)];

28. }

29. // 获取切割边

30. function getCutSide(colorRange) { // r:0,g:1,b:2

31. var arr = [];

32. for (var i = 0; i < 3; i++) {

33. arr.push(colorRange[i][1] - colorRange[i][0]);

34. }

35. return arr.indexOf(Math.max(arr[0], arr[1], arr[2]));

36. }

37. // 切割颜色范围

38. function cutRange(colorRange, colorSide, cutValue) {

39. var arr1 = [];

40. var arr2 = [];

41. colorRange.forEach(function (item) {

42. arr1.push(item.slice());

43. arr2.push(item.slice());

44. })

45. arr1[colorSide][1] = cutValue;

46. arr2[colorSide][0] = cutValue;

47. return [arr1, arr2];

48. }

49. // 找到出现次数为中位数的颜色

50. function getMedianColor(colorCountMap, total) {

51. var arr = [];

52. for (var key in colorCountMap) {

53. arr.push({

54. color: parseInt(key),

55. count: colorCountMap[key]

56. })

57. }

58. var sortArr = __quickSort(arr);

59. var medianCount = 0;

60. var medianColor = 0;

61. var medianIndex = Math.floor(sortArr.length / 2)

62. for (var i = 0; i <= medianIndex; i++) {

63. medianCount += sortArr[i].count;

64. }

65. return {

66. color: parseInt(sortArr[medianIndex].color),

67. count: medianCount

68. }

69. // 另一种切割颜色判断方法，根据数量和差值的乘积进行判断，自己试验后发现效果不如中位数方法，但是少了排序，性能应该有所提高

70. // var count = 0;

71. // var colorMin = arr[0].color;

72. // var colorMax = arr[arr.length - 1].color

73. // for (var i = 0; i < arr.length; i++) {

74. // count += arr[i].count;

75. // var item = arr[i];

76. // if (count * (item.color - colorMin) > (total - count) * (colorMax - item.color)) {

77. // return {

78. // color: item.color,

79. // count: count

80. // }

81. // }

82. // }

83. return {

84. color: colorMax,

85. count: count

86. }

87. function __quickSort(arr) {

88. if (arr.length <= 1) {

89. return arr;

90. }

91. var pivotIndex = Math.floor(arr.length / 2),

92. pivot = arr.splice(pivotIndex, 1)[0];

93. var left = [],

94. right = [];

95. for (var i = 0; i < arr.length; i++) {

96. if (arr[i].count <= pivot.count) {

97. left.push(arr[i]);

98. }

99. else {

100. right.push(arr[i]);

101. }

102. }

103. return __quickSort(left).concat([pivot], __quickSort(right));

104. }

105. }

106. // 切割颜色盒子

107. function cutBox(colorBox) {

108. var colorRange = colorBox.colorRange,

109. cutSide = getCutSide(colorRange),

110. colorCountMap = {},

111. total = colorBox.total,

112. data = colorBox.data;

113. // 统计出各个值的数量

114. for (var i = 0; i < total; i++) {

115. var color = data[i * 4 + cutSide];

116. if (colorCountMap[color]) {

117. colorCountMap[color] += 1;

118. }

119. else {

120. colorCountMap[color] = 1;

121. }

122. }

123. var medianColor = getMedianColor(colorCountMap, total);

124. var cutValue = medianColor.color;

125. var cutCount = medianColor.count;

126. var newRange = cutRange(colorRange, cutSide, cutValue);

127. var box1 = new ColorBox(newRange[0], cutCount, data.slice(0, cutCount * 4)),

128. box2 = new ColorBox(newRange[1], total - cutCount, data.slice(cutCount * 4))

129. return [box1, box2];

130. }

131. // 队列切割

132. function queueCut(queue, num) {

133. while (queue.length < num) {

134. queue.sort(function (a, b) {

135. return a.rank - b.rank

136. });

137. var colorBox = queue.pop();

138. var result = cutBox(colorBox);

139. queue = queue.concat(result);

140. }

141. return queue.slice(0, 8)

142. }

143. function themeColor(img, callback) {

144. var canvas = document.createElement('canvas'),

145. ctx = canvas.getContext('2d'),

146. width = 0,

147. height = 0,

148. imageData = null,

149. length = 0,

150. blockSize = 1,

151. cubeArr = [];

152. width = canvas.width = img.width;

153. height = canvas.height = img.height;

154. ctx.drawImage(img, 0, 0, width, height);

155. imageData = ctx.getImageData(0, 0, width, height).data;

156. var total = imageData.length / 4;

157. var rMin = 255,

158. rMax = 0,

159. gMin = 255,

160. gMax = 0,

161. bMin = 255,

162. bMax = 0;

163. // 获取范围

164. for (var i = 0; i < total; i++) {

165. var red = imageData[i * 4],

166. green = imageData[i * 4 + 1],

167. blue = imageData[i * 4 + 2];

168. if (red < rMin) {

169. rMin = red;

170. }

171. if (red > rMax) {

172. rMax = red;

173. }

174. if (green < gMin) {

175. gMin = green;

176. }

177. if (green > gMax) {

178. gMax = green;

179. }

180. if (blue < bMin) {

181. bMin = blue;

182. }

183. if (blue > bMax) {

184. bMax = blue;

185. }

186. }

187. var colorRange = [[rMin, rMax], [gMin, gMax], [bMin, bMax]];

188. var colorBox = new ColorBox(colorRange, total, imageData);

189. var colorBoxArr = queueCut([colorBox], 8);

190. var colorArr = [];

191. for (var j = 0; j < colorBoxArr.length; j++) {

192. colorBoxArr[j].total && colorArr.push(colorBoxArr[j].getColor())

193. }

194. callback(colorArr);

195. }

196. window.themeColor = themeColor

197. })()

三、八叉树算法实践

也许是我算法实现的问题，使用八叉树算法得到的最终结果并不理想，所消耗的时间相对于中位切分法也长了不少，平均时间分别为160ms,250ms,400ms还是主要看八叉树算法吧...同样贴上代码

1. (function () {

2. var OctreeNode = function () {

3. this.isLeaf = false;

4. this.pixelCount = 0;

5. this.red = 0;

6. this.green = 0;

7. this.blue = 0;

8. this.children = [null, null, null, null, null, null, null, null];

9. this.next = null;

10. }

11. var root = null,

12. leafNum = 0,

13. colorMap = null,

14. reducible = null;

15. function createNode(index, level) {

16. var node = new OctreeNode();

17. if (level === 7) {

18. node.isLeaf = true;

19. leafNum++;

20. } else {

21. // 将其丢到第 level 层的 reducible 链表中

22. node.next = reducible[level];

23. reducible[level] = node;

24. }

25. return node;

26. }

27. function addColor(node, color, level) {

28. if (node.isLeaf) {

29. node.pixelCount += 1;

30. node.red += color.r;

31. node.green += color.g;

32. node.bllue += color.b;

33. }

34. else {

35. var str = "";

36. var r = color.r.toString(2);

37. var g = color.g.toString(2);

38. var b = color.b.toString(2);

39. while (r.length < 8) r = '0' + r;

40. while (g.length < 8) g = '0' + g;

41. while (b.length < 8) b = '0' + b;

42. str += r[level];

43. str += g[level];

44. str += b[level];

45. var index = parseInt(str, 2);

46. if (null === node.children[index]) {

47. node.children[index] = createNode(index, level + 1);

48. }

49. if (undefined === node.children[index]) {

50. console.log(index, level, color.r.toString(2));

51. }

52. addColor(node.children[index], color, level + 1);

53. }

54. }

55. function reduceTree() {

56. // 找到最深层次的并且有可合并节点的链表

57. var level = 6;

58. while (null == reducible[level]) {

59. level -= 1;

60. }

61. // 取出链表头并将其从链表中移除

62. var node = reducible[level];

63. reducible[level] = node.next;

64. // 合并子节点

65. var r = 0;

66. var g = 0;

67. var b = 0;

68. var count = 0;

69. for (var i = 0; i < 8; i++) {

70. if (null === node.children[i]) continue;

71. r += node.children[i].red;

72. g += node.children[i].green;

73. b += node.children[i].blue;

74. count += node.children[i].pixelCount;

75. leafNum--;

76. }

77. // 赋值

78. node.isLeaf = true;

79. node.red = r;

80. node.green = g;

81. node.blue = b;

82. node.pixelCount = count;

83. leafNum++;

84. }

85. function buidOctree(imageData, maxColors) {

86. var total = imageData.length / 4;

87. for (var i = 0; i < total; i++) {

88. // 添加颜色

89. addColor(root, {

90. r: imageData[i * 4],

91. g: imageData[i * 4 + 1],

92. b: imageData[i * 4 + 2]

93. }, 0);

94. // 合并叶子节点

95. while (leafNum > maxColors) reduceTree();

96. }

97. }

98. function colorsStats(node, object) {

99. if (node.isLeaf) {

100. var r = parseInt(node.red / node.pixelCount);

101. var g = parseInt(node.green / node.pixelCount);

102. var b = parseInt(node.blue / node.pixelCount);

103. var color = r + ',' + g + ',' + b;

104. if (object[color]) object[color] += node.pixelCount;

105. else object[color] = node.pixelCount;

106. return;

107. }

108. for (var i = 0; i < 8; i++) {

109. if (null !== node.children[i]) {

110. colorsStats(node.children[i], object);

111. }

112. }

113. }

114. window.themeColor = function (img, callback) {

115. var canvas = document.createElement('canvas'),

116. ctx = canvas.getContext('2d'),

117. width = 0,

118. height = 0,

119. imageData = null,

120. length = 0,

121. blockSize = 1;

122. width = canvas.width = img.width;

123. height = canvas.height = img.height;

124. ctx.drawImage(img, 0, 0, width, height);

125. imageData = ctx.getImageData(0, 0, width, height).data;

126. root = new OctreeNode();

127. colorMap = {};

128. reducible = {};

129. leafNum = 0;

130. buidOctree(imageData, 8)

131. colorsStats(root, colorMap)

132. var arr = [];

133. for (var key in colorMap) {

134. arr.push(key);

135. }

136. arr.sort(function (a, b) {

137. return colorMap[a] - colorMap[b];

138. })

139. arr.forEach(function (item, index) {

140. arr[index] = item.split(',')

141. })

142. callback(arr)

143. }

144. })()

四、结果对比

在批量跑了10000张图片之后，得到了下面的结果

平均耗时对比（js-cgi)

可以看到在不考虑图片加载时间的情况下，用中位切分法提取的耗时相对较短，而图片加载的耗时可以说是难以逾越的障碍了（整整拖慢了450ms），不过目前的代码还有不错的优化空间，比如间隔采样，绘制到canvas时减小图片尺寸，优化切割点查找等，就需要后续进行更深一点的探索了。

颜色偏差

所以看来准确性还是可以的，约76%的颜色与cgi提取结果相近，在大于100的中抽查后发现有部分图片两者提取到的主题色各有特点，或者平分秋色，比如

五、小结

总结来看，通过canvas的中位切分法与cgi提取的结果相似程度还是比较高的，也有许多图片有很大差异，需要在后续的实践中不断优化。同时，图片加载时间也是一个难以逾越的障碍，不过目前的代码还有不错的优化空间，比如间隔采样，绘制到canvas时减小图片尺寸，优化切割点查找等，就需要后续进行更深一点的探索了。

最后，推荐一个Github：https://github.com/lokesh/color-thief/

关于本文 作者：@jordiawang 原文：https://mp.weixin.qq.com/s/6K7vE3lZbVob3aEWIV5S_g

为你推荐

欢迎自荐投稿，前端早读课等你来