Содержание к диссертации
Введение
1. Цели и основные направления развития цифровых методов и алгоритмов обработки, распознавания и понимания изображений 19
2. Анализ случайных дискретно-точечных полей с помощью символьно-аналитических преобразований на ЭВМ 29
2.1. Оценивание надежности считывания случайных дискретных полей путем аналитического вычисления на ЭВМ параметрически заданных многомерных интегралов 33
2.1.1. Программы рекурсивных комбинаторно-аналитических вычислений в задаче двухпорогового считывания случайных дискретных изображений 40
2.2. Аналитический расчет асимптотически оптимальных декоррелирующих преобразований 49
3. Быстродействующие алгоритмы анализа случайных импульсно-точечных полей 57
3.1. Программы и алгоритмы оптимального по быстродействию поиска одиночного импульсного объекта 58
3.1.1.Одношаговые алгоритмы поиска 58
3.1.2. Многошаговые алгоритмы поиска 63
3.2. Символьно-аналитические и численные алгоритмы в задаче оптимального многоцелевого поиска 67
3.3. Быстрые алгоритмы классификации импульсно-шумовых кластеров на прямоугольной решётке 78
4. Быстрые алгоритмы идентификации и совмещения цифровых изображений 92
4.1. Инвариантные к повороту алгоритмы идентификации изображений, базирующиеся на спектральном разложении сигнала 94
4.2. Алгоритмы и программы высокоточного совмещения фрагментов двух цифровых изображений на основе статистического оценивания производных двумерного сигнала 99
4.2.1. Статистическое оценивание взаимного смещения двух изображений с использованием конечно-разностных соотношений для частных производных сигнала. Линейный случай 101
4.2.2. Статистическое оценивание взаимного смещения двух изображений с использованием конечно-разностных соотношений для частных производных сигнала. Нелинейный случай 103
4.3. Быстрое обращение симметричных теплицевых матриц в задачах оперативной обработки
последовательности цифровых изображений Ю7
4.3.1. Разностные уравнения для прямого
вычисления определителей и миноров 108
4.3.2 Двухсторонняя процедура Гаусса 112
4.3.3. Представление ленточной матрицы
в виде рекурсивного фильтра 115
5. Эффективные по быстродействию методы цифровой обработки динамических последовательностей изображений 120
5.1. Ускоренное восстановление глубины трехмерной сцены и оценивание неизвестных параметров камеры на основе одновременной обработки серии стереопроекций 120
5.1.1. Постановка задачи 122
5.1.2. Восстановление глубины сцены по известным сопряженным точкам 123
5.1.3. Поиск сопряженных точек при известных внутренних параметрах камеры и известной геометрии съемки 127
5.1.4. Автоматический поиск сопряженных точек при неизвестном положении главной точки изображения и неизвестных углах поворота камеры вокруг оптической
оси 130
5.1.5. Интерполяция трехмерных сцен по нерегулярным отсчетам
5.1.6. О точности восстановления трехмерной сцены по совокупности зашумленных стереопроекций 146
Сжатие без потерь динамической последовательности изображений 156
5.2.1. Сравнительные характеристики современных алгоритмов сжатия цифровых изображений без потерь 156
5.2.2. Сжатие статических цифровых изображений 165
5.2.2.1. Построение алгоритмов сжатия, адаптивных к изображению в среднем 166
5.2.2.2. Результаты сжатия эталонных и реальных цифровых изображений алгоритмами "статического" сжатия
без потерь 171
5.2.3. Сжатие динамической последовательности изображений. Проверка алгоритмов компрессии/декомпрессии на реальной информации 175
5.2.3.1. Описание стандартного подхода к сжатию, динамической последовательности изображений 178
5.2.3.2. Модифицированный метод сжатия динамической последовательности изображений 181
5.3. Быстрые алгоритмы субпиксельной цифровой реконструкции, основанные на поиске сигналов и изображений с минимальной энергией 188
5.3.1. Реконструкция сигналов с минимальной нормой и минимальной дисперсией 190
5.3.2. Быстрые алгоритмы восстановления изображений на основе критерия минимума дисперсии (двумерный случай) 199
5.3.3. Результаты численного моделирования 202
5.4. Повышение пространственного разрешения цифровых изображений с помощью кругового сканирования 203
Заключение 221
Литература
- Программы рекурсивных комбинаторно-аналитических вычислений в задаче двухпорогового считывания случайных дискретных изображений
- Символьно-аналитические и численные алгоритмы в задаче оптимального многоцелевого поиска
- Алгоритмы и программы высокоточного совмещения фрагментов двух цифровых изображений на основе статистического оценивания производных двумерного сигнала
- Восстановление глубины сцены по известным сопряженным точкам
Введение к работе
Актуальность темы, В настоящее время трудно наши область человеческой деніельносін н которой в той или шюн мере не использовались бы современные информациопно-вычиелшельные іехікі іоі ми ліачиїельная Чііііь котрых базируется на цифровых методах обработки июбрлАений Диссертационная работа представляет собой обобщение результатов исс il юваний п облаин цифровой обработки случайных полей и изображении проио ншшихся автором на протяжении более 25 леї в Инеіиіуіс ашомаїики и і.іскіромсірии СО РАН No і.пмяіошес большинство лих исслечоианий проведено it рамках тематических планов лаборатории "Нсрояі носпіьіч мегодон нсслс шпация информационных процессов", чем, собсівенпо и обі.ясняеіся (в посыновочном плане) кр\і рассмагринаемых в диссертации і,і ыч, - это сложные проб темы вероигпосшот характера возникающие при ан^мизе многомерных полей ijf>чайных временные рилов и динамически меняющихся н іображении, которые не моїуі быть решены с помощью lіандартного .чагемагическоіо анпараіа. а іребуїоі для своею решения ыидапии новых специализированных методов и мощном вычислительной поддержки
Значтельный вклад в решение задач и разработку математических методов, относящихся к цифровой обработке мшиомерных сиі налов и изображений, внесен мисі ими auiopLKHMH коллективами, научными школами и о і дельным и учеными как у нас в стране так и за рубежом И і зарубежных авторов наиболее известны в этой области рабоїьі Л Р Габипера, Ь Гоулда, Iі В Шафера, А Розснфельда, М Мак-Доннела, Р Ьлейхута, 1Ї1 Пелега, V [[ртгта Д Даджиона, ФМарнасти, I Кііпда, Iі Харди, Дж Серра и др Что касается исследований отечественных ученых в области новых методов обработки изображений, распознавания обрачов и их применений, то наибольшее признание получили работы [О И Журавлева, Л [I Ярославского, И ГЗагоруико В II Пягкина, В С Кнрич)ка, В А Виттиха, В В Сергеева, В А Сойфера, А АСпектора, 10 I Васина, В В Mori ля, А II Немирко, К К Васильева, Ю В Обухова, И Г Персианцева, В В Рязанова. Я А Фурмана и др
Важной особенностью, выделяющей реферируемую диссертацию из круга
научных исследований, проводимых в области цифровой обработки сигналов и
изображений является то, что отыскание решения каждой из проблем, составляющих
предмет диссертационного исследования, ведется с применением специально
разработанных программно-алгоритмических методов, ориентированных на
эффективное решение именно этой конкретно выделенной теоретической или
прикладной проблемы Такой подход продиктован тем обстоятельством, что набора
стандартных классических средств, обычно применяемых в области цифровой
обработки изображений, оказалось недостаточно для нахождения оптимальных
решений поставленных задач Получаемые стандартными методами решения не
удовлетворяли по одному или ряду параметров (как правило главный из таких
критических параметров - быстродействие создаваемых алгоритмов) Разработанные в
диссертации программные компоненты условно можно разделить на те. которые
относятся к традиционным численным методам расчета, когда в ходе решения задачи
компьютер используется в качестве мощного и надежного вычислителя, и на
компоненты, осуществляющие оригинальные символьно-аналитические
преобразования на ЭВМ
Пионерами в области машинно-аналитических преобразований у нас в стране являются Л В Канторович, Н Н Яненко, В М Глушков, И В Поттосин,
Л В.Ширков с коллегами (1960-1970 гг) Первые программные системы аналитического манипулирования были успешно применены ими для решения алгебраическо-дифференниальных уравнений, проведения полиномиальных выкладок, решения проблемных и трудоемких задач теоретической физики Разработанный в диссертации аппарат для проведения символьно-аналитических преобразований на ЭВМ создавался для решения проблем, возникающих при изучении случайных дискретно-точечных изображений Кроме того, созданные пакеты программ машинной аналитики за счет своей универсальности также эффективны при решении задач статистической радиотехники, теории массового обслуживания, автоматического сканирования, оптимального управления и в других активно развиваемых в последнее время научно-технических дисциплинах Предложенные в диссертации программные методы аналитического вычисления параметрически заданных объемных интегралов по сложным областям в «-мерном пространстве применимы не только для исследования процесса многопорогового считывания дискретных изображений, но и для построения оптимальных по быстродействию алгоритмов анализа динамически меняющихся дискретно-точечных полей - в частности, для минимизации времени поиска точечно-импульсных объектов образующих случайное поле Свидетельством актуальности проведенных в этом направлении исследований является то, что полученные в диссертации формулы, рассчитанные для анализа надежности считывания случайных полей и изображений, необходимы также во многих других научно-технических дисциплинах так, в теории массового обслуживания анало!ичными соотношениями описывается вероятность безотказной работы многоканальных обслуживающих систем с постоянным временем обслуживания Сходные в теоретическом отношении проблемы возникают при статистическом исследовании потока отсчетов в процессе регистрации ядерных частиц счетчиками с "мертвым" временем, а также в теории надежности при поиске неисправностей динамических систем, которые проявляются в форме случайной последовательности перемежающихся отказов
Значительное внимание в диссертации уделяется построению устойчивых и быстродействующих алгоритмов обработки сверхбольших массивов цифровых изображений, которые в нашем случае были востребованы, в частности, при анализе и классификации ледовых поверхностей, при реконструкции трехмерных сцен в условиях неполной или недостоверной информации о параметрах съемки, при исследовании методов повышения пространственного разрешения фотоматричных изображений по результатам субпиксельного сканирования И здесь важнейшим требованием было не только создание адекватных программных средств обработки информации, но и достижение максимально высокого быстродействия Разработанные в этой части диссертации алгоритмы оказались весьма эффективны при решении задач аэрокосмического стерео видения, возникших в рамках совмесгното российско-американского космического эксперимента RAMOS по выявлению, локализации и мониторингу быстропротекающих процессов на поверхности Земли и в атмосфере Построенное математическое обеспечение создавалось для решения вполне конкретных прикладных задач, но в принципе оно универсально и может применяться для исследования весьма широкого круга вопросов, возникающих в цифровой обработке стереоизображений
Не менее актуальны проведенные в диссертации исследования, касающиеся ускоренных алгоритмов идентификации и совмещения фрагментов цифровых изображений Они разрабатывались для автоматической классификации ледовых поверхностей по нескольким цифровым изображениям с большими отклонениями в ракурсах, но диапазон применения разработанных программных средств также
оказался значительно шире первоначального Таким образом, из скампного следует, ч го актуальность проведенных в іиссергации научных исследовании обеспечивалась в первую очереди необходимое! ыо ранни им меюдов решения трудоемких всроншосіпо-іеометрических ia ij'i цифровой обработки случайных полей и июбражений объем и с.юлоюсп. яитрых непрерывно возраеіаюі вевизи с раївитием ипформациоппо-вычислшельных кхнолоіий и ноіребносіями паучно-іехнического проірссса Кроме тою специализированная направленность созданных методов исс нею пан и и на эффективное решение конкретных прикладных ыддч сочетается н (Иссерlimiiu с мод\пышм принципом построения и универсальное 11,10 программных кимнонспюп веех сосланных сисісм 'по і к) ihojihl і успешно примспяіь их при и с с пело ванн и проблемных и прикладных вопросов не кілько при обработке случайных дискрешых полей и цифровых июбражепии по и н смежных научно-іехнических лисин ил пнах
Цель работы и шдача исследовании Целью работы нвішеїся создание маїсМіїїи'іескіїх меголов и посіроеиис \\л их основе бьісіродсиив_чі>пшх ирограммно-ллюриімических средств обеспечивающих ускоренное решение на ')НМ широкого кру і а сложных іеореіических и прикладных проблем вероятной мого характера, и от икающих при цифровой обработке многомерных сіп палов и июбражений Для доыижепия )гой пели решены следующие іадачи
Предложены и научно обоснованы принципиально новые методы исследования базирующиеся на проведении аналитических преобразований па ЭВМ с помощью коюрых изучен процесс іспевизиоипшо считывания случайных дискретно-точечных полей и рассчитаны асимптотически опшчальные декоррелируюшие преобраювания цифровых сиі налов Отображений) pa J n ич і ній l кисни і падкое і и
Разработаны новые бьіетродеіісівуютие методы анализа случайных дискрепю-и.чпульсных полей на основе которых построены оптимальные алгоритмы лока.'іиіашіито'іечпич объекте со случайным пространственным расположением и случайным временем іеперации импульсов, а іакже созданы проіраммьі быырои классификации одпосвязных импуньено-шухювых класіеров на нрямоуюлыши решетке
Созданы быстрые алюршмы идентификации цифровых изображений, базирующиеся на выделении инвариантных к повороіу характеристик двумерного сиінала, статистическом анализе ею конечных разностей н ускоренном обращении ленточных симмеїричньїх теплипевых матриц
С о таны алгоритмы и программы усюйчивото и высокоточного воссіацоніїения рельефа по серии цифровых аїрокосмических июбражений при неполных или неточных данных о геометрии съемки основанные на быстрой парад пел ы ю-труп повой обработке нескольких стерео проекций
Предложены методы и созданы быстрые алгоритмы повышения просі ранет венного разрешения цифровых изображений посредством отималыюи обработки данных, полученных с помощью реї улируемого субпиксельного сканирования
Методы исследований В диссертационной работе используются методы теории вероиіноеіей маїемаїИ'іеской статистики, теории случайных процессов, математическою моделирования, к о ррс ,тя цио и но-с центральної о анализа, вариационною исчисления комбинаторики, теории массового обслуживания,
вычислительной математики, прикладною программирования и ряда других дисциплин
Научная новизна лиссеріаиии заключается н следующем
Разработан новый >ффективный метод оценивания достоверное [ и регистрации случайных дискретно-точечных, m ображений, основан і и.ін па аналитическом расчете на JHM многомерных параметрических иніеіралов
Предложена матемашчески обосновала проіраммно реализована и применена для расчеіа вероятностей безошибочного двухпоропжоїп считывания едучаииы\ дискретных изображений методика проведения рекурсивных комбипатрно-аналитических преобразований на ЭВМ
і Создано npot рам мно-ал го ритми чес кое обеспечение для быстрою аналитического расчеіа собственных де коррелирующих преобразований, требующихся при отнмальним сжатии мноюмерных сигналов и цифровых изображений различной степени гладкости
Методами машинной анадитики и вариационною исчисления рассчитаны параметры оптимальных по быстродействию ашоритмов локализации точечных импульсных объектов со случайным временем іепершшн импульсов
Созданы быстрые алюритмы расчета іеомепричееких параметров односвязных импульсно-шумовых кластеров образующихся надискрешо-ирямоую.тьиои решетке при прохождении случайной ірупповои помехи
Разработаны и проіраммію реализованы новые высокоскоростные меючы оперативной идентифи капни и прецизионнош совмещения зашум.іеншах цифровых изображении основанные на сопоставлении кр)м:шых инвариантов изображения анализе конечных разностей дну мерно і о uu пала и ускоренном обращении ленточных симметричных теплиценых мл рип
Предложена и проіраммно реализована (цифровая методика иараллслыю-групповой обработки нескольких стереонроекций для высоко і очного восстановления трехмерного рельефа но серии аэрокосмических изображений при неполных или неточных данных о внешних и вііуїрепних параметрах камер
Разработаны новые скоростные методы повышения пространственною разрешения изображении основанные на поиске сигнала с минимальной анергией и оптимальной обработке результатов кругового сканирования
Практическая иенность и реализация научных результатов работы Полученные в диссертации точные аналитические выражения описывающие распределение разности порядковых статистик при случайном разбиении интервала, кроме чисто теоретической ценности, позволяют выбрать оптимальные параметры процесса автоматического считывания дискретно-точечных полей при наличии нескольких пороговых уровней Эти же соотношения описывают вероятность безотказной работы целого класса многоканальных систем с постоянным временем обслуживания, что делает полученные результаты непосредственно применимыми в телефонии, радиосвязи на транспорте (например, при проведении железнодорожных сортировок или при оптимизации управления уличным движением) и во многих других приложениях теории массового обслуживания
Разработанный в диссертации пакет программ машинной аналитики дал возможность рассчитать асимптотически оптимальные декоррелирующие преобразования для сигналов различной степени гладкости, а это, в свою очередь,
обеспечило построение рациональных алгоритмов сжатия и кодирования сигналов с учетом их статистических характеристик Построенные в диссертации методы оптимального поиска точечных импульсных объектов применимы для решения самых разнообразных прикладных задач в которых требуется минимизировать время локализации точечных объектов способных в случайные моменты времени генерировать мгновенные ельта-импульсы Такие задачи возникают при обработке сигналов и изображении как в научной сфере (радиоастрономия, квантовая физика [еория надежности и др ) так и во многих промышленных естественно-технических и других приложениях науки (например при поиске неисправностей в динамических системах в случае перемежающихся отказов) а также в различных областях военного дела
Предложенные в диссертации инвариантные к поворот алгоритмы идентификации изображений на несколько порядков увеличивают скорость привязки реальных зашумленных изображении а предложенные методы субпиксельного совмещения обладают высоким быстродействием и надежностью что позволило с успехом применить их при решении сложных и трудоемких задач классификации ледовых поверхностей (хоздоговорная работа I ребень-СО по заказу НПО Ленинец", г Санкт-Петербург) Созданная в ходе выполнения диссертации скоростная высокоточная методика цифрового восстановления трехмерного рельефа по серии аэрокосмических снимков базирующаяся на параллельной обработке нескольких стереопроекций успешно применена в рамках совместною российско-американского проекта RAMOS для реконструкции и мониторинга земной поверхности
Построенные в работе ускоренные алгоритмы обращения симметричных теплицевых мафии в сочетании с двумя разработанными алгоритмами разложения сигналов (соответственно гармоническим и дифференциальным) существенно ускорили и повысили точность решения задач оперативной обработки последовательности цифровых изображений
Результаты полученные в диссертации, послужили научным фундаментом
для многих научно-исследовательских и опытно-конструкторских работ,
выполненных Институтом автоматики и электрометрии СО РАН "Радуга", "Вихрь",
Исеть' Пакет', Луговина", Семан", "Гребень-СО" "Цимус-СО", "Чулым",
"Стерео", "Рельеф", "Уссури" и др
Значительная часть вошедших в диссертацию исследований была поддержана грантами российских и международных научных фондов и организаций (в частности грантами РФФИ № 03-01-00913 'Методы повышения пространственного разрешения фотоматричных изображений основанные на оптимальной цифровой обработке результатов субпиксельного сканирования", № 99-01-00610 "Исследование и разработка робастных методов восстановления сигналов по их неравномерным отсчетам", грантами Миннауки № 020105 221 "Модели методы и программно-аппаратные средства обработки и анализа данных дистанционного зондирования, получаемых с сети космических станций, для оценивания в реальном времени динамики событий и явлений на поверхности Земли и в атмосфере" и № 0201 05 12 Модели методы и программно-алгоритмические средства анализа многозональных стереоизображений, получаемых с сети космических станций", программами Президиума РАН № 5 16/2003 'Определение пространственно-временной эволюции трехмерной структуры и параметров движения сложных динамических сцен по данным мониторинга поверхности Земли и приземного слоя атмосферы" и № 2 13/2004 Быстродействующие методы анализа интегрированных потоков данных в
системах аїрокосмического сіереовидения на основе оптимальной цифровой обработки' і рантом № І (Н'-962 американского исследовательски о фон іа СІШГ)
На нішшпу выносятся сіедутщигпччожепии'
І ІОІЛіПШ ІірИІЩИІІИаЛМЮ MCI ОЛЫ рЄ[ИЄНИЯ lipilkJId 1ИЫ\ И
фу и іЕімсім.1 [ції і\ задач оіірабоїмі дискретных изображении Гышрчшниссч
Н.І ІІ|>ОВЄ КПИН ф) ДОС ЧЬИ \ LMUlH.l III ІИрОНаїШІ.ІХ СИМВО If ltd .Ш.І.ІИІ И'ІИ.МІЧ
преобразовании на МІМ с iioviiphi.io которых ішслііосм.
іелеиизиошюіо считывании і луїашнач іискреіньїх изображении и паи iun і
аснмпіаіичики оншча.п.ные дскоррслируїонше преобразовании
мпоіочерніїч сиіналов и іноіїраліпиіі ра(личини иенепи їла іміии
І кім роемы шпнмалышс по Гіьісіродействню прагепіи о питанною периодическою и мноіопелевою поиска точечных импульсных 0ІУІ,ЄКІОВ со случайным нроираниненным распределением и случайным кременем генерации импульсов
Гаїрабоганм быстрые алюритки идентификации фраіменіоп цифровых изображений основанные на сравнигелыю.ч апалиіе иішариапіпілх к понороіу харамерисіик двумерною сшпа.ча еіатнстическом анализе ею конечных разностей и ускоренном решении линейных алгебраических системі, симметричными ісіілицсьмми маїрицами специальною вида
(.оілгіїн.і новые методы, алюришы и проіраммьі ускоренною решения на ')ВМ фудос.чких чадач дальнею космическою сіереошдеиия, базирующиеся па параллелыш-грумпонои обработке нескольких цифровых сіереопроешиіі с нредвариіельпои линеаризацией задачи н последующей глобальной мної омерпои оптимизацией
Предложены обоснованы и пршраммно рсалиюваны быирые алюршмы повышении просі ранетвешюю разрешения фоюмагричных изображении, основанные на оптимальной обрабоїке данных реіулнруемою субниксельної о сканирования
Апробация набиты Полученные в диссертации новые научные резулыаты докладывались чл Всесоюзной конференции "Автоматизация научных исследований на основе применения ")ВМ" (і Новосибирск, 1974], на Всесоюзной конференции "Применение и перспективі развита ')ВМ ГС.-10Ш" (і І'ига,1978), на Всесоюзной конференции "Автоматизация научных исследовании на основе применении '")ВМ" (г І Іовосибирск 1979) на Всесоюзной конференции "Авгочаїизацня научных исследований на основе применения ')ІШ" (і Новосибирск, 1981). на XIX Всесоюзной школе по аитомашзаіши научных исследований (і Новосибирск 1985). на Международном коллоквиуме "Новые информационные іехнолщии" (і Москва, 8-10 октября ІУ9И ), на 10 Международном симпозиуме "Модульные компьіоісрньїе системы и сети" (і Саїш-Пстсріїурі, ], на научной конференции "Научная сессия-93" в ИАи'з СО РАН (г Новосибирск І993і ) на II Всероссийской конференции "Распознавание образов и анализ изображении новые информационные ісмюлоіии" (і Ульяновск. 1995г ). на научной конференции "Научная ссссия-9б" в ИЛиЭ СО РАІI (г Новосибирск. 1996т) на 111 Всероссийской конференции "Распознавание обраюв и анализ изображений новые информационные іехполоіии" (і Нижний Поенород 1-7 декабря І997і ) на IV Всероссийской с между нарочным учасіием конференции "Распознавание образов и анализ изображений новые информационные іечнолоіии" (г Новосибирск 11-18 октября 1998:), на Научном Совете ПИП "Перспекшвные информационные технологии" но направлению "Распознавание образов и анализ
изображений" (г Новосибирск, 1998г), на V Международной конференции "Распознавание образов и анализ изображений новые информационные технологии" (г Самара, 16-22 октября 2000г), на Международной конференции "Информационные системы и технологии"-ИСТ'2000 (Новосибирск, 8-11 ноября 2()()0г), на VII Международной конференции IASTED по обработке сигналов и изображений "Signal and Image Processing" (г Гонолулу, Гавайи, США, 13-16 августа 2001 г), на Международной конференции IASTED по автоматизации управлению и информационным технологиям "Automation Control, and Information lechnology" (г.Новосибирск, 10-13 июня 2002г), на VI Международной конференции "Распознавание образов и анализ изображений новые информационные технологии" (г Великий Новгород, 21-26 октября 2002г ), на Международной конференции IASTED по обработке сигналов, распознаванию образов и их приложениям SPPRA-2003 (г Родос, I реция 30 июня-2 июля 2003г) на Международном Симпозиуме по распознаванию образов и пониманию изображений OGRW-6-2003 (the 6-th German-Russian Workshop on Pattern Recognition and Image Understanding, Russian Federation, Katun village, Altai Region, August 25-30 2003)
Личный вклад Участие автора заключается в научной постановке и математической формализации всех исследованных в диссертации теоретических и прикладных проблем, разработке идейной части алгоритмов и непосредственном решении задач, составляющих предмет диссертационного исследования, в создании всех изложенных в диссертации программных компонентов Участие других авторов в определенных этапах работы полностью отражает приводимый в диссертации список литературы
Объем и структура работы Диссертация состоит из введения 5 разделов, заключения, списка литературы и приложений Материал изложен на 241 странице, включая 40 рисунков, 20 таблиц и список литературы из 173 наименовании
Программы рекурсивных комбинаторно-аналитических вычислений в задаче двухпорогового считывания случайных дискретных изображений
В этом подразделе 2.2 приводится более скоростной узко специализированный алгоритм вычисления вероятностей РІі2(Є), т.е. вероятностей безошибочного телевизионного считывания случайных дискретных изображений, проводимого при двух пороговых уровнях интегратора. Необходимость разработки нового метода объясняется тем, что трудоемкость алгоритмов, изложенных в подразделе 2.1, не позволяла вычислять формулы P,Jtk{) при значениях п 9.
По аналогии с известным решением (2.3) для к=\ мы попытались найти общее решение P,hk(s) для случая к—1. В отличие от описанных выше алгоритмов при создании этого метода использовалась совершенно другая математическая техника, а именно: с помощью чисто комбинаторных средств были построены соответствующие рекурсивные соотношения, которые применялись для расчета целочисленного прототипа формул Р„,2().
Формулы РПі2І) как функции непрерывного аргумента є получались из дискретной аппроксимации с помощью предельного перехода. При этом использовалась следующая комбинаторная модель. Интервал (0,L) интерпретировался как совокупность г равных дискретов. Случайное бросание п точек на интервал (0,L) интерпретировалось как случайное бросание п неразличимых шаров по г ящикам. Множество из / смежных ячеек служило аналогом подынтервала длиной Є. Исход бросания, когда ни один из таких /-подынтервалов, содержащихся внутри исходного г-интервала (0,L), не имел более 2 точек, считался "успешным", а отношение общего числа "успешных" бросаний Q{r,n,l) к общему числу исходов опыта Q(r,n) принималось в качестве целочисленного аналога для вероятности Лг,2( )-Если бы имелась возможность найти замкнутое аналитическое выражение для общего числа "успешных бросаний", то это было бы эквивалентно полному решению задачи для к=2, поскольку в этом случае вероятность Pn,i{) вычисляется простым предельным переходом Pn,i(z)= hm / \\ (2.10) а выражение для общего числа бросаний Q(r,ri) известно (Feller, W. (1967) An Introduction to Probability Theory and Its Applications (in Russian), Mir, Moscow) [91]: Q(r,n) = C;+J_, = K—- -f. (2.11) n\(r-\)\
Прежде чем привести рекуррентно-рекурсивные соотношения для расчета числа "успешных " бросаний Q(r,n,l) введем ряд соглашений относительно дальнейших обозначений. Количество шаров п запишем в таком виде : n=2N+s; N=0,1,2,...; =1,2. Общее число "удачных" бросаний п шаров по г ящикам при условии, что один шар попал в 1-й ящик, один шар - в /-й, а остальные попали в ящики с номерами, большими, чем / (/ /) , обозначим q{i,r,n,l).
При фиксированном п функции q(i,r,n,l) и Q{r,n,l) представляют собой кусочно-полиномиальные выражения относительно остальных аргументов. Для полиномов, описывающих поведение этих функций на отдельных участках, введем такие обозначения:
Начальные данные для инициации рекуррентно-рекурсивного вычислительного процесса берутся из тривиальных соображений, когда «=0,1,2. Из-за огромного объема вычислений, необходимых для осуществления описанной рекурсии, весь алгоритм комбинаторного расчета был опять-таки реализован в виде компьютерной программы. На этом пути удалось продвинуться в вычислении вероятностей РПіг{є) и получить новые ранее неизвестные формулы. В частности, для четных п рассчитаны соотношения:
Символьно-аналитические и численные алгоритмы в задаче оптимального многоцелевого поиска
В подразделе 3.2 исследуются аналитические и численные алгоритмы оптимального многоцелевого поиска. Основная задача, которая здесь рассматривается, может быть сформулирована следующим образом. Ма отрезке (0,//) находится п точечных объектов. Об их местоположении не имеется никаких априорных сведений, так что можно считать, что п точек равномерно распределены на отрезке (О, L). Каждый объект в случайные моменты времени производит мгновенные импульсы (дельта-функции), паузы между которыми имеют показательное распределение с параметром Я. Как и ранее, импульс фиксируется, если активный объект, инициировавший импульс, находится в "окне обзора" регистрирующего устройства. Необходимо за минимальное время отыскать все источники с точностью . Вообще говоря, построение оптимальной стратегии многоцелевого поиска можно свести к последовательной процедуре, когда на первом этапе с требуемой точностью определяется местоположение одного из / источников, после этого ищется один из (я-1) оставшихся и т.д. Здесь возможны два различных подхода: либо на каждом последующем этапе используется информация, накопленная на всех предыдущих, либо такого накопления информации не происходит. Использование ранее накопленной информации приводит к чрезмерному усложнению алгоритмов поиска и самой сканирующей системы, поскольку в этом случае она должна обладать возможностями для хранения и переработки промежуточных данных.
Рассматриваемые ниже алгоритмы построены в предположении, что регистрирующая аппаратура не имеет памяти, так что поставленная выше задача сводится к нахождению оптимальной по быстродействию стратегии поиска одного из п точечных объектов с заранее заданной точностью с.
Процедуру поиска на каждом из п этапов, в свою очередь, тоже можно рассматривать как многошаговый процесс. Так как первоначально не имеется никаких априорных сведений о расположении п источников внутри отрезка (0,L), то на первом шаге поисковое усилие должно быть равномерно распределено между всеми точками х є (О, L). Реализовать такое усилие можно, например, сканированием всего отрезка некоторой щелью шириной /j. Затем (при регистрации импульса) поиск продолжается внутри выделенного окна шириной /j некоторой другой щелью, имеющей ширину І2, и т.д. На последнем шаге (а их количество зависит от п,Є,Ь) для обеспечения необходимой точности локализации поиск ведется щелью шириной Є. Задача теперь заключается в том, чтобы для заданных значений п,є и L определить оптимальное число этапов сканирования k(n,s,L), а также ширину сканирующего окна на каждом из них.
После нахождения одного из объектов значение п уменьшается на единицу, и поиск повторяется для п — п — \ и т.д. Введем в рассмотрение функцию g(x) - плотность распределения центра щели в момент регистрации первого импульса. Если предположить, что п источников расположены в точках Хі,лг2,...,х/г, а сканирование проводится щелью шириной /, то для g(x) справедливо соотношение gW = l[x-(xi-0.5l)]x\[(xi+0.5l)-x], (3.17) где \[х] - функция единичного скачка: \[х] 1, х 0.
В дальнейшем нам потребуется знание распределения числа объектов в щели в момент регистрации импульса. Для этого нужно вычислить Рп(к,1) вероятность того, что в щели в момент регистрации импульса окажется в точности к (к —1,2,...,/?) источников, включая объект - генератор импульса. Поскольку при реализации равномерного поискового усилия возникают нежелательные краевые эффекты, то для того, чтобы последующее изложение сделать более строгим, будем считать отрезок свернутым в окружность длиной L. При этом без ограничения общности можно считать, что L — 1, а 0 / 1.
Пусть объекты расположены в точках Х\,х2,...,хп. Считая точку Х началом отсчета, упорядочим все остальные источники, двигаясь от точки Х = 0 по часовой стрелке. Вероятность P}J(k,l) складывается из вероятностей того, что в момент фиксации импульса в щель попадают точки Х\, Х-у v-5 Хк ЛИОО л2, Лі,..., Хл. , і и т.д. Таких комбинаций всего п.
Алгоритмы и программы высокоточного совмещения фрагментов двух цифровых изображений на основе статистического оценивания производных двумерного сигнала
В подразделе 4.2 диссертации исследуются методы и алгоритмы прецизионной привязки изображений. Основная задача, о которой идет речь, формулируется следующим образом. Имеются два изображения U и V: Ф,у) = Ах, у) + O,J0; (4.8) v(x, У) = Ах + дх, у + ду) + 7/(х, у). Здесь/(х,у)- опорное изображение; и(х,у) и v(x,y) - наблюдаемые зашумленные изображения, отличающиеся одно от другого относительным сдвигом 8 = ( 5х, ду), где Sx - сдвиг по оси абсцисс, а ду - сдвиг по оси ординат; (х,у) и 1](х,у) - две различные реализации "белого" гауссовского шума с неизвестной дисперсией а. Взаимный поворот изображений исключен (либо по условиям регистрации, либо в результате предобработки). Необходимо для заданного в цифровом виде фрагмента щ = u(ih, jh) = Aty, jh) + {ih, jh) = /«+« (/, j = 0,n-l) (4.9) одного изображения оценить его местоположение на втором изображении.
Вообще говоря, в большинстве реальных задач обработки изображений оказывается достаточным оценить взаимное смещение фрагментов с точностью до шага решетки и, и для их решения разработан широкий спектр эффективных алгоритмов, учитывающих как специфику обрабатываемых изображений, так и специфику конкретной научной или прикладной задачи [114-117]. Но существует класс задач с повышенными требованиями к точности координатной привязки, для которых необходимо оценить сдвиг с точностью до долей дискрета, что требует разработки специализированных алгоритмов, поскольку в таких задачах прямое использование "целочисленных" алгоритмов, как правило, совершенно неэффективно либо по точности привязки, либо по быстродействию, а для некоторых задач критичными являются оба этих параметра. В этом подразделе 4.2 мы предполагаем, что "грубая" привязка (т.е. совмещение с точностью до дискрета) зарегистрированных изображений уже проведена (разумный способ ее осуществления уже обсуждался в подразделе 4.1), так что в соотношении (4.8) можно считать, что &, Sy 0.5/z, причем шаг дискретизации h, не нарушая общности, можно в дальнейшем принять равным единице. Из реализованных нами алгоритмов прецизионной привязки наилучшие результаты на модельных и реальных изображениях были получены с помощью двух способов разложения сигнала в ряд, когда в качестве оценки производных сигнала используется статистика самих совмещаемых изображений (первый способ - разложение с удержанием членов до первого порядка малости относительно оцениваемых смещений дх, и ду, второй способ - с удержанием членов до второго порядка малости).
Оценивание эффективности всех исследованных алгоритмов осуществлялось по трем параметрам: точности совмещения, быстродействию и устойчивости по отношению к шуму различного уровня. В качестве эталонного метода, с которым проводилось сравнение, был выбран метод максимального правдоподобия с билинейной интерполяцией изображения между узлами решетки. Сложность практического применения метода ММП заключается в том, что его стандартная реализация требует огромных вычислительных ресурсов. Поэтому нами были внесены собственные доработки в стандартный алгоритм ММП. В результате использования циклической редукции [118] эффективность вычислительного процесса выросла на порядок. Но поскольку быстродействие усовершенствованного метода максимального правдоподобия все равно не позволяло применять его в задачах, требующих проведения обработки в реальном времени, были предложены и программно реализованы два алгоритма прецизионного расчета взаимного смещения двух сдвинутых фрагментов изображения, основанные на статистическом оценивании частных производных двумерного сигнала по его конечным разностям.
Восстановление глубины сцены по известным сопряженным точкам
Описанный выше алгоритм поиска сопряженных точек эффективно работает в том случае, когда полностью известны все внутренние и внешние параметры камеры, включая полные сведения о геометрии съемки. Задача существенно усложняется, когда часть этих параметров неизвестна. В нашем случае, как уже отмечалось, требовалось разработать устойчивый алгоритм нахождения сопряженных точек в условиях, когда неизвестны координаты главной точки изображения и углы поворота камеры вокруг оптической оси. При этом угол расхождения между направлениями оптических осей анализируемых стереопроекций предполагался произвольным.
Для решения этой задачи нами был разработан специальный алгоритм отыскания сопряженных точек на стереопроекциях, не использующий априорных сведений о положении главной точки камеры и об углах поворота камеры вокруг своей оптической оси. Алгоритм предназначен для работы в условиях, когда характерное удаление камеры от наблюдаемого участка земной поверхности в момент регистрации первой и второй стереопроекций (эти расстояния обозначим соответственно L\ и Li) СОх х О) существенно больше перепада высот восстанавливаемого рельефа.
Таким образом, предполагается, что значения высот в каждой точке восстанавливаемого рельефа лежат в некотором интервале (Zmjn,Zmax), причем (Zmax-Zmjn) много меньше расстояний L\, L2. Координаты камеры в глобальной системе, а также фокусное расстояние камеры и линейные размеры элемента ПЗС матрицы считаются известными. Алгоритм содержит несколько основных этапов.
Сначала осуществляется поиск особых (реперных) точек. Сразу отметим, что алгоритмы поиска особых точек должны устойчиво выделять некие экстремальные локально-точечные неоднородности, присутствующие на анализируемых изображениях. В описываемом алгоритме сначала строится поле, характеризующее дисперсию сигнала в окрестности изучаемой точки. Координаты глобального максимума поля дисперсии являются главными претендентами на включение в список особых точек. Затем, исключая из дальнейшего рассмотрения найденную точку максимума вместе с ее окрестностью (в нашем случае это было окно 9x9 элементов), аналогичным образом (т.е. путем отыскания глобального максимума по оставшейся области) определяется вторая особая точка и т.д. Количество выделяемых особых точек можно варьировать изменением размера окна.
Суть процедуры, осуществляемой на следующем этапе, заключается в том, чтобы подгонкой неизвестных углов поворота камеры вокруг оптической оси, а также неизвестных координат главной точки изображения добиться такого положения, чтобы максимально возможному числу особых точек, найденных на первом изображении, были поставлены в соответствие особые точки на другом изображении. При этом должна быть минимизирована сумма невязок, взятая по всем сопряженным точкам с учетом уже известного проективного преобразования, связывающего эти стереопроекции. Важным моментом здесь является обеспечение необходимого быстродействия, поскольку, во-первых, приходится вести оптимизацию сразу по нескольким параметрам, входящим в систему уравнений нелинейно, во-вторых, необходимо корректно учесть тот факт, что особые точки на изображениях имеют различную пространственную глубину.
Обойти различие особых точек по пространственной глубине, не прибегая к перебору в диапазоне возможного изменения глубин, удается за счет того, что разброс высот особых точек на изображениях, как отмечалось выше, несопоставим с расстоянием от них (как и от всей наблюдаемой трехмерной сцены) до точек съемки. Поэтому, временно считая наблюдаемый объемный рельеф плоским, мы вносим в минимизируемый функционал незначительные искажения, которые в решаемых нами задачах дальнего космического стереовидения практически не влияют на точность оценивания неизвестных параметров съемки и надежность программно-автоматического отыскания сопряженных точек. Итак, сначала
осуществляется итеративный перебор по углам поворота камеры вокруг оптической оси. Далее последовательно для каждой особой точки исходного изображения производится поиск эпиполяр на других изображениях. Поиск осуществляется при ограничении на высоту соответствующей особой точки, которая считается находящейся в интервале (Zmjn,Zmax), так что эпиполяра из линии преобразуется в отрезок. При этом предварительно полагаем координаты главной точки ХО и 70 равными половине ширины рабочего диапазона ПЗС-матрицы по осям АГ и У соответственно, т.е. на первом шаге процесса подгонки неизвестных параметров считаем, что оптическая ось проецируется в геометрический центр снимка.
