" Вдохновение, которое искал все утро,
настигло в самый неудачный момент.
И как объяснить что я ухожу на SCRUM?
— Пойдем со мной ?! "

Коммуникация в команде— суровая необходимость больших проектов. Это не должно выглядеть как эшафот или принудительное собрание анонимных алкоголиков. От команды нужно участие, нужен блеск в глазах, каждого должно рвать от желания высказаться, как от пафосности этого предложения. Постепенно наша команда эволюционировала до SCRUM-модели, во многом благодаря простым и наглядным наклейкам. Какой же SCRUM без наклеек? Почти у каждого в детстве были наклейки и, где-то глубоко в подсознании засели воспоминания, когда нас, еще будучи ребенком, учила клеить воспитательница и, если наклейка была приклеена ровно, в качестве поощрения, она не била по рукам. Но даже в нашем беззаботном детстве приходилось делать вещи, которые казались нам скучны и непонятны — убирать игрушки, оттирать стену от ручки или писать под диктовку. Повзрослев, у нас появляется выбор — мы можем переложить работу на других. А кто захочет за всех писать backlog (отчет) и потом переносить данные в Jira? Использование Jira непосредственно в процессе митинга выводит участника из обсуждения, поэтому, после принятие конвенции ООН об упразднении рабства, остается переложить эту задачу на роботов.

В результате родилась идея написать программу распознавания и отслеживания карточек задач на SCRUM-доске.

Постановка минимальной задачи видится так:

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

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

С оцифровкой изображения доски правило простое — последний вставший со стула фотографирует доску. В будущем его должен заменить робот.

Ниже фотография того, как может выглядеть упрощенная SCRUM-доска. Очень упрощенная.


Рис.1. Пример SCRUM-доски.

Сверху стикеры для невыбранных задач, ниже области задач разработчиков (синего, зеленого и красного). Область каждого разработчика разбита на две части — слева находятся задачи, которые выполняются, справа — выполненные.

Сегментация

Начнем с банальностей — загрузка исходного изображения с фотографией доски делается средствами OpenCV очень просто:

int main(int argc, char** argv)  { 
    vector<cv::Mat> stickers;
    cv::CommandLineParser parser( argc, argv, keys );
    String image_path = parser.get<String>( 0 );
 
    if( image_path.empty() ) {
       help();
       return -1;
    }

     cv::Mat image = cv::imread(image_path);

Для представления изображений в OpenCV используется класс cv::Mat. Это интересная структура данных и подробную информацию про этот класс можно найти туточки.

Далее необходима основная функция для выделения изображений стикеров:

   recognizeStickers(stickers);

В первой версии мы просто сохраним найденные стикеры в файлы с именами sticker1.jpg … stickerN.jpg:

   saveStickers(stickers);
}

Рассмотрим более подробно функцию выделения изображений стикеров. Прототип функции может быть таким:

void recognizeStickers(vector<cv::Mat> &stickers);

Алгоритм решения задачи выделения контрастных объектов на однородном фоне может быть реализован различными способами:

• Алгоритм 1. Выделение объектов (стикеров), имеющих заданный цвет при помощи функции inRange;
• Алгоритм 2. Выделение ярких объектов (стикеров) из S-канала HSV-изображения при помощи функции threshold;

Алгоритм 1

Выделение стикеров при помощи inRange может быть следующим:

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

Ниже грубый набросок, иллюстрирующий идею алгоритма:

void recognizeStickersByRange(cv::Mat image,std::vector<cv::Mat> &stickers) 
{ 
    cv::Mat imageHsv; 
    std::vector< std::vector<cv::Point> > contours; 

    // Преобразуем в hsv, чтобы точнее вылавливать цвет стикера 
    cv::cvtColor(image, imageHsv, cv::COLOR_BGR2HSV); 

    cv::Mat tmp_img(image.size(),CV_8U); 

    // Выделение подходящих по цвету областей 
    cv::inRange(imageHsv, 
                cv::Scalar(key_light-delta_light,key_sat-delta_sat,key_hue-delta_hue), 
                cv::Scalar(key_light+delta_light,key_sat+delta_sat,key_hue+delta_hue), 
                tmp_img); 

    // "Замазать" огрехи при выделении по цвету 
    cv::dilate(tmp_img,tmp_img,cv::Mat(),cv::Point(-1,-1),3); 
    cv::erode(tmp_img,tmp_img,cv::Mat(),cv::Point(-1,-1),1); 

    //  Выделение непрерывных областей 
    cv::findContours(tmp_img,contours,
           CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE); 

    for (uint i = 0; i<contours.size(); i++) 
    { 
        cv::Mat sticker; 
        //Для каждой области определяем ограничивающий прямоугольник 
        cv::Rect rect=cv::boundingRect(contours[i]); 

        image(rect).copyTo(sticker); 

        //Добавить к массиву распознанных стикеров 
        stickers.push_back(sticker); 
    } 
} 

После ступенчатого преобразования и растягивания области с использованием фильтра для объединения областей, разделенных шумом (метод cv::dilate), получим:


Рис.2. Изображение после бинаризации.

Отправим бинаризованное изображение на вход алгоритма выделения контуров сv::findConturs и для каждого контура найдем ограничивающий прямоугольник при помощи cv::boundingRect. Для наглядности нарисуем ограничивающие прямоугольники зеленым цветом на исходном изображении.

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


Рис.3. Стикеры выделены.

Зная параметры ограничивающих прямоугольников, легко вырезать и сохранить изображения стикеров на диск в виде отдельных файлов:

for (uint i = 0;i < stickers.size();i++) {
        cv::imwrite("sticker"+toString(i+1)+".jpg",stickers[i]);
    }

В результате, на диске будет сформированы файлы sticker1.jpg … stickerN.jpg. Пример содержимого файла-стикера приведен ниже:


Рис.4. Изображение выделенного стикера.

Необходимо отметить, что в вышеприведенном примере мы не реализовали алгоритма определения цвета стикера, а задали его константами key_light, key_sat, key_hue в HSV-пространстве, что в нормальных условиях нехорошо. И если вдруг стикеры будут другого цвета, алгоритм надо будет перенастраивать. Граничные прямоугольники для областей разработчиков (синий, зеленый, красный) не выделены. Принципиально возможно задать константами цвета, а для них уже выделить аналогичным алгоритмом, что позволит автоматически определять границы областей и определять статус задач.

Алгоритм 2.

Воспользуемся функцией cv::threshold, как показано в примерах /1/ и /3/. Для начала мы перевели входной кадр в HSV-формат с помощью функции cv::cvtColor, а результат разбили с помощью cv::split. Результат ниже:


Рис.5. H-канал изображения.

Рис.6. S-канал изображения.

Рис.7. V-канал изображения.

Как видно из рис.5 — рис.7, наибольший интерес для обработки стикеров на белом фоне представляет S-канал изображения, где значение насыщенных цветом стикеров будет максимальным, а белого фона — минимальным. Наиболее наглядно это показано здесь. Можно предположить, что используя функцию cv::threshold с правильным значением границы, мы получим желаемое бинарное изображение с выделенными стикерами, из которого стикеры могут быть выделены при помощи функции cv::findContours, аналогично алгоритму 1.

   std::vector<cv::Mat> hsvPlanes;
   cv::split(inputHsvImage, hsvPlanes);
   cv::Mat image = hsvPlanes[1];
   double thresh = 110;
   double maxValue = 255; 
   threshold(image,image, thresh, maxValue, cv::THRESH_BINARY);

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


Рис.8. Гистограмма для S канала изображения.

Так как стикеры светлые, то цветам стикера соответствует самый правый пик на гистограмме S-канала. Определив его границы при помощи алгоритма /4/, мы получим искомое значение границы для ступенчатого преобразования.

int findMostRightExtremum(cv::Mat histNorm)
{
    vector< float > data;
    for (int i=0; i<histNorm.rows; i++)
          data.push_back(histNorm.at<float>(i));

    // Поиск экстремумов функции.
    Persistence1D p;
    p.RunPersistence(data);

    // Получить все экстремумы больше 0,002.
    vector< TPairedExtrema > Extrema;
    p.GetPairedExtrema(Extrema, 0,002);

   sort(Extrema.begin(),Extrema.end(),
          [](const TPairedExtrema &a,  const TPairedExtrema &b) -> bool
          {
                  return (a.MaxIndex) > (b.MaxIndex);
          }
    );
    // Используем левую границу самого правого экстремума на графике
    return (Extrema[0].MinIndex)*(255/histNorm.rows);
}

В результате бинаризации при помощи функции cv::threshold получим:


Рис.9. Бинаризация при помощи cv::threshold для рассчитанной границы.

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

Это первая статья из цикла статей о внедрении технологии компьютерного зрения в SCRUM-процесс. Остались вне рассмотрения следующие задачи:

• выделение зон доски («зона невыбранных задач», области «в процессе » и «выполнено» для разработчиков");
• определения зоны доски, в которой находится стикер;
• сопоставление стикеров после перемещения на доске;
• распознавание текста задачи;
• взаимодействие с jira.

Кстати, скоро у нас намечается серия бесплатных вебинаров, посвященных программированию на C++11/14, с примерами из области обработки изображений и дополненной реальности.

Источники

1. Basic Thresholding Operations
2. Thresholding Operations using inRange
3. akaifi.github.io/MultiObjectTrackingBasedhOnColor
4. Алгоритм поиска локальных экстремумов