Оптимизация сравнения двух изображений

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

Оптимизация сравнения двух изображений

Сообщение Brainenjii » 02.04.2011 09:19:49

Есть IP-камера, выдающая картинку в разрешение 640x480 в JPEG. Задача определить - произошло ли какое-то движение в кадре, для того, чтобы начать запись. Вот мой вариант:
Код: Выделить всё
Var
    bBitmap: TBitmap;
    bPicture: TPicture;
    bMemoryStream: TMemoryStream;
    bBuffer: TBitmap;

Procedure TForm1.Timer1Timer(Sender: TObject);
Var
  aPixel, aBufferedPixel: TFPColor;
  i, j, aDiff: Integer;
Begin
   aDiff := 0;
   bMemoryStream.Clear;
   HttpGetBinary('http://admin:123456@192.168.0.243/snapshot.cgi', bMemoryStream);
   bMemoryStream.Seek(0, soFromBeginning);
   bPicture.Clear;
   bBitmap.Clear;
   bPicture.LoadFromStream(bMemoryStream);
   bBitmap.SetSize(20, 20);
   bBitmap.Canvas.StretchDraw(Rect(0, 0, 20, 20) , bPicture.Bitmap);
   If bBuffer = nil Then
     Begin
       bBuffer := TBitmap.Create;
       bBuffer.Assign(bBitmap);
       Exit;
     End;
   For i := 0 To bBitmap.Width - 1 Do
     For j := 0 To bBitmap.Height - 1 Do
       Begin
         aPixel := TColorToFPColor(bBitmap.Canvas.Pixels[i, j]);
         aBufferedPixel := TColorToFPColor(bBuffer.Canvas.Pixels[i, j]);
         If Abs(aPixel.blue - aBufferedPixel.blue) +
           Abs(aPixel.red - aBufferedPixel.red) +
           Abs(aPixel.green - aBufferedPixel.green) > 5000 Then
           Inc(aDiff);
       End;
  Memo1.Lines.Insert(0, IntToStr(aDiff));
  bBuffer.Assign(bBitmap);
End;

Всё работает, на движение реагирует адекватно, но слишком уж ресурсоёмко. С графикой дела никогда не имел, так что сделано всё довольно топорно и "на глазок". Буду очень рад советам опытных коллег ^_^
Аватара пользователя
Brainenjii
энтузиаст
 
Сообщения: 1352
Зарегистрирован: 10.05.2007 00:04:46

Re: Оптимизация сравнения двух изображений

Сообщение Odyssey » 02.04.2011 10:58:55

Тут есть как минимум два тормоза:

1) Куча вычислений в цикле. Если я правильно понял, преобразование к TfpColor и обратно делается для удобного разложения цвета на составляющие. Я бы посоветовал обойтись без преобразования, и сравнивать два TColor напрямую. Алгоритм разложения TColor на составляющие с помощью битовых масок можно подсмотреть в TColorToFPColor (строчки вида "(c and <маска>)"). Сравнение полученных составляющих напрямую позволит сэкономить на изменении порядка байт с BGR (TColor) на RGBA (TfpColor). Поскольку сравнение пикселов в данном алгоритме выполняется многократно, даже небольшая оптимизация сравнения скажется на общей производительности.

2) StretchDraw - не самая быстрая операция. Может быть можно избавиться от неё вообще?

Если смотреть дальше:

3) Насколько я знаю, попиксельный доступ к канве - тоже не самая быстрая операция. С альтернативами я плохо знаком, поэтому сходу ничего не предложу, но возможно стоит поискать способы быстрого доступа к пикселам, типа Scanline.

4) В качестве ненадёжного альтернативного способа сравнения, можно посмотреть вариант предварительного сравнения изображений на уровне байт в файле. Это позволит сэкономить на чтении графического формата. Для выполнения такого сравнения нужно понять, насколько сильно различаются файлы с примерно одинаковым содержанием на уровне байтов формата хранения. Если не сильно - можно использовать это как предварительный этап сравнения. Целесообразность такого способа лучше проверять экспериментально. Он зависит формата получаемых изображений, и при частых изменениях картинки может, наоборот, замедлить общий процесс сравнения.

P.S. Как обычно, сначала написал, потом присмотрелся к коду :) Похоже что StretchDraw - основной тормоз, потому что 400 итераций для пикселей не так много. Понял, что StretchDraw используется как часть установки порога срабатывания. А что если:
* Убрать StretchDraw и просто рассчитывать число пикселей, значение цвета которых изменилось свыше установленного порога?
* Суммировать разницу значений по всем пикселам, и в случае выхода значения суммы за определённый общий порог, считать что картинка изменилась?
И вообще, наверняка есть какая-то литература по этой теме, там должны быть описаны нужные алгоритмы :)
Odyssey
энтузиаст
 
Сообщения: 581
Зарегистрирован: 29.11.2007 17:32:24

Re: Оптимизация сравнения двух изображений

Сообщение Brainenjii » 02.04.2011 12:29:15

Если убрать StretchDraw - будет пробегаться не по 400 пикселям, а по 307200. Да и картинки сами по себе получаются довольно различными и без движения - шумы и т.п. Литература-то есть, но она предусматривает какой-то уровень начальной подготовки, а я до сей поры кроме как сквозь VCL/LCL с графикой-то и не работал... Полагаю, что нужно уйти от попиксельного сравнения в сторону какого-нибудь Scanline, и, соответственно, от тяжёлых расчётов в цикле (преобразование типов/вычисление модуля).
Аватара пользователя
Brainenjii
энтузиаст
 
Сообщения: 1352
Зарегистрирован: 10.05.2007 00:04:46

Re: Оптимизация сравнения двух изображений

Сообщение Vadim » 02.04.2011 13:09:32

Мне понравилось предложение побайтового сравнения двух потоков. ;) Правда не уверен, что не будет воздействовать шум на изображении.
Vadim
долгожитель
 
Сообщения: 3661
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Оптимизация сравнения двух изображений

Сообщение Odyssey » 02.04.2011 14:01:52

Brainenjii писал(а):Если убрать StretchDraw - будет пробегаться не по 400 пикселям, а по 307200.

Верно, но ведь сама StretchDraw работает не "в обход процессора" :) Она тоже пробегается по всем 307200 пикселям, и ещё усредняет их цвета для получения более мелкой картинки. Может быть, эта функция хорошо оптимизирована, может быть нет.

Думаю, имеет смысл померить и сравнить затраты времени на обход 400 пикселей и на StretchDraw. И уже по результатам решить, стоит ли прорабатывать вариант со Scanline. Я сам пока не написал предыдущий пост, не обратил внимание что цикл всего 20х20. Даже если сильно его ускорить, даст ли это заметный прирост скорости по сравнению с отказом от (или заменой на более быстрый вариант) StretchDraw, в которой крутиться цикл 640х480?
Odyssey
энтузиаст
 
Сообщения: 581
Зарегистрирован: 29.11.2007 17:32:24

Re: Оптимизация сравнения двух изображений

Сообщение daesher » 02.04.2011 14:37:41

Поиск шума - это очень серьёзно. Я бы копал в сторону поиска минимальной разности между самими jpeg-файлами.
daesher
постоялец
 
Сообщения: 220
Зарегистрирован: 09.03.2010 22:17:14

Re: Оптимизация сравнения двух изображений

Сообщение v-t-l » 02.04.2011 19:31:45

Может быть, пригодится http://ru.wikipedia.org/wiki/OpenCV
v-t-l
энтузиаст
 
Сообщения: 703
Зарегистрирован: 13.05.2007 16:27:22
Откуда: Belarus

Re: Оптимизация сравнения двух изображений

Сообщение Сквозняк » 03.04.2011 00:04:57

А если сравнивать две картинки преобразованные в 256 цветов? При конвертировании часть лишних данных автоматически отсеется. Должен быть способ повесить преобразование на opengl :D
Сквозняк
энтузиаст
 
Сообщения: 665
Зарегистрирован: 29.06.2006 22:08:32

Re: Оптимизация сравнения двух изображений

Сообщение Brainenjii » 03.04.2011 13:17:45

Попробовал:
  • без scanline'а:
    Код: Выделить всё
    Function TForm1.BruteCompare(Const aHTTP: String;
      Var aBuffer: TPicture): Integer;
    Var
      i, j: Integer;
      aPicture: TPicture;
      aStream: TMemoryStream;
      aPixel, aBufferedPixel: TFPColor;
    Begin
      Result := -1;
      aStream := TMemoryStream.Create;;
      HttpGetBinary(aHTTP, aStream);
      aStream.Seek(0, soFromBeginning);
      aPicture := TPicture.Create;
      aPicture.LoadFromStream(aStream);
      If aBuffer = nil Then
        Begin
          aBuffer := aPicture;
          Exit;
        End;
      Result := 0;
      For i := 0 To aPicture.Height - 1 Do
        For j := 0 To aPicture.Width - 1 Do
          Begin
            aPixel := TColorToFPColor(aPicture.Bitmap.Canvas.Pixels[j, i]);
            aBufferedPixel :=
    TColorToFPColor(aBuffer.Bitmap.Canvas.Pixels[j, i]);
            Result := Abs(aPixel.red - aBufferedPixel.Red) +
              Abs(aPixel.green - aBufferedPixel.green) +
              Abs(aPixel.blue - aBufferedPixel.blue);
          End;
      aBuffer.Free;
      aBuffer := aPicture;
    End;

    atop 10 писал(а):project1: 94% // UPD: было 24%
  • со scanline'ом:
    Код: Выделить всё
    Function TForm1.NonStretchompare(Const aHTTP: String;
      Var aBuffer: TLazIntfImage): Integer;
    Var
      i, j: Integer;
      aPicture: TPicture;
      aImage: TLazIntfImage;
      aStream: TMemoryStream;
      aRow, aBufferedRow: pBruteArray;
    Begin
      Result := -1;
      aStream := TMemoryStream.Create;;
      HttpGetBinary(aHTTP, aStream);
      aStream.Seek(0, soFromBeginning);
      aPicture := TPicture.Create;
      aPicture.LoadFromStream(aStream);
      aImage := aPicture.Bitmap.CreateIntfImage;
      aPicture.Free;
      If aBuffer = nil Then
        Begin
          aBuffer := aImage;
          Exit;
        End;
      Result := 0;
      For i := 0 To aImage.Height - 1 Do
        Begin
          aRow := aImage.GetDataLineStart(i);
          aBufferedRow := aBuffer.GetDataLineStart(i);
          For j := 0 To aImage.Width - 1 Do
            Begin
              Result += Abs(aRow^[j].rgbtBlue - aBufferedRow^[j].rgbtBlue) +
                Abs(aRow^[j].rgbtGreen - aBufferedRow^[j].rgbtGreen) +
                Abs(aRow^[j].rgbtRed - aBufferedRow^[j].rgbtRed);
            End;
        End;
      aBuffer.Free;
      aBuffer := aImage;
    End;

    atop 10 писал(а):project1: 23%

  • и stretch:
    Код: Выделить всё
    Function TForm1.CycleCompare(Const aHTTP: String;
      Var aBuffer: TLazIntfImage): Integer;
    Var
      i, j: Integer;
      aBitmap: TBitmap;
      aPicture: TPicture;
      aImage: TLazIntfImage;
      aStream: TMemoryStream;
      aRow, aBufferedRow: pRGBArray;
    Begin
      Result := -1;
      aStream := TMemoryStream.Create;;
      HttpGetBinary(aHTTP, aStream);
      aStream.Seek(0, soFromBeginning);
      aPicture := TPicture.Create;
      aPicture.LoadFromStream(aStream);
      aStream.Free;
      aBitmap := TBitmap.Create;
      aBitmap.SetSize(20, 20);
      aBitmap.Canvas.StretchDraw(Rect(0, 0, 20, 20) , aPicture.Bitmap);
      aPicture.Free;
      aImage := aBitmap.CreateIntfImage;
      aBitmap.Free;
      If aBuffer = nil Then
        Begin
          aBuffer := aImage;
          Exit;
        End;
      Result := 0;
      For i := 0 To aImage.Height - 1 Do
        Begin
          aRow := aImage.GetDataLineStart(i);
          aBufferedRow := aBuffer.GetDataLineStart(i);
          For j := 0 To aImage.Width - 1 Do
            Begin
              Result += Abs(aRow^[j].rgbtBlue - aBufferedRow^[j].rgbtBlue) +
                Abs(aRow^[j].rgbtGreen - aBufferedRow^[j].rgbtGreen) +
                Abs(aRow^[j].rgbtRed - aBufferedRow^[j].rgbtRed);
            End;
        End;
      aBuffer.Free;
      aBuffer := aImage;
    End;

    atop 10 писал(а):project1: 19%
Странно, мне казалось что разница будет больше. К сожалению, не овладел valgrind'ом - где-нибудь есть хороший мануал - как разбираться в выводе valgrind/kcachevalgrind, применительно к FPC?

P.S. упс, запустил тест для первого случая с кодом второго - поэтому изначально для первых двух вариантов вышло 24% и 23% соответственно. Теперь разница существенней ^_^

P.P.S. Блин, надо овладевать valgrind'ом. Проблема оказалась не там где искал:
Код: Выделить всё

Function TForm1.CycleCompare(Const aHTTP: String;
  Var aBuffer: TLazIntfImage): Integer;
Var
  i, j: Integer;
  aBitmap: TBitmap;
  aPicture: TPicture;
  aImage: TLazIntfImage;
  aStream: TMemoryStream;
  aRow, aBufferedRow: pRGBArray;
Begin
  Result := -1;
  aStream := TMemoryStream.Create;;
  HttpGetBinary(aHTTP, aStream);
  aStream.Seek(0, soFromBeginning);
  aPicture := TPicture.Create;
  aPicture.LoadFromStream(aStream);
  aStream.Free;
  aPicture.Free;
End;


atop 10 писал(а):project1: 19%

!!! Просто загрузка файла в Stream - 2%. Как можно кошерней перевести поток в LazIntfImage? ^_^
Аватара пользователя
Brainenjii
энтузиаст
 
Сообщения: 1352
Зарегистрирован: 10.05.2007 00:04:46

Re: Оптимизация сравнения двух изображений

Сообщение Alex2013 » 19.04.2019 13:59:03

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

Код: Выделить всё
Function CompareBMP (B1,B2:TBitmap):Bool;
begin
Result:=False; If (B1<> Nil) and (B2<> Nil) then
if (B1.RawImage.DataSize>0) and (B1.RawImage.DataSize=B2.RawImage.DataSize) then
Result:= CompareByte(B1.RawImage.Data^,b2.RawImage.Data^,b1.RawImage.DataSize) = 0;
end;

Может кому-то пригодится ... :idea:
Alex2013
энтузиаст
 
Сообщения: 1469
Зарегистрирован: 03.04.2013 11:59:44

Re: Оптимизация сравнения двух изображений

Сообщение olegy123 » 19.04.2019 14:26:38

Самое простое: перевести картинку RGB в Gray и каждый пиксел двух картинок сравнивать на их разницу значение (diff) [+/-]..
Если во всем массиве diff не было abs(x)>некого порогового значения - значит картинки равны.
olegy123
энтузиаст
 
Сообщения: 1456
Зарегистрирован: 25.02.2016 12:10:20

Re: Оптимизация сравнения двух изображений

Сообщение Лекс Айрин » 19.04.2019 14:47:11

olegy123, вот не Художник ты. Иначе бы знал, что перевод в полутон может сильно исказить изображение. Иногда вплоть до неузнаваемости. Да и оттенки иногда важны. Если реально сравнивать, то по световым плоскостям. Да, намного труднее, но качество лучше. В твоём же алгоритме один маленький нюанс. Если постараться, то можно так, допустим, изменить изображение, что оно будет сильно непохоже не себя же, но до обработки. Допустим, притенить.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Оптимизация сравнения двух изображений

Сообщение Alex2013 » 19.04.2019 16:00:09

olegy123 писал(а):Самое простое: перевести картинку RGB в Gray и каждый пиксел двух картинок сравнивать на их разницу значение (diff) [+/-]..
Если во всем массиве diff не было abs(x)>некого порогового значения - значит картинки равны.

Упс ... :shock:
1 RGB в Gray...
2 каждый пиксел двух картинок сравнивать ...

Да в "глубокой сирости и убогости" объем данных будет меньше.
но по "суме технологий" ... сложнее и медленней. ( да и не точно)

А у меня на все про все по сути одна строчка(и с точностью нет проблем ):
Код: Выделить всё
Result:= CompareByte(B1.RawImage.Data^,b2.RawImage.Data^,b1.RawImage.DataSize) = 0;
Последний раз редактировалось Alex2013 19.04.2019 22:57:21, всего редактировалось 1 раз.
Alex2013
энтузиаст
 
Сообщения: 1469
Зарегистрирован: 03.04.2013 11:59:44

Re: Оптимизация сравнения двух изображений

Сообщение Лекс Айрин » 19.04.2019 19:38:26

Alex2013, а ты подними исходный код CompareByte, так, чисто для справки. Это либо цикл сравнивающий побайтно, либо его ассемблерный эквивалент. В крайнем случае сравниваться будут 2, 4 или 8 байт.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Оптимизация сравнения двух изображений

Сообщение Alex2013 » 19.04.2019 22:33:12

Фокус не в CompareByte(можно и без него обойтись) который просто под руку подвернулся ... (Хотя штуковина удобная и не такая уж простая как может показаться) Суть в доступе через RawImage.Data^ который позволяет его применить. Глянь на "наливочки из кода" (хорошо что не "простыни" ) :wink: вначале темы . (Я уж молчу про скорость доступа через Canvas.Pixels...)
Зы
Есть впечатление, что очень многие пользователи Лазаруса (включая меня) многие годы ходили "под заклятием отвода глаз" не замечая возможность использования RawImage . (Да там есть хитрость с BeginUpdate но ничего особо страшного в ней нет)
Alex2013
энтузиаст
 
Сообщения: 1469
Зарегистрирован: 03.04.2013 11:59:44

След.

Вернуться в Общее

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Рейтинг@Mail.ru