*Математика и программирование

[Hellerick]

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

[_Swetlana]

Неужели никто не знает? Вроде ещё не ночь, спать рановато. Америка не в счёт.

Предполагаю:  вокруг иностранцы, поскольку в России такие задачи под силу ребёнку.
Смотрите моё решение, затратил 2-3 минуты — возможно у кого-нибудь получится лучше.

За такие задачи Канторович нобелевскую премию получил.
(wiki/ru) Канторович,_Леонид_Витальевич

Раз уж мы этого коснулись, на ночь глядя. ЛП - медленная вещь. Многие задачи, которые допускают сетевую постановку (через графы), например, все варианты транспортной задачи, быстрее решаются алгоритмами построения потоков в сетях. Линейное программирование - универсальный метод; потоковые алгоритмы более специализированы, потому  быстрее. Но с формальной точки зрения, как бы мы не решали NP-полные задачи, линейным программированием или потоковыми алгоритмами, всё равно в худшем случае выч. сложность экспоненциальна. Просто у потоковых алгоритмов экспоненциальный взрыв отодвинут до нескольких тысяч вершин.

[Ömer]

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

Хмм, наверно нужно разложить в ряд Фурье. Фингерпринт будет содержать конечное число кофициентов при гармониках.

[Ömer]

За такие задачи Канторович нобелевскую премию получил.
(wiki/ru) Канторович,_Леонид_Витальевич

После того, как Л. В. Канторовичем был предложен оптимальный метод распила фанерного листа, этот метод в том числе попытались применить к разрезанию стальных листов. После внедрения методов оптимизации на производстве одной из фабрик инженерам удалось улучшить показатели, что привело, однако, к негативным последствиям: система социалистического планирования требовала, чтобы в следующем году план был перевыполнен, что было принципиально невозможно при имеющихся ресурсах, поскольку найденное решение было абсолютным максимумом; фабрика не выполнила план по металлолому, львиная доля которого складывалась из обрезков стальных листов. Руководство фабрики получило выговор и больше с математиками не связывалось.

[Hellerick]

Хмм, наверно нужно разложить в ряд Фурье. Фингерпринт будет содержать конечное число кофициентов при гармониках.

Звучит здорово.

Жаль, непонятно. Нам практическое применение рчдов Фурье вообще никак не объясняли.

[Ömer]

Жаль, непонятно. Нам практическое применение рчдов Фурье вообще никак не объясняли.

Схема такая.

Берём пиксельное представление картинки, т.е. функцию f(x,y) -> (R,G,B). Для каждой из цветовых компонент проделываем следующий алгоритм. Для примера возьмём компоненту R. Для неё имеем скалярную функцию:
f(x,y) -> R

Применяем к ней двумерное преобразование Фурье, т.е. находим коэффициенты ряда Фурье при разложении этой функции по какому-то ортогональному базису (обычно берутся синусы-косинусы):
http://math.stackexchange.com/questions/211689/real-valued-2d-fourier-series

(Существуют вычислительные алгоритмы, позволяющие быстро найти коэффициенты Фурье, например Fast Foruier transform)

В итоге получаем набор коэффициентов c_i,j. Для создания сжатого образа картинки берём конечный набор этих коэффициентов (меньший, чем размер исходной картинки). На этом принципе работают алгоритмы сжатия типа jpeg или mp3.

Для создания fingerprint'a можно отсортировать коэффициенты в одномерный массив, например, пронумеровав "змейкой" (имеем в виду, что чем меньше номер коэффициента, тем важнее отвечающая ему гармоника).
(wiki/en) Pairing_function#/media/File:Diagonal_argument.svg

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

[лад]

Жаль, непонятно. Нам практическое применение рчдов Фурье вообще никак не объясняли.

Схема такая.

Берём пиксельное представление картинки, т.е. функцию f(x,y) -> (R,G,B). Для каждой из цветовых компонент проделываем следующий алгоритм. Для примера возьмём компоненту R. Для неё имеем скалярную функцию:
f(x,y) -> R

Для фингерпринта это не нужно, надо брать Y (яркость, lumu). А цветные компоненты надо вообще выбрасывать, в них информации практически нет.

[Hellerick]

Берём пиксельное представление картинки, т.е. функцию f(x,y) -> (R,G,B). Для каждой из цветовых компонент проделываем следующий алгоритм. Для примера возьмём компоненту R. Для неё имеем скалярную функцию:
f(x,y) -> R

Фурье ведь работает с рядом, а не с двухмерым массивом. То есть в него надо скармливть не двухмерное изображение, а один поток пикселей, собираемый по строкам? А не получатся ли итоговые коэффициенты зависящими от размера изображения? Хотелось бы, чтобы у разных размеров одной картинки фингерпринт был один.

[Ömer]

Фурье ведь работает с рядом, а не с двухмерым массивом.

Фурье работает с функцией. В одномерном случае он преобразует функцию R->R в ряд c_i.

Существует преобразование Фурье для любых размерностей, я выше давал ссылку.
http://math.stackexchange.com/questions/211689/real-valued-2d-fourier-series

В двумерном случае, функция R² -> R преобразуется в двумерный массив с_i,j.

А не получатся ли итоговые коэффициенты зависящими от размера изображения?

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

[Ömer]

Hellerick, а как вы сделали?

[лад]

А не получатся ли итоговые коэффициенты зависящими от размера изображения?

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

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

[Hellerick]

А не получатся ли итоговые коэффициенты зависящими от размера изображения?

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

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

Для этого достаточно просто предварительно сжать изображение до стандартной миниатюры. Например, 16x16 пикселей.

[Ömer]

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

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

[лад]

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

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

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

[Ömer]

Не тот же. Вейвлеты это и есть разложение с масштабированием, грубо говоря.

То есть, вы хотите сказать, что у функции 3*f(x) будут такие же коэффициенты в вейвлет-разложении, что и у функции f(x)? Это же нелогично. Понятно, что коэффициенты всё равно будут в три раза больше.

В целом я согласен, вейвлет-базис лучше подходит для картинок и музыки. Он вроде бы лучше выделяет значимые для глаза/уха компоненты.

[лад]

Не тот же. Вейвлеты это и есть разложение с масштабированием, грубо говоря.

То есть, вы хотите сказать, что у функции 3*f(x) будут такие же коэффициенты в вейвлет-разложении, что и у функции f(x)? Это же нелогично. Понятно, что коэффициенты всё равно будут в три раза больше.

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

[Hellerick]

Hellerick, а как вы сделали?

Да я мудрствовал.

В первую очередь изображение кадрируется — чтобы избавиться от неинформативного фона.

Потом для каждого цветового уровня изображения замеряю среднее значение. Потом замеряю, а в каждой четверти средний уровень выше или ниже среднего по изображению — таким образом получаю 4 бита информации. А для трех цветовых уровней — 12 бит.

Потом такую же операцию проделываю для каждой четверти. Всего таким образом получаю 60 бит. При перекодировании в латиницу-26 эта информация умещается в 13 символах, которые добавляются спереди к названию файла.

[лад]

Hellerick, а как вы сделали?

Да я мудрствовал.

В первую очередь изображение кадрируется — чтобы избавиться от неинформативного фона.

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

Вот это излишне. Качественнее перевести изображение в YCbCr,  CbCr выкинуть, то есть вообще не считать. С Y сделать то что вы делаете. А если хочется, то приибавить средние по Cb Cr, чтобы различать цвета картинок. Так сжатие будет сильнее, и качество картинки будет передаваться лучше.

[Тайльнемер]

CbCr выкинуть, то есть вообще не считать.

Тут ещё неизвестно, что сильнее влияет на «похожесть». Может захотеться сгруппировать жёлтые картинки с жёлтыми, красные — с красными и т. д.

[Тайльнемер]

Потом для каждого цветового уровня изображения замеряю среднее значение. Потом замеряю, а в каждой четверти средний уровень выше или ниже среднего по изображению — таким образом получаю 4 бита информации. А для трех цветовых уровней — 12 бит.

Потом такую же операцию проделываю для каждой четверти.

Это практически  и есть фурье.

[лад]

Потом для каждого цветового уровня изображения замеряю среднее значение. Потом замеряю, а в каждой четверти средний уровень выше или ниже среднего по изображению — таким образом получаю 4 бита информации. А для трех цветовых уровней — 12 бит.

Потом такую же операцию проделываю для каждой четверти.

Это практически  и есть фурье.

Нет. Это больше похоже на преобразование Уолша(Адамара) или вейвлет Хаара. Коэффициентами Фурье тут и не пахнет.

[Hellerick]

Задачка из моей темы Проект автомобильных номеров России

Чтобы автомобильные номера выдавались не по порядку, а максимально разными, я их порядок перепутываю по такой формуле:

n = p*128142731%207339264,

где:
% — операция остатка от деления:
p — изначальный порядковый номер;
n — число, определяющее, что именно будет написано на собственно номерном знаке;
207339264 — теоретическое максимальное количество выдаваемых номеров;
128142731 — простое число, используемое для «перетасовывания» номеров (выбрано так, чтобы 207339264/128142731 было похоже на золотое сечение).

Но что если мне наоборот хочется из n получить p?

Я составил для этого формулу, но сам не понимаю, как и почему она работает. Что-то у меня мозги вообще в теме остатка от деления плохо работают.

Как бы вы находили p?

[Upliner]

Как бы вы находили p?

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

[Hellerick]

Кто-нибудь пытался освоить разведение нейросетей?

[Тайльнемер]

Кто-нибудь пытался освоить разведение нейросетей?

Вадимий щас этим занимается в универе. Если есть вопросы, могу ему передать.