मिलान पहेली टुकड़े

Question

मुझे क्या करना उपयोगी कुछ भी नहीं है और इस तरह पहेली के साथ खेल रहा था:

alt text http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg

और मैं सोच रहा था अगर यह एक कार्यक्रम है कि मुझे डाल करने में सहायता करता बनाने के लिए संभव हो जाएगा यह एक साथ

कल्पना कीजिए कि मेरे पास 4x3 टुकड़े की तरह एक छोटी पहेली है, लेकिन छोटे टैब और रिक्त स्थान गैर-वर्दी हैं - अलग-अलग टुकड़ों में अलग-अलग आकार के विभिन्न आकारों के अलग-अलग आकार होते हैं। मैं इन सभी टुकड़ों की तस्वीरें लेने के लिए क्या करना चाहता हूं, एक प्रोग्राम उन्हें विश्लेषण करने और कहीं भी उनके गुणों को स्टोर करने दें। फिर, जब मैं एक टुकड़ा उठाता हूं, तो मैं प्रोग्राम से पूछ सकता हूं कि मुझे कौन सा टुकड़ा 'पड़ोसियों' होना चाहिए - या अगर मुझे खाली जगह भरनी है, तो यह मुझे बताएगा कि वांछित पहेली टुकड़े कैसे हैं देखो।

दुर्भाग्य से मैं छवि प्रसंस्करण और पैटर्न मान्यता के साथ कुछ भी किया था कभी नहीं किया है, इसलिए मैं कुछ संकेत के लिए आप से पूछना करना चाहते हैं - कैसे मैं में एक पहेली टुकड़ा (मूल रूप से टैब और छेद के साथ एक वर्ग) पहचाना एक तस्वीर?

तो मुझे शायद इसे घुमाए जाने की आवश्यकता होगी, इसलिए यह सही स्थिति में है, कुछ अनुपात में स्केल करें और फिर प्रत्येक तरफ टैब/रिक्त मापें, और यदि मौजूद हो, तो प्रत्येक पक्ष की ढलान भी मापें।

मुझे पता है कि पहेली के 1000 टुकड़ों को स्कैन/फोटोग्राफ करने में बहुत समय लगेगा और इसका इस्तेमाल होगा, यह सिर्फ एक पालतू परियोजना होगी जहां मैं कुछ नया सीखूंगा।

Answer 1

डाटा अधिग्रहण

कमरे में कम से कम प्रकाश बदलाव के साथ,

1. अच्छी तरह से प्रकाशित कमरे का पता लगाएं (यह क्रोमा कुंजी, ब्लू स्क्रीन या पृष्ठभूमि रंग पद्धति के रूप में जाना जाता है)।
2. एक रंग (रंग) खोजें जो पूरी पहेली/चित्र में शायद ही कभी उपयोग किया जाता है।
3. एक रंगीन कागज़ प्राप्त करें जिसमें बिल्कुल वही रंग हो।
4. रंगीन कागज़ पर जितने पहेली टुकड़े होंगे उतना ही फिट होगा।
   • आप पहेली को बैचों में वर्गीकृत कर सकते हैं और बाद में कंप्यूटर संकेत के रूप में इसका उपयोग कर सकते हैं।
   • सुनिश्चित करें कि टुकड़े एक दूसरे को ओवरलैप या स्पर्श नहीं करते हैं।
   • अभी तक अभिविन्यास के बारे में चिंता न करें।
5. तस्वीर लें और कंप्यूटर पर डाउनलोड करें।
   • रंग अंशांकन की आवश्यकता हो सकती है क्योंकि क्रोमा कुंजी पृष्ठभूमि डिजिटल कैमरे के अंतर्निहित रंग संतुलन को परेशान कर सकती है।

अधिग्रहण डाटा प्रोसेसिंग

1. कुछ कंप्यूटर दृष्टि सॉफ्टवेयर जाओ
   • OpenCV, MATLAB, सी ++, जावा, पायथन इमेजिंग पुस्तकालय, आदि
2. क्रोमो कुंजी रंग पर जुड़े घटक को करें छवि।
   • छेद जुड़ा घटक के है, जो पहेली टुकड़े कर रहे हैं की रूपरेखा के लिए पूछें।
3. पता लगाई गई सूची में त्रुटियों को ठीक करें।
4. indexing vocabulary (सीएफ। ईरा बैक्सटर की पोस्ट) चुनें और टुकड़ों को मापें।
   • यदि टुकड़े आयताकार हैं, तो पहले कोनों को ढूंढें।
   • यदि टुकड़े चुपचाप चतुर्भुज हैं, तो पक्ष की लंबाई (कोने के लिए मापा कोने) भी एक मूल्यवान हस्ताक्षर है।
   • SO या Google या here पर "आकार संदर्भ" के लिए खोजें।
   • अंत में, टुकड़े का रंग हिस्टोग्राम प्राप्त करें, ताकि आप बाद में रंग से टुकड़े पूछ सकें।
5. उन्हें खोजने योग्य बनाने के लिए, उन्हें डेटाबेस में रखें, ताकि आप इंडेक्सिंग शब्दावली के किसी भी संयोजन के साथ टुकड़े पूछ सकें।

Answer 2

स्वयं समस्या के लिए एक कदम पीछे। एक पहेली बनाने की समस्या आसान (पी) या हार्ड (एनपी) हो सकती है, इस पर निर्भर करता है कि टुकड़े केवल एक पड़ोसी या कई फिट बैठते हैं या नहीं। यदि प्रत्येक किनारे के लिए केवल एक फिट है, तो आप बस अपने पड़ोसी के प्रत्येक टुकड़े/पक्ष के लिए पाते हैं और आप कर चुके हैं (ओ (# टुकड़े * # पक्ष))। यदि कुछ टुकड़े अलग-अलग पड़ोसियों में कई फिट बैठते हैं, तो पूरी पहेली को पूरा करने के लिए, आपको बैकट्रैकिंग की आवश्यकता हो सकती है (क्योंकि आपने गलत विकल्प बनाया है और आप फंस गए हैं)।

हालांकि, हल करने की पहली समस्या यह है कि टुकड़ों का प्रतिनिधित्व कैसे करें। यदि आप मनमाने ढंग से आकार का प्रतिनिधित्व करना चाहते हैं, तो आप शायद पारदर्शिता या मास्क का उपयोग कर सकते हैं यह दर्शाते हैं कि टाइल के कौन से क्षेत्र वास्तव में टुकड़े का हिस्सा हैं। यदि आप स्क्वायर आकृतियों का उपयोग करते हैं तो समस्या आसान हो सकती है। बाद के मामले में, आप वर्ग के प्रत्येक किनारे पर पिक्सेल की आखिरी पंक्ति पर विचार कर सकते हैं और इसे अन्य सभी टुकड़ों में पाए जाने वाले पिक्सेल की सबसे समान पंक्ति के साथ मेल कर सकते हैं।

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