Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 18
Текст из файла (страница 18)
8.2 построены соответствующие графики зависимости временных затрат от величины Р, изменяющейся от 0 до Р = 20 (М = 1048576). Хотя Р = 20 не является наибольшим значением Р, которое может встретиться на практике, оно фигурировало бы при анализе изображений, имеющих структуру вида 1024 х!024 элементов разрешения, для которых разрешающая способность выше реализуемой прн использовании телевизионного экрана. Подавляющее большинство преобразований, осуществляемых в повседневной практике, без сомнения оперирует величинами Р, не превышающими Р= 10.
Графики наглядно илз люстрируют, что при цифровой обработке изображений больших размеров крайне важным становится вопрос о скорости реализации алгоритма. Ясно, что введение быстрого преобразования Фурье (БПФ) сильно расширяет наши возможности. Необходимость обработки изображений в реальном времени требует на сегодняшний день еще более высокого быстродействия, н обратно, по мере увеличения быстродействия будут открываться новые приложения. Повторное разбиение последовательностей Если необходимо получить преобразование Фурье заданной последовательности, то можно выполнить разбиение последовательности на две части и осуществить преобразование каждой нз этих частей в отдельности.
Так как затрачиваемое время возрастает быстрее скорости изменения М, при реализации преобразования будет иметь место экономия времени счета; однако потребуется некоторое дополнительное время, так как два коротких преобразования объединяются каким-либо образом с целью получения совокупного более длинного преобразования. Данная идея представляется заманчивой, так как подобная процедура может быть применена вновь, а именно сами зти короткие последовательности могут быть поделены пополам с целью дальнейшей экономии времени.
В принципе любая факторизация приводит к упрощению вычислительной процедуры. После выполнения (Р— 1)-го разбиения исходной последовательности получим двухэлементные сегменты. Теперь уже преобразование двухэлементной последовательности является тривиальным и включает в себя два действия сложения и ни одного действия умножения. Количество 95 операций, требуемых для объединения последовательностей, получаемых на каждом этапе разбиения, имеет пор!Шок величины М, так как каждому из /3/ элементов может быть присвоен некоторый коэффициент, а всего имеется (Р— 1) этапов разбиения.
Следовательно, при доста~очно больших Ы количество операций определяется как Ь/ (Р— 1) или приближенно как Ь/Р. " Так же как и при обосновании закона вида гчг, рассуждения в подтверждение закономерности внца Ь7Р носят приближенный характер. Теперь мы подробно проанализируем механизм формирования преобразования Хартли. Далее мы выполним эмпирическую проверку времешгых затрат на реализацию преобразования в рамках анализа, заменяющего процедуру подсчета количества операций. Преобразование с использованием разложения на подпоследовательности Рассмотрим последовательность данных /(т) = (а, аг Ь, Ьг с, сг 3/1 Г/2) = ( о, О Ь, О с, О 2(1 О) + (О ог О Ьг О сг О 2/2), которая представляется в виде суммы двух слагаемых. Две короткие последовательности (а, Ь, сгг/1) и (о, Ьгсгг/2) при их точном «прослаивании» по аналогии с идеальным «тасованием» воспроизводят исходную последовательность /(2). Требуется найти преобразование Хартлн Н(ч) последовательности /(г) исходя из преобразований коротких последовательностей.
Будем полагать, что последовательность (а, Ь, с, !21) имеет ДПХ (а, р1 у, 5,), (огЬгс2322) имеет ДПХ (агргугбд). На основании теоремы о растяжении для ДПХ (см. гл. 4) непосредственно можем утвержцатгс (а, О Ь, О с, О дг О) имеет ДПХ (а, Рг у, Ь, а, (1!у, 5,), (ад О Ьг О гг О г/2 О) имеет ДПХ (ад РгугбгагРгугбг). Однако пряменительно к последнему выражению следует отметить, что нам требуется ДПХ последовательности (О о, О Ьг О с, О 2/2).
С целью получения преобразования этой последовательности применим теорему о сдвиге. При сдвиге на один элемент вправо эта теорема формулируется следующим образом: Если последовательность д (г) имеет ДПХ б(ч), то д(т — 1) имеет ДПХ вида С(ч) соз(2яч//3/) + С(Ж вЂ” ч) згп(2яч/Ы). Используя обозначение 0 = 2я/Ы, можем утверждать, что последовательность (С(ч)) приобретает вид (б (О) С (1) сов 8 С (2) соз 28 б (3) сов 38 С (4) соз 40 б (5) сов 58 С(6)соз60 б(7)соз70) + (С(7)яп0 б(6) вш20 б(5)ап 30 б(4) ап40 б(3)яп50 С(2)яп60 б(1)яп70 О).
Следовательно, при условии что последовательность д (г) = (о, О Ь, О с, О д, О) вмеет ДПХ С(ч) = (агргУгбгагйгУ25,), ДлЯ последовательности д(т — 1) = (О ог О Ьг О сг О Г/2) ДПХ равно (а,б,соз0 у,соз20 Ь,сов30 а соз48 бгсоз50 у,соз60 Ь,соз78) + + (О Ь яп8 у,яп20 О Ь,зш50 у,ап68 Огз)п70). Наконец, применяя теорему сложения, получим Н(ч) = (а, Р1У,Ь,агР17151) + (ад Ргсозй Угсоз20 Ьгсоз30 а соз40 ()2соз58 у соз68 Ьгсоз70) + (О Ьгяпй у!ап20 О Ьгяп50 у ап68 (3, яп 70). Если в это равенство для Ы = 8 входят коэффициенты О, 1 или — 1, то оно упрощается: Н(ч) = ',а, + аг 01 + Г(рг + 52) 71 + уг а, + аг н! — Г((32 + 52) у! 72 51 — Г(332 52)).
На этом завершается доказательство того, что 8-элементное преобразование Н(ч) может быть сформировано из двух четырех- элементных преобразований (а, Цгу, 5,) и (а, 02 72 52). Общая фягрмула разложения. Ясно, каким образом можно обббпшть структуру вышеприведенного равенства. Для заданной последовательности/(т), т = О, 1, ..., Ь7 — 1 будем полагать, что М-элементные подпоследовательности (/(О) О /'(2) О /(4) О .. ), (/(1) О /'(3) О /(5) Π— ) имеют соответственно ДПХ Н, (ч) и Н, (ч). Тогда Н (ч) = Н, (ч) + Н, (ч) соз (2яч/Ы) + Н, (М вЂ” ч) яп (2яч/М).
Это равенство представляет собой общую формулу разложения, определяющую дискретное преобразование Хартли, с использованием последовательного разбиения последовательностей иа две части. Так как Н,(ч) и Нг(ч) могут быть получены путем непрерывно повторяющегося разбиения вплоть до четырехэлементных последовательностей, полное разложение выражается через исходные последовательности. Например, для простого 8-элементного преобразования элемент Н(3), как оказывается, связан с восемью элементами последовательности /(т) следующим образом: Н(З) = (1/8) К(О) + Π— /(2) + /2/(3) — /(4) + О +/'(6) — /2/(7)1.
Эта зависимость согласуется с выражением Н(3) = (1/8) (/(О) + / (1) саз 30 + / (2) саз 68 + /(3) саз 90 + / (4) саз 120 + +/ (5) саз 150 + /(6) саз 180 + Л7) саз 210), 97 7-!236 с4 40 сч св с в — — о со са сч" ОГ ст са О Ф \ тттт й,овса й тттт » Я»~Ж й, Гв, й, й, ТТТТ \О с и с ГГ~ Г, й„й, ТТТТ Е»»»» р7 «4» «4 С'» $» оТ»» 4 о о Г, Га, Гв, Гв, + ооСС й, й.
й, Г + .Г- + + СоСо 04» СЧ С» Гв, Гв, Г.:И +++ о ССо О С- И с. + .Г- .Г- + СооС 40 с й, Т Т »» о— св с й, т т »» — »» о- О Гв, й, .т т Ч О» И Г,й, тт сй»» о о О о о й Га, Гв Га .~. -Г- Г + оооо оооо СО Ь И о й, СО»»» СО С» И С'» СО» В» С'» й,й,й,й, й,»а,й,й, ++++ ++++ Га, Га, Г» й тттт ~»тт т т т — —— 40 ттт С» СО СО» С» С0 СО И СО И СО И СО СО СО Я,й„Г,Г, й,й,й й, Гчс»Га,й, й,Г»,Г,Г», и о о Га, Гв, + 0» Гв, о о й, й, й СО 4» о о" Гв, Га, са сс о о 00 00 о" о ГЧ й Га, й, й, +» + о" о о" Га, ГЧ + о о с — 0 «4 С» » 40 с»" 40 Га, й тт„'„ ~ -еа »»»» -— с» «4» Гв, й, Га, о" о" о" й.й, Га, с'» » с'» о о с» й, Г*, Г». т т т о" о" о т т т СО С О о о" о" ГЧ й, й, о" о" о" о Г,Г,й,й, тттт — о «4 о о т т "с и о о Гв, й, т т о" ОГ Гв, Га, т т 4 в о О О Ю О.
Ф \' ОСОС Г, Гв, Га, Г, ++++ -ОВ ОС СЧ ОС" —— — Г Гв, й, Гв, .Г- й — о сО о й, Гв, й, й„ СЧ С'С С'4 «4 Г» Г» Г» Га + + О сч 40 С4 04 0» Са о «44» 04 СЧ «4 «4 Оа ""Ф И о СО О» Гв, Г, Га, С'» и О о" о ГЧ ГЧ 40 «4 С'» С»ОЧ» С«Оѻѻ о «а сч й, Га, Гв, Га, тттт в» о" о" о" о" Га, й, Г; +» + ! о о сч сч о" о" ОГ ОГ Га, Га, Гс, й, о са со ь О о с Га, Гч Га, й, й, й, Гв, й О сч В» С о и Га, й„Г», Г, Га, Га, й, й, «4 СО о ~ттт т ж-- СО О О» 40 с'» СО С'» й, Г», + + СоСС 00 СВ и с'» с'» с» й,й,й,й, ++ й+ 40 40 0» в» й, й, й, Гв„ тттт ж»»»" »» ч с" о .о йа сч й. + + + + СоСо О»«ОС » и с Гвс Гв, Гв, Га, тттт СО СО СО»» Г, Га, Га, Га, + Г-.~.й оооС ь ь О» о» -й,й, -Гчт т й, т т„аа .0 с» с'» Г», Г, Гв, й, + + СССо о 00 О \О \О в» с'» й, й, «ттт »»-4 о7 "С с« св в са 04 С4 СЧ й, Гс, Га, й, + + О-оС "С О С4 СО СЧ «4 Ос ОС Г», й, Гв, й„ + + СССС вЂ” 0 С4 С» СЧ С4 С'4 ОС й, й, й, Г„ + + -С» 00 СВ «а «Т СГ сч которое непосредственно следует из определения преобразования Хартли.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
