ডিসক্রিট কোসাইন ট্রান্সফর্ম (DCT) ও কমপ্রেশন

The discrete cosine transform (DCT) & compression

৯ মিনিট পড়া মধ্যম-উচ্চ · Intermediate-Advanced Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

DCT (Discrete Cosine Transform) হলো DFT-এর একটি আত্মীয় ট্রান্সফর্ম, যা শুধু কোসাইন বেসিস ফাংশন ব্যবহার করে (কোনো কমপ্লেক্স/সাইন অংশ নেই)।
DCT-এর মূল সুবিধা হলো এনার্জি কম্প্যাকশন — মসৃণ, ধীরে-পরিবর্তনশীল সিগন্যালের জন্য প্রায় সব এনার্জি প্রথম কয়েকটি কোয়েফিসিয়েন্টে কেন্দ্রীভূত হয়।
নিচের ডেমোতে একটি মসৃণ (Gaussian bump) সিগন্যালের DCT বনাম DFT গণনা করে দেখানো হয়েছে — প্রথম ৩টি DCT কোয়েফিসিয়েন্ট মোট এনার্জির ৯৯.৭৩% ধরে রাখে, যেখানে DFT-এর প্রথম ৩টি ম্যাগনিটিউড ধরে রাখে মাত্র ৮২.৭৫%।
এই এনার্জি-কম্প্যাকশন বৈশিষ্ট্যই JPEG (ছবি), MP3/AAC (অডিও)-এর মতো কমপ্রেশন স্ট্যান্ডার্ডের মূল ভিত্তি — কম কোয়েফিসিয়েন্ট সংরক্ষণ করেও প্রায় পুরো সিগন্যাল পুনর্গঠন করা যায়।

এই পাঠে যা শিখবেন

DCT-II-এর সংজ্ঞা ও সরাসরি ক্লোজড-ফর্ম সামেশন সূত্র
Python-এ হাতে-লেখা DCT বাস্তবায়ন করা, DFT-এর সাথে তুলনা করে
এনার্জি কম্প্যাকশন ধারণা ও কেন এটি মসৃণ সিগন্যালের জন্য বিশেষভাবে কার্যকর
DCT কীভাবে JPEG/MP3-এর মতো বাস্তব কমপ্রেশন স্ট্যান্ডার্ডে ব্যবহৃত হয়

১ · DCT-II-এর সংজ্ঞা

DCT (Discrete Cosine Transform)Discrete Cosine Transformশুধু কোসাইন বেসিস ফাংশন ব্যবহারকারী একটি রিয়েল-ভ্যালুড ফ্রিকোয়েন্সি-ডোমেইন ট্রান্সফর্ম, যা মসৃণ সিগন্যালের এনার্জি কম কয়েকটি কোয়েফিসিয়েন্টে কেন্দ্রীভূত করে। -এর সবচেয়ে প্রচলিত রূপ, DCT-II, সংজ্ঞায়িত হয়:

$$X[k] = \sum_{n=0}^{N-1} x[n] \cos\!\left(\frac{\pi}{N}\left(n+\tfrac{1}{2}\right)k\right), \quad k=0,1,\dots,N-1$$

M২২-এর DFT সূত্রের সাথে তুলনা করলে — DFT-তে $e^{-j2\pi kn/N}$ (কমপ্লেক্স, সাইন ও কোসাইন উভয় অংশ থাকে), DCT-তে শুধু $\cos(\cdot)$ (বিশুদ্ধ রিয়েল সংখ্যা)। এই সাধারণ পরিবর্তনটাই DCT-কে একটি বাস্তব-মূল্যবান ($x[n] \in \mathbb{R}$-এর জন্য $X[k] \in \mathbb{R}$) ট্রান্সফর্মে পরিণত করে — সংরক্ষণ ও প্রসেসিং-এর জন্য সুবিধাজনক, কারণ কমপ্লেক্স সংখ্যার আলাদা রিয়েল/ইমাজিনারি অংশ ব্যবস্থাপনা করতে হয় না।

সরাসরি সামেশন সূত্র
DFT-এর মতোই DCT-ও একটি $O(N^2)$ সরাসরি সামেশন হিসেবে গণনাযোগ্য — এই পাঠে সেটাই বাস্তবায়ন করা হয়েছে, কোনো লাইব্রেরি ছাড়া।

এনার্জি কম্প্যাকশন
মসৃণ সিগন্যালের জন্য DCT কোয়েফিসিয়েন্টগুলো $k$ বাড়ার সাথে সাথে দ্রুত ছোট হয়ে যায় — নিচের ডেমোতে সরাসরি গণনা করে দেখানো হয়েছে।

বাস্তব প্রয়োগ
JPEG ছবিকে ৮×৮ ব্লকে ভাগ করে প্রতিটিতে ২D DCT প্রয়োগ করে, তারপর ছোট (উচ্চ-ফ্রিকোয়েন্সি) কোয়েফিসিয়েন্টগুলো বাদ দিয়ে/কম নির্ভুলতায় সংরক্ষণ করে কমপ্রেস করে।

২ · একটি সত্যিকারের ডেমো — DCT বনাম DFT এনার্জি কম্প্যাকশন

নিচের কোডে $N=16$ দৈর্ঘ্যের একটি মসৃণ টেস্ট সিগন্যাল তৈরি করা হয়েছে — একটি Gaussian bump ($x[n] = e^{-(n-7.5)^2/(2\cdot3^2)}$, কেন্দ্রে সর্বোচ্চ, প্রান্তে ধীরে শূন্যের কাছে নামে, কোনো আকস্মিক লাফ নেই)। এই একই সিগন্যালের উপর M৫-এর হাতে-লেখা DFT এবং সরাসরি সূত্র দিয়ে বাস্তবায়িত DCT-II — উভয়ই প্রয়োগ করে প্রতিটির এনার্জি (কোয়েফিসিয়েন্ট স্কয়ারের যোগফল) কতটা প্রথম কয়েকটি পদে কেন্দ্রীভূত তা তুলনা করা হয়েছে।

Python

import math, cmath

def dft(x):
    N = len(x)
    X = []
    for k in range(N):
        s = 0 + 0j
        for n in range(N):
            s += x[n] * cmath.exp(-2j * math.pi * k * n / N)
        X.append(s)
    return X

def dct2(x):
    N = len(x)
    X = []
    for k in range(N):
        s = 0.0
        for n in range(N):
            s += x[n] * math.cos(math.pi / N * (n + 0.5) * k)
        X.append(s)
    return X

N = 16
# মসৃণ টেস্ট সিগন্যাল: একটি Gaussian bump, কেন্দ্র n=7.5, sigma=3
x = [math.exp(-((n - 7.5) ** 2) / (2 * 3.0 ** 2)) for n in range(N)]

X_dct = dct2(x)
X_dft = dft(x)

dct_energy = [c * c for c in X_dct]
dft_energy = [abs(c) ** 2 for c in X_dft]

total_dct = sum(dct_energy)
total_dft = sum(dft_energy)

print(f"{'k':>3} | {'DCT coef':>10} | {'DFT |X[k]|':>10}")
for k in range(N):
    print(f"{k:>3} | {X_dct[k]:>10.4f} | {abs(X_dft[k]):>10.4f}")

print()
for K in [2, 3, 6]:
    dct_pct = 100 * sum(dct_energy[:K]) / total_dct
    dft_pct = 100 * sum(dft_energy[:K]) / total_dft
    print(f"প্রথম K={K} কোয়েফিসিয়েন্ট: DCT ধরে রাখে {dct_pct:.2f}% এনার্জি, DFT(mag) ধরে রাখে {dft_pct:.2f}% এনার্জি")

রান করলে দেখা যায় DCT কোয়েফিসিয়েন্ট $k=0$ ($7.4644$) আর $k=2$ ($-3.8059$) ছাড়া বাকি সব প্রায় শূন্যের কাছাকাছি (বিজোড় $k$-গুলো একদম শূন্য, কারণ সিগন্যালটি প্রতিসম) — ফলে প্রথম ৩টি কোয়েফিসিয়েন্ট (K=৩) মোট এনার্জির ৯৯.৭৩% ধরে রাখে। একই সিগন্যালের DFT ম্যাগনিটিউডে $k=0$ ($7.4644$) আর $k=1$ ($3.8059$) প্রধান, কিন্তু সিমেট্রির কারণে $k=15$-তেও ($3.8059$) সমান শক্তি "উল্টো দিকে" থাকে (M২৩-এর কনজুগেট সিমেট্রি — বাস্তব সিগন্যালের জন্য $X[N-k]=\overline{X[k]}$) — তাই প্রথম ৩টি (শুধু $k=0,1,2$) কোয়েফিসিয়েন্ট ধরে রাখে মাত্র ৮২.৭৫%, বাকি এনার্জির একটি বড় অংশ উচ্চ-ইনডেক্স বিনে ($k=14,15$) "লুকিয়ে" থাকে।

মূল কথা · Key takeaway

DCT-এর কোসাইন-শুধু বেসিস মসৃণ সিগন্যালের জন্য DFT-এর চেয়ে অনেক বেশি এনার্জি-কম্প্যাক্ট প্রতিনিধিত্ব দেয় — উপরের ডেমোতে ৯৯.৭৩% বনাম ৮২.৭৫% এই পার্থক্য স্পষ্ট করে। যেহেতু ছবি ও অডিও সিগন্যালের বেশিরভাগ অংশই স্থানীয়ভাবে মসৃণ (পাশাপাশি পিক্সেল/স্যাম্পল কাছাকাছি মানের), DCT-ভিত্তিক কমপ্রেশন (JPEG, MP3, AAC) অল্প কয়েকটি বড় কোয়েফিসিয়েন্ট সংরক্ষণ করে আর বাকিগুলো বাতিল/কোয়ান্টাইজ করে ফাইল-সাইজ অনেক কমাতে পারে, গুণগত মান খুব একটা না হারিয়ে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ উপরের ডেমোতে সব বিজোড় $k$-এর DCT কোয়েফিসিয়েন্ট প্রায় শূন্য কেন?

টেস্ট সিগন্যাল $x[n] = e^{-(n-7.5)^2/(2\cdot 3^2)}$ ঠিক $n=7.5$-এর চারপাশে প্রতিসম (symmetric) — অর্থাৎ $x[7-i] \approx x[8+i]$ যেকোনো $i$-এর জন্য। কোসাইন ফাংশন নিজেও একটি জোড় (even) ফাংশন, তাই বিজোড় কোসাইন বেসিসগুলো (যেগুলোর মধ্যে একটি প্রতিসাম্য-বিরোধী গঠন আছে) এই প্রতিসম সিগন্যালের সাথে গুণ করলে ধনাত্মক ও ঋণাত্মক অবদান একে অপরকে বাতিল করে দেয় — ঠিক M২৩-এর জোড়/বিজোড় সিমেট্রি বিশ্লেষণের মতোই একটি যুক্তি।

প্র ০২ যদি টেস্ট সিগন্যালটি মসৃণ না হয়ে সম্পূর্ণ র‍্যান্ডম (যেমন random.gauss নয়েজ) হতো, তাহলে DCT-এর এনার্জি-কম্প্যাকশন কেমন হতো বলে আপনার ধারণা?

অনেক খারাপ হতো — প্রায় সমান-সমান ছড়িয়ে যেত। এনার্জি-কম্প্যাকশন নির্ভর করে সিগন্যালের পাশাপাশি স্যাম্পলগুলোর মধ্যে পারস্পরিক সম্পর্ক (correlation)-এর উপর — মসৃণ সিগন্যালে পাশাপাশি মানগুলো কাছাকাছি (উচ্চ correlation), যা কম কয়েকটি নিম্ন-ফ্রিকোয়েন্সি কোসাইনেই ভালোভাবে প্রকাশযোগ্য। বিশুদ্ধ র‍্যান্ডম নয়েজে পাশাপাশি স্যাম্পলের মধ্যে কোনো সম্পর্ক থাকে না, তাই এনার্জি সব কোয়েফিসিয়েন্টে প্রায় সমানভাবে ছড়িয়ে যায় — এটাই কমপ্রেশন অ্যালগরিদম নয়েজি ডেটাতে খারাপ কাজ করার মূল কারণ।

প্র ০৩ DFT আর DCT উভয়েরই $k=0$ কোয়েফিসিয়েন্ট $7.4644$ — একদম সমান। এটি কি কাকতালীয়?

না। উভয় সূত্রেই $k=0$-তে বসালে সাইন/কোসাইন পদ যথাক্রমে $e^0=1$ এবং $\cos(0)=1$ হয়ে যায় (DCT-তে $\cos(\frac{\pi}{N}(n+0.5)\cdot 0) = \cos(0) = 1$ সব $n$-এর জন্য) — তাই উভয় ক্ষেত্রেই $k=0$ কোয়েফিসিয়েন্ট আসলে শুধু সিগন্যালের সব মানের যোগফল, $\sum_n x[n]$। যেহেতু একই $x$ ব্যবহার হয়েছে, দুটোই একই মান দেয়।

অনুশীলন

চিন্তা করুন: উপরের কোডে K-এর মান ২ থেকে ৩-এ বাড়ালে DCT-এর এনার্জি-শতাংশ ৭৯.১৫%(K=২) থেকে হঠাৎ ৯৯.৭৩%(K=৩)-এ লাফ দেয়। এত বড় লাফের কারণ কী হতে পারে বলে আপনার ধারণা (উপরের প্র ০১-এর উত্তর মনে করুন)?

কারণ $k=1$ (বিজোড়) কোয়েফিসিয়েন্ট প্রায় শূন্য, তাই K=২ থেকে K=৩-এ যাওয়ার আসল "লাফ"টা ঘটে $k=2$ যোগ হওয়ার সময় (যার মান $-3.8059$, দ্বিতীয়-সবচেয়ে-বড় এনার্জি-অবদানকারী), $k=1$ যোগ হওয়ার সময় নয়। এটাই দেখায় কেন K বাড়ানোর প্রভাব সবসময় সরল-রৈখিক নয় — নির্দিষ্ট সিগন্যালের গঠনের উপর নির্ভর করে।
পরীক্ষা করুন: কোড সেলে সিগন্যাল x-কে একটি সরল লিনিয়ার র‍্যাম্প (x = [n/15 for n in range(16)])-এ বদলে Run চাপুন — এটিও একটি মসৃণ সিগন্যাল, কি DCT এনার্জি-কম্প্যাকশন আগের Gaussian bump-এর মতোই শক্তিশালী থাকে?

রান করলে দেখা যাবে একটি রৈখিক র‍্যাম্পও ভালো এনার্জি-কম্প্যাকশন দেখায় (যদিও প্রতিসম না হওয়ায় বিজোড় কোয়েফিসিয়েন্টগুলো এবার শূন্য হবে না) — কারণ এটিও একটি মসৃণ, ধীরে-পরিবর্তনশীল সিগন্যাল। তবে সঠিক শতাংশ ভিন্ন হবে, কারণ সিগন্যালের গঠন ভিন্ন — এটি নিশ্চিত করে এনার্জি-কম্প্যাকশন সিগন্যালের "মসৃণতা"-র উপর নির্ভরশীল একটি সাধারণ বৈশিষ্ট্য, শুধু একটি নির্দিষ্ট উদাহরণের কাকতালীয় ফলাফল নয়।

এই পাঠে যা শিখবেন

১ · DCT-II-এর সংজ্ঞা

২ · একটি সত্যিকারের ডেমো — DCT বনাম DFT এনার্জি কম্প্যাকশন

ভাবনার প্রশ্ন

অনুশীলন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ