|
導讀 Python123 特別策劃，教你如何像程序員和設計師一樣思考，探索技術(shù)背后的真相。 一念之差，大有不同。上百小時的精心制作，只為給你帶來更易理解，更具深度的知識。 PART 1 - 當我看到詞云時，我在想什么？ - 關(guān)鍵問題在哪？ - 笨辦法 - 動手做？ - Wordcloud 探秘 - 初窺圖像處理一角 - 快速重疊檢測 - 詞云布局方法 - 著手實現(xiàn) - 明顯的缺點 - 更好的策略 PART 2 - 四叉樹 - 四叉樹重疊檢測 - 矩形螺旋布局 - 新的實現(xiàn) - 性能瓶頸 - 優(yōu)化！優(yōu)化！ - 為什么要實現(xiàn)一個新的詞云？ - 更多字體 - 更多顏色 - 更多布局方法 - 表情包云？ - 你能做的更好！ 當我看到詞云時，我在想什么？當?shù)谝谎劭吹皆~云時，基于程序員的條件反射，一個大大的「How」字浮現(xiàn)在眼前：它是如何實現(xiàn)的？仔細觀察，又發(fā)現(xiàn)一些現(xiàn)象。詞語之間沒有重疊，詞語中間的空隙被更小的詞語填滿，有的詞語與詞語之間以奇怪的姿勢交錯在一起。考慮了一會兒，我知道我又一次進入了未知領(lǐng)域，以我所知的方法，似乎沒有一個能夠輕易解決這個問題。 關(guān)鍵問題在哪？首先，在圖片上繪制文字肯定不是難事，雖然我沒用 python 畫過任何圖像，但如果這件事成為難點，那肯定是 python 生態(tài)出了問題。同樣的，設置文字為不同顏色或不同大小也應該不是難事。文字的位置、顏色、大小看起來都比較隨機，這也很簡單，random 庫就能實現(xiàn)。那最后就剩下一個問題，要如何做到詞語之間緊密排布但又沒有重疊呢？ 笨辦法假設先在一張白色的圖片 A 上放一個黑色的詞語 A，又在另一張同樣大小的白色的圖片 B 上放一個詞語 B，把這兩張圖片都打印到紙上，整齊的疊在一起，對著陽光看，不就能知道這兩個詞語有沒有重疊了嗎？如果重疊，就把詞語 B 換一個地方，重新打印對比；不重疊時，記下這個位置，詞語 B 打印到圖片 A 上…… 似乎不太困難，而且我知道我并不需要把圖片打印出來，可以讓 python 幫我完成對比的工作。 圖片是由一個一個像素組成的，比如一張 800 × 600 的圖片，說明它是由 800 × 600 = 48萬 個像素組成。每個像素中保存了一個顏色值，通過對比圖片 A 和 B 的每一個像素，如果相同位置上，A 和 B 的像素都為黑色，那就意味這兩個詞語有重疊。 雖然還有一些不清楚的地方，不過這確實是一個可行的方案。 動手做？要開始用 python 動手實現(xiàn)了嗎？ 那要開始介紹 wordcloud 庫嗎？ Wordcloud 探秘從 Github 上可以輕易的下載到 wordcloud 庫的代碼。從入口函數(shù)開始，粗略的追蹤了幾個函數(shù)的調(diào)用，有幾個地方引起了我的注意：
初窺圖像處理一角積分圖？聽起來似乎很復雜，但理解起來卻特別簡單。首先，積分圖不是一張真實的圖片，接下來……看圖吧：  積分圖中，每個單元的值，等于原圖此位置左上角所有像素值之和（橙框的值 = 藍框中所有值之和）。這個性質(zhì)，能夠幫助我們快速判斷一個區(qū)域內(nèi)有沒有內(nèi)容。為什么這么說呢？ 快速重疊檢測如果一個矩形區(qū)域內(nèi)沒有內(nèi)容，說明這個區(qū)域內(nèi)所有像素值之和為零。根據(jù)積分圖的特征，我們可以進行如下計算：用大矩形所有像素值之和，減去上方和左側(cè)兩個矩形像素值之和，再加上左上角小矩形像素值之和，就得到了所求區(qū)域內(nèi)像素值之和。  這樣，只需要進行 四次取值和一次運算 就能夠判斷某區(qū)域是否為空，比逐個像素檢測快很多。 每個詞語都能夠被框在一個矩形中（寬度為 w，高度為 h），我們只需要對圖片每個位置 (x,y) 進行計算，如果 (x,y) 到 (x + w - 1, y + h - 1) 這個矩形區(qū)域內(nèi)沒有內(nèi)容，就能夠放置這個詞語。 至此，我們知道了詞云的第一個關(guān)鍵點：重疊檢測方法。 詞云布局方法我們已經(jīng)能夠判斷新放置的詞語是否和其它詞語重疊，接下來的問題就是選擇一種策略來放置新詞語。 wordcloud 庫使用了一個非常簡單的布局方法：
這樣的方法推翻了我們之前的觀測，wordcloud 并沒有做任何工作來保證詞語之間緊密排布。但這并不困難，只要我們換一種方法：
不錯，就是簡單的貪心策略。 著手實現(xiàn) import random import math from PIL import Image from PIL import ImageDraw from PIL import ImageFont words = ['發(fā)展', '中國', '人民', '建設', '社會主義', '堅持', '黨', '全面', '國家', '實現(xiàn)', '制度', '推進', '特色', '社會'] # 創(chuàng)建一張 800×600 的圖片 img = Image.new("L", (800, 600)) draw = ImageDraw.Draw(img) for word in words: # 選擇字體和大?。汉隗w，大小隨機 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() 關(guān)鍵的確定位置方法： 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): # 檢測矩形區(qū)域內(nèi)容是否為空 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 至此，我們已經(jīng)理解 wordcloud 生成詞云的基本原理。
明顯的缺點當詞語數(shù)量增多時，運行代碼，久久未能得出結(jié)果。我意識到生成詞云是一個需要極大計算量的工作。 wordcloud 使用了很多使代碼變得難以理解的優(yōu)化策略，并且將 find_position 函數(shù)轉(zhuǎn)用 Cython 實現(xiàn)（轉(zhuǎn)換為 C 語言）也在很大程度上說明了這個問題。 速度問題暫且不提，畢竟生成詞云不是我的日常工作。但是通過實現(xiàn)上面的算法，我還發(fā)現(xiàn)另一個問題：矩形檢測的積分圖算法似乎不能很好的支持文字的旋轉(zhuǎn)。 這件事很好理解，如果將一個單詞旋轉(zhuǎn)一定角度，那么它的外接矩形面積必然會比不旋轉(zhuǎn)時候大，這就需要更大的矩形區(qū)域來放置這個詞語，導致很多實際可以放置的位置卻不能放置。 那么，有沒有更好的策略呢？ 更好的策略答案是肯定的，包含旋轉(zhuǎn)文字的詞云圖片并不鮮見。經(jīng)過一段時間的調(diào)查，我們發(fā)現(xiàn)，在其它一些語言實現(xiàn)的詞云中，使用了不一樣的實現(xiàn)方式。 四叉樹在 Wordcloud 算法中，每放置完一個詞語，就需要重新計算一次積分圖，下一個詞語需要與整張圖片進行重疊檢測。有沒有可能將每個詞視為單獨的實體，在放置新詞時，檢測它與其它每一個詞語有沒有重疊？ 在 Jonathan Feinberg 的書中，介紹了一種叫做 層次邊界框（Hierarchical bounding boxes）的方法來快速實現(xiàn)兩個詞語間的重疊檢測。 層次邊界框這個詞太拗口，我們換用「四叉樹」來代指這種結(jié)構(gòu)，它本質(zhì)上也是一棵記錄空間信息的四叉樹。 四叉樹的構(gòu)建并不困難，將圖片橫縱各切一刀，平均分割為「左上、左下、右上、右下」四個區(qū)域，如果某個區(qū)域中有內(nèi)容（此時可以用積分圖算法判斷），那么繼續(xù)將這個區(qū)域分割為四個部分，直到區(qū)域的大小小于某個值。      
四叉樹每深一層，對形狀的描述就越精確，每一次分隔，都能排除一些空白矩形區(qū)域，剩下的有像素的區(qū)域，都記錄到了樹中。 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: # 區(qū)域內(nèi)沒有像素 return None # 區(qū)域內(nèi)有像素，繼續(xù)劃分 children = [] cx = int((x1 + x2) / 2) cy = int((y1 + y2) / 2) tree = QuadTree(x1,y1,x2,y2) # 最小矩形區(qū)域邊長為 1 像素 if x2 - x1 > 1 or y2 - y1 > 1: c0 = build_tree_recursive(x1, y1, cx, cy) # 左上區(qū)域 c1 = build_tree_recursive(cx, y1, x2, cy) # 右上區(qū)域 c2 = build_tree_recursive(x1, cy, cx, y2) # 左下區(qū)域 c3 = build_tree_recursive(cx, cy, x2, y2) # 右下區(qū)域 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 四叉樹重疊檢測 那么，如何使用四叉樹檢測單詞是否重疊呢？ 首先，通過搜索我們知道，檢測兩個矩形是否重疊非常容易，只要知道兩個矩形的坐標，通過簡單的公式就可以計算。 對于兩個單詞，首先可以構(gòu)建兩棵四叉樹。判斷四叉樹第一層的矩形是否有重疊，如果沒有，說明兩個單詞不可能重疊；如果有，說明兩個單詞可能重疊，繼續(xù)檢測下一層中記錄的區(qū)域。
最終，要確定兩個單詞重疊，需要判斷兩個四叉樹的各葉子結(jié)點中，至少有兩個重疊。當然，直接進行葉子結(jié)點的遍歷也是可行的，但逐層判斷能省掉大量時間。 # (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 矩形螺旋布局 除了使用新的重疊檢測算法，我們還打算引入一個新的布局方法來使最終的詞云更好看。  矩形螺旋布局也是一種貪心布局策略，所有的單詞緊密放置在圖中心的螺旋形狀上。每個單詞都從螺旋的中心位置開始檢測，如果不能放置，就移動到螺旋的下一個位置。 # 參數(shù)為圖像的大小 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 新的實現(xiàn)我們已經(jīng)有充足的知識來重新實現(xiàn)一個詞云了，順便實現(xiàn)文字以隨機角度旋轉(zhuǎn)布局。
（完整代碼見文末） 性能瓶頸詞云的生成速度比積分圖算法稍快，但仍然需耐心等待。 因為每個單詞都需要與其它所有單詞進行重疊檢測，導致 N2 的時間復雜度，單詞數(shù)量增多時性能會急劇下降。 由于圖像中心文字密集，需要檢測大量無效位置后才能確定放置地點（通常只能放在圖像的外側(cè)邊緣）。 優(yōu)化！優(yōu)化！為了使詞云運行速度達到可以接受的程度，我們使用兩種簡單策略來優(yōu)化詞云算法。 一種策略的想法來源于四叉樹。先把圖像分割為多個矩形區(qū)域，比如 800×600 的圖片，分割為 48（8×6）個區(qū)域，每個區(qū)域長寬都是 100 像素。布局每個單詞后，就將這個單詞添加到對應的區(qū)域中，這樣在布局一個新的單詞時，只要根據(jù)單詞大概的大小和放置的位置，在有限的幾個區(qū)域中進行重疊檢測，大幅降低了需要進行重疊檢測的次數(shù)。 第二種策略更多來源于經(jīng)驗。假如要放置數(shù)十個大小差不多的單詞，第一個單詞檢測了螺旋上的 200 個坐標后，找到一個放置位置，那么下一個單詞就跳過這 200 個坐標（因為大概率重疊），在第 300 個坐標上放置，下一個單詞從第 300 個坐標開始……如果檢測到了圖片邊界未找到可以放置的坐標，那么回到初始位置重新尋找。 為什么要實現(xiàn)一個新的詞云？為了更多的可能性。 更多顏色詞云庫多數(shù)都使用隨機顏色，但是懂得了實現(xiàn)原理，顏色可以更有意義：
更多布局方法在網(wǎng)絡上的詞云圖中，我們經(jīng)常見到把所有詞語放置在一定區(qū)域內(nèi)的圖片。 要實現(xiàn)起來也很簡單，事先制作一張黑白圖片作為遮罩，當作單詞計算四叉樹后，放到圖片中即可。單詞除了與其它單詞進行重疊檢測外，也與遮罩進行重疊檢測。 使用多個遮罩也不是難事，甚至可以使用代碼繪制遮罩。
除此之外，你還可以：
例如頁面開頭的詞云。 表情包云？聰明的你已經(jīng)意識到，詞云中的每個單詞其實都是當作圖片處理的，那么，是不是可以用詞云算法來布局圖片呢，比如表情包？ |
|
|
來自： Gavin_Rainer > 《編程》
