Звёздные датчики

[mistermuscle]

К вопросу о важности использования устойчивых алгоритмов в звездных датчиках

Если одна из "двух самых ярких звезд" (или обе) окажется помехой, то отождествления не произойдет.

...

цитирую препринт ИКИ про БОКЗ

http://www.iki.rssi.ru/ofo/pdf/stand_prepr.pdf

из раздела 2.1

Бортовой звездный каталог прибора содержит 8500 звезд. В поле зрения прибора в среднем попадает около 60 звезд, из которых в бортовой каталог включена пятая часть. Звезды, не входящие в бортовой каталог прибора, представляют собой для прибора «помеховые» объекты.

Выводы. У БОКЗ помех в 4 раза больше, чем звезд в каталоге и это стандартная ситуация.

Еще из приведенны данных про число звезд можно оценить размер поля зрения того БОКЗ, про который говорится в препринте: площадь около 300 кв.град., т.е. размер 17х17 град. (Брал площадь небесной сферы равно 42000 кв.град.) Но это так, из интереса.

хмм, надо же а я никогда незная как делают звездные датчики придумал алгоритм лучше чем профессионалы!

Я предложил резать фильтром звезды по яркости - тогда у нас попадет в обьектив только X звезд входящих в ТОП-чарт звезд по яркости. И кол-во помех будет сверхнизким!

[ДмитрийК]

Я занимался поиском созвездий в изображениях, правда к звездам на небе они имели мало отношения

Вот например как один из вариантов, первое что приходит в голову:

В идеале изображение звезды на растре будет иметь вид функции точечного рассеяния (PSF - point spread function - как это по-рюсски?). Это позволяет найти координаты звезды с точностью до долей пиксела. В простейшем случае аппроксимируем получившееся пятно гауссианом и берем координаты пимпочки Лучше конечно померить и использовать реальную PSF - для этого есть куча методов.

Далее надо каким-то образом закодировать в базе информацию о взаимном расположении звезд, при этом в виде удобном для поиска и инвариантном к повороту/сдвигу. Напр. можно брать N звезд в некоем радиусе от "ключевой" звезды, обходить по часовой стрелке и считать скалярные произведения между ними (скалярное произведение удобно тем что оно инвариантно, кодирует и расстояния и углы и при этом его легко считать). Из полученного набора чисел путем хитрого квантования и комбинирования изготовляем хэш который потом используется для индексации данных в базе.
При поиске выбираем звезду ближе к центру, выбираем нужное кол-во звезд в заданном радиусе, считаем скалярные произведения, хеш и т.д. Если значение лежит близко к порогу квантования, придется проверять варианты с округлением как вверх так и вниз. Если звезд больше чем нужно то опять придется проверить несколько вариантов. После того как круг поиска сузился от >тысяч до <сотен, каждый вариант проверяется подстановкой в лоб. Если не нашли берем другую звезду и т.д.

Примерно так. Прошу строго не судить, это то что пришло в голову за 5 минут. Не исключено что подумав еще 5 минут я обнаружу что "а слона-то я и не приметил"

PS: С Новым Годом всех!

[Saul]

Интересно, а как в эту навигацию вписываются созвездия древних народов.

[Дмитрий Виницкий]

Никак.

[m939]

PSF - point spread function - как это по-рюсски?

ФРТ - функция рассеяния точки.

PS: Поздравляю всех с Новым Годом (предыдущий был годом астрономии).

[m939]

В идеале изображение звезды на растре будет иметь вид функции точечного рассеяния (PSF). Это позволяет найти координаты звезды с точностью до долей пиксела. В простейшем случае аппроксимируем получившееся пятно гауссианом и берем координаты пимпочки Лучше конечно померить и использовать реальную PSF - для этого есть куча методов.

Верно, но два замечания.

1). Чтобы найти координаты с точностью до малой доли пикселя, размер PSF (в пикселях) должен быть оптимальным. Если PSF<1 пикселя или (еще хуже) PSF1««пикселя, то сигнал от звезды обнаруживается только в одном пикселе - вот и вся точность координат, никаких долей.
[Требуются оговорки: В идеале крылья PSF тянутся бесконечно, но есть шумы, сам сигнал дискретен (кванты света), в результате получается так, как сказано выше.]

Эта ситуация (PSF<пикселя) называется "субпиксельным изображением" и она типична для широкоугольных звездных датчиков, если специально не расфокусировать изображение.

В противоположной ситуации - PSF»»пикселя - к сигналу звезды примешивается много шумов от многих пикселей, что тоже снижает точность.

Идеальный размер PSF для определения координат около 1.5 пикселей (точное значение немного зависит от точной формы PSF).

2). В современных звездных датчиках используются ПЗС или КМОП с так называемой "передней засветкой" (front illuminated). Они технологически проще и намного дешевле. В них электроды расположены с передней стороны матрицы, они сделаны полупрозрачными, свет через них проходит, но их пропускающая способность (=чувствительность) меняется в пределах пикселя вдвое или сильнее.  На таких приборах точно мерить координаты трудно.

[m939]

Далее надо каким-то образом закодировать в базе информацию о взаимном расположении звезд, при этом в виде удобном для поиска и инвариантном к повороту/сдвигу. Напр. можно брать N звезд в некоем радиусе от "ключевой" звезды, обходить по часовой стрелке и считать скалярные произведения между ними (скалярное произведение удобно тем что оно инвариантно, кодирует и расстояния и углы и при этом его легко считать). Из полученного набора чисел путем хитрого квантования и комбинирования изготовляем хэш который потом используется для индексации данных в базе.

Сможете ответить на эти вопросы: Можно ли построить хэш устойчивый к появлению звезд-помех? Как быть с погрешностью определения координат (и скалярных произведений и пр.)?

Если звезд больше чем нужно то опять придется проверить несколько вариантов.

Если как в БОКЗ в кадре будет 60 звезд из которых мы выбирает 10-15, то число комбинаций С(15,60) это ОЧЕНЬ много.

Далее надо каким-то образом закодировать в базе информацию о взаимном расположении звезд, при этом в виде удобном для поиска и инвариантном к повороту/сдвигу.

Инвариантным (к повороту/сдвигу) является, например, расстояние между 2-мя звездами. Это простейший инвариант. Для 3-х звезд (треугольника) инвариантами являются углы (например два меньших) или отношения наименьшей и средней сторон треугольника к наибольшей. То же можно сделать для 4-, 5-угольников и т.д. Но при N звездах в кадре расстояний будет N^2, треугольников N^3 ... Попадание помехи в такую фигуру создает неверный набор параметров, который может совпасть с реальным (каталожным) только в пределах погрешности измерений, т.е. случайно. А реальные фигуры будут совпадать систематически.

[Saul]

На разных континентах Земли есть древние пирамиды. Если на их грани положить "фазированные решетки" и обьеденить в информационную сеть, получится система наблюдения за небесной сферой.
 Фото подмосковной пирамиды, РЛС "Дон".

[m939]

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

А зачем пирамиды? Решетки можно ставить горизонтально. В этом случае их площадь может быть гораздо больше.

[ДмитрийК]

Можно ли построить хэш устойчивый к появлению звезд-помех?

Скорее всего нет. Придется повторить процесс для нескольких звезд пока мы не найдем совпадение. Каждое совпадение дополнительно проверяем по паре-тройке звезд не вошедших в хеш.

Как быть с погрешностью определения координат (и скалярных произведений и пр.)?

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

Если как в БОКЗ в кадре будет 60 звезд из которых мы выбирает 10-15, то число комбинаций С(15,60) это ОЧЕНЬ много.

А зачем их всех перебирать? Может я неясно выразился. При составлении базы для каждой звезды мы кодируем расположение (напр. в виде скалярных произведений) N _ближайших_ соседей (начиная с самого близкого и далее по часовой стрелке). Оптимальное N определяется экспериментально, но где-то между 3 и 10. При поиске просто берем звезду на выбор, находим N ближайших соседей, вычисляем хеш, ищем в базе.  Разумеется для поиска соседей совершенно необязательно перебирать все звезды в кадре, есть методы быстрее. Если нашли - проверяем/уточняем по другим звездам, если нет - пробуем другую звезду. Думаю можно позволить себе перепробовать несколько (до пары десятков) "центральных" звезд.

Инвариантным (к повороту/сдвигу) является, например, расстояние между 2-мя звездами. Это простейший инвариант.

Угу, всего лишь частный случай скалярного произведения, из которого еще зачем-то взят квадратный корень

Для 3-х звезд (треугольника) инвариантами являются углы (например два меньших) или отношения наименьшей и средней сторон треугольника к наибольшей.

Как-то сложно все это. Отношение сторон - их сперва посчитать надо а потом еще и поделить. Углы это вообще тригонометрия, загребешся считать То ли дело например тройка скалярных произведений (AB,AB), (AC,AC), (AB, AC) - инвариант не хуже других и считается на раз.

Но в общем я особо не настаиваю, вы все правильно пишете

[Monoceros]

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

[m939]

Если как в БОКЗ в кадре будет 60 звезд из которых мы выбирает 10-15, то число комбинаций С(15,60) это ОЧЕНЬ много.

А зачем их всех перебирать? Может я неясно выразился. При составлении базы для каждой звезды мы кодируем расположение (напр. в виде скалярных произведений) N _ближайших_ соседей (начиная с самого близкого и далее по часовой стрелке). Оптимальное N определяется экспериментально, но где-то между 3 и 10. При поиске просто берем звезду на выбор, находим N ближайших соседей, вычисляем хеш, ищем в базе.  Разумеется для поиска соседей совершенно необязательно перебирать все звезды в кадре, есть методы быстрее. Если нашли - проверяем/уточняем по другим звездам, если нет - пробуем другую звезду. Думаю можно позволить себе перепробовать несколько (до пары десятков) "центральных" звезд.

Правильно ли я понимаю? Сначала мы делаем хэши по каталогу: берем звезду, проводим вокруг нее окружность радиуса R, оставляет N ближайших соседей (N=3-10?) из окружности, считаем хэш, заносим в базу. Эта процедура повторяется много раз - для всех звезд каталога или только для некоторых?

Теперь работаем с кадром. Выбираем звезду примерно в центре. Проводим вокруг окружность того же радиуса R. Из звезд (и помех) внутри нее выбираем N, по ним считаем хэш и ищем его в БД. Если не нашли - берем другие N из этой же окружности и т.д. Если ни один хэш не совпал - берем другую  звезду и все повторяем.

Но, на примере того же БОКЗа, если в окружности R будет N каталожных звезд, то внутри такой же окружности в кадре не менее 4N.  Для N=3 C(3,12)=220, для N=10 C(10,40)~8.5 10^8. Слишком много сочетаний. Так ли это и что можно сделать?

[чайник17]

Сначала мы делаем хэши по каталогу: берем звезду, проводим вокруг нее окружность радиуса R, оставляет N ближайших соседей (N=3-10?) из окружности, считаем хэш, заносим в базу. Эта процедура повторяется много раз - для всех звезд каталога или только для некоторых?

Зачем Вам окружность радиуса R ? Просто берите N ближайших.

Хэш считается не по всем N+1 звёздам, а по C(2, N) треугольников. И треугольник добавляется в базу только если его там ещё нет. И так для всех звёзд (примерно, скажем звёзды на расстоянии 0.1 - 2 пиксела можно исключать, и добавить кучу похожих эвристик).

Теперь работаем с кадром. Выбираем звезду примерно в центре. Проводим вокруг окружность того же радиуса R. Из звезд (и помех) внутри нее выбираем N, по ним считаем хэш и ищем его в БД. Если не нашли - берем другие N из этой же окружности и т.д. Если ни один хэш не совпал - берем другую  звезду и все повторяем.

Опять же, не надо никакой окружности. Просто берёте, скажем, 4N ближайших звёзд.

Но, на примере того же БОКЗа, если в окружности R будет N каталожных звезд, то внутри такой же окружности в кадре не менее 4N.  Для N=3 C(3,12)=220, для N=10 C(10,40)~8.5 10^8. Слишком много сочетаний. Так ли это и что можно сделать?

Соответственно получается C(2,12) = 66 и C(2,40) = 780. Если исключать уже рассмотренные треугольники, общее число поисков в базе будет сильно меньше, чем 66*M и 780*M, где M - число просмотренных звёзд до нахождения соответствия. В среднем примерно 4 в Вашем примере.

[чайник17]

Инвариантным (к повороту/сдвигу) является, например, расстояние между 2-мя звездами. Это простейший инвариант. Для 3-х звезд (треугольника) инвариантами являются углы (например два меньших) или отношения наименьшей и средней сторон треугольника к наибольшей.

Зачем Вам инварианты относительно масштабирования? Масштаб (угловых секунд на пиксел) ведь не меняется? (Не учитывая мелкие погрешности.)

Именно к повороту и сдвигу инвариантны, например, три длины сторон.
(Длины сторон, правда, инвариантны ещё и к отражению, что плохо - отражение в звёздном датчике невозможно.)

[mistermuscle]

http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81%D0%B0%D0%BC%D1%8B%D1%85_%D1%8F%D1%80%D0%BA%D0%B8%D1%85_%D0%B7%D0%B2%D1%91%D0%B7%D0%B4    

[ДмитрийК]

Правильно ли я понимаю?

Наверное примерно где-то так. По крайней мере я бы с этого начал а дальше было б видно.

Общая идея простая: выбираем из имеющихся в кадре звезд некую конфигурацию, по ней вычисляем некую инвариантную метрику, используем ее в качестве ключа для поиска в базе, проверяем найденные варианты. Если совпадение не найдено, берем следующую конфигурацию итд.
При этом во избежание комбинаторного взрыва следует неким образом ограничить круг рассматриваемых конфигураций, причем желательно сделать это "конструктивно", т.е. сразу генерировать по кадру только подходящие конфигурации.
Все остальное - детали которые обычно проясняются по мере разработки.

Для N=3 C(3,12)=220, для N=10 C(10,40)~8.5 10^8. Слишком много сочетаний. Так ли это и что можно сделать?

Хрен его знает.  220 вроде как мало, 10^8 наверное много, истина где-то посередине. С этой блин комбинаторикой можно запросто влететь на +/- порядок В любом случае понятно что грубой силой перебирать на небе треугольники не прокатит, значит придется хитрить

[Saul]

Сейчас есть програмки для сшивания кадров (накладывающихся краями) в панорамный снимок. Отклацать сектор неба горизонтально-вертикальным сканированием, сшить в панораму. По самым ярким звёздам, известным созвездиям, привязаться!

[m939]

http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81%D0%B0%D0%BC%D1%8B%D1%85_%D1%8F%D1%80%D0%BA%D0%B8%D1%85_%D0%B7%D0%B2%D1%91%D0%B7%D0%B4    

25 - мало.

Большинство датчиков с запасом укладываются в Bright Star Catalog: 1908 год, 9110 звезд до 6.5 величины в полосе V (visual - зеленый). Описание здесь http://adc.gsfc.nasa.gov/adc-cgi/cat.pl?/catalogs/5/5050/, а сам каталог вот ftp://adc.astro.umd.edu/pub/adc/archives/catalogs/5/5050/catalog.dat.gz.

Правда большинство ЗД работает не в V, а в красном или инфракрасном диапазоне - там величины звезд несколько другие и список будет отличаться.

[mistermuscle]

http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81%D0%B0%D0%BC%D1%8B%D1%85_%D1%8F%D1%80%D0%BA%D0%B8%D1%85_%D0%B7%D0%B2%D1%91%D0%B7%D0%B4    

25 - мало.

Большинство датчиков с запасом укладываются в Bright Star Catalog: 1908 год, 9110 звезд до 6.5 величины в полосе V (visual - зеленый). Описание здесь http://adc.gsfc.nasa.gov/adc-cgi/cat.pl?/catalogs/5/5050/, а сам каталог вот ftp://adc.astro.umd.edu/pub/adc/archives/catalogs/5/5050/catalog.dat.gz.

Правда большинство ЗД работает не в V, а в красном или инфракрасном диапазоне - там величины звезд несколько другие и
список будет отличаться.

Проблема чтоб ПЗС видел эти звезды до 6,5зв величины!
Мне кажется разумным иметь общую базу в 100-150звезд, не более!
И их вполне можно перебрать и грубой силой!

Почему ЗД работают в красном и в ИК?

А если сделать такой ЗД (механический)
стоит ПЗС прикрытый фильтром так чтоб обнаруживать только одну самую яркую звезду - Сириус, а остальные были ниже порога чувствительности. Головка вращает башкой так чтоб всю сферу оглядеть и найти Сириус и по нему определиться!
Ну чтоб угол найти можно 2е звезды отыскать - еще и Канопус

[m939]

... надо каким-то образом закодировать в базе информацию о взаимном расположении звезд в удобном для поиска и инвариантном к повороту/сдвигу виде. ...  Из полученного набора чисел изготовляем хэш который потом используется для индексации данных в базе.

PS: С Новым Годом всех!

Спасибо! Идея с такой хэш-таблицей интересна. Есть над чем подумать.