Кодирование графических изображений

Существуют разные способы кодирования графических изображений (векторное, фрактальное, растровое), но при выводе на экран все виды кодов графических изображений преобразуются в растровый код.

Каждая точка (пиксель) получает свой цифровой код цвета. Значение кода зависит от числа бит (этот параметр называют иногда глубиной цвета), выделенного для кодирования палитры цветов.

Если цвет точки кодируется одним битом, то рисунок может быть черно-белым (двухцветным) и коды цвета: 0 и 1, если четырьмя битами, то палитра шестнадцатицветная с кодами 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15.

Количество цветов палитры определяется возможным количеством кодов и равно 2^N, где N - число бит, выделенных под код цвета палитры.

Пример. Пусть имеется черно - белый рисунок 7х 8 точек. Каждая точка кодируется 1 битом, содержащим цвет: 0 - белый, 1 - черный.

Двоичный код рисунка:   100 0001 110 0011 111 1111 101 1101 100 1001 111 0111 011 0110 001 1100

Шестнадцатиричный код:   7F 5D 1C

 

Пример. Пусть рисунок выполнен в серых оттенках и палитра состоит из 4 цветов: 0 - белый, 1 - светло-серый, 10 -темносерый, 11-черный. Для кодирования точки требуется 2 бита, а для 56 точек рисунка требуется 2x56= 112 бит, или 112/8= 14 байт

Двоичный код рисунка: 10 00 00 00 00 00 10 10 10 00 00 00 10 10 11 11 11 11 11 11 11 11 00 11 11 11 00 11 11 00 00 11 00 00 11 01 11 11 00 11 11 01 00 01 11 00 11 01 00 00 00 11 11 11 00 00

Шестнадцатиричный код:

 

В 256 цветной палитре необходимо 8 бит для кодирования одного цвета точки. Для рисунка 100x100 точек потребуется объем памяти:

8 бит х 100 х 100=80 000 бит, или 10000 байт, или 10000/ 1024 = 9,8 кб.

Задание 6. Закодировать графическое изображение двухцветной палитрой и записать его в двоичном и шестнадцатиричном кодах.

\

 

Задание 7. Рисунок имеет размеры а*b точек. Подсчитать объем памяти в байтах занимаемый при растровом кодировании изображения с цветной палитрой:

1)	а=300	b=350	N=16	6) a=600	b=300	n=16
2)	а=100	b=50	N=1024	7) a=100	b=180	n=1024
3)	а=300	b=200	N=128	8) a=150	b=300	n=128
4)	а=400	b=300	N=4	9) a=240	b=130	n=512
5)	а=120	b=200	n=512	10)a=700	b=150	n=8

 

Задание 8. На мониторах Х" установлено оптимальное разрешение (14":640x480 пиксель, 15": 800х600 пиксель, 17":1024х768 пиксель, 19":1280xl024 пиксель). Изображение занимает 1/k часть экрана. Какой объем видеопамяти в килобайтах будет занимать растровый код изображения с 65536 цветной палитрой?

1)	X=15”	k=2	6)	X=15”	k=8
2)	X=19”	k=15	7)	X=19”	k=20
3)	X=17”	k=6	8)	X=14”	k=3
4)	X=14”	k=4	9)	X=17”	k=5
5)	X=17”	k=10	10)	X=14”	k=2

1. Подсчитать число бит для кодирования одной точки.

2. Подсчитать число точек экрана

3. Подсчитать число точек рисунка.

4. Вычислить объем растрового кода рисунка.

Задание 9. Растровый код занимает X Кб. Какую примерную часть экрана при разрешении 1024х768 пикселей будет занимать рисунок при 63536 цветной палитре.

1)	Х = 8 Кб	6)	Х = 4 Кб
2)	X = 48 Кб	7)	Х = 12 Кб
3)	Х = 6 Кб	8)	Х = 64 Кб
4)	X = 45 Кб	9)	Х = 1 Кб
5)	Х = З Кб	10)	Х = 96 Кб

1. Подсчитать число бит для кодирования одной точки.

2. Подсчитать число точек экрана.

3. Подсчитать число точек рисунка.

4. Подсчитать какую часть экрана занимает рисунок.

Вопросы для самоконтроля:

1. Что такое кодирование информации в общем смысле?

2. Каково место кодирования среди процессов обработки информации?

3. Какие коды называются двоичными? Приведите примеры.

4. Какой код используется для кодирования букв латинского алфавита буквами
персонального компьютера?

5. Какие коды используются в вычислительной технике для кодирования букв
русского алфавита?

6. Как кодируется графическая информация, если изображение черно-белое
(цветное)?

ЛАБОРАТОРНАЯ РАБОТА №2. «ИНФОРМАЦИЯ И ЭНТРОПИЯ»

Цель работы:изучить теоретическое понимание энтропии, ее свойства и практическое применение при решении задач.

Задачи:

1.Изучить теоретическое понимание энтропии.

2.Изучить свойства энтропии.

3.Выполнить практические задания по теме (решение задач).

4.Оформить отчет по лабораторной работе и представить преподавателю.

Краткая теория по теме:

Рассмотрим ко­личество информации с точки зрения возможности передачи данных сообщений оптимальным образом.

Основные положения:

1) количество информации не зависит от способа ее передачи;

2) длина сообщений об одном и том же факте определяется числом качественных признаков вторичного алфавита, но количество инфор­мации от длины этого сообщения не зависит;

3) количество информации зависит от числа сообщений, если каж­дое из них устраняет неизвестность о передаваемом факте.

Число сообщений N, которое можно получить, комбинируя m символов алфавита по n элементов в сообщении

(1)

Как видим, число сообщений N, а вместе с ним и количество передаваемой информации находятся в экспоненциальной зависимос­ти от количества элементов в сообщении. Поэтому N нельзя непосред­ственно использовать как меру количества информации.

Комбинируя два символа по 3 в сообщении можно передать восемь сообщений, по 4 – шестнадцать, по 5 – тридцать два и т.д.

В 1929 г. американский ученый Р. Хартли предложил в качестве меры количества информации принять логарифм числа возможных последовательностей символов:

(2)

Основание логарифма зависит от выбранной единицы количества информации. В выражениях, где могут быть использованы двоичные, десятичные и натуральные логарифмы, основание логарифма не ставится. При использовании двоичного логарифма информация измеряется в битах.

Пусть для составления сообщения имеется k знаков, обладающих m качественными признаками и p_i – вероятность появления каждого качественного признака или символа. Шенноном было получено соотношение для определение среднего количества информации в сообщении с произвольными вероятностями появления значений символов:

(3)

При равновероятностных символах, т.е. при p_i = 1/m, формула Шеннона переходит в формулу Хартли:

(4)

Чем больше априорная неопределенность, тем больше количество информации получается при снятии ее. В этом смысле неопределенность является удобной меры оценки количества информации.

В теории информации мерой неопределенности является энтропия – удельное количество информации, приходящееся на один элемент сообщения (на букву первичного алфавита). Для сообщения из k элементов эта величина равна

(5)

и называется средней энтропией сообщения.

В случае одинаковой вероятности появления любого из m элементов сообщения

(6)

Таким образом, если при передаче информации не было информационных потерь, то количество информации на символ сообщения будет точно равно Н, а количество информации при передаче символов .

Следует делать различие между понятиями «количества информации» и «объем информации».

Количество информации вычисляется относительно первичного алфавита, а объем информации – относительно вторичного алфавита.

Объем информации зависит от длины сообщения во вторичном алфавите n и равен

(7)

k – число символов первичного алфавита в сообщении

n – число символов вторичного алфавита для кодирования 1 символа первичного алфавита.

Энтропия - это мера неопределенности некоторого опыта, исход которого зависит от выбора одного элемента из мно­жества исходных. Множество исходных элементов называется выбороч­ным пространством. Вероятности нахождения элементов исходного множества в том или ином состоянии есть числа положительные, а сумма их равна 1 (в противном случае результат опыта не относился бы к полной группе событий).

Выборочное пространство и его вероятностные характеристики представляют собой ансамбль сообщений. Для дискретного ансамбля вероятность события равна сумме вероятностей элементов выборочного пространства, содержащихся в этом событии.

Ансамбль сообщений на выходе источника будем называть ансамб­лем источника сообщений и обозначать буквой А. Абстрактный алфа­вит, при помощи которого мы представляем исходное множество эле­ментов источника сообщений, обозначается {а₁ , а₂ , ..., а _i,..., а_т }. Веро­ятности появления буквы на выходе источника сообщений обозначим

(8)

В этом случае энтропия источника сообщений и представляет собой неопределенность появления на выходе источ­ника сообщений буквы первичного алфавита.

(9)

Ансамбль сообщений на входе приемника будем называть ансамб­лем приемника сообщений и обозначать буквой В. Для того чтобы отличить переданные и принятые сигналы, абстрактный алфавиту в котором представлен ансамбль приемника сообщений, обозначается (b₁ , b_г, ..., b_i , ...,b_m,}, а соответствующие вероятности - p(b₁); p(b₂),... .... р (b_i), ..., р (b_т).

Энтропия приемника сообщений.

(10)

и представляет собой неопределенность появления на входе приемника буквы после ее появления на выходе источника сообщений. Если в ка­нале связи не происходит потерь информации, то всегда буква % соответствует букве b₁ а₂ - b₂ и т. д. При этом Н (А) = Н (В). Понятие энтропии используется не только при передаче сообщений. Энтропия широко применяется для описания состояния механических и термодинамических систем, для изучения свойств алфавитов раз­личных языков, при исследовании экономических систем и т. д.

При исследовании свойств энтропии наибольший интерес представ­ляет ее зависимость от числа m возможных признаков (качеств) и ве­роятности р_i появления в сообщении элемента с i-м признаком.

Энтропия характеризует меру неопределенности совокупности со­бытий, составляющих полную группу сумма вероятностей появления отдельных событий должна быть равна единице, т.е. .

Если m = i = 1, т.е. передается сообщение с одним i-м признаком и вероятность его появление p_i=1, то

(11)

(12)

Это очевидно, так как заранее известно, что будет передано сообщение с i-м признаком и при его получении ничего нового мы не узнаем, т. е. получим нулевую информацию. Если сообщение заранее известно, то энтропия минимальна и равна 0.

Если вероятность появления i-гo признака в ансамбле сообщений равна нулю, то слагаемое с этим признаком принимает вид неопреде­ленности типа нуль, умноженный на бесконечность.

Итак, энтропия есть величина вещественная и имеет экстремум. Так как логарифмы правильных дробей отрицательны, то энтропия опыта с конечным числом исходов всегда положительна.

Пример. Какова мощность алфавита, с помощью которого записано сообщение, содержащее 2048 символов, если его объем составляет 1,25 Кбайта.

Арифметически переведем информационный объем сообщения в биты:

I =1,25*1024*8= 10 240 бит.

Определить количество бит, приходящееся на один символ:

10 240 бит : 2 048 = 5 бит.

По формуле (1) определить количество символов в алфавите:

N = 2^I = 2⁵

лг= 32.

Задача 1. Какова мощность алфавита, с помощью которого записано сообщение, содержащее 2048 символов, если его объем составляет 1/512 часть одного мегабайта?

Задача 2.Пользователь компьютера, хорошо владеющий навыками ввода информации с клавиатуры, может вводить в минуту 100 знаков. Мощность алфавита, используемого в компьютере, равна 256. Какое количество информации в байтах может ввести пользователь в компьютер за 1 минуту?

Задача 3. Система оптического распознавания символов позволяет преобразовывать отсканированные изображения страниц документа в текстовый формат со скоростью 4 страницы в минуту и использует алфавит мощностью 65536 символов. Какое количество информации будет нести текстовый документ после 5 минут работы приложения, страницы которого содержат 40 строк по 50 символов?

Задача 4. Тексты, составленные из 32 букв украинского алфавита, передаются по телетайпу при помощи двух качественных признаков: наличия и отсутствия таковой посылки. Чему равно количество информации, приходящееся на одну принятую букву, на k принятых букв?

Задача 5. Определить объем и количество информации при передаче русского текста из 350 букв при помощи пятизначного двоичного кода.

Задача 6. Алфавит состоит из букв A,B,C,D. Вероятности появления буквы равны соответственно ; ; . Определить количество информации на символ сообщения, составленного из такого алфавита.

Задача 7. Определить объем и количество информации при следующих исходных условиях:

А) алфавит равновероятностный. Символы вторичного алфавита комбинируются в равномерные кодовые комбинации числом символов .

Б) первичный алфавит содержит 8 букв . Буквы алфавита встречаются в сообщении с вероятностями: ; ; ; ; .

Кодовые комбинации во вторичном алфавите равномерные .

В) первичные алфавит состоит из 5 букв , которые встречаются с равными вероятностями в тексте, а и вторичные сообщения имеют одинаковую длину;

Г) первичный алфавит равновероятный , а вторичные сообщения построены из кодовых комбинаций, имеющих среднюю длину 6 двоичных символов.

Задача 8. На вычислительный центр с периферийного объекта необходимо передать определенную экономическую информацию, содержащуюся в таблицах с различными показателями. Определить максимально возможный объем информации, которым может быть загружен канал связи, если таблиц 100 шт., таблицы имеют 64 клетки, цифры, содержащиеся в таблицах не более, чем трехзначные, а код, в котором передаются сообщения – пятизначный двоичный.

Задача 9. Рассмотрим некоторую ситуацию. В коробке имеется 50 шаров. Из них 40 белых и 10 черных. Очевидно, вероятность того, что при вытаскивании "не глядя" попадется белый шар больше, чем вероятность попадания черного. Можно сделать заключение о вероятности события, которые интуитивно понятны. Провести количественную оценку вероятности для каждой ситуации.

Задача 10. Ресурсы человеческого мозга позволяют обрабатывать информацию со скоростью около 16 бит/с. Какое количество информации перерабатывает человек в течение жизни (принять среднюю продолжительность жизни за 60 лет).

Задача 11. Система имеет N равновероятных состояний. Количество информации в системе (о ее состоянии) равно 5 бит. Чему равна вероятность одного состояния? Если состояние системы неизвестно, то каково количество информации в системе? Если известно, что система находится в состоянии номер 8, то чему равно количество информации?

Задача 12. Некоторая система может находиться в четырех состояниях с вероятностями: в первом (худшем) - 0,1, во втором и третьем (среднем) - 0,25, в четвертом (лучшем) - 0,4. Чему равно количество информации (неопределённость выбора) в системе?

Задача 13. Чему равна энтропия системы, состоящей:

А) из двух элементов, каждый из которых может с равной вероятностью находиться в двух состояниях?

Б) из трех элементов, каждый из которых может с равной вероятностью находиться в четырех состояниях?

Задача 14. Чему равна энтропия системы, состояние которой описывается дискретной величиной со следующим распределением вероятностей состояний

	0,1	0,2	0,3	0,4

 

Задача 15. Чему равна энтропия сообщений: «Сейчас Луна упадет на Землю», «Сейчас Луна не упадет на Землю»?

Задача 16. На вычислительном центре постоянная информация хранится в 32768 стандартных ячейках. Сколькими способами можно передать сведения о том, из какой ячейки необходимо извлечь информацию? Чему равно количество информации в каждом отдельном случае? Какое геометрическое расположение ячеек в хранилище позволит передавать эту информацию минимальным количеством качественных признаков?

Задача 17. Генератор вырабатывает четыре частоты . В шифраторе частоты комбинируются по три в кодовой комбинации. Определить:

А) чему равно максимальное количество сообщений, составленных из этих частот

Б) чему равно количество информации на один символ первичного алфавита?

Вопросы для самоконтроля:

1. Назовите определение понятий информация и количество информации?

2. Поясните цель и основные задачи измерения количества информации.

3. Поясните формулы Р. Хартли и К. Шеннона для определения количества информации?

4. В чем заключается процесс кодирования информации?

5. Перечислите способы кодирования информации?

6. Дайте определение понятию «энтропия»?

ЛАБОРАТОРНАЯ РАБОТА №3. «ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ»

Цель:изучить позиционные системы счисления.

Задачи:

1. Изучить позиционные системы счисления.

2. Изучить правила записи любого числа в позиционной системе счисления.

3. Изучить взаимное преобразование чисел в различных системах счисления.

Краткие теоретические сведения:

В позиционных системах счисления количественный эквивалент (значение) цифры зависит от ее места (позиции) в записи числа.

В системе счисления с основанием q (q-ичная система счисления) единицами разрядов служат последовательные степени числа q, иначе говоря, q единиц какого-либо разряда образуют единицу следующего разряда. Для записи чисел в q-ичной системе счисления требуется различных цифр (0, 1, …q-1).

В позиционной системе счисления число в развернутой форме может быть представлено в следующем виде:

(1)

где: А- само число;

q — основание системы счисления;

a_i—цифры, принадлежащие алфавиту данной системе счисления;

n — число целых разрядов числа;

m — число дробных разрядов числа.

Примером позиционной системы счисления является арабская десятичная система, в которой основание Р=10, для изображения используется 10 цифр от 0 до 9;

Пример. Десятичное число в развернутой форме запишется так:

Существует множество позиционных систем счисления. Наиболее распространенные приведены в таблице:

Основание	Система счисления	Знаки
	Двоичная	0,1
	Троичная	0,1,2
	Четвертичная	0,1,2,3
	Пятиричная	0,1,2,3,4
	Восьмиричная	0,1,2,3,4,5,6,7
	Десятичная	0 – 9
	Двенадцатиричная	0 – 9,А,В
	Шестнадцатиричная	0 – 9, A,B,C,D,E,F

В информатике нашли применение двоичная, восьмеричная, десятичная и шестнадцатеричная.

Соответствие чисел в основных системах счисления

Таблица 3.1

десятичная	Шестнадцатеричная	Восьмеричная	двоичная
	A
	B
	C
	D
	E
	F