Гонсалес Р., Вудс Р. Цифровая обработка изображений (3-е изд., 2012) (1246138), страница 79
Текст из файла (страница 79)
Сокращение вычислений, обеспечиваемое БПФ, являетсявпечатляющим. Так, вычисление двумерного БПФ изображения размерами1024×1024 пикселей потребует всего порядка 2·107 операций умножения и сложения, что является значительным сокращением по сравнению с первоначальным числом 1012, указанным выше.Несмотря на то, что вопрос вычисления БПФ достаточно широко освещенв литературе по обработке сигналов, этот предмет настолько важен в нашей работе, что данная глава была бы неполной без рассмотрения хотя бы начального объяснения того, почему БПФ работает столь эффективно.
Для достиженияуказанной цели мы выбрали алгоритм, называемый методом последовательногоудвоения, который являлся оригинальным алгоритмом и привел к рождениюцелой индустрии. Данный алгоритм предполагает, что число отсчетов преобразуемой последовательности является степенью двойки, но это требованиене является общим и существуют также другие подходы (см. [Brigham, 1988]).Из раздела 4.11.1 известно, что двумерное ДПФ может быть реализовано в видепоследовательных проходов одномерных преобразований, так что достаточносфокусироваться на вычислении БПФ только одной переменной.При рассмотрении вывода алгоритма БПФ удобно выразить (4.4-6) в следующей форме:M −1u = 0, 1, ..., M – 1, гдеF (u ) = ∑ f ( x )(WM )ux ,(4.11-4)WM = e −i 2π/M(4.11-5)x =0и предполагается, что M является степенью двойки, т.
е. представимо в видеM = 2n ,(4.11-6)причем n — целое положительное число. Отсюда следует, что M представимов видеM = 2K ,(4.11-7)где K — также целое положительное число. Подставив (4.11-7) в (4.11-4), получим354Глава 4. Фильтрация в частотной области2 K −1K −1K −1x =0x =0x =0F (u ) = ∑ f ( x )W2uxK = ∑ f (2 x )W2uK( 2 x ) + ∑ f (2 x + 1)W2uK( 2 x +1) .(4.11-8)Используя (4.11-5), нетрудно показать, что (W2K)2ux = (W K)ux, поэтому (4.11-8) может быть переписано в видеK −1K −1x =0x =0F (u ) = ∑ f (2 x )WKux + ∑ f (2 x + 1)WKuxW2uK .(4.11-9)Положив по определениюK −1Feven (u ) = ∑ f (2 x )WKux , для u = 0,1, 2,K, K − 1(4.11-10)x =0K −1иFodd (u ) = ∑ f (2 x + 1)WKux , для u = 0,1, 2,K, K − 1 ,(4.11-11)x =0приводим выражение (4.11-9) к видуF (u ) = Feven (u ) + Fodd (u )W2uK .Также, поскольку (W M)(4.11-12) даютu+Mu= (W M) и (W2M)u+M(4.11-12)u= –(W2M) , выражения (4.11-10)—F (u + K ) = Feven (u ) − Fodd (u )W2uK .(4.11-13)Анализ выражений (4.11-10)—(4.11-13) обнаруживает ряд их интересныхсвойств.
Как показывают выражения (4.11-12) и (4.11-13), M-точечное преобразование может быть вычислено с помощью разложения исходного выражения на две части. Для вычисления первой половины массива F(u) нужно вычислить два (M/2)-точечных преобразования, заданных формулами (4.11-10)и (4.11-11). Подстановка полученных значений Feven(u) и Fodd(u) в (4.11-12) дает F(u)для u = 0, 1, 2, …, (M/2 – 1). Вторая половина массива прямо получается при подстановке этих значений в (4.11-13) без дополнительного вычисления преобразований.Для того чтобы понять последствия применения такой процедуры с вычислительной точки зрения, обозначим через m(n) и a(n) соответственно число комплексных умножений и сложений, необходимых для ее выполнения. Как и ранее,полное число отсчетов равно 2 n, где n — положительное целое число.
Предположим сначала, что n = 1. Двухточечное преобразование требует вычисления значения F(0); затем значение F(1) может быть получено из (4.11-13). Для полученияF(0) сначала нужно вычислить Feven(0) и Fodd(0). Поскольку в данном случае K = 1,то выражения (4.11-10) и (4.11-11) представляют собой одноточечные преобразования. Однако поскольку ДПФ единственного отсчета есть сам этот отсчет, тодля получения Feven(0) и Fodd(0) не требуются ни умножения, ни сложения. Одноумножение Fodd(0) на W20 и одно сложение дает F(0) по формуле (4.11-12). ЗатемF(1) получается по формуле (4.11-13) при помощи еще одного сложения (вычитание рассматривается как операция аналогичная сложению).
Поскольку величина Fodd(0)W20 уже была сосчитана ранее, то полное число операций, необходимоедля вычисления двухточечного преобразования, состоит из m(1) = 1 умноженийи a(1) = 2 сложений.4.11. Вопросы реализации355Пусть теперь n = 2.
В соответствии с предыдущими результатами 4-точечноепреобразование может быть разделено на две части. Первая половина F(u) требует вычисления двух двухточечных преобразований, задаваемых формулами(4.11-10) и (4.11-11) с K = 2. Как отмечено в предыдущем параграфе, вычислениедвухточечного преобразования требует m(1) умножений и a(1) сложений, таким образом, вычисление по двум указанным формулам потребует всего 2m(1)умножений и 2a(1) сложений.
Еще два сложения и умножения необходимы дляполучения F(0) и F(1) по формуле (4.11-12). Поскольку величины Fodd(u)W2K u дляu = {0,1} уже были посчитаны, еще два сложения дадут F(2) и F(3). Таким образом, полное число операций m(2) = 2m(1) +2 и a(2) = 2a(1) +4.Когда n = 3, вычисление Feven(0) и Fodd(0) сводится к вычислению двух 4-точечных преобразований. Это требует 2m(2) умножений и 2a(2) сложений.Для полного завершения вычислений необходимо еще четыре умноженияи восемь сложений.
Таким образом, полное число операций m(3) = 2m(2) +4и a(3) = 2a(2) +8.Продолжая рассуждать подобным образом, мы придем к следующим рекуррентным соотношениям для числа операций, необходимых для вычисленияБПФ при любом положительном значении n:иm(n) = 2m(n − 1) + 2n−1 , n ≥ 1(4.11-14)a(n) = 2a(n − 1) + 2n , n ≥ 1;(4.11-15)кроме того, m(0) = 0, a(0) = 0, поскольку одноточечное преобразование не требует ни умножений, ни сложений.Формулы (4.11-10)—(4.11-13) лежат в основе БПФ алгоритма с последовательным удвоением.
Это название связано с методом вычисления двухточечного преобразования на основе двух одноточечных, 4-точечного — на основе двухдвухточечных и т. д. для любого M, равного целой степени 2. В качестве упражнения (задача 4.41) мы предлагаем читателю показать, чтои1m(n) = M log2 M2(4.11-16)a(n) = M log2 M .(4.11-17)Преимущество в скорости, которое дает алгоритм БПФ по сравнению с методом прямого вычисления одномерного ДПФ, определяется выражениемC (M ) =M2M.=M log2 M log2 M(4.11-18)Поскольку предполагается, что M = 2 n, то (4.6-49) можно переписать относительно n:C (n) =2n.n(4.11-19)График соответствующей функции представлен на рис.
4.67. Очевидно, чтопреимущество в скорости быстро возрастает с ростом числа n. Например, при356Глава 4. Фильтрация в частотной области24001800C(n) 120060001Рис. 4.67.2345678n9 10 11 12 13 14 15Преимущество в скорости, которое дает алгоритм БПФ по сравнениюс прямым методом вычисления одномерного ДПФ. Обратите внимание на быстрый рост этого показателя как функции от nn = 15 (32768 отсчетов) БПФ превосходит в скорости метод прямого вычисленияпочти в 2200 раз. Поэтому можно ожидать, что на одном и том же компьютеревычисления с помощью БПФ будут совершаться почти в 2200 раз быстрее, чемпрямое вычисление ДПФ.Детальному рассмотрению БПФ посвящено так много прекрасных работ(см., например, [Brigham, 1988]), что мы не будем более останавливаться на этомвопросе.
Фактически все полные пакеты программ для обработки сигналови изображений включают в себя реализацию обобщенного БПФ алгоритма,который может также оперировать с количеством отсчетов, не равным целойстепени 2 (за счет меньшей вычислительной эффективности). Бесплатные БПФпрограммы также легко доступны, в основном через Интернет.4.11.4. Некоторые замечания по поводу построения фильтровПри рассмотрении в этой главе методов фильтрации в частотной области мы намеренно сосредоточили внимание на основных принципах, чтобы стала яснеесуть используемых методов. Лучшего пути для этого, чем избранный способ изложения, мы не знаем.
Материал главы может рассматриваться как фундаментдля конструирования фильтров. Другими словами, если мы хотим подобратьфильтр для некоторой конкретной задачи, то частотные методы будут тем идеальным инструментом, который даст возможность экспериментировать быстрои с полным контролем над параметрами фильтра.Когда для конкретного приложения уже найден фильтр, часто возникаетвопрос о реализации соответствующей фильтрации непосредственно в пространственной области с использованием встроенных программ и/или аппаратных средств. Данный вопрос выходит за рамки настоящей книги. В работе[Petrou, Bosdogianni, 1999] представлена подходящая связь между двумернымипространственными фильтрами и соответствующими цифровыми фильтрами.По поводу разработки двумерных цифровых фильтров см.
[Lu, Antoniou, 1992].Ссылки и литература для дальнейшего изучения357Çàêëþ÷åíèåПредставленные в настоящей главе сведения являются последовательным изложением материала от дискретизации к преобразованию Фурье и затем до вопросов фильтрации в частотной области. Некоторые из концепций, такие кактеорема отсчетов, не имеют почти никакого смысла, если не рассматриваютсяв контексте частотной области. То же самое справедливо и в отношении вопросов наложения спектров. Таким образом, изложенный материал служит прочной базой для понимания основ цифровой обработки сигналов. Мы специально постарались вести изложение, начиная с самых основных принципов, чтобылюбой читатель с умеренным уровнем математической подготовки был способен не только впитать материал, но также и использовать его.Второй важной целью главы было рассмотрение дискретного преобразования Фурье и вопросов его использования для фильтрации в частотнойобласти.
Для этой цели нам потребовалось рассмотреть теорему о свертке.Этот вопрос служит базой для построения линейных систем и лежит в основемногих методов восстановления, рассматриваемых в главе 5. Набор рассмотренных фильтров достаточно репрезентативен для множества, используемого на практике. Однако ключевым вопросом представления этих фильтровбыло стремление показать, насколько просто формулировать и реализовывать фильтры в частотной области. Хотя окончательная реализация найденного решения, как правило, базируется на пространственных фильтрах, темне менее невозможно переоценить роль интуиции, возникающей при работев частотной области и служащей затем руководством для выбора пространственных фильтров.Хотя большинство примеров фильтрации в данной главе касаются вопросов улучшения изображений, тем не менее сами процедуры являются общимии широко используются в последующих главах книги.Ññûëêè è ëèòåðàòóðà äëÿ äàëüíåéøåãî èçó÷åíèÿВ качестве дополнительного чтения по вопросам, затронутым в разделе 4.1,мы рекомендуем [Hubbard, 1998].
Книги [Bracewell, 2000, 1995] могут служитьхорошим введением в теорию непрерывного преобразования Фурье и егообобщения на двумерный случай для обработки изображений. Две упомянутые книги, а также [Lim, 1990], [Castleman, 1996], [Petrou, Bosdogianni, 1999],[Brigham, 1988] и [Smith, 2003] содержат исчерпывающее изложение вопросов,составляющих основу всех рассмотрений разделов 4.2—4.6. В качестве обзора ранних работ, касающихся вопросов картин муара, см. [Oster, Nishijima,1963]. Уровень науки в этой области спустя тридцать лет рассмотрен в [Creath,Wyant, 1992]. Вопросы дискретизации, наложения спектров и восстановления изображений, рассмотренные в разделе 4.5, также являются предметомзначительного интереса в компьютерной графике, как это иллюстрируетсяв [Shirley, 2002].358Глава 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
