Software & Systems

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

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

Понятие изображения

Определение 1. Под непрерывным изображением будем понимать функцию f(x,y), определенную на подмножестве Р плоскости R2 и принимающую действительные значения. Значение функции f(x,y) определяет яркость изображения в точке (x,y).

Будем считать, что каждому изображению f можно поставить в соответствие конечный набор признаков X={X1,X2,…,Xk}, однозначно определяющий f среди множества других изображений, заданных на Р.

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

В связи с этим вводится набор операторов О, таких, что

, ,…, . (1)

Пусть также для каждого набора X каким-либо образом определено расстояние между двумя изображениями:

, .  (2)

Последовательность изображений

Определение 2. Последовательностью изображений назовем, каким-либо образом упорядоченное некоторое множество изображений f, присвоив каждому его элементу индекс

.                                              (3)

Так как каждое изображение из исходного множества f однозначно характеризуется набором признаков X, можно построить тождественную (3) последовательность

{Xn}={X0, X1, X2 …}.                                             (4)

Определение 3. Вектор А назовем пределом последовательности {Xn}, если для всякого e >0 найдется (зависящее от e) число n0=n0(e), такое, что выполняется неравенство  для всех (натуральных) n>n0.

Запишем это как {Xn}®А.                                      (5)

Определение 4. Так как {fn} однозначно определяется {Xn}, будем говорить, что последовательность изображений {fn} сходится к пределу g по множеству признаков Х:

.                                                          (6)

Вектор А можно интерпретировать как некоторый эталон (значения вектора признаков Х эталонного изображения).

Теорема 1. На f можно сформировать множество нестрого упорядоченных последовательностей {fn}Х, каждая из которых сходится по некоторому множеству признаков Х, для определенного расстояния .

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

Определение 5. Пусть Р1 и Р2 – два подмножества пространства Р, причем Р1ÍР2. Тогда будем говорить, что на Р2 определен оператор формирования последовательности Т: Р2®Р1, если каждому элементу (i2,j2)ÎР2 изображения f2 можно поставить в соответствие элемент (i1,j1)ÎР1 изображения f1.

Наследственность и изменчивость признаков последовательности изображений

Наибольший интерес для изучения представляют последовательности, в которых между изображениями обнаруживается некоторая связь. На практике это означает, что если имеется некоторая последовательность изображений {fn}, упорядоченная по какому-либо набору признаков X, то соседние изображения в этой последовательности могут иметь некоторую степень сходства (подобия). То есть если некоторый признак х присутствует, на изображении fkÎ{fn}, то весьма вероятно, что он проявится и на соседних изображениях fk-1Î{fn} и fk+1Î{fn}, k=1,…,N-2.

Это позволяет говорить о наличии фактора наследственности признаков в последовательности изображений.

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

Это можно охарактеризовать как изменчивость признаков в последовательности изображений.

Пусть имеется последовательность , для которой {Xn}®А.

Рассмотрим последовательность, составленную из элементов {Xn}, определяющих один и тот же признак (например, какой-нибудь i-й признак) для всех изображений исходной последовательности

Oi[{fn}]={Oi [f0], Oi [f1],…,Oi [fn]},

{x(i)n} = {x0(i), x1(i),… xn(i)}.                                   (7)

Для описания поведения одного признака на последовательности изображений предлагается использовать математический аппарат нечетких множеств. Действительно, один и тот же признак (особенность) может проявлять себя в той или иной мере на нескольких изображениях, постоянно при этом изменяясь. Однако в результате таких изменений он может либо исчезнуть, либо измениться настолько, что будет рассматриваться уже как другой независимый признак (особенность). Для характеристики наличия признака xj(i) на изображении fj введем оператор принадлежности mi.

Определение 6. Оператором принадлежности признака назовем оператор, определяющий уровень вхождения признака x(i) в нечеткое множество Х(i), то есть степень соответствия отдельной реализации признака на последовательности изображений его предельному (эталонному) значению ai, aiÎA, {Xn}®А.

mi : mi[xj(i)]®[0,1].                                                 (8)

Тогда каждому набору признаков Хj изображения fjÎ{fn} можно поставить в соответствие вектор m Хj = (m1х1, m2х2, .. mkхk )Т, где k – число признаков.

Для каждого признака введем пороговый оператор

Г: Гmi[xj(i)]®{0,1}.                                               (9)

В результате применения (9) к исходному вектору Хj, характеризующему изображение fj, получим некоторый вектор Wj, состоящий из нулей и единиц:

W=(w1,w2,…,wк)Т, wiÎ{0,1}, i=1,2,…k.           (10)

Ясно, что при этом последовательности реализаций некоторого признака на последовательности изображений (7) также будет соответствовать последовательность, состоящая из нулей и единиц:

Q={q1,q2,…,qn}, qjÎ{0,1}, j=1,2,…,n.              (11)

Пусть имеются два соседних изображения fm и fm+1 последовательности {fn}. Им соответствуют векторы Wm и Wm+1. Рассмотрим пары элементов (wmi, wm+1i), i = 1, 2,..k. Совпадение элементов в такой паре означает, что на обоих изображениях fm и fm+1 либо присутствует один и тот же признак, либо его нет на обоих изображениях. То есть фактически количество совпадающих пар (wmi, wm+1i) будет характеризовать сходство двух изображений по заданному набору признаков Х.

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

Для характеристики изменчивости можно, например, воспользоваться выражением:

,             (12)

где Å  – операция неравнозначности (сумма по модулю 2).

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

.               (13)

Теорема 2. Последовательность изображений {fn}, для которой, начиная с некоторого индекса n0, для определенного набора признаков Х выполняется , i=n0,...,n, сходится по набору признаков Х.

Последовательности дополнений

Изменчивость, сопутствующая отображению fk-1=Тfk, приводит к исчезновению на fk-1 части особенностей, присущих fk. Обозначим через fk\fk-1 изображение, являющееся результатом воздействия на fk некоторого оператора Т* и сохраняющее признаки (особенности), исчезающие при переходе от fk к fk-1.

При этом для каждого fk из последовательности {fn} выполняется:

если Тfk = fk-1, Т* fk = fk\ fk-1, то, применяя (1), (8) и (9), получим:

O[fk-1] = Xk-1,                           Гm[ Xk] = Wk;

O[Тfk] = O[fk-1] = Xk-1,                  Гm[ Xk] = W*k;

O[Т* fk] = O[fk\ fk-1] = X*k-1,   Гm[ Xk] = Wk-1.

При этом

Wk = Wk-1 + W*k.                                                     (14)

Определение 9. Назовем оператор Т* дополнительным к оператору Т, если выполняется усло- вие (14).

Обозначим gi = fi\ fi-1.                                          (15)

Определение 10. Назовем {gn} последовательностью дополнений последовательности {fn}, если  для каждого fiÎ{fn} есть соответствующее ему giÎ{gn}, такое, что Т* fi = gi.

Теорема 3. Если последовательность изображений {fn} сходится по  набору признаков Х к некоторому вектору А, то последовательность дополнений {gn} сходится по тому же набору признаков Х к нулевому вектору 0 той же размерности, что и А.

В случае существования Т* вызывает интерес возможность построения оператора , такого, что

fi¢=Т(fi)Т*(fi )                                                       (16)

или, согласно (15),

fi¢=fi-1gi,                                                               (17)

причем для каждого fi и fi выполняется , или, иначе:

.                            (18)

То есть оператор  может и не давать точного восстановления изображения fiÎ{fn} по предыдущему изображению последовательности fi-1Î{fn} и дополнению giÎ{gn}, но он формирует такое изображение fi¢, которое совпадает с fi по некоторому набору признаков XÎX.

Пусть имеется последовательность {gn}=Т*{fn}, оператор  обеспечивает восстановление только в смысле условия (18). Известно изображение fk Î{fn}.

Определение 11. Назовем

 оценкой изображения fk+mÎ{fn} по изображению fkÎ{fn} на основе последовательности {gn} с помощью оператора .

Сходство двух изображений по определенному набору признаков можно определить на основе понятия изменчивости (20). Отсюда можно вывести выражение, характеризующее точность оператора восстановления:

.                                   (19)

Выражение (19) определяет величину изменчивости изображения fkÎ{fn } по отношению к его оценке fk(m) по изображению fk-mÎ{fn }. Для характеристики оператора  на всей последовательности (19) усредняется по k:

.             (20)

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

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