import cv2 # pip install opencv-python
import numpy as np # pip install numpy
import random
from collections import Counter, defaultdict
from functools import cmp_to_key
from itertools import combinations, permutations
from skimage.util import view_as_windows # pip install scikit-image
from PIL import Image # pip install pillow
h = w = 3 # будем использовать rolling window 3x3 (подобие свёртки)
n_channels = 3 # цветовые каналы изображения
n_samples = -1 # константа для более наглядного использования в .reshape()
active_pixels_in_3x3_cross = 5 # 5 из 9 пикселей образую крест ('+')
# Читаем картинку из файла
image = cv2.imread('5fc2a4fbb4bbd344880635.png', cv2.IMREAD_COLOR)
# Разбиваем изображение на блоки H x W @ CHANNELS и удаляем углы, чтобы получился крест из 5 пикселей
# Вместо view_as_windows() можно использовать np.lib.stride_tricks.as_strided(), но там очень сложно:
# tiles = np.lib.stride_tricks.as_strided(image, shape=(498, 498, 3, 3, 3), strides=(1500, 3, 1500, 3, 1))
tiles = view_as_windows(image, (h, w, n_channels)) # shape = (498, 498, 1, 3, 3, 3)
tiles = tiles.reshape(n_samples, h * w, n_channels) # shape = (248004, 9, 3)
tiles = tiles[:, (1, 3, 4, 5, 7), :] # shape = (248004, 5, 3)
# Нас интересуют только пересечения линий (полные кресты, где все 5 пикселей не чёрные)
mask = tiles.any(axis=-1).sum(axis=-1) == active_pixels_in_3x3_cross
crossovers = tiles[mask] # shape = (12, 5, 3)
# Собираем статистику
stats = defaultdict(Counter)
# Перебираем все пересечения цветных линий
for crossover in crossovers:
# Подсчитываем количество пикселей разных цветов, в сумме 5
counter = Counter(map(tuple, crossover))
# Добавляем в статистику
stats[frozenset(counter)] += counter
# Все встречающиеся цвета
all_colors = list({color for colors in stats for color in colors})
# Специально перемешаем, чтобы проверить устойчивость сортировки
random.shuffle(all_colors)
# Функция сравнения двух цветов
def cmp(color1, color2):
colors = frozenset({color1, color2})
if colors in stats: # явное лучше, чем неявное
num_pixels_of_color1 = stats[colors][color1]
num_pixels_of_color2 = stats[colors][color2]
return num_pixels_of_color1 - num_pixels_of_color2
else: # пара цветов не пересекается явным образом
return 0 # это может быть проблемой при сортировке
# Плохой алгоритм сортировки брутфорсом, но работает устойчиво
def sorted_colors():
for colors in permutations(all_colors, len(all_colors)):
for color1, color2 in combinations(colors, 2):
if cmp(color1, color2) > 0:
break
else: # обратите внимание на конструкцию for..else
return colors
# z_index = cmp_to_key(cmp)
# Рисуем отсортированную плашку цветов
Image.fromarray(
np.hstack(
# [np.full((64, 64, n_channels), color, np.uint8) for color in sorted(all_colors, key=z_index)]
[np.full((64, 64, n_channels), color, np.uint8) for color in sorted_colors()]
)[..., ::-1] # BGR -> RGB
)
# Массив туплов формата (нижний цвет, верхний цвет)
crossovers = [('red', 'blue'), ('red', 'green'), ('green', 'blue'), ('green', 'yellow')]
colors_to_sort =[]
for crossover in crossovers:
colors_to_sort.append(crossover[0])
colors_to_sort.append(crossover[1])
colors_to_sort = list(set(colors_to_sort))
colors_top_bottom = []
def is_top_color(color, crossovers):
if not list(filter(lambda x: x[0] == color ,crossovers)):
return True
else:
return False
while len(colors_to_sort) > 0:
found_top_color = False
for color in colors_to_sort[:]:
if is_top_color(color, crossovers):
found_top_color = True
colors_top_bottom.append(color)
colors_to_sort.remove(color)
crossovers = list(filter(lambda x: x[1] != color, crossovers))
if not found_top_color:
print('Невозможное наложение прямоугольников')
break
print(colors_top_bottom)