Алгоритм разбить множество объектов на определенное количество групп?

Question

Например, скажем, у меня есть двумерный массив пикселей (другими словами, изображение), и я хочу упорядочить их в группы, чтобы количество групп идеально складывалось в определенное количество (скажем, общее количество элементов). в другом двумерном массиве пикселей). В настоящий момент я пытаюсь использовать комбинацию соотношений и пикселей, но это не дает результата, кроме идеальных целочисленных соотношений (1: 2, 1: 3, 1: 4 и т. Д.). Когда происходит сбой, он просто масштабирует его до целого числа меньше его, поэтому, например, в масштабной пропорции 1: 2,93 будет использоваться масштаб 1: 2 с обрезанной частью изображения. Я бы предпочел не делать этого, так какие же алгоритмы я мог бы использовать, которые не попадают в Matrix Multipication? Я помню, что видел нечто похожее на то, что я описал вначале, но я не могу его найти. Это проблема NP-типа?

Например, скажем, у меня есть изображение размером 12 на 12 пикселей, и я хочу разделить его на ровно 64 части изображения размером n на м. Посредством анализа можно увидеть, что я могу разбить его на 8 подизображений 2 на 2 и 56 подизображений 2 на 1, чтобы получить это точное количество подизображений. Итак, другими словами, я бы получил 8 + 56 = 64 субизображения, используя все 4 (8) +56 (2) = 144 пикселя.

Точно так же, если бы у меня было изображение 13 на 13 пикселей, и я хотел бы получить 81 субизображение размером n на м, мне нужно было бы разбить его на 4 субизображения 2 на 2, 76 2 -by-1 подизображения и 1 1-на-1 подизображения, чтобы получить точное количество необходимых подизображений. Другими словами, 4 (4) +76 (2) + 1 = 169 и 4 + 76 + 1 = 81.

Еще один пример: если бы я хотел разделить одно и то же изображение 13 на 13 на 36 подизображений размером n на м, мне потребовалось бы 14 подизображений 4 на 2, 7 2 на 2 подизображения, 14 подизображений 2 на 1 и 1 подизображения 1 на 1. Другими словами, 8 (13) +4 (10) +2 (12) + 1 = 169 и 13 + 10 + 12 + 1 = 36.

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

Answer 1

Я понимаю, что вы хотите разделить прямоугольное изображение заданного размера на n прямоугольные подизображения. Допустим, у вас есть:

• изображение размером w * h
• и вы хотите разделить на n подизображения размером x * y

Я думаю, что вы хотите

R = { (x, y) | x in [1..w], y in [1..h], x * y == (w * h) / n }

Это набор пар (x, y) такой, что x * y равен (w * h) / n, где / - целочисленное деление. Кроме того, вы, вероятно, хотите взять прямоугольник x * y с наименьшим периметром, то есть наименьшее значение x + y.

Для трех примеров в вопросах:

• разделив 12 x 12 изображение на 64 подизображения, вы получите R = {(1,2),(2,1)}, и у вас будет 64 1 x 2 подизображения или 64 2 x 1 подизображения

• разделение 13 x 13 изображения на 81 подизображение, вы получите R = {(1,2),(2,1)}, и поэтому у вас есть либо 64 1 x 2 подизображения, либо 64 2 x 1 подизображения

• разделение 13 x 13 изображения на 36 подизображений, вы получите R = {(1,4),(2,2),(4,1)}, и вы можете использовать 36 2 x 2 подизображений (наименьший периметр)

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

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

Answer 2

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