На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
Друзья! С Днём Защитника Отечества!
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Поиск исходной области в повторяющемся фоне
    Всем привет!

    Поясню. Картинка большого размера создана путем повторения некоторой области. Часто говорят "замостили".
    Задача по картинке этого большого размера найти (исходную область или минимальную по площади), которую можно использовать для воссоздания этой большой картинки.

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

    Прикреплённая картинка
    Прикреплённая картинка


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

    Прикреплённая картинка
    Прикреплённая картинка


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

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

    В общем, хелп!
      Цитата Majestio @
      можно выбрать из нее и меньшую область, не обязательно квадратную - это предположение

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

      Прикреплённая картинка
      Прикреплённая картинка
        Представленную большую картинку я получил путем склеивания маленьких 9 раз (в 3x3). Но подозреваю, что большую картинку можно получить и из более мелкого "штампа", ибо и на изначальной маленькой картинке видны повторяющиеся фигуры ...

        Mikle, но мне ващета алгоритм поиска нужен :-?
          Вот тут описан интересный подход.
            Цитата Profi @
            Вот тут описан интересный подход.

            Почитал. Там описан вопрос нахождения Расстояния Евклида.
            Практической пользы этого для решения моего вопроса я не наблюдаю :-?
              Цитата Majestio @
              мне ващета алгоритм поиска нужен

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

                Должен работать на любых картинках, которые можно получить путем повторения прямоугольной картинки, которую и нужно найти. Требование только одно, найденная картинка должна быть минимальной площади, если найдена не одна, а несколько картинок для повторения. Пример с камуфляжем - только пример.
                  Цитата Majestio @
                  Должен работать на любых картинках, которые можно получить путем повторения прямоугольной картинки

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

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

                  Что противоречит новому условию "Она получается повторением прямоугольной картинки".
                  Не зря говорят: "правильное формулирование задачи - это половина её решения".
                    ADD: У мне уже примерно сложился возможный алгоритм, увы - перебором:
                    1. Выбираем "опорную" точку (пиксель), откуда начинаем поиск
                      • Верхний левый угол
                      • Центр картинки
                      • Случайная координата
                    2. Попеременно увеличиваем ширину и высоту выбранной области, и смотрим - повторяется ли полученная область слева (и справа)
                    3. Если слева и снизу достигнуты пределы размеров - сдвигаем опорную точку, и повторяем поиск
                    4. Сдвиг опорной точки осуществляем исходя из начального его выбора:
                      • Вниз-вправо
                      • Вверх-влево
                      • Вверх-влево
                    Чисто интуитивно опорную ячейку хочется выбрать в середине картинки (п.2), а расширять область как-бы по спирали.
                    ADD-1: По финишу найденный "штапм" возможно нужно будет корректировать, ибо в большой картинке начало "повторения" этого штампа может быть не с его координат 0,0, а возможно правее и/или ниже.

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

                    Добавлено
                    Цитата Mikle @
                    но на холст картинка кладётся под углом к сканлиниям

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

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

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

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

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

                    Пример:

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

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

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

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

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

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

                        Мы договорились - только и строго прямоугольники.
                          Цитата Majestio @
                          Там описан вопрос нахождения Расстояния Евклида.

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

                            Ну тут же решается совершенно другая задача - найти заранее известные мелкие изображения в большом.
                            А у меня задача иная - найти (определить) мелкие изображения, которые, собственно, заранее не известны.
                              Ну, так можно адоптировать:
                              1. Берем кусок, например 1/4.
                              2. Пытаемся найти внутри него хотя бы одну повторяющуюся область.
                              3. Нашли - идем на шаг один.
                              4. Нет - смотрим, не совпадает ли область с другим куском с предыдущего шага.
                              5. Да - мы нашли искомый.
                              6. Нет (такое возможно, если исходная картинка была чуть обрезана) - начинаем чуть увеличивать найденную область и искать совпадения.
                                Цитата Profi @
                                Пытаемся найти внутри него хотя бы одну повторяющуюся область.

                                Не нужно всех шагов - вот этот шаг №2 нужно реализовать. Это и будет ответом в первом приближении.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0585 ]   [ 19 queries used ]   [ Generated: 24.02.24, 12:40 GMT ]