@13_nastya_13

Как отсортировать словарь?

Я не знаю как по другому задать вопрос, поэтому прошу не судить строго... Мне нужно было найти порядок наложения друг на друга прямоугольников(пустых в середине). В начале я сделала функцию которая проверяла каждый пиксель, и если он был не черным, записывала его в словарь(цвета в формате RGB (255,0,0)) и запоминала координаты их углов как значение, то есть xmin xmax ymin ymax. Далее чтобы найти пересечение я сделала функцию, которая проверяет каждую сторону прямоугольников и если встречает другой цвет записывает в словарь(цвет текущего прямоугольника: другой цвет)
Получился такой словарь: {(0, 255, 255): (255, 255, 0), (255, 255, 0): (255, 0, 255), (0, 0, 255): (0, 255, 255), (255, 0, 0): (255, 255, 0), (0, 255, 0): (0, 0, 255), (255, 0, 255): ''}
Из этого словаря следует что (255, 255, 0) наложен на (0,255,255), цвет (255,0,255) наложен на (255, 255,0) и так далее, в конечном итоге их порядок равен: (255,0,0), (0,255,0), (0,0,255), (0,255,255), (255,255,0), (255,0,255)
Еще есть вариант записать в словарь в значения списки со цветами, которые находятся на каждом прямоугольнике, получается вот это: {(0, 255, 255): [(255, 255, 0)], (255, 255, 0): [(255, 0, 255), (255, 0, 255)], (0, 0, 255): [(0, 255, 255)], (255, 0, 0): [(255, 255, 0), (255, 255, 0), (0, 255, 0), (0, 255, 0)], (0, 255, 0): [(0, 0, 255), (0, 0, 255)], (255, 0, 255): ''}

Может кто-то сможет мне помочь, или у кого-то будут какие-то идеи как это можно сделать, я себе уже голову сломала, пробовав различные способы.
5fc2a4fbb4bbd344880635.png
  • Вопрос задан
  • 212 просмотров
Решения вопроса 1
adugin
@adugin Куратор тега Python
Чтобы не тратить время на борьбу с устойчивостью сортировки (cmp и cmp_to_key, либо вручную типа BubbleSort), сделал тупой подбор последовательности брутфорсом. Напишите нормальную сортировку, если требуется.
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
)

5fc38ee645101574639798.png
5fc38efccaac4295087739.png
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@OlegPyatakov
pyatakov.com
Тот словарь, который получился изначально, кажется, не очень подходит под задачу.
Можно сделать список пересечений цветов и дальше итеративно отфильтровывать этот список, находя цвета, над которыми нет пересечений.

# Массив туплов формата (нижний цвет, верхний цвет)
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)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы