提取手写数字的属性以紧固最近邻算法

Question

我有1024位长的三个手写数字的二进制表示形式：0、1、8。基本上，在数字的32x32位图中，将行连接起来以形成二进制向量。

每个数字有50个二进制矢量。当我们对每个数字应用最近邻居时，我们可以使用汉明距离度量或其他度量，然后应用该算法来区分向量。现在，我想使用另一种技术，而不是查看向量的每一位，而是想在比较向量的同时分析更少的位数。

例如，我知道当比较数字'8'和'0'的位图（大小：1024位）时，我们必须在数字'8'的向量中间有1，因为数字8在视觉上显示为列中两个零的组合。因此，我们的算法将查找两个零的交集（这将是数字的中位数。

这就是我想要的工作方式。我想将低级表示形式（从1024位图矢量看）转换为高级表示形式（由从位图提取的两个属性组成）。

有任何建议吗？我希望这个问题对听众来说有点清楚。

Answer 1

想法1：充水

[这个想法不会使用您每位数有50个模式：它基于这样的想法：通常，“ 1”将所有0位连接在“ 1”形状周围，而“ 0”将0位分开从内部到外部，“ 8”具有两个这样的封闭区域。因此，对0位的连接区域进行计数将可以识别出这三个区域中的哪一个。

因此您可以使用flood fill algorithm，从向量的任何0位开始，并将所有连接的0位设置为1。在一维数组中，您需要注意正确识别连接的位（水平方向：相隔1个位置，但不越过32个边界或垂直...相隔32个位置）。当然，这种泛洪会破坏图像-因此请确保使用副本。如果在一个这样的洪水填充之后仍然有0位（因此未与您变为1的位连接），则选择其中之一，然后在此处开始第二次洪水填充。如有必要，请重复。

当所有位都以此方式设置为1时，请使用您必须执行的泛洪填充次数，如下所示：

1. 一个洪水填充物？因为所有0位都已连接，所以它是一个“ 1”。
2. 两个洪水填充？这是一个“ 0”，因为零的形状将两个区域（内部/外部）分隔开]
3. 三个洪水？它是一个“ 8”，因为此形状将连接的0位的三个区域分开。

当然，此过程假定这些手写数字的格式正确。例如，如果8形的间隙很小，例如：

..那么它将不会被标识为“ 8”，而是一个“ 0”。通过标识1位的“松散结尾”（停止的“行”）可以解决此特定问题。如果您有两个距离较近的设备，则将充水计数得到的数量增加1（就像两端连接在一起一样）。

类似地，如果“ 0”偶然有一个小的第二循环，如这里：

...它将被标识为“ 8”而不是“ 0”。您可以通过要求每个泛洪填充找到最少数目的0位（例如至少10个0位）算为1，来防止出现此特定问题。

想法2：概率向量

对于每个数字，将您拥有的50个示例向量相加，这样对于每个位置，您的计数就介于0到50之间。每个数字您将有一个这样的“概率”向量，因此prob0，prob1和prob8。如果prob8 [501] = 45，则表示“ 8”向量在索引501处具有1位的可能性很大（45/50）。

现在对这3个概率向量进行如下转换：而不是为每个位置存储一个计数，而是以递减计数（概率）的顺序存储这些位置。因此，如果prob8 [513]的值最高（如49），则该新数组应以[513，...]开头。让我们将这些新向量称为A0，A8和A1（用于相应的数字）。

最后，当您需要匹配给定的输入向量时，同时遍历A0，A1和A8（始终在三个向量中寻找相同的索引）并保持3分。当输入向量在A0 [i]中指定的位置具有1时，则将1加到score0。如果它在A1 [i]中指定的位置也具有1（相同的[[i

）），则将1加到score1中。得分8同样。递增i，然后重复。一旦有明确的获胜者，即当score0，score1和score8中的最高分数超过阈值差异且其中第二高的分数时，立即停止此迭代。此时，您知道要代表哪个数字。