roboforum.ru

Есть два изображения разных размеров. Одно из изображений (меньшее) является промасштабированным участком другого (большего) изображения. Необходимо найти коэффициент масштабирования и смещение данного участка изображения.
Интересует следующее:
1. как решить данную задачу с помощью библиотеки OpenCV.
2. какие алгоритмы можно применить для решения данной задачи своими средствами.

А. Надеюсь повороты и отражения не использовались?

Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.

=DeaD= писал(а):А. Надеюсь повороты и отражения не использовались?

Нет.

=DeaD= писал(а):Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.

1. А какие существуют алгоритмы нахождения "особых точек"? 2. Как можно понять, что особых точек в изображении нет?

Degun писал(а):

=DeaD= писал(а):Б. Если масштабирование не сильное, то можно попробовать найти фрагмент по "особым точкам", но если таких точек не будет в масштабированном фрагменте - тогда вы почти гарантированно "попали" на полный перебор.

1. А какие существуют алгоритмы нахождения "особых точек"? 2. Как можно понять, что особых точек в изображении нет?

GoodFeaturesToTrack - как пример функции из OpenCV, отлавливающей отличные точки для совмещения.

Вообще поищите по словам Feature Point Detection

А еще можно по гистограммам поискать если не нужно особой надежности.

Виталий писал(а):А еще можно по гистограммам поискать если не нужно особой надежности.

А поподробней можно каким образом искать по гистограммам.

Поподробней - сравнивать не изображения а их гистограммы.

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

Например средние значения 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]

=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]

Такое ускорение конечно хорошо, но всё же полный перебор остаётся. А не в курсе есть ли такие алгоритмы, которые позволяют сопоставлять объекты на двух изображениях после их обработки как я уже написал выше?