Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Delphi: Звук, графика и видео > Быстрое сравнение двух рисунков


Автор: EPaul 20.9.2010, 09:29
Есть ли какой нибудь метод быстрого сравнения двух рисунков, типа if bitmap1 = bitmap2 then Попиксельный метод сравнения 2 bitmap не подходит, очень медленно, да и систему нагружает сильно. Заранее спасибо за ответы 

Автор: ~FoX~ 20.9.2010, 09:48
ScanLine быстрее в делфях не предусмотрено... Можно использовать GDI+, там много быстрее работа с изображениями...
Вобще то тему в алгоритмы, но и в этом разделе вопрос сравнения изображений поднимался не раз...
Проще всего сравнивать не сами рисунки, а например МД5 или ЦРЦ (если это файлы), есть алгоритм PSNR, но это сложно... 

Автор: Snowy 20.9.2010, 09:55
Можно загрузить оба битмапа в TMemoryStream.
Если размер стримов разный, то сразу нет.
Если одинаковый, то сравнить с помощью CompareMem.

Автор: EPaul 20.9.2010, 11:12
Snowy,  Спасибо.  Буду пробовать

Автор: EPaul 20.9.2010, 16:26
Snowy,  Попробовал.  Сравнение стримов и попиксельное сравнение по нагрузке на систему большой разницы не заметил. Кроме того, загрузка в stream также сильно нагружает систему, в зависимости от размера Bitmapa.  Может есть другие методы или компонеты для быстрой работы с графикой, использующие DirectX, например, или еще что. 

Автор: Alexeis 20.9.2010, 16:39
Цитата(EPaul @  20.9.2010,  15:26 Найти цитируемый пост)
Кроме того, загрузка в stream также сильно нагружает систему, в зависимости от размера Bitmapa.  Может есть другие методы или компонеты для быстрой работы с графикой, использующие DirectX, например, или еще что.  

  Можно для начала файлы открыть в TFileStream и сравнить размеры, если не совпадают, то перейти к началу растра и подгружать кусками, скажем по 4кб и сравнивать. 
  Вообще, есть решение лучше. Вместо TMemoryStream использовать отображение файлов в память FileMapping, а уже для отображений использовать CompareMem. Функция CompareMem сравнивая будет постепенно подгружать файл. Если файлы одного размера, но с разным контентом, то реально загрузиться лишь небольшой фрагмент от каждого файла, что займет значительно меньше времени.

Автор: EPaul 20.9.2010, 19:04
Alexeis,  Сравниваю не файлы, а картинку с экрана. Принцип такой, при старте программы сохраняю картинку с экрана в bitmap, допустим в PredBMP. Через определенные промежутки времени снимаю экран в CurrBMP. Это делаю методом BitBlt.  Нагрузка почти нулевая при разрешении экрана 1680Х1050
Далее дроблю оба bitmapa на N-ное количество мелких LPredBMP и LCurrBMP , допустим 50х50 пикселей, получаю при таких входных параметрах 714 мелких картинок методом
    LPredBMP.Canvas.CopyRect(Rect(0, 0, LRight-LLeft, LPredBMP.Height),   PredBMP.Canvas,   Rect(LLeft, LTop, LRight, LBottom)); 
и  LCurrBMP.Canvas.CopyRect(Rect(0, 0, LRight-LLeft, LCurrBMP.Height),   CurrBMP.Canvas,   Rect(LLeft, LTop, LRight, LBottom)); Тормоза начинаются уже здесь. Потом сравниваю между собой мелкие картинки. Если разные, сохраняю в StringList порядковый номер картинки и саму измененную картинку записываю в конец результирующего LLongBMP, размером Height =50 и Width = количество измененных картинок * 50. 
StringList с номерами и LLongBMP пересылаются потоками другой программе которая, по номеру вычисляет координаты измененных мест на экране и прорисовывает их. Сравнивать пробовал и попиксельно и с помощью MemoryStream, разницы не заметил. При частоте опроса 10 раз в секунду, процессор грузится до 50%.  Что можно сделать? 

Автор: Qu1nt 21.9.2010, 09:03
Опиши задачу smile

Автор: Alexeis 21.9.2010, 09:39
Цитата(EPaul @  20.9.2010,  18:04 Найти цитируемый пост)
StringList с номерами и LLongBMP пересылаются потоками другой программе которая, по номеру вычисляет координаты измененных мест на экране и прорисовывает их. Сравнивать пробовал и попиксельно и с помощью MemoryStream, разницы не заметил. При частоте опроса 10 раз в секунду, процессор грузится до 50%.  Что можно сделать?  

  Ну так количество сравнений будет n^2/2 = 250000 сравнений на 1 кадр и 2,5 млн сравнений в секунду по 250 пикселов. Можно процесс несколько ускорить, если для каждого фрагмента посчитать например сумму цветов всех пикселов (или crc сумму). Если суммы отличаются, то картинки на 100% отличаются, если же суммы совпали, то нужно дополнительно проверить сравнением. 
  Если совпадения кадров явление частое, то можно считать crc32. Случайное совпадение crc32 событие исключительно редкое, так что совпадение crc32 можно считать совпадением картинок. 

  Алгоритм со сложностью n^2 является плохим, но сравнение целых чисел куда быстрее чем картинок + расходы на расчет 714 (это все таки не 250 000). Кроме того, и этот алгоритм можно улучшить, если ключи (хеш суммы) отсортировать при помощи алгоритма быстросорт (сложность алгоритма n * log2 n ).

  Итого вместо жуткого n^2 по картинкам можно дойти до сложности n * log2 n по ключам + сложность n по вычислению хеша

Добавлено через 4 минуты и 3 секунды
Цитата(Alexeis @  21.9.2010,  08:39 Найти цитируемый пост)
если ключи (хеш суммы) отсортировать при помощи алгоритма быстросорт (сложность алгоритма n * log2 n ).

  На всякий случай. Чтобы найти одинаковые картинки в отсортированном массиве нужно сравнивать только соседние элементы. Можно оптимизировать быстросорт так чтобы он сразу же исключал повторения и создавал уже готовый массив уникальных ключей.

Автор: EPaul 21.9.2010, 19:02
Alexeis,  Это нужно переварить

Автор: Dimonka2 22.9.2010, 11:43
Картинки можно сначала уменьшить, а потом сравнивать уменьшенные верии. Это если конечно не интересуют какие-то сверх-мелкие детали.

Автор: Alexeis 22.9.2010, 11:45
Цитата(Dimonka2 @  22.9.2010,  10:43 Найти цитируемый пост)
Картинки можно сначала уменьшить, а потом сравнивать уменьшенные верии. 

  Так картинки и так относительно маленькие 50х50. 

Автор: xkor 22.9.2010, 15:42
Цитата(EPaul @  20.9.2010,  19:04 Найти цитируемый пост)
Далее дроблю оба bitmapa на N-ное количество мелких LPredBMP и LCurrBMP , допустим 50х50 пикселей, получаю при таких входных параметрах 714 мелких картинок методом
    LPredBMP.Canvas.CopyRect(Rect(0, 0, LRight-LLeft, LPredBMP.Height),   PredBMP.Canvas,   Rect(LLeft, LTop, LRight, LBottom)); 
и  LCurrBMP.Canvas.CopyRect(Rect(0, 0, LRight-LLeft, LCurrBMP.Height),   CurrBMP.Canvas,   Rect(LLeft, LTop, LRight, LBottom)); Тормоза начинаются уже здесь.

естественно тут будут тормоза CopyRect вещь медленная, тут тоже лучше BitBlt использовать (правда не помню умеет ли она куски вырывать, но если нет то 100% есть аналог который умеет)
НО у вас мне кажется неверный подход, зачем изображение сразу дробить?, вы сначала сравните старую большую и новую большую картинку, а дальше уже копируйте только куски с изменившимися данными, а лучше одновременно, то есть сравниваете попиксельно (быстрее невозможно) и как только один пиксель оказался не таким как раньше копируете соответствующий этому пикселю кусок картинки в массив изменившихся и больше пиксели этого куска не трогаете.

Автор: EPaul 22.9.2010, 19:36
xkor, Я вообщето так и делаю. На пальцах трудно объяснять. Если не поленитесь посмотреть код, могу выслать.

Автор: x128 22.9.2010, 21:35
Цитата(EPaul @  20.9.2010,  19:04 Найти цитируемый пост)
Далее дроблю оба bitmapa на N-ное количество мелких LPredBMP и LCurrBMP , допустим 50х50 пикселей, ... Тормоза начинаются уже здесь. Потом сравниваю между собой мелкие картинки. Если разные, сохраняю в StringList порядковый номер картинки и саму измененную картинку записываю в конец результирующего LLongBMP, размером Height =50 и Width = количество измененных картинок * 50. 

Зачем делать лишнюю работу если результат может потом не понадобиться? Сначала нужно проверить, а только потом копировать фрагменты где есть разница.

Цитата(EPaul @  20.9.2010,  19:04 Найти цитируемый пост)
tringList с номерами и LLongBMP пересылаются потоками другой программе которая, по номеру вычисляет координаты измененных мест на экране и прорисовывает их. Сравнивать пробовал и попиксельно и с помощью MemoryStream, разницы не заметил. При частоте опроса 10 раз в секунду, процессор грузится до 50%.  Что можно сделать? 

Если все делать в приделах одного приложения, скорость будет значительно больше, на пересылку данных нужно время и полученую информацию нужно обработать, такая связка будет отнимать больше времени, чем само сравнение. Опиши какой в этом смысл подробней, возможно есть другое решение.

Цитата(Alexeis @  21.9.2010,  09:39 Найти цитируемый пост)
Можно процесс несколько ускорить, если для каждого фрагмента посчитать например сумму цветов всех пикселов (или crc сумму). Если суммы отличаются, то картинки на 100% отличаются, если же суммы совпали, то нужно дополнительно проверить сравнением.   Если совпадения кадров явление частое, то можно считать crc32. Случайное совпадение crc32 событие исключительно редкое, так что совпадение crc32 можно считать совпадением картинок.

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

З.Ы. ради интереса прикинул затраты на сравнение, в результате на р4-2.4 с размером изображения 1600х1200 и размером блоков 16х16 и с визуализацией, при 10 кадрах в секунду нагрузка на процессор составила ~5%. 

Автор: Alexeis 22.9.2010, 21:55
Цитата(x128 @  22.9.2010,  20:35 Найти цитируемый пост)
Контрольная сумма считается не по волшебству, в любом случае нужно прочитать и произвести манипуляции с данными каждого из фрагментов, какая в таком подходе польза? Сравнение двух областей памяти займет меньше времени.

  Речь идет о попарном сравнении всех кусочков 1-2 1-3 .. 1-n, 2-3, 2-4, 2-n,...n-1 - n. Это отнюдь не n сравнений.

Автор: EPaul 22.9.2010, 23:58
x128, Как ты делаешь? У меня не получается меньше 40%. Сравниваю и память и пиксели. Посмотри мой код, что делаю не так? 

Автор: x128 23.9.2010, 12:33
Цитата(EPaul @  22.9.2010,  23:58 Найти цитируемый пост)
Посмотри мой код, что делаю не так? 

В принципе все не так... Выполняется много не нужного кода и много бесполезного кода, все затраты в конечном счете суммируются и получаешь тормоза. После получения очередного снимка экрана нужно сначала найти места где есть разница и только после этого производить манипуляции с измененными блоками. У тебя все наоборот, делаешь снимок, потом начинаешь вырезать фрагменты, далее каждый фрагмент пихать в TMemoryStream, только после этого сравнивать, после чего еще раз копировать. Логику в этих действиях я не уловил... 

Автор: EPaul 23.9.2010, 13:05
x128,   Т.е.  попиксельно сравнивать 2 больших снимка, по изменившемуся пикселю расчитать и вырезать фрагмент ?

Автор: x128 23.9.2010, 13:54
Примерно так, только не на мудри с "по изменившемуся пикселю расчитать и вырезать фрагмент", организуй грамотно цикл так, что бы не нужно было делать лишние вычисления т.е. в момент нахождения блока у тебя должны быть известны все значения (размер блока, положение, где данные и куда они должны попасть). Самое важное избавиться от лишних операций в циклах и других критичных местах.

Автор: EPaul 23.9.2010, 14:14
x128,  По изменившемуся пикселю, определить фрагмент его местонахождения, если фрагмент уже был замечен как измененный, до конца цикла сранения перескакивать через него, смещая индексы X,Y   если замечен впервые - вырезать. Так наверное будет лучше. Щас буду пробовать.   

Автор: xkor 23.9.2010, 19:51
Цитата(EPaul @  23.9.2010,  14:14 Найти цитируемый пост)
x128,  По изменившемуся пикселю, определить фрагмент его местонахождения, если фрагмент уже был замечен как измененный, до конца цикла сранения перескакивать через него, смещая индексы X,Y   если замечен впервые - вырезать. Так наверное будет лучше. Щас буду пробовать. 

и к чему тогда было отвечать:
Цитата(EPaul @  22.9.2010,  19:36 Найти цитируемый пост)
xkor, Я вообщето так и делаю. На пальцах трудно объяснять. Если не поленитесь посмотреть код, могу выслать. 

на моё сообщение:
Цитата(xkor @  22.9.2010,  15:42 Найти цитируемый пост)
НО у вас мне кажется неверный подход, зачем изображение сразу дробить?, вы сначала сравните старую большую и новую большую картинку, а дальше уже копируйте только куски с изменившимися данными, а лучше одновременно, то есть сравниваете попиксельно (быстрее невозможно) и как только один пиксель оказался не таким как раньше копируете соответствующий этому пикселю кусок картинки в массив изменившихся и больше пиксели этого куска не трогаете.

если только сейчас начали делать так как я написал?

Автор: EPaul 23.9.2010, 23:31
xkor,  Попробовал и Ваше предложение. Результат тот-же. Простой цикл перебора 1680х1050х3 без каких либо операций внутри, 10 раз в сек - до 5%.  Просто снимок экрана единственной процедурой BitBlt -  6-7%. А если поставить в цикл какое-либо условие на сравнение пикселей, расчет фрагмента, в котором находится пиксель, определяние был-ли этот фрагмент уже изменен - плюс еще 25-30%  В итоге меньше 50% не получается. (процессор P4® D-2.66 ОЗУ 3ГБ)   Пришел к выводу - в делфи это сделать невозможно. Жаль. Может на С++ это быстрее будет?   

Автор: xkor 24.9.2010, 00:04
EPaul, ну может в С++ и выиграешь процентик за счет более навороченного оптимизатора, но в целом один алгорим что на дельфи что на С++, что на другом языке с нативным компилятором будет работать практически с одной скоростью...

Автор: x128 24.9.2010, 00:06
Цитата(EPaul @  23.9.2010,  23:31 Найти цитируемый пост)
Пришел к выводу - в делфи это сделать невозможно. Жаль. Может на С++ это быстрее будет?

Разницы в среде разработки нет! Смотри прикрепленный исходник и думай над своими ошибками...

Автор: x128 24.9.2010, 00:06
Цитата(EPaul @  23.9.2010,  23:31 Найти цитируемый пост)
Пришел к выводу - в делфи это сделать невозможно. Жаль. Может на С++ это быстрее будет?

Разницы в среде разработки нет! Смотри прикрепленный исходник и думай над своими ошибками...

Автор: EPaul 24.9.2010, 00:18
x128,  Спасибо.

Автор: SeeDeeS 23.5.2012, 19:55
Как сделать чтоб она была не черно-белая? А то при этом:
Код

if i=bs then img[2][y div bs, x div bs]:=gr(img[1][y, x])
              else img[2][y div bs, x div bs]:=img[1][y, x];

картинка становится серой. О.О

Автор: MetalFan 23.5.2012, 22:04
SeeDeeS, оймама. трупокопатель)

Кстати, а что, если реализовать алгортим сравнения/поиска изменившихся областей таким образом:
Сравниваемые картинки отрисовываются друг на друга с пом BitBlt c dwRop = PATINVERT (xor), а затем смотрим, ищем ненулевые триплеты/дворды...
не быстрее ли это будет, чем сравнение через CompareMem и т.п.

Автор: Signal 24.10.2012, 22:06
Есть возможность предварительной проверки картинок это не попиксельное сравнение картинки, а побайтно, например 32 или 64 битном представлении.
Делаем массив типа int64
(предварительно картинку переводим в формат 1bit)
грузим в этот массив картинку
т.е. в 64 битном 1 елементе мы имеем сразу 64 точки, а далее математика, мы будем знать в каком элементе есть несовпадения и вычисляем
недавно находил пример, жаль сейчас по быстрячку не нашел на каком форуме я видел.
как писал автор, скорость сравнения битмапа выросла в 20 раз, сам не проверял

Автор: Чучмек 26.10.2012, 22:44
На два года опоздал,но все равно. 
Вот.
Сравнение 32битных битмапов
Код

type
 tcbp=function(bmp:tbitmap;x,y,pc,ud:cardinal):bool;stdcall;

function CmpBmp(bmp1,bmp2:TBitmap;pc:cardinal;cbp:tcbp;ud:cardinal):boolean;
var
 xn,yn,
 adr1,adr2,
 linesize1,
 linesize2:cardinal;
begin
if not Assigned(bmp1) or not Assigned(bmp2) or not Assigned(cbp)or(pc=0)or(pc>8192)then
 begin
 result:=false;
 exit;
 end;
if bmp2.PixelFormat<>pf32bit then bmp2.PixelFormat:=pf32bit;
xn:=bmp2.Width div pc;
if bmp2.Width>xn*pc then
 begin
 inc(xn);
 bmp2.Width:=xn*pc;
 end;
yn:=bmp2.Height div pc;
if bmp2.Height>yn*pc then
 begin
 inc(yn);
 bmp2.Height:=yn*pc;
 end;
if bmp1.PixelFormat<>bmp2.PixelFormat then bmp1.PixelFormat:=bmp2.PixelFormat;
if bmp1.Width<>bmp2.Width then bmp1.Width:=bmp2.Width;
if bmp1.Height<>bmp2.Height then bmp1.Height:=bmp2.Height;
if bmp2.Height=1 then
 begin
 linesize1:=bmp2.Width*4;
 linesize2:=linesize1;
 end else
 begin
 linesize1:=cardinal(bmp1.ScanLine[0])-cardinal(bmp1.ScanLine[1]);
 linesize2:=cardinal(bmp2.ScanLine[0])-cardinal(bmp2.ScanLine[1]);
 end;
pointer(adr1):=bmp1.ScanLine[bmp1.Height-1];
pointer(adr2):=bmp2.ScanLine[bmp2.Height-1];
asm
pushad
mov eax,linesize1
mul pc
mov ebx,eax
mov eax,linesize2
mul pc
mov edx,esp
sub esp,32                               
mov [edx-28],ebx
mov [edx-32],eax
mov ebx,adr1
mov [edx-20],ebx
mov ebx,adr2
mov [edx-24],ebx
mov eax,pc
shl eax,2
mov ecx,yn
@a:
   push ecx
   mov ecx,xn
   mov ebx,[edx-20]
   mov [edx-12],ebx
   mov ebx,[edx-24]
   mov [edx-16],ebx
   @b:
      push ecx
      mov ecx,pc
      mov ebx,[edx-12]
      mov [edx-4],ebx
      mov ebx,[edx-16]
      mov [edx-8],ebx
      @c:
         push ecx
         mov ecx,pc
         mov esi,[edx-4]  
         mov edi,[edx-8]
         repe cmpsd       
         jz @d
         pushad
         push ud
         push pc
         mov ebx,[edx-12]
         sub ebx,[edx-20]
         shr ebx,2
         mov eax,[edx-36]
         dec eax
         mul pc
         push eax
         push ebx
         push bmp1
         call cbp
         cmp eax,0
         popad
         jz @br2
         add esp,4
         jmp @br1
         @d:
         mov ebx,linesize1
         add [edx-4],ebx
         mov ebx,linesize2
         add [edx-8],ebx
         pop ecx
      loop @c
      @br1:
      add [edx-12],eax
      add [edx-16],eax
      pop ecx
   loop @b
   mov ebx,[edx-28]
   add [edx-20],ebx
   mov ebx,[edx-32]
   add [edx-24],ebx
   pop ecx
loop @a
@br2:
mov esp,edx
popad
end;
result:=true;
end;

Код

function cbp(bmp:tbitmap;x,y,pc,ud:cardinal):bool;stdcall;
begin
BitBlt(form1.Canvas.Handle,x,y,pc,pc,bmp.Canvas.Handle,x,y,SRCCOPY);
result:=true;
end;

procedure TForm1.Button1Click(Sender: TObject);
var bmp1,bmp2:tbitmap;
begin
bmp1:=TBitmap.Create;
bmp2:=TBitmap.Create;
bmp1.LoadFromFile('1.bmp');
bmp2.LoadFromFile('2.bmp');
CmpBmp(bmp1,bmp2,50,cbp,0);
end;


Автор: Чучмек 27.10.2012, 15:24
Вот, сейчас потестил, для интереса.
32битные битмапы 2000*1500
Проц AMD  AthlonII 3.1ГГц
Число сравнений в секунду, для абсолютно идентичных и для абсолютно различных битмапов. При различных N 
Код

 ------------------------------------------------
 |    N    |    ==    |    !=    |
 ------------------------------------------------
 |    1    |    17    |    15    |
 ------------------------------------------------
 |    5    |    72    |    248    |
 ------------------------------------------------
 |    10    |    74    |    918    |
 ------------------------------------------------
 |    50    |    73    |    7812    |
 ------------------------------------------------
 |    100    |    86    |    21276    |
 ------------------------------------------------
 |    500    |    101    |    166666    |
 ------------------------------------------------ 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)