Bitmap in Bitmap (Black & white)

Question

Below is my attempt at bitmap in bitmap searching using 1bpp bitmaps. Any suggestions on how I can reduce complexity and improve speed? Any comment is appreciated.

using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
using System.Linq;
using System.Collections.Generic;
using System.Windows.Forms;
namespace AutoBot
{
 public partial class ActiveScreenMatch
 {
 public static bool ScreenMatch(Rectangle rect = default, string path = "")
 {
 if (rect == default && string.IsNullOrEmpty(path))
 {
 return false;
 }
 Bitmap bw;
 if (rect == default)
 {
 bw = new Bitmap(path);
 bw = bw.Clone(new Rectangle(new Point(0, 0), new Size(bw.Width, bw.Height)), PixelFormat.Format1bppIndexed);
 }
 else
 {
 bw = GetBlackWhiteAt(rect.Location, rect.Size);
 }
 /// Initialize Search image array.
 bool[][] ba1;
 using (bw)
 {
 ba1 = GetBooleanArray(bw).ToArray();
 }
 int SkippedBlackLines = 0;
 foreach (bool[] bl1 in ba1)
 {
 if (bl1.Any(x => x))
 {
 break;
 }
 else
 {
 SkippedBlackLines++;
 }
 }
 bool[][] ba2;
 using (Bitmap SearchWindow = GetBlackWhiteAt(new Point(0, 0), new Size(Screen.PrimaryScreen.Bounds.Width, Screen.PrimaryScreen.Bounds.Height)))
 {
 ba2 = GetBooleanArray(SearchWindow).ToArray();
 }
 var Base = ba1.Skip(SkippedBlackLines);
 for (int i = ba2.GetUpperBound(0); i > 0; i--)
 {
 if (SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) != -1)
 {
 if (Base.Count() == 1)
 {
 MoveTo(
 SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) + (ba1[0].Length / 2),
 i + (ba1.GetUpperBound(0) / 2));
 return true;
 }
 else
 {
 Base = Base.Take(Base.Count() - 1);
 }
 }
 }
 return false;
 }
 private static IEnumerable<bool[]> GetBooleanArray(Bitmap bitmap)
 {
 BitmapData data = bitmap.LockBits(new Rectangle(0, 0, bitmap.Width, bitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
 for (int y = 0; y <= bitmap.Height - 1; y++)
 {
 var ba2 = new bool[bitmap.Width];
 for (int x = 0; x <= bitmap.Width - 1; x++)
 {
 if (GetIndexedPixel(x, y, data) > 0)
 {
 ba2[x] = true;
 }
 }
 yield return ba2;
 }
 bitmap.UnlockBits(data);
 }
 private static int GetIndexedPixel(int x, int y, BitmapData data)
 {
 var index = (y * data.Stride) + (x >> 3);
 var mask = (byte)(0x80 >> (x & 0x7));
 byte ret = Marshal.ReadByte(data.Scan0, index);
 ret &= mask;
 return ret;
 }
 private static int SubListIndex(IEnumerable<bool> list, int start, IEnumerable<bool> sublist)
 {
 for (int listIndex = start; listIndex < list.Count() - sublist.Count() + 1; listIndex++)
 {
 int count = 0;
 while (count < sublist.Count() && sublist.ElementAt(count).Equals(list.ElementAt(listIndex + count)))
 count++;
 if (count == sublist.Count())
 return listIndex;
 }
 return -1;
 }
 private static Bitmap GetBlackWhiteAt(Point On, Size PickArea)
 {
 // Create a new bitmap.
 using (Bitmap bmp = PrintWindow())
 return bmp.Clone(new Rectangle(On, PickArea), PixelFormat.Format1bppIndexed);
 }
 private static void PrintScreen()
 {
 keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_EXTENDEDKEY, 0);
 keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_KEYUP, 0);
 }
 private static Bitmap PrintWindow()
 {
 PrintScreen();
 Application.DoEvents();
 if (Clipboard.ContainsImage())
 {
 using (Image img = Clipboard.GetImage())
 {
 if (img != null)
 {
 return new Bitmap(img);
 }
 }
 }
 return PrintWindow();
 }
 }
 public static class VKey
 {
 public readonly static byte VK_BACK = 0x08;
 public readonly static byte VK_TAB = 0x09;
 public readonly static byte VK_RETURN = 0x0D;
 public readonly static byte VK_SHIFT = 0x10;
 public readonly static byte VK_CONTROL = 0x11;
 public readonly static byte VK_MENU = 0x12;
 public readonly static byte VK_PAUSE = 0x13;
 public readonly static byte VK_CAPITAL = 0x14;
 public readonly static byte VK_ESCAPE = 0x1B;
 public readonly static byte VK_SPACE = 0x20;
 public readonly static byte VK_END = 0x23;
 public readonly static byte VK_HOME = 0x24;
 public readonly static byte VK_LEFT = 0x25;
 public readonly static byte VK_UP = 0x26;
 public readonly static byte VK_RIGHT = 0x27;
 public readonly static byte VK_DOWN = 0x28;
 public readonly static byte VK_PRINT = 0x2A;
 public readonly static byte VK_SNAPSHOT = 0x2C;
 public readonly static byte VK_INSERT = 0x2D;
 public readonly static byte VK_DELETE = 0x2E;
 public readonly static byte VK_LWIN = 0x5B;
 public readonly static byte VK_RWIN = 0x5C;
 public readonly static byte VK_NUMPAD0 = 0x60;
 public readonly static byte VK_NUMPAD1 = 0x61;
 public readonly static byte VK_NUMPAD2 = 0x62;
 public readonly static byte VK_NUMPAD3 = 0x63;
 public readonly static byte VK_NUMPAD4 = 0x64;
 public readonly static byte VK_NUMPAD5 = 0x65;
 public readonly static byte VK_NUMPAD6 = 0x66;
 public readonly static byte VK_NUMPAD7 = 0x67;
 public readonly static byte VK_NUMPAD8 = 0x68;
 public readonly static byte VK_NUMPAD9 = 0x69;
 public readonly static byte VK_MULTIPLY = 0x6A;
 public readonly static byte VK_ADD = 0x6B;
 public readonly static byte VK_SEPARATOR = 0x6C;
 public readonly static byte VK_SUBTRACT = 0x6D;
 public readonly static byte VK_DECIMAL = 0x6E;
 public readonly static byte VK_DIVIDE = 0x6F;
 public readonly static byte VK_F1 = 0x70;
 public readonly static byte VK_F2 = 0x71;
 public readonly static byte VK_F3 = 0x72;
 public readonly static byte VK_F4 = 0x73;
 public readonly static byte VK_F5 = 0x74;
 public readonly static byte VK_F6 = 0x75;
 public readonly static byte VK_F7 = 0x76;
 public readonly static byte VK_F8 = 0x77;
 public readonly static byte VK_F9 = 0x78;
 public readonly static byte VK_F10 = 0x79;
 public readonly static byte VK_F11 = 0x7A;
 public readonly static byte VK_F12 = 0x7B;
 public readonly static byte VK_NUMLOCK = 0x90;
 public readonly static byte VK_SCROLL = 0x91;
 public readonly static byte VK_LSHIFT = 0xA0;
 public readonly static byte VK_RSHIFT = 0xA1;
 public readonly static byte VK_LCONTROL = 0xA2;
 public readonly static byte VK_RCONTROL = 0xA3;
 public readonly static byte VK_LMENU = 0xA4;
 public readonly static byte VK_RMENU = 0xA5;
 }
}

• BanMe: Partitioning to me is bad in this case, as it gives way to a match on the boundary of the split leading to a 'non-completable' search pattern. This is unacceptable to me, so rather than fail with one. How do I Concurrently run the Left half, Right half, the top half, and bottom half and whole and cancel them all when one is successful?
• BanMe: Instead of doing the detection in parallel, I redid that portion to simply check the whole screen.

Answer 1

Ok so let's focus on this part the actual search routine.

 for (int i = ba2.GetUpperBound(0); i > 0; i--)
 {
 if (SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) != -1)
 {
 if (Base.Count() == 1)
 {
 MoveTo(
 SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) + (ba1[0].Length / 2),
 i + (ba1.GetUpperBound(0) / 2));
 return true;
 }
 else
 {
 Base = Base.Take(Base.Count() - 1);
 }
 }
 }
 return false;

This routine resizes the search Image on each successful pass instead of iterating it

The amount of checking when finding a potential match can be reduced to 3 checks.

 var m = SearchImage.Length - 1;
 for (int i = SearchArea.GetUpperBound(0); i > 0; i--)
 {
 if (SubListIndex(SearchArea[i].AsEnumerable(), 0, SearchImage[m]) != -1)
 {
 int x;
 if (SubListIndex(SearchArea[i - m].AsEnumerable(), 0, SearchImage[0]) != -1)
 {
 if (SubListIndex(SearchArea[i - (m / 2)].AsEnumerable(), 0, SearchImage[m / 2]) != -1)
 {
 x = SubListIndex(SearchArea[i - m].AsEnumerable(), 0, SearchImage[0]);
 }
 else
 {
 continue;
 }
 }
 else
 {
 continue;
 }
 if (x != -1)
 {
 return new Point(x + (SearchImage.Length / 2), (SearchImage.Length / 2) + i);
 }
 }
 }
 return default;

Linq version, reduces Search Area, by directly checking Target sequence in Search Area Instead of using SubListIndex.

 var m = SearchImage.Length - 1;
 return (from line in Enumerable.Range(0, SourceArea.GetUpperBound(0))
 let Index = SubListIndex(SourceArea[line].AsEnumerable(), 0, TargetArea[m])
 where Index != -1
 let Test = SourceArea[line - m].AsEnumerable().Skip(Index).SequenceEqual(TargetArea[0])
 let Test2 = SourceArea[line - (m / 2)].AsEnumerable().Skip(Index).SequenceEqual(TargetArea[m / 2])
 where Test && Test2
 select new Point(Index + (TargetArea[0].Length / 2), line + (TargetArea.Length / 2))).FirstOrDefault();

Answer 2

That last linq routine was half baked. Moving to a more Drier Approach for bitmap handling.

First here is the new Search Routine

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Windows.Forms;
namespace AutoBot
{
 public partial class ActiveScreenMatch
 {
 public static Point ScreenMatch(BitData Target = default)
 {
 if (Target == default)
 {
 return default;
 }
 var TargetArea = Target.GetBitData();
 int SkippedBlackLines = 0;
 foreach (bool[] bl1 in TargetArea)
 {
 if (bl1.Any(x => x))
 {
 break;
 }
 else
 {
 SkippedBlackLines++;
 }
 }
 TargetArea = TargetArea.Skip(SkippedBlackLines).ToArray();
 Bitmap SourceImage = GetBlackWhiteAt(new Point(0, 0), new Size(Screen.PrimaryScreen.Bounds.Width, Screen.PrimaryScreen.Bounds.Height));
 BitData SourceData = new BitData(dataMap: SourceImage);
 var SourceArea = SourceData.GetBitData();
 SourceImage.Dispose();
 var m = TargetArea.Count() -1;
 return (from line in Enumerable.Range(0, SourceArea.Count() - 1)
 let Index = SubListIndex(SourceArea.ElementAt(line), 0, TargetArea.ElementAt(0))
 where Index != -1 && Index != 0 && line > m
 let SourceLast = SourceArea.ElementAt(line + m).Skip(Index).Take(TargetArea.ElementAt(0).Length).ToArray()
 let TargetLast = TargetArea.ElementAt(m).ToArray()
 let SourceMid = SourceArea.ElementAt(line + (m/2)).Skip(Index).Take(TargetArea.ElementAt(0).Length).ToArray()
 let TargetMid = TargetArea.ElementAt(m/2).ToArray()
 where TargetLast.SequenceEqual(SourceLast) && TargetMid.SequenceEqual(SourceMid)
 select new Point(Index + (TargetArea.ElementAt(0).Length / 2), line + (TargetArea.ElementAt(0).Length / 2))).FirstOrDefault();
 }
 [MethodImpl(MethodImplOptions.AggressiveInlining)]
 private static int SubListIndex(IEnumerable<bool> list, int start, IEnumerable<bool> sublist)
 {
 for (int listIndex = start; listIndex < list.Count() - sublist.Count() + 1; listIndex++)
 {
 int count = 0;
 while (count < sublist.Count() && sublist.ElementAt(count).Equals(list.ElementAt(listIndex + count)))
 count++;
 if (count == sublist.Count())
 return listIndex;
 }
 return -1;
 }
 public static Bitmap GetBlackWhiteAt(Point On, Size PickArea)
 {
 // Create a new bitmap.
 using (Bitmap bmp = PrintWindow())
 return bmp.Clone(new Rectangle(On, PickArea), PixelFormat.Format1bppIndexed);
 }
 private static void PrintScreen()
 {
 keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_EXTENDEDKEY, 0);
 keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_KEYUP, 0);
 }
 private static Bitmap PrintWindow()
 {
 PrintScreen();
 Application.DoEvents();
 if (Clipboard.ContainsImage())
 {
 using (Image img = Clipboard.GetImage())
 {
 if (img != null)
 {
 img.Save("Output.PNG", ImageFormat.Png);
 return new Bitmap(img);
 }
 }
 }
 return PrintWindow();
 }
 }
 public static class VKey
 {
 public readonly static byte VK_BACK = 0x08;
 public readonly static byte VK_TAB = 0x09;
 public readonly static byte VK_RETURN = 0x0D;
 public readonly static byte VK_SHIFT = 0x10;
 public readonly static byte VK_CONTROL = 0x11;
 public readonly static byte VK_MENU = 0x12;
 public readonly static byte VK_PAUSE = 0x13;
 public readonly static byte VK_CAPITAL = 0x14;
 public readonly static byte VK_ESCAPE = 0x1B;
 public readonly static byte VK_SPACE = 0x20;
 public readonly static byte VK_END = 0x23;
 public readonly static byte VK_HOME = 0x24;
 public readonly static byte VK_LEFT = 0x25;
 public readonly static byte VK_UP = 0x26;
 public readonly static byte VK_RIGHT = 0x27;
 public readonly static byte VK_DOWN = 0x28;
 public readonly static byte VK_PRINT = 0x2A;
 public readonly static byte VK_SNAPSHOT = 0x2C;
 public readonly static byte VK_INSERT = 0x2D;
 public readonly static byte VK_DELETE = 0x2E;
 public readonly static byte VK_LWIN = 0x5B;
 public readonly static byte VK_RWIN = 0x5C;
 public readonly static byte VK_NUMPAD0 = 0x60;
 public readonly static byte VK_NUMPAD1 = 0x61;
 public readonly static byte VK_NUMPAD2 = 0x62;
 public readonly static byte VK_NUMPAD3 = 0x63;
 public readonly static byte VK_NUMPAD4 = 0x64;
 public readonly static byte VK_NUMPAD5 = 0x65;
 public readonly static byte VK_NUMPAD6 = 0x66;
 public readonly static byte VK_NUMPAD7 = 0x67;
 public readonly static byte VK_NUMPAD8 = 0x68;
 public readonly static byte VK_NUMPAD9 = 0x69;
 public readonly static byte VK_MULTIPLY = 0x6A;
 public readonly static byte VK_ADD = 0x6B;
 public readonly static byte VK_SEPARATOR = 0x6C;
 public readonly static byte VK_SUBTRACT = 0x6D;
 public readonly static byte VK_DECIMAL = 0x6E;
 public readonly static byte VK_DIVIDE = 0x6F;
 public readonly static byte VK_F1 = 0x70;
 public readonly static byte VK_F2 = 0x71;
 public readonly static byte VK_F3 = 0x72;
 public readonly static byte VK_F4 = 0x73;
 public readonly static byte VK_F5 = 0x74;
 public readonly static byte VK_F6 = 0x75;
 public readonly static byte VK_F7 = 0x76;
 public readonly static byte VK_F8 = 0x77;
 public readonly static byte VK_F9 = 0x78;
 public readonly static byte VK_F10 = 0x79;
 public readonly static byte VK_F11 = 0x7A;
 public readonly static byte VK_F12 = 0x7B;
 public readonly static byte VK_NUMLOCK = 0x90;
 public readonly static byte VK_SCROLL = 0x91;
 public readonly static byte VK_LSHIFT = 0xA0;
 public readonly static byte VK_RSHIFT = 0xA1;
 public readonly static byte VK_LCONTROL = 0xA2;
 public readonly static byte VK_RCONTROL = 0xA3;
 public readonly static byte VK_LMENU = 0xA4;
 public readonly static byte VK_RMENU = 0xA5;
 }
}

And the BitData Class

using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
namespace AutoBot
{
 public class BitData
 {
 private Rectangle DataRect { get; }
 private string DataPath { get; }
 private Stream DataStream { get; }
 private Image DataImage { get; }
 private Bitmap DataMap { get; }
 public IEnumerable<bool[]> GetBitData()
 {
 if (DataMap == default && DataRect == default && string.IsNullOrEmpty(DataPath) && DataStream == default && DataImage == default)
 {
 return default;
 }
 Bitmap TargetImage;
 if (DataMap != default)
 {
 TargetImage = DataMap;
 }
 else if (DataRect != default)
 {
 TargetImage = ActiveScreenMatch.GetBlackWhiteAt(DataRect.Location, DataRect.Size);
 }
 else if (!string.IsNullOrEmpty(DataPath))
 {
 if (File.Exists(DataPath))
 {
 using (var Image = new Bitmap(DataPath))
 TargetImage = Image.Clone(new Rectangle(new Point(0, 0), new Size(Image.Width, Image.Height)), PixelFormat.Format1bppIndexed);
 }
 else
 {
 return default;
 }
 }
 else if (DataStream != default)
 {
 using (var Image = new Bitmap(DataStream))
 TargetImage = Image.Clone(new Rectangle(new Point(0, 0), new Size(Image.Width, Image.Height)), PixelFormat.Format1bppIndexed);
 }
 else
 {
 using (var Image = new Bitmap(DataImage))
 TargetImage = Image.Clone(new Rectangle(new Point(0, 0), new Size(Image.Width, Image.Height)), PixelFormat.Format1bppIndexed);
 }
 var Array = GetBooleanArray(TargetImage);
 TargetImage.Dispose();
 return Array;
 }
 public BitData(Rectangle dataRect = default, string dataPath = default, Stream dataStream = default, Image dataImage = default, Bitmap dataMap = default)
 {
 DataRect = dataRect;
 DataPath = dataPath;
 DataStream = dataStream;
 DataImage = dataImage;
 DataMap = dataMap;
 }
 [MethodImpl(MethodImplOptions.AggressiveInlining)]
 private static IEnumerable<bool[]> GetBooleanArray(Bitmap bitmap)
 {
 BitmapData data = bitmap.LockBits(new Rectangle(0, 0, bitmap.Width, bitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
 bool[][] ba2 = new bool[bitmap.Height][];
 for (int y = 0; y <= bitmap.Height - 1; y++)
 {
 ba2[y] = new bool[bitmap.Width];
 for (int x = 0; x <= bitmap.Width - 1; x++)
 {
 if (GetIndexedPixel(x, y, data) > 0)
 {
 ba2[y][x] = true;
 }
 }
 }
 bitmap.UnlockBits(data);
 return ba2;
 }
 [MethodImpl(MethodImplOptions.AggressiveInlining)]
 private static int GetIndexedPixel(int x, int y, BitmapData data)
 {
 var index = (y * data.Stride) + (x >> 3);
 var mask = (byte)(0x80 >> (x & 0x7));
 byte ret = Marshal.ReadByte(data.Scan0, index);
 ret &= mask;
 return ret;
 }
 }
}

I think this version is much improved and would greatly appreciate another's eye.

• BanMe: I can optimize it even further, With BitVector32 for size, and doing a competition style search where one thread searches top-down, and another thread searches down up to ensure speed, use WaitHanlde WaitAny(). I would like to turn the source search area into a plane, and my target into a 4x4 matrix and subtract from the plane, but I think it would be hard to ensure it was put together in the same way that results in the same matrix being created in the plane. I am not sure if I can do that, so more research is needed from me.