PixelSearch功能效率很低,我该如何优化呢？

Question

我目前在循环中截取一个区域的屏幕截图,然后在其中搜索4个像素.这些像素的颜色相同 - 红色或$ 001300FF .使用的变量在OnCreate事件中定义和初始化:

//The variables for the area:
ScanL := 500; // Left
ScanR := 800; // Right
ScanT := 180; // Top
ScanB := 400; // Bottom

screenshot: TBitMap;
canvas : TCanvas;

要截取屏幕截图,我使用以下功能:

procedure TFormMain.GetSCREENSHOT(var a: TBitMap);
var
  Locked: Boolean;
begin
  Locked := Canvas.TryLock;
  try
    screenshot.Canvas.CopyRect(screenshot.Canvas.ClipRect, Canvas, Rect(ScanL, ScanT, ScanR, ScanB)); 
  finally
    if Locked then
      Canvas.Unlock;
  end;
end;

全局定义的变量" screenshot:TBitMap "将传递给GetSCREENSHOT函数.要搜索这4个像素,我只是做了一个新手会做的事情:

   function TFormMain.findImage : Boolean;
    var
      x,y : Integer;
    begin
      Result := false;
      for x := 0 to screenshot.Width-10 do
      begin
        for y := 0 to screenshot.Height-10 do
        begin
          if screenshot.Canvas.Pixels[x,y] = $001300FF then
          begin
            if screenshot.Canvas.Pixels[x,y+1] = $001300FF then
              if screenshot.Canvas.Pixels[x,y+2] = $001300FF then
                if screenshot.Canvas.Pixels[x,y+3] = $001300FF then
                begin
                  FoundPixelX := ScanL + x;
                  FoundPixelY := ScanT + Y;
                  Result := True;
                  Exit;
                end;
          end;
        end;
      end;
    end;

因为它表现如此糟糕,我测量了运行该函数所需的时间:

  QueryPerformanceFrequency(freq);
  QueryPerformanceCounter(startTime);

  findImage;

  QueryPerformanceCounter(endTime);
  ShowMessage('the function needs about ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');

它需要108ms!太疯狂了.我不知道为什么,我希望你能帮助我如何改进它!我认为它可能与.Pixels属性的访问有关？

比较:getSCREENSHOT不到1ms.

Answer 1

加快扫描速度可以通过几种方式完成.
首先,避免打电话给pixels.虽然方便,但它却很慢.
打电话scanline来.这使您可以直接访问位图的原始数据.

第二步是优化搜索循环.
循环像素时总是将x维放在内循环中.
因为我正在寻找4个相同颜色的像素,我可以使用简单的Knuth–Morris–Pratt优化,y每个循环增加4个(见下文).
如果我正在寻找具有不同颜色的4个像素,则此优化的实际代码会变得更加复杂.

{$pointermath on}

function TFormMain.findImage : Boolean;
var
  ScanLine, NextScanLine: PInteger;
  Stride: integer;
  MaxX: integer;
const
  MinX = 0;
  BytesPerPixel = SizeOf(integer);
  MagicColor = $001300FF; 
begin
  MaxX:= Screenshot.Width - 10;
  Assert(Screenshot.PixelFormat = pf32bit);
  Result := false;
  ScanLine:= Screenshot.ScanLine[0];
  Stride:= (NativeInt(Screenshot.ScanLine[1]) - NativeInt(ScanLine)) div BytesPerPixel; 
  y := 0
  repeat
    NextScanLine:= @ScanLine[Stride]; 
    for x:= MinX to MaxX do begin
      if (ScanLine[0] = MagicColor) then begin
        if (ScanLine[stride] = MagicColor) then begin
          if (ScanLine[stride*2] = MagicColor) then begin
            if (ScanLine[stride*3] = MagicColor) then begin
              FoundPixelX := ScanL + x;
              FoundPixelY := ScanT + Y;
              Exit(True);
            end;
          end;
        end;
      end;
      Inc(ScanLine);
    end; {for x}
    ScanLine:= NextScanLine;
    Inc(y);
  until (y > (Height - 10));
end;

注意事项
请注意,scanline[0]并scanline[1]不一定相差Width * BytePerPixel.出于对齐原因,Windows有时会在位图数据中放松一些.这就是我测试两条扫描线之间差异的原因.
在循环本身我从不称scanline这是另一种优化.

进一步优化:战舰到救援
如果你正在寻找四个相同的像素(即你喜欢的红色).你只需要扫描每4条扫描线中的1条.只要你找到一个红色像素,看起来上下(如你在经典游戏将:战列舰),看看是否有一个线的4个红色像素.
如果是这样你就找到了匹配.

在这种情况下,内循环变为:

//Start with ScanLine[3]: the fourth scanline {we start at 0}
NextScanLine:= @ScanLine[Stride*4]; 
for x:= MinX to MaxX do begin
  if (ScanLine[0] = MagicColor) then begin
    Count:=   (integer(ScanLine[-stride*3] = MagicColor) * 1 
             + integer(ScanLine[-stride*2] = MagicColor) * 2
             + integer(ScanLine[-stride*1] = MagicColor) * 4
             + 8; //The line itself
    case Count of  
      1+2+4+8: begin
        FoundPixelX := ScanL + x;
        FoundPixelY := ScanT + Y-3;
        Exit(True);
      end;
      4+8+16: if (ScanLine[stride] = MagicColor) then begin
        FoundPixelX := ScanL + x;
        FoundPixelY := ScanT + Y-2;
        Exit(True);
      end;
      8+16, 1+8+16: if (ScanLine[stride] = MagicColor) and
                       (ScanLine[stride*2] = MagicColor) then begin
        FoundPixelX := ScanL + x;
        FoundPixelY := ScanT + Y-1;
        Exit(True);
      end;
    end; {case}
    if   (ScanLine[stride] = MagicColor) and
         (ScanLine[stride*2] = MagicColor) and
         (ScanLine[stride*3] = MagicColor) then begin
      FoundPixelX := ScanL + x;
      FoundPixelY := ScanT + Y;
      Exit(True);
    end;
  end;
  Inc(ScanLine);
end; {for x}
ScanLine:= NextScanLine;
Inc(y);

在优化版本中,我使用了一些技巧来简化加速逻辑以测试匹配.
首先,我滥用快,true = 1并false = 0在比赛转换为整数.
然后我使用连续位具有值1,2,4,8等的事实来跟踪红色匹配.如果需要,我只会做进一步的测试.

我可以进一步限制内存访问次数,但这需要更多测试的代价.在Delphi生成的代码中,测试通常比内存访问要贵(微小)一点,所以我对后来的错误.

Knuth-Morris-Pratt
如果你正在寻找4个不同的像素,那么这个技巧将无法工作,你需要实现更复杂的代码.
复杂性需要CPU周期,所以我怀疑使用Knuth-Morris-Pratt会有所帮助.
当您的搜索"字符串"变长时,该特定算法的效果会更好.在搜索字符串中只有四个'字符'不足以让它闪耀.