335

Image Compression Through “Cutting of Numbers” Algorithm (Separating of High an​d Low Value Digit of Pixels in Spatial Domain) an​d “Code Length Encoding” Algorithm

كارشناسي ارشد

كامپيوتر

تهران شمال

94

94/6/8

18/75

74ص

عسگري مقدم

74-72ص

Image compression , Pre-processing , Code Length Encoding

در اين پايان‌نامه يك روش پايه بر اساس الگوريتم پيشنهادي برش اعداد، جهت فشرده‌سازي داده ارائه‌شده است كه اين الگوريتم در اين پايان‌نامه، به‌طور اختصاصي به فشرده‌سازي داده‌هاي تصاوير 24 بيتي با عنوان ”” PGH در دو حالت فشرده‌سازي «با اتلاف» و «بدون اتلاف» مي‌پردازد. اگر داده‌هاي كامپيوتري به چمن تشبيه شود، به‌وضوح مي‌توان فهميد كه توسط يك الگوريتم برش مي‌توان قسمت‌هاي مشترك زيادي از داده‌ها را كه داراي فراواني بسيار زيادتري هستند از قسمت‌هاي كم‌ارزش و هرز كه باعث كم شدن فراواني مي‌شود جدا كرده و هر دو را با توجه به ارزششان به‌طور مجزا نگهداري نمود. در اين روش پيشنهادي، داده‌ها با برش، به اعداد برش يافته باارزش و كم‌ارزش تفكيك‌شده و به‌طور جداگانه فشرده و نگهداري مي‌شوند. بزرگ‌ترين ويژگي عمل برش، جدا كردن بخش مشترك داده‌هاست. با اين عمل فراواني داده‌ها افزايش مي‌يابد و عمل فشرده‌سازي توسط هر روش ديگري نتايج بهتري خواهد داشت. در اين پايان‌نامه ضمن اثبات جبري الگوريتم برش، اثبات‌شده است كه در هر داده‌ي t بيتي، 41.6 درصد از حجم هر داده، مربوط به اعداد كم‌ارزش است كه فقط حاوي 9 درصد اطلاعات آن داده هست. همچنين كاربرد آن در الگوريتم LZW موجود در فرمت png و الگوريتم هافمن بررسي و نتايج مثبت آن ارائه‌شده است كه اين نتايج بر روي‌داده‌هاي فرمت png، افزايش 10 تا 70 درصدي فشرده‌سازي آن بوده است. همچنين اين الگوريتم توانست ميزان فشرده‌سازي الگوريتم هافمن را كه بر روي تصوير Lena با اندازه‌ي 512*512 انجام شد را تا 35 درصد بهبود بخشد. اين الگوريتم را مي‌توان به‌منظور فشرده‌سازي هر نوع داده‌اي به كاربرد. در اين الگوريتم هرچه داده‌ها داراي عمق بيتي بيشتري باشند، بهتر و بيشتر فشرده مي‌گردند. در اين الگوريتم پيشنهادي با استفاده از قضيه‌ها و لم هاي ارائه‌شده و با كمك فن جداسازي ارقام باارزش و كم‌ارزش داده و به‌كارگيري اين قضايا و روش‌ها براي داده‌هاي عددي پيكسلي در فضاي RGB و تشكيل اعداد باارزش و كم‌ارزش، ثابت مي‌شود كه در همه‌ي تصاوير 24 بيتي، در صورت ذخيره اعداد با طول ثابت، اعداد كم‌ارزش به‌طور ثابت 41.6 درصد از حجم هر تصوير را اشغال مي‌كنند كه توسط SNR به‌عنوان معيار سنجش كيفيت و بر طبق نتايج حاصله، مشخص‌شده است كه قابليت اعداد كم‌ارزش پيكسل‌هاي تصوير در كيفيت دهي به آن تصوير بسيار ناچيز هست. در ادامه براي فشرده‌سازي ارقام كم‌ارزش، يك روش پيشنهادي به نام MEA ارائه‌شده كه از آن در الگوريتم PGH استفاده‌شده است. همچنين اعداد باارزش نيز به علت يكنواختي مقادير و افزايش يافتن فراواني داده‌هايشان با الگوريتم‌هايي كه اولاً از فراواني داده‌ها و ثانياً از الگوريتم كدگذاري با طول متغير مانند الگوريتم پيشنهادي كدگذاري طول كد، در جهت فشرده‌سازي خود استفاده مي‌كنند فشرده و نگهداري مي‌شوند. در حالت فشرده‌سازي با اتلاف، ميزان فشرده‌سازي به‌دست‌آمده در اين قسمت با 41.6 درصد فشرده‌سازي قسمت قبل، مجموع فشردگي تصوير را در بيشترين حالت ممكن تشكيل مي‌دهند. نتايج پياده‌سازي اين روش در حالت بدون اتلاف، نشان‌دهنده‌ي برتري فشردگي حدود 20 درصدي تصاوير نسبت به فرمت‌هاي tiff, png, bmp هست، همچنين با بررسي و پياده‌سازي الگوريتم پيشنهادي مشخص گرديد كه اين الگوريتم بهتر از فرمت‌هاي png و tiff توسط نرم‌افزارهاي zip مانند WinZip و WinRAR، فشرده مي‌شود

34813