Нужны ли нам нейронные сети?

Или повесть о том, как я сделал распознавания изображений с помощью свёрточной нейронной сети без нейронной сети. Интересно? Тогда прошу под кат.

Предыстория

Одним летним вечером играя в Dota 2, я подумал, было бы не плохо распознавать персонажей в игре, и выдавать статистику по наиболее удачному выбору контрперсонажа. Первая мысль, нужно как-то тянуть данные из матча и тут же их обрабатывать. Но я эту затею отбросил, так как нет у меня опыта во взломе игр. Тогда я решил, что можно делать скрины во время игры, быстро их обрабатывать, и таким образом получать данные о выбранных персонажей.

Подготовка

И так приступим. Для начала сделаем скриншот экрана.
На вид изображения все похожи, может быть просто брать hash от изображения и искать его.


«О Гейб! Ну за, что такие муки мне.» Нет не получиться. Одному Гейбу известно почему изображения персонажей так кривляются (хотя нет не только ему, есть у меня предположение, что изображения на ходу resize(тся), причем размеры заданы дробным числом). Значит надо распознавать изображения другим способом. Сейчас в моде нейронные сети. Вот и попробуем их прикрутить. Будем использовать свёрточные нейронные сети. Так нам понадобятся:

1. Свёрточное ядро.
2. Признаки хаара.
3. Тестовый набор изображений. 1000 — другая на одного персонажа …
4. …

Погоди те ка что о о о о о!

Мне жизни не хватит что бы накопить такую базу. Я подумал надо как-то обойтись без огромной тренировочной выборки, при этом не в ущерб скорости распознавания. Есть исчерпывающая статья о СНС (Свёрточной нейронной сети) на википедии. Вкратце объяснить принцип работы СНС можно так. На вход подаётся матрица яркостей пикселей, в градациях серого. И умножается на свёрточное ядро, затем значения суммируются и нормализуются. Свёрточное ядро представляет из себя обычно -1 и 1, обозначающие черные и белые цвета соответственно, либо на оборот.

Есть популярные шаблоны ядер, к примеру признаки Хаара. Далее в статье мы будем использовать именно некоторые признаки Хаара. Затем значения свёрток проходят по входным связям нейрона, умножаются на веса связей, суммируются, и в конечном итоге полученное значение подается на функцию активации нейрона. Но это же чистой воды сравнение, или разница свёрток, вот ОНО. Нам необходимо просто взять разность исходной свертки со свертками персонажей, чем меньше разница, тем сильнее похожи изображения. Это простейшая архитектура. В ней нет скрытых слоев, так как нам нет нужды в абстрактных параметрах. Попробуем сделать все выше сказанное.

Пишем код

Исходное изображение персонажа будет размером 78x53 px. В градациях серого. То есть матрица размером 78x53 со значениями 0… 255. Ядро будем брать размером 10x10. Шаг ядра будет размером с ядро – 10. Как по x так и по y. (Нам много параметров не надо всё-таки изображения не сильно отличаются друг от друга). Итого 48 значений на одного персонажа. Теперь приступим к коду. Нам необходимо инициализировать ядро числами в соответствии с признаками Хаара. Возьмём следующие признаки. Создадим класс ConvolutionCore где будем инициализировать свёрточное ядро.

Класс ConvolutionCore

package com.kuldiegor.recognize;  /**  * Created by aeterneus on 17.03.2017.  */ public class ConvolutionCore {     public int unitMin; //количество -1     public int unitMax; //количество 1     public  int matrix[][];     public ConvolutionCore(int width,int height,int haar){         matrix = new int[height][width];         unitMax=0;         unitMin=0;         switch (haar){             case 0:{                 // -1 = черная часть                 //  1 = белая часть                 /*                     -1  -1  -1  1 1 1                     -1  -1  -1  1 1 1                     -1  -1  -1  1 1 1                 */                 for (int y=0;y<height;y++){                     for (int x=0;x<(width/2);x++){                         matrix[y][x]=-1;                         unitMin++;                     }                     for (int x=width/2;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 break;             }             case 1:{                 // -1 = черная часть                 //  1 = белая часть                 /*                     1  1  1  1  1  1                     1  1  1  1  1  1                     1  1  1  1  1  1                    -1 -1 -1 -1 -1 -1                    -1 -1 -1 -1 -1 -1                    -1 -1 -1 -1 -1 -1                 */                 for (int y=0;y<(height/2);y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 for (int y=(height/2);y<height;y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=-1;                         unitMin++;                     }                 }                 break;             }             case 2:{                 // -1 = черная часть                 //  1 = белая часть                 /*                     1 1 -1 -1 -1 1 1                     1 1 -1 -1 -1 1 1                     1 1 -1 -1 -1 1 1                 */                 for (int y=0;y<height;y++){                     for (int x=0;x<(width/3);x++){                         matrix[y][x]=1;                         unitMax++;                     }                     for (int x=(width/3);x<(width*2/3);x++){                         matrix[y][x]=-1;                         unitMin++;                     }                     for (int x=(width*2/3);x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 break;             }             case 3:{                 // -1 = черная часть                 //  1 = белая часть                 /*                     1  1  1  1                     1  1  1  1                     1  1  1  1                    -1 -1 -1 -1                    -1 -1 -1 -1                    -1 -1 -1 -1                     1  1  1  1                     1  1  1  1                     1  1  1  1                 */                 for (int y=0;y<(height/3);y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 for (int y=(height/3);y<(height*2/3);y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=-1;                         unitMin++;                     }                 }                 for (int y=(height*2/3);y<height;y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 break;             }             case 4:{                 // -1 = черная часть                 //  1 = белая часть                 /*                     1  1  1  1  1                     1  1  1  1  1                     1  1  1  1  1                     1 -1 -1 -1  1                     1 -1 -1 -1  1                     1 -1 -1 -1  1                     1  1  1  1  1                     1  1  1  1  1                     1  1  1  1  1                 */                 for (int y=0;y<(height/3);y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 for (int y=(height/3);y<(height*2/3);y++){                     for (int x=0;x<(width/3);x++){                         matrix[y][x]=1;                         unitMax++;                     }                     for (int x=(width/3);x<(width*2/3);x++){                         matrix[y][x]=-1;                         unitMin++;                     }                     for (int x=(width*2/3);x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 for (int y=(height*2/3);y<height;y++){                     for (int x=0;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 break;             }             case 5:{                 // -1 = черная часть                 //  1 = белая часть                 /*                     1  1  1 -1 -1 -1                     1  1  1 -1 -1 -1                    -1 -1 -1  1  1  1                    -1 -1 -1  1  1  1                 */                 for (int y=0;y<(height/2);y++){                     for (int x=0;x<(width/2);x++){                         matrix[y][x]=1;                         unitMax++;                     }                     for (int x=width/2;x<width;x++){                         matrix[y][x]=-1;                         unitMin++;                     }                 }                 for (int y=(height/2);y<height;y++){                     for (int x=0;x<(width/2);x++){                         matrix[y][x]=-1;                         unitMin++;                     }                     for (int x=width/2;x<width;x++){                         matrix[y][x]=1;                         unitMax++;                     }                 }                 break;             }         }     } } 

Я сделал динамическое наполнение, и инициализацию, вне зависимости от размера ядра. Теперь создадим класс Convolution, в нем мы будем делать свёртку

Класс Сonvolution

package com.kuldiegor.recognize;  import java.awt.image.BufferedImage; import java.util.ArrayList;  /**  * Created by aeterneus on 17.03.2017.  */ public class Convolution {     static ConvolutionCore convolutionCores[]; //Ядра свертки     static {         //Добавляем все признаки Хаара         convolutionCores = new ConvolutionCore[6];         for (int i=0;i<6;i++){             convolutionCores[i] = new ConvolutionCore(10,10,i);         }     }      private int matrixx[][]; //Матрица значений изображения 0 .. 255      public Convolution(BufferedImage image){         matrixx = getReadyMatrix(image);      }     private int[][] getReadyMatrix(BufferedImage bufferedImage){         //Получение матрицы значений из изображения         int width  = bufferedImage.getWidth();         int heigth = bufferedImage.getHeight();          int[] lineData = new int[width * heigth];         bufferedImage.getRaster().getPixels(0, 0, width, heigth, lineData);          int[][] res = new int[heigth][width];         int shift = 0;         for (int row = 0; row < heigth; ++row) {             System.arraycopy(lineData, shift, res[row], 0, width);             shift += width;         }          return res;     }     private double[] ColapseMatrix(int[][] matrix,ConvolutionCore convolutionCore){         //Произведение матрицы на ядро свёртки         int cmh=convolutionCore.matrix.length; //Высота ядра свёртки         int cmw=convolutionCore.matrix[0].length; //Ширина ядра свёртки         int mh=matrix.length; //Высота матрицы значений         int mw=matrix[0].length; //Ширина матрицы значений         int addWidth = cmw - (mw%cmw); //В случае если ядро ровно не ложится, то добавляем нули в матрицу         int addHeight = cmh - (mh%cmh);         int nmatrix[][]=new int[mh+addHeight][mw+addWidth];         for (int row = 0; row < mh; row++) {             System.arraycopy(matrix[row], 0, nmatrix[row], 0, mw);         }         int nw = nmatrix[0].length/cmw;         int nh = nmatrix.length/cmh;         double result[] = new double[nh*nw];         int dmin = -convolutionCore.unitMin*255; //Для нормализации значений         int dm = convolutionCore.unitMax*255-dmin;         int q=0;         for (int ny=0;ny<nh;ny++){             for (int nx=0;nx<nw;nx++){                 int sum=0;                 for (int y=0;y<cmh;y++){                     for (int x=0;x<cmw;x++){                         sum += nmatrix[ny*cmh+y][nx*cmw+x]*convolutionCore.matrix[y][x];                     }                 }                 result[q++]=((double)sum-dmin)/dm;             }         }         return result;     }     public ArrayList<double[]> getConvolutionMatrix(){         //Создаём массив сверток по всем признакам Хаара         ArrayList<double[]> result = new ArrayList<>();         for (int i=0;i<convolutionCores.length;i++){             result.add(ColapseMatrix(matrixx,convolutionCores[i]));         }         return result;     } } 

Поясню, в классе, в статическом блоке, мы подгружаем ядра свертки, так как они постоянны и не меняются, а свёрток мы будем делать очень много, инициализируем ядра один раз и больше не будем этим заниматься. В конструкторе по имеющемся изображению возьмём матрицу значений, это необходимо для ускорения алгоритма, что бы не брать каждый раз по 1 пикселю с изображения, создадим сразу матрицу градации серого. В методе ColapseMatrix на входе у нас матрица изображения и ядро свёртки. Сначала производится добавление нулей в конец матрицы в случае если ядро не совмещается с матрицей. Затем проходимся ядром по матрице и считаем свёртку. Сохраняем все в массив. Нам так же понадобиться хранить свёртки персонажей. Поэтому создадим класс hero и добавим следующие поля:

1. Массив свёрток;
2. Имя персонажа;

Класс Hero

package com.kuldiegor.recognize;  import java.util.ArrayList;  /**  * Created by aeterneus on 17.03.2017.  */ public class Hero {     public String name;     public ArrayList<double[]> convolutions;     public Hero(String Name){         name = Name;     } } 

Еще необходимо подгружать свёртки образцы, для сравнения персонажей, создадим класс DefaultHero.

Класс DefaultHero

package com.kuldiegor.recognize;  import javax.imageio.ImageIO; import java.awt.image.BufferedImage; import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator;  /**  * Created by aeterneus on 17.03.2017.  */ public class DefaultHero {     public ArrayList<Hero> heroes;     public String path;     public DefaultHero(String path,int tload){         heroes = new ArrayList<>();         this.path = path;         switch (tload){             case 0:{                 LoadFromFolder(path);                 break;             }             case 1:{                 LoadFromFile(path);             }         }      }     private void LoadFromFolder(String path){         //Загрузка из каталога изображений с последующем получением свёрток         File folder = new File(path);         File[] folderEntries = folder.listFiles();         for (File entry : folderEntries)         {             if (!entry.isDirectory())             {                 BufferedImage image = null;                 try {                     image = ImageIO.read(entry);                 } catch (IOException e) {                     e.printStackTrace();                 }                 Hero hero = new Hero(StringTool.parse(entry.getName(),"",".png"));                 hero.convolutions = new Convolution(image).getConvolutionMatrix();                 heroes.add(hero);               }         }      }     private void LoadFromFile(String name){         //Загрузка готовых свёрток из файла         try {             BufferedReader bufferedReader = new BufferedReader(new FileReader(name));             String str;             while ((str = bufferedReader.readLine())!= null){                 Hero hero =new Hero(StringTool.parse(str,"",":"));                 String s = StringTool.parse(str,":","");                 String mas[] = s.split(";");                 int n=mas.length/48;                 hero.convolutions = new ArrayList<>(n);                 for (int c=0;c<n;c++) {                     double dmas[] = new double[48];                     for (int i = 0; i < 48; i++) {                         dmas[i] = Double.parseDouble(mas[i+c*48]);                     }                     hero.convolutions.add(dmas);                 }                 heroes.add(hero);             }         } catch (IOException e){             e.printStackTrace();         }       }     public void SaveToFile(String name){         //Сохранение свёрток в файл         Collections.sort(heroes, Comparator.comparing(o -> o.name));         FileWriter fileWriter = null;         try {             fileWriter = new FileWriter(name);         } catch (IOException e){             e.printStackTrace();         }         for (int i=0;i<heroes.size();i++){             Hero hero = heroes.get(i);             StringBuilder stringBuilder = new StringBuilder();             stringBuilder.append(hero.name).append(":");             for (int i2=0;i2<hero.convolutions.size();i2++){                 double matrix[] = hero.convolutions.get(i2);                 for (int i3=0;i3<matrix.length;i3++){                     stringBuilder.append(matrix[i3]).append(";");                 }             }             try {                 fileWriter.write(stringBuilder.append(" ").toString());             } catch (IOException e){                 e.printStackTrace();             }          }         try {             fileWriter.close();         } catch (IOException e){             e.printStackTrace();         }     }     public String getSearhHeroName(Hero hero){         //Поиск и получение имени персонажа         for (int i=0;i<heroes.size();i++){             if (equalsHero(hero,heroes.get(i))){                 return heroes.get(i).name;             }         }         return "0";      }     public boolean equalsHero(Hero hero1,Hero hero2){         //Сравнение 2 персонажей         int min=0;         int max=0;         for (int i=0;i<hero1.convolutions.size();i++){             double average=0;             for (int i1=0;i1<hero1.convolutions.get(i).length;i1++){                 //Разность 2 сверток по модулю                 average += Math.abs(hero1.convolutions.get(i)[i1]-hero2.convolutions.get(i)[i1]);             }             average /=hero1.convolutions.get(0).length;             if (average<0.02){                 //Если среднее арифметическое меньше порога нахождение то добавляем бал к положительному результату                 min++;             } else {                 max++;             }          }          return (min>=max);     } } 

Тут всё очень просто, пробегаемся по всем свёрткам и сохраняем их в файл. Аналогично загрузка из файла. Загрузка из каталога отличается тем что мы считаем свёртки из изображений это нам будет необходимо, когда будем накапливать базу изображений персонажей.

Ну и само сравнение. Считаем среднюю арифметическую разность свёрток на 1 ядро, если меньше 0,02 тогда считаем, что изображения похожи, грубо говоря: «если изображения похожи на 98% то считаем их одинаковыми». Затем считаем, если хотя бы половина, или даже больше признаков, показала положительный результат то указываем, что персонажи равны.

Теперь сделаем скриншот экрана.

Код скриншота

try { //Делаем скриншот image = new Robot().createScreenCapture(new Rectangle(Toolkit.getDefaultToolkit().getScreenSize())); } catch (AWTException e) { e.printStackTrace(); }

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

Класс HRecognize

package com.kuldiegor.recognize;  import java.awt.image.BufferedImage; import java.util.ArrayList;  /**  * Created by aeterneus on 17.03.2017.  */ public class HRecognize {     private DefaultHero defaultHero;     public String heroes[]; //Список имён распознанных персонажей      public HRecognize(BufferedImage screen, DefaultHero defaultHero){         heroes = new String[10];         ArrayList<Hero> heroArrayList = new ArrayList<>();         this.defaultHero = defaultHero;         for (int i=0;i<5;i++){             //Создаем пустое изображение в режиме градаций серого             BufferedImage bufferedImage = new BufferedImage(78,53,BufferedImage.TYPE_BYTE_GRAY);             //Вырезаем изображения из скриншота             bufferedImage.getGraphics().drawImage(screen.getSubimage(43+i*96,6,78,53),0,0,null);             Hero hero = new Hero("");             //Получение свёрток             hero.convolutions = new Convolution(bufferedImage).getConvolutionMatrix();             heroArrayList.add(hero);         }         for (int i=0;i<5;i++) {             //Создаем пустое изображение в режиме градаций серого             BufferedImage bufferedImage = new BufferedImage(78, 53, BufferedImage.TYPE_BYTE_GRAY);             //Вырезаем изображения из скриншота             bufferedImage.getGraphics().drawImage(screen.getSubimage(777 + i * 96, 6, 78, 53), 0, 0, null);             Hero hero = new Hero("");             //Получение свёрток             hero.convolutions = new Convolution(bufferedImage).getConvolutionMatrix();             heroArrayList.add(hero);         }         for (int i=0;i<10;i++){             //Поиск персонажа и получении имени             heroes[i] = defaultHero.getSearhHeroName(heroArrayList.get(i));         }       } } 

Теперь необходимо накопить базу изображений. Я пробовал брать с дотабафф картинки, но были изображения, абсолютно отличавшиеся от dota(вских). Поэтому было принято решение, собирать их в полуавтоматическом режиме. Слегка переписав код для мастера свёртки, добавил кнопку «Сделать скриншот». Сравнения сверток происходит, каждый раз, с подгрузкой образцов из каталога, а если образцов не было, то сохранять их в каталог.

Мастер свёртки на github

Поехали! Запускаем доту в лобби и поочередно выбираем всех 113 персонажей.


Базу накопили. Теперь необходимо дать имя каждому персонажу.


И сохранить все свёртки в файл. Теперь можно пробовать тестировать приложение


Ошибок распознавания практических нет. Есть только одна, когда запускается игра и кругом чёрный фон приложение реагирует на это и выдает персонажа Shadow Fiend, а когда наступает выбор персонажа, ошибок не наблюдается. Осталось отправлять данные о распознанных персонажах по сети на Android приложение чтобы не сворачивать каждый раз игру.

Тут всё просто.

Код принятия широковещательного запроса

try {                     DatagramSocket socket = new DatagramSocket(6001);                     byte buffer[] = new byte[1024];                     DatagramPacket packet = new DatagramPacket(buffer, 1024);                     InetAddress localIP= InetAddress.getLocalHost();                     while (!Thread.currentThread().isInterrupted()) {                         //Ждем широковещательного пакета                         socket.receive(packet);                         String s=new String(packet.getData(),0,packet.getLength());                         if (StringTool.parse(s,"",":").equals("BroadCastFastDefinition")){                             String str = "OK:"+localIP.getHostAddress();                             byte buf[] = str.getBytes();                             DatagramPacket p = new DatagramPacket(buf,buf.length,packet.getAddress(),6001);                             //Отправляем ответ что мы сервер                             socket.send(p);                         }                      }                 }catch (Exception e) {                     e.printStackTrace();                 }

Код отправки данных

try {                             //Ждём клиента                             Socket client = socket.accept();                             final String ipclient = client.getInetAddress().getHostAddress();                             Platform.runLater(new Runnable() {                                 @Override                                 public void run() {                                     label1.setText("Подключен");                                     label1.setTextFill(Color.GREEN);                                     textfield2.setText(ipclient);                                 }                             });                             DataOutputStream streamWriter = new DataOutputStream(client.getOutputStream());                             BufferedImage image = null;                             while (client.isConnected()){                                 try {                                     //Делаем скриншот                                     image = new Robot().createScreenCapture(new Rectangle(Toolkit.getDefaultToolkit().getScreenSize()));                                 } catch (AWTException e) {                                     e.printStackTrace();                                 }                                 //Производим распознавание                                 HRecognize hRecognize = new HRecognize(image,defaultHero);                                 StringBuilder stringBuilder = new StringBuilder();                                 for (int i=0;i<5;i++){                                     stringBuilder.append(hRecognize.heroes[i]).append(";");                                 }                                 stringBuilder.append(":");                                 for (int i=5;i<10;i++){                                     stringBuilder.append(hRecognize.heroes[i]).append(";");                                 }                                 stringBuilder.append(" ");                                 String str = stringBuilder.toString();                                 //Отправляем то что распознали                                 streamWriter.writeUTF(str);                                 try {                                     Thread.sleep(300);                                  } catch (InterruptedException e){                                     threadSocket.interrupt();                                 }                              }                         }catch (IOException e){                          }

Принимаем широковещательный запрос. Отвечаем на него плюс дополнительно отправляем в запросе свой ip хотя это и не надо, но пусть будет. Затем с нами открывают tcp соединение, и мы начинаем отправлять данные каждые 300 миллисекунд. Как только соединение обрывается, перестаем распознавать персонажей. Я сделал это для снижения нагрузки на процессор. Когда игра уже началась я просто рву соединение на клиенте и процессор больше не грузится.

Android приложение. Код приводить здесь не буду так как это очень простое приложение расскажу вкратце как оно работает. И дам ссылку на GitHub.

Приложение отправляет широковещательный запрос по сети (можно ввести и конкретный ip адрес сервера) для определения серверной части приложения. Как только приходит ответ от одного из серверов подключаемся к нему и начинаем принимать от него данные. Для определения контрпика я выбрал сайт dotabuff.com. Прохожу по списку по каждому персонажу и выдёргиваю данные «Силён против» и «Слаб против» Строю связный список. Затем беру присланных персонажей и вывожу список всех персонажей кто слабее выбранной пятёрки. Попутно проверяя чтобы в списке не было персонажей, которые «контрят» одного из пятёрки, то есть в списке персонажи абсолютно слабы против пятёрки выбранных персонажей.

Нерешенные задачи

Работает только при разрешении 1280x1024, на других разрешениях не пробовал.

Заключение

Распознавание происходит очень быстро, процессор практически не напрягается на моем ноутбуке Lenovo B570e с процессором Intel Celeron 1.5 GHz. Нагрузка 6%, при такте распознавания 3 раза в секунду. Если тема будет интересна расскажу, как делал распознавания чисел на HealthBar(е), с какими трудностями я столкнулся, и как я их решал. Всем спасибо, кто дочитал до конца. .S. Все ссылки на гитхаб с мастером свёртки и самой программой распознавания и на архив изображений со сверткой:

? GitHub-ссылка на мастера свёртки
? GitHub-ссылка на само приложение
? GitHub-ссылка на Android приложение
? Ссылка на архив с изображениями
? Ссылка на файл-свёрток