Содержание к диссертации
Введение
1 Анализ и исследование алгоритмов идентификации групп звезд для астронавигационных приборов 17
1.1 Эволюция и классификация алгоритмов распознавания групп звезд для астроприборов 17
1.1.1 Геометрические алгоритмы 19
1.1.2 Графовые алгоритмы 22
1.1.3 Пирамидальный алгоритм Мортари и SLA-методика 24
1.1.4 Сеточные алгоритмы 28
1.2 Сравнительный анализ вычислительной сложности алгоритмов распознавания групп звезд 30
1.3 Проблема селекции «ложных звезд» 33
1.5 Выводы по главе 1 35
2 Разработка методов селекции звезд на фоне помех типа «светящаяся частица» 37
2.1 Постановка задачи и требования к методам селекции помех типа «светящаяся частица» 37
2.2 Анализ траекторий движения проекций звезд 39
2.3 Метод селекции звезд на основе критерия постоянства взаимных угловых расстояний 45
2.3.1 Непараметрический алгоритм предварительного отбора звезд... 47
2.3.2 Параметрический алгоритм предварительного отбора звезд 50
2.3.3 Алгоритм окончательного отбора звезд 53
2.4 Обоснование выбора линейной модели и оценка погрешности алгоритма 55
2.5 Метод селекции звезд, основанный на критерии постоянства скоростей 59
2.6 Выводы по главе 2 68
3 Методы определения координат точечных источников света 72
3.1 Повышение точности алгоритмов определения координат 72
3.2 Проблема определения координат точечного источника света и методы ее решения 75
3.3 Методы фильтрации изображения 77
3.4 Проблема определения положения звезд в условиях вращения спутника по орбите 80
3.5 Выводы по главе 3 81
4 Программно-аппаратная реализация предложенных методов и анализ полученных результатов 83
4.1 Особенности организации и функционирования бортового вычислительного блока 83
4.2 Обзор и сравнение современных сигнальных процессоров 84
4.3 Методика моделирования алгоритмов определения положения ТИС 85
4.4 Результаты моделирования алгоритмов и их анализ 91
4.5 Алгоритм пересчета звездного бортового каталога 94
4.6 Методика оценки неортогональности итоговой матрицы
ориентации 101
4.8 Выводы по главе 4 105
Заключение 108
Список использованных источников 111
Приложение
- Сравнительный анализ вычислительной сложности алгоритмов распознавания групп звезд
- Метод селекции звезд на основе критерия постоянства взаимных угловых расстояний
- Проблема определения координат точечного источника света и методы ее решения
- Обзор и сравнение современных сигнальных процессоров
Введение к работе
В диссертационной работе исследованы алгоритмы распознавания групп звезд для задачи определения ориентации космического аппарата в пространстве. Для повышения устойчивости алгоритмов к помехам типа «светящаяся частица» разработаны, исследованы и реализованы вспомогательные алгоритмы предварительной селекции звезд на основе критериев постоянства скоростей и постоянства взаътных угловых расстояний. Для проверки эффективности, тестирования и отладки предложенных алгоритмов реализовано программное обеспечение визуализации их работы. Для увеличения вероятности правильного распознавания исследованы характеристики алгоритмов определения координат проекции точечного источника света на фоточувствительной матрице. Проведено имитационное моделирование с целью сравнения эффективности алгоритмов для методов «центр тяэюести» и максимального правдоподобия.
Объектом исследования являются методы, алгоритмы и программные средства распознавания звезд для задачи определения автономной ориентации космического аппарата в пространстве. Предмет исследования составляют методы и алгоритмы повышения эффективности процедуры распознавания групп звезд и их вероятностные и вычислительные характеристики.
Определение угловой ориентация космического аппарата (КА) в пространстве осуществляется с помощью гироскопов или специальных опто-электронных приборов. Оптоэлектронные приборы осуществляют определение ориентации по различным небесным объектам - Солнцу, Земле (в инфракрасном диапазоне, [18]), звездам [28, 29, 22, 14]. Среди перечисленных объектов для определения ориентации КА наибольшую точность дают звезды (в англоязычной литературе используется термин star tracker).
Схема функционирования прибора звездной ориентации представлена на рисунке 1. Свет от звезд проходит через оптическую систему и попадает на фоточувствительную матрицу (матрицу Пространственно-зарядовой связи (ПЗС) или Active Pixel Sensor(APS)). Сигнал проходит аналого-дискретное преобразование, и поступает на вычислительный блок прибора. Используя последовательность отображений участков звездного неба, необходимо определить матрицу перехода из приборной в геоцентрическую систему координат. Приборной системой координат называется система координат, связанная с прибором звездной ориентации. Центр геоцентрической системы координат связан с центром масс Земли, а одна из осей направлена на точку весеннего равноденствия. Зная положение спутника в геоцентрической системе координат, траекторию орбиты и текущее время можно определить положение КА относительно поверхности Земли. і ,' ,
V—J j
Рисунок 1 -- Схема функционирования прибора звездной ориентации Примечание — Цифрами помечено: 1 — участок звездного неба, 2 — оптиче ская система, 5'-фоточувствительная матрица, 4 — вычислительный блок, 5-опто-элетронный прибор.
Первые приборы ориентации космического аппарата по звездам, использующие матрицы ПЗС, были разработаны в 1976 г [94]. В своей работе они использовали только яркие звезды, поэтому применяемые в них алгоритмы ориентации были достаточно примитивными [49, 50, 65]. Впоследствии с развитием процессоров и элементарных фотоприемников увеличивалось количество рабочих звезд, а вместе с ним и сложность алгоритмов.
Ведущими научными и производственными центрами разработки приборов звездной ориентации являются: JenaOptronik (Германия), Sodern (Франция), Texas University (США), Technical University of Denmark (Дания), Aerospace GNC Laboratory at the University of Naples (Италия), Институт Космических Исследований РАН (Москва), Научно-производственное объединение «Геофизика-Космос» (Москва).
В последние годы было опубликовано достаточно большое количество работ, посвященных алгоритмам определения ориентации К А по звездам: [31, 32, 33, 36, 37, 40, 41, 42, 44, 46, 47, 51, 54, 55,60, 61, 72, 76, 78, 83, 95, 97, 98, 99], что обусловлено, в первую очередь, хозяйственной важностью данной проблемы. Точность ориентации спутников существенно влияет на работу систем связи, телевещания, определение координат объектов на поверхности Земли.
При разработке алгоритмов звездной ориентации необходимо учитывать, что исследуемая проблема относится к задачам реального времени, поскольку действуют существенные ограничения на время, требуемое для ориентации КА. Решение задачи усложняется постоянным вращением КА по орбите и изменением его ориентации. Кроме того, существуют значительные ограничения на мощность процессора, используемого в приборе, что связано с недостатком электроснабжения автономных систем в космосе и проблемой терморегуляции бортового вычислительного блока
Так, определение ориентации КА должно осуществляться за время около 4-х секунд, а частота современных процессоров, используемых в приборах навигации КА, составляет 100 - 200 Мгц. При таких ограничениях количество операций с 32-х разрядными словами, которые может выполнить процессор за время, отведенное для определения ориентации КА, имеет порядок 109. Количество пикселей на матрице ПЗС имеет порядок 105, поэтому только для первичного анализа изображения участка звездного неба (фильтрация помех, вычисление координат звезд, отождествление кадров) требуется порядка 109 элементарных операций.
Критичным является не только время работы, но и размер программного обеспечения приборов определения ориентации КА по звездам. Объем
ОЗУ и ПЗУ (чаще всего флеш память) для современных бортовых систем составляют порядка нескольких мегабайт, что связано с жесткими требованиями к их радиационной активной стойкости и требуемой наработкой на отказ. Время функционирования прибора звездной ориентации на орбите составляет 10-15 лет.
Осуществление ориентации по звездам затруднено наличием оптических искажений (дисторсия, хроматическая аберрация и т.д.), собственными шумами матрицы и прибора, засветкой от Солнца, Луны и газопылевого облака КА (в том числе помехи типа «светящаяся частица), наличием «ложных» звезд. Требуемая точность в ориентации КА для современных приборов составляет порядка десятка угловых секунд, в то время как разрешающая способность матрицы и оптической системы составляет до нескольких угловых минут. Высокая точность астронавигационных приборов достигается благодаря использованию эффективных алгоритмов, анализирующих множество отображений звездного неба. Благодаря разработке эффективных алгоритмов, учитывающих, с одной стороны, доступные характеристики бортового вычислителя, а с другой, наличие оптических искажений, помех, «ложных» звезд, возможно значительно повысить точность ориентации.
Актуальность диссертации обусловлена необходимостью разработки методов и программных средств, повышающих эффективность процедуры распознавания групп звезд в автономной астронавигации на основе введения и исследования дополнительных критериев селекции помех типа «светящаяся частица» и разработки эвристических алгоритмов и строгих статистических процедур, базирующихся на этих критериях. Кроме того, недостаточно исследованы алгоритмы определения положения точечного источника света, спроецированного на фоточувствительную матрицу.
Целью диссертационной работы является разработка методов и программных средств для повышения эффективности и точности процедуры распознавания групп звезд астроприборами при наличии помех различного типа и оценке качества работы предложенных методов. Для достижения указанной цели ставились и решались следующие задачи: анализ вычислительной сложности и устойчивости современных методов распознавания групп звезд к наличию «ложных звезд»; исследование и создание программной модели отображения проекций светящихся точек на фоточувствительной матрице при движении космического аппарата по орбите, оценка нелинейности движения траекторий и максимальной разности скоростей движения проекций звезд при заданной угловой скорости вращения спутника; исследование характеристик алгоритмов, определяющих координаты точечных источников света на фоточувствительной матрице для гауссовской формы сигнала и пуассоновском характере помех; создание программного обеспечения для моделирования алгоритмов и визуализации их работы; разработка и исследование эвристических методов селекции помех типа «светящаяся частица», позволяющих уменьшить асимптотическую сложность выполнения селекции звезд и «светящихся частиц» по сравнению с переборными алгоритмами, программная реализация методов и создание программного обеспечения для визуализации их работы. разработка и исследование статистических процедур для селекции звезд и помех типа «светящаяся частица» и их программная реализация.
Методы исследования. Поставленные задачи решаются с использованием статистического анализа, методов проверки многокритериальных гипотез, метода максимального правдоподобия, теории графов, численных методов, методов анализа вычислительной сложности алгоритмов и программного моделирования.
На защиту выносятся: 1. классификация методов распознавания групп звезд с оценкой их вычислительной сложности и устойчивости по отношению к наличию помех типа «светящаяся частица»; модель движения проекций светящихся частиц по плоскости фоточувствительной матрицы; метод селекции звезд, основанный на критерии постоянства скоростей проекций, и анализ его характеристик; метод селекции звезд, основанный на критерии постоянства взаимных угловых расстояний, и анализ его характеристик; результаты имитационного моделирования по определению координат центра проекции точечного источника света на фоточувствительной матрице методом максимального правдоподобия.
Достоверность научных результатов подтверждена теоретическими выводами, результатами программного моделирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе.
Научная новизна исследования состоит в следующем:
1. предложена классификация алгоритмов распознавания групп звезд, дана оценка их вычислительной сложности и устойчивости по отношению к на личию «ложных» звезд;
6. исследованы траектории движения проекций звезд на фоточувствительной матрице при вращении космического аппарата по орбите, произведена оценка нелинейности движения траекторий и максимальной разности ско ростей движения проекций звезд при заданной угловой скорости вращения спутника; получены характеристики алгоритма определения координат положения точечного источника света методом максимального правдоподобия для га-уссовской формы сигнала и пуассоновского характера помех, сделаны выводы об оптимальном отношении радиуса рассеяния проекции к размерам элементарного фотоприемника с точки зрения минимизации погрешности определения координат; разработаны эвристические алгоритмы предварительной селекции звезд, основанные на критериях отбора по постоянству взаимных угловых рас- стояний и постоянству скоростей проекций звезд, позволяющие с высокой вероятностью осуществлять селекцию помех типа «светящаяся частица» и требующие меньше времени выполнения по сравнению с переборными алгоритмами; 4. разработана последовательная (вальдовская) статистическая процедура для селекции звезд с заданной вероятностью ошибок пропуска и ложного обнаружения.
Практическая значимость работы заключается в разработке методов и программных средств, которые повышают вероятность правильного распознавания групп звезд при автономной ориентации космического аппарата. Реализованные программные средства обладают по сравнению с существующими большим быстродействием и требуют меньший объем памяти. Разработанные методы и программные средства учитывают особенности современной вычислительной техники, оптики и фоточувствительных датчиков. Для тестирования и анализа алгоритмов распознавания звезд созданы программные средства визуализации процесса распознавания.
Реализация результатов. Предложенные в работе методы и алгоритмы и созданные на их основе программные средства, использованы при разработке современных приборов звездной ориентации в ОАО «НПО «Геофизика-Космос», которые применяются в отечественных космических аппаратах специального назначения. Благодаря применению результатов диссертационного исследования уменьшено время и увеличена точность ориентации космического аппарата. Акт о внедрении и использовании результатов работы прилагается.
Результаты работы использованы в НИР, выполненной в рамках Аналитической ведомственной целевой программы Рособразования «Развитие научного потенциала высшей школы» (направление №2.2.2.3 «Развитие научной и академической мобильности в рамках международного сотрудничества») по теме № 8093 «Разработка и исследование алгоритмов для задачи астронавигации космических аппаратов» (рук. и отв. исп.: Кружилов И.С.).
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях: «Радиотехника, электроника и энергетика» (г. Москва, 2005 г., 2007 - 2009 гг.), «Радиолокация, навигация, связь» (г. Воронеж, 2009 г.), «Информационные средства и технологии» (г. Москва, 2005 г., 2008 г., 2009 г.), Digital Signal Processing and its Applications (г. Москва, 2010 г.). В рамках программ Германской академической службы обменов (DAAD) «Ostpartner-schaft» и «Michail Lomonosow II» были проведены две научные стажировки в Техническом Университете Ильменау (Германия). Результаты исследований, полученных во время стажировок, были доложены и обсуждены на семинарах в г. Бонне (ноябрь 2009 г.) и г. Москве (апрель 2010 г.).
Публикации. Основные результаты диссертационной работы опубликованы в 13 печатных работах, включая 4 работы в изданиях, рекомендуемых ВАК.
Диссертация содержит 117 листов машинописного текста и состоит из Введения, 4-х глав и Заключения. В конце работы приведен список использованных источников, содержащий 102 наименования. Работа содержит 4 Приложения.
Первая глава посвящена обзору существующих методов распознавания групп звезд. В процессе работы прибора звездной ориентации возникает необходимость в отождествление группы звезд из поля зрения прибора со звездами из базы данных прибора. В главе предложена классификация алгоритмов распознавания групп звезд и оценка их вычислительной сложности и устойчивости по отношению к наличию помех типа «светящаяся частица».
Во второй главе произведен анализ траекторий движения проекций звезд по плоскости фоточувствительной матрицы. Предложены эвристические алгоритмы селекции звезд, основанные на критериях постоянства взаимных угловых расстояний между звездами и постоянства скорости движения проекций. Для достижения требуемых характеристик распознавания ис- пользована последовательная процедура Вальда. Приведены характеристики алгоритмов.
Третья глава посвящена алгоритмам определения координат центра проекции точечного источника света на фоточувствительной матрице, как эффективному способу уменьшения порога распознаваемой скорости частиц. Рассматриваются алгоритмы определения координат центра проекции точечного источника света, требующие и не требующие априорных данных о энергетической плотности проекции и мощности помех, а также методы фильтрации изображений.
В четверной главе рассмотрены особенности вычислительного блока астронавигационного прибора, и связанных с ним особенностей при разработке программного обеспеченья. Приведены данные имитационного моделирования по точности оценки положения точечного источника света методом максимального правдоподобия. Произведено сравнение полученных результатов с точностью для метода «центр тяжести» и границей Рао-Крамера. Сделаны выводы об оптимальном отношении радиуса рассеянья проекции к размеру пикселя с точки зрения минимизации погрешности определения координат. Приведен список программного обеспеченья, разработанного в рамках диссертационной работы.
Апробация работы. Результаты работы были внедрены и использованы при разработке программного обеспеченья для астроприборов на ОАО «Научно Производственное Объединение «Геофизика-Космос». Полученные в диссертационной работе результаты позволили увеличить точность ориентации и вероятность правильного распознавания звезд, уменьшить время ра-боты алгоритмов. Акт о внедрении приведен в Приложении А.
За поддержку, оказанную при выполнении данного исследования хотелось бы поблагодарить моего научного руководителя О.Ю. Шамаеву и Ю.А. Горицкого, который познакомил меня с темой работы и под руководством которого в рамках выполнения выпускных бакалаврской и магистерской работ была проведена часть данного исследования. Кроме того, хочу поблагодарить моих коллег по предприятию «Геофизика-Космос», в творческом кругу которых была написана диссертационная работа.
По теме диссертации автором было опубликовано 13 работ, том числе 4 статьи, опубликованные в журналах, рекомендованных ВАК:
Кружилов И.С. О влиянии относительного размера изображения на погрешность определения координат // Компьютерная оптика. -2009. -Т. 32. № 3. -С. 210-215. - ISSN 0134-2452.
Кружилов И.С. Селекция звезд по скоростям в алгоритме астронавигации // Системы Управления и Информационные Технологии. —2009. -№ 3. -С. 55-58. -ISSN 1729-5068.
Кружилов И.С, Шамаева О.Ю. Алгоритм селекции звезд по постоянству угловых расстояний // Программные продукты и системы. -2009. -№ 3. -С. 82-84. -ISSN 0236-235Х.
Кружилов И.С. Селекция звезд в задаче астронавигации по признаку постоянства угловых расстояний // Вестник МЭИ. -2009. —№ 6. —С 199-205. -ISSN 1993-6982. Kruzhilov I. Estimation of stars coordinates for stars trackers II 12th International Conference and exhibition on DIGITAL SIGNAL PROCESSING AND ITS APPLICATIONS. Moscow. 2010. -P. 218. -ISBN 978-5-904602-07-9.
Кружилов И.С. Выбор размера проекции для алгоритмов определения координат точечных источников света // XV международная научно-техническая конференция РАДИОЛОКАЦИЯ, НАВИГАЦИЯ, СВЯЗЬ : в 3 т. -Воронеж: НПФ «САКВОЕЕ» ООО. 2009. -Т. 1. -С. 321-329. -ISBN 978-5-904259-01-3.
Кружилов И.С. Метод отбора звезд в алгоритме астронавигации // Математика, компьютер, образование. Сборник научных тезисов. Выпуск 14. -Ижевск: НИЦ «Регулярная и хаотическая динамика». 2007. -С. 72. -ISBN 5-93972-582-1.
Кружилов И.С. Особенности разработки алгоритмов фильтрации светящихся источников в астроприборах. Труды XVI международной научно- технической конференции «Информационные средства и технологии» : в 3 т. -М.: Издательский дом МЭИ. 2008. -Т. 3 -С. 50-57. -ISBN 978-5-383-00317-6.
9. Круэюилов К. С. Алгоритм распознавания звезд в задаче астронавигации // Труды международной научно-технической конференции «Информацион ные средства и технологии»: в 2 т. -М.: Янус-К. 2005. -Т. 2. -С. 28-30. — ISBN 5-8037-0287-0.
Кружилов К. С. Распознавание образов для алгоритма астронавигации // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА тринадцатая международная научно-техн. конф. студентов и аспирантов: Тезисы докладов: в 3 т. -М.: МЭИ, 2007 г. -Т. 1. С. 369-370. -ISBN 978-5-903072-97-2.
Круэюилов КС, Шамаева О.Ю. Выбор размера проекции для алгоритмов определения координат точечных источников света // Моделирование и анализ данных: Труды факультета информационных технологий МГППУ (Вып. 4). -М.: РУСАВИА. 2009 -С. 46-54 -ISBN 978-5-900078-63-2. Kruzhilov I. Evaluation of maximal error of star selection criterion for the problem of astronavigation II Mathematic, Computer, Education 15. Dubna. 2008. -P. 452. Kruzhilov I. S. Movement of stellar projection on plane of analysis in astronavigation problem. // 13-th Annual Conference of under-graduate and postgraduate students "RADIO-ELECTRONICS, ELECTRICAL and POWER EN-GINEERГNG,,. Moscow. 2008. -P. 289.
Сравнительный анализ вычислительной сложности алгоритмов распознавания групп звезд
Основными характеристиками алгоритмов распознавания звезд являются размер каталога, время вычисления базовых характеристик и суммарное время обращения к каталогу, а также общее время распознавания. В дальнейшем принимаются следующие обозначения: п — количество рабочих звезд в каталоге, /— количество звезд в поле зрения, b - количество звезд в распознаваемой группе (обычно 3 или 4). Рабочими звездами называются те звезды, данные об угловом положение которых заданы в бортовом каталоге. Обычно рабочими звездами являются все звезды ярче заданной величины, из которых исключаются переменные звезды, двойные звезды, звезды, взаимные угловые расстояния между которыми малы и т.д.
Для геометрических алгоритмов, работающих с тройками звезд, Ь=Ъ. Для алгоритма ориентированных треугольников Мазари, это, однако, будет не так, поскольку на втором этапе идентификации производится умножение матриц размером/х3.
Первые алгоритмы, хранившие информацию обо всех тройках звезд, имели размер базы данных 0(nf3). Для геометрических и сеточных алгоритмов, использующих для работы ближайшие звезды, размер каталога линейно пропорционален количеству рабочих звезд 0(п). Для графовых алгоритмов, где необходимо хранить информацию о взаимных угловых расстояниях, размер каталога вырастает до 0{n-f). Поскольку для анализа представляют интерес только те угловые расстояния, которые не превышают размеров поля зрения прибора, то целесообразно хранить в каталоге только их.
Для геометрических алгоритмов, где данные в каталоге упорядочены, время поиска заданной величины составляет 0(1п(и)). В худшем случае, если необходимо перебрать все звезды из поля зрения прибора, время, затраченное на поиск в каталоге составляет 0(f\n(n)).
Для сеточных алгоритмов необходимо произвести сравнение полученного изображения со всеми базовыми изображениями из каталога, поэтому время обработки данных пропорционально 0{п).
Для выборочной схемы Коломенкина время поиска в каталоге пропор-ционально 0(/ ), так как необходимо вычислять взаимные расстояния между всеми звездами. Для алгоритмов сопоставления групп на первом этапе требу-ется лишь 0(/) операций, но на вторичном этапе 0(/ ), если вычисляются все взаимные угловые расстояния. Необходимо отметить, что среди/ всех взаимных угловых расстояний только 2/— 3 являются независимыми величинами. Таким образом, количество обращений к каталогу может быть сокращено до 0(/), хотя в существующих модификациях алгоритма сопоставления групп такая эффективность так и не была достигнута.
Влияние асимптотической сложности алгоритмов на их выполнение на реальном процессоре не однозначно, поскольку это время существенно зависит от системы команд процессора и времени обращения к памяти. Кроме того, существенным фактором является качество написания программного обеспеченья (ПО). Такого рода ПО чаще всего пишется на языках низкого уровня (ассемблере), где важную роль играет умение программиста оптимально написать код. Так, алгоритмически более сложная, но простая в реализации методика, может выполняться быстрее, чем алгоритмически более быстрая, но требующая вызова большого количества подпрограмм, связанного с лишними операциями со стеком, сохранением регистров и т.д. Например, переборные алгоритмы для процессора частотой 100 мГц выполняются в среднем за время 0.6 - 1 с для каталога, содержащего около 2000 звезд.
Сравнительные характеристики алгоритмов идентификации групп звезд приведены в таблице 1.3.
Задача поиска группы звезд в каталоге усложняется тем, что среди обнаруженных светящихся точек могут оказаться не только рабочие звезды, именуемые далее ложными звездами. Это могут быть как звезды, не вошедшие в каталог, так и светящиеся (отраженным солнечным светом) космические крупнодисперсные частицы (далее помеха типа «светящаяся частица») в газово-пылевом облаке КА.
Отделить рабочие звезды от нерабочих (с таким же блеском) представляется возможным только на этапе поиска в бортовом каталоге. Ряд алгоритмов, например таких, как метод сопоставления групп и выборная схема Ко-ломенкина являются устойчивыми к наличию ложных звезд. Так, если в поле зрения прибора попадают ложные звезды, то в таблице соответствий для выборной схемы Коломенкина лишь появятся новые единичные элементы. «Голоса», поданные за истинные пары соответствий, не изменятся.
Сравнительная характеристика устойчивости алгоритмов по отношению к наличию ложных звезд приведена в таблице 1.4. За k обозначено количество «ложных» звезд.
В то же время, помехи типа «светящаяся частица» можно селектировать еще до этапа поиска в бортовом каталоге. Предварительная селекция светящихся частиц обладает следующими преимуществами: сокращает время работы алгоритма на этапе поиска в бортовом каталоге; уменьшает вероятность ложного распознавания.
Важно то, что на этапе предварительной селекции используются данные о динамическом изменении звезд от кадра к кадру и другие вспомогательные характеристики, в то время как для поиска в каталоге используются усредненные данные, и, таким образом, теряется часть полезной информации.
Метод селекции звезд на основе критерия постоянства взаимных угловых расстояний
Как будет показано в разделе 2.4 для анализа изменения взаимных угловых расстояний между светящимися объектами достаточно ограничиться лишь их линейной составляющей. Таким образом, выделение группы звезд среди / (порядка 30) светящихся точек сводится к анализу вещественной симметричной матрицы М взаимных относительных скоростей размерности
М Отбор 4 звезд для распознавания осуществляется на основании критерия максимального правдоподобия, путем перебора всех возможных сочетаний по 4 светящихся точки. Среди всех сочетаний выбирается то, которое с наибольшей вероятностью содержит все звезды. После этого с помощью критерия Неймана-Пирсона [5] с заданными вероятностями ошибок аир принимается решение о том, являются ли 4 выбранные точки звездами.
Количество всех сочетаний по 4 светящихся точки равно С4П поэтому асимптотическая сложность алгоритма распознавания составит 0(f). С учетом большого объема обрабатываемых данных и ограничений, накладываемых на время обработки и вычислительную мощность прибора, такая сложность алгоритма является неприемлемой. Для того, чтобы распознавание производилось за меньшее время алгоритм разделен на два этапа - предварительного и окончательного отбора.
На этапе предварительного отбора с помощью одного из эмпирических алгоритмов, имеющих сложность 0(f) или 0(fln(f)), выделяются 5-6 светя- щихся точек, таких, что среди них с большой вероятностью содержатся 4 звезды. Благодаря этому анализ матрицы размером fxf сводится к анализу матрицы 5x5, что уменьшает сложность алгоритма селекции. Наличие логарифма в асимптотической сложности алгоритма вызвано необходимостью сортировки строк матрицы. В общем случае, алгоритмы предварительного отбора разделяются на две категории — параметрические и не параметрические.
Параметрические алгоритмы используют информацию о параметрах движения частиц, при которых селекция должна производиться с заданной вероятностью, в то время как для непараметрических алгоритмов не требуется априорной информации о погрешностях определения взаимных угловых расстояний. К достоинствам параметрических алгоритмов стоит отнести высокую (по отношению к непараметрическим) надежность селекции при удачном подборе параметров, а к недостаткам, соответственно, ухудшение характеристик селекции при использовании параметров алгоритма, несогласованных с процедурой окончательного отбора. В последующих двух разделах приведены разработанные в рамках данного исследования алгоритмы каждого из типов — параметрический (с использованием вспомогательного порогового значения Д) и непараметрический (без дополнительных переменных).
Итак, пусть имеется/ светящихся точек, т - скорость изменения взаимных угловых расстояний между точками і nj. Будем предполагать, что если / и у являются звездами, то Шу распределено нормально с нулевым мате-матическим ожиданием mjj N(0,a). Если в паре есть хотя бы одна «не звез-да», то mij N(a, 7) при а О. Количество звезд N3, количество не звезд - NH3. Предполагается, что скорости частиц также распределены нормально:
Среди f светящихся точек требуется отобрать 5, среди которых будет по меньшей мере 4 звезды. Основная характеристика алгоритма Рл - вероятность ложного решения зависит от следующих параметров: распределения скоростей «не звезд», погрешности определения межзвездных угловых расстояний а, количества звезд и «не звезд» N3, NH3,
От алгоритма требуется отобрать 4 звезды и установить диапазон работоспособности. Идея приведенного в данном разделе алгоритма основана на следующем эмпирическом факте. Каждой светящейся точке соответствует ряд (строка матрицы) скоростей относительно других точек. Если каждую строку матрицы скоростей М упорядочить по возрастанию, звездам (если они существуют) будут соответствовать первые элементы отсортированного ряда. Угол обзора прибора и чувствительность матрицы гарантируют, что в любой части неба будет зафиксировано не менее 4-х звезд, поэтому первые четыре элемента упорядоченного ряда будут рассматриваться как «подозрительные на звездность». Для сокращения перебора, отбираются те ряды, у которых сумма абсолютных значений первых четырех элементов будет минимальна. Таким образом, задача сводится к анализу вспомогательной таблицы размером 5 строкх 5 столбцов.
Выбрав светящиеся точки, удовлетворяющие критериям, получим как минимум 5 и как максимум 25 (5 строк х 5 столбцов) точек, чем сократим перебор и сделаем его независимым от количества точек на экране. Чтобы еще сильнее сократить перебор, среди этих точек (если их, конечно не 4 и не 5) отбираются 6, которые наиболее часто встречаются в мультимножестве.
Из этой шестерки, путем полного перебора отбирается пятерка точек, имеющая минимальную сумму квадратов скоростей изменения межзвездных расстояний. Основные этапы алгоритма: 1. Для строк /=1..п матрицы скоростей изменения межзвездных расстояний М упорядочить по возрастания элементы каждой строки матрицы тц,...,тип и сформировать вектор перестановок J{ = /І,Ь ..., jl n содержащий номера элементов исходной матрицы.
Проблема определения координат точечного источника света и методы ее решения
Ошибка в определении координат светового источника зависит от характеристик фоточувствительной матрицы, параметров проецируемого изображения и от используемого алгоритма определения координат. На точность определения координат оказывают основное влияние следующие параметры проекции светового сигнала: мощность сигнала, функция распределения энергии сигнала, размер проекции изображения, время накопления сигнала, положение изображения относительно приемной структуры и интенсивность помех.
Методы определения координат ТИС разделяются на 2 класса - требующие априорной информации об анализируемых сигналах и шумах, и не требующие никакой информации о сигнале. К методам, не требующим знания предварительной информации о сигнале, относится метод «центр тяжести» (ЦТ) или центроиды [1], а также методы, использующие преобразование Фурье [20] или другие ортогональные преобразования.
Пусть Дх) принятый сигнал от ТИС, х — пространственная координата, a, Ь, с, d— границы прямоугольной области, тогда координаты центра проекции ТИС методом «центр тяжести» определяются как нормированный первый момент функции распределения:
Так как система состоит из дискретных элементов (пикселей), то интеграл в выражении (3.5) заменяется взвешенной суммой где /, j — все множество дискретных координат фотоприёмника, Ny — величина заряда каждого элементарного фотоприемника. Суммируются только заряды, превышающие заданный порог.
Метод «центр тяжести» хотя и обладает достаточно низкой точностью, является самым простым и быстрым методом оценки координат проекции ТИС. Благодаря этим свойствам алгоритм «центр тяжести» используется чаще всего в приборах звездной ориентации, где время и надежность алгоритма являются основными параметрами. Простота реализации важна для алгоритмов ориентации КА постольку, поскольку многие навигационные системы программируются на языках низкого уровня, что значительно усложняет их отладку.
Метод подгонки использует априорно заданную модель сигнала, в котором неизвестен ряд параметров. Чаще всего в исследованиях используется гауссовская модель сигнала с неизвестными параметрами а, с, х, а:
В работа [73] было предложено использовать для оценки параметров метод Левенберга-Марквардта (Levenberg-Marquardt algorithm).
В работе [93] было проведено моделирование с целью получить зависимость погрешности в определении положения точечного источника света от интенсивности шума. Для моделирования использовалась Гауссовская форма сигнала. Были сравнены 3 метода: метод подгонки, метод, основанный на преобразовании Фурье, и метод центра тяжести. Результаты моделирования представлены на рисунке 3.2. Анализ результатов моделирования показывает, что метод подгонки и метод, основанный на преобразование Фурье, обладают сходной точностью. Метод, основанный на преобразование Фурье, лишь немного уступает по точности методу подгонки. При этом метод Фурье не требует априорной информации о типе сигнала. К сожалению, автором статьи [93] не были указаны временные затраты алгоритмов.
Высокочастотная шумовая составляющая может быть частично удалена с помощью использования различных фильтров - как линейных, так и нелинейных.
Линейные фильтры популярны в использовании благодаря простоте своей реализации и удобству их теоретического анализа. Свойство линейности фильтра проявляется в том, что можно отдельно исследовать влияние фильтра как на полезную, так и на шумовую составляющую. Пусть L — линейный фильтр, А, В - дискретизированные изображения (целочисленные прямоугольные матрицы). Фильтр L преобразует изображение А и В в новое изображение Ли В, возможно, другой размерности:
Обзор и сравнение современных сигнальных процессоров
Тактовая частота и архитектура используемых процессоров накладывают существенные ограничения на разрабатываемые под них алгоритмы для систем реального времени. В этом разделе приведены основные характеристики современных ЦСП, как зарубежного, так и отечественного производства, которые используются, или могли бы использоваться для создания астро-приборов. В таблице Б.1 Приложения Б представлены основные характеристики указанных ЦСП. Вычислительная производительность рассматриваемых процессоров оценивалась для типовых арифметических и логических операций, применяемых при реализации функциональных алгоритмов звездных датчиков. К таким операциям можно отнести: - сложение (вычитание) 16-разрядных, 32-разрядных и 64-разрядных операндов; - умножение 32-разрядных и 64-разрядных операндов; - деление 32-разрядных и 64-разрядных операндов; - сдвиг 32-разрядных, 64-разрядных и 128-разрядных операндов; - поиск старшей единицы в 32-разрядных и 64-разрядных операндах. Все вышеуказанные операции являются одно/двух-операндовыми. Анализ потоковой обработки данных не представляется возможным без непосредственного программирования конкретных алгоритмов. Данных по тестированию на типовых алгоритмах (БПФ и др.), позволяющих осуществить равноправное сравнение сразу всех представленных процессоров, найдено не было. Сравнительные данные по вычислительной производительности исследуемых процессоров приведены в Таблице Б.2 Приложения Б. Исследуемые ЦСП имеют следующие особенности архитектуры и системы команд. Процессоры ТІ — возможность работы с 8- и 16-разрядными данными. FP-процессоры ТІ - возможность итеративного вычисления квадратного корня из FP-числа. Power-Efficient процессоры ТІ - возможность записи 2-х инструкций в одной команде.
Процессоры «Мультикор» — MIMD-архитектура вычислительной системы (отдельная программа для каждого ядра); наличие FPU-сопроцессоров у RISC-ядра; вычисление квадратного корня из чисел с плавающей точкой. Процессоры SHARC и TigerSHARC - аппаратная поддержка большого набора дополнительных функций: логарифм, модуль, преобразование типов, мин./макс и др. Приведенные в таблице Б.З Приложения Б параметры (напряжение, потребляемый ток и мощность) соответствуют максимальной тактовой частоте рассматриваемых процессоров. В рамках диссертационной работы впервые был промоделирован метод максимального правдоподобия для определения координат центра проекции ТИС. Программное обеспечение для моделирования было разработано в среде MATLAB 7.0. Для определения координат используются методы максимального правдоподобия и «центр тяжести». Оба алгоритма представляют собой два принципиально разных подхода к определению координат - алгоритм метода максимального правдоподобия (ММП) предполагает априорное знание о форме и мощности сигнала и помех [21], а ЦТ не требует никакой дополнительной информации.
Реализованная модель основана на предположении, что фоточувствительная матрица представляет собой совокупность прилегающих друг к другу пикселей без зазоров между ними. Геометрически плоскости матрицы соответствует область проекции изображения G (см. рисунок 4.1 ). Область G разбита на прилегающие друг к другу непересекающиеся подобласти gy прямоугольной формы, соответствующие пикселям матрицы. Модель построена, исходя из предположения, что количество квантов АЦП с каждого элементарного фотоприемника (J.J) есть случайная величина Ny. В [23] показано, что поведение этой величины может быть описано распределением Пуассона. То есть Ny Po(Ly-f). Где Ly - интенсивность светового потока, падающего на пиксель (i,j), значение которой определяется выражением: где L(x) = Ы(х) + 10 - двумерная пространственная функция распределения интенсивности падающего на фотоприемник светового потока, х = (х/, х2) — координаты на приемной матрице, 10 — интенсивность помех3 на единицу площади, а Ы(х) - плотность энергии светового потока от полезного сигнала равная подобласть g области G, соответствующая элементарному фотоприемнику. В выражении (4.1) функция f(x) определяет пространственный характер распределения мощности энергии сигнала на проекции, хО = (хО/ , хО ) координаты проекции ТИС. В модели предполагается, что мощность света, падающего на область G от источника Ы.яе зависит от положения ТИС.
