У нас есть фрагмент фото. Как найти его координаты на полном фото?

Question

[Stanislav111]

Есть фрагмент фото (изображение 1).
Есть полное фото (изображение 2).
Какой наиболее простой способ получить координаты этого фрагмента на полном фото?
Пропорции одинаковые, никакую обработку не проходили.

Comments

[Hemul GM]

Размеры изображений так скажем одного размера? Т.е. фрагмент соответствует размеру области на полной картинке?

[Сергей Соколов]

Уточнение предыдущего комментария: фрагмент попиксельно идентичен искомой части целого изображения?

Или же, скажем, целое изображение уменьшено, всего 650x488, а фрагмент при этом четче-крупнее, 500x500 — т.е. появляется ещё одна неопределённость: scale.

И про искажения тогда уж уточню: фрагмент на нужно поворачивать на неизвестный угол или ещё как-то искажать, чтобы он «лёг» на исходную картинку?

Ещё вопросы:
фрагмент гарантированно присутсвует на большом фото, или его может и не быть?
фрагмент единичен или их может быть несколько (паттерн)?

[Stanislav111]

Hemul GM, одного размера

[Stanislav111]

Сергей Соколов, Может и не быть. Единичен.

Answer 1

[dom1n1k]

Если фрагмент строго попиксельно идентичен куску большого изображения, то всё просто.
Берется первый ряд пикселей фрагмента и проверяется его вхождение в ряды пикселей исходника.
То есть это фактически задача поиска подстроки в большой строке. Это суперклассическая задача, по ней написаны тонны научных работ, разработано стопиццот оптимизированных алгоритмов, многие реализованы в библиотеках. Да хоть википедию можно смотреть:
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D...
Если найден - проверяются последующие ряды.

Вот если вхождение нестрогое (например, фрагмент отмасштабирован, или яркость не совпадает, или просто немного покоцан jpeg-пересжатием) - тогда всё сильно сложнее.

Comments

[Stanislav111]

Видимо, так и буду делать.
Я думал, что есть библитеки для этого готовые и заодно хотел другие способы узнать.
У JS-а очень долго работает поиск. Поэтому мне даже сложно представить, сколько времени займет поиск фрагмента 200x200 на холсте 1000x500.
Посмотрю, может на плюсах напишу этот участок кода.

[Interface]

Stanislav111, поиск не должен быть супер долгим. Я набросал черновик кода (супер банальный брутфорс), на моем ноутбуке фрагмент 500х400 на холсте 2848х4288 находится примерно за 400мс. Возможно, если у вас поиск происходит значительно дольше - дело в том, что вы неэффективно читаете данные.

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

Скажите, что для вас медленно.

Answer 2

[towin]

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

Comments

[mbenner]

Самый просто реализуемый вариант. Делай так, а дальше смотри устраивает ли скорость

[Сергей Соколов]

хорошо бы брать самый «необычный» пиксель.
Иначе. например, если левый верхний пиксель – небо, поиск будет долгим.

[Robur]

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

[Сергей Соколов]

Robur, тс'у уточняющие вопросы заданы, но пока без ответа

[tester12]

Сергей Соколов,

хорошо бы брать самый «необычный» пиксель.

Для этого придётся пройтись по всем пикселям, составляя рейтинг "необычности".

[Сергей Соколов]

tester12, всем пикселям не целого изображения, а только искомого фрагмента.

Answer 3

[hint000]

https://ru.wikipedia.org/wiki/Корреляция_цифровых_...
и дальше гуглёж по теме

Answer 4

[xmoonlight]

Ясно, что нужно начинать с крупных объектов.
На данном примере - это: небо, песок и вода.
1. Ищем линию границ крупных объектов (обводка) и находим значимые "точки" (круговая область с автоматическим радиусом): те, где линия изгибается уникально.
2. Производим сопоставление этих точек на фрагменте и полном изображении, используя повороты только этих небольших круговых областей в ч/б режиме.
3. При совпадении любых двух из них (фрагмента с полным изображением) - мы сразу же знаем точные координаты искомого фрагмента на полном изображении.

Comments

[Сергей Соколов]

коллаж из QR-кодов

[xmoonlight]

Сергей Соколов, :)
ну, смысл-то, да, похожий, но крутить же каждую область нужно для проверки совмещения...

Answer 5

[Александр]

Внесу вклад для запутывания ...
Тут чистая математика с теорией вероятности (кажись) и численных методов.
Берешь Хеш фрагмента и сравниваешь с Хешем участков полного фото.
Есть программы для 3-D панорам которые сшивают плоские фото в объемное изображение. Те же принципы.

Comments

[Interface]

Расскажите, что вы имеете в виду под "Берешь Хеш фрагмента"? Фрагмент - это все срезы изображения (для поиска 10х10 в картинке 1000х1000 их будет 990х990 = 980100 штук)?

[Александр]

Interface,
Да. Почти. Берем Хеш-функцию от 10х10 и сравниваем с 980100 Хеш-функций ))). Так быстрее чем сравнение по "пиксельно" (тут подвох), учитывая что сравнивать надо не jpg, а более низкого уровня Bitmap из за разновидности схем сжатия jpg.
Учитывайте что если это в пикселях 1000х1000, то надо умножить на 2-4 раза.

[Interface]

Александр, я боюсь что это будет намного дольше. Вероятность того что цвет 1-го пикселя совпадет на самом деле не такая уж большая, поэтому проверяя только один пиксель, можно отсеять большое количество неподходящих фрагментов. В вашем случае вместо операции сравнения 4 байтов будет подсчет хэша.

[Александр]

Interface,
Тут накладные расходы связаны с тем, что при решении в "лоб" не обходим цикл внутри цикла: Сравниваем 1-е байты - совпали - Сравниваем 2-е байты - совпали - Сравниваем 3-е байты - совпали - .... Сравниваем 99-е байты - НЕ совпал. Зараза ))) . Смещаем на 1 байт и заново проверяем все 99 байт ...

Я не зря добавил в ответ теорию вероятности ))). Берем картинку 10х10 и складываем все цвета и превращаем в 1 пиксель. Далее в большой картинке вырезаем квадрат 10х10 и превращаем в 1 пиксель ... Если пиксели одинаковы то есть вероятность что это то что мы ищем. Берем Хеш-функцию от обоих массивов и сравниваем. Сравнить 100 пикселей возможно проще, а если искомое изображение 500х500 то лучше Хеш-функцией.

[Interface]

Александр, я понимаю в чем разница подходов, я просто сомневаюсь, что вычисление ~n^2 хэш сумм не убьет весь профит с самого начала

Answer 6

[Александр Таратин]

opencv surf
Раз в тегах есть nodejs, то можно воспользоваться https://www.npmjs.com/package/opencv4nodejs

Answer 7

[mayton2019]

Давайте сразу самую хардкорную постановку. Изображение было скейлировано. Тоест по-пиксельное сравнение вам ничего не даст. Нужно что-то более умное.

Comments

[Karpion]

«Выглядит похоже». Как работает перцептивный хэш

Answer 8

[Дмитрий Макаров]

Еще совет предварительно картинку ужать обе пропорционально и градиентом серого сделать сделать, это ускорит предварительный поиск потом уже уточнять края