什么条件下最短 4 路径的长度等于D4D4距离?

信息处理 图像处理 距离度量
2022-02-11 07:54:33

以下是《数字图像处理》一书中的一道题。

考虑两点pq. 说明条件D4之间的距离 pq等于这些点之间的最短 4 路径。

以下是“解决方案手册”中的解决方案

每当我们可以从pq通过遵循一条路径,其元素 (1) 来自 V,并且 (2) 的排列方式使得我们可以从pq最多在两个方向(例如,向右和向上)转弯。【下图中的黑色路径。】

但是我不明白为什么其他“直角”路径,例如下图中的红色路径,不是解决方案。为什么最多只能有两个方向?

PS 对于像素pq有坐标(X,是的)(s,),分别是D4距离为|X-s|+|是的-|.

在此处输入图像描述

谢谢

1个回答

D4您定义中的距离基本上就是所谓的大号1基于范数的距离或曼哈顿距离

它也被称为出租车距离或出租车几何。
从它的名字你可以理解,只要你走直线并转向目标(如果它向上和向右,那么你只能向上和向右,如果它是向左和向下,你只能向左和向下)所有路径都有使用此规范的相同距离。