machine-learning - 提取手写数字的属性以加快最近邻算法

Question

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

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

例如，我知道当比较数字“8”和“0”的位图（大小：1024 位）时，我们必须在数字“8”的向量中间有 1，因为数字 8 在视觉上表现为两个零放在列中。所以我们的算法会寻找两个零的交集（这将是数字的中间。

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

有什么建议吗？我希望，这个问题对观众来说有点清楚。

标签： machine-learningcomputer-visionartificial-intelligencenearest-neighbor

Answer 1

想法1：洪水填充

这个想法不使用每个数字的 50 个模式：它基于这样的想法：通常“1”具有围绕“1”形状连接的所有 0 位，而“0”分隔其中的 0 位从外面看，一个“8”有两个这样的封闭区域。因此，计算 0 位的连接区域将确定它是三个中的哪一个。

因此，您可以使用洪水填充算法，从向量中的任何 0 位开始，并将所有连接的 0 位设置为 1。在一维数组中，您需要注意正确识别连接位（水平方向：1 位置分开，但不跨越 32 个边界，或垂直...分开 32 个位置）。当然，这种填充会破坏图像——所以一定要使用副本。如果在一次这样的洪水填充之后仍然有 0 位（因此没有连接到你变成 1 的那些），那么选择其中之一并在那里开始第二次洪水填充。必要时重复。

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

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

当然，这个过程假设这些手写数字格式正确。例如，如果一个 8 字形的间隙很小，如下所示：

..那么它将不会被识别为“8”，而是“0”。这个特殊问题可以通过识别 1 位的“松散端”（停止的“线”）来解决。当您在短距离内有两个时，然后将您从洪水填充计数中获得的数字增加 1（就好像这两个末端是连接的一样）。

同样，如果一个“0”意外地有一个小的第二个循环，就像这里：

...它将被标识为“8”而不是“0”。您可以通过要求每个洪水填充找到最小数量的 0 位（例如至少 10 个 0 位）来计为一个来防止这个特殊问题。

思路二：概率向量

对于每个数字，将您拥有的 50 个示例向量相加，这样对于每个位置，您都有一个介于 0 到 50 之间的计数。每个数字都有一个这样的“概率”向量，即 prob0、prob1 和 prob8。如果 prob8[501] = 45，则意味着“8”向量很可能 (45/50) 在索引 501 处具有 1 位。

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

最后，当你需要匹配一个给定的输入向量时，同时经过 A0、A1 和 A8（总是在三个向量中查看相同的索引）并保持 3 个分数。当输入向量在 A0[i] 中指定的位置为 1 时，则将 score0 加 1。如果它在 A1[i] 中指定的位置也有 1（相同的i），则将 1 添加到 score1。score8 也是一样。增加i，然后重复。一旦你有了明确的赢家，即当 score0、score1 和 score8 中的最高分超过阈值差且其中第二高分时，立即停止此迭代。此时，您知道代表的是哪个数字。