图像轮廓跟踪:Jacob的停止准则问题

Question

我正在尝试在我的JavaScript项目中采用摩尔邻居轮廓跟踪算法，目前我正在阅读关于轮廓跟踪：Ghuneim/sq.html的教程。

但我很难理解雅各布的停车标准。教程将此标准解释为

在第二次输入开始像素后，按照最初输入的方式停止

据我所知，这意味着，如果我们第一次以一定的绝对方向输入开始像素S(例如，如果我们从左下角搜索开始像素)，我们必须在以相同的绝对方向(向上，与第一次一样)重新进入开始像素后停止跟踪。

这听起来很清楚，但我发现有些情况下，这一条件永远不会得到满足。其中一个例子显示在这张图片上：Jacobs停止准则问题

如您所见，起始像素(标记为S)最初是用向上方向(紫色箭头)输入的，但第二次和其他所有时间它都将以左方向(红色箭头)输入。因此，Jacob的停止标准(输入与第一次相同方向的开始像素)将永远无法实现。

我想我只是误解了教程的这一部分.如果你能向我解释我哪里错了，我会很高兴的。

Answer 1

我认为你最好使用径向扫描算法，在同一个网站上描述。它非常类似摩尔邻居算法，但它不跟踪方向，所以你不能使用雅各布的停止准则。

相反，本教程提出了一个新的标准：

停止准则2 假设算法每次发现新的边界像素Pi时，将其插入到边界像素序列中: P1、P2、P3、.、Pi，并声明为当前边界像素。(假设P1是起始像素)。这意味着我们知道每个当前边界像素的前一个边界像素Pi-1 .(对于开始像素，我们假设P0是一个虚拟像素-not，相当于网格上的任何像素--在边界像素序列中的起始像素之前)。 考虑到上述假设，我们可以定义我们的停止准则:算法在以下情况下终止： ( a)当前边界像素Pi以前在边界像素序列中以像素Pj (其中jb) Pi-1 = Pj-1。 换句话说，该算法在第二次访问边界像素P时终止，条件是第二次访问P之前的边界像素(在边界像素序列中)与第一次访问P之前的像素相同。

有了这个标准，算法应该能够处理大多数情况，包括图片上的情况和不连接的8个连接模式。

在理论上，你甚至应该能够使用这个准则与摩尔邻居算法。

Answer 2

我试了一试，我不认为你在这里有什么问题，但事实上，我们发现了一个例子，摩尔邻居的追踪不符合Jacob的停止准则。

有趣的是，它在平方跟踪(使用Jacob的停止准则)和Theo的算法下是接近的。如果你忽略使用Jacob的停止准则，它也会在Moore邻居跟踪下关闭，如果你只是垂直翻转网格，它也会在Moore邻居跟踪下关闭。