एक श्रेडर के बाद दस्तावेजों की बहाली के लिए प्रतियोगिता के परिणाम

^{समस्या संख्या 5, लगभग 6200 टुकड़े, प्रत्येक टुकड़े का आकार लगभग 150 x 60 px है।}

DARPA एजेंसी ने श्रेडर के बाद दस्तावेजों की बहाली के लिए प्रतियोगिता के परिणामों की घोषणा की। प्रतियोगिता में लगभग 9,000 टीमों ने हिस्सा लिया।

प्रत्येक पहेली में एक नए वाणिज्यिक श्रेडर पर कटा हुआ हस्तलिखित पाठ के टुकड़े शामिल थे और 400 डीपीआई के एक संकल्प के साथ स्कैन किया गया था। सबसे कठिन कार्य संख्या 5 में, अज्ञात संख्या के पृष्ठों से लगभग 6200 टुकड़े थे - केवल दो टीमों ने इस कार्य का सामना किया।

विजेता टीम थी ऑल योर श्रेड्स आर बिलॉन्ग टू यूएस - वह सभी कार्यों को पूरा करके अधिकतम संभव 50 अंक बनाने में सक्षम थी। निकटतम प्रतियोगियों ने 30 और 26 अंक बनाए।

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

प्रोग्रामर मार्क न्यूलिन ( वसाबी टीम), जिन्होंने तीसरा स्थान हासिल किया, ने अपने दस्तावेज़ पुनर्प्राप्ति पद्धति को प्रकाशित किया। सभी मॉड्यूल C # / .NET 4.0 / MSSQL में विकसित किए गए हैं। पहले चरण में, विधानसभा के लिए तैयारी की जाती है: छवि को अलग-अलग टुकड़ों में विभाजित करना, पृष्ठभूमि और संरेखण से सफाई करना।



पृष्ठभूमि के भरे जाने के बाद सीमाओं का चयन किया जाता है। टुकड़ों की संरेखण अधिकतम पिक्सेल की ओर से स्वचालित होती है, और विवादास्पद मामलों में, मैनुअल संरेखण मदद करता है (मार्क के अनुसार, इस तरह के लगभग 1% थे)। टुकड़े के ऊपरी और निचले सीमाओं को भी आसानी से श्रेडर के विशेषता निशान द्वारा पहचाना जाता है, ताकि, यदि आवश्यक हो, तो टुकड़ा 180 ° घूमता है। पहेली का प्रत्येक टुकड़ा एक फ़ाइल में सहेजा जाता है। टुकड़े के "साफ" संस्करण, लंबे पक्षों से काट दिया जाता है, अलग से बचाया जाता है - यह पेन ट्रेस के कनेक्शन बिंदुओं को खोजने के लिए आवश्यक है।

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

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

इस जानकारी के आधार पर, दस्तावेज़ को आलेखीय संपादक में मैन्युअल रूप से इकट्ठा किया जाता है। मार्क ने जीआईएमपी और पेंट.नेट का उपयोग किया, लेकिन हजारों टुकड़ों के साथ चौथे और पांचवें कार्यों की जटिल पहेली के लिए, उन्हें अलग-अलग मापदंडों के अनुसार डेटाबेस से टुकड़ों के देखने को फ़िल्टर करने के लिए एक अलग इंटरफ़ेस बनाना पड़ा: निकटता संभावना, कलम का रंग, एक कॉफी दाग ​​की उपस्थिति, आदि। ।



स्क्रीन पर सबसे उपयुक्त टुकड़े प्रदर्शित करने के लिए एक इंटरफ़ेस भी जोड़ा गया था, जिसने विधानसभा की सटीकता और गति को बढ़ा दिया।



पाए गए सभी मैचों के साथ सामान्य दस्तावेज को धीरे-धीरे पूरक किया गया था, और संभावनाओं को फिर से जोड़ा गया था।



मार्क न्यूलिन का कहना है कि उन्होंने पिछले कुछ हफ्तों में इस परियोजना पर अपना सारा खाली समय बिताया। वह प्रतियोगिता के पांच कार्यों में से चार को हल करने में कामयाब रहा, 6200 टुकड़ों की सबसे कठिन पांचवीं पहेली को छोड़कर, जिसके लिए 24 अंक दिए गए थे। जाहिर है, मार्क के पास बस इतना समय नहीं था, क्योंकि उन्होंने अकेले काम किया था। अब वह प्रयोगों को जारी रखने और अपनी तकनीक में सुधार करने के लिए कुछ वाणिज्यिक श्रेडर खरीदने जा रहा है। शायद भविष्य में, मार्क Unshredder.com के साथ प्रतिस्पर्धा करने के लिए एक किताब लिखेगा या अपनी खुद की कंपनी खोलेगा । हालांकि, वह अकेले नहीं होंगे। DARPA प्रतियोगिता के बाद, इस विषय में रुचि रखने वाले लोगों का एक बड़ा समुदाय शायद बन गया है।

विजेता टीम ऑल योर श्रेड्स आर बिलॉन्ग टू यूएस भी निकट भविष्य में अपने समाधान एल्गोरिदम को प्रकट करने का वादा करती है । मार्क के ब्लॉग पोस्ट पर टिप्पणियों में , उन्होंने कहा कि उन्होंने एक ही तरीके का बहुत उपयोग किया। एक कवर नोट में, उन्होंने कहा कि सभी समस्याओं को हल करने में लगभग 600 मानव-घंटे लगे।

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

पृष्ठ 1 , अंतिम पंक्ति में मोर्स कोड


पेज 2 उल्टा हो गया


पेज 3


श्रेडर DIN 32757 के लिए सुरक्षा मानक प्रत्येक सुरक्षा स्तर के लिए पीसने के बाद न्यूनतम टुकड़े का आकार निर्दिष्ट करता है:

स्तर 1 = 12 मिमी स्ट्रिप्स या 11 x 40 मिमी टुकड़े
स्तर 2 = 6 मिमी स्ट्रिप्स या 8 x 40 मिमी टुकड़े
स्तर 3 = 2 मिमी स्ट्रिप्स या 4 x 30 मिमी टुकड़े (गोपनीय अंकन)
स्तर 4 = 2 x 15 मिमी के टुकड़े (व्यावसायिक रूप से संवेदनशील लेबलिंग)
स्तर 5 = 0.8 x 12 मिमी टुकड़े (शीर्ष गुप्त या वर्गीकृत अंकन)
स्तर 6 = 0.8 x 4 मिमी टुकड़े (शीर्ष गुप्त या वर्गीकृत)

प्रतियोगिता के पांचवें कार्य में, टुकड़े का आकार लगभग 148 x 59 पिक्सेल है, अर्थात 9.4 x 3.7 मिमी, जो सुरक्षा मानक DIN 32757 के अनुसार लगभग 4 स्तर तक मेल खाता है। विकिपीडिया के अनुसार, श्रेडर के लिए CIA मानक मानक टुकड़े के आकार के लिए प्रदान करते हैं। रूसी संघ में 1 एक्स 5 मिमी से अधिक नहीं - 1 एक्स 1 मिमी।