بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
فشرده سازي با اتلاف و بدون اتلاف تصاوير بر اساس جداسازي ارقام با ارزش و کم ارزش مقادير
پيکسل ها در حوزه ي فضايي
خلاصه :
در اين مقاله يک روش پايه جهت فشرده سازي تصاوير ٢٤ بيتي با عنوان ”IRN” در دو حالت فشرده سازي "با اتلاف " و "بدون اتلاف "ارايه مي شود. براي فشرده سازي ارقام کم ارزش پيکسلها، يک روش پيشنهادي به نام MIA ارايه شده ، که از آن در الگوريتم IRNاستفاده شده است . همچنين ارقام با ارزش نيز به علت يکنواختي مقادير و افزايش يافتن فراواني داده هايشان با الگوريتمهايي فشرده و نگهداري مي شوند که اولا از فراواني داده ها و ثانيا از الگوريتم کد گذاري با طول متغير در جهت فشرده سازي خود استفاده مي کنند.
در حالت فشرده سازي با اتلاف ، ميزان فشرده سازي بدست آمده در اين قسمت با ٣٨ درصد فشرده سازي قسمت قبل ، مجموع فشردگي تصوير را در بيشترين حالت ممکن تشکيل مي دهند. نتايج پياده سازي اين روش در حالت "بدون اتلاف "، نشان دهنده ي فشردگي بيشتر تصاوير نه چندان بزرگ نسبت به فرمت هاي tiff, png, bmp مي باشد، همچنين با بررسي و پياده سازي الگوريتم پيشنهادي مشخص گرديد که اين الگوريتم بهتر از فرمت هاي png و tif توسط نرم افزارهاي zip مانند winzip وwinrar ، فشرده مي شود.
کلمات کليدي: فشرده سازي تصاوير، جداسازي ارقام در پيکسلها
١. مقدمه :
تا کنون روش هاي زيادي جهت فشرده سازي تصوير ارايه شده است که در سالهاي اخير روشهايي مبتني بر شبکه هاي عصبي، تبديلات فرکانسي در پردازش تصوير و همچنين هندسه ي فراکتالي بيشتر مورد توجه بوده اند، از جمله مقالاتي که در اين حوزه ها انتشار يافته است مي توان به روشهاي پايه اي چون روش Huffman، -که همواره در تلفيق با روشهاي گوناگون استفاده گرديده است -[١,٢]، مقالاتي چون فشرده سازي تصوير به روش [٣]LZ٧٧، آناليز اجزا اصلي(pca)[٤]، فشرده سازي تصوير توسط شبکه هاي عصبي [٥] و فشرده سازي فراکتالي تصوير [٦]، اشاره کرد. همچنين قابل ذکر است روش پيشنهادي اين مقاله بر اساس فشرده سازي تصاوير در حوزه ي مکاني مي باشد. در اين مقاله جديدترين روشهايي که در حوزه ي مکاني ارايه شده است بررسي و نتايج آنها ارائه مي شود.
در يکي از مقالات اخير که عمل فشرده سازي را بر روي تصاوير ويژه RGB انجام داده است توانسته است نسبت فشرده سازي را در حالت بدون اتلاف براي همه ي تصاوير به طور ثابت تا حداکثر ١.٨٢ برساند[٧]. در مقاله اي، با يکسان سازي بلاک هايي از تصاوير و بهره گيري از روش RLE ، تصاوير بسيار بزرگ و با کيفيت حدود ٩٥ درصد فشرده شده است که براي تصاوير کوچک و کم کيفيت نتايجي ارايه نشده است [٨].در روشي نيز که در حالت با اتلاف ارايه شده توانسته است تصوير رنگي
”Lena“ را با ٣٢.٢٦= PSNR با ١٦٠=BPP فشرده نمايد [٩] . در مقاله ديگري تصوير ”Lena“ در اندازه ي ٥١٢*٥١٢با ٣٣.١١= PSNR با ٥٩٨=BPP به صورت فشرده ذخيره شده است [١٠] . همچنين در روشي ديگري که انجام گرفته است ، تصوير ”Lena“ با ٣١=PSNR با ميانگين ١٩٤=BPP فشرده شده است [١١].
در مقاله اي که با رويکرد رمز گذاري و فشرده سازي ارايه شده است توانسته است با حذف اعوجاج تصوير، آنرا به صورت فشرده و رمز شده تبديل کندکه درصد فشرده سازي در اين روش براي تصوير ”Lena“ ٧٥% با ٢٨=PSNR گزارش شده است [١٢] .اما آنچه که اين مقاله را متمايز مي کند ارايه يک الگوريتم پايه و جديد با عنوان ”IRN” در جهت فشرده سازي تصاوير با دقت ٢٤ بيتي براي هر پيکسل و به بالاست که قابل تلفيق با ساير الگوريتمها نيز مي باشد. اين الگوريتم در دو حالت
"با اتلاف " و "بدون اتلاف " مطرح شده است که در حالت بدون اتلاف در تصاوير کوچک بهتر از فرمت هاي ٢٤ بيتي معروف و بدون اتلافي چون tif،png ،bmp مي باشد. در ضمن پياده سازي اين الگوريتم پيشنهادي که در حوزه ي مکاني ارايه شده است در بسياري از محيط ها به مراتب آسانتر از روشهاي ارايه شده در حوزه ي فرکانسي ست .
٢. قضايا و لم هاي رياضي
در اين قسمت ، قضايا و لم هاي رياضي مطرح و اثبات مي گردند و در بخشهاي بعدي در اجراي الگوريتم پيشنهادي جهت فشرده سازي تصاوير از آنها استفاده خواهد شد. آنچه در اين بخش بحث خواهد شد ٣ قضيه و ٢ لم مي باشد که توسط روابط رياضي ارايه و اثبات شده اند.
٢.١. قضيه (١): اگر تعاريف زير در نظر گرفته شود:
Z{0,1,2,3,...},N{1,2,3,...}
f:Z
(١) "تعداد بيت هاي لازم براي ذخيره کردن عدد صحيح و مثبت
آنگاه خواهيم داشت :
علامت x به معناي جزء صحيح عدد x است يعني قسمت صحيح هر عدد اعشاري و همچنين تعريف مي شود :
1 (4)
اثبات :
اگر مي توان طبق قوانين تصاعد هندسي آنرا به صورت حاصلجمع زير نوشت :
که طبق قاعده ي حاصلجمع تصاعد هندسي در صورتيکه جمله ي اول تصاعد ١=a و قدر نسبت ٢=q خواهيم داشت :
بنابراين رابطه ي فوق را مي توان به صورت زير نوشت :
اين رابطه ، اگر در مبناي ٢ در نظر گرفته شود خواهيم داشت :
تعداد يک ها در مبناي ٢, n مي باشد، بنابراين مي توان فهميد که x از بزرگترين داده ي n بيتي ١ واحد بزرگتر است بنابراين نتيجه گرفته مي شود که x ، ١+n بيتي بوده و براي ذخيره کردن آن ١+n بيت نياز است يعني:
در اينجا بخش اول قضيه يعني رابطه (٢) ثابت مي شود.
براي اثبات حالت دوم قضيه نيز با توجه رابطه ي(٧) داريم :
که عدد سمت چپ رابطه ي نامساوي(١٠) ، n و عدد سمت راست نامساوي(١٠) ،١+n بيتي است که اين رابطه نشان مي دهد که x از بزرگترين داده ي ١-n بيتي بزرگتر و از کوچکترين داده ي ١+n بيتي کوچکتر است ، بنابراين x فقط مي تواند n بيتي باشد، يعني:
f(x)n (12)
بنابراين حکم ثابت است .
٢.١.١. لم (١): در قضيه (١) داريم :
اثبات : در نظر مي گيريم :
٢.١.٢. لم (٢):همچنين در قضيه (١) داريم :
اثبات : تعريف مي کنيم : خواهيم داشت :
بنابر اين با ٢ حالت مواجه خواهيم شد که در دو حالت نيز طبق دلايل ارايه شده حکم برقرار است :
٢.٢. قضيه (٢): عدد داراي t رقم در مبناي b را به صورت زير تعريف مي کنيم :
در صورتيکه باشد ، عدد x بزرگترين عدد t رقمي در مبناي b است و در
آن صورت خواهيم داشت :
اثبات : با توجه به قانون تبديل مبناها مي توان نوشت :
و طبق تعريف اين عدد بزرگترين عدد t رقمي در مبناي b است و داريم :
بنابراين :
اگر در نظر بگيريم ، طبق لم (١) و لم (٢) خواهيم داشت :
٢.٢.١. قضيه (٣): اعداد کم ارزش ، ٣٨ درصد از حجم هر تصوير را اشغال مي کنند.
براي اثبات اين قضيه نياز به تعاريف و مقدمات زير مي باشد که پس از ذکر آنها، به اثبات آن پرداخته خواهد شد.
.2.2.1.1 تعريف ارقام و اعداد کم ارزش و با ارزش
مقادير عددي هر تصويري که به صورت ٢٤ بيتي ذخيره شده است از سه رنگ R,G,B تشکيل شده است ، بنابراين مقدار
عددي هر پيکسلي مانند x را به صورت زير نمايش داده مي شود:
ارقام Rx,Gx,Bx، ارقامي در مبناي ٢٥٦ هستند که طبق رابطه ي(١٥)، پس از بسط و تبديل آن به مبناي ١٠ ،تبديل به ضرايبي در مبناي ١٠ شده اند و آنها را اعدادي در مبناي ١٠ در نظر مي گيريم ، بنابراين به کمک قانون تقسيم ها
داريم (تقسيم بر ١٠):
که در آنها Rxh,Gxh,Bxh خارج قسمت تقسيم يا ارقام با ارزش و Bxl,Gxl ,Rxl باقيمانده ي تقسيم يا ارقام کم ارزش مي باشند که ، توسط آنها، اعداد با ارزش و کم ارزش در مبناي ٢٥٦ طبق رابطه ي(١٩) و (٢٠) ايجاد مي شوند.
که به کمک قانون جمع مبناها مي توان نوشت :
اثبات :
از آنجا که در رابطه هاي (١٩)،(٢٠) و (٢١)، مبناي ٢٥٦ مبناي بزرگي است و اعداد بزرگي توليد مي کند مي توان اين مبنا را به حداقل مقدار خود کاهش داده و اعداد را با مبناي کوچک نگهداري کرد و در هنگام کدگشايي بدون از دست دادن هيچ مقداري دوباره به مبناي ٢٥٦ بازگشت .
در روابط (١٦) و (١٧) و (١٨) مي توان از ضريب ثابت ١٠ صرفنظر کرد، بنابراين واضح است بزرگترين خارج قسمت ٢٥ خواهد بود، بنابراين مي توان به جاي ذخيره ي عدد حاصل از ارقام با ارزش در مبناي ٢٥٦ ، از مبناي ٢٦ استفاده کرد تا اعداد کوچکتري توليد شود.
در مورد ارقام کم ارزش چون بزرگترين باقيمانده يا بزرگترين رقم کم ارزش ، ٩ مي باشد بنابراين براي ذخيره ي عدد حاصل از ارقام کم ارزش در مبناي ٢٥٦ ، نيز مي توان از مبناي ١٠ کمک گرفت .
بنابراين براي هر پيکسل مي توان رابطه ي(٢١) را به صورت رابطه ي برگشت پذير زير ارايه داد:
در اين رابطه مقادير سمت راست بدون هيچ اتلاف داده اي قابل تبديل به مقدار واقعي چپ مي باشد، کافي است ١٠ برابر
ارقام با ارزش را به مبناي ٢٥٦ برده و با ارقام کم ارزش در مبناي ٢٥٦ جمع کنيم يعني :
حال بر طبق قضيه (٢) و رابطه ي(١٤) ، تعداد بيت هاي لازم جهت ذخيره کردن اجزاء رابطه ي(٢٢) چنين خواهد شد:
پيداست که طبق رابطه ي (٢٥)، تنها ١٥ بيت براي ذخيره کردن بزرگترين عدد با ارزش هر پيکسل لازم است و اگر از الگوريتم کدگذاري با طول ثابت استفاده شود در آنصورت بايد همه ي اعداد با ارزش ديگر پيکسلها نيز در اندازه و طول ثابت
١٥ بيت کدکذاري و ذخيره شوند، همچنين به طور مشابه ، طبق رابطه ي(٢٤)، ٢٤ بيت جهت ذخيره ي بزرگترين مقدار هر پيکسل (متشکل از مقادير عددي با ارزش و کم ارزش ) نياز است ، که مقادير ساير پيکسلها نيز بايد در اندازه و طول ثابت ٢٤ بيت کدگذاري و ذخيره شوند. بنابراين با حذف مقادير عددي کم ارزش طبق رابطه ي(٢٦)، به طور ثابت ٣٨ درصد از حجم هر پيکسل و در مجموع ٣٨ درصد از حجم هر تصوير کاسته خواهد شد.
خوشبختانه حذف مقادير کم ارزش ، کيفيت تصاوير را در حد معقول نگه مي دارد، ولي در ادامه به کمک الگوريتم هاي پيشنهادي به کدکردن ارقام کم ارزش و ذخيره سازي آنها پرداخته شده است . همچنين اعداد با ارزش نيز به علت يکنواختي مقادير و افزاايش يافتن فراواني داده هايشان با الگوريتمهايي که اولا از فراواني داده ها و ثانيا از کد گذاري با طول متغير در جهت فشرده سازي خود استفاده مي کنند، فشرده و نگهداري مي شوند که در حالت فشرده سازي با اتلاف ميزان فشرده سازي بدست آمده در اين قسمت با ٣٨ درصد فشرده سازي قسمت قبل ، مجموع فشردگي تصوير را در بيشترين حالت ممکن تشکيل مي دهند. ، که در ادامه به آنها پرداخته خواهد شد.
٣. الگوريتم هاي فشرده سازي اعداد با ارزش و ارقام کم ارزش
در اين قسمت دو الگوريتم با عناوين "الگوريتم ميانه اي"، و "الگوريتم کدگذاري طول کد" که اولي براي فشرده کردن ارقام کم ارزش و دومي براي فشرده سازي اعداد با ارزش به کار ميرود ارايه مي گردد.
٣.١. الگوريتم فشرده سازي با اتلاف ويژه ارقام کم ارزش
٣.١.١. الگوريتم ميانه اي يا Middle Algorithm( MIA)
اين الگوريتم به معني دسته بندي ارقام و انتخاب رقم ميانه در بين هر يک از دسته هاست که در اين الگوريتم ، ارقام ميانه کدگذاري و نگهداري مي شوند.
به عنوان مثال دامنه ي ارقام کم ارزش را که ارقامي بين ٠ تا ٩ مي باشند را طبق جدول (١)، دسته بندي و کدگذاري مي کنيم .
