Идея данной статьи возникла у нас после прочтения статьи «Как работает автоматическое выделение документа на изображении в программе ABBYY FineScanner?», опубликованной на Хабре компанией ABBYY, в которой подробно описан алгоритм определения границ документа на образе, полученном камерой мобильного телефона.
Статья, безусловно, интересная и полезная. Мы, «с чувством глубокого удовлетворения» отметили, что ABBYY использует в работе те же математические алгоритмы, что и мы, и благоразумно опускает некоторые детали, без которых точность определения границ документа существенно снижается.
Думаю, что по прочтении статьи у некоторой части читателей возник резонный вопрос: «А что делать с обнаруженным на снимке документом дальше?» Отвечу словами Чеширского Кота Алисе: «А куда ты хочешь прийти?» Если конечная цель – «вытащить» из снимка текстовые данные, тогда нужно максимально облегчить задачу системе распознавания. Для этого в первую очередь нужно исправить перспективные искажения, бич всех фотоснимков документов «от руки». Если не решить эту проблему, попытка распознать данные может дать результат, сравнимый с попытками распознавания капчи. На фрилансерских сайтах с завидной регулярностью появляются «верующие» в победу машинного интеллекта над капчой за мелкий прайс. Блажен, кто верует, но мы сейчас не об этом.
Итак, в данной статье мы попытаемся подхватить эстафету у ABBYY и рассказать на своем опыте, как можно с минимальными затратами привести призмообразный, в лучшем случае, документ, который мы идентифицировали на снимке (спасибо ABBYY за науку), к прямоугольной форме, желательно с сохранением исходных пропорций. Экзотические случаи, вроде пятиугольных или овальных документов мы пока не рассматриваем, хотя, вопрос интересный.
Проблема искажения перспективных искажений возникла перед ALANIS Software не совсем с той стороны, откуда можно было ожидать. Я имею в виду, тот факт, что мы не специализируемся на мобильной разработке. Однако, наш заказчик, для которого мы разрабатываем систему сканирования и обработки образов для планетарных сканеров на базе цифрозеркальных камер Canon EOS (привет, фотографы!) в определенный момент захотел иметь такой функционал в арсенале. Причем, речь шла не об обработке готового снимка камеры, а о корректировке видеопотока, на этапе предпросмотра LiveView. Впрочем, разработанное нами решение одинаково хорошо работает и в режиме коррекции уже сделанного снимка документа.
Дано:
Задача:
привести документ к исходной форме кратчайшим путем
Challenge (русский эквивалент как-то не приходит в голову):
Решение:
Итак, чтобы решить задачу в целом, предлагаем разбить её на две отдельные:
Можно, конечно, было попытаться изобрести велосипед, и некоторым это до сих пор удается, но мы пошли более легким путем и использовали инструментарий OpenCV. Работаем мы по большей части в среде .NET, через C# Wrapper OpenCVSharp. Также OpenCVSharp доступен в виде Nuget-пакета в среде Visual Studio. «Вот это всё» (с) и будем использовать.
Рассмотрим основные интересные моменты в решении задачи по исправлению перспективного изображения на следующем изображении:
1. Для того чтобы найти контур на представленном изображении, необходимо избавиться от мелких деталей, которые могут мешать. Это можно сделать применив «заклинание размытия» по Гауссу малой мощности, предварительно сконвертировав изображение в оттенки серого:
Вот, что получилось в результате применения вышеописанной цепочки (если я сниму очки, будет примерно такой же эффект. Отсюда мораль: «Близорукость не недуг, а интеллектуальная обработка изображения, имеющая целью отсеять всё лишнее и сделать мир более прекрасным!»):
2. Далее необходимо сделать изображение черно-белым:
3. На полученном изображении легко найти контур документа. Будем искать максимальный внешний контур. В OpenCVSharp есть замечательный класс CvContourScanner, который может перечислять все найденные контуры изображения. С использованием Linq можно эти контуры отсортировать по площади и взять первый, который и будет самым максимальным.
Если нарисовать найденный контур, то получается следующее изображение:
4. Ура! Нашли контур! Однако, он мало что может показать – необходимо знать точно координаты всех угловых точек – точек пересечения сторон документа. Очевидно, что для нахождения координат этих точек желательно описать стороны найденного контура уравнениями прямой линии. Как же нам в этом может помочь OpenCV? Очень просто! В нем есть инструмент, использующий преобразование Хафа. «Кастуем» этот метод на изображение, полученное на предыдущем шаге:
Статья, безусловно, интересная и полезная. Мы, «с чувством глубокого удовлетворения» отметили, что 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();
Только не думайте, что эта волшебная строчка вернет Вам 4 линии, которые Вы бы ожидали получить, нет! Их будет 100, а может быть 200, а может вообще не быть. Дело в том, что данный метод ищет все участки, которые были приняты за линии, и удовлетворяющие входным параметрам (за разъяснениями приведенных параметров обращайтесь в «гримуар» по OpenCV). Тем не менее, с этими данными уже можно что-то делать, например, разложить их по кучкам: вертикальные отдельно, горизонтальные отдельно:
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(c))
.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, а результат вычислений применяется уже в момент сканирования.
Мы планируем и дальше делиться некоторыми хитростями обработки изображений на Хабре, если эта тема окажется востребованной. На нашем канале в youtube уже есть пара роликов, иллюстрирующих наши разработки, мы планируем и дальше вести летопись нашего развития в видео формате и в формате статей. Спасибо за внимание!
