Software & Systems

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

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

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

Пусть  – конечное или счетное множество, на котором каждой упорядоченной паре элементов x и y отнесено число  Отметим, что задание такой функции индуцирует на X дополнительные структуры.

1.        Если функция  симметрична, на X можно ввести структуру неориентированного графа. Его вершинами являются элементы из X; предполагается, что вершины x и y связаны ребром, если u(x,y)¹0.

2.        Если функция u(x,y) несимметрична, на X можно ввести структуру ориентированного графа. Его вершинами являются элементы из X; вершина x соединена с y ребром, направленным из x в y, если u(x,y)¹0. Считаем, что y покрывает x, и пишем  если u(x,y)¹0.

3.        Если функция u(x,y) такова, что индуцированный ориентированный граф не содержит циклов, на X можно также ввести комбинаторную структуру частично упорядоченного множества: полагаем  если x и y являются соответственно началом и концом некоторого пути по стрелам.

Обратно, с каждым неориентированным (ориентированным) графом естественно связана функция u(x,y) на множестве пар его вершин, определяющая структуру графа. Именно u(x,y)=1, если x и y – концы ребра (соответственно, концы направленного ребра из x в y), и u(x,y)=0 в противном случае.

Определение. Назовем усреднением по X функции  на X (относительно заданной функции u(x,y)) следующую функцию на X:

                             (1)

В других обозначениях операция усреднения принимает вид:

                             (2)

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

1.        Для любого x функция u(x,y) отлична от нуля лишь на конечном множестве точек y.

2.        Исходная функция f(x) финитна, то есть отлична от нуля, лишь на конечном множестве точек x.

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

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

Описание алгоритма, восстанавливающего f по функции F

Назовем любую конечную последовательность  элементов из X путем в X, а число n – длиной этого пути.

Теорема 1. Для любого натурального числа n имеет место соотношение:

(3)

где

;               (4)

  (5)

(В силу условий финитности суммы (4) и (5) содержат лишь конечное число ненулевых слагаемых.)

Доказательство. Заметим предварительно, что  для всех элементов  не обладающих покрытиями. Пусть теперь  – произвольный элемент. Из (2) следует:

Значит,

.

Повторяя этот процесс, получаем на n-м шаге выражение (3), где  задается равенством (5).

Следствие. Если  для всех , функция f может быть представлена в форме сходящегося ряда

        (6)

где  задается равенством (4).

Достаточные условия сходимости ряда

Теорема 2. Предположим, что для каждого элемента  число покрывающих его элементов не превышает фиксированное число r и  для всех  Тогда, если , преобразование обратимо для любой ограниченной функции f на X и формула обращения представима в виде сходящегося ряда (6), а также в форме ряда, полученного из (6) перестановкой порядка суммирования:

,                            (7)

где

Доказательство. Оценим остаточный член  в формуле (5). Число слагаемых в этой формуле не превосходит , а каждое из них не превосходит по модулю число  где . Таким образом,  Так как по условию , то  при  Следовательно, ряд (3) сходится, а потому равенство (6) справедливо. Очевидно, что из (6) следует (7).

Теорема 3. Предположим, что для любых x и y число путей из x в y не более чем конечно. Тогда для любой финитной функции  преобразование обратимо, и формула обращения представима в виде ряда (6), обрывающегося на конечном шаге.

Доказательство. Пусть M – носитель финитной функции f. По условию теоремы, для любой фиксированной точки xÎX максимальная длина путей из x в точки множества M не превосходит некоторого числа m, значит, остаточный член Rn в формуле (3) равен нулю при n>m.

Случай финитных функций f

Теорема 4. Предположим, что для любого yÎX подмножество элементов yÎX, покрывающих x, и подмножество элементов  покрываемых элементом x, не более чем конечны. Тогда для каждой финитной функции f(x) ее образ также является финитной функцией.

Доказательство. Пусть L – носитель финитной функции f и  – множество, полученное присоединением к L всех точек , таких что u(x,y)¹0 хотя бы для одной точки yÎL. Из условия теоремы следует, что множество  также конечно. Очевидно, если , то x и все точки, покрывающие y, для которых u(x,y)¹0, не принадлежат L. Значит, F(x)=0 при .

Теорема 5. Пусть существует точка x0ÎX, такая, что для любого x¹x0 имеется хотя бы один путь из x0 в x. Тогда, если выполнены условия теоремы 4, любая финитная функция F может быть получена усреднением некоторой финитной функции f.

Доказательство. Из условий теоремы следует, что функция u(x,y) удовлетворяет условию теоремы 4, значит, образ финитной функции является финитной функцией. Обратно, пусть F – финитная функция и LÌX – ее носитель. Докажем, что функция f, заданная равенством (3), также финитна. Рассмотрим множество путей из точки x0 в точки множества L и обозначим через  совокупность точек  принадлежащих хотя бы одному из этих путей. Из условия теоремы следует, что множество  конечно. По условию на , для любой точки  пути в X с началом в этой точке не содержат точек из , а значит, и точек из L. Но тогда из формулы (3) для f следует, что f(x)=0 для любой точки .

Частный случай

Рассмотрим случай, когда функция u(x,y) принимает только значения 0 и  Число путей длины k из x в y обозначим . Если выполнены условия соответствующих теорем сходимости, формула обращения приводится к виду:

                            (8)

где

Этот случай для a=1 рассмотрен в [5], где показано, что формула обращения существует только для особых случаев, когда в индуцированном графе каждая вершина принадлежит циклу нечетной длины. Из (8) следует, что при достаточно малом a задача разрешима на любом конечном графе, если положить , где N – число вершин графа.

Простейший пример

Пусть X – конечная или бесконечная циклическая группа с естественной структурой графа. Рассмотрим преобразование .

Если X=Z и f(x) – финитная функция, то F(x) – также финитная функция и формула обращения имеет вид:

                       (9)

где ряд обрывается на конечном шаге. Когда X – конечная циклическая группа порядка n, ряд (9) бесконечен и сходится тогда и только тогда, когда . В последнем случае, по условию периодичности f(x)=f(x+n), он приводится к виду: f(x)= , и эта формула является формулой обращения для преобразования I, связанного с конечной циклической группой.

Усреднения на графах

Рассмотрим усреднения на множествах с дополнительными структурами.

Пусть X – множество вершин конечного или бесконечного графа и каждому его ребру I=(x,y) отнесено число u(x,y) (вес ребра), такое, что u(x,y)= =u(y,x)¹0 в случае неориентированного графа и u(x,y)¹0, u(x,y)=0 в случае ориентированного графа, если ребро (x,y) направлено из x в y.

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

Тогда при сформулированных выше условиях на u(x,y) и функцию f исходная функция f восстанавливается по своему усреднению согласно формуле (6) или (7). В частности, если число ребер, выходящих из каждой вершины графа, не превышает фиксированное число r и u(x,y) на каждом (ориентированном) ребре, где  то формула обращения принимает вид (8). Таким образом, в этом случае с каждым путем на графе из вершины x в вершину y связан бесконечный, но заведомо сходящийся при  степенной ряд. Его коэффициенты определяются структурой графа.

Рассмотрим другое усреднение на графе. Отнесем каждой функции f, определенной на множестве вершин графа, функцию j на множестве его (ориентированных) ребер  заданную равенством

                              (10)

Требуется восстановить функцию f по функ- ции j. Эта задача легко сводится к предыдущей. Определим функцию F(x) на X по формуле:

,                                     (11)

где r(x) – число ребер, выходящих из x, а суммирование ведется по множеству концов y всех этих ребер. Подставив выражение j через f, получим: , где .

Таким образом, F является усреднением f относительно функции v(x,y). Исходная функция f выражается через F по формуле обращения (6), где функция u(x,y) в выражении для  должна быть заменена функцией v(x,y). Чтобы получить выражение f через функцию j, достаточно подставить в эту формулу обращения выражение (11) функции F через функцию j.

В частности, формула обращения для преобразования  имеет вид:

где  – сумма по всем путям длины k из x в y.

Усреднения на множествах с биективными отображениями

Пусть X – произвольное конечное или счетное множество с заданным на X конечным набором биективных отображений  i=1,…r. Образ точки xÎX при отображении gi обозначим через xgi. Предположим, что выполнены следующие условия.

1.   Для каждой биекции  не существует неподвижных точек.

2.   Для каждой точки  ее образы  попарно различны.

Определим усреднения функций f на X равенством

Тогда для любой ограниченной функции f на X справедлива формула обращения (7), где  – число различных представлений y в виде композиции k биекций.

Усреднения на целочисленной решетке

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

                             (12)

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

,                     (13)

где .

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

                                       (14)

(сумма по всем векторам вида , ), где

              (15)

(сумма по всем представлениям элемента y в виде , где ).

Из теоремы 2 следует, что при , i=1,…,r, формула обращения (14) справедлива для любой ограниченной функции f(x). Если между  не существует линейных соотношений вида , где все числа  одного знака (это условие необходимо и достаточно для выполнения условия теоремы 3), то формула обращения справедлива для всех финитных функций, и операция усреднения является биекцией пространства финитных функций.

Замечание. Выражение (15) для c(y) – это сходящийся при  ряд гипергеометрического типа; если векторы xi линейно зависимы, его можно свести к ряду от меньшего числа переменных.

Примеры гипергеометрических формул обращения

Пример 1. Пусть X – множество целых неотрицательных чисел и  – произвольный набор целых положительных чисел. Тогда операция усреднения (12) обратима и является биекцией пространства финитных функций на X. В справедливости последнего утверждения можно убедиться и непосредственно, рассматривая структуру матрицы инцидентности преобразования

Функция f восстанавливается по формуле: , где коэффициенты c(y) задаются равенством (15). В частности, при r=2 имеем:

Поскольку  и  связаны соотношением , выражение для c(y) может быть приведено к виду:

где .

Пример 2. Пусть X – конечный циклический граф с n вершинами и {x1,…,xr} – множество точек графа. Пронумеруем вершины графа целыми числами, полагая, что числа x и x+n задают одну и ту же его вершину. Таким образом, любую функцию на графе можно интерпретировать как периодическую функцию на множестве целых чисел: f(x+n)=f(x), а усреднение определяется так же, как в предыдущем примере. Поскольку усреднение F функции f также является периодической функцией, формула для коэффициента в формуле обращения может быть сведена к следующей:  .

Здесь внутренняя сумма берется по всем целым неотрицательным ni, а внешняя – только по ki из интервала

Усреднения по путям

Пусть X – произвольное множество с покрытиями. Отметим, что задание покрытий в X эквивалентно заданию функции u(x,y) на X, такой, что u(x,y)=1, если y покрывает x, и u(x,y)=0 в противном случае.

Назовем путь на X полным слева, если он либо бесконечен влево (против стрел), либо имеет начальную точку, не покрывающую ни одного элемента из X (нет входящих стрел). Аналогично назовем путь на X полным справа, если он либо бесконечен вправо, либо имеет конечную точку, не покрываемую ни одним элементом из X (без исходящих стрел). Назовем путь полным, если он полон как слева, так и справа.

Свяжем с каждым полным слева путем s множество Bs его элементов и обозначим через B набор множеств Bs. Введем преобразование, относящее каждой финитной функции f(x) на X функцию  на множестве полных слева путей, заданную равенством

                                                     (16)

Тогда имеется очевидная формула восстановления. Назовем ограничением справа s(x) пути s часть этого пути, которая входит в фиксированную вершину x на этом пути (задание нового окончания пути в точке x). Ограничение справа полного слева пути тоже является полным слева путем. Поэтому множество B содержит все ограничения справа любого своего члена. Если s – один из путей (любой), содержащих точку x, и  – точка, которую x покрывает на этом пути, тогда

                                    (17)

Аналогичная формула верна и для полных справа путей, если использовать ограничения пути слева (задание нового начала пути) и точку  которая покрывает x на этом пути.

Для полных путей ситуация сложнее. Свяжем с каждым полным путем l множество  его элементов и обозначим через A набор множеств . Введем преобразование, относящее каждой финитной функции f(x) на X функцию  на множестве полных путей, заданную равенством:

                                                     (18)

Ставится задача восстановления функции f по функции F. Приведем ее решение для одного специального случая. Пусть X – множество с покрытиями, удовлетворяющее условию полумодулярности: если  и  покрывают элемент , то существует элемент  покрывающий  и .

Определение. Назовем точки   соседями, если они покрывают один и тот же элемент y. Из условия полумодулярности следует, что существует элемент , покрывающий x и .

Предложение 1. Для любых двух соседей x и  существует формула обращения, восстанавливающая разность  по функции F(l).

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

Таким образом, для восстановления функции f(x) по функции F(l) достаточно решить другую задачу: восстановить функцию f(x) по функции  , определенной на множестве пар соседей x и .

Отметим случай, когда эта задача явно решается для финитных функций на X. Назовем последовательность {xn} путем второго рода, если любые две точки xn и xn+1 этой последовательности являются соседями. Предположим, что для каждой точки x существует бесконечный вправо или влево путь {xn} второго рода. Пусть для определенности этот путь бесконечен вправо и x=xn. Тогда .

Эта сумма обрывается на конечном шаге для каждой финитной функции f(x).

Общая ситуация описывается следующим утверждением.

Теорема 6. Пусть функция f(x) имеет известный конечный носитель W на множестве с покрытиями X и заданы усреднения по полным путям F(l) вида (18). Задача восстановления функции разрешима, только если можно выбрать набор полных путей Q, в котором столько же элементов, что и в носителе W, и матрица инцидентности H, определенная формулой

,            (19)

не вырождена. Предполагается, что заданы некоторые произвольные нумерации точек из X и путей из Q. Условие  не зависит от нумерации строк и столбцов матрицы. Тогда наборы значений функций f(x) и F(l) превращаются в векторы и формула обращения имеет вид: . (Для доказательства достаточно заметить, что формулу (18) для путей из Q можно записать в виде: F=Hf.)

Пример эффективного обращения усреднения по полным путям

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

Предположим, точки из W и полные пути из Q пронумерованы так, что точка xÎW с номером n=n(x) принадлежит пути  с номером m(l)=n, причем остальные точки этого пути имеют более высокие номера:

                                (20)

Тогда матрица инцидентности (19) получается верхней треугольной порядка  с единичной диагональю. Ее определитель равен 1, а обращение не требует применения операций второй ступени и производится путем последовательных вычитаний, для чего необходимо не более N(N+1)/2 операций суммы и разности. Низкая обусловленность не снижает при этом точности вычислений.

Рассмотрим один из случаев, когда такая нумерация возможна. Пусть  Носитель функции f(x) – куб на решетке X вида W= . Общее число точек носителя . Граф на решетке X с единичными векторами  зададим весовой функцией

.    (21)

Элементы решетки будем записывать в векторной форме . Сопоставим каждой точке  полный путь по решетке:

  (22)

Это лестничная линия, идущая параллельно оси , со ступенькой по координате  в точке x. Первое подмножество объединения дает полный справа путь, а второе – полный слева, что обеспечивает полноту всего пути. Разным точкам x соответствуют разные полные пути. Тогда положим  Зададим нумерацию точек :

        (23)

Это лексикографический порядок векторов в кубе. Нумерацию полных путей из Q определим равенством  по (22,23). Легко видеть, что при  выполняется .

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

Список литературы

1. Radon J. Über die Bestimmung von Funktionen durch ihre Integralwerte längs gevisser Mannigfaltigkeiten. Ber. Verh. Königl. Sächs. Gesellsh. Leipzig, Math. Naturwiss. KI. 69 (1917), 262–277.

2. Гельфанд И.М., Граев М.И., Виленкин Н.Я. Интегральная геометрия и связанные с ней проблемы теории представлений. – М.: Физматгиз, 1962.

3. Гельфанд И.М., Гиндикин С.Г., Граев М.И. Избранные задачи интегральной геометрии. – М.: Добросвет, 2000. – 208 с.

4. Коганов А.В. Комбинаторные методы интегральной геометрии. // Сб.: Математика. Компьютер. Образование. – М.–Ижевск, 2005. – Вып. 12. – Ч. 2. – С. 746–758.

5. Koltsova S.V., Molchanov V.F. Radon Transform on Graphs and admissible complex. // Вестник ТГУ, 2006. – Т. 11. – Вып. 1. – С. 41–48.

6. Гиндикин С.Г. Дискретное преобразование Радона. // Сиб. матем. журн. – 1966. – № 3. – С. 708–712.