Обнаружьте местоположение изображения в рамках увеличенного изображения
Как Вы обнаруживаете местоположение изображения в рамках увеличенного изображения? У меня есть неизмененная копия изображения. Это изображение затем изменяется на произвольное разрешение и помещается случайным образом в рамках большого количества увеличенного изображения, которое имеет произвольный размер. Никакие другие преобразования не проводятся на получающемся изображении. Код Python был бы идеален, и он, вероятно, потребует libgd. Если Вы будете знать о хорошем подходе к этой проблеме, то Вы получите +1.
4 ответа
Есть быстрое и грязное решение, и это просто перемещение окна по целевому изображению и вычисление некоторой степени сходства в каждом месте, затем выбор место с наибольшим сходством. Затем вы сравниваете сходство с пороговым значением; если оценка выше порогового значения, вы заключаете, что изображение есть и это местоположение; если оценка ниже порога, то изображения нет.
В качестве меры сходства можно использовать нормализованную корреляцию или сумму квадратов разностей (также известную как норма L2). Как уже упоминалось, это не касается изменений масштаба. Таким образом, вы также несколько раз масштабируете исходное изображение и повторяете описанный выше процесс с каждой масштабированной версией. В зависимости от размера входного изображения и диапазона возможных масштабов этого может быть достаточно, и его легко реализовать.
Правильное решение - использовать аффинные инварианты. Попробуйте поискать «стереофоническое соответствие с широкой базой», люди смотрели на эту проблему в этом контексте. Обычно используются следующие методы:
Предварительная обработка исходного изображения
- Запуск «детектора точек интереса». Это позволит найти на изображении несколько точек, которые легко локализовать, например углы. Детекторов много, детектор под названием «харрис-аффинный» работает хорошо и довольно популярен (так что реализации, вероятно, существуют). Другой вариант - использовать детектор разности гауссианов (DoG), он был разработан для SIFT и тоже хорошо работает.
- В каждой точке интереса извлечь небольшое фрагмент изображения (например, 30x30 пикселей).
- Для каждого фрагмента изображения вычислить «дескриптор», некоторое представление содержимого изображения в этом окне. Опять же, существует множество дескрипторов. Следует обратить внимание на то, насколько хорошо дескриптор описывает содержимое изображения (вы хотите, чтобы два дескриптора совпадали, только если они похожи), и насколько он инвариантен (вы хотите, чтобы он оставался таким же даже после масштабирования). В вашем случае я бы рекомендовал использовать SIFT. Он не так инвариантен, как некоторые другие дескрипторы, но может хорошо справляться с масштабированием, и в вашем случае масштаб - единственное, что изменяется.
В конце этого этапа у вас будет набор дескрипторов.
Тестирование (с новым тестовым изображением).
- Сначала вы запускаете тот же детектор точек интереса, что и на шаге 1, и получаете набор точек интереса. Вы вычисляете тот же дескриптор для каждой точки, как указано выше. Теперь у вас есть набор дескрипторов для целевого изображения.
- Затем вы ищите спички. В идеале для каждого дескриптора исходного изображения в целевом изображении должен быть какой-то довольно похожий дескриптор. (Поскольку целевое изображение больше, будут также «оставшиеся» дескрипторы, то есть точки, которые не соответствуют чему-либо в исходном изображении.) Таким образом, если достаточное количество исходных дескрипторов соответствует с достаточным сходством, то вы знаете, что цель - это там. Более того, поскольку дескрипторы зависят от местоположения, вы также будете знать, где в целевом изображении находится исходное изображение.
http://en.wikipedia.org/wiki/Autocorrelation - мой первый инстинкт.
Вам, вероятно, нужна кросс-корреляция. (Автокорреляция - это корреляция сигнала с самим собой; кросс-корреляция - это корреляция двух различных сигналов.)
Что корреляция делает для вас вместо простой проверки точных совпадений, так это то, что она скажет вам, где находятся лучшие совпадения и насколько они хороши. Обратная сторона заключается в том, что для двухмерного изображения это что-то вроде O(N^3), и это не такой уж простой алгоритм. Но это волшебство, как только вы заставите его работать.
EDIT: Ааргх, вы указали произвольный размер. Это сломает любой алгоритм, основанный на корреляции. Извините, теперь вы за пределами моего опыта, и SO не позволяет мне удалить этот ответ.
Посмотрите на Scale-Invariant Feature Transforms; существует множество различных вариантов, которые могут быть более или менее приспособлены к типу изображений, с которыми вы работаете.