Алгоритм

Основные сущности

Кадр (frame) - картинка, полученная с системы сбора данных (либо из гигабитного канала при реалтайм-обработке, либо с диска или по сети при обработке постфактум).

Средний кадр (average frame) - некоторая производная определенного количества кадров, функцией которой является получение ответа на вопрос, отскакивает ли заданный пиксел за заданное число сигм от своего среднего значения.

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

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

Объект - некоторое эфемерное образование, получаемое из сравнения листов записей с различных кадров. Может соответствовать реально пролетающему по небу спутнику или метеору, вспыхнувшему транзиенту и так далее, а может и ничему не соответствовать.

Алерт - писк, который издает компьютер, когда объект начинает удовлетворять некоторым критериям.

Собственно алгоритм

Собственно алгоритм начинается с момента проведения предварительной обработки текущего кадра и берет на вход лист записей. Основной задачей алгоритма является корректировка на его основе текущего листа объектов и выдача алертов.

Запись содержит следующую информацию - время, координаты центра, размер, интенсивность.

Объект в свою очередь состоит из листа записей (проявления объекта на различных кадрах) и некоторого описателя статуса. В этот статус, в частности, входит информация о времени (или числе кадров), прошедшем с момента первого появления объекта в поле.

Алгоритм состоит из следующих функциональных частей (не обязательно соответствующих программным кускам - там будут существенно сказываться соображения оптимизации).

1. Цикл по всем объектам из листа объектов. Для каждого объекта на основании его листа записей предвычисляется ожидаемая область его проявления на текущем кадре. Если данному объекту соответствует лишь одна запись, ожидаемая область выбирается из соображения необходимости поймать быстролетящий спутник, которым этот объект может оказаться, если же этих записей много (мы видим объект на протяжении уже нескольких кадров), то эта область определяется путем завязывания траектории с вычислением соответствующих ошибок положения.

Далее отбираются все записи текущего кадра, попадающие в эту область. Если запись одна, она добавляется в лист записей объекта, если же их несколько - имеет место быть «вилка» - форк (fork). Данный объект разделяется на несколько имеющих одинаковую предысторию и отличающихся лишь последней записью. Один из этих новообразованных объектов в дальнейшем выживет, остальные (ложные) умрут.

2. Цикл по всем объектам из листа объектов, в котором проверяется статус данного объекта на соответствие его критериям алерта. Такими критериями является существование объекта на протяжении некоторого числа кадров и его неподвижность. Критерием неподвижности может служить, к примеру, попадание в текущую ожидаемую область объекта самой первой его записи. Кроме того, имеет смысл проверить здесь данное событие на соответствие его известным спутникам (по посчитанным заранее их эфемеридам).

3. Цикл по всем объектам из листа объектов, в котором проверяется статус данного объекта на предмет его «смерти». «Смерти» объекта соответствует его вылет за пределы кадра (если мы имеем на данный объект завязанную траекторию), ненаблюдаемость его в течение некоторого заданного числа кадров и так далее. «Умершие» объекты могут сбрасываться в некоторый лог или в несколько логов в зависимости от их типа (подвижен/неподвижен, виден на одном кадре/на нескольких кадрах, и так далее) для проведения некоторой дополнительной их обработки в дальнейшем.

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

Что сделано

На данный момент существует работающая реализация данного алгоритма с упрощенной схемой формирования алертов (только проверка на движение и на существование объекта на заданном числе кадров). Существует модельный вариант процедуры предварительной обработки, который выделяет на кадре связные области, отскакивающие на заданное число сигм, и фильтрует их по размеру (отбрасываются все области размером в один пиксел). В таком варианте уверенно ловятся и ведутся спутники на тестовых последовательностях, в том числе и спутник, давший приснопамятную вспышку звезды на две величины (ведется на протяжении некоторого количества кадров до и после вспышки - то есть такие события считаются спутником, а не транзиентом).

Демо

Работа предварительной версии алгоритма продемонстрирована на следующих видеофрагментах.

Поле со спутниками
Поле со спутниками
Разностные кадры
Выделение объектов
Каждый объект подписывается его "длиной". Срывы алгоритма выделения объектов на последнем видеофрагменте связаны с неравномерностью процесса получения кадров.

«Вспыхивающая звезда»
Вспыхивающая звезда
Выделение объектов

Официальное уведомление. Как автор алгоритма и его программной реализации запрещаю использование данных видеофрагментов без моего ведома.