roboforum.ru

Подробнее погляжу попозжее, но вот в оценке W*H*log2(W*H) я сумневаюсь. Не учтены сравнения как мне кажется. И еще это будет не очень хорошо работать на полутоновых изображениях как мне кажется.

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

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

Возможно продать только готовый продукт. Алгоритм - не продукт.

Солидарен с Виталием. Или может не доконца допонял смысл - сложно чтолибо осознать в вечер понедельника.

Повторюсь - солидарен с Виталием на тему гистограмм. Средний цвет, на мой взгляд, уш очень слабая особенность изображения. Куда лучше использовать гистограмму.

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

По твоему - мы берем квадрат скажем 50х50 и находим средний цвет для этого. Можно даже использовать интегральное изображение (возможно). Далее можно даже масштабировать окно поиска скажем на 1.25 каждый раз. Но на мой взгляд (если я правильно понял) не даст высокого процента обнаружения.

Надо просто сделать и посмотреть результат.

Николай_Алексеевич писал(а):Повторюсь - солидарен с Виталием на тему гистограмм. Средний цвет, на мой взгляд, уш очень слабая особенность изображения. Куда лучше использовать гистограмму.

нормализованный к размеру окна градиент еще лучше (от масштаба не зависит)

Добавлено спустя 6 минут 31 секунду:

=DeaD= писал(а):1. Быстрая оценка среднего значения цвета в прямоугольном регионе - подготовка кэша промежуточных данных занимает O(W*H) и памяти пропорционально W*H*log2(W*H), потом за константу можно мгновенно извлечь средний цвет в любом регионе.

2DeaD. Че-то не понятно о каком из средних идет речь, из каких регионов.
Вот еще давно пытался "влоб" оптимизировать свертку, т.е. перемножение пикселей с окном NxN значений ядра. Т.е. подготовив несколько массивов перемноженных данных, дак вышло в 20 раз медленнее просчета по пиксельно. Тут надо от платформы исходить, если PC - память у нее слабая...

GraphD писал(а):нормализованный к размеру окна градиент еще лучше (от масштаба не зависит)

Это что за зверь такой?

GraphD писал(а):2DeaD. Че-то не понятно о каком из средних идет речь, из каких регионов.
Вот еще давно пытался "влоб" оптимизировать свертку, т.е. перемножение пикселей с окном NxN значений ядра. Т.е. подготовив несколько массивов перемноженных данных, дак вышло в 20 раз медленнее просчета по пиксельно. Тут надо от платформы исходить, если PC - память у нее слабая...

Дык какой смысл как вы предлагаете оптимизировать? конечно у вас медленней выйдет, множитель то у вас не инвариантен относительно сдвига.

Ладно, так и быть садитесь поудобнее, начинаем урок динамического программирования, из классической школы построения алгоритмов

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

Далее перейдем к нашей задаче (для простоты будем считать картинку черно-белой, 256 градаций серого):

Пусть Pic[x][y] - матрица яркостей пикселей картинки, где 0<=x<W, 0<=y<H.

Рассчитаем матрицу Pic0[x0][y0] сумм яркостей Pic[x][y] из прямоугольника (0,0)-(x0,y0):

Тупо бежим по всем пикселям в двойном цикле и выставляем Pic0[x][y]=Pic[x][y]+Pic0[x-1][y]+Pic0[x][y-1]-Pic0[x-1][y-1].

Средний цвет прямоугольной области (x1+1,y1+1)-(x2,y2), где x2>x1, y2>y1 теперь можно вычислить значение следующей формулы:
AverageColor(x1+1,y1+1,x2,y2)=(Pic0[x2][y2]-Pic0[x1][y2]-Pic0[x2][y1]+Pic0[x1][y1])/((x2-x1)*(y2-y1)), то есть за фиксированное число операций.

Вот и всё. Урок классических алгоритмов окончен

PS: Домашнее задание решить с помощью динпрога игру в камешки (где можно забирать из кучки 1-3 камешка и кто последний берет, тот проиграл)

PPS: Только обувью не кидаться за стёбный тон )))))))

PPPS: Просьба извинить меня всем пострадавшим и сломавшим мозг при попытке понять моё недавно еще постоянно изменяющееся и кривое сообщение, форум видимо что-то из кода принял за тег и сломал мне пол сообщения. Еле вернул текст

Добавлено спустя 1 минуту 4 секунды:

Виталий писал(а):

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

Все зависит от гистограммы - среднее значение - это вырожденная гистограмма. =)
Можно на 2, на 4, на 8 значений гистограмму делать.
Да и современные процессоры умеют конфейером эт дела обсчитывать вроде (но я толком не знаю как).

Конкретизируйте ваше предложение с помощью указания функции расстояния/нормы для гистограмм

GraphD писал(а):

=DeaD= писал(а):

GraphD писал(а):нормализованный к размеру окна градиент еще лучше (от масштаба не зависит)

Это что за зверь такой?

Ну, иначе говоря, если из значений элементов в матрице NxN мы хотим сформировать некую величину F`, а потом сравнить с величиной F`` матрицы MxM, которая расчитана по такой же схеме, то нужно нормализовать F` и F``. Если схема расчета F основана на сумме величин пикселей (или их градиента), то нормализация идет по числу пикселей, т.е. по N^2 и M^2 соответственно. Т.е. школа, 10й класс, или максимум 1курс =))

Ну не совсем математически четко, но вашу мысль понял только это не к размеру, а к площади для математической четкости надо еще некоторые ограничения ввести - типа чтобы можно было это отображение NxN => F' было представлять в непрерывной области прямоугольной формы, тогда становится ясным смысл, а произвольные дискретные матрицы сравнивать - нафиг надо

GraphD писал(а):

=DeaD= писал(а):Пусть Pic[x][y] - матрица яркостей пикселей картинки, где 0<=x<W, 0<=y<H.

Очень интересная схема на 1й взгляд. Дак она найдет средний цвет произвольной области? Т.е. фактически будет разномасштабить картинку налету одной формулой на пиксель?

Не совсем понимаю что значит "разномасштабить картинку"
Но одно могу сказать точно - средний цвет любой прямоугольной области указанного вида находит за "1 формулу"