|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 11 Dec 2001 10:41:27
To : Konstantin Filinov
Subject : Вейвлеты
--------------------------------------------------------------------------------
Mon Dec 10 2001 22:58, Konstantin Filinov wrote to Евгений Машеров:
ЕМ>> В трех - кратно-масштабный анализ:)
ЕМ>> Если чуть больше слов - используем базисные функции, которые после
ЕМ>> растяжения в два раза (рассматриваются и иные растяжения) переходят в
ЕМ>> себя. Основное уравнение: f(2x)=SUM a(i)*f(x-i) Эти функции локализованы
ЕМ>> в пространстве, в отличие от раскинутых от плюс до минус бесконечности
ЕМ>> синусов/косинусов. Поэтому ими лучше приближаются функции, содержащие
ЕМ>> быстрые изменения, скажем, изображения. Далее либо мылом, либо, если
ЕМ>> народу интересно, можно начать обсуждение в эхе.
Один из критериев для выбора вида вейвлета - энтропийный, определяемый, как
exp(-SUM|dj,k|^2 *log |dj,k|^2)
Он показывает количество существенных членов вейвлет-разложения. Чем он ниже -
тем более эффективно вейвлет-представление. Иначе говоря, малые значения
критерия означают, что среди коэффициентов немногие весьма велики, тогда как
прочие малы. Однако в практических задачах для выбора вида вейвлета существены
и другие критерии, такие, как симметричность, гладкость, наличие производных
заданного порядка и т.п..
Вычисление вейвлет-разложения функции, заданной набором своих значений, может
быть произведено за достаточно малое время, если воспользоваться быстрым
вейвлет-преобразованием. Оно имеет большое сходство с быстрым преобразованием
Фурье, также требуя выполнения log2N шагов, каждый из которых требует О(N)
операций. Hачав с исходного вектора, превратим его в N/2 отсчетов 'разностей',
полученных пропусканием исходного сигнала через фильтр с коэффициентами g и
N/2 отсчетов 'сумм', полученных при помощи фильтра с коэффициентами h.
(Уменьшение числа отсчетов достигается тем, что точки берутся с шагом 2). В
ряде случае можно рассматривать это, как пропускание сигнала через
высокочастотный и низкочастотный фильтры, разделяющие сигнал на две частотные
полосы. Оставив последовательность 'разностей', повторим ту же процедуру с
рядом 'сумм', пока в нем не останется лишь единственный отсчет. Это и будет
вейвлет-разложением. Обратное преобразование, ввиду ортогональности
преобразования, производится аналогично.
Рассмотрим несколько подробнее программу вейвлет-преобразования:
procedure wavdir(a:array of double);
var
i,j,k,nn,nh,nh1:integer;
begin
nn:=65536;
while nn>=4 do
begin
nh:=nn div 2;
i:=0;
j:=0;
while j<nn-4 do
begin
W[i ]:=C[0]*a[j]+C[1]*a[j+1]+C[2]*a[j+2]+C[3]*a[j+3];
W[i+nh]:=C[3]*a[j]-C[2]*a[j+1]+C[1]*a[j+2]-C[0]*a[j+3];
j:=j+2;
i:=i+1;
end;
W[i ]:=C[0]*a[nn-2]+C[1]*a[nn-1]+C[2]*a[0]+C[3]*a[1];
W[i+nh]:=C[3]*a[nn-2]-C[2]*a[nn-1]+C[1]*a[0]-C[0]*a[1];
for i:=0 to nn-1 do
a[i]:=W[i];
nn:=nn div 2;
end;
end;
вычисляющий вейвлет-преобразование Добеши 4-го порядка. Она весьма проста.
Двигаясь по исходному вектору данных с шагом 2, вычисляем свертку сигнала с
коэффициентами масштабной и базисной функций. Результат записывается
соответственно в первую и вторую половины вспомогательного вектора, который
затем замещает исходный. Расстояние, проходимое по вектору, каждый раз
уменьшается вдвое. В результате вектор преобразования оказывается записан на
месте исходного. Особо следует отметить, что имеет место "заворачивание"
сигнала - последние отсчеты полагаются переходящими в первые. Подобный эффект
имеет место и при Фурье-преобразовании, и связан с тем, что мы рассматриваем
конечный отрезок данных, однако пользуемся функциями, определенными на
бесконечном. Такие краевые эффекты надлежит всегда принимать в расчет.
Программа обратного преобразования
procedure wavinv(a:array of double);
var
i,j,k,nn,nh,nh1:integer;
begin
nn:=4;
while nn<=65536 do
begin
nh:=nn div 2;
nh1:=nh+1;
W[0]:=C[2]*a[nh-1]+C[1]*a[nn-1]+C[2]*a[0]+C[3]*a[nh1-1];
W[1]:=C[3]*a[nh-1]-C[0]*a[nn-1]+C[1]*a[0]-C[2]*a[nh1-1];
j:=2;
i:=0;
while i<nh-1 do
begin
W[j]:=C[2]*a[i]+C[1]*a[i+nh]+C[0]*a[i+1]+C[3]*a[i+nh1];
j:=j+1;
W[j]:=C[3]*a[i]-C[0]*a[i+nh]+C[1]*a[i+1]-C[2]*a[i+nh1];
j:=j+1;
i:=i+1;
end;
for i:=0 to nn-1 do
a[i]:=W[i];
nn:=nn*2;
end;
end;
совершенно подобна по своей структуре и также относится к "быстрым"
алгоритмам. Другие вейвлеты могут быть вычислены программами, отличающимися
только наборами коэффициентов. Приведем их для вейвлетов Добеши 4-го, 12-го и
20-го порядка.
c4[4]={0.4829629131445341,0.8365163037378079,
0.2241438680420134,-0.1294095225512604};
c12[12]={0.111540743350, 0.494623890398, 0.751133908021,0.315250351709,
-0.226264693965,-0.129766867567,0.097501605587,
0.027522865530,-0.031582039318,
0.000553842201, 0.004777257511,-0.001077301085};
c20[20]={0.026670057901, 0.188176800078, 0.527201188932,0.688459039454,
0.281172343661,-0.249846424327,-0.195946274377, 0.127369340336,
0.093057364604,-0.071394147166,-0.029457536822,
0.033212674059,0.003606553567,-0.010733175483, 0.001395351747,
0.001992405295,-0.000685856695,-0.000116466855,0.000093588670,-0.000013264203};
Таким образом, использование вейвлет-анализа сводится в большинстве случаев к
следующей схеме: переход от исходного сигнала к его разложению по базису
вейвлетов, нелинейное преобразование их в соответствии с поставленной задачей
(зануление малых и квантование больших коэффициентов - в задаче сжатия,
накопление значений между реализациями - в задаче анализа ВП, сравнение с
критериальными значениями и преобразование в соответствии с ними - в задаче
поиска эпилептиформной активности и т.п.) и затем обратное преобразование,
переводящее вновь в пространство сигнала. (Последнее может быть опущено, если
задача - построить частотно-временной спектр сигнала, пользуясь
вейвлет-анализом).
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Вейвлеты |
Roman Kirillov |
09 Dec 2001 17:29:49 |
 Вейвлеты |
…ўЈҐЁ© Њ иҐа®ў |
10 Dec 2001 20:52:00 |
 Вейвлеты |
Konstantin Filinov |
10 Dec 2001 23:58:29 |
 Вейвлеты |
Evgenij Masherov |
11 Dec 2001 10:35:26 |
|
Вейвлеты |
Evgenij Masherov |
11 Dec 2001 10:37:24 |
|
Вейвлеты |
Evgenij Masherov |
11 Dec 2001 10:39:32 |
 Вейвлеты |
Evgenij Masherov |
11 Dec 2001 10:41:27 |
|
Вейвлеты |
Roman Kirillov |
14 Dec 2001 09:38:48 |
 Вейвлеты |
…ўЈҐЁ© Њ иҐа®ў |
17 Dec 2001 20:37:10 |
|
Re: Вейвлеты |
Alexander Lezin |
10 Dec 2001 19:07:04 |
|
Вейвлеты |
Ilia Kantor |
12 Dec 2001 17:00:26 |
|
|
