Image Overlap到手写数字识别

      给出两个图像 A 和 B ，A 和 B 为大小相同的二维正方形矩阵。（并且为二进制矩阵，只包含0和1）。
      我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。（请注意，转换不包括向任何方向旋转。）
      最大可能的重叠是什么？

示例 1:

输入：A = [[1,1,0],
          [0,1,0],
          [0,1,0]]
     B = [[0,0,0],
          [0,1,1],
          [0,0,1]]
输出：3
解释: 将 A 向右移动一个单位，然后向下移动一个单位。

注意:

1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <= A[i][j], B[i][j] <= 1

理解示例：初始状态时A和B两个图像是重叠放置的（我刚刚理解不了题目意思就是在这里），为了使A和B中1重叠的数目最多（示例中是3）可将A向右移动1位，向下移动1位，我们记为（-1，-1），“-”表示右/下移。

一维的思路

二维矩阵有点复杂，我们思考如果是一维数组怎么解。给定A=[1,1,1,0]，B=[0,0,1,1]。我们可以一眼看出最大重叠1的数目是2，A右移2位即可。虽然我们是一眼看出来的，其实我们经历了以下过程：
为了便于叙述令 $a_{i}$ 和 $b_{i}$ 表示为两个数组中第i个元素。→表示记为

①a0和b2重叠，右移2，重叠1数目2→-2;
②a0和b3重叠，右移3，重叠1数目1→-3;

④a1和b2重叠，右移1，重叠1数目2→-1;
⑤a1和b3重叠，右移2，重叠1数目2→-2;

⑥a2和b2重叠，右移0，重叠1数目1→0;
⑦a2和b3重叠，右移1，重叠1数目2→-1.

经过以上步骤我们可以得到：{-2:2,-1:2,0:1,-3:1}，表示右移n位及这种移动方式的数目。一维数组是这样做，我们可以升级到二维了。

二维解法的代码

def largestOverlap(A, B):
        N = len(A)
        #获取A矩阵中所有1的位置，放在LA中
        LA = [(i, j) for i in xrange(N) for j in xrange(N) if A[i][j]] 
        #获取B矩阵中所有1的位置，放在LB中
        LB = [(i, j) for i in xrange(N) for j in xrange(N) if B[i][j]]
        #使用A中的每个1去重叠B中的每个1，记录下移动的方式如右移1，下移1（-1，-1）
        dict = [(x1 - x2, y1 - y2) for x1, y1 in LA for x2, y2 in LB]
        #记录下相同的移动方式及这种移动方式的数量（每一种移动方式都是A中的某一点和B中的某一点重合得来的）
        #譬如如果（-1，-1）数量为3，说明通过这种移动方式有三个不同的点重合了
        c = collections.Counter(dict)
        return max(c.values() or [0])

简易手写数字识别

如果A和B越相似，则重叠的数字1越多。我觉得这可以用于手写数字识别，当然这肯定是简易版的。

import collections


def largestOverlap(A, B):
    N = len(A)
    # 获取A矩阵中所有1的位置，放在LA中
    LA = [(i, j) for i in range(N) for j in range(N) if A[i][j]]
    # 获取B矩阵中所有1的位置，放在LB中
    LB = [(i, j) for i in range(N) for j in range(N) if B[i][j]]
    # 使用A中的每个1去重叠B中的每个1，记录下移动的方式如右移1，下移1（-1，-1）
    c = [(x1 - x2, y1 - y2)for x1, y1 in LA for x2, y2 in LB]
    # 记录下相同的移动方式及这种移动方式的数量（每一种移动方式都是A中的某一点和B中的某一点重合得来的）
    # 譬如如果（-1，-1）数量为3，说明通过这种移动方式有三个不同的点重合了
    dict = collections.Counter(c)
    return max(dict.values() or [0])

listsA = []#未知的0~9
listsB = []#已知的0~9
#将所有的数字图像都存储在listsAlistsB中
for dir in ['A','B']:
    for i in range(10):
        with open("{}/{}.txt".format(dir,i),"r") as file:
            num = []
            lines = file.readlines()
            for line in lines:
                num.append([int(line[i]) for i in range(len(line)-1)])
            if dir=='A':
                listsA.append(num)
            else:
                listsB.append(num)

#取出listsA中的图像，和listsB中的全部图像匹配，重叠1多的就是对应数字
for A in listsA:
    temp = []
    for B in listsB:
        temp.append(largestOverlap(A, B))
    print("识别到：",temp.index(max(temp)))

数字资源链接：https://pan.baidu.com/s/1qWasLX7eb_EQOUr-ynOIcw
提取码：xf41
运行结果：
Image Overlap到手写数字识别
数字1，4，8识别出错，这也正常，毕竟我这也只是玩玩而已，简易版嘛！还有很多细节没有考虑

Image Overlap到手写数字识别

一维的思路

二维解法的代码

简易手写数字识别

相关推荐