Каков наилучший алгоритм уменьшения изображения (по качеству)?
Я хочу выяснить, какой алгоритм является лучшим, который можно использовать для уменьшения растровой картинки. Под лучшим я подразумеваю тот, который дает самые привлекательные результаты. Я знаю бикубику, но есть ли что-то лучше? Например, я слышал от некоторых людей, что Adobe Lightroom имеет какой-то запатентованный алгоритм, который дает лучшие результаты, чем стандартная бикуба, которую я использовал. К сожалению, я сам хотел бы использовать этот алгоритм в своем программном обеспечении, поэтому тщательно охраняемые коммерческие секреты Adobe не подойдут.
Добавлено:
Я проверил Paint.NET и, к моему удивлению, кажется, что Super Sampling лучше, чем бикубический при уменьшении размера изображения. Это заставляет меня задаться вопросом, являются ли алгоритмы интерполяции способом вообще пойти.
Это также напомнило мне алгоритм, который я "изобрел" сам, но никогда не реализовывал. Я предполагаю, что у этого также есть имя (поскольку кое-что это тривиальное не может быть идеей обо мне одном), но я не мог найти это среди популярных. Super Sampling был самым близким.
Идея такова - для каждого пикселя в целевом изображении рассчитайте, где он будет находиться в исходном изображении. Это, вероятно, наложит один или несколько других пикселей. Тогда можно будет рассчитать площади и цвета этих пикселей. Затем, чтобы получить цвет целевого пикселя, нужно просто вычислить среднее значение этих цветов, добавив их области в качестве "весов". Таким образом, если целевой пиксель будет покрывать 1/3 желтого исходного пикселя и 1/4 зеленого исходного пикселя, я получу (1/3* желтый + 1/4* зеленый)/(1/3+1/4).
Естественно, это потребует значительных вычислительных ресурсов, но оно должно быть как можно ближе к идеалу, не так ли?
Есть ли название для этого алгоритма?
8 ответов
К сожалению, я не могу найти ссылку на исходный опрос, но когда голливудские кинематографисты перешли от кинофильмов к цифровым изображениям, этот вопрос часто возникал, поэтому кто-то (может быть, SMPTE, может быть, ASC) собрал группу профессиональных кинематографистов и показал им кадры. это было изменено, используя кучу разных алгоритмов. В результате для этих профессионалов, рассматривающих огромные движущиеся изображения, был достигнут консенсус, что Mitchell (также известный как высококачественный Catmull-Rom) является лучшим для увеличения, а sinc - для уменьшения. Но sinc - это теоретический фильтр, который уходит в бесконечность и поэтому не может быть полностью реализован, поэтому я не знаю, что они на самом деле имели в виду под "sinc". Вероятно, это относится к усеченной версии sinc. Lanczos - это один из нескольких практических вариантов sinc, который пытается улучшить только его усечение и, вероятно, является лучшим выбором по умолчанию для уменьшения количества неподвижных изображений. Но, как обычно, это зависит от изображения и того, что вы хотите: сжатие рисования линий для сохранения линий - это, например, случай, когда вы предпочитаете делать акцент на сохранении краев, что нежелательно при сжатии фотографии цветов.
Есть хороший пример результатов различных алгоритмов в Cambridge in Color.
Ребята из fxguide собрали много информации об алгоритмах масштабирования (наряду со многими другими вещами о компоновке и другой обработке изображений), на которые стоит обратить внимание. Они также включают тестовые изображения, которые могут быть полезны при выполнении ваших собственных тестов.
Теперь у ImageMagick есть обширное руководство по фильтрам передискретизации, если вы действительно хотите в него войти.
Немного иронично, что существует больше споров о масштабировании изображения, что теоретически может быть сделано идеально, поскольку вы только выбрасываете информацию, чем о масштабировании, когда вы пытаетесь добавить информацию, которая не не существует. Но начнем с Ланцоша.
Существует выборка Ланцоша, которая медленнее бикубической, но дает изображения более высокого качества.
(Би-) линейная и (би) кубическая повторная выборка не только некрасивы, но и ужасно некорректны при уменьшении масштаба с коэффициентом, меньшим 1/2. Они приведут к очень плохому алиасингу, схожему с тем, что вы получите, если вы уменьшите коэффициент вдвое, а затем будете использовать понижающую выборку ближайшего соседа.
Лично я бы порекомендовал (по районам) усреднять выборки для большинства задач понижающей дискретизации. Это очень просто, быстро и почти оптимально. Гауссова передискретизация (с выбранным радиусом, пропорциональным обратному коэффициенту, например, радиус 5 для понижающей дискретизации на 1/5), может дать лучшие результаты с немного большими вычислительными затратами, и это более математически обоснованно.
Одна из возможных причин использования гауссовой передискретизации заключается в том, что, в отличие от большинства других алгоритмов, она работает правильно (не вводит артефакты / псевдонимы) для повышающей и понижающей выборки, если вы выбираете радиус, соответствующий коэффициенту повторной выборки. В противном случае для поддержки обоих направлений вам понадобятся два отдельных алгоритма - усреднение области для понижающей дискретизации (что приведет к ухудшению до ближайшего соседа для повышения частоты дискретизации) и что-то вроде (би) кубического для повышения частоты дискретизации (что приведет к ухудшению до ближайшего соседа для снижения частоты дискретизации). Один из способов увидеть это замечательное свойство гауссовой передискретизации математически состоит в том, что гауссиан с очень большим радиусом приближается к усреднению по площади, а гауссов с очень маленьким радиусом приближается к (би) линейной интерполяции.
Я видел статью о Slashdot о Резке Шва некоторое время назад, возможно, это стоит посмотреть.
Резьба по шву - это алгоритм изменения размера изображения, разработанный Шаем Авиданом и Ариэлем Шамиром. Этот алгоритм изменяет размеры изображения не путем масштабирования или обрезки, а путем интеллектуального удаления пикселей (или добавления пикселей) к изображению, которое имеет небольшое значение.
Алгоритм, который вы описываете, называется линейной интерполяцией и является одним из самых быстрых алгоритмов, но не лучшим на изображениях.
Есть ли название для этого алгоритма?
Это может быть упомянуто как "коробка" или "окно" пересэмплирования в литературе. Это на самом деле менее вычислительно дорого, как вы думаете.
Он также может быть использован для создания промежуточного растрового изображения, которое впоследствии используется би-кубической интерполяцией, чтобы избежать наложения псевдонимов при пониженной дискретизации более чем на 1/2.
Не существует одного лучшего алгоритма уменьшения масштаба. Это во многом зависит от содержимого изображения и даже от того, что вы с ним делаете. Например, если вы обрабатываете изображение с использованием градиентов, часто лучше всего подогнать его к дифференцируемому сплайну (например, B-сплайну) и взять его производные. Если пространственная частота изображения относительно низкая, почти все будет работать достаточно хорошо (подход, пропорциональный площади, который вы описываете, популярен; в OpenCV он называется INTER_AREA, хотя на самом деле это скорее сглаживатель, чем интерполятор), но он получает сложный с высокочастотным содержанием (резкие края, высокая контрастность). В таких случаях вам обычно приходится выполнять какое-то сглаживание, либо встроенное в ресэмплер, либо в качестве отдельного шага.
Единственное правило, которое действительно выполняется почти в каждом случае, заключается в том, что худшее качество имеет ближайший сосед, за которым следует билинейность. Если вы можете позволить себе время обработки, чтобы сделать что-то лучше, чем билинейное, не используйте билинейное. Единственные достоинства билинейного метода заключаются в том, что он действительно быстр, прост в кодировании и часто поддерживается аппаратным обеспечением графического процессора.
Существует множество схем передискретизации более высокого порядка. Я видел десятки в литературе и сказал бы, что около 10 из них заслуживают внимания, в зависимости от того, чем вы занимаетесь. ИМХО, лучший подход — взять набор типичных изображений для того, что вы делаете, пропустить их через список обычных подозреваемых (сверточные бикубические ключи, Catmull-Rom, Lanczos2/4, Lanczos3/6, O-MOMS, B-сплайн...) и посмотрите, что обычно лучше всего подходит для вашего приложения. Скорее всего, как только вы перейдете на ресэмплер 4x4, не останется ни одного действительно последовательного победителя, если все ваши изображения не будут очень похожи. Иногда вы увидите некоторое последовательное улучшение с 6x6, таким как Lanczos3, но в большинстве случаев переход от билинейной 2x2 к любой 4x4 является большой победой. Именно поэтому большинство программ обработки изображений поддерживают разные варианты. Если бы одна вещь всегда работала лучше всего, все бы ею пользовались.
Если кому-то интересно, вот моя реализация на C++ алгоритма масштабирования с усреднением площади:
void area_averaging_image_scale(uint32_t *dst, int dst_width, int dst_height, const uint32_t *src, int src_width, int src_height)
{
// 1. Scale horizontally (src -> mid)
int mid_width = dst_width,
mid_height = src_height;
float src_width_div_by_mid_width = float(src_width) / mid_width;
float mid_width_div_by_src_width = 1.f / src_width_div_by_mid_width;
std::vector<uint32_t> mid(mid_width * mid_height);
for (int y=0; y<mid_height; y++)
for (int x=0; x<mid_width; x++)
for (int c=0; c<4; c++) {
float f = x * src_width_div_by_mid_width;
int i = int(f);
float d = ((uint8_t*)&src[i + y*src_width])[c] * (float(i) + 1 - f);
float end = f + src_width_div_by_mid_width;
int endi = int(end);
if (end - float(endi) > 1e-4f) {
assert(endi < src_width);
d += ((uint8_t*)&src[endi + y*src_width])[c] * (end - float(endi));
}
for (i++; i < endi; i++)
d += ((uint8_t*)&src[i + y*src_width])[c];
int r = int(d * mid_width_div_by_src_width + 0.5f);
assert(r <= 255);
((uint8_t*)&mid[x + y*mid_width])[c] = r;
}
// 2. Scale vertically (mid -> dst)
float mid_height_div_by_dst_height = float(mid_height) / dst_height;
float dst_height_div_by_mid_height = 1.f / mid_height_div_by_dst_height;
for (int y=0; y<dst_height; y++)
for (int x=0; x<dst_width; x++)
for (int c=0; c<4; c++) {
float f = y * mid_height_div_by_dst_height;
int i = int(f);
float d = ((uint8_t*)&mid[x + i*mid_width])[c] * (float(i) + 1 - f);
float end = f + mid_height_div_by_dst_height;
int endi = int(end);
if (end - float(endi) > 1e-4f) {
assert(endi < mid_height);
d += ((uint8_t*)&mid[x + endi*mid_width])[c] * (end - float(endi));
}
for (i++; i < endi; i++)
d += ((uint8_t*)&mid[x + i*mid_width])[c];
int r = int(d * dst_height_div_by_mid_height + 0.5f);
assert(r <= 255);
((uint8_t*)&dst[x + y*dst_width])[c] = r;
}
}