Нескучный SCRUM и сегментация изображения для выделения Post-it наклеек26.01.2017 11:33

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

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

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

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

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

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

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

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

Сегментация


Начнем с банальностей — загрузка исходного изображения с фотографией доски делается средствами OpenCV очень просто: 
int main(int argc, char** argv)  { 
    vector stickers;
    cv::CommandLineParser parser( argc, argv, keys );
    String image_path = parser.get( 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 &stickers);

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

Алгоритм 1

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

Ниже грубый набросок, иллюстрирующий идею алгоритма: 
void recognizeStickersByRange(cv::Mat image,std::vector &stickers) 
{ 
    cv::Mat imageHsv; 
    std::vector< std::vector > 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

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

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

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

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

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

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

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

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

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

Алгоритм 2.

Воспользуемся функцией cv: threshold, как показано в примерах /1/ и /3/. Для начала мы перевели входной кадр в HSV-формат с помощью функции cv: cvtColor, а результат разбили с помощью cv: split. Результат ниже:
9fa7dd9242934b4c80ee42fe03776f48.jpg
Рис. 5. H-канал изображения.
212f508bce8a441a9db36796f0d2da24.jpg
Рис. 6. S-канал изображения.
70c8a4dffcde420da523d1bf27328ebc.jpg
Рис. 7. V-канал изображения.
Как видно из рис. 5 — рис. 7, наибольший интерес для обработки стикеров на белом фоне представляет S-канал изображения, где значение насыщенных цветом стикеров будет максимальным, а белого фона — минимальным. Наиболее наглядно это показано здесь. Можно предположить, что используя функцию cv: threshold с правильным значением границы, мы получим желаемое бинарное изображение с выделенными стикерами, из которого стикеры могут быть выделены при помощи функции cv: findContours, аналогично алгоритму 1.
   std::vector 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, мы опять сталкиваемся с необходимостью подбирать значение границы, которое можно вычислить путем анализа гистограммы изображения.
a2d180027c22424297c5679a356a7584.png
Рис. 8. Гистограмма для S канала изображения.
Так как стикеры светлые, то цветам стикера соответствует самый правый пик на гистограмме S-канала. Определив его границы при помощи алгоритма /4/, мы получим искомое значение границы для ступенчатого преобразования. 
int findMostRightExtremum(cv::Mat histNorm)
{
    vector< float > data;
    for (int i=0; i(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 получим:

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

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

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

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

Источники


  1. Basic Thresholding Operations. docs.opencv.org/master/db/d8e/tutorial_threshold.html
  2. Thresholding Operations using inRange docs.opencv.org/master/da/d97/tutorial_threshold_inRange.html
  3. akaifi.github.io/MultiObjectTrackingBasedhOnColor
  4. Алгоритм поиска локальных экстремумов. people.mpi-inf.mpg.de/~weinkauf/notes/persistence1d.html

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

© Habrahabr.ru