আসুন একটি ভিডিও কোডেক লিখি - পার্ট 3: স্টিল ইমেজ

এই সিরিজের আগের অংশগুলিতে, আমরা ডিসক্রিট কোসাইন ট্রান্সফর্ম সম্পর্কে শিখেছি, এর গাণিতিক সংজ্ঞা থেকে বাস্তব উদাহরণে এর বাস্তবায়ন পর্যন্ত। উপরন্তু, আমরা দেখেছি কিভাবে ডিসিটি ফ্রিকোয়েন্সি ডোমেনে ডেটা উপস্থাপন করার ক্ষমতা ক্ষতিকারক ডেটা কম্প্রেশন সক্ষম করতে পারে।

এখন, আমরা পরবর্তী পদক্ষেপ নিচ্ছি। আমরা পরিশেষে এই বিমূর্ত অ্যারেগুলিকে আমরা আলোচনা করেছি এবং তারা যে প্রকৃত চিত্রগুলি উপস্থাপন করতে পারে তার সাথে সংযোগ করার লাইনটি আঁকব।

এই নিবন্ধের শেষে, আমরা প্রকৃত JPEG ইমেজ কম্প্রেশন প্রক্রিয়ার প্রায় 80% পুনঃআবিষ্কার করব।

জরায়ু

পূর্ববর্তী নিবন্ধে, আমরা 2D-DCT প্রবর্তন করেছি। এখন, আসুন সেই সূত্রটির একটি সামান্য সামঞ্জস্যপূর্ণ সংস্করণ দেখি:

u এবং v ভেরিয়েবল ডিসিটি-এনকোডেড 2D অ্যারেতে মানের অনুভূমিক এবং উল্লম্ব অফসেট উপস্থাপন করে। ফাংশন α(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 DCT গণনা করি:

 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 }

নিয়মিত এবং ট্রান্সপোজড ডিসিটি ম্যাট্রিক্স অদলবদল করে ইনভার্স ডিসিটি পাওয়া যেতে পারে:

 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% সংকোচন অনুপাত যা কেবলমাত্র ম্যাট্রিক্সকে গুণ করে এবং নির্ধারকভাবে ডেটা বাতিল করে অর্জিত হয়!

যখন আমরা DCT সহগগুলির 86% বাতিল করি, তখন এটি ঘটে:

কোয়ান্টাইজেশন

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

যেমন আমরা আগে দৃশ্যত নিশ্চিত করেছি, বড় মানগুলি উপরের-বাম কোণের কাছাকাছি ঘটতে পারে। যাইহোক, প্রতিটি ব্লক এই প্যাটার্ন অনুসরণ করে না। এখানে আমাদের ইমেজ থেকে আরেকটি ব্লক আছে:

এই ব্লকটি DCT মানগুলির সাধারণ বন্টন মেনে চলে না। আমরা যদি অন্ধভাবে নীচের-ডান মানগুলি বাতিল করতে থাকি, তাহলে ছবির কিছু অংশ আরও কম্প্রেশন আর্টিফ্যাক্ট প্রদর্শন করতে পারে। এটি এড়াতে, আমাদের সিদ্ধান্ত নিতে হবে কোন ব্লকে অন্যদের চেয়ে বেশি ডেটা প্রয়োজন।

একটি সহজ কিন্তু মার্জিত সমাধান আমরা আগে আবিষ্কৃত ক্লাস্টারিং সম্পত্তিকে পুঁজি করে। একে "পরিমাণকরণ" বলা হয়। আমরা আমাদের ডিসিটি মানগুলিকে বিভিন্ন সহগ দ্বারা ভাগ করি। আমরা সুবিধার জন্য প্রতিটি DCT সহগের জন্য একটি মান ধারণ করে এমন একটি টেবিল ব্যবহার করব:

 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

আপনি লক্ষ্য করবেন যে দ্বিতীয় ব্লকে আরও অ-শূন্য মান রয়েছে। এইভাবে, কোয়ান্টাইজেশন ধাপ আমাদের আরও দরকারী ডেটা সঞ্চয় করতে এবং বাকিগুলি বাতিল করতে দেয়।

উপসংহার এবং পরবর্তী কি?

মৌলিক গণিত থেকে, আমরা বাস্তব চিত্রগুলিকে এনকোডিং এবং ডিকোড করার জন্য আমাদের পথ তৈরি করেছি৷ আমরা চাক্ষুষভাবে দেখেছি যে কীভাবে ডিসিটি নির্বিচারে ডেটাকে ফ্রিকোয়েন্সির সেটে রূপান্তর করে এবং কীভাবে কিছু ফ্রিকোয়েন্সি অন্যদের চেয়ে বেশি গুরুত্বপূর্ণ।

আমরা মৌলিক সংকোচনের সাথে আরামদায়ক হওয়ার পরে, আমরা কোয়ান্টাইজেশনের ধারণাটি চালু করেছি, যা স্টোরেজ প্রয়োজনীয়তাকে আরও কমিয়ে দেয়।

পরবর্তী অংশে, আমরা আরজিবি চিত্রগুলিতে চলে যাব এবং ফলস্বরূপ ডেটা আরও সংকুচিত করার উপায়গুলি অন্বেষণ করব।

এই নিবন্ধটির কোডটি https://github.com/petertechstories/image-dct এ পাওয়া যাবে