Пример сегментации изображений средствами PHP

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

Итак, рассмотрим исходные данные

Прямоугольные картинки разного размера и пропорций, с белым фоном, на которых изображены фигурки киндер сюрприза и water mark, который иногда касается фигурок. Задача — получить картинки фигурок без water mark'a

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

Интерация 1. Выбор не белых областей

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

PHP код

$path = '../images/series/9/1.jpg';
$size = getimagesize($path);
$img = imagecreatefromjpeg($path);

$x = 1;
$y = 1;
$color = array();
for ($i = 1; $i < $size[0] * $size[1]; $i++) {

    $color_index = imagecolorat($img, $x, $y); //16777215
// делаем его удобочитаемым
    $color_tran = imagecolorsforindex($img, $color_index);

    if (($color_tran['red'] == 0 && $color_tran['green'] == 0 && $color_tran['blue'] == 0)
            or
            ($color_tran['red'] <= 255 && $color_tran['red'] >= 235 &&
            $color_tran['green'] <= 255 && $color_tran['green'] >= 235 &&
            $color_tran['blue'] <= 255 && $color_tran['blue'] >= 235)
            or
            ($color_tran['red'] >= 190 && $color_tran['red'] <= 230 &&
            $color_tran['green'] >= 225 && $color_tran['green'] <= 245 &&
            $color_tran['blue'] >= 245 && $color_tran['blue'] <= 255)
    ) {
          $color[$x][$y] = 0;
    } else {
        $color[$x][$y] = 1;
    }

    $x++;
    if ($x > $size[0]) {
        $x = 1;
        $y++;
    }
}

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

Закрасим теперь полученные области на исходном изображении.



Как видно сейчас наш алгоритм цепляет кусочки мусора (поэтому в вышеприведенном коде и есть фильтрация по цвету)

Ошибочный подход, попытка выделения граничных областей сегментов

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



Шлифуем



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



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



Со стороны человеческого взгляда эти сегменты уже можно однозначно разделить, но со стороны нашего алгоритма это все еще массив единичек и ноликов, а так же массив ноликов и единиц – только границ сегментов (но сейчас это все еще 1 массив и основной вопрос в том, как разделить его в соответствии с сегментами).
На исходном изображении можно видеть явные белые пробелы между сегментами, попробуем разделить сегменты по принципу: «Если у нас есть большие разрывы (больше чем N) между закрашенными сегментами, то делим пиксели в основном массиве по левую и правую сторону от разрыва».





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

Метод разрастания областей

Краткое описание дано выше (в начале статьи), поэтому приступим сразу к делу.



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

PHP код

function nburn($ret, $color, $img, $col = false) {
    $ret_arr = array();
    foreach ($ret as $k => $v) {
        foreach ($v as $k2 => $v2) {
            $ret_arr['numb'] = get_nearleast($color, $k, $k2);
            $stop = false;
            if (count($ret_arr['numb']) > 0) {

                if (count($ret_arr['numb']) == 1) // 1- потому что только точка сама возвращается
                    $stop = true;
                else
                    $toys[] = array();
            }
            if (!$stop) {
                while (count($ret_arr['numb']) > 0) {
                    $x = key($ret_arr['numb']);
                    $y = key($ret_arr['numb'][$x]);
                    $toys[key($toys)][$x][$y] = 1;

                    unset($ret_arr['numb'][$x][$y]);
                    if (count($ret_arr['numb'][$x]) == 0)
                        unset($ret_arr['numb'][$x]);
                    unset($color[$x][$y]);


                    // Берем следующий элемент
                    $x = key($ret_arr['numb']);
                    if ($x == "")
                        break;
                    $y = key($ret_arr['numb'][$x]);
                    $near = get_nearleast($color, $x, $y);
                    foreach ($near as $f => $g) {
                        foreach ($g as $f2 => $g2) {

                            $ret_arr['numb'][$f][$f2] = 1;
                        }
                    }
                }
                next($toys);
            }
        }
    }

    return $toys;
}

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



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



Размещенный код писался для себя, поэтому, скорее всего, есть более элегантные решения.
Ссылки по теме:

• Википедия
• habrahabr.ru/post/81279 Сегментация изображений на графах
• habrahabr.ru/post/128768 Мат. модели сегментации изображений

UPD
Спасибо всем, кто плюсует.