Есть два изображения разных размеров. Одно из изображений (меньшее) является промасштабированным участком другого (большего) изображения. Необходимо найти коэффициент масштабирования и смещение данного участка изображения.
Интересует следующее:
1. как решить данную задачу с помощью библиотеки OpenCV.
2. какие алгоритмы можно применить для решения данной задачи своими средствами.
roboforum.ru
Технический форум по робототехнике.
Совмещение двух изображений
А. Надеюсь повороты и отражения не использовались? 
Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.
Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.
=DeaD= писал(а):А. Надеюсь повороты и отражения не использовались?
Нет.
=DeaD= писал(а):Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.
1. А какие существуют алгоритмы нахождения "особых точек"? 2. Как можно понять, что особых точек в изображении нет?
Degun писал(а):=DeaD= писал(а):Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.
1. А какие существуют алгоритмы нахождения "особых точек"? 2. Как можно понять, что особых точек в изображении нет?
GoodFeaturesToTrack - как пример функции из OpenCV, отлавливающей отличные точки для совмещения.
Вообще поищите по словам Feature Point Detection
Виталий писал(а):А еще можно по гистограммам поискать если не нужно особой надежности.
А поподробней можно каким образом искать по гистограммам.
Кстати, да, если изображение не искажено по цветам (а иначе гистограммы тоже не катят), а только масштабированно, то можно ввести оценочные функции, инвариантные относительно масштабирования и легко рассчитываемые по частичным суммам из прямоугольника задаваемом парой "верхний левый угол - точка на картинке", и искать по ним.
Например средние значения R, G, B выцепить и по ним искать.
Оценка производительности - если картинка, в которой ищем, размером N*N, тогда скорость поиска можно улучшить до O(N^4) практически, если очень повезет, вместо O(N^6) при полном переборе.
Например средние значения R, G, B выцепить и по ним искать.
Оценка производительности - если картинка, в которой ищем, размером N*N, тогда скорость поиска можно улучшить до O(N^4) практически, если очень повезет, вместо O(N^6) при полном переборе.
Виталий писал(а):Поподробней - сравнивать не изображения а их гистограммы.
При переходе от изображения к его гистограмме теряется информация о пространственном расположении пикселей. Остаётся только информация о статистике цветов пикселов изображения. Если одно изображение является всего лишь промасштабированной версией другого, то в этом случае действительно можно узнать коэффициент масштабирования как корень из усреднения отношений элементов гистограмм двух изображений. Но конкретно в моём случае одно изображение является промасштабированным участком другого изображения. Как в таком случае можно вычислить коэффициент масштабирования и смещение участка изображения на основе гистограмм, где очевидно требуется информация именно о пространственном расположении пикселей?
=DeaD= писал(а):Degun писал(а):1. А какие существуют алгоритмы нахождения "особых точек"? 2. Как можно понять, что особых точек в изображении нет?
GoodFeaturesToTrack - как пример функции из OpenCV, отлавливающей отличные точки для совмещения.
Вообще поищите по словам Feature Point Detection
Меня вообще-то интересует следующее. Допустим я уже нашёл на одном и на другом изображениях особые области для сопоставления их друг с другом и пронумеровал их. Делается это путём сегментации с глобальным порогом, который разделяет все пикселы изображения на относящиеся или к фону или к областям (объектам) изображения. Теперь мне необходим алгоритм сопоставления областей этих двух изображений. Т. е. необходим такой алгоритм, который бы нашёл бы, например, что область с номером 3 на первом изображении соответствует области 5 на втором, а область с номером 7 на первом соответствует области 2 на втором и т. д. В принципе достаточно 4 таких сопоставления, чтобы найти параметры оптимального аффинного преобразования (усечённой его версии не поддерживающего вращения), которые и будут ответом на мою задачу.
=DeaD= писал(а):Кстати, да, если изображение не искажено по цветам (а иначе гистограммы тоже не катят), а только масштабированно, то можно ввести оценочные функции, инвариантные относительно масштабирования и легко рассчитываемые по частичным суммам из прямоугольника задаваемом парой "верхний левый угол - точка на картинке", и искать по ним.
Не совсем понял мысль. Можно пояснить как-то более яснее.
=DeaD= писал(а):Например средние значения R, G, B выцепить и по ним искать.
Допустим для облегчения задачи, что изображения являются полутоновыми серыми.
Degun писал(а):=DeaD= писал(а):Кстати, да, если изображение не искажено по цветам (а иначе гистограммы тоже не катят), а только масштабированно, то можно ввести оценочные функции, инвариантные относительно масштабирования и легко рассчитываемые по частичным суммам из прямоугольника задаваемом парой "верхний левый угол - точка на картинке", и искать по ним.
Не совсем понял мысль. Можно пояснить как-то более яснее.
Есть картинка X*Y, сохранённая в массиве pic[x][y][c], x из 0..X-1, y из 0..Y-1, c из 0..2 (две координаты и номер цвета).
Заведём массив picsum[x][y][c] по правилу picsum[x][y][c]=Сумма всех pic[i][j][c] для i из 0..x, j из 0..y.
Тогда среднее значение цвета c на прямоугольнике x1,y1,x2,y2 (x1<x2, y1<y2) вычисляется за 1 ход как (picsum[x2][y2][c]-picsum[x1][y2][c]-picsum[x2][y1][c]+picsum[x1][y1][c])/( (x2-x1+1)*(y2-y1+1) ).
Сравниваем его со средним значением этого цвета на искомом фрагменте и если все 3 компоненты не сильно отклонены, тогда начинаем сверку попиксельную, чем сильно экономим количество вариантов, подвергающееся тупому перебору.
Degun писал(а):=DeaD= писал(а):Например средние значения R, G, B выцепить и по ним искать.
Допустим для облегчения задачи, что изображения являются полутоновыми серыми.
Это как раз в вашем случае - усложнение
Сравниваем его со средним значением этого цвета на искомом фрагменте и если все 3 компоненты не сильно отклонены, тогда начинаем сверку попиксельную, чем сильно экономим количество вариантов, подвергающееся тупому перебору.
Вот примерно это я имел ввиду =)
Как в таком случае можно вычислить коэффициент масштабирования и смещение участка изображения на основе гистограмм, где очевидно требуется информация именно о пространственном расположении пикселей?
Пробежаться окошком по изображению. И так с несколькими масштабами... можно даже подумать насчет адаптивного "шага" перемещения окна.
Кстати, массив picsum[][][] заполняется за время пропорциональное количеству пикселей на картинке:
picsum[x][y][c]=pic[x][y][c]+picsum[x-1][y][c]+picsum[x][y-1][c]-picsum[x-1][y-1][c]
picsum[x][y][c]=pic[x][y][c]+picsum[x-1][y][c]+picsum[x][y-1][c]-picsum[x-1][y-1][c]
=DeaD= писал(а):Кстати, массив picsum[][][] заполняется за время пропорциональное количеству пикселей на картинке:
picsum[x][y][c]=pic[x][y][c]+picsum[x-1][y][c]+picsum[x][y-1][c]-picsum[x-1][y-1][c]
Такое ускорение конечно хорошо, но всё же полный перебор остаётся. А не в курсе есть ли такие алгоритмы, которые позволяют сопоставлять объекты на двух изображениях после их обработки как я уже написал выше?