ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
17 June 2024

Reconstruction of images via variational principle

The article was published in issue no. № 4, 2009
Abstract:A mathematical approach to reconstruction of images via the following variational principle is described: the reconstruction curve (x(t), y(t)) should minimize length in the space (x, y, ), where  is the angle of slope of the curve. A software in Mathematica system for solving the problem is developed, its output is presented. A parallel algorithm for reconstruction of hidden image via the variational approach is proposed.
Аннотация:Описан математический подход к решению задачи восстановления изображения на основе следующего вариационного принципа: восстанавливаемая кривая (x(t), y(t)) должна минимизировать длину в пространстве (x, y, q), где q – угол наклона кривой. Разработана программа в системе Mathematica для решения этой задачи, продемонстрированы результаты ее работы. Предложен параллельный алгоритм восстановления скрытого изображения на основе данного подхода.
Authors: (sachkov@sys.botik.ru) - , (sachkov@sys.botik.ru) - , Ph.D, (sachkov@sys.botik.ru) - , (sachkov@sys.botik.ru) -
Keywords: parallel algorithms and programs Image processing, optimal control, image processing
Page views: 11899
Print version
Full issue in PDF (4.85Mb)

Font size:       Font:

Рассмотрим задачу восстановления черно-белого (штрихового или полутонового) изображения с некоторыми испорченными или скрытыми от наблюдения фрагментами. Необходимо восстановить испорченные фрагменты антропоморфным (естественным для человека) способом. Математически задача может быть формализована следующим образом. Даны прямоугольная область 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.


Permanent link:
http://swsys.ru/index.php?page=article&id=2392&lang=en
Print version
Full issue in PDF (4.85Mb)
The article was published in issue no. № 4, 2009

Perhaps, you might be interested in the following articles of similar topics: