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;
    }
}

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, Feb 3, 2020 at 1:45
Instead of doing the detection in parallel, I redid that portion to simply check the whole screen. — BanMe, Feb 3, 2020 at 18:45

BanMe · Accepted Answer · 2020-02-05 23:18:15Z

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();

BanMe · Accepted Answer · 2020-02-06 16:22:00Z

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.

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. — BanMe, Feb 7, 2020 at 16:31

Stack Exchange Network

Bitmap in Bitmap (Black & white)

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
c#
image
bitwise
or ask your own question.

Hot Network Questions

Bitmap in Bitmap (Black & white)

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c#imagebitwise or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c#
image
bitwise
or ask your own question.