performance - 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 花费的时间不到 1 毫秒。

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 生成的测试通常比内存访问贵一点(一点点)，所以我犯了后者的错误。

高德-莫里斯-普拉特
如果您正在寻找 4 个不同的像素，则该技巧将不起作用，您将需要实现更复杂的代码。
复杂性会消耗 CPU 周期，因此我怀疑使用 Knuth-Morris-Pratt 会有帮助。
当您的搜索“字符串”变长时，该特定算法的效果会更好。搜索字符串中只有四个“字符”不足以使其发光。