Некоторые способы кодирования растров в геоинформационных системах
Рассмотрены вопросы повышения компрессии при кодировании 256-цветных палитровых изображений. Учтена необходимость прямого доступа к растровым данным для геоинформационных систем. Даны описание и оценка эффективности разработанных способов кодирования. Розглянуто питання підвищення компресії при коду...
Gespeichert in:
| Veröffentlicht in: | Электронное моделирование |
|---|---|
| Datum: | 2008 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/101556 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Некоторые способы кодирования растров в геоинформационных системах / Т.А. Блинова, В.Н. Порев // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 119-128. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860046301869113344 |
|---|---|
| author | Блинова, Т.А. Порев, В.Н. |
| author_facet | Блинова, Т.А. Порев, В.Н. |
| citation_txt | Некоторые способы кодирования растров в геоинформационных системах / Т.А. Блинова, В.Н. Порев // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 119-128. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Рассмотрены вопросы повышения компрессии при кодировании 256-цветных палитровых изображений. Учтена необходимость прямого доступа к растровым данным для геоинформационных систем. Даны описание и оценка эффективности разработанных способов кодирования.
Розглянуто питання підвищення компресії при кодуванні 256-кольорових палітрових зображень. Враховано необхідність прямого доступу до растрових даних для геоінформаційних систем. Дано опис і оцінку ефективності розроблених способів кодування.
The problems of compression increase when encoding the 256-coloured palette images are considered. The necessity of direct access to raster data for the geographic information systems is taken into account. The description and efficiency estimate for developed encoding models are presented.
|
| first_indexed | 2025-12-07T16:58:24Z |
| format | Article |
| fulltext |
ÓÄÊ 681.327
Ò. À. Áëèíîâà *, Â.Í. Ïîðåâ **, êàíäèäàòû òåõí. íàóê
* Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò Óêðàèíû «ÊÏÈ»
(Óêðàèíà, 03056, Êèåâ, ïð-ò Ïîáåäû, 37, ÔÈÎÒ, êîðï. 18,
òåë.: (044) 4549338),
** Èí-ò çåìëåóïîðÿäî÷åíèÿ è èíôîðìàöèîííûõ òåõíîëîãèé
(Óêðàèíà, 03113, Êèåâ, óë. Äðóæêîâñêàÿ, 8, êàôåäðà ÃÈÑ,
òåë.: (044) 4835223, E-mail: kafedra_gis@ukr.net)
Íåêîòîðûå ñïîñîáû êîäèðîâàíèÿ
ðàñòðîâ â ãåîèíôîðìàöèîííûõ ñèñòåìàõ
(Ñòàòüþ ïðåäñòàâèë êàíä. òåõí. íàóê Â. Â. Àðèñòîâ)
Ðàññìîòðåíû âîïðîñû ïîâûøåíèÿ êîìïðåññèè ïðè êîäèðîâàíèè 256-öâåòíûõ ïàëèòðîâûõ
èçîáðàæåíèé. Ó÷òåíà íåîáõîäèìîñòü ïðÿìîãî äîñòóïà ê ðàñòðîâûì äàííûì äëÿ ãåîèí-
ôîðìàöèîííûõ ñèñòåì. Äàíû îïèñàíèå è îöåíêà ýôôåêòèâíîñòè ðàçðàáîòàííûõ ñïîñîáîâ
êîäèðîâàíèÿ.
Ðîçãëÿíóòî ïèòàííÿ ï³äâèùåííÿ êîìïðåñ³¿ ïðè êîäóâàíí³ 256-êîëüîðîâèõ ïàë³òðîâèõ çîáðà-
æåíü. Âðàõîâàíî íåîáõ³äí³ñòü ïðÿìîãî äîñòóïó äî ðàñòðîâèõ äàíèõ äëÿ ãåî³íôîðìàö³éíèõ
ñèñòåì. Äàíî îïèñ ³ îö³íêó åôåêòèâíîñò³ ðîçðîáëåíèõ ñïîñîá³â êîäóâàííÿ.
Ê ë þ ÷ å â û å ñ ë î â à: êîìïðåññèÿ áåç ïîòåðü, ïàëèòðîâûå èçîáðàæåíèÿ, ìåòîä RLE,
ïðÿìîé äîñòóï, ãåîèíôîðìàöèîííûå ñèñòåìû.
Ïðè ðàçðàáîòêå è èñïîëüçîâàíèè ïðîãðàììíîãî îáåñïå÷åíèÿ ãåîèíôîðìà-
öèîííûõ ñèñòåì (ÃÈÑ) âîçíèêàþò ïðîáëåìû, ñâÿçàííûå ñ ðàñòðîâûìè
èçîáðàæåíèÿìè. Ôîðìàò êîäèðîâàíèÿ 256-öâåòíûõ ïàëèòðîâûõ èçîáðà-
æåíèé èñïîëüçóåòñÿ, íàïðèìåð, äëÿ ýëåêòðîííûõ êàðò. Â ÃÈÑ òðåáóåòñÿ
÷èòàòü ïðîèçâîëüíûé ôðàãìåíò ðàñòðà è ìàñøòàáèðîâàòü èçîáðàæåíèÿ.
Äëÿ ýòîãî íåîáõîäèìî îðãàíèçîâàòü ïðÿìîé äîñòóï ê îòäåëüíûì ýëåìåí-
òàì ðàñòðà â ôàéëå èëè ãðóïïå ôàéëîâ, ÷òî äîëæíî ñî÷åòàòüñÿ ñ ýôôåêòèâ-
íîé êîìïðåññèåé áåç ïîòåðü. Íàèáîëåå ÷àñòî ñàìûé áûñòðûé ïðÿìîé
äîñòóï îêàçûâàåòñÿ ó íåñæàòûõ ðàñòðîâ. Ïîïûòàåìñÿ ãàðìîíèçèðîâàòü
êîìïðåññèþ è ïðÿìîé äîñòóï è ñôîðìóëèðîâàòü ïðåäëîæåíèÿ, êîòîðûå
ìîãóò ïîìî÷ü ðàçðàáîò÷èêàì ÃÈÑ â îòäåëüíûõ ñëó÷àÿõ ïîâûñèòü êîìï-
ðåññèþ ïðè ñîõðàíåíèè ïðèåìëåìîé ñêîðîñòè ïðÿìîãî äîñòóïà ê ðàñòðàì.
Êðàòêèé îáçîð ìåòîäîâ. Äëÿ ïðÿìîãî äîñòóïà óäîáåí ôîðìàò TIFF, à
òàêæå åãî ðàñøèðåíèå äëÿ ÃÈÑ — GeoTIFF. Â ýòîì ôîðìàòå ìîæíî ãèáêî
ðàñïðåäåëÿòü ðàñòð, çàïèñûâàÿ åãî îòäåëüíûìè ÷àñòÿìè â åäèíîì ôàéëå,
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 119
÷òî ïîçâîëÿåò îðãàíèçîâàòü áûñòðûé ïðÿìîé äîñòóï. Ôîðìàò ïîääåðæè-
âàåò ìíîæåñòâî ìåòîäîâ êîìïðåññèè.
Äëÿ ìàñøòàáèðîâàíèÿ è áûñòðîãî ïðÿìîãî äîñòóïà ïðèìåíÿåòñÿ ôîð-
ìàò MrSID [1], îäíàêî îí îðèåíòèðîâàí íà êîìïðåññèþ ñ ïîòåðÿìè íåïà-
ëèòðîâûõ èçîáðàæåíèé. Îäíèì èç ïðèìåðîâ ðåøåíèÿ ïðîáëåìû áûñòðîãî
äîñòóïà ê ðàçíîîáðàçíûì ðàñòðîâûì äàííûì ÿâëÿåòñÿ òåõíîëîãèÿ ìîçàèê,
ðåàëèçîâàííàÿ â ÃÈÑ «ÎÊλ [5].
Ñðåäè ìåòîäîâ êîìïðåññèè áåç ïîòåðü, èñïîëüçóåìûõ äëÿ 256-öâåòíûõ
ïàëèòðîâûõ ðàñòðîâ, íàèáîëåå ïîïóëÿðíû LZ-ïîäîáíûå [2] ñëîâàðíûå
ìåòîäû.  ïåðâóþ î÷åðåäü ýòî LZW [3] è Deflate [4], âîïëîùåííûå â
ôîðìàòàõ GIF, PNG è TIFF, êîòîðûå îáåñïå÷èâàþò âûñîêóþ ñòåïåíü êîì-
ïðåññèè [5—7]. Èõ íåäîñòàòêè — îòíîñèòåëüíî íåâûñîêàÿ ñêîðîñòü äåêî-
äèðîâàíèÿ è áîëüøèå çàòðàòû ïàìÿòè äëÿ ñëîâàðÿ. Ìåòîäû êîìïðåññèè
áåç ïîòåðü íà îñíîâå êîäèðîâàíèÿ äëèí ïîâòîðîâ (Run Length Encoding —
RLE) èñïîëüçóþòñÿ â ôîðìàòàõ PCX, TGA è äð. [5, 6]. Èõ äîñòîèíñòâî —
âûñîêàÿ ñêîðîñòü äåêîäèðîâàíèÿ, íåäîñòàòîê — ìàëàÿ êîìïðåññèÿ.
Ñëåäóåò óïîìÿíóòü òàêæå ìåòîäû êîìïðåññèè áåç ïîòåðü íà îñíîâå
ïðåîáðàçîâàíèÿ Áàððîóçà—Óèëëåðà [6, 8]. Ýòè ìåòîäû ìîãóò îáåñïå÷èòü
âûñîêóþ êîìïðåññèþ, íî òðåáóþò çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ ðåñóð-
ñîâ. Îíè ðåàëèçîâàíû â íåêîòîðûõ àðõèâàòîðàõ. Èñïîëüçîâàíèå òàêèõ
ìåòîäîâ â ãðàôè÷åñêèõ ôîðìàòàõ ôàéëîâ àâòîðàì ñòàòüè íå èçâåñòíî.
Îñíîâíàÿ ïðîáëåìà ïðè ÷òåíèè ñæàòûõ ðàñòðîâ â ðåæèìå ïðÿìîãî
äîñòóïà ñîñòîèò â ñëåäóþùåì: äëÿ òîãî ÷òîáû ïðî÷èòàòü íóæíûé ïèêñåë,
íåîáõîäèìî äåêîäèðîâàòü âñå ïðåäûäóùèå çàêîäèðîâàííûå ïèêñåëû. Ïðè
ýòîì âûïîëíÿåòñÿ ìíîãî ëèøíèõ âû÷èñëåíèé, ÷òî ñíèæàåò ñêîðîñòü ðàáî-
òû. Ýòî õàðàêòåðíî äëÿ òàêèõ ðåæèìîâ ïðÿìîãî äîñòóïà, êàê ïðîðåæè-
âàíèå ïèêñåëîâ ïðè ïîêàçå ðàñòðà â óìåíüøåííîì âèäå èëè ñêîëüçÿùåå
îêíî ïðè ïîêàçå ÷àñòè ðàñòðà (ñêðîëëèíã).
Îäèí èç ïîäõîäîâ ê ðåøåíèþ ýòîé ïðîáëåìû — íåçàâèñèìîå êîäèðî-
âàíèå îòäåëüíûõ íåáîëüøèõ áëîêîâ ðàñòðà è ñîîòâåòñòâóþùàÿ ïîääåðæêà
â ôàéëîâîì ôîðìàòå. Ìîæíî áûëî áû ïðåäïîëîæèòü, ÷òî â ýòîì ñëó÷àå
íàèáîëåå ïîäõîäÿùèì ÿâëÿåòñÿ ìåòîä JPEG, îðèåíòèðîâàííûé íà áëîêè
ðàñòðà, îäíàêî îí íå ïðèñïîñîáëåí äëÿ ñæàòèÿ ïàëèòðîâûõ èçîáðàæåíèé
áåç ïîòåðü [9]. Ìîæíî èñïîëüçîâàòü ôîðìàò GIF, â êîòîðîì çàëîæåíà
âîçìîæíîñòü ÷åðåññòðî÷íîãî êîäèðîâàíèÿ, íî, ó÷èòûâàÿ ñïåöèôèêó àëãî-
ðèòìà LZW, ýòî íå ïîâûøàåò ñêîðîñòü ïðÿìîãî äîñòóïà â ðåæèìå ñêîëü-
çÿùåãî îêíà, à ïðè ïîêàçå ñ óìåíüøåíèåì ýôôåêòèâíîå ìàñøòàáèðîâàíèå
îãðàíè÷åíî ôèêñèðîâàííîé ÷åðåññòðî÷íîñòüþ. Ïîäîáíûõ îãðàíè÷åíèé
ëèøåí ôîðìàò TIFF.
Âûáåðåì íåçàâèñèìîå êîäèðîâàíèå îòäåëüíûõ ñòðîê. Ìîæíî çàìå-
òèòü, ÷òî â ñòàíäàðòíûõ ôîðìàòàõ íà îñíîâå ìåòîäà RLE ðàñòð îáû÷íî òàê
è êîäèðóåòñÿ. Äåëàåòñÿ ýòî íå äëÿ ïðÿìîãî äîñòóïà, à ïî òîé ïðè÷èíå, ÷òî
Ò. À. Áëèíîâà, Â.Í. Ïîðåâ
120 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
ñïëîøíîå íåïðåðûâíîå RLE-êîäèðîâàíèå âñåãî ðàñòðà íå èìååò ñìûñëà,
òàê êàê ñòåïåíü êîìïðåññèè îò ýòîãî ïðàêòè÷åñêè íå óâåëè÷èâàåòñÿ. Èíàÿ
êàðòèíà íàáëþäàåòñÿ ïðè èñïîëüçîâàíèè LZ-ïîäîáíûõ ìåòîäîâ. Äàæå ÷åðåñ-
ñòðî÷íîå êîäèðîâàíèå âñåãî ðàñòðà óìåíüøàåò ñòåïåíü êîìïðåññèè, à íåçà-
âèñèìîå êîäèðîâàíèå îòäåëüíûõ ñòðîê ìîæåò çíà÷èòåëüíî óìåíüøèòü ñòå-
ïåíü êîìïðåññèè è ñäåëàòü åå ìåíüøåé, ÷åì ïðè èñïîëüçîâàíèè ïðîñòåéøèõ
âàðèàíòîâ RLE. Ïðåèìóùåñòâà ñëîâàðíûõ ìåòîäîâ ïðîÿâëÿþòñÿ òîãäà, êîãäà
â ôîðìèðîâàíèè ñëîâàðÿ ó÷àñòâóþò âñå ïèêñåëû è èõ êîìáèíàöèè.
Ó÷èòûâàÿ èçëîæåííîå, äëÿ îáëåã÷åíèÿ ïðÿìîãî äîñòóïà áûëî âûáðà-
íî íåçàâèñèìîå êîäèðîâàíèå ñòðîê ìåòîäîì RLE. Ïðîâåäåì íåêîòîðûå
óñîâåðøåíñòâîâàíèÿ ìåòîäà RLE, ñîñòîÿùèå â ïîâûøåíèè êîìïðåññèè è,
ïî âîçìîæíîñòè, ñîõðàíåíèè åãî ïîëîæèòåëüíûõ õàðàêòåðèñòèê.
Ââåäåì îáîçíà÷åíèÿ: M — ÷èñëî áèòîâ äâîè÷íîãî êîäà, íåîáõîäèìîå
äëÿ êîäèðîâàíèÿ öâåòà, M = log2 (÷èñëî öâåòîâ); ñëåäóåò ó÷åñòü, ÷òî â íåêîòî-
ðîì èçîáðàæåíèè ìîãóò èñïîëüçîâàòüñÿ íå âñå öâåòà èç 256-öâåòíîé ïàëèòðû,
òîãäà M < 8; C1 — ÷èñëî áèòîâ, íåîáõîäèìîå äëÿ êîäèðîâàíèÿ èíäåêñîâ
ìíîæåñòâà ãëàâíûõ öâåòîâ.
Åñëè ñäåëàòü ñîðòèðîâêó âñåõ öâåòîâ ïàëèòðû ñîãëàñíî ÷àñòîòå èõ
èñïîëüçîâàíèÿ, òî M-áèòíûé êîä 00..00 îçíà÷àåò íîìåð íàèáîëåå ÷àñòî
èñïîëüçóåìîãî öâåòà, êîä 00..01 — íîìåð ñëåäóþùåãî ïî ïîïóëÿðíîñòè è
ò. ä. Áóäåì ñ÷èòàòü, ÷òî êîäåð è äåêîäåð îáðàáàòûâàþò îòäåëüíî ìíîæåñò-
âî èç 2
C1
ãëàâíûõ öâåòîâ. Òîãäà C1 < M. Åñëè èç M áèòîâ âûäåëèòü C1
ìëàäøèõ áèòîâ, òî ýòî è áóäåò èíäåêñ ãëàâíîãî öâåòà. Íàïðèìåð, åñëè C1 =
= 2, òî ýòî îçíà÷àåò ÷åòûðå ãëàâíûõ öâåòà, èíäåêñû êîòîðûõ êîäèðóþòñÿ
êàê 00, 01, 10 è 11 â ïîðÿäêå óìåíüøåíèÿ ÷àñòîò èñïîëüçîâàíèÿ ñîîòâåòñò-
âóþùèõ öâåòîâ.
Ñïîñîá êîäèðîâàíèÿ 1. Èñïîëüçóåì òðè ðàçíîâèäíîñòè êîäîâûõ
ïîñëåäîâàòåëüíîñòåé:
0c...c (âñåãî M áèòîâ) — äëÿ îäèíî÷íûõ ïèêñåëîâ, ó êîòîðûõ ñòàðøèé
áèò öâåòà ðàâåí 0. Îäèíî÷íûå ïèêñåëû öâåòîâ 1c...c áóäóò êîäèðîâàòüñÿ
êàê öåïî÷êà äëèíû 1. Äëÿ êîäèðîâàíèÿ öåïî÷åê ïèêñåëîâ ïðåäóñìîòðèì
òàêèå ïîñëåäîâàòåëüíîñòè:
10n...nc...c — ñíà÷àëà ïðåôèêñ (áèòû 10), ïîòîì N1 áèòîâ êîäà äëèíû
öåïî÷êè (áèòû n). Çàâåðøàþò ïîñëåäîâàòåëüíîñòü C1 áèòîâ c, êîòîðûå
îçíà÷àþò èíäåêñ ãëàâíîãî öâåòà;
11n...nc...c — ñíà÷àëà ïðåôèêñ (áèòû 11), ïîòîì N2 áèòîâ äëèíû öåïî÷-
êè è äàëåå M áèòîâ öâåòà.
Ïðèìå÷àíèå. Ïîäðàçóìåâàåòñÿ, ÷òî êîäèðîâàíèå îäèíî÷íîãî ïèêñåëà
ãëàâíîãî öâåòà ìîæåò áûòü ïðåäñòàâëåíî è â âèäå öåïî÷êè äëèíû 1 â
ñëó÷àå, êîãäà ñîîòâåòñòâóþùèé êîä êîðî÷å M.
Ñâîéñòâà òàêîãî ñïîñîáà êîäèðîâàíèÿ îïðåäåëÿþòñÿ ïàðàìåòðàìè C1,
N1 è N2. Åñëè ïîñòàâèòü çàäà÷ó äîñòèæåíèÿ íàèìåíüøåãî ÷èñëà áèòîâ äëÿ
Íåêîòîðûå ñïîñîáû êîäèðîâàíèÿ ðàñòðîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 121
êîäèðîâàííûõ ñòðîê (èëè èíûõ áëîêîâ ðàñòðà), òî îêàçûâàåòñÿ, ÷òî ðàçëè÷-
íûì ñòðîêàì áóäóò ñîîòâåòñòâîâàòü ðàçíûå çíà÷åíèÿ ïàðàìåòðîâ. Ìîæíî
íàõîäèòü íåêîòîðûå îïòèìàëüíî óñðåäíåííûå çíà÷åíèÿ ýòèõ ïàðàìåòðîâ,
íàïðèìåð, ïóòåì ñòàòèñòè÷åñêîãî àíàëèçà ðåçóëüòàòîâ êîäèðîâàíèÿ ìíîãèõ
èçîáðàæåíèé ðàçíûõ òèïîâ, â ðåçóëüòàòå çàôèêñèðîâàâ êîíêðåòíûå ÷èñëîâûå
çíà÷åíèÿ ïàðàìåòðîâ C1, N1, N2, è ïîëó÷åííûå çíà÷åíèÿ ðåêîìåíäîâàòü äëÿ
âíåäðåíèÿ â íåêîòîðîì ôàéëîâîì ôîðìàòå èëè â ïðîòîêîëå îáìåíà.
Îäíàêî áîëåå öåëåñîîáðàçíûì ïðåäñòàâëÿåòñÿ èíîé ïóòü, à èìåííî: âîç-
ëîæèòü âñå èññëåäîâàíèÿ îïòèìàëüíûõ ïàðàìåòðîâ íà êîäåð—óñòðîéñòâî
(èëè ïðîãðàììó), àíàëèçèðóþùåå ðàñòð â õîäå çàïèñè åãî â ôàéë. Ïðè êîäè-
ðîâàíèè îòäåëüíûìè ñòðîêàìè êîäåð íàõîäèò îïòèìàëüíûå çíà÷åíèÿ C1, N1
è N2 èíäèâèäóàëüíî äëÿ êàæäîé ñòðîêè êîíêðåòíîãî ðàñòðà. Åñëè ïðîäîë-
æàòü äàëåå òàêîå êîäèðîâàíèå, òî ìîæíî ïîëó÷èòü êîäåð, íàõîäÿùèé äëÿ
êàæäîé ñòðîêè íå òîëüêî îïòèìàëüíûå ïàðàìåòðû îäíîãî ñïîñîáà êîäèðîâà-
íèÿ, íî è èñïîëüçóþùèé íåñêîëüêî ðàçëè÷íûõ ñïîñîáîâ, âûáèðàÿ èç íèõ òîò,
êîòîðûé äàñò ìèíèìóì áèòîâ äëÿ êîäèðîâàíèÿ òåêóùåé ñòðîêè.
Ñïîñîá êîäèðîâàíèÿ 2. Èñïîëüçóåì êîäîâûå ïîñëåäîâàòåëüíîñòè
äâóõ òèïîâ:
0c...c — äëÿ îäèíî÷íûõ ïèêñåëîâ ïðîèçâîëüíîãî öâåòà, ñíà÷àëà ïðå-
ôèêñ (0), à çàòåì M áèòîâ öâåòà;
1c...cnn...n — äëÿ öåïî÷åê ïèêñåëîâ ãëàâíîãî öâåòà, ñíà÷àëà ïðåôèêñ
(1), çàòåì C1 áèòîâ èíäåêñà ãëàâíîãî öâåòà (òàê ìîæíî çàêîäèðîâàòü
òîëüêî 2
Ñ1
íàèáîëåå ïîïóëÿðíûõ öâåòîâ). Çàâåðøàþò êîäîâóþ ïîñëåäî-
âàòåëüíîñòü áèòû äëèíû öåïî÷êè (nn...n). Êàæäîìó i-ìó ãëàâíîìó öâåòó
ñîîòâåòñòâóåò îïðåäåëåííîå ÷èñëî áèòîâ n – Ni.
Ïðèìåð êîäèðîâàíèÿ öåïî÷åê ãëàâíûõ öâåòîâ äëÿ C1 = 2:
100nnn — N0 = 3 äëÿ íàèáîëåå ïîïóëÿðíîãî öâåòà (èíäåêñ 00);
101nnnnnnn — N1 = 7 äëÿ ãëàâíîãî öâåòà ñ èíäåêñîì 01;
101nnnn — N2 = 4 äëÿ ãëàâíîãî öâåòà ñ èíäåêñîì 10;
111nnnnn — N3 = 5 äëÿ ãëàâíîãî öâåòà ñ èíäåêñîì 11.
Ñïîñîá êîäèðîâàíèÿ 2 çàäàåòñÿ ìíîæåñòâîì ïàðàìåòðîâ C1 è Ni (i = 0 �
�2
C1
– 1). Âûáîð îïòèìàëüíûõ çíà÷åíèé ýòèõ ïàðàìåòðîâ îñóùåñòâëÿåò êîäåð.
Îäíî èç îòëè÷èé âòîðîãî ñïîñîáà êîäèðîâàíèÿ îò ïåðâîãî çàêëþ-
÷àåòñÿ â òîì, ÷òî ïðîèñõîäèò êîäèðîâàíèå îäèíî÷íûõ ïèêñåëîâ íå áîëåå
÷åì (M + 1)-ðàçðÿäíûì êîäîì, íåçàâèñèìî îò öâåòà. Òàê ó÷èòûâàåòñÿ âå-
ðîÿòíîñòü áîëüøîãî ÷èñëà îäèíî÷íûõ ïèêñåëîâ âòîðîñòåïåííûõ öâåòîâ.
Ñëåäóåò çàìåòèòü, ÷òî ñïîñîá 2 ó÷èòûâàåò íå òîëüêî ïðåîáëàäàíèå
ïèêñåëîâ íåêîòîðûõ öâåòîâ íàä äðóãèìè, íî è òî, ÷òî îäèí èç ãëàâíûõ
öâåòîâ ìîæåò áûòü ïðåäñòàâëåí ïðåèìóùåñòâåííî êîðîòêèìè öåïî÷êàìè
ïèêñåëîâ, à äðóãîé — äëèííûìè.  îòëè÷èå îò òðàäèöèîííîãî RLE-êîäè-
ðîâàíèÿ öåïî÷åê, êîãäà ñíà÷àëà èäåò äëèíà öåïî÷êè, à çàòåì öâåò, â êîäî-
âûõ ïîñëåäîâàòåëüíîñòÿõ ñïîñîáà 2 ñíà÷àëà èäåò öâåò, à çàòåì äëèíà
Ò. À. Áëèíîâà, Â.Í. Ïîðåâ
122 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
öåïî÷êè. Ýòî íóæíî äëÿ òîãî, ÷òîáû äåêîäåð áûë ñïîñîáåí ïðàâèëüíî
ðàñøèôðîâàòü êîä äëèíû öåïî÷êè.
 ñïîñîáå 2 ÷èñëî íà÷àëüíûõ áèòîâ (1c...c) îäèíàêîâî äëÿ êîäîâ öåïî-
÷åê âñåõ ãëàâíûõ öâåòîâ. Âàðèàíòîì ñïîñîáà 2 ÿâëÿåòñÿ ñëåäóþùèé ñïî-
ñîá, â êîòîðîì öâåòà êîäèðóþòñÿ ïðåôèêñàìè ðàçíîãî ðàçìåðà, ïðè÷åì
äëèíà ïðåôèêñà çàâèñèò îò ÷àñòîòû èñïîëüçîâàíèÿ öâåòà. Åãî ìîæíî ðàñ-
ñìàòðèâàòü êàê ñî÷åòàíèå RLE è ìåòîäà Õàôôìàíà [10].
Ñïîñîá êîäèðîâàíèÿ 3. Èñïîëüçóþòñÿ òàêèå êîäîâûå ïîñëåäîâàòåëü-
íîñòè:
0c...c — äëÿ îäèíî÷íûõ ïèêñåëîâ ïðîèçâîëüíîãî öâåòà, ñíà÷àëà ïðå-
ôèêñ (0), à çàòåì M áèòîâ öâåòà;
1p...pnn...n — äëÿ öåïî÷åê ïèêñåëîâ, ñíà÷àëà ïðåôèêñ (1p...p), ïîòîì
áèòû äëèíû öåïî÷êè (nn...n). Êàê è â ñïîñîáå 2, êàæäîìó i-ìó ãëàâíîìó
öâåòó ñîîòâåòñòâóåò îïðåäåëåííîå ÷èñëî (Ni) áèòîâ n.
Êîäèðîâàíèå ïðåôèêñíûìè êîäàìè ñïîñîáîì 3 ðàññìîòðèì íà òàêîì
ïðèìåðå:
0c...c — îäèíî÷íûå ïèêñåëû;
10nn...n — öåïî÷êà öâåòà 0 (N0 áèòîâ n);
110nn...n — öåïî÷êà öâåòà 1 (N1 áèòîâ n);
1110nn...n — öåïî÷êà öâåòà 2 (N2 áèòîâ n);
1111nn...n —öåïî÷êà öâåòà 3 (N3 áèòîâ n).
 äàííîì ïðèìåðå äëèíà êîäà öåïî÷êè öâåòà 0 ìåíüøå, ÷åì äëÿ
ñïîñîáà 2, îäíàêî äëÿ öâåòîâ 2 è 3 êîäû öåïî÷åê äëèííåå. Ïàðàìåòðû
ñïîñîáà êîäèðîâàíèÿ 3: ÷èñëî ãëàâíûõ öâåòîâ è ìíîæåñòâî çíà÷åíèé NI.
Ïðè êîäèðîâàíèè íåêîòîðûõ ñòðîê ðàñòðà ìîãóò âîçíèêíóòü òàêèå
ïðîáëåìû. Äîïóñòèì, ñòðîêà ñîäåðæèò ìíîãî ïèêñåëîâ ãëàâíîãî öâåòà â
âèäå öåïî÷åê ðàçíîé äëèíû. Íàïðèìåð, åñòü ìíîãî öåïî÷åê äëèíû 4 è
öåïî÷åê äëèíû 100 îäíîãî öâåòà. Êàêîå ÷èñëî áèòîâ (n...n) äëèíû öåïî÷êè
ïðèíÿòü â êà÷åñòâå îïòèìàëüíîãî? Åñëè âçÿòü äâà áèòà, òî öåïî÷êè äëèíû
100 äîëæíû êîäèðîâàòüñÿ êàê 25 êîäîâ öåïî÷åê äëèíû 4. À åñëè âûáðàòü
ñåìü áèòîâ, òî äëÿ êîðîòêèõ öåïî÷åê — ýòî èçáûòî÷íûé êîä. Ìîæíî
ïðèíÿòü â êà÷åñòâå îïòèìàëüíîãî íåêîòîðîå ñðåäíåå çíà÷åíèå, íî ïðè ýòîì
ïîÿâÿòñÿ ëèøíèå áèòû äëÿ êîðîòêèõ öåïî÷åê è îäíîâðåìåííî áóäåò ïðî-
èñõîäèòü ìíîãîêðàòíîå êîäèðîâàíèå äëèííûõ. ×àñòè÷íî ýòó ïðîáëåìó
ðåøàåò ñïîñîá 1, â êîòîðîì äëÿ öåïî÷åê ãëàâíîãî öâåòà ìîãóò áûòü
èñïîëüçîâàíû ëèáî N1 ëèáî N2 áèòîâ äëèíû. Îäíàêî â íåêîòîðûõ ñëó÷àÿõ
ëó÷øå èñïîëüçîâàòü ñëåäóþùèé ñïîñîá êîäèðîâàíèÿ.
Ñïîñîá êîäèðîâàíèÿ 4. Èñïîëüçóåì êîäîâûå ïîñëåäîâàòåëüíîñòè:
0c...c — äëÿ îäèíî÷íûõ ïèêñåëîâ ïðîèçâîëüíîãî öâåòà, ñíà÷àëà ïðå-
ôèêñ (0), à çàòåì M áèòîâ öâåòà;
1c...cxx...x — äëÿ öåïî÷åê ïèêñåëîâ ãëàâíîãî öâåòà, ñíà÷àëà ïðåôèêñ
(1), çàòåì C1 áèòîâ äëÿ èíäåêñà ãëàâíîãî öâåòà. Çàâåðøàþò êîäîâóþ
Íåêîòîðûå ñïîñîáû êîäèðîâàíèÿ ðàñòðîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 123
ïîñëåäîâàòåëüíîñòü áèòû äëèíû öåïî÷êè (xx...x). Êàæäîìó çíà÷åíèþ èí-
äåêñà ãëàâíîãî öâåòà (áèòû c...c) ñîîòâåòñòâóåò ôîðìàò êîäà äëèíû öå-
ïî÷êè, êîòîðûé âûáèðàåòñÿ èç òðåõ ôîðìàòîâ: à, á, â.
Ôîðìàò à:
1c...cnn...n — N1 áèòîâ n äëèíû öåïî÷êè (N1 = 0 � 15).
Ôîðìàò á:
1c...c0nn...n— N1 áèòîâ n (N1 = 0 � 15);
1c...c1nn...n — N2 áèòîâ n (N2 = N1+1�N1+16).
Ôîðìàò â:
1c...c0nn...n — N1 áèòîâ n (N1= 0 � 7);
1c...c10nn...n — N2 áèòîâ n (N2 = N1+1 �N1+8);
1c...c11nn...n — N3 áèòîâ n (N3= N2+1 � N2+8).
Âûáîð îïòèìàëüíûõ çíà÷åíèé ïàðàìåòðîâ Ñ1, N1, N2, N3 è ôîðìàòà
êîäà äëèíû äëÿ êàæäîé ñòðîêè ðàñòðà âîçëàãàåòñÿ íà êîäåð.
Ñëåäóÿ ñóùåñòâóþùèì òðàäèöèÿì ïî êîìïðåññèè èíôîðìàöèè, íàáîð
ðàññìîòðåííûõ âûøå ñïîñîáîâ 1—4 íàçîâåì RLE-ÁÏ.
Íà îñíîâå ñïîñîáîâ 1— 4 áûëè ðàçðàáîòàíû è äðóãèå âàðèàöèè êîäè-
ðîâàíèÿ äëèí ïîâòîðîâ. Äàííûå ñïîñîáû êîäèðîâàíèÿ è èõ âàðèàöèè
çàëîæåíû â ôàéëîâûé ôîðìàò, äëÿ êîòîðîãî áûëè ñîçäàíû àäàïòèâíûé
êîäåð è äåêîäåð. Ôàéëîâûé ôîðìàò áûë ñíà÷àëà èñïîëüçîâàí â ïðåïîäà-
âàòåëüñêîé äåÿòåëüíîñòè, à çàòåì è â ìîçàèêàõ äëÿ ÃÈÑ.
Ðåçóëüòàòû àíàëèçà ñïîñîáîâ êîäèðîâàíèÿ. Áûëî èññëåäîâàíî íå-
ñêîëüêî òûñÿ÷ ôàéëîâ, îáðàáîòàííûõ ðåàëüíîé ÃÈÑ, êîòîðàÿ èñïîëüçóåò
êîäåð äëÿ êîìïðåññèè ðàñòðîâûõ èçîáðàæåíèé òèïà ÷åðòåæåé, ïëàíîâ,
êàðò è äð. Ñîçäàííàÿ ïðîãðàììà-àíàëèçàòîð ìîæåò îòîáðàæàòü ïàðàìåòðû
ñïîñîáîâ êîäèðîâàíèÿ, èñïîëüçîâàííûõ äëÿ êàæäîãî ôàéëà, à òàêæå ñòà-
òèñòèêó äëÿ ãðóïï ôàéëîâ.
Äëÿ êàæäîé ñòðîêè êîäåð âûáèðàåò ñïîñîá êîäèðîâàíèÿ, äàþùèé
íàèìåíüøåå ÷èñëî áèòîâ êîäà. Ñóùåñòâóþò ðàñòðû, äëÿ êîòîðûõ äîìèíè-
ðóåò îäèí ñïîñîá. Îäíàêî åñòü èçîáðàæåíèÿ, äëÿ îïòèìàëüíîãî êîäèðî-
âàíèÿ êîòîðûõ èñïîëüçîâàíû âñå ñïîñîáû (1—4). Îêàçàëîñü, ÷òî ïî âíåø-
íåìó âèäó èçîáðàæåíèÿ ïî÷òè íåâîçìîæíî ñïðîãíîçèðîâàòü, êàêîé èç
ñïîñîáîâ êîäåð èçáåðåò îïòèìàëüíûì. Ïîýòîìó çäåñü íå ïðèâåäåíû êîíê-
ðåòíûå îáðàçöû èçîáðàæåíèé.
Àíàëîãè÷íàÿ ñèòóàöèÿ íàáëþäàåòñÿ íà óðîâíå ïàðàìåòðîâ êîäîâ. Äà-
æå äëÿ òåõ èçîáðàæåíèé, äëÿ êîòîðûõ äîìèíèðóåò îäèí ñïîñîá, ðàçíûå
ñòðîêè çàêîäèðîâàíû ñ ðàçëè÷íûìè ïàðàìåòðàìè êîäîâ. Îäíàêî òåîðåòè-
÷åñêè ìîãóò ñóùåñòâîâàòü èçîáðàæåíèÿ, âñå ñòðîêè êîòîðûõ ëó÷øå âñåãî
êîäèðîâàòü îäíèì ñïîñîáîì ñ îäèíàêîâûìè ïàðàìåòðàìè êîäîâ (òðè-
âèàëüíûé ñëó÷àé — èçîáðàæåíèå âåðòèêàëüíûõ ïîëîñ).
Ïðèâåäåì ïðèìåðû îòäåëüíûõ ïàðàìåòðîâ ñïîñîáîâ êîäèðîâàíèÿ. Ðàñ-
ñìîòðèì ñïîñîá 1, äëÿ êîòîðîãî åñòü òðè ïàðàìåòðà: C1, N1 è N2. Äëÿ
Ò. À. Áëèíîâà, Â.Í. Ïîðåâ
124 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
àíàëèçà îãðàíè÷èì äèàïàçîí çíà÷åíèé C1, N1 è N2 òàêèìè ÷èñëàìè: C1 îò
0 äî 7, N1 îò 1 äî 8 è N2 îò 1 äî 8. Ðåçóëüòàòû àíàëèçà êîäèðîâàíèÿ ãðóïïû
ôàéëîâ ïîêàæåì â âèäå ãèñòîãðàììû ðàñïðåäåëåíèÿ çíà÷åíèé ïàðàìåòðîâ.
Ïîñêîëüêó ïàðàìåòðîâ òðè, òî ãèñòîãðàììà äîëæíà áûòü ÷åòûðåõìåðíîé.
×òîáû íàãëÿäíåå ïðåäñòàâèòü ðåçóëüòàòû, ïðåîáðàçóåì ãèñòîãðàììó â
äâóìåðíóþ. Çàïèøåì òðîéêó ïàðàìåòðîâ (C1, N1, N2) â âèäå äâîè÷íîãî
÷èñëà K = ccc.nnnppp, ãäå ccc — áèòû Ñ1, äàëåå — òî÷êà äðîáíîé ÷àñòè,
çàòåì nnn — áèòû N1, ppp — áèòû N2. Òàêèì îáðàçîì, 512 êîìáèíàöèé
çíà÷åíèé ïàðàìåòðîâ C1, N1 è N2 ïðåäñòàâëåíû ÷èñëàìè îò íóëÿ äî ñåìè.
Íà ãèñòîãðàììå, ïîêàçàííîé íà ðèñ 1, à, ñòîëáèêè îçíà÷àþò ïðîöåíò îò
îáùåãî ÷èñëà ñòðîê, çàêîäèðîâàííûõ ñïîñîáîì 1. Êàê âèäèì, ñàìûé èñïîëü-
çóåìûé (18 %) êîä (C1, N1, N2) = (0, 5, 2), ñ íèì êîíêóðèðóþò êîäû (0,6,2),
(1,5,2), è (2,5,1).  àáñîëþòíîì âûðàæåíèè çíà÷åíèÿ C1, N1 è N2 ðàñïðå-
äåëèëèñü, êàê ïîêàçàíî íà ðèñ. 1, á.
Åñëè àíàëèçèðîâàòü ðàñïðåäåëåíèå çíà÷åíèé ïàðàìåòðîâ â îäíîì
èçîáðàæåíèè èç äàííîé ãðóïïû, òî îíî ìîæåò áûòü, íàïðèìåð, òàêèì, êàê
ïîêàçàíî íà ðèñ. 2, à. Çäåñü ñàìûé èñïîëüçóåìûé (21 %) êîä (3, 2, 6). Äëÿ
ýòîãî èçîáðàæåíèÿ ðàñïðåäåëåíèå çíà÷åíèé C1, N1 è N2 â àáñîëþòíîì
âûðàæåíèè ïîêàçàíî íà ðèñ. 2, á. Êàê âèäèì, åñëè ôèêñèðîâàòü íåêîòîðóþ
òðîéêó çíà÷åíèé (C1, N1, N2) êàê îïòèìàëüíóþ è ïûòàòüñÿ êîäèðîâàòü ñ
äàííûìè ïàðàìåòðàìè âñå èçîáðàæåíèÿ íåêîòîðîé ãðóïïû ïîäîáíûõ
èçîáðàæåíèé, òî ýòî ìîæåò ïðèâåñòè ê ñíèæåíèþ êîìïðåññèè äëÿ êàæäîãî
êîíêðåòíîãî îáðàçöà äàæå èç ýòîé ãðóïïû.
Íåêîòîðûå ñïîñîáû êîäèðîâàíèÿ ðàñòðîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 125
0
18 %
0
1
2
3
4
5
6
7
0 1 2 3 4 5 6 7 K
Ñ1
68658
60753
35956
13185
6971
692
445
16
1
2
3
4
5
6
7
8
N1
10070
6482
7393
16640
66019
50060
29443
569
1
2
3
4
5
6
7
8
N2
57449
80503
24719
10070
7080
2681
4010
164
à
á
Ðèñ. 1. Ãèñòîãðàììà ïàðàìåòðîâ C1, N1 è N2 (à) è ðàñïðåäåëåíèå èõ çíà÷åíèé (á) äëÿ
ïåðâîé ãðóïïû èçîáðàæåíèé (166 ôàéëîâ)
Ïîñêîëüêó èçëîæèòü çäåñü â ïîëíîì îáúåìå ðåçóëüòàòû ïðîâåäåííîãî
àíàëèçà ïðåäëîæåííûõ ñïîñîáîâ êîäèðîâàíèÿ çàòðóäíèòåëüíî, ïðèâåäåì
òîëüêî âûâîä: èñêàòü ôèêñèðîâàííûå îïòèìàëüíûå çíà÷åíèÿ ïàðàìåòðîâ
êîäèðîâàíèÿ ïðàêòè÷åñêè áåññìûñëåííî. Èíäèâèäóàëüíî äëÿ êàæäîé
ñòðîêè ðàñòðà ýòî äîëæåí äåëàòü êîäåð. Ïðè ðàçðàáîòêå êîäåðà äîñòàòî÷íî
ó÷åñòü îáùèé äèàïàçîí çíà÷åíèé ïàðàìåòðîâ êîäîâ.
Ïðèâåäåì ñðàâíèòåëüíûå äàííûå î ñòåïåíè êîìïðåññèè K äëÿ ôàéëîâ,
ïðåäñòàâëåííûõ â ðàçëè÷íûõ ôîðìàòàõ. Ñïîñîá êîìïðåññèè RLE-ÁÏ áûë
ðåàëèçîâàí â ôîðìàòå GGF4. Çà åäèíèöó ïðèíÿòî îòñóòñòâèå êîìïðåññèè
(ôîðìàò BMP). Ñòåïåíü êîìïðåññèè îöåíèâàëàñü îòíîøåíèåì ðàçìåðà
ôàéëîâ BMP ê ðàçìåðó ôàéëîâ èíûõ ôîðìàòîâ. Äëÿ êàæäîé èç äâóõ ãðóïï
ôàéëîâ (óïîìÿíóòîé âûøå ïåðâîé è âòîðîé, ñîñòîÿùåé èç äâóõ ñîòåí
ôàéëîâ) íàõîäèëè ìèíèìàëüíóþ Kmin, ìàêñèìàëüíóþ Kmax è ñðåäíþþ Kñð
ñòåïåíè êîìïðåññèè (ñì. òàáëèöó). Ñðåäíÿÿ ñòåïåíü êîìïðåññèè äëÿ ãðóï-
ïû ôàéëîâ ðàâíà îòíîøåíèþ ñóììàðíîãî îáúåìà ôàéëîâ BMP ê ñóììàð-
íîìó îáúåìó ôàéëîâ èññëåäóåìîãî ôîðìàòà.
Êàê âèäíî èç òàáëèöû, RLE-ÁÏ ëó÷øå, ÷åì òðàäèöèîííûå ìåòîäû
RLE (â ôîðìàòàõ PCX è TGA). Ïðè ñðàâíåíèè ïðåäëàãàåìîãî ñïîñîáà ñî
ñëîâàðíûìè LZ-ïîäîáíûìè ìåòîäàìè ïîëó÷åíû ïðèáëèçèòåëüíî îäèíàêî-
âûå ðåçóëüòàòû. Òàê, ó 50 % èññëåäîâàííûõ èçîáðàæåíèé ðàçìåðû ôàéëîâ,
ïðåäñòàâëåííûõ â ôîðìàòå GGF4, ìåíüøå, ÷åì ðàçìåðû ñîîòâåòñòâóþùèõ
ôàéëîâ GIF. Ïî ñòåïåíè êîìïðåññèè ôîðìàò GGF4 íåìíîãî óñòóïàåò
ôîðìàòó PNG.
Ò. À. Áëèíîâà, Â.Í. Ïîðåâ
126 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
0
0
1
2
3
4
5
6
7
0 1 2 3 4 5 6 7
Ñ1
21 %
1
105
356
1278
438
1
1
1
2
3
4
5
6
7
8
N1
751
906
63
87
211
161
1
1
2
3
4
5
6
7
8
N2
9
395
95
509
618
525
29
à
á
Ðèñ. 2. Ãèñòîãðàììà ïàðàìåòðîâ C1, N1 è N2 (à) è ðàñïðåäåëåíèå èõ çíà÷åíèé (á) äëÿ
îäíîãî èçîáðàæåíèÿ èç ïåðâîé ãðóïïû
Ðàññìàòðèâàÿ ñêîðîñòíûå õàðàêòåðèñòèêè RLE-ÁÏ, ìîæíî çàìåòèòü
àñèììåòðèþ: âðåìÿ êîäèðîâàíèÿ ñóùåñòâåííî (5—10 ðàç) ïðåâûøàåò âðå-
ìÿ äåêîäèðîâàíèÿ. Ýòî çàâèñèò îò ÷èñëà âàðèàíòîâ êîäà è èõ ïàðàìåòðîâ,
àíàëèçèðóåìûõ àäàïòèâíûì êîäåðîì ïðè îáðàáîòêå êîíêðåòíîãî èçîáðà-
æåíèÿ. (Ïðè ðàáîòå ñ ðàñòðîâûìè äàííûìè â ÃÈÑ ÷àùå ïðèõîäèòñÿ äåêîäè-
ðîâàòü ôàéëû, êîäèðîâàíèå âûïîëíÿåòñÿ îäèí ðàç ïðè çàïèñè ôàéëà).
Ñïîñîáû êîäèðîâàíèÿ, èñïîëüçóåìûå â RLE-ÁÏ, íåðàâíîçíà÷íû ïî
âû÷èñëèòåëüíîé ñëîæíîñòè. Êàæäîìó êîíêðåòíîìó èçîáðàæåíèþ ñîîò-
âåòñòâóåò îïðåäåëåííûé íàáîð ñïîñîáîâ êîäèðîâàíèÿ. Ïîýòîìó ñêîðîñòü
äåêîäèðîâàíèÿ äëÿ ðàçëè÷íûõ èçîáðàæåíèé ìîæåò áûòü íåîäèíàêîâà. Ñ
îäíîé ñòîðîíû, äåêîäèðîâàíèå RLE-ÁÏ ñëîæíåå, ÷åì RLE (äëÿ ôàéëîâ
PCX è TGA), ñ äðóãîé ñòîðîíû, êîäîâûìè ïîñëåäîâàòåëüíîñòÿìè RLE-ÁÏ
ìîãóò áûòü ïðåäñòàâëåíû áîëåå äëèííûå öåïî÷êè ïèêñåëîâ. Ìíîãîå çàâè-
ñèò îò ðåàëèçàöèè ìåòîäîâ êîìïðåññèè, îäíàêî ýòîò âîïðîñ âûõîäèò çà
ðàìêè äàííîé ñòàòüè. Çäåñü îãðàíè÷èìñÿ ñëåäóþùèì íàáëþäåíèåì. Ïðè
ðàáîòå ñîîòâåòñòâóþùèõ ïðîãðàììíûõ ñðåäñòâ íà ïåðñîíàëüíûõ êîìïüþ-
òåðàõ íûíåøíåãî ïîêîëåíèÿ, âðåìÿ ïîëíîãî äåêîäèðîâàíèÿ ôàéëîâ, ñæàòûõ
ìåòîäîì RLE-ÁÏ, íà 5—20 % áîëüøå, ÷åì ïðè èñïîëüçîâàíèè ìåòîäà RLE
PCX, è íà 20—30 % ìåíüøå, ÷åì ïðè èñïîëüçîâàíèè LZW GIF.
 ôîðìàòå ôàéëîâ GGF4 ïðåäóñìîòðåíà ïîääåðæêà ðåæèìà ïðÿìîãî
äîñòóïà. Ýòî îçíà÷àåò, ÷òî â ýòîì ðåæèìå îöåíêè ñêîðîñòè ìîãóò ñóùåñò-
âåííî îòëè÷àòüñÿ îò ïðèâåäåííûõ âûøå. Ïðÿìîé äîñòóï ïîäðàçóìåâàåò
áûñòðûé ïåðåõîä îò íà÷àëà ôàéëà äî çàäàííîãî áëîêà äàííûõ, ìèíóÿ
ðàñïàêîâêó íåíóæíûõ äàííûõ. Òàê, íàïðèìåð, â ôîðìàòå PCX íå çàëîæåíà
ïîääåðæêà ïðÿìîãî äîñòóïà, ïîýòîìó ïðîñìîòð ñîäåðæèìîãî âñåãî ðàñòðà
ðàçìåðàìè 10000�10000 ïèêñåëîâ íà ýêðàíå ìîíèòîðà ìîæåò ïîòðåáîâàòü
â äåñÿòêè ðàç áîëüøåãî âðåìåíè, ÷åì ïðîñìîòð òîãî æå ðàñòðà â ôîðìàòå
GGF4, íåñìîòðÿ íà òî ÷òî ñêîðîñòü äåêîäèðîâàíèÿ PCX ìîæåò áûòü âûøå.
Íåêîòîðûå ñïîñîáû êîäèðîâàíèÿ ðàñòðîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 127
Ôîðìàò
ôàéëà
Ìåòîä
êîìïðåññèè
Ãðóïïà ôàéëîâ
² ²²
K1,ñð K1,min K1,max K2,ñð K2,min K2,max
BMP — 1 1 1 1 1 1
GIF LZW 4,9 2,6 27,4 3,4 1,7 7,5
PCX RLE 3,1 1,5 10,5 2,4 1,4 4,7
PNG Deflate 5,3 2,9 32,3 3,7 2 7,5
TGA RLE 3,3 1,4 14 2,4 1,5 4,6
GGF4 RLE-ÁÏ 4,7 2,4 23,8 3,3 1,8 6,4
Òàê æå è ïîêàç îòäåëüíûõ ôðàãìåíòîâ â ñêîëüçÿùåì îêíå ìîæåò áûòü â
äåñÿòêè ðàç áûñòðåå â ôîðìàòå GGF4 ïî ñðàâíåíèþ ñ PCX (ýòî çàâèñèò îò
ïîëîæåíèÿ ôðàãìåíòà îòíîñèòåëüíî íà÷àëüíîé òî÷êè ðàñòðà).
Êîäèðîâàíèå RLE-ÁÏ ïî ñòåïåíè êîìïðåññèè ñðàâíèìî ñ LZW GIF è
ïîçâîëÿåò îðãàíèçîâàòü ïðÿìîé äîñòóï, ÷òî ïðîáëåìàòè÷íî äëÿ LZ-ïîäîá-
íûõ ìåòîäîâ.
Òàêèì îáðàçîì, ïðåäëîæåííûå ÷åòûðå ñïîñîáà êîäèðîâàíèÿ, ñîâîêóï-
íîñòü êîòîðûõ íàçâàíà RLE-ÁÏ, ïîçâîëÿþò ïîâûñèòü ñòåïåíü êîìïðåññèè
ìåòîäà RLE. Êîäèðîâàíèå RLE-ÁÏ ìîæíî ðåêîìåíäîâàòü äëÿ ýëåêòðîí-
íûõ ðàñòðîâûõ êàðò, ïðèìåíÿåìûõ â ãåîèíôîðìàöèîííûõ ñèñòåìàõ.
The problems of compression increase when encoding the 256-coloured palette images are
considered. The necessity of direct access to raster data for the geographic information systems is
taken into account. The description and efficiency estimate for developed encoding models are
presented.
1. http://www.lizardtech.com.
2. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression //IEEE Transac-
tions on Information Theory. — 1977.
3. Welch T. A Technique for High-Performance Data Compression //Computer. — June. —1984.
4. Deutch P. DEFLATE Compressed Data Format Specification version 1.3.// RFC 1951,
Aladdin Enterprises, May, 1996.
5. Áëèíîâà Ò. À., Ïîðåâ Â. Í. Êîìïüþòåðíàÿ ãðàôèêà. — Êèåâ : Þíèîð, 2005. — 520 ñ.
6. Âàòîëèí Ä., Ðàòóøíÿê À., Ñìèðíîâ Ì., Þêèí Â. Ìåòîäû ñæàòèÿ äàííûõ. — Ì. : —
Äèàëîã-ÌÈÔÈ, 2002. — 384 ñ.
7. PNG (Portable Network Graphics) Specification Version 1.0. Massachusetts Institute of
Technology. — 1996.
8. Burrows Ì., Wheeler D. J. A block-sorting lossless data compression algorithm. Technical
Report 124, Digital SRC, Palo Alto, 1994.
9. Wallace G. K. The JPEG still picture compression standard //Communication of ACM.—
1991. — Vol. 34, ¹ 4.
10. Huffman D. A. A method for the construction of minimum redundancy codes //Proc. of
IRE.— 1952. — Vol. 40. — Ð. 1098—1101.
Ïîñòóïèëà 27.10.06;
ïîñëå äîðàáîòêè 05.04.07
ÁËÈÍÎÂÀ Òàòüÿíà Àëåêñàíäðîâíà, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð. êàô. âû÷èñëèòåëüíîé
òåõíèêè Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà Óêðàèíû «ÊÏÈ».  1979 ã. îêîí÷èëà
Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — âûñîêîïðîèçâîäèòåëüíûå
ïàðàëëåëüíûå âû÷èñëèòåëüíûå ñèñòåìû, êîäèðîâàíèå èíôîðìàöèè.
ÏÎÐÅ Âèêòîð Íèêîëàåâè÷, êàíä. òåõí. íàóê, äîöåíò Èí-òà çåìëåóïîðÿäî÷åíèÿ è èíôîðìà-
öèîííûõ òåõíîëîãèé.  1981 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ
èññëåäîâàíèé — êîìïüþòåðíàÿ ãðàôèêà, ãåîèíôîðìàöèîííûå ñèñòåìû.
Ò. À. Áëèíîâà, Â.Í. Ïîðåâ
128 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-101556 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T16:58:24Z |
| publishDate | 2008 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Блинова, Т.А. Порев, В.Н. 2016-06-04T19:22:15Z 2016-06-04T19:22:15Z 2008 Некоторые способы кодирования растров в геоинформационных системах / Т.А. Блинова, В.Н. Порев // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 119-128. — Бібліогр.: 10 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101556 681.327 Рассмотрены вопросы повышения компрессии при кодировании 256-цветных палитровых изображений. Учтена необходимость прямого доступа к растровым данным для геоинформационных систем. Даны описание и оценка эффективности разработанных способов кодирования. Розглянуто питання підвищення компресії при кодуванні 256-кольорових палітрових зображень. Враховано необхідність прямого доступу до растрових даних для геоінформаційних систем. Дано опис і оцінку ефективності розроблених способів кодування. The problems of compression increase when encoding the 256-coloured palette images are considered. The necessity of direct access to raster data for the geographic information systems is taken into account. The description and efficiency estimate for developed encoding models are presented. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Применение методов и средств моделирования Некоторые способы кодирования растров в геоинформационных системах Some Raster Encoding Methods in Geographic Information Systems Article published earlier |
| spellingShingle | Некоторые способы кодирования растров в геоинформационных системах Блинова, Т.А. Порев, В.Н. Применение методов и средств моделирования |
| title | Некоторые способы кодирования растров в геоинформационных системах |
| title_alt | Some Raster Encoding Methods in Geographic Information Systems |
| title_full | Некоторые способы кодирования растров в геоинформационных системах |
| title_fullStr | Некоторые способы кодирования растров в геоинформационных системах |
| title_full_unstemmed | Некоторые способы кодирования растров в геоинформационных системах |
| title_short | Некоторые способы кодирования растров в геоинформационных системах |
| title_sort | некоторые способы кодирования растров в геоинформационных системах |
| topic | Применение методов и средств моделирования |
| topic_facet | Применение методов и средств моделирования |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101556 |
| work_keys_str_mv | AT blinovata nekotoryesposobykodirovaniârastrovvgeoinformacionnyhsistemah AT porevvn nekotoryesposobykodirovaniârastrovvgeoinformacionnyhsistemah AT blinovata somerasterencodingmethodsingeographicinformationsystems AT porevvn somerasterencodingmethodsingeographicinformationsystems |