import numpy as np
import matplotlib.pyplot as plt
from collections import deque
from PIL import Image

def find_galaxies(img):
    """
    Анализирует изображение и находит на нем галактики (светлые пятна).
    Использует алгоритм поиска в ширину (BFS) для выделения связных областей пикселей.
    
    :param img: 2D numpy массив (изображение в оттенках серого)
    :return: Список кортежей (x_центра, y_центра, размер_объекта)
    """
    
    # 1. Пороговая фильтрация (Thresholding)
    # Создаем бинарную маску: все пиксели ярче 35 считаем частью объектов, остальные - фоном.
    # Значение 35 подобрано эмпирически для отсечения темного космоса.
    mask = img > 35 

    # Получаем индексы (координаты) всех светлых пикселей
    y_idx, x_idx = np.where(mask)
    
    # Преобразуем координаты в множество (set) кортежей для быстрого поиска за O(1)
    active_pixels = set(zip(y_idx, x_idx))
    
    # Множество для отслеживания уже обработанных пикселей
    visited = set()
    
    # Список для хранения найденных галактик
    galaxies = []
    
    # Возможные смещения для 8-связности (поиск соседей по горизонтали, вертикали и диагоналям)
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    # 2. Поиск связных компонент (кластеризация пикселей)
    for start in active_pixels:
        if start in visited:
            continue # Если пиксель уже отнесен к какой-то галактике, пропускаем

        # Инициализируем очередь для алгоритма поиска в ширину (BFS)
        queue = deque([start])
        visited.add(start)

        # Списки для хранения координат всех пикселей текущего найденного объекта
        group_y = [start[0]]
        group_x = [start[1]]

        # Пока есть соседние светлые пиксели, "растим" область
        while queue:
            cy_px, cx_px = queue.popleft()

            # Проверяем всех 8 соседей текущего пикселя
            for dy, dx in directions:
                ny, nx = cy_px + dy, cx_px + dx
                
                # Если сосед тоже светлый и мы его еще не посещали
                if (ny, nx) in active_pixels and (ny, nx) not in visited:
                    visited.add((ny, nx))
                    queue.append((ny, nx))
                    group_y.append(ny)
                    group_x.append(nx)

        # 3. Фильтрация найденных объектов (убираем шум)
        
        # Галактика должна состоять как минимум из 5 пикселей (отсеиваем мелкий шум и одиночные звезды)
        if len(group_x) >= 5:
            # Вычисляем габариты объекта (высоту и ширину ограничивающего прямоугольника)
            h_obj = max(group_y) - min(group_y) + 1
            w_obj = max(group_x) - min(group_x) + 1
            
            # Вычисляем соотношение сторон (защита от деления на ноль с помощью max(..., 1))
            aspect_ratio = max(w_obj, h_obj) / max(min(w_obj, h_obj), 1)

            # Оставляем объекты, которые не являются слишком узкими линиями
            # Если aspect_ratio >= 8, это скорее всего трек от спутника, метеор или битый пиксель матрицы
            if aspect_ratio < 8:
                # Вычисляем центр масс объекта (среднее арифметическое координат)
                mean_x = sum(group_x) / len(group_x)
                mean_y = sum(group_y) / len(group_y)
                
                # Сохраняем координаты центра и максимальный размер (для отрисовки кружка)
                galaxies.append((mean_x, mean_y, max(h_obj, w_obj)))

    return galaxies

def open_gray(path):
    """
    Открывает изображение по указанному пути и переводит его в градации серого.
    """
    # Конвертация 'L' переводит изображение в 8-битный черно-белый формат (0-255)
    pil_img = Image.open(path).convert('L')
    return np.array(pil_img)


image_path = 'galaxy.png'

# 1. Загрузка изображения
img_gray = open_gray(image_path)

# 2. Поиск объектов
found_objects = find_galaxies(img_gray)
print(f"Найдено объектов: {len(found_objects)}")

# 3. Визуализация результатов
# Создаем полотно для рисования размером 12х10 дюймов
fig, ax = plt.subplots(figsize=(12, 10))

# Показываем оригинальное изображение в цвете (RGB) как фон
ax.imshow(Image.open(image_path).convert('RGB'))

# Отрисовываем маркеры (круги) вокруг каждой найденной галактики
for x, y, size in found_objects:
    # Формула радиуса: size/1.5 + 5. Немного увеличиваем кружок, чтобы он не перекрывал саму галактику.
    # color='lime' (светло-зеленый), fill=False (прозрачный внутри)
    circle = plt.Circle((x, y), size/1.5 + 5, color='lime', fill=False, linewidth=1.5, alpha=0.7)
    ax.add_patch(circle)

# Настройка внешнего вида графика
ax.set_title(f"Результат поиска: обнаружено {len(found_objects)} галактик", fontsize=15)
ax.axis('off') # Отключаем оси координат с цифрами, так как это просто картинка

# Убираем лишние белые поля вокруг изображения
plt.tight_layout()

# Выводим результат на экран
plt.show()