आइए एक वीडियो कोडेक लिखें - भाग 3: स्थिर छवियां

इस श्रृंखला के पिछले भागों में, हमने असतत कोसाइन रूपांतरण के बारे में सीखा है, इसकी गणितीय परिभाषा से वास्तविक उदाहरणों में इसके कार्यान्वयन तक। इसके अतिरिक्त, हमने देखा है कि फ़्रीक्वेंसी डोमेन में डेटा का प्रतिनिधित्व करने की DCT की क्षमता हानिपूर्ण डेटा संपीड़न को कैसे सक्षम कर सकती है।

अब, हम अगला कदम उठा रहे हैं। हम अंत में उन संख्याओं के सार सरणियों को जोड़ने वाली रेखा खींचेंगे जिनकी हम चर्चा कर रहे हैं और वास्तविक छवियों का वे प्रतिनिधित्व कर सकते हैं।

इस लेख के अंत तक, हम वास्तविक जेपीईजी छवि संपीड़न प्रक्रिया का लगभग 80% पुनः खोज लेंगे।

गणित का सवाल

पिछले लेख में, हमने 2डी-डीसीटी पेश किया था। अब, आइए उस सूत्र के थोड़े समायोजित संस्करण को देखें:

वेरिएबल्स u और v डीसीटी-एन्कोडेड 2डी सरणी में मूल्य के क्षैतिज और लंबवत ऑफ़सेट का प्रतिनिधित्व करते हैं। फ़ंक्शन α(x) 1/sqrt(2) के बराबर है यदि x == 0 और 1 अन्यथा। अंत में, x और y स्रोत छवि में पिक्सेल की स्थिति का प्रतिनिधित्व करते हैं।

यह स्पष्ट प्रतीत नहीं हो सकता है, लेकिन समान गणना को निम्न रूप में मैट्रिक्स गुणन के रूप में दर्शाया जा सकता है:

इस सूत्रीकरण में, DCT DCT मैट्रिक्स है, T मैट्रिक्स ट्रांसपोज़िशन को दर्शाता है, और IMG स्रोत छवि है।

ध्यान रखें कि इस ऑपरेशन की जटिलता स्रोत छवि के आकार के समानुपाती होती है। किसी भी आकार की छवियों को प्रबंधित करने और काम को कम करने के लिए, हम अपनी गणनाओं को 8-बाई-8-पिक्सेल छवि ब्लॉक तक सीमित कर देंगे।

जबकि वास्तविक छवियों में एक उच्च रिज़ॉल्यूशन होता है, हम उन्हें कई स्वतंत्र 8x8 ब्लॉकों से बने होने के बारे में सोच सकते हैं।

यहां बताया गया है कि हम डीसीटी मैट्रिक्स की गणना कैसे करते हैं जो वांछित प्रभाव पैदा करता है:

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

dctMatrix का मान है:

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

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

यह कोड 8x8 मैट्रिक्स गुणा करता है:

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

हम निम्नानुसार 8x8 डीसीटी की गणना करते हैं:

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

व्युत्क्रम DCT को केवल नियमित और ट्रांसपोज़्ड DCT मैट्रिसेस की अदला-बदली करके प्राप्त किया जा सकता है:

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

बड़ी तस्वीर

अब, हम अपने ज्ञान को वास्तविक छवियों पर लागू करने के लिए तैयार हैं। आइए इसके साथ काम करें:

कल्पना कीजिए कि हमारे पास कोड है जो इस छवि को संख्याओं की एक सरणी के रूप में लोड करता है जहां प्रत्येक संबंधित स्थान पर पिक्सेल की चमक का प्रतिनिधित्व करता है:

 func loadImage(width: Int, height: Int) -> [Float] { ... }

छवि को 256x256 पिक्सेल मानते हुए, निम्न मान शीर्ष-बाएँ कोने के अनुरूप होंगे:

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

गणितीय सुविधा के लिए, पिक्सेल चमक को 0.0 से 255.0 तक की संख्या के रूप में व्यक्त करने के बजाय, हम 128.0 घटाते हैं। दूसरे शब्दों में, हम मान को 128.0 के बजाय 0.0 के आसपास केंद्रित करते हैं।

फिर, हम छवि के प्रत्येक 8x8 ब्लॉक पर dct फ़ंक्शन लागू करते हैं:

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

परिणाम यह छवि है:

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

यह 8x8 ब्लॉक दिखाता है कि फ्रीक्वेंसी-डोमेन प्रतिनिधित्व क्या है। गैर-शून्य मान ब्लॉक के ऊपरी-बाएँ कोने में क्लस्टर होते हैं। जैसे-जैसे हम नीचे-दाएं कोने की ओर बढ़ते हैं, वैसे-वैसे बड़े मूल्य की संभावना काफी कम हो जाती है।

यह इंगित करता है कि शीर्ष-बाएँ मान छवि के लिए अधिक महत्व रखते हैं।

हम इसे "संपीड़न" फ़ंक्शन लिखकर प्रदर्शित कर सकते हैं जो कुछ निचले-दाएं मानों को 0.0 पर सेट करके हटा देता है:

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

हमारे प्रसंस्करण पाश को समायोजित करने के बाद:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

हमें यह छवि मिलती है:

क्या हुआ है इस पर विचार करने के लिए कुछ समय निकालें। हमने प्रत्येक छवि ब्लॉक के लिए 64 में से 39 मानों को हटा दिया है और अभी भी एक ऐसी छवि बनाई है जो मूल के समान है। यह एक 60% संपीड़न अनुपात है जो केवल मेट्रिसेस को गुणा करके और निश्चित रूप से डेटा को हटाकर प्राप्त किया जाता है!

जब हम 86% DCT गुणांकों को छोड़ देते हैं, तो ऐसा होता है:

परिमाणीकरण

DCT गुणांकों को फ्लोटिंग-पॉइंट नंबरों के रूप में संग्रहीत करना अविश्वसनीय रूप से बेकार होगा, जिसके लिए आमतौर पर 4 बाइट्स स्टोरेज की आवश्यकता होती है। इसके बजाय, हमें उन्हें निकटतम पूर्णांक पर गोल करना चाहिए। 8x8 ब्लॉक के लिए, प्रत्येक मान को 2-बाइट पूर्णांक संख्या द्वारा दर्शाया जा सकता है।

आइए उस ब्लॉक पर दोबारा गौर करें जिसकी हमने पहले जांच की थी। इसका (गोलाकार) संख्यात्मक प्रतिनिधित्व है:

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

जैसा कि हमने पहले देखा था, बड़े मान ऊपरी-बाएँ कोने के करीब होने की अधिक संभावना है। हालांकि, हर ब्लॉक इस पैटर्न का पालन नहीं करता है। यहाँ हमारी छवि से एक और ब्लॉक है:

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

एक सरल लेकिन सुरुचिपूर्ण समाधान हमारे द्वारा पहले खोजी गई क्लस्टरिंग संपत्ति का लाभ उठाता है। इसे "परिमाणीकरण" कहा जाता है। हम अपने डीसीटी मूल्यों को विभिन्न गुणांकों से विभाजित करते हैं। सुविधा के लिए हम प्रत्येक डीसीटी गुणांक के लिए एक मान वाली तालिका का उपयोग करेंगे:

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

अधिक महत्वपूर्ण पद निचले विभाजक के अनुरूप हैं, और इसके विपरीत। हम तालिका से गुणांकों द्वारा परिमाणित डेटा को गुणा करके विचलन चरण का प्रदर्शन करते हैं।

ये फ़ंक्शन क्रमशः क्वांटिज़ेशन और डिक्वांटिज़ेशन चरणों का प्रदर्शन करते हैं:

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

आइए हमारे कोड में परिमाणीकरण और विकेंद्रीकरण को शामिल करें:

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

मात्रा निर्धारित होने पर पहला ब्लॉक कैसा दिखता है:

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

और यह दूसरा ब्लॉक है:

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

आप देखेंगे कि दूसरे ब्लॉक में अधिक गैर-शून्य मान हैं। इस प्रकार, परिमाणीकरण कदम हमें अधिक उपयोगी डेटा संग्रहीत करने और बाकी को त्यागने की अनुमति देता है।

निष्कर्ष और आगे क्या है?

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

बुनियादी संपीड़न के साथ सहज होने के बाद, हमने क्वांटिज़ेशन की अवधारणा पेश की, जो भंडारण आवश्यकताओं को और कम कर देता है।

अगले भाग में, हम RGB छवियों की ओर बढ़ेंगे और परिणामी डेटा को और भी कम करने के तरीके तलाशेंगे।

इस लेख का कोड https://github.com/petertechstories/image-dct पर पाया जा सकता है