Брейсуэлл Р. - Преобразование Хартли (теория и приложения), страница 12

Необходимо также представить фильтруюшую последовательность в виде 13 требуемых коэффициентов и 115 нулей. Применительно к рис. 5.3 используется массив вида '/1з (! 1 1 1 1 1 '/з 0... 0 '/, 1 1 1 1 1). Таким образом, каждое сглаженное значение согласуется во времени с серединой группы из 13 элементов фильтрующей последовательности. При использовании последовательности вида '/„(1/, ! 1 1 1 1 1 1 1 1 1 1 '/з 0 0 0 ... 0 О) будет иметь место различие в индексации, а именно сглаженная последовательность окажется задержанной на б месяцев. Эффект циклической свертки проявляется в получении 128 выходных (сглаженных) значений, из которых только 84 (с 7-го по 90-й месяцы) имеют физический смысл. Перед группой этих значений и после нее наблюдаются участки более или менее линейного изменения сглаженной кривой; небольшой участок возрастания этой кривой наблюдается в конце графика справа.

Диапазон изменения аргумента (времени), в пределах которого сглаженная последовательность не равна нулю, в явном виде отражает искусственный характер формирования данных в результате расширения массива до 128 элементов, и 58 Подчеркивание границ Значительная доля информации, содержащейся в видеоизображении, распределена в пределах границ раздела более или менее однородных , областей, и зрительное восприятие изображения может быть улучшено усилением контрастности этих границ. Одним из видов границ данного типа является линия раздела областей с разной средней яркостью. Для повышения контрастности аэрофотоснимков, например, обрабатываемой пашни, имеющей условную яркость 7 единиц, и , окружающего ландшафта с условной яркостью 8 единиц, можно ' вычесть из этих значений б. В результате условные яркости этих областей оказываются равными 1 и 2, а при четырехкратном усиле, нии — соответственно 4 и 8, за счет чего контраст существенно усили' вается.

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

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

Привлекательной чертой этой идеи является то, что операция вычитания в равной степени может быть реализована для всех точек изображения, что не требует принятия решения относительно местоположения границы. Дця одномерного варианта результат свертки с последовательностью (1 — 2 1) равен разности второго порядка, являющейся соответствующим приближенным представлением второй производной при условии, что интервал дискретизапии отсчетов достаточно мал. Если это условие не выполняется, то бессмысленно задавать вопрос о действительной степени повышения разрешающей способ- 59 ности. С другой стороны, если интервал дискретизации много меньше представляющего для нас интерес интервала разрешения, что обычно и имеет место, то должна использоватъся некоторая последовательность с большим числом элементов, представляющая собой, например, совокупность отсчетов второй производной гауссовой кривой.

Для двумерного варианта соответственно оценивается локальная кривизна, например, с помощью свертки с массивом отсчетов (д'/дг') ехр( — хгз/И>з), где масштабный коэффициент И'выбирается меньше интервала разрешения, но не малым по сравнению с интервалом дискретизации. Для иллюстрации рассмотрим следующую небольшую матрицу, состоящую из 9 элементов; 1 2 1 2 — 12 2 1 2 1 б ажением, ряд признаков которого должен Двумерная свертка с изо р быть усилен, с последующим вычитанием некоторой части результата свертки из исходного изображения дает желаемый эффект. Выбор величины этого вычитаемого включает в себя оценки качественного характера, которые изменяются от случая к случаю, и ие может быть осуществлен только на основе математических выкладок. Полная операция усиления признаков (вьщеления границ) может быть сведена к одноэтапной процедуре; например, если должна вычитаться величина, равная '(> карты «кривизны», то окончательный результат, реализующий требуемое усиление, непосредственно получается с помощью свертки с матрицей вида — 1 — 2 — 1 — 2 28 — 2 — 1 — 2 — 1 Свертка с использованием быстрого преобразовании Хартли Процедура свертки, представленная в табл.

5.1, может быть реализована на базе быстрого алгоритма с использованием программы ГНТСОХЧ, приведенной в приложении 1. Основная программа предполагает, что та или иная из заданных функций обладает свойством симметрии, так как в этом широкораспространенном случае скорость выполнения программы очень высока. Однако в отсутствие симметрии осуществляется обращение к подпрограмме 4400, а не 4000, просто реализующей перемножение двух вещественных ДПХ.

Использование быстрого алгоритма ЕНТЯ)В предполагает ограничение числа элементов каждой последовательности, которое должно быть кратным 2, что является известным ограничением, причем не очень жестким по своему характеру. Большее значение имеет тот факт, что для последовательностей данных, над которыми выполня- ется операция свертки, в общем случае маловероятно равенство числа элементов, тогда как программа требует дополнения обеих последовательностей нулями для их уравнивания.

Если последовательности данных существенно отличаются числом элементов, то может оказаться более быстрым алгоритм свертки в области исходных данных с использованием программы СОЕК Когда результат выводится на печать, в нем присутствует делитель М или 2!Ч (для несимметричного случая) в соответствии со стратегией, описанной выше в разделе, посвященном коэффициенту !Ч '.

В рамках данной программы имеются три обращения к быстрой подпрограмме 9000; следовательно, было бы пустой тратой времени . повторять предварительное табулирование тригонометрических функций и степеней числа 2. В самой программе этот факт учитывается посредством ее автоматической адаптации.

В случае когда циклическая свертка не требуется, для получения свертки, содержащей А> элементов, для каждой входной функции достаточно всего А>>>2 значений исходных данных. Таким образом„ в дополнение к нулям, предусмотренным для увеличения числа элементов последовательности до кратного двум, требуется еше одна подпоследовательность из А>>2 нулей.

Свертка посредством умножения является превосходной процедурой при ее умелом использовании, простой в реализации при внимательном анализе практических деталей, связанных с нулями последовательностей, и более наглядной по сравнению с ее комплексным вариантом. Способ без использования перестановок Операция свертки может быть выполнена в полном объеме без перестановки элементов ценой запоминания второго типа преобразования. Алгоритмы, рассмотренные в данной книге, предполагают использование перестановки с последующим замещением, однако существуют алгоритмы другого типа, в которых замещение элементов предшествует процедуре перестановки. Описание структур этих алгоритмов применительно к ДПФ приводится в статье: И> Т.

Сос!>гав е! аЬ !Ч!>а! В !1>е Газ! Гоппег Тгапз!опп? 1ЕЕЕ Тгапз. Анси апд Е!есггоасопзйсз, чо!. А() — 15, рр. 45 — 55, 1985 (Кохран. Что такое быстрое преобразование Фурье?). В обозначениях, введенных в гл. 7, алгоритм, реализующий в качестве первого этапа операцию перестановки, использует матричный оператор Ь Ь, ... Ь, Ь, Р„; подобный оператор для алгоритма, в котором операция перестановки является завершающей, имеет вид Р» Ь> Ьз 1 р > Ьр Если алгоритм второго типа применить к двум входным (исходным) функциям, а алгоритм первого типа — к произведению получающихся при этом результатов (выходных функций), то, очевидно, операция перестановки не потребуется.

Быстрая перестановка, как описано ниже, означает, что экономия времени составляет неболь- б! шую долю всего времени счета, а эта доля уменьшается с ростом Х. Однако могут иметь место частные случаи, когда имеет смысл не выполнять процедуру перестановки. Свертка квк умножение матриц Дискретная свертка двух последовательностей вргражается в виде матричного произведения определенной прямоугольной матрицы на* вектор-столбец. Правила умножения матриц требуют, чтобы число столбцов прямоугольной матрицы было равно числу элементов вектора-столбца; получающийся в результате этой процедуры вектор-столбец будет иметь М+ ]У вЂ” 1 элементов, где М и Ж вЂ” число элементов свертываемых последовательностей.

Таким образом, следующая свертка пятиэлементной и трехэлементной последователь- ностей ЯО) )(1 ) Я2) У(3).Г(4)] * (д (О) д (1) д (2)) эквивалентна равенству х д(!) Так как операция свертки обладает свойством коммутативности, справедлива другая форма записи: х г(1) которая с позиций теории матриц не является очевидной. Для ЭВМ, которые обеспечивают выполнение операции умножения матриц, не обязательно иметь специальную программу для свертки. В приложении 1 приводится такая программа под названием МАТСОХ. При этом массив (вектор) В( ) заполняется ]У значениями данных (строки 70 — 90) по аналогии с программой СОМУ. Затем первый столбец массива (матрицы) А(,), который является двумерным, заполняется М значениями данных и дополняется нулями до * Напомним, что операция умножения матриц не коммутативна. 62 ДО) 0 0 Д1) ДО) 0 Л2) Л1) 1(0) Лз) У(2) У(1] у(4) у(3) Д2) О Д4) г (3) о о у(4) д(0) 0 О д(!) д(0) д(2) д(1) д(0) д(3) д(2) д(1) д(4) д(З] д(2) о д(4) д(з) О 0 д(4) У(0)д(0) Д Пд(о) + д(о)д( 1] у(2)д(о) + у(цд(!] + у(о)д(2) 1(з]д(о) + у(2)д(!) + у(!)д(2) г(4)д(0) + ДЗ)д(1) + Д2)д(2) Д4)д(!) + 1(З)д(2) Д4)д(2) о щей длины Р= М+ )У вЂ” 1 (сгрока 120), а остальные столбцы б массива А(,) заполняютсн таким образом, чтобы получилась циклическая структура (строка 130 — 150).

После выполнения этих предварительных действий реализуется в полном объеме операция свертки, а ее значение присваивается матрипе С( ) с помощью оператора умножения матриц, занимающего одну строку: 180 МАТ С = АпВ. Задачи 5.! . Определение корреляциоппай д)уикции. Определить циклическую корреляционную функцию следующих последовательностей с числом элементов !у=8: а) (1 ! 1 1 О О О О), б) (1 ! 1 1 1 О О 0], в) (1 1 1 1 1 1 0 О), г) (! 1 1 1 1 ! 1 О]. 5.. Определение корреляционной Яупкции. Какова циклическая коррсляцаон- 52 О ная функция последовательностей а) (! Р 1 0 1 0 1 О), б) (1 0 0 ! О 0 1 О), в) (1 0 0 0 1 0 0 1)? П росуммнровать элементы полученных корреляционных последовательностей и объяснить результат. 5.3, Определение корреляционной д5уикции. Определить циклическую корреляционную функцию последовательностей а) (1100 0000],б) (1010 0000], в) (1 ! 0 1 0 0 0 О], г) (1 ! 0 0 ! 0 1 О].