Материал: 1 мод ответы мво

1. Преобразование Фурье.

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

Преобразование Фурье функции {\displaystyle f}вещественной переменной является интегральным и задаётся следующей формулой:

Операция преобразования Фурье математически записывается следующим образом:

где  - символ прямого преобразования Фурье.

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

На рис. 1 представлено типичное изображение спектра непериодического сигнала.

Рис. 1

Отметим следующие особенности спектра непериодической функции :

1. Спектр непериодической функции времени непрерывен;

2. Область допустимых значений аргумента спектра

3. Действительная часть спектра – четная функция частоты, мнимая часть спектра – нечетная функция, что позволяет использовать одну половину спектра

Преобразование Фурье обратимо, то есть, зная Фурье-изображение, можно определить исходную функцию – оригинал. Соотношение обратного преобразования Фурье имеет следующий вид:

или в сокращенной записи , где  - символ обратного преобразования Фурье. Заметим, что временная функция имеет преобразование Фурье тогда и только тогда, когда:

• функция однозначна, содержит конечное число максимумов, минимумов и разрывов;

• функция абсолютно интегрируема, то есть

Обратное преобразование Фурье возможно только в том случае, если все полюсы  - левые.

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

Пример:

Найдем частотный спектр дельта-функции.

,

так как при 

,

а при   и

.

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

Рис. 2

2. Кривые Безье.

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

Виды кривых Безье:

Кривая Безье задаётся опорными точками. Их может быть две, три, четыре или больше. Например:

По двум точкам: По трём точкам: По четырём точкам:

Если вы посмотрите внимательно на эти кривые, то «на глазок» заметите:

1. Точки не всегда на кривой. Это совершенно нормально, как именно строится кривая мы рассмотрим чуть позже.

2. Степень кривой равна числу точек минус один. Для двух точек – это линейная кривая (т.е. прямая), для трёх точек – квадратическая кривая (парабола), для четырёх – кубическая.

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

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

Основная ценность кривых Безье для рисования – в том, что, двигая точки, кривую можно менять, причём кривая при этом меняется интуитивно понятным образом.

Математика

У кривых Безье есть математическая формула.

Координаты кривой описываются в зависимости от параметра t⋲[0,1]

• Для двух точек:

P = (1-t)P₁ + tP₂

• Для трёх точек:

P = (1−t)²P₁ + 2(1−t)tP₂ + t²P₃

• Для четырёх точек:

P = (1−t)³P₁ + 3(1−t)²tP₂ +3(1−t)t²P₃ + t³P₄

Вместо P_i нужно подставить координаты i-й опорной точки (x_i, y_i).

Эти уравнения векторные, то есть для каждой из координат:

• x = (1−t)²x₁ + 2(1−t)tx₂ + t²x₃

• y = (1−t)²y₁ + 2(1−t)ty₂ + t²y₃

Вместо x₁, y₁, x₂, y₂, x₃, y₃ подставляются координаты трёх опорных точек, и в то время как t пробегает множество от 0 до 1, соответствующие значения (x, y) как раз и образуют кривую.

Итого

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

Мы рассмотрели два определения кривых:

1. Через математическую формулу.

2. Через процесс построения де Кастельжо.

Их удобство в том, что:

• Можно легко нарисовать плавные линии вручную, передвигая точки мышкой.

• Более сложные изгибы и линии можно составить, если соединить несколько кривых Безье.

Применение:

• В компьютерной графике, моделировании, в графических редакторах. Шрифты описываются с помощью кривых Безье.

• В веб-разработке – для графики на Canvas или в формате SVG. Кстати, все живые примеры выше написаны на SVG. Фактически, это один SVG-документ, к которому точки передаются параметрами. Вы можете открыть его в

3. Jpeg алгоритм сжатия изображений.

JPEG — один из самых новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений [1]. Оперирует алгоритм областями 8х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам (см. формулы ниже) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении.

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — Международной организации по стандартизации. Название алгоритма читается ['jei'peg]. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

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

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

Как работает алгоритм

Итак, рассмотрим алгоритм подробнее. Пусть мы сжимаем 24-битное изображение.

Шаг 1.

Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV).

В нем Y — яркостная составляющая, а Cr, Cb — компоненты, отвечающие за цвет (хроматический красный и хроматический синий). За счет того, что человеческий глаз менее чувствителен к цвету, чем к яркости, появляется возможность архивировать массивы для Cr и Cb компонент с большими потерями и, соответственно, большими коэффициентами сжатия. Подобное преобразование уже давно используется в телевидении. На сигналы, отвечающие за цвет, там выделяется более узкая полоса частот.

Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить с помощью матрицы перехода:

Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу.

Шаг 2.

Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП — по 8 бит отдельно для каждой компоненты. При больших коэффициентах сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y — как и в первом случае, а для компонент Cr и Cb матрицы набираются через строчку и через столбец. Т.е. из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При этом, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в два раза. Мы можем поступать так благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается несильно.

Шаг 3.

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

В упрощенном виде это преобразование можно представить так:

где

Шаг 4.

Производим квантование. В принципе, это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантования q[u,v] (далее МК).

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

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

С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента gamma потери в низких частотах могут быть настолько велики, что изображение распадется на квадраты 8х8. Потери в высоких частотах могут проявиться в так называемом “эффекте Гиббса”, когда вокруг контуров с резким переходом цвета образуется своеобразный “нимб”.

Шаг 5.

Переводим матрицу 8x8 в 64-элементный вектор при помощи “зигзаг”-сканирования, т.е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...

Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце — высоким.

Шаг 6.

Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где “пропустить” является счетчиком пропускаемых нулей, а “число” — значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1 ... будет свернут в пары (0,42) (0,3) (3,-2) (4,1) ... .

Шаг 7.

Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей.

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.