roboforum.ru

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

Виталий писал(а):но вот в оценке W*H*log2(W*H) я сумневаюсь. Не учтены сравнения как мне кажется.

Это оценка требуемого объема памяти, что там сомневаться?

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

Полутоновые изображения по сути приближаются к изображениям типа "шум", на них по моему все методы распознавания валятся, или я не прав?

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

Виталий писал(а):Насчет полутоновых изображений - почти все методы распознавания с ними и работают.

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

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

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

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

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

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

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

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

Было бы интересно конкретно от вас услышать мнение по существу алгоритма, а не по поводу возможностей его продажи.

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

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

Куда уж лучше вообще тупо изображения попиксельно накладывать, раз уж на то пошло.

Не могли бы вы с Виталием привести функцию расстояния для гистограмм, которая будет эффективно по времени считаться и даст хорошую оценку для среднеквадратичного отклонения между двумя картинками?

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

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

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

Николай_Алексеевич писал(а):Начал уже пробовать создавать такое... но времени маловато свободного.

По твоему - мы берем квадрат скажем 50х50 и находим средний цвет для этого.

Не понял чем продиктован выбор квадрата 50х50 у меня такого не было.

Николай_Алексеевич писал(а):Можно даже использовать интегральное изображение (возможно).

Не можно, а нужно. Если я конечно правильно понял, что вы под этими словами имели в виду, как считать знаю, а названия для этого в техническом зрении - не знаю

Николай_Алексеевич писал(а):Далее можно даже масштабировать окно поиска скажем на 1.25 каждый раз. Но на мой взгляд (если я правильно понял) не даст высокого процента обнаружения.

Тут вопрос открытый - надо рассчеты делать по метрикам явно, там всё считабельно, вопрос не в том какой % обранужения это даст, вопрос на сколько получится отсекать по времени обработки, вот что важно

Николай_Алексеевич писал(а):Надо просто сделать и посмотреть результат.

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

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

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

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

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

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

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

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

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 значений гистограмму делать.
Да и современные процессоры умеют конфейером эт дела обсчитывать вроде (но я толком не знаю как).

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

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

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

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

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

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

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

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 формулу"