Конечно-разностная аппроксимация производных

↑

▷ Содержание

⇐ ПредыдущаяСтр 8 из 13Следующая ⇒

При весовой пространственно-временной фильтрации решаются задачи минимизации таких функций, которые хотя и являются гладкими, но настолько сложными, что оказывается трудным или невозможным организовать вычисление аналитических значений даже первых производных. В этом случае наиболее эффективными и успешно применяемыми являются методы спуска, в которых вектор градиента аппроксимируется конечными разностями [6,11]. При этом успех применения метода во многом зависит от точности аппроксимации градиента.

Простейшая конечно-разностная аппроксимация градиента получается на основе разложения функции  в ряд Тейлора [8,11]:

,

где  - интервал конечной разности, связанный с j -й компонентой аргумента ;  - единичный вектор, j -я компонента которого равна единице;  - ошибка порядка , связанная с отбрасываемыми членами ряда Тейлора и называемая ошибкой отбрасывания. Выражение (2.2-20) называется односторонней конечно-разностной аппроксимацией.

Если в формуле (2.2-20) выполняется еще один шаг тейлоровского разложения, то центральная конечно-разностная аппроксимация градиента имеет вид:

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

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

Эта формула есть результат аппроксимации j -го столбца матрицы  вектором  с последующей заменой компонент векторов  и  соответствующими разностями первого порядка.

Неточность конечно-разностных аппроксимаций вида (2.2-20) - (2.2-22) связана с ошибками трех типов [8,11,15]:

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

Ошибка потери значащих цифр, связанная с разностью двух близких значений функции . Если  - относительная точность вычисления  (в лучшем случае , где m - число двоичных цифр, с которыми ведутся вычисления). Абсолютная ошибка вычисления  имеет величину , тогда максимальная ошибка потери значащих цифр для аппроксимаций вида (2.2-20) и (2.2-21) равна .

Ошибки округления. Вычисление оценки  по заданным ,  и  сопровождается ошибками округления, неизбежными при машинном вычитании и делении. Они пренебрежимо малы в сравнении с предыдущими.

Таким образом, ошибка численного определения градиента в (2.2-20) и (2.2-21) определяется ошибками отбрасывания и потери значащих цифр. Но если первая из них пропорциональна конечно-разностному интервалу , то вторая - обратной ему величины. Поэтому последствия варьирования  для них противоположны. На практике конечно-разностный интервал выбирается из соображений минимизации вычислимой оценки суммарной ошибки.

Результаты многочисленных исследований [8-11,14,15] показали эффективность использования относительного конечно-разностного интервала , одинакового для всех компонент . При этом оценка абсолютного конечно-разностного интервала определяется выражением:

, , .

В настоящее время принята следующая стратегия вычисления градиента. Сначала градиент надо вычислять по менее трудоемкой формуле (2.2-20), а затем, когда последовательность точек попадает в область, где норма градиента мала, надо переключиться на формулу (2.2-21). Переход осуществляется тогда, когда на какой-либо итерации использование алгоритмом односторонней конечно-разностной аппроксимации градиента не приводит к достаточному убыванию функции, но критерии останова еще не выполняются. В этом случае алгоритм продолжает свою работу с использованием центральной аппроксимации градиента до тех пор, пока не выполнятся или критерии останова, или условие обратного перехода. Условие перехода определяется следующим неравенством:

.

Величина q, показывающая «существенность» убывания целевой функции от итерации к итерации, является, по существу, порогом адаптивной процедуры переключения с одной схемы численного дифференцирования на другую. Чем больше величина q, тем раньше происходит переход к центральной аппроксимации, и, наоборот, при  решение задачи происходит по односторонней схеме.

Методы условной оптимизации

В задачах весовой пространственно-временной фильтрации всегда имеет место наличие ограничений, накладываемых на вектор весовых коэффициентов . Указанные ограничения можно записать в общем виде:

,

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

.

Ограничения значительно усложняют процесс оптимизации и приводят к необходимости решения задач условной минимизации. Наличие эффективных алгоритмов безусловной оптимизации дает возможность их применения в задачах с ограничениями. В этом случае целевая функция должна быть модифицирована так, чтобы она оставалась почти неизменной внутри допустимой области, но резко возрастала при подходе к границам, задаваемым ограничениями. Последнего можно добиться, если назначить штрафную функцию по каждому из ограничений. Тогда вспомогательная функция будет иметь следующий вид [17]:

,

где  - вектор управляющих параметров,  - «штрафная» функция, воздействие которой регулируется вектором , а . Различные методы преобразования отличаются друг от друга выбором  и способом задания управлений, позволяющим найти минимум функции  при наличии ограничений посредством безусловной минимизации  по . Если обозначить точку безусловного локального минимума функции  через , то методы преобразования, в которых функция  и последовательность  задаются так, что точки  существуют, их можно отыскать (с любой степенью точности) каким-нибудь из алгоритмов минимизации без ограничений и  при , называются методами последовательной безусловной минимизации или просто последовательными методами [17]. Последовательные методы распадаются на два класса. Первый - это методы штрафных функций (или, как они еще называются методами внешней точки), использующие при поиске недопустимые точки. Второй класс составляют методы барьерных функций (методы внутренней точки). Они характеризуются тем, что поиск решения осуществляется, не выходя за пределы допустимой области, что является определяющим при решении задач нелинейной регрессии, для которых целевая функция  вне W может быть не определена. Поэтому целесообразно рассмотреть только методы барьерных функций.

В методах барьерных функций  подбирается так, чтобы на границе допустимой области «построить барьер», препятствующий нарушению ограничений в процессе безусловной минимизации функции , и чтобы точки  с изменением  по некоторому правилу приближались к  изнутри W. При этом барьерная функция определяется выражением [17]:

,

где r - положительное число, а  - непрерывные на интервале  дифференцируемые функции, причем  при . Вспомогательная функция имеет вид:

.

Она определена внутри W и неограниченно возрастает, если  для какого-нибудь i. Наиболее часто используются следующие барьерные функции [11,17]:

логарифмическая функция ;

обратная функция .

Чем меньше значение r, тем меньше влияние второго слагаемого в выражении для . Это обеспечивает сходимость при  точек  к  и как следствие существенное убывание значения  и совпадение его в пределе с .

Модельная схема оптимизации в этом случае формулируется так [17]:

Выбирается монотонно убывающая сходящаяся к нулю последовательность , например, . Определяется начальное приближение  и полагается .

.

Начиная с точки , находится безусловный локальный минимум для  и принимается . Если критерий остановки не выполняется, то возвращаются к шагу 2.

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

Непосредственное применение стандартных алгоритмов безусловной минимизации функции  встречает определенные трудности [17]. Так стандартные методы безусловной минимизации рассчитаны на то, что целевая функция определена на всем пространстве. Но для функции  это условие не выполняется, и, чем ближе  к границе множества W, тем реальнее возможность сделать шаг за пределы допустимой области. Следовательно, в данном случае необходима специальная процедура спуска по направлению, включающая проверку соблюдения ограничений и эффективное правило сокращения недопустимого шага. Вполне эффективным является следующий метод [17]. Если имеются точка , направление поиска метода  и необходима следующая точка , то сначала выбирается значение шага , проверяется выполнение ограничений . Если они выполняются, то  не меняется, иначе  заменяется величиной  (где  - коэффициент коррекции шага), находится новая точка  и вновь осуществляется проверка. В конце концов, допустимая точка  будет найдена.

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

Критерии останова

Поскольку методы оптимизации носят итерационный характер, то при их практической реализации возникает задача определения специальных правил прерывания счета - критериев останова. Как правило, процесс оптимизации прекращается, если:

1 достигнута требуемая точность решения;

2 хорошее приближение еще не найдено, но скорость движения к минимуму так упала, что не имеет смысла продолжать счет;

3 метод начал расходится или зациклился.

Этим условиям удовлетворяют следующие критерии останова, используемые в работе [11,16,17]:

,

.

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

3.
 Структура программы пространственно-временной обработки изображений

Результатом дипломного проекта стала рабочая версия программы пространственно-временной обработки изображений STIP32, обобщённая структурная схема которой приведена на рисунке 3.1. Программа состоит из трёх частей. Разработанный доцентом кафедры РУС Смирновым А.А. графический интерфейс пользователя (Graphical User Interface - GUI), в основу которого положена система окон и стандартных средств ввода / вывода информации (меню, таблицы, кнопки, радиокнопки, переключатели, строки ввода, списки и так далее), осуществляет взаимодействие с блоком ввода / вывода информации.

Рисунок 3.1 - Обобщенная структурная схема программы пространственно-временной обработки изображений

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

В блок ввода / вывода информации поступают соответствующие данные от пользователя, который устанавливает необходимые параметры (вид фильтра и фильтрации, размер апертуры, СКО белого шума, вероятности  и  появления импульсного шума, выбирает вид целевой функции, метод оптимизации), используя интуитивно понятный графический интерфейс. Эти данные поступают в блок фильтрации изображений и блок оптимизации.

Структурная схема блока фильтрации изображений приведена на рисунке 3.2.

Рисунок 3.2 - Структурная схема блока фильтрации изображений

Библиотеки пространственных и временных фильтров включают в себя следующие типы фильтров:

1. Среднеарифметический.

2. Среднегеометрический.

3. Среднегармонический.

4. Среднеконтргармонический.

5. Медианный.

6. Модифицированный медианный.

7. Минимальный.

8. Максимальный.

9. Псевдомедианный.

Блок статистического анализа позволяет произвести обработку набора изображений с различными плотностями вероятности распределения яркости с заданной величиной выборки каждого изображения из набора.

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

10.Метод Ньютона.

11.Квазиньютоновский метод с DFP-формулой пересчета.

12.Квазиньютоновский метод с преобразованной BFGS-формулой.

13.Метод сопряженных градиентов.

В качестве метода глобальной оптимизации используется метод динамического программирования (ДП). В библиотеке алгоритмов оптимизации представлено три метода ДП:

14.Классический метод ДП.

15.Модифицированный метод ДП.

16.ДП со случайной сеткой.

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

4.
 Пользовательский интерфейс программы пространственно-временной обработки изображений

Исследование обработки реальных изображений с различными статистическими характеристиками проводится с использованием программного комплекса Space-time image processing 32 (STIP32), структура модели которого рассмотрена в предыдущем разделе.

Программа пространственно-временной обработки изображений разработана на языке Си и имеет удобный графический интерфейс пользователя. Табличный ввод данных, система окон и меню обеспечивают быстрое освоение программы, не требующее специальной подготовки. В программе реализован контроль информации, вводимой пользователем, при некорректных данных ему обеспечивается соответствующая подсказка. Вводимая информация, результаты фильтрации, а также весовые коэффициенты могут быть сохранены. Использование языка Си и Ассемблера при разработке математического ядра и интерфейса приводит к уменьшению размера исполняемого модуля и увеличению производительности базовых алгоритмов. Кроме этого, исследование влияния оптимизирующих свойств современных Си-компиляторов на производительность вычислительных программ показало, что наиболее компактный и производительный код генерирует компилятор Watcom C++ 10.0, который и был использован для создания данной программы. Программный комплекс работает на компьютерах типа IBM PC с VGA адаптером под управлением MS-DOS версии 3.30 и выше, занимает около 80K пространства на жестком диске.

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

Элементами ввода / вывода информации являются:

1. Раскрывающийся список, позволяющий сделать выбор фильтра, используемого при выделении ТВ сигнала на фоне помех и шумов.

2. Выбор типа фильтрации:

.   Загрузка обрабатываемого изображения.

При нажатии на кнопку [F3] «Загрузить» появляется диалоговое окно «Обзор», в котором пользователю предоставляется возможность выбора тестового изображения в формате *.pcx.

4. Выбор параметров параметрической оптимизации.

При вводе параметров оптимизации вызывается диалоговое окно «Параметры оптимизации».

Для задания параметров оптимизации пользователю необходимо:

1) Выбрать в выпадающем списке метод первого (глобального) этапа.

2) Выбрать в выпадающем списке метод второго (локального) этапа.

)   Выбрать в выпадающем списке вид барьерной функции.

)   Задать параметры локальных методов оптимизации:

–   относительное приращение аргумента;

· штрафной коэффициент;

· пороговую точность адаптации;

· относительное приращение градиента;

· нижнюю границу весовых коэффициентов;

· верхнюю границу весовых коэффициентов.

5) Задать параметры глобальных методов оптимизации:

–   количество итераций;

– число точек на интервале.

6) Заполнить таблицу признаков оптимизации по следующему правилу: если признак оптимизации равен 0, то соответствующий весовой коэффициент не будет изменяться в ходе оптимизации, в противном случае (признак оптимизации не равен 0) - будет.

5. Редактирование и просмотр весовых коэффициентов для обработки изображений.

При нажатии клавиши F4 (кнопка «Веса»), у пользователя появляется возможность, в раскрывшемся окне «Весовые коэффициенты», редактировать или просмотреть весовые коэффициенты.

6. Загрузка ранее полученных весовых коэффициентов.

Нажатие клавиши F5 (кнопка «Загрузить веса») приводит к открытию окна «Открыть» в котором можно указать путь к ранее сохраненным весовым коэффициентам, записанным в файле с расширением *.txt, и открыть этот файл. Указание пути к файлу с весовыми коэффициентами осуществляется посредством окон «Папки» и «Диски», все найденные по указанному пути файлы с расширением *.txt будут отображены в окне «Файлы». Для выбора необходимого файла, потребуется навести на его имя, в окне «Файлы», курсор и нажать правую кнопку мыши, чтобы его подсветить, затем нажать OK.

7. Запуск процесса параметрической оптимизации.

При условии заданных ранее параметрах оптимизации, нажатие клавиши F9 (кнопка «Оптимизация») приводит к запуску процесса оптимизации.

8. Сохранение новых весовых коэффициентов.

В случае необходимости сохранения, полученных весовых коэффициентов, нажатие клавиши F2 (кнопка «Сохранить веса») приводит к открытию окна «Сохранить как».

Для сохранения коэффициентов в файле с расширением *.txt, необходимо ввести имя файла в графу «Имя файла» и указать путь сохранения, используя для этого окна «Папки» и «Диски». После этого нажать кнопку OK.

9. Установка параметров статистического анализа.

Нажатие клавиши F8 (кнопка «Параметры стат. анализа») активирует окно «Параметры статистического анализа». В данном окне производятся выбор серии изображений, по которым будет проводиться исследование, и установка величины выборки каждого изображения в процессе статистического анализа. Помимо этого, установка галочки у опции «Оптимизация», позволяет произвести оптимизацию весовых коэффициентов по всему заданному набору изображений для анализа.

10. Выбор дополнительных способов обработки отфильтрованного ТВ изображения.

Нажатием клавиши F7 (кнопка «Доп. обработка»), открывается окно «Дополнительная обработка отфильтрованного изображения».

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

11. Запуск статистического анализа.

Если предварительно были заданы параметры статистического анализа, то нажатие комбинации клавиш Ctrl+F9 (кнопка «Стат. анализ») запускает процесс статистического анализа, информация о ходе которого отображается в окне «Информация о ходе статистического анализа».

12. Установка размера апертуры фильтра.

Размер апертуры устанавливается в пределах от 2 до 15.

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

Возможные значения лежат в пределах от 0 до 0.5.

14. Ввод значения вероятности появления черного  импульсного шума. Также как и для белого импульсного шума, вероятность черного импульсного шума можно задать в пределах от 0 до 0.5.

.   Ввод значения СКО белого шума .

.   Установка значения параметра Q для контргармонического фильтра.

.   Индикаторы статистических характеристик:

1) СКО1 - СКО зашумленного изображения;

2) СКО2 - СКО отфильтрованного изображения;

3) - коэффициент улучшения СКО на выходе фильтра (дБ):

;

4) ПОСШ1 - пиковое отношение сигнал-шум на входе фильтра (дБ);

5) ПОСШ2 - пиковое отношение сигнал-шум на выходе фильтра (дБ):

;

6) P_ч1 - вероятность появления черного импульсного шума на зашумленном изображении;

7) P_ч2 - вероятность появления черного импульсного шума на отфильтрованном изображении (вероятность ложного воспроизведения);

8) P_б1 - вероятность появления белого импульсного шума на зашумленном изображении;

9) P_б2 - вероятность появления белого импульсного шума на отфильтрованном изображении (вероятность ложного воспроизведения);

10) К_{п ср} - средний коэффициент улучшения СКО на выходе фильтра, рассчитанный путем статистического усреднения по набору тестовых изображений (дБ);

11) ПОСШ1_ср - среднее значение ПОСШ на входе фильтра, рассчитанное путем статистического усреднения по набору тестовых изображений (дБ);

12) ПОСШ2_ср - среднее значение ПОСШ на выходе фильтра, рассчитанное путем статистического усреднения по набору тестовых изображений (дБ).

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

Таким образом, для выполнения весовой пространственной или временной фильтрации, пользователю необходимо выполнить следующие действия:

1) Выбрать в главном окне программы нужное изображение. Если же требуется произвести статистический анализ, то установить параметры статистического анализа (F8);

2) Выбрать требуемый вид фильтра;

)   Выбрать необходимый вид фильтрации;

)   Установить требуемый размер апертуры, требуемые значения СКО белого шума и вероятностей импульсного шума;

)   Выбрать метод 1-го (глобального) этапа (нет, ДП классический, ДП модифицированный или ДП со случайной сеткой);

)   Выбрать метод 2-го (локального) этапа (Ньютона, DFP, преобразованный BFGS или метод сопряженных градиентов);

)   Выбрать вид барьерной функции (логарифмическая или обратная);

)   Установить параметры глобальных и локальных методов и указать признаки;

)   Запустить оптимизацию, нажав кнопку «Оптимизация» (клавишу F9).

)   После этого результаты выполнения программы можно посмотреть на дисплее и при необходимости запустить оптимизацию повторно с другими параметрами.

5.
 Экспериментальная часть

В экспериментальной части дипломного проекта разработаны методика проведения и порядок выполнения лабораторной работы №1 «Исследование эффективности пространственно-временной обработки изображений с использованием статистик среднего ранга при наличии импульсных помех».

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры