Автоматическое выравнивание сканов документов

Запись от Storm23 размещена 01.11.2015 в 19:54

Показов 32369 Комментарии 12

Метки .net, c#

Автоматическое выравнивание сканов документов

Часто отсканированные или сфотографированные документы имеют перекос:

Нажмите на изображение для увеличения
Название: Exhibit-C-WF-00.jpg
Просмотров: 1304
Размер: 14.5 Кб
ID: 3416

От этого перекоса хотелось бы избавиться. Причем сделать это простым и максимально быстрым способом, без использования тяжелых библиотек типа OpenCV или AForge.NET.

Идея алгоритма

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

Нажмите на изображение для увеличения
Название: 1.png
Просмотров: 1198
Размер: 56.4 Кб
ID: 3417

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

Нажмите на изображение для увеличения
Название: 2.png
Просмотров: 1200
Размер: 15.7 Кб
ID: 3418

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

Нужный сдвиг можно найти если сдвигать одну из полосок на 1, 2, 3 и т.д. пикселов по вертикали, и считать коэффициент корреляции между полосками. Где корреляция достигнет максимального значения – такой сдвиг и является оптимальным.

Реализация

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

Для того что бы сделать это быстро, сделаем хитрость – используем встроенный в GDI+ механизм. Создадим новый битмап, высота которого будет равна высоте исходного изображения, а ширина – равна 2 пикселам.

Затем отрисуем исходное изображение на новом битмапе, сжимая изображение по горизонтали до 2 пикселов:

C#
1
2
3
4
5
6
7
8
            using (var bmp = new Bitmap(2, sourceImage.Height))
            using (var gr = Graphics.FromImage(bmp))
            {
                gr.InterpolationMode = InterpolationMode.Low;
                gr.DrawImage(sourceImage, 0, 0, 2, sourceImage.Height);
 
                ...
            }

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

Поскольку качество интерполяции нам не важно, выбираем максимально быстрый режим интерполяции - InterpolationMode.Low.

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

Далее, нужно перенести яркость найденных пикселов в массив int[] для каждой полоски. Для этого нужно использовать метод Bitmap.LockBits для быстрого доступа к пикселам. Яркость пиксела можно вычислить методом Color.GetBrightness(), но я использовал более быстрый аналог – просто брал зеленый канал цвета Color.G в качестве яркости.

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

C#
1
2
3
            var sum = 0;
            for (int i = 0; i < strip1.Length - shift; i++)
                sum += - Math.Abs(strip1[i] - strip2[i + shift]);

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

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

C#
1
            var dx = sourceImage.Width / stripCount;

А по вертикали – найденный сдвиг shift.

Теперь найдем угол поворота по формуле

C#
1
            var angle = Math.Atan2(shift, dx);

Наконец, вращаем исходное изображение на найденный угол:

C#
1
2
3
4
5
6
7
8
            var rotated = new Bitmap(sourceImage.Width, sourceImage.Height);
            using (var gr = Graphics.FromImage(rotated))
            {
                gr.InterpolationMode = InterpolationMode.HighQualityBicubic;
                gr.TranslateTransform(sourceImage.Width / 2, sourceImage.Height / 2);
                gr.RotateTransform(-(float)angle);
                gr.DrawImage(sourceImage, -sourceImage.Width / 2, -sourceImage.Height / 2, sourceImage.Width, sourceImage.Height);
            }

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

Сохраняем изображение в файл. Радуемся результату.

Замечания

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

Изображение делится не на 2 полоски, а на 10 полосок. Чем уже полоска, тем точнее можно вычислить сдвиг.
Сравнивается несколько пар полосок, для нахождения наиболее точного результата, а также для того что бы обойти неудачные случаи, когда полоска попадает в пустую область документа.
Сдвиг ищется как вверх так и вниз. Учитывается также то, что при сдвиге возможен выход за пределы изображения.
Что бы сделать расчеты быстрее, при расчете полосок, исходное изображение сжимается до 600 пикселов по вертикали.
Наиболее длительная операция – поворот исходного изображения на найденный угол. Для того, что бы сделать это быстрее – можно либо уменьшить размеры исходного изображения, либо снизить качество интерполяции.
Данный алгоритм не предназначен для коррекции трапецеидальных искажений (искажений перспективы, например).

Примеры работы алгоритма

Нажмите на изображение для увеличения
Название: ex3.png
Просмотров: 1513
Размер: 634.9 Кб
ID: 3421

Нажмите на изображение для увеличения
Название: ex1.png
Просмотров: 1026
Размер: 153.9 Кб
ID: 3419

Нажмите на изображение для увеличения
Название: ex2.png
Просмотров: 1188
Размер: 174.2 Кб
ID: 3420

Исходные коды и тестовое приложение: SkewCorrection.zip
Код распространяется под лицензией GPL3.

Метки .net, c#

Размещено в Без категории

« HowTo: Как сделать Undo, Redo Главная страница Простая тайловая игра (WinForms, GDI+) »

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 12

Комментарии

	Скажите, почему выбран именно такой вариант? Ведь гораздо легче и точнее определить границы и повернуть прямоугольник относительно центра на нужный угол.
	Запись от HighPredator размещена 02.11.2015 в 16:47

	Интересный алгоритм. HighPredator, а как можно определить угол поворота прямоугольника? (бегло погуглил, но ничего не нашел)
	Запись от castaway размещена 02.11.2015 в 17:01

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

Запись от HighPredator размещена 02.11.2015 в 17:40 HighPredator вне форума

Сообщение от HighPredator

Вы наверно говорите про метод описанный на хабре, здесь http://habrahabr.ru/post/223507/
Так как же найти этот самый прямоугольник? Если бы он был, то все можно было бы сделать по другому. Только вот его нет на сканах. Если вы отсканите чек, то он будет белым прямоугольником на белом фоне. То есть его не будет видно. Вот пример реального скана чека: https://www.dropbox.com/s/tobv... 1.jpg?dl=0
Нет там прямоугольника.

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

А вообще описанный мною алгоритм - лишь один из многих. Просто он самый простой и быстрый. И кроме того достаточно точный. Этим он мне нравится. Кроме него еще я знаю несколько методов: ваш метод прямоугольника, метод преобразований Хафа, метод БПФ.

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

А разве это легче? Для этого нужно найти границы листа (при чем будут мешаться еще линии на самом документе), а потом еще как-то искать прямоугольник. Это не просто. Кроме того, для этого полюбому вам нужно бегать по пикселам, а в моем методе - пикселы не перебираются вообще, если вы прочитали про реализацию. Поэтому моя реализация самая быстрая так точно.

Запись от Storm23 размещена 02.11.2015 в 19:13 Storm23 вне форума

	Интересный проект. И решение тоже. Захожу иногда в "этот" магазин. (=имя сетевых магазинов. Джинсы Levi's покупал там на подарки домой, на распродаже.)
	Запись от politov01 размещена 03.11.2015 в 00:48

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

Или вот нечто более реальное. Вот вы утверждаете:

А что если срока состоит из слешей или бэкслешей например? Это символы сами по себе "перекошенные". Вот вам уже естественный псевдо-перекос строки.

Запись от HighPredator размещена 03.11.2015 в 10:39 HighPredator вне форума

	HighPredator, точно. Как то сам с ходу и не сообразил...
	Запись от castaway размещена 03.11.2015 в 11:05

	castaway, кстати прошу прощения, я вас с автором слегка попутал.. Вопросы ему адресованы.
	Запись от HighPredator размещена 03.11.2015 в 11:22

Так, давайте по порядку

Сообщение от HighPredator

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

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

Сообщение от HighPredator

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

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

Сообщение от HighPredator

Ну и совсем упоротый пример: что если на скане присутствует изображение чего-то близкого к белому шуму в ргб-палитре допустим круглой формы?

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

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

Но никто и не ожидает 100% робастности.
Если посмотреть на альтернативные алгоритмы, то они работают ничуть не лучше. Например, метод преобразований Хафа по сути делает то же самое что и данный алгоритм, но при этом имеет большую погрешность, из-за того, что строка символов у него будет представлена множеством линий с разным наклоном.
Метод БПФ - более точен, но имеет такой же недостаток - как и Хафа. Если ему подсунуть одну строку с большим шрифтом, он скорее всего не сможет ее выровнять.
В общем я не вижу причин по которой какой-то из перечисленных алгоритмов работал бы лучше, чем данный. По крайней мере по быстродействию - так точно.

Что бы не быть голословным, вот для интереса подсунул ему изображения с разными шрифтами, с картинками:
https://www.dropbox.com/s/49ka... 1.png?dl=0
https://www.dropbox.com/s/3j5k... 5.png?dl=0
https://www.dropbox.com/s/bbmy... 4.png?dl=0

А здесь вот сильно зашумленное изображение:
https://www.dropbox.com/s/8c4g... 8.png?dl=0

Все точно работает.

Сообщение от HighPredator

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

Сообщение от HighPredator

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

Теперь по сути. Ну какое доказательство вы ожидаете?

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

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

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

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

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

Запись от Storm23 размещена 03.11.2015 в 12:33 Storm23 вне форума

Вот, отметил границу: http://tinyurl.com/o4gk3nv

Спасибо за комментарии и иллюстрации. Собственного этого в статье и не хватало.

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

Вот! Вот это и стоило в самом начале написать

Я-то понял откуда взялись пресловутые "полоски", но не всем читателям это может быть так очевидно

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

Запись от HighPredator размещена 03.11.2015 в 13:57 HighPredator вне форума

Сообщение от HighPredator

Спасибо за комментарии и иллюстрации.

Пожалуйста

Запись от Storm23 размещена 03.11.2015 в 17:39 Storm23 вне форума

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

К сожалению всё-таки страдает, хоть и при единственном повороте и не видно будет, но если изображение вращать несколько раз, то даже используя InterpolationMode.HighQualityBicubic, четкость теряется.

Запись от _Radik_ размещена 08.08.2017 в 12:16 _Radik_ вне форума

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

Сообщение форума

Отменить изменения