XFEWorkflow

using System.Drawing;
using System.Text.Json.Nodes;
using XFEWorkflow.Abstractions;

namespace XFEWorkflow.Plugins.Vision;

public static partial class ImageMatcher
{
    // Similarity = 1 - mean absolute RGB error / 255. Test every pixel of each
    // surviving window. Block sums give an exact lower bound on the error;
    // they reject impossible windows without changing the similarity result.
    public static JsonArray FindSimilar(Bitmap source, Bitmap template, ScreenRegion origin, double minimumSimilarity, int maxMatches, CancellationToken ct)
    {
        if (!double.IsFinite(minimumSimilarity) || minimumSimilarity is < .01 or > 1 || maxMatches is < 1 or > 100)
            throw new ArgumentException("匹配相似度范围为 1%～100%，匹配数量范围为 1～100。");
        ct.ThrowIfCancellationRequested();
        JsonArray matches = [];
        var tw = template.Width; var th = template.Height; var sw = source.Width; var sh = source.Height;
        if (tw > sw || th > sh) return matches;
        var screen = ReadPixels(source); var target = ReadPixels(template);
        var bx = Math.Min(4, tw); var by = Math.Min(4, th);
        var xs = Enumerable.Range(0, bx + 1).Select(i => i * tw / bx).ToArray();
        var ys = Enumerable.Range(0, by + 1).Select(i => i * th / by).ToArray();
        var targetSums = new long[bx * by * 3];
        var xBlocks = Enumerable.Range(0, tw).Select(col => Array.FindIndex(xs, end => end > col) - 1).ToArray();
        var yBlocks = Enumerable.Range(0, th).Select(row => Array.FindIndex(ys, end => end > row) - 1).ToArray();
        for (var row = 0; row < th; row++)
            for (var col = 0; col < tw; col++)
            {
                var index = (yBlocks[row] * bx + xBlocks[col]) * 3; var pixel = (row * tw + col) * 3;
                for (var channel = 0; channel < 3; channel++) targetSums[index + channel] += target[pixel + channel];
            }
        // Rolling vertical bands use O(screen width) memory, including on x86.
        var columns = new long[by][]; var prefixes = new long[by][];
        for (var band = 0; band < by; band++)
        {
            columns[band] = new long[sw * 3]; prefixes[band] = new long[(sw + 1) * 3];
            for (var row = ys[band]; row < ys[band + 1]; row++)
                for (var i = 0; i < sw * 3; i++) columns[band][i] += screen[row * sw * 3 + i];
        }
        var width = sw - tw + 1; var height = sh - th + 1;
        var scores = new float[checked(width * height)]; Array.Fill(scores, -1f);
        var denominator = (double)tw * th * 3 * 255;
        var budget = (1 - minimumSimilarity) * denominator + 1e-7;
        for (var y = 0; y < height; y++)
        {
            ct.ThrowIfCancellationRequested();
            for (var band = 0; band < by; band++)
            {
                if (y > 0)
                {
                    var remove = (y - 1 + ys[band]) * sw * 3; var add = (y - 1 + ys[band + 1]) * sw * 3;
                    for (var i = 0; i < sw * 3; i++) columns[band][i] += screen[add + i] - screen[remove + i];
                }
                var prefix = prefixes[band]; var column = columns[band];
                for (var i = 0; i < sw * 3; i++) prefix[i + 3] = prefix[i] + column[i];
            }
            for (var x = 0; x < width; x++)
            {
                if ((x & 127) == 0) ct.ThrowIfCancellationRequested();
                long lowerBound = 0;
                for (var band = 0; band < by && lowerBound <= budget; band++)
                    for (var block = 0; block < bx && lowerBound <= budget; block++)
                    {
                        var left = (x + xs[block]) * 3; var right = (x + xs[block + 1]) * 3;
                        var index = (band * bx + block) * 3;
                        for (var channel = 0; channel < 3; channel++)
                            lowerBound += Math.Abs(prefixes[band][right + channel] - prefixes[band][left + channel] - targetSums[index + channel]);
                    }
                if (lowerBound > budget) continue;
                long error = 0;
                for (var row = 0; row < th && error <= budget; row++)
                {
                    ct.ThrowIfCancellationRequested();
                    var a = ((y + row) * sw + x) * 3; var b = row * tw * 3;
                    for (var i = 0; i < tw * 3; i++) error += Math.Abs(screen[a + i] - target[b + i]);
                }
                if (error <= budget) scores[y * width + x] = (float)(1 - error / denominator);
            }
        }
        // Highest similarity first; suppress overlapping windows around each
        // accepted match so a near miss cannot hide a later exact match.
        for (var count = 0; count < maxMatches; count++)
        {
            ct.ThrowIfCancellationRequested(); var best = -1; var score = -1f;
            for (var i = 0; i < scores.Length; i++)
            {
                if ((i & 65535) == 0) ct.ThrowIfCancellationRequested();
                if (scores[i] > score) { best = i; score = scores[i]; }
            }
            if (best < 0) break;
            var x = best % width; var y = best / width;
            var region = new ScreenRegion(origin.X + x, origin.Y + y, tw, th);
            var match = region.ToJson(); match["point"] = VisionParameters.Point(region.CenterX, region.CenterY); match["score"] = Math.Round(score, 4); matches.Add(match);
            for (var row = Math.Max(0, y - th + 1); row <= Math.Min(height - 1, y + th - 1); row++)
                Array.Fill(scores, -1f, row * width + Math.Max(0, x - tw + 1), Math.Min(width - 1, x + tw - 1) - Math.Max(0, x - tw + 1) + 1);
        }
        return matches;
    }
}