行程编码数字形状的轮廓

Question

数字形状是二进制图像(blob)中的一组连接像素.

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

对于平滑的形状,存储要求从O(N²)下降到O(N).

形状的轮廓是一个封闭的像素链,当其内部被填充时(通过填充算法)恢复形状.它也是O(N)表示.Wen的形状可用作位图,轮廓可以通过轮廓算法获得.

我正在寻找一种算法,该算法直接计算给定其RLC表示的形状轮廓,而不是在中间位图中绘制它.期望算法在运行次数中以时间线性运行.

你有遇到过解决方案吗？

Answer 1

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

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

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

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

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

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

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

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