Поиск подписи на документе

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

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

Постановка задачи

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

 

А внизу будет место для подписи:

Задача проста: нужно по скану заявления сказать, есть тут подпись или нет. Задача разбивается на две подзадачи:

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

Поиск места для подписи

Чтобы искать место для подписи его нужно как-то предварительно пометить. В процессе поиска решения я попробовал несколько вариантов:

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

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

Разумеется, вырезать из такого скана по одному изображению, да и еще описывать его в good.txt вручную очень долго, поэтому пришлось написать инструменты автоматизации этого процесса, которые мне значительно ускорили процесс. (я повторял эти действия для различных способов выделения подписи)
Отрицательную выборку я сделал скачав электронный вариант каких-то двух книг про Assembler.  В итоге у меня было было 594 положительных изображения и 1518 отрицательных. Экспериментальным путем удалось успешно обучить алгоритм на следующих параметрах (остальные по умолчанию):

minHitRate 0.99
height 30
width 43
maxFalseAlarm 0.4

Выборка оказалась хорошей и алгоритм закончил свою работу за 9 стадий (считая от 0), достигнув максимального уровня ложной тревоги. Суммарное время обучение около 3 суток, правда последние сутки была 10 стадия, которая потом была прервана.

Если читать официальную документацию opencv, то перед тем, как производить поиск они советуют совершить преобразование equalizeHist с изображением. Это позволяет улучшить яркость и контраст изображения перед последующим поиском. Заявление после преобразование выглядело примерно так:

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

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

Определение наличия подписи

Первое что я сделал, это сузил площадь поиска в 4 раза. Это позволило мне не обращать внимание на рамку и свести задачу к тому, есть ли что-либо на белом фоне или нет. Рисунок снизу наглядно показывает допустимость такого шага. (Маловероятно, что человек распишется в углу за границей рамки)

 

Первая мысль была просто считать количество темных пикселей. Но это неправильно, т.к. сканеры бывают разные, бумага бывает разной и поэтому никто не знает, что значит "темный" пиксель. Я поступил следующим образом: у каждого пикселя есть цвет, причем поскольку картинка черно-белая, то этот цвет представлен одним числом. 255 - белый, 0 - черный. Для удобства я ввел параметр "чернота" пикселя, который вычисляется по формуле:

 blackness =  255 - color

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

Код

package ru.kosdev;

import org.bytedeco.javacpp.opencv_core;
import org.bytedeco.javacpp.opencv_imgproc;
import org.bytedeco.javacpp.opencv_objdetect;

import java.nio.ByteBuffer;

import static org.bytedeco.javacpp.opencv_imgcodecs.CV_LOAD_IMAGE_GRAYSCALE;
import static org.bytedeco.javacpp.opencv_imgcodecs.imread;
import static org.bytedeco.javacpp.opencv_imgcodecs.imwrite;
import static org.bytedeco.javacpp.opencv_imgproc.rectangle;

/**
 * Created by Константин on 21.08.2015.
 */
public class SignDetector {

    private final int squareDeviation;
    private opencv_objdetect.CascadeClassifier classifier;

    /**
     * Создание детектора
     * @param cascadeFileName - имя файла каскада
     * @param deviationLevel - уровень стандартного отклонения для обнарукжения подписи
     */
    public SignDetector(String cascadeFileName, int deviationLevel) {
        classifier = new opencv_objdetect.CascadeClassifier(cascadeFileName);
        this.squareDeviation = deviationLevel*deviationLevel;
    }

    /**
     * Проверяет, есть ли подпись в скане.
     * @param srcFName - имя исходного файла
     * @param drawFileName - имя файла для сохранения результата рисования
     * @return
     */
     public boolean detectSign(String srcFName, String drawFileName) {
        //читаем изображение из файла
        opencv_core.Mat mat = imread(srcFName, CV_LOAD_IMAGE_GRAYSCALE);

        //сюда складываем области изображения, в которых может быть подпись
        opencv_core.RectVector rectVector = new opencv_core.RectVector();

        //поиск фрагментов
        classifier.detectMultiScale(mat, rectVector);
        boolean hasFound = rectVector.size() > 0;

        if (!hasFound) {
            //попробуем обработать изображение и опять найти
            opencv_core.Mat equalized = new opencv_core.Mat();
            opencv_imgproc.equalizeHist(mat, equalized);
            classifier.detectMultiScale(equalized, rectVector);
            hasFound = rectVector.size() > 0;
        }
        if (hasFound) {
            //находим самую большую область и уменьшаем ее в два раза
            opencv_core.Rect rect = reduceTwice(getMaxRect(rectVector));
            if (drawFileName != null) {
                //нарисуем рабочую область и сохраним в отдельный
                drawRect(mat, drawFileName, rect);
            }
            //поиск подписи
            return searchSign(mat, rect);
        }
        System.out.println("Sign place is not found");
        return false;
    }

    /**
     * Рисует прямоугольник и сохраняет в файл
     * @param mat - исходная матрица
     * @param resultFName - имя файла
     * @param rect - прямоугольник
     */
    private void drawRect(opencv_core.Mat mat, String resultFName, opencv_core.Rect rect) {
        int height = rect.height();
        int width = rect.width();
        int x = rect.tl().x();
        int y = rect.tl().y();
        opencv_core.Point start = new opencv_core.Point(x, y);
        opencv_core.Point finish = new opencv_core.Point(x+width, y + height);
        rectangle(mat, start, finish, opencv_core.Scalar.all(0));
        imwrite(resultFName, mat);
    }

    /**
     * Поиск подписи в фрагменте изображения
     * @param mat - матрица изображения
     * @param rect - выделенная область
     * @return
     */
    private boolean searchSign(opencv_core.Mat mat, opencv_core.Rect rect) {
        int x0 = rect.x();
        int y0 = rect.y();
        int x1 = rect.width() + x0;
        int y1 = rect.height() + y0;
        ByteBuffer byteBuffer = mat.getByteBuffer();

        //считаем среднюю "черноту" пикселя
        long blackness = 0;
        for (int y = y0; y <= y1; y++) {
            for (int x = x0; x <= x1; x++) {
                long index = y*mat.step() + x*mat.channels();
                int color = byteBuffer.get((int)index) & 0xFF;
                blackness += (255 - color);
            }
        }

        float background = blackness/rect.width()/rect.height();

        //считаем стандартное отклонение "черноты" пикселей
        long squareDev = 0;
        for (int y = y0; y <= y1; y++) {
            for (int x = x0; x <= x1; x++) {
                long index = y*mat.step() + x*mat.channels();
                int color = byteBuffer.get((int)index) & 0xFF;
                squareDev += (background - (255-color))*(background - (255-color));
            }
        }
        squareDev = squareDev/rect.width()/rect.height();

        return squareDev > squareDeviation;
    }

    /**
     * Возвразает максимальный прямоугольник
     * @param rectVector
     * @return
     */
    private opencv_core.Rect getMaxRect(opencv_core.RectVector rectVector) {
        int maxWidth = 0;
        opencv_core.Rect result = null;
        for (int i = 0; i <= rectVector.size(); i++) {
            opencv_core.Rect currentRect = rectVector.get(i);
            int width = currentRect.width();
            if (width > maxWidth) {
                maxWidth = width;
                result = currentRect;
            }
        }
        return result;
    }

    /**
     * Уменьшает размер прямоугольника в два раза, сохраняя положение центра
     * @param big
     * @return
     */
    private opencv_core.Rect reduceTwice(opencv_core.Rect big) {
        int height = big.height();
        int width = big.width();
        int x = big.tl().x();
        int y = big.tl().y();
        return new opencv_core.Rect(x+width/4, y+height/4, width/2, height/2);
    }
}

Пока алгоритм еще не прошел полноценного тестирования, но на моих 24 различных примерах он успешно работает.

UPD: на тестировании на 92 заявлений алгоритм ошибся в 3 случаях. Модернизация алгоритма с добавлением еще 3 преобразований позволила уменьшить количество ошибок до 1 случая из выборки. Преобразования следующие:

• перевернуть на 180 градусов.
• повернуть на 5 градусов влево
• повернуть на 5 градусов вправо

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