当我看到词云时，我在想什么？

当第一眼看到词云时，基于程序员的条件反射，一个大大的「How」字浮现在眼前：它是如何实现的？仔细观察，又发现一些现象。词语之间没有重叠，词语中间的空隙被更小的词语填满，有的词语与词语之间以奇怪的姿势交错在一起。考虑了一会儿，我知道我又一次进入了未知领域，以我所知的方法，似乎没有一个能够轻易解决这个问题。

关键问题在哪？

首先，在图片上绘制文字肯定不是难事，虽然我没用 python 画过任何图像，但如果这件事成为难点，那肯定是 python 生态出了问题。同样的，设置文字为不同颜色或不同大小也应该不是难事。文字的位置、颜色、大小看起来都比较随机，这也很简单，random 库就能实现。那最后就剩下一个问题，要如何做到词语之间紧密排布但又没有重叠呢？

笨办法

假设先在一张白色的图片 A 上放一个黑色的词语 A，又在另一张同样大小的白色的图片 B 上放一个词语 B，把这两张图片都打印到纸上，整齐的叠在一起，对着阳光看，不就能知道这两个词语有没有重叠了吗？如果重叠，就把词语 B 换一个地方，重新打印对比；不重叠时，记下这个位置，词语 B 打印到图片 A 上……

似乎不太困难，而且我知道我并不需要把图片打印出来，可以让 python 帮我完成对比的工作。

图片是由一个一个像素组成的，比如一张 800 × 600 的图片，说明它是由 800 × 600 = 48万 个像素组成。每个像素中保存了一个颜色值，通过对比图片 A 和 B 的每一个像素，如果相同位置上，A 和 B 的像素都为黑色，那就意味这两个词语有重叠。

虽然还有一些不清楚的地方，不过这确实是一个可行的方案。

动手做？

要开始用 python 动手实现了吗？
当然不，我们知道 python 有一个 wordcloud 库可以生成词云。

那要开始介绍 wordcloud 库吗？
是也不是。我更关心的是 wordcloud 库如何解决我们的关键问题？

Wordcloud 探秘

从 Github 上可以轻易的下载到 wordcloud 库的代码。从入口函数开始，粗略的追踪了几个函数的调用，有几个地方引起了我的注意：

1. 它使用了 Pillow 库，搜索发现这是一个 python 图像处理库。
2. 它在一个 for word, freq in frequencies 循环中，将单词逐个放到图片上。
3. 这个循环中，除了对字体进行设置外，还调用了一个 sample_position 方法来寻找放置的位置。<- 这就是我们所要的
4. sample_position 很简单，它的实现在 query_integral_image.pyx 文件中，仅有 30 多行，它从图片左上角第一个像素开始，遍历所有像素，检查各个位置能否放置。另外，integral_image 翻译为 积分图。

初窥图像处理一角

积分图？听起来似乎很复杂，但理解起来却特别简单。首先，积分图不是一张真实的图片，接下来……看图吧：

点击左图中的某个像素位置，绘制图形。

积分图中，每个单元的值，等于原图此位置左上角所有像素值之和（橙框的值 = 蓝框中所有值之和）。这个性质，能够帮助我们快速判断一个区域内有没有内容。为什么这么说呢？

快速重叠检测

如果一个矩形区域内没有内容，说明这个区域内所有像素值之和为零。根据积分图的特征，我们可以进行如下计算：用大矩形所有像素值之和，减去上方和左侧两个矩形像素值之和，再加上左上角小矩形像素值之和，就得到了所求区域内像素值之和。

这样，只需要进行 四次取值和一次运算 就能够判断某区域是否为空，比逐个像素检测快很多。

每个词语都能够被框在一个矩形中（宽度为 w，高度为 h），我们只需要对图片每个位置 (x,y) 进行计算，如果 (x,y) 到 (x + w - 1, y + h - 1) 这个矩形区域内没有内容，就能够放置这个词语。

至此，我们知道了词云的第一个关键点：重叠检测方法。

词云布局方法

我们已经能够判断新放置的词语是否和其它词语重叠，接下来的问题就是选择一种策略来放置新词语。

wordcloud 库使用了一个非常简单的布局方法：

1. 从左上角第一个像素开始，判断在这个位置放置新词语会不会与已放置的内容重叠；
2. 如果不重叠，将这个位置添加一个列表 list 中；
3. 遍历图片所有像素，将所有可放置的位置都加到 list 中；
4. 从 list 中随机选择一个位置放置这个词语。

这样的方法推翻了我们之前的观测，wordcloud 并没有做任何工作来保证词语之间紧密排布。但这并不困难，只要我们换一种方法：

1. 选择一个初始位置 P；
2. 对每一个单词，从位置 P 开始，稍微移动一点点距离，看能不能放下，如果不能，再稍微移动一点距离，直到能够放下。

不错，就是简单的贪心策略。

着手实现

import random
import math

from PIL import Image
from PIL import ImageDraw
from PIL import ImageFont

words = ['发展', '中国', '人民', '建设', '社会主义', '坚持', '党', '全面', '国家', '实现', '制度', '推进', '特色', '社会']

# 创建一张 800×600 的图片
img = Image.new("L", (800, 600))
draw = ImageDraw.Draw(img)

for word in words:
  # 选择字体和大小：黑体，大小随机
  font_size = random.randint(50,150)
  font = ImageFont.truetype('C:\Windows\Fonts\SIMHEI.TTF', font_size)

  # 计算文字矩形框的大小
  box_size = draw.textsize(word, font=font)

  # 在图片中寻找一个能放下矩形框的位置
  x, y = find_position(img, box_size[0], box_size[1])
  if x:
    # 找到一个位置，并绘制上文字
    draw.text((x, y), word, fill="white", font=font)
img.show()
      

关键的确定位置方法：

import numpy as np
def find_position(img, size_x, size_y):
  # 计算积分图，cumsum([1,2,3,4]) => [1,3,6,10]
  integral = np.cumsum(np.cumsum(np.asarray(img), axis=1), axis=0)

  # 使用 wordcloud 的布局策略
  for x in range(1, 800 - size_x):
    for y in range(1, 600 - size_y):
      # 检测矩形区域内容是否为空
      area = integral[y - 1, x - 1] + integral[y + size_y - 1, x + size_x - 1]
      area -= integral[y - 1, x + size_x - 1] + integral[y + size_y - 1, x - 1]
      if not area:
        return x, y

  return None, None
      

至此，我们已经理解 wordcloud 生成词云的基本原理。

明显的缺点

当词语数量增多时，运行代码，久久未能得出结果。我意识到生成词云是一个需要极大计算量的工作。

wordcloud 使用了很多使代码变得难以理解的优化策略，并且将 find_position 函数转用 Cython 实现（转换为 C 语言）也在很大程度上说明了这个问题。

速度问题暂且不提，毕竟生成词云不是我的日常工作。但是通过实现上面的算法，我还发现另一个问题：矩形检测的积分图算法似乎不能很好的支持文字的旋转。

这件事很好理解，如果将一个单词旋转一定角度，那么它的外接矩形面积必然会比不旋转时候大，这就需要更大的矩形区域来放置这个词语，导致很多实际可以放置的位置却不能放置。

那么，有没有更好的策略呢？

更好的策略

答案是肯定的，包含旋转文字的词云图片并不鲜见。经过一段时间的调查，我们发现，在其它一些语言实现的词云中，使用了不一样的实现方式。

四叉树

在 Wordcloud 算法中，每放置完一个词语，就需要重新计算一次积分图，下一个词语需要与整张图片进行重叠检测。有没有可能将每个词视为单独的实体，在放置新词时，检测它与其它每一个词语有没有重叠？

在 Jonathan Feinberg 的书中，介绍了一种叫做 层次边界框（Hierarchical bounding boxes）的方法来快速实现两个词语间的重叠检测。

层次边界框这个词太拗口，我们换用「四叉树」来代指这种结构，它本质上也是一棵记录空间信息的四叉树。

四叉树的构建并不困难，将图片横纵各切一刀，平均分割为「左上、左下、右上、右下」四个区域，如果某个区域中有内容（此时可以用积分图算法判断），那么继续将这个区域分割为四个部分，直到区域的大小小于某个值。

四叉树每深一层，对形状的描述就越精确，每一次分隔，都能排除一些空白矩形区域，剩下的有像素的区域，都记录到了树中。

class QuadTree:
x1 = 0
y1 = 0
x2 = 0
y2 = 0
children = None

def __init__(self, x1, y1, x2, y2):
  self.x1,self.y1,self.x2,self.y2 = x1,y1,x2,y2

# 计算积分图
integral = np.cumsum(np.cumsum(np.asarray(sprite.img), axis=1), axis=0)

def build_tree_recursive(x1, y1, x2, y2):
  area = integral[y1 - 1, x1 - 1] + integral[y2, x2]
  area -= integral[y1 - 1, x2] + integral[y2, x - 1]
    if not area:
      # 区域内没有像素
      return None

  # 区域内有像素，继续划分
  children = []
  cx = int((x1 + x2) / 2)
  cy = int((y1 + y2) / 2)

  tree = QuadTree(x1,y1,x2,y2)

  # 最小矩形区域边长为 1 像素
  if x2 - x1 > 1 or y2 - y1 > 1:
    c0 = build_tree_recursive(x1, y1, cx, cy)  # 左上区域
    c1 = build_tree_recursive(cx,  y1, x2, cy) # 右上区域
    c2 = build_tree_recursive(x1, cy, cx, y2)  # 左下区域
    c3 = build_tree_recursive(cx, cy, x2, y2)  # 右下区域
    if c0:
      children.append(c0)
    if c1:
      children.append(c1)
    if c2:
      children.append(c2)
    if c3:
      children.append(c3)
    if len(children):
      tree.children = children
  return tree
      

四叉树重叠检测

那么，如何使用四叉树检测单词是否重叠呢？

首先，通过搜索我们知道，检测两个矩形是否重叠非常容易，只要知道两个矩形的坐标，通过简单的公式就可以计算。

对于两个单词，首先可以构建两棵四叉树。判断四叉树第一层的矩形是否有重叠，如果没有，说明两个单词不可能重叠；如果有，说明两个单词可能重叠，继续检测下一层中记录的区域。

最终，要确定两个单词重叠，需要判断两个四叉树的各叶子结点中，至少有两个重叠。当然，直接进行叶子结点的遍历也是可行的，但逐层判断能省掉大量时间。

# (x1,y1) 为 tree 对应单词放置位置，(x2,y2) 为 otherTree 对应单词放置位置
def overlaps(tree, other_tree, x1, y1, x2, y2):
  if rectCollide(tree, other_tree, x1, y1, x2, y2):
    if not tree.children:
      if not other_tree.children:
        return True
      else:
        for i in range(0, len(other_tree.children)):
          if overlaps(tree, other_tree.children[i], x1, y1, x2, y2):
            return True
    else:
      for i in range(0, len(tree.children)):
        if overlaps(other_tree, tree.children[i], x2, y2, x1, y1):
          return True
  return False

# 位于 (x1,y1) 的四叉树中矩形 a 和位于 (x2,y2) 的四叉树中矩形 b 是否重叠
# (a.x1,a.y1) 是 a 在矩形树中的相对坐标
# (a.x1 + x1, a.y1 + y1) 是矩形 a 在图像中的坐标
def rect_collide(a, b, x1, y1, x2, y2):
  return y1 + a.y2 > y2 + b.y1 and y1 + a.y1 < y2 + b.y2 and x1 + a.x2 > x2 + b.x1 and x1 + a.x1 < x2 + b.x2

矩形螺旋布局

除了使用新的重叠检测算法，我们还打算引入一个新的布局方法来使最终的词云更好看。

矩形螺旋布局也是一种贪心布局策略，所有的单词紧密放置在图中心的螺旋形状上。每个单词都从螺旋的中心位置开始检测，如果不能放置，就移动到螺旋的下一个位置。

# 参数为图像的大小
def rectangular_sprial(width, height):
  dy = dx = 10
  x = y = 0
  def sprial(t):
    nonlocal x, y
    num = int(math.sqrt(1 + 4 * t) - 1) & 3
    if num == 0:
      x += dx
    elif num == 1:
      y += dy
    elif num == 2:
      x -= dx
    else:
      y -= dy
  return x + (width) // 2, y + (height) // 2

  # 返回一个闭包
  return sprial

新的实现

我们已经有充足的知识来重新实现一个词云了，顺便实现文字以随机角度旋转布局。

（完整代码见文末）

性能瓶颈

词云的生成速度比积分图算法稍快，但仍然需耐心等待。

因为每个单词都需要与其它所有单词进行重叠检测，导致 N² 的时间复杂度，单词数量增多时性能会急剧下降。

由于图像中心文字密集，需要检测大量无效位置后才能确定放置地点（通常只能放在图像的外侧边缘）。

优化！优化！

为了使词云运行速度达到可以接受的程度，我们使用两种简单策略来优化词云算法。

一种策略的想法来源于四叉树。先把图像分割为多个矩形区域，比如 800×600 的图片，分割为 48（8×6）个区域，每个区域长宽都是 100 像素。布局每个单词后，就将这个单词添加到对应的区域中，这样在布局一个新的单词时，只要根据单词大概的大小和放置的位置，在有限的几个区域中进行重叠检测，大幅降低了需要进行重叠检测的次数。

第二种策略更多来源于经验。假如要放置数十个大小差不多的单词，第一个单词检测了螺旋上的 200 个坐标后，找到一个放置位置，那么下一个单词就跳过这 200 个坐标（因为大概率重叠），在第 300 个坐标上放置，下一个单词从第 300 个坐标开始……如果检测到了图片边界未找到可以放置的坐标，那么回到初始位置重新寻找。

为什么要实现一个新的词云？

为了更多的可能性。

更多字体

作为前端开发者，我们经常使用 fontawesome 图标字体，那么用它来制作词云如何？

更多颜色

词云库多数都使用随机颜色，但是懂得了实现原理，颜色可以更有意义：

1. 按词频设置单词颜色。
2. 读取另一张色彩丰富的图片作为颜色映射。
3. 对不同区域使用不用颜色。

更多布局方法

在网络上的词云图中，我们经常见到把所有词语放置在一定区域内的图片。

要实现起来也很简单，事先制作一张黑白图片作为遮罩，当作单词计算四叉树后，放到图片中即可。单词除了与其它单词进行重叠检测外，也与遮罩进行重叠检测。

使用多个遮罩也不是难事，甚至可以使用代码绘制遮罩。

除此之外，你还可以：

1. 让词语都平行或斜向排布。
2. 固定一些词语的大小、位置和颜色，让重点更加突出。

例如页面开头的词云。

表情包云？

聪明的你已经意识到，词云中的每个单词其实都是当作图片处理的，那么，是不是可以用词云算法来布局图片呢，比如表情包？

你能做的更好！

尝试修改 wordcloud.py，创作你自己的词云！

欢迎向 supportpython123.org 邮箱发送你的创意，我们会定期收集和展示优秀的作品。

可能还需要学习的知识：

1. 使用 Pillow 库绘制和处理图像
2. 使用 numpy 库进行数学运算

Python123 版权所有，不允许任何形式转载和使用。