हफ ट्रांसफॉर्म एक फीचर निष्कर्षण तकनीक है जिसका उपयोग छवि विश्लेषण, कंप्यूटर विज़न, पैटर्न पहचान और डिजिटल छवि प्रसंस्करण में किया जाता है। इसका उद्देश्य मतदान प्रक्रिया द्वारा आकृतियों के एक निश्चित वर्ग के भीतर वस्तुओं के अपूर्ण उदाहरणों को खोजना है। यह मतदान प्रक्रिया एक पैरामीटर स्थान में की जाती है, जहाँ से वस्तु उम्मीदवारों को एक संचायक स्थान में स्थानीय मैक्सिमा के रूप में प्राप्त किया जाता है, जिसे एल्गोरिदम द्वारा स्पष्ट रूप से निर्मित किया जाता है। गणितीय रूप से, यह समतल में रेडॉन ट्रांसफॉर्म है, जो कम से कम 1917 से ज्ञात है, लेकिन हफ ट्रांसफॉर्म विशेष रूप से छवि विश्लेषण में इसके उपयोग को संदर्भित करता है।
शास्त्रीय हफ ट्रांसफॉर्म छवि में रेखाओं की पहचान करने से संबंधित था, लेकिन तब से इसे मनमानी आकृतियों, विशेष रूप से वृत्तों या दीर्घवृत्तों की स्थितियों की पहचान करने के लिए विस्तारित किया गया है। आज सार्वभौमिक रूप से उपयोग किया जाने वाला ट्रांसफॉर्म 1972 में रिचर्ड डुडा और पीटर हार्ट द्वारा आविष्कार किया गया था, जिन्होंने पॉल हफ के 1962 के संबंधित पेटेंट के बाद इसे "सामान्यीकृत हफ ट्रांसफॉर्म" कहा। इसे डाना एच. बैलार्ड द्वारा 1981 के एक जर्नल लेख "जनरलाइज़िंग द हफ ट्रांसफॉर्म टू डिटेक्ट अर्बिट्रेरी शेप्स" के माध्यम से कंप्यूटर विज़न समुदाय में लोकप्रिय बनाया गया।
इतिहास
हफ ट्रांसफॉर्म का आविष्कार शुरू में पॉल हफ द्वारा 1959 में बबल चैंबर तस्वीरों के मशीन विश्लेषण के लिए किया गया था। इसे 1962 में अमेरिकी पेटेंट 3,069,654 के रूप में पेटेंट कराया गया था और इसे "मेथड एंड मीन्स फॉर रिकग्नाइज़िंग कॉम्प्लेक्स पैटर्न्स" नाम से अमेरिकी परमाणु ऊर्जा आयोग को सौंपा गया था। इस पेटेंट में सीधी रेखाओं के लिए ढलान-अवरोधन पैरामीट्रिजेशन का उपयोग किया गया था, जो अजीब तरह से एक असीमित ट्रांसफॉर्म स्थान की ओर ले गया, क्योंकि ढलान अनंत तक जा सकती है।
आज सार्वभौमिक रूप से उपयोग किया जाने वाला रो-थीटा पैरामीट्रिजेशन पहली बार 1972 के रिचर्ड डुडा और पीटर हार्ट के पेपर "यूज़ ऑफ़ द हफ ट्रांसफॉर्मेशन टू डिटेक्ट लाइन्स एंड कर्व्स इन पिक्चर्स" में वर्णित किया गया था, जो कम्युनिकेशंस ऑफ़ द एसीएम में प्रकाशित हुआ था। यह पैरामीट्रिजेशन कम से कम 1930 के दशक से रेडॉन ट्रांसफॉर्म के लिए पहले से ही मानक था। फ्रैंक ओ'गोर्मन और एम.बी. क्लोज़ ने 1976 में आईईईई ट्रांजेक्शन्स ऑन कंप्यूटर्स में "फाइंडिंग पिक्चर एजेज़ थ्रू कॉलिनियरिटी ऑफ़ फीचर पॉइंट्स" शीर्षक से एक भिन्नता प्रकाशित की। आधुनिक रूप का आविष्कार कैसे हुआ, इसकी कहानी पीटर हार्ट के 2009 के लेख "हाउ द हफ ट्रांसफॉर्म वाज़ इन्वेंटेड" में आईईईई सिग्नल प्रोसेसिंग पत्रिका में विस्तृत है।
सिद्धांत
डिजिटल छवियों के स्वचालित विश्लेषण में, सरल आकृतियों, जैसे सीधी रेखाओं, वृत्तों या दीर्घवृत्तों का पता लगाने की एक उपसमस्या अक्सर उत्पन्न होती है। एक किनारा डिटेक्टर का उपयोग वांछित वक्र पर छवि बिंदु प्राप्त करने के लिए पूर्व-प्रसंस्करण चरण के रूप में किया जा सकता है। हालाँकि, छवि डेटा या किनारा डिटेक्टर में अपूर्णताओं के कारण, आदर्श आकार और शोर वाले किनारे बिंदुओं के बीच लापता बिंदु या स्थानिक विचलन हो सकते हैं। हफ ट्रांसफॉर्म पैरामीटरयुक्त छवि वस्तुओं के एक सेट पर एक स्पष्ट मतदान प्रक्रिया करके इसे संबोधित करता है, जिससे किनारे बिंदुओं को वस्तु उम्मीदवारों में समूहित करना संभव हो जाता है।
रेखाओं का पता लगाना
सबसे सरल मामला सीधी रेखाओं का पता लगाना है। सामान्य तौर पर, एक रेखा y = mx + b को पैरामीटर स्थान में एक बिंदु (b, m) के रूप में दर्शाया जा सकता है, लेकिन ऊर्ध्वाधर रेखाएँ असीमित ढलान मानों के कारण एक समस्या पैदा करती हैं। डुडा और हार्ट ने हेस सामान्य रूप का उपयोग करने का प्रस्ताव रखा: r = x cos(theta) + y sin(theta), जहाँ r मूल बिंदु से रेखा पर निकटतम बिंदु की दूरी है, और theta x-अक्ष और मूल बिंदु से उस निकटतम बिंदु को जोड़ने वाली रेखा के बीच का कोण है। रेखा पर प्रत्येक वेक्टर मूल बिंदु से लंबाई r के रेखा खंड के लंबवत है। प्रतिच्छेदन बिंदु P0 = (r cos(theta), r sin(theta)) पर है। रेखा पर किसी भी बिंदु P के लिए, वेक्टर P - P0 को P0 के लंबवत होना चाहिए, जो (P - P0) डॉट P0 = 0 को लागू करता है, जो r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta)) को सरल करता है।
एल्गोरिदम और मतदान प्रक्रिया
व्यवहार में, हफ ट्रांसफॉर्म पैरामीटर स्थान को एक संचायक सरणी में विभाजित करता है। छवि में प्रत्येक किनारे बिंदु के लिए, एल्गोरिदम सभी संभावित पैरामीटर मानों (जैसे, रेखाओं के लिए r और theta) की गणना करता है जो उस बिंदु से गुजरने वाली आकृति के अनुरूप हो सकते हैं, और संबंधित संचायक कोशिकाओं को बढ़ाता है। सभी बिंदुओं को संसाधित करने के बाद, संचायक में स्थानीय मैक्सिमा संभावित आकार उम्मीदवारों को इंगित करते हैं। यह मतदान प्रक्रिया शोर और लापता डेटा के प्रति मजबूत है, क्योंकि इसके लिए किसी आकृति पर सभी बिंदुओं को पूरी तरह से संरेखित होने की आवश्यकता नहीं होती है।
विस्तार और अनुप्रयोग
सामान्यीकृत हफ ट्रांसफॉर्म, जिसे 1981 में डाना बैलार्ड द्वारा पेश किया गया था, एक संदर्भ बिंदु और किनारे अभिविन्यास की एक तालिका का उपयोग करके मनमानी आकृतियों के लिए तकनीक का विस्तार करता है। यह रेखाओं, वृत्तों और दीर्घवृत्तों से परे जटिल आकृतियों का पता लगाने की अनुमति देता है। ट्रांसफॉर्म को स्वायत्त ड्राइविंग, चिकित्सा इमेजिंग और औद्योगिक निरीक्षण जैसे क्षेत्रों में व्यापक रूप से लागू किया गया है। Computer vision प्रणालियों में, इसे अक्सर डिजिटल-छवि-प्रसंस्करण पाइपलाइनों में वस्तुओं की पहचान करने के लिए किनारा-पहचान एल्गोरिदम के साथ जोड़ा जाता है। radon transform में इसकी गणितीय नींव इसे Machine learning और Artificial intelligence अनुप्रयोगों में उपयोग की जाने वाली व्यापक छवि-विश्लेषण तकनीकों से जोड़ती है।
सीमाएँ और विविधताएँ
शास्त्रीय हफ ट्रांसफॉर्म की एक सीमा इसकी कम्प्यूटेशनल लागत है, विशेष रूप से उच्च-आयामी पैरामीटर स्थानों के लिए। संभाव्य हफ ट्रांसफॉर्म और हफ सर्कल ट्रांसफॉर्म जैसी विविधताएँ दक्षता में सुधार के लिए विकसित की गई हैं। संभाव्य संस्करण गणना को कम करने के लिए किनारे बिंदुओं के एक उपसमुच्चय का नमूना लेता है, जबकि सर्कल ट्रांसफॉर्म त्रि-आयामी पैरामीटर स्थान (केंद्र x, केंद्र y, त्रिज्या) का उपयोग करता है। ये विविधताएँ आमतौर पर opencv जैसी लाइब्रेरीज़ में लागू की जाती हैं और वास्तविक समय प्रणालियों में उपयोग की जाती हैं, जिनमें autonomous-vehicles और Robotics शामिल हैं।
यह भी देखें
- radon-transform
- edge-detection
- Computer vision
- image-processing