Python图像识别+KNN求解数独的实现

Python-opencv+KNN求解数独

最近一直在玩数独,突发奇想实现图像识别求解数独,输入到输出平均需要0.5s。

整体思路大概就是识别出图中数字生成list,然后求解。

输入输出demo

数独采用的是微软自带的Microsoft sudoku软件随便截取的图像,如下图所示:

经过程序求解后,得到的结果如下图所示:

程序具体流程

程序整体流程如下图所示:

读入图像后,根据求解轮廓信息找到数字所在位置,以及不包含数字的空白位置,提取数字信息通过KNN识别,识别出数字;无数字信息的在list中置0;生成未求解数独list,之后求解数独,将信息在原图中显示出来。

# -*-coding:utf-8-*-
import os
import cv2 as cv
import numpy as np
import time

####################################################
#寻找数字生成list
def find_dig_(img, train_set):
  if img is None:
    print("无效的图片!")
    os._exit(0)
    return
  _, thre = cv.threshold(img, 230, 250, cv.THRESH_BINARY_INV)
  _, contours, hierarchy = cv.findContours(thre, cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE)
  sudoku_list = []
  boxes = []
  for i in range(len(hierarchy[0])):
    if hierarchy[0][i][3] == 0: # 表示父轮廓为 0
      boxes.append(hierarchy[0][i])
  # 提取数字
  nm = []
  for j in range(len(boxes)):  # 此处len(boxes)=81
    if boxes[j][2] != -1:
      x, y, w, h = cv.boundingRect(contours[boxes[j][2]])
      nm.append([x, y, w, h])
      # 在原图中框选各个数字
      cropped = img[y:y + h, x:x + w]
      im = img_pre(cropped)			#预处理
      AF = incise(im)				#切割数字图像
      result = identification(train_set, AF, 7)		#knn识别
      sudoku_list.insert(0, int(result))				#生成list
    else:
      sudoku_list.insert(0, 0)

  if len(sudoku_list) == 81:
    sudoku_list= np.array(sudoku_list)
    sudoku_list= sudoku_list.reshape((9, 9))
    print("old_sudoku -> \n", sudoku_list)
    return sudoku_list, contours, hierarchy
  else:
    print("无效的图片!")
    os._exit(0)

######################################################
#KNN算法识别数字
def img_pre(cropped):
  # 预处理数字图像
  im = np.array(cropped) # 转化为二维数组
  for i in range(im.shape[0]): # 转化为二值矩阵
    for j in range(im.shape[1]):
      # print(im[i, j])
      if im[i, j] != 255:
        im[i, j] = 1
      else:
        im[i, j] = 0
  return im

# 提取图片特征
def feature(A):
  midx = int(A.shape[1] / 2) + 1
  midy = int(A.shape[0] / 2) + 1
  A1 = A[0:midy, 0:midx].mean()
  A2 = A[midy:A.shape[0], 0:midx].mean()
  A3 = A[0:midy, midx:A.shape[1]].mean()
  A4 = A[midy:A.shape[0], midx:A.shape[1]].mean()
  A5 = A.mean()
  AF = [A1, A2, A3, A4, A5]
  return AF

# 切割图片并返回每个子图片特征
def incise(im):
  # 竖直切割并返回切割的坐标
  a = [];
  b = []
  if any(im[:, 0] == 1):
    a.append(0)
  for i in range(im.shape[1] - 1):
    if all(im[:, i] == 0) and any(im[:, i + 1] == 1):
      a.append(i + 1)
    elif any(im[:, i] == 1) and all(im[:, i + 1] == 0):
      b.append(i + 1)
  if any(im[:, im.shape[1] - 1] == 1):
    b.append(im.shape[1])
  # 水平切割并返回分割图片特征
  names = locals();
  AF = []
  for i in range(len(a)):
    names['na%s' % i] = im[:, range(a[i], b[i])]
    if any(names['na%s' % i][0, :] == 1):
      c = 0
    else:
      for j in range(names['na%s' % i].shape[0]):
        if j < names['na%s' % i].shape[0] - 1:
          if all(names['na%s' % i][j, :] == 0) and any(names['na%s' % i][j + 1, :] == 1):
            c = j
            break
        else:
          c = j
    if any(names['na%s' % i][names['na%s' % i].shape[0] - 1, :] == 1):
      d = names['na%s' % i].shape[0] - 1
    else:
      for j in range(names['na%s' % i].shape[0]):
        if j < names['na%s' % i].shape[0] - 1:
          if any(names['na%s' % i][j, :] == 1) and all(names['na%s' % i][j + 1, :] == 0):
            d = j + 1
            break
        else:
          d = j
    names['na%s' % i] = names['na%s' % i][range(c, d), :]
    AF.append(feature(names['na%s' % i])) # 提取特征
    for j in names['na%s' % i]:
      pass
  return AF

# 训练已知图片的特征
def training():
  train_set = {}
  for i in range(9):
    value = []
    for j in range(15):
      ima = cv.imread('E:/test_image/knn_test/{}/{}.png'.format(i + 1, j + 1), 0)
      im = img_pre(ima)
      AF = incise(im)
      value.append(AF[0])
    train_set[i + 1] = value

  return train_set

# 计算两向量的距离
def distance(v1, v2):
  vector1 = np.array(v1)
  vector2 = np.array(v2)
  Vector = (vector1 - vector2) ** 2
  distance = Vector.sum() ** 0.5
  return distance

# 用最近邻算法识别单个数字
def knn(train_set, V, k):
  key_sort = [11] * k
  value_sort = [11] * k
  for key in range(1, 10):
    for value in train_set[key]:
      d = distance(V, value)
      for i in range(k):
        if d < value_sort[i]:
          for j in range(k - 2, i - 1, -1):
            key_sort[j + 1] = key_sort[j]
            value_sort[j + 1] = value_sort[j]
          key_sort[i] = key
          value_sort[i] = d
          break
  max_key_count = -1
  key_set = set(key_sort)
  for key in key_set:
    if max_key_count < key_sort.count(key):
      max_key_count = key_sort.count(key)
      max_key = key
  return max_key

# 生成数字
def identification(train_set, AF, k):
  result = ''
  for i in AF:
    key = knn(train_set, i, k)
    result = result + str(key)
  return result

######################################################
######################################################
#求解数独
def get_next(m, x, y):
  # 获得下一个空白格在数独中的坐标。
  :param m 数独矩阵
  :param x 空白格行数
  :param y 空白格列数
  """
  for next_y in range(y + 1, 9): # 下一个空白格和当前格在一行的情况
    if m[x][next_y] == 0:
      return x, next_y
  for next_x in range(x + 1, 9): # 下一个空白格和当前格不在一行的情况
    for next_y in range(0, 9):
      if m[next_x][next_y] == 0:
        return next_x, next_y
  return -1, -1 # 若不存在下一个空白格,则返回 -1,-1

def value(m, x, y):
  # 返回符合"每个横排和竖排以及九宫格内无相同数字"这个条件的有效值。

  i, j = x // 3, y // 3
  grid = [m[i * 3 + r][j * 3 + c] for r in range(3) for c in range(3)]
  v = set([x for x in range(1, 10)]) - set(grid) - set(m[x]) - \
    set(list(zip(*m))[y])
  return list(v)

def start_pos(m):
  # 返回第一个空白格的位置坐标
  for x in range(9):
    for y in range(9):
      if m[x][y] == 0:
        return x, y
  return False, False # 若数独已完成,则返回 False, False

def try_sudoku(m, x, y):
  # 试着填写数独
  for v in value(m, x, y):
    m[x][y] = v
    next_x, next_y = get_next(m, x, y)
    if next_y == -1: # 如果无下一个空白格
      return True
    else:
      end = try_sudoku(m, next_x, next_y) # 递归
      if end:
        return True
      m[x][y] = 0 # 在递归的过程中,如果数独没有解开,
      # 则回溯到上一个空白格

def sudoku_so(m):
  x, y = start_pos(m)
  try_sudoku(m, x, y)
  print("new_sudoku -> \n", m)
  return m

###################################################
# 将结果绘制到原图
def draw_answer(img, contours, hierarchy, new_sudoku_list ):
  new_sudoku_list = new_sudoku_list .flatten().tolist()
  for i in range(len(contours)):
    cnt = contours[i]
    if hierarchy[0, i, -1] == 0:
      num = new_soduku_list.pop(-1)
      if hierarchy[0, i, 2] == -1:
        x, y, w, h = cv.boundingRect(cnt)
        cv.putText(img, "%d" % num, (x + 19, y + 56), cv.FONT_HERSHEY_SIMPLEX, 1.8, (0, 0, 255), 2) # 填写数字
  cv.imwrite("E:/answer.png", img)

if __name__ == '__main__':
  t1 = time.time()
  train_set = training()
  img = cv.imread('E:/test_image/python_test_img/Sudoku.png')
  img_gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)
  sudoku_list, contours, hierarchy = find_dig_(img_gray, train_set)
  new_sudoku_list = sudoku_so(sudoku_list)
  draw_answer(img, contours, hierarchy, new_sudoku_list )
  print("time :",time.time()-t1)

PS:

使用KNN算法需要创建训练集,数独中共涉及9个数字,“1,2,3,4,5,6,7,8,9”各15幅图放入文件夹中,如下图所示。

到此这篇关于Python图像识别+KNN求解数独的实现的文章就介绍到这了,更多相关Python KNN求解数独内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 用Python解数独的方法示例

    芬兰数学家因卡拉花费3个月时间设计出的世界上迄今难度最大的数独.数独是 9 横 9 竖共有 81 个格子,同时又分为 9 个九宫格.规则很简单:每个空格填入 1~9 任意一个数字,需要保证每个横排和竖排以及九宫格内无相同数字. 解数独是一个可有可无的爱好,知道这个益智游戏,但是不很上心.但是前两天,由于自己的学生装了一个 ubuntu 18.04 的系统,上面有一些数独游戏,偶然间,让我看见了,为了更好的显摆自己的 Python 知识,决定用 Python 写一个程序,所以就有了下面的文字. 1

  • 简单实现python数独游戏

    网上看到一个python写的数独,很好玩,分享给大家. import random import itertools from copy import deepcopy def make_board(m = 3): numbers = list(range(1, m**2 + 1)) board = None while board is None: board = attempt_board(m, numbers) return board def attempt_board(m, numbe

  • python实现解数独程序代码

    偶然发现linux系统附带的一个数独游戏,打开玩了几把.无奈是个数独菜鸟,以前没玩过,根本就走不出几步就一团浆糊了. 于是就打算借助计算机的强大运算力来暴力解数独,还是很有乐趣的. 下面就记录一下我写解数独程序的一些思路和心得. 一.数独游戏的基本解决方法 编程笼统的来说,就是个方法论.不论什么程序,都必须将问题的解决过程分解成计算机可以实现的若干个简单方法.俗话说,大道至简.对于只能明白0和1的计算机来说,就更需要细分步骤,一步一步的解决问题了. 首先来思考一下解数独的基本概念. 数独横九竖九

  • python实现自动解数独小程序

    跟朋友最近聊起来数独游戏,突发奇想使用python编写一个自动计算数独解的小程序. 数独的规则不再过多阐述,在此描述一下程序的主要思路: (当前程序只针对于简单的数独,更复杂的还待深入挖掘) 1.计算当前每个空格可能的取值集合,并将空格顺序值对应取值集合置于字典中: 2.对取值集合位数为1,即空格处为单一取值的进行赋值,(填入动作),重复1刷新字典直到字典为空位置: 当前实现如下: 1.将数独输入列表中,并定义函数count_candinate_number(j)根据数独规则计算每一个为0的位置

  • python实现数独算法实例

    本文实例讲述了python实现数独算法的方法.分享给大家供大家参考.具体如下: # -*- coding: utf-8 -*- ''' Created on 2012-10-5 @author: Administrator ''' from collections import defaultdict import itertools a = [ [ 0, 7, 0, 0, 0, 0, 0, 0, 0], #0 [ 5, 0, 3, 0, 0, 6, 0, 0, 0], #1 [ 0, 6, 2

  • Python如何判断数独是否合法

    介绍 该数独可能只填充了部分数字,其中缺少的数字用 . 表示. 注意事项 一个合法的数独(仅部分填充)并不一定是可解的.我们仅需使填充的空格有效即可. 解体思路 将数独按照行.列和块进行预处理,然后分别判断是否合法. 利用Python的表达式推导,匿名函数和all函数可以很方便的进行处理. 代码 class Solution: # @param board, a 9x9 2D array # @return a boolean def isValidSudoku(self, board): ro

  • Python判断有效的数独算法示例

    本文实例讲述了Python判断有效的数独算法.分享给大家供大家参考,具体如下: 一.题目 判断一个 9x9 的数独是否有效.只需要根据以下规则,验证已经填入的数字是否有效即可. 1. 数字 1-9 在每一行只能出现一次. 2. 数字 1-9 在每一列只能出现一次. 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次. 数独部分空格内已填入了数字,空白格用 '.' 表示. 例1: 输入: [ ["5","3",".","

  • python3.6数独问题的解决

    算法比较暴力,直接用穷举的方式一个一个去试,所以程序运行时间会比较长,运行时间视数独而定. 不过从一开始到运行成功,整个过程却是一波三折,设计算法就花了不少时间,然后就是不断地去调试,找bug.刚开始的时候为了省事直接在sudoku类中递归调用blank,但是老哥还是too young too simple,sometimes navie,计算量实在是太大了,后面编译器直接抛出 "RecursionError: maximum recursion depth exceeded while cal

  • python实现数独游戏 java简单实现数独游戏

    使用python和java实现数独游戏,有比较才有收获哦. 1.Python版 #--coding:utf-8-- import random import itertools from copy import deepcopy def make_board(m=3): numbers = list(range(1,m**2+1)) #可能出现的数字为1-9 board = None #board是数度二维列表 while board is None: board = get_board(m,n

  • 150行Python代码实现带界面的数独游戏

    今天闲着没事干,以前做过html+js版的数独,这次做个python版本的,界面由pygame完成,数独生成由递归算法实现,由shuffle保证每次游戏都是不一样的情况,have fun: 功能列表: 图形化的数独游戏: python实现,依赖pygame库: 随机生成游戏,每次运行都不一样: 数字填入后的正确性判断以及颜色提示: 显示剩余需填入的空格,已经操作的次数: 难度可选,通过修改需要填入的空的数量:  游戏界面 初始界面 过程中界面 运行方式 python main.py 15 这里的

随机推荐