Metody matematicheskoj fiziki v obrabotke signalov i izobrazhenij

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

I. FLEXPDE: СРЕДА ОПИСАНИЯ И РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ
Интерфейс системы
Структура описания задачи
Задание области решения на плоскости
Задание граничных условий
Графический вывод решения
Контроль вида графического вывода

II. ОБРАБОТКА ИЗОБРАЖЕНИЙ И СИГНАЛОВ
1. Изображение как поле яркости
2. Простая диффузия: сглаживание деталей и подавление шума
3. Метод разделения переменных, собственные числа и собственные функции
4. Градиент, поток и плотность потока его источников
5. Выделение контуров и анизотропная диффузия
6. Кратномасштабные методы
7. Глобальный и локальный спектральный анализ

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

ВВЕДЕНИЕ

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

Разработка соответствующей математической основы существенным образом базируется на теории дифференциальных уравнений математической физики. При таком подходе яркость изображения (или же интенсивность его цветовых составляющих) рассматривается как скалярная функция координат экрана, подчиняющаяся тем же закономерностям, что и, например, поля температуры или концентрации диффундирующих частиц. Основанный на такой математической аналогии с уравнением простой диффузии кратномасштабный анализ изображений был обоснован в конце 1970-х – начале 1980-х годов Марром, Хильдретом, Кёндеринком, Виткином (Marr, Hildreth, Koenderink, Witkin). Следующим заметным шагом стала концепция анизотропной диффузии, предложенная в 1990 году Перона и Маликом (Perona, Malik)^[1] и позволяющая эффективно учесть при обработке локальные особенности изображения. Эта работа положила начало целому направлению в математической теории обработки изображений – применению нелинейных дифференциальных уравнений в частных производных и разработке прикладных средств на их основе^[2].

Еще одно важное направление, возникшее в середине 1980-х годов и активно развивающееся в настоящее время – вейвет-анализ, имеющее важные приложения как для локального анализа сигналов и изображений, как и для их обработки и сжатия. Функции-вейвлеты представляют весьма широкое семейство, различные представители которого адаптированы к решению разнообразных задач. Их представители из действительнозначного гауссова семейства позволили Малла (Mallat) развить кратномасштабные методы Марра–Хильдрета–Кёндеринка–Виткина, а использование комплексного вейвлета Морле стало мощным обобщением спектрального анализа сигналов.

Основная цель данного учебного пособия – дать обзор основных методов обработки сигналов и изображений, базирующихся на решении дифференциальных уравнений в частных производных. Изложение материала рассчитано на то, что читатель владеет основами математического анализа (дифференцирование, интегрирование, основы векторной алгебры), все же вопросы, относящиеся к методам математической физики, вводятся и поясняются по ходу изложения в объеме, необходимом для понимания сущности изучаемых процессов. Естественно, это вызывает определенное упрощение математической стороны проблемы, основное внимание уделяется пояснению на примерах, а не строгим доказательствам. Читатели, заинтересованные в более глубоком знании чисто-математической стороны вопроса могут обратиться к учебникам математической физики^[3]. Метод вычисления комплексного интегрального вейвлет-преобразования с вейвлетом Морле описан на основе статьи автора^[4].

Так как пособие ориентировано, прежде всего, на пояснение сущности методов, основанных на решении дифференциальных уравнений в частных производных, то перед читателем прежде всего ставится задача правильно формулировать соответствующую математическую проблему. Нахождение ее же решение предполагается численно, с использованием система решения задач математической физики FlexPDE, разработанной фирмой PDE solutions^[5]. Она представляет собой совокупность среды для описания задач математической физики, решателя, базирующегося на методе конечных элементов (Галеркина), и средств графического вывода решения.

Применяемый во FlexPDE язык описания задачи является полностью декларативным и весьма близок к естественному языку: пользователь должен только описать конфигурацию области решения и постановку граничной задачи, не производя программирования самого процесса решения. Написание операторов, используемых в дифференциальных уравнениях, практически совпадает со стандартным математическим. FlеxPDE может решать системы дифференциальных уравнений первого и второго порядка на прямой, плоскости (в декартовых и полярных координатах) и в пространстве (в декартовых координатах). Уравнения могут быть как линейными, так и нелинейными, численное решение осуществляется модифицированным методом Ньютона-Рафсона.

Студенческая версия FlexFDE (с ограничением узлов сетки до 100 узлов в одномерных, 800 – в двумерных и 1600 – в трехмерных задачах) может быть бесплатно скачана с сайта фирмы-разработчика. Там же имеется полный комплект документации и электронные варианты книг, посвященных применению системы для решения задач математической физики.

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

Курс построен на основе лекций и практических занятий по предмету «Методы математической физики» для специальности «Информатика» в Курском государственном университете.

I. FLEXPDE: СРЕДА ОПИСАНИЯ И РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ

ИНТЕРФЕЙС СИСТЕМЫ

illustration not visible in this excerpt

При запуске FlexPDE открывается редактор среды:

illustration not visible in this excerpt

Области редактора

illustration not visible in this excerpt

illustration not visible in this excerpt

Интерактивное управление видом графиков решения

Двойной клик левой клавишей мыши по любому из окон графиков приводит к его увеличению до размеров полного экрана. Повторный двойной клик возвращает многооконный режим.

Однократный клик правой клавишей мыши вызывает появление меню, в котором управлению видом графика отвечают пункты: Maximize, Restore (описанное выше увеличение – уменьшение окна), Rotate^*.

Выполнение команды Rotate вызывает появление куба с координатными осями и пирамидой, указывающей направление вверх (см. рис) на месте области контроля сетки разбиения^**. Смещением движков можно вращать график (направление координатных осей можно контролировать по кубу). Движок Az определяет вращение вокруг вертикальной оси (проходящей через вершину пирамиды перпендикулярно ее основанию); движок Po осуществляет поворот вокруг горизонтальной оси (перпендикулярной оси Az). Переключатели режимов отображения вращения: при включенном Live Redraw график вращается одновременно с кубом, при Static Redrow – вращается только куб, а для поворота графика требуется нажать Redrow.

Интерактивное сохранение графика

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

illustration not visible in this excerpt

Пункт Print отправляет на печать изображение, отображаемое в данном графическом окне.

СТРУКТУРА ОПИСАНИЯ ЗАДАЧИ

Описание задачи для FlexPDE состоит из фиксированной последовательности разделов, снабженных заголовками. После заголовка указываются операторы, задающие соответствующую часть задачи. В том случае, когда какой-либо раздел в данной задаче не используется, соответствующий заголовок не пишется. Текст может быть снабжен комментариями в фигурных скобках ({}), с употреблением только латинских букв. Кроме того, восклицательный знак (!) обращает в комментарий стоящий после него текст строки.

TITLE ‘Имя’– имя данной задачи (латиницей), указывается в апострофах.

SELECT

В этом разделе указывается значение контролирующих параметров.

В случае задачи на собственные значения тут помещается обязательный оператор: modes=#. Здесь # – рассчитываемое число мод; одновременно инициализируется системная переменная LAMBDA, которой будут присваиваться собственные числа задачи.

COORDINATES

Выбор системы координат: декартовой прямоугольной (по умолчанию) или цилиндрической. Команды: YCYLINDER – цилиндрическая система координат, в которой ось Oz направлена вертикально, а радиальное направление – горизонтально; XCYLINDER – система координат, к которой ось Oz горизонтальна, а Or – вертикальна. В декартовых координатах командой CARTESIAN(‘name1’, ‘name2’) можно изменить имена координат с x и y на name1 и name2 (в этом случае эти имена должны использоваться и в дифференциальных операторах, например dname1() вместо dx()).

VARIABLES

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

В случае сложных расчетов следует указывать в скобках после имени переменной задается параметр threshold, который определяет уровень точности определения переменной (ее значение, меньше которого не следует проводить уточнение деталей решения).

Например, u(threshold=1e-3), v(threshold=0.01).

DEFINITIONS

Инициализация пользовательских констант (присвоение им значений) и функций (задание функции ее выражением через координаты, время или другие переменные)

Задание значения константы:

<имя константы>=<значение константы>; например, k=3.

Задание функции: <имя функции>=<выражение>. Выражение связывает координаты, время, векторы, заданные ранее константы и функции при помощи арифметических, векторных, дифференциальных операторов.

Например: f=x^2, g=sin(x)+exp(y), f1=1/r, v=-k*grad(phi) – в последнем случае предварительно должны быть заданы k (например, k=5) и phi (например, phi=x^2+y^2).

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

EQUATIONS

Запись системы дифференциальных уравнений, которым удовлетворяют неизвестные функции, указанные в разделе VARIABLES. Число уравнений должно равняться числу неизвестных, перед каждым уравнением указывается имя одной входящей в него переменной c двоеточием, например, u: dt(u)=dxx(u).

INITIAL VALUES

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

BOUNDARIES

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

TIME

Указание границ изменения времени для нестационарных задач:

FROM time1 TO time 2, где time1 – начальное время, time 2 – конечное время. По умолчанию, начальный временной шаг равен

(time2– time1)/104. Это значение можно изменить на другое, командой в форме: FROM time1 BY timestep TO time 2.

MONITORS

Команды графического вывода текущего состояния решения.

PLOTS

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

HISTORIES

Графический вывод (и сохранение в файл) значений искомой функции в заданных точках, с течением времени в нестационарных задачах.

END – команда указывает на завершение текста программы.

ЗАДАНИЕ МАТЕМАТИЧЕСКИХ ВЕЛИЧИН: ПЕРЕМЕННЫХ, ФУНКЦИЙ, ОПЕРАТОРОВ

Зарезервированные системные переменные

(не требуют декларации, не могут использоваться как функции)

illustration not visible in this excerpt

Зарезервированные системные функции

illustration not visible in this excerpt

Арифметические операторы

illustration not visible in this excerpt

Векторные операторы

illustration not visible in this excerpt

Дифференциальные операторы

illustration not visible in this excerpt

Операторы интегралов и суммы

illustration not visible in this excerpt

Неаналитические функции

illustration not visible in this excerpt

ЗАДАНИЕ ОБЛАСТИ РЕШЕНИЯ НА ПЛОСКОСТИ

Двумерные задачи

Область, к которой осуществляется решение, задается прочерчиванием ее контура и может содержать несколько подобластей. Описание контура каждой области (подобласти) должно начинаться с команды REGION. При этом области (подобласти) может быть присвоен номер: REGION #, где через # обозначено число – номер (области) подобласти, или имя: REGION ‘name’. Контур должен быть замкнутым и рисуется последовательным соединением вершин, идущим от начальной точки START (x0,y0) (между START и значением координат может быть задано имя контура в кавычках: “con”) линиями или дугами к дальнейшим точкам с координатами (x1, y1), (x2, y2) и т.д. до точки (xn, yn), которая соединяется с начальной, что определяется указанием команды CLOSE вместо координат. Имена областей (контуров) могут быть использованы в интегральных оперторах. Чтобы подобласть была вырезана из области, необходимо начать ее описание не с команды REGION, а с команды EXCLUDE. Вырезаемая область описывается после той, из которой она вырезается.

Построение отрезка

LINE TO (xk,yk) проводит отрезок от текущей точки до точки с координатами (xk,yk).

Построение дуги окружности

ARC (radius=R) TO (xk,yk) проводит дугу окружности радиусом R от текущей точки до точки с координатами (xk,yk).

ARC (center=xc,yc) TO (xk,yk) проводит дугу окружности c центром в точке (xc,yc) от текущей точки до точки с координатами (xk,yk).

ARC (center=xc,yc) angle=A проводит дугу окружности c центром в точке (xc,yc) от текущей точки на угол А, выраженный в градусах. Положительное значение А соответствует повороту против часовой стрелки.

ARC (center=xc,yc) angle=360 строит окружность с центром в точке (xc,yc).

Построение линии, заданной функцией

Контур области в виде линии, заданной функцией Abbildung in dieser Leseprobe nicht enthalten строится из линий, последовательно соединяющих точки с координатами Abbildung in dieser Leseprobe nicht enthalten:

REPEAT xi=x0 BY step TO xn

LINE TO (xi, f(xi))

ENDREPEAT

Здесь x0 – координата х начальной точки, step – шаг по координате x, xe – координата конечной точки. Функция f(xi) может быть записана непосредственно в виде выражения, содержащего арифметические действия и зарезервированные функции FlexPDE, либо может быть предварительно описана в разделе DEFINITIONS в формате f(имя аргумент)=действия над аргументом (например, f(i)=i^2). Имя аргумента не должно совпадать с зарезервированными переменными.

Построение границы по массиву координат ее вершин

Часть контура области, состоящая из линий, последовательно соединяющих точки с координатами (xc[i], yc[i]), где xc[i] и yc[i] – числа, содержащиеся в массивах xc и yc под номером i, организуется в виде цикла:

illustration not visible in this excerpt

Одномерные задачи

В разделе SELECT указывается соотвтствующая спецификация, например, coordinate=cartesian1 для обыкновенных декартовых координат.

В разделе BOUNDARIES линии задаются аналогично двумерному случаю, за исключением того, что не производится замыкания (отсутствует команда to close) и координата указывается одна. Задание отрезка [x0, x1]:

REGION 1

START (x0) LINE TO (x1)

ЗАДАНИЕ ГРАНИЧНЫХ УСЛОВИЙ

Граничные условия указываются для всех искомых функций задачи при вычерчивании области в разделе BOUNDARIES. Условие действует на всех следующих за ним линиях, до тех пор, пока не будет указано иное, либо не встретится оператор nobc(имя_функции), который прекращает действие граничного условия для указанной функции.

illustration not visible in this excerpt

Условия в точках и на незамкнутых линиях

Чтобы выделить точку с координатами (xp,yp), надо после описания области решения указать оператор fixed point(xp,yp). После него можно задать значение функции в этой точке point value(f)=g или значение величины плотности источника поля point load(f)=g (положительное значение g соответствует поглощению поля в точке). Эти же условия употребляются при задании граничных условий для одномерных задач (без оператора fixed point на границах интервала), point load играет для одномерных задач роль natural для двумерных.

Незамкнутые линии строятся в разделе BOUNDARIES после описания области решения. Заданию кривой предшествует заголовок FEATURE, далее – описанное выше построение линии, начинающейся с оператора START операторами LINE и ARC; построение не должно заканчиваться оператором FINISH. Граничные условия указываются так же, как и на границе области расчета. Если линии присвоено имя, то оно может быть использовано для вычисления интеграла по контуру, совпадающему с этой линией.

ГРАФИЧЕСКИЙ ВЫВОД РЕШЕНИЯ

Графики решения строятся в разделах MONITORS и PLOTS. Для стационарных задач в разделе MONITORS отображается процесс приближения к решению, в PLOTS – окончательный результат (который записывается в файл с расширением .pg4 и может быть просмотрен после окончания решения по команде верхнего меню P lots). В нестационарных задачах оба раздела работают одинаково. По умолчанию двумерные графики строятся на всей области решения. Для построения графика в выделенной подобласти с именем ‘name’ следует указать после оператора построения графика on ‘name’. Аналогично строится график типа elevation вдоль именованной линии.

Для нестационарных задач необходимо после заголовка использовать один из операторов, указывающих, когда следует перерисовывать график: for cycle=# (на каждом #-ом цикле пересчета); for time=time1,time2 (в моменты времени time1, time2 и т.д.); for time time1 by time_step to time2 (от момента времени time1 до time2 с шагом time_step).

illustration not visible in this excerpt

Каждый двумерный график строится в отдельном окне; вдоль линии можно одновременно построить несколько графиков, используя перечень аргументов: elevation (f1,f2,f3) from (x1,y1) to (x2,y2).

[...]

---

^[1] Perona P., Malik J. Scale-Space and Edge Detection Using Anisotropic Diffusion // IEEE Transactions on Pattern Analysis and Machine Inteligence.– 1990.– V. 12.– No. 7.– P. 629–639.

^[2] См. широкий обзор различных методов в Special Issue on Partial Differential Equations and Geometry-Driven Diffusion in Image Processing // IEEE Transactions on Image Processing.– 1998.– V. 7.– No. 3.

(http://ieeexplore.ieee.org/xpl/tocresult.jsp?isNumber=14393&puNumber=83).

^[3] Например, можно рекомендовать такие учебники, сочетающие математическую строгость с ясностью изложения, как

Арсенин В.Я. Математическая физика. Основные уравнения и специальные функции.- М.: Наука, 1966 (переиздание: Арсенин В.Я. Методы математической физики и специальные функции.- М.: Наука, 1974.); Кошляков Н.С., Глинер Э.Б., Смирнов М.М. Уравнения в частных производных математической физики.- М.: Высшая школа.- 1970; Мартинсон Л.К., Малов Ю.И. Дифференциальные уравнения математической физики.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

^[4] Постников Е.Б. Вычисление непрерывного вейвлет–преобразования как решение задачи Коши для системы дифференциальных уравнений в частных производных // Журнал вычислительной математики и математической физики.– 2006.– Т. 46.– №1.– С. 77–82.

^[5] www.pdesolutions.com

^* Команда применима только для трехмерных графиков (поверхностей).

^** Редактор написан для разрешения экрана 1024´768 точек и не масштабируется (за исключением окна графического вывода), поэтому при меньшем разрешении экрана (например, 800´600) движки не видны.