Гонсалес Р., Вудс Р. Цифровая обработка изображений (3-е изд., 2012) (1246138), страница 60
Текст из файла (страница 60)
4.9. (а) Преобразование Фурье субдискретизованной функции с ограниченной полосой частот. (Наложение спектров соседних периодовпоказано пунктиром.) (б) Идеальный низкочастотный фильтр; тотже самый, что и на рис. 4.8(б). (в) Результат произведения (а) и (б).Взаимовлияние соседних периодов приводит к наложению спектров,что препятствует точному восстановлению как F(μ), так и исходнойнепрерывной функции с ограниченной полосой частот. Сравнитес рис. 4.8поскольку даже если исходная дискретизуемая функция имела ограниченнуюполосу частот, в момент ограничения длительности функции, что мы всегдавынуждены делать на практике, возникают компоненты бесконечной частоты.Предположим, например, что мы хотим ограничить длительность функции f(t)c ограниченной полосой частот интервалом, скажем, [0, T].
Это можно сделатьумножением f(t) на функцию⎧1h(t ) = ⎨⎩00 ≤ t ≤T ,в остальных случаях.(4.3-10)Данная функция имеет ту же базовую форму, что и функция на рис. 4.4(а), чейФурье-образ H(μ) имеет частотные компоненты, продолжающиеся в бесконечность, как показано на рис. 4.4(б). Из теоремы о свертке известно, что Фурьеобраз произведения h(t)f(t) равняется свертке Фурье-образов функций. Дажеесли Фурье-образ f(t) ограничен по частоте, результат его свертки с H(μ) будетиметь частотные компоненты, продолжающиеся в бесконечность.
Таким образом, ни одна из ограниченных по времени функций не может являться функ-266Глава 4. Фильтрация в частотной областицией с ограниченной полосой частот. И наоборот, функция с ограниченной полосой частот обязана простираться от –∞ до ∞.9Исходя из вышеуказанных причин, можно сделать заключение, что наложение спектров является неизбежным фактом при работе с дискретизованными записями конечной длины. На практике эффект наложения спектров может бытьуменьшен сглаживанием исходной функции путем ослабления самых верхнихчастот сигнала (например, в случае изображения, при помощи расфокусировки). Процесс сглаживания (anti-aliasing) должен выполняться до дискретизациифункции, поскольку наложение спектров, являющееся результатом дискретизации, не может быть «отменено» при помощи вычислительных методов.Пример 4.3. Наложение спектров.■ Классическая иллюстрация эффекта наложения спектров представленана рис.
4.10. Чисто синусоидальная функция, продолжающаяся бесконечнов обоих направлениях, имеет единственную частоту, т. е. имеет ограниченнуюполосу частот. Пусть функция на рисунке (в данный момент отвлечемся от больших точек) описывается закономерностью sin(πt), а горизонтальная ось соответствует времени t в секундах. Функция пересекает эту ось в точках t = ... –1, 0, 1,2, 3, ...
.Период P функции sin(πt) составляет 2 с., а частота ее равна 1/P, т. е.1/2 цикла/с. В соответствии с теоремой отсчетов, данный сигнал может бытьвосстановлен по набору отсчетов, если их частота дискретизации 1/ΔT вдвоепревышает верхнюю частоту сигнала. Это означает, что для восстановлениясигнала требуется частота дискретизации выше, чем 1 отсчет/с. (1/2 × 2 = 1) илиΔT < 1 c. Заметим, что дискретизация выбранного сигнала с частотой, точноравной его удвоенной (т. е. 1 отсчет/с.), и отсчетами, взятыми в точках t = ...
–1, 0,1, 2, 3, ... , даст в результате значения ... sin(–π), sin(0), sin(π), sin(2π), ... , которыевсе равны 0. Это является иллюстрацией причины, по которой теорема отсчетов требует, чтобы частота дискретизации обязательно превышала удвоеннуюверхнюю частоту сигнала, как и было указано выше.Напомним, что частота 1 цикл/с есть по определению 1 Гц.Большие точки на рис. 4.10 суть отсчеты, взятые равномерно со скоростью,меньшей, чем 1 отсчет/с (фактически расстояния между отсчетами превышают2 с, что дает частоту дискретизации ниже 1/2 отсчета/с).
Оцифрованный сигналвыглядит как синусоидальный, однако его частота — около одной десятой частоты оригинала. Этот дискретизованный сигнал, частота которого значительно ниже частоты исходной непрерывной функции, также является результатомналожения спектров. Имея в качестве результата фильтрации отсчеты, показанные черными точками на рис. 4.10 (являющиеся серьезнейшими погрешностя9Важный особый случай имеет место, когда функция, простирающаяся от –∞до ∞, имеет ограниченную полосу частот и является периодической. В такой ситуациифункция может быть усечена по времени и все еще оставаться ограниченной по полосечастот, при условии, что остается целое число периодов. Единственный оставленный период (а значит, и вся функция) может быть представлен набором дискретных отсчетов,взятых на усеченном интервале и удовлетворяющих теореме отсчетов.4.3.
Дискретизация и преобразование Фурье дискретных функций267...t...ΔTРис. 4.10.Иллюстрация эффекта наложения спектров. Субдискретизованная функция (черные точки) выглядит как синус, имеющий частотумного ниже, чем частота исходного непрерывного синусоидальногосигнала с периодом 2 с, пересечения которого с горизонтальной осьюпроисходят каждую секунду. ΔT — период между отсчетамими, вызванными наложением спектров), невозможно узнать, что полученныеотсчеты не дают правильного представления об исходной функции.
Как будетвидно ниже в данной главе, в случае изображений наложение спектров может■привести к аналогичным обманчивым результатам.4.3.5. Реконструкция (восстановление) функции из отсчетовРеконструкция функции по набору ее отсчетов сводится к интерполяции междуотсчетами. Даже простой вывод изображения на дисплей требует восстановления его из отсчетов устройством воспроизведения. Таким образом, пониманиеоснов восстановления дискретизованных данных весьма важно. Центральнойдля понимания этого вопроса является свертка, что еще раз показывает актуальность этой концепции.Основные принципы процедуры точного восстановления функции с ограниченной полосой частот из отсчетов при помощи частотных методов былиизложены при обсуждении рис. 4.8 и выражения (4.3-8). Используя теоремуо свертке, можно получить эквивалентный результат в пространственной области.
Согласно (4.3-8), F (μ) = H (μ)F% (μ) и, следовательно,f (t ) = F −1 {F (μ)} = F −1 {H (μ)F% (μ)} = h(t ) f% (t ) ,(4.3-11)где последний шаг следует из соотношения (4.2-21) теоремы о свертке. Можнопоказать (задача 4.6), что подстановка (4.3-1) для f¦(t) в выражение (4.3-11) и использование затем уравнения (4.2-20) приводит к следующему выражению дляf(t) в пространственной области:f (t ) =∞∑ f (nΔT )sinc[(t − nΔT ) /ΔT ],(4.3-12)n =−∞где функция sinc определена в (4.2-19). Данный результат не является неожиданным, поскольку обратное преобразование Фурье от прямоугольного фильтра H(μ) также является sinc-функцией (см.
пример 4.1). Выражение (4.3-12) показывает, что точно восстанавливаемая функция является бесконечной суммой268Глава 4. Фильтрация в частотной областиsinc-функций, взвешенных значениями отсчетов, и ее важным свойством является то, что значения такой функции точно совпадают со значениями отсчетов,расположенных в целочисленном ряду периодов ΔT. То есть для любого t = kΔT,где k — целое, f(t) равна k-му отсчету f(kΔT). Это следует из выражения (4.3-12),поскольку sinc(0) = 1 и sinc(m) = 0 для любого другого значения m. Значения f(t)между точками отсчетов даются интерполяциями, формирующимися суммамиsinc-функций.Для интерполяции между отсчетами выражение (4.3-12) требует бесконечного числа членов.
На практике это означает, что необходимо искать приближения в виде конечных интерполяций между отсчетами. Как обсуждалось в разделе 2.4.4, основными методами интерполяции, используемыми в обработкеизображений, являются выбор ближайшего соседа, билинейная и бикубическаяинтерполяции. Эффекты интерполяции будут обсуждаться в разделе 4.5.4.4.4. Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå (ÄÏÔ)îäíîé ïåðåìåííîéОдной из основных целей данной главы является вывод дискретного преобразования Фурье (ДПФ), начиная с основных принципов.
Сведения, изложенныек данному моменту, можно рассматривать как фундамент этих основных принципов, так что теперь у нас есть все необходимое для вывода ДПФ.4.4.1. Получение ДПФ из непрерывного преобразованиядискретизованных функцийСогласно изложенному в разделе 4.3.2, преобразование Фурье дискретизованной функции, определенной от –∞ до ∞ и имеющей ограниченную полосу частот, является непрерывной периодической функцией, которая также заданаот –∞ до ∞. На практике приходится иметь дело с конечным числом отсчетов,поэтому целью настоящего раздела является вывод ДПФ, соответствующего такому набору значений.Выражение (4.3-5) дает Фурье-преобразование F¦(μ) дискретизованнойфункции f¦(t) через преобразование исходной функции F(μ), но не через значения самой дискретизованной функции f¦(t).
Выведем это выражение напрямуюиз определения Фурье-преобразования, определяемого (4.2-16):F% (μ) =∞∫ f%(t )e− i 2 πμtdt .(4.4-1)−∞Подставляя f¦(t) из (4.3-1), получимF% (μ) =∞∫f% (t )e −i 2 πμt dt ==∞∫ ∑ f (t )δ(t − nΔT )e− i 2 πμtdt =−∞ n =−∞−∞∞∞∞∑ ∫ f (t )δ(t − nΔT )en =−∞ −∞− i 2 πμtdt =∞∑fen =−∞n− i 2 πμnΔT(4.4-2),4.4. Дискретное преобразование Фурье (ДПФ) одной переменной269где последний шаг следует из (4.3-2). Хотя fn является дискретной функцией, ееФурье-преобразование F¦(μ) — непрерывная периодическая функция с периодом 1/ΔT, как видно из (4.3-5).
Таким образом, для описания всей функции F¦(μ)требуется лишь один период, и дискретизация одного периода является основой для ДПФ.Предположим, нам требуется получить M равноотстоящих отсчетов F¦(μ),взятых на отрезке от μ = 0 до μ = 1/ΔT. Для этого берутся отсчеты на следующихчастотах:μ=mM ΔTm = 0,1, 2,..., M − 1 .(4.4-3)Подставляя этот результат для μ в выражение (4.4-2) и обозначая результат черезFm, получим:M −1Fm = ∑ fne −i 2 πmn/Mm = 0,1, 2,..., M − 1.(4.4-4)n =0Это выражение и является искомым дискретным преобразованием Фурье10.Для заданного набора {fn}, состоящего из M отсчетов, выражение (4.4-4) позволяет получить набор {Fm} также из M комплексных дискретных величин, соответствующих дискретному преобразованию Фурье исходного набора отсчетов.И наоборот, используя обратное дискретное преобразование Фурье (обратноеДПФ), из заданного набора {Fm} можно восстановить набор отсчетов {fn}:fn =1MM −1∑F em =0mi 2 πmn /Mn = 0,1, 2,..., M − 1 .(4.4-5)Нетрудно показать (задача 4.8), что подставляя (4.4-5) вместо f n в (4.4-4), получим тождественный результат: F m ≡ F m.
И наоборот, подставляя (4.4-4)в (4.4-5), получим аналогичное тождество f n ≡ f n. Это означает, что выражения (4.4-4) и (4.4-5) составляют пару дискретных преобразований Фурье(ДПФ-пару). Более того, эти тождества показывают, что прямое и обратноепреобразования Фурье существуют для любых наборов данных с конечными значениями. Заметим, что ни одно из выражений явно не зависит ни отшага дискретизации ΔT, ни от частотного интервала в выражении (4.4-3).Таким образом, ДПФ-пара применима к любому равномерно взятому наборуотсчетов.Мы использовали символы m и n в предыдущих операциях для обозначениядискретных переменных, поскольку эти обозначения обычны для выкладок.Однако более наглядно, особенно при работе с двумя переменными, использовать символы x и y для обозначения координат на изображении, а для частотных10Согласно рис. 4.6(б), отрезок [0, 1/ΔT] покрывает два полупериода соседних периодов преобразования, и высокие частоты в нем расположены посередине.