| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск одного изображения в другом [D7, WinXP]
czuryk © (2009-01-23 15:48:00)Добрый день коллеги! Очень прошу помочь!
Давно уже бьюсь, но никак не могу расколоть сабжевую проблему, гугл выдает некую информацию, но мне никак не удается ее адаптировать для своих нужд. Учтите, речь идет не о сравнении одного изображения с другим.
Мне нужно организовать поиск одного изображения (маленького, порядка 100х50 пикселей) в другом - большом, порядка 1280х1024 пикселей, причем поиск должен осуществлятся максимально быстро < 1 сек. Результатом работы функкции должны быть координаты X,Y маленьгоко изображения в большом (исходном).
Причем поиск долже выполнятся по полному схождению части большого изображения и маленького. Так как если искать по нескольки ключевых точек, то такие функции в моем случае дают сбой.
procedure TForm1.Button4Click(Sender: TObject);
Type
TRGBTripleArray = ARRAY[WORD] OF TRGBTriple;
pRGBTripleArray = ^TRGBTripleArray;
var
b1, b2: TBitmap;
// c1, c2: PByteArray;
c1, c2: pRGBTripleArray;
x, y, i,: Integer;
eq: boolean;
resX, resY: integer;
begin
b1 := Image1.Picture.Bitmap;
b2 := Image2.Picture.Bitmap;
Assert(b1.PixelFormat = b2.PixelFormat); // they have to be equal
for y := 0 to b1.Height - 1 do // Внешний цикл по строкам оригинала
begin
c1 := b1.Scanline[y];
c2 := b2.Scanline[0]; // Ищу на соответствие только по 1-й строке
for x := 0 to b1.Width - 1 do
begin
eq := true;
for i := 0 to b2.Width - 1 do // Цикл по строке искомой строки
begin
if (c1[x+i].RGBtRed <> c2[i].RGBtRed) or (c1[x+i].RGBtGreen <> c2[i].RGBtGreen) or (c1[x+i].RGBtBlue <> c2[i].RGBtBlue) then
begin eq := false; break; end
end;
if ( eq ) then begin resX:=x; resY:=y; break; end;
end;
if ( eq ) then break;
end;
if ( eq ) then
begin
Memo1.Lines.Add('FOUND');
b1.canvas.Brush.Color := clRed;
b1.canvas.Ellipse(resX-3, resY-3, resX+3, resY+3);
end
else Memo1.Lines.Add('NOT FOUND');
end;
Этот код работает, но не быстро (в силу его примитивности и неоптимизированности) и ищет только по первой строке второго изображения. Как оптимально сделать чтобы он искал быстро по всем строкам под-изображения я еще не придумал.
Есть другой вариант, с которым мне помогли, там очень быстро ищется под-изображение по 4-м точкам. Но этот алгоритм в силу его ограниченности часто дает сбой, а модифицировать его должным образом у меня не вышло.
...
...
PInt = ^integer;
var
Form1: TForm1;
implementation
{$R *.dfm}
function SearchBitmap(const bmMain,bmSub:TBitmap; var Res:TPoint):boolean;
var iMainHeight, iMainWidth,
iSubHeight, iSubWidth,
iMainPXWidth, iSubPXWidth, iDiffPXWidth,
iDiffHeight: integer;
i,j:integer;
eq: boolean;
pRowMain, pRowSub : PByteArray;
ltPt,rtPt,lbPt,rbPt : PInt;
cPoints:array[0..3] of integer;
begin
Res.X := -1;
Res.Y := -1;
SearchBitmap := false;
bmMain.PixelFormat:=pf24bit;
bmSub.PixelFormat:=pf24bit;
iMainHeight := bmMain.Height;
iMainWidth := bmMain.Width;
iMainPXWidth := iMainWidth * 3;
iSubHeight := bmSub.Height;
iSubWidth := bmSub.Width ;
iSubPXWidth := iSubWidth *3 ;
iDiffPXWidth := iMainPXWidth - iSubPXWidth;
iDiffHeight:= iMainHeight - iSubHeight;
pRowSub := bmSub.ScanLine[0];
cPoints[0]:= PInt(@(pRowSub^[0]))^ and $FFFFFF;
cPoints[1]:= PInt(@(pRowSub^[iSubPXWidth-3]))^ and $FFFFFF;
pRowSub := bmSub.ScanLine[iSubHeight-1];
cPoints[2]:= PInt(@(pRowSub^[0]))^ and $FFFFFF;
cPoints[3]:= PInt(@(pRowSub^[iSubPXWidth-3]))^ and $FFFFFF;
eq:=false;
for i:=0 to iDiffHeight - 1 do
begin
pRowMain := bmMain.ScanLine[i];
pRowSub := bmMain.ScanLine[i+iSubHeight-1];
j:=0;
ltPt := PInt(@pRowMain^[j]);
lbPt := PInt(@pRowSub^[j]);
//rtPt := PInt(pRowMain + iSubPXWidth - 3);
//rbPt := PInt(pRowSub + iSubPXWidth - 3);
asm
mov eax,iSubPXWidth
sub eax,3
mov ecx,eax
add ecx,ltPt
mov rtPt,ecx
mov ecx,eax
add ecx,lbPt
mov rbPt,ecx
end;
while j<iDiffPXWidth do
begin
{
eq := ((PInt(@(pRowMain^[j]))^ and $FFFFFF) = cPoints[0])
and ((PInt(@(pRowMain^[j+iSubPXWidth-3]))^ and $FFFFFF) = cPoints[1])
and ((PInt(@(pRowSub^[j]))^ and $FFFFFF ) = cPoints[2])
and ((PInt(@(pRowSub^[j+iSubPXWidth-3]))^ and $FFFFFF) = cPoints[3]);
}
eq := ((ltPt^ and $FFFFFF) = cPoints[0])
and ((rtPt^ and $FFFFFF) = cPoints[1])
and ((lbPt^ and $FFFFFF) = cPoints[2])
and ((rbPt^ and $FFFFFF) = cPoints[3]);
if ( eq ) then
begin
Res.X := j div 3;
Res.Y := i;
SearchBitmap := true;
break;
end;
asm
add ltPt,3
add rtPt,3
add lbPt,3
add rbPt,3
end;
inc(j,3);
end;
if eq then break;
end;
end;
function CaptureScreenRect(ARect : TRect) : TBitmap;
var
ScreenDC: HDC;
begin
Result:=TBitmap.Create;
with result, ARect do
begin
Width:=Right-Left;
Height:=Bottom-Top;
ScreenDC:=GetDC(0);
try
BitBlt(Canvas.Handle, 0,0,Width,Height,ScreenDC, Left, Top, SRCCOPY );
finally
ReleaseDC(0, ScreenDC);
end;
end;
end;
procedure Search(pattern: string; p_color: TColor);
var
bmMain, bmSub: TBitmap;
startPoint: TPoint;
c: TCanvas;
begin
c := TCanvas.Create;
c.Handle := GetDC(0);
bmMain := TBitmap.Create();
bmSub := TBitmap.Create();
try
// image1.Picture.Bitmap := CaptureScreenRect(Rect(0,0,Screen.Width,Screen.Height));
bmMain := CaptureScreenRect(Rect(0,0,Screen.Width,Screen.Height));
// bmMain.LoadFromFile('screen_main.bmp');
bmSub.LoadFromFile(pattern);
if (SearchBitmap(bmMain, bmSub, startPoint)) then
begin
c.Brush.Color := p_color;
c.Ellipse(startPoint.x-3, startPoint.y-3, startPoint.x+3, startPoint.y+3);
end;
finally
bmMain.Free;
bmSub.Free;
c.Free;
end;
end;</CODE
Германн (2009-01-25 03:03:00) [1]
> czuryk © (25.01.09 02:07) [35]
>
> Вот тут представленны два неплохих алгоритма
Ну так и используй их!
czuryk (2009-01-25 02:07:00) [2]Вот тут представленны два неплохих алгоритма, которые быстро справляются с моей задачей:
http://forum.sources.ru/index.php?act=ST&f=11&t=263125
Всем спасибо.
czuryk (2009-01-24 22:53:00) [3]Pavia, а можно примерчик?
Pavia (2009-01-24 22:17:00) [4]
> я тут тоже ноль без палочки, как работать с битмапом напрямую
> как с массивом .... :(
Да тут достаточно scanline будет прямая работа с битмепом в памяти.
Только совет делать так через scanline получаем указатель на первый пиксель. Через разность получаем длину линии. Из-за выравнивания она будет отличаться от width*bytePerPixel. И еще вспомнить что у битмепа обратный порядок строк. И работать с указателями.
czuryk (2009-01-24 21:50:00) [5]я тут тоже ноль без палочки, как работать с битмапом напрямую как с массивом .... :(
KilkennyCat (2009-01-24 21:07:00) [6]
> czuryk © (24.01.09 19:20) [28]
Не нужно сканлайн и проч, это все теже танцы с графикой. Читаем память напрямую. Но это выше моего уровня, кодом не помогу, ибо мне придется пару дней сидеть за учебниками. Но я бы шел в этом направлении. Или в направлении
> Pavia © (23.01.09 23:22) [20]
czuryk (2009-01-24 20:30:00) [7]Johnmen, и? проблема до сих пор актуальна.
Johnmen (2009-01-24 20:15:00) [8]http://sql.ru/forum/actualthread.aspx?tid=632890
czuryk (2009-01-24 19:20:00) [9]Pavia, нет, текст это только одна из подзадач, вторая подзадача это поиск картинок, а с интегральнальными проекциями я не силен...
KilkennyCat, я пытался, но получаемая информация из ScanLine в виде массива не сравнивается как элементы массива, а нужно расшифровывать:
for i := 0 to b2.Width - 1 do // Цикл по строке искомой строки
begin
if (c1[x+i].RGBtRed <> c2[i].RGBtRed) or (c1[x+i].RGBtGreen <> c2[i].RGBtGreen) or (c1[x+i].RGBtBlue <> c2[i].RGBtBlue) then
begin eq := false; break; end
end;
Как это преодолеть я не знаю.
KilkennyCat (2009-01-24 15:47:00) [10]
> т.к. работа идет с 24-битным цветом.
А какая разница? Я вообще цвет не рассматриваю, я всегда рассматриваю некий набор байт, который можно интерпретировать в цвет, в текст, во что угодно. попробуй отойти от "цветных шор" и тебе сразу откроется больше возможностей.
Pavia (2009-01-24 15:40:00) [11]
> распозновать границы окна, и текст в некоторых окнах, а
> это не так много шаблонов.
Так бы сразу и сказал что тебе текст анализировать, а то картинки.
Делаешь выделение связанных областей а после распознаешь. Тут можно еще попробовать замутить интегральные проекции для ускорения.
czuryk (2009-01-24 12:33:00) [12]Привет Ramon, да, согласен. Я с него и начал... но он оооочень медленный. Прядка 1-2 секунд на двухядернике. Быстрее работает через ScanLine, но тоже недостаточно быстро, можешь посмотреть код, который я выложил.
Ramon (2009-01-24 12:26:00) [13]Привет!
А если например считываем цвет верхнего левого пиксела малой картинки(1х1), ищем его в большом изображении, если находим - тогда опять считываем цвет с малой картинки, но уже под другим пикселом (2х1), и т.д. Если по горизонтали кончились пикселы, переходим на следующий ряд (1х2) и т.д.!
Имхо очень простой алгоритм, но верный :)
czuryk (2009-01-24 12:25:00) [14]Меня опять неправильно поняли, directshow фильтры и прочие видео-прибамбасы - в сад.
Мне нужно исследовать статичную картинку на рабочем столе, и анализировать работу программы на JAVA. распозновать границы окна, и текст в некоторых окнах, а это не так много шаблонов.
Но их больше 10, так что алгоритм заточенный под определенный вид шаблона не получится, так как они будут разднится, нужен некий универсальный попиксельный алгоритм, который пусть не "срезая углы", будет одинаково хорошо искать все шаблоны, причем некоторые из них могут быть небольшие, примером 10-10 пикселей.
И вот еще пример. Нужно будет найти слово "Hello" в окне JAVA программы, то что это слово есть, мне будет известно, мне просто нужно найти его координаты. Поэтотому, у меня будут шаблоны для всех букв и я составлю из них один шаблон (шаблоны приходится использовать так как JAVA использует свои шрифты и извлечь их нет возможности), соединив Битмапы шаблонов нужной последовательности букв, и ища уже единый шаблон.
KilkennyCat, идея с матрицей неплоха, но ее внедрить не получится, т.к. работа идет с 24-битным цветом.
Pavia (2009-01-23 23:36:00) [15]
> и припаять DSP :)
Можно и на видео карте.
KilkennyCat (2009-01-23 23:32:00) [16]
> Свертку делать через FFT.
и припаять DSP :)
Pavia (2009-01-23 23:22:00) [17]
> Быстрого говоришь, а ведь тут примерно 1280х1024х100х50/2
> сравнений.
Несогласен вы про свертку забыли Будет примерно 1280х1024х11х10х2
И время сравнения порядка 1 секунды.
Свертку делать через FFT.
tesseract (2009-01-23 22:35:00) [18]
> Диагональ, спираль, ход конем... Но это реально ускорит.
Вилкой надо вилкой - она твои предположения в десятки раз ускорит, сечём например по первому пикселу - потом хоть по даигонали хоть по прямой сечём вотороя пиксель - например выясняли правый нижний (оптимально по вариантам перебора, позволит отсечь кучу переборов в большинстве случаев) смотрим правый верхний и тд, потом сечем пересечения по диагонлям по среднему и тд - сильно снизит сложность алгоритма. Хотя тут мы имеем сферического коня в вакууме - по любэ автор имеет в видео через филтры directshow.
KilkennyCat (2009-01-23 22:11:00) [19]На всякий случай добавлю пояснение, почему я предложил по диагонали проверку. Предположим упрощенную модель, белый фон, на нем черные квадраты и черные уголки , как буква "г" с шириной равной ширине квадрату (N). В этом случае, тупой перебор будет работать на N итераций больше, чем по диагонали. Но если там присутствуют косые отрезки "\" - то, наоборот будет... т.е. необходимо задавать метод для каждого шаблона. Диагональ, спираль, ход конем... Но это реально ускорит.
KilkennyCat (2009-01-23 22:02:00) [20]
> tesseract © (23.01.09 21:43) [16]
А причем здесь кодирование? Предлагаешь лезть сразу по исходному видео? Ну это тогда точно, извиняюсь, Ж..па...
Но, вроде, в исходной задаче о таких нюансах не говорилось... я рассматривал вариант просто поиск подмножества.
Ну, а если так, как ты думаешь, (распознавание текста в видео, я правильно понял?) то да... тогда вообще один вариант - бить видео на фрагменты, запускать на разных машинах - иначе долго будет. Офигитильно долго.
| |
Страницы: 