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

Рассмотрим задачу восстановления черно-белого (штрихового или полутонового) изображения с некоторыми испорченными или скрытыми от наблюдения фрагментами. Необходимо восстановить испорченные фрагменты антропоморфным (естественным для человека) способом. Математически задача может быть формализована следующим образом. Даны прямоугольная область PÌR2, взаимно непересекающиеся подобласти O1,…,ONÌP и гладкая функция . Требуется восстановить функцию f в областях O1, …, ON. Здесь P – область исходного изображения; Oi – подобласти с испорченным изображением; функция f задает доступное наблюдателю изображение (для полутонового изображения – яркость, а для штрихового – это функция, линии уровня которой совпадают с кривыми, составляющими изображение). Предлагается восстановить изображение в подобластях Oi на основе дополнения линий уровня функции f в этих подобластях (области между восстановленными кривыми в случае полутонового изображения раскрашиваются согласно значениям яркости на этих кривых). Кривые вычисляются на основе вариационного подхода: построенная линия (x(t), y(t)) должна минимизировать расстояние в пространстве (x, y, q), где (x, y) – координаты на плоскости R2; q(t) – угол наклона касательной к кривой (x(t), y(t)). Этот подход принят в нейрофизиологии зрения как естественный для человеческого глаза метод восстановления частично скрытого изображе- ния [1]. Алгоритм решения соответствующей задачи оптимального управления основан на результатах работ [2, 3] и реализован в системе Mathematica [4]. В настоящее время разрабатывается параллельная версия программ в системах gridMathematica и TSim [5].

Восстановление кривой на основе вариационного подхода

Рассмотрим гладкую плоскую кривую AB={(x(t), y(t)çtÎ[a,b]}. Предположим, что часть этой кривой  скрыта от наблюдения или повреждена. Согласно недавним работам по нейрофизиологии зрения, при первичном восприятии контура мозг человека сохраняет информацию о контуре не в виде последовательности точек (xi, yi) этого контура, а в виде набора контактных элементов (xi, yi, qi), где qi – угол наклона касательной к контуру в точке (xi, yi). Этот способ гораздо эффективнее для сохранения информации о контуре. Восстановить скрытую часть кривой CD можно следующим образом. Построим касательную TC к кривой AC в точке C и касательную TD в точке D. Обозначим через qc, qd углы наклона касательных TC, TD. Искомая кривая  должна выходить из точки C с углом наклона qc, приходить в точку D с углом наклона qd и иметь кратчайшую длину в пространстве (x, y, q):

.

Граничные условия означают гладкое сопряжение новой кривой CD с известными участками AC и DB исходной кривой. Условие минимума формализует условие естественности новой кривой CD: при ее поиске штрафуются большие отклонения как по координатам (x, y), так и по углу наклона q. Таким образом, минимизируется некоторый интегральный компромисс между линейной и угловой скоростями движения кривой. Считается, что при первичной обработке контура зрительная кора человеческого мозга достраивает небольшие скрытые дуги кривых именно этим способом. Описанная задача формализуется как следующая задача оптимального управления:

, , ,

, qÎ[0, p], , ,

, , ,

.

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

Восстановление семейства кривых

В системе Mathematica написана программа восстановления семейства линий уровня функции f в подобласти OÌP.

Входные данные программы: прямоугольник P; функция ; параметрически заданная граница подобласти O; значения C1,…,CN функции f, соответствующие линиям уровня изображения на границе области O.

Результаты работы программы:

-    серия кривых, восстанавливающих линии уровня функции f в области O (параметрические уравнения),

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

Программа имеет следующий алгоритм.

1.   Считываются входные данные.

2.   Вычисляются точки пересечения линий уровня  с границей области O и углы наклона касательных к линиям уровня в этих точках (предполагается, что область O имеет малый диаметр и каждая линия уровня пересекает ее границу в двух точках). Результат записывается в массив

{(…,(}.

3.   Решается описанная в пункте 2 задача оптимального управления для пар граничных точек  i=1, …, N. Решения запоминаются как кривые .

4.   Кривые  добавляются в область O. Если исходное изображение полутоновое, то области между кривыми  раскрашиваются оттенками серого цвета в соответствии со значениями яркости C1,…,CN.

Параллельный алгоритм восстановления изображения

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

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

Результаты работы алгоритма:

-    серия кривых, восстанавливающих линии уровня функции f в подобластях ;

-    графический файл с изображением исходной и восстановленной сеток линий уровня.

Алгоритм предусматривает несколько уровней параллелизма:

1) задача восстановления изображения для одной подобласти Oi, i=1,…,N1;

2) восстановление одной кривой по паре граничных контактных элементов  , i=1,…,N2;

3) решение систем алгебраических уравнений в двух областях однородной параметризации кривых (см. подробнее в [2]);

4) i-я итерация решения систем алгебраических уравнений с фиксированным выбором начального приближения, i=1,…,N4.

Эта схема вычисления допускает 2×N1×N2×N4 гранул параллелизма (для упрощения предполагается, что на каждом уровне j число Nj остается постоянным для всех задач). Задачи каждого уровня могут решаться независимо, что дает уверенность в высокой эффективности распараллеливания данного алгоритма. В настоящее время разрабатываются соответствующие параллельные программы в системах gridMathematica (параллельной версии системы Mathematica) и TSim (C++ библиотеки для параллельных вычислений).

Литература

1. Petitot J. The neurogeometry of pinwheels as a sub-Riemannian contact structure. J. Physiology. Paris, № 97 (2003), pp. 265–309.

2. Moiseev I., Sachkov Yu.L. Maxwell strata in sub-Rie­mannian problem on the group of motions of a plane, ESAIM: COCV. URL: http://arxiv.org/abs/0807.4731v1 (дата обращения: 21.07.09).

3. Sachkov Yu. L. Conjugate and cut time in the sub-Riemannian problem in sub-Riemannian problem on the group of motions of a plane, ESAIM: COCV. URL: http://arxiv.org/abs/ 0903.0727v1 (дата обращения: 21.07.09).

4. Wolfram S. Mathematica: a system for doing mathematics by computer, Addison-Wesley, Reading, MA 1991.

5. Московский А.А. T-Sim-библиотека для параллельных вычислений на основе подхода Т-системы // Программные системы: теория и приложения: Междунар. конф. (Переславль-Залесский, октябрь 2006). М.: Наука-Физматлит, 2006. Т. 1. С. 183–193.