Bagaimana cara menghapus cacat kecembungan pada kotak Sudoku?

Saya sedang melakukan proyek yang menyenangkan: Memecahkan Sudoku dari gambar input menggunakan OpenCV (seperti di Google goggles dll). Dan saya telah menyelesaikan tugas, tetapi pada akhirnya saya menemukan sedikit masalah di mana saya datang ke sini.

Saya melakukan pemrograman menggunakan Python API dari OpenCV 2.3.1.

Di bawah ini yang saya lakukan:

1. Baca gambarnya
2. Temukan kontur
3. Pilih satu dengan luas maksimum, (dan juga agak setara dengan kuadrat).

4. Temukan titik sudut.

   misalnya diberikan di bawah ini:

   

   ( Perhatikan di sini bahwa garis hijau bertepatan dengan benar dengan batas sejati Sudoku, sehingga Sudoku dapat dibengkokkan dengan benar . Periksa gambar berikutnya)

5. warp gambar ke kotak yang sempurna

   misalnya gambar:

   

6. Lakukan OCR (yang saya gunakan metode yang saya berikan dalam Simple Digit Recognition OCR di OpenCV-Python )

Dan metodenya bekerja dengan baik.

Masalah:

Lihat gambar ini.

Melakukan langkah 4 pada gambar ini memberikan hasil di bawah ini:

Garis merah yang digambar adalah kontur asli yang merupakan garis besar batas sudoku yang sebenarnya.

Garis hijau yang ditarik adalah kontur yang diperkirakan yang akan menjadi garis besar gambar melengkung.

Yang tentu saja, ada perbedaan antara garis hijau dan garis merah di tepi atas sudoku. Jadi saat warping, saya tidak mendapatkan batas asli dari Sudoku.

Pertanyaan saya :

Bagaimana saya bisa melengkungkan gambar pada batas Sudoku yang benar, yaitu garis merah ATAU bagaimana saya bisa menghapus perbedaan antara garis merah dan garis hijau? Apakah ada metode untuk ini di OpenCV?

Saya punya solusi yang berfungsi, tetapi Anda harus menerjemahkannya sendiri ke OpenCV. Itu ditulis dalam Mathematica.

Langkah pertama adalah menyesuaikan kecerahan pada gambar, dengan membagi setiap piksel dengan hasil operasi penutupan:

src = ColorConvert[Import["http://davemark.com/images/sudoku.jpg"], "Grayscale"];
white = Closing[src, DiskMatrix[5]];
srcAdjusted = Image[ImageData[src]/ImageData[white]]

Langkah selanjutnya adalah menemukan area sudoku, jadi saya bisa mengabaikan (menutupi) latar belakang. Untuk itu, saya menggunakan analisis komponen terhubung, dan pilih komponen yang punya area cembung terbesar:

components = 
  ComponentMeasurements[
    ColorNegate@Binarize[srcAdjusted], {"ConvexArea", "Mask"}][[All, 
    2]];
largestComponent = Image[SortBy[components, First][[-1, 2]]]

Dengan mengisi gambar ini, saya mendapatkan topeng untuk kisi sudoku:

mask = FillingTransform[largestComponent]

Sekarang, saya dapat menggunakan filter turunan urutan ke-2 untuk menemukan garis vertikal dan horizontal dalam dua gambar terpisah:

lY = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {2, 0}], {0.02, 0.05}], mask];
lX = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {0, 2}], {0.02, 0.05}], mask];

Saya menggunakan analisis komponen terhubung lagi untuk mengekstrak garis grid dari gambar-gambar ini. Garis kisi jauh lebih panjang daripada angka, jadi saya bisa menggunakan panjang caliper untuk memilih hanya komponen yang terhubung garis kisi. Mengurutkan mereka berdasarkan posisi, saya mendapatkan gambar topeng 2x10 untuk setiap garis kisi vertikal / horizontal pada gambar:

verticalGridLineMasks = 
  SortBy[ComponentMeasurements[
      lX, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All, 
      2]], #[[2, 1]] &][[All, 3]];
horizontalGridLineMasks = 
  SortBy[ComponentMeasurements[
      lY, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All, 
      2]], #[[2, 2]] &][[All, 3]];

Selanjutnya saya mengambil setiap pasangan garis grid vertikal / horizontal, melebarkannya, menghitung persimpangan pixel-demi-pixel, dan menghitung pusat hasilnya. Titik-titik ini adalah persimpangan garis kisi:

centerOfGravity[l_] := 
 ComponentMeasurements[Image[l], "Centroid"][[1, 2]]
gridCenters = 
  Table[centerOfGravity[
    ImageData[Dilation[Image[h], DiskMatrix[2]]]*
     ImageData[Dilation[Image[v], DiskMatrix[2]]]], {h, 
    horizontalGridLineMasks}, {v, verticalGridLineMasks}];

Langkah terakhir adalah mendefinisikan dua fungsi interpolasi untuk pemetaan X / Y melalui titik-titik ini, dan mengubah gambar menggunakan fungsi-fungsi ini:

fnX = ListInterpolation[gridCenters[[All, All, 1]]];
fnY = ListInterpolation[gridCenters[[All, All, 2]]];
transformed = 
 ImageTransformation[
  srcAdjusted, {fnX @@ Reverse[#], fnY @@ Reverse[#]} &, {9*50, 9*50},
   PlotRange -> {{1, 10}, {1, 10}}, DataRange -> Full]

Semua operasi adalah fungsi pemrosesan gambar dasar, jadi ini juga harus dimungkinkan di OpenCV. Transformasi gambar berbasis spline mungkin lebih sulit, tetapi saya tidak berpikir Anda benar-benar membutuhkannya. Mungkin menggunakan transformasi perspektif yang Anda gunakan sekarang pada setiap sel individu akan memberikan hasil yang cukup baik.

Jawaban Nikie memecahkan masalah saya, tetapi jawabannya ada di Mathematica. Jadi saya pikir saya harus memberikan adaptasi OpenCV di sini. Tetapi setelah mengimplementasikan saya bisa melihat bahwa kode OpenCV jauh lebih besar dari kode natici Mathematica. Dan juga, saya tidak bisa menemukan metode interpolasi yang dilakukan oleh nikie di OpenCV (walaupun itu bisa dilakukan dengan menggunakan scipy, saya akan memberi tahu kapan saatnya tiba.)

1. Image PreProcessing (operasi penutupan)

import cv2
import numpy as np

img = cv2.imread('dave.jpg')
img = cv2.GaussianBlur(img,(5,5),0)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
mask = np.zeros((gray.shape),np.uint8)
kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))

close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)
div = np.float32(gray)/(close)
res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)

Hasil:

2. Menemukan Sudoku Square dan Membuat Gambar Topeng

thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)
contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)

max_area = 0
best_cnt = None
for cnt in contour:
    area = cv2.contourArea(cnt)
    if area > 1000:
        if area > max_area:
            max_area = area
            best_cnt = cnt

cv2.drawContours(mask,[best_cnt],0,255,-1)
cv2.drawContours(mask,[best_cnt],0,0,2)

res = cv2.bitwise_and(res,mask)

Hasil:

3. Menemukan garis vertikal

kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))

dx = cv2.Sobel(res,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)

contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if h/w > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()

Hasil:

4. Menemukan Garis Horizontal

kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy = cv2.Sobel(res,cv2.CV_16S,0,2)
dy = cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely)

contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if w/h > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)

close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)
closey = close.copy()

Hasil:

Tentu saja, yang ini tidak begitu baik.

5. Menemukan Poin Grid

res = cv2.bitwise_and(closex,closey)

Hasil:

6. Memperbaiki cacat

Di sini, nikie melakukan semacam interpolasi, tentang yang aku tidak punya banyak pengetahuan. Dan saya tidak dapat menemukan fungsi yang sesuai untuk OpenCV ini. (mungkin ada di sana, saya tidak tahu).

Lihatlah SOF ini yang menjelaskan bagaimana melakukan ini menggunakan SciPy, yang saya tidak ingin gunakan: Transformasi gambar di OpenCV

Jadi, di sini saya mengambil 4 sudut dari masing-masing sub-square dan menerapkan warp Perspektif untuk masing-masing.

Untuk itu, pertama kita temukan centroid.

contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
centroids = []
for cnt in contour:
    mom = cv2.moments(cnt)
    (x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])
    cv2.circle(img,(x,y),4,(0,255,0),-1)
    centroids.append((x,y))

Tetapi centroid yang dihasilkan tidak akan disortir. Lihat gambar di bawah ini untuk melihat pesanan mereka:

Jadi kami mengurutkannya dari kiri ke kanan, atas ke bawah.

centroids = np.array(centroids,dtype = np.float32)
c = centroids.reshape((100,2))
c2 = c[np.argsort(c[:,1])]

b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in xrange(10)])
bm = b.reshape((10,10,2))

Sekarang lihat di bawah pesanan mereka:

Akhirnya kami menerapkan transformasi dan membuat gambar baru berukuran 450x450.

output = np.zeros((450,450,3),np.uint8)
for i,j in enumerate(b):
    ri = i/10
    ci = i%10
    if ci != 9 and ri!=9:
        src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))
        dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)
        retval = cv2.getPerspectiveTransform(src,dst)
        warp = cv2.warpPerspective(res2,retval,(450,450))
        output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()

Hasil:

Hasilnya hampir sama dengan nikie, tetapi panjang kode besar. Mungkin, metode yang lebih baik tersedia di luar sana, tetapi sampai saat itu, ini berfungsi dengan baik.

Salam ARK.

Anda dapat mencoba menggunakan beberapa jenis pemodelan berbasis grid dari Anda sembarang warping. Dan karena sudoku sudah berupa kisi, itu seharusnya tidak terlalu sulit.

Jadi, Anda bisa mencoba mendeteksi batas setiap subkawasan 3x3 dan kemudian membengkokkan masing-masing wilayah secara terpisah. Jika deteksi berhasil, itu akan memberi Anda perkiraan yang lebih baik.

Saya ingin menambahkan bahwa metode di atas hanya berfungsi ketika papan sudoku berdiri tegak, jika tidak, uji rasio tinggi / lebar (atau sebaliknya) kemungkinan besar akan gagal dan Anda tidak akan dapat mendeteksi tepi sudoku. (Saya juga ingin menambahkan bahwa jika garis yang tidak tegak lurus terhadap batas gambar, operasi sobel (dx dan dy) akan tetap berfungsi karena garis masih akan memiliki tepi sehubungan dengan kedua sumbu.)

Untuk dapat mendeteksi garis lurus, Anda harus mengerjakan analisis kontur atau piksel-bijaksana seperti contourArea / boundingRectArea, titik kiri atas dan kanan bawah ...

Sunting: Saya berhasil memeriksa apakah satu set kontur membentuk garis atau tidak dengan menerapkan regresi linier dan memeriksa kesalahan. Namun regresi linier berkinerja buruk ketika kemiringan garis terlalu besar (yaitu> 1000) atau sangat dekat dengan 0. Oleh karena itu menerapkan uji rasio di atas (dalam sebagian besar jawaban tervvotasikan) sebelum regresi linier logis dan berhasil bagi saya.

Untuk menghapus sudut yang tidak terlindungi, saya menerapkan koreksi gamma dengan nilai gamma 0,8.

Lingkaran merah digambar untuk menunjukkan sudut yang hilang.

Kode tersebut adalah:

gamma = 0.8
invGamma = 1/gamma
table = np.array([((i / 255.0) ** invGamma) * 255
                  for i in np.arange(0, 256)]).astype("uint8")
cv2.LUT(img, table, img)

Ini sebagai tambahan atas jawaban Abid Rahman jika beberapa titik sudut hilang.

Saya pikir ini adalah pos yang bagus, dan solusi yang bagus oleh ARK; ditata dengan sangat baik dan dijelaskan.

Saya sedang mengerjakan masalah yang sama, dan membangun semuanya. Ada beberapa perubahan (yaitu xrange to range, argumen di cv2.findContours), tetapi ini harus bekerja di luar kotak (Python 3.5, Anaconda).

Ini adalah kompilasi dari elemen-elemen di atas, dengan beberapa kode yang hilang ditambahkan (yaitu, pelabelan poin).

'''

/programming/10196198/how-to-remove-convexity-defects-in-a-sudoku-square

'''

import cv2
import numpy as np

img = cv2.imread('test.png')

winname="raw image"
cv2.namedWindow(winname)
cv2.imshow(winname, img)
cv2.moveWindow(winname, 100,100)


img = cv2.GaussianBlur(img,(5,5),0)

winname="blurred"
cv2.namedWindow(winname)
cv2.imshow(winname, img)
cv2.moveWindow(winname, 100,150)

gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
mask = np.zeros((gray.shape),np.uint8)
kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))

winname="gray"
cv2.namedWindow(winname)
cv2.imshow(winname, gray)
cv2.moveWindow(winname, 100,200)

close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)
div = np.float32(gray)/(close)
res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)

winname="res2"
cv2.namedWindow(winname)
cv2.imshow(winname, res2)
cv2.moveWindow(winname, 100,250)

 #find elements
thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)
img_c, contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)

max_area = 0
best_cnt = None
for cnt in contour:
    area = cv2.contourArea(cnt)
    if area > 1000:
        if area > max_area:
            max_area = area
            best_cnt = cnt

cv2.drawContours(mask,[best_cnt],0,255,-1)
cv2.drawContours(mask,[best_cnt],0,0,2)

res = cv2.bitwise_and(res,mask)

winname="puzzle only"
cv2.namedWindow(winname)
cv2.imshow(winname, res)
cv2.moveWindow(winname, 100,300)

# vertical lines
kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))

dx = cv2.Sobel(res,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)

img_d, contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if h/w > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()

winname="vertical lines"
cv2.namedWindow(winname)
cv2.imshow(winname, img_d)
cv2.moveWindow(winname, 100,350)

# find horizontal lines
kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy = cv2.Sobel(res,cv2.CV_16S,0,2)
dy = cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely)

img_e, contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)

for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if w/h > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)

close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)
closey = close.copy()

winname="horizontal lines"
cv2.namedWindow(winname)
cv2.imshow(winname, img_e)
cv2.moveWindow(winname, 100,400)


# intersection of these two gives dots
res = cv2.bitwise_and(closex,closey)

winname="intersections"
cv2.namedWindow(winname)
cv2.imshow(winname, res)
cv2.moveWindow(winname, 100,450)

# text blue
textcolor=(0,255,0)
# points green
pointcolor=(255,0,0)

# find centroids and sort
img_f, contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
centroids = []
for cnt in contour:
    mom = cv2.moments(cnt)
    (x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])
    cv2.circle(img,(x,y),4,(0,255,0),-1)
    centroids.append((x,y))

# sorting
centroids = np.array(centroids,dtype = np.float32)
c = centroids.reshape((100,2))
c2 = c[np.argsort(c[:,1])]

b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in range(10)])
bm = b.reshape((10,10,2))

# make copy
labeled_in_order=res2.copy()

for index, pt in enumerate(b):
    cv2.putText(labeled_in_order,str(index),tuple(pt),cv2.FONT_HERSHEY_DUPLEX, 0.75, textcolor)
    cv2.circle(labeled_in_order, tuple(pt), 5, pointcolor)

winname="labeled in order"
cv2.namedWindow(winname)
cv2.imshow(winname, labeled_in_order)
cv2.moveWindow(winname, 100,500)

# create final

output = np.zeros((450,450,3),np.uint8)
for i,j in enumerate(b):
    ri = int(i/10) # row index
    ci = i%10 # column index
    if ci != 9 and ri!=9:
        src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))
        dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)
        retval = cv2.getPerspectiveTransform(src,dst)
        warp = cv2.warpPerspective(res2,retval,(450,450))
        output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()

winname="final"
cv2.namedWindow(winname)
cv2.imshow(winname, output)
cv2.moveWindow(winname, 600,100)

cv2.waitKey(0)
cv2.destroyAllWindows()