Предлагаю вашему вниманию суровую историю о разработке программы машинного зрения под 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

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


  1. SKY_nv
    15.06.2015 21:31
    +1

    А как приложение учитывает кривизну рук игроков при подборе «победной комбинации»?


    1. realimba Автор
      15.06.2015 21:33

      В планах было получать статистику по игроку через dotabuff и давать приоритет лучшим героям. Но не судьба.


      1. SKY_nv
        15.06.2015 21:37

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

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


        1. AtomKrieg
          16.06.2015 04:15

          А значит в текущей реализации приложение чуть меньше чем бесполезное.


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


          1. Aios
            24.06.2015 17:50

            Ну я посмотрю как Вам поможет контрпик, когда с Вами вместе попадется 4 ракообразных не очень хорошо играющих существа.


            1. AtomKrieg
              26.06.2015 10:40

              Вообще-то в игре есть рейтинг. Поэтому такие ситуации редки.


              1. Aios
                26.06.2015 11:08

                Знаете мне и на 6000+ попадаются интересные особы. Никто не застрахован.


                1. AtomKrieg
                  26.06.2015 19:08

                  купленные акки


                  1. Aios
                    26.06.2015 19:30

                    Ну тогда вернемся к тому что Синергию 100-пудово нужно учитывать. А точнее ее учет должен быть на первом месте.


        1. BupycNet
          16.06.2015 06:05
          +1

          Можно вообще создать сервис сразу для компа. Нажал комбинацию — распознал героей, показал на экране что пикать.
          При этом будут учитываться профили по дотабафу. Более того — если профиль закрыт, то тут в игру вступает популярность. Т.е. для использования сервиса надо дать доступ к своим данным. И в итоге, чем больше человек использует — тем проще контрпикать.
          Но тут есть одна беда — у обычных игроков будет меньше шансов.
          Хотя возможно наоборот, игра будет как раз веселее, ведь пик будет балансным, и все будет уже зависеть от игроков.


        1. Temirkhan
          16.06.2015 09:22

          Может тогда уж сразу на ИИ сфокусироваться, который будет выбирать и играть заместо игроков? К чему вся эта возня? Ладно, быстрая напоминалка соотношений контрпиков, но вести подсчет всех карт в игре — это уже перебор.


        1. josser
          16.06.2015 09:40
          -1

          Вы наверно про-дотер, на рейтинге 2000-2500 победа это хотя бы не пикнуть бесполезного героя.


          1. SKY_nv
            16.06.2015 10:43

            Не бесполезный герой еще может быть сложен в реализации. 4500-4700.


          1. VioletGiraffe
            16.06.2015 23:34

            Бред, 2500 отнюдь не плохой уровень.
            P. S. В системе MMR что-то очень сильно поломано. ИМХО рандом лучше.


            1. Temirkhan
              17.06.2015 09:01

              Вы правы лишь отчасти. Однако, система ММР — это не то, что воспринимается, как уровень игры. Это психологический портрет. Люди, у которых ММР ниже 2000, часто могут превосходить игроков с 3000-3500 ммр по всем игровым пунктам (фарм, добивания, закупка предметов, подбор героев, манипуляция игровой механикой и т.д). Однако, последние имеют более устойчивую психику(решения более обдуманы, решения анализируются не только за своего героя, но всю команду. Настрой на победу и позитивное отношение к команде тянутся дольше, чем у первых. И, как результат, они всегда или почти всегда побеждают у первых. Точно так же отличаются игроки 3-3.5к от более высоких рангов. Это не шкала от 0 до 10. Это аттрибуты, которые есть у игроков более высокого ранга, и, которых нет у более низких.


      1. Wigaro
        16.06.2015 00:23
        -1

        Мои друзья делают сбор статистики пик к пику, чтобы находить контр-пики, сайт dota2picker.com. Если есть что с ними обсудить, могу дать контакты


  1. Smi1e
    15.06.2015 22:22

    Что обозначают подобранные герои, которые отображает приложение? Это связанные пятерки или одиночные герои? По каким параметрам они подбираются и какие показатели при этом учитываются?


    1. cccr85
      15.06.2015 22:36
      -1

      Я думаю здесь взялиdotaedge.com


    1. realimba Автор
      15.06.2015 23:45
      +1

      Приложение показывает наиболее удачных героев по мнению dotabuff. Там у каждого героя есть поле best versus и worst versus которые dotabuff вычисляет по своим алгоритмам на базе собранной статистики. Генератор крутых пиков планировался на потом.


      1. nikolayvaganov
        16.06.2015 10:32
        +2

        Не хочу уходить в терминологию и тонкости, которые могут быть не понятны людям, далеким от dota, но удачность контрпика на основе best/worst одиночных героев даст больше вреда чем пользы, потому как в данный конкретный момент основной профит все же идет от связок героев ( два и более ), когда, например, очень слабые сами по себе слабые саппорты дают много больше пользы в связке, чем более менее сильные в одиночку.


  1. lostmsu
    16.06.2015 05:46

    А почему не десктопное приложение? Можно было бы прямо поверх интерфейса Доты рисовать.


    1. Salabar
      16.06.2015 06:03
      +2

      И список героев можно было бы взять тупо из памяти.


    1. alexevil
      16.06.2015 13:45
      +1

      Может защита от «античит» системы? Все процессы в памяти анализируются в ммо играх для борьбы с ботами…


  1. nikolayvaganov
    16.06.2015 08:44
    +2

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

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

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

    2. Лайнинг

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

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

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

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

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

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

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