提取手写数字的属性以加强最近邻算法
Extracting properties of handwritten digits to fasten nearest neighbour algorithm
我有三个手写数字的 1024 位长二进制表示：0、1、8。
基本上，在一个数字的 32x32 位图中，行被连接起来形成一个二进制向量。
每个数字有 50 个二进制向量。
当我们对每个数字应用最近邻时，我们可以使用汉明距离度量或其他一些，然后应用算法来区分向量。
现在我想使用另一种技术，而不是查看向量的每一位，我想在比较向量时分析更少的位数。
例如，我知道当比较数字“8”和“0”的位图（大小：1024 位）时，我们必须在数字“8”的向量中间有 1，因为视觉上有数字 8显示为列中放置的两个零的组合。
所以我们的算法会寻找两个零的交集（这将是数字的中间。
这就是我想要的工作方式。我想将低级表示（查看 1024 位图矢量）转换为高级表示（由从位图中提取的两个属性组成）。
有什么建议吗？我希望这个问题对听众来说有点清楚。
想法 1：洪水填充
这个想法不使用每个数字的 50 个模式：它基于这样的想法，即通常“1”的所有 0 位都连接在“1”的形状周围，而“0”分隔它内部的 0 位与外部的 0 位，“8”有两个这样的封闭区域。因此，计算 0 位的连接区域将确定它是三个中的哪一个。
因此您可以使用 flood fill algorithm，从向量中的任意 0 位开始，并将所有连接的 0 位设置为 1。在一维数组中，您需要注意正确识别连接位（水平：相隔 1 个位置，但不跨越 32 个边界，或垂直......相隔 32 个位置）。当然，这种泛滥会破坏图像 - 所以一定要使用副本。如果在一个这样的泛洪填充之后仍然有 0 位（因此它们没有连接到你变成 1 的那些），那么选择其中一个并在那里开始第二次泛洪填充。如有必要，请重复。
当所有位都以这种方式设置为 1 时，使用您必须执行的泛洪填充次数，如下所示：
- 一个洪水填充？它是一个“1”，因为所有的 0 位都是相连的。
- 两次填充？这是一个“0”，因为零的形状将两个区域分开(inside/outside)
- 三个洪水填充？它是一个“8”，因为这个形状将三个相连的 0 位区域分开。
当然，这个过程假设这些手写数字是格式正确的。例如，如果 8 字形有一个小间隙，如下所示：
..那么它不会被识别为“8”，而是“0”。这个特殊问题可以通过识别 1 位的 "loose ends"（停止的 "line"）来解决。当你在短距离内有两个时，然后将你从 flood-fill 计数中得到的数字增加 1（就好像这两个末端是相连的）。
同样，如果一个“0”不小心有一个小秒循环，就像这里：
...它将被识别为“8”而不是“0”。您可以通过要求每个泛洪填充找到最小数量的 0 位（例如至少 10 个 0 位）来算作一个来防止这个特殊问题。
思路二：概率向量
对于每个数字，将您拥有的 50 个示例向量相加，这样对于每个位置，您都有一个介于 0 到 50 之间的计数。每个数字都有一个这样的 "probability" 向量，所以 prob0，概率 1 和概率 8。如果 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），则对score1加1。 score8 也一样。递增 i，然后重复。一旦你有明显的赢家，即当 score0、score1 和 score8 中的最高分与其中第二高分超过阈值差异时，立即停止此迭代。那时你知道代表的是哪个数字。
我有三个手写数字的 1024 位长二进制表示：0、1、8。 基本上，在一个数字的 32x32 位图中，行被连接起来形成一个二进制向量。
每个数字有 50 个二进制向量。 当我们对每个数字应用最近邻时，我们可以使用汉明距离度量或其他一些，然后应用算法来区分向量。 现在我想使用另一种技术，而不是查看向量的每一位，我想在比较向量时分析更少的位数。
例如，我知道当比较数字“8”和“0”的位图（大小：1024 位）时，我们必须在数字“8”的向量中间有 1，因为视觉上有数字 8显示为列中放置的两个零的组合。 所以我们的算法会寻找两个零的交集（这将是数字的中间。
这就是我想要的工作方式。我想将低级表示（查看 1024 位图矢量）转换为高级表示（由从位图中提取的两个属性组成）。
有什么建议吗？我希望这个问题对听众来说有点清楚。
想法 1：洪水填充
这个想法不使用每个数字的 50 个模式：它基于这样的想法，即通常“1”的所有 0 位都连接在“1”的形状周围，而“0”分隔它内部的 0 位与外部的 0 位，“8”有两个这样的封闭区域。因此，计算 0 位的连接区域将确定它是三个中的哪一个。
因此您可以使用 flood fill algorithm，从向量中的任意 0 位开始，并将所有连接的 0 位设置为 1。在一维数组中，您需要注意正确识别连接位（水平：相隔 1 个位置，但不跨越 32 个边界，或垂直......相隔 32 个位置）。当然，这种泛滥会破坏图像 - 所以一定要使用副本。如果在一个这样的泛洪填充之后仍然有 0 位（因此它们没有连接到你变成 1 的那些），那么选择其中一个并在那里开始第二次泛洪填充。如有必要，请重复。
当所有位都以这种方式设置为 1 时，使用您必须执行的泛洪填充次数，如下所示：
- 一个洪水填充？它是一个“1”，因为所有的 0 位都是相连的。
- 两次填充？这是一个“0”，因为零的形状将两个区域分开(inside/outside)
- 三个洪水填充？它是一个“8”，因为这个形状将三个相连的 0 位区域分开。
当然，这个过程假设这些手写数字是格式正确的。例如，如果 8 字形有一个小间隙，如下所示：
..那么它不会被识别为“8”，而是“0”。这个特殊问题可以通过识别 1 位的 "loose ends"（停止的 "line"）来解决。当你在短距离内有两个时，然后将你从 flood-fill 计数中得到的数字增加 1（就好像这两个末端是相连的）。
同样，如果一个“0”不小心有一个小秒循环，就像这里：
...它将被识别为“8”而不是“0”。您可以通过要求每个泛洪填充找到最小数量的 0 位（例如至少 10 个 0 位）来算作一个来防止这个特殊问题。
思路二：概率向量
对于每个数字，将您拥有的 50 个示例向量相加，这样对于每个位置，您都有一个介于 0 到 50 之间的计数。每个数字都有一个这样的 "probability" 向量，所以 prob0，概率 1 和概率 8。如果 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），则对score1加1。 score8 也一样。递增 i，然后重复。一旦你有明显的赢家，即当 score0、score1 和 score8 中的最高分与其中第二高分超过阈值差异时，立即停止此迭代。那时你知道代表的是哪个数字。