形态学操作

形态学操作

> 编程

何不在地图上玩玩形态学操作呢？

什么是形态学操作？

形态学操作是数学形态学领域里的概念。先别跑！它其实简单得很。 粗略地说，就是用一个集合（一个由对象组成的“列表”）去修改另一个集合。在我们这里，要用的集合就是地图，而那个对象“列表”嘛……就是一个格子列表！就这么简单！

总结一下：输入是一个集合（一张地图），输出也是一个集合（另一张地图）。

最常见（也最容易实现！）的操作是膨胀和腐蚀，它们会根据一个格子周围邻居的状态来修改这个格子的值。“什么才算邻居”是另一个话题了，不过在 Leek Wars 里，我决定使用一个格子的 4 个相邻格子作为邻居。

这是非常简化的说法，但大意就是这样。

在地图上操作

要在地图上做形态学操作，首先得在内存中把地图表示出来。具体怎么表示，随你喜欢！ 不需要多么精细的表示，一开始只要有 0 和 1 就够了。

首先，我们把所有障碍物标记为 1。这样会显示出下面这些格子（使用的地图：304026719）：  图中障碍物被标成了绿色，因为只有它们的值为 1。

我们先来实现膨胀：只要一个格子至少有一个值为 1 的邻居，它的值也会变成 1。只需检查每个格子的每个邻居，一旦遇到值为 1 的邻居，就把这个格子的值设为 1。 应该会得到下面的结果：  这里我把地图的边缘也当作障碍物，不过这不是必须的。 可以看到，障碍物像融化的卡门贝尔奶酪一样摊开、变大了。

接着，我们对这张地图进行腐蚀。腐蚀是膨胀的逆操作：只要一个格子至少有一个值为 0 的邻居，它就会变成 0。 先膨胀、再腐蚀，这种形态学操作叫作闭运算：它会在相距很近的障碍物之间形成一条“通道”。 反过来的操作叫作开运算，也就是先做腐蚀，再做膨胀。

在下图中，红色的格子就是会被腐蚀掉的格子： 

最终结果（去掉红色格子之后）如下：  于是就得到了一张标出障碍物附近狭窄通道的地图！就这么简单。

要把其中的障碍物去掉，可以再实现一些其他操作，比如 AND 和 NOT。例如，对障碍物为 1 的地图执行 NOT（把 1 和 0 互换）的算法，就会得到一张到处是 1、只有障碍物为 0 的地图。然后，对这张满是 1 的地图和前面用闭运算得到的地图执行 AND（两个格子都为 1 时返回 1，否则返回 0），所有障碍物就都变成 0 了。当当！


我们得到了一组靠近障碍物的格子。可以用它来找出几乎无处可走的地方、死胡同、可能的藏身之处…… 试试先做两次膨胀、再做两次腐蚀，或者让两者交替进行，你会看到一些有趣的结果。

如果实现得当，这种方法几乎不消耗操作数：我是用二进制形式的地图来实现的（见二进制形式的地图），每次形态学操作只消耗大约 68 次操作。

所以，借助形态学操作，可以快速分析地图，并从中获取信息。其他操作也很容易用代码实现，还能得出有趣的结果。快去敲代码吧！