[ScanDoc] передобробка сканів



Є думка, що система електронного документообігу повністю позбавляє від роботи з паперами, але це не так. Для оцифровки паперових примірників документів їх зазвичай пропускають через сканер. Коли потік документів та вимоги до якості сканів перевищують певний поріг виникає ряд питань, які необхідно вирішувати програмно.

Які проблеми доводиться вирішувати:
  • Коректувати кут нахилу зображення, т. к. фідер сканера неминуче нахиляє документ при протяганні. Неохайність у важливих документах неприпустима.
  • Виділяти корисну частину на скані, решта — видаляти, так як це не інформативно і займає дисковий простір даремно.
  • Знаходити і видаляти порожні сторінки, які обов'язково будуть при дуплекс-сканування.

Алгоритми, які вирішують поставлені завдання розроблені і ймовірно навіть викладені в інтернеті, але знайти їх виразне опис не вдалося. Звичайно, ці проблеми вирішують дорогі професійні сканери, але використовувати вбудоване не завжди можливо.
Ідея статті народилася як раз в процесі розробки інструменту для вирішення цих проблем. Сподіваюся, вона доповнить доступну інформацію з оцифрування документів і виявиться корисною розробникам, які займаються схожою завданням.

Розглянемо три скана документів, які ми отримали за допомогою старого-доброго сканера Futjitsu fi-6140.
  1. Скан бланка анкети на отримання карти Тінькофф банку;
  2. Скан ксерокопії паспорта;
  3. Скан поштового конверта.




Корекція нахилу
Після отримання скану документа, потрібно привести його до строго вертикальному або горизонтальному увазі. Мається на увазі, що на вхід можуть бути подані довільні документи без будь-яких позначок, за якими можна скорегувати нахил. Тому прив'яжемось до горизонтальним і вертикальним складовими документа: рядки, лінії таблиць, штрих-коди і навіть місця згину.
Першим ділом усуваємо надмірність зображення, тобто виділяємо контур. Для цього застосовуємо детектор кордонів.
Ми вибрали детектор кордонів Канни —оскільки він дає найбільш якісний результат.



Тепреь на зображенні слід знайти прямі лінії. Для цього застосовуємо популярне рішення використовується в комп'ютерному зорі — перетворення Хафа. Я не буду детально розписувати його принцип, його можна знайти в інтернеті. Суть перетворення полягає в перереборе всіх можливих варіантів ліній на зображенні та обчислення для них відгуку. Чим більше відгук, тим вираженіша лінія. В результаті перетворення буде побудована фазова площина, де Y взято кут нахилу, X — відстань до лінії.



На візуалізації фазової площини кожному пікселю відповідає унікальна лінія. Координати будемо обчислювати за найбільш вираженим лініях.

Візьмемо 5 найбільш інтенсивних ліній, для наочності покажемо їх на контурі вихідного зображення:



Видно, що уголы нахилу ліній відповідають нахилу осей координат документа.

Щоб отримати кут на який потрібно повернути зображення обчислюємо кут відхилення ліній від глобальних осей координат(від 0 до 90 градусів), усредняем значення і отримуємо кут нахилу зображення. Повертаємо зображення на отриманий кут зі знаком мінус. Тепер з цим зображенням можна працювати далі.

! Кут нахилу деяких ліній буде сильно відрізнятися від інших, тобто вони далеко не паралельні. Такі лінії краще виключити з обчислень, щоб вони не псували результат.



Для роботи з графікою ми скористалися чудовою бібліотекою aforgenet. В ній вже є реалізація описаного вище алгоритму пошуку кута нахилу документа. В результаті всього 15 рядків коду і корекція налона готова.

! Функція GetAverageBorderColor повертає середній колір периметра вихідного зображення. Її можна замінити константою або інший більш просунутою функцією.
public static Bitmap DocumentAngleCorrection(Bitmap image) {
var grayImage = Grayscale.CommonAlgorithms.RMY.Apply(image);
var skewChecker = new DocumentSkewChecker();

var angle = skewChecker.GetSkewAngle(grayImage);

while (angle >= 90) {
angle -= 90;
}

while (angle <= -90) {
angle += 90;
}

var rotator = new RotateBilinear(-angle, false);
rotator.FillColor = GetAverageBorderColor(image);
image = rotator.Apply(image);

return image;
}


Кадрування
Ми выровнили зображення. Тепер потрібно обрізати його інформативну частину. На цьому етапі важливо врахувати деякі особливості.

Алгоритм повинен справно працювати:
  • за будь-колір тексту і фону;
  • зі сканами будь-якої якості;
  • з документами будь-якого типу.
За основу алгоритму ми взяли припущення: в інформативної області зображення буде багато перепадів яскравості, в порожній — мало. Тому рішення задачі зводиться до трьох дій:
  1. Розбиваємо зображення на фрагменти, підраховуємо кількість перепадів яскравості по вертикалі і горизонталі для кожного фрагмента.
  2. Шукаємо фрагменти з великою кількістю перепадів яскравості.
  3. Вирізаємо інформативну область.
Для швидкого доступу до пікселям зображення, краще працювати з масивом байтів. Його можна отримати так:
var bitmapData = sourceBitmap.LockBits(new Rectangle(0, 0, sourceBitmap.Width, sourceBitmap.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

var bytes = bitmapData.Stride * sourceBitmap.Height;
var sourceBytes = new byte[bytes];

System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, sourceBytes, 0, bytes);

Алгоритм виглядає так:
const int sensitivity = 25;
const int widthQuantum = 100;

var regionSize = bitmapData.Width / widthQuantum;


for (var y = 0; y < bitmapData.Height + regionSize; y += regionSize) { // x processing
for (var x = 0; x < bitmapData.Width + regionSize; x += regionSize) { // y processing
var value = 0;

for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) { // Horosontal counting
var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, x, yy);

for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) {
var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

if (Math.Abs(pixel - nextPixel) > sensitivity) {
value++;
}

pixel = nextPixel;
}
}

for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) { // Vertical counting
var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, y);

for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) {
var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

if (Math.Abs(pixel - nextPixel) > sensitivity) {
value++;
}

pixel = nextPixel;
}
}

// value TODO
}
}


Змінна value в позначеному місці буде утримувати кількість перепадів яскравості по вертикалі і горизонталі в оброблюваному фрагменті. Це значення і координати фрагмента можна, наприклад, зберегти у списку.

! Функція GetGrayPixel повертає середнє значення яскравості пікселя.
private static byte GetGrayPixel(byte[] src, int w, int x, int y) {
var s = GetShift(w, x, y);

if ((s + 3 > src.Length) || (s < 0)) {
return 127;
}

int b = src[s++];
b += src[s++];
b += src[s];
b = (int)(b / 3.0);
return (byte)b;
}


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



! Для економії ресурсів краще працювати зі зменшеною копією зображення. Потім масштабувати результат і застосовувати до вихідній картинці.



Дивимося результат. Алгоритм спрацював коректно — не залишив і не зрізав нічого зайвого.



Такий результат ми отримали в більшості випадків.

Видалення порожніх сторінок
Вийшло так, що завдання видалення порожніх сторінок документів з'явилася вже після того, як ми розробили алгоритм виділення інформативної частини документа. Тому для видалення порожніх сторінок ми використовували той же алгоритм, тільки трохи видозмінили його. Замість побудови карти перепадів яскравості зображення, ми підраховували кількість фрагментів з великим і малим перепадом яскравості. Якщо високочастотних блоків багато, зображення містить цінну інформацію і не є порожнім.
Здавалося б щоб скоротити час обробки можна видаляти зайві сторінки і кадрувати зображення за один підхід, тобто один проходити циклом тільки один раз. Але очевидно, що кадрувати зображення можна тільки після вирівнювання. При цьому довелося б повертати карту перепадів. Тому, щоб не ускладнювати собі життя, ми визначили такий порядок дій:
видалення порожніх сторінок --> корекція нахилу --> кадрування
Ми отримали один зайвий прохід по пікселях для підрахунку частоти. Але це не є проблемою в наш час завдяки закону Гордона Мура.

! Повний сирок
public static Bitmap DocumentAngleCorrection(Bitmap image) {
var grayImage = Grayscale.CommonAlgorithms.RMY.Apply(image);
var skewChecker = new DocumentSkewChecker();

var angle = skewChecker.GetSkewAngle(grayImage);

while (angle >= 90) {
angle -= 90;
}

while (angle <= -90) {
angle += 90;
}

var rotator = new RotateBilinear(-angle, false);
rotator.FillColor = GetAverageBorderColor(image);
image = rotator.Apply(image);

return image;
}

private static Color GetAverageBorderColor(Bitmap bitmap) {
var widthProcImage = (double)200;

var sourceImage = bitmap;
var sizeFactor = widthProcImage / sourceImage.Width;
var procBtmp = new Bitmap(sourceImage, (int)Math.Round(sourceImage.Width * sizeFactor), (int)Math.Round(sourceImage.Height * sizeFactor));
var bitmapData = procBtmp.LockBits(new Rectangle(0, 0, procBtmp.Width, procBtmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

var bytes = Math.Abs(bitmapData.Stride) * procBtmp.Height;
var sourceBytes = new byte[bytes];
System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, sourceBytes, 0, bytes);

var channels = new Dictionary<char, int>();
channels.Add('r', 0);
channels.Add('g', 0);
channels.Add('b', 0);

var cnt = 0;

for (var y = 0; y < bitmapData.Height; y++) { // vertical
var c = GetColorPixel(sourceBytes, bitmapData.Width, 0, y);
channels['r'] += c.R;
channels['g'] += c.G;
channels['b'] += c.B;
cnt++;

c = GetColorPixel(sourceBytes, bitmapData.Width, bitmapData.Width - 1, y);
channels['r'] += c.R;
channels['g'] += c.G;
channels['b'] += c.B;
cnt++;
}

for (var x = 0; x < bitmapData.Width; x++) { // horisontal
var c = GetColorPixel(sourceBytes, bitmapData.Width, x, 0);
channels['r'] += c.R;
channels['g'] += c.G;
channels['b'] += c.B;
cnt++;

c = GetColorPixel(sourceBytes, bitmapData.Width, x, bitmapData.Height - 1);
channels['r'] += c.R;
channels['g'] += c.G;
channels['b'] += c.B;
cnt++;
}

procBtmp.UnlockBits(bitmapData);

var r = (int)Math.Round(((double)channels['r']) / cnt);
var g = (int)Math.Round(((double)channels['g']) / cnt);
var b = (int)Math.Round(((double)channels['b']) / cnt);

var color = Color.FromArgb(r > 255 ? 255 : r, g > 255 ? 255 : g, b > 255 ? 255 : b);

return color;
}

private static byte GetGrayPixel(byte[] src, int w, int x, int y) {
var s = GetShift(w, x, y);

if ((s + 3 > src.Length) || (s < 0)) {
return 127;
}

int b = src[s++];
b += src[s++];
b += src[s];
b = (int)(b / 3.0);
return (byte)b;
}

private static Color GetColorPixel(byte[] src, int w, int x, int y) {
var s = GetShift(w, x, y);

if ((s + 3 > src.Length) || (s < 0)) {
return Color.Gray;
}

byte r = src[s++];
byte b = src[s++];
byte g = src[s];

var c = Color.FromArgb(r, g, b);

return c;
}
private static int GetShift(int width, int x, int y) {
return y * width * 3 + x * 3;
}

public static bool DocumentDetectInfo(Bitmap image) {
const double widthProcImage = 200;
const int sens = 15;
const int treshold = 25;
const int widthQuantum = 10;


var sourceImage = image;
var sizeFactor = widthProcImage / sourceImage.Width;
var procBtmp = new Bitmap(sourceImage, (int)Math.Round(sourceImage.Width * sizeFactor), (int)Math.Round(sourceImage.Height * sizeFactor));
var bd = procBtmp.LockBits(new Rectangle(0, 0, procBtmp.Width, procBtmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
var bytes = Math.Abs(bd.Stride) * procBtmp.Height;
var source = new byte[bytes];

System.Runtime.InteropServices.Marshal.Copy(bd.Scan0, source, 0, bytes);

var maxV = 0;

var size = bd.Width / widthQuantum;

var hight = 0;
var low = 0;

for (var y = 0; y < bd.Height + size; y += size) { // x processing
for (var x = 0; x < bd.Width + size; x += size) { // y processing
var value = 0;

for (var yy = y; (yy < y + size) && (yy < bd.Height); yy++) { // Horosontal counting
var pixel = GetGrayPixel(source, bd.Width, x, yy);

for (var xx = x; (xx < x + size) && (xx < bd.Width); xx++) {
var point = GetGrayPixel(source, bd.Width, xx, yy);

if (Math.Abs(pixel - point) > sens) {
value++;
}

pixel = point;
}
}

for (var xx = x; (xx < x + size) && (xx < bd.Width); xx++) { // Vertical counting
var pixel = GetGrayPixel(source, bd.Width, xx, y);

for (var yy = y; (yy < y + size) && (yy < bd.Height); yy++) {
var point = GetGrayPixel(source, bd.Width, xx, yy);

if (Math.Abs(pixel - point) > sens) {
value++;
}

pixel = point;
}
}

maxV = Math.Max(maxV, value);

if (value > treshold) {
hight++;
} else {
low++;
}
}
}

double cnt = hight + low;
hight = (int)Math.Round(hight / cnt * 100);

procBtmp.UnlockBits(bd);

return (hight > treshold);
}

public static Bitmap DocumentCropInfo(Bitmap image) {
const double widthProcImage = 1000;
const int sensitivity = 25;
const int treshold = 50;
const int widthQuantum = 100;


var sourceImage = image;
var sizeFactor = widthProcImage / sourceImage.Width;
var procBtmp = new Bitmap(sourceImage, (int)Math.Round(sourceImage.Width * sizeFactor), (int)Math.Round(sourceImage.Height * sizeFactor));
var bitmapData = procBtmp.LockBits(new Rectangle(0, 0, procBtmp.Width, procBtmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
var bytes = Math.Abs(bitmapData.Stride) * procBtmp.Height;
var sourceBytes = new byte[bytes];

System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, sourceBytes, 0, bytes);

var x1 = procBtmp.Width;
var y1 = procBtmp.Height;
var x2 = 0;
var y2 = 0;
var maxV = 0;

var pointList = new List<Point>();
var regionSize = bitmapData.Width / widthQuantum;

for (var y = 0; y < bitmapData.Height + regionSize; y += regionSize) { // x processing
for (var x = 0; x < bitmapData.Width + regionSize; x += regionSize) { // y processing
var value = 0;

for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) { // Horosontal counting
var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, x, yy);

for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) {
var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

if (Math.Abs(pixel - nextPixel) > sensitivity) {
value++;
}

pixel = nextPixel;
}
}

for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) { // Vertical counting
var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, y);

for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) {
var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

if (Math.Abs(pixel - nextPixel) > sensitivity) {
value++;
}

pixel = nextPixel;
}
}

pointList.Add(new Point() { V = value, X = x, Y = y });
maxV = Math.Max(maxV, value);
}
}

var vFactor = 255.0 / maxV;

foreach (var point in pointList){
var v = (byte)(point.V * vFactor);

if (v > treshold) {
x1 = Math.Min(x1, point.X);
y1 = Math.Min(y1, point.Y);

x2 = Math.Max(x2, point.X + regionSize);
y2 = Math.Max(y2, point.Y + regionSize);
}
}

procBtmp.UnlockBits(bitmapData);

x1 = (int)Math.Round((x1 - regionSize) / sizeFactor);
x2 = (int)Math.Round((x2 + regionSize) / sizeFactor);
y1 = (int)Math.Round((y1 - regionSize) / sizeFactor);
y2 = (int)Math.Round((y2 + regionSize) / sizeFactor);

var bigRect = new Rectangle(x1, y1, x2 - x1, y2 - y1);
var clippedImg = CropImage(sourceImage, bigRect);

return clippedImg;
}
public static Bitmap CropImage(Bitmap source, Rectangle section) {
section.X = Math.Max(0, section.X);
section.Y = Math.Max(0, section.Y);
section.Width = Math.Min(source.Width, section.Width);
section.Height = Math.Min(source.Height, section.Height);

var bmp = new Bitmap(section.Width, section.Height);

var g = Graphics.FromImage(bmp);

g.DrawImage(source, 0, 0, section, GraphicsUnit.Pixel);

return bmp;
}

private class Point {
public int X;
public int Y;
public int V;
}



Висновок
Алгоритми відмінно справляються зі своїм завданням і донині. Цілком імовірно, що це не найбільш ефективне рішення. Тому запрошуємо всіх бажаючих в коментарі, щоб обговорити інші можливі алгоритми і підходи для вирішення конкретного завдання.

До швидких зустрічей!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.