Найти изображение в изображении
Я ищу лучший способ обнаружить изображение в другом изображении. У меня есть небольшое изображение, и я хотел бы найти место, где оно появляется на большом изображении, которое на самом деле будет снимками экрана. Концептуально это похоже на «Где Уолдо?» своего рода поиск по большему изображению.
Есть ли какие-нибудь эффективные / быстрые способы сделать это? Скорость важнее памяти.
Редактировать:
«Внутреннее» изображение не всегда может иметь одинаковый масштаб, но может иметь одинаковое вращение.
Небезопасно предполагать, что изображение будет идеально содержаться в другом, пиксель за пикселем.
Должен ли он соответствовать "точно" пиксель за пикселем? А как насчет проблем с вращением и масштабированием?
@PolyThinker: Верно, я опущу этот конкретный квалификатор для вопроса.
Дубликат? stackoverflow.com/questions/297762/…
Дубликат? stackoverflow.com/questions/876142
Ответы 3
Вы можете рассматривать это как проблему с подстрокой, где символы в алфавите - это пиксели, а ваша строка - это изображение. Вам также потребуется использовать специальный символ, аналогичный переносу строки, для обозначения границы изображения.
Нужный алгоритм есть в Википедии: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Обновлять: Если вы не можете предположить, что изображение полностью содержится в другом, пиксель за пикселем, то этот подход не будет работать.
Существуют и другие, более сложные алгоритмы, основанные на той же концепции динамического программирования, что и выше, но я не буду вдаваться в них, если в этом нет необходимости.
Если изображения в формате JPEG, у вас будет головная боль :-)
Да. Это очень и очень хороший момент. Если вы не можете предположить идеальное совпадение, тогда понятие «лучший», потому что трудный и «эффективный / быстрый», становится трудным. Вам нужно будет сделать что-то, основанное на минимизации энергии / динамическом программировании.
Проголосовал против, потому что подобные методы вообще не работают с изображениями.
@Owen Не могли бы вы дать мне несколько советов о том, как обрабатывать перенос строки? В настоящее время я выполняю поиск по пикселям, аналогичный приведенному в примере кода в ссылке "Соответствие шаблонов википедии" в первом ответе, и это занимает вечность. Кто-то предложил мне изучить алгоритм Horspool, который выполняет тот же поиск строк, что и ваш алгоритм KMP. Кроме того, что не так с JPEG?
В Википедии есть статья о Соответствие шаблонов с образцом кода.
(Хотя эта страница не обрабатывает измененные масштабы, на ней есть ссылки на другие стили сопоставления, например Преобразование инвариантного элемента масштабирования)
+1, алгоритм SIFT, который я много использовал в user.cs.tu-berlin.de/~nowozin/autopano-sift, и он очень эффективен в том, что он делает, иногда даже обрабатывает искажение изображения.
Есть Java-реализация SIFT в fly.mpi-cbg.de/~saalfeld/javasift.html
Если также необходимо учитывать вращение, можно использовать Обобщенное преобразование Хафа.
Я сомневаюсь, что проблема в языке. Ключевым моментом является наличие у вас подходящего набора инструментов для обработки изображений.