Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892715 Mon, 10 Jul 2023 07:09:51 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892715 Цитата MBo @ 10.07.23, 06:58

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

Навскидку хорошей ссылки не нашёл:

https://www.nanoindustry.su/files/article_p...cle_3308_33.pdf

Для моей задачи это не нужно, решение будет гораздо проще.

Но ... тема отличная. И я знаю где ее применение возможно будет супер! Простой пример. Есть фон из повторяющихся элементов, который, например, на последнем этапе обработали градиентом освещенности. По факту структура с повторениями, но выделить в ней тайтл не представляется возможным, ибо все "портит" градиент. Предлагаемой тобою методикой возможно получится "убрать" градиент, а потом уже искать нужный тайтл. Ну это как предположение.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892714 Mon, 10 Jul 2023 06:58:05 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892714
Навскидку хорошей ссылки не нашёл:

https://www.nanoindustry.su/files/article_p...cle_3308_33.pdf]]> MBo Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892712 Sun, 09 Jul 2023 20:12:30 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892712 Цитата Qraizer @ 09.07.23, 16:23

Ну, в неком лайтовом варианте. Не?

Наверное всё же не :-?]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892711 Sun, 09 Jul 2023 16:23:43 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892711 Qraizer Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892710 Sun, 09 Jul 2023 08:49:04 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892710 Цитата Mikle @ 09.07.23, 07:46

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

Все верно! Я уже там в середине обсуждения внес правки в "свой вариант". Да, перебором и с верхнего левого угла.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892709 Sun, 09 Jul 2023 07:46:15 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892709 Накладывать картинку саму на себя субтрактивно, сдвигая попиксельно вниз до тех пор, пока не получим на пересечении нулевой результат, так находим DY, потом аналогично сдвигом вправо находим DX, тут уже можно для оптимизации уменьшить картинку по вертикали до найдённой величины DY.
Неоднозначно тут только то, что мы принимаем за нулевой результат, как считаем допуск.]]> Mikle Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892708 Sun, 09 Jul 2023 06:59:47 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892708 Цитата Profi @ 08.07.23, 13:14

1. Берем кусок, например 1/4.

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

Примеры:

1) Тайтл занимает 4/5 по ширине от большой картинки ⇒ при делении ничего не найдём
2) Большая картинка представляет собой "шахматную доску", где ячейка - пиксель. Искомый тайтл 2x2, тогда какой смысл в делении, к примеру, 4096 на 4? Не сильно легче станет, имхо.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892702 Sat, 08 Jul 2023 13:48:29 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892702 Цитата Profi @ 08.07.23, 13:14

Пытаемся найти внутри него хотя бы одну повторяющуюся область.

Не нужно всех шагов - вот этот шаг №2 нужно реализовать. Это и будет ответом в первом приближении.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892701 Sat, 08 Jul 2023 13:14:50 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892701 1. Берем кусок, например 1/4.
2. Пытаемся найти внутри него хотя бы одну повторяющуюся область.
3. Нашли - идем на шаг один.
4. Нет - смотрим, не совпадает ли область с другим куском с предыдущего шага.
5. Да - мы нашли искомый.
6. Нет (такое возможно, если исходная картинка была чуть обрезана) - начинаем чуть увеличивать найденную область и искать совпадения.]]> Profi Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892689 Sat, 08 Jul 2023 10:07:30 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892689 Цитата Profi @ 08.07.23, 09:56

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

Ну тут же решается совершенно другая задача - найти заранее известные мелкие изображения в большом.
А у меня задача иная - найти (определить) мелкие изображения, которые, собственно, заранее не известны.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892688 Sat, 08 Jul 2023 09:56:26 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892688 Цитата Majestio @ 07.07.23, 22:41

Там описан вопрос нахождения Расстояния Евклида.

Ну, надо читать чуть дальше заголовка. Вот пример, как этот алгоритм использовать.]]> Profi Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892687 Sat, 08 Jul 2023 09:05:07 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892687 Цитата Mikle @ 08.07.23, 08:59

То есть не находить...

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

Цитата Mikle @ 08.07.23, 08:59

Это всё прямоугольники, а в первой картинке можно предельно уменьшить до параллелограмма.

Мы договорились - только и строго прямоугольники.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892686 Sat, 08 Jul 2023 08:59:48 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892686 Цитата Majestio @ 08.07.23, 08:28

Большая картинка создана из штампа "3x3". Нужный нам штамп тут будет "1x1" или "3x1" или "3x2" ... (если с помощью его можно получить 3x3)

Это всё прямоугольники, а в первой картинке можно предельно уменьшить до параллелограмма.

Цитата Majestio @ 08.07.23, 08:28

В масштабированной картинке искать штамп (тайтл) по целым пикселям.

То есть не находить...]]> Mikle Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892685 Sat, 08 Jul 2023 08:28:10 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892685 Чисто интуитивно опорную ячейку хочется выбрать в середине картинки (п.2), а расширять область как-бы по спирали.
~~ADD-1:~~ По финишу найденный "штапм" возможно нужно будет корректировать, ибо в большой картинке начало "повторения" этого штампа может быть не с его координат 0,0, а возможно правее и/или ниже.

ADD-2: Нет-нет-нет - ищем строго слева-сверху! Нам же не нужно искать именно исходный тайтл, из которого сделали фон (а вдруг там замостили, а потом обрезали?). Нам нужно найти тайтл, которым можно получить фон.

Добавлено 08.07.23, 08:29

Цитата Mikle @ 08.07.23, 08:27

но на холст картинка кладётся под углом к сканлиниям

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

Добавлено 08.07.23, 08:31

Цитата Mikle @ 08.07.23, 08:27

А как на счёт нецелых размеров тайла? Это, например, если взять холст 1024*1024 и замостить его картинкой 64*64, а потом холст смасштабировать (возможно, с фильтрацией) до размера 777*777. Размер тайла получится 48.5625. Или картинка, на которой нужно искать тайлы, всегда содержит их целого (в пикселях) размера?

В масштабированной картинке искать штамп (тайтл) по целым пикселям.

Добавлено 08.07.23, 08:35

Цитата Mikle @ 08.07.23, 08:27

Что противоречит новому условию "Она получается повторением прямоугольной картинки".
Не зря говорят: "правильное формулирование задачи - это половина её решения".

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

Пример:

Большая картинка создана из штампа "3x3". Нужный нам штамп тут будет "1x1" или "3x1" или "3x2" ... (если с помощью его можно получить 3x3)]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892684 Sat, 08 Jul 2023 08:27:15 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892684 Цитата Majestio @ 08.07.23, 07:48

Должен работать на любых картинках, которые можно получить путем повторения прямоугольной картинки

Так моя картинка подходит под эти условия? Поясню. Она получается повторением прямоугольной картинки, но на холст картинка кладётся под углом к сканлиниям.
Ещё важные уточнения:
Алгоритм должен допускать некоторую погрешность (например, от сжатия JPG)?
А как на счёт нецелых размеров тайла? Это, например, если взять холст 1024*1024 и замостить его картинкой 64*64, а потом холст смасштабировать (возможно, с фильтрацией) до размера 777*777. Размер тайла получится 48.5625. Или картинка, на которой нужно искать тайлы, всегда содержит их целого (в пикселях) размера?

И в первом сообщении написано:

Цитата Majestio @ 07.07.23, 13:35

можно выбрать из нее и меньшую область, не обязательно квадратную - это предположение

Что противоречит новому условию "Она получается повторением прямоугольной картинки".
Не зря говорят: "правильное формулирование задачи - это половина её решения".]]> Mikle Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892683 Sat, 08 Jul 2023 07:48:25 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892683 Цитата Mikle @ 08.07.23, 05:27

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

Должен работать на любых картинках, которые можно получить путем повторения прямоугольной картинки, которую и нужно найти. Требование только одно, найденная картинка должна быть минимальной площади, если найдена не одна, а несколько картинок для повторения. Пример с камуфляжем - только пример.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892682 Sat, 08 Jul 2023 05:27:05 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892682 Цитата Majestio @ 07.07.23, 19:42

мне ващета алгоритм поиска нужен

Так я и спрашиваю, должен алгоритм работать на таких картинках, как я показал, или только на простых, как выше?]]> Mikle Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892681 Fri, 07 Jul 2023 22:41:15 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892681 Цитата Profi @ 07.07.23, 21:06

Вот тут описан интересный подход.

Почитал. Там описан вопрос нахождения Расстояния Евклида.
Практической пользы этого для решения моего вопроса я не наблюдаю :-?]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892680 Fri, 07 Jul 2023 21:06:08 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892680 тут описан интересный подход.]]> Profi Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892679 Fri, 07 Jul 2023 19:42:20 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892679
Mikle, но мне ващета алгоритм поиска нужен :-?]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892678 Fri, 07 Jul 2023 18:12:35 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892678 Цитата Majestio @ 07.07.23, 13:35

можно выбрать из нее и меньшую область, не обязательно квадратную - это предположение

Можно сразу вдвое урезать ширину, будет прямоугольник, а в пределе минимизации - параллелограмм.
Это всё не сложно найти автоматически, а вот, если наклонить оси, станет значительно сложнее:

3x3R.jpg (, : 215) ]]> Mikle Алгоритмы https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892671 Fri, 07 Jul 2023 13:35:28 +0000 Поиск исходной области в повторяющемся фоне https://forum.sources.ru/index.php?showtopic=436297&view=findpost&p=3892671
Поясню. Картинка большого размера создана путем повторения некоторой области. Часто говорят "замостили".
Задача по картинке этого большого размера найти (исходную область или минимальную по площади), которую можно использовать для воссоздания этой большой картинки.

Приведу один из примеров большой картинки:

3x3.jpg (, : 217)

из неё нужно получить вот такую:

1x1.jpg (, : 213)

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

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

В общем, хелп!]]> Majestio Алгоритмы