ЛекцииММ3 (Курс электронных лекций), страница 4

- шум.

Задача фильтрации – определить функцию f.

Если обе координаты всех точек входят в окрестность не превышающую координаты текущей строки, то такая стратегия называется каузальной. Если все превышают или недобирают – некаузальная, если часть превышает, часть – нет, то полукаузальная.

Выходной эффект определяется линейной комбинацией входных данных.

i1, j1- определённое количество элементов, по которым осуществляется работа.

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

Постоянные считаются переменными и по ним берётся производная. Эти производные должны быть равны 0.

Число неизвестных > числа уравнений => решений будет бесконечное множество => необходимо провести дополнительную дифференциацию по всем остальным коэффициентам a, считая их переменными.

Полученное уравнение является линейным относительно искомых коэффициентов i, j. Число неизвестных в этом уравнении определяется количеством точек в окрестности. Т.о. получается уравнение Винера-Хопфера.

Относительно к теории фильтров является наиболее простым, когда a – некоторые константы, и рассматривается некоторая окрестность и по ней составляется уравнение.

Белый шум – к полученному сигналу прибавляются некоторые пиксели:

Фильтры Колмана (рекуррентные) – на систему коэффициентов оказывает влияние предыстория

1. Графика. Эффекты в растровой графике.

Большинство эффектов формируется с помощью специальной матрицы 3x3.

- матрица эффектов, - ядро матрицы.

а11 а12 а13

а21 а22 а23 - Матрица Эффектов

а31 а32 а33

А11 А12 А13

А21 А22 А32 - Ядро Матрицы

А 31 А32 А33

Алгоритм преобразования:

1. Значение светопикселя ( ) умножается на

2. К результату прибавляется произведение окаймляющих элементов. => получаем цвет. Содержимое заменяется на эту сумму.

Если сумма элементов ядра = 1, то яркость преобразуемого пикселя не изменяется, если >1 – уменьшается.

1. Размывание

Все коэффициенты <1,. Производится для каждого цвета отдельно.

1. Резкость

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

1. Тиснение

=0. Матрица ядра составляется таким образом, что фоновым пикселям (которые не находятся на границе перехода от одного цвета к другому) присваиваются нулевые значения, а нефоновым – ненулевые. Положительные значения заменяются на отрицательные для изменения направления тиснения.

1. Акварелизация

1. Сглаживание цветов изображения. Медианное усреднение цвета в каждой точке. Для каждого пикселя рассматриваются 24 соседних. Все значения помещаются в список и сортируются в порядке возрастания. Пикселю присваивается 13 значение в списке.

2. Каждый пиксель обрабатывается ядром резкости.

1. Графика. Кодирование, методы сжатия, JPEG.

Кодирование разрабатывалось для сжатия телеметрической и звуковой информации.

• С потерями

• Без потерь

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

Алгоритмы без потерь

• RLE

PCX, BMP. Основан на методе повторяющихся символов. Ищется одинаковая цепочка и кодируется следующим образом.

Пр: wwwwwww – исходная последовательность 7w - закодированная

Лучшее сжатие 1/32, среднее ½, худшее 2/1.

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

• LZW (Алгори́тм Ле́мпеля — Зи́ва — Ве́лча) GIF

Основан на том, что ищутся последовательности символов, которые кодируются битами длиной от 8 до 12.

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные)

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

Пр. TOBEORNOTTOBEORTOBEORNOT#

Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5-ти бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают 25 = 32 возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код 32. Начальный словарь будет содержать:

# = 00000

A = 00001

B = 00010

T 20 = 10100

O 15 = 01111

Для ч/б изображений сжатие 1/1000, 5/4, 7/5

Алгоритм Хаффмана (JPEG)

Алгоритм Хаффмана (англ. Huffman) — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее время используется во многих программах сжатия данных

Применяется понятие, что символы появляются с разной вероятностью.

Алгоритм

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

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

3. Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.

4. Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.

Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущего шага и т.д.

Листья имеют различное расстояние от узла. Символы, которые имеют наименьшую вероятность появления, расположены дальше от корня и кодируются более длинной последовательностью символов.

«-» необходимо иметь матрицу вероятностей.

1/8 – лучшее кодирование, 2/3 – среднее

Кодирование с потерями – фронтальное кодирование

JPEG

1/20 ½ 1 - кодирование без потерь

1/200 - с потерями.

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

При сжатии изображение переводится в цветовую систему YCbCr. Далее каналы изображения Cb и Cr, отвечающие за цвет, уменьшаются в 2 раза (по линейному масштабу). Уже на этом этапе необходимо хранить только четверть информации о цвете изображения. Реже используется уменьшение цветовой информации в 4 раза или сохранение размеров цветовых каналов как есть. Количество программ, которые поддерживают сохранение в таком виде, относительно невелико.

Далее цветовые каналы изображения, включая черно-белый канал Y, разбиваются на блоки 8 на 8 пикселей (разбиваются по матрицам по каждой компоненте).

Каждый блок подвергается дискретному косинусному преобразованию.

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

Для каждого составляющего матрица YCbCr составляется своя матрица квантования и осуществляется деление на эту матрицу. Здесь же происходят основные потери и сжатие.

Осуществляется контроль качества. Если матрицу квантования задать очень грубо, то потеря цветности может быть такой большой, что изображения распадутся на отдельные матрицы 8*8.

Полученные коэффициенты упаковываются с помощью кодов Хаффмана

«+» хорошее сжатие для фотографических изображений

«-» медленная программная упаковка и распаковка.

Фрактальное сжатие (1992)

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

1. Графика. Цвет, модели, палитры.

1. RGB (Red Green Blue) – аддитивная модель, 3 цвета – красный, зелёный, синий (256x256x256 ≈ 16,7 млн. цветов). Для чёрно-белого изображения достаточно 256 оттенков. Человеческий глаз воспринимает порядка 5 млн. цветов. Каждый пиксель представляет собой трилистник. (0,0,0) – чёрный, (255,255,255) – белый.

Недостатки:

• Плохая передача пурпурных тонов.

• Трудности при работе с чёрным цветом.

• Не подходит для вывода на бумагу.

[wiki]

RGB (аббревиатура английских слов Red, Green, Blue — красный, зелёный, синий) — аддитивная цветовая модель, описывающая способ синтеза цвета. В российской традиции иногда обозначается как КЗС.

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

Аддитивной она называется потому, что цвета получаются путём добавления (англ. addition) к черному. Иначе говоря, если цвет экрана, освещённого цветным прожектором, обозначается в RGB как (r₁, g₁, b₁), а цвет того же экрана, освещенного другим прожектором, — (r₂, g₂, b₂), то при освещении двумя прожекторами цвет экрана будет обозначаться как (r₁+r₂, g₁+g₂, b₁+b₂).

[/wiki]

1. CMYK (Сyan Magenta Yellow Black) – субстрактивная модель (цвета вычитаются из белого), 4 цвета – голубой, пурпурный, жёлтый и чёрный, используется для вывода на бумагу. CMY – полиграфическая триада.

(0,0,0,0) – белый.

[wiki]

Четырёхцветная автотипия (CMYK: Cyan, Magenta, Yellow, Key colour) — субтрактивная схема формирования цвета, используемая прежде всего в полиграфии для стандартной триадной печати. Схема CMYK, как правило, обладает сравнительно небольшим цветовым охватом.

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