Поиск изображения в изображении

#c_sharp #cpp #распознавание_образов

Пишу автокликер для одной мобильной игры (скрин ниже). Задача находить на карте объекты.
Точнее, программа делает скриншот экрана игры запущенной в эмуляторе Bluestacks, получаю
bitmap, и нужно искать объекты на карте по фрагментам на скриншоте. Подскажите алгоритм
поиска фрагмента на изображении?


    

Ответы

Ответ 1

Использование OpenCV конечно должно быть более успешным. Я поэкспериментировал с AForge

 

получилось тоже неплохо



Вот класс работы с библиотекой, фактически само использование занимает 2 строки,
каюсь, взял эту часть из интернета, остальное написал сам

public class AforgeService
{
    //найденные совпадения
    private TemplateMatch[] _matchings;

    /// 

    /// Количество найденных совпадений
    /// 
    public int CountMatchings
    {
        get => _matchings != null ?  _matchings.Length : 0;
    }


    //ctor
    public AforgeService()
    {

    }

    /// 

    /// Содержит ли исходное изображение представленый образец
    /// 
    /// путь к файлу исходного изображения
    /// путь к файлу образца
    /// true если содержит
    public async Task IsContains(string pathOriginalImage, string pathSampleImage)
    {
        if (String.IsNullOrEmpty(pathOriginalImage)) throw new ArgumentNullException(nameof(pathOriginalImage));
        if (String.IsNullOrEmpty(pathSampleImage)) throw new ArgumentNullException(nameof(pathSampleImage));

        var sample = new Bitmap(pathSampleImage);
        var orig = new Bitmap(pathOriginalImage);

        //пользуемся библиотекой
        ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0.921f);
        _matchings = await Task.Run(() => tm.ProcessImage(orig, sample));

        return _matchings.Any();
    }


    /// 

    /// Получение коллекции найденных мест где находится образец
    /// 
    /// коллекция найденных мест
    public List GetPlaces()
    {
        List result = new List();
        if (CountMatchings == 0) return result;

        int id = 0;
        foreach (var match in _matchings)
        {
            FoundPlace place = new FoundPlace
            {
                Id = ++id,
                Similarity = match.Similarity,
                Top = match.Rectangle.Top,
                Left = match.Rectangle.Left,
                Height = match.Rectangle.Height,
                Width = match.Rectangle.Width
            };

            result.Add(place);
        }

        return result;
    }

}


Этот класс для сохранения найденного места

public class FoundPlace
{
    public int Id { get; set; }
    public double Left { get; set; }
    public double Top { get; set; }
    public double Width { get; set; }
    public double Height { get; set; }
    public double Similarity { get; set; }
}


Это класс вьюмодели

public class MainViewModel : INotifyPropertyChanged, IDisposable
{
    public event PropertyChangedEventHandler PropertyChanged;

    private readonly IMainWindow _mainWindow;
    private string _pathOriginalImage;

    //ctor
    public MainViewModel(IMainWindow mainWindow)
    {
        _mainWindow = mainWindow;
    }

    /// 

    /// Флаг запуска поиска, для выкл./вкл. кнопок
    /// 
    private bool _IsSearching;
    public bool IsSearching
    {
        get => _IsSearching;
        set
        {
            _IsSearching = value;
            SelectSampleCommand.RaiseCanExecuteChanged();
            SearchCommand.RaiseCanExecuteChanged();
        }
    }

    /// 

    /// Исходное изображение (поле игры)
    /// 
    public string OriginalImage
    {
        get => @"~\..\Assets\Original.jpg";
    }

    /// 

    /// Образец для поиска
    /// 
    private string _SampleImage;
    public string SampleImage
    {
        get => _SampleImage;
        set
        {
            _SampleImage = value;
            PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(SampleImage)));
            SearchCommand.RaiseCanExecuteChanged();
        }
    }

    /// 

    /// Текстовое сообщение о процессе
    /// 
    private string _Message;
    public string Message
    {
        get => _Message;
        set
        {
            _Message = value;
            PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(Message)));
        }
    }

    /// 

    /// Список найденных мест для ListBox
    /// 
    private List _Places;
    public List Places
    {
        get { return _Places; }
        set
        {
            _Places = value;
            PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(Places)));
        }
    }

    private FoundPlace _SelectedPlace;
    public FoundPlace SelectedPlace
    {
        get => _SelectedPlace;
        set
        {
            _SelectedPlace = value;
            PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(SelectedPlace)));
            _mainWindow.DrawPlace(_SelectedPlace);
        }
    }



    /// 

    /// Кнопка Выбрать
    /// 
    private RelayCommand _SelectSampleCommand;
    public RelayCommand SelectSampleCommand
    {
        get => _SelectSampleCommand = _SelectSampleCommand ?? new RelayCommand(OnSelectSample,
CanSelectSample);
    }
    private bool CanSelectSample()
    {
        if (IsSearching)
        {
            return false;
        }
        return true;
    }
    private void OnSelectSample()
    {
        string file = _mainWindow.SelectSample();
        if (String.IsNullOrEmpty(file)) return;

        SampleImage = file;
    }

    /// 

    /// Кнопка Искать
    /// 
    private RelayCommand _SearchCommand;
    public RelayCommand SearchCommand
    {
        get => _SearchCommand = _SearchCommand ?? new RelayCommand(OnSearch, CanSearch);
    }
    private bool CanSearch()
    {
        if (String.IsNullOrEmpty(SampleImage) || IsSearching)
        {
            return false;
        }
        return true;
    }
    private async void OnSearch()
    {
        Message = "Ждите...";
        IsSearching = true;
        AforgeService service = new AforgeService();

        try
        {
            using (OverrideCursor cursor = OverrideCursor.GetWaitOverrideCursor())
            {
                string pathOrigin = GetOriginalImage();
                bool isContains = await service.IsContains(pathOrigin, SampleImage);
                if (isContains)
                {
                    Places = service.GetPlaces();
                }
                else
                {
                    Places = new List();
                }
            }
        }
        catch (Exception ex)
        {
            var message = $"Возникла ошибка: {ex.Message}";
            _mainWindow.ShowMessage(message, "Ошибка");
        }
        finally
        {
            Message = $"Найдено мест: {service.CountMatchings}";
            IsSearching = false;
        }
    }

    /// 

    /// Получение пути к оригинальному изображению (полю игры)
    /// 
    /// 
    private string GetOriginalImage()
    {
        if (!String.IsNullOrEmpty(_pathOriginalImage) && File.Exists(_pathOriginalImage))
        {
            return _pathOriginalImage;
        }

        _pathOriginalImage = Path.Combine(Path.GetTempPath(), "Original.jpg");


        Uri imgUri = new Uri("pack://application:,,,/Assets/Original.jpg");
        StreamResourceInfo imgStream = Application.GetResourceStream(imgUri);

        using (Stream imgs = imgStream.Stream)
        using (FileStream fs = File.Create(_pathOriginalImage))
        {
            byte[] ar = new byte[imgs.Length];
            imgs.Read(ar, 0, ar.Length);

            fs.Write(ar, 0, ar.Length);
        }

        return _pathOriginalImage;
    }

    /// 

    /// IDisposable
    /// 
    public void Dispose()
    {
        if (!String.IsNullOrEmpty(_pathOriginalImage) && File.Exists(_pathOriginalImage))
        {
            File.Delete(_pathOriginalImage);
        }
    }
}


Весь пример можно скачать здесь


Ответ 2

Думаю, тебе хватит функционала реализованного в OpenCV


  OpenCV (англ. Open Source Computer Vision Library, библиотека компьютерного зрения
с открытым исходным кодом) — библиотека алгоритмов компьютерного зрения, обработки
изображений и численных алгоритмов общего назначения с открытым кодом.


(с) Википедия.

Вот неплохие уроки по ней, а вот то, что тебе в теории может пригодиться.


Ответ 3

Есть большая, сложная и популярная область технологий, называемая распознанием образов.
По большей части там используются глубокие нейронные сети, но не только. И вряд ли
в Вашем случае нужна такая сложность (хотя и может вдохновить на правильный вектор
дальнейших действий).

Простой способ – разбить игровое поле на части (кажется, в данной игре это особенно
актуально) и сверять каждую часть на сходство с известными предметами. Если же предметы
могут находиться в случайных местах, а не только на заданной сетке, то нужен более
продвинутый анализ: можно сначала сверять по сетке, затем по той же сетке со смещение
на половину (или даже треть и две трети). Ещё можно масштабировать, брать некий хэш
от части изображения... 

Кстати, если не удастся добиться 99% точности (что в принципе возможно, ведь все
предметы будут статично, а не поворачиваться под разным освещением, как в реальном
мире), то можно компенсировать точность продуманностью кликов: сохранять позиции, куда
уже безуспешно кликах, чтобы в следующие разы не тупить, не тратить время. Тогда главное,
чтобы алгоритм поиска выдавал как можно меньше ложно отрицательных срабатываний, а
ложно положительные будут быстро отсекаться на практике.

Полезные ссылки:


Закрытый вопрос на ruSO, но всё же с некоторыми интересными идеями.
Статья о распознании образов (Хабр)
Метод Виолы-Джонса для поиска и распознания лиц (Хабр)


Ответ 4

Если нужно искать на изображении фрагмент этого изображения, а не что-то отдаленно
напоминающее фрагмент, нет ничего лучше, чем корреляционный метод. Быстро и надежно.
И не нужно никакого распознавания.