python सुडोकू वर्ग में उत्परिवर्तन दोषों को कैसे हटाया जाए?




opencv computer-vision (3)

मैं एक मजेदार प्रोजेक्ट कर रहा था: ओपनसीवी (जैसे Google चश्मा इत्यादि) का उपयोग कर इनपुट छवि से सुडोकू को हल करना। और मैंने कार्य पूरा कर लिया है, लेकिन अंत में मुझे एक छोटी सी समस्या मिली जिसके लिए मैं यहां आया था।

मैंने ओपनसीवी 2.3.1 के पायथन एपीआई का उपयोग कर प्रोग्रामिंग किया।

नीचे मैंने जो किया है:

  1. छवि पढ़ें
  2. समोच्च खोजें
  3. अधिकतम क्षेत्र वाला एक चुनें, (और वर्ग के बराबर कुछ हद तक)।
  4. कोने अंक खोजें।

    उदाहरण के लिए नीचे दिया गया है:

    ( यहां ध्यान दें कि हरी रेखा सुडोकू की सही सीमा के साथ सही ढंग से मेल खाती है, इसलिए सुडोकू को सही तरीके से खराब किया जा सकता है । अगली छवि जांचें)

  5. एक पूर्ण वर्ग के लिए छवि warp

    उदाहरण के लिए छवि:

  6. ओसीआर करें (जिसके लिए मैंने ओपनसीवी-पायथन में सरल डिजिट रिकग्निशन ओसीआर में दी गई विधि का उपयोग किया)

और विधि अच्छी तरह से काम किया।

मुसीबत:

इस छवि को देखें।

इस छवि पर चरण 4 करने से नीचे परिणाम मिलता है:

खींची गई लाल रेखा मूल समोच्च है जो सुडोकू सीमा की वास्तविक रूपरेखा है।

तैयार की गई हरी रेखा अनुमानित समोच्च है जो विकृत छवि की रूपरेखा होगी।

निश्चित रूप से, सुडोकू के शीर्ष किनारे पर हरी रेखा और लाल रेखा के बीच अंतर है। तो युद्ध करते समय, मुझे सुडोकू की मूल सीमा नहीं मिल रही है।

मेरा प्रश्न :

मैं सुडोकू की सही सीमा पर छवि को कैसे घुमा सकता हूं, यानी लाल रेखा या लाल रेखा और हरे रंग की रेखा के बीच अंतर कैसे हटा सकता हूं? ओपनसीवी में इसके लिए कोई तरीका है?


मेरे पास एक समाधान है जो काम करता है, लेकिन आपको इसे ओपनसीवी में अनुवाद करना होगा। यह गणित में लिखा है।

पहला चरण एक बंद संचालन के परिणामस्वरूप प्रत्येक पिक्सेल को विभाजित करके, छवि में चमक समायोजित करना है:

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

अगला कदम सुडोकू क्षेत्र ढूंढना है, इसलिए मैं पृष्ठभूमि को अनदेखा कर सकता हूं (मास्क आउट)। इसके लिए, मैं कनेक्टेड घटक विश्लेषण का उपयोग करता हूं, और उस घटक का चयन करता हूं जो सबसे बड़ा उत्तल क्षेत्र प्राप्त करता है:

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

इस छवि को भरकर, मुझे सुडोकू ग्रिड के लिए एक मुखौटा मिलता है:

mask = FillingTransform[largestComponent]

अब, मैं दो अलग-अलग छवियों में लंबवत और क्षैतिज रेखाओं को खोजने के लिए दूसरे ऑर्डर व्युत्पन्न फ़िल्टर का उपयोग कर सकता हूं:

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];

मैं इन छवियों से ग्रिड लाइनों को निकालने के लिए फिर से जुड़े घटक विश्लेषण का उपयोग करता हूं। ग्रिड लाइनें अंकों की तुलना में काफी लंबी हैं, इसलिए मैं केवल ग्रिड लाइन-कनेक्टेड घटकों का चयन करने के लिए कैलिपर लंबाई का उपयोग कर सकता हूं। स्थिति के आधार पर उन्हें छंटनी, मुझे छवि में प्रत्येक लंबवत / क्षैतिज ग्रिड लाइनों के लिए 2x10 मास्क छवियां मिलती हैं:

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]];

इसके बाद मैं लंबवत / क्षैतिज ग्रिड लाइनों की प्रत्येक जोड़ी लेता हूं, उन्हें फैलाता हूं, पिक्सेल-बाय-पिक्सेल चौराहे की गणना करता हूं, और परिणाम के केंद्र की गणना करता हूं। ये अंक ग्रिड लाइन चौराहे हैं:

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}];

अंतिम चरण इन बिंदुओं के माध्यम से एक्स / वाई मैपिंग के लिए दो इंटरपोलेशन फ़ंक्शंस को परिभाषित करना है, और इन फ़ंक्शंस का उपयोग करके छवि को बदलना है:

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]

सभी ऑपरेशन मूल छवि प्रसंस्करण कार्य हैं, इसलिए यह ओपनसीवी में भी संभव होना चाहिए। स्पलीन-आधारित छवि परिवर्तन कठिन हो सकता है, लेकिन मुझे नहीं लगता कि आपको वास्तव में इसकी आवश्यकता है। शायद आप प्रत्येक व्यक्तिगत सेल पर उपयोग किए जाने वाले परिप्रेक्ष्य परिवर्तन का उपयोग करके पर्याप्त अच्छे परिणाम देंगे।


निकी के जवाब ने मेरी समस्या हल की, लेकिन उसका जवाब गणित में था। तो मैंने सोचा कि मुझे यहां अपना ओपनसीवी अनुकूलन देना चाहिए। लेकिन कार्यान्वयन के बाद मैं देख सकता था कि ओपनसीवी कोड निकी के गणित कोड से काफी बड़ा है। और साथ ही, मुझे ओपनसीवी में निकी द्वारा किए गए इंटरपोलेशन विधि नहीं मिल सका (हालांकि इसे एससीआई का उपयोग करके किया जा सकता है, मैं समय आने पर इसे बताउंगा।)

1. छवि प्रीप्रोसेसिंग (समापन ऑपरेशन)

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)

परिणाम :

2. सुडोकू स्क्वायर ढूँढना और मास्क छवि बनाना

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)

परिणाम :

3. लंबवत रेखाएं ढूँढना

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()

परिणाम :

4. क्षैतिज रेखाएं ढूँढना

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()

परिणाम :

बेशक, यह इतना अच्छा नहीं है।

5. ग्रिड अंक ढूँढना

res = cv2.bitwise_and(closex,closey)

परिणाम :

6. दोषों को सुधारना

यहां, निकी कुछ प्रकार का इंटरपोलेशन करता है, जिसके बारे में मुझे ज्यादा ज्ञान नहीं है। और मुझे इस ओपनसीवी के लिए कोई संबंधित फ़ंक्शन नहीं मिला। (हो सकता है कि यह वहां हो, मुझे नहीं पता)।

इस एसओएफ को देखें जो बताता है कि साइपी का उपयोग करके इसे कैसे किया जाए, जिसे मैं उपयोग नहीं करना चाहता: ओपनसीवी में छवि परिवर्तन

तो, यहां मैंने प्रत्येक उप-वर्ग के 4 कोनों और प्रत्येक के लिए लागू वार परिप्रेक्ष्य लिया।

इसके लिए, पहले हम Centroids पाते हैं।

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))

लेकिन परिणामस्वरूप सेंट्रॉइड को हल नहीं किया जाएगा। उनके ऑर्डर देखने के लिए नीचे दी गई छवि देखें:

इसलिए हम उन्हें बाएं से दाएं, ऊपर से नीचे तक सॉर्ट करते हैं।

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))

अब उनके आदेश के नीचे देखें:

अंत में हम परिवर्तन लागू करते हैं और 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()

परिणाम :

नतीजा लगभग निकी के समान है, लेकिन कोड की लंबाई बड़ी है। हो सकता है, वहां बेहतर तरीके उपलब्ध हैं, लेकिन तब तक, यह ठीक काम करता है।

सादर एआरके।


आप मनमाने ढंग से युद्ध करने के कुछ प्रकार के ग्रिड आधारित मॉडलिंग का उपयोग करने का प्रयास कर सकते हैं। और चूंकि सुडोकू पहले से ही एक ग्रिड है, जो बहुत कठिन नहीं होना चाहिए।

तो आप प्रत्येक 3x3 सबग्रेन की सीमाओं का पता लगाने की कोशिश कर सकते हैं और फिर प्रत्येक क्षेत्र को अलग-अलग वार कर सकते हैं। यदि पहचान सफल हो जाती है तो यह आपको बेहतर अनुमान लगाएगी।





sudoku