Сортировка контуров по приоритету в Python, OpenCV

Это мой взгляд на проблему. Я дам вам общую суть, а затем мою реализацию в C++. Основная идея заключается в том, что я хочу обрабатывать изображение слева направо, сверху вниз. Я буду обрабатывать каждую каплю (или контур), как только найду ее, однако мне потребуется несколько промежуточных шагов для достижения успешной (упорядоченной) сегментации.

Вертикальная сортировка по строкам

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

После того как капли (вертикально) отсортированы по строкам, я могу проверить их центроиды (или центр масс) и отсортировать их по горизонтали. Идея состоит в том, что я буду обрабатывать строку за строкой и for в каждой строке сортировать BLOB-объекты по центроидам. Давайте посмотрим на пример того, чего я пытаюсь достичь здесь.

Это ваше входное изображение:

Это то, что я называю маской строки:

Это последнее изображение содержит белые области, каждая из которых представляет строку. Каждая строка имеет номер (например, Row1 , Row2 и т. д.), а каждая row содержит набор больших двоичных объектов (или символов, в данном случае). Обрабатывая каждый row, сверху вниз, вы уже сортируете капли по вертикальной оси.

Если я пронумерую каждую строку сверху вниз, я получу это изображение:

Маска строк — это способ создания строк больших двоичных объектов, и эта маска может быть вычислена морфологически. Посмотрите на 2 изображения, наложенные друг на друга, чтобы лучше понять порядок обработки:

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

Горизонтальная сортировка с использованием центроидов

Давайте теперь посмотрим, как мы можем отсортировать капли horizontally. Если мы создадим более простое изображение с width, равным входному изображению, и height, равным числам rows в нашей маске строки, мы можем просто наложить каждую горизонтальную координату (координату x) каждого блоба. центроид. Посмотрите этот пример:

Это таблица строк. Каждая строка представляет собой количество строк, найденных в маске строк, и также читается сверху вниз. width таблицы совпадает с width входного изображения и пространственно соответствует горизонтальной оси. Каждый квадрат — это пиксель входного изображения, сопоставленный с таблицей строк с использованием только горизонтальной координаты (поскольку наше упрощение строк довольно простое). Фактическое значение каждого пикселя в таблице строк — это label, помечающее каждую каплю на входном изображении. Обратите внимание, что этикетки не упорядочены!

Так, например, в этой таблице показано, что в строке 1 (вы уже знаете, что такое строка 1 — это первая белая область на маске строки) в позиции (1,4) есть номер блоба 3. В позиции (1,6) находится большой двоичный объект с номером 2 и так далее. Что хорошего (я думаю) в этой таблице, так это то, что вы можете просмотреть ее, и for каждое значение, отличное от 0, горизонтальное упорядочение становится очень тривиальным. Это таблица строк, упорядоченная слева направо:

Сопоставление информации о больших двоичных объектах с центроидами

Мы собираемся использовать BLOB-объекты центроиды для map информации между двумя нашими представлениями (маска строки/таблица строки). Предположим, у вас уже есть оба вспомогательных изображения, и вы одновременно обрабатываете каждую каплю (или контур) на входном изображении. Например, у вас есть это в качестве начала:

Хорошо, здесь есть капля. Как мы можем сопоставить его с маской строки и таблицей строк? Используя его центроиды. Если мы вычислим центроид (показанный на рисунке зеленой точкой), мы сможем построить dictionary из центроидов и меток. Например, для этого BLOB-объекта centroid находится по адресу (271,193). Хорошо, давайте назначим label = 1. Итак, теперь у нас есть этот словарь:

Теперь мы находим row, в котором находится этот блоб, используя тот же centroid в маске строки. Что-то вроде этого:

rowNumber = rowMask.at( 271,193 )

Эта операция должна вернуть rownNumber = 3. Ницца! Мы знаем, в какой строке находится наш большой двоичный объект, поэтому теперь он упорядочен вертикально. Теперь давайте сохраним его горизонтальную координату в таблице строк:

rowTable.at( 271, 193 ) = 1

Теперь rowTable содержит (в своей строке и столбце) метку обработанного большого двоичного объекта. Таблица строк должна выглядеть примерно так:

Таблица намного шире, потому что ее размер по горизонтали должен совпадать с исходным изображением. На этом изображении label 1 помещено в Column 271, Row 3. Если бы это было единственное пятно на вашем изображении, пятна были бы уже отсортированы. Но что произойдет, если вы добавите еще один блоб, скажем, Column 2, Row 1? Вот почему вам нужно снова пройтись по этой таблице после того, как вы обработали все блобы, чтобы правильно исправить их метку.

Реализация на C++

Хорошо, надеюсь, алгоритм должен быть немного ясен (если нет, просто спросите, мой друг). Попробую реализовать эти идеи в OpenCV с помощью C++. Во-первых, мне нужно binary image вашего вклада. Вычисление тривиально с использованием метода Otsu’s thresholding:

//Read the input image:
std::string imageName = "C://opencvImages//yFX3M.png";
cv::Mat testImage = cv::imread( imageName );

//Compute grayscale image
cv::Mat grayImage;
cv::cvtColor( testImage, grayImage, cv::COLOR_RGB2GRAY );

//Get binary image via Otsu:
cv::Mat binImage;
cv::threshold( grayImage, binImage, 0, 255, cv::THRESH_OTSU );

//Invert image:
binImage = 255 - binImage;

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

Первый шаг — получить Row Mask. Этого можно добиться с помощью морфологии. Просто примените dilation + erosion с ОЧЕНЬ большим горизонтальным structuring element. Идея в том, что вы хотите превратить эти капли в прямоугольники, соединив их вместе по горизонтали:

//Create a hard copy of the binary mask:
cv::Mat rowMask = binImage.clone();

//horizontal dilation + erosion:
int horizontalSize = 100; // a very big horizontal structuring element
cv::Mat SE = cv::getStructuringElement( cv::MORPH_RECT, cv::Size(horizontalSize,1) );
cv::morphologyEx( rowMask, rowMask, cv::MORPH_DILATE, SE, cv::Point(-1,-1), 2 );
cv::morphologyEx( rowMask, rowMask, cv::MORPH_ERODE, SE, cv::Point(-1,-1), 1 );

Это приводит к следующему Row Mask:

Это очень здорово, теперь, когда у нас есть Row Mask, мы должны пронумеровать их ряды, хорошо? Есть много способов сделать это, но сейчас меня интересует более простой: пройтись по этому изображению и получить каждый пиксель. If пиксель белый, используйте операцию Flood Fill, чтобы пометить эту часть изображения как уникальный блоб (или строку, в данном случае). Это можно сделать следующим образом:

//Label the row mask:
int rowCount = 0; //This will count our rows

//Loop thru the mask:
for( int y = 0; y < rowMask.rows; y++ ){
    for( int x = 0; x < rowMask.cols; x++ ){
        //Get the current pixel:
        uchar currentPixel = rowMask.at<uchar>( y, x );
        //If the pixel is white, this is an unlabeled blob:
        if ( currentPixel == 255 ) {
            //Create new label (different from zero):
            rowCount++;
            //Flood fill on this point:
            cv::floodFill( rowMask, cv::Point( x, y ), rowCount, (cv::Rect*)0, cv::Scalar(), 0 );
        }
    }
}

Этот процесс пометит все строки от 1 до r. Это то, что мы хотели. Если вы посмотрите на изображение, вы увидите слабые строки, потому что наши метки соответствуют очень низким значениям интенсивности пикселей в градациях серого.

Хорошо, теперь давайте подготовим таблицу строк. Эта таблица на самом деле просто еще одно изображение, помните: та же ширина, что и у ввода, и высота, равная количеству строк, которые вы подсчитали в Row Mask:

//create rows image:
cv::Mat rowTable = cv::Mat::zeros( cv::Size(binImage.cols, rowCount), CV_8UC1 );
//Just for convenience:
rowTable = 255 - rowTable;

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

Теперь самое интересное. У нас есть оба изображения (или контейнеры данных). Нам нужно обрабатывать каждый блоб независимо. Идея состоит в том, что вы должны извлечь каждый блоб/контур/символ из бинарного изображения и вычислить его centroid и присвоить новый label. Опять же, есть много способов сделать это. Здесь я использую следующий подход:

Я пройдусь по binary mask. Я получу current biggest blob из этого бинарного ввода. Я вычислю его centroid и сохраню его данные во всех необходимых контейнерах, а затем delete извлеку этот блоб из маски. Я буду повторять процесс, пока не останется больше капель. Это мой способ сделать это, особенно потому, что у меня есть функции, которые я уже написал для этого. Это подход:

//Prepare a couple of dictionaries for data storing:
std::map< int, cv::Point > blobMap; //holds label, gives centroid
std::map< int, cv::Rect > boundingBoxMap; //holds label, gives bounding box

Сначала два dictionaries. Один получает метку большого двоичного объекта и возвращает центроид. Другой получает ту же метку и возвращает ограничивающую рамку.

//Extract each individual blob:
cv::Mat bobFilterInput = binImage.clone();

//The new blob label:
int blobLabel = 0;

//Some control variables:
bool extractBlobs = true; //Controls loop
int currentBlob = 0; //Counter of blobs

while ( extractBlobs ){

    //Get the biggest blob:
    cv::Mat biggestBlob = findBiggestBlob( bobFilterInput );

    //Compute the centroid/center of mass:
    cv::Moments momentStructure = cv::moments( biggestBlob, true );
    float cx = momentStructure.m10 / momentStructure.m00;
    float cy = momentStructure.m01 / momentStructure.m00;

    //Centroid point:
    cv::Point blobCentroid;
    blobCentroid.x = cx;
    blobCentroid.y = cy;

    //Compute bounding box:
    boundingBox boxData;
    computeBoundingBox( biggestBlob, boxData );

    //Convert boundingBox data into opencv rect data:
    cv::Rect cropBox = boundingBox2Rect( boxData );


    //Label blob:
    blobLabel++;
    blobMap.emplace( blobLabel, blobCentroid );
    boundingBoxMap.emplace( blobLabel, cropBox );

    //Get the row for this centroid
    int blobRow = rowMask.at<uchar>( cy, cx );
    blobRow--;

    //Place centroid on rowed image:
    rowTable.at<uchar>( blobRow, cx ) = blobLabel;

    //Resume blob flow control:
    cv::Mat blobDifference = bobFilterInput - biggestBlob;
    //How many pixels are left on the new mask?
    int pixelsLeft = cv::countNonZero( blobDifference );
    bobFilterInput = blobDifference;

    //Done extracting blobs?
    if ( pixelsLeft <= 0 ){
        extractBlobs = false;
    }

    //Increment blob counter:
    currentBlob++;

}

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

Теперь несколько заметок к приведенному выше фрагменту. У меня есть несколько вспомогательных функций: biggestBlob и computeBoundingBox. Эти функции вычисляют самый большой двоичный объект в двоичном изображении и преобразуют пользовательскую структуру ограничительной рамки в структуру OpenCV Rect соответственно. Это операции, которые выполняют эти функции.

Суть фрагмента заключается в следующем: если у вас есть изолированный большой двоичный объект, вычислите его centroid (на самом деле я вычисляю center of mass через central moments). Создайте новый файл label. Сохраните эти label и centroid в словаре dictionary, в моем случае blobMap. Дополнительно вычислите bounding box и сохраните его в другом dictionary, boundingBoxMap:

//Label blob:
blobLabel++;
blobMap.emplace( blobLabel, blobCentroid );
boundingBoxMap.emplace( blobLabel, cropBox );

Теперь, используя данные centroid, fetch соответствующие row этого блоба. Как только вы получите строку, сохраните это число в своей таблице строк:

//Get the row for this centroid
int blobRow = rowMask.at<uchar>( cy, cx );
blobRow--;

//Place centroid on rowed image:
rowTable.at<uchar>( blobRow, cx ) = blobLabel;

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

int blobCounter = 1; //The ORDERED label, starting at 1
for( int y = 0; y < rowTable.rows; y++ ){
    for( int x = 0; x < rowTable.cols; x++ ){
        //Get current label:
        uchar currentLabel = rowTable.at<uchar>( y, x );
        //Is it a valid label?
        if ( currentLabel != 255 ){
            //Get the bounding box for this label:
            cv::Rect currentBoundingBox = boundingBoxMap[ currentLabel ];
            cv::rectangle( testImage, currentBoundingBox, cv::Scalar(0,255,0), 2, 8, 0 );
            //The blob counter to string:
            std::string counterString = std::to_string( blobCounter );
            cv::putText( testImage, counterString, cv::Point( currentBoundingBox.x, currentBoundingBox.y-1 ),
                         cv::FONT_HERSHEY_SIMPLEX, 0.7, cv::Scalar(255,0,0), 1, cv::LINE_8, false );
            blobCounter++; //Increment the blob/label
        }
    }
}

Ничего необычного, просто обычный вложенный цикл for, перебирающий каждый пиксель на row table. Если пиксель отличается от белого, используйте label, чтобы получить как centroid, так и bounding box, и просто измените label на возрастающее число. Для отображения результата я просто рисую ограничивающие рамки и новую метку на исходном изображении.

Посмотрите упорядоченную обработку в этой анимации:

Очень круто, вот бонусная анимация, таблица строк заполняется горизонтальными координатами:

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

def get_contour_precedence(contour, cols):
tolerance_factor = 4
origin = cv2.boundingRect(contour)
return (((origin[1] + origin[3])/2 // tolerance_factor) * tolerance_factor) * cols + (origin[0] + origin[2]) / 2

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

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

def get_contour_precedence(contour, cols):
     tolerance_factor = 61
     M = cv2.moments(contour)
     # calculate x,y coordinate of centroid
     if M["m00"] != 0:
             cX = int(M["m10"] / M["m00"])
             cY = int(M["m01"] / M["m00"])
     else:
     # set values as what you need in the situation
             cX, cY = 0, 0
     return ((cY // tolerance_factor) * tolerance_factor) * cols + cX

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

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

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

import cv2
import numpy as np

## (1) read
img = cv2.imread("yFX3M.png")
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

## (2) threshold
th, threshed = cv2.threshold(gray, 127, 255, cv2.THRESH_BINARY_INV|cv2.THRESH_OTSU)

## (3) minAreaRect on the nozeros
pts = cv2.findNonZero(threshed)
ret = cv2.minAreaRect(pts)

(cx,cy), (w,h), ang = ret
if w>h:
    w,h = h,w

## (4) Find rotated matrix, do rotation
M = cv2.getRotationMatrix2D((cx,cy), ang, 1.0)
rotated = cv2.warpAffine(threshed, M, (img.shape[1], img.shape[0]))

## (5) find and draw the upper and lower boundary of each lines
hist = cv2.reduce(rotated,1, cv2.REDUCE_AVG).reshape(-1)

th = 2
H,W = img.shape[:2]
#   (6) using histogramm with threshold
uppers = [y for y in range(H-1) if hist[y]<=th and hist[y+1]>th]
lowers = [y for y in range(H-1) if hist[y]>th and hist[y+1]<=th]

rotated = cv2.cvtColor(rotated, cv2.COLOR_GRAY2BGR)
for y in uppers:
    cv2.line(rotated, (0,y), (W, y), (255,0,0), 1)

for y in lowers:
    cv2.line(rotated, (0,y), (W, y), (0,255,0), 1)
cv2.imshow('pic', rotated)

# (7) we iterate all rois and count 
for i in range(len(uppers)) : 
    print('line=',i)
    roi = rotated[uppers[i]:lowers[i],0:W]
    cv2.imshow('line', roi)
    cv2.waitKey(0)
    # here again calc thres and contours

Я нашел старый пост с этим кодом здесь

Вот один из способов в Python/OpenCV, сначала обрабатывая строки, а затем символы.

• Прочитать ввод
• Преобразовать в оттенки серого
• Порог и инвертировать
• Используйте длинные горизонтальные ядра и применяйте морфологию, близкую к ряду формы.
• Получите контуры строк и их ограничивающие рамки
• Сохраните поля строк и отсортируйте по Y
• Прокрутите каждое поле отсортированной строки и извлеките строку из изображения с пороговым значением.
• Получите контуры каждого символа в строке и сохраните ограничивающие рамки символов.
• Сортировать контуры для данной строки по X
• Нарисуйте ограничивающие рамки на входе и номер индекса в виде текста на изображении.
• Увеличить индекс
• Сохраните результаты

Вход:

import cv2
import numpy as np

# read input image
img = cv2.imread('vision78.png')

# convert img to grayscale
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# otsu threshold
thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_OTSU )[1]
thresh = 255 - thresh 

# apply morphology close to form rows
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (51,1))
morph = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kernel)

# find contours and bounding boxes of rows
rows_img = img.copy()
boxes_img = img.copy()
rowboxes = []
rowcontours = cv2.findContours(morph, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
rowcontours = rowcontours[0] if len(rowcontours) == 2 else rowcontours[1]
index = 1
for rowcntr in rowcontours:
    xr,yr,wr,hr = cv2.boundingRect(rowcntr)
    cv2.rectangle(rows_img, (xr, yr), (xr+wr, yr+hr), (0, 0, 255), 1)
    rowboxes.append((xr,yr,wr,hr))

# sort rowboxes on y coordinate
def takeSecond(elem):
    return elem[1]
rowboxes.sort(key=takeSecond)
    
# loop over each row    
for rowbox in rowboxes:
    # crop the image for a given row
    xr = rowbox[0]
    yr = rowbox[1]
    wr = rowbox[2]
    hr = rowbox[3]  
    row = thresh[yr:yr+hr, xr:xr+wr]
    bboxes = []
    # find contours of each character in the row
    contours = cv2.findContours(row, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    contours = contours[0] if len(contours) == 2 else contours[1]
    for cntr in contours:
        x,y,w,h = cv2.boundingRect(cntr)
        bboxes.append((x+xr,y+yr,w,h))
    # sort bboxes on x coordinate
    def takeFirst(elem):
        return elem[0]
    bboxes.sort(key=takeFirst)
    # draw sorted boxes
    for box in bboxes:
        xb = box[0]
        yb = box[1]
        wb = box[2]
        hb = box[3]
        cv2.rectangle(boxes_img, (xb, yb), (xb+wb, yb+hb), (0, 0, 255), 1)
        cv2.putText(boxes_img, str(index), (xb,yb), cv2.FONT_HERSHEY_COMPLEX_SMALL, 0.75, (0,255,0), 1)
        index = index + 1
    
# save result
cv2.imwrite("vision78_thresh.jpg", thresh)
cv2.imwrite("vision78_morph.jpg", morph)
cv2.imwrite("vision78_rows.jpg", rows_img)
cv2.imwrite("vision78_boxes.jpg", boxes_img)

# show images
cv2.imshow("thresh", thresh)
cv2.imshow("morph", morph)
cv2.imshow("rows_img", rows_img)
cv2.imshow("boxes_img", boxes_img)
cv2.waitKey(0)

Пороговое изображение:

Морфологическое изображение рядов:

Изображение контуров строк:

Изображение контуров персонажей: