Привет, Всем!
Даны два снимка в формате BMP: первый снимок имеет, например, размер 512х1024, а второй — 1200х2048. Каждый из них по содержанию, одинаков, но разница есть, например, первый — снят год назад, а второй — сегодня и ещё, снимок м.б. разного масштаба. На первом снимке мышью выводим квадратик 24х24, а затем во втором — квадратик 96х96. Требуется: во втором снимке, в квадрате 96х96 найти ту область, кот. выбралась в первом снимке. Надо перевести координаты квадрата 24х24, как и квадрат 96х96 в матрицы. А затем, во втором квадрате "по-пиксельно прогнать" первый квадрат. Трабла в том, как перевести координаты квадратика в матрицу и как учесть разницу в масштабах...???? Помогите, пожалуйста. Спасибо.

Здравствуйте, Аноним, Вы писали:

А> Привет, Всем!
А>Даны два снимка в формате BMP: первый снимок имеет, например, размер 512х1024, а второй — 1200х2048. Каждый из них по содержанию, одинаков, но разница есть, например, первый — снят год назад, а второй — сегодня и ещё, снимок м.б. разного масштаба. На первом снимке мышью выводим квадратик 24х24, а затем во втором — квадратик 96х96. Требуется: во втором снимке, в квадрате 96х96 найти ту область, кот. выбралась в первом снимке. Надо перевести координаты квадрата 24х24, как и квадрат 96х96 в матрицы. А затем, во втором квадрате "по-пиксельно прогнать" первый квадрат. Трабла в том, как перевести координаты квадратика в матрицу и как учесть разницу в масштабах...???? Помогите, пожалуйста. Спасибо.

Масштабирование — это афинное преобразование, любое из ктр. может быть выполнено след. образом:

Строится матрица преобразования и, затем, каждая точка картинки (её координаты) домножается на эту матрицу...
Любое преобразование может быть выполнено с помощью комбинации простейших преобразований: поворота R, сдвига T, васштабирования S и отражения M. Например, нужно повернуть вектор V на 5 градусов вокруг точки (x, y, z): V*(T(-x, -y)*R(5)*T(x, y))
Матрица преобразования — это квадратная матрица размерности на 1 больше размерности пространства. Для 2D преобраззований это матрица 3x3, для 3D 4x4 и т. д.
Вектор координат дополняется 1: (x, y, 1) — 2D, (x, y, z, 1) — 3D ...

Матрицы простейших преобразований (2D):
1) вращение R(fi):
cos(fi) sin(fi) 0
-sin(fi) cos(fi) 0 fi — угол поворота
0 0 1
2) масштабирование S(sx, sy):
sx 0 0
0 sy 0 sx>0, sy>0
0 0 1
3) отражение M:
1 0 0
0 -1 0
0 0 1
4) сдвиг T(dx, dy):
1 0 0
0 1 0
dx dy 1

Подробности можно найти в любой книге по компьютерной графике или поиском по rsdn-у — тема неоднократно обсуждалась

Здравствуйте, GarikTot, Вы писали:
GT>Масштабирование — это афинное преобразование, любое из ктр. может быть выполнено след. образом:
GT>Строится матрица преобразования и, затем, каждая точка картинки (её координаты) домножается на эту матрицу...
GT>Любое преобразование может быть выполнено с помощью комбинации простейших преобразований: поворота R, сдвига T, васштабирования S и отражения M. Например, нужно повернуть вектор V на 5 градусов вокруг точки (x, y, z): V*(T(-x, -y)*R(5)*T(x, y))
GT>Матрица преобразования — это квадратная матрица размерности на 1 больше размерности пространства. Для 2D преобраззований это матрица 3x3, для 3D 4x4 и т. д.
GT>Вектор координат дополняется 1: (x, y, 1) — 2D, (x, y, z, 1) — 3D ...
GT>Матрицы простейших преобразований (2D):
GT>1) вращение R(fi):
GT>cos(fi) sin(fi) 0
GT>-sin(fi) cos(fi) 0 fi — угол поворота
GT>0 0 1
GT>2) масштабирование S(sx, sy):
GT>sx 0 0
GT>0 sy 0 sx>0, sy>0
GT>0 0 1
GT>3) отражение M:
GT>1 0 0
GT>0 -1 0
GT>0 0 1
GT>4) сдвиг T(dx, dy):
GT>1 0 0
GT>0 1 0
GT>dx dy 1
GT>Подробности можно найти в любой книге по компьютерной графике или поиском по rsdn-у — тема неоднократно обсуждалась

Спасибо за отклик от Анонима, он же Scherhan
Программировать графику недавно начала...Вот и пытаюсь, сие гранит грызть. Пишу на Билдере. У меня снимки представлены в плоскости, т.е. в координатах X,Y. Первое, мне надо понять, как перевести координаты выделенного квадрата в матрицу???
Спасибо за внимание. Пока

Здравствуйте, Scherhan, Вы писали:


S>Спасибо за отклик от Анонима, он же Scherhan
S>Программировать графику недавно начала...Вот и пытаюсь, сие гранит грызть. Пишу на Билдере. У меня снимки представлены в плоскости, т.е. в координатах X,Y. Первое, мне надо понять, как перевести координаты выделенного квадрата в матрицу???
S>Спасибо за внимание. Пока

Я не совсем понимаю — зачем переводить координаты выделенного квадрата в матрицу?
И каким образом снимки заданы на плоскости? Это массив? TBitmap? Или что?

Предположим, задан двумерный массив:

COLORREF img[Width][Height]; // можно и TColor вместо COLORREF

Width и Height — ширина и высота снимка соответственно
Верхний-левый угол снимка — точка img[0][0], поэтому, если координаты выделенного квадрата, допустим (10, 10) — (20, 20), то нам и нужны точки с img[10][10] по img[20][20]. В этом случае код обработки (масштабирования) этого фрагмента будет выглядеть примерно так:

// M - матрица масштабирования (см. предыдущий постинг)
// TVector - вектор (x, y), должна быть определена операция умножения матрицы на вектор
TVector tl(10, 10); // верхний левый
TVector br(20, 20); // нижний правый
tl *= M; br *= M;
int w = br.x - tl.x; h = br.y - tl.y; // размерность нового массива
COLORREF *buf = new COLORREF[w*h];
M *= T(-tl.x, -tl.y); // домножаем на матрицу сдвига, чтобы новый массив начинался с точки (0, 0)
TMatrix IM = Inverse(M); // обращаем матрицу - операция так же должна быть определена
for(int y=0; y<h; y++){
   for(int x=0; x<w; x++){
      TVector V(x, y); V *= IM; // получаем координаты точки результирующего изображения (x, y) в исходном
      buf(w*y + x) = img[V.x][V.y];
   }
}

нетрудно заметить, что в данном случае масштабирование работает несовсем корректно: при уменьшении масштаба, часть точек исходного изображения просто пропадёт, а при увеличении — на результирующем изображении будут "одинокие" пиксели в окружении "пустоты"...

Бороться с этой проблемой можно таким образом:
1)при увеличении масштаба заполнять все точки от (x, y) до (x + sx, y + sy) одним цветом, получая блочную структуру (то же самое делает стандартная WINAPI'шная ф-ция StretchDIBits())
2)Использовать различные алгоритмы фильтрации

Что конкретно использовать (и использовать ли вообще) зависит от конкретной задачи... Как предполагается в дальнейшем сравнивать снимки (фрагменты снимков)? Вобщем — это тема отдельного разговора

зы.
Настоятельно советую поискать на rsdn'е — похожие вопросы уже были, причём недавно... Приводились примеры и интересные ссылки по данной тематике
зы. 2
Я когда-то писал нечто подобное... Если интересно могу поискать

Здравствуйте, GarikTot, Вы писали:
Спасибо за отклик
GT> Я когда-то писал нечто подобное... Если интересно могу поискать
Да, мне очень интересно, т.к. недавно начала работать с программированием графики. Обычно работала с БД, а тут...что поделаешь, работа
Хочу пояснить общую постановку задачи:
В двух окнах отображены снимки. Например, снимки твоего района: первый снимок сделан 10 ноября прошлого года
с самолёта, а второй снимок сделан 23 августа этого года со спутника. На первом снимке виден (не весь район)
твой дом, а на втором — весь район. На первом снимке выбираем область с твоим домом, где кликом мышью, рисуется
квадрат 24х24. Далее, на втором снимке выбираем интересующую область, где кликом мышью , рисуется квадрат 96х96.
В квадрате 96х96 второго снимка требуется найти выделенную область 24х24 (с твоим домом). Если в квадрате 96х96
находится область квадрата 24х24, то выделить его местоположение, а иначе повторить процесс выделения квадрата 96х96
и т.д. до тех пор пока не будет найдена выбранная область квадрата 24х24 в квадрате 96х96.
Половину задачи уже сделала, но самую важную часть — никак...
Спасибо за внимание. До свидания.

Извиняюсь за продолжительное молчание — проблемы со связью...

Здравствуйте, Scherhan, Вы писали:

S>Да, мне очень интересно, т.к. недавно начала работать с программированием графики. Обычно работала с БД, а тут...что поделаешь, работа

Дай адрес — пришлю примерчик

S>Хочу пояснить общую постановку задачи:
S>[...]

Поставленная задача естественным образом распадается на две:
1) подготовка изображения
Т. е. подготовка того, что нужно найти. Здесь возникает вопрос: масштаб на обоих снимках одинаков (и если нет — известна ли разница в масштабах)? И второй: ориентация обоих снимков одинакова (т. е. наклоннён ли один снимок относительно другого)?
Порядок действий здесь мне видится таким:
— выделяем из первого снимка интересующий фрагмент (копируем в массив, bitmap или ещё как-то — из соображений удобства)
— трансформируем его (поворачиваем и масштабируем) в случае необходимости; при этом, возможно, необходимо будет применить какой-либо из алгоритмов фильтрации
— возможно также, что нужно будет применить один из алгоритмов для подавления шумов (помех) на обоих снимках, т. к. снимки сделаны в разное время и разным оборудованием — помехи (шумы) будут разными — всё зависит от качества снимков
2) поиск
Предполагается, что к этому моменту масштаб и ориентация обоих изображений совпадают. Для поиска фрагмента, выделенного из первого снимка, во втором можно применить несколько способов:
— нейронная сеть (далее НС): реализовать достаточно просто (к тому же существует ряд библиотек уже реализующих НС), но её (НС) сложно обучить и для этого требуется большое количество исходных данных (по крайней мере тысячи подобных снимков)
— методы оконтуривания: выделение объектов (с помощбю определения их контуров) и поиск похожих на др. снимке
— если снимки различаются не слишком сильно, можно вычесть значения интенсивностей одного снимка (фрагмента) из другого, грубо говоря попиксельно сравнить картинки, и посчитать ошибку (отклонение), например в среднеквадратическом. Если она невелика — считать сравнённые фрагменты идентичными
— визуальный: можно накладывать выделенный фрагмент на второй снимок и позволить пользователю сдвгать его и самому решать — то это или нет

Больше пока ничего в голову не приходит...

GT>Поставленная задача естественным образом распадается на две:
GT>1) подготовка изображения
GT> Т. е. подготовка того, что нужно найти. Здесь возникает вопрос: масштаб на обоих снимках одинаков (и если нет — известна ли разница в масштабах)? И второй: ориентация обоих снимков одинакова (т. е. наклоннён ли один снимок относительно другого)?
GT> Порядок действий здесь мне видится таким:
GT> — выделяем из первого снимка интересующий фрагмент (копируем в массив, bitmap или ещё как-то — из соображений удобства)
GT> — трансформируем его (поворачиваем и масштабируем) в случае необходимости; при этом, возможно, необходимо будет применить какой-либо из алгоритмов фильтрации
GT> — возможно также, что нужно будет применить один из алгоритмов для подавления шумов (помех) на обоих снимках, т. к. снимки сделаны в разное время и разным оборудованием — помехи (шумы) будут разными — всё зависит от качества снимков
GT>2) поиск
GT> Предполагается, что к этому моменту масштаб и ориентация обоих изображений совпадают. Для поиска фрагмента, выделенного из первого снимка, во втором можно применить несколько способов:
GT> — нейронная сеть (далее НС): реализовать достаточно просто (к тому же существует ряд библиотек уже реализующих НС), но её (НС) сложно обучить и для этого требуется большое количество исходных данных (по крайней мере тысячи подобных снимков)
GT> — методы оконтуривания: выделение объектов (с помощбю определения их контуров) и поиск похожих на др. снимке
GT> — если снимки различаются не слишком сильно, можно вычесть значения интенсивностей одного снимка (фрагмента) из другого, грубо говоря попиксельно сравнить картинки, и посчитать ошибку (отклонение), например в среднеквадратическом. Если она невелика — считать сравнённые фрагменты идентичными
GT> — визуальный: можно накладывать выделенный фрагмент на второй снимок и позволить пользователю сдвгать его и самому решать — то это или нет

GT>Больше пока ничего в голову не приходит...

Извиняюсь, что влезаю в диалог . Но задача автораспозанвания образов аэрофотосъемки достаточно сложна, чтобы рассуждать об удобстве копирования в Bitmap. В то же время она уже решена (в спецприложениях), в т.ч. и у нас в стране. Предлагаемая схема в общем правильная, так примерно все и делается , но реализация ее не тривиальна. Я в аналогичной ситуации полагаюсь на оператора — масштаб подгоняет он вручную, начала координат изображений — тоже. После этого можно действительно вычесть и что-нибудь посчитать для оператора, желательно скалярную величину (функционал), по значению которого пользователь решает — похоже-непохоже.
А если по науке , то читай Прэтта, Ярославского (хотя бы "Цифровую обработку изображений" от 1982) или по аглицки в инете. Но по науке получается ОЧЕНЬ ресурсоемко и зачастую неточно

Здравствуйте, Аноним, Вы писали:


А>Извиняюсь, что влезаю в диалог . Но задача автораспозанвания образов аэрофотосъемки достаточно сложна, чтобы рассуждать об удобстве копирования в Bitmap.

Совершенно согласен, но человеку-то помочь нужно

А>В то же время она уже решена (в спецприложениях), в т.ч. и у нас в стране.

Это не значит, что не стоит за неё браться — обстоятельства разные бывают...

А>Предлагаемая схема в общем правильная, так примерно все и делается , но реализация ее не тривиальна. Я в аналогичной ситуации полагаюсь на оператора — масштаб подгоняет он вручную, начала координат изображений — тоже. После этого можно действительно вычесть и что-нибудь посчитать для оператора, желательно скалярную величину (функционал), по значению которого пользователь решает — похоже-непохоже.

Я и не говорил, что реализация тривиальна, однако задача вполне решаема и без участия оператора

А>А если по науке , то читай Прэтта, Ярославского (хотя бы "Цифровую обработку изображений" от 1982) или по аглицки в инете.

Дополнительная информация ещё никому не помешала

А>Но по науке получается ОЧЕНЬ ресурсоемко и зачастую неточно

Существует масса алгоритмов, которые предназначены специально для реализации на ЭВМ. Например, задача ориентации самолётов по снимкам поверхности земли — суть, задача распознавания объектов на снимках и сравнения с эталонными (почти та же задача, что и предложенная здесь) решается без участия человека, причём во временной отрезок менее секунды и на более чем скромных машинах

Спасибо ВСЕМ, кто мне помогает )

Здравствуйте, GarikTot, Вы писали:
Масштаб на обоих снимках не известен, а также разница. Ориентация обоих снимков, вроде-бы похожа.
С нейронной сетью сталкивалась ранее, но знания в этой области поверхностны. Попиксельно вряд-ли получится, т.к. снимки одной местности имеют отличия, например: в четкости; в масштабе; в цвете, хотя снимки черно-белые (градация серого). А вот поиск по контуру, м.б. — лучший вариант.
Визуальный метод совсем не подходит.
Я уже сделала перевод в пикселы координаты двух квадратов в матрицы, проверила значения двух квадратов->вывод, что попиксельно не сравнить ((
Мой адрес: scherhan@hotmail.ru

Здравствуйте, Scherhan, Вы писали:

S>Мой адрес: scherhan@hotmail.ru

Пример уже отправил

S>Масштаб на обоих снимках не известен, а также разница. Ориентация обоих снимков, вроде-бы похожа.

Это плохо — задача усложняется... Автоматически определять масштаб не всегда удобно. Возможно стоит предоставить пользователю возможность масштабировать на разные величины и сказать когда примерно похоже, или каким-нибудь другим способом выяснить масштаб (снимки же откудато взялись)

S>А вот поиск по контуру, м.б. — лучший вариант.

Возможно, что так. Могу здесь посоветовать только одно: необходимо изучать данную тему (главным образом, читая литературу )
[1] Кузьмин С. З. "Основы проектирования систем цифровой обработки радполокационной информации"
[2] Фу К. "Структурные методы распознавания образов"
Кроме того любая книга по машинной графике и мат. методам обработки изображений сможет что-то добавить

Здравствуйте, GarikTot, Вы писали:

GT>Пример уже отправил
Спасибо, большое, за пример и за помощь

Здравствуйте, GarikTot!
Вот хочу спросить у Вас, я правильно сделала:
Когда кликаю мышью на двух PaintBox'ах,рисуются квадраты, т.е. на PaintBox1 — квадрат 48х48, а на PaintBox2 — квадрат 96х96. Затем каждый квадрат загоняю в матрицы:
//n = 48
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
Matrix1[n][n]=PaintBox1->Picture->Canvas->Pixels[i+X0][j+Y0];
}
//Для m = 96 тоже самое.

Т.о. получила матрицы с пикселами, но не знаю, как сделать построчный поиск. Понятно, что надо взять Matrix1[0][0] и прогнать по Matrix2[m][m] до его нахождения в данной матрице. Если есть такой пиксел, рисуется точка в квадрате_2 и так до тех пор, пока не нарисуется квадрат_1.
Спасибо. Пока

Здравствуйте, Scherhan, Вы писали:

S>Т.о. получила матрицы с пикселами, но не знаю, как сделать построчный поиск. Понятно, что надо взять Matrix1[0][0] и прогнать по Matrix2[m][m] до его нахождения в данной матрице. Если есть такой пиксел, рисуется точка в квадрате_2 и так до тех пор, пока не нарисуется квадрат_1.
S>Спасибо. Пока

А зачем это нужно?

Если сравниваются два различных снимка, то это работать не будет, т. к. одинаковых точек всё равно не найдётся... Если хочется делать таким образом, лучше всего поступить так: не искать одинаковые точки, а вычитать точки одного квадрата — из другого, а затем посчитать средне-квадратическое отклонение...

Или я что-то неправильно понял?

Здравствуйте, GarikTot, Вы писали:
GT>а вычитать точки одного квадрата — из другого, а затем посчитать средне-квадратическое отклонение...
И что это даст?

Здравствуйте, GarikTot, Вы писали:
"а вычитать точки одного квадрата — из другого, а затем посчитать средне-квадратическое отклонение..." Для чего используется данный метод???

Здравствуйте, Scherhan, Вы писали:

S> "а вычитать точки одного квадрата — из другого, а затем посчитать средне-квадратическое отклонение..." Для чего используется данный метод???

Если известно, что на обоих фрагментах фасштаб одинаков, можно попробовать сделать так, как я написал выше... Дело в том, что если на снимках одно и то же место (даже если они сделаны в разное время), величина ошибки (отклонения) будет заметно отличаться от тех случаев, когда снимки разные... Тут нужно правильно (экспереминтальным путём, "методом научногго тыка" ) подобрать пороговое значение ошибки, после ктр. считать объекты идентичными...

Я не настаиваю на этом методе: сам так никогда не пробовал делать, просто один приятель рассказывал, что можно поступить таким образом... мы с ним даже помнится на пиво поспорили...

Здравствуйте, GarikTot, Вы писали:

GT>Если известно, что на обоих фрагментах фасштаб одинаков, можно попробовать сделать так, как я написал выше... Дело в том, что если на снимках одно и то же место (даже если они сделаны в разное время), величина ошибки (отклонения) будет заметно отличаться от тех случаев, когда снимки разные... Тут нужно правильно (экспереминтальным путём, "методом научногго тыка" ) подобрать пороговое значение ошибки, после ктр. считать объекты идентичными...

GT>Я не настаиваю на этом методе: сам так никогда не пробовал делать, просто один приятель рассказывал, что можно поступить таким образом... мы с ним даже помнится на пиво поспорили...

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

Здравствуйте, Scherhan, Вы писали:

S>Хм, оригинально...такую тему спорят, аж на пиво

И не просто, а на ящик!

S>Сказали,что после прогона каждого пиксела первой матрицы во второй надо из суммы эталона вычесть сумму текущей, что-то вроде этого...

Вариации всё на ту же тему...
В том случае предлогалось минимизировать средне-квадратическое (СК) отклонение (разницу между точками) методом наименьших квадратов (МНК)
енто, второй (нето третий) курс — ТВИМС, насколько я помню...

только всё равно, мне кажется, ничего достойного из этого не выйдет...

Здравствуйте, GarikTot, Вы писали:

GT>Здравствуйте, Scherhan, Вы писали:

S>>Хм, оригинально...такую тему спорят, аж на пиво

GT>И не просто, а на ящик!

S>>Сказали,что после прогона каждого пиксела первой матрицы во второй надо из суммы эталона вычесть сумму текущей, что-то вроде этого...

GT>Вариации всё на ту же тему...
GT>В том случае предлогалось минимизировать средне-квадратическое (СК) отклонение (разницу между точками) методом наименьших квадратов (МНК)
GT>енто, второй (нето третий) курс — ТВИМС, насколько я помню...

GT>только всё равно, мне кажется, ничего достойного из этого не выйдет...

Привет всем.
может что пропустил, но все равно скажу. Есть замечательный метод motion estimation назывется, используется в MPEG'ах для апроксимации движения между кадрами.
Для данного случая примерно так:
берем маленький квадрат увеличиваем его интерполяцией до размеров большого и начинаем поиск в заданной области картинки (можно по всей конечно, но если есть какие-то предположения — то лучше их использовать)
минимизируя функцию расстояния между блоками — СКО.
Зря между прочим некоторые товарищи шуткуют по этому поводу — MPEG group на данной технологии давно деньги рубит и как вы могли заметить довольно успешно не смотря на столь простую функцию как СКО. Если кто не знает, то без motion estimation MPEG просто ничто (точнее MJPEG), т.е. ~20-30 кратное сжатие .

Здравствуйте, Аноним, Вы писали:

полезная статья по теме:
IMAGE RETRIEVAL BASED ON ENERGY HISTOGRAMS OF THE LOW FREQUENCY DCT COEFFICIENTS

http://www.telecom.tuc.gr/paperdb/icassp99/PDF/AUTHOR/IC991221.PDF — статья

http://debut.cis.nctu.edu.tw/pages/slides/jeffrey/present2.pdf — тезисы