Augmented reality для Dota2

Предлагаю вашему вниманию суровую историю о разработке программы машинного зрения под Android с использованием OpenCV. Задача такова — необходимо распознать вражеских героев на экране и показать победоносную комбинацию для своей команды.



План работ


  • Распознать иконки героев на изображении плохого качества с искажениями;
  • Провести анализ выбранных героев и подобрать для каждой команды хорошую комбинацию;
  • Показать результат.

Для начала было решено разработать x86 приложение (C++ / OpenCV), позже портировать под Android с реальной камерой. Нужен был быстрый и точный алгоритм сравнения изображений. После продолжительного поиска выяснились наиболее популярные подходы:

  • Simple euclidean distance
  • Cross Correlation
  • Histogram comparison
  • Detectors of salient points/areas

Остальные варианты отброшены как слишком сложные или не реализованные в OpenCV.

В ходе экспериментов стало понятно, что необходимо сначала распознать контуры героев, а уже потом сравнивать их содержимое с оригинальными иконками. Искать на большом скриншоте маленькую иконку с помощью template matching очень медленно. Принцип работы такой:

  • Подготовить двоичную маску иконок
  • Найти контуры
  • Отфильтровать ложные срабатывания
  • Запустить потоки распознавания

Оригинальное изображение:



Маска:



Контуры героев:



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

Для распознавания иконок был написан крутой велосипед, который комбинировал cv::matchTemplate для ранней фильтрации и cv::FlannBasedMatcher для точного сравнения. На базе этих коэффициентов вычислялся вес похожести и возвращался герой с наивысшим весом.

Долго боролся с проблемой сравнения похожих иконок, но в итоге забил, т.к. редкое явление. Например, входное изображение A распознается как герой C:



Итого, по результатам распознавания погрешность около 10%, один кадр на Core i5 вычисляется до 200ms, на Nexus7 до 2sec. Наверняка можно много чего оптимизировать, но для прототипа было достаточно.

Основной функционал приложения был готов, оставалось портировать его на Android, добавить поддержку камеры и отобразить результат. Тут я очень сильно ошибался, около 70% времени работы над приложением ушло на борьбу с багами Android на разных устройствах.

Особенно порадовал camera API. Управление фокусом, разрешение видео искателя и фотографии – все это может вызвать проблемы вплоть до полного зависания. Советую тестировать на малобюджетных китайских телефонах, чтобы поймать максимум багов.

Стоит упомянуть, что JNI это боль. Поэтому я решил просто передавать данные в ByteBuffer. Да, есть всякие генераторы вроде SWIG, но они ужасно громоздкие и код выхлопа страшный.

Небольшой совет по оптимизации размера apk. Весь native код я собрал в одну shared library и удалил лишнее, в результате общий размер сократился в 3 раза:

CFLAGS := -DANDROID_NDK -DNDEBUG -O3 -Ofast -flto -fvisibility=hidden -ffunction-sections -fdata-sections
LDFLAGS := -Wl,--gc-sections -Wl,--exclude-libs=ALL

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 24

    +1
    А как приложение учитывает кривизну рук игроков при подборе «победной комбинации»?
      0
      В планах было получать статистику по игроку через dotabuff и давать приоритет лучшим героям. Но не судьба.
        0
        Даже для такого подхода вам нужно для начала получить статистику по героям у соперников. Потому что даже если герой как-бы контрится, но при винрейте 60-70+ есть вероятность что просто взять контрпик будет недостаточно. НУ это само собой не работает со скрытыми профилями. А значит в текущей реализации приложение чуть меньше чем бесполезное.

        Помимо контрпиков нужно еще и синергию героев учитывать и навыки игроков, учитывать лайнинг и т.д. Слишком много неизвестных.
          0
          А значит в текущей реализации приложение чуть меньше чем бесполезное.


          Вы люто бешено категоричны. Вся дота построена на контр пиках. Синергию конечно стоит учитывать, но это лучше отдать на откуп игрокам.
            0
            Ну я посмотрю как Вам поможет контрпик, когда с Вами вместе попадется 4 ракообразных не очень хорошо играющих существа.
              0
              Вообще-то в игре есть рейтинг. Поэтому такие ситуации редки.
                0
                Знаете мне и на 6000+ попадаются интересные особы. Никто не застрахован.
                  0
                  купленные акки
                    0
                    Ну тогда вернемся к тому что Синергию 100-пудово нужно учитывать. А точнее ее учет должен быть на первом месте.
            +1
            Можно вообще создать сервис сразу для компа. Нажал комбинацию — распознал героей, показал на экране что пикать.
            При этом будут учитываться профили по дотабафу. Более того — если профиль закрыт, то тут в игру вступает популярность. Т.е. для использования сервиса надо дать доступ к своим данным. И в итоге, чем больше человек использует — тем проще контрпикать.
            Но тут есть одна беда — у обычных игроков будет меньше шансов.
            Хотя возможно наоборот, игра будет как раз веселее, ведь пик будет балансным, и все будет уже зависеть от игроков.
            • НЛО прилетело и опубликовало эту надпись здесь
                –1
                Вы наверно про-дотер, на рейтинге 2000-2500 победа это хотя бы не пикнуть бесполезного героя.
                  0
                  Не бесполезный герой еще может быть сложен в реализации. 4500-4700.
                    0
                    Бред, 2500 отнюдь не плохой уровень.
                    P. S. В системе MMR что-то очень сильно поломано. ИМХО рандом лучше.
                    • НЛО прилетело и опубликовало эту надпись здесь
                  –1
                  Мои друзья делают сбор статистики пик к пику, чтобы находить контр-пики, сайт dota2picker.com. Если есть что с ними обсудить, могу дать контакты
                0
                Что обозначают подобранные герои, которые отображает приложение? Это связанные пятерки или одиночные герои? По каким параметрам они подбираются и какие показатели при этом учитываются?
                  –1
                  Я думаю здесь взялиdotaedge.com
                    +1
                    Приложение показывает наиболее удачных героев по мнению dotabuff. Там у каждого героя есть поле best versus и worst versus которые dotabuff вычисляет по своим алгоритмам на базе собранной статистики. Генератор крутых пиков планировался на потом.
                      +2
                      Не хочу уходить в терминологию и тонкости, которые могут быть не понятны людям, далеким от dota, но удачность контрпика на основе best/worst одиночных героев даст больше вреда чем пользы, потому как в данный конкретный момент основной профит все же идет от связок героев ( два и более ), когда, например, очень слабые сами по себе слабые саппорты дают много больше пользы в связке, чем более менее сильные в одиночку.
                    0
                    А почему не десктопное приложение? Можно было бы прямо поверх интерфейса Доты рисовать.
                      +2
                      И список героев можно было бы взять тупо из памяти.
                        +1
                        Может защита от «античит» системы? Все процессы в памяти анализируются в ммо играх для борьбы с ботами…
                        +2
                        Очень давно уже есть мысль хотя бы снять более менее достоверную статистику по контрпикам героев, связкам и прочим, но слишком много неизвестных в итоге и вся статистика нивелируется. Вот несколько пунктов, которые нужно учитывать:

                        1. Личный скилл

                        В команде нужно два саппорта, но статистика игроков в команде по саппортам ниже плинтуса

                        2. Лайнинг

                        Та самая ситуация, когда трое хотят мид :) либо невозможность объяснить нестандартную расстановку героев

                        3. Адекватность и возраст

                        Беспощадный русский паб, когда все хотят идти убивать ( я не саппорт, а керри )

                        4. Новые патчи

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

                        5. Уровень алкоголя в крови игроков твоей любимой команды

                        Тут все понятно. =)

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое