Введение

Привет, Хабр! Я работаю разработчиком в АльфаСтрахование – в команде, которая занимается электронным документооборотом. Наша команда уже рассказывала о своих решениях на хабре (статья про Odata, статья про интеграцию с Почтой России). Цель новой серии статей о распознавании подписи  – рассказать о ещё одной решенной нами задаче (как нам кажется, интересной)

В чем суть проблемы, с которой мы столкнулись: несмотря на то, что документооборот внутри компании полностью электронный, на «входе» документы могут поступать к нам в самых разных форматах: отсканированные с бумажных носителей, в «цифре» с ЭЦП или без электронной подписи – чтобы обеспечить сквозную обработку таких документов, в ряде процессов нам требуется распознавать наличие подписи.

Анализ проблемы и требований

Изначально пилотировали процесс на документах со статичной формой, где место для подписи жестко закреплено шаблоном. Но потом расширили задачу до проработки общих правил и механизмов распознавания подписи в разных документах, отличающихся по формату. Поэтому начали с того, что на этапе дизайна шаблонов документов добавили в макет квадрат для подписи. Квадрат был нужен для того, чтобы на листе появился объект, за который алгоритм распознавания в будущем мог бы «цепляться» при поиске подписи.

Документы, подписи на которых нам необходимо было распознавать, соответствуют следующему шаблону:

На входе перед нами стояло два основных требования: Во-первых, необходимо было распознавать не менее 95% подписей на документах. Оставшимися процентами можно пренебречь, и оставить на валидацию человеком. Во-вторых, решение требовалось внедрить в существующую систему сканирования, но при этом обеспечить его атомарность. Система сканирования написана на .Net Framework 4.7 (.net47).

Выбор инструмента для распознавания

Одним из первых инструментов, на который мы обратили внимание, стало распознавание средствами RPA (Robotic Process Automation). Но по ряду причин нам пришлось от него отказаться:

• решение распознавания наличия подписи с помощью инструмента RPA не являлось бы универсальным и масштабируемым для аналогичных задач из-за:

  • лицензии RPA, которую нужно продлевать;

  • времени, которое необходимо потратить на каждую операцию;

  • большой завязки на UI-интерфейс.

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

Также мы рассматривали Python + OpenCV. Но от этой идеи также пришлось отказаться из-за отсутствия в команде глубоких компетенции в Python.

После поиска и анализа различных инструментов существующих на рынке было принято решение остановится на EmguCV. Это Open-Source библиотека, которая позволит использовать OpenCV для распознавания изображений из приложения созданного на базе .net.

Распознавание подписи по прямоугольнику

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

Наш итоговый алгоритм распознавания по прямоугольнику выглядит следующим образом:

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

Прежде чем переходить к реализации алгоритма, добавьте в свой проект следующие зависимости:

• <PackageReference Include="Emgu.CV" Version="4.5.2.4673" /> - для взаимодействия с OpenCV через API EmguCV;

• <PackageReference Include="Emgu.CV.runtime.windows" Version="4.5.2.4673" /> - содержит среду выполнения EmguCV
  для windows.

Также нам пришлось настроить проект на платформу x86. Это связанно с тем, что nuget пакет Emgu.CV тянет библиотеки, работающие именно под эту платформу. Нам показалось проще переделать проект под платформу, чем «научить» Emgu.CV тянуть другие библиотеки.

Для работы с изображением мы будем использовать класс UMat в EmguCV. Его основное отличие от Mat в том, что он старается использовать ресурсы GPU, если это возможно.

Для преобразования массива байт в объект UMat мы использовали следующий код:

public static UMat ConvertToUMat(byte[] buffer, ImreadModes imread = ImreadModes.Color)
{
 using (var imageMat = new Mat())
 {
 CvInvoke.Imdecode(buffer, imread, imageMat);
 var result = new UMat();
 imageMat.CopyTo(result);
 return result;
 }
}

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

Повернуть документ в изображении строго вертикально

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

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

public static double GetRotateAngle(UMat src, CannyOptions options)
{
 using var crop = new UMat(src, new Rectangle(0, 0, src.Size.Width, src.Size.Height / 2));
 using var gray = new UMat();
 crop.CvtColor(gray, ColorConversion.Bgr2Gray);
 using UMat canny = gray.GetCannyByOption(options);
 /*
 * Ищем отрезки, по углам которых, будем ориентировать поворот картинки
 * Это может помочь разобраться https://stackoverflow.com/questions/40531468/explanation-ofrho-and-theta-parameters-in-houghlines
 */
 LineSegment2D[] lines = canny.HoughLinesP(1, Math.PI / 180, 100, 100, 5);
 var angles = new List<double>(lines.Length);
 foreach (LineSegment2D line in lines)
 {
 // Через тангенс определяем угол отрезка (математика 8-го класса)
 double atan = Math.Atan2(line.P2.Y - line.P1.Y, line.P2.X - line.P1.X);
 // Переводим в радианы
 double angle = atan * 180 / Math.PI;
 angles.Add(angle);
 }
 // Медиана всех углов и будет углом поворота
 return angles.Median();
}
/// <summary>
/// Возвращает медиану чисел <paramref name="numbers"/>
/// </summary>
public static double Median(this IEnumerable<double> numbers)
{
 int count = numbers.Count();
 int halfIndex = count / 2;
 IOrderedEnumerable<double> sorted = numbers.OrderBy(item => item);
 if (count % 2 != 0)
 return sorted.ElementAt(halfIndex);
 var counter = 0;
 int nextHalfIndex = halfIndex + 1;
 double result = 0;
 foreach (double number in sorted)
 {
 if (counter == halfIndex || counter == nextHalfIndex)
 result += number;
 else if (counter > nextHalfIndex)
 break;
 counter++;
 }
 return result / 2;
}

*CannyOptions - класс для упрощения взаимодействия с методом CvInvoke.Canny и настройки значений через appsettings.json.

*.CvtColor – метод расширения для упрощения взаимодействия, который под капотом просто перевызывает CvInvoke.CvtColor.

*.GetCannyByOption – метод расширения, который создает новый объект UMat и записывает в него результат обработки алгоритмом Canny.

*.HoughLinesP - метод расширения для упрощения взаимодействия, который под капотом просто перевызывает CvInvoke.HoughLinesP.

Теперь, когда мы можем определить угол поворота, нам нужен метод, который может повернуть изображение на этот угол.

/// <summary>
/// Возвращает повернутое изображение
/// </summary>
public static UMat GetRotateUMat(byte[] buffer, double angle)
{
    using Image image = ConvertToImage(buffer);
    using Image rotate = image.GetRotateImage(Convert.ToSingle(angle));

    return rotate.ToUMat();
}

/// <summary>
/// Преобразует массив байт (<paramref name="buffer"/>) в изображение в формате <see cref="Image"/>
/// </summary>
/// <param name="buffer">Буфер с изображением</param>
/// <returns>Изображение</returns>
public static Image ConvertToImage(byte[] buffer)
{
    using var memoryStream = new MemoryStream(buffer);

    return Image.FromStream(memoryStream);
}

/// <summary>
/// Возвращает повернутое изображение
/// </summary>
/// <remarks>Код взят по ссылке: https://stackoverflow.com/questions/2163829/how-do-i-rotate-a-picture-in-winforms</remarks>
public static Image GetRotateImage(this Image img, float rotationAngle)
{
    var bmp = new Bitmap(img.Width, img.Height);
    using Graphics gfx = Graphics.FromImage(bmp);

    gfx.TranslateTransform((float)bmp.Width / 2, (float)bmp.Height / 2);
    gfx.RotateTransform(rotationAngle);
    gfx.TranslateTransform(-(float)bmp.Width / 2, -(float)bmp.Height / 2);

    gfx.InterpolationMode = InterpolationMode.HighQualityBicubic;

    gfx.DrawImage(img, new Point(0, 0));

    return bmp;
}

Важное уточнение! В этом участке кода мы работаем с System.Drawing.Image. Мы не использовали методы поворота в API EmguCV, так как эти методы позволяли поворачивать изображение только на 90%.

Теперь нужно непосредственно повернуть документ в изображении строго вертикально:

public static UMat VerticalRotateDocument(byte[] src, CannyOptions cannyOptions)
{
    UMat srcUmat = ConvertToUMat(src);
    double median = GetRotateAngle(srcUmat, cannyOptions);

    // документ уже вертикально стоит
    if (median == 0)
        return srcUmat;

    UMat result = GetRotateUMat(src, median);

    // Если так случилось, то значит повернули изображение не в ту сторону
    if (median < GetRotateAngle(result, cannyOptions))
    {
        result.Dispose();
        result = GetRotateUMat(src, median * -1);
    }

    return result;
}

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

Обрезать 80% изображения сверху и 20% по бокам

Прибегая к данному шагу мы уменьшаем зону поиска и, как следствие, сокращаем время и ресурсы, которые нужны алгоритму на обработку:

public static UMat CropUMat(this UMat src, CropOptions options)
{
    decimal cropLeft = (decimal)options.LeftInPercentage / 100;
    decimal cropTop = (decimal)options.TopInPercentage / 100;
    decimal cropRight = (decimal)options.RightInPercentage / 100;
    decimal cropBotton = (decimal)options.BottomInPercentage / 100;

    Size oldSize = src.Size;

    var location = new Point(
        (int)Math.Round(oldSize.Width * cropLeft),
        (int)Math.Round(oldSize.Height * cropTop)
    );

    int width = cropRight > 0
        ? oldSize.Width - (int)Math.Round(oldSize.Width * cropRight) - location.X
        : oldSize.Width - location.X;

    int height = cropBotton > 0
        ? oldSize.Height - (int)Math.Round(oldSize.Height * cropBotton) - location.Y
        : oldSize.Height - location.Y;

    return new UMat(src, new Rectangle(location, new Size(width, height)));
}

*CropOptions - это созданный нами класс для метода инкапсуляции логики обрезания картинки.

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

Найти наибольший прямоугольник

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

public static UMat ContoursReconstruction(UMat src,
                                          GaussianBlurOptions gaussianBlurOptions,
                                          CannyOptions cannyOptions)
{
    using var gray = new UMat();
    src.CvtColor(gray, ColorConversion.Bgr2Gray);

    using UMat blur = gray.GetGaussianBlurByOption(gaussianBlurOptions);
    using UMat canny = blur.GetCannyByOption(cannyOptions);
    using Mat kernel = CvInvoke.GetStructuringElement(ElementShape.Cross, new Size(3, 3), new Point(1, 1));

    var result = new UMat();
    var defaultColor = new MCvScalar(255, 255, 255);
    var defaultPoint = new Point(1, 1);
    var iteration = 1;

    canny.MorphologyEx(
        result,
        MorphOp.Close,
        kernel,
        defaultPoint,
        iteration,
        BorderType.Constant,
        defaultColor);

    return result;
}

*GaussianBlurOptions - класс для упрощения взаимодействия с методом CvInvoke.GaussianBlur и настройки значение через appsettings.json.

*.GetGaussianBlurByOption – метод расширения, который создает новый объект UMat и записывает в него результат обработки алгоритмом Gaussian.

*.MorphologyEx - метод расширения для упрощения взаимодействия, который под капотом перевызывает CvInvoke.MorphologyEx.

После того как как мы восстановили контуры, их необходимо получить:

public static VectorOfVectorOfPoint GetCountors(this UMat src)
{
    using var hierarchy = new UMat();
    var contours = new VectorOfVectorOfPoint();
    src.FindContours(contours, hierarchy, RetrType.List, ChainApproxMethod.ChainApproxNone);

    return contours;
}

*.FindContours - метод расширения для упрощения взаимодействия, который под капотом просто перевызывает CvInvoke.FindContours.

Теперь мы можем благополучно искать прямоугольник:

public static Rectangle? GetLargestRectangle(VectorOfVectorOfPoint contours)
{
    const double minRectanglePerimeter = 0.4;
    const double partOfPerimeterEpsilon = 0.07;

    foreach (KeyValuePair<int, double> item in contours.GetSortedContoursByArea())
    {
        using var contour = contours[item.Key];
        double contourPerimeter = contour.ArcLength(true);

        if (contourPerimeter < minRectanglePerimeter)
            continue;

        using var approximation = new VectorOfPoint();
        contour.ApproxPolyDP(approximation, partOfPerimeterEpsilon * contourPerimeter, true);

        if (contour.IsContourRectangle(partOfPerimeterEpsilon * contourPerimeter))
            return contour.BoundingRectangle();
    }

    return null;
}

/// <summary>
/// Определяет является ли контур приблизительно прямоугольником 
/// </summary>
public static bool IsContourRectangle(this VectorOfPoint contour, double epsilon)
{
    using var approximation = new VectorOfPoint();

    contour.ApproxPolyDP(approximation, epsilon, true);

    // Если это приблизительно 4-угольник и он выпуклый
    return approximation.IsApproximationRectangle();
}

/// <summary>
/// Определяет является ли аппроксимация приблизительно прямоугольником
/// </summary>
public static bool IsApproximationRectangle(this VectorOfPoint approximation)
{
    // Если это приблизительно 4-угольник и он выпуклый
    return approximation.Size >= 4
        && approximation.Size <= 8
        && approximation.IsContourConvex();
}

/// <summary>
/// Возвращает индексы контуров, отсортированные по убыванию площадей
/// </summary>
/// <returns>Индексы контуров отсортированные по убыванию площадей {key: index; value: area}</returns>
public static Dictionary<int, double> GetSortedContoursByArea(this VectorOfVectorOfPoint contours)
{
    var result = new Dictionary<int, double>();
    int size = contours.Size;

    if (size == 0)
        return result;

    for (var i = 0; i < size; i++)
        using (VectorOfPoint contour = contours[i])
        {
            double area = contour.ContourArea();
            result.Add(i, area);
        }

    return result
       .OrderByDescending(item => item.Value)
       .ToDictionary(item => item.Key, item => item.Value);
}

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

• *.ApproxPolyDP -> CvInvoke.ApproxPolyDP

• *.IsContourConvex -> CvInvoke.IsContourConvex

• *.BoundingRectangle -> CvInvoke.BoundingRectangle

• *.ContourArea -> CvInvoke.ContourArea

Обрезать изображение по прямоугольнику

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

public static UMat CropImageByLargestRectangle(UMat src)
{
    using var contours = src.GetCountors();

    // Если контуров нет, то и искать нечего
    if (contours.Size == 0)
        return null;

    Rectangle? rectangle = GetLargestRectangle(contours);

    if (!rectangle.HasValue)
        return null;

    return new UMat(src, rectangle.Value);
}

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

Найти любой контур, напоминающий подпись

Ну и, собственно, последний штрих: нужно найти любой контур напоминающий подпись:

public static bool ContainsSigned(UMat src)
{
    const double partOfPerimeterEpsilon = 0.07;

    using var hierarchy = new UMat();
    using var contours = new VectorOfVectorOfPoint();

    src.FindContours(contours, hierarchy, RetrType.List, ChainApproxMethod.ChainApproxNone);

    double minSignatureContourPerimeter = Math.Round(src.Size.Width * 0.4);

    int size = contours.Size;

    // Если контуров нет, то подписи тем более нет
    if (contours.Size == 0)
        return false;

    double imageOfSignatureArea = src.Size.Width * src.Size.Height;

    for (var i = 0; i < size; i++)
    {
        using VectorOfPoint contour = contours[i];
        double perimeter = contour.ArcLength(true);

        if (perimeter < minSignatureContourPerimeter)
            continue;

        double contourArea = contour.ContourArea();
        double areaRatio = contourArea / imageOfSignatureArea;

        // Словили какой-то не внятный объект
        if (areaRatio >= 0.3)
            continue;

        using var approximation = new VectorOfPoint();
        contour.ApproxPolyDP(approximation, partOfPerimeterEpsilon * perimeter, true);

        // Не подходящий объект
        bool invalid = approximation.IsApproximationRectangle()
            || approximation.Size <= 2
            && perimeter / contourArea >= 0.5
            || approximation.ToArray().AnyAngle90Degree();

        if (invalid)
            continue;

        return true;
    }

    return false;
}

/// <summary>
/// Определяет содержит ли кривая хотя бы один угол примерно 90 градусов
/// </summary>
public static bool AnyAngle90Degree(this Point[] pts, double deviation = 5)
{
    double leftDeviation = 90 - deviation / 2;
    double rightDeviation = 90 + deviation / 2;

    return pts
       .GetExteriorAngles()
       .Any(angle => angle > leftDeviation && angle < rightDeviation);
}

/// <summary>
/// Вернуть внешние углы кривой
/// </summary>
public static IEnumerable<double> GetExteriorAngles(this Point[] pts)
{
    LineSegment2D[] edges = pts.PolyLine(true);

    return edges
       .Select((edge, j) => Math.Abs(edges[(j + 1) % edges.Length]
           .GetExteriorAngleDegree(edge)));
}

Потребляемые ресурсы

Разработка данного решения велась на компьютере со следующей конфигурацией:

Посмотрим на потребляемые ресурсы, используя изображение с указанными параметрами:

После однократного прогона такого изображения через алгоритм мы получаем такие результаты:

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

Так как на машине, на которой велась разработка, используется встроенный GPU, на обработку графики задействовались мощности CPU – на скриншоте видно, какую долю ресурсов процессора это занимает.

Теперь прогоним это же изображение, но уже 10 раз и посмотрим на результат:

Как видно из рисунка, наше предположение оказалось верным. Прогнав изображение 10 раз, мы не получили повышенное потребление памяти. Оно вообще почти не изменилось.

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

Результат алгоритма распознавания по прямоугольнику

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

В следующей статье речь пойдет о том, как мы решали указанные проблемы.