Manuscript ID : 202005076585 Visit : 11232 Page: 15 - 26

Article Type: Original Research

A New Algorithm for Fastintra-Frame Modes Selection in H.264/Avc Video Coding

Subject Areas :

Mahnaz Nejadali ^{1
*} , mahdi jafari ² , majid mohammadi ³

1 -
2 -
3 -

Received: 2020-05-07 Accepted : 2023-02-28 Published : 2019-10-30

Keywords: Video Coding, H.264/AVC, Prediction, Intra-Frame, RDO,

Abstract :

By the increasing of video communication in portable and functional devices, encoders design with low complexity and high performance are required. H.264 / AVC standard offers higher compression efficiency than previous standards. But this standard by employing several powerful coding techniques, considerably increased complexity at the encoder. This paper presents a new algorithm to reduce the complexity of the H.264/AVC encoder. The proposed method uses simple directional masks, neighboring blocks modes and detection of 4×4 and/or 16×16 intra estimation modes with determination of quantization parameters for fast mode selection in Intra-Frame Modes prediction. Experimental results show that the proposed method reduces maximum 29% of the encoding time, while has little effect on visual quality and PSNR.

References:

1. Wiegand, T., Sullivan, G. J., Bjontegaard, G. J., Luthra, A. :‘Overview of the H.264/AVC Video Coding Standard’, IEEE Trans. On circuits and systems for video technology, 13, (7), pp. 560-576, 2003.
2. Ghanbari, M.: ‘Standard codecs: image compression to advanced video coding’, 3nd edition, The Institution of Engineering and Technology, 2011.
3. Kim, C. S., Li, Q., Kuo, C. C. J.: ‘Fast Intra-Prediction Model Selection for H.264 Codec’, SPIE International Symposium ITCOM, Orlando, Florida, pp. 99-110, 2003.
4. Pan, F., Lin, X., Rahardja, S., Lim, K. P., Li, Z. G., Wu, D., Wu, S.: ‘Fast Mode Decision Algorithm for Intra-prediction in H.264/AVC Video Coding’, IEEE Trans. On circuits and systems for video Tech., 15, (7), pp. 813-822, 2005.
5. Pan, F., Lin, X., Rahardja, S., Lim, K. P., Li, Z. G., Wu, D., Wu, S.: ‘Fast Mode Decision for Intra Prediction’, JVT-G013, 7th Meeting: Pattaya II, Thailand, 7-14 March 2003.
6. Pan, F., Lin, X., Rahardja, S., Lim, K. P., Li, Z. G.: ‘A Directional Field Based Fast Intra-Mode Decision Algorithm for H.264 Video Coding’, IEEE Inter. Conf. on Multimedia and Expo, 2, pp. 1147-1150, June 2004.
7. Ren, Z., Ye, C., Liu, M.: ‘A Fast Intra Prediction Algorithm for H.264’, IEEE Computer Society, First International Workshop on Education Technology and Computer Science, 2,(2), pp. 772 - 775, March 2009.
8. Kim, J., Jeong, J.: ‘Fast Intra-Mode Decision in H.264 Video Coding Using Simple Directional Masks’, Proc. of SPIE, 5960, pp 1071-1079, July 2005.
9. Garg, R., Jindal, M., chauhan, M.: ‘Statistics Based Fast Intra- Mode Detection’, Proc. of SPIE, 5960, pp 2085-2091, July 2005.
10. Jeon,B., Lee, J.: ‘Fast Mode Decision for H.264’, IEEE Inter. Conf. on Multimedia and Expo, 2, pp. 1131-1134, June 2004.
11. Hsu, C. L., Ho, M. H., Hong, J. J.: ‘An Efficient Algorithm for Intra-Prediction Mode Selection in H.264’, IEEE 7th International Conference, pp. 778-781, October 2007.
12. Elyousfi, A.: ‘Gravity direction-based ultra-fast intraprediction algorithm for H.264/AVC video coding’, Journal Signal, Image and Video Processing, 7,(1), pp. 53–65, 2013.
13. Wu, C. Y., Su, P. C. : ‘Fast Intra-Coding for H.264/AVC by Using Projection-Based Predicted Block Residuals’, IEEE Transactions on Multimedia , 15, (5), pp. 1083-1093, 2013.
14. Shang, J., Ding, W., Shi, Y., Sun, Y. : ‘Fast Intra Mode Decision Algorithm Based on Texture Direction Detection for H.264/AVC’, IJMECS,1, (5), pp.70-77, 2011.
15. Richardson, Iain EG: ‘H.264 and MPEG-4 Video Compression’, West Sussex: John Wiley & Sons, Ltd., ISBN 0-470-84837-5, 2003.
16. Jafari, M., Kasaei, S.: ‘Fast Intra- and Inter-Prediction Mode Decision in H.264 Advanced Video Coding’, International Journal of Computer Science and Network Security, 8, (5), pp. 130-140, 2008.
17. Pan, L. j., Ho, Y. S.: ‘A Fast Mode Decision Algorithm for H.264/AVC Intra Prediction’, IEEE Workshop in Signal Processing Systems, pp. 704-709, October 2007.
18. Muniyappa, S. k.: ‘Implementation of Complexity Reduction Algorithm for Intra Mode Selection’, Master of science Thesis, University of Texas, Arlington, December 2011.
19. Joint Video Team Reference Software JM 18.4: http://iphone.hhi.de/suehring/tml/download.

Full-Text:

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال هفتم، شماره‌هاي 25 و 26، پاییز و زمستان 1394

صص: 15- 26

$E:\E Drive\logo\iicta Logo0.JPG$

الگوریتم جدید انتخاب مُد داخل فریمی سریع در استاندارد کدگذاری ویدیویی H.264/AVC

*مهناز نژادعلی **مهدی جعفری *** مجید محمدی

* کارشناس ارشد، مهندسی برق و الکترونیک، دانشگاه آزاد اسلامی، واحد علوم و تحقيقات ** استادیار، گروه برق، دانشگاه آزاد اسلامی، دانشکده فنی، كرمان ***دانشیار، گروه برق و کامپیوتر، دانشگاه شهيد بهشتی، دانشكده مهندسی برق و كامپيوتر، تهران تاریخ دریافت:04/03/92 تاریخ پذیرش: 20/11/94

چکیده

با افزایش روزافزون ارتباطات ویدیویی در دستگاه‌های قابل‌حمل و کاربردی، طراحی کدکننده‌ها با میزان پیچیدگی کم و عملکرد بالا موردنیاز است. استاندارد‌ H.264/AVC کارایی فشرده‌سازی بالاتري را نسبت به استانداردهاي قبلي ارائه مي دهد. اما این استاندارد با بکارگیری چندین تکنیک کدگذاری قدرتمند، پیچیدگی کدگذار را بطور قابل ملاحظهای افزایش میدهد. این مقاله الگوریتم جدیدی برای کاهش پیچیدگی کدگذار H.264/AVC ارائه میدهد. روش پیشنهادی از ماسکهای جهتدار ساده، مُد بلوکهای همسایه و تشخیص مُد تخمین داخلی 4×4 و/يا16×16 با تعيين پارامترهاي كوانتيزه به منظور انتخاب سریع مُد در پیش‌بینی به روش داخلفریمی استفاده میکند. نتایج شبیه‌سازی نشان می‌دهد که روش پیشنهادی زمان کدگذاری را ماکزیمم 29% درصد کاهش می‌دهد در حالی که تاثیر ناچیزی در کیفیت تصویر و میزان PSNR دارد.

واژههای کلیدی: کدگذاری ویدیو،H.264/AVC ، پیشبینی، داخلفریمی،RDO

1- مقدمه

از آنجائیکه کاربردهای جدید چندرسانه‌ای (استفاده از انواع مختلف شبکه‌ها) به سرعت در حال رشد میباشد، کدگذاری ویدیو به کارایی بیشتر و ویژگی‌های تازه نیازمند است. استاندارد کدگذاری ویدیو H.264/AVC در سال 2003 و به طور مشترک توسط تیم‌های ویدیویی ISO/IEC MPEG و ITU_T VCEG تحت عنوان استاندارد بینالمللی کدگذاری ویـدئو پیشـرفته با نـام 14496-10 ( MPEG-4 part 10یا H.264/AVC) ارائه شده است [1].

نویسنده عهددار مکاتبات: مهناز نژادعلی m.nejadali@gmail.com

استاندارد H.264/AVC می‌تواند کیفیت تصویر خوبی را در نرخ داده‌ای که اساسا پایین‌تر از آنچه استانداردهای قبلی ارائه دادند بدون پیچیده و گران کردن سیستم فراهم آورد. این استاندارد داراي کارائي بسيار بالاتري نسبت به استانداردهاي پيشين مي‌باشد و به دلايل افزایش بازده فشردهسازی(نرخ بيت متوسط آن تا 50% نسبت بهH.263 , MPEG-4و MPEG-2 صرفه‌جويي مي‌كند)‌، سازگاری با محدودیت تاخیر زمانی, مقاومت در مقابل خطا و آساني کارکرد

شکل1- مقایسه کدکهای H.263 , MPEG-4و MPEG-2 با [2]H.264

در انواع مختلف شبكهها، توجه زيادي را به خود جلب كرده است. شکل (1) کیفیت این کدکننده را در مقایسه با سایر کدکها و در نرخ بیتهای مختلف نشان میدهد. در این استاندارد مزایای روش‌های مختلف استانداردهای کدگذاری قبلی بکار گرفته شده و در یک پروسه با هم ترکیب شده‌اند؛ پیش‌بینی داخل و بین‌فریمی، تبدیل با عنصرهای اعداد صحیح، کدگذاری طول-صفر و کدگذاری آنتروپی منجر به کاهش افزونگی مکانی، زمانی و آماری در این استاندارد گردیده است[2].

از عواملی که کدک H.264 را از استانداردهای قبلی متمایز ساخته جبران حرکت در ماکروبلوک‌های 16´16 پیکسلی با ابعاد مختلف است و این استاندارد برای کدگذاری بیشترین استفاده را از مُد تخمین/جبران حرکت یا پیش‌بینی بین‌فریمی می‌برد. دقت جبران حرکت در این استاندارد در حالت عادی یک چهارم پیکسل است و می‌تواند تا یک هشتم پیکسل با پیچیدگی بیشتر افزایش یابد. کدگذار H.264 از بلوک‌های با سایز کوچک‌تر برای بخش‌های متحرک تصویر و از بلوک‌های با سایز بزرگ‌تر برای پس زمینه‌ها استفاده می‌کند تا کارآیی کدینگ و کیفیت را همزمان بالا ببرد.

اما گاهي بهتر است يک ماکروبلوک به جاي مُد بين فريمي به صورت داخل فريمي کدگذاري شود. براي اين کار واريانس خود بلوک را با وريانس تفاوت آن با فريم قبلي مقايسه کرده و کمترين انرژي را مبنا قرار ميدهيم. براي انرژي هاي زياد(واريانس بالا) تفاوتي در انتخاب مُد داخل/بين فريمي وجود نداشته ولي در انرژي هاي کم نوع بين فريمي ترجيح داده مي شود. لذا در تصاوير ويديويي که در اثر تغيير صحنه و يا حرکت هاي سريع تفاوت بين فريمها از اطلاعات داخل يک فريم بيشتر است روش داخل فريمي ترجيح داده ميشود و تعداد بيت کمتري ايجاد ميکند. همچنين ماکروبلوکهايي که به صورت داخل فريمي کدگذاري مي شوند در مقابل خطاي کانال مقاومتر هستند و مصونيت را در مقابل خطاي کانال افزايش ميدهند[2].

پيشگويي داخل فريمي از مهمترين عوامل برتري تكنيك كدينگ H.264/AVC نسبت به ديگرروشهاي فشرده سازي استاندارد است که از تشابهات مکانی جهتدار برای کاهش افزونگی استفاده میکند. تکنیک بهینه‌سازی نرخ اعوجاج(RDO) در این استاندارد برای انتخاب بهترین مُد پیش‌بینی داخل‌فریمی و دستیابی به بهترین مُد کدکردن و بالاترین بازدهی بکار گرفته میشود[1]. کدگذار در کدکردن بلوک موردنظر، برای یافتن بهترین حالت نرخ اعوجاج(RD)، باید همه مُدهای ممکن برای کدینگ داخلی را تست کند و ارزشهای RD آنها را محاسبه نماید تا مُدی که کمترین اعوجاج را ایجاد کند، برگزیند. اما تعیین مقادیر ارزش RD برای نمونه هاي روشنایی(LUMA) و رنگ (CHROMA) در یک ماکروبلوک، نیازمند محاسبات بسیار بوده و منجر به افزایش پیچیدگی میگردد[3] كه كاركرد اين استاندارد را برای کاربردهای بلادرنگ با مشكل مواجه میكند.

تلاش‌های زیادی برای توسعه الگوریتم‌های پیش‌بینی داخل‌فریمی سریع و کاهش زمان کدگذاری در این استاندارد انجام شده است. پان و همکاران 6]، 5، [4الگوریتم‌های برآورد مُد داخلی با استفاده از نمودار ستونی(هیستوگرام) آشکارسازی لبه و شناسایی لبه محلی با روش پیش‌پردازش را پیشنهاد کردند، که‌ در آن اندازه‌گیری جهت لبه بلوک به منظور کاهش تعداد مُد‌های احتمالی و کاهش پیچیدگی انجام می‌گیرد. هرچند این روش برای آشکارسازی راستای لبه و دستهبندی در یک راستای محدود، نیازمند عملیات اضافی بوده که باعث اتلاف زمان کدگذاری می‌گردد. یک الگوریتم تصمیم‌گیری مُد داخلي سریع برای پیش‌بینی داخلی H.264 در مرجع [7] ارائه شده است. این الگوریتم با استفاده از ویژگی‌های ماکروبلوک و تخمین یکنواختی و همگن بودن آن یکی از مُدهای 4´4و 16´16 را برای تعیین بهترین مُد پیش‌بینی برمیگزیند. این الگوریتم 30 تا 60 درصد محاسبات را کاهش داده در حالیکه عملکرد PSNR و نرخ بیت با استاندارد H.264 یکسان میباشد. الگوریتم‌ سریعی برای انتخاب مد پیشبيني داخلی بهینه با بکار بردن ماسک‌های ساده جهت‌دار و اطلاعات مد بلوک همسایه، در مرجع [8] وجود دارد که تا70% زمان کدگذاری را کاهش میدهد. روشی مبتني بر خصوصيات آماري برای پیشبینی مُد داخلی روشنایی در مرجع [9] ارائه شده است که 45% در زمان كدگذاري صرفه جویی میکند. مرجع [10] با پیشنهاد دو تکنیک "تصمیم مُد پرش زودهنگام" و "تصمیم مُد داخلی انتخابی" پیچیدگی کدگذاری را کاهش داده و سرعت کدگذاری را به طور متوسط 30% بهبود میبخشد. در مرجع [11]، یک الگوریتم سریع بر پایه انتخاب نوع بلوک و اطلاعات لبه محلی که از محاسبه پارامترهای ویژگی لبه و تكنیكهای نمونهبرداری از عملیات انطباقی بدست میآید، معرفی شده است. این روش با افت بسيار كمي در مقدار PSNR، زمان کدگذاری را بیش از 71% کاهش میدهد. روشي مبتني بر بردار مركز ثقل بلوك در مرجع [12] پيشنهاد شده است كه جهت اين بردار براي انتخاب جهت پيشبيني داخلي استفاده ميشود. اين الگوريتم با اتخاذ روشي هوشمند تعداد مُدهاي كمتري كه در محاسبات RD موردنياز است بر ميگزيند و فقط با محاسبه مقدار زاويه مركز ثقل بهترين مُد پيشبيني داخل فريمي را انتخاب ميكند. مرجع [13] تكنيك انتخاب مُد پیش‌بینی داخل‌فریمی را ارائه مي كند كه در آن محتواي بلوك و پيكسلهاي كناري بازسازي شده به منظور تسهيل روند كدگذاري بكار برده میشود. اين روش میتواند به طور موثر مُدهاي با احتمال پايين در محاسبات نرخ اعوجاج(RD) را حذف نمايد. طرح تصميم گيري مُد داخلي سريع مبتني بر جهت بافت و زمينه تصوير در [14] ارائه شده است كه تنها زير مجموعه اي از مُدهاي داخلي را مطابق با جهت بافت تصوير شناسايي شده، تست مینمايد و میتواند تا60% زمان کدگذاری را کاهش دهد.

در این مقاله الگوریتم سادهای برای انتخاب مُد پیشبینی داخلفریمی 4´4 در نظر گرفته شده است. این الگوریتم با استفاده از ماسکهای جهتدار و مُد بلوکهای همسایه، بهترین مُد کاندید برای تخمین بلوک فعلی را بدست میآورد. با این روش میتوان تعداد مُدهای RD در بلوکهای 4´4 را از 9 مُد، در بدترین شرایط به 4 مُد و در بهترین شرایط به یک مُد کاندید کاهش داد. نتایج شبیهسازی نشان میدهد که این روش میتواند به میزان قابل توجهی زمان کدگذاری را کاهش دهد.

ادامه این مقاله بصورت زیر تنظیم گردیده است: در بخش 2 پیشبینی داخلفریمی استاندارد H.264/AVC را بازبینی می‌کنیم. در بخش 3 الگوریتم جدید مُد داخل فریمی سریع پیشنهادی مبتنی بر ماسکهای جهتدار، مُد بلوکهای همسایه و تشخیص مُد تخمین داخلی 4×4 و/يا16×16 با تعيين پارامترهاي كوانتيزه معرفی میگردد. نتایج شبیهسازی روش پیشنهادی در بخش 4 ارائه میشود و در نهایت نتیجهگیری و پيشنهادات در بخش 5 آورده شده است.

2- پیشبینی داخلفریمی در استاندارد H.264/AVC

از آنجائيكه در یک فریم تصویر ميزان افزونگي بالاست، مُد داخل فریمی در كاهش بيتهاي افزونگي موردنياز است در واقع پیشبینی داخلفریمی براي كاهش افزونگي مکانی در تصویر بکار برده میشود. در اين روش ماکروبلوک فعلی از پیکسلهای مجاور، ماکروبلوکهای بالا و/يا چپ در انتخاب مُد تخمین و افزایش بازده کدگذاری استفاده میکند. تفاوت بین ماکروبلوک اصلی و ماکروبلوک کدگشایی شده توسط بهترین مُد تخمین کدگذاری میشود. لذا تعداد بیتهای موردنیاز در کدگذاری نسبت به حالتی که تبدیل روی ماکروبلوک اصلی انجام گردد به مراتب پایینتر خواهد بود. مجموعه حالتهای كدگذاري برای اطلاعات روشنایی در روش داخلفریمی، 4´4 و 16´16 و در تخمین رنگ، 8´8 میباشد. استاندارد اصلی H.264 هشت جهت تخمین به اضافه یک مُد DC(مُد 2) را برای کدگذاری داخل فریمی بلوک‌های روشنایی4×4 استفاده می‌کند. جهت‌های تخمین همراه با بلوک 4´4 و پیکسل‌های مجاور آن در شکل (2) نشان داده شده‌اند. جهت پیکان‌ها در این شکل جهت تخمین برای کدگذاری بلوک 4´4 را نشان می‌دهند. در قسمت‌هایی از تصویر که جزئیات زیادی وجود ندارد(نواحي صاف تصوير)، لزومی ندارد که از 9 مُد تخمین استفاده شود زیرا تعداد مُدهاي تخمین تاثیری در بازده کدگذاري ندارد و فقط اطلاعات سربار برای مشخص کردن جهت تخمین را بالا می‌برد. از این رو در این قسمت‌های تصویر در استاندارد H.264، کل ماکروبلوک (16×16) از 4 نوع تخمین که عبارت‌اند از DC، افقی، عمودی و صاف استفاده میکند. در این استاندارد برای تخمین بلوک‌های رنگ، از تکنیک مشابه 16´16 و با 4 تخمین برای دو بلوک رنگ پیشنهاد ميگردد.

شکل2- (a)بلوک 4´4 و پیکسلهای مجاور (b) نه مُد تخمین در بلوک 4´4 روشنایی[15]

شکل3- تعداد ماکروبلوکهای کدشده داخلی 4×4 و

16×16 در پارامترهای کوانتیزه مختلف[16]

برای انتخاب بهترین مُد تخمین از میان مُدهای فوق این استاندارد از تکنیک RDO استفاده میکند و مُدی با کمترین ارزش RD بهعنوان بهترین مُد برگزیده میشود. روش RDO مبتنی بر تابع لاگرانژ بوده و دادوستدی بین نرخبیت و اعوجاج در آن مطرح میباشد. ارزش RD برای تعیین بهترین مُد تخمین داخل فریمی از معادله (1) بدست میآید:

(1)

J = D+lR

که در آنD اعوجاج، R نرخ بیت و l ضریب لاگرانژین میباشد و از رابطه (2) محاسبه میگردد:

(2)	l = 0.85´2(QP-12)/3

l کوچکتر بهمعنای اعوجاج کمتر و نرخ بیت بیشتر و l بزرگتر به معنای اعوجاج بیشتر و نرخبیت کمتر است. R تعداد بیت مربوط به هر مُد و D از مجموع اختلاف مربعات بین بلوک اصلی و بلوک بازسازی شده محاسبه میگردد.

بنابراین تعداد ترکیبات ممکن انتخاب مُد برای اجزای روشنایی و رنگ در یک ماکروبلوک 592=(4+16´9)´4N8´(N4´16+N16)= خواهد بود که N8،N4 و N16 به ترتیب تعداد مُدهای تخمین 8´8 رنگ، 4´4 و 16´16 روشنایی میباشند. بنابراین برای انتخاب بهترین مُد تخمین در مُد داخلفریمی در یک ماکروبلوک نیاز به 592 محاسبه RDO در کدگذار H.264 خواهد بود که بهشدت پیچیدگی کدگذار را افزایش میدهد.

3- الگوریتم تصمیم مُد داخلی سریع

در تخمین نمونههای روشنایی در مُد داخلی و پارامترهای کوانتیزه معمول(35~20)، احتمال سایز بلوک 4×4 بیشتر از سایز بلوک 16×16 میباشد؛ همانطور که در شکل(3) نشان داده شده است. بنابراین در این مقاله با تشخیص سریع مُد تخمین داخلی 4×4 در QP های پایین و 16×16 در QPهای بالا بطور قابل ملاحظهای سرعت کدگذاری افزایش مییابد[16].

3-1- تصمیم مُد داخلی در بلوکهای4×4

استاندارد H.264/AVC در تخمین داخلی بلوکهای 4´4 روشنایی، 9 مُد تخمین بصورت نشان داده در شکل(2) را بکار میبرد. در نرمافزار مرجع، پیکسلها در جهت تخمین یکسان مقادیر یکسانی دارند؛ برای مثال در مُد 0 (مُد عمودی) همه پیکسلهای تخمین زده شده برای موقعیتهای a، e، i و m باید دارای مقادیر یکسان و مساوی با مقدار پیکسل A طبق شکل (2)باشند. پس از محاسبات RDO اگر مُد 0 به عنوان بهترین مُد پیشبینی برگزیده شود، در آنصورت مقادیر پیکسلهای تخمین زده شده در امتداد جهت عمودی یکسان بوده و این در اصل نشاندهنده آنست که در بلوک اصلی، مقادیر پیکسلها در این موقعیتها بسیار شبیه به هم هستند. بنابراین در این مقاله روش تخمین بهترین مُد کاندید بر اساس محاسبات NSAD یا مجموع نرمال شده قدرمطلق تفاوتها (Normalized Sum of Absolute Differences) با انتخاب موقعیت برخی پیکسلها در بلوک اصلی طبق كد نوشته شده زير میباشد.

NSAD 0=(abs(a-m)+abs(b-n)+abs(c-o)+abs(d-p))>> 2;

NSAD 1 =(abs(a-d)+abs(e-h)+abs(i-l)+abs(m-p))>> 2;

NSAD 3 = (abs(b-e) + abs(d-m) + abs(l-o))/3;

NSAD 4 = (abs(a-p) + abs(i-n) + abs(c-h))/3;

NSAD 5 = (abs(a-j) + abs(b-k) + abs(c-l))/3;

NSAD 6 = (abs(a-g) + abs(e-k) + abs(i-o))/3;

NSAD 7 = (abs(b-i) + abs(c-j) + abs(d-k))/3;

NSAD 8 = (abs(e-c) + abs(i-g) + abs(m-k))/3;

چون مُد DC)2) از میانگین مقادیر پیکسلهای A تا M تخمین زده میشود و بدون جهت میباشد رابطه (3) برای تخمین مُدDC در نظر گرفته شده و باDDC نشان داده میشود.

(3)	DDC = Si=015\|m-pi\|

هر پیکسل در بلوک فعلی با Pi نشان داده می شود و m از رابطه (4) محاسبه میگردد.

(4)	m = (Si=015pi+8)>> 4

مُدهای محتمل دیگر میتواند از بلوکهای چپ و بالایی بدست آید؛ شکل (4) بلوكهای مجاور بلوک فعلی را نشان میدهد[17].

شکل4- بلوکهای مجاور بلوک فعلی[17]

با آزمون روی فریمهای ویدیویی مختلف و با ساختار گوناگون مشاهده شد که احتمال آنکه) مُد فعلی= مُد U= مُد L) باشد 62/40% است و احتمال آنکه (مُد فعلی= مُد U) یا (مُد فعلی= مُد L) باشد 86/80% است. اما وقتی (مُد U = مُد L) است احتمال آنکه مُد فعلی برابر آنها باشد 5/87% است. بنابراین بررسی مُدهای بلوکهای مجاورU و L میتواند برای پیشتخمین بهترین مُد کاندید كه با C نشانهگذاری شده استفاده گردد. لذا وقتی (مُد U = مُد L) است، تنها مُد کاندید C كه برابر مُد بلوكهاي مجاور Uو L ميباشد بررسي ميگردد؛ در اين شرایط تعداد مُدهای RD در بلوکهای 4´4 از 9 مُد، به یک مُد کاندید کاهش مييابد[17]. در غير اينصورت الگوریتم انتخاب مُد داخلی پیشنهادی برای بلوکهای روشنایی بهصورت زیر خلاصه میشود:

مرحله 1: برای بلوک 4´4 روشنایی، DDCاز رابطه(3) محاسبه گردد.

مرحله2-1: اگر DDC بزرگتر از آستانهT1(با مقدار32) است، روش RDO در نهایت برای 4 مُد کاندید بررسی شود. دو مُد از کمترین مقدار محاسبه شده NSAD ( C بهترین مُد کاندید با كمترين مقدار NSAD و S با دومين كمترين مقدار NSAD به عنوان دومين مُد كانديد) و دو مُد از بلوکهای مجاور و درصورتیکه بلوکهای مجاور شامل مُد DC باشند در محاسبهRDO مُد DC در نظر گرفته نمیشود(بدليل آنكه DDC بزرگتر از آستانه T1است) [18].

مرحله2-2: اگر DDC کوچکتر از آستانه T1 باشد، آنگاه روش RDO در نهایت شامل 4 مُد کاندید است.

یک مُد با کمترین مقدار محاسبه شده NSAD، دو مُد از بلوکهای مجاور و مُد [18] DC.

3-2- تصمیم مُد داخلی در بلوکهای16×16 روشنایی و بلوکهای 8´8 رنگ

در اين مقاله محاسبات RDO و انتخاب مُد داخلی در بلوکهای 16×16 روشنایی و بلوکهای 8×8 رنگ، همان روش بكار برده شده در نرم افزار مرجع JM 18.4 میباشد.

4- نتایج شبیهسازی روش پیشنهادی

الگوریتم پیشنهادی در JM18.4 كه توسط JVT ارائه گردید پیادهسازی شد [19]. آزمایش روی فریمهای ویدیویی Mobile،Forman ،Silent ،Coastguard ، Bus و Tempete با ابعاد CIFو QCIF انجام گردید و شبیهسازی با پارامترهای کوانیزه 16،28،32،44 و بر روی فریمهای نوعI ( تعداد 100 فريم در تصاوير ويديويي QCIF و 30 فریم در تصاويرCIF) انجام شد. سختافزار استفاده شده در شبیهسازی روش پیشنهادی، کامپیوترIntel Core i3 CPU با حافظه 2GB وسرعت2.13 GHz و ویندوز 7 میباشد.

برای سنجش كارایی، تفاوتPSNR((DPSNR، نرخبیت(DBR) و درصد زمان صرفهجویی روش پیشنهادی در مقایسه با نرمافزار مرجعJM 18.4 توسط روابط (5)،( 6) و (7) محاسبه میگردد.

(5)	DPSNR = PSNRProposed - PSNRRef.
(6)	DBR =
(7)	DTime =

جداول 1و 2 نتایج شبیهسازی تصاویرQCIFو CIF را در QPهای مختلف نشان میدهد. نتایج حاکی از آن است که ماکزیمم زمان کدگذاری کاهش یافته به میزان28/29% میباشد درحالی که افت کیفیت تصویر و افزایش نرخبیت بسیار ناچیز است.

جدول1- نتايج شبيهسازی در تصاوير QCIF برایQPهای متفاوت

DTime(%)	DBR(%)	DPSNR(dB)	Sequence	QP
-23.7402	0.007	-0.013	Coastguard	16
-28.7519	0.047	-0.016	foreman
-29.2775	0.004	-0.021	Mobile
-26.3554	0.0012	-0.016	Silent
-27.0942	0.011	-0.023	Coastguard	28
-28.0496	0.041	-0.025	foreman
-24.6228	0.016	-0.015	Mobile
-29.1798	0.005	-0.01	Silent
-25.3247	0.028	-0.031	Coastguard	32
-26.1614	0.046	-0.035	foreman
-28.0129	0.002	-0.012	Mobile
-29.5139	0.05	-0.026	Silent
-25.9205	0.035	0.046	Coastguard	44
-22.1993	0.0294	-0.014	foreman
-23.6253	0.037	-0.023	Mobile
-25.2765	0.025	-0.038	Silent

جدول2- نتايج شبيهسازی در تصاوير CIF برایQPهای متفاوت

DTime(%)	DBR(%)	DPSNR(dB)	Sequence	QP
-21.2321	0.005	-0.01	Bus	16
-21.4380	0.012	-0.023	Coastguard
-23.2457	0.017	-0.013	Mobile
-23.9489	0.013	-0.01	Tempete
-21.2302	0.023	-0.017	Bus	28
-24.6460	0.032	-0.012	Coastguard
-21.8864	0.072	-0.015	Mobile
-22.7450	0.032	-0.012	Tempete
-25.9081	0.039	-0.019	Bus	32
-22.5709	0.028	-0.032	Coastguard
-22.1182	0.027	-0.02	Mobile
-28.4581	0.032	-0.021	Tempete
-27.4132	0025	-0.05	Bus	44
-23.9026	0.029	-0.052	Coastguard
-23.3868	0.032	-0.044	Mobile
-22.5405	0.015	-0.012	Tempete

جدول3- مقايسه زمان كدگذاری روش پيشنهادی با نرمافزار مرجع در QP=28 در تصاویر نوعQCIF

جدول4- مقايسه زمان كدگذاری روش پيشنهادی با نرمافزار مرجع در QP=28 در تصاویر نوع CIF

جدول5- مقایسه PSNR

		DPSNR
		QP=32
FOREMAN	M1(Pan’s Method [16])	-0.063
	M2 (Improved Pan’s Method[16])	-0.001
	M3(new proposed Method[16])	-0.05
	Proposed Method	-0.035
SILENT	M1(Pan’s Method [16])	-0.041
	M2 (Improved Pan’s Method[16])	-0.023
	M3(new proposed Method[16])	-0.032
	Proposed Method	-0.026

جداول 3و4 مقایسه از زمان کدگذاری روش پیشنهادی و نرافزارمرجعJM18.4 را نشان میدهد. متوسط کاهش پیچدگی کدگذار در تصاوير ويديويي QCIF برابر 5/22% و در تصاویر از نوع CIF برابر 6/26% است.

جداول 5، 6 و 7 نتایج مقایسه با سایر الگوریتمهای ارائه شده در [16] را نشان می‌دهد. در روش پیشنهادی کاهش پیچیدگی محاسباتی با تاثیر ناچیز در کیفیت تصویر و میزان PSNR بدست آمده است.

جداول 8 و 9 نتایج مقایسه با الگوریتم ارائه شده در [14] را در ويديويي QCIF و CIF نشان می‌دهد. در روش پیشنهادی کاهش زمان كدگذاري با تاثیر ناچیز در ميزان نرخ بيت و PSNR بدست آمده است.

جدول6- مقایسه نرخ بیت

		DBR%
		QP=32
FOREMAN	M1(Pan’s Method [16])	1.142
	M2 (Improved Pan’s Method[16])	0.997
	M3(new proposed Method of[16])	0.887
	Proposed Method	0.046
SILENT	M1(Pan’s Method [16])	0.905
	M2 (Improved Pan’s Method[16])	0.590
	M3(new proposed Method of[16])	0.435
	Proposed Method	0.05

جدول7- مقایسه پیچیدگی

		DTime%
		QP=32
FOREMAN	M1(Pan’s Method [16])	-49.10
	M2 (Improved Pan’s Method[16])	-54.20
	M3(new proposed Method of[16])	-42.82
	Proposed Method	-26.1614
SILENT	M1(Pan’s Method [16])	-45.38
	M2 (Improved Pan’s Method[16])	-49.62
	M3(new proposed Method of[16])	-49.38
	Proposed Method	-29.5139

جدول8- مقایسه روش پيشنهادي و مرجع [14] در تصاوير QCIF

QP=32	QP= 28		Sequence	الگوريتم
-61	-62.73	ΔT (%)	coastguard	[14]
-0.03	-0.029	ΔPSNR (dB)
0.94	0.59	ΔBit-rate (%)
-25.3	-27.09	ΔT (%)		روش پيشنهادي
-0.03	-0.023	ΔPSNR (dB)
0.028	0.011	ΔBit-rate (%)

جدول9- مقایسه روش پيشنهادي و مرجع [14] در تصاوير CIF

QP=32	QP= 28		Sequence	الگوريتم
-62.3	-63.81	ΔT (%)	bus	[14]
-0.05	-0.063	ΔPSNR (dB)
1.56	1.23	ΔBit-rate (%)
-61.5	-62.23	ΔT (%)	mobile
-0.06	-0.065	ΔPSNR (dB)
1	0.75	ΔBit-rate (%)
-60.5	-61.72	ΔT (%)	tempete
-0.05	-0.065	ΔPSNR (dB)
1.79	1.21	ΔBit-rate (%)
-25.9	-21.23	ΔT (%)	bus	روش پيشنهادي
-0.02	-0.017	ΔPSNR (dB)
0.039	0.023	ΔBit-rate (%)
-22.1	-21.89	ΔT (%)	mobile
-0.02	-0.015	ΔPSNR (dB)
0.027	0.072	ΔBit-rate (%)
-28.5	-22.75	ΔT (%)	tempete
-0.02	-0.012	ΔPSNR (dB)
0.032	0.032	ΔBit-rate (%)

5- نتیجهگیری و پيشنهادات

از نتایج شبیهسازی در بخش 4 میتوان نتیجه گرفت که الگوریتم پیشنهادی سریعتر از نرمافزار استاندارد JM18.4 است. به این دلیل که نرمافزار مرجع برای محاسبات RDO همه مُدهای ممکن کدگذاری را بررسی کرده درحالیکه با الگوریتم پیشنهادی تعداد مُدهای ممکن جهت بررسی کاهش داده شد و با تشخیص سریع مُد تخمین داخلی 4×4 در QP های پایین و 16×16 در QPهای بالا بطور قابل ملاحظهای سرعت کدگذاری افزایش يافت.

نتایج نشان داد که این روش میتواند به کاهش زمان محاسباتی تا ماکزیمم 28/29% با کاهش ناچیز در PSNR و افزایش نرخ بیت دست یابد. الگوريتم پيشنهادي در این مقاله تركيب روشهاي تصمیم مُد داخلی سریع روي بلوكهاي 4×4 و 16´16 با استفاده از پارامترهای کوانتیزه و استفاده از ماسکهای جهتدار ساده و مُد بلوکهای همسایه در بلوک 4´4 ميباشد که میتواند به بلوکهای 16´16 نیز بسط داده شود. در این مقاله شبیهسازی بر روی تصاویر ويديويي QCIF و CIF پیادهسازی شد و میتواند در سایر فرمتهای ویدیویی چون HDنیز ادامه یابد.

منابع

1. Wiegand, T., Sullivan, G. J., Bjontegaard, G. J., Luthra, A. :‘Overview of the H.264/AVC Video Coding Standard’, IEEE Trans. On circuits and systems for video technology, 13, (7), pp. 560-576, 2003.

2. Ghanbari, M.: ‘Standard codecs: image compression to advanced video coding’, 3nd edition, The Institution of Engineering and Technology, 2011.

3. Kim, C. S., Li, Q., Kuo, C. C. J.: ‘Fast Intra-Prediction Model Selection for H.264 Codec’, SPIE International Symposium ITCOM, Orlando, Florida, pp. 99-110, 2003.

4. Pan, F., Lin, X., Rahardja, S., Lim, K. P., Li, Z. G., Wu, D., Wu, S.: ‘Fast Mode Decision Algorithm for Intra-prediction in H.264/AVC Video Coding’, IEEE Trans. On circuits and systems for video Tech., 15, (7), pp. 813-822, 2005.

5. Pan, F., Lin, X., Rahardja, S., Lim, K. P., Li, Z. G., Wu, D., Wu, S.: ‘Fast Mode Decision for Intra Prediction’, JVT-G013, 7th Meeting: Pattaya II, Thailand, 7-14 March 2003.

6. Pan, F., Lin, X., Rahardja, S., Lim, K. P., Li, Z. G.: ‘A Directional Field Based Fast Intra-Mode Decision Algorithm for H.264 Video Coding’, IEEE Inter. Conf. on Multimedia and Expo, 2, pp. 1147-1150, June 2004.

7. Ren, Z., Ye, C., Liu, M.: ‘A Fast Intra Prediction Algorithm for H.264’, IEEE Computer Society, First International Workshop on Education Technology and Computer Science, 2,(2), pp. 772 - 775, March 2009.

8. Kim, J., Jeong, J.: ‘Fast Intra-Mode Decision in H.264 Video Coding Using Simple Directional Masks’, Proc. of SPIE, 5960, pp 1071-1079, July 2005.

9. Garg, R., Jindal, M., chauhan, M.: ‘Statistics Based Fast Intra- Mode Detection’, Proc. of SPIE, 5960, pp 2085-2091, July 2005.

10. Jeon,B., Lee, J.: ‘Fast Mode Decision for H.264’, IEEE Inter. Conf. on Multimedia and Expo, 2, pp. 1131-1134, June 2004.

11. Hsu, C. L., Ho, M. H., Hong, J. J.: ‘An Efficient Algorithm for Intra-Prediction Mode Selection in H.264’, IEEE 7th International Conference, pp. 778-781, October 2007.

12. Elyousfi, A.: ‘Gravity direction-based ultra-fast intraprediction algorithm for H.264/AVC video coding’, Journal Signal, Image and Video Processing, 7,(1), pp. 53–65, 2013.

13. Wu, C. Y., Su, P. C. : ‘Fast Intra-Coding for H.264/AVC by Using Projection-Based Predicted Block Residuals’, IEEE Transactions on Multimedia , 15, (5), pp. 1083-1093, 2013.

14. Shang, J., Ding, W., Shi, Y., Sun, Y. : ‘Fast Intra Mode Decision Algorithm Based on Texture Direction Detection for H.264/AVC’, IJMECS,1, (5), pp.70-77, 2011.

15. Richardson, Iain EG: ‘H.264 and MPEG-4 Video Compression’, West Sussex: John Wiley & Sons, Ltd., ISBN 0-470-84837-5, 2003.

16. Jafari, M., Kasaei, S.: ‘Fast Intra- and Inter-Prediction Mode Decision in H.264 Advanced Video Coding’, International Journal of Computer Science and Network Security, 8, (5), pp. 130-140, 2008.

17. Pan, L. j., Ho, Y. S.: ‘A Fast Mode Decision Algorithm for H.264/AVC Intra Prediction’, IEEE Workshop in Signal Processing Systems, pp. 704-709, October 2007.

18. Muniyappa, S. k.: ‘Implementation of Complexity Reduction Algorithm for Intra Mode Selection’, Master of science Thesis, University of Texas, Arlington, December 2011.

19. Joint Video Team Reference Software JM 18.4: http://iphone.hhi.de/suehring/tml/download.

Share To

Article Url

A New Algorithm for Fastintra-Frame Modes Selection in H.264/Avc Video Coding