Алгоритм для WRO: непрерывное считывание цветов кубиков +1


Здесь я бы хотел рассказать про интересный алгоритм, который я использовал в решении WRO Senior (старшая категория, которая), для непрерывного считывания цветов в сезоне 2019 года. Весь код будет написан на C++ в реализации (правильнее будет сказать, что почти в той реализации), которая сейчас лежит в основе EvCpp - если я допилю его, то должен получиться хороший аналог Basic.

Робот НЕ моей команды - https://instagram.fuln9-1.fna.fbcdn.net/v/t51.2885-15/e35/110169087_605944503630575_2158832733950492729_n.jpg?_nc_ht=instagram.fuln9-1.fna.fbcdn.net&_nc_cat=111&_nc_ohc=-CzNhhHw9HYAX-3wyje&edm=AP_V10EBAAAA&ccb=7-4&oh=f627c52a4cac1591dff57569b3a13ebd&oe=61056CC8&_nc_sid=4f375e
Робот НЕ моей команды - https://instagram.fuln9-1.fna.fbcdn.net/v/t51.2885-15/e35/110169087_605944503630575_2158832733950492729_n.jpg?_nc_ht=instagram.fuln9-1.fna.fbcdn.net&_nc_cat=111&_nc_ohc=-CzNhhHw9HYAX-3wyje&edm=AP_V10EBAAAA&ccb=7-4&oh=f627c52a4cac1591dff57569b3a13ebd&oe=61056CC8&_nc_sid=4f375e

Давайте приступим к алгоритму.

Постановка задачи

У вас имеется 4 кубика разных цветов, расположенных вдоль линии. Нужно определить их цвета - они влияют на расположение "ветрогенераций" в центральной части поля. Чтобы не добавлять лишних изображений и не подписывать их - обрезал макет поля так, чтоб на нем остались чисто линия для проезда и позиции кубиков (цветовых индикаторов).

Часть макета поля (снизу зона старта финиша), цветами отмечены кубики которые там как бы стоят
Часть макета поля (снизу зона старта финиша), цветами отмечены кубики которые там как бы стоят

Самый простой способ - это считывать цвета проезжая каждый раз по линии определенное количество градусов (в моторах встроен энкодер). Данное решение было отброшено, так как если бы появлялось бы дополнительное задание, которое меняло количество (а еще хуже расположение кубиков), то нужно было бы подбирать градусы заново.

Тут и был придуман (кажется нашим с сокомандником тренером) алгоритм - мы просто едем по линии и постоянно считываем значения датчика цвета. Затем уже, когда данный отрезок линии был пройден роботом - обрабатываем "накопившиеся" значения и получаем ответ - количество и порядок цветов.

Изначально алгоритм был написан на графическом языке от авторов набора, и график здесь приведен именно с этого времени (поздних или не сохранилось, или их и не было) - это можно определить по количеству считываний. После уже использовался С++ - это дало сильный прирост количества считаных (RGB) значений.

А как же обрабатывать-то этот массив?

Тут все просто - берете и обрабатываете. Нужно просто обратиться к другому способу кодирования цветов - HSV. Не думаю, что объяснение того, как он работает (и что значит каждая буква) это тема этой статьи, но если вам интересно - вот ссылка.

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

Я покажу вам один график, на котором есть информация про HSV сведенная в одно место (подписи к линиям значения не имеют, так что вырежу их для простоты). Посмотрите на график и алгоритм в целом придет к вам сам.

(к сожалению сырых данных к графикам нет - только скрины тех лет, так что качество может чутка страдать)
(к сожалению сырых данных к графикам нет - только скрины тех лет, так что качество может чутка страдать)

Как вы можете заметить - синяя линия (это V) уходит "вниз" на каждом из четырех кубиков - общий шум (в нашем случае стенка за кубиками плюс освещение и прочее) образуют примерно прямую линию. Таким образом нам нужно просто отделить области в которых график растет сильно вверх, и определить их цвет (делалось это по H - серая линия). Давайте приступим к коду, ведь мы здесь для этого и собрались!

Накопление всех данных

Изначально накапливались данные вот в такой структуре:

struct rgbhsv {
  Ev3LightSensor::RGB rgb;
  HSV hsv;
};

Собственно мы накопили обычный вектор таких структур - по факту у нас есть только rgb, а в hsv лежит мусор. Теперь нужно перейти в более комфортный для нас способ представления цветов. Это сделать достаточно просто - обычный for по всем элементам вектора.

vector < vector < rgbhsv >> calcData;
bool flag = false;
vector < rgbhsv > buff;
for (unsigned int i = 0; i < data.size(); i++) {
  if (data[i].hsv.v * 100 > 4) {
    flag = true;
    buff.push_back(data[i]);
  } else {
    if (flag) {
      flag = false;
      calcData.push_back(buff);
      buff.clear();
    }
  }
}

Тут мы простой системой одного флага (Вектор data заполен сырыми значениями с датчика), разделяем одну последовательность с N кубиками, на N подпоследовательностей с одним кубиком в каждой. Таким образом нам остается просто определить цвет характерный каждой из последовательностей и вот он ответ.

ЧТО? Предпоследнее предложение другими словами.

У нас имеется массив (на самом деле вектор, но я буду использовать термин массив) в котором имеются какие-то значения - там лежат N считанных кубиков (каждый кубиков по несколько считываний). Наша задача разобрать этот массив на подмассивы, в каждом из подмассивов будут только считывания одного кубика.

Немного про несовпадение теории и практики

Но тут в дело вступает физика - как вы помните из графика сверху - синяя и серые линии не ровные - кубик для датчика это не одна тройка rbg, а некоторое их количество - в частности, такое случается на границах кубика. Так же есть проблема с определением черного (нет в основном задании, но может быть в дополнительном) и синего кубиков - если не исхитриться и просто посчитать (например) среднее от всех h, то вы будете часто их путать. Тут на помощь пришла идея медианной сортировки, но так как никому не хотел особо заморачиваться с сортировками и перемешиванием, было решено просто сделать подсчет.

Для каждого "сырого" значения множества кубика (одно из тех, что получились из алгоритма выше), сопоставлялось какое-то значение в кодировке цветов. Элементу массива с таким индексом делался инкремент. Затем, обработав всю последовательность выбирался тот элемент, который чаще других был определен алгоритмом. Так же отбрасывались начало и конец считывания кубиков (так как в целом при нескольких тысячах считанных значений, мы можем отбросить те, которые нам не нравятся), и все последовательности длина которых была меньше доверительного порога - мало-ли вспышка прилетела в инфракрасном спектре и получился кратковременный скачек, который в ином случае будет определен как какой-то из цветов и все испортит.

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

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

Немного мимо темы

Тут ниже приведен один и тот же алгоритм, реализованный на графическом языке и на C++. Можете заметить разницу. (Данные видео были приготовлены мною для выступления на МНСК - научная конференция НГУ, но, из-за моей невнимательности, их так никто и не увидел).

Заранее прошу прощение за монтаж - я не умею монтировать.

Встроенный графический язык (таймер тут это время обработки выборки сырых значений, длиной примерно в 160-180 элементов):

C++ (тут таймер я не вставлял - тот факт, что робот развернулся означает, что алгоритм отработал - размер первоначальной выборки 16к элементов):

Завершение

Спасибо, что дочитали эту статью. Тот факт, что я реализовал и (в какой-то мере осмыслил и доделал этот алгоритм в 10 классе) - является предметом моей гордости, конечно это не код на ассемблере, который приземляет ракету на луну, но...




К сожалению, не доступен сервер mySQL