Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 40
А разве не достаточно простого увеличения разрешения, потом применения матрицы поворота для каждого субпикселя и последующего антиалиасинга/фильрации?
3 преобразования => 3-х кратная потеря качества изображения.
Единственное преобразование с потерями- это поворот. Когда вы увеличиваете разрешение, скажем в 2 или 4 раза — все пиксели делятся на соответственно 4 или 16 субпикселей. Это преобразование без потерь.
Теперь, если не делать поворот, и снова уменьшить изображение, применив хоть линейную интерполяцию — изображение вернется в исходное состояние.
Все потери именно из-за поворота.
Теперь, если не делать поворот, и снова уменьшить изображение, применив хоть линейную интерполяцию — изображение вернется в исходное состояние.
Все потери именно из-за поворота.
Кардинально неверный подход, по-моему.
Невозможно ставить задачу «прецизионного» преобразования для растрового изображения, которое само по себе уже приближение. Фактически, лучше всего было бы сделать векторизацию, а затем её растрирование после поворота.
Photoshop'овский метод в данном случае честнее — сделайте 5 последовательных поворотов направо, а затем — налево. Ваш алгоритм, скорее всего, очень сильно «размажет» изображение, а «профессиональные» — скорее всего сохранят хотя бы контуры.
Невозможно ставить задачу «прецизионного» преобразования для растрового изображения, которое само по себе уже приближение. Фактически, лучше всего было бы сделать векторизацию, а затем её растрирование после поворота.
Photoshop'овский метод в данном случае честнее — сделайте 5 последовательных поворотов направо, а затем — налево. Ваш алгоритм, скорее всего, очень сильно «размажет» изображение, а «профессиональные» — скорее всего сохранят хотя бы контуры.
А при суммировании цвета пикселя вы учитываете необходимость проведения гамма-коррекции? Так как RGB — это нелинейная шкала, то нельзя просто суммировать значения цвета в RGB: так получится неверный цвет пикселя.
Впервые о таком слышу. Можно подробнее?
Интенсивность цвета:
Оно?
(R * 77 + G * 150 + B * 28) >> 8) & 255
Оно?
Нет, это
Csrgb = Clinear <= 0.0031308? 12.92*Clinear: (1+a)*Clinear1/2.4-a; where a=0.055.
The forward transformation
Csrgb = Clinear <= 0.0031308? 12.92*Clinear: (1+a)*Clinear1/2.4-a; where a=0.055.
The forward transformation
Вам нужно преобразовать изображения к гамме 1.0, сделать необходимые операции, вернуть исходную гамму.
Будьте осторожны с sRGB и ему подобными системами, там гамма «плавающая», подробнее тут.
Будьте осторожны с sRGB и ему подобными системами, там гамма «плавающая», подробнее тут.
У меня, как правило, не стояло задачи аккуратно крутить, а стояла задача — быстро крутить. Поэтому юзал всю жизнь что-то типа такого:
Вроде бы брал алгоритм из demo.design.faq, если не ошибаюсь.
// buffer = source buffer RGB565[320x200]
// scn = target buffer RGB565[320x200]
void FastRotate(float scale, //the scaling factor
float ang) //the rotation angle
{
long xscale=sin(ang)*65536L/scale;
long yscale=cos(ang)*65536L/scale;
long xc=(screen_dx/2)*65536L - ((screen_dx/2)*yscale+(screen_dy/2)*xscale);
long yc=(screen_dy/2)*65536L - ((screen_dy/2)*yscale-(screen_dx/2)*xscale);
WORD far *scn=shadow_buffer;
for (int y=0;y<screen_dy;y++) //normally from 0 to 199
{
long xlong=xc,ylong=yc; //init x/ylong to topleft of square
for (int x=0;x<screen_dx;) //normally from 0 to 319
{
register int tempx=xlong>>16;
register int tempy=ylong>>16;
if( (tempx<0) || (tempx>=screen_dx) || (tempy<0) || (tempy>=screen_dy) )
scn[x++]=0;
else
scn[x++]= buffer[tempx+y320[tempy]];
xlong+=yscale;ylong-=xscale;
}
scn+=screen_dx; // WARNING
xc+=xscale;yc+=yscale;
}
}
Вроде бы брал алгоритм из demo.design.faq, если не ошибаюсь.
Хороший подход, но теперь Вам ещё предстоит поработать над теорией цвета (и света). Дело в том, что коэффициенты смешения нельзя брать пропорциональными просто площади «осколков». Поясню на примере. Если белый пиксел на черном фоне сдвинуть на 50% в сторону, то результирующие два пиксела не будут содержать цвета (128,128,128) ни (127,127,127) — т.к. количество света, излучаемые парой таких серых пикселов, будет отличаться от количества света, излучаемое одним белым пикселом (из-за гаммы), хотя при прецизионном смещении очевидно, что яркость картинки должна была бы остаться полностью прежней.
А почему бы на сделать тест, при котором изображение поворачивается на небольшой угол за один шаг и обратно за два шага и сравнить изображения?
Идея интересная.
Покажите, пожалуйста, сравнение результата поворота 365 раз на 1° вашим алгоритмом и фотошопом.
Желательно картинку поконтрастнее.
Покажите, пожалуйста, сравнение результата поворота 365 раз на 1° вашим алгоритмом и фотошопом.
Желательно картинку поконтрастнее.
Попутно отметим, что алгоритм поворота, реализованный в Photoshop, не претерпел за 10 лет каких-либо ощутимых изменений.
Наверное потому, что он является интеллектуальной собственностью компании и запатентован всеми мыслимыми и немыслимыми патентами. :)
Но некоторые изменения все же были внесены. Если я не ошибаюсь, то начиная с Creative Suite, поворот на углы кратные 90 градусам проводятся без потери качества.
Ваш алгоритм, автор, эквивалентен следующему. Применим для увеличения разрешения исходного изображения Билинейную интерполяцию и повысим разрешение, скажем, в 100 раз. После этого выполним поворот простым алгоритмом «ближайшего соседа», который для каждого повернутого пикселя в результирующем изображени, имеющем такое же разрешение, как исходное, находит координаты пикселя в обработанном изображении, разрешение которого было многократно увеличено. Так как эти координаты, вообще говоря, будут не совпадать с координатами центров пикселей исходного изображения, а будут ближе к центрам каких-нибудь интерполированных пикселей — то в результирующем изображении и окажутся значения, промежуточные между соседними пикселями исходного изображения.
Неважно, что в реализации это как бы выглядит сложнее, но это позволяет по-другому взглянуть на задачу математически. Теперь можно подумать об использовании других видов интерполяции, кроме билинейной. Например, взять бикубическую интерполяцию, которая используется в настоящее время как один из прецизионных методов изменения разрешения изображения. Или можно провести найквист-интерполяцию исходного изображения. В общем, вариантов очень много, хотя ни один из них не является идеальным.
Неважно, что в реализации это как бы выглядит сложнее, но это позволяет по-другому взглянуть на задачу математически. Теперь можно подумать об использовании других видов интерполяции, кроме билинейной. Например, взять бикубическую интерполяцию, которая используется в настоящее время как один из прецизионных методов изменения разрешения изображения. Или можно провести найквист-интерполяцию исходного изображения. В общем, вариантов очень много, хотя ни один из них не является идеальным.
Вы не правы. Очевидно, что предложенный алгоритм не содержит в себе (ни явно, ни неявно) билинейной интерполяции. Если говорить о формальном аналоге, то тут используется кусочно постоянная интерполяция исходного изображения, т.е. фактически точечные пикселы заменяются квадратными пикселами конечного размера (что явно написано в статье) и потом производится интегрирование полученной кусочно-постоянной функции-интерполянта по квадратам, соответствующим повернутым пикселам.
Это вы не правы. Данный алгоритм содержит билинейную интерполяцию неявно. К ней приводит интегрирование кусочно-постоянной функции. Ведь интеграл от константы является линейной функцией!
Представьте себе ту же ситуацию в одномерном случае. Возьмем таблично заданную функцию y[i] в равноотстоящих точках x[i]: x[i+1]-x[i]=d=const при любом i. Проинтерполируем ее кусочно-постоянно с центрами постоянных кусков, расположенных в x[i]. Получим: y(x)=y[i] при x[i]-d/2<=x<x[i]+d/2.
Возьмем интервал (x1, x2), равный расстоянию между значениями в таблице: x2-x1=d. Это будет аналог повернутых пикселей. Проинтегрируем y(x) на этом интервале. Интеграл разобьется на два слагаемых, так как, в общем случае, в интервал (x1,x2) попадет два соседних интервала, на которых y(x) постоянна. Найдем i такое, что x[i]-d/2 <= x1< x[i]+d/2. Тогда значение интеграла будет равно:
I = y[i]*(x[i]+d/2-x1) + y[i+1]*(x2 — x[i] — d/2)
Если задать интервал координатой его центра x3, так что x1=x3-d/2, x2=x3+d/2 — то интеграл будет равен:
I(x3) = y[i]*(x[i] + d/2 — x3 + d/2) + y[i+1]*(x3 + d/2 — x[i] — d/2)
Упростим выражение:
I(x3) = y[i]*(x[i]+d-x3) + y[i+1]*(x3-x[i])
Но значение этого интеграла есть линейная интерполяция исходной функции, с поправкой лишь на постоянный множитель d. Если I(x3) разделить на d — то получится линейная интерполяция от исходной функции. В этом несложно убедиться, если подставить x3=x[i]. В этом случае второе слагаемое обращается в нуль, и значение интеграла, деленное на d, будет равно y[i], то есть интерполяция проходит через y[i], как и требуется. С другой стороны, если устремить x3 к x[i]+d (сделать равным нельзя, т.к. при этом требуемое значение i изменится) — то в пределе обратится в нуль первое слагаемое, а от второго, деленного на d, останется y[i+1]. То есть интерполяция проходит и через y[i+1]. Значение I является линейной функцией относительно x3. А через две точки (x[i],y[i]) и (x[i+1],y[i+1]) можно провести одну и только одну прямую, поэтому приведенный выше способ приводит к линейной интерполяции.
Все вышесказанное обобщается для двумерного случая и приводит к билинейной интерполяции.
Представьте себе ту же ситуацию в одномерном случае. Возьмем таблично заданную функцию y[i] в равноотстоящих точках x[i]: x[i+1]-x[i]=d=const при любом i. Проинтерполируем ее кусочно-постоянно с центрами постоянных кусков, расположенных в x[i]. Получим: y(x)=y[i] при x[i]-d/2<=x<x[i]+d/2.
Возьмем интервал (x1, x2), равный расстоянию между значениями в таблице: x2-x1=d. Это будет аналог повернутых пикселей. Проинтегрируем y(x) на этом интервале. Интеграл разобьется на два слагаемых, так как, в общем случае, в интервал (x1,x2) попадет два соседних интервала, на которых y(x) постоянна. Найдем i такое, что x[i]-d/2 <= x1< x[i]+d/2. Тогда значение интеграла будет равно:
I = y[i]*(x[i]+d/2-x1) + y[i+1]*(x2 — x[i] — d/2)
Если задать интервал координатой его центра x3, так что x1=x3-d/2, x2=x3+d/2 — то интеграл будет равен:
I(x3) = y[i]*(x[i] + d/2 — x3 + d/2) + y[i+1]*(x3 + d/2 — x[i] — d/2)
Упростим выражение:
I(x3) = y[i]*(x[i]+d-x3) + y[i+1]*(x3-x[i])
Но значение этого интеграла есть линейная интерполяция исходной функции, с поправкой лишь на постоянный множитель d. Если I(x3) разделить на d — то получится линейная интерполяция от исходной функции. В этом несложно убедиться, если подставить x3=x[i]. В этом случае второе слагаемое обращается в нуль, и значение интеграла, деленное на d, будет равно y[i], то есть интерполяция проходит через y[i], как и требуется. С другой стороны, если устремить x3 к x[i]+d (сделать равным нельзя, т.к. при этом требуемое значение i изменится) — то в пределе обратится в нуль первое слагаемое, а от второго, деленного на d, останется y[i+1]. То есть интерполяция проходит и через y[i+1]. Значение I является линейной функцией относительно x3. А через две точки (x[i],y[i]) и (x[i+1],y[i+1]) можно провести одну и только одну прямую, поэтому приведенный выше способ приводит к линейной интерполяции.
Все вышесказанное обобщается для двумерного случая и приводит к билинейной интерполяции.
Человеческий глаз лучше воспринимает разницу в яркости (контраст) чем цвет. Именно поэтому качественные алгоритмы над графикой подгоняются под наше восприятие (предпочтение контрасту, а не цвету), а не математическую точность. Алгоритм в фотошопе дает более качественное изображение на выходе, т.к. не замыливает картинку. Это гораздо сложней, чем вы подумали.
Теперь бы к идеальному повороту добавить еще и идеальное повышение резкости
Несмотря на критику метода в комментариях, статья мне понравилась. Побольше бы таких на хабре.
В чем смысл, если картинка выглядит хуже, а потери все равно есть?)
Неоправданно сложный алгоритм, в плане анализа различных геометрических case'ов наложения.
Намного проще (и с той же точностью) можно было бы сделать так: берем математически воображаемый градиент между центрами каждых соседних пикселей (2-мерный). Таким образом получаем непрерывную функцию по каждой компоненте изображения (r, g, b) = f(x, y), где x, y — любые вещественные. При повороте — соответственно пересчитываем новые значения для центров пикселей (для повернутого растра), и через ранее определенную функцию для каждого получаем цвет.
Это также позволяет, задавая различные варианты этой функции получать разные распределения «воображаемых межпиксельных градиентов» (он ведь не обязательно может быть линейный), и будем получать различный результат (например, как в фотошопе, более резкое изображение).
p.s. При повороте на 0* предложенный алгоритм вернет в точности то же изображение, т.к. центры поподут на «целочисленные» части функции, для которых цвет определен из исходных пикселей.
Намного проще (и с той же точностью) можно было бы сделать так: берем математически воображаемый градиент между центрами каждых соседних пикселей (2-мерный). Таким образом получаем непрерывную функцию по каждой компоненте изображения (r, g, b) = f(x, y), где x, y — любые вещественные. При повороте — соответственно пересчитываем новые значения для центров пикселей (для повернутого растра), и через ранее определенную функцию для каждого получаем цвет.
Это также позволяет, задавая различные варианты этой функции получать разные распределения «воображаемых межпиксельных градиентов» (он ведь не обязательно может быть линейный), и будем получать различный результат (например, как в фотошопе, более резкое изображение).
p.s. При повороте на 0* предложенный алгоритм вернет в точности то же изображение, т.к. центры поподут на «целочисленные» части функции, для которых цвет определен из исходных пикселей.
при этом создаёт «ореолы» искажённого цвета
У вас исходное изображение крепко шарплено. Возмите фотографию без обработки для примера.
Ореолы искаженного цвета будут почти всегда — цвет объекта при поворотах будет смешиваться с цветом фона. Чтобы их избежать, пришлось бы брать пиксель исходного изображения, площадь пересечения которого с нашим максимальна, и использовать его цвет (компоненту H или HS в пространстве HSL или компоненты AB в LAB), а яркость получать усреднением. Но не уверен, выйдет ли из этого что-нибудь хорошее.
Благодарю всех за отзывы! Они были действительно ценными и нтересными.
С вашего позволения, отвечу в одном сообщении на ключевое. Материал статьи я готовил месяц, потому и с комментарием задержался.
1. На практике редко возникает потребность в том, чтобы вращать одно и то же изображение много раз. В таких условиях применение любого алгоритма приведёт к накоплению ошибок и усилению искажений. На практике возникает задача повернуть одно изображение один раз. И здесь вполне уместно поставить вопрос, что ценнее: контрастные детали или информация о цвете? Фотошоп даёт ответ — контрастные детали важнее, цветом можно пожертвовать. Предложенный мной алгоритм отвечает на вопрос иначе — цвет важнее, контрастом можно пожертвовать. Я отнюдь не настаиваю на том, что мой алгоритм лучше всех алгоритмов. Он просто предоставляет выбор метода под конкретную задачу.
Вместе с тем, я всё же провёл эксперимент, подобный тому, который предложили Krovosos и archim. В итоге изображение, повёрнутое прецизионным алгоритмом, действительно, получилось более размытым, чем у фотошопа, но и ошибка в цвете у фотошопа получилась большей. Например, по каналу G для изображения тюльпана из теста №2 ошибка после 32 последовательных поворотов на 5° у Фотошопа достигла 0,4%, а у моего алгоритма оказалась на уровне 0,005% т.е. на 2 порядка лучше.
Тут же следует заметить, что размытость изображения — это не приговор. Можно подумать над эффективным алгоритмом шарпизации, специфичными для данного алгоритма поворота. Вопрос не так прост и очевиден, тут действительно есть над чем подумать.
2. Касательно гамма-коррекции я предлагаю провести такой мысленный эксперимент. Представим, что тестовое изображение получено непосредственно с идеальной фотоматрицы. Теперь представим, что мы повернули фотоматрицу на небольшой угол и снова сделали снимок таким образом, чтобы элемент изображения, который снимался одним фотоэлементом фотоматрицы оказался разделённым между двумя фотоэлементами. Совершенно понятно, что в таком случае каждый фотоэлемент получит в 2 раза меньше света, поэтому и в прецизионном алгоритме яркость этого пикселя должна разделиться. С другой стороны, если RGB шкала действительно нелинейная (что для меня новость), коррекцию итогового цвета произвести надо обязательно. Над этим нюансом я тоже обещаю подумать.
Ещё раз всем спасибо за комментарии.
С вашего позволения, отвечу в одном сообщении на ключевое. Материал статьи я готовил месяц, потому и с комментарием задержался.
1. На практике редко возникает потребность в том, чтобы вращать одно и то же изображение много раз. В таких условиях применение любого алгоритма приведёт к накоплению ошибок и усилению искажений. На практике возникает задача повернуть одно изображение один раз. И здесь вполне уместно поставить вопрос, что ценнее: контрастные детали или информация о цвете? Фотошоп даёт ответ — контрастные детали важнее, цветом можно пожертвовать. Предложенный мной алгоритм отвечает на вопрос иначе — цвет важнее, контрастом можно пожертвовать. Я отнюдь не настаиваю на том, что мой алгоритм лучше всех алгоритмов. Он просто предоставляет выбор метода под конкретную задачу.
Вместе с тем, я всё же провёл эксперимент, подобный тому, который предложили Krovosos и archim. В итоге изображение, повёрнутое прецизионным алгоритмом, действительно, получилось более размытым, чем у фотошопа, но и ошибка в цвете у фотошопа получилась большей. Например, по каналу G для изображения тюльпана из теста №2 ошибка после 32 последовательных поворотов на 5° у Фотошопа достигла 0,4%, а у моего алгоритма оказалась на уровне 0,005% т.е. на 2 порядка лучше.
Тут же следует заметить, что размытость изображения — это не приговор. Можно подумать над эффективным алгоритмом шарпизации, специфичными для данного алгоритма поворота. Вопрос не так прост и очевиден, тут действительно есть над чем подумать.
2. Касательно гамма-коррекции я предлагаю провести такой мысленный эксперимент. Представим, что тестовое изображение получено непосредственно с идеальной фотоматрицы. Теперь представим, что мы повернули фотоматрицу на небольшой угол и снова сделали снимок таким образом, чтобы элемент изображения, который снимался одним фотоэлементом фотоматрицы оказался разделённым между двумя фотоэлементами. Совершенно понятно, что в таком случае каждый фотоэлемент получит в 2 раза меньше света, поэтому и в прецизионном алгоритме яркость этого пикселя должна разделиться. С другой стороны, если RGB шкала действительно нелинейная (что для меня новость), коррекцию итогового цвета произвести надо обязательно. Над этим нюансом я тоже обещаю подумать.
Ещё раз всем спасибо за комментарии.
>> Представим, что тестовое изображение получено непосредственно с идеальной фотоматрицы.
Вот именно, а теперь вернёмся в реальность и поймём что тестовое изображение получено с фотоматрицы очень далёкой от идеала, где пиксель нередко состоит из элементов RGGB (и это не опечатка). И соответственно признаем что гамма-коррекцию не то чтобы не всегда надо делать, а надо делать вообще всегда.
Вот именно, а теперь вернёмся в реальность и поймём что тестовое изображение получено с фотоматрицы очень далёкой от идеала, где пиксель нередко состоит из элементов RGGB (и это не опечатка). И соответственно признаем что гамма-коррекцию не то чтобы не всегда надо делать, а надо делать вообще всегда.
На досуге переработал и упростил структуру программы. Время расчётов при этом увеличилось примерно в 1,7 раз но память теперь расходуется только на хранение битмапов, что позволяет работать с изображениями любых размеров.
Скачать программу и исходники можно здесь: prosolver.kiev.ua/PreciseRotation2.zip
Скачать программу и исходники можно здесь: prosolver.kiev.ua/PreciseRotation2.zip
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Прецизионный поворот растрового изображения на произвольный угол