پایان نامه دوره ی کارشناسی رشته ی
ICT(مهندسی فناوری اطلاعات وارتباطات)
تهیه وتنظیم:
موضوع:
کدینگ ویدئو
1391
فصل اول: روشهای فشرده سازی
1-چند رسانه ای چیست؟ ——————————————————————-
– تعریف چند رسانه ای………………………………………………………………………..
– عناصر تشکیل دهنده سیستم های چند رسانه ای……………………………………………..
2- کاربردهای چند رسانه ای —————————————————————
3- عکس ———————————————————————————-
4-ویدئو————————————————————————————
5-فشرده سازی —————————————————————————-
-چرا فشرده سازی………………………………………………………………………………
-تعریف ………………………………………………………………………………………..
-فشرده سازی از نظر تئوری اطلاعات………………………………………………………….
6-دو استراژی اصلی ———————————————————————–
– lossless …………………………………………………………………………………….
– lossy…………………………………………………………………………………………
7-فشرده سازی تصویر ———————————————————————
8-redundancy درتصویر و ویدئو ———————————————————
– فشرده سازی lossless……………………………………………………………………….
-فشرده سازی lossy…………………………………………………………………………..
9- نیازهای فشرده سازی – بسته به کاربرد ————————————————–
10- تئوری اطلاعات ————————————————————————
11- تئوری شنون —————————————————————————
12- کدبا طول متغیرvariable lengh code————————————————-
13- کد هافمن —————————————————————————-
فصل دوم: رنگ درتصویر و ویدئو
1-علم رنگها——————————————————————————-
2-بینایی انسان—————————————————————————–
3-حساسیت طیفی چشم———————————————————————
4-تصویر سازی (image formation)—————————————————-
5-سیستم دوربینها—————————————————————————
6-تصحیح گاما در صفحه نمایش————————————————————-
7-مدل های رنگ درتصویر—————————————————————–
-مدلRGB……………………………………………………………………………………..
-مدل رنگ تفاضلی: CMY…………………………………………………………………….
-تبدیل RGBبهCMY……………………………………………………………………………
-بهبود درسیستم CMY………………………………………………………………………….
8-مدل های رنگ درویدئو——————————————————————-
-مدل رنگ YUV………………………………………………………………………………..
-مدل رنگ YIQ………………………………………………………………………………….
-مدل رنگ YCbCr……………………………………………………………………………….
فصل سوم: مفاهیم اولیه در ویدئو
1-انواع سیگنال های ویدئویی——————————————————————
-ویدئو مولفه ای(component video)………………………………………………………….
-ویدئوی مرکب (Composite Video)………………………………………………………….
-S-video………………………………………………………………………………..
2-ویدئو آنالوگ————————————————————————–
3-ویدئو NTSC————————————————————————–
4-ویدئویPAL—————————————————————————
5-ویدئوی SECAM———————————————————————-
6-ویدئوی دیجیتال————————————————————————
-نمونه برداری رنگ (Chroma Subsampling)………………………………………….
-انتخاب اجزای رنگ………………………………………………………………………
7-استانداردهای CCIRبرای ویدئوهای دیجیتال———————————————
8-HDTV (تلویزیون با آشکارسازی بالا)————————————————–
فصل چهارم: دیجیتال سازی صدا،Quantization،انتفال صدا
1-صدا———————————————————————————–
-ویژگی های یک صوت…………………………………………………………………….
2-چگونه اصوات را می شنویم؟———————————————————–
-دامنه ی صداهای رایج برحسب دسی بل……………………………………………………..
3-ذخیره وبازنوازی صوت—————————————————————–
4-تبدیل صوت به دیجیتال——————————————————————-
-پارامترهای مهم دردیجیتال کردن……………………………………………………………
5-تئوری نایکوییست———————————————————————–
-انتخاب نرخ نمونه برداری برای صدا………………………………………………………..
6-کوانتیزه کردن(گسسته سازی درجهت دامنه)———————————————–
7-کوانتایز———————————————————————————-
8-فیلتر کردن صوت ((Audio Filtering—————————————————
9-انتقال صوت——————————————————————————
10-بلوک دباگرام کدینگ PCM———————————————————-
11-فایل های WAV———————————————————————
12-کدینگ تفاضلی———————————————————————–
13-بلاک دیاگرام Lossless Predictive Coding—————————————-
14-کدینگ DPCM———————————————————————-
-بلوک دیاگرام ……………………………………………………………………………………. DPCM
-مثالی ازکدینگ DPCM…………………………………………………………………….
15-کدینگ Delta Modulation——————————————————–
-مثال کدینگ Delta Modulation………………………………………………………..
فصل پنجم: کد کردن تبدیلی
1-مقدمه———————————————————————————
2-کدکردن تبدیلیtransform coding—————————————————
3-تبدیل کسینوسی گسسته(DCT)———————————————————-
4-تبدیل بلاک یا کل تصویر————————————————————–
5-DCT چه عملی انجام میدهد؟————————————————————
-مثال :DCT……………………………………………………………………………….
-DCTدو بعدی…………………………………………………………………………….
فصل ششم: فشرده سازی تصویرJPEG
1-jpeg در یک نگاه———————————————————————-
2-فشرده سازی jpeg———————————————————————-
-بلوک دیاگرام jpeg………………………………………………………………………….
-کیفیت………………………………………………………………………………………..
3-کد کردن آنتروپی————————————————————————
4-کد کردن انتروپی باقیمانده های DC——————————————————-
5-کد کردن ضرریب AC—————————————————————–
6-مروری بر jpeg———————————————————————-
فصل هفتم: فشرده سازی ویدئو
1-مقدمه ای بر فشرده سازی ویدئویی——————————————————–
2-ساختار سلسه مراتبی ویدئو—————————————————————
3-ساختار یک فربمQCIF——————————————————————-
4-استانداردهای فشرده سازی ویدئو———————————————————
5-فشرده سازی ویدئویی توسط انطباق حرکتی———————————————–
6-Motion Estimation && Motion Compensation———————————
7-اصطلاحات انطباق حرکتی————————————————————–
8-معیارتطبیق——————————————————————————
9-روشFull-Search———————————————————————–
10-برنامه جستجوی ترتیبی—————————————————————–
12-جستجوی لگاریتمی دو بعدی————————————————————-
13-جستجوی سلسله مراتبیHierarchical Search——————————————
14-مقایسه روشهای Motion Estimation—————————————————
-مقایسه سرعت روشها…………………………………………………………………………..
15-کد کردن یک فریم————————————————————————–
16-فریم های نوعP & B———————————————————————-
– دیاگرام یک کد کننده ویدئو………………………………………………………………………..
17-کد کردن فریم نوع I ———————————————————————–
18- کد کردن فریم های P و B—————————————————————
19-استانداردH.261————————————————————————–
– فرمت های ویدئویی پشتیبانی شده توسطH.261…………………………………………………
– فریمها و ترتیب آنها در H.261…………………………………………………………………
– کوانتیزاسیون در H.261……………………………………………………………………..
– بلاک دیاگرام کد کننده در H.261……………………………………………………………..
– بلاک دیاگرام دیکد کننده در H.261……………………………………………………………
20- استاندارد H.263————————————————————————
21- ستاندارد Mpeg————————————————————————
فصل اول
روشهای فشرده سازی
مقدمه
چندرسانه ای چیست؟ اصطلاح چندرسانه ای به ترکیب رسانه های منفرد نظیر فیلم، ویدئو، موسیقی، کلام، عکس، پایگاه های اطلاعاتی، و جز آن اطلاق می شود که از طریق فن آوری رایانه به صورت محصولی واحد بر محملی رقومی ذخیره شده باشد.در واقع چند رسانه ای پردازش یا نمایش اطلاعات دو یا چند رسانه می باشد. شیوه های انتقال اطلاعات به دیگران می تواند به شکل اعداد ومتن،نمودار،صدا،تصویر وغیره باشد.عناصر تشکیل دهنده سیستم های چند رسانه ای شامل اعداد ومتن ،گرافیک(اشکال ترسیم شده توسط انسان یا کامپیوتر)،انیمیشن(با نمایش متوالی تصاویر گرافیکی ایجاد می شو)،عکس،صدا و ویدئو در واقع می توان گفت یک سیستم چند رسانه ای ترکیبی از عناصر فوق رادارد.
کاربردهای چند رسانه ای
سیستم های چند رسانه ای کاربرد های فراوانی دارند،که از این کاربد ها می توان موارد زیر را بر شمرد:
• کنفرانس راه دور ویدئویی
• ارایهٔ مقالات مشترک و توزیع شده برای سطوح بالای آموزش عالی
• پزشکی از راه دور
• ایجاد محیط های عملیاتی و مشارکتی کار
• جستجو در پایگاه داده های بسیار وسیع فیلم ها و تصاویر برای موضوعات بصری مورد نظر.
• واقعیت تقویت شده(Augmented reality): جایگذاری تصاویر و اجزا ویدویی به نظر واقعی، توسط گرافیک کامپیوتری در نما و صحنه ها
• تولید جلوه های قابل جستجو درون ویدئوهای جدید و افزودن این امکان به تمامی محصولالات تولید شده با این روش
• قابلیت ویرایش برای اجزای چندرسانه ای
• تولید برنامه های کاربردی " "Inverse-Hollywood که قابلیت تولید دوباره فرآیند ها از طریق ویدئو های از قبل ساخته شده را دارند.
عکس(Image)
یک تصویر بهتر از صداها تمثیل می باشد.به عنوان مثال ازعکس زیر دهها برداشت را میتوان داشت،یک گربه،گربه ی آبکشیده باموهای ژولیده با یک حوله دور گردن و…
شکل 1-1 نمایانگر یک عکس می باشد:
شکل1-1
یک عکس دیجیتال مجموعه ای از نقاط(Pixel) است.هرنقطه دارای رنگ می باشد. انواع pixel شامل: باینری (1 bit) : فقط دو رنگ سیاه و سفید،سطح خاکستری Grayscale (8bit) :256 رنگ خاکستری ،رنگی (24 bit) : Red Green Blueعکس دارای مشخصاتی چون طول،عرض،تعداد بیت رنگ برای هرنقطه عکس می باشد.
برای ذخیره سازی یک عکس 1024×768 به صورت 2 رنگ:
1024×768 *1 = 768 Kb = 0.75 Mb = 0.09MB
سطح خاکستری(8bit):
1024×768 *8 = 6144 Kb = 6 Mb =0.75MB
رنگی(24bit):
1024×768 *24 = 18432Kb = 18 Mb = 2.25MB
شکل1-2
چند سوال:
بر روی یک flash card ، 64 مگا بایتی چند تصویر رنگی می توان ذخیره کرد؟
یک تصویر 1024×768 رنگی (24 bit) دارای حجم 2.25MB می باشد.
64MB/ 2.25MB =28
28 یک تصویر !
ارسال یک تصویر با خط 64 Kbps چقدر طول می کشد؟
2.25*1024*8 Kb / 64Kbps= 18432Kbit / 64Kbps =288 s
288 s = 4.8 m
5 دقیقه !
ولی در دنیای واقعی اینگونه نیست. چرا؟
ویدئو
یک ویدئو تشکیل شده از چندین تصویر متوالی که در هر ثانیه(25یا 30) تصویر (فریم)نمایش داده می شود.برای ذخیره سازی یک ثانیه ویدئو ( 352*248*24*30=59.94=7.49 MB) بر روی یک CDچقدر فیلم می تواند ذخیره کرد؟ 650 MB/7.49 = 86.8) ) تقریبا 78 ثانیه!!! ولی روی یک CD تقریبا 74 دقیقه فیلم ذخیره می شود.
فشرده سازی
برای ذخیره سازی فیلم وتصویر نیاز به فشرده سازی می باشد.فشرده سازی تصاویروفیلم، کاربردی از فشرده سازی اطلاعات بر روی تصاویر دیجیتال است به عبارتی هدف از این کار کاهش افزونگی (redundancy)محتویات عکس می باشد برای توانایی ذخیره کردن یا انتقال اطلاعات به فرم بهینه.
شکل1-3 مثالهایی را از روشها و کاربرد های فشرده سازی نشان داده شده است که فشرده شده آن را با فشرده نشده مقایسه کرده است.
میزان فشرده سازی
فشرده
فشرده نشده
کاربرد
16
4 kb/sec
64 kb/sec
صدا – صحبت
12 -2
128 – 768 Kb/sec
1.5 Mb/sec
صدا- موسیقی
480 – 40
64-768 kb/sec
30 Mb/sec
ویدئو کنفرانس
40
1.5 Mb/sec
60.83 Mb/sec
VCD
69
20 Mb/sec
1.33 Gb/sec
HDTV
شکل 1-4
فشرده سازی Compression
هدف از این کار حذف اطلاعات زاید می باشد.درواقع همان اطلاعات را با تعداد بیت کمتر ارسل می کنیم برای نمونه فشرده سازی فایل های(WinZip،WinRar).
یک سیستم فشرده سازی شامل:
1- کد کننده(Encoder):اطلاعات زاید را حذف می کند.
2- دیکد کننده(Decoder):از روی فایل فشرده شده اطلاعات اولیه را بازسازی می کند.
فشرده سازی ازنظر تئوری اطلاعات:
تعریف سیگنال:هر کمیت متغیر نسبت به زمان سیگنال می باشد. سیگنال ها اغلب توابع سطری از زمان هستند (سهمی شکل)، ولی ممکن است به صورت توابع ستونی نیز یافت شوند و نیز ممکن است توابعی از هر متغیر مستقل مربوطه دیگری باشند. این مفهوم بسیار گسترده است و تعریف دقیق آن بسیار دشوار. مفاهیم مربوط به رشته های زیر مجموعه، مشترک می باشد برای مثال در تئوری اطلاعات یک سیگنال پیغام کد دار شده ای است که این همان ترتیب حالت ها در یک کانال ارتباطی است که پیغام را دربر می گیرد.
تئوری اطلاعات:هرسیگانل شامل دو قسمت است.1- Entropy 2- Redundancy
Entropy: میزان بی نظمی در یک سیستم دارای انرژی یا داده ها، است. هر چقدر که یک سیستم از نظم کمتری برخوردار باشد، آنتروپی بیشتری دارد.در واقع قسمت غیر قابل پیش بینی سیگنال می باشد،که به صورت تصادفی وغیر منظم عمل می کند.
Redundancy: سیستمی که قسمت قابل پیش بینی سیگنال را شامل می شود به صورت منظم می باشد وقسمت زاید اطلاعات را شامل می شود.
در فشرده سازی اطلاعات زاید سیگنال حذف می شود. یعنی کد کننده Entropy و Redundancy از یکدیگر جدا کند کد کننده Redundancy را به نحوی از سیگنال حذف شود که دیکد کننده بتواند آن را باز سازی کند. در حالت ایده آل، فقط قسمت Entropy باید نگهداری (انتقال) یابد.
شکل 1-5 نمونه ای ازEntropy و Redundancy نشان داده شده است.
شکل1-5
دو استراتژی اصلی شامل:
Lossless : سیگنال دقیقا قابل بازسازی است.(مشابه Zip,Rar)
Lossy : دقیقا قابل بازسازی نیست، ولی بسیار شبیه است.
فشرده سازی تصویر
می توان گقت پیکسلهای کنارهم در تصویرمشابه هستند و تصاویر پشت سر هم دیگر در ویدئو مشابه می باشند.می توان نتیجه گرفت در تصویر و ویدئو اطلاعات قابل پیش بینی (زاید) وجود دارد.با حذف اطلاعات زاید فشرده سازی انجام می شود.در اشکال 1-6 و 1-7 میزان تغییرات شکل در هرفریم نشان داده شده است که نقطه مشخص شده بیشترین تغییر را اعمال کرده است.
شکل1-6
شکل1-7
Redundancy در تصویر و ویدئو
در تصویر spatial Redundancy (پیکسل های مشابه) در ویدئو spatial Redundancy و Temporal Redundancy (فریم های مشابه) وجود دارد. کد کننده های ویدئو به همراه Entropy مقداری از Redundancy را نیزذخیره می کنند. هر قدر میزان کد کردن Redundancy کمتر باشد، کد کننده پیچیده تر، کندتر وبهتر است.
فشرده سازی Lossless: سیگنال (اطلاعات) باز سازی شده دقیقا برابر سیگنال اولیه است.
معیارکارآیی:
1. میزان فشرده سازی : به میزان Entropy سیگنال محدود است.
2. پیچیدگی کدکننده : محاسبات لازم برای فشرده سازی سیگنال
3. تاخیر: زمان لازم برای فشرده سازی. به طورکلی هر چه میزان فشرده سازی بیشتر باشد، پیچیدگی وتاخیر افزایش می یابد.(و بر عکس)
فشرده سازی Lossy: سیگنال اولیه دقیقا قابل بازسازی نیست، ولی سیگنال بازسازی شده بسیار شبیه آن است. مقداری از Entropy که اهمیت کمتری دارد، حذف می شود. کیفیت کیفی : یک بینده دو سیگنال را مقایسه کند. کیفیت کمی: مشخص کردن کیفیت با یک عدد.( مثلا PSNR)
معیارکارآیی:
1. میزان فشرده سازی : به Entropy محدود نیست. 2. پیچیدگی 3. تاخیر 4.کیفیت
شکل1-8 معیار های کارایی و نحوخ عملکرد رو با استفاده از یک کدینگ یا فشرده سازی یک ویدئو نشان داده است می توان گفت بستگس این موارد بیشتر خواهد بود تا ما یک کانال فشرده سازی خوب و مفید را در یک معیار اصلی داشته باشیم.
شکل1-8
این جدول معیار های کارایی را که از چهار بلوک مشخص که برای یک سیستم lossy تعیین شده است که مزان بالا و پایین و کم و زیاد ان را مشخص میکند.
کیفیت
تاخیر
پیچیدگی
میزان فشرده سازی
بالا
زیاد
زیاد
زیاد
پایین
کم
کم
زیاد
بالا
کم
کم
کم
—
—
زیاد
کم
شکل 1-9
نیازهای فشرده سازی – بسته به کاربرد
تشکیل شده از مواردی هم چون: ارسال بلادرنگ تعاملی (ویدئو کنفرانس)، بازیابی بلادرنگ (video on demand، رادیوی اینترنتی )، ذخیره سازی (ویدئو خانگی: VCD,DVD)
که این نیازها موارد زیر را در برمی گیرند:
1. تاخیر کم2. نرخ بیت ثابت 3.کیفیت بالا 4.مقاومت در برابر خطا 5.قابلیت FF و نمایش از یک زمان دلخواه
جدول شکل 1-10 این نیاز ها را بسته به ملکرد و اهمیت بالا و پایین آنها را مشخص میکند.
قابلیت FF
کیفیت بالا
تاخیرکم
مقاومت در برابر خطا
نرخ بیت ثابت
کاربرد
—
کم اهمیت
با اهمیت
با اهمیت
با اهمیت
ارسال بلادرنگ تعاملی
نیاز است
با اهمیت
کم اهمیت
با اهمیت
با اهمیت
بازیابی بلادرنگ
نیاز است
با اهمیت
بی اهمیت
بی اهمیت
بی اهمیت
ذخیره سازی
شکل 1-10
جزییات فشرده سازی Lossless:
یک سیگنال متشکل از سمبلهای a, b ,c ,d داریم ، سیگنال شامل 1000 سمبل است، فراوانی هر سمبل به صورت:
Symbol
Number
Code
a
900
00
b
50
01
c
25
10
d
25
11
Coding: 2 bits per symbol
total bits = 2×1000 = 2000
جزییات فشرده سازی lossy:
اختصاص کد با طول متفاوت به سمبل های مختلف، سمبل با فراوانی بیشتر کد کوتاه تر می گیرد.
Symbol
Number
Code
Bits
a
900
0
900
b
50
10
100
c
25
110
75
d
25
111
75
Total bits = 900 + 100 + 75 + 75 = 1150
Average bits/symbol = 1150/1000 = 1.15 < 2
Compression = source bits/code bits = 2/1.15 =1.74
مثال : فشرده سازی
Symbol
Number
Code
Bits
a
900
0
900
b
50
10
100
c
25
110
75
d
25
111
75
(فشرده سازی)Encoding: Source = abaaaaca Code = 01000001100
(بازسازی) Decoding: Code 0011100100 Decode = aadaaba
تئوری اطلاعات
درس تئوری اطلاعات و کدینگ در کلی ترین بیان ممکن، سیر اطلاعات (و نه سیگنال) را در یک سیستم مخابراتی گسسته مورد تجزیه و تحلیل قرار می دهد. یک سیگنال مجموعه ای از سمبل های متوالی است که از یک الفبا محدود تشکیل شده است. Nتعداد سمبل های الفبا
مثال: یک متن دنباله ای از حروف است.N =26 ، یک تصویر دنباله ای از نقاط رنگی است.
N =2^24 = 16,777,216
تئوری شانون:
در مدل ارتباطی شانون و ویور سه دسته مشکل برای تحلیل ارتباط باز شناخته شده است که در سه سطح الف (فنی)، ب (معنایی ـ حاصل شیوه خطاب فرستنده)، و پ (اثربخشی، از حیث دریافت یا درک گیرنده) ظاهر می شود. هدف عمده شانون در ساختن این مدل، از بین بردن مشکلات در سطح الف و با این فرض اصلی بود که اگر رمرگذاری را اصلاح و مشکلات فنی را برطرف کنیم، مشکلات سطوح ب و پ نیز خودبه خود اصلاح خواهند شد.
در یک سیگنال اگر احتمال سمبل i ام pi باشد. Entropy سیگنال به صورت:
Bit
شنون ثابت کرد که غیر ممکن است بتوان سیگنال را با اختصاص کمتر از H بیت به هر سیمبل کد کرد.
مثال:تئوری شنون
مثال 1
N = 2, binary source
H = .469 bits
مثال 2
N = 6, p = 1/6 for all symbols
bit
مثال : تئوری شنون
دنباله زیر به عنوان سیگنال داده شده است
4 5 8 6 4 7 8 9 4 8
الفبا شامل سمبل های 4, 5, 6, 7, 8, 9 است.
s1 = 4, s2 = 5 , s3 = 6 , s4 = 7 , s5 = 8 , s6 = 9
p1 = p5 = 3/10, p2 = p3 = p4 = p6 = 1/10
Symbol
Number
Pi
4
3
0.3
5
1
0.1
6
1
0.1
7
1
0.1
8
3
0.3
9
1
0.1
H = 2.371 bits.
کد با طول متغییر Variable Length Code
برای هر سمبل (si) یک کد با طول li نسبت می دهیم.کدها باید قابل دیکد کردن باشند.شرط قابل دیکد بودن این است که هیچ کلمه کدی در ابتدای دیگری ظاهر نشود.(شرط prefix)، میانگین بیت اختصاصی به هر سمبل
همیشه Lave ≥ H
مثال : کد با طول متغییر
H = 1.75
کد کننده ایده ال می باشد چون
Lavg=H
Compression = code bits/source bits = 2/1.75 =1.143
کد هافمن(Huffman )
مشخصات
احتمال(فراوانی) سمبل ها باید مشخص باشد Codeword. با طول متفاوت به سمبل های مختلف نسبت داده می شود. سمبل ها تک تک کد می شوند. این کد شرط prefix را دارد.(قابل دیکد کردن می باشد)
خصوصیات کدینگ هافمن
• خصوصیت منحصر به فرد پیشوندی: هیچ کد هافمنی پیشوند کد هافمن دیگر نیست. این نکته مانع ایجاد هر گونه ابهامی در مرحلهٔ رمزگشایی می شود.
• بهینگی: حداقل افزونگی کد.دو نماد با کمترین فراوانی، دارای طول مساوی برای کد هافمنشان هستند و تنها در آخرین بیت تفاوت دارند.نمادهایی با فراوانی بیشتر دارای کد هافمن کوتاه تری نسبت به نمادهای با فراوانی کمترهستند.
کدینگ هافمن مراحلی از قبیل ساخت کد، کد کردن و دیکد کردن می باشد که به اختصار آن را توضیع میدهیم.
ساخت کد هافمن
1. سمبل ها به صورت نزولی بر اساس احتمال مرتب شوند.
2. دو سمبل آخر با هم ترکیب شده، یک سمبل فرضی با احتمال مجموع آن دو ایجاد شود.
3. اگربیش از یک سمبل باقی مانده برو به 1
4. بر اساس ترکیبات یک درخت بساز
5. به یال های سمت راست '0' و به یال سمت چپ '1' نسبت بده.
مثال: ساخت کد
مثال :کد کردن
می خواهیم دنباله زیر را کد کنیم
Werul
?
111
3
e
10
2
k
11010
5
l
01
2
r
00
2
u
1100
4
w
11011
5
دیکد کردن:
اگر k ماکزیمم طول کد سمبل می باشد. یک جدول 2k سطری ایجاد شود. هر سطرشامل: سمبل،طول کد می باشد.هر سمبل با طول L شامل 2k-l سطر از جدول می باشد.
مثال: K = 5 بنابراین جدول 32 خانه دارد. r با کد '00' ، 25-2=8 سطر را اشغال می کند. هر سطردارای سمبل خروجی r و طول 2 است.
00
r
01
l
10
e
111
?
1100
u
11010
k
11011
w
Symbol
Code
a
0
b
10
c
110
d
111
code
symbol
length
000
a
1
001
a
1
010
a
1
011
a
1
100
b
2
101
b
2
110
c
3
111
d
3
مثال :دیکد کردن
00
r
01
l
10
e
111
?
1100
u
11010
k
11011
w
• اولین کدجستجو 11011. Output = 'w', l = 5 . 5 بیت دیگر خوانده شود.
• کدجستجو 10001. Output = 'e', l = 2. '10' حذف می شود و 2 بیت دیگر خوانده می شود.
• کدجستجو 00110. Output = 'r', l = 2. '00' حذف می شود و 2 بیت دیگر خوانده می شود.
• کدجستجو 11000. Output = 'u', l = 4. '1100' حذف می شود و 4 بیت دیگر خوانده می شود.
• کدجستجو 01101……
فصل دوم:
رنگ درتصویر و ویدئو
علم رنگها
نور یک موج الکترومغناطیس است. رنگ آن به وسیله طول موج نور مشخص می شود. اکثر منابع نور، طول موج های مختلفی را تولید می کنند.چشم نمی تواند تمام موج ها را شناسایی کند، فقط قادر به تشخیص مواردی است که در محدوده طول موج های مرئی است.طول موج های کوتاه، آبی به نظر می رسند، طول موج های بلند هم قرمز.
شکل 2-1 جایگاه نور مرئی در طیف امواج الکترومغناطیس را نشان می دهد.
شکل 2-1
نور سفید شامل همه رنگ های یک رنگین کمان است. نور مرئی یک موج الکترومغناطیس در رنج 400 نانو متر تا 700 نانو متر است و می توان گفت:
(1 نانومتر معادل 9-10متر است). λf=c
توان طول موجهای مختلف در یک روز آفتابی با یکدیگر متفاوت است. Λنمادی برای طول موج است.این منحنی E(λ) نامیده می شود.
شکل2-2
شکل 2-2 توزیع توان نور در یک روز روشن را نشان میدهد که با توجه به آن بینایی انسان وتشخیص نور بهتر مورد تجزیه وتحلیل قرار می گیرد.
بینایی انسان
چشم مانند یک دوربین عمل می کند، با لنزها یا عدسی هایی که یک تصویر را به شبکیه چشم منعکس می کنند (بالا به پایین و چپ به راست معکوس شده).
شکل2-3
شبکیه چشم شامل تعداد زیادی سلولهای استوانه ای(Rod) و سلولهای مخروطی(Cone) است سلولهای استوانه ای (Rod)شدت روشنایی را حس می کنند و حتی در سطوح پایین نوری هم می توانند عمل کنند و تصویری در سایه هایی از خاکستری تولید می کنند همه گربه ها در شب خاکستری هستند.در سطوح نوری بالاتر، سلولهای مخروطی شکل(Cone)، هر کدام یک سیگنال تولید می کنند.که در شکل 2-4 ظاهر فیزیکی آن نشان داده شده است. به دلیل رنگدانه های متفاوت آنها، سه نوع از مخروطی شکل ها، به نور قرمز(R)، سبز(G) و آبی(B)، خیلی حساس هستند.مغز از تفاوت های R-G، G-B و B-R برای تولید سیگنال رنگ استفاده می کند.
شکل2-4
چشم انسان، به نورمیانه طیف مرئی، حساس تر است. حساسیت گیرنده های بینایی انسان، تابعی از طول موج است. حساسیت گیرنده آبی خیلی کوچکتر از منحنی های قرمز یا سبز است برایند نمودار حساسیت چشم به رنگها با (V (λ نمایش داده می شود.که در شکل5-2 نمایش داده شده است.
شکل2-5
منحنی سلولهای استوانه ای ، شبیه تابع روشنایی-بهره وریV (λ) است، اما انتقالی به سمت انتهای طیف قرمز، داشته است. چشم انسان در حدود 6 میلیون سلول مخروطی دارد ولی نسبت تعداد سلولهای حساس به قرمز و سبز و آبی متفاوت است و به نسبت 40، 20 ، 1 است بنابراین می توان گفت رنگی که تولید می شود به صورت 2R+G+B/20 است.
سطوح، مقادیر متفاوتی از نور را در انواع طول موج ها منعکس می کنند، و سطوح تیره انرژی کمتری نسبت به سطوح روشن منعکس می کنند. شکل 2-6 نشان دهنده انعکاس طیفی سطح نسبت به (1) کفش های ورزشی نارنجی (2) جین آبی کم رنگ می باشد. تابع انعکاس با( S(λمشخص می شود.
شکل 2- 6 (توابع انعکاس طیفی سطح برای S(λ)اشیاء)
تصویر سازی (Image Formation)
نحوه دیدن سطوح مختلف:
_ نور از منبع نور با (SPD E(λ روی یک سطح تابیده می شود، این نور با تابع انعکاس طیفی سطح S(λ)، منعکس می شود، و سپس توسط توابع سلول های مخروطی چشم فیلتر می شود. (q (λ
_ تابع C(λ)، سیگنال رنگ نامیده می شود و از حاصلضرب(E(λ (اسپکتورام)، در (S(λ (انعکاس):
C(λ) = E(λ) S(λ).
شکل2-7
سیستم دوربین ها
یک دوربین در هر موقعیت پیکسل (متناظر با یک موقعیت شبکیه ای)، سه سیگنال تولید می کند. سیگنال های آنالوگ به دیجیتال تبدیل می شوند، به عدد صحیح گرد شده و ذخیره می شوند.
تصحیح گاما درصفحه نمایش:
تصحیح گاما الگوریتمی ساده است که برای نمایش صحیح تصاویر به کار گرفته می شود.نور ساتع شده در حقیقت متناسب با ولتاژ نیست و متناسب با توانی از ولتاژ است؛ این توان، گاما (Gamma)نامیده می شود، با نماد γ .اگر مقدار عددی قرمز، R (نرمال شده بین صفر تا یک)باشد، مانیتور، نوری متناسب با Rγ را ساتع می کند. مقدار گاما حدود 2.2 است. برای حل این مشکل باید مقدار R را قبل از ارسال به صفحه نمایش تصحیح شود. توان (1/γ) قبل از انتقال افزوده می شود. بنابراین ما به سیگنال های خطی می رسیم: R → R′ = R1/γ ⇒ (R′)γ → R
مدل های رنگ در تصاویر
برای نمایشگرهای CRT از مدل رنگ RGB استفاده می شود.برای پرینترها از فضاهای رنگی تفاضلی (مانند CMY) استفاده می کنیم.استفاده از 8 بیت برای نمایش هر یک از کانال های رنگی.وقتی که دو پرتو نور، نقطه ای هدفی را روشن می کنند، رنگ های آن ها باهم جمع می شود.ولی برای جوهر که روی کاغذ رها می شود،وضعیت متفاوتی به وجود می آید؛ رنگ ها در اصطلاح از هم کم (تفریق) می شوند.جوهر زرد از کم شدن رنگ آبی از سفید پدیدار می شود،اما از بازتاب قرمز و سبز.
شکل2-8
همان طور که در شکل 2-8 دیده میشود مدل RGB ازسه رنگ R ،G ،B تشکیل شده است.این مدل به صورت additive عمل می کند.
مدل رنگ تفاضلی:CMY
تاکنون , ما بطور موثری تنها با رنگ های افزایشی (Additive Colors) سروکار داشتیم. یعنی , وقتیکه دو پرتو روشن هدفی را روشن میکند ، رنگ های آنها باهم جمع میشود ؛ وقتی که دو فسفر در یک صفحهCRT روشن میشوند، رنگ های شان به هم اضافه می کنند.ولی برای جوهر که روی کاغذ رها میشود،وضعیت متفاوتی بوجود میاد؛جوهر زرد از کم شدن رنگ آبی از سفید پدیدار می شود،اما از بازتاب قرمز و سبز؛ رنگ زرد ظاهر می شود.
CRM رنگ های تفاضلی CRM تجمعی
شکل 2-9
به جای رنگ های ابتدایی قرمز،سبز،آبی؛ما به رنگ اولیه ای نیاز داریم که مقدار آن -R ؛ – G ؛-B باشد.این رنگهای اولیه از هم کم شونده فیروزه ای (C ) ، ارغوانی (M) ، زرد (Y) هستند.
تبدیل RGBبه CMY:
تبدیل معکوس:
بهبود در سیستم CMY: رنگ سیاه ایجاد شده توسط ترکیب C,M,K سیاه واقعی نیست و شبیه رنگ پوست بادمجان است (قهوه ای خیلی پررنگ) رنگ سیاه تولید شده توسط پرینتر واقعا سیاه است.به جای ترکیب سه جوهر برای ایجاد رنگ سیاه از جوهر سیاه استفاده می شود. برای حل این مشکل اصلاح زیر را انجام می دهیم.
مدل های رنگ در ویدیو
اکثر مدلهای رنگ در ویدئو از روشهای آنالوگ استفاده شده در تلویزیونهای قدیمی مشتق شده اند. (Luminance) درخشندگی ازاطلاعات رنگ (Chrominance) جداشده است. مدلهای معروف YIQ ، YUV و YCbCr هستند مدل YIQ برای کد کردن سیگنالهای تلویزیون درآمریکای شمالی و ژاپن استفاده می شود دراروپا نوارهای ویدیو از کدینگ PAL یا SECAM استفاده میکنند.که در تلویزیون هایی که بر اساس ماتریس انتقالی که YUV نامیده میشود،بکار برده میشود. ویدیو دیجیتال عمدتا از یک تبدیل ماتریس که YCbCr نامیده میشود استفاده می کند که خیلی شبیه YUV است.
مدل رنگYUV : طلاعات مربوط به روشنایی در Y ذخیره می شود. اطلاعات مربوط به رنگ در U و V ذخیره می شود :
U = B′ − Y′ V = R′ − Y′
برای =1 , R′ = G′ = B′ مقدار (luminance)، Y′ برابر است با 0.299+0.587+0.114 = 1.0 .و برای یک تصویر (سیاه و سفید ) ،U و V صفر هستند.
شکل 2-10 یک مدل رنگ YUV را نشان می دهد.
Y U V
شکل2-10
مدل رنگ YIQ :YIQ در پخش رنگ تلویزیون NTSC به کار رفته است. I و Q دوران داده شده U وV هستند.Y' در YIQ مشابه است با YUV ؛ U وV به اندازه 33° چرخیده شده اند.
شکل2-11 یک مدل رنگ YIQ رانشان می دهد که Q ،I مولفه های رنگی هستند.
شکل2-11
مدل رنگ YCbCr : از این مدل در ویدیو دیجیتال استفاده می شود.این مدل ارتباط نزدیکی با YUV دارد.
CD = ((B′ − Y′)/1.772)+0.5
Cr = ((R′ − Y′)/1.402)+0.
در عمل از8 بیت برای کد کردن Y و Cb و Cr استفاده شده است .مقدار Y، حداکثر 219 و حداقل مقدار 16+ است.(بقیه مقادیر رزرو شده اند.)Cb وCr در محدوده ای از 112 ± و مقدار آفست 128+ هستند.(حداقل 16 و حداکثر 240) اگر R′, G′, B′ اعداد اعشاری در بازه [0..+ 1], باشند،پس ما می توانیم Y ′, Cb, Cr را در محدوده [0..255] فراهم کنیم.
تبدیل YCbCr در فشرده ازی تصویر JPEG وفشرده سازی ویدیویی MPEG استفاده شده است.
فصل سوم
مفاهیم اولیه در ویدئو
انواع سیگنال های ویدئویی
ویدئو مولفه ای ( Component Video):از 3 سیگنال ویدیوی متفاوت (قرمز و سبز و آبی) ارسال استفاده می شود. هر کانال رنگی یک سیگنال ویدیویی جدا ارسال می کند.بیشتر سیستم های کامپیوتری از ویدیو های مرکب با سیگنال های متفاوتی برای باندهای R, G, B استفاده می کنند. جداسازی رنگ در ویدیوی مرکب در بهترین حالت ممکن انجام می شود.این روش به پهنای باند بالا و الگوریتمهای همزمان سازی خوبی بین این 3 ترکیب نیاز دارد.
شکل3-1
ویدئوی مرکب (Composite Video): سیگنال های رنگی (Chrominance) و شدت نور(Luminance) در یک طول موج حامل ترکیب می شوند.
Chrominance : ترکیبی از 2 مولفه رنگی است (I,Q یا U,V).اطلاعات رنگی و سطح خاکستری می توانند در گیرنده از هم جدا شده و سپس دو مولفه رنگی میتوانند مجدداً بازسازی شوند.انتقال فقط از طریق یک سیم انجام می شود. سیگنال های صدا به این تک سیگنال اضافه می شوند. زمانی که رنگ و شدت در یک سیگنال ترکیب می شوند، مقداری تداخل بین سیگنال های رنگی و سطح خاکستری بوجود می آید که غیر قابل اجتناب است.
شکل3-2
S-Video:
S-Video (separated video یا Super-video در S-VHS )از 2 تا سیم استفاده میکند یکی برای روشنایی و دیگری برای رنگ در نتیجه تداخل کمتری بین اطلاعات رنگ و اطلاعات روشنایی بوجود می اید. علت استفاده از یک سیگنال مجزا برای روشنایی ، حساسیت زیاد آن برای چشم است. چون حساسیت چشم به روشنایی تصویر بیشتر از رنگ آن است در نتیجه ما میتوانیم اطلاعات کمتری را برای رنگهای سیگنال نسبت به اطلاعات شدت روشنایی ارسال کنیم.
شکل3-3
ویدئو آنالوگ:
سیگنال آنالوگ در هر لحظه از زمان فقط حاوی یک مقدار است بنابراین برای ارسال ویدئو باید اطلاعات تصویر به صورت سطر به سطر ارسال شود در تلویزیون و دیگر مونیتورها و سیستم های چند رسانه ای برای ایجاد کیفیت بیشتر از تکنیک Interlace استفاده می شود(اسکن یک در میان) در این روش سطرها به دو دسته زوج وفرد تقسیم می شوند و سطرهای فرد، اول پیمایش شده و سپس سطرهای زوج پیمایش میشوند.
شکل3-4
ابتدا سطرهای فرد اسکن می شوند.از P تا Q سپس R تا S و…و در آخر تا T برای اسکن سطرهای زوج از U شروع میکند تا در اخر به V برسد. پرش از Q تا R و.. را جابجایی افقی میگویند(horizontal retrace ) پرش از T تا U و V تا P راجابجایی عمودی مینامند. (Vertical retrace ) به دلیل نمونه برداریِ یک درمیان، خط های زوج و فرد به صورت هم زمان نمایش داده می شوند.این تفاوت زمانی معمولاً قابل ملاحظه نیست. مگر زمانی که تغییری سریع در تصویر وجود داشته باشد. اسکن کردن یک در میان 2 فیلد برای هر فریم blur تولید می کند.فریم ویدیو، فیلد 1، فیلد 2 و اختلاف فیلدها، در یک ویدئوی انالوگ چگونه عملیات همزمانی انجام شود؟ از کجا بفهمیم سیگنالی که در حال دریافت هستیم الان در حال ارسال کدام سطر یا ستون است؟در سیگنال ویدئو برای نمایش رنگ سیاه از مقدار صفر استفاده نمی کنند (مقدار استفاده شده برای رنگ سیاه یک عدد کوچک نزدیک به صفر است) بنابراین از مقدار صفر می توان برای سنکرون سازی استفاده کرد
.
شکل 3-5 سیگنال الکترونیکی برای یک اسکن خط NTSC
ویدئو NTSC
NTSC (National Television System Committee) استانداردی است که بیشترین استفاده را در آمریکای شمالی و ژاپن دارد. از نسبت صفحه (Aspect Ratio) 4:3، 525 خط اسکن در هر فریم و 30 فریم در ثانیه استفاده می کند.NTSC از مدل رنگ YIQ استفاده می کند.NTSC از یک سیستم اسکن یک خط در میان پیروی می کند و هر فریم به دو فیلد با 262.5 lines/field تقسیم می شود .بنابراین فرکانس حرکت افقی 525×29.97 ≈ 15, 734 lines/sec است که هر کدام از خط ها در 1/15.734 × 103 sec ≈ 63.6μsec به خارج منتقل می شوند. زمان جابجایی افقی 10.9 μsecزمان می گیرد، پس 52.7 μsec برای سیگنال خط فعال (اطلاعات تصویر) باقی می ماند.
شکل3-6
شکل 3-6 یک Video raster یا همان ویدئوی شطرنجی است. که شامل پیمایش و اطلاعات همزمان سازی می باشد. در جابجایی عمودی در شروع هر فیلد طی 20 خط اطلاعات کنترلی ذخیره میشود از اینرو تعداد خطوط فعال ویدئویی در هر فریم فقط 485 عدد است. (2*20- 525) بطور مشابه تقریبا 16درصد از رستر افقی،که در طرف چپ هستند برای جابجایی افقی وهمزمانسازی است. از آنجایی که جابجایی افقی 10.9 μsec طول می کشد بنابراین مدت زمانی که در یک سطر نمایش انجام می شود ، 52.7 μsec است.
تعداد نمونه ها افقی در ویدیوی NTSC یک سیگنال آنالوگ مقداری ثابت نیست. تعداد نمونه های هر خط برای فرمت های مختلف ویدیو در جدول 3-1 نشان داره شده است.
انواع
تعداد نمونه ها در هر خط
VHS
240
S-VHS
400-425
Beta-SP
500
Standard 8 mm
300
Hi-8 mm
425
جدول3-1
ویدئوی PAL
PAL(Phase Alternating Line) یک استاندارد تلویزیونی است که در غرب اروپا، چین، هند، و بسیاری از مناطق دیگر جهان به طور گسترده استفاده می شود.PAL در هر فریم از 625 خط اسکن، 25 فریم بر ثانیه، نسبت صفحه 4:3 و فیلدهای یک در میان استفاده می کند.PAL از مدل رنگیYUV استفاده می کند. برای بهتر کردن کیفیت تصویر، در خطوط اسکن متوالی سیگنال های رنگی علامت های یک در میان (U-و+U) دارند. با استفاده از یک فیلتر شانه ای، جداسازی سیگنال ها انجام می شود. در خطوط متوالی برای حذف سیگنال های رنگی (که همواره مقادیر قرینه را حمل می کند) و بدست آوردن کیفیت بالاتر سیگنال های Yمیانگین گیری می شوند.
ویدئوی SECAM
SECAM مخفف System Electronique Couleur Avec Memoire می باشد، و سومین استاندارد مهم پخش تلویزیونی است.SECAM همچنین در هر فریم از 625 خط اسکن، 25 فریم در هر ثانیه،با نسبت دید 4:3 و از تکنیک اینترلیس استفاده می کند.SECAM و PAL بسیار بهم شبیه هستند. آنها اندکی در طرح کدگذاری رنگ متفاوت هستند:آنها بصورت خطوط متناوب فرستاده میشوند، در هر خط اسکن فقط یکی از سیگنالهای U یا V فرستاده خواهد شد.
مقایسه ای از سیستم های تلویزیون آنالوگ :
سیستم تلویزیونی
نرخ فریم(fps)
تعداد خطوط پویش
کل پهنای کانال(MHz)
پهنای باند تخصیص داده شده(MHz)
Y
I یا U
Q یا Vش
NTSC
29.97
525
6.0
4.2
1.6
0.6
PAL
25
625
8.0
5.5
1.8
1.8
SECAM
25
625
8.0
6.0
2.0
2.0
جدول3-2
انتخاب اجزای رنگ
شکل3-7
استانداردهای CCIR برای ویدیوهای دیجیتال
Consultative Committee for International Radio
یکی از مهمترین استانداردهای تولیدی آن CCIR-601 است که برای ویدیو دیجیتال ایجاد شده است.
CCIR 601
525/60
NTSC
CCIR 601
625/50
PAL/SECAM
CIF
QCIF
وضوح سیاه سفید
720 x 480
720 x 576
352 x 288
176 x 144
وضوح رنگی
360 x 480
360 x 576
176 x 144
88 x 72
نمونه برداری رنگ
4:2:2
4:2:2
4:2:0
4:2:0
فیلد/ثانیه
60
50
30
30
یک در میانی
Yes
Yes
No
No
جدول3-4
HDTV (تلویزیون با آشکارسازی بالا)
هدف اصلی HDTV افزایش آشکارسازی در هر واحد سطح نیست، بلکه بیشتر افزایش عرض فیلد تصویر به طور خاص است.نسل اول HDTV بر پایه یک فن آوری آنالوگ به وسیله Sony و NHK در ژاپن در اواخر سال 1970 توسعه داده شد.از آنجایی که HDTV غیر فشرده پهنای باند بیشتر از 20 مگا هرتز نیاز دارد و در حال حاضر کانال های 6 مگاهرتزی یا 8 مگا هرتزی موجودند، تکنیک های متفاوت فشرده سازی مورد تحقیق قرار گرفتند.
تعداد پیکسل های فعال هر خط
تعداد خطوط فعال
نسبت تصویر
نرخ تصویر
1,920
1,080
16:9
60I 30P 24P
1,280
720
16:9
60P 30P 24P
704
480
16:9 & 4:3
60I 60P 30P 24P
640
480
4:3
60I 60P 30P 24P
استاندارد پشتیبان فرمتهای پویش ویدئویی که در جدول 4.5 نشان داده شده است. "I" به معنی Interlaceو "P" به معنی پویش پیشرونده (غیر یک در میان) می باشد.
جدول3-5
برای ویدئو، MPEG-2 به عنوان استاندارد فشرده سازی انتخاب شده است. برای صدا AC-3 استاندارد است. از 5کانال فراگیر صدا به اضافه یک کانال subwooferپشتیبانی میکند. تفاوت برجسته بین تلویزیون های اولیه و HDTV :HDTV یک نسبت تصویر عریضتر، 16:9 به جای 4:3 دارد.HDTV بسوی پویش پیشرونده ( non interlace) حرکت می کند.
انواع سرویسهای فراهم شده عبارتند از:
SDTV (Standard Definition TV ) -1: تلویزیون NTSC رایج یا بالاتر.
EDTV (Enhanced Definition TV): 480 -2 خط فعال یا بالاتر.
HDTV (High Definition TV): 720 -3 خط فعال یا بالاتر.
فصل چهارم
دیجیتال سازی صدا
Quantization
انتقال صدا
مقدمه:
صدا نوعی موج (مانند نور) است، اما مرئی نبوده و از درگیری مولکول های هوای فشرده و منبسط شده، توسط دستگاه های فیزیکی ایجاد می شود.برای نمونه، یک پخش کننده صدا در یک سیستم صوتی، فضای جلو و عقب خود را مرتعش کرده و یک موج فشار طولی تولید می کند که ما آن را به عنوان صدا دریافت می کنیم.از آنجایی که صدا یک موج فشرده است، کمیتی پیوسته محسوب می شود. برای دیجیتال سازی آن باید این کمیت گسسته شود.اگرچه این موج، موجی طولی است، اما مشخصات و رفتار موج معمولی را دارد مانند reflection، (تغییر زاویه هنگامی که یک واسطه با چگالی متفاوت وارد می شود) و diffraction (خمیدگی حول یک مانع).ویژگیهای یک صوت شامل دامنه(برحسبdb)،فرکانس(زیر وبم)Pich و طنین(timbre) می باشد.
چگونه ما اصوات را می شنویم؟!
انسان می تواند فرکانس های بازه 20 تا 20کیلو هرتز را بشنود،صدای تولید شده توسط حنجره در بازه صفر تا حدود 4 کیلوهرتز است،توانایی تشخیص اصواتی با اختلاف 1.5 هرتز را دارد،این توانایی با افزایش سن کاهش می یابد که در سن 50 سالگی حداکثر 14 کیلو هرتز و در سن 70 سالگی حداکثر 10 کیلو هرتز می باشد.
در جدول 4-1 دامنه صداهای رایج بر حسب دسی بل مشخص شده اند..
جدول4-1
ذخیره وباز نوازی صوت
در این بخش ما ابتدا باید با تبدیل یک موج آنالوگ به دیجیتال جهت ذخیره و دستکاری آن (Sampling) و تبدیل موج دیجیتال به آنالوگ برای نواخت مجدد انجام کیرد.نمونه برداری ممکن است توسط خود PC یا یک سخت افزار کمکی انجام شود.که در شکل 4-2 مراحل کار ذخیره وباز نوازی یک صوت مشخص شده است.
شکل 4-2
پارامترهای مهم در دیجیتال کردن شامل :نمونه برداری(sampling Rate)،نحوه کوانتیزاسیون،نحوه کد کردن داده ها می باشد.
تئوری نایکوییست
هر سیگنال تشکیل شده از مجموع تعدادی منحنی های سینوسی تشکیل شده است.
شکل4-3
که درشکل 4-3 ایجاد یک سیگنال پیچیده توسط منحنی های سینوسی دیده می شود. تئورینایکوییست این نکته را بیان می کند که چه طور به صورت متناوب در بعد زمان نمونه برداری کنیم تا بتوان صدای اصلی را به شکل درستی بازیابی کرد.
شکل 4-4
در شکل 4-4 : (a) یک فرکانس سیگنال ،(b) نمونه برداری دقیقاً روی فرکانس، یک سیگنال ثابت را تولید می کند،(c) نمونه برداری روی 1.5 برابر هر سیکل، alias ایجاد می کند. برای نمونه برداری درست باید از نرخ نمونه برداری دو برابر بیشترین فرکانس موجود در سیگنال استفاده شود. این نرخ، نرخ نایکوییست نامیده می شود.
انتخاب نرخ نمونه برداری برای صدا انسانها حداکثر فرکانسهای نزدیک به 20000 هرتز را می شنوند سرعت نمونه برداری مناسب 40 کیلو نمونه در ثانیه است سرعت نمونه برداری در عمل 44100 نمونه در ثانیه است در این صورت مشکل Aliasing رخ نخواهد داد.انتخاب نرخ نمونه برداری به کاربرد نیز بستگی دارد(برای تلفن مقدار کمتری نیاز است).
کوانتیزه کردن(گسسته سازی در جهت دامنه):در شکل 4-5 (a) :نمونه برداری سیگنال آنالوگ در بعد زمان (b) :نمونه برداری سیگنال آنالوگ در بعد دامنه
شکل4-5
با افزایش تعداد بیت دقت بالاتری خواهیم داشت،8 بیت : 256 مقدار ممکن،16 بیت : 65536 مقدار ممکن در ضمن میتوان گفت مشکل کوانتیزه کردن با 8 بیت بسیاری از سطوح برای دامنه سیگنال قابل بیان نخواهد بود ودر نهایت تولید نویز.
کوانتیزه کردن دارای دونوع خطی وغیر خطی می باشد که نوع خطی ان به صورت فواصل ثابت و مستقل از دامنه است وغیر خطی آن به صورت فواطل متغیر، افزایش فواطل در دامنه های بالا و نگاشت لگاریتمی می باشد.
کوتنایز
تعداد مقادیر خروجی متفاوت (متمایز) را به مجموعه بسیار کوچکتری کاهش می دهد.یه روش lossy می باشد.درشکل 4-6 پارامترهای مختلفی شامل مقدار آستانه ،th و طول گام ،q ونصف طول گام ،Qp
شکل 4-6
شکل 4-7
اندیس کوانتایز به گیرنده ارسال می شود.
ضرایب بازسازی شده در گیرنده بصورت زیر محاسبه می شوند.
مثال کوانتایز:
ورودی : نقاط 8 بیتی به صورت سطح خاکستری 0 ≤ data ≤ 255، هدف: تبدیل هر نقطه (سمبل) به 3 بیت، روش : 5 بیت شیفت به راست (تقسیم بر 32=25) این کار کوانتایز نامیده می شود. گام کوانتایز 32 q= ، تمامی مقادیر بین 0 تا 31 به مقدار 0 نگاشته می شوند.تمامی مقادیر بین 32 تا 63 به مقدار 1 نگاشته می شوند. بازیابی مقادیر : ضرب در 32 q = و سپس جمع با 16، این کار dequantization – عکس کوانتایز نامیده می شود. هر مقداری که بین 0 تا 31 بوده الان 16 است. هر مقداری که بین 32 تا 64 بوده الان 48 است.
مقدار بازسازی شده
کوانتایز شده
محدود ه ورودی
16
0
0-31
48
1
32-63
80
2
64-95
112
3
96-127
144
4
128-159
176
5
160-191
208
6
192-223
240
7
224-255
شکل4-7
فیلتر کردن صوت (Audio Filtering):
قبل از نمونه گیری و تبدیل آنالوگ به دیجیتال، سیگنال صوت را معمولاً به منظور رفع فرکانس های ناخواسته فیلتر می کنند.برای صحبت، فرکانس های 50Hz تا 10kHzنگه داشته می شوند، و سایر فرکانس ها توسط فیلتر band-pass مسدود می شوند.سیگنال صوتی موسیقی، معمولاً شامل 20Hz تا حدود 20kHz است. در طرف رمزگشا، یک فیلتر low-pass بعد از مدار دیجیتال به آنالوگ استفاده می شود.
بلوک دیاگرام کدینگPCM
شکل 4-8
درشکل 4-8 بلوک های دوم وسوم، این دو بلوک باهمدیگر باعث کوانتیزه کردن غیر یک نواخت سیگانال می شود.بلوک چهارم تبدیل آنالوگ به دیجیتال را برعهده دارد. بلوک پنجم، عکس تابع یک نواخت ساز می باشد.و اما بلوک آخر سیگالهای بالا تراز 4کیلوهرتز را که به خاطر کوانتیزاسیون ایجادشده است را حذف میکند.
کدینگ تفاضلی
کدینگ PCM حافظه زیادی مصرف می کند، معمولا از تفاضل برای کد کردن استفاده می شود تا اعداد کوچکتر شوند و تعداد بیت کمتری برای ذخیره سازی نیاز داشته باشند. چون نمونه ها در محور زمان به نحوی با یکدیگر رابطه دارند بنابراین تفاضل باعث فشرده شدن هیستوگرام حول مقدار صفر می گردد. بنابراین تعداد بیتهای تخصیصی به هر کد کاهش می یابد.
انتقال صوت:
کدگذاری تفاضلی صدا
در طول زمان اطلاعات مشابه فراوانی وجود دارد، که به آن افزونگی زمانی (Temporal Redundancy) گفته می شود.با تفاضل گیری نمونه های متوالی سیگنال می توان این افزونگی را کاهش داد.
سیگنال اصلی
هیستوگرام سیگنال
هیستوگرام سیگنال تفاضلی
کدگذاری پیش بینی کننده بدون تلف (Lossless Predictive Coding):در این روش نمونه بعدی را از نمونه های قبل پیش بینی می کنیم و فقط تفاضل مقدار اصلی و پیش بینی شده را ارسال می کنیم.
می توان از پیش بینی کننده های بهتری هم استفاده کرد. می توان مقدار پیشبینی شده را تابعی از مقادیر قبلی سیگنال در نظر گرفت.
مثال: برای انتقال رشته
f1, f2, f3, f4, f5 = 21, 22, 27, 25, 22
با کدگذاری پیش بینی کننده با این رابطه مقادیر خطا به این شکل خواهند بود:
Lossless Predictive Coding:
وجود یک مشکل در ارسال e
اگر مقادیر سیگنال در بازه صفر تا 255 باشد آنگاه مقدار e در بازه 255- تا 255+ خواهد شد و به تعداد بیت بیشتری نیاز است.
راه حل اول: استفاده از کدها با طول های متغیر (Variable Length Coding)
راه حل دوم: تعریف دو کد جدید و خاص به نامهای Shift-Up و Shift-Down
در این راه حل تعداد کدهای را محدود می کنیم مثلا بین 15- تا 16+، اگر مقدار e خارج از این بازه قرار گرفت، به تعداد کافی کدهای SU یا SD ارسال می کنیم. برای بازه فوق ، SU معادل با 32 و SD معادل با 32- است. مثلا برای ارسال عدد 100 برای e، رشته SU ,SU ,SU ,4 ارسال می شود.
بلاک دیاگرام Lossless Predictive Coding:
شکل 4-9 شامل شماتیک دیاگرام رمزکننده و رمزگشای پیش بینی کننده می باشد.
شکل 4-9
کدینگ DPCM:
این روش مشابه روش قبلی است با این تفاوت که e کوانتیزه و سپس ارسال می شود.بنابراین الگوریتم DPCM از نوع Lossy است.
کدینگ DPCM:
چرا در این روش برای محاسبه مقدار پیشبینی از مقادیر واقعی استفاده نمی شود؟
به علت lossy بودن الگوریتم سمت گیرنده به مقادیر واقعی دسترسی ندارد بنابراین مقدار پیشبینی دو طرف با هم برابر نمی شود.
شکل 4-10 بلوک دیاگرام کدینگDCMP رانشان میدهد.
شکل 4-10
مثال از کدینگDPCM
کدینگ Delta Modulation:
در این روش مقدار e یک بیتی در نظر گرفته می شود.
مثال کدینگ Delta Modulation:
با فرضk=4 و
اگر تغییرات سیگنال اصلی شدید باشد آنگاه امکان دنبال کردن آن وجود ندارد.
فصل پنجم
کدکرن ترکیبی
مقذمه:
الگوریتم های فشرده سازی بدون از دست رفتن اطلاعات، غالباً نرخ فشرده سازی مناسبی ندارند.بیشتر الگوریتم های فشرده سازی چند رسانه ای از نوع باتلف هستند. (Lossy) فشرده سازی با اتلاف چیست ؟
– بعد از دیکد کردن داده فشرده شده همان داده اصلی به دست نمی آید ولی تقریباً نزدیک به آن است .
– از نرخ فشرده سازی بسیار بیشتری نسبت به فشرده سازی بدون از دست رفتن اطلاعات برخوردار است .
کدکردن ترکیبی:
تبدیل دامنه برای حذف افزونگی مکانی در تصاویر استفاده می شود.پیکسلها به دامنه دیگری نگاشت می شوند. اکثر انرژی یک تصویر از صحنه طبیعی در منطقه فرکانس پایین می باشد.حذف فرکانس های بالا تاثیر قابل توجهی بر کیفیت تصویر باز سازی شده ندارد.
شکل 5-1
y1 میانگین x1,x2 می باشد.به y1 مقدار DC می گویند.ضریب برای یکسان سازی انرژی سیگنال اولیه و سیگنال تبدیل یافته می باشد.
انرژی سیگنال اولیه
انرژی سیگنال تبدیل یافته
ورودی : x = (x1, x2, … xn) یک سیگنال وابسته، تبدیل به ( y = (y1, y2, … yn که یک سیگنال غیر وابسته است. Y=Ax A یک ماتریس متعامد (A-1 = AT) y1 دارای مقدار بزرگی می باشد n-1 ضریب باقی مانده مقدار کوچکتری دارند.عناصر ماتریس تبدیل باید بگونه ای باشند که یک یا چند ضریب بزرگ و بقیه خیلی کوچک باشند.
تبدیل کسینوسی گسسته (DCT):
دلایل استفاده از این تبدیل انرژی را در تصاویر بخوبی در یک یا چند ضریب فشرده می کند، الگوریتم سریع و کارآمد در دسترس می باشد(fast DCT)، وابستگی پیکسل ها ، در جهت عمودی، درجهت افقی، درجهت زمانی و نوع دیگر آن DCT سه بعدی، DCT دوبعدی، یک DCT در جهت افقی، سپس یک DCT در جهت عمودی می باشد.
برای یک بلاک MxN پیکسل، با استفاده از تبدیل DCTیک بعدی درجهت افقی می توان گفت:
C(u) = for u = 0
C(u) = 1 otherwise
N مجموعه از تبدیلات برروی M ضریب با فرکانس مشابه در جهت عمودی گرفته می شود:
تبدیل بلاک یا کل تصویر، شامل مراحل تبدیل کل تصویر، تبدیل بلاک، تقسیم تصویر به بلاک های کوچک، که هر بلاک به صورت مجزا تبدیل می شود. روش بلاکی کارآیی بهتری از همه تصویر دارد. استاندارد JPEG, MPEG ، DCT را بر روی بلاک های 8×8 انجام می دهند.که در شکل 5-3 مشخص شده است.
شکل 5-3
DCT چه عملی انجام می دهد؟
مقادیر بین (0,255) را به (-2047,+2047) تبدیل می کند. هیچ فشرده سازی انجام نمی دهد.تصویر را de-correlate می کند. انرژی تصویر را فشرده می کند. ضرایب AC,DC ضرایب DC، اهمیت بیشتری از ضرایب AC دارند.
شکل 5-5 یک DCT دو بعدی را نمایش میدهد که بصورت گرافیکی می باشد ودر بعاد8*8 است.
شکل 5-5
فصل ششم
فشرده سازی تصویر
Jpeg
مقدمه:
JPEG: the Joint Photographic Experts Group
در سال 1992JPEG به صورت رسمی به عنوان استاندارد بین المللی پذیرفته شد.دارای دو روش حذف وابستگی، شامل DCT در پیاده سازی های lossyو Predictive coding در پیاده سازی های lossless است. و دو روش کد کردن انتروپی که آنها نیز شامل:Huffmanو Arithmetic هستند. ودر نهایت چهار روش فشرده سازی: Sequential DCTو Progressive DCTو Losslessو Hierarchical
فشرده سازی :JPEG
روش کد گذاری تبدیلیDCT در JPEG بر پایه دو نظریه می باشد:نظریه1: محتوای مفید تصویر به طور نسبتا آهسته ای در طول تصویر تغییر می کند، برای مثال در یک بلوک تصویر8*8، شدت تغییر زیاد در فضای کوچک و در زمان های متعدد غیر معمول است. نظریه2: آزمایش های روانشناسی، نشان داده است که انسانها در صورت حذف مولفه های فرکانس بالای تصویر متوجه نمی شوند و به مولفه های فرکانس پایین حساس تر هستند. چشم انسان وجود یک تغییر کوچک در یک زمینه ثابت را خیلی زود درک می کند(مولفه فرکانس پایین) ولی وجود تغییرات در یک زمینه پر از تغییرات را براحتی درک نمی کند.
بلوک دیاگرام :jpeg
شکل6-1
ابتدا باید مراحل الگوریتم فشرده سازی Jpegطی کنیم. تبدیل مدل RGBبه YIQ یا YUV، کاهش نمونه های I,Q (اطلاعات رنگ)، تبدیل تصویر به بلاکهای 8×8، محاسبه تبدیلDCT روی بلاکهای 8×8، تصویر اصلی را با( f(i, j و تبدیل یافته آن را با( F(u, v نمایش می دهند.
مراحل الگوریتم فشرده سازی Jpeg: در صورتی که نرخ اتلاف زیاد شود در تصویر باز سازی شده بلاک ها و مرز آنها مشخص می شود.
کوانتیزه کردن:
ماتریس Q، مقادیر استانداردی دارد. البته قابل تغییر نیز می باشد.
کوانتیزه کردن: هر یک از 64 جزء فرکانسی بدست آمده برای هر بلوک بر ضرایب کوانتیزه کردن تقسیم شده و سپس نزدیکترین عدد صحیح گِرد می شوند. ماتریس (Q(u, v در پایین ترین گوشه راست، مقادیر بزرگتری دارد. این امر، باعث وارد کردن اتلاف بیشتر در فرکانس های بالاتر خواهد شد. مشخصات ماتریس Q: مقادیر (Q(u, v پیش فرض که از مطالعات روانشناسی و با هدف افزایش نرخ فشرده سازی وکاهش اتلاف های ادراکی تصاویر JPEG بدست آمده اند.
مقادیر استفاده شده برای ماتریس Q، این ماتریس برای شدت روشنایی و اطلاعات رنگ متفاوت است.
شکل6-2
روش کد کردن
اعداد از گوشه ی بالای سمت چپ بصورت مورب و زیگ زاگ جاروب شده و 64 ضریب پشت سر هم قرار می گیرند. اولین ضریب این رشته مولفه DC بلوک است و 63 ضریب بعدی مولفه های AC هستند. به خاطر کوانتزاسیون تعداد زیادی از ضرایب انتهایی صفر هستند به همین دلیل مقادیر AC به روش RLE کد می شوند. مقادیر DC به روش DPCM کد می شوند. جداول کوانتایز base line برای کیفیت 50(q_JPEG ) استفاده می شوند، برای سایر کیفیت ها مقادیر این جداول باید در عدد α ضرب شوند. حداقل مقدار ( αQ(u, v, یک می با شد.(حالت lossless)
ضرایب DC به صورت تفاضلی (DPCM )کد می شوند. ضرایب AC ابتدا به صورت zig-zag scan(ZZ) می شوند.ZZ برای ایجاد بیشترین سلسله (run) صفر پشت سر هم می باشد. کد هر ضریب AC متشکل از طول run و به دنبال آن مقدار ضریب AC می باشد.
شکل 6-3
برای انتروپی کد کردن هر ضریب کوانتایز شده بصورت (symob1,symbol2)کد می شود. symob1 بصورت VLC کد می شودsymob2 . بصورت باینری کد می شود.symob2 معرف مقدار ضریب می باشد.
در کدکردن انتروپی باقیمانده های DC باقیمانده ها به 11 categories (دسته) تقسیم می شوند. هر باقیمانده به صورت (category, value) کد می شود. بجز گروه 0 که مقدار 0 حذف می شود. برای category شماره K، value با 2k بیت مشخص می شود. اگر مقدار منفی باشد به شکل مکمل یک تبدیل می شود.Category ، با روش هافمن کد شده اند و مقادیر بدون کد کردن ارسال می شوند.
ضرایب DCT قبل از entropy coding ، pre-process می شوند. ضرایب AC و ضرایب DC به دو روش متفاوت کد می شوند. ضرایب غیر صفر به صورت run-length کد می شوند. Huffman یا arithmetic coding استفاده می شود. Arithmetic coding عملکرد بهتری دارد. برای استفاده از Arithmetic coding نیاز به مجوز می باشد.(پیاده سازی آن نیز مشکل می باشد.) برای کد هافمن جدول کد نیز باید در فایل ذخیره شود. معمولا، جداول baseline استفاده می شوند. محدودیت ها : هیچ کدی نباید بزرگتر از 16 بیت باشد.xFF 0 نباید استفاده شود.به عوان نمونه می توان مثال زیر را بیان کرد.
CAT
Range
0
–
1
-1, 1
2
-3, -2, 2,3
3
-7,…-4, 4,…7
4
-15, …-8, 8, …15
5
-31, …-16, 16,…31
6
-63, …-32, 32, …63
7
-127, … -64, 64, … 127
8
-255, …-128, 128, …255
9
-511,… -256, 256, …511
10
-1023, …-512, 512, …1023
11
-2047,… -1024, 1024,… 2047
residual = 5 (1012)
Category = 3, code=100
value= 101 =>100101
residual = -10, (-10102)
Category = 4, code=101
value = 0101=>1010101
residual = 67 = 10000112
Category = 7, 11110
(CAT)
Codeword
0
00
1
010
2
011
3
100
4
101
5
110
6
1110
7
11110
8
111110
9
1111110
10
11111110
11
111111110
value = 1000011=> 11110 1000011
کد کردن ضریب AC
ضرایب AC ابتدا به صورت zig-zag scan(ZZ) می شوند.ZZ برای ایجاد بیشترین سلسله (run) صفر پشت سر هم می باشد. هر ضریب غیر صفر AC به صورت ((RUN, CAT), value)کد می شود. RUN تعداد ضرایب صفر قبل از این ضریب AC می باشد.
شکل6-4
حداکثر طول run ، 15 می باشد. یک run ، طولانی تر به صورت ( 15,0) وبه دنبال آن ادامه run می آید. به عنوان مثال یک run از 24 صفر که به دنبال آن 7 قرار دارد به صورت (15,0) (9,7) کد می شود. بعد از آنکه تمامی ضرایب غیر صفر کد شدند. 0,0) ((EOB)اضافه می شود که نشان دهنده انتهای بلاک می باشد. طول RUN و شماره category به صورت offline از روی جدول تبدیل به کد می شود.
مثال:
run of 6 zeros,
size = -18. In the table, -18
is in category 5. Code is
(6/5, 01101). If the Huffman
code for 6/5 is 1101 (baseline table),
codeword = 110101101
مروری بر JPEG:
ضرایب AC و DC به صورت متفاوت کد می شوند. ضرایب DC به صورت تفاضلی نسبت به ضریب DC بلاک قبلی کد می شوند. Size/Amplitude coding
ضرایبAC:Zig-zag scan ، Run-length، length/value تبدیل به Run/size/amplitudeمی شود. ترکیب Run/sizeبه روش هافمن کد می شود.
فصل هفتم
فشرده سازی ویدئو و کدینگ ویدئو
مقدمه:
ویدئو متشکل از سکانس های دارای اولویت زمانی از فریمهایی(یعنی تصاویر) هستند. یک راه حل واضح برای فشرده سازی ویدئویی ،پیشگویی مبتنی بر فریم های قبلی می باشد. فشرده سازی با کم کردن فریم از فریم قبلی وکد کردن تفاضل آنها اعمال می شود. برای بهبود فشرده سازی می توان به جای تفاضل پیکسل به پیکسل، الگوی خاصی از فریم فعلی را در فریم بعدی جستجو کنیم و آن دو را از هم کم کنیم.
شکل7-1
ساختارسلسله مراتبی ویدئو:
هر تصویر در یک ویدئو یک فریم Frame) ) نامیده می شود.طول و عرض فریم بر اساس پیکسل
CIF(352×288) is standard frame size
QCIF(176×144) is a quarter of CIF frame
GOB (Group Of Blocks):هر فریم شامل Kx16 خط می باشد. K تعداد GOB های یک فریم می باشد.
(ماکروبلاک Macro block (MB:
16×16 Luminance
8×8 U , 8×8 V
هر ماکرو بلاک شامل 6 بلاک است (4Y,1U,1V)
ساختاریک فریم QCIF که در شکل7-2 مشخص شده است:
شکل7-2
استانداردهای فشرده سازی ویدئو:
در این بخش فقط به معرفی برخی از استاندارد های فشرده سازی ویدئو که تبیین شده اند میپردازیم.
MPGE، Mpeg1 (CD)، Mpeg2 (DVD)، Mpeg4 (object bas)، Mpeg7، ITU-T، H.261، H.263، H.264
فشرده سازی ویدئویی توسط انطباق حرکتی :
فریم های متوالی در یک ویدئو ، مشابه هستند به ونه ای که افزونگی زمانی وجود دارد. از افزونگی زمانی(Temporal redundancy) استفاده می شود تا نیاز نباشد هر فریم از ویدئو بطور مستقل به عنوان یک تصویر جدید کدگذاری شود. تفاوت بین فریم فعلی و سایر فریم ها در توالی مربوطه کدگذاری خواهد شد. تعداد بیت کمتر وآنتروپی کمتربرای فشرده سازی مناسب می باشد.
مراحل فشرده سازی ویدئویی بر اساس انطباق حرکتی(MC )یا (Motion Compensation)که شامل سه مرحله می شود:
1- برآورد حرکت (جستجوی بردار حرکت).
2- پیش بینی مبتنی برMC.
3- بدست آوردن خطای پیش بینی یعنی تفاوت.
اندازه ماکروبلاک MxN
معیار تطبیق
MAE (mean absolute error)
پنجره جستجو (Search window)
±p pixel
فریم قبلی (بعدی!!) برای تخمین فریم فعلی استفاده می شود.
I(x, y, t) = I(x, y, t-1) + e(x, y, t)
محاسبه جابجایی اشیاء
I(x, y, t) = I(x+u, y+v, t-1) + e(x, y, t)
(u, v) – motion vector
تخمین حرکت
برای هر ماکروبلاک مجزا
اصتلاحات انطباق حرکتی می تواند شامل اندازه ماکرو بلاک، اندازه محدوده جستجو، در استاندارد های کدکردن ویدئو و درآن M=N=16 می باشد.که درشکل 7-3 بیشتر مشخص شده است.
شکل7-3
شکل 7-4
شکل 7-4 یک حالت انطباق حرکتی را نشان می دهد.
معیار انتخاب بهترین ماکروبلاک از تصویر مرجع
بهترین ماکروبلاک: شبیه ترین <-ماکروبلاکی که تخمین بر اساس آن کمترین کد را ایجاد کند. کد کردن ماکروبلاک به ازای تمامی مقادیر بردار حرکت (u,v) زمان زیادی لازم دارد(کند است) در عمل( mean absolute error (MAE بیشترین کاربرد را دارد.
C-فریم فعلی
R- فریم مرجع
(i,j) بردار حرکت
روشFull-Search:
بررسی تمامی ماکروبلاکهای موجود در پنجره جستجو و انتخاب بهترین آنها را شامل می شود. محاسبه MAE به ازای (2p+1)2 مقدار برای بردار حرکت (i, j) هر بردار حرکت احتیاج به 3MN عمل ریاضی دارد.اگر ابعاد تصویر IxJ باشد و تعداد F فریم در ثانیه 3IJF(2p + 1)2 عملیات در ثانیه، تضمین می کند که بهترین بلاک را پیدا کند.چگونه میزان محاسبات راکاهش داد؟ مقادیر p کوچک باشند. الگوریتم های سریعتر (با نتایج بدتر)
برنامه جستجوی ترکیبی به صورت زیز می باشد:
begin
min_MAE = LARGE NUMBER; /* Initialization */
for i = −p to p
for j = −p to p
{
cur_MAE = MAE(i, j);
if cur_MAE < min_MAE
{
min_MAE= cur_MAE;
u = i; /* Get the coordinates for MV. */
v = j;
}
}
end
جستجوی لگاریتمی دو بعدی
جستجوی لگاریتمی: مدل سریعتر و نیمه بهینه است ولی معمولا" قابل استفاده است. رویه جستجوی لگاریتمی دو بعدی شبیه جستجوی باینری است. همانطور که در شکل 2-10 نشان داده شده است در ابتدا فقط 9 مکان در پنجره جستجو به عنوان نقطه های شروع برای یک جستجوی مبتنی بر MAE استفاده می شود; آنها با "1" علامت گذاری می شوند.پس از اینکه پنجره ای که کمترین MAE را حاصل می کند شناسایی می شود مرکز منطقه جستجوی جدید به آن انتقال داده می شود و محدوده جستجو به نصف کاهش داده می شود. در تکرار بعدی 9 مکان با "2" علامتگذاری می شود و ….(به همین ترتیب).
شکل7-5
فریم فعلی و فریم مرجع را downsampled می شود
Full macroblock 16×16
Down 2 macroblock 8×8
Down 4 macroblock 4×4
بر روی فریم Down 4 ، با استفاده از روش Full search بهترین ماکروبلاک را انتخاب می شود. 16 برابر ، افزایش سرعت (ماکروبلاک های کمتر)، بردار حرکت کوچکتر p = ±16, p' = ±4 حول بهترین تطبیق ، یک جستجو در فریم Down 2 با p=1انجام می شود. این جستجو 3×3 ماکروبلاک را چک می کند. جستجو حول بهترین تطبیق در فریم اصلی نیز انجام می شود.p=1
شکل7-6
جدول زیرمقدار سرعت روشها را باهم مقایسه کرده است.
تشخیص حرکت بر اساس چندین تصویربه سه صورت زیر میباشد.که درشکل 7-7ابعاد و زوایای ان نشان داده شده است.
1. تخمین فریم بر اساس فریم قبلی و بعدی
2. شانس بیشتر برای پیدا کردن بهترین تطبیق
3. محاسبات بیشتر ، امکان فشرده سازی بیشتر
شکل 7-7
کد کردن یک فریم:
یک فریم می تواند به دو شکل کد شود:
INTRA (I mode):
Spatial redundancy، فریم می تواند بدون وابستگی به بقیه فریم ها دیکد شود. مشابه کد کردن تصویر، فشرده سازی کم و نرخ بیت بالا است.
INTER (P or B mode) :
temporal redundancy، تفاوت فریم با فریم مرجع کد می شود. فریم به تنهای قابل دیکد شدن نیست. فشرده سازی بالا ولی حساسیت به خطا بالاست.(error sensitive)
شکل 7-8
فریم های نوع P&B: فریم نوع p بر اساس فریم قبلی کد می شود. فریم قبلی به عنوان فریم مرجع می باشد. فریم نوع B بر اساس فریم قبلی یا بعدی کد می شود. ممکن است بعضی از ماکروبلاک های فریم B بر اساس فریم قبلی و بعضی بر اساس فریم بعدی کد شوند. درشکل7-8 می توان دید که فریم های نوعP&B درچه سطحی قرار دارند واختلاف بین آن دو را مشخص میکند.
شکل 7-9 دیاگرام یک کد کننده ویدئو را نشان میدهد:
شکل7-9
کد کردن فریم نوع I:
مشابه کد کردن تصویرمی باشد، مراحل کد کردن فریم نوع I به شرح زیر است. کاهش اجزاء رنگ (معمولا 4:2:0 )، تبدیل DCT را بر روی بلاک های فریم، فشرده سازی انرژی، ضرایب DCT در محدوده [-2047,2047]، کوانتایز کردن ضرایب DCT، تقسیم ضرایب به ماتریس کوانتایز، با تغییر ضریب کوانتایز ؛ می توان نرخ بیت کد کننده را تغییر داد.
کد کردن فریم های P و B: Motion estimation، برای هر ماکروبلاک بهترین تطبیق را در فریم مرجع پیدا می شود. بردار حرکت (Motion vector ) تفاوت مکان ماکروبلاک فعلی و ماکروبلاک مرجع می باشد. تفاوت دو ماکروبلاک به عنوان خطا مشابه فریم های Non-Inter کد می شود.
شکل7-10
فشرده سازی ویدئو – خلاصه: ویدئو – دنباله ای از تصاویر است. تشابه بین فریم های متوالی امکان بالقوه خوبی برای فشرده سازی است. برای استفاده از تشابه فریم های از Motion estimation و Motion compensation استفاده می شود. تشخیص و تصحیح حرکت برروی ماکروبلاک ها انجام می شود. در Motion estimation (تشخیص حرکت)بهترین بلاک در فریم مرجع از نظر تشابه (تطبیق) پیدا می شود. در Motion compensation (تصحیح حرکت) تفاوت بلاک فریم مرجع و بلاک فریم فعلی به عنوان خطا کد می شود.
استانداردH.261: H.261 : از قدیمی ترین استانداردهای فشرده سازی دیجیتالی ویدئویی می باشد ، فشرده سازی مبتنی بر MC است که در همه استانداردهای فشرده سازی ویدئویی بعدی نیز مورد استفاده قرار گرفته شده است. این استاندارد برای videophoneو video conferencing و سایر خدمات سمعی بصری از طریق ISDN طراحی شده بود. video codec از نرخهای p x 64 kbps حمایت میکند که p بین 1 تا30 می تواند باشد.(این روش به عنوان p * 64 هم معروف است ) . لازم است که تاخیر کدگذار ویدئویی کمتر از 150 میلی ثانیه باشد تا اینکه ویدئو بتواند برای video conferencing بلادرنگ دو طرفه استفاده شود.
فرمت های ویدئویی پشتیبانی شده توسط H.261در شکل 7-11 نشان داده شده است:
شکل7-11
فریمها و ترتیب آنها در H.261:
شکل7-12
فریم ها در H.261 از دلایل و علل استفاده از i-Frame ها می توان گفت، در صورت روشن کردن دستگاه پخش ویدئو، در حین پخش، امکان دیکد وجود داشته باشد. جهت اجتناب از انتشار خطاهای کدگذاری معمولا یک I-frame چندین باردر هر ثانیه از ویدئو فرستاده می شود . هنگام جلو و عقب بردن نیاز به انجام همه پردازشها نباشد. بردارهای حرکتی در H.261 همیشه در واحد پیکسل اندازه گیری می شوند و دامنه محدوده آن 15± است.
کدگذاری I-frame:
شکل 7-13
شکل 10-5 کد گذاری را I-Frameنشان می دهد. ماکروبلاک ها به اندازه پیکسل های 16×16 برای فریم y و 8×8 برای فریم های Cb and Cr هستند چون از روش4:2:0استفاده می شود. یک ماکروبلاک شامل 4 بلاک Y ، یک Cb و یک Cr است. برای هر بلاک 8×8 یک تبدیلDCT استفاده می شود. سپس ضریب های DCT کوانتیزه شده و نهایتا کد گذاری آنتروپی می شوند.
کدگذاری p-frame:
شکل 7-14 ، طرح کدگذاری p-frame ،H.261 را مبتنی بر انطباق حرکتی نشان میدهد: برای هر ماکروبلاک در فریم هدف یک بردار حرکتی توسط یکی از روش های جستجو که قبلا توضیح داده شد اختصاص داده می شود . پس از پیشگویی یک ماکروبلاک ، مقدار تفاضل محاسبه می شود از هر یک از این بلاک های 8×8 تبدیل DCT گرفته می شود ، سپس ضریب های DCT کوانتیزه شده و نهایتا کد گذاری آنتروپی می شوند. در p-frame مقدار تفاضل بین فریم و فریم بعدی کد می شود (نه خود ماکروبلاک هدف) گاهی اوقات نمی توان به انطباق مناسب دست یافت یعنی خطای پیشگویی از یک سطح قابل قبول خاص بیشتر می شود. بنابراین خود MB کدگذاری می شود( که به عنوان MB درونی در نظر گرفته می شود) و در چنین موردی یک MB منطبق شده غیر حرکتی نامیده می شود. برای یک بردار حرکتی MVD مقدار تفاضل بدست آمده برای کدگذاری آنتروپی فرستاده می شود: (3-10) MVD = MVPreceding − MVCurrent
شکل7-13
کوانتیزاسیون در H.261:
برای کوانتیزاسیون در H.261 ، برای همه ضریب های DCT در داخل یک ماکروبلاک از یک گام ثابت استفاده می کند. اگر QDCT ضرایب DCT بعد از کوانتیزه کردن باشد: برای ضریب مقدار DC از رابطه زیر:
و برای سایر ضریب ها:
Scale یک عدد صحیح در محدوده [1,31] است .
بلاک دیاگرام کد کننده در H.261:
شکل7-14
بلاک دیاگرام دیکد کننده در H.261:
شکل7-15
استاندارد H.263:
H.263 ، یک استاندارد کدگذاری ویدئویی اصلاح شده برای ویدئو کنفرانس و سایر خدمات سمعی _بصری انتقال داده شده در شبکه های تلفنی انتقال عمومی (PSTN) می باشد. هدفش ارتباط و انتقال های با میزان بیت پایین به میزانی کمتر از kbps 64 می باشد. از کدگذاری پیش گویانه برای inter-frames (p-frames) جهت کاهش افزونگی موقتی و تغییر شکل کدگذاری برای سیگنال باقیمانده استفاده میکند تا افزونگی فاصله ای (برای پیش بینیP-frames و i-frames) را کاهش دهد.
مانند H.261 در H.263 از کدگذاری طول متغیر (VLC) به عنوان روش کدگذاری پیش فرض برای ضریب های DCT استفاده می شود. همانند H.261 ترتیب H.263 بصورت سلسله مراتبی از 4 لایه ساخته شده است . هر لایه با استفاده از ترکیبی از کد طول ثابت و کد طول متغیر کدگذاری می شود.
روش پیش بینی پیشرفته:
– در این روش اندازه ماکروبلاک برای MC از 16 به 8 کاهش داده می شود .
– برای هر ماکروبلاک در تصویر مربوط به شدت روشنایی ، 4 بردار حرکتی (از هر بلاک 8×8 )ایجاد می شود.
استفاده از فریم های-PB: در H.263 ، یک فریم PB از فریم قبلی و بعدی بدست می آید.
شکل7-15
استاندارد Mpeg:
این استاندارد بر پایه استاندارد H261 بنا نهاده شده است. تفاوتهای عمده آن با H-261 عبارتند از: پشتیبانی از فرمت های بیشتر ویدئویی، ضرایب استفاده شده در کوانتیزه کردن متفاوت است، بازه جستجوی ماکروبلاک از 15 به 512 تغییر یافته است، ترتیب فریمها ارسال شده متفاوت است.
شکل 7-16 ترتیب فریمها در Mpeg-1 را نشان میدهد.
شکل7-16
1