Алгоритмы сжатия изображения
элективный курс по информатике и икт (10 класс) на тему

Элективный курс «Алгоритмы сжатия изображения».

Методика изучения алгоритмов сжатия изображений

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

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

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

Программа курса состоит из 17 часов и включает лекционные занятия, практические занятия, контрольные занятия и лабораторные работы.

Элективный курс разрабатывался для 10-11 классов информационно-технологического профиля,

Следует отметить, что элективный курс «Алгоритмы сжатия изображения» носит межпредметный характер: расширяет и углубляет знания учащихся по математике и информатике.

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

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

При подготовке курса был проанализирован государственный стандарт среднего полного общего образования по информатике и ИКТ (профильный уровень).

В Государственном образовательном стандарте среднего (полного) общего образования по «Информатике и ИКТ» (профильный уровень) в разделе «Информация и информационные процессы» имеются темы: «Сигнал, кодирование, декодирование, искажение информации», «Дискретное (цифровое) представление текстовой, графической, звуковой информации и видеоинформации», «Язык программирования», «Основные конструкции языка программирования». Тема «Восприятие, запоминание и обработка информации человеком, пределы чувствительности и разрешающей способности органов чувств» выделена курсивом, и это говорит о том, что материал подлежит изучению, но не включается в Требования к уровню подготовки выпускников. Так же в разделе «Технология создания и обработки графической и мультимедийной информации» имеются темы «Форматы графических и звуковых объектов», «Ввод и обработка графических объектов».

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

Чтобы составить представление о степени разработанности темы «Алгоритмы сжатия изображения» в школьном курсе информатики, был проведен анализ учебных программ по информатике для 10-11 классов.

С.А. Бешенков, Е.А. Ракитина «Информатика» (для гуманитарных и естественно-научных профилей).

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

В учебнике С.А. Бешенкова и Е.А. Ракитина «Информатика» 10 класс  в разделе «Компьютер как средство обработки информации» рассматривается представление графической информации. В данной теме ученики знакомятся с растровым и векторным способом представления информации, глубиной цвета и форматами графических файлов. В разделе «Информация и информационные процессы» учащимся даются такие определения как, код, длина кода, коды с постоянной длиной, цели кодирования, матричный принцип дискретизации графического изображения.

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

В данных учебниках не рассматриваются вопросы сжатия графической информации.

В учебнике И.Г. Семакина, Е.К. Хеннера «Информатика» не рассматривается компьютерная графика, за исключением деловой графики и ее реализации в табличном процессоре.

Н.Д. Угринович «Информатика и ИКТ» (базовый и профильный  уровни):

В разделе «Информационные технологии» базового уровня данной программы подробно рассматриваются растровая и векторная графика, форматы графических файлов.

На профильном уровне данной программы в разделе «Информация. Системы счисления» имеются темы «Кодирование текстовой, графической и звуковой информации», «Хранение информации». В разделе «Основы алгоритмизации и объектно-ориентированного программирования» подробно рассматриваются  графические возможности языка Visual Basic.

Ю.А. Шафрин «Информатика и информационные технологии». В разделе «Объектно-ориентированная технология как целостная система содержания образования» данной программы рассматриваются основы растровой и векторной графики.

А.Г. Гейн, А.И. Сенокосов, Н.А. Юнерман «Информатика» (учебное пособие для 10-11 классов общеобразовательных учреждений).

В данном учебнике в разделе «Введение в информатику» рассматривается вопрос о графическом представлении информации, включающий понятия пиксель, графический режим, разрешение, цветовые модели. Уделяется внимание графическим редакторам, основным инструментарием графического редактора. В параграфе «Графическое представление информации. Печать на бумаге и сохранение на диске» даётся понятие о сжатии информации как о способе кодирования, с целью сэкономить память на диске.

Н.В. Макарова «Информатика» 10-11 класс [10]. В    данном    учебнике    не    рассматриваются    вопросы    связанные  c компьютерной графикой и методами сжатия графики.

В.Ф. Ляхович «Информатика» (учебное пособие для 10-11 классов общеобразовательных учреждений).

В разделе «Обработка текстовой и графической информации» ученики знакомятся с элементарными сведениями о представлении графической информации на экране монитора. А также рассматривают вопрос о графических возможностях языка Basic, а именно изучают алгоритмы и программы построения изображений.

В результате может быть сделан вывод, что графическая информация рассматривается в школьном курсе информатики, но не затрагивается вопрос об алгоритмах сжатия изображения в полной мере. Соответственно, целесообразно ввести элективный курс «Алгоритмы сжатия изображения».

Актуальность данного курса заключается в том, что он приведёт к более глубокому пониманию:

1. представления графической информации;
2. необходимости сжатия графической информации с потерями;
3. роли алгоритмов сжатия в оптимальном хранении и быстрой передачи        графической информации;
4. а так же к развитию алгоритмического мышления, способностей к формализации, развитию элементов системного мышления учащихся.

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

Анализ учебных программ и школьных учебников по информатике показал, что тема «Алгоритмы сжатия изображения» в учебной литературе не достаточно раскрыта, что обуславливает необходимость создания электронного учебного пособия в поддержку курса.

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

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

Таким образом, можно выделить следующие задачи курса:

1. Познакомить   с   основными   понятиями   темы,   существующими принципами представления изображений;

2. Расширить знания учащихся о математических основах сжатия графической информации.

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

Таблица

Тематическое планирование

Поурочное планирование

Урок 1: Компьютерная графика

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать сущность и особенности способов представления графической информации;
2. Знать достоинства и недостатки каждого из видов компьютерной графики;
3. Уметь определять наиболее предпочтительный способ представления графической информации для решения конкретной задачи.

Содержание:

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

Контрольные вопросы:

1. Перечислите все виды графики
2. Какая графика устарела и практически не используется на сегодняшний день?
3. В чем преимущества растровой графики?
4. В чем  недостатки растровой графики?
5. В чем преимущества векторной графики?
6. В чем  недостатки векторной графики?
7. Какая графика используется при создании компьютерных игр?

Урок 2:  Цвет и цветовые модели в компьютерной графике

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать взаимосвязь света и цвета;
2. Знать взаимосвязь между глубиной цвета и максимальным количеством цветов;
3. Знать принципы цифрового представления цвета;
4. Знать сущность и особенности цветовых моделей RGB, CMYK, Lab, HSB;
5. Знать способы получения цветовых оттенков на экране и принтере;
6. Уметь определять числовой код представления цвета в режимах RGB и CMYK,

Содержание:

Восприятие цвета человеком. Соотношение между глубиной цвета и количеством возможных оттенков цветов. Понятие цветовой модели. Характеристики цветовых моделей RGB, CMYK, LAB, HSB. Аппаратно-зависимые и аппаратно-независимые цветовые модели.  Аддитивные и субтрактивные цветовые модели. Понятие цветового режима. Виды цветовых режимов. Монохромный режим. Полутоновый режим. 16-цветный режим. Режим индексированных цветов. Режим HighColor и TrueColor.

Контрольные вопросы:

1. Перечислите известные вам цветовые модели.
2. Почему мы видим цвет?
3. В какой цветовой модели цвет объекта складывается из трёх составляющих: красный, зелёный, синий?
4. Какая цветовая модель использует понятия Яркость и Интенсивность?
5. Какая цветовая модель используется при выводе на печать в настольном принтере?
6. В какой цветовой модели цвет складывается из четырёх составляющих: синий, пурпурный, жёлтый, чёрный?
7. Приведите пример аппаратно - независимых цветовых моделей.

Урок 3: Цветовые модели.

Тип урока: урок усвоения навыков и умений.

Цели:

1. Уметь анализировать изменение в изображении при отключении одного из каналов;
2. Применять навыки при использовании цветовых каналов.

Содержание:

Обучающиеся выполняют практическую работу: Настройка цвета.

Контрольные вопросы:

1. Перечислите цветовые модели в Adobe Photoshop.
2. Какой командой изменяются цветовые режимы в Adobe Photoshop?
3. Что такое канал?
4. Почему каналы представляются в градации серого цвета?

Урок 4: Размеры изображений.

Тип урока: урок усвоения навыков и умений.

Цели:

1. Знать характеристики способов представления изображений;
2. Знать формулы, описывающие соотношения между различными характеристиками;
3. Уметь определять физический размер изображения по заданному размеру в пикселях и разрешению;
4. Уметь определять информационный объем изображения.

Содержание:

Единицы измерения размера изображения. Понятие разрешения изображения.

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

Контрольные вопросы:

1. Дайте определение физическому размеру изображения.
2. Как определить информационный объём графического файла?
3. Что такое разрешение?
4. Сколько сантиметров в 1 дюйме?
5. Как увеличение глубины пикселя отразится на размере файла?
6. Что означает величина ppi?
7. Что означает величина dpi?

Урок 5: Сжатие информации.

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать необходимость сжатия информации;
2. Знать основные определения теории сжатия;
3. Понимать актуальность идеи сжатия.

Содержание:

Необходимость сжатия информации. Понятие избыточности, уменьшение избыточности. Основные понятия (архиватор, компрессия, кодер, декодер). Обратимость и необратимость алгоритмов. Определение избыточности в тексте,  изображении и видео. Практическая работа «Частотный анализ букв русского языка».

Контрольные вопросы:

1. Дайте определение архиватора.
2. Что такое кодер?
3. Что такое декодер?
4. Почему люди стремятся сделать запись как можно короче?
5. Дайте определение "избыточности".
6. Что применяется для уменьшения избыточности?
7. Дайте определение компрессии.
8. Дайте определение декомпрессии.
9. Насколько сегодня актуальна идея сжатия данных с точки зрения информатики?
10. Как вы думаете на чем можно экономить при сжатии графических файлов?
11. На чем основано сжатие графической информации?

Урок 6:  Алгоритм Хаффмана.

Тип урока: комбинированный.

Цели:

1. Знать историю создания алгоритмов Шеннона-Фано и Хаффмана;
2. Знать этапы алгоритма Хаффмана;
3. Уметь строить дерево Хаффмана.

Содержание:

История алгоритмов сжатия. Этапы алгоритма Хаффмана. Префиксность. Понятие бинарного дерева. Построение дерева Хаффмана. Декодирование алгоритма.

Контрольные вопросы:

1. Кем было предложена идея использования кодов переменной длины?
2. Что такое "дерево"?
3. Дайте определение "бинарному дереву".
4. Каким свойством обладает код Хаффмана?
5. Что такое префиксность?
6. Что такое вес символа?

Урок 7: Особенности сжатия графической информации.

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать особенности сжатия графической информации;
2. Знать назначение сжатия графических данных;
3. Знать свойства графических данных, обуславливающих высокую степень сжатия;
4. Знать характеристики и основные классы изображений;
5. Знать классификацию приложений, использующих алгоритмы компрессии.

Содержание:

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

Контрольные вопросы:

1. Почему алгоритмы сжатия текстовой информации оказываются       несостоятельными в применении к графики?
2. Приведите примеры избыточности в цифровых изображениях.
3. Что такое корреляция пикселов?
4. Приведите пример изображения, которое будет очень хорошо сжиматься любым методом компрессии.
5. Приведите пример изображения которое нельзя сжать никаким методом.
6. Приведите основные различия между текстом и графическими изображениями.
7. Что понимается под классом изображения?

Урок 8:  Алгоритмы сжатия изображений.

Тип урока: урок усвоения новых знаний.

Цели:

1. Познакомить с основными алгоритмами сжатия изображения;
2. Рассмотреть основные требования приложений к алгоритмам компрессии;
3. Рассмотреть критерии сравнения алгоритмов.

Содержание:

Алгоритмы сжатия изображений с потерями и без потерь. Требования приложений к алгоритмам сжатия. Критерии сравнения алгоритмов.

Контрольные вопросы:

1. Приведите пример алгоритма сжатия изображения без потерь.
2. Приведите пример алгоритма сжатия изображения с потерями.
3. Какими свойствами изображений мы можем пользоваться, создавая алгоритм компрессии?
4. Что такое редактируемость?
5. Назовите основные требования приложений к алгоритмам сжатия.
6. Что такое симметричность?
7. Почему высокая степень компрессии, высокое качество изображения, высокая степень компрессии взаимно противоречивы?

Урок 9: Методы обхода плоскости.

Тип урока: комбинированный.

Цели:

1. Рассмотреть задачу обхода плоскости при обработке двухмерных данных;
2. Рассмотреть примеры обхода плоскости;
3. Рассмотреть применение основных обходов плоскости в конкретных алгоритмах.

Содержание:

Постановка задачи. Применение методов в различных алгоритмах сжатия изображений. Зиг-заг сканирование, обход полосами, обход строками и др.

Контрольные вопросы и задания:

1. В каких случаях выгодно использование метода обхода «змейка» (зигзаг-сканирование)?
2. В каком алгоритме применяется метод обхода «змейка» (зигзаг-сканирование)?
3. Какой метод обхода используется в самых распространенных форматах (BMP, TGA…)?
4. Нарисовать пример обхода плоскости столбцами с разворотами.
5. Какой вариант лучше: 3+3+1 или 3+2+2 при обходе квадрата 7*7 полосами шириной 3 с разворотом.

Урок 10: Алгоритмы сжатия изображения без потерь. Алгоритм RLE.

Тип урока: комбинированный.

Цели:

1. Перечислять алгоритмы сжатия без потерь;
2. Знать принцип сжатия алгоритма RLE.

Контрольные вопросы:

1. За счет чего происходит сжатие в алгоритме RLE?
2. На какой класс изображений рассчитан алгоритм RLE?
3. Предложите пример «плохих» изображении для алгоритма RLE. Почему размер сжатого файла больше исходного файла?
4. В каком формате реализован алгоритм RLE?

Домашнее задание: подготовить пример «плохого» изображения в формате .bmp для алгоритма RLE.

Урок 11: Реализация алгоритма RLE на примере программного продукта «Алгоритм RLE».

Тип урока: урок усвоения навыков и умений.

Цели:

1. Познакомиться с интерфейсом программы;
2. Осуществлять сжатие изображения с помощью программы;
3. Осуществлять восстановление изображения;
4. Понимать изменения, происходящие с размером файла при изменении глубины цвета;
5. Уметь рассчитывать коэффициент сжатия.

Содержание:

Учитель предлагает ученикам выполнить практическую работу, используя программный продукт «Алгоритм RLE».

Контрольные вопросы:

1. С какой программой вы познакомились на уроке?
2. Если коэффициент сжатия меньше 1, что можно сказать о таком файле?
3. Что показывает степень сжатия?
4. Что показывает коэффициент сжатия?
5. Размер файла складывается из нескольких составляющих, перечислите эти составляющие.

Урок 12:  Алгоритм LZW.

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать историю развития алгоритмов семейства LZ;
2. Знать принцип сжатия алгоритма LZW.

Содержание:

История семейства алгоритмов LZ. Алгоритм LZW. Сравнительный анализ алгоритма LZW и RLE.

Контрольные вопросы:

1. В честь кого алгоритм был назван LZW?
2. В каком формате изображений используется алгоритм LZW?
3. За счет чего происходит сжатие в алгоритме LZW?
4. Когда будет получено худшее сжатие алгоритмом LZW?
5. На какой класс изображений рассчитан алгоритм LZW?

Урок 13: Алгоритмы сжатия с потерями.

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать проблему архивации с потерями;
2. Знать подходы к сжатию с потерями.

Содержание:

Оценка потерь качества изображений. Подходы к сжатию с потерями: сжатие на основе дискретного косинусного преобразования (ДКП); фрактальные алгоритмы сжатия; сжатие на основе волнового (wavelet) преобразования.

Контрольные вопросы:

1. На чем основывается идея сжатия изображений с потерями?
2. На какой класс изображений ориентированы алгоритмы сжатия с потерями?
3. Что является самой важной мерой оценки потери качества?
4. Приведите примеры критериев оценки потерь качества.
5. Какие подходы к сжатию изображений с потерями существуют на сегодняшний день?

Урок 14: Этапы алгоритма сжатия JPEG.

Тип урока: комбинированный

Цели:

1. Знать этапы сжатия JPEG;
2. Знать формулу ДКП;
3. Понимать за счет чего осуществляется сжатие.

Содержание:

Этапы сжатия (подготовка, ДКП, квантование, вторичное сжатие). Формула ДКП, назначение преобразования. Возможные проблемы реализации. Возможные пути реализации. Важность ДКП в алгоритме сжатия JPEG.

Контрольные вопросы:

1. На какой класс изображений рассчитан алгоритм JPEG?
2. Назовите характерные особенности алгоритма JPEG?
3. За счет чего происходит сжатие изображения в алгоритме JPEG?
4. Перечислите положительные  стороны алгоритма.
5. Назовите отрицательные стороны алгоритма.
6. Почему JPEG не рекомендуется использовать в полиграфии?

Урок 15: Фрактальное сжатие.

Тип урока: комбинированный.

Цели:

1. Знать основную идею алгоритма фрактального сжатия;
2. Знать этапы построения алгоритма.

Содержание:

Идея метода фрактального сжатия. Система итерируемых функций (IFS). Построение алгоритма. Оценка потерь и методы их регулирования.

Контрольные вопросы:

1. На какой класс изображений рассчитан алгоритм фрактального сжатия?
2. Назовите характерные особенности алгоритма.
3. Что такое IFS?
4. Назовите наиболее известные изображения, полученные с помощью IFS.
5. Почему фрактальное сжатие занимает много времени?
6. Что делать если алгоритм не может подобрать для какого-то фрагмента изображения подобный ему?

Урок 16: Рекурсивно (волновой) алгоритм.

Тип урока: урок усвоения новых знаний.

Цели:

1. Знать в чем заключается идея wavelеt-сжатия;

Контрольные вопросы:

1. Как переводится с английского wavelet?
2. На какие изображения ориентирован алгоритм?
3. В чем заключается идея алгоритма?
4. Назовите достоинства алгоритма.
5. В чем отличие wavelet-сжатия от алгоритма JPEG и фрактального?
6. Какова степень сжатия алгоритма?
7. Назовите характерные особенности алгоритма.

Урок 17: Итоговое занятие.

Тип урока: урок контроля полученных знаний, умений, навыков.

Цели:

1. Знать тенденции развития алгоритмов сжатия последних лет;
2. Уметь анализировать алгоритмы сжатия.

Содержание:

Сравнительный анализ алгоритмов, рассмотренных в процессе изучения элективного курса. Тенденции развития алгоритмов. Выполнение итогового теста.

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