7 января, 2018 18:47
Дэрістін мэнмэтіні
Мақсаты: Ақпаратты қысу эдістерінің жалпы бағыггарын білу
Дэріс жоспары
1. Түрлендірулерді кодтау. ІРЕО қысу стандарты
2. Фракталды эдіс
3. Рекурсивті (толқынды) алгоритм
Негізгі түсініктер: абсолютті дәл, деректерді жуықтап калпына келтіру, кванттау, пиксель, квадраттық блоктар, дабыл спектрі, арифметикалық кодтау, Хаффмен алгоритмі, спектрлік компонент- тер, фракталды кодтау, шауеіеі
Тақырыптың мазмүны: Алғашқы деректерді тұтынушыға берудің, абсолютті дэлдігіне деген қажеттіліктің, көбінесе керегі жоқ болады. Біріншіден, деректер көздерінің өзі шектеулі динамикалық диапозонға ие және бұрмалаулар мен қателердің белгілі бір деңгейімен алғашқы хабарды шығарады. Екіншіден, байланыс ар- налары бойынша деректерді беру мен оларды сақтау эрқашанда эртүрлі кедергілердің болуы кезінде жүргізіледі. Сондықтан (жаңғыртылған) хабар эрқашанда белгілі бір дэрежеде берілген хабардан өзгешеленеді. Ең соңында, акпараттарды алушылар — адамның сезетін органдары, атқарушы тетіктер жэне т.б., сондай- ақ соңғы шешуші қабілетке ие, яғни жаңғыртылатын хабардың абсолютті дәл жэне жуьің мәндері арасындағы шамалы айырма- ларды байқамайды. Бұзумен кодтау осы дәлелдерді деректерді жуыңтап ңалпына келтіру пайдасы үшін ескереді жэне шамасы бойынша кейбір бақыланатын қателер есебінен қысу коэффициенттерін алуға мүмкіндік береді, бұл кейбір уақытта бұзбайтын әдістер үшін қысу дэрежесінен ондаған есе артып кетеді. Бұзатын қысу әдістерінің басым көпшілігі, деректердің өзін емес, одан, мысалы, Фурье дискреттік түрлендіруінің коэффициенттерінен, |
косинустык түрлендірудің коэффициенттерінен сияқты сызықтык түрлендірулерді кодтауға негізделген.
ІРЕО — аса қуатты алгоритм. Тэжірибеде ол толық түрлі түсті бейнелер үшін де-факто стандарты болып саналады. Анықтығы мен түсі салыстырмалы түрде бірқалыпты өзгеретін алгоритм 8×8 аймақтарында сүйеніп пайдаланылады. Осының салдары- нан, матрицалардың осындай аймағын косинустар бойынша екілік қатарға жіктеу кезінде, алғашқы коэффициенттер ғана маңызды болады. Сонымен ІРЕО-ке қысу, бейнелердегі түстерді өзгертудің бірқалыптылығы есебінен жүзеге асырылады. Алгоритм 24-биттік бейнелерді қысу үшін фотографиялар саласындағы сарапшылар тобы арнайы әзірлеген болатын. ІРЕО — Іоіпі РһоІо§гарһіс Ехрегі Огоир — 180 — стандарттау жөніндегі Халықаралық ұйым шеңберіндегі бөлімше. Тұтастай алғанда ал- горитм — коэффициенттердің белгілі бір жаңа матрицаларын алу үшін бейнелеу матрицасына қолданылатын дискреттік косинусой- далды түрлендірулерге ДКТ (Бізсгеіе-Созіпе ТгапзГогш — БСТ)-ке негізделеді. Алғашқы бейнені алу үшін кері түрлендіру алынады. БСТ бейнелерді кейбір жиіліктер амплитудалары бойынша өзара бөледі. Сонымен, түрлендіру кезінде біз көптеген коэффициенттері нөлге жақын, я тең болатын матрицаны аламыз. Бүдан өзге, адам көзінің жетілмегендігінен коэффициенттерді бейнелеу сапасын айтарлықтай жоғалтусыз неғұрлым өрескелдеу аппроксимациялауға болады. Бұл үшін коэффициенттерді кванттау (циапПгаНоп) пайдаланы- лады. Ең қарапайым жағдайда — бұл арифметикалық бит бойынша оң жаққа ығысу. Мұндай түрлендірулерде ақпараттардың бір бөлігі жоғалады, бірақ үлкен қысу дэрежесіне қол жеткізілуі мүмкін. 256 деңгейлердегі (8 екілік разрядтар) аныктық градацияларының санымен өзінің санаулар (пиксельдер) жиынымен берілген ақ- қара бейнені кодтау кезіндегі ІРЕС қысу алгоритмінің жұмысын қарастырамыз. Бұл бейнелерді сақтаудың ең көп таралған тәсілі — экрандағы эрбір нүктеге, оның айқындығын анықтайтын, бір байт (8бит — 256 мүмкін мәндер) сэйкес келеді. 255 — ең жоғары айқындық (ақ түс), 0 — ең төменгі айқындық (қара түс). Аралық мэн сұр түстердің бүкіл қалған гаммасын құрайды (58-сурет). .ГРЕО қысу алгоритмінің жұмысы бейнені 8 х 8 = 64 пиксельдер өлшемімен квадраттъщ блоктарга бөліктеу жолымен басталады. |
Қысудың екінші кезеңі — бүкіл блоктарга дискреттік косинустъщ түрлендіруді — ОСТ цолдану. Дискреттік косинустык түрлендіру бейнені кеңістіктік көрсетуден (санаулар немесе пиксельдер жиы- нымен) спектрлік көрсетуге (жиілікті қүраушылардың жиынымен) көшуге жэне керісінше жасауға мүмкіндік береді.
ІМС (х, у) бейнелеуден дискреттік косинустық түрлендіру мына- дай түрде жазылуы мүмкін: ОСТ(иу) = 8цгі(2Ш) ЪчІМС (х ,,у ,)со8 ((2і +1)ки/2Ы)со8 ((2] +1) ж у/2Ы), (183) мұндағы, N = 8, 0<і<7,0<і<7, немесе, матрицалық формада КЕ5 = ӘСТ Т*ІМС * ОСТ (184) мұндағы, ӘСТ — төмендегідей түрге ие, өлшемі 8×8 түрлендіру үшін базистік (косинустық) коэффициенттер матрицасы: |
.35355 | .35355 | .35355 | .35355 | .35355 | .35355 | .35355 | .35355 |
3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
.49039 | .41581 | .27799 | .09788 | — | — | — | — |
3 | 8 | 2 | 7 | .09710 | .27732 | .41537 | .49024 |
6 | 9 | 5 | 6 | ||||
.46197 | .19161 | — | — | — | — | .19014 | .46136 |
8 | 8 | .19088 | .46167 | .46228 | .19235 | 5 | 6 |
2 | 3 | 2 | 3 | ||||
.41481 | — | — | — | .27666 | .49071 | .09944 | — |
8 | .09710 | .49024 | .27865 | 7 | 0 | 8 | .41448 |
6 | 6 | 3 | 6 | ||||
.35369 | — | — | .35256 | .35481 | — | — | .35143 |
4 | .35313 | .35425 | 7 | 9 | .35200 | .35537 | 5 |
1 | 6 | 1 | 8 | ||||
.27799 | — | .09632 | .41670 | — | — | .49101 | — |
2 | .49024 | 4 | 0 | .41448 | .10022 | 3 | .27467 |
6 | 6 | 8 | 3 | ||||
.19161 | — | .46136 | — | — | .46318 | — | .18719 |
8 | .46228 | 6 | .18940 | .19382 | 7 | .46044 | 5 |
2 | 9 | 2 | 0 | ||||
.09788 | — | .41670 | — | .48977 | — | .27400 | — |
7 | .27865 | 0 | .49086 | 1 | .41359 | 8 | .09241 |
3 | 2 | 3 | 4 |
Сонымен, блокқа дискреттік косинустык түрлендірудің өлшемі 8×8 пиксельдері бейнесін қолдану нәтижесінде, сондай-ақ санаулардың 8×8 өлшеміне ие екі өлшемді спектр аламыз. Басқаша айтсақ, бейненің санауларын көрсететін 64 саны, оның ОСТ- спектрінің санауларын көрсететін 64 санға айналады. |
351 |
-> | <- | 8 | пи | кс | ел | ь | |||||||
я; | |||||||||||||
— | |||||||||||||
і’- | |||||||||||||
\ | |||||||||||||
АА | Г |
154 | 154 | 175 | 182 | 189 | 168 | 217 | 175 |
154 | 147 | 168 | 154 | 168 | 168 | 196 | 175 |
175 | 154 | 203 | 175 | 189 | 182 | 196 | 182 |
175 | 168 | 168 | 168 | 140 | 175 | 168 | 203 |
168 | 168 | 154 | 196 | 175 | 189 | 203 | 154 |
168 | ібі | ібі | 168 | 154 | 154 | 189 | 189 |
147 | ібі | 175 | 182 | 189 | 175 | 217 | 175 |
175 | 175 | 203 | 175 | 189 | 175 | 175 | 182 |
231 | 224 | 224 | 217 | 217 | 203 | 189 | 196 | ||
210 | 217 | 203 | 189 | 203 | 224 | 217 | 224 | ||
196 | 217 | 210 | 224 | 203 | 203 | 196 | 189 | ||
210 | 203 | 196 | 203 | 182 | 203 | 182 | 189 | ||
203 | 224 | 203 | 217 | 196 | 175 | 154 | 140 | ||
182 | 189 | 168 | 161 | 154 | 126 | 119 | 112 | ||
175 | 154 | 126 | 105 | 140 | 105 | 119 | 84 | ||
154 | 98 | 105 | 98 | 105 | 63 | 112 | 84 | ||
42 | 28 | 35 | 28 | 42 | 49 | 35 | 42 | ||
49 | 49 | 35 | 28 | 35 | 35 | 35 | 42 | ||
42 | 21 | 21 | 28 | 42 | 35 | 42 | 28 | ||
21 | 35 | 35 | 42 | 42 | 28 | 28 | 14 | ||
56 | 70 | 77 | 84 | 91 | 28 | 28 | 21 | ||
70 | 126 | 133 | 147 | 161 | 91 | 35 | 14 | ||
126 | 203 | 189 | 182 | 175 | 175 | 35 | 21 | ||
49 | 189 | 245 | 210 | 182 | 84 | 21 | 35 |
58-сурет. Сұр түстер гаммаларының аралық мәндері
Дабьш спектрі — бұл тиісті спектрлік кұраушьшар, нэтижесінде осы дабылды беретін жиынға кіретін коэффициенттер шамалары. Да- был соған өзара бөлінетін, жекелеген спектрлік кұраушьшар, көбінесе базистік атқарымдар деп аталады. ПФ үшін эртүрлі жиіліктердегі сину- стар мен косинустар базистік атқарымдар деп аталады. 8×8 ОСТ үшін базистік атқарымдар жүйесі мына формуламен беріледі |
Ь[ х,у ] = С08 |
(2х + 1 )ил
Тб |
С05 |
(2у + 1 )үл
Тб |
(186) |
ал базистік атқарымдардың өзі 59-суретте көрсетілген сияқты көрінеді. (0,0) индекстерге сэйкес келетін, аса төмен жиілікті базистік атқарым суреттің сол жақ жоғарғы бұрышында, ал аса жоғары жиілік — төменгі оң жақта бейнеленген. (0,1) үшін базистік атқарым, бір координат бойынша косинусоид периодының жарты- сын жэне (1,0) индекстермен өзге базистік атқарым бойынша кон- |
стантаны көрсетеді, бірақ 90°-қа бұрылған.
Дискреттік косинустық түрлендіру 8×8 пиксельдер бейнесінің блоктарын осы базистік атқарымдардың әрбірімен элемент бойын- ша қайта көбейту жэне қосындылау жолымен есептеледі. Нәтижесінде, мысал үшін, ЭСТ — спектрінің компоненті (0,0) индекстермен, бейне блогының бүкіл элементтерінің жиынын жай түрде көрсететін болады, яғни блок үшін орташа анықтықты көрсетеді. (0,1) индекспен компонентке бейненің бүкіл горизон- таль бөлшектері бірдей салмақтармен орташаландырылады, ал вер- тикаль бойынша ең үлкен салмақ бейненің жоғарғы бөліктерінің элементтеріне беріледі. ВСТ матрицасында оның компоненті неғұрлым төмен және оң жақка қарай болса, ол соғұрлым бейненің неғұрлым жоғары жиіліктік бөлшектеріне сәйкес келеді. БСТ-спектрі бойынша алгашқы бейнені алу үшін (кері түрлендіруді орындау үшін), енді (0,0) индекстері бар базистік атқарымды (0,0) координаталарымен спектрлік компонент- ке көбейту, көбейтінді нәтижесіне, спектрлік (1,0) базистік атқарымдар көбейтіндісінің нэтижесіне компонентке (1,0) базистік атқарымдарды (1,0) қосу қажет. Төменде келтірілген 10-кестеден бейне блоктарының жэне оның ОСТ-спектрінің бірінің сандық мәндерін көруге болады: 10- кесте. Бейненің жэне оның ОСТ-спектрінің сандық мэні |
Алғаіицы деректер | |||||||
139 | 144 | 149 | 153 | 155 | 155 | 155 | 155 |
144 | 151 | 153 | 156 | 159 | 156 | 156 | 156 |
150 | 155 | 160 | 163 | 158 | 156 | 156 | 156 |
159 | 161 | 161 | 160 | 160 | 159 | 159 | 159 |
159 | 160 | 161 | 162 | 162 | 155 | 155 | 155 |
161 | 161 | 161 | 161 | 160 | 157 | 157 | 157 |
161 | 162 | 161 | 163 | 162 | 157 | 157 | 157 |
162 | 162 | 161 | 161 | 163 | 158 | 158 | 15 |
ОСТ нәтижесі | |||||||
235,6 | -1 | -12,1 | -5,2 | 2,1 | -1,7 | -2,7 | 1,3 |
-22,6 | -17,5 | -6,2 | -3,2 | -2,9 | -0,1 | 0,4 | -1,2 |
-10,9 | -9,3 | -1,6 | 1,5 | 0,2 | -0,9 | -0,6 | -0,1 |
Алгашқы деректер | |||||||
-7,1 | -1,9 | 0,2 | 1,5 | 0,9 | -о,і | 0 | 0,3 |
-0,6 | -0,8 | 1,5 | 1,6 | -0,1 | -0,7 | 0,6 | 1,3 |
1,8 | -0,2 | 1,6 | -0,3 | -0,8 | 1,5 | 1 | -1 |
-1,3 | -0,4 | -0,3 | -1,5 | -0,5 | 1,7 | 1,1 | -0,8 |
-2,6 | 1,6 | -3,8 | -1,8 | 1,9 | 1,2 | -0,6 | -0,4 |
I |
1/а 3 4 $ б 7 |
іИ |
• | ||||
♦ | ||||
Т | ||||
іір) |
ЭСТ-спектр |
оЩ|) ИтЩ» |
59-сурет. 8×8 БСТ үшін базистік атқарымдар жүйесі
Алынған ОСТ-спектрдің өте қызықты ерекшелігін атап өтеміз: оның ең үлкен мэні сол жақ жоғарғы бүрышына шоғырландырылған (төменжиілікті күраушылар), оның оң жақтағы төменгі бөлігі (жоғары жиілікті құраушылар) салыстырмалы түрде шағын сан- дармен толтырылған. Бұл сандар, бейне блогындағыдай болады: 8×8 = 64, яғни эзірге ешқандай қысу болмағандай жэне егер кері түрлендіруді орындайтын болсақ, бейненің сондай блогын алатын боламыз. ДРЕО алгоритм жүмысының келесі кезеңі кванттау (11 -кесте) бо- лып саналады. Егер БСТ нэтижесінде алынған коэффициенттерге назар салып |
қарайтын болсақ, онда олардың жартысы — нөлдік немесе ең кіші мэнге ие (1-2) болатынын көретін боламыз. Бұл ешкандай нұқсан келтірусіз алып тасталуы мүмкін немесе ең жуық бүтін мэнге дейін дөңгелектенуі мүмкін жоғары жиіліктер.
БСТ эрбір коэффициентін кванттау матрицасына сэйкес белгілі бір санға бөлу кванттау болып табылады. Бүл матрица, я тіркелген болуы, я неғұрлым сапалы жэне тиімді кысу үшін алғашқы суреттерді талдау нәтижесінде алынған болуы мүмкін. Бөлінетін сан неғұрлым үлкен болса, бөлу нәтижесінде нөлдік мән соғұрлым үлкен, қысу күштірек жэне жоғалтулар елеулі болады. |
11- кесте.
ЛРЕС алгоритм жүмысы |
Бұрын алынган ОСТ нәтижесі |
235,6 | -1 | -12,1 | -5,2 | 2,1 | -1,7 | -2,7 | 1,3 |
-22,6 | -17,5 | -6,2 | -3,2 | -2,9 | -0,1 | 0,4 | -1,2 |
-10,9 | -9,3 | -1,6 | 1,5 | 0,2 | -0,9 | -0,6 | -0,1 |
-7,1 | -1,9 | 0,2 | 1,5 | 0,9 | -о,і | 0 | 0,3 |
-0,6 | -0,8 | 1,5 | 1,6 | -о,і | -0,7 | 0,6 | 1,3 |
1,8 | -0,2 | 1,6 | -0,3 | -0,8 | 1,5 | 1 | -1 |
-1,3 | -0,4 | -0,3 | -1,5 | -0,5 | 1,7 | 1,1 | -0,8 |
-2,6 | 1,6 | -3,8 | -1,8 | 1,9 | 1,2 | -0,6 | -0,4 |
Кванттау кестесі | |||||||
16 | 11 | 10 | 16 | 24 | 40 | 51 | 61 |
12 | 12 | 14 | 19 | 26 | 58 | 60 | 55 |
14 | 13 | 16 | 24 | 40 | 57 | 69 | 56 |
14 | 17 | 22 | 29 | 51 | 87 | 80 | 62 |
18 | 22 | 37 | 56 | 68 | 109 | 103 | 77 |
24 | 35 | 55 | 64 | 81 | 104 | 113 | 92 |
49 | 64 | 78 | 87 | 103 | 121 | 120 | 101 |
72 | 92 | 95 | 98 | 112 | 100 | 103 | 99 |
Кванттау нэтижесі | |||||||
15 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
-2 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
-1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Сызықтық тізбектіліктегі БСТ-спектрі матрицаларының 8×8 түрлендіруі ІРЕО алгоритм жүмысының келесі кезеңі болып санала- ды. Бірақ, бұл, мүмкіндік бойынша бүкіл үлкен мәні мен спектрдің бүкіл нөлдік мэнін бірге топтастыратындай етіп жасалады. Бүл үшін, ЭСТ коэффициенттері матрицаларының элементтерін (60-су- рет) сол жақ жоғарғы бүрыштан оң жак төменгі бұрышқа қарай таза- лау қажет болатыны анық. Бүл рәсім иректіксканирлеу деп аталады.
Осындай түрлендіру нәтижесінде БСТ квантталған коэффициенттердің 8×8 квадраттық матрицасы 64 саннан тұратын сызықтық тізбектілікке айналады, оның үлкен бөлігі — катар жүретін нөлдер. Осындай ағындарды цайталау ұзындъщтарын кодтау жо- лымен өте тиімді қысуға болады. |
60-сурет. Сызықтық тізбектіліктегі БСТ-спектр матрицаларының 8×8
түрлендірілуі |
Алынган тізбектіліктерді белгілі бір статистикалың алгоритм- мен кодтау (қайыра қысу) АРЕС алгоритм жұмысыныц келесі кезеңі болып саналады. Әдетте арифметикалық кодтау немесе Хаффмен алгоритмі пайдаланылады. Нәтижесінде, өлшемі алгашқы дерек- тер массивінің өлшемінен түбегейлі кіші болатын жаңа тізбектілік алынады.
ІРЕО алгоритмге сәйкес қысылған деректерді декодтау, код- тау сияқты, дэл сондай түрде жүргізіледі. Хаффмен (немесе Б2\¥) арифметикалық кодтау әдісімен бүзбайтындай етіп ашу жэне |
сызықтық тізбектіліктерді өлшемі 8×8 сандардың блоктарына қою кезінде, спектрпік компоненттер кодтау кезінде сақталған квант- тау кестелерінің көмегімен деквантталады. Бұл үшін ОСТ-тың ашылған 64 мэні кестелердің тиісті сандарына көбейтіледі. Осыдан кейін эрбір блок, оның рәсімі тікелей түрлендіруге сәйкес келетін және түрлендіру матрицасындағы таңбалармен ғана ерекшеленетін, кері косинустық түрлендіруге тартылады. Декодтау кезіндегі әрекеттердің тізбектілігі мен алынған нэтиже төменде берілген
12- кестеде кескінделген. Қалпына келтірілген деректер алғашқы деректерден біршама өзгешеленетіні анық. Бүл заңды болып саналады, өйткені ІРЕО, жогалтулармен қысу сияқты эзірленген болатын. |
12-кесте.
Әрекеттер тізбектілігі және декодтау кезінде алынған нәтиже |
Квантталган деректер | |||||||
15 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
-2 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
-1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Декквантталган деректер | |||||||
240 | 0 | -10 | 0 | 0 | 0 | 0 | 0 |
-24 | -12 | 0 | 0 | 0 | 0 | 0 | 0 |
-14 | -13 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Кері ОСТ нәтижесі | |||||||
144 | 146 | 149 | 152 | 154 | 156 | 156 | 156 |
148 | 150 | 152 | 154 | 156 | 156 | 156 | 156 |
155 | 156 | 157 | 158 | 158 | 157 | 156 | 155 |
160 | 161 | 161 | 162 | 161 | 159 | 157 | 155 |
163 | 163 | 164 | 163 | 162 | 160 | 158 | 156 |
163 | 164 | 164 | 164 | 162 | 160 | 158 | 157 |
160 | 161 | 162 | 162 | 162 | 161 | 159 | 158 |
158 | 159 | 161 | 161 | 162 | 161 | 159 | 158 |
Салыстыру уиіін — алгашқы деректер | |||||||
139 | 144 | 149 | 153 | 155 | 155 | 155 | 155 |
144 | 151 | 153 | 156 | 159 | 156 | 156 | 156 |
150 | 155 | 160 | 163 | 158 | 156 | 156 | 156 |
159 | 161 | 161 | 160 | 160 | 159 | 159 | 159 |
159 | 160 | 161 | 162 | 162 | 155 | 155 | 155 |
161 | 161 | 161 | 161 | 160 | 157 | 157 | 157 |
161 | 162 | 161 | 163 | 162 | 157 | 157 | 157 |
162 | 162 | 161 | 161 | 163 | 158 | 158 | 15 |
Төменде көрсетілген 61-суретте алғашқы бейне, сондай-ак ІРЕО алгоритмдерді пайдалана отырып, 10 есе (сол жақтан) жэне 45 есе (ортасында) қосылған бейне кескінделген. Соңғы жағдайда са- паны жоғалту тольщтай байқалады, бірақ көлемі бойынша ұту да айтарлықтай болады. |
61-сурет. .ІРЕС алгоритм пайдаланылган алғашқы жэне қысылған бейне |
Фракталъді кодтау — бұл, нацты бейнелерден, бейненің фракталъді қасиетін сипаттайтын математикальщ деректердің жиынтыгынан түратын, растрларды кодтау үшін қолданьілатын математикалық үдеріс. Фрактальді кодтау, бүкіл жасанды жэне ба- сым көпшілік табиғи объектілер, фрактальдар деп аталатын, бірдей, қайталанатын суреттер түріндегі артық ақпараттан тұратын фактіге негізделеді. Фрактальді қысу бейне, итерирленетін атқарымдар (Іісгаіесі Ғипсііоп Зузіегп — ІҒ8) жүйелері коэффициенттерінің көмегімен неғұрлым жиынтық (компактілі) формада көрсетілетініне негізделеді.
Фрактальді қысу үдерісінің өзін қарастырмас бұрын, ІҒ8 қалай бейнені жасайтынын анықтап аламыз, яғни декомпрессиялау үдерісін қарастырамыз. Нақтырақ айтатын болсақ, ІҒ8, біздің жағдайымызда бір бейнені екінші бейнеге ауыстыратын үшөлшемді аффиналық түрлендіргіштердің жиыны бөлып көрсетіледі. Үшөлшемдік кеңістіктегі нүктелер (X бейне нүктелерінің координатасы, Ү бейне нүктелерінің координатасы жэне I нүктелер жарықтығы) түрлендіруге тартылады. Бүл үдерісті ықшамдап мынадай түрде түсіндіруге болады. Алғашқы сурет бейнеленген экраннан жэне екінші экранга бейнені кескіндейтін линзалар жүйесінен тұратын, суретті көшіргілейтін машинаны (62-сурет) қарастырамыз. Суретті көшіргілейтін машина мынадай эрекеттерді орындауы мүмкін: • линзалар еркін формада бейненің бөлігін жаңа бейненің кез кел- ген өзге орнына кескіндеуі мүмкін; • бейнелеу кескінделетін аймақтар, қиылыспайды, • линза жарықтықты өзгертуі жэне контрастылықты кішірейтуі мүмкін; • линза айнадай көрсетуі жэне өз бейнесінің фрагментін бүруы мүмкін; • линза өз бейнесінің фрагментін масштабтауы (кішірейтуі) тиіс. Линзаны орнына қойып жэне олардың сипаттамаларын өзгертіп, алынатын бейнемен басқаруға болады. Машина жұмысының бір итерациясы мынадан тұрады: алғашқы бейне бойынша жобалау көмегімен жаңасы қүрылады, содан кейін жаңа алгашқы ретінде алы- натын болады. Итерациялар үдерісінде біздің, өзгеруін тоқтататын бейнені алатынымыз расталатын болады. Ол линзаның орналасуы |
мен сипаттамаларына ғана қатысты болады жэне алғашқы сурет- терге тэуелді болмайды. Бұл бейне «қозғалмайтын нүкте» немесе аталған ІҒ8-тің аттракторы деп аталады. Тиісті теория, эрбір ІҒ8 үшін тура бір қозғалмайтын нүктенің болуына кепілдік береді. |
62-сурет. Суретті көшіргілейтін машина
Өйткені линза бейнесі кысушы болып саналады, эрбір лин- за, біздің бейнедегі өзіне ұқсас аймақты анық береді. Өзіне ұқсастығының арқасында қалай үлкейтсек те, бейненің күрделі құрылымын аламыз. Осылайша, итерацияланатын атқарымдар жүйесі фрактальді — өзіне ұқсас математикалық объектіні беретіні түйсік арқылы түсінікті болады. Төрт аффиналық түрлендіргіштермен (немесе біздің термино- логияларымыздағы «линзалармен» берілетін, «папоротник Барнсли» (63 а-суреті) жэне үш аффиналық түрлендіргіштермен берілетін «Серпинский үшбұрышы» (63 б-суреті) ІҒ8 көмегімен алынған бейнелердің белгісі болып саналады. Әрбір түрлендіру, саналған байттармен кодталады, сол уақытта олардың көмегімен құрылған бейне ретінде, бірнеше мегабайтқа ие болуы мүмкін. Жоғарыда айтылғандардан, фрактальді кодердің қалай жұмыс істейтіні түсінікті болады жэне сондай-ақ, қысу үшін оған өте көп уақыт қажет екендігі анықталады. |
■Алынатын бейне |
63-сурет. Итерацияланатын аткарымдар жүйелері коэффициенттерінің көмегімен алынған бейне |
Нақты фрактальдік компрессия — бүл бейнелердегі өзіне ұксас аймактарды іздеу жэне ол үшін аффиналық түрлендіргіштер параметрлерін анықтау. Бұл үшін асып кетуді орындау жэне эртүрлі өлшемдегі бейненің бүкіл мүмкін фрагменттерін салыстыру кажет бо- лады. Тіпті шағын бейнелер үшін дискретгілікті есепке алған кезде біз іріктеп алатын нұсқалардың астрономиялық санын алатын боламыз, эрі түрлендіру саныптарын (кластарын), мысалы, масштабтау есебінен күрт тартылу белгілі бір санда ғана уақыт бойынша айтарлықтай үтуға әкелмейді. Бүдан өзге, бұл ретге бейне сапасы жоғалады. Фрактальдік қысу саласындағы зерттеулердің басым көпшілігі сапалы бейне алу үшін қажет архивтендіру уақытын азайтуға бағытталған.
Рекурсивтік қысудың ағылшынша атауы — \\’а\’еІеІ. Орыс тіліне ол толқынды қысу жэне су сылдырларын пайдаланып қысу ретінде ау- дарылады. Алгоритм біркалыпты ауысатын түрлі-түсті жэне ақ-қара бейнеге бағдарланған, рентгендік суретке түсіру типіндегі суреттер үшін мінсіз. Қысу коэффициенті 5-100 шектерінде беріледі жэне өзгереді. Әсіресе, диагональ бойынша өтетін шекараларда үлкен коэффициенттер беруге ұмтылыс жасау кезінде, «баспалдақтық эф- фект» — өлшемі бірнеше пиксельдер болатын эртүрлі жарықтық са- тылар көрінетін болады. Өз бейнесін кодтаудың орнына, әдетте 0-ге жуық мэні ңабылданатын, бейнелердегі көрші блоктардың орташа мэндері |
арасындагы айырма сақталатыны алгоритм идеясы болып табылады.
Мәселен, а2. жэне а2.+І екі санды эркашанда Ь’ =(а2:+а2і+І)/2 жэне Ь2=(а2-а2.+І)/2 түрде көрсетуге болады. Осыған ұқсас а. тізбектілігі Ь1-‘ тізбектілікке жұп болып ауыстырылуы мүмкін. Мысалдарды қарастырамыз. Біз пиксельдердің а. жарықтығының сегіз мэнінен жолды қысамыз: (220, 211, 212, 218, 217, 214, 210, 202). Мынадай Ьп, и Ь2і тізбектілік аламыз: ( 215.5, 215, 215.5, 206 ) жэне ( 4.5, -3, 1.5, 4). Ь мэнінің 0-ге аса жақын екенін байқаймыз. Ь -ні а. ретінде қарастырып, операцияны қайталаймыз. Аталған эрекет рекурсивті сияқты орындалады жэне алгоритм атауы содан шыққан. (215.5, 215, 215.5, 206)-дан (215.25, 210.75) (0.25, 4.75) аламыз. Алынған коэффициенттерді бүтінге дейін дөңгелектеп жэне қысып (мысалы, Хаффман алгоритмінің көмегімен), кодтау нәтижесі деп санауға болады. Біз өзіміздің түрлендіруімізді тізбекке екі рет қана қолданғанымызды байқаймыз. ка^еіеі — түрлендіруді 4-6 рет қолдану үшін өзімізге нақты мүмкіндік берсек, қысудың айтарлықтай коэффициенттеріне жетуге болады. Екі өлшемдер үшін алгоритм жоғарыдағыға ұқсас жүзеге асыры- лады. Егер бізде анықтықтары а2і2/ а2і+г а2.а2.2.+І, жэне а2і+І, а2.+г төрт нүктелерден тұратын квадрат бар болса, онда К2 ~( <*2і,2]+ а2і+1,2]+ ®2і,2]+1 «Е <*2і+1,2і+і)/4, Кі =( а2і,2]+ а2і+1,2}~ а2і,2}+Г а2і+1,2]+і)/4, Кі =( а2і,2]~ а2і+1,2]+ а2і,2]+Г а2і+1,2]+і)/4, Кі =( а2і,2Г а2і+1,2]~ а2і,2}+1+ <*2і+1,2і+і)/4, 512×512 пиксельдер бейнесі үшін осы формулаларды пайдала- нып, бірінші түрлендіруден кейін элементтердің өлшемі 256×256 4 матрицаларын аламыз. (64 а жэне б-суреттер): |
Алғашты
бейне |
В’ | в2 |
в3 | в4 |
Біріншісінде, бейненің кішірейтілген көшірмесі сақталатынына |
а) б)
64-сурет. \Уа\>еІе! түрлендіруді колдану |
оңай көз жеткізуге болады, екіншісінде — горизонталь бойынша пиксельдер мәндері жұптардың орташа айырмдары, үшіншісінде — вертикаль бойынша пиксельдер мэндерінің орташа айырымдары, төртіншіде — диагональ бойынша пиксельдер мәндерінің орташа ай- ырымдары.
Екіөлшемді жағдай ұкастықтары бойынша түрлендіруді қайталауға жэне бірінші матрицаның орнына өлшемі 128×128 4 матрица алуға болады. Түрлендіруді үшінші рет қайталап, қорытындысында 64×64 4 матрица, 128×1283 матрица жэне 256×256 3 матрица аламыз. Әрі қарай қысу айырымдық матрицаларда, квантталғаннан кейін тиімді қысылатын көптеген нөлдік немесе нөлге жақын мәндердің болуы есебінен орындалады. Желілер бойынша бейнені беру кезінде бейненің бірте-бірте «көріну» мүмкіндігін, оның өте оңай жүзеге асыруға мүмкіндік бере- тін осы алгоритмінің артықшылықтарына жатқызуға болады. Бұдан өзге, бейне басталар алдында біз оның кішірейтілген көшірмесін нақты сақтаймыз, тақырыбы (басы) бойынша «тереңдетілген» бейнесін көрсету оңайлатылады. ІРЕО жэне фрактальдік алгорит- мнен өзгешелігі — аталған эдіс блоктармен, мысалы, 8×8 пиксельдер- мен асып түспейді. Дэлірек айтқанда, біз 2×2, 4×4, 8×8 блоктармен асып түсеміз. Бірақ осы блоктар үшін коэффициенттердің тәуелсіз сақталатындығы есебінен, бейненің «мозаикалык» квадраттарга бөлшектенуін оңай болдырмауға болады. |
ҚОРЫТЫНДЫ |
• Бұзумен кодтау дәлелдерді деректерді жуъщтап цалпына келтіру пайдасы үшін ескереді жэне шамасы бойынша кейбір бақыланатын қателер есебінен қысу коэффициенттерін алуға мүмкіндік береді, бұл кейбір уақытта бұзбайтын әдістер үшін қысу дәрежесінен ондаған есе артып кетеді.
• Бұзатын қысу эдістерінің басым көпшілігі, деректердің өзін емес, одан, мысалы, Фурье дискреттік түрлендіруінің коэффициенттерінен, косинустық түрлендірудің коэффициенттері сияқты сызықтық түрлендірулерді кодтауға негізделген. • ІРЕО — аса қуатты алгоритм. Тәжірибеде ол, толық түрлі-түсті бейнелер үшін де-факто стандарты болып саналады. Анықтығы мен түсі салыстырмалы түрде бірқалыпты өзгеретін алгоритм 8×8 аймақтарында сүйеніп пайдаланылады. • Дабыл спектрі — бұл тиісті спектрлік күраушылар, нәтижесінде осы дабылды беретін жиынға кіретін коэффициенттер шамалары. Дабыл соған өзара бөлінетін, жекелеген спектрлік құраушылар, көбінесе базистік атқарымдар деп аталады. • ОСТ эрбір коэффициентін кванттау матрицасына сэйкес белгілі бір санға бөлу кванттау болып табылады. Бұл матрица, я тіркелген болуы, я неғұрлым сапалы жэне тиімді кысу үшін алғашқы суреттерді талдау нэтижесінде алынған болуы мүмкін. • Фрактальді кодтау — бұл, нақты бейнелерден, бейненің фрактальді қасиетін сипаттайтын математикалық деректердің жиынтығынан тұратын, растрларды кодтау үшін қолданылатын математикалық үдеріс. • Нақты фрактальдік компрессия — бұл бейнелердегі өзіне ұқсас аймақтарды іздеу жэне ол үшін аффиналық түрлендіргіштер параметрлерін анықтау. Бұл үшін асып кетуді орындау жэне эртүрлі өлшемдегі бейненің бүкіл мүмкін фрагменттерін салыстыру қажет болады. • Өз бейнесін кодтаудың орнына, эдетте 0-ге жуық мэні қабылданатын, бейнелердегі көрші блоктардың орташа мәндері арасындагы айырма сақталатыны, алгоритм идеясы болып табьша- ды. • Желілер бойынша бейнені беру кезінде бейненің бірте-бірте «көріну» мүмкіндігін оның өте оңай жүзеге асыруға мүмкіндік |
беретін осы алгоритмінің артықшылықтарына жатқызуға бола- ды. Бұдан өзге, бейне басталар алдында біз оның кішірейтілген көшірмесін нақты сақтаймыз, тақырыбы бойынша «тереңдетілген» бейнесін көрсету оңайлатылады.
СОӨЖ және СӨЖ тапсырмалары 1. Тақырып бойынша бақылау сұрақгарына жауап беру: 1. Түрлендірулер қалай кодталады? 2. ІРЕО деген не? 3. Фрактальді әдістің мэні қандай? 4. Рекурсивті алгоритм қалай кұрылады? 5. Базистік атқарымдар дегеніміз не? 6. Көшіргілейтін машина қандай іс-әрекеттерді орындайды? 2. Тақырып бойынша тест тапсырмаларының сұрақтарына жауап беру: 1. Ақпарат бірлігінің атын өзгерту деп нені айтады? A) Анықтамалық ақпараттарды өзгертуді айтады B) Материалдық құндылықтарды сақтауды айтады C) Мэліметтерді қорғауды айтады Б) Жаңа ат беруді айтады Е) Аталғандардың барлығы жатады 2. Іріктеу дегеніміз не? A) Бір облыстағы жинақталған АҚБ мәндері B) Бір аймақтағы АҚБ мәндер көпшісін бөлу операциясы C) Кез келген АҚБ мэндер жиынтығы Б) Барлық АҚБ мэндерін алу операциясы Е) Алын ала койылған іріктеу шартын қанағаттандыратын АҚБ мәндер көпшесін бөлу операциясы 3. Өндіру деңгейлері қандай шектеулерді қамтамасыз етеді? A) Технологиялық, шикілік, адамдық B) Уақыттық, сандық C) Жылдық, шикілік, адамдық О) Орталық, уақыттық |
Е) Технологиялық, уақыттық |
4. Сызықтық кодтардың негізгі қасиеттері қанша бөлімнен турады?
A) Жеті B) Алты C) Бес Б) Төрт Е) Үш 5. Экономикалық ақпараттық жүйеге астында аталғандардын қайсысы жатпайды? A) Сақтау B) Өңдеу C) Жинау О) Жою Е) Тарату 6. Дискриминатордың шығу жолына астында келтірілгендердің қайсысын қосқан жөн болады? A) Шектенушіні B) Сигналды C) Жиілікті Б) Девиацияны Е) Аталғандардың барлығы дұрыс 7. Соцғы қолданушы арқылы пайдалы ретінде қабылданған, үғынылған және бағаланған жаца мәліметтер: A) Ақпарат B) Құбылыс C) Жағдай Б) Жарнама Е) Алгоритм 8. Адамнын ұғыну және бағалау жүйесіне салынған, адам санасындағы хабарды көрсету: A) Ассимиляцияланған ақпарат B) Құжатталған ақпарат C) Берілетін акпарат О) Келтірілген ақпарат |
Е) Реттелген ақпарат |
9. Жүйенін көптеген элементтері және олардың арасындағы өзара байланыс қалай аталады?
A) Таңба B) Құрылым C) Сигнал В) Сөз Е) Рет 10. Объектіні басқарудың тиімділігін арттыру A) С4-С6 мақсаттары B) С6-С9 мақсаттары C) СІ-СЗ мақсаттары В) С9-С12 мақсаттары Е) СІ-СЗ мақсаттары 11. ЭАЖ ресурстарын тиімді қолдану A) С4-С6 мақсаттары B) С6-С9 мақсаттары C) СІ-СЗ мақсаттары Б) С9-С12 мақсаттары Е) СІ-СЗ мақсаттары 12. ЭАЖ көптеген аспектілер бойынша мыналарга жіктеледі: A) түрлерге B) типтерге C) деңгейлерге О) класстарға Е) үрдістерге 13. Біз қарастыратын ЭАЖ қандай жүйеге жатқызуға болады? A) практикалық B) теориялық C) әкімшілік-территориялық Б) құқықтық-экімшілік Е) экімшілік-үйымдасқан |
14. ЭАЖ-ны деректерді өңдеу жүйесі, басқарудың автоматтандырылған жүйесі жэне ақпараттық іздеу жүйесі деп неге байланысты бөлуге болады?
A) Қызметіне карай B) Типіне қарай C) Түріне қарай Б) Класына қарай Е) Ретіна қарай 15. ДӨЖ басқару шешімдерін таңдауды орындай алуға (өз бетімен немесе маманның қатысуымен) бейім болса, онда ол басқарудын автоматтандырылган жүйесі мынаган айналады: A) ЭАЖ айналады B) БАЖ айналады C) БҚБЖ айналады О) ДБ айналады Е) Бағдарламаларға айналады 16. Экономикалық-математикалық тәсілдер негізінде немесе маманның басқару шешімін қабылдау бойынша әрекеттерді модельдеу арқылы іске асатын үрдіс: A) Жүйенің есеп шығаруы B) Жүйенің қызмет атқаруы C) Жүйенің шешім қабылдауы Б) ЭЕМ дұрыс жүмыс істеуі Е) Процессордың жүмысын реттеу 17. Тапсырманы онтайландыруға арналған бастапқы мәліметтер дереқтердің қандай жүйесі режимінде есептеледі? A) сақтау B) теңестіру C) реттеу О) есептеу Е) өндеу 18. Индекстеу деп неше кезеңнен түратын процесті атаймыз? A) бес B) төрт C) үш |
Э) бір
Е) екі 19. Қандай да бір ақпараттық сұранысқа сәйкес келетін қркаттарды АІЖ арқылы іздеу үшін сүраныстың өзінде не істелуі керек? A) индекстелу B) реттелу C) көбейтілу Б) идентификациялану Е) сақталу 20. Өңдеудің қандай белгіленген уақыт мерзімі болмайынша және деректер көлемі қандай да бір шектен асып кетпейінше жүйеге деректер жинала береді: A) уакыттык режимінде B) пакеттік режимінде C) тэуелділік режимінде Э) тэуліктік режимінде Е) қолданбалы режимінде |