[Из песочницы] Документ в перспективе, что с ним делать? Корректировка результатов бесконтактного сканирования и фотографий документов
Идея данной статьи возникла у нас после прочтения статьи «Как работает автоматическое выделение документа на изображении в программе ABBYY FineScanner?», опубликованной на Хабре компанией ABBYY, в которой подробно описан алгоритм определения границ документа на образе, полученном камерой мобильного телефона.Статья, безусловно, интересная и полезная. Мы, «с чувством глубокого удовлетворения» отметили, что ABBYY использует в работе те же математические алгоритмы, что и мы, и благоразумно опускает некоторые детали, без которых точность определения границ документа существенно снижается.Думаю, что по прочтении статьи у некоторой части читателей возник резонный вопрос: «А что делать с обнаруженным на снимке документом дальше?» Отвечу словами Чеширского Кота Алисе: «А куда ты хочешь прийти?» Если конечная цель — «вытащить» из снимка текстовые данные, тогда нужно максимально облегчить задачу системе распознавания. Для этого в первую очередь нужно исправить перспективные искажения, бич всех фотоснимков документов «от руки». Если не решить эту проблему, попытка распознать данные может дать результат, сравнимый с попытками распознавания капчи. На фрилансерских сайтах с завидной регулярностью появляются «верующие» в победу машинного интеллекта над капчой за мелкий прайс. Блажен, кто верует, но мы сейчас не об этом.Итак, в данной статье мы попытаемся подхватить эстафету у ABBYY и рассказать на своем опыте, как можно с минимальными затратами привести призмообразный, в лучшем случае, документ, который мы идентифицировали на снимке (спасибо ABBYY за науку), к прямоугольной форме, желательно с сохранением исходных пропорций. Экзотические случаи, вроде пятиугольных или овальных документов мы пока не рассматриваем, хотя, вопрос интересный.Проблема искажения перспективных искажений возникла перед ALANIS Software не совсем с той стороны, откуда можно было ожидать. Я имею в виду, тот факт, что мы не специализируемся на мобильной разработке. Однако, наш заказчик, для которого мы разрабатываем систему сканирования и обработки образов для планетарных сканеров на базе цифрозеркальных камер Canon EOS (привет, фотографы!) в определенный момент захотел иметь такой функционал в арсенале. Причем, речь шла не об обработке готового снимка камеры, а о корректировке видеопотока, на этапе предпросмотра LiveView. Впрочем, разработанное нами решение одинаково хорошо работает и в режиме коррекции уже сделанного снимка документа.Дано: снимок прямоугольного документа фотокамерой с искажениями
контуры документа на снимке
Задача: привести документ к исходной форме кратчайшим путемChallenge (русский эквивалент как-то не приходит в голову): пропорции исходного документа нам точно не известны
расстояние до плоскости, на которой лежит документ нам не известно
референсных объектов, на которые можно ориентироваться (например, правильный квадрат, попавший в объектив) на снимке нет
Решение: Итак, чтобы решить задачу в целом, предлагаем разбить её на две отдельные: Нахождение, собственно, искаженного контура документа на отсканированном изображении (пожалуй, осветим ещё раз этот вопрос для тех, кто не читал статью ABBYY).
Определение правильных пропорций документа, в которые исходный искаженный контур должен быть отображен для того, чтобы получить выровненный документ.
Можно, конечно, было попытаться изобрести велосипед, и некоторым это до сих пор удается, но мы пошли более легким путем и использовали инструментарий OpenCV. Работаем мы по большей части в среде .NET, через C# Wrapper OpenCVSharp. Также OpenCVSharp доступен в виде Nuget-пакета в среде Visual Studio. «Вот это всё» © и будем использовать.Рассмотрим основные интересные моменты в решении задачи по исправлению перспективного изображения на следующем изображении: 
1. Для того чтобы найти контур на представленном изображении, необходимо избавиться от мелких деталей, которые могут мешать. Это можно сделать применив «заклинание размытия» по Гауссу малой мощности, предварительно сконвертировав изображение в оттенки серого: imgSource.CvtColor (imgGrayscale, ColorConversion.BgrToGray); imgSource.Smooth (imgSource, SmoothType.Gaussian, 15);
Вот, что получилось в результате применения вышеописанной цепочки (если я сниму очки, будет примерно такой же эффект. Отсюда мораль: «Близорукость не недуг, а интеллектуальная обработка изображения, имеющая целью отсеять всё лишнее и сделать мир более прекрасным!»): 
2. Далее необходимо сделать изображение черно-белым:
imgSource.Threshold (imgSource, 0, 255, ThresholdType.Binary | ThresholdType.Otsu); 
3. На полученном изображении легко найти контур документа. Будем искать максимальный внешний контур. В OpenCVSharp есть замечательный класс CvContourScanner, который может перечислять все найденные контуры изображения. С использованием Linq можно эти контуры отсортировать по площади и взять первый, который и будет самым максимальным.
using (var storage = new CvMemStorage ()) using (var scanner = new CvContourScanner (image, _storage, CvContour.SizeOf, ContourRetrieval.External, ContourChain.ApproxSimple)) { var largestContour = scanner.OrderBy (contour => Math.Abs (contour.ContourArea ())).FirstOrDefault (); }
Если нарисовать найденный контур, то получается следующее изображение: 
4. Ура! Нашли контур! Однако, он мало что может показать — необходимо знать точно координаты всех угловых точек — точек пересечения сторон документа. Очевидно, что для нахождения координат этих точек желательно описать стороны найденного контура уравнениями прямой линии. Как же нам в этом может помочь OpenCV? Очень просто! В нем есть инструмент, использующий преобразование Хафа. «Кастуем» этот метод на изображение, полученное на предыдущем шаге: var lineSegments = imgSource.HoughLines2(storage, HoughLinesMethod.Probabilistic, 1, Math.PI / 180.0, 70, 100, 1).ToArray
var verticalSegments = segments .Where (s => Math.Abs (s.P1.X — s.P2.X) < Math.Abs(s.P1.Y - s.P2.Y)) .ToArray(); var horizontalSegments = segments .Where(s => Math.Abs (s.P1.X — s.P2.X) >= Math.Abs (s.P1.Y — s.P2.Y)) .ToArray ();
Отрезки линий, которые «динамичнее» изменяются по вертикали — это вертикальные; по горизонтали — горизонтальные. Стало намного проще, можно даже нарисовать, что получилось: 
Далее, попробуем найти точки пересечения всех вертикальных и горизонтальных линий. Смотрим, что получается:
var corners = horizontalSegments .SelectMany (sh => verticalSegments .Select (sv => sv.LineIntersection (sh)) .Where (v => v!= null) .Select (v => v.Value)) // exclude points which is out of image area .Where (c => new CvRect (0, 0, imgSource.Width, imgSource.Height).Contains©) .ToArray ();
Осталось теперь отсортировать все найденные точки по часовой стрелке относительно центра масс этих точек: 
— среднее арифметическое по каждой из координат). После этого из отсортированного массива создаем контур и аппроксимируем его средствами OpenCVSharp:
contour = contour.ApproxPoly (CvContour.SizeOf, storage, ApproxPolyMethod.DP, contour.ArcLength () * 0.02, true);
И, вуаля! Мы, наконец-то получили искомые точки искаженного контура: 
5. Вот, теперь самое вкусное. Единственное, что осталось сделать — это вычислить угловые точки выровненного контура с тем, чтобы потом отобразить в них искаженные точки. Если быть точным, необходимо найти пропорции документа, которые восприятие человеческого глаза могло посчитать верными. Основная проблема, которая встала перед нами — это отсутствие каких-либо начальных данных, по которым можно было бы вычислить правильные пропорции документа. Не было информации ни о том, под каким углом был отсканирован документ, ни о фокусном расстоянии.
Сразу оговорюсь, решение, описанное далее, не является универсальным для всех случаев перспективного искажения и не дает 100% точности восстановления исходных пропорций документа. Однако, для наших целей и с нашими вводными, это решение компактно, вполне жизнеспособно, не лишено элегантности, и дает неплохие результаты.Итак, дисклэймер озвучен, к делу. Мы решили пойти простым путем: взять максимальные по длине горизонтальную и вертикальную стороны искаженного контура и использовать эти величины в качестве размеров выровненного контура. Однако этот метод давал приемлемые результаты лишь на небольших искажениях. Более серьезные искажения, такие как это, например: 
приводили к получению подобных результатов: 
Согласитесь, это не то, что хотелось увидеть на выходе. Квадратный документ нам не нужен!
Необходимо было придумать что-то более качественное. Опытным путем было замечено, что на искаженных документах наблюдается отклонение центра масс угловых точек контура от точки пересечения диагоналей контура (рисунок 10, желтое кольцо — центр масс, зеленый круг — точка пересечения диагоналей): 
Нетрудно догадаться, что на «ровных» документах эти точки совпадают. Если же есть какое-то искажение, то обязательно будет наблюдаться отклонение и чем искажение больше, тем больше и отклонение. Вооружившись этим фактом и еще чуть-чуть поисследовав, мы пришли к простой формуле, точнее к двум: 
где:
deltaX, deltaY — это отклонения центра масс от точки пересечения диагоналей, соответственно; targetWidth, targetHeight — размеры результирующего контура; topWidth, bottomWidth, leftHeight, rightHeight — размеры искаженного контура.
А вот результат применения этой формулы: 
Для сравнения приведем пропорции исходного документа, отсканированного без искажений: 
Вот это уже больше походит на правду. И заказчикам нравится, и нам очень приятно получать такие близкие результаты.
Безусловно, если «копать» дальше, то можно «отрыть» более качественный способ вычисления правильных пропорций, и я уверен, что сообщество Хабра обязательно предложит что-то или натолкнет на мысль…
Надеемся, что наш материал окажется кому-то полезным. В заключение, предлагаю ознакомиться с вещественным доказательством реальности описанного. Мы сняли видео ролик с помощью нашей программы сканирования, управляющей цифровой камерой Canon. В данном случае «магия» происходит «на лету» в режиме предпросмотра сканирования LiveView, а результат вычислений применяется уже в момент сканирования.
[embedded content]
Мы планируем и дальше делиться некоторыми хитростями обработки изображений на Хабре, если эта тема окажется востребованной. На нашем канале в youtube уже есть пара роликов, иллюстрирующих наши разработки, мы планируем и дальше вести летопись нашего развития в видео формате и в формате статей. Спасибо за внимание!
