Алгоритм разделения изображения на меньшие изображения, уменьшающий количество пробелов и определяющий максимальное количество прямоугольников

Question

Я ищу алгоритм, который может разбить изображение на более мелкие изображения с некоторыми ограничениями.Одним из ограничений является использование наименьшего количества «пробелов», означающих пустые пиксели.А другой - указать максимальное количество изображений, чтобы разделить его.

Например, давайте посмотрим на изображение ниже.В нем много «пробелов».Я хотел бы разделить эти изображения на несколько других изображений, чтобы я мог уменьшить объем памяти, занимаемый этим изображением, а также уменьшить количество «рисования», которое займет это изображение.

.=transparent pixel
x=colored pixel

....................
.xxxxxxxxxxx........
...xxxx...xxxxxx....
.............xxxxx..
...............xxx..
...............xxx..
....................
..xxxxxx............
.....xxxxxxxxxxx....
.........xxxxxxxxxx.
....................

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

....................
.111111111111111....
.111111111111111....
.............22222..
.............22222.
.............22222..
....................
..3333333...........
..33333334444444444.
.........4444444444.
....................

Есть ли у кого-нибудь алгоритм для этого или знает название алгоритма, который это делает?Я искал некоторое время и нашел несколько связанных алгоритмов, но алгоритмы, которые я нашел, не учитывают пробелы, например, они разбивают изображение на прямоугольники, покрывающие только непрозрачные пиксели, что приводит к огромному количеству прямоугольников.Реальные данные, с которыми я работаю, представляют собой изображения размером 1024 * 1024 пикселей, и я бы предпочел уменьшить их до максимум 16 частей.хитрость заключается в том, чтобы извлечь 16 изображений, используя наименьшее количество пробелов.

Answer 1

Я бы пошел с тем же алгоритмом, что и ravloony , но с небольшим и важным изменением, используя операцию «обрезать», которая ищет минимальные / максимальные столбцы и строки, которые не являются полностью пустыми и отбрасывать остальное.

На практике операция кадрирования получит область X*Y в качестве входных данных и выведет 4 целых числа - координаты наименьшего прямоугольника, который содержит все используемые пиксели области. Это также может быть использовано для обнаружения и удаления пустых областей.

Пример

....................
.xxxxxxxxxxx........     xxxxxxxxxxx.......
...xxxx...xxxxxx....     ..xxxx...xxxxxx...
.............xxxxx..     ............xxxxx.
...............xxx.. =>  ..............xxx. (first crop)
...............xxx..     ..............xxx.
....................     ..................
..xxxxxx............     .xxxxxx...........
.....xxxxxxxxxxx....     ....xxxxxxxxxxx...
.........xxxxxxxxxx.     ........xxxxxxxxxx
....................

Теперь разделите изображение на NxN частей (здесь используется N = 4) и используйте операцию кадрирования на каждой из частей:

xxxxx|xxxxx|x....|
..xxx|x...x|xxxxx|
---------------------
     |     |  xxx|xx
     |     |  ..x|xx
---------------------
     |     |    x|xx
     |     |     |
---------------------
 xxxx|xx...|     |
 ...x|xxxxx|xxxxx|
     |...xx|xxxxx|xxx

Для этого примера мы получаем 10 + 10 + 10 + 6 + 4 + 1 + 2 + 8 + 15 + 10 + 3 = 79 пикселей вместо 21 * 11 = 231, что составляет всего 34,2%. Обратите внимание, что это та же сумма, что и при ручной 4-сегментной сегментации (30 + 15 + 14 + 20 = 79)!

Выводы

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

О дополнительных данных: изображения размером 1024x1024 и разбиение на части 4x4 дадут вам возможность использовать 4-байтовые значения для хранения каждого прямоугольника, поэтому дополнительный размер данных будет только 16 * 4 = 64 байта - относительно этого вы возможно, стоит подумать об увеличении вашего максимума в 16 частей, если только он не замедлит какую-то другую часть, например рисунок.

Худшие случаи

Наихудшими случаями для этого алгоритма будут части с некоторыми пикселями на или около заданных краев, например:

x......x    xxxxxxxx    xx......
........    ........    x.......
........    ........    ........
x......x    ...x....    .......x

Мне приходит в голову несколько решений для них:

• Разделение региона снова (в конечном итоге с реализацией quadtree)
• Использование дополнительного шага для обнаружения полностью пустые прямоугольники в внутри.
• Перевод сетки, которая немного определяет части

Answer 2

Извините за поздний комментарий, но мне понадобилось некоторое время, чтобы найти "хороший" алгоритм.

После некоторых исследований я собираюсь найти следующее решение. Сначала я использую Quadtree и делаю SplitAndMerge. Я сначала разделился на «Пробел». Затем я объединяю все прямоугольники в прямоугольники с наибольшей площадью.

После этого я сортирую квадродерево по размеру области, сохраняя только самые большие х области. (Так важно сохранить самые большие пробельные площади). Но я не хочу пробелов, я хочу все, кроме пробелов, поэтому я инвертирую Quadtree и снова делаю SplitAndMerge. Затем извлеките оставшиеся прямоугольники из изображения и упакуйте их в окончательное изображение.

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

Answer 3

Моя интуиция говорит, что идеальное решение сродни проблеме рюкзака и, таким образом, неосуществимо в вычислительном отношении.Вы можете использовать какую-то эвристику для генерации «достаточно хорошего» решения.

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

Answer 4

Я бы посмотрел, как делать это рекурсивно, каждый раз, разбивая пополам или на четыре, пока не достигнете желаемого уровня (для вас 2 -> 4 ^ 2 = 16).На нижнем уровне проверьте наличие пустых квадратов и выбросьте их.Конечно, это дает вам сетку прямоугольников, пропорциональную форме исходного изображения, а не оптимально расположенные прямоугольники, но это может привести вас к правильному следу.

Answer 5

Вы хотите написать алгоритм длины цикла или дельта-сжатия.Или вы хотите использовать кривую пространственного заполнения или пространственный индекс.SFC рекурсивно подразделяет поверхность на более мелкие 4 плитки и уменьшает сложность 2 измерения до 1 измерения, таким образом, это облегчает идентификацию пустого пространства.Вы хотите найти блог пространственного индекса квадра дерева Гильберта-кривой Ника.Вы хотите загрузить мою кривую Гильберта класса php на phpclasses.org.