Двумерная дискретизация (лекция 8)

1.

Двумерная дискретизация
Оцифровка и визуализация изображений
Основное требование при компьютерной
обработке изображений – трансформация
(физически непрерывной) функции в дискретную форму.
Оцифровка включает в себя последовательное
выполнение двух операций:
- дискретизации
- квантования
f x, y
f S x, y u m, n

2.

Процедура визуализации изображения
предусматривает операцию дискретно-аналогового
преобразования
u m, n
~
f x, y

3.

Теория дискретизации
Математически процесс дискретизации
изображения продемонстрируем для
двумерной функции с ограниченным спектром
Двумерная функция
f x, y
имеет ограниченный
спектр, если для Фурье-образа
F 1 , 2
выполняется условие

4.

F 1 , 2 0, 1 x0 ; 2 y 0
где переменные
x 0 ; y 0
максимальные пространственные частоты по x и y
В случае циркулярной симметрии
0 x0 y0

5.

Идеальная дискретизирующая функция представляет
собой (бесконечный) двумерный массив Дельта-функций,
расположенных в узлах прямоугольной регулярной сетки
comb x, y; x, y x m x, y n y
m ,n

6.

Операция дискретизации есть произведение исходной
функции на дискретизирующую
f S x, y f x, y comb x, y; x, y
f m x, n y x m x, y n y
m , n

7.

Фурье-образ дискретизирующей (comb) функции есть
функция,
имеющая тот же вид, что и исходная
COMB 1 , 2 F comb x, y; x, y
xs ys 1 k xs , 2 l ys
k ,l
xs ys comb 1 , 2 ; 1 , 1
x y

8.

Пространственные частоты дискретизации по
координатным направлениям равны величинам,
обратным соответствующим шагам дискретизации
xs 1 x , ys 1 y

9.

Воспользуемся правилом, согласно которому
произведение функций в исходном пространстве
эквивалентно свертке соответствующих Фурье-образов
FS 1 , 2 F 1 , 2 COMB 1 , 2
xs ys F 1 , 2 1 k xs , 2 l ys
k ,l
xs ys F 1 k xs , 2 l ys
k ,l

10.

Фурье-образ дискретизированной функции
представляет собой периодическую (бесконечную)
комбинацию Фурье-образа исходной (непрерывной)
функции, продублированного в узлах сетки
,
xs
ys

11.

Восстановление непрерывной функции
Если спектр исходного (непрерывного) изображения
может быть каким-либо образом восстановлен из
спектра дискретного, то мы можем восстановить
и исходную функцию.
Это возможно, если выполняются условия
xs 2 x 0 , ys 2 y 0
что эквивалентно условию выбора шагов дискретизации,
удовлетворяющих
x
1
2 x 0
, y
1
2 y 0

12.

В этом случае “сохранить” Фурье-образ исходной
функции можно, применив идеальный
низкочастотный фильтр со следующими
характеристиками
1
,
H 1 , 2 xs ys
0,
1 , 2
иначе
При этом результат действия фильтра приводит к
исходному Фурье-образу
~
F 1 , 2 H 1 , 2 FS 1 , 2 F 1 , 2

13.

Частота Найквиста
Нижние границы пространственных частот,
при которых возможно сохранение (восстановление)
спектра исходной функции
2 x 0 ,
2 y 0
называются (пространственными) частотами
Найквиста (Котельникова)

14.

Теория дискретизации констатирует, что функция
с ограниченным спектром, дискретизированная
с частотой выше частоты Найквиста, может быть
восстановлена без ошибки с помощью простейшего
(идеального) низкочастотного фильтра
Если же условие не выполняется, т.е.
xs 2 x 0 , ys 2 y 0
то (соседние) Фурье-образы будут накладываться друг
на друга, тем самым искажая исходный спектр

15.

Если область “поддержки” низкочастотного фильтра
представляет собой прямоугольник
1 1
1
1
xs , xs ys , xs
2 2
2
2
то его импульсный отклик есть произведение SINC-функций
h x, y sin c x xs sin c y ys

16.

Обратное Фурье-преобразование реконструирует
изображение по формуле
~
f x, y f m x, n y sin c x xs m sin c y ys n
m ,n
результат будет совпадать с исходной функцией,
если выполняется условие дискретизации
Найквиста-Котельникова

17.

Теорема дискретизации
Двумерная (непрерывная) функция с ограниченным
спектром
f x, y
может быть однозначно (безошибочно) восстановлена
из дискретной
f m x, n y
при условии, что шаги дискретизации выбраны из условия
1
1
xs 2 x 0 ,
ys 2 y 0
x
y

18.

Восстановление функции проводится по
интерполяционной формуле
f x, y
sin x xs m sin y ys n
f m x, n y
m , n
x xs m y ys n

19.

Задача
Изображение описывается функцией
f x, y 2 cos 2 3x 4 y
Дискретизация функции проводится
со значениями интервалов дискретизации
x 0.2,
y 0.2
Восстановить функцию после дискретизации

20.

Решение
Фурье-образ заданной функции
F 1 , 2 1 3, 2 4 1 3, 2 4
Откуда
x 0 3, y 0 4
Частоты дискретизации
1
xs 5,
x
1
ys 5
y
меньше частоты Найквиста-Котельникова
2 x 0 ,
2 y 0

21.

Найдем спектр дискретизированного изображения:
FS 1 , 2 xs ys F 1 k xs , 2 l ys
k ,l
25 1 3 5k , 2 4 5l 1 3 5k , 2 4 5l
k ,l
Применим низкочастотный фильтр
1
1
, 2.5 1 2.5, 2.5 2 2.5
H 1 , 2 xs ys 25
0,
иначе

22.

Получим Фурье-образ
~
F 1 , 2 H 1 , 2 FS 1 , 2
1 2, 2 1 1 2, 2 1
который при восстановлении дает функцию
~
f x, y 2 cos 2 2 x y