Интенсивное развитие за последние 40 лет технических средств регистрации и обработки изображений привело к бурному росту числа методов и алгоритмов обработки и анализа изображений. По широте используемого математического аппарата эти методы покрывают практически все разделы современной математики. В то же время привлечение разнообразного математического аппарата не всегда сопровождалось качественным анализом разработанных методов и алгоритмов. Как правило, при анализе алгоритмов доминировал статистический подход, выбор параметров алгоритмов осуществлялся путем обучения по выборке образов некоторого класса. Это не всегда позволяло найти качественные аналитические закономерности работы алгоритмов для разных классов изображений, найти оптимальные значений параметров, спрогнозировать результаты работы «похожих» алгоритмов или применение алгоритмов для других классов изображений и т. д.
Кроме того, одним из ключевых требований, предъявляемых к методам обработки и анализа изображений, является необходимость учитывать высокую степень неопределенности обрабатываемой графической информации. Характер неопределенностей может быть различен, по условно их можно разделить на две группы:
1) неопределенности, связанные с аппаратным зашумлением, оцифровкой и квантованием изображений, перекрытием объектов, наличием бликов, теней и т. д.;
2) неопределенности, связанные с выделением информативных признаков объекта, а, следовательно, и с построением моделей изображаемого объекта, обусловленные тем, что любое изображение объекта не обладает полнотой информации об его геометрических свойствах.
Необходимость выделения информативных признаков объектов на изображении в условиях неопределенности выдвигает на первый план решение следующих задач: а) нахождение робастных к зашумлению локальных информативных признаков объектов на изображенииб) формирование робастных к зашумлению высокоуровневых представлений и описаний изображений объектов, являющихся результатом агрегирования информации о локальных признакахв) нахождение минимальных, информативных, устойчивых к зашумлению векторных представлений и описаний изображенийг) оценка количества неопределенности в том или ином представлении объектовд) ранжирование неопределенностей и т. д.
Решению этих и смежных задач посвящена настоящая диссертационная работа.
Кратко рассмотрим основные подходы и методы выделения информативных признаков объектов на изображениях, методы формирования высокоуровневых представлений и описаний изображений объектов, обращая особое внимание на степень их робастности к зашумлениям.
Для анализа и распознавания объектов на изображении, как правило, стараются выделить на нем некоторые особенности. Различают низкоуровневые и высокоуровневые особенности.
Под низкоуровневыми обычно понимают такие особенности [1], которые могут быть выделены на изображении без использования информации о форме объекта или, другими словами, о пространственном расположение отдельных частей объекта. Напротив, для выделения высокоуровневых признаков используется информация о пространственном расположении частей объекта. Можно сказать, что низкоуровневые особенности являются локальными признаками объекта, а высокоуровневые — глобальными.
К низкоуровневым особенностям, прежде всего, относят края изображения, кривизну кривой, описывающей край объекта и некоторые другие.
Под высокоуровневыми особенностями понимают, как правило, форму объекта, или то или иное, удобное для дальнейшего распознавания, представление формы объекта. Часто высокоуровневые особенности на изображении выделяют путем анализа и обработки низкоуровневых особенностей.
При выделении и высокоуровневых и низкоуровневых особенностей на изображении следует учитывать, что реальное изображения является зашум-ленным. Причины шумов на изображении могут быть разными и они, а также характер этих шумов довольно подробно проанализированы в литературе.
2,3].
Однако значительно меньше внимания в литературе уделено вопросам влияние зашумления на выделение низкоуровневых и высокоуровневых особенностей на изображении. Одна из целей настоящей работы — восполнить этот пробел. В частности, в работе будут рассмотрены основные подходы к вычислению оценок кривизны плоской оцифрованной зашумленной кривой и вычислены такие качественные характеристики случайной оценки кривизны, как систематическая ошибка, случайная ошибка и смещение. Анализируя эти качественные характеристики, можно сделать вывод, какие из существующих подходов могут быть предпочтительными при вычислении оценок кривизны, учитывая уровень зашумления изображения, его характер, быстроту обработки, вид изображения, цель использования оценок кривизны и другие факторы.
Кривизна, наряду с краем, является одной из важнейших низкоуровневых особенностей изображения. Можно выделить следующие области применения оценок кривизны:
1) для получения аналитических характеристик формы объекта [2]. Существуют различные аналитические характеристики формы: функция кривизны контура, функция наклона контура, дескрипторы Фурье, моменты изображения и т. д. Одной из основных аналитических характеристик изображения кривой является функция ее кривизны. Функция кривизны вместе с функцией наклона однозначно определяют кривую.
2) для получения информативных признаков изображения (контрольных, доминантных точек) с целыо последующего преобразования системы первичных признаков в систему инвариантных векторных представлений и дальнейшего решения задач классификации, распознавания, компактного храпения и быстрой обработки. Например, в геоинформатике для векторного представления объектов изображения необходимо решать задачу полигональной аппроксимации кривых на изображенияхв компьютерной графике для быстроты обработки гладкие кривые и поверхности аппроксимируются полигональными кривыми и полиэдральными поверхностями.
3) в конечно-элементном анализе для построения эффективных процедур разбиения области, ограниченной кривой, на конечные элементы можно использовать полигональное представление этой кривой.
4) для построения алгоритмов оптимальной интерполяции точечных данных кривой, имеющей наименьшую интегральную кривизну и минимизирующей некоторые другие функционалы (например, длину). Из физических соображений такие кривые еще называют кривыми минимальной энергии.
Для плоской гладкой кривой кривизну k (g) в точке g можно определить как скорость изменения направления касательного вектора при движении точки по кривой, т. е. k (g) = 0[(g), где 0(g) — функции наклона (угол между касательной и положительным направлением оси Ох) и производная берется по длине дуги s. Точки, где направление касательного вектора быстро изменяется, являются точками высокой кривизны. Эти точки будут более информативными, чем точки кривой с низкой кривизной в том смысле, что положение именно этих точек на изображении определяет форму объекта. Проведенные еще в 50-х годах прошлого века психологические исследования [4] показали, что человеческое восприятие остается практически инвариантным при замене контурного изображения его полигональным представлением, построенным по точкам высокой кривизны. Поэтому точки высокой кривизны (в литературе их часто называют контрольными, доминантными или угловыми точками) служат, прежде всего, для построения высокоуровневых описаний изображений объектов.
Кривизна относится к тем понятиям классической (в данном случае, дифференциальной) геометрии, которые не имеют однозначного аналога в цифровой геометрии, занимающейся изучением свойств точечных множеств, полученных в результате дискретизации плоских или пространственных фигур. Действительно, если Г — гладкая кривая на плоскости R2, то кривизну можно рассматривать как результат действия на Г некоторого, вообще говоря, нелинейного оператора CurR k (g) = Смгд[r](g) для всех geT, определенного на множестве CX (R2) всех гладких кривых плоскости R2. В цифровой геометрии все геометрическое объекты рассматриваются на некотором базовом дискретном множестве (сетке), например, на Z2. Переход с плоскости R2 на сетку Z2 осуществляется с помощью некоторого оператора дискретизации D: R2 —> Z2, который является всюду определенным, сюръектив-ным, но не инъективным. Оператор D ставит в соответствие гладкой кривой.
Г с R2 оцифрованную кривую Т = D (Y)aZ2. Пусть CD{Z2) = {f = £>(Г): ГеСЧД2)}. Возникает вопрос, как определить «кривизну» оцифрованной кривой Г, если оператор вычисления кривизны CurR, заданный на множестве CR2), не определен на множестве CD (Z2)1 Аналогичный вопрос возникает при попытке перенести многие понятия классической геометрии на множество Z2. В общем случае под оценкой кривизны дискретной (оцифрованной) кривой Г в точке gef будем понимать такую скалярную функцию кЕ (g), зависящую от векторного параметра ?, что для гладкой кривой Ге Cl (R2) выполняется равенство limкс (g) = k (g) для всех geT, где ?0 — некоторое.
L->E0 значение вектора параметров. Чаще всего параметр е характеризует размер окрестности, в пределах которой вычисляется оценка. Пусть? c (g) =.
CurZc[r](g). Теоретически существует три подхода к определению оператора кривизны Сиг2г на CD (Z2):
1) CurzjE = CurR о /?, где /Е: CD (Z2) —> C'(fi2) — оператор локальной интерполяции цифровой кривой;
2) Curz е = CurR о Аг, где Аг: CD (Z2) —> C'(i?2) — некоторый оператор гладкой локальной аппроксимации цифровой кривой;
3) CurZL = М (Curz ],., Cutгде М — оператор агрегирования (усреднения), a Curz^P^ - операторы кривизны, найденные 1-м или 2-м способами.
Заметим, что во втором подходе кроме явных способов построения гладкой аппроксимации дискретной кривой существуют и неявные схемы следующего вида. Пусть X = R или X — Z и кривой Гс!2 оператор? Л,(Г) ставит в соответствие некоторую локальную характеристику (вообще говоря, векторную) q. Например, ^(Г) — площадь, ограниченная кривой Г в пределах некоторой окрестностиq® — вектор изменения интенсивностей в разных направлениях полутонового изображения, содержащего кривуюд (Г) -отношение длины хорды, стягиваемой кривой к расстоянию от кривой до хорды. Характеристика q должна быть определенной и для гладких и для цифровых кривых. Тогда аппроксимирующий оператор, А можно искать в виде, А = Z" 1 о Lz. Так как оператор Lz является сюръективным, но не инъек-тивным, то оператор L" 1 не определяется однозначно. Причем степень неопределенности в выборе L" 1 будет тем меньше, чем точнее будет определен класс аппроксимирующих кривых в С1 (Л2). В качестве такого класса обычно используются алгебраические кривые. Неявная схема аппроксимации обладает следующей очень важной особенностью. Если характеристика q =LZ (T) является устойчивой к зашумлению кривой Г (например, <�у (Г) — площадь, ограниченная кривой Г в пределах некоторой окрестности), то и оценка кривизны, полученная с помощью такой схемы, будет устойчивой к зашумлению изображения.
Кроме алгоритмов оценивания кривизны широко распространены так называемые детекторы углов, не связанные явно с вычислением кривизны. Как правило, в этих алгоритмах неявно вычисляется некоторая функция от кривизны. В настоящее время известно около 100 алгоритмов оценки кривизны и детекторов углов плоских оцифрованных кривых. Кратко охарактеризуем основные алгоритмы оценивания кривизны в соответствии с вышеуказанной схемой классификации.
Если в первом подходе / - интерполяционный многочлен, то этот подход связан с заменой дифференциального оператора кривизны разностным (сеточным) аналогом. Например, если 6(g) — функции наклона кривой, то оценка кривизны в точке gможет быть найдена по формуле (g/) = (^Cg/+1) —))/('y (g/+i) — -yCgf-i)), где s (g) — функция длины кривой (нижний индекс кривизны указывает на то, что оценка вычисляется на трехточечном шаблоне ={-1,0,1}). Для параметризованной кривой (x (t), y (t)), teT, Т — дискретное множество, оценку функции в можно найти на том же шаблоне по формуле 0(gi) = artcg ((y (ti+[)-у ((ы))/(х01+[)-х ((^))). Недостатком этого метода является то, что полученные таким образом оценки кривизны существенно будут зависеть от дискретизации кривой и будут совершенно неустойчивыми к зашумлению кривой. Этот способ можно сделать менее чувствительным к значениям отдельных данных, если вычислять значения разностных производных не на трехточечном шаблоне S{, а па некотором большем шаблоне. Такой способ оценки кривизны рассматривался в 70-х годах прошлого века в алгоритме Bennet и MacDonald [5] по выделению угловых точек. В алгоритме Freeman и Davis [6] вычислялись первичные оценки кривизны с помощью алгоритма [5], а затем реализовывался третий подход — рассматривалось усреднение s подряд идущих первичных оценок для разных ^ значений шагов интерполяции (обычно выбирались 3.
Кроме интерполирования многочленами в ряде алгоритмов применяется интерполирование окружностью. Так, например, в известном детекторе Chetverikov и Szabo [10] определялась окружность наименьшего радиуса, описанная вокруг треугольника, вписанного в оцифрованную кривую, одна из вершин которого — точка оценки кривизны. Кроме того, во многих детекторах углов и алгоритмах сегментации кривых используется так называемая мера расстояния между хордой и стягиваемой ее дугой кривой. В главе 1 будет показано, что эта мера связана с радиусом интерполирующей окружности. Поэтому все методы детекции углов и сегментации кривых, основанные на вычислении этой меры, можно отнести к методам первого подхода. В частности, мера расстояния между хордой и стягиваемой ее дугой использовалась в таких популярных алгоритмах, как в алгоритме Douglas-Peucker [11], алгоритме Rutkowski и Rosenfeld [12], в алгоритме Ramer [13] и др..
Второй подход к вычислению оценок кривизны основан на гладкой аппроксимации дискретной кривой и нахождению кривизны аппроксимирующей функции. Причем, как указывалась выше, аппроксимация может быть явной и неявной. Явная квадратичная аппроксимация дискретных данных в 90-е годы прошлого века была реализована, например, в алгоритмах [14] и [15]. Явная аппроксимация окружностью рассматривалась, например, в алгоритмах [16]. Предварительное сглаживание кривой с помощью гауссовского ядра рассматривалось в алгоритмах Mokhtarian и Mackworth [17], Pei и Lin [18], Rattarangsi и Chin [19]. Выделение точек высокой кривизны для различных значений параметров гладкости ядра получило развитие в так называемом пространственно-масштабном представлении {scale-space representation). В ряде алгоритмов была реализована неявная схема аппроксимации. В частности, широкое распространение получили алгоритмы неявной аппроксимации, в которых в качестве характеристики я (Г) рассматривался вектор изменения интенсивностей в разных направлениях полутонового изображения, содержащего кривую. Например, в работе [20] по активным контурам был предложен следующий алгоритм оценивания кривизны по изменению интенсивности в точке. В каждой точке (х, у) изображения рассматривается функция <�р (х, у), численно равная углу градиента изображения в данной точке. Затем в направлениях (р + кл/2, к = 0,1,2,3, оценивается изменение функции (р (х, у). Показано, что это изменение является функцией координат градиента функции изображения, который оценивается численно с помощью известных разностных схем. Изменение функции (р (х, у) будет оценкой кривизны в данном направлении. Тот же подход — вычисление оценки кривизны по изменению интенсивности функции изображения в четырех перпендикулярных направлениях в пределах некоторой окрестности, был применен в так называемом детекторе Харриса [21]. Этот алгоритм основан на том наблюдении, что для точек высокой кривизны такие изменения будут достаточно большими по всем направлениямдля точек низкой кривизны в двух колли-неарных направлениях изменения интенсивности будут большими, а в перпендикулярном направлении — небольшиминаконец, если точка вообще не является краевой, то эти изменения будут небольшими по всем направлениям. Преимуществом этого подхода является то, что он пригоден и для оценивания кривизны полутонового изображения, на котором не выделены кривые. Более того, используя этот подход можно совместить процедуру выделения краев и выделения точек высокой кривизны..
Третий подход к вычислению оценок кривизны связан с применением агрегирующего (усредняющего) оператора к первичным оценкам кривизны, найденным первым или вторым способами. Применение такого оператора интегрирует информацию о кривизне, полученную с помощью других процедур. Так в алгоритме Freeman и Davis [6] осуществлялось усреднение первичных оценок кривизны, найденных с помощью разностного оператора кривизны. В алгоритме Chetverikov и Szabo [10] усредняющий оператор применялся к первичным оценкам кривизны, найденным методом интерполирования дискретных данных окружностью. Общий подход применения усредняющего оператора, а именно усредняющего интегрального оператора Соболева, был реализован в так называемом детекторе Кэнни [22], который является наиболее популярным (и в определенном смысле оптимальным) способом выделения краев на изображении. Применительно к оцениванию кривизны детектор Кэнни представляет собой свертку первичных дифференциальных оценок кривизны (или оценок первообразных кривизны — функции наклона в) с усредняющим гладким ядром (например, с равномерным или с гауссовским ядрами)..
Завершая обзор основных методов вычисления оценок кривизны, можно сделать следующий вывод. Первый способ вычисления оценки кривизны сам по себе, без дальнейшего агрегирования информации, применялся только в ранних алгоритмах. Позднее, для того чтобы сделать алгоритмы более ро-бастными к дискретизации и зашумлению кривой, разностный подход к вычислению оценок кривизны стали дополнять процедурой усреднения. Параллельно с этим широкое распространение получил и второй — аппроксимативный подход. Причем в этом подходе можно выделить два направления — явная и неявная аппроксимация. Второе направление — неявная аппроксимация позволяет совмещать вычисление оценок кривизны с другими процедурами низкоуровневой обработки. Кроме того, и первый и второй подходы в некоторых алгоритмах дополняются процедурой агрегирования. Подчеркнем, что такая классификация алгоритмов является достаточной условной. Действительно, если оценка кривизны вычисляется по схеме усреднения разностных оценок: CurzгM (Curz,., Curzp^), то оператор, А = Сиг~ °.
M (Curzl,., Curz'^), А: CD (Z2) С1 (R2) можно считать оператором гладкой аппроксимации цифровой кривой..
Существуют различные критерии оценки качества алгоритмов детекции угловых точек и оценивания кривизны. Основными критериями оценивания качества таких алгоритмов являются следующие [10]:.
1) селективность, т. е. частота правильной детекции угловых точек должна быть высокой, а неправильной детекции — низкой-.
2) каждая угловая точка должна детектироваться единожды-.
3) точность расположения угловых точек или точность оценки кривизны-.
4) робастность к зашумлению-.
5) робастность к параметрам-.
6) легкость настройки параметров-.
7) скорость работы алгоритма..
В настоящей работе основное внимание будет уделено анализу точности и устойчивости к зашумлению оценок кривизны. Под точностью (систематической ошибкой) оценки kc (g) кривизны k (g) в точке geT будем понимать величину sc = ke (g)-k (g). Если дискретная кривая подвергнута аддитивному вероятностному зашумлении, то оценка кривизны будет случайной величинойc (g), которая качественно характеризуется величиной смещения bz = |E[ATJ — |, где Е[-] - оператор математического ожидания, и величиной случайной ошибки (дисперсии) Оценку A" ?(g) будем называть устойчивой к заданному зашумлению при выполнении условий: a) lim|E[^J-/cl = 0- б) 1пп<�т2[^] = 0. Если <52[Кг] = 0(£-а), |Е|Хе]-/се| = €—€—.
0(е~р), то числа а,{3>0 характеризуют степень устойчивости оценки кривизны к зашумлению..
Поскольку кривизна является локальным свойством кривой, то, точную оценку кривизны молено получить только в небольшом «окне». С другой стороны, чем меньше «окно» обработки дискретных данных, тем менее устойчивой к зашумлению будет полученная оценка. Поэтому, как правило, чем точнее алгоритм вычисляет оценку кривизны, тем больше значения смещения и случайной ошибки у этой оценки и наоборот..
С точки зрения точности и устойчивости к зашумлению способы оценивания кривизны можно (достаточно условно) разделить на две группы: локально-интерполяционные и локально-аппроксимативные..
К локально-интерполяционным оценкам будем относить те, в которых реализуется первый из указанных выше подходов, связанный с локальной интерполяцией дискретных данных и последующим вычислением кривизны интерполирующей функции, дополненный, быть может, процедурой агрегирования оценок. К этой группе методов можно отнести: 1) методы, связанные с заменой дифференциального оператора кривизны разностным аналогом- 2) методы усреднения дифференциальных оценок (например, алгоритм Freeman и Davis и др.) — 3) методы, основанные на использовании сглаживающих интегральных операторов (детектор Кэнни)..
К другой группе методов, назовем их методами локально-аппроксимативного оценивания кривизны, будем относить те, в которых реализуется второй из указанных выше подходов, дополненный, быть может, процедурой агрегирования первичных оценок кривизны. К этой группе методов можно отнести: 1) методы явной аппроксимации дискретных данных функциями из некоторого класса- 2) методы неявной аппроксимации, в том числе основанные на вычислении изменения интенсивностей в разных направлениях полутонового изображения (детектор Харриса и др.)..
Можно ожидать, что при использовании методов первой группы систематическая ошибка оценки кривизны будет меньше, чем при использовании методов второй группы, а величины смещения и случайной ошибки будут меньше при использовании методов второй группы..
В работе будут проанализированы точность и устойчивость к зашумлению некоторых «модельных» алгоритмов, реализующих основные схемы вычисления локально-интерполяционных и локально-аппроксимативных оценок кривизны..
Для получения компактных представлений объектов изображения осуществляется агрегирование низкоуровневых признаков изображения. В результате получаются высокоуровневые представления и описания изображений объектов, в частности, кривых. Необходимость в компактном представлении кривых возникает при сжатии изображений, векторизации изображений объектов, в компьютерной графике и др. В общем случае оцифрованная точечная кривая Г зависит от множества параметров, число которых может быть равно количеству точек кривой. Тогда задача представления кривой состоит в нахождении кривой Г', зависящей от меньшего числа парахметров, которая сохраняла бы основную информацию о форме кривой Г. Множество методов решения этой задачи можно условно разбить на две группы — группу аппроксимативных методов и группу интерполяционных методов..
Методы первой группы основаны на замене оцифрованной кривой Г такой кривой из некоторого фиксированного класса, которая удовлетворяла бы определенным условиям «близости». Наиболее популярными аппроксимативными способами представления кривой являются методы, использующие многочлены Безье и В-сплайны [23, 24]. Применение этих методов требует предварительного определения узлов сплайнов или точек-ориентиров, а эта задача практически равносильна общей постановке задачи представления кривой..
Методы второй группы предполагает выбор некоторого множества точек на кривой Г и замену каждого участка кривой между двумя соседними точками другой кривой из фиксированного класса, исходя из определенных условий оптимальности. В качестве класса интерполяционных кривых чаще всего рассматриваются отрезки прямых, дуги окружностей [25], алгебраические кривые небольшого порядка. Кусочно-липейная интерполяция в литературе называется полигональным представлением кривой..
Таким образом, задача получения полигонального представления кривой (в том числе замкнутой кривой — контура) состоит в построении ломаной (многоугольника в случае полигональной аппроксимации замкнутого контуpa) с вершинами на кривой, которая сохраняла бы основную информацию о форме кривой..
Существуют два основных подхода к решению этой задачи: эвристический и оптимизационный. К алгоритмам первого подхода относят алгоритмы, основанные на выделении доминантных точек, алгоритмы, основанные на применении процедур слияния и разбиения сторон многоугольника (например, методы, использующие «подбор концевых точек» — алгоритмы Douglas-Peucker и др.), генетические алгоритмы [26], алгоритмы многократного сглаживания [27], алгоритмы, использующие нечеткую логику [28] и др. Эти алгоритмы, как правило, являются быстрыми, но не оптимальными..
Во втором подходе находится такая аппроксимирующая ломаная, которая удовлетворяла бы определенному условию оптимальности. В качестве критериев оптимальности рассматриваются, например, следующие:.
1) многоугольник с фиксированным числом вершин должен иметь наименьший периметр [29]-.
2) максимальное расстояние от точек кривой до сторон многоугольника должно быть минимальным [13, 30, 31]-.
3) число сторон многоугольника вместе с погрешностью аппроксимации должно быть минимальным [32−35]-.
4) площадь симметрической разности между множеством, ограниченным замкнутой кривой и множеством, ограниченным многоугольником, должна быть минимальной [36, 37]-.
5) погрешность аппроксимации многоугольником с фиксированной длиной стороны должна быть минимальной [38]..
Таким образом, алгоритмы второго подхода являются алгоритмами нелинейной оптимизации с ограничениями. Заметим, что большинство из указанных выше алгоритмов являются субоптимальными. Как правило, для улучшения сходимости и уменьшения числа итераций оптимизационных алгоритмов предварительно строится «хорошее» полигональное приближение к оптимальному решению путем определенного выбора точек высокой кривизны. После чего «запускается» тот или иной метод нелинейного программирования. Следует отметить, что лучшие из оптимизационных алгоритмов при нахождении оптимальных полигональных представлений замкнутых оцифрованных кривых, содержащих п точек, имеют вычислительную сложность порядка О (п^) [39]..
Практически все подходы к нахождению компактного представления кривой предполагают предварительное определение так называемого базового множества точек кривой и последующую его оптимизацию в соответствии с выбранным критерием. В качестве базового множества, как правило, выбирается множество точек высокой кривизны..
В работах [40, 41] был предложен новый подход к решению задачи нахождения минимального полигонального представления замкнутой кривой, основанный на применении монотонной меры информативности, определенной на упорядоченных подмножествах точек кривой. Примерами таких мер могут быть нормированная (к длине всего контура) длина замкнутой ломаной с вершинами в точках подмножества, или нормированная (к площади, ограниченной кривой) площадь многоугольника с вершинами в точках подмножества, если многоугольник — выпуклый. В указанных работах были исследованы как общие свойства мер информативности контура, так и свойства конкретных мер. Были также рассмотрены различные постановки задач нахождения оптимального полигонального представления по мере информативности, найдены условия, накладываемые на меру информативности, позволяющие организовать эффективную процедуру поиска оптимального контура..
Вместе с тем, новые постановки задач агрегирования информативных признаков, требуют дальнейшего исследования свойств мер информативности. В диссертационной работе исследование мер информативности будет осуществлено по нескольким направлениям. Первое направление связано с исследованием общих свойств мер информативности, которые представляют собой нормированные усреднения значений информативных признаков — так называемые усредненные меры информативности. В частности, будут подробно рассмотрены усредненные меры информативности по кривизне. Второе направление связано с исследованием мер информативности зашумлен-ных кривых. В этом случае мера информативности будет стохастической. Возникает задача нахождения такого представления кривой, стохастическая мера информативности которого будет иметь наименьшую дисперсию (такое представление будем называть устойчивым к зашумлению относительно данной меры информативности)..
Для решения задачи распознавания контурных изображений, как правило, непосредственно полигональные представления кривых не используются, поскольку они не являются инвариантными относительно аффинных преобразований плоскости. Поэтому, кроме полигональных рассматривают так называемые векторные представления кривых..
Векторное представление кривой это описание кривой множеством векторов, удобное для дальнейшего решения задачи распознавания. Основными требованиями к векторному представлению плоской кривой являются:.
1) инвариантность относительно определенной группы геометрических (обычно — аффинных) преобразований плоскости-.
2) компактность представления-.
3) однозначность восстановления полигонального представления с точностью до гомотетии..
Векторное представление, как правило, получают в результате преобразования полигонального представления кривой..
Существуют несколько подходов к построению векторных представлений. Первый подход предполагает, что если сравниваемое изображение кривой и модельная кривая принадлежат одному классу, то существует геометрическое преобразование из некоторой группы, которое минимизирует меру расхождения между двумя кривыми. Поэтому в этом подходе векторное представление должно, прежде всего, обеспечивать однозначность восстановления полигонального представления и обладать высокой геометрической информативностью (т.е. содержать «много» геометрической информации о кривой). Например, в работе [42] рассматривалось векторное представление контура, состоящее из двух векторов — вектора отношений длин сторон многоугольника к длине первого ребра и вектора внутренних углов многоугольника. Зная положение и ориентацию первой стороны многоугольника (4-е параметра) по такому векторному представлению можно однозначно найти положение и ориентацию всех сторон многоугольника. Указанное векторное представление использовалось для решения оптимизационной задачи нахождения такого соответствия между двумя контурами, один из которых задан векторным представлением, при котором величина среднеквадратичной ошибки расстояний от всех точек кривой до ближайших сторон многоугольника будет наименьшей..
Более сложное векторное представление рассматривалось в работе [43]. Это представление состояло из векторов, содержащих не только информацию о сторонах и углах полигонального представления, но и интервальную информацию о возможных диапазонах изменения этих параметров для указанного класса объектов..
Другой подход к построению векторного представления — символьное представление, ставит в соответствии полигональному представлению кривой (или всей кривой) некоторое множество геометрических примитивов (например, ломаных определенного вида) и множество отношений между этими примитивами. Эти множества кодируются некоторыми символами, которые в дальнейшем на этапе распознавания классифицируются с помощью так называемых синтаксических (структурных) методов распознавания [44]. Такие представления в диссертации не рассматриваются..
Кроме векторных представлений в задачах распознавания рассматриваются различные способы описания кривых, например, дескрипторы Фурье, которые, как правило, обладают указанными выше свойствами инвариантности, но не предполагают однозначного восстановления полигонального представления. ..
В работе рассматриваются некоторые способы векторного представления и описания кривых, а также исследуется робастность таких представлений и описаний к зашумлению изображений..
При использовании меры информативности для описания представлений дискретной кривой Г, мы можем столкнуться с неопределенностью вычисления значения меры информативности ju (A) представления А, если нам известны только значения информативных признаков а>{g) всех точек geT. Эта неопределенность обусловлена тем, что в мере информативности /и{А) может агрегироваться информация не только об отдельных точках представления А, но и более сложная информация о структурной зависимости между информативностями отдельных точек относительно выбранного признака хп. Такая информативная неопределенность присуща любой неаддитивной мере и связана с информационной недостаточностью или с отсутствием описания структурной зависимости между информативностями отдельных точек. Таким образом, количество неопределенности об объекте, описываемом мерой информативности, связано с количеством информации об этом объекте..
Существуют разные подходы к определению информативности (количества информации) объекта или системы. Это и вероятностный подход, в котором количество информации определяется как величина, равная изменению неопределенности системы при осуществлении некоторого опыта, а [45]: 1{ос) = S{p)-Sa (p). Сама неопределенность системы S (p), следуя К. Шеннону [46], определяется как степень неопределенности нахождения системы в одном из состояний: S (p) = р, log2 pt, если нахождение системы в этих состояниях описывается вероятностным распределением р = {/?,}. Это и вычислительный (или алгоритмический) подход [47], в котором количество информации об образе равно длине его наименьшего описания в некотором стандартном языке (например, длине наименьшей программы для стандартной машины Тьюринга). Это и комбинаторный (или алгебраический) подход [48], в котором количество информации, заключенной в слове определяется логарифмом числа различных слов, которые можно получить из данного слова путем всевозможных перестановок его букв. Существуют и, время от времени, появляются все новые и новые подходы..
Тот или иной подход к определению информативности объекта или системы обусловлен двумя факторами. Во-первых, кругом тех задач, где это понятие предполагается использовать. Так в теории связи более продуктивным оказался вероятностный подход, в теории кодирования — комбинаторный и вероятностный подходы, в теории алгоритмов — алгоритмический подход, в физике — некоторые физически обусловленные и статистический подходы (в статистической термодинамике), в статистике — информация Фишера, в генетике и базах данных — алгебраический подход и т. д. В распознавании образов для выделения наиболее информативных признаков и решения последующей задачи распознавания используется алгебраический подход [48], в котором измеряется информативность слов признаков образа относительно слова меток классов. Этот подход предполагает, что признаки имеют качественный характер, т. е. задаются элементом конечного множества, что существенно сужает возможность применения такого подхода (квантование качественных характеристик неоднозначно и не решает алгебраически задачу измерения количества информации)..
Другой фактор, определяющий выбор способа измерения информативности — это та модель неопределенности (например, мера информативности), которая используется в описании объекта или системы. Причем указанные два фактора могут зависеть друг от друга, так как круг решаемых задач часто определяет и способ описания неопределенности..
В диссертационной работе будем придерживаться неопределенностно-обусловленного подхода в теории информации, появившегося в начале 80-х годов прошлого века в работах R.R. Yager [49], U. Hohle [50], М. Higashi, G.J. Klir [51], согласно которому понятие неопределенности тесно связано с понятием информации, в том смысле, что неопределенность входит в любую проблемную ситуацию как результат некоторой информационной недостаточности системы. Предположим, что мы можем измерить количество неопределенности, содержащейся в данной системе, и в этой системе выполняются какие-либо действия, связанные с получением значимой информации от системы. Тогда количество информации, полученной в результате выполнения этих действий, может быть измерено как количество уменьшенной неопределенности..
Выделяют различные типы неопределенности, такие как неполноту, фрагментарность, ненадежность, неясность, противоречивость и др. Разные типы неопределенности предполагают наличие своего понятийного аппарата для их описания — своей теории неопределенности, в которой основным объектом исследования является некоторая функция (мера) неопределенности (например, вероятностная мера в теории вероятностей или меры необходимости и возможности в теории возможностей). В диссертационной работе основное внимание уделим развитию математического аппарата, связанного с измерением количества такого типа неопределенности как неточность. Если X — некоторое конечное множество взаимно исключающих альтернатив, то функция неточности /и (А), характеризует ту или иную (в зависимости от конкретной теории неточности) качественную степень того, что истинная альтернатива содержится во множестве альтернатив, А с: X. Например, так.
А, В с!, характеризует степень доверия того, что множество, А содержит истинную альтернативу, если известно, что все возможные альтернативы составляют множество В..
Функция неточности характеризует качественную степень принадлежности истинной альтернативы рассматриваемому множеству с некоторой неточностью. Поэтому в каждой теории неточности должен быть обоснован выбор функционала (называемого индексом неточности), с помощью которого для каждой функции /л этой теории вычисляется количество неточности, связанной с ju. В теории возможностей, как показал Хартли в 1928 году, для измерения количества неточности, связанной с выбором множества альтерназываемая примитивная мера доверия, т. е. мера вида натив из некоторого подмножества В (такая неточность называется неспецифичностью), следует использовать функционал H (rj^) = log2|i?|, называемый мерой Хартли. Для измерения количества неопределенности, задаваемой вероятностной мерой р (такой тип неточности называют конфликтом), используют энтропию Шэннона S (p)..
После того как появились обобщения классических теорий возможностей и вероятностей, возникла задача исследования обобщений классических мер неопределенности. Эти обобщения должны были, с одной стороны наследовать основные свойства меры Хартли и энтропии Шэннона, а с другой стороны, отражать специфику конкретной теории неточности. Наиболее популярным обобщением классической теории возможностей является теория свидетельств (теория Демпстера-Шефера [52]), основным объектом исследования которой является так называемая функция (мера) доверия, представи-мая в виде /1 = т{В)т]^, где т (0) — 0, т (В)> 0 для всех Be 2х, и д^хт (В) = ]. В классе всех функций доверия Bel (X) для измерения количества неточности D. Dubois и Н. Prade [53] предложили использовать так называемую обобщенную меру Хартли.
GH (/i) =? m (5)log2|5|..
Ве2х{0].
Обзор мер неопределенности в других теориях неточности можно найти в [54]. В ряде работ [55, 56] рассматривалась аксиоматика мер неопределенности. В то же время оставался открытым вопрос об определении и описаниях индекса неточности в более широких классах мер, чем меры доверия. Наиболее широким классом функций неточности является класс так называемых нижних (верхних) вероятностей, т. е. таких монотонных нормированных мер /л, которые являются нижними (верхними) оценками вероятностных мер. Относительно мало исследовались алгебраические свойства, представления и описания самих индексов неточности в тех или иных классах монотонных мер. Кроме того, представляет интерес исследование индексов неточности на мерах информативности..
В общем случае мера информативности (1 может быть довольно громоздким описанием полигонального представления В, так как для своего задания она должна быть определена на всех 2'в' подмножествах представления В. Поэтому для ряда задач удобней использовать более простое представление, связанное с монотонной мерой (1. Таким представлением может быть монотонная мера из некоторого класса, аппроксимирующая в том или ином смысле монотонную меру (1. Простейшей такой мерой является вероятностная мера. Представляет интерес исследование свойств вероятностной меры, аппроксимирующей заданную монотонную меру, а также решение обратной задачи — описание класса тех монотонных мер, для которых заданная вероятностная мера будет аппроксимирующей мерой..
Целью настоящей диссертационной работы является разработка и анализ робастных к зашумлению методов и алгоритмов выделения низкоуровневых информативных признаков, методов формирования устойчивых к зашумлению высокоуровневых представлений и описаний изображений объектов, развитие математического аппарата, связанного с вычислением количества неопределенности мер информативности и с аппроксимацией таких мер..
В связи с поставленной целью необходимо было решить следующие задачи:.
1. Исследовать на робастность к зашумлению изображений новые и ранее разработанные локально-интерполяционные методы оценивания кривизны оцифрованной кривой, описать законы распределения вероятностей случайных оценок кривизны..
2. Проанализировать на робастность к зашумлению изображений новые и ранее разработанные методы локально-аппроксимативного подхода к оцениванию кривизны, решить задачу выбора оптимальных значений параметров методов, минимизирующих среднюю ошибку..
3. Исследовать на устойчивость к зашумлению векторные представления и описания кривых, разработать методы нахождения наиболее устойчивых к зашумлению векторных представлений, исследовать меры информативности представлений кривых, агрегирующих локальные оценки кривизны..
4. Аксиоматически ввести и исследовать индексы неточности в классах нижних и верхних вероятностей, предложить способы продолжения индексов неточности на множество всех монотонных мер, рассмотреть применения индекса неточности для исследования мер информативности..
5. Рассмотреть решение задачи аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку, описать множество тех мер доверия, для которых заданная вероятностная мера является ближайшей в среднеквадратичном..
Методы исследований основаны па использовании теории вероятностей, теории неаддитивных мер, теории неточных вероятностей, теории нечетких множеств, функционального анализа, комбинаторики и комбинаторной геометрии, дифференциальной геометрии, численных методов..
Материалы диссертационной работы распределены по главам в соответствии перечисленным задачам..
В главе 1 исследуется локально-интерполяционный подход к оцениванию кривизны плоской кривой. Показано, что ряд известных алгоритмов относятся к локально-интерполяционным методам оценивания. Оценивается систематическая погрешность оценки кривизны методом локальной интерполяции, исследуется распределение вероятностей случайной оценки кривизны, полученной методом локальной интерполяции при некоррелированном нормальном зашумлении кривой, оцениваются смещение и случайная ошибка оценки кривизны..
В этой же главе разрабатывается и исследуется метод усреднения локально-интерполяционных оценок, оцениваются систематическая и случайная ошибки оценки кривизны, полученные этим методом при некоррелированном нормальном зашумлении кривой. Находятся оптимальные значения параметров метода, при котором среднеквадратичная ошибка вычисления оценки кривизны будет наименьшей. Разрабатывается процедура уточнения размера окна при вычислении оценок кривизны кривой методом усреднения локально-интерполяционных оценок в случае известного уровня зашумления кривой и процедура нахождения оптимальных значений весовых коэффициентов функционала усреднения точечных оценок..
Кроме того, в главе 1 исследуется вычисление оценки кривизны с помощью свертки первичных локально-интерполяционных оценок со сглаживающим ядром. Оценивается систематическая ошибка такой оценки кривизны. Доказывается сходимость оценки кривизны к точному значению. Находятся распределения вероятностей системы зависимых случайных величин наклона при некоррелированном нормальном зашумлении кривой. Оцениваются смещения и случайные ошибки величин наклона и оценки кривизны, полученные методом сглаживания локально-интерполяционных оценок. Доказывается существование оптимальных значений параметров метода, при которых суммарная ошибка вычисления оценки кривизны методом аналитического сглаживания будет наименьшей..
В главе 2 исследуется локально-аппроксимативный подход к оцениванию кривизны плоской кривой. Находятся оценки для систематической и случайной ошибок оценки кривизны, полученной локально-аппроксимативным методом при некоррелированном нормальном зашумлении кривой, условия оптимального выбора степени аппроксимативного многочлена..
В этой же главе разрабатывается и исследуется метод геометрического сглаживания как модельный метод неявного локально-аппроксимативного подхода к оцениванию кривизны. Показывается, что метод геометрического сглаживания является бинарным аналогом детектора Харриса. В рамках этого метода рассматриваются линейные и нелинейные оценки кривизны как функции относительного изменения площади области, ограниченной кривой в пределах окрестности рассматриваемой точки. Ставится вариационная задача нахождения оптимальной такой функции. Находятся систематические ошибки оценок кривизны в линейном и нелинейном случаях, исследуются случайные ошибки оценок кривизны для различных вероятностных моделей зашумления кривой. Для всех этих моделей зашумления найдены точные значения или оценки случайных ошибок вычисления оценок кривизны. В случае одномерного целочисленного зашумления оцифрованной кривой находится вероятностное распределение случайной оценки кривизны, оцениваются смещения случайной ошибки линейной и нелинейной оценок кривизны. Решается задача нахождения оптимальных значений параметров метода, минимизирующих среднеквадратичную ошибку вычисления оценки кривизны..
Для всех разработанных и исследованных в главах 1 и 2 методов нахождения оценок кривизны как важнейших низкоуровневых признаков оцифрованных кривых осуществляется сравнительный анализ трех основных качественных характеристик оценок: систематической, случайной ошибок и смещения для различных моделей зашумления кривой. Предлагаются рекомендации по выбору метода и значений параметров для оптимального вычисления оценок кривизны..
Для агрегирования низкоуровневых признаков изображения (в частности, оценок кривизны) в главе 3 вводится и исследуется класс усредненных мер информативности по кривизне. Рассматриваются свойства таких мер, в ряде случаев находятся эффективные выражения для их вычисления. Определяется усредненная функция информативности кривой относительно данного локального признака изображения. Исследуется класс аддитивных усредненных мер информативности в случае вероятностного зашумления кривой. Показывается, что в этом случае усредненная аддитивная мера информативности является элементарной ортогональной стохастической мерой. Выводятся вычислительно эффективные формулы для среднего значения и дисперсии такой меры. Ставится и решается задача нахождения для дискретной кривой такого полигонального представления ограниченной мощности, для которого суммарная дисперсия меры информативности по всем подмножествам полигонального представления была бы минимальной, а сумма квадратов математических ожиданий всех представлений была бы максимальной..
В этой же главе рассматривается неаддитивная (монотонная) усредненная мера информативности. Для соответствующей стохастической меры при аддитивном некоррелированном зашумлении кривой выводятся формулы вычисления среднего значения, находятся необходимое и достаточное условие монотонности среднего значения стохастической меры. Исследуется стохастическая мера информативности по длине при аддитивном стационарном некоррелированном нормальном зашумлении дискретной кривой. Выводятся асимптотические формулы для среднего значения и дисперсии случайной длины стороны зашумленного многоугольника, а также формула для кова-риации длин соседних сторон зашумленного многоугольника. Находятся асимптотические выражения для величины смещения и случайной ошибки стохастической меры информативности по длине. Ставится и решается задача нахождения полигонального представления, наиболее устойчивого относительно меры информативности по длине..
В главе 3 рассматривается и нечеткостный подход к нахождению полигонального представления кривой, состоящий в выборе таких точек, информативные признаки которых удовлетворяют определенным нечетким отношениям близости и различия. В рамках этого подхода рассматривается алгоритм нахождения субоптимального полигонального представления, доказываются достаточные условия, при выполнении которых с помощью рассмотренного алгоритма мы получим минимальное нечеткое представление кривой..
В последних разделах третьей главы оцениваются величины уклонения центра масс полигонального представления, изменения векторных характеристик полигонального представления и дескриптора Фурье этих характеристик при добавлении в полигональное представление новых контрольных точек и (или) при изменении весов (значений информативных признаков) этих точек. Кроме этого оцениваются вероятности изменения центра масс векторного представления кривой, подвергнутой целочисленному стационарному некоррелированному зашумлению..
В главе 4 в рамках исследования степени неточности мер информативности, аксиоматически вводятся понятия индекса неточности в классе нижних (верхних) вероятностей и линейного индекса неточности, как линейного положительного функционала определенного вида. Рассматриваются различные описания линейных индексов неточности: в терминах описания дескриптивных мер, преобразования Мёбиуса этих мер и др. Подробно исследуется важный класс линейных симметричных по дополнению индексов неточности. В частности, описывается алгебраическая структура этого класса, находится его крайнее множество. Показывается, что для верхних (нижних) огибающих семейства вероятностных мер линейный симметричный по дополнению индекс неточности характеризует диаметр этого семейства в некоторой метрике. Доказывается, что некоторые широко известные меры неопределенности, в частности обобщенная мера Хартли в классе мер доверия, являются линейными индексами неточности. Предлагается и исследуется один способ продолжения индекса неточности на множество всех монотонных мер. При этом выделяются два типа неопределенностей, связанных с нижними (верхними) оценками вероятностей — неточность и противоречивость. Вводятся и исследуются индексы неточности и противоречивости монотонных мер..
Кроме того, в этой главе рассматривается индекс неточности меры информативности по длине, в частности, для правильных многоугольников. Показывается, как с помощью введенных понятий можно оценить априорную информативность полигонального представления кривой. Устанавливается связь между простейшим индексом неточности меры информативности по длине и изменением информативности при формировании полигонального представлении..
В главе 5 решается задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Исследуются различные представления ближайшей вероятностной меры. Доказывается, что вероятностная мера, минимизирующая среднеквадратичную невязку с мерой доверия, минимизирует и среднеквадратичную невязку с сопряженной мерой и со средней частью неточности. Показывается, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования. Исследуются алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру. Подробно исследуются свойства ближайшей в среднеквадратичном меры в классе так называемых симметричных мер доверия. Доказывается, что для симметричной меры доверия ближайшая вероятностная мера является равновероятной и будет мажорировать саму симметричную меру доверия. Рассматривается задача аппроксимации мер доверия /t-аддитивными мерами в среднеквадратичной метрике, связанной с преобразованием Мебиуса, а также равномерная аппроксимация мер доверия..
Кроме того, в этой главе рассматривается и решается обратная задача вероятностной аппроксимации: находится множество тех мер доверия (так называемых ближайших мер доверия), для которых заданная вероятностная мера является ближайшей в среднеквадратичном. Доказывается, что множество ближайших мер доверия является выпуклым и задается системой линейных уравнений и неравенств. Находится семейство экстремальных точек выпуклого класса ближайших мер доверия и оцениваются мощности крайнего множества этого класса. Алгебраическое описание класса ближайших мер доверия применяется к решению задачи оценивания выигрышей коалиций игроков при заданных полезностях отдельных игроков..
В приложении приведены копии актов о внедрении и использовании результатов работы..
В диссертационной работе получены следующие новые научные результаты:.
1. Исследован локально-интерполяционный подход к оцениванию кривизны плоской кривой. Оценены систематическая погрешность, смещение и случайная ошибка оценки кривизны при некоррелированном нормальном зашумлении кривой..
2. Разработан и исследован метод усреднения локально-интерполяционных оценок. Найдены оптимальные значения параметров метода..
3. Исследовано вычисление оценки кривизны с помощью свертки первичных локально-интерполяционных оценок со сглаживающим ядром. Оценены смещение и случайная ошибка оценки кривизны, полученная методом сглаживания локально-интерполяционных оценок. Рассмотрена процедура нахождения оптимальных значений параметров метода..
4. Исследован локально-аппроксимативный подход к оцениванию кривизны плоской кривой. Найдены значения систематической и случайной ошибок оценки кривизны, полученной локально-аппроксимативным методом при некоррелированном нормальном зашумлении кривой..
5. Разработан и исследован метод геометрического сглаживания как модельный метод неявного локально-аппроксимативиого подхода к оцениванию кривизны. Найдены систематические ошибки, смещения и случайные ошибки оценок кривизны, полученных этим методом для различных моделей зашумления кривой..
6. Введен и исследован класс усредненных мер информативности по кривизне. Определена усредненная функция информативности кривой относительно данного локального признака изображения. Исследован класс стохастических аддитивных усредненных мер информативности в случае вероятностного зашумления кривой. Решена задача нахождения полигонального представления кривой, ограниченной мощности, минимизирующего дисперсию стохастической меры информативности..
7. Исследована неаддитивная (монотонная) усредненная стохастическая мера информативности, в частности мера информативности по длине при аддитивном стационарном некоррелированном нормальном зашумлении дискретной кривой. Найдены асимптотические выражения для величины смещения и случайной ошибки стохастической меры информативности по длине. Поставлена и решена задача нахождения полигонального представления, наиболее устойчивого относительно меры информативности по длине..
8. Поставлена и исследована задача нахождения полигонального представления кривой, состоящего из всех таких точек, информативные признаки которых удовлетворяют определенным нечетким отношениям близости и различия..
9. Оценены величины изменение векторных характеристик представлений и описаний дискретной кривой при изменении информативности контрольных точек. Получены вероятностные оценки изменения центра масс векторного представления кривой, подвергнутой стационарному некоррелированному зашумлению..
10. В рамках исследования степени неточности мер информативности, аксиоматически введены и описаны линейные индексы неточности в классе нижних (верхних) вероятностей. Предложен и исследован один способ продолжения индекса неточности на множество всех монотонных мер. Рассмотрен индекс неточности меры информативности по длине..
11. Решена задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Получены различные представления ближайшей вероятностной меры. Показано, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования. Исследованы алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру..
12. Решена обратная задача вероятностной аппроксимации: найдено множество тех мер доверия, для которых заданная вероятностная мера является ближайшей в среднеквадратичном. Найдено семейство экстремальных точек выпуклого класса ближайших мер доверия и рассмотрены некоторые применения найденных описаний в теории игр..
Основные результаты работы докладывались на Всероссийской научно-технической конференции «Интеллектуальные САПР» CAD (п. Дивноморское, 1997, 1998, 2002), на Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999), на VI Международной конференции «Радиолокация, навигация, связь» (Воронеж, 2000), на Всероссийских симпозиумах по прикладной и промышленной математике (1999, 2000, 2001, 2002), на Международной научной конференции «Искусственный интеллект» (п. Кацивели, 2000), на Национальной конференции по искусственному интеллекту с международным участием КИИ (Переславль-Залесский, 2000), на Международной конференции по мягким вычислениям и измерениям SCM (Санкт Петербург, 2000), на Международной конференции «Цифровая обработка сигналов и ее применение» DSPA (Москва, 2000, 2002), на Международном научно-практическом семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2001, 2003), на Международном конгресса «Искусственный интеллект в XXI веке» (п. Дивноморское, 2001), на I Международном семинаре по мягким методам в вероятности и статистике SMPS (Варшава, 2002), на Международном конгрессе ассоциации нечетких систем IFSA (Турция, 2003), на 11-й Международной конференции по обработке информации и управлению в неопределенных экспертных системах IPMU (Париж, 2006), на Всероссийской научной конференции по нечетким системам и мягким вычислениям НСМВ (Тверь, 2006), на IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 2006), на восьмой Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные системы» (Донецк, 2007), на 5-м Международном симпозиуме по неточным вероятностям и их применениям ISIPTA (Прага, 2007), на 5-й конференции Европейского сообщества по нечеткой логике и технологиям EUS-FLAT (Острава, 2007), на конференции Северо-Американского общества по обработке нечеткой информации NAFIPS (Нью-Йорк, 2008)..
По теме диссертации опубликованы 42 печатные работы, из них 17 работ — в изданиях рекомендованных ВАК. Кроме того, результаты исследований отражены в 5-ти отчетах о НИР. Исследования по теме диссертации были поддержаны 4 грантами РФФИ: 98−01-ООО 13-а, 07−07−67-а, 07−708 036−3, 08−07−129-а..
Диссертация состоит из введения, пяти тематических глав, заключения, списка литературы и приложений. Общий объем основного текста — 349 стр., включая 19 рисунков и 10 таблиц.
Список литературы
изложен на 14 стр. и содержит 153 наименования..
5.12. Выводы.
1. Решена задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Получены различные представления ближайшей вероятностной меры..
2. Показано, что вероятностная мера р, минимизирующая среднеквадратичную невязку с мерой доверия g, минимизирует и среднеквадратичную невязку с сопряженной мерой g и со средней частью неточности р ..
Показано, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования..
3. Исследованы алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру..
4. Исследованы свойства ближайшей в среднеквадратичном меры в классе так называемых симметричных мер доверия. Показано, что для симметричной меры доверия ближайшая вероятностная мера является равновероятной и будет мажорировать саму симметричную меру доверия..
5. Рассмотрена задача аппроксимации мер доверия к-аддитивными ме * i рами в среднеквадратичной метрике, связанной с преобразованием Мебиуса, а также равномерная аппроксимация мер доверия..
6. Рассмотрена и решена обратная задача вероятностной аппроксимации: для заданной вероятностной меры р найдено множество тех мер доверия Belp (X), для которых мера р является ближайшей в среднеквадратичном. Показано, что множество «ближайших» мер доверия является выпуклым и задается системой линейных уравнений и неравенств в 2'*' -1 -м пространстве..
7. Найдено семейство экстремальных точек выпуклого класса Belp{X) и получены оценки мощности крайнего множества этого класса..
8. Алгебраическое описание класса Belp (X) применено к решению задачи оценивания выигрышей коалиций игроков при заданных полезпостях отдельных игроков..
ЗАКЛЮЧЕНИЕ.
Основной научный результат диссертационной работы заключается в найденных качественных характеристиках оценок кривизны плоских кривых, полученных различными методами и для разных моделей зашумления кривых, в указанных оптимальных значениях параметров методов оценок кривизны, в исследованных усредненных аддитивных и неаддитивных стохастических мерах информативности признаков изображения, в найденных оценках изменения векторных представлений и описаний изображений кривых, во введенном и исследованном понятии индекса неточности, как степени неточности монотонной меры, в вероятностной аппроксимации мер доверия, в применении разработанных методов и качественных оценок их работы в моделях обработки и анализа изображений..
При проведении исследований по теме настоящей работы были получены следующие теоретические и прикладные результаты..
1. Исследован локально-интерполяционный подход к оцениванию кривизны плоской кривой. Показано, что ряд известных алгоритмов относятся к локально-интерполяционным методам оценивания. Оценена систематическая погрешность оценки кривизны методом локальной интерполяции. Найдено распределение вероятностей случайной оценки кривизны, полученной методом локальной интерполяции при некоррелированном нормальном зашумлении кривой. Оценены смещение и случайная ошибка оценки кривизны..
Разработан и исследован метод усреднения локально-интерполяционных оценок. Оценены систематическая и случайная ошибки оценки кривизны этим методом при некоррелированном нормальном зашумлении кривой. Найдены оптимальные значения параметров метода, при котором среднеквадратичная ошибка вычисления оценки кривизны будет наименьшей. Разработана процедура уточнения размера окна при вычислении оценок кривизны кривой методом усреднения локально-интерполяционных оценок в случае известного уровня зашумления кривой. Разработана процедура нахождения оптимальных значений весовых коэффициентов функционала усреднения точечных оценок..
2. Исследовано вычисление оценки кривизны с помощью свертки первичных локально-интерполяционных оценок со сглаживающим ядром. Оценена систематическая ошибка такой оценки кривизны. Доказана сходимость оценки кривизны к точному значению. Найдены распределения вероятностей случайной величины наклона оцифрованной кривой в точке и системы зависимых случайных величин наклона при некоррелированном нормальном зашумлении кривой. Оценены смещения и случайные ошибки величин наклона и оценки кривизны, полученные методом сглаживания локально-интерполяционных оценок. Доказано существование оптимальных значений параметров метода, при которых суммарная ошибка вычисления оценки кривизны методом аналитического сглаживания будет наименьшей..
3. Исследован локально-аппроксимативный подход к оцениванию кривизны плоской кривой. Найдены оценки для систематической и случайной ошибок оценки кривизны, полученной локально-аппроксимативным методом при некоррелированном нормальном зашумлении кривой. Найдены условия оптимального выбора степени аппроксимативного многочлена..
Разработан и исследован метод геометрического сглаживания как модельный метод неявного локально-аппроксимативного подхода к оцениванию кривизны. Показано, что метод геометрического сглаживания является бинарным аналогом детектора Харриса. В рамках этого метода рассмотрены линейные и нелинейные оценки кривизны как функции относительного изменения площади области, ограниченной кривой в пределах окрестности рассматриваемой точки. Поставлена вариационная задача нахождения оптимальной такой функции. Найдены систематические ошибки оценок кривизны в линейном и нелинейном случаях. Исследованы случайные ошибки оценок кривизны для различных вероятностных моделей зашумления кривой. Для всех этих моделей зашумления найдены точные значения или оценки случайных ошибок вычисления оценок кривизны. В случае одномерного целочисленного зашумления оцифрованной кривой найдено вероятностное распределение случайной оценки кривизны, оценены смещения случайной ошибки линейной и нелинейной оценок кривизны. Решена задача нахождения оптимальных значений параметров метода, минимизирующих среднеквадратичную ошибку вычисления оценки кривизны..
Для всех разработанных и исследованных методов нахождения оценок кривизны как важнейших низкоуровневых признаков оцифрованных кривых осуществлен сравнительный анализ трех основных качественных характеристик оценок: систематической, случайной ошибок и смещения для различных моделей зашумления кривой. Предложены рекомендации по выбору метода и значений параметров для оптимального вычисления оценок кривизны..
4. Для агрегирования низкоуровневых признаков изображения (в частности, оценок кривизны) введен и исследован класс усредненных мер информативности по кривизне. Рассмотрены свойства таких мер, в ряде случаев найдены эффективные выражения для их вычисления. Определена усредненная функция информативности кривой относительно данного локального признака изображения. Исследован класс аддитивных усредненных мер информативности в случае вероятностного зашумления кривой. Показано, что в этом случае усредненная аддитивная мера информативности является элементарной ортогональной стохастической мерой. Получены вычислительно эффективные формулы для среднего значения и дисперсии такой меры. Поставлена и решена задача нахождения для дискретной кривой такого полигонального представления ограниченной мощности, для которого суммарная дисперсия меры информативности по всем подмножествам полигонального представления была бы минимальной, а сумма квадратов математических ожиданий всех представлений была бы максимальной..
Рассмотрена неаддитивная (монотонная) усредненная мера информативности. Для соответствующей стохастической меры при аддитивном некоррелированном зашумлении кривой получены формулы вычисления среднего значения, найдено необходимое и достаточное условие монотонности среднего значения стохастической меры. Исследована стохастическая мера информативности по длине при аддитивном стационарном некоррелированном нормальном зашумлении дискретной кривой. Получены асимптотические формулы для среднего значения и дисперсии случайной длины стороны зашумленного многоугольника, а также формула для ковариации длин соседних сторон зашумленного многоугольника. Найдены асимптотические выражения для величины смещения и случайной ошибки стохастической меры информативности по длине. Поставлена и решена задача нахождения полигонального представления, наиболее устойчивого относительно меры информативности по длине..
5. Поставлена задача нахождения полигонального представления кривой, состоящего из всех таких точек, информативные признаки которых удовлетворяют определенным нечетким отношениям близости и различия. Рассмотрен алгоритм нахождения субоптимального полигонального представления. Доказаны достаточные условия, при выполнении которых с помощью рассмотренного алгоритма мы получим минимальное нечеткое представление кривой..
6. Оценены величины уклонения центра масс полигонального представления, изменения векторных характеристик полигонального представления и дескриптора Фурье этих характеристик при добавлении в полигональное представление новых контрольных точек и (или) при изменении весов (значений информативных признаков) этих точек. Получены вероятностные оценки изменения центра масс векторного представления кривой, подвергнутой целочисленному стационарному некоррелированному зашумлению..
7. В рамках исследования степени неточности мер информативности, аксиоматически введены понятия индекса неточности в классе нижних (верхних) вероятностей и линейного индекса неточности, как линейного положительного функционала определенного вида. Даны различные описания линейных индексов неточности: в терминах описания дескриптивных мер, преобразования Мёбиуса этих мер и др. Исследован важный класс линейных.
348 j симметричных по дополнению индексов неточности. Описана алгебраическая структура этого класса, найдено его крайнее множество. Показано, что для верхних (нижних) огибающих семейства вероятностных мер линейный симметричный по дополнению индекс неточности характеризует диаметр этого семейства в некоторой метрике. Доказано, что некоторые широко известные меры неопределенности, в частности обобщенная мера Хартли в классе мер доверия, являются линейными индексами неточности. Предложен и исследован один способ продолжения индекса неточности на множество всех монотонных мер. Выделены два типа неопределенностей, связанных с нижними (верхними) оценками вероятностей — неточность и противоречивость. Введены и исследованы индексы неточности и противоречивости монотонных мер..
Рассмотрен индекс неточности меры информативности по длине, в частности, для правильных многоугольников. Показано, как с помощью введенных понятий можно оценить априорную информативность полигонального представления кривой. Установлена связь между простейшим индексом неточности меры информативности по длине и изменением информативности при формировании полигонального представлении..
8. Решена задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Получены различные представления ближайшей вероятностной меры. Доказано, что вероятностная мера, минимизирующая среднеквадратичную невязку с мерой доверия, минимизирует и среднеквадратичную невязку с сопряженной мерой и со средней частью неточности. Показано, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования. Исследованы алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру. Рассмотрены свойства ближайшей в среднеквадратичном меры в классе так называемых симметричных мер доверия. Показано, что для симметричной меры доверия ближайшая вероятностная мера является равновероятной и будет мажорировать саму симметричную меру доверия. Рассмотрена задача аппроксимации мер доверия-аддитивными мерами в среднеквадратичной метрике, связанной с преобразованием Мебиуса, а также равномерная аппроксимация мер доверия..
9. Рассмотрена и решена обратная задача вероятностной аппроксимации: найдено множество тех мер доверия (так называемых ближайших мер доверия), для которых заданная вероятностная мера является ближайшей в среднеквадратичном. Показано, что множество ближайших мер доверия является выпуклым и задается системой линейных уравнений и неравенств. Найдено семейство экстремальных точек выпуклого класса ближайших мер доверия и получены оценки мощности крайнего множества этого класса. Алгебраическое описание класса ближайших мер доверия применено к решению задачи оценивания выигрышей коалиций игроков при заданных полез-ностях отдельных игроков..
