5

数字形状是二进制图像（斑点）中的一组连接像素。

它可以通过游程编码紧凑地表示，即将像素分组为水平线段并存储起始端点坐标和长度。通常，RLC 表示以光栅顺序存储游程，即逐行并向右移动。

对于平滑的形状，存储需求从 O(N²) 下降到 O(N)。

形状的轮廓是一个封闭的像素链，当其内部被填充（通过填充算法）时，它会恢复形状。它也是一个 O(N) 表示。文中的形状可以作为位图使用，轮廓可以通过轮廓算法获得。

我正在寻找一种算法，它可以直接计算给定 RLC 表示的形状的轮廓，而不是在中间位图中绘制它。该算法预计在运行次数上线性运行。

在此处输入图像描述

你遇到过解决方案吗？

4

3 回答 3

1

如果像素被填充但与未填充的像素相邻，则该像素是边界像素。给定填充像素的每行 RLE 编码，我们可以对三个相邻行进行操作以计算边界像素的 RLE 版本，然后对其进行解码。

基本上，我们有一个扫描线算法。三行像

   ***********   ****
************************
  ****        ******

^我们从 RLE获得事件点 ( )：

   ***********   ****
************************
  ****        ******
^ ^^  ^       ^  ^  ^^  ^

首先要做的是将上方或下方具有空像素的中间填充像素指定为边界。（如果您需要指导，区间列表上的集差算法非常相似。）

   ***********   ****
BBB***BBBBBBBBBBB***BBBB
  ****        ******

然后，对于被填充但不知道是边界的区间，检查左端点是否左侧有空间，右端点是否有右侧空间。如果是这样（分别），它们就是边界。

于 2015-09-02T14:18:39.803 回答
0

注意：此答案假定“非轮廓”表示“被 4 个邻居包围”，因此结果与您的示例略有不同（1 像素绿色而不是蓝色）。

所有轮廓像素都是未设置所有 4 个“相邻像素”（像素的左、右、上、下）的像素。

在从上到下解码RLC时，可以通过如下伪代码算法得到轮廓像素：

 For the first line
   All decoded pixels are outline pixels
 For the subsequent lines
   Leftmost and rightmost pixels of each RLC run are outline pixels
   All other pixels are outline pixels if:
     The pixel above isn't set (case A)
     The pixel below isn't set (case B)

案例 A 和 B 意味着您必须查看当前像素上方/下方的像素，因此该算法实际上应该是一种流水线/向前看一行，因为直到下一行才能检测到案例 B被解码。

编辑：要在之后按顺时针顺序对像素进行排序，您可以使用您的轮廓是对角连接的一个像素宽度的线这一事实。选择最上面一行中的一个像素，您将有两个可能的下一个像素，跟随当前像素的右侧、下方或右侧和下方的一个。之后，只需跟随您尚未访问的相邻像素，直到没有相邻像素。例子：

  /----- First pixel you pick, A and B are neighbour candidates, A is the "correct" one
  v
  xAxxx           
 B     x        
 x    x      xxx
 x     xxxxxx   x
  xx           x
    xxxxxxxxxxx

  s0123             Result after following the neighbours (s = start, e = end),
 e     4            numbers from 0-9 show order of traversal
 1    5      234
 0     678901   5
  98           6
    76543210987
于 2015-09-02T14:19:55.790 回答
0

提示：

正如在其他答案中所说，发出轮廓像素列表可以实现为扫描线过程，在此过程中检查运行端点的 3x3 邻域。

此过程将以加扰的方式发出像素，作为需要存储和重新排序的一系列直接和反向弧。

另一种方法可以基于实现标准摩尔邻域算法的想法，该算法具有以所需顺序枚举轮廓像素的优势。

这个过程需要知道当前像素周围的 8 邻域配置，并且想法是在每次移动到另一个像素时更新这个邻域：我们维护包含当前像素的运行的索引以及行中两个面向运行的索引上面和下面。

每次移动到另一个像素时，我们都需要更新这三个索引，这将涉及排序运行列表中的短顺序搜索。这可以看作是对像素的伪随机访问机制，考虑到连续访问是强本地的并且可以被缓存。

更新：

在我使用的运行长度编码表示中，只有黑色运行被编码为三元组(X, Y, L)。运行按行从上到下排序，然后从左到右连续排序。

为方便起见，我们可以切换到“线性寻址”方案，就好像所有图像行已经被一个接一个地附加，并且每个像素都由一个数字指定Z = X + Y.Nx（其中Nx是图像宽度）。

所以我们有一个黑色运行列表，白色运行隐含在两个连续的黑色运行之间。

在处理过程中，我们可以随时记住在当前像素之前或当前像素上开始的运行的索引（R[I].Z <= Z < R[I+1].Z）。我们可以通过检查我们是在运行内部还是在运行与下一个之间（Z < R[I].Z + R[I].L）来判断像素的颜色。

如果我们向左移动一个位置，则Z减少一个1，我们可能必须选择上一个运行 ( I--)。

如果我们向上移动一个位置，则Z减少一个位置，Nx我们可能不得不回溯几次（I--直到R[I].Z <= Z再次）。

在此处输入图像描述

图片显示了当前像素及其 4 个相邻像素，以及黑色运行的“影响区”。我们可以类似地处理所有八个位移方向。

正如我们所看到的，每一步都需要进行一些操作，甚至等于连续运行的次数，这被认为是一个很小的值。使用这个概念，我们可以以合理的成本沿着任意路径遍历 RLC 表示，而无需重建整个位图。

由于 Moore Neighborhood 算法在轮廓长度上采用线性时间，因此基于此线性运行寻址的实现也将采用线性时间（对于每行有限数量的运行）。

于 2015-09-02T15:26:21.097 回答