Морфологический анализ цветных спектрозональных изображений 1. Введение Хорошо известно, что изображения одной и той же сцены, полученные при различных условиях освещения иили измененных оптических свойствах объектов могут отличаться радикально.Это обстоятельство порождает значительные трудности в прикладных задачах анализа и интерпретации изображений реальных сцен, в которых решение должно не зависеть от условий регистрации изображений. Речь идет, например, о задачах выделения неизвестного объекта на фоне известной местности, известного объекта на произвольном фоне при неконтролируемых условиях освещения, о задаче совмещения изображенний одной и той же сцены, полученных в различных спектральных диапазонах и т.д. Методы морфологического анализа, разработанные более десяти лет тому назад, 1-5, для решения перечисленных задач, были в основном ориентированы для применения к черно-белым изображениям 3. и оказались достаточно эффективными, 5-11. Между тем, по меньшей мере два обстоятельства указывают на целесообразность разработки морфологических методов анализа цветных изображений.
Во-первых, в задаче обнаружения и выделения объекта последний, как правило, прежде всего цветом отличается от фона. Во-вторых, описание формы изображения в терминах цвета позволит практически устранить эффект теней и влияние неопределенности в пространственном распределении интенсивности спектрально однородного освещения. 2. Цвет и яркость спектозонального изображения. Рассмотрим некоторые аспекты теории цвета так называемых многоспектральных спектрозональных, 13 изображений, аналогичной классической колориметрии 12. Будем считать заданными n детекторов излучения со спектральными чувствительностями j1,2 n, где 0 длина волны излучения.
Их выходные сигналы, отвечающие потоку излучения со спектральной плотностью e0, 0 далее называемой излучением, образуют вектор , w . Определим суммарную спектральную чувствительность детекторов , 0 и соответствующий суммарный сигнал назовем яркостью излучения e. Вектор назовем цветом излучения e. Если цвет e и само излучение назовем черным.
Поскольку равенства и эквивалентны, равенство имеет смысл и для черного цвета, причем в этом случае - произвольный вектор, яркость оторого равна единице. Излучение eназовем белым и его цвет обозначим если отвечающие ему выходные сигналы всех детекторов одинаковы . Векторы , и удобно считать элементами n-мерного линейного пространства . Векторы fe, соответствующие различным излучениям e, содержатся в конусе . Концы векторов содержатся в множестве , где П - гиперплоскость . Далее предполагается, что всякое излучение , где E - выпуклый конус излучений, содержащий вместе с любыми излучениями все их выпуклые комбинации смеси Поэтому векторы в образуют выпуклый конус , а векторы . Если то и их аддитивная смесь . Для нее . 1 Отсюда следует Лемма 1. Яркость fe и цвет e любой аддитивной смеси e излучений e1 em, m1,2 определяются яркостями и цветами слагаемых.
Подчеркнем, что равенство , означающее факт совпадения яркости и цвета излучений e и , как правило, содержит сравнительно небольшую информацию об их относительном спектральном составе.
Однако замена e на в любой аддитивной смеси излучений не изменит ни цвета, ни яркости последней.
Далее предполагается, что вектор w таков, что в E можно указать базовые излучения , для которых векторы , j1 n, линейно независимы.
Поскольку цвет таких излучений непременно отличен от черного, их яркости будем считать единичными j1 n. В таком случае излучение характеризуется лишь цветом , j1 n. Для всякого излучения e можно записать разложение , 1 в котором - координаты в базисе , или, в виде выходных сигналов детекторов излучения где выходной сигнал i-го детектора, отвечающий j-ому излучению j, i, j1 n. Матрица - стохастическая, поскольку ее матричные элементы как яркости базовых излучений неотрицательны и , j1 n. При этом яркость и вектор цвета j1 n, конец которого лежит в П определяются координатами j и цветами излучений , j1 n, и не зависят непосредственно от спектрального состава излучения e. В ряде случаев белое излучение естественно определять исходя из базовых излучений, а не из выходных сигналов детекторов, считая белым всякое излучение, которому в 1 отвечают равные координаты . Заметим, что слагаемые в 1, у которых j 0, fe , физически интерпретируются как соответствующие излучениям, помещенным в левую часть равенства 1 с коэффициентами -j 0 . В такой форме равенство 1 представляет баланс излучений.
Определим в скалярное произведение и векторы , биортогонально сопряженные с , i,j1 n. Лемма 2. В разложении 1 , j1 n Яркость , где , причем вектор ортогонален гиперплоскости П, так как , i,j1 n. Что касается скалярного проиведения , то его естественно определять так, чтобы выходные сигналы детекторов были координатами fe в некотором ортонормированном базисе . В этом базисе конус . Заметим, что для любых векторов и, тем более, для Rn Пусть Х - поле зрения, например, ограниченная область на плоскости R2, или на сетке , спектральная чувствительность j-го детектора излучения, расположенного в точке - излучение, попадающее в точку . Изображением назовем векторнозначную функцию 2 Точнее, пусть Х - поле зрения, Х, С измеримое пространство Х с мерой C - -алгебра подмножеств X. Цветное спектрозональное изображение определим равенством , 2 в котором почти для всех -измеримые функции на поле зрения X, такие, что . Цветные изображения образуют подкласс функций лебеговского класса функций . Класс цветных изображений обозначим LE,n. Впрочем, для упрощения терминологии далее любой элемент называется цветным изображением, а условие 2 условием физичности изображений f. Если f - цветное изображение 2, то , как нетрудно проверить черно-белое изображение 2, т.е Изображение , назовем черно-белым вариантом цветного изображения f, а цветное изображение , fx0, xX - цветом изображения f. В точках множества ВxX fx0 черного цвета x, xВ произвольные векторы из , удовлетворяющие условию яркость x1. Черно-белым вариантом цветного изображения f будем также называть цветное изображение b, имеющее в каждой точке Х ту же яркость, что и f, bxfx, xX, и белый цвет, xbxbx, xX. 3. Форма цветного изображения.
Понятие формы изображения призвано охарактеризовать форму изображенных объектов в терминах характерности изображений, инвариантных относительно определенного класса преобразований изображения, моделирующих меняющиеся условия его регистрации.
Например, довольно часто может меняться освещение сцены, в частности, при практически неизменном спектральном составе может радикально изменяться распределение интенсивности освещения сцены. Такие изменения освещения в формуле 2 выражаются преобразованием , в котором множитель kx модулирует яркость изображения в каждой точке при неизменном распределении цвета.
При этом в каждой точке у вектора fx может измениться длина, но направление останется неизменным.
Нередко изменение распределения интенсивности освещения сопровождается значительным изменением и его спектрального состава, но - пространственно однородным, одним и тем же в пределах всей изображаемой сцены.
Поскольку между спектром излучения e и цветом нет взаимно однозначного соответствия, модель сопутствующего преобразования изображения fx в терминах преобразования его цвета . Для этого определим отображение A , ставящее в соответствие каждому вектору цвета подмножество поля зрения в точках которого изображение , имеет постоянный цвет . Пусть при рассматриваемом изменении освещения и, соответственно, предлагаемая модель преобразования изображения состоит в том, что цвет преобразованного изображения должен быть также постоянным на каждом множестве A, хотя, вообще говоря другим, отличным от . Характекрным в данном случае является тот факт, что равенство влечет . Если - самое детальное изображение сцены, то, вообще говоря, на различных множествах A и A цвет изображения может оказаться одинаковым A A A f, vf , Как правило, следует учитывать непостоянство оптических характеристик сцены и т.д. Во всех случаях форма изображения должна быть инвариантна относительно преобразования из выделенного класса и, более того, должна определять изображение с точностью до произвольного преобразования из этого класса.
Для определения понятия формы цветного изображения f на удобно ввести частичный порядок , т.е. бинарное отношение, удовлетворяющее условиям 1 , 2 то , отношение должно быть согласованным с определением цветного изображения с условием физичности, а именно если . Отношение интерпретируется аналогично тому, как это принято в черно-белой морфологии2, а именно, означает, что изображения fиg сравнимы по форме, причем форма g не сложнее, чем форма f. Если и , то f и g назовем совпадающими по форме изоморфными, f g. Например, если f и g - изображения одной и той же сцены, то g, грубо говоря, характеризует форму изображенных объектов не точнее подробнее, детальнее, чем f, если . В рассматриваемом выше примере преобразования изображений если между множествами A, и A, существует взаимно-однозначное соответствие, т.е если существует функция , такая, что A A причем , если . В этом случае равенства и эквивалентны, и изоморфны и одинаково детально характеризуют сцену, хотя и в разных цветах.
Если же не взаимно однозначно, то AU A и . В этом случае равенство влечет но не эквивалентно , передает, вообще говоря, не все детали сцены, представленные в . Пусть, скажем, g - черно-белый вариант f, т.е. gxfx и gxgx, xX. Если преобразование - следствие изменившихся условий регистрации изображения, то, естественно Аналогично, если fgизображения одной и той же сцены, но в gвследствие неисправности выходные сигналы некоторых датчиков равны нулю, то . Пусть F - некоторая полугруппа преобразований , тогда для любого преобразования FF , поскольку, если некоторые детали формы объекта не отражены в изображении f, то они, тем более, не будут отражены в g. Формой изображения f назовем множество изображений , форма которых не сложнее, чем форма f, и их пределов в черта символизирует замыкание в . Формой изображения fв широком смысле назовем минимальное линейное подпространство , содержащее . Если считать, что для любого изображения , то это будет означать, что отношение непрерывно относительно сходимости в в том смысле, что . Рассмотрим теперь более подробно понятие формы для некоторых характерных классов изображений и их преобразований. 4. Форма кусочно-постоянного мозаичного цветного изображения.
Во многих практически важных задачах форма объекта на изображении может быть охарактеризована специальной структурой излучения, достигающего поле зрения X в виде здесь - индикаторные функции непересекающихся подмножеств Аi, i1 N, положительной меры поля зрения Х, на каждом из которых функции j1 n, i1 N, непрерывны.
Поскольку согласно лемме 2 , 3 то цветное изображение fe, такого объекта характеризует его форму непрерывным распределением яркости и цвета на каждом подмножестве Ai, i1 N. Для изображения , где , также характерно напрерывное распределение яркости и цвета на каждом Ai, если непрерывные функции.
Если, в частности, цвет и яркость постоянны на Ai, i1 N, то это верно и для всякого изображения , если не зависит явно от . Для такого изображения примем следующее представление , 4 его черно-белый вариант 4 на каждом Ai имеет постоянную яркость , и цвет изображения 4 4 не меняется на Ai и равен , i1 N. Поскольку для реальных изображений должно быть выполнено условие физичности 2 то форму изображения 4, имеющего на различных множествах Аi имеет несовпадающие яркости и различные цвета , определим как выпуклый замкнутый в конус . 4 va, очевидно, содержится в nN мерном линейном подпространстве , 4 которое назовем формой a в широком смысле.
Форму в широком смысле любого изображения a, у которого не обязательно различны яркости и цвета на различных подмножествах Ai ,i1 N, определим как линейное подпространство , натянутое не вектор-функции Fa,FF, где F - класс преобразований , определенных как преобразования векторов axFax во всех точках xX здесь F - любое преобразование . Тот факт, что F означает как преобразование , так и преобразование , не должен вызывать недоразумения.
Изображения из конуса4 имеют форму, которая не сложнее, чем форма a 4, поскольку некоторые из них могут иметь одно и то же значение яркости илии цвета на различных множествах Аi, i1 N. Также множества оказываются, по существу, объединенными в одно, что и приводит к упрощению формы изображения, поскольку оно отражает меньше деталей формы изображенного объекта, чем изображение 4. Это замечание касается и La, если речь идет о форме в широком смысле.
Лемма 3. Пусть Аi - измеримое разбиение X . Изображение 3 имеет на каждом подмножестве Ai постоянную яркость и цвет , если и только если выполняется равенство 4 постоянный цвет , если и только если в 3 постоянную яркость fi , i1 N, если и только если в 3 не зависит от , i1 N. Доказательство . На множестве Ai яркость и цвет изображения 3 равны соответственно i1 N. Если выполнено равенство 4, то и от не зависят.
Наоборот, если и , то и , т.е. выполняется 4. Если , то цвет не зависит от . Наоборот, пусть не зависит от . В силу линейной независимости координаты ix не зависят от , т.е. и, следовательно, где - яркость на A i и . Последнее утверждение очевидно Цвет изображения определяется как электродинамическими свойствами поверхности изображенного объекта, так и спектральным составом облучающего электромагнитного излучения в том диапазоне, который используется для регистрации изображения.
Речь идет о спектральном составе излучения, покидающего поверхность объекта и содержащего как рассеянное так и собственное излучения объекта.
Поскольку спектральный состав падающего излучения, как правило, пространственно однороден, можно считать, что цвет изображения несет информацию о свойствах поверхности объекта, о ее форме, а яркость в значительной степени зависит и от условий освещения.
Поэтому на практике в задачах морфологического анализа цветных изображений сцен важное значение имеет понятие формы изображения, имеющего постоянный цвет и произвольное распределение яркости в пределах заданных подмножеств Ai , i1 N, поля зрения X. Итак, пусть в согласии с леммой 3 , 5 где индикаторная функция Ai функция gi задает распределение яркости 6 в пределах Ai при постоянном цвете , i1 N, 7 причем для изображения 5 цвета i, i1 N, считаются попарно различными, а функции gi, i1 N удовлетворяющими условиям i1 N. Нетрудно заметить, что в выражениях 5,6 и 7 без потери общности можно принять условие нормировки , позволяющее упростить выражения 6 и 7 для распределений яркости и цвета. С учетом нормировки распределение яркости на Ai задается функцией а цвет на Ai равен 7 Форму изображения 5 определим как класс всех изображений 8 , каждое из которых, как и изображение 5, имеет постоянный цвет в пределах каждого Ai, i1 N. Форма таких изображений не сложнее, чем форма f 5, поскольку в изображении на некоторых различных подмножествах Ai, i1 N, могут совпадать значения цвета, которые непременрно различны в изображении f 5. Совпадение цвета на различных подмножествах Ai, i1 N ведет к упрощению формы изображения по сравнению с формой f 5. Все изображения , имеющие различный цвет на различных Ai, i1 N, считаются изоморфными fи между собой, форма остальных не сложнее, чем форма f. Если , то, очевидно Если в 8 яркость , то цвет на Ai считается произвольным постоянным, если же в точках некоторого подмножества , то цвет на Ai считается равным цвету на , i1 N. Цвет изображения 8 может не совпадать с цветом 5. Если же по условию задачи все изображения , форма которых не сложнее, чем форма , должны иметь на Ai, i1 N, тот же цвет, что и у то следует потребовать, чтобы , в то время, как яркости остаются произвольными если , то цвет на Ai определяется равным цвету f на Ai, i1 N. Нетрудно определить форму любого, не обязательно мозаичного, изображения fв том случае, когда допустимы произвольные изменения яркости при неизменном цвете x в каждой точке . Множество, содержащее все такие изображения 9 назовем формой в широком смысле изображения , у которого fx0, -почти для всех , ср. 2. является линейным подпространством , содержащем любую форму , 10 в которой включение определяет допустимые значения яркости. В частности, если означает, что яркость неотрицательна , то - выпуклый замкнутый конус в , принадлежащий . Более удобное описание формы изображения может быть получено на основе методов аппроксимации цветных изображений, в которых форма определяется как оператор наилучшего приближения.
В следующем параграфе дано представление формы изображения в виде оператора наилучшего приближения. 5. Задачи аппроксимации цветных изображений.
Форма как оператор наилучшего приближения. Рассмотрим вначале задачи приближения кусочно-постоянными мозаичными изображениями.
Решение этих задач позволит построить форму изображения в том случае, когда считается, что для любого преобразования , действующего на изображение как на вектор в каждой точке и оставляющего элементом , т.е. изображением.
Форма в широком смысле определяется как оператор наилучшего приближения изображения изображениями где - класс преобразований , такой, что . Иначе можно считать, что 10 а - оператор наилучшего приближения элементами множества , форма которых не сложнее, чем форма . Характеристическим для является тот факт, что, если fxfy, то для любого . 5.1. Приближение цветного изображения изображениями, цвет и яркость которых постоянны на подмножествах разбиения поля зрения X. Задано разбиение , требуется определить яркость и цвет наилучшего приближения на каждом . Рассмотрим задачу наилучшего приближения в цветного изображения f 2 изображениями 4, в которых считается заданным разбиение поля зрения X и требуется определить из условия 11 Теорема 1. Пусть . Тогда решение задачи 11 имеет вид , i1 N, j1 n, 12 и искомое изображение 4 задается равенством . 13 Оператор является ортогональным проектором на линейное подпространство 4 изображений 4, яркости и цвета которых не изменяются в пределах каждого Ai , i1 N. Черно-белый вариант 4 цветного изображения 4 является наилучшей в аппроксимацией черно-белого варианта цветного изображения f, если цветное изображение 4 является наилучшей в аппроксимацией цветного изображения f. Оператор , является ортогональным проектором на линейное подпространство черно-белых изображений, яркость которых постоянна в пределах каждого . В точках множества цвет 4 наилучшей аппроксимации 4 цветного изображения f 2 является цветом аддитивной смеси составляющих f излучений, которые попадают на . Доказательство.
Равенства 12 - условия минимума положительно определенной квадратичной формы 11, П - ортогональный проектор, поскольку в задаче 11 наилучшая аппроксимация - ортогональная проекция f на . Второе утверждение следует из равенства , вытекающего из 13. Последнее утверждение следует из равенств ,i1 N вытекающих из 12 и равенства 1, в котором индекс k следует заменить на xX. Замечание 1. Для любого измеримого разбиения ортогональные проекторы и определяют соответственно форму в широком смысле цветного изображения 4, цвет и яркость которого, постоянные в пределах каждого , различны для различных , ибо , и форму в широком смысле черно-белого изображения, яркость которого постоянна на каждом и различна для разных ,2. Если учесть, условие физичности 2, то формой цветного изображения следует считать проектор на выпуклый замкнутый конус 4 Аналогично формой черно-белого изображения следует считать проектор на выпуклый замкнутый конус изображений 4, таких, что 2. Дело в том, что оператор определяет форму изображения 4, а именно - множество собственных функций оператора . Поскольку - наилучшее приближение изображения изображениями из , для любого изображения из и только для таких Поэтому проектор можно отождествить с формой изображения 4. Аналогично для черно-белого изображения a 2. И проектор можно отождествить с формой изображения 4, как это сделано в работах 2,3. Примечания.
Формы в широком смысле не определяются связью задач наилучшего приближения элементами и , которая известна как транзитивность проецирования.
Именно, если оператор наилучшего в приближения злементами выпуклого замкнутого в и в конуса , то . Иначе говоря, для определения наилучшего в приближения элементами можно вначале найти ортогональную проекцию изображения на , а затем спроецировать в на . При этом конечномерный проектор для каждого конкретного конуса может быть реализован методом динамического программирования, а для многих задач морфологического анализа изображений достаточным оказывается использование лишь проектора П . Форма в широком смысле 4 изображения 4 полностью определяется измеримым разложением , последнее, в свою очередь определяется изображением , если векторы попарно различны.
Если при этом , то форма в широком смысле может быть определена и как оператор П ортогонального проецирования на , определенный равенством 13. Посмотрим, каким образом воспользоваться этими фактами при построении формы в широком смысле как оператора ортогонального проецирования на линейное подпространство 10 для произвольного изображения . Пусть - множество значений и - измеримое разбиение X , порожденное , в котором - подмножество X , в пределах которого изображение имеет постоянные яркость и цвет, определяемые вектором , если . Однако для найденного разбиения условие , вообще говоря, невыполнимо и, следовательно, теорема 1 не позволяет построить ортогональный проектор П на . Покажем, что П можно получить как предел последовательности конечномерных ортогональных проекторов.
Заметим вначале, что любое изображение можно представить в виде предела в должным образом организованной последовательности мозаичных изображений где - индикатор множества , принадлежащего измеримому разбиению В можно, например, использовать так называемую исчерпывающую последовательность разбиений , удовлетворяющую следующим условиям C - измеримо N1-oe разбиение является продолжением N-го, т.е. для любого , найдется iij такое, что - минимальная -алгебра, содержащая все , совпадает с C. Лемма . Пусть - исчерпывающая последователь-ность разбиений X и - то множество из , которое содержит . Тогда для любой C-измеримой функции и -почти для всех . Воспользуемся этим результатом для построения формы в широком смысле П произвольного изображения . Пусть - минимальная -алгебра, относительно которой измеримо , т.е. пусть , где - прообраз борелевского множества , B - -алгебра борелевских множеств . Заменим в условиях, определяющих исчерпывающую последовательность разбиений, C на и выберем эту, зависящую от , исчерпывающую последовательность - измеримых разбиений в лемме . Теорема . Пусть исчерпывающая последовательность разбиений X, причем - минимальная -алгебра, содержащая все и ПN - ортогональный проектор , определенный равенством , Тогда 1 для любого -измеримого изображения и почти для всех 2 для любого изображения при в , где П - ортогональный проектор на . Доказательство.
Первое утверждение непосредственно следует из леммы и определения . Для доказательства второго утверждения заметим, что, так как AN1 - продолжение разбиения AN, N1,2 то последовательность проекторов ПN, N1,2 монотонно неубывает и потому сходится поточечно к некоторому ортогональному проектору П. Так как - множество всех -измеримых изображений и их пределов в , а в силу леммы для любого -измеримого изображения , то для любого изображения и для любого , ибо -измеримо, N1,2 Вопрос о том, каким образом может быть построена исчерпывающая последовательность разбиений, обсуждается в следующем пункте.
Заданы векторы f1 fq, требуется определить разбиение , на множествах которого наилучшее приближение принимает соответственно значенния f1 fq. Рассмотрим задачу приближения цветного изображения f, в которой задано не разбиение поля зрения X, а векторы в , и требуется построить измеримое разбиение поля зрения, такое, что цветное изображение - наилучшая в аппроксимация f. Так как , 14 то в Ai следует отнести лишь те точки , для которых , 1,2 q, или, что то же самое, 1,2 q. Те точки, которые согласно этому принципу могут быть отнесены к нескольким множествам, должны быть отнесены к одному из них по произволу.
Учитывая это, условимся считать, что запись , 14 означает, что множества 14 не пересекаются и . Чтобы сформулировать этот результат в терминах морфологического анализа, рассмотрим разбиение , в котором 15 и звездочка указывает на договоренность, принятую в 14. Определим оператор F, действующий из в по формуле i1 q. Очевидно, F всегда можно согласовать с 14 так, чтобы включения и , i1 q, можно было считать эквивалентными.
F Теорема 2. Пусть - заданные векторы Rn. Решение задачи наилучшего в приближения изображения f изображениями имеет вид , где - индикаторная функция множества . Множество определено равенством 15. Нелинейный оператор , как всякий оператор наилучшего приближения удовлетворяет условию F2F, т.е. является пректором.
Замечание 2. Если данные задачи доступны лишь в черно-белом варианте, то есть заданы числа , i1 q, которые можно считать упорядоченными согласно условию , то, как показано в 3, искомое разбиение X состоит из множеств где , и имеет мало общего с разбиением 14. Замечание 3. Выберем векторы fi, i1 q единичной длины , i1 q. Тогда . 16 Множества 16 являются конусами в Rn , ограниченными гиперплоскостями, проходящими через начало координат.
Отсюда следует, что соответствующее приближение изображения f инвариантно относительно произвольного преобразования последнего, не изменяющего его цвет например , в частности, относительно образования теней на f. Замечание 4. Для любого заданного набора попарно различных векторов оператор F, приведенный в теореме 2, определяет форму изображения, принимающего значения соответственно на измеримых множествах любого разбиения X. Всякое такое изображение является неподвижной в точкой F , если , все они изоморфны между собой.
Если некоторые множества из - пустые, или нулевой меры, соответствующие изображения имеют более простую форму.
Иначе говоря, в данном случае формой изображения является множество всех изображений, принимающих заданные значения на множествах положительной меры любого разбиения X, и их пределов в . Теоремы 1 и 2 позволяют записать необходимые и достаточные условия наилучшего приближения изображения f изображениями , в котором требуется определить как векторы , так и множества так, чтобы . Следствие 1. Пусть Di ,i1 N подмножества Rn 15, П - ортогональный проектор 13 где . Тогда необходимые и достаточные условия суть следующие , где Следующая рекуррентная процедура, полезная для уточнения приближений, получаемых в теоремах 1,2, в некоторых случаях позволяет решать названную задачу.
Пусть - исходные векторы в задаче 14 соответствующее оптимальное разбиение 14, F1- оператор наилучшего приближения и - невязка.
Воспользовавшись теоремой 1, определим для найденного разбиения оптимальные векторы . Согласно выражению 13 , и соответствующий оператор наилучшего приближения П1 13 обеспечит не менее точное приближение f, чем F1 . Выберем теперь в теореме 2 , определим соответствующее оптимальное разбиение и построим оператор наилучшего приближения F2. Тогда . На следующем шаге по разбиению строим и оператор П3 и т.д. В заключение этого пункта вернемся к вопросу о построении исчерпывающего -измеримого разбиения X, отвечающего заданной функции . Выберем произвольно попарно различные векторы из fX и построим по формуле 15 разбиение Rn . Для каждого q1,2 образуем разбиение ENq, множества , j1 Nq, которого образованы всеми попарно различными пересечениями множеств из . Последовательность соответствующих разбиений X , i1 Nq, q1,2 -измеримы и является продолжением 5.2. Приближение изображениями, цвет которых постоянен на подмножествах разбиения поля зрения X. Задано разбиение , требуется определить цвет и распределение яркостей наилучшего приближения на каждом Ai,i1 N. Для практики, как уже было отмечено, большой интерес представляет класс изображений 5, цвет которых не изменяется в пределах некоторых подмножеств поля зрения, и задачи аппроксимации произвольных изображений изображениями такого класса.
Запишем изображение 5 в виде 17 где . Пусть A1 AN - заданное разбиение X индикаторная функция Ai, i1 N. Рассмотрим задачу наилучшего в приближения изображения изображениями 17, не требуя, чтобы 18 Речь идет о задаче аппроксимации произвольного изображения изображениями, у которых яркость может быть произвольной функцией из , в то время, как цвет должен сохранять постоянное значение на каждом из заданных подмножеств A1 AN поля зрения X, см. Лемму 3. Так как то минимум S 19 по достигается при , 20 и равен 21 Задача 18 тем самым сведена к задаче . 22 В связи с последней рассмотрим самосопряженный неотрицательно определенный оператор . 23 Максимум неотрицательной квадратичной формы на сфере в Rn, как известно, см например, 11 достигается на собственном векторе yi оператора Фi, отвечающем максимальному собственному значению 0 и равен , т.е Следовательно, максимум в 22 равен и достигается, например, при Теорема 3. Пусть A1 AN -заданное измеримое разбиение X, причем mAs0, 18 As , s. Ai 0, i1 N. Решением задачи 18 наилучшего приближения изображения изображениями g 17 является изображение 24 Операторы ,i1 N, и - нелинейные зависящие от f проекторы Пi проецирует в Rn векторы на линейное подпространство , натянутое на собственный вектор оператора Фi 23, отвечающий наибольшему собственному значению i, 25 П проецирует в изображение на минимальное линейное подпространство , содержащее все изображения Невязка наилучшего приближения 19. Доказательство. Равентство 24 и выражение для Пi следует из 17,20 и решения задачи на собственные значения для оператора Фi 23. Поскольку Фi самосопряженный неотрицательно определенный оператор, то задача на собственные значения 23 разрешима, все собственные значения Фi неотрицательны и среди них i - наибольшее.
Для доказательства свойств операторов Пi, i1 N, и П введем обозначения, указывающие на зависимость от f 26 Эти равенства, показывающие, что результат двукратного действия операторов Пi, i1 N, и П 26 не отличается от результатата однократного их действия, позволят считать операторы 26 проекторами.
Пусть fi - cсобственный вектор Фi , отвечающий максимальному собственному значению i. Чтобы определить следует решить задачу на собственные значения для оператора . Поскольку rank 1, имеет единственное положительное собственное значение, которое, как нетрудно проверить, равно i, и ему соответствует единственный собственный вектор fi. Поэтому . Отсюда, в свою очередь, следует равенство 26 для Лемма 4. Для любого изображения решение 24 задачи 18 наилучшего приближения единственно и является элементом . Доказательство.
Достаточно доказать, что единственный с точностью до положительного множителя собственный вектор fi оператора 23, отвечающий максимальному собственному значению i, можно выбрать так, чтобы , поскольку в таком случае будут выполнены импликации , составляющие содержание леммы.
Действительно, если то согласно 23 , поскольку включение означает, что отсюда и из 25 получим, что ,i1 N, а поэтому и в 24 . Убедимся в неотрицательности . В ортонормированном базисе e1 en, в котором , выходной сигнал i-го детектора в точке см. замечание 1 задача на собственные значения 23 имеет вид , p1 n, где Так как матрица симметрическая и неотрицательно определенная она имеет n неотрицательных собственных значений , которым соответствуют n ортонормированных собственных векторов , а поскольку матричные элементы , то согласно теореме Фробенуса-Перрона максимальное собственное значение - алгебраически простое некратное, а соответствующий собственный вектор можно выбирать неотрицательным . Следовательно, вектор fi определен с точностью до положительного множителя Замечание 4. Если , т.е. если аппроксимируемое изображение на множествах того же разбиения имеет постоянный цвет, то в теореме 3 Наоборот, если , то , т.е. определяется выражением 17, в котором . Итак, пусть в изображении g 17 все векторы f1 fN попарно не коллинеарны, тюею цвета всех подмножеств A1 AN попарно различны.
Тогда форма в широком смысле изображения 17 есть множество решений уравнения 27 где , fi - собственный вектор оператора Фi , отвечающий максимальному собственному значению i, i1 N . В данном случае , если и только если выполнено равенство 27. Оператор П 24, дающий решение задачи наилучшего приближения , естественно отождествить с формой в широком смысле изображения 17. Заданы векторы цвета 1 q, требуется определить разбиение A1 Aq, на множествах которого наилучшее приближение имеет соответственно цвета 1 q и оптимальные распределения яркостей 1 q Речь идет о следующей задаче наилучшего в приближения изображения . 28 Рассмотрим вначале задачу 28 не требуя, чтобы . Так как для любого измеримого , 29 и достигается на , 30 то, как нетрудно убедиться 31 где звездочка означает то же самое, что и в равенстве 14 точки xX, в которых выполняется равенство могут быть произвольно отнесены к одному из множеств Ai или Aj. Пусть - разбиение , в котором 32 а F Rn Rn оператор, определенный условием 33 Тогда решение задачи 28 можно представить в виде , 34 где - индикаторная функция множества Ai 31, i1 q и F -оператор, действующий в по формуле 34 см. сноску 4 на стр. 13. Нетрудно убедиться, что задача на минимум 29 с условием физичности 35 имеет решение 36 Соответственно решение задачи 28 с условием физичности имеет вид , 37 где - индикаторная функция множества , 38 В ряде случаев для построения 34 полезно определить оператор F Rn Rn, действующий согласно формуле 39 где , так что ,i1 q. 40 Подытожим сказанное.
Теорема 4. Решение задачи 28 наилучшего в приближения изображения изображениями на искомых множествах A1 Aq разбиения X заданные цветами 1 q соответственно, дается равенством 34, искомое разбиение A1 Aq определено в 31. Требование физичности наилучшего приближения приводит к решению 37 и определяет искомое разбиение формулами 38. Решение 34 инвариантно относительно любого, а 37 - относительно любого, сохраняющего физичность, преобразования, неизменяющего его цвет. Формой в широком смысле изображения, имеющего заданный набор цветов 1 q на некоторых множествах положительной меры A1 Aq разбиение поля зрения можно назвать оператор 34, формой такого изображения является оператор F 37. Всякое такое изображение g, удовлетворяющее условиям физичности неотрицательности яркостей, удовлетворяет уравнению Fgg, те из них, у которых Ai 0, i1 q, изоморфны, остальные имеют более простую форму.
В заключение этого раздела вернемся к понятию формы изображения, заданного с точностью до произвольного, удовлетворяющего условиям физичности, преобразования яркости.
Речь идет о форме изображения , заданного распределением цвета , при произвольном физичном распределении яркости, например Для определения формы рассмотрим задачу наилучшего в приближения изображения такими изображениями , 41 Теорема 5. Решение задачи 41 дается равенством , 42 в котором , где . Невязка приближения , 43 Определение.
Формой изображения, заданного распределением цвета , назовем выпуклый, замкнутый конус изображений или - проектор на . Всякое изображение g, распределение цвета которого есть и только такое изображение содержится в и является неподвижной точкой оператора g g. Поскольку на самом деле детали сцены, передаваемые распределением цвета , не представлены на изображении f f в той области поля зрения, в которой яркость fx0, xX, будем считать, что - форма любого изображения fx fxx, fx 0, xXmod, все такие изображения изоморфны, а форма всякого изображения g, удовлетворяющего уравнению , не сложнее, чем форма f. Замечание 5. Пусть 1 N - исходный набор цветов A1 AN - соответствующее оптимальное разбиение X, найденное в теореие 4 и , 34 - наилучшее приближение f. Тогда в равенстве 24 , 24 если A1 AN - исходное разбиение X в теореме 3. Наоборот, если A1 AN - заданное в теореме 3 разбиение X и f1 fN - собственные векторы операторов Ф1 ФN 23 соответственно, отвечающие максимальным собственным значениям, то f1 fN и будет выполнено равенство 24, если в 34 определить i как цвет fi в 24, i1 N. Проверка этого замечания не представляет затруднений.
В. Случай, когда допускаются небольшие изменения цвета в пределах каждого Ai, i1 N. Разумеется, условие постоянства цвета на множествах Ai, i1 N, на практике может выполняться лишь с определенной точностью.
Последнюю можно повысить как путем перехода к более мелкому разбиению , так и допустив некоторые изменения цвета в пределах каждого Ai, i1 N, например, выбрав вместо 17 класс изображений 17 в котором в 3. Поскольку в задаче наилучшего приближения f изображениями этого класса предстоит найти , векторы при любом i1 N, можно считать ортогональными, определив , из условия минимума невязки по . После этого для каждого i1 N векторы должны быть определены из условия при дополнительном условии ортогональности . Решение этой задачи дается в следующей лемме Лемма 5. Пусть ортогональные собственные векторы оператора Фi 23, упорядоченные по убыванию собственных значений . Тогда решение задачи дается равенствами . Доказательство.
Заметим, что, поскольку Фi - самосопряженный неотрицательно определенный оператор, его собственные значения неотрицательны, а его собственные векторы всегда можно выбрать так, чтобы они образовали ортогональный базис в Rn. Пусть Pi - ортогонально проецирует в Rn на линейную оболочку собственных векторов и Pi Фi Pi - сужение оператора Pi Фi Pi на . Тогда левая часть равна следу оператора Pi Фi Pi , где - j-ое собственное значение оператора см например, 10. Пусть . Тогда согласно теореме Пуанкаре, 10 откуда следует утверждаемое в лемме.
Воспользовавшись выражениями и леммой 5, найдем, что в рассматриваемом случае имеет место утверждение, аналогичное теореме 3. Теорема 3. Наилучшее приближение любого изображения f изображениями 17 имеет вид , Где ортогональный проектор на линейную оболочку , собственных векторов задачи . Невязка наилучшего приближения равна . Рассмотрим теперь задачу наилучшего приближения изображения f изображениями 17, в которых заданы и фиксированы векторы , и надлежит определить измеримое разбиение и функции , как решение задачи 30 При любом разбиении минимум в 30 по достигается при , определяемых равенством 20. В свою очередь, очевидно, что 31 где точки , в которых выполняется равенство могут быть произвольно включены в одно из множеств либо в , либо в . Это соглашение отмечено звездочкой в 31. Таким образом доказана Теорема 6. Пусть заданные векторы Rn. Решением задачи 30 является изображение , где ортогональный проектор определен равенством 25, а - индикаторная функция множества 31, i1 N. Невязка наилучшего приближения равна . Замечание 5. Так как при , то условия 31, определяющие разбиение , можно записать в виде , 32 показывающем, что множество в 32 инвариантно относительно любого преобразования изображения , не изменяющего его цвет. Теоремы 3 и 6 позволяют сформулировать необходимые и достаточные условия наилучшего приближения изображения f изображениями 17, при котором должны быть найдены и i0 , i1 N, такие, что . Теорема 7. Для заданного изображения f определим множества равенствами 32, оператор П - равенством 24 равенствами 25. Тогда , определено равенством 32, в котором - собственный вектор оператора Фi 23, отвечающий наибольшему собственному значению, причем в 23 , наконец, будет дано равенством 20, в котором , где - собственный вектор оператора , отвечающий наибольшему собственному значению наконец Замечание 6. Следующая итерационная процедура полезна при отыскании Для изображения f зададим и по теореме 5 найдем и , затем по теореме 3, используя найдем и . После этого вновь воспользуемся теоремой 3 и по найдем и и т.д. Построенная таким образом последовательность изображений очевидно обладает тем свойством, что числовая последовательность , k1,2 монотонно не возрастает и, следовательно, сходится.
К сожалению ничего определенного нельзя сказать о сходимости последовательности . Формы 10 и 9 удобно задавать операторами Пf и Пf соответственно. Теорема 7. Форма в широком смысле изображения определяется ортогональным проектором Пf , при этом и . Доказательство.
Так как для , то получаем первое утверждение.
Для доказательства второго утверждения рассмотрим выпуклую задачу на минимум , решение которой определяется условиями см например, 11 . Отсюда следует, что и тем самым доказано и второе утверждение Замечание.
Так как , где fix - выходной сигнал i-го детектора в точке , причем fix0 ,i1 n, и, следовательно цвет реальных изображений непременно имеет неотрицательные , то для реальных изображений , условия и , эквивалентны.
Если же для некоторого , то условие не влечет . Заметим также, что для изображений g, удовлетворяющих условию , всегда . Для спектрозональных изображений характерна ситуация, при которой k детекторов регистрируют рассеянную объектами солнечную радиацию в диапазоне видимого света, а остальные n-k регистрируют собственное тепловое излучение объектов в инфракрасном диапазоне.
В таком случае любое изображение можно представить разложением 40 В котором . Если ИК составляющей солнечного излучения можно пренебречь по сравнению с собственным излучением объектов, то представляет интерес задача приближения изображениями f , в которых f1 - любая неотрицательная функция из , 1 - фиксированное векторное поле цвета, f2 - термояркость, 2 - термоцвет в точке . Форма Пf видимой компоненты f 40 определяется как оператор наилучшего приближения в задаче , в данном случае , причем Пf действует фактически только на видимую компоненту g, обращая невидимую, ИК, компоненту g в ноль. Форма ИК компоненты f может быть определена лишь тогда, когда известно множество возможных преобразований 2 f2. Некоторые применения.
Задачи идентификации сцен. Рассмотрим вначале задачи идентификации сцен по их изображения, неискаженным геометрическими преобразованиями, поворотами, изменениями масштаба и т.д. Ограничимся задачами, в которых предъявляемые для анализа изображения получены при изменяющихся и неконтролируемых условиях освещения и неизвестных и, вообще говоря, различных оптических характеристиках сцены. 1. Задачи идентификации при произвольно меняющейся интенсивности освещения.
Можно ли считать f и g изображениями одной и той же сцены, возможно, отличающимя лишь распределениями яркости, например, наличием теней В простейшем случае для идентификации достаточно воспользоваться теоремой 5, а именно, f и g можно считать изображениями одной и той же сцены, если существует распределение цвета , для которого v содержит f и g. Если , и , то, очевидно, существует , при котором fxv, gxv, а именно если если , и, наконец произвольно, если . На практике удобнее использовать другой подход, позволяющий одновременно решать задачи совмещения изображений и выделения объектов.
Можно ли, например, считать g изображением сцены, представленной изображением f Ответ следует считать утвердительным, если . Здесь - распределение цвета на изображении f, символ 0 означает, что значение g можно объяснить наличием шума, каких-либо других погрешностей, или, наконец наличием или, наоборот, отсутствием объектов объясняющим несовпадение g и f с точностью до преобразования распределения яркостей.
Такие объекты, изменившие распределение цвета g по сравнению с распределением цвета f, представлены в . 2.Идентификация при произвольном изменении распределения интенсивности и пространственно однородном изменении спектрального состава освещения.
Можно ли считать изображением сцены, представленной на изображении f, изображение, полученное при изменившихся условиях регистрации, например, перемещением или изменением теней и изменением спектрального состава освещения Пусть П - форма в широком смысле изображения f, определенная в теореме , П - форма f. Тогда ответ на поставленный вопрос можно считать утвердительным, если . Если изменение g обусловлено не только изменившимися условиями регистрации, но также появлением и или исчезновением некоторых объектов, то изменения, обусловленные этим последним обстоятельством будут представлены на . 3. Задачи совмещения изображений и поиска фрагмента.
Пусть f - заданное изображение, AX - подмножество поля зрения, A - его индикатор, Af -назовем фрагментом изображения f на подмножестве A, представляющем выделенный фрагмент сцены, изображенной на f. Пусть g - изображение той же сцены, полученное при других условиях, в частности, например, сдвинутое, повернутое, т.е. геометрически искаженное по сравнению с f. Задача состоит в том, чтобы указать на g фрагмент изображения, представляющий на f фрагмент сцены и совместить его с Af. Ограничимся случаем, когда упомянутые геометрические искажения можно моделировать группой преобразований R2- R2, преобразование изображения назовем сдвигом g на h. Здесь Qh Rn- Rn, hH группа операторов.
Векторный сдвиг на hH даст . В задаче выделения и совмещения фрагмента рассмотрим фрагмент сдвинутого на h изображения g в окне A 100 причем, поскольку где то в 100 - ограничение на сдвиг окна А, которое должно оставаться в пределах поля зрения X. Если кроме цвета g может отличаться от f, скажем, произвольным преобразованием распределения яркости при неизменном распределении цвета и - форма фрагмента f, то задача выделения и совмещения фрагмента сводится к следующей задаче на минимум .101 При этом считается, что фрагмент изображения g, соответствующий фрагменту Af, будет помещен в окно.А путем соответствующего сдвига hh, совпадает с Af с точностью до некоторого преобразования распределения яркости на нем. Это означает, что . т.е. в 101 при hh достигается минимум. 4. В ряде случаев возникает следующая задача анализа спектрозональных изображений выделить объекты которые видны, скажем, в первом канале и не видны в остальных.
Рассмотрим два изображения и . Определим форму в широком смысле как множество всех линейных преобразований A - линейный оператор R2- R2, не зависящий от xX. Для определения проектора на рассмотрим задачу на минимум . Пусть тогда задача на минимум эквивалентна следующей tr AAS - 2trAB . Ее решение знаком - обозначено псевдообращение.
Рис.1. fe - вектор выходных сигналов детекторов, отвечающий излучению e, e - его цвет 1,2,3 векторы цвета базовых излучений белый цвет, конец вектора находится на пересечении биссектрис.
Литература. 1 Пытьев Ю.П. Морфологические понятия в задачах анализа изображений Докл. АН СССР, 1975, т. 224, 6, сс. 1283-1286. 2 Пытьев Ю.П. Морфологический анализ изображений Докл. АН СССР, 1983, т. 296, 5, сс. 1061-1064. 3 Пытьев Ю.П. Задачи морфологического анализа изображений Математические методы исследования природных ресурсов земли из космоса, ред. Золотухин В.Г Наука, Москва, 1984, сс. хххх-х. 4 Пытьев Ю.П Чуличков А.И. ЭВМ анализирует форму изображения Знание,сер. Математика, Кибернентика, Москва, 1988, 47 стр. 5 Yu.P.Pyt ev. Morphological Image Analysis, Patt. Recogn. and Image Analysis, 1993, v.3, 1, pp.19-28. 6 Антонюк В.А Пытьев Ю.П. Спецпроцессоры реального времени для морфологического анализа реальных сцен. Обработка изображений и дистанционное исследования, -Новосибирск, 1981, сс. 87-89. 7 Антонюк В.А Пытьев Ю.П Рау Э.И. Автоматизация визуального контроля изделий микроэлектроники,Радиотехника и электроника, 1985, т. ХХХ,12, сс. 2456-2458. 8 Ермолаев А.Г Пытьев Ю.П. Априорные оценки полезного сигнала для морфологических решающих алглритмов Автоматизация, 1984, 5, сс. 118-120. 9 Пытьев Ю.П, Задорожный С.С Лукьянов А.Е. Об автоматизации сравнительного морфологического анализа электронномикроскопических изображений Изв. АН СССР, сер. физическая, 1977, т. 41, 11, сс. хххх-хххх. 10 A.A. Stepanov, S.Yu. Zheltov, Yu.V. Visilter.
Shape analysis using Pytev morphological paradigm and its using in machine vision. Proc. SPIE - Th. Intern.
Soc. For Optical Engineering Videometrics III, 1994, v. 2350, pp. 163-167. 11 Пытьев Ю.П Математические методы интерпретации эксперимента, Высшая школа, 351 стр 1989. 12 Майзель С.О. Ратхер Е.С. Цветовые расчеты и измерения.
МЛГосэнергоиздат 1941, Труды всесоюзного электротехнического института, вып.56. 13 P. Kronberg.
Fernerkundung der Erde Ferdinand Enke. Verlag Stuthgart 1985.