Авторы благодарности Calvin's Hobbies за продвижение моей идеи в правильном направлении.
Рассмотрим набор точек на плоскости, которые мы будем называть сайтами , и сопоставьте цвет каждому сайту. Теперь вы можете раскрасить всю плоскость, окрасив каждую точку цветом ближайшего участка. Это называется картой Вороного (или диаграммой Вороного ). В принципе, карты Вороного могут быть определены для любой метрики расстояния, но мы просто будем использовать обычное евклидово расстояние r = √(x² + y²)
. ( Примечание. Вам не обязательно знать, как рассчитать и отобразить один из них, чтобы участвовать в этом соревновании.)
Вот пример с 100 сайтами:
Если вы посмотрите на любую ячейку, то все точки в этой ячейке будут ближе к соответствующему сайту, чем к любому другому сайту.
Ваша задача - аппроксимировать данное изображение такой картой Вороного. Вам дают изображение в любом удобном формате растровой графики, а также целое число N . Затем вы должны создать до N сайтов и цвет для каждого сайта, чтобы карта Вороного, основанная на этих сайтах, максимально приближалась к исходному изображению.
Вы можете использовать Фрагмент стека в нижней части этого задания, чтобы визуализировать карту Вороного из вашего вывода, или вы можете сделать это самостоятельно, если хотите.
Вы можете использовать встроенные или сторонние функции для вычисления карты Вороного из набора сайтов (если вам нужно).
Это конкурс популярности, поэтому победит ответ с наибольшим количеством голосов. Избирателям предлагается судить ответы по
- насколько хорошо исходные изображения и их цвета приблизительны.
- насколько хорошо алгоритм работает на разных видах изображений.
- насколько хорошо работает алгоритм для малых N .
- может ли алгоритм адаптивно кластеризовать точки в тех областях изображения, которые требуют более подробной информации.
Тестовые изображения
Вот несколько изображений для проверки вашего алгоритма (некоторые из наших обычных подозреваемых, некоторые новые). Нажмите на картинку для увеличения.
Пляж в первом ряду нарисовал Оливия Белл и включил с ее разрешения.
Если вам нужен дополнительный вызов, попробуйте Йоши с белым фоном и нарисуйте правильную линию живота.
Вы можете найти все эти тестовые изображения в этой imgur галерее, где вы можете скачать их все в виде zip-файла. Альбом также содержит случайную диаграмму Вороного в качестве еще одного теста. Для справки, вот данные, которые его сгенерировали .
Пожалуйста, включите примеры диаграмм для различных изображений и N , например, 100, 300, 1000, 3000 (а также вставки для некоторых из соответствующих спецификаций ячеек). Вы можете использовать или опускать черные края между ячейками по своему усмотрению (это может выглядеть лучше на некоторых изображениях, чем на других). Не включайте сайты (за исключением, например, отдельного примера, если, конечно, вы хотите объяснить, как работает размещение вашего сайта).
Если вы хотите показать большое количество результатов, вы можете создать галерею на imgur.com , чтобы размер ответов был разумным. В качестве альтернативы, поместите миниатюры в свое сообщение и сделайте их ссылками на большие изображения, как я сделал в своем справочном ответе . Вы можете получить маленькие миниатюры, добавив s
имя файла в ссылку на imgur.com (например, I3XrT.png
-> I3XrTs.png
). Кроме того, не стесняйтесь использовать другие тестовые изображения, если вы найдете что-то хорошее.
Renderer
Вставьте свой вывод в следующий фрагмент стека, чтобы отобразить результаты. Точный формат списка не имеет значения, если в каждой ячейке заданы 5 чисел с плавающей запятой в порядке x y r g b
, где x
и y
- это координаты сайта ячейки, а r g b
также красный, зеленый и синий цветовые каналы в диапазоне 0 ≤ r, g, b ≤ 1
.
Фрагмент предоставляет опции для указания ширины линии краев ячейки и того, должны ли показываться сайты ячейки (последний в основном для целей отладки). Но обратите внимание, что выходные данные повторно отображаются только при изменении спецификаций ячеек - поэтому, если вы измените некоторые другие параметры, добавьте пробел в ячейки или что-то еще.
Огромные благодарности Раймонду Хиллу за написание этой действительно хорошей библиотеки JS Voronoi .
Связанные проблемы
источник
Ответы:
Python + scipy + scikit-image , взвешенная выборка диска Пуассона
Мое решение довольно сложное. Я делаю некоторую предварительную обработку изображения, чтобы удалить шум и получить отображение того, насколько «интересна» каждая точка (используя комбинацию локальной энтропии и обнаружения краев):
Затем я выбираю точки отбора, используя выборку диска Пуассона с поворотом: расстояние от круга определяется весом, который мы определили ранее.
Затем, когда у меня есть точки отбора проб, я делю изображение на сегменты вороного и назначаю среднее значение L * a * b * значений цвета внутри каждого сегмента каждому сегменту.
У меня много эвристик, и я также должен немного посчитать, чтобы убедиться, что количество точек выборки близко
N
. Я получаюN
именно то, что немного перебегаю , а затем отбрасываю некоторые пункты с помощью эвристики.С точки зрения времени выполнения этот фильтр недешев , но ни одно изображение ниже не заняло более 5 секунд.
Без дальнейших церемоний:
Картинки
Соответственно
N
это 100, 300, 1000 и 3000:источник
C ++
Мой подход довольно медленный, но я очень доволен качеством результатов, которые он дает, особенно в отношении сохранения краев. Например, вот Йоши и Коробка Корнелла с всего 1000 сайтами каждый:
Есть две основные части, которые делают это галочкой. Первый,
evaluate()
реализованный в функции, берет набор возможных местоположений сайта, устанавливает для них оптимальные цвета и возвращает оценку PSNR визуализированной тесселяции Вороного в сравнении с целевым изображением. Цвета для каждого сайта определяются путем усреднения пикселей целевого изображения, охватываемых ячейкой вокруг сайта. Я использую алгоритм Уэлфорда, чтобы помочь рассчитать как наилучший цвет для каждой ячейки, так и полученный PSNR, используя всего один проход по изображению, используя взаимосвязь между дисперсией, MSE и PSNR. Это сводит проблему к поиску лучшего набора местоположений сайта без особого отношения к цвету.Затем вторая часть, воплощенная в
main()
, пытается найти этот набор. Он начинается с выбора набора точек наугад. Затем на каждом шаге он удаляет одну точку (циклический перебор) и проверяет набор случайных точек-кандидатов для ее замены. Тот, который дает самый высокий PSNR из группы, принимается и сохраняется. По сути, это заставляет сайт переходить на новое место и, как правило, улучшает изображение побитно. Обратите внимание, что алгоритм намеренно не сохраняет исходное местоположение в качестве кандидата. Иногда это означает, что скачок снижает общее качество изображения. Это позволяет избежать застревания в локальных максимумах. Это также дает критерии остановки; программа завершается после выполнения определенного количества шагов без улучшения лучшего набора сайтов, найденных до сих пор.Обратите внимание, что эта реализация довольно проста и может легко занять часы процессорного времени, особенно по мере роста количества сайтов. Он пересчитывает полную карту Вороного для каждого кандидата и методом грубой силы проверяет расстояние до всех участков для каждого пикселя. Поскольку каждая операция включает в себя удаление одной точки за раз и добавление другой, фактические изменения изображения на каждом шаге будут достаточно локальными. Существуют алгоритмы для эффективного постепенного обновления диаграммы Вороного, и я считаю, что они дадут этому алгоритму огромное ускорение. Однако для этого конкурса я выбрал простоту и грубую силу.
Код
Бег
Программа является автономной и не имеет внешних зависимостей, кроме стандартной библиотеки, но требует, чтобы изображения были в двоичном формате PPM . Я использую ImageMagick для преобразования изображений в PPM, хотя GIMP и ряд других программ тоже могут это делать.
Чтобы скомпилировать его, сохраните программу как
voronoi.cpp
и запустите:Я ожидаю, что он, вероятно, будет работать в Windows с последними версиями Visual Studio, хотя я не пробовал это. Вы захотите убедиться, что вы компилируете с C ++ 11 или лучше и OpenMP включен, если вы это делаете. OpenMP не является строго необходимым, но он очень помогает сделать время выполнения более терпимым.
Чтобы запустить его, сделайте что-то вроде:
Более поздний файл будет обновляться с данными сайта по мере его поступления. Первая строка будет иметь ширину и высоту изображения, за которыми следуют строки значений x, y, r, g, b, подходящие для копирования и вставки в средство визуализации Javascript в описании проблемы.
Три константы в верхней части программы позволяют вам настраивать скорость и качество.
decimation
Фактор укрупняет изображение цели при оценке набора сайтов для цвета и PSNR. Чем оно выше, тем быстрее будет работать программа. При установке значения 1 используется изображение с полным разрешением. Вcandidates
постоянных управлений , сколько кандидатов для проверки на каждом шаге. Чем выше, тем больше шансов найти хорошее место для прыжка, но замедляет работу программы. И, наконец,termination
сколько шагов может пройти программа, не улучшая свой вывод перед тем, как выйти. Увеличение может дать лучшие результаты, но сделать это займет немного больше времени.Картинки
N
= 100, 300, 1000 и 3000:источник
IDL, адаптивное уточнение
Этот метод основан на Адаптивном уточнении сетки из астрономических симуляций, а также на поверхности подразделения . Это та задача, которой гордится IDL, о которой вы сможете судить по большому количеству встроенных функций, которые я смог использовать. : D
Я вывел некоторые промежуточные продукты для тестового изображения йоши на черном фоне, с
n = 1000
.Сначала мы выполняем яркость серого на изображении (используя
ct_luminance
) и применяем фильтр Prewitt (prewitt
см. Википедию ) для хорошего обнаружения краев:Затем следует настоящая грубая работа: мы подразделяем изображение на 4 и измеряем дисперсию в каждом квадранте отфильтрованного изображения. Наша дисперсия взвешивается на размер подразделения (который на этом первом этапе равен), так что «острые» области с высокой дисперсией не делятся на все меньшие, меньшие и меньшие. Затем мы используем взвешенную дисперсию для более детального таргетирования подразделений и итеративно подразделяем каждый подробный раздел на 4 дополнительных, пока не достигнем целевого числа сайтов (каждое подразделение содержит ровно один сайт). Так как мы добавляем 3 сайта при каждой итерации, мы получаем
n - 2 <= N <= n
сайты.Я сделал .webm процесса подразделения для этого изображения, которое не могу встроить, но оно здесь ; цвет в каждом подразделе определяется взвешенной дисперсией. (Я сделал такое же видео для йоши на белом фоне, для сравнения, таблица цветов перевернута, поэтому она идет к белому, а не к черному; это здесь .) Конечный продукт подразделения выглядит следующим образом:
Как только у нас есть список подразделений, мы проходим каждое подразделение. Конечное местоположение сайта - это позиция минимума изображения Prewitt, то есть наименее «острый» пиксель, а цвет сечения - это цвет этого пикселя; Вот оригинальное изображение с отмеченными сайтами:
Затем мы используем встроенный модуль
triangulate
для вычисления триангуляции Делоне для сайтов и встроенный модульvoronoi
для определения вершин каждого многоугольника Вороного, прежде чем рисовать каждый многоугольник в буфере изображения соответствующего цвета. Наконец, мы сохраняем снимок буфера изображения.Код:
Звоните через
voro_map, n, image, output_filename
. Я также включилwrapper
процедуру, которая проходила через каждое тестовое изображение и выполнялась на 100, 500 и 1000 сайтах.Выходные данные собраны здесь , а вот несколько миниатюр:
n = 100
n = 500
n = 1000
источник
Python 3 + PIL + SciPy, Fuzzy k-means
Алгоритм
Основная идея заключается в том, что кластеризация k-средних естественным образом разделяет изображение на клетки Вороного, поскольку точки привязаны к ближайшему центроиду. Однако нам нужно как-то добавить цвета в качестве ограничения.
Сначала мы конвертируем каждый пиксель в цветовое пространство Lab для лучшей цветопередачи.
Затем мы делаем своего рода «обнаружение края бедного человека». Для каждого пикселя мы смотрим на его ортогональных и диагональных соседей и вычисляем среднеквадратическую разницу в цвете. Затем мы сортируем все пиксели по этой разнице, с пикселями, наиболее похожими на их соседей в начале списка, и пикселями, наиболее отличающимися от их соседей сзади (то есть, более вероятно, что это будет крайняя точка). Вот пример для планеты, где чем ярче пиксель, тем больше он отличается от своих соседей:
(Существует четкий узор в виде сетки на приведенном выше выводе. Согласно @randomra, это, вероятно, связано с кодированием JPG с потерями или сжатием изображений imgur.)
Далее мы используем этот порядок пикселей для выборки большого количества точек для кластеризации. Мы используем экспоненциальное распределение, отдавая приоритет точкам, похожим на ребро и более «интересным».
Для кластеризации мы сначала выбираем
N
центроиды, случайно выбранные с использованием того же экспоненциального распределения, что и выше. Выполняется начальная итерация, и для каждого из полученных кластеров мы назначаем средний цвет и порог цветовой дисперсии. Затем для ряда итераций мы:(Нажмите для увеличения)
Наконец, мы отбираем большое количество точек, на этот раз используя равномерное распределение. Используя другое kd-дерево, мы присваиваем каждую точку ближайшему центроиду, образуя кластеры. Затем мы аппроксимируем срединный цвет каждого кластера, используя алгоритм восхождения на холм, давая наши окончательные цвета ячеек (идея для этого шага благодаря @PhiNotPi и @ MartinBüttner).
Примечания
В дополнение к выводу текстового файла для сниппета (
OUTFILE
), еслиDEBUG
он установлен,True
программа также выведет и перезапишет изображения выше. Алгоритм занимает пару минут для каждого изображения, так что это хороший способ проверки прогресса, который не добавляет слишком много времени.Пример выходов
N = 32:
N = 100:
N = 1000:
N = 3000:
источник
Mathematica, Случайные ячейки
Это базовое решение, поэтому вы получите представление о минимуме, о котором я вас спрашиваю. Учитывая имя файла (локально или в виде URL) в
file
и N вn
, следующий код просто выбирает N случайных пикселей и использует цвета, найденные в этих пикселях. Это действительно наивно и работает не очень хорошо, но я хочу, чтобы вы, ребята, победили это в конце концов. :)Вот все тестовые изображения для N = 100 (все изображения ссылаются на увеличенную версию):
Как видите, они по сути бесполезны. Хотя они могут иметь некоторую художественную ценность, с точки зрения экспрессионизма, оригинальные образы едва узнаваемы.
Для N = 500 ситуация немного улучшается, но все еще остаются очень странные артефакты, изображения выглядят размытыми, и много ячеек теряется в областях без деталей:
Твой ход!
источник
Dimensions@ImageData
и нетImageDimensions
? Вы можете избежать медленного вImageData
целом, используяPixelValue
.Mathematica
Мы все знаем, что Мартин любит Mathematica, поэтому позвольте мне попробовать его с Mathematica.
Мой алгоритм использует случайные точки от краев изображения, чтобы создать начальную диаграмму Вороного. Диаграмма затем предварительно проверяется путем итерационной корректировки сетки с помощью простого фильтра средних значений. Это дает изображения с высокой плотностью клеток вблизи областей с высокой контрастностью и визуально приятные клетки без сумасшедших углов.
На следующих изображениях показан пример процесса в действии. Веселье несколько испорчено плохим сглаживанием Mathematicas, но мы получаем векторную графику, которая должна чего-то стоить.
Этот алгоритм без случайной выборки можно найти в
VoronoiMesh
документации здесь .Тестовые изображения (100,300,1000,3000)
Код
источник
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Python + SciPy + ведущий
Алгоритм, который я использовал, следующий:
Алгоритм, кажется, работает очень хорошо. К сожалению, он может работать только на маленьких изображениях. У меня не было времени взять очки Вороного и применить их к большим изображениям. Они могут быть уточнены на этом этапе. Я мог бы также запустить MCMC дольше, чтобы получить лучшие минимумы. Слабым местом алгоритма является то, что он довольно дорогой. Я не успел подняться выше 1000 пунктов, и пара изображений из 1000 точек на самом деле все еще уточняется.
(щелкните правой кнопкой мыши и просмотрите изображение, чтобы получить увеличенную версию)
Ссылки на более крупные версии: http://imgur.com/a/2IXDT#9 (100 баллов), http://imgur.com/a/bBQ7q (300 баллов) и http://imgur.com/a/rr8wJ. (1000 баллов)
Изображения без маскировки выглядят следующим образом. Случайные точки выбираются из изображения, если случайное число меньше, чем значение изображения (нормированное на 1):
Я выложу большие изображения и очки Вороного, если у меня будет больше времени.
Редактировать: если вы увеличите число проходов до 100 * npts, измените функцию стоимости на несколько квадратов отклонений во всех каналах и ждите в течение длительного времени (увеличивая количество итераций, чтобы выйти из цикла до 200), можно сделать несколько хороших снимков всего за 100 баллов:
источник
Использование энергии изображения в качестве точечно-весовой карты
В моем подходе к этой задаче я хотел найти способ сопоставить «релевантность» конкретной области изображения с вероятностью того, что конкретная точка будет выбрана в качестве центроида Вороного. Тем не менее, я все еще хотел сохранить художественное ощущение мозаики Вороного путем случайного выбора точек изображения. Кроме того, я хотел работать с большими изображениями, чтобы ничего не потерять в процессе понижающей дискретизации. Мой алгоритм примерно так:
Результаты
N
= 100, 500, 1000, 3000источник