如何实现位图的最小分配搜索？

Question

首先，我的问题是，找到一种新的方法来实现快速有效的图像搜索，并尝试使其超过0.65〜.80 ms的时间。

到目前为止，我已经通过使用并行不安全位图解析，对初始索引后的各部分进行排序以及许多其他的减少进行了广泛的改进。但是让我难以理解的是一种不使用中介来存储和比较数据的方法，额外的好处还包括最小化对搜索到的位图的解析（即在对目标进行解析搜索时）。

因此，鉴于此算法，我该怎么做才能对其进行修改以实现此目的？

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public unsafe static Point InMemSearch(Bitmap Haystack, Bitmap NeedleStack)
    {
        if (NeedleStack == null)
            throw new System.ArgumentNullException(nameof(NeedleStack));

        if (Haystack == null)
        {
            return default;
        }

        BitmapData Stack = Haystack.LockBits(new Rectangle(0, 0, Haystack.Width, Haystack.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
        BitmapData Needle = NeedleStack.LockBits(new Rectangle(0, 0, NeedleStack.Width, NeedleStack.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
        Point p = default;
        bool[][] NeedleBytes = new bool[Needle.Height][];
        bool[][] StackBytes = new bool[Stack.Height][];
        byte* PtrStackPixel = (byte*)Stack.Scan0;
        byte* PtrNeedlePixel = (byte*)Needle.Scan0;
        int MatchHeight = (NeedleBytes.Length - 1) / 2;

        Parallel.For(0, Stack.Height, y =>
        {
            if (y <= NeedleBytes.Length - 1)
            {
                var NeedleLine = new bool[Needle.Width - 1];
                for (int x = 0; x < Needle.Width - 1; x++)
                {
                    byte np = *(PtrNeedlePixel + (y * Needle.Stride) + (x >> 3));
                    np &= (byte)(0x80 >> (x & 0x7));
                    NeedleLine[x] = (np > 0);
                }
                if (NeedleLine.Any(x => x))
                {
                    NeedleBytes[y] = NeedleLine;
                }
            }
            StackBytes[y] = new bool[Stack.Width - 1];
            for (int x = 0; x < Stack.Width - 1; x++)
            {
                byte sp = *(PtrStackPixel + (y * Stack.Stride) + (x >> 3));
                sp &= (byte)(0x80 >> (x & 0x7));
                if (sp > 0)
                {
                    StackBytes[y][x] = true;
                }
            }
        });
        NeedleBytes = NeedleBytes.Where(x => x != null).ToArray();
        _ = Parallel.ForEach(Enumerable.Range(0, Stack.Height).Reverse(), (y, loopState) =>
          {
              var MatchPoint = ActiveScreenMatch.SubListIndex(StackBytes[y], 0, NeedleBytes[MatchHeight]);
              if (MatchPoint > -1)
              {
                  MatchHeight--;
                  if (MatchHeight == 0)
                  {
                      p = new Point(MatchPoint, y);
                      loopState.Break();
                  }
              }
              else
              {
                  MatchHeight = NeedleBytes.Length - 1;
              }
          });

        Haystack.UnlockBits(Stack);

        return p;
    }

Answer 1

这是我要实现这个想法所要做的。

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public unsafe static Point InMemSearch(Bitmap Haystack, Bitmap NeedleStack)
    {
        if (NeedleStack == null)
            throw new System.ArgumentNullException(nameof(NeedleStack));

        if (Haystack == null)
        {
            return default;
        }

        BitmapData Stack = Haystack.LockBits(new Rectangle(0, 0, Haystack.Width, Haystack.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
        BitmapData Needle = NeedleStack.LockBits(new Rectangle(0, 0, NeedleStack.Width, NeedleStack.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
        Point p = default;
        byte* PtrStackPixel = (byte*)Stack.Scan0;
        byte* PtrNeedlePixel = (byte*)Needle.Scan0;
        Dictionary<int, IEnumerable<byte>> NeedleLookup = new Dictionary<int, IEnumerable<byte>>();
        Dictionary<int, IEnumerable<byte>> StackLookup = new Dictionary<int, IEnumerable<byte>>();
        IEnumerable<byte> GetNeedleLine(int needleY)
        {
            if(NeedleLookup.ContainsKey(needleY))
            {
                return NeedleLookup[needleY];
            }
            var NeedleLine = new byte[Needle.Width];
            for (int x = 0; x < Needle.Width; x++)
            {
                byte np = *(PtrNeedlePixel + (needleY * Needle.Stride) + (x >> 3));
                np &= (byte)(0x80 >> (x & 0x7));
                NeedleLine[x] = np;
            }
            NeedleLookup.Add(needleY, NeedleLine);
            return NeedleLine;
        }
        IEnumerable<byte> GetStackLine(int stackY)
        {
            if(StackLookup.ContainsKey(stackY))
            {
                return StackLookup[stackY];
            }
            var StackLine = new byte[Stack.Width];
            for (var x = 0; x < Stack.Width; x++)
            {
                byte sp = *(PtrStackPixel + (stackY * Stack.Stride) + (x >> 3));
                sp &= (byte)(0x80 >> (x & 0x7));
                StackLine[x] = sp;
            }
            StackLookup[stackY] = StackLine;
            return StackLine;
        }
        int Bad = 0;
        while(!GetNeedleLine(0 + Bad).Any(b => b > 0))
        {
            Bad++;
        }
        int BadStackLines = 0;
        while (ActiveScreenMatch.SubListIndex(GetStackLine(Stack.Height - BadStackLines), 0, GetNeedleLine(0 + Bad)) < 0)
        {
            BadStackLines++;
        }
        p = new Point(ActiveScreenMatch.SubListIndex(GetStackLine(Stack.Height - BadStackLines), 0, GetNeedleLine(0 + Bad)), Stack.Height - BadStackLines);
        return p;
    }

它需要添加更多检查，但是它显示了它的想法，并且按原样时钟0.4+ ms。 ：）