वर्ण परिमाणीकरण

An example image in 24-bit RGB color

The same image reduced to a palette of 16 colors specifically chosen to best represent the image; the selected palette is shown by the squares at the bottom of the image.

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

वर्ण परिमाणीकरण नाम का उपयोग मुख्य रूप से कंप्यूटर चित्रलेख अनुसंधान साहित्य में किया जाता है; अनुप्रयोगों में, अनुकूलित पैलेट पीढ़ी, इष्टतम पैलेट पीढ़ी, या घटती वर्ण गहराई जैसे शब्दों का उपयोग किया जाता है। इनमें से कुछ भ्रामक हैं, क्योंकि मानक एल्गोरिदम द्वारा उत्पन्न पैलेट आवश्यक रूप से सर्वोत्तम संभव नहीं हैं।

एल्गोरिदम

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

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

एक छोटा प्रतिबिम्ब जिसका नीला चैनल हटा दिया गया है। इसका अर्थ है कि इसके सभी पिक्सेल वर्ण वर्ण घन में द्वि-विमीय समतल में स्थित हैं।

फ़ोटोशॉप द्वारा निर्मित 16-वर्ण अनुकूलित पैलेट के साथ बाईं ओर प्रतिबिम्ब का वर्ण स्थान। प्रत्येक पैलेट प्रविष्टि के वोरोनोई क्षेत्र दिखाए गए हैं।

यदि पैलेट निश्चित है, जैसा कि प्रायः ऑपरेटिंग सिस्टम में उपयोग किए जाने वाले वास्तविक समय के वर्ण परिमाणीकरण सिस्टम में होता है, तो वर्ण परिमाणीकरण सामान्यतः सीधी-रेखा दूरी या निकटतम वर्ण एल्गोरिदम का उपयोग करके किया जाता है, जो मूल प्रतिबिम्ब में प्रत्येक वर्ण को लेता है और निकटतम पैलेट प्रविष्टि पाता है, जहां दूरी त्रि-विमीय समष्टि में दो संबंधित बिंदुओं के बीच की दूरी से निर्धारित होती है। दूसरे शब्दों में, यदि वर्ण $(r_{1},g_{1},b_{1})$ और $(r_{2},g_{2},b_{2})$ हैं तो हम यूक्लिडियन दूरी को कम करना चाहते हैं:

${\sqrt {(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}}}.$

यह प्रभावी रूप से वर्ण घन को वोरोनोई आरेख में विघटित करता है, जहां पैलेट प्रविष्टियां बिंदु होती हैं और सेल में एकल पैलेट प्रविष्टि में सभी वर्णों का प्रतिचित्रण होती है। वोरोनोई आरेखों की गणना करने और यह निर्धारित करने के लिए कि कोई दिया गया बिंदु किस क्षेत्र में आता है, कम्प्यूटेशनल ज्यामिति से कुशल एल्गोरिदम हैं; व्यवहार में, अनुक्रमित पैलेट इतने छोटे होते हैं कि ये सामान्यतः आवश्यकता से अधिक होते हैं।

स्थानिक वर्ण परिमाणीकरण का उपयोग करके वर्णीय प्रतिबिम्ब को 4 वर्णों में घटा दिया गया।

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

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

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

<गैलरी मोड = नोलाइन्स पेरो = 7 कैप्शन = वहाँ लवलेस है का पोर्ट्रेट - वफादार प्रतिनिधित्व और के-मीन्स रंग-मात्राकरण द्वारा संसाधित कई संस्करण। > File:Ada lovelace.png|मूल File:Ada lovelace 02k 31i.png| वर्ण की File:Ada lovelace 05k 24i.png| वर्ण की File:Ada lovelace 10k 31i.png|10 रंग File:Ada k15 i48.png|15 रंग File:Ada lovelace k100 i295.png|100 रंग </गैलरी>

उच्च गुणवत्ता वाला परन्तु धीमा न्यूक्वांट एल्गोरिदम स्व-संगठित मानचित्र को प्रशिक्षित करके प्रतिबिम्बों को 256 वर्णों तक कम कर देता है जो इनपुट प्रतिबिम्ब में वर्णों के वितरण से मेल खाने के लिए सीखने के माध्यम से स्व-व्यवस्थित होता है। प्रत्येक न्यूरॉन के आरजीबी-स्पेस में स्थिति लेने से उच्च गुणवत्ता वाला वर्ण मानचित्र मिलता है जिसमें आसन्न वर्ण समान होते हैं। यह ग्रेडिएंट वाली प्रतिबिम्बों के लिए विशेष रूप से लाभप्रद है।

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

इतिहास और अनुप्रयोग

पीसी के प्रारम्भिक दिनों में, वीडियो मेमोरी सीमाओं के कारण वीडियो एडेप्टर के लिए मात्र 2, 4, 16, या (अंततः) 256 वर्णों का समर्थन करना सामान्य बात थी; उन्होंने वीडियो मेमोरी को अधिक वर्णों के अतिरिक्त अधिक पिक्सेल (उच्च रिज़ॉल्यूशन) के लिए समर्पित करना पसंद किया। वर्ण परिमाणीकरण ने सीमित दृश्य गिरावट के साथ 16- और 256-वर्ण मोड में कई उच्च वर्णीय प्रतिबिम्बों को प्रदर्शित करना संभव बनाकर इस ट्रेडऑफ़ को उचित ठहराने में मदद की। 256 वर्णीय वीडियो मोड में उच्च वर्णीय प्रतिबिम्बों को देखते समय कई ऑपरेटिंग सिस्टम स्वचालित रूप से परिमाणीकरण और स्पंदन करते हैं, जो तब महत्वपूर्ण था जब 256 वर्ण मोड तक सीमित वीडियो डिवाइस प्रभावी थे। आधुनिक कंप्यूटर अब साथ लाखों वर्ण प्रदर्शित कर सकते हैं, जो कि मानव आंखों द्वारा पहचाने जा सकने वाले वर्णों से कहीं अधिक हैं, इस एप्लिकेशन को मुख्य रूप से मोबाइल उपकरणों और पुराने हार्डवेयर तक सीमित कर दिया गया है।

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

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

प्रारंभिक कंप्यूटरों पर उपलब्ध कुछ वर्णों के साथ, विभिन्न परिमाणीकरण एल्गोरिदम ने बहुत अलग दिखने वाली आउटपुट प्रतिचित्र तैयार कीं। परिणामस्वरूप, अधिक सजीव होने के लिए परिष्कृत एल्गोरिदम लिखने में बहुत समय व्यतीत हुआ।

प्रतिबिम्ब संपीड़न के लिए परिमाणीकरण

कई अनुक्रमित रंग#प्रतिबिम्ब फ़ाइल स्वरूप अनुक्रमित वर्ण का समर्थन करते हैं।

एक संपूर्ण-प्रतिबिम्ब पैलेट सामान्यतः संपूर्ण प्रतिबिम्ब के लिए 256 प्रतिनिधि वर्णों का चयन करता है, जहां प्रत्येक पिक्सेल पैलेट में किसी वर्ण को संदर्भित करता है, जैसा कि GIF और PNG फ़ाइल स्वरूपों में होता है।

एक ब्लॉक पैलेट सामान्यतः 4x4 पिक्सेल के प्रत्येक ब्लॉक के लिए 2 या 4 वर्णों का चयन करता है, जिसका उपयोग ब्लॉक ट्रंकेशन कोडिंग, वर्ण सेल कंप्रेशन, S2TC और एस3 टेक्सचर कंप्रेशन में किया जाता है।

संपादक समर्थन

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

• फ़ोटोशॉप का मोड→अनुक्रमित वर्ण फ़ंक्शन किसी विशेष प्रतिबिम्ब या प्रतिबिम्बों के अनुकूल पैलेट उत्पन्न करने के लिए निश्चित विंडोज सिस्टम और वेब पैलेट से लेकर मालिकाना स्थानीय और वैश्विक एल्गोरिदम तक कई परिमाणीकरण एल्गोरिदम प्रदान करता है।
• पेंट शॉप प्रो, अपने कलर्स→डिक्रीज़ वर्ण डेप्थ डायलॉग में, तीन मानक वर्ण परिमाणीकरण एल्गोरिदम प्रदान करता है: मीडियन कट, ऑक्ट्री, और निश्चित मानक वेब सुरक्षित पैलेट।
• जीआईएमपी 2.8 में, प्रतिबिम्ब को अनुक्रमित वर्णों में कनवर्ट करें विकल्प (प्रतिबिम्ब → मोड → अनुक्रमित ..) 2 से 256 तक वर्णों की संख्या में विकल्प के साथ इष्टतम पैलेट बनाने की अनुमति देता है, वेब-अनुकूलित पैलेट का उपयोग करने का विकल्प, काले और सफेद पैलेट (1 बिट) का उपयोग करना या कस्टम पैलेट का उपयोग करना। यह अप्रयुक्त वर्णों को पैलेट से हटाने की अनुमति देता है और यह विभिन्न प्रकार के स्पंदन विकल्प प्रदान करता है: कोई नहीं, फ्लोयड-स्टाइनबर्ग (सामान्य), फ्लोयड-स्टाइनबर्ग (कम वर्ण रक्तस्राव) और पोजिशन के साथ-साथ पारदर्शिता को सक्षम करने की क्षमता।

वर्ण परिमाणीकरण का उपयोग posterization प्रभाव बनाने के लिए भी किया जाता है, हालांकि पोस्टराइजेशन में ही वर्ण स्थान के भीतर उपयोग किए जाने वाले वर्णों की संख्या को कम करने का थोड़ा अलग लक्ष्य होता है, और सामान्यतः निश्चित पैलेट का उपयोग किया जाता है।

कुछ वेक्टर ग्राफ़िक्स संपादक वर्ण परिमाणीकरण का भी उपयोग करते हैं, विशेष रूप से रेखापुंज करने वाली वेक्टर तकनीकों के लिए जो किनारे का पता लगाने की मदद से बिटप्रतिचित्रित प्रतिबिम्बों की ट्रेसिंग बनाते हैं।

• इंकस्केप का पथ→ट्रेस बिटमैप: एकाधिक स्कैन: वर्ण फ़ंक्शन वर्ण निशान बनाने के लिए ऑक्ट्री परिमाणीकरण का उपयोग करता है।

यह भी देखें

• अनुक्रमित रंग
• पैलेट (कंप्यूटिंग)
• सॉफ़्टवेयर पैलेटों की सूची - सॉफ्टवेयर पैलेट्स की सूची#अनुकूली पैलेट्स अनुभाग।
• स्पंदन
• परिमाणीकरण (प्रतिबिम्ब प्रसंस्करण)
• प्रतिबिम्ब विभाजन

अग्रिम पठन

• Paul S. Heckbert. Color Image Quantization for Frame Buffer Display. ACM SIGGRAPH '82 Proceedings. First publication of the median cut algorithm.
• Dan Bloomberg. Color quantization using octrees. Leptonica.
• Oleg Verevka. Color Image Quantization in Windows Systems with Local K-means Algorithm. Proceedings of the Western Computer Graphics Symposium '95.
• J. Puzicha, M. Held, J. Ketterer, J. M. Buhmann, and D. Fellner. On Spatial Quantization of Color Images. (full text .ps.gz) Technical Report IAI-TR-98-1, University of Bonn. 1998.