| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / 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
tesseract (2009-01-23 21:43:00) [21]
> Нет ребят, замазывать я ничего не буду, мне нужно OCR-ить
> то что идет на экран
Псих что-ли ? У тебя шаблонов будет около миллиарда, а то и больше.
> И еще: определение в шаблоне области размером 2x2 одного
> цвета
размер блока фиксирован, т.е метод приближения работает. Хотя по квадрату выясняй хоть по диагонали, для такой фичи требуеться поизучать RFC по mp2 или mp4 и плюс если в качестве источника видео будет выступать сжатое видео - там цвет пикселя плавает в широких пределах - т.е надо выяснять шаблон - шаблон, что для такого экрана за 1 секунду сделать нереально. Делать из картинки матрицу полной резкости тупо отбрасывая неподходящие шаблоны и создавая 5-6 шаговый алгоритм,,,,, это уже наверно только с CUDA возможно.
AndreyV (2009-01-23 21:42:00) [22]> [11] KilkennyCat © (23.01.09 21:13)
> Смысл в том, что не будет действительно полного перебора
> всех вариантов, посчитанных в [1].
Не понимаю куда они денутся, кроме уже оговорённых краёв.
KilkennyCat (2009-01-23 21:36:00) [23]И возможно ускорит запуск второго (и последующего циклов) в Thread
KilkennyCat (2009-01-23 21:31:00) [24]И еще: определение в шаблоне области размером 2x2 одного цвета в 4 раза уменьшит количество итераций первого цикла.
KilkennyCat (2009-01-23 21:26:00) [25]Вообще, надо считать. Возможно, имеет смысл увеличить время выполнения каждой итерации цикла но снизить их количество в разы.
Возможно, булевская алгебра в асме выполнится намного быстрее, тогда можно привести матрицу экрана к виду
1110111
1111011
1101111
1011111
Где 0 - вхождение первой точки, и так далее.
KilkennyCat (2009-01-23 21:13:00) [26]
> Anatoly Podgoretsky © (23.01.09 20:40) [9]
Ну, у нас внизуу и справа ведь отсекаются области, именно из-за полного вхождения. Не влезет шаблон.
> AndreyV © (23.01.09 21:10) [10]
Смысл в том, что не будет действительно полного перебора всех вариантов, посчитанных в [1]. Даже без заранее известных особенностей.
AndreyV (2009-01-23 21:10:00) [27]> [2] KilkennyCat © (23.01.09 17:26)
> Просто сделать не тупой перебор, а поиск с вероятностью,
Что-то я не понял разницы между перебором по горизонтали или вертикали и диагональю. Ну нашли мы первое совпадение: надо проверить н*м точек (размер маленькой картинки), последовательность перебора никак не повлияет на скорость, если нет заранее известных особенностей.
Другое дело, что достаточно проверить Н*М-н*м точек, Н*М - размер большой картинки
Anatoly Podgoretsky (2009-01-23 20:40:00) [28]
> сотню и полсотни можно ведь вычесть ?
Нельзя, поскольку "поиск долже выполнятся по полному схождению", или ты знаешь метод сравнения без сравнения каждого пикселя, Дельфи то 32 битная.
KilkennyCat (2009-01-23 20:37:00) [29]
> опрос с диаганалью, мне кажется не сильно даст прирост,
> в скорости
Это общий механизм. Если шаблонов не много, и не часто требуется добавлять новые, то механизм можно оптимально подстроить для каждого шаблона.
Но прирост в скорости даст, так как формула Анатолия сократится до 1180х974 основного пробега плюс небольшие пробеги в случае совпадения.
czuryk (2009-01-23 19:28:00) [30]Нет ребят, замазывать я ничего не буду, мне нужно OCR-ить то что идет на экран. Есть одна извращенская программа написанная на JAVA, и с т.з. WinAPI к нейне подступиться, и приходится писать OCR модуль по шаблонуам.
Поэтому мне нужно реализовать совпадение до последнего пикселя.
Я уже давно говыряюсь и перерыл гору всего, и пуляли меня в разныеместа, поэтому если честно буду очень рад практической помощи, но и от теории не откажусь.
2 KilkennyCat, вопрос с диаганалью, мне кажется не сильно даст прирост, в скорости, но я над этим еще подумаю. Спасибо!
easy (2009-01-23 18:11:00) [31]
> tesseract © (23.01.09 17:33) [4]
> Очередной замазыватель эмблемы канала ?
>
замазыватель делается не так.
рисуется логотип побольше и всё..
KSergey (2009-01-23 17:46:00) [32]> tesseract © (23.01.09 17:33) [4]
> Очередной замазыватель эмблемы канала ?
Если так - то, конечно, не выйдет у него тогда так вот "просто".
А зафик ее замазывать?? Перепродавать эфир не платя отчислений?
tesseract (2009-01-23 17:33:00) [33]Очередной замазыватель эмблемы канала ?
KSergey (2009-01-23 17:29:00) [34]Вопроса два:
1. Маленькое изображение буквально присутствует в большом (с точностью до значения каждого пикселя) или только "примерно иакое же на вид", но буквальное значение пикселей может отличаться (например, разная яркость большой и маленькой картинки как самый простой случай).
2.Вам нужен готовый код или идеи?
KilkennyCat (2009-01-23 17:26:00) [35]Просто сделать не тупой перебор, а поиск с вероятностью, или как бы выразиться... Вообщем, ищем вхождение первой точки. Если есть - проверяем совпадение с координатами на 1 больше (т.е по диагонали). Если вся диагональ совпала, мы получаем большую вероятность, что наткнулись на искомое и запускаем тотальную проверку. Вероятность можно регулировать, например, приплюсовать сотню и проверить обратную диагональ.
> Anatoly Podgoretsky ©
> примерно 1280х1024х100х50/2 сравнений.
сотню и полсотни можно ведь вычесть ?
Anatoly Podgoretsky (2009-01-23 15:57:00) [36]
> Причем поиск долже выполнятся по полному схождению части
> большого изображения и маленького.
Быстрого говоришь, а ведь тут примерно 1280х1024х100х50/2 сравнений.
| |
Страницы: 