Посчитать градиент цвета/интенсивности картинки быстро

[zgemm]

Добрый день,

пусть у меня картинка задана функцией $f(x,y) \in R^3$, где $x$, $y$ - координаты точки, и $f \in R^3$ - RGB цветность пикселя. Мне надо считать градиент (для детектора углов) но так, чтобы

1. сглаживать шумы на картинке,
2. учитывать, что граница или угол может иметь одинаковую яркость, но отличимую цветность (например, желтые листья на фоне зеленых),
3. и все это укладывалось в минимально возможное чиисло арифметических операций на пиксель (желательно меньше 5 операций на пиксель), что выглядит как-то не реально, но...

То есть надо считать $8 \log_2 \left( ||f(x,y)'_x||_2^2+||f(x,y)'_y||_2^2\right)$ в виде целого числа от 0 до 160 или что-то очень по сути похожее и с предварительным сглаживанием.

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

А можно ли как-то записать что-то типа Гаусса, но сразу на несколько точек, и в нем считать максимум градиента, и, чтобы это арифметически было быстро? Запутался, все попытки дают слишком много арифметических операций.

[ozheredov]

zgemm
Что если аппроксимировать исходное двумерное поле плоскостью по некоторой окрестности каждого пикселя, и вектор коэффициентов плоскости считать градиентом?

Если есть пиксели, у которых градиент яркости равен нулю, то брать два поля (допустим, яркость в палитре hsv и оттенок в палитре cielab) и из 2-х градиентов оставлять максимальный.

[zgemm]

ozheredov в сообщении #1587775 писал(а):

zgemm
Что если аппроксимировать исходное двумерное поле плоскостью по некоторой окрестности каждого пикселя, и вектор коэффициентов плоскости считать градиентом?

это хорошая идея, но пока у меня там 10 операций на пиксель на цвет/интенсивность получается, то есть чуть лучше, чем через рекуррентный почти-Гаусс фильтр, где 11 операций, но это все только на каждый цвет или яркость. То есть все равно хочется еще быстрее.

Тут разве только аппроксимировать не плоскостью, а поверхностью второго порядка, но строить такую поверхность не на каждый пиксель, а с шагом в 2-3 пикселя, но там все то же за 10 операций на пиксель получается.

ozheredov в сообщении #1587775 писал(а):

zgemm
Если есть пиксели, у которых градиент яркости равен нулю, то брать два поля (допустим, яркость в палитре hsv и оттенок в палитре cielab) и из 2-х градиентов оставлять максимальный.

Вот тут сомневаюсь, что тут все будет идеально или я Вас правильно понял,
1. cielab довольно сложная палитра и для конвертации в нее мне надо будет ну очень много арифметических операций,
2. в реальных картинках часто градиент яркости может быть маленьким, но градиент цвета - большим, тут на уровне да-нет нельзя так сразу переключаться. Нужна какая-то разумная норма, но если ее считать постфактум после того, как обрабатывать каждый цвет, то все будет ужасно плохо, и потребуется 32 арифметические операции на пиксель, что для меня не приемлемо.

То есть я предполагаю, что можно что-то изначально с пикселем сделать (получить какую-то интегральную характеристику по парам соседних пикселей в RGB) и вот потом эту интегральную характеристику уже начинать аппроксимировать дальше, но пока не придумал как.

Грубо говоря, в голове вертится мысль посчитать

$$(r_{x,y+1}-r_{x,y-1})^2+(g_{x,y+1}-g_{x,y-1})^2+(b_{x,y+1}-b_{x,y-1})^2 +$$

$$(r_{x+1,y}-r_{x-1,y})^2+(g_{x+1,y}-g_{x-1,y})^2+(b_{x+1,y}-b_{x-1,y})^2$$

что само по себе уже будет составлять 17 операций, но потом как-то это сгладить гауссом или еще как-то, но вот такой метод хоть и улучшит скорость с 32 арифметических операций до 20 примерно, но, во-первых, хочется быстрее, во-вторых, сглаживать после взятия производной как-то вроде не правильно, надо наоборот.

[wrest]

zgemm
Если логарифм нужен не слишком точный (скажем целочисленный) то это просто номер старшего разряда в котором есть единица в двоичной записи числа. Например для числа $0010011010$ двоичный целочисленный логарифм равен 7.

[photon]

1. Сглаживание гауссом подпортит градиенты, которые вы пытаетесь найти. Если хочется сгладить, но не потерять границы, то понадобится другой фильтр, например, билатеральный.
2. Если вам не нужна прям высокая точность, и вы готовы искать приблизительно и что-то на несколько пикселей, то в подавляющем большинстве случаев на цвет можно не обращать внимания. Даже для листьев желтых и зеленых границы будут видны.
3. Само по себе количество операций - такой себе параметр, вас точно интересует именно это? С точки зрения быстродействия интереснее смотреть на то, как это векторизуется/параллелится, как ведется доступ к данным в памяти - в этом смысле свёртки будут эффективнее, чем поиск какого-то максимума в окрестностях заданной точки.

[zgemm]

Спасибо большое, photon за очень важные советы!

Попробую ответить, чтобы прояснить ситуацию:

Ваш пункт 3: да, к сожалению, уже все процессорные ухищрения учтены, у меня трафик 75 мегапикселей в секунду в формате RGB (5:6:5), а пик процессора, что работает с этим изображением - 3 миллиардов операций в секунду (слабенький DSP), и, кроме градиентов мне очень моного другого сделать надо с этим изображением. Важно точное получение значений градиентов на границах и точное местоположение этих границ, а вот там, где все ровно я могу вообще градиенты не считать, или считать их с очень плохой точностью - мне они там просто не нужны.

Ваш пункт 2: на большом числе картинок действительно это так, но, вот, например в датасете bark из Оксфорда https://www.robots.ox.ac.uk/~vgg/research/affine/ в черно-белом варианте совсем перестают детектироваться контуры растений.

Ваш пункт 1: согласен, что сглаживание портит градиенты, но и без сглаживания повышается уровень шума градиентов и не получается достоверно детектировать границы на фоне текстур.

wrest Ой да, верно, можно даже еще точнее, если целое во флоат перевести и взять только с 20 по 27 биты, то для чисел больше 32 такая процедура дает с хорошей точностью логарифм по основанию 2, помноженный на 8.

[photon]

zgemm в сообщении #1588077 писал(а):

у меня трафик 75 мегапикселей

Если речь о видео, то вопрос: вам точно надо обрабатывать каждый кадр или, может быть, можно пропускать часть, если не успеваете обработать?

-- Mon Apr 03, 2023 18:10:59 --

zgemm в сообщении #1588077 писал(а):

на большом числе картинок действительно это так, но, вот, например в датасете bark

Специфические случаи, на которых будет работать плохо, практически всегда можно подобрать. Я бы делал поиск на цвете опциональным и смотрел как его включение влияет на точность и скорость на достаточно большом тестовом наборе - оптимизация алгоритма под конкретную картинку - не самый лучший подход. ИМХО, лучше высвобождающееся процессорное время потратить на более качественную фильтрацию, что улучшит результат на большинстве картинок, а не на специфических.

(Оффтоп)

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

[zgemm]

Спасибо большое photon за комментарии!

photon в сообщении #1588149 писал(а):

Если речь о видео, то вопрос: вам точно надо обрабатывать каждый кадр или, может быть, можно пропускать часть, если не успеваете обработать?

может и 5% сбоев и необработанных кадров и устроят меня, но существенно больше - однозначно нет, то есть по факту - надо почти всегда обрабатывать все. На подходе железо с 300 мегапикселями в секунду, а там железка по гигафлопсам будет не сильно-то жирнее.

photon в сообщении #1588149 писал(а):

Специфические случаи, на которых будет работать плохо, практически всегда можно подобрать. Я бы делал поиск на цвете опциональным и смотрел как его включение влияет на точность и скорость на достаточно большом тестовом наборе - оптимизация алгоритма под конкретную картинку - не самый лучший подход. ИМХО, лучше высвобождающееся процессорное время потратить на более качественную фильтрацию, что улучшит результат на большинстве картинок, а не на специфических.

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

Пока работаю по принципу - вначале считаю через точку квадрат градиентов по всем цветам и направлениям, если он получился меньше порога - считаю, что там границ нет совсем, и полагаю значения этих градиентов константами, иначе - все уточняю. Это позполяет находиться в диапазоне около 10 операций на пиксель, но есть примеры, когда такой подход работает с ошибкой, то есть он теряет границы.

photon в сообщении #1588149 писал(а):

Вот пример картинки

хороший пример, спасибо, на днях попробую прогнать через то, что у меня есть.

[photon]

zgemm в сообщении #1588170 писал(а):

вначале считаю через точку квадрат градиентов по всем цветам и направлениям

Градиент считается сверткой с каким-нибудь ядром Собеля или Щарра, при этом при вычислении для следующей точки можно использовать часть вычислений для предыдущей, а перепрыгивая через точку вы теряете часть того, что могли бы переиспользовать из вычисленного ранее. Не уверен, что вообще что-то при этом выигрываете в скорости. Учтите, что переиспользовать часть ранее вычисленных данных можно не только для последующих точек в той же строке, но и для следующих строк.

[zgemm]

photon в сообщении #1588216 писал(а):

...можно использовать часть вычислений для предыдущей... Учтите, что переиспользовать часть ранее вычисленных данных можно не только для последующих точек в той же строке, но и для следующих строк.

полностью разделяю Ваши опасения, так как по-другому там совсем все будет плохо! Я выше писал, что у меня по 10 арифметических операций на пиксель и на цвет получалось именно с таким переиспользованием информации, там даже несколько проходов по горизонтали и по вертикали требовалось, чтобы посчитать локальные суммы и только потом на их основе все можно дальше считать, иначе можно и в сотню операций на пиксель-цвет не уложиться!

Но ведь точно также можно работать на псевдорегулярной сетке, просто там больше ухищрений надо делать, чтобы случайно не потерять каких-то особенностей типа резкой и очень узкой границы, которая попала между большими шагами. Самый простой и наивный вариант - просто вначале все усреднить с исходной сетки $N \times M$ на $\frac{N}{K} \times \frac{M}{K}$, где $K$ от $2$ до $4$ потратив только одну арифметическую операцию на пиксель и цвет, и только потом уже применять все это, но, как я понимаю, этот метод не всегда хорошо работает, собственно именно из-за этого я и начал эту тему.

Моя же идея (я еще не придумал как реализовать и именно это и здесь спрашиваю) состоит в том, чтобы взять блок пикселей $8 \times 8$ в RGB и, каким-то образом, не потратив больше примерно 100 арифметических операций (с учетом цвета) оценить есть ли в этом блоке большой градиент или нет. Такими блоками с шагом скажем 6 по вертикали и горизонтали покрыть всю картинку, чтобы было перекрывание, и тогда я за примерно 3 операции на пиксель смогу гарантированно сказать где у меня нет большого градиента, а там где есть (пусть таких блоков будет 10%) я применю алгоритм как я писал выше (30 операций на пиксель) и тогда суммарно уложусь в 6 операций на пиксель на всю картинку.

[photon]

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

[zgemm]

Спасибо большое, photon за советы! Структурированная подсветка у меня в виде прямых линий, то есть границ там не много получается, это не точки, как многие делают. С линиями проще работать и детектировать их на фоне неизвестного постоянно меняющегося ландшафта. Буду смотреть что получается, есть пища для размышления.

[photon]

Еще мысль возникла. Подсветка инфракрасная же? По идее, она должна быть видна преимущественно в красном канале и меньше всего в синем. Что получится, если сплошняком просчитать градиенты в этих двух каналах и выбрать только те, которые есть в красном, но нет в синем, то есть смотреть на разность градиентов этих двух каналов? Другие границы тоже просочатся, но ИК-подсветка не должна потеряться.

[zgemm]

Спасибо большое, photon за идеи! Подсветка-то хоть и ИК, но 805нм, и, на мое удивление, минимум видимости там в зеленом, а не синем канале! Зеленый детектор тоже хорошо видит эту подсветку, почти также, как и красный. Физику не спрашивайте, не знаю почему так все интересно, просто два максимума у синего.

Пока подсветка у меня хорошо детектировалась на медленно движущихся объектах, так как можно именно так и поиграться, единственно, если все скачет в ближней зоне, а я включил 60fps, сложно понять где подсветка, а где - просто граница какого-то объекта. Собственно из-за этого-то и хочется сделасть что-то на все случаи жизни, хоя понятно, что такого не бывает.

[photon]

Еще мысль. Я не знаю, как себя поведет картинка в свете ИК-подсветки, но для обычного света затененный и освещенный участки почти не отличаются по каналу hue в HSV, правда, насколько я помню, там как раз на границе света в области полутеней могли вылазить отличия, которые в вашем случае могут все испортить, но, может, и нет - надо пробовать. В качестве эксперимента можно попробовать посмотреть на различия каналов H и V при вашей подсветке. Минус, что придется конвертировать RGB565 в HSV - точнее, в H+V, потому как S вам не понадобится. Не знаю, удастся ли выгадать что-то в поиске границ настолько, чтобы скомпенсировать затраты на конвертацию.

(Оффтоп)

Начинаю чувствовать себя ребе из анекдота про дохнущих кур.

Кстати, всем, кого это касается: хаг самеах!