5.4. Сравнение обсуждаемых алгоритмов

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

5.4.1. Размерность библиотеки базисов

Может быть показано, что для одномерного сигнала длиной N при применении двухканального блока фильтров число базисов перебираемых алгоритмом одиночного дерева, вычисляется рекурсивно:

Это вытекает из следующих соображений. Любое двоичное дерево может быть представлено в виде суммы двух субдеревьев высотой на 1 меньше. Если количество базисов в этих субдеревьях то количество базисов во всем дереве

Для упрощения анализа алгоритма двойного дерева предположим, что используются фильтры Хаара, так как в этом случае не требуется применение граничных фильтров. Аналогично предыдущему случаю может быть показано, что количество перебираемых базисов

- количество «новых» базисов одиночного дерева, когда нет пространственной сегментации.

Количество базисов для частотно-временного дерева может быть вычислено аналогично (для фильтров Хаара):

. В случае использования других фильтров количество базисов увеличивается за счет применения граничных фильтров либо периодического расширения сигнала и становится равным

Для алгоритма гибкой временной сегментации количество базисов

подытожено количество базисов, перебираемых различными алгоритмами. Например, при При Конечно, для двумерного случая количество базисов значительно больше.

Таблица 5.1. Сравнение количества базисов, перебираемых различными алгоритмами