干貨 | 手把手教你用115行代碼做個(gè)數(shù)獨(dú)解析器！
大數(shù)據(jù)文摘出品
來源：medium
編譯：牛婉楊
你也是數(shù)獨(dú)愛好者嗎？
Aakash Jhawar和許多人一樣，樂于挑戰(zhàn)新的難題。上學(xué)的時(shí)候，他每天早上都要玩數(shù)獨(dú)。長大后，隨著科技的進(jìn)步，我們可以讓計(jì)算機(jī)來幫我們解數(shù)獨(dú)了！只需要點(diǎn)擊數(shù)獨(dú)的圖片，它就會(huì)為你填滿全部九宮格。
叮~ 這里有一份數(shù)獨(dú)解析教程，等待你查收~ 喜歡收藏硬核干貨的小伙伴看過來~
我們都知道，數(shù)獨(dú)由9×9的格子組成，每行、列、宮各自都要填上1-9的數(shù)字，要做到每行、列、宮里的數(shù)字都不重復(fù)。
可以將解析數(shù)獨(dú)的整個(gè)過程分成3步：
第一步：從圖像中提取數(shù)獨(dú)
第二步：提取圖像中出現(xiàn)的每個(gè)數(shù)字
第三步：用算法計(jì)算數(shù)獨(dú)的解
第一步：從圖像中提取數(shù)獨(dú)
首先需要進(jìn)行圖像處理。
1、對圖像進(jìn)行預(yù)處理
首先，我們應(yīng)用高斯模糊的內(nèi)核大小(高度，寬度)為9的圖像。注意，內(nèi)核大小必須是正的和奇數(shù)的，并且內(nèi)核必須是平方的。然后使用11個(gè)最近鄰像素自適應(yīng)閾值。
proc = cv2.GaussianBlur（img.copy（），（9，9），0）proc?=?cv2.adaptiveThreshold（proc，255，cv2.ADAPTIVE_THRESH_GAUSSIAN_C，cv2.THRESH_BINARY，11，2）
為了使網(wǎng)格線具有非零像素值，我們顛倒顏色。此外，把圖像放大，以增加網(wǎng)格線的大小。
proc = cv2.bitwise_not（proc，proc）kernel = np.array（[[0。，1.，0.]，[1.，1.，1.]，[0.，1.，0.]] ，np.uint8）proc = cv2.dilate（proc，kernel）
? ? ? ?
2、找出最大多邊形的角
下一步是尋找圖像中最大輪廓的4個(gè)角。所以需要找到所有的輪廓線，按面積降序排序，然后選擇面積最大的那個(gè)。
_, contours, h = cv2.findContours(img.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)contours = sorted(contours, key=cv2.contourArea, reverse=True)polygon = contours[0]
使用的操作符。帶有max和min的itemgetter允許我們獲得該點(diǎn)的索引。每個(gè)點(diǎn)都是有1個(gè)坐標(biāo)的數(shù)組，然后[0]和[1]分別用于獲取x和y。
右下角點(diǎn)具有最大的(x + y)值；左上角有點(diǎn)最小(x + y)值；左下角則具有最小的(x - y)值；右上角則具有最大的(x - y)值。
bottom_right, _ = max(enumerate([pt[0][0] + pt[0][1] for pt inpolygon]), key=operator.itemgetter(1))top_left, _ = min(enumerate([pt[0][0] + pt[0][1] for pt inpolygon]), key=operator.itemgetter(1))bottom_left, _ = min(enumerate([pt[0][0] - pt[0][1] for pt inpolygon]), key=operator.itemgetter(1))top_right, _ = max(enumerate([pt[0][0] - pt[0][1] for pt inpolygon]), key=operator.itemgetter(1))
現(xiàn)在我們有了4個(gè)點(diǎn)的坐標(biāo)，然后需要使用索引返回4個(gè)點(diǎn)的數(shù)組。每個(gè)點(diǎn)都在自己的一個(gè)坐標(biāo)數(shù)組中。
[polygon[top_left][0], polygon[top_right][0], polygon[bottom_right][0], polygon[bottom_left][0]]
最大多邊形的四個(gè)角
3、裁剪和變形圖像
有了數(shù)獨(dú)的4個(gè)坐標(biāo)后，我們需要剪裁和彎曲一個(gè)矩形部分，從一個(gè)圖像變成一個(gè)類似大小的正方形。由左上、右上、右下和左下點(diǎn)描述的矩形。
注意：將數(shù)據(jù)類型顯式設(shè)置為float32或‘getPerspectiveTransform’會(huì)引發(fā)錯(cuò)誤。
top_left, top_right, bottom_right, bottom_left = crop_rect[0], crop_rect[1], crop_rect[2], crop_rect[3]src = np.array([top_left, top_right, bottom_right, bottom_left], dtype='float32')side = max([ distance_between(bottom_right, top_right),distance_between(top_left, bottom_left),distance_between(bottom_right, bottom_left),distance_between(top_left, top_right) ])
用計(jì)算長度的邊來描述一個(gè)正方形，這是要轉(zhuǎn)向的新視角。然后要做的是通過比較之前和之后的4個(gè)點(diǎn)來得到用于傾斜圖像的變換矩陣。最后，再對原始圖像進(jìn)行變換。
dst = np.array([[0, 0], [side - 1, 0], [side - 1, side - 1], [0, side - 1]], dtype='float32')m = cv2.getPerspectiveTransform(src, dst)cv2.warpPerspective(img, m, (int(side), int(side)))
裁剪和變形后的數(shù)獨(dú)圖像
4、從正方形圖像中推斷網(wǎng)格
從正方形圖像推斷出81個(gè)單元格。我們在這里交換 j 和 i ，這樣矩形就被存儲(chǔ)在從左到右讀取的列表中，而不是自上而下。
squares = []side = img.shape[:1]side = side[0] / 9for j in range(9):for i in range(9):p1 = (i * side, j * side) #Top left corner of a boxp2 = ((i + 1) * side, (j + 1) * side) #Bottom right cornersquares.append((p1, p2)) return squares
5、得到每一位數(shù)字
下一步是從其單元格中提取數(shù)字并構(gòu)建一個(gè)數(shù)組。
digits = []img = pre_process_image(img.copy(), skip_dilate=True)for square in squares:digits.append(extract_digit(img, square, size))
extract_digit 是從一個(gè)數(shù)獨(dú)方塊中提取一個(gè)數(shù)字(如果有的話)的函數(shù)。它從整個(gè)方框中得到數(shù)字框，使用填充特征查找來獲得框中間的最大特征，以期在邊緣找到一個(gè)屬于該數(shù)字的像素，用于定義中間的區(qū)域。接下來，需要縮放并填充數(shù)字，讓適合用于機(jī)器學(xué)習(xí)的數(shù)字大小的平方。同時(shí)，我們必須忽略任何小的邊框。
def extract_digit(img, rect, size):digit = cut_from_rect(img, rect)w = digit.shape[:2]margin = int(np.mean([h, w]) / 2.5)bbox, seed = find_largest_feature(digit, [margin, margin], [wmargin, h - margin])digit = cut_from_rect(digit, bbox)w = bbox[1][0] - bbox[0][0]h = bbox[1][1] - bbox[0][1]if w > 0 and h > 0 and (w * h) > 100 and len(digit) > 0:return scale_and_centre(digit, size, 4)else:return np.zeros((size, size), np.uint8)
? ? ? ?
最后的數(shù)獨(dú)的形象
現(xiàn)在，我們有了最終的數(shù)獨(dú)預(yù)處理圖像，下一個(gè)任務(wù)是提取圖像中的每一位數(shù)字，并將其存儲(chǔ)在一個(gè)矩陣中，然后通過某種算法計(jì)算出數(shù)獨(dú)的解。
第二步：提取圖像中出現(xiàn)的每個(gè)數(shù)字
?
對于數(shù)字識別，我們將在MNIST數(shù)據(jù)集上訓(xùn)練神經(jīng)網(wǎng)絡(luò)，該數(shù)據(jù)集包含60000張0到9的數(shù)字圖像。從導(dǎo)入所有庫開始。
import numpyimport cv2from keras.datasetsimport mnistfrom keras.modelsimport Sequentialfrom keras.layersimport Densefrom keras.layersimport Dropoutfrom keras.layersimport Flattenfrom keras.layers.convolutionalimport Conv2Dfrom keras.layers.convolutionalimport MaxPooling2Dfrom keras.utilsimport np_utilsfrom kerasimport backend as Kimport matplotlib.pyplot as plt
需要修復(fù)隨機(jī)種子以確保可重復(fù)性。
K.set_image_dim_ordering('th')seed = 7numpy.random.seed(seed)(X_train, y_train), (X_test, y_test) = mnist.load_data()
然后將圖像重塑為樣本*像素*寬度*高度，并輸入從0-255規(guī)范化為0-1。在此之后，對輸出進(jìn)行熱編碼。
X_train = X_train.reshape(X_train.shape[0], 1, 28,28).astype('float32')X_test = X_test.reshape(X_test.shape[0], 1, 28,28).astype('float32')X_train = X_train / 255X_test = X_test / 255y_train = np_utils.to_categorical(y_train)y_test = np_utils.to_categorical(y_test)num_classes = y_test.shape[1]
接下來，我們將創(chuàng)建一個(gè)模型來預(yù)測手寫數(shù)字。
model = Sequential()model.add(Conv2D(32, (5, 5), input_shape=(1, 28, 28),activation='relu'))model.add(MaxPooling2D(pool_size=(2, 2)))model.add(Conv2D(16, (3,3), activation='relu'))model.add(MaxPooling2D(pool_size=(2, 2)))model.add(Dropout(0.2))model.add(Flatten())model.add(Dense(128, activation='relu'))model.add(Dense(64, activation='relu'))model.add(Dense(num_classes, activation='softmax'))
模型總結(jié)
在創(chuàng)建模型之后，需要進(jìn)行編譯，使其適合數(shù)據(jù)集并對其進(jìn)行評估。
model.compile(loss='categorical_crossentropy', optimizer='adam',metrics=['accuracy'])model.fit(X_train, y_train, validation_data=(X_test, y_test),epochs=10, batch_size=200)scores = model.evaluate(X_test, y_test, verbose=0)print("Large CNN Error: %.2f%%" % (100-scores[1]*100))
現(xiàn)在，可以測試上面創(chuàng)建的模型了。
test_images = X_test[1:5]test_images = test_images.reshape(test_images.shape[0], 28, 28)print ("Test images shape: {}".format(test_images.shape))for i, test_image in enumerate(test_images, start=1):org_image = test_imagetest_image = test_image.reshape(1,1,28,28)prediction = model.predict_classes(test_image, verbose=0)print ("Predicted digit: {}".format(prediction[0]))plt.subplot(220+i)plt.axis('off')plt.title("Predicted digit: {}".format(prediction[0]))plt.imshow(org_image, cmap=plt.get_cmap('gray'))plt.show()
手寫體數(shù)字分類模型的預(yù)測數(shù)字
神經(jīng)網(wǎng)絡(luò)的精度為98.314%！最后，保存序列模型，這樣就不必在需要使用它的時(shí)候反復(fù)訓(xùn)練了。
# serialize model to JSONmodel_json = model.to_json()with open("model.json", "w") as json_file:json_file.write(model_json)# serialize weights to HDF5model.save_weights("model.h5")print("Saved model to disk")
更多關(guān)于手寫數(shù)字識別的信息：
https://github.com/aakashjhawar/Handwritten-Digit-Recognition
下一步是加載預(yù)先訓(xùn)練好的模型。
json_file = open('model.json', 'r')loaded_model_json = json_file.read()json_file.close()loaded_model = model_from_json(loaded_model_json)loaded_model.load_weights("model.h5")
調(diào)整圖像大小，并將圖像分割成9x9的小圖像。每個(gè)小圖像的數(shù)字都是從1-9。
sudoku = cv2.resize(sudoku, (450,450))grid = np.zeros([9,9])for i in range(9):for j in range(9):image = sudoku[i*50:(i+1)*50,j*50:(j+1)*50]if image.sum() > 25000:grid[i][j] = identify_number(image)else:grid[i][j] = 0grid = grid.astype(int)
identify_number 函數(shù)拍攝數(shù)字圖像并預(yù)測圖像中的數(shù)字。
def identify_number(image):image_resize = cv2.resize(image, (28,28)) # For plt.imshowimage_resize_2 = image_resize.reshape(1,1,28,28) # For input to model.predict_classes# cv2.imshow('number', image_test_1)loaded_model_pred = loaded_model.predict_classes(image_resize_2, verbose = 0)return loaded_model_pred[0]
?
完成以上步驟后，數(shù)獨(dú)網(wǎng)格看起來是這樣的：
提取的數(shù)獨(dú)
第三步：用回溯算法計(jì)算數(shù)獨(dú)的解
?
我們將使用回溯算法來計(jì)算數(shù)獨(dú)的解。
在網(wǎng)格中搜索仍未分配的條目。如果找到引用參數(shù)行，col 將被設(shè)置為未分配的位置，而 true 將被返回。如果沒有未分配的條目保留，則返回false?！發(fā)” 是 solve_sudoku 函數(shù)傳遞的列表變量，用于跟蹤行和列的遞增。
def find_empty_location(arr,l):for row in range(9):for col in range(9):if(arr[row][col]==0):l[0]=rowl[1]=colreturn Truereturn False
返回一個(gè)boolean，指示指定行的任何賦值項(xiàng)是否與給定數(shù)字匹配。
def used_in_row(arr,row,num):for i in range(9):if(arr[row][i] == num):return Truereturn False
返回一個(gè)boolean，指示指定列中的任何賦值項(xiàng)是否與給定數(shù)字匹配。
def used_in_col(arr,col,num):for i in range(9):if(arr[i][col] == num):return Truereturn False
返回一個(gè)boolean，指示指定的3x3框內(nèi)的任何賦值項(xiàng)是否與給定的數(shù)字匹配。
def used_in_box(arr,row,col,num):for i in range(3):for j in range(3):if(arr[i+row][j+col] == num):return True????return?False
檢查將num分配給給定的(row, col)是否合法。檢查“ num”是否尚未放置在當(dāng)前行，當(dāng)前列和當(dāng)前3x3框中。
def check_location_is_safe(arr,row,col,num):return not used_in_row(arr,row,num) andnot used_in_col(arr,col,num) andnot used_in_box(arr,row - row%3,col - col%3,num)
采用部分填入的網(wǎng)格，并嘗試為所有未分配的位置分配值，以滿足數(shù)獨(dú)解決方案的要求(跨行、列和框的非重復(fù))?！發(fā)” 是一個(gè)列表變量，在 find_empty_location 函數(shù)中保存行和列的記錄。將我們從上面的函數(shù)中得到的行和列賦值給列表值。
def solve_sudoku(arr):l=[0,0]if(not find_empty_location(arr,l)):return Truerow=l[0]col=l[1]for num in range(1,10):if(check_location_is_safe(arr,row,col,num)):arr[row][col]=numif(solve_sudoku(arr)):return True# failure, unmake & try againarr[row][col] = 0return False
最后一件事是print the grid。
def print_grid(arr):for i in range(9):for j in range(9):print (arr[i][j])????????print?('\n')
最后，把所有的函數(shù)整合在主函數(shù)中。
def sudoku_solver(grid):if(solve_sudoku(grid)):print('---')else:print ("No solution exists")grid = grid.astype(int)return grid
這個(gè)函數(shù)的輸出將是最終解出的數(shù)獨(dú)。
最終的解決方案
當(dāng)然，這個(gè)解決方案絕不是萬無一失的，處理圖像時(shí)仍然會(huì)出現(xiàn)一些問題，要么無法解析，要么解析錯(cuò)誤導(dǎo)致無法處理。不過，我們的目標(biāo)是探索新技術(shù)，從這個(gè)角度來看，這個(gè)項(xiàng)目還是有價(jià)值的。
相關(guān)報(bào)道：
https://medium.com/@aakashjhawar/sudoku-solver-using-opencv-and-dl-part-1-490f08701179
https://medium.com/@aakashjhawar/sudoku-solver-using-opencv-and-dl-part-2-bbe0e6ac87c5
實(shí)習(xí)/全職編輯記者招聘ing
加入我們，親身體驗(yàn)一家專業(yè)科技媒體采寫的每個(gè)細(xì)節(jié)，在最有前景的行業(yè)，和一群遍布全球最優(yōu)秀的人一起成長。坐標(biāo)北京·清華東門，在大數(shù)據(jù)文摘主頁對話頁回復(fù)“招聘”了解詳情。簡歷請直接發(fā)送至[email protected]
