Материал: Курсовая

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра САПР

Курсовая РАБОТА

по дисциплине «Схемотехника»

Тема: Дискретное косинусное преобразование

Санкт-Петербург

2020

ЗАДАНИЕ

на курсовую работу

Аннотация

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

SUMMARY

This course work contains the implementation of a discrete cosine transform of the original image. The first section presents the theoretical foundations of the discrete cosine transform algorithm. The second section presents the program code implemented in the Python language. The third section shows the results of the program

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1. Теоритическая часть 6

1.1. Препроцессинг 6

1.2. Дискретное косинусное преобразование 6

1.3. Округление 8

1.4. Сжатие 9

1.5. Кодирование энтропии 10

14

14

15

ЗАКЛЮЧЕНИЕ 17

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 17

ВВЕДЕНИЕ

Целью выполнения данной курсовой работы является закрепление и углубление теоретических знаний по дисциплине «Схемотехника». Задачей курсового проекта является реализация программы, выполняющей алгоритм дискретного косинусного преобразования. Данный алгоритм применяется в сжатии информации, например, в JPEG и MPEG, и тесно связан с дискретным преобразованием Фурье.

1. Теоритическая часть

1.1. Препроцессинг

Если изображение содержит более одной компоненты, то они кодируются по отдельности. В связи с этим, на данном этапе выполняется перевод графического изображения из его компонентного представления в цветоразностное, яркостное представление (ICT — Irreversible Color Transform). В связи с тем, что человеческий глаз более восприимчив к яркостному сигналу, чем к цветовому, это преобразование позволит добиться больших результатов сжатия при меньших визуальных потерях. Далее будет рассматриваться кодирование одной отдельной компоненты.

Помимо ICT преобразования, на данном этапе исходное изображение разбивается на малые квадратные блоки и выполняется сдвиг основания значений цвета относительно нуля для корректного пространственного представления изображения: [0,2p - 1] -> [-2p-1, 2p-1 - 1]. Эти шаги важны для эффективной работы кодера на следующем этапе.

1.2. Дискретное косинусное преобразование

Являясь ключевым шагом алгоритма сжатия, дискретное косинусное преобразование (далее ДКП) представляет собой разновидность преобразования Фурье и, также как и последнее, имеет обратное преобразование (ОДКП). Если рассматривать изображение как совокупность пространственных волн, где оси X и Y соответствуют ширине и высоте картинки, а по оси Z откладываются значения цвета соответствующих пикселей, то можно перейти от пространственного представления картинки к ее спектральному представлению и обратно. ДКП преобразует матрицу пикселей размера N x N в матрицу частотных коэффициентов соответствующего размера.

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

Из формул видно, что вычисление одного элемента результирующей матрицы требует O(N2) времени, поэтому почти невозможно выполнить преобразование всей матрицы целиком. Группа разработчиков JPEG предложила оптимальный вариант решения этой проблемы: разбивать исходную матрицу на квадраты стандартного размера 8x8 и выполнять преобразование каждого из них. Использование блоков большего размера позволит улучшить качество сжатия, но не до бесконечности, так как слишком мала вероятность того, что сильно отдаленные точки похожи друг на друга.

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

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

1.3. Округление

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

Округлением называется процесс уменьшения объема информации, необходимого для хранения матрицы ДКП, с частичной потерей точности. По стандарту JPEG для этого используется матрица округления (МО). Каждому элементу исходной матрицы ДКП соответствует элемент МО. Результирующая матрица получается делением исходной матрица на МО. При этом низкочастотным значениям в матрице ДКП соответствуют меньшие коэффициенты МО, что позволяет оставлять более значимую, низкочастотную информацию и отбрасывать менее важную высокочастотную. В связи с тем, что низкочастотные компоненты сосредоточены в левом верхнем углу матрицы ДКП, значения МО растут слева направо и сверху вниз.

Результаты округления и качества восстановленного изображения напрямую зависят от выбранной матрицы округления. Стандарт JPEG позволяет использовать любую МО, однако ISO в ходе долгих экспериментальных тестирований разработала набор матриц, позволяющих добиться оптимальных результатов.

1.4. Сжатие

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

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

Рисунок — 1 Порядок обхода матрицы зигзагом

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

1.5. Кодирование энтропии

Энтропийное кодирование – кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности.

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

Различают несколько вариантов кодов:

1) Сопоставление каждому элементу исходной последовательности различного числа элементов результирующей последовательности. Чем больше вероятность появления исходного элемента, тем короче соответствующая результирующая последовательность. Примером могут служить код Шеннона — Фано, код Хаффмана.

2) Сопоставление нескольким элементам исходной последовательности фиксированного числа элементов конечной последовательности. Примером является код Танстола.

3) Другие структурные коды, основанные на операциях с последовательностью символов. Примером является кодирование длин серий.

4) Если приблизительные характеристики энтропии потока данных предварительно известны, может быть полезен более простой статический код, такой как унарное кодирование, гамма-код Элиаса, код Фибоначчи, код Голомба или кодирование Райса.

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

2. Практическая часть

2.1. Разработка VHDL кода схемы

2.2. Описание процесса проектированивя схемы в среде САПР-Active HDL (Aldec)

2.3. Разработка временных диаграмм схем (ТИ в виде графика)

2.4. Разработка схемы подключения

Заключение

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