Как подсчитать количество звезд на ночном небе?

Question

[imlynn]

У меня есть фото ночного неба:



Программа оставляет на фото только те области, которые соответствуют определенному порогу, и так мы сможем определить все звезды на фото.
Пусть следующее изображение является примером работы этой программы и оно удовлетворяет всем нашим требованиям (на самом деле нет, но не в этом суть):



Теперь нам надо определить, сколько же звезд есть на этом фото и их размер, при этом игнорируя различные помехи.
Изображение закодировано в один долгий однострочный массив, где белые области отвечают "1", а черные - "0" (с ним мы и должны работать), но есть также функция, которая возвращает значение цвета определенного пикселя из него (пусть это будет выглядеть так: pick(x,y) == 0 или 1).

Размер звезды - диаметр наложенного не нее круга. Т.е. для звезды с одной точкою размер равен 1, если это квадрат 2на2 - то 2, если это крест 3на3 - то 3 и так далее.

На фото есть звезды, которые на изображении показаны прямой линией. Да, это не координаты круга, но если линия меньше 3 пикселей в длину, то это допускается. (пример ниже)

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

Все помеченные участки - звезды.

Есть небольшие помехи, но они не играют важной роли. Можно зачислить к звездам.

Есть серьезные помехи. Хотя за логикой описанного, несколько областей все-таки попадут под определение звезды. Но это не столь важно.


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

Ести ли какой-нибудь способ сделать это красиво?

Замечание

Я не требую от программы 100% точности, и даже гарантирую, что буду кормить ее изображениями с минимальными помехами, а то, что показано выше - только пример.

Answer 1

[Alexej Simakov]

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

Я бы построил график который для каждой смежной закрашеной области показывал бы ее величину, например количество точек входящих в смежную область. Для данного изображения получится сначала медленно поднимающаяся (много маленьких точек разного размера) и потом резко уходящая вверх кривая (большая область. Так можно будет выявить диапазон допустимых значений для размера звезды, на этом расстоянии. Т.е правую часть графика вы отсечете. Все остальное будут "наверное звезды".

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

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

Comments

[imlynn]

Немного улучшил схему постройки изображения с порогом и сделал как Вы сказали. На выходе одержал вот такую картину:

Размер	Количество
1	2659
2	850
3	552
4	154
5	64
6	22
7	10
8	3
9	10
10	1
11	4
12	1
13	1
14	3
15	1
16	1
34	1

Что же, я нашел то, что искал, спасибо.

Answer 2

[Roman Mindlin]

Попробуйте какой нибудь алгоритм кластеризации объектов. Сколько кластеров получится - примерно столько звезд. Объектами должны быть пиксели с яркостью выше какого то порога.