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


Вопрос:
каким образом можно определить граничные (между которыми находятся все остальные) цвета градиента?


Пример:
Для рисунка



на выходе алгоритма хотелось бы получить [clMagenta, clOrange]

первым делом выбрасываем из рассмотрения все что не относится к градиенту (на примере это белый цвет)

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

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

решение аналитическое оцифровать и оптимизировать самостоятельно

Здравствуйте, Vladix, Вы писали:

V>каким образом можно определить граничные (между которыми находятся все остальные) цвета градиента?

Взять множество цветов всех пикселов и найти минимум и максимум.
Естественно, надо знать алгоритм интерполяции цвета. То ли это в цветовой модели HSV, то ли RGB.

---

Теперь посмотрим, как можно сэкономить на обходе всех пикселов.

Для линейной растяжки: все изолинии (множества пикселов с одинаковым цветом) пенпердикулярны оси растяжки и пересекаются с периметром фигуры.
Следовательно, достаточно оббежать периметр.

Для концентрической круговой растяжки: изолинии — это концентрические окружности.
Найти центр можно так: берём две точки, находим там вектор градиента цвета, проводим из этих точек прямые по градиенту. Где пересекутся — там и центр окружности.
После чего находим наиболее удалённую от центра точку периметра — и пробегаем от центра до неё.

Для эллиптической растяжки... затруднюсь сказать. Видимо, по градиенту в четырёх точках.
То же касается концентрической параллелограммной (diamond) растяжки.

Как вариант: ткнуть в произвольную точку и оббежать её изолинию. По форме изолинии можно узнать и характер растяжки, и её центр (если это концентрическая). Правда, в случае параллелограмной — есть риск, что данная изолиния будет прямой от края до края фигуры.

Здравствуйте, cvetkov, Вы писали:

C>в случае с несколькими волнами цвет одной из границ может не присутствовать на рисунке.
Как раз в случае с несколькими волнами — оба граничных цвета будут присутствовать.

Вот если у нас интерполяция не пилообразная, а синусоидальная, то можно по фрагменту синусоиды найти её амплитуду.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, cvetkov, Вы писали:

C>>в случае с несколькими волнами цвет одной из границ может не присутствовать на рисунке.
К>Как раз в случае с несколькими волнами — оба граничных цвета будут присутствовать.
если картинка не обязана быть непрерывной, то как раз в нужных местах легко могут оказатся дыры

К>Вот если у нас интерполяция не пилообразная, а синусоидальная, то можно по фрагменту синусоиды найти её амплитуду.
по пилообразной это делается абсолютно так же

Здравствуйте, cvetkov, Вы писали:

К>>Как раз в случае с несколькими волнами — оба граничных цвета будут присутствовать.
C>если картинка не обязана быть непрерывной, то как раз в нужных местах легко могут оказатся дыры

Проклятье!

К>>Вот если у нас интерполяция не пилообразная, а синусоидальная, то можно по фрагменту синусоиды найти её амплитуду.
C>по пилообразной это делается абсолютно так же

Как это, по фрагменту пилы (меньше одного полупериода) можно найти амплитуду?
Хотя, если у нас есть несколько фрагментов, то мы можем найти период, а оттуда амплитуду.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, cvetkov, Вы писали:

К>>>Как раз в случае с несколькими волнами — оба граничных цвета будут присутствовать.
C>>если картинка не обязана быть непрерывной, то как раз в нужных местах легко могут оказатся дыры

К>Проклятье!

К>>>Вот если у нас интерполяция не пилообразная, а синусоидальная, то можно по фрагменту синусоиды найти её амплитуду.
C>>по пилообразной это делается абсолютно так же

К>Как это, по фрагменту пилы (меньше одного полупериода) можно найти амплитуду?
никак. я про такой use case забыл.
синусойда тут круче.
К>Хотя, если у нас есть несколько фрагментов, то мы можем найти период, а оттуда амплитуду.
вот про это я и говорил.

Здравствуйте, Vladix, Вы писали:

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


V>Вопрос:
V>каким образом можно определить граничные (между которыми находятся все остальные) цвета градиента?
Ну, для начала нужно провести анализ картинки.
Применяем к ней функцию... Градиента!
Получаем в каждой точке вектор градиента (шестикомпонентный) и начинаем исследовать его свойства.
1. По всей интересующей нас области градиент имеет одно и то же направление (среднеквадратичное отклонение тангенса угла поворота вектора градиента достаточно мало). Ага, это линейный градиент.
1.1. Модуль градиента тоже везде один и тот же — градиент равномерный; граничные цвета находятся "в начале" и "конце" линейки, заданной обнаруженным в п.1 направлением.
1.2. Модуль градиента меняется несколько раз — имеем несколько "волн" градиента. Ищем точки изменения модуля, в них как раз расположены "граничные" цвета
2. Градиент имеет радиальную природу. Вот тут я что-то туплю, не могу сообразить, какой формулой мы это обнаружим. Но в целом всё будет точно так же — находим центр градиента, исследуем градиент вдоль радиуса способом, аналогичным п.1 и получаем то же самое
3. Прямоугольный градиент — это комбинация из нескольких областей с линейным градиентом.

Считаем, что наш градиент — это кусочно-какое-нибудь (кусочно-линейное, -синусоидальное, -сплайновое — это все пофиг) изменение компонент r, g, и b. Вид интерполяции нам не важен, нас интересуют только экстремумы. Учтем, что меняются компоненты r, g и b независимо.

Пробегаем по картинке, находим максимум и минимум одной компоненты. Запоминаем, в каких точках они случились. То же делаем для других компонент. Экстремумы должны быть в тех же точках. Все.

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

Здравствуйте, goto, Вы писали:

G>Считаем, что наш градиент — это кусочно-какое-нибудь (кусочно-линейное, -синусоидальное, -сплайновое — это все пофиг) изменение компонент r, g, и b.

... или HSV.
Растяжка по RGB проходит по цветам с низкой насыщеностью и яркостью — т.е. по грязным.

Но, для примера, пусть будет RGB.
Тем более, что компонент Hue циклический, при переходе от фиолетового к бордовому будет скачок.

G>Вид интерполяции нам не важен, нас интересуют только экстремумы.
G>Учтем, что меняются компоненты r, g и b независимо.

Неправда, компоненты меняются синхронно. RGB(t) = RGB1 + (RGB2-RGB1)·f(t) где f(t) — скалярная функция.

G>Пробегаем по картинке, находим максимум и минимум одной компоненты. Запоминаем, в каких точках они случились. То же делаем для других компонент.
G>Экстремумы должны быть в тех же точках. Все.

Собственно, это и означает, что компоненты зависимы

G>Для ускорения можно посмотреть, какая из компонент меняется быстрее, по ней вычислить вектор градиента и пробежаться по нему. Вычислять и пробегаться можно (и нужно) неточно, в целых пикселах. Тут достаточно не пройти близко к изолинии.

Градиент же направлен пенпердикулярно изолиниям. Или имеется в виду — не попасть на изолинию минимума/максимума синусоиды, где модуль градиента близок к нулю, и непонятно, в какую сторону двигаться?

Наверно, можно сперва сделать грубую пристрелку. Прыгать по точкам с большим приращением координат, в сторону наибольшего изменения поля.
Мы же считаем, что функция периодическая либо линейная, поэтому любой локальный минимум и максимум нас устроит, его значение равно абсолютному минимуму или максимуму, соответственно.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, goto, Вы писали:

G>>Считаем, что наш градиент — это кусочно-какое-нибудь (кусочно-линейное, -синусоидальное, -сплайновое — это все пофиг) изменение компонент r, g, и b.

К>... или HSV.
К>Растяжка по RGB проходит по цветам с низкой насыщеностью и яркостью — т.е. по грязным.

Если градиент получен вручную каким-нибудь софтом типа Фотошопа, то он наверняка по RGB. Если требуется затейливое, к примеру, радуга (круг по Hue), то ее обычно получают последовательностью точек в RGB. Не припомню, чтобы HSV использовалось для ручных заливок в распространенных графических софтах.

К>Но, для примера, пусть будет RGB.
К>Тем более, что компонент Hue циклический, при переходе от фиолетового к бордовому будет скачок.

Меняем направление вращения .

G>>Вид интерполяции нам не важен, нас интересуют только экстремумы.
G>>Учтем, что меняются компоненты r, g и b независимо.

К>Неправда, компоненты меняются синхронно. RGB(t) = RGB1 + (RGB2-RGB1)·f(t) где f(t) — скалярная функция.

Ну, я имел в виду, что R(t) = f(R1, R2, t), в расчете R другие компоненты не участвуют. Интересующие точки можно найти, используя только одну из компонент (меняющуюся). Это в идеале. Поскольку мы имеем дело с целочисленной арифметикой, наш экстремум может размазаться на несколько пикселов, и придется шаманить в его окрестности и учитывать экстремумы других компонент.

G>>Пробегаем по картинке, находим максимум и минимум одной компоненты. Запоминаем, в каких точках они случились. То же делаем для других компонент.
G>>Экстремумы должны быть в тех же точках. Все.

К>Собственно, это и означает, что компоненты зависимы

G>>Для ускорения можно посмотреть, какая из компонент меняется быстрее, по ней вычислить вектор градиента и пробежаться по нему. Вычислять и пробегаться можно (и нужно) неточно, в целых пикселах. Тут достаточно не пройти близко к изолинии.

К>Градиент же направлен пенпердикулярно изолиниям. Или имеется в виду — не попасть на изолинию минимума/максимума синусоиды, где модуль градиента близок к нулю, и непонятно, в какую сторону двигаться?

В смысле не пойти вдоль изолинии. Но это, конечно, только для линейного и радиального градиента.

Синусоиды обычно не используются. В софтах изредка, в частных случаях для нтерполяции используются сплайны (как монотонная ф-я), а чаще всего все линейно. Если построить градиент по кусочно-линейной "пиле", то на глаз он будет выглядеть очень гладенько, и каждый посмотрит и скажет, что это синус .

К>Наверно, можно сперва сделать грубую пристрелку. Прыгать по точкам с большим приращением координат, в сторону наибольшего изменения поля.
К>Мы же считаем, что функция периодическая либо линейная, поэтому любой локальный минимум и максимум нас устроит, его значение равно абсолютному минимуму или максимуму, соответственно.

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

Тут еще везде целочисленная арифметика с возможностью промазать на пиксел-другой, в частности, пройти мимо экстремума. Все веселее, если тип градиента заранее неизвестен. Решаемо, но какая-то слегка муторная задачка. И, что обидно, наверняка кем-то уже неоднократно закодированная.

Еще есть подозрение, что задачка, стоящая перед ТС, проще (я прочитал его пост ). Цветов у него только два. "Волны" — это, видимо, их повторы (несколько периодов). И найти надо только сами эти цвета. Тогда пробегаем всю картинку (это быстро. В смысле быстро пробегаем ), не обращая внимания на затейливые цветные узоры. Находим абсолютный минимум и максимум R, G и B. Если их координаты совпадают (или, скажем, являются соседними), то задача решена. Если не совпадают, то говорим, что картинка неправильная .

Здравствуйте, goto, Вы писали:

G>Если градиент получен вручную каким-нибудь софтом типа Фотошопа, то он наверняка по RGB. Если требуется затейливое, к примеру, радуга (круг по Hue), то ее обычно получают последовательностью точек в RGB. Не припомню, чтобы HSV использовалось для ручных заливок в распространенных графических софтах.

XaraX предлагает растяжку радугой, не как что-то экзотическое, а очень даже штатное.
Причём интерполирует по компонентам HSV, а не просто по кругу с зафиксированными S и V.


G>>>Для ускорения можно посмотреть, какая из компонент меняется быстрее, по ней вычислить вектор градиента и пробежаться по нему. Вычислять и пробегаться можно (и нужно) неточно, в целых пикселах. Тут достаточно не пройти близко к изолинии.

К>>Градиент же направлен пенпердикулярно изолиниям. Или имеется в виду — не попасть на изолинию минимума/максимума синусоиды, где модуль градиента близок к нулю, и непонятно, в какую сторону двигаться?

G>В смысле не пойти вдоль изолинии. Но это, конечно, только для линейного и радиального градиента.

G>Синусоиды обычно не используются. В софтах изредка, в частных случаях для нтерполяции используются сплайны (как монотонная ф-я), а чаще всего все линейно. Если построить градиент по кусочно-линейной "пиле", то на глаз он будет выглядеть очень гладенько, и каждый посмотрит и скажет, что это синус .

Надо будет попробовать — сделать в Заре периодическую растяжку, продифференцировать и посмотреть, что там за функция.
Очень может быть, что пила /\/\/\


G>Еще есть подозрение, что задачка, стоящая перед ТС, проще (я прочитал его пост ). Цветов у него только два. "Волны" — это, видимо, их повторы (несколько периодов). И найти надо только сами эти цвета. Тогда пробегаем всю картинку (это быстро. В смысле быстро пробегаем ), не обращая внимания на затейливые цветные узоры. Находим абсолютный минимум и максимум R, G и B. Если их координаты совпадают (или, скажем, являются соседними), то задача решена. Если не совпадают, то говорим, что картинка неправильная .

Так я, собственно, и предложил это. Но Цветков указал, что для невыпуклых (а особенно, несвязанных) картинок может оказаться, что минимум и максимум лежат вне картинки. Тогда их можно вычислить экстраполяцией.

Здравствуйте, Vladix, Вы писали:

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


V>Вопрос:
V>каким образом можно определить граничные (между которыми находятся все остальные) цвета градиента?


V>Пример:
V>Для рисунка

V>

V>на выходе алгоритма хотелось бы получить [clMagenta, clOrange]
Преобразовать изображение в чб. Найти две наиболее отличающиеся по яркости точки.
Найти в списке известных цветов цвета, наиболее близкие к цветам найденных точек. ?)

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, goto, Вы писали:

G>>Если градиент получен вручную каким-нибудь софтом типа Фотошопа, то он наверняка по RGB. Если требуется затейливое, к примеру, радуга (круг по Hue), то ее обычно получают последовательностью точек в RGB. Не припомню, чтобы HSV использовалось для ручных заливок в распространенных графических софтах.

К>XaraX предлагает растяжку радугой, не как что-то экзотическое, а очень даже штатное.
К>Причём интерполирует по компонентам HSV, а не просто по кругу с зафиксированными S и V.

круг был просто для примера. Надо будет посмотреть, что сделано в Заре. Интересно. Мне градиенты в HSV всегда казались ненужной сущностью.

...
G>>Синусоиды обычно не используются. В софтах изредка, в частных случаях для нтерполяции используются сплайны (как монотонная ф-я), а чаще всего все линейно. Если построить градиент по кусочно-линейной "пиле", то на глаз он будет выглядеть очень гладенько, и каждый посмотрит и скажет, что это синус .

К>Надо будет попробовать — сделать в Заре периодическую растяжку, продифференцировать и посмотреть, что там за функция.
К>Очень может быть, что пила /\/\/\

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

Здесь слева синус, справа пила.


На глаз и в цветах синус часто напоминает сглаженные "прямоугольные импульсы". Я очень давно писал плагин для генерации градиентов. Помню, пробовал и синус, но в итоге его оттуда выбросил.

G>>Еще есть подозрение, что задачка, стоящая перед ТС, проще (я прочитал его пост ). Цветов у него только два. "Волны" — это, видимо, их повторы (несколько периодов). И найти надо только сами эти цвета. Тогда пробегаем всю картинку (это быстро. В смысле быстро пробегаем ), не обращая внимания на затейливые цветные узоры. Находим абсолютный минимум и максимум R, G и B. Если их координаты совпадают (или, скажем, являются соседними), то задача решена. Если не совпадают, то говорим, что картинка неправильная .

К>Так я, собственно, и предложил это. Но Цветков указал, что для невыпуклых (а особенно, несвязанных) картинок может оказаться, что минимум и максимум лежат вне картинки. Тогда их можно вычислить экстраполяцией.

Да, конечно, я что-то не подумал.

Задачка из тех, что на бумаге понятна, но из-за дискретности (ступеньки) и границ вычисление любого вектора превращается в небольшой танец.

Здравствуйте, abespalov, Вы писали:
...
V>>на выходе алгоритма хотелось бы получить [clMagenta, clOrange]
A>Преобразовать изображение в чб. Найти две наиболее отличающиеся по яркости точки.
A>Найти в списке известных цветов цвета, наиболее близкие к цветам найденных точек. ?)

Например, для градиента могут использоваться 2 разных значения RGB с одинаковой яркостью.

Здравствуйте, Аноним, Вы писали:

goto, ты?

А>Задачка из тех, что на бумаге понятна, но из-за дискретности (ступеньки) и границ вычисление любого вектора превращается в небольшой танец.

Там есть ещё одно маленькое заподло, как раз связанное со ступеньками.
Наивная интерполяция — это кусочно-константная функция. И на небольших значениях градиента получается плашечная заливка.
Глаз, хотя и не обладающий "абсолютным слухом" и не способный отличать цвета, скажем, #336699 и #326598, — тем не менее, границу эту прекрасно заметит по контрасту. (Особенно, если дисплей не 888-, а 565-битный, как на винмобайле).
То есть, картинка становится отчётливо полосатой.
Чтобы такого не было, применяют дизеринг, как в старом добром gif'е.
Получается, что по направлению градиента не ступеньки, а ШИМ

                _______
       _________
_______
             _ __ _____
    _ __ ____ _  _
____ _  _

да ещё и не одинаковая для смежных линий (иначе бы по-прежнему были полоски).
Вектор градиента должен сходить с ума!

Так что, возможно, есть смысл перед дифференцированием натравить на картинку какой-нибудь НЧ-фильтр.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:

К>goto, ты?

Да, оно не залогинилось.

А>>Задачка из тех, что на бумаге понятна, но из-за дискретности (ступеньки) и границ вычисление любого вектора превращается в небольшой танец.

К>Там есть ещё одно маленькое заподло, как раз связанное со ступеньками.
К>Наивная интерполяция — это кусочно-константная функция. И на небольших значениях градиента получается плашечная заливка.
К>Глаз, хотя и не обладающий "абсолютным слухом" и не способный отличать цвета, скажем, #336699 и #326598, — тем не менее, границу эту прекрасно заметит по контрасту. (Особенно, если дисплей не 888-, а 656-битный, как на винмобайле).
К>То есть, картинка становится отчётливо полосатой.

Так называемый "эффект Маха". Видимо, зрение первобытного человека должно было эффективно распознавать контуры и в низкоконтрастных областях, что бы человека никто не съел.

К>Чтобы такого не было, применяют дизеринг, как в старом добром gif'е.
...
К>Вектор градиента должен сходить с ума!

К дизерингу тогда уж стоит добавить потенциальную возможность jpeg-сжатия, мыло и веревку .

К>Так что, возможно, есть смысл перед дифференцированием натравить на картинку какой-нибудь НЧ-фильтр.

Да, наверное. И скорее всего с более высокой, не 8-битной точностью.

---
Маленькая картинка — большая погрешность. Большая картинка — более протяженные ступеньки (максимум 256 градаций каждой компоненты. В градиенте длиной 257 пикс. встретятся как минимум 2-пикс. ступеньки). Кругом одни проблемы .

Мне кажется (сиюминутно), здесь стоит плясать от изолиний, примерно как ты предлагал выше.
— Строим часть изолинии (часть — из-за границ).
— Анализируем на предмет углов.
— Аппроксимируем ее гладкие куски разными геометрическими фигурами. По, скажем, минимуму среднеквадратичного отклонения определяем подходящий тип фигуры. Собственно, для гладкого куска выбор — прямая или эллипс.
— Можем сразу попасть в эллипс с нужной точностью, тогда это почти готовое решение задачи.
— Если надо, повторяем в других областях заливки, добирая число параметров до достаточного, чтобы определить тип заливки и конкретную форму изолинии. Или, если надо, для дополнительного уточнения чисел.
— Если нужен вектор градиента, вычисляем аналитически, как номаль к аппроксимированной, аналитической изолинии.
— Вычисляем все необходимое, т.к. набрали достаточное число аналитически представленных кусочков.
— Для очистки совести просматриваем доступные окрестности вычисленных экстремумов на предмет возможного промаха в пиксел-другой (это грубо и ненаучно, но пусть будет).

Так, все слегка сумбурно и неполно. По сути аппроксимированные изолинии позволяют определять тип заливки и строить нормали к себе без танцев на ступеньках. Увы, уверенности ни в легкости реализации, ни в надежности работы такой аппроксимации у меня нет. Всякой возни там должно быть очень много, теперь уже в основном из-за границ.

Все было бы проще, если бы вектор градиента вычислялся с достаточной точностью непосредственно. Увы. Изолиния же — штука в пикселах более предсказумая, надежная. Для аппроксимации есть (должен быть!) готовый код.

Еще можно представить заливку у которой изолиний может не быть, у точек-соседей могут быть разные цвета. Например, это довольно распространенный 4-corner (задаются 4 цвета в углах прямоугольника). Хорошо, если таких заливок нет в списке Заказчика, а то Всемогутора заведомо не выйдет.

Какие-то сверхсадистские конфигурации границ картинки представить можно, но, я надеюсь, рассматривать не нужно.