Итак, одна из задач сводилась к распознаванию номеров на листе скана талонов. Стоит обратить внимание, что талонов может быть несколько, и располагаться на листе они могут как вертикально, так и горизонтально.
То, что мы увидели на сканах талонов, сильно напоминало штрих-код Codabar, с которым нам уже приходилось сталкиваться на других проектах.
Codabar – это линейный штрих-код. Каждый символ кодируется 7 элементами: 4 линиями и 3 пробелами между ними. Между собой символы разделяются дополнительным пространством. Начинается Codabar со стартового символа, и заканчивается стоповым. Стартовыми или стоповыми символами служат, как правило, символы ABCD. Информативными: 0-9, -, $.
Таким образом, для данного штрих-кода существует алфавит, где каждому символу соответствует определённая последовательность линий и пробелов.
На картине показан пример Codabar’a, содержащий значение «401».
ZXing
При работе со штрих-кодами в .NET мы используем портированную версию библиотеки Zxing. Библиотека умеет генерировать и распознавать всевозможные 1D и 2D баркоды: QR-Code, PDF 417, EAN, UPC, Aztec, Data Matrix. И главное, она умеет работать с Codabar. Применение библиотеки Zxing обычно не вызывает проблем, мы использовали ее на разных платформах. Но наш штрих-код Zxing сходу распознать не удалось. Всё оказалось не так просто… При внимательном изучении оказалось, что коды заказчика хоть и очень похожи на Codabar, но всё же отличаются, а именно:
- имеют другие стартовые и стоповые символы;
- каждый информативный символ состоит не из стандартных 7 элементов (4 линии и 3 пробела), а из 9 (5 линий, 4 пробела);
- стартовый и стоповый символы также состоят не из 7 элементов, а из 3 (2 линии, 1 пробел).
Возможно, этот формат тоже «стандартен», хотя мы не нашли его детального описания и информации о нём. Возможно, существуют реализации библиотек для автоматизации распознавания этого кода, но нам не посчастливилось их найти… В итоге, было решено попытаться продолжить работу с Zxing, и сделать следующее: взять исходники кода и изменить алгоритм распознавания под собственные нужды.
Алгоритм
В Zxing у каждого класса, реализующего логику распознавания конкретного кода (например, CodabarReader.cs), есть своя реализация абстрактного метода decodeRow, объявленного в классе OneDReader.cs.
override public List<Result> decodeRow(int rowNumber, BitArray row, Hashtable hints)
На вход подаётся номер строки изображения и собственно массив, содержащий значения пикселей строки (тёмный — светлый).
Далее при помощи метода setCounters(BitArray row) инициируется массив int[] counters по следующему алгоритму: начиная с темного пикселя первый элемент массива начинает инкрементироваться, пока в массиве row не встретится белый пиксель. После этого происходит переход ко второму элементу массива counters, и он тоже инкрементируется, пока не появится черный пиксель. И так до конца строки. В итоге массив counters будет иметь например следующий вид:
15 7 10 3 4 8 16…
т.е.: 15 чёрных пикселей, 7 белых, 10 чёрных, 3 белых и т.д. (первый элемент в данной реализации соответствует черным пикселям).
Далее ищем последовательность, соответствующую стартовому символу (в нашем случае это символ «А», в оригинальном Codabar – один из символов «A», «B», «C» или «D»). Ищем с помощью метода findStartPattern(out int charOffset, int globalOffset). Пока непоследовательность не найдена, увеличиваем значение globalOffset (определяет текущее положение в строке изображения) и переходим к следующему символу массива counters. В методе findStartPattern вызывается метод:
int toNarrowWidePattern(int position, int offset)
Он принимает номер текущего элемента массива counters и длину символа (3 – для стартового или стопового символа; 9 – для остальных символов). Возвращает -1 если символ не найден. Если символ найден – возвращает эту позицию в массиве CHARACTER_ENCODINGS.
Алфавит
Алфавит кода определяется следующими полями:
- char[] ALPHABET_STRING – содержит все символы, используемые в коде.
- int[] CHARACTER_ENCODINGS – содержит цифру, определяющую кодовую последовательность, характерную для каждого символа кода.
Немного слов о значениях, хранящихся в массиве CHARACTER_ENCODINGS и вообще о том, как кодируется Codabar. Например, цифра «0» кодируется следующей последовательностью полосок и пробелов:
Записывается это следующим образом: 101010011 (barcode encoding). Одиночный 0/1 кодирует короткий пробел/полосу, сдвоенный 00/11 кодирует длинный пробел/полосу. Далее эта последовательность преобразуется в код 0000011 (width encoding), или в шестнадцатеричном виде: 0х03. Т.е. одиночные символы записываются нулём, сдвоенные – единицей. В нашем случае каждый символ кодируется не 7, а 9 символами, но логика создания цифрового кода та же.
Нам пришлось потратить некоторое время на изучение примеров талонов. Мы внимательно вглядывались в штрих-коды и выписывали последовательности, которые соответствуют тому или иному символу. В результате получился наш собственный алфавит:
private const String ALPHABET_STRING = "0123456789AE";
static int[] CHARACTER_ENCODINGS = {
0x014, 0x101, 0x041, 0x140, 0x011, 0x110, 0x050, 0x005, 0x104, 0x044, // 0-9
0x000, 0x004, // AE};
Итак, процесс обработки кода выглядит следующим образом: как только находим стартовый символ – ищем информационные, используя всё тот же метод toNarrowWidePattern. Длина последовательности фиксированная, т.е. на определённом шаге нам надо проверить, не является ли символ стоповым. Если да – формируем результат и переходим к следующему элементу массива counters, продолжая поиск штрих-кодов в строке.
В итоге, просканировав строку, имеем (или не имеем) один и более кодов, которые сохраняем в глобальный массив результатов. И переходим к следующей строке изображения.
Также была добавлена возможность включать поворот изображения по часовой стрелке на 90 градусов, если необходимо проверить документ на наличие кодов во всех четырёх положениях. В библиотеке Zxing изображение, которое необходимо обработать, содержится в классе BinaryBitmap, который имеет метод rotateCounterClockwise(). Повернуть изображение не составляет труда.
Таким образом, немного подумав и потрудившись, мы смогли доработать библиотеку под новый формат кода. Кому интересно, код можно найти тут
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using BitArray = ETR.REBT.BarcodeReader.common.BitArray;
namespace ETR.REBT.BarcodeReader.oned
{
public sealed class MyCodeReader : OneDReader
{
// These values are critical for determining how permissive the decoding
// will be. All stripe sizes must be within the window these define, as
// compared to the average stripe size.
private static readonly int MAX_ACCEPTABLE = (int)(PATTERN_MATCH_RESULT_SCALE_FACTOR * 2.0f);
private static readonly int PADDING = (int)(PATTERN_MATCH_RESULT_SCALE_FACTOR * 1.5f);
private static readonly int STARTEND_LENGTH = 3;
private static readonly int SYMBOL_LENGTH = 9;
private static readonly int DATA_LENGTH = 15; // 15 symbols + 2 start/stop symbols
private static readonly int All_LENGHT = (16 + DATA_LENGTH * SYMBOL_LENGTH + 2 * STARTEND_LENGTH);
private const String ALPHABET_STRING = "0123456789AE";
internal static readonly char[] ALPHABET = ALPHABET_STRING.ToCharArray();
/**
* These represent the encodings of characters, as patterns of wide and narrow bars. The 7 least-significant bits of
* each int correspond to the pattern of wide and narrow, with 1s representing "wide" and 0s representing narrow.
*/
internal static int[] CHARACTER_ENCODINGS = {
0x014, 0x101, 0x041, 0x140, 0x011, 0x110, 0x050, 0x005, 0x104, 0x044, // 0-9
0x000, 0x004, // AE
};
// minimal number of characters that should be present (inclusing start and stop characters)
// under normal circumstances this should be set to 3, but can be set higher
// as a last-ditch attempt to reduce false positives.
private const int MIN_CHARACTER_LENGTH = 3;
// Start and end patterns
private static readonly char[] START_ENCODING = { 'A' };
private static readonly char[] END_ENCODING = { 'E' };
private static readonly char[] DATA_ENCODING = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
// some codabar generator allow the codabar string to be closed by every
// character. This will cause lots of false positives!
// some industries use a checksum standard but this is not part of the original codabar standard
// for more information see : http://ift.tt/1f59tyR
// Keep some instance variables to avoid reallocations
private readonly StringBuilder decodeRowResult;
private int[] counters;
private int counterLength;
public MyCodeReader()
{
decodeRowResult = new StringBuilder(40);
counters = new int[500];
counterLength = 0;
}
override public List<Result> decodeRow(int rowNumber, BitArray row, Hashtable hints)
{
List<Result> returnList = null;
if (!setCounters(row))
return null;
int globalOffset = 0;
while (globalOffset < counterLength)
{
int startSymbolPos = -1;
int startOffset = findStartPattern(out startSymbolPos, globalOffset);
if (startOffset < 0)
return returnList; // we can't find start char in the whole row -> so, exit
decodeRowResult.Length = 0;
decodeRowResult.Append((char)startSymbolPos);
int nextStart = startOffset;
nextStart += (STARTEND_LENGTH + 1/*space between symbols*/);
bool findNextStart = false;
do
{
int charOffset = toNarrowWidePattern(nextStart, SYMBOL_LENGTH);
if (charOffset == -1 || !arrayContains(DATA_ENCODING, ALPHABET[charOffset]))
{
findNextStart = true;
break;
}
decodeRowResult.Append((char)charOffset);
nextStart += (SYMBOL_LENGTH + 1);
// Stop as soon as length of data symbols equals to corresponding number
if (decodeRowResult.Length == DATA_LENGTH + 1/*start symbol*/)
{
int endOffset = toNarrowWidePattern(nextStart, STARTEND_LENGTH);
if (endOffset == -1 || !arrayContains(END_ENCODING, ALPHABET[endOffset]))
{
findNextStart = true;
break;
}
globalOffset = nextStart + STARTEND_LENGTH;
decodeRowResult.Append((char)endOffset);
break;
}
} while (nextStart < counterLength); // no fixed end pattern so keep on reading while data is available
if (findNextStart)
{
globalOffset = ++startOffset;
continue;
}
if (!validatePattern())
{
globalOffset = ++startOffset;
continue;
}
// remove stop/start characters character
decodeRowResult.Remove(decodeRowResult.Length - 1, 1);
decodeRowResult.Remove(0, 1);
int runningCount = 0;
for (int i = 0; i < startOffset; i++)
{
runningCount += counters[i];
}
float left = (float)runningCount;
for (int i = startOffset; i < nextStart - 1; i++)
{
runningCount += counters[i];
}
float right = (float)runningCount;
Result result = new Result(
decodeRowResult.ToString(),
null,
new ResultPoint[]
{
new ResultPoint(left, (float) rowNumber),
new ResultPoint(right, (float) rowNumber)
},
BarcodeFormat.CODABAR);
if (returnList == null)
returnList = new List<Result>();
returnList.Add(result);
}
return returnList;
}
private bool validatePattern()
{
if (decodeRowResult.Length != DATA_LENGTH + 2)
{
return false;
}
// Translate character table offsets to actual characters.
for (int i = 0; i < decodeRowResult.Length; i++)
{
decodeRowResult[i] = ALPHABET[decodeRowResult[i]];
}
// Ensure a valid start character
char startchar = decodeRowResult[0];
if (!arrayContains(START_ENCODING, startchar))
{
return false;
}
// Ensure a valid end character
char endchar = decodeRowResult[decodeRowResult.Length - 1];
if (!arrayContains(END_ENCODING, endchar))
{
return false;
}
// Ensure a valid data symbols
for (int i = 1; i < decodeRowResult.Length - 1; i++)
{
if (!arrayContains(DATA_ENCODING, decodeRowResult[i]))
{
return false;
}
}
return true;
}
/// <summary>
/// Records the size of all runs of white and black pixels, starting with white.
/// This is just like recordPattern, except it records all the counters, and
/// uses our builtin "counters" member for storage.
/// </summary>
/// <param name="row">row to count from</param>
private bool setCounters(BitArray row)
{
counterLength = 0;
// Start from the first white bit.
int i = row.getNextUnset(0);
int end = row.Size;
if (i >= end)
{
return false;
}
bool isWhite = true;
int count = 0;
for (; i < end; i++)
{
if (row[i] ^ isWhite)
{
// that is, exactly one is true
count++;
}
else
{
counterAppend(count);
count = 1;
isWhite = !isWhite;
}
}
counterAppend(count);
return true;
}
private void counterAppend(int e)
{
counters[counterLength] = e;
counterLength++;
if (counterLength >= counters.Length)
{
int[] temp = new int[counterLength * 2];
Array.Copy(counters, 0, temp, 0, counterLength);
counters = temp;
}
}
private int findStartPattern(out int charOffset, int globalOffset)
{
charOffset = -1;
//
// Assume that first (i = 0) set of pixels is white,
// so we start find symbols from second set (i = 1).
// And next we step over white set ('i += 2').
//
for (int i = 1 + globalOffset; i < counterLength; i += 2)
{
if (counters[i - 1] < counters[i] * 5) // before start char must be a long space
continue;
charOffset = toNarrowWidePattern(i, 3);
if (charOffset != -1 && arrayContains(START_ENCODING, ALPHABET[charOffset]))
{
return i;
}
}
return -1;
}
internal static bool arrayContains(char[] array, char key)
{
if (array != null)
{
foreach (char c in array)
{
if (c == key)
{
return true;
}
}
}
return false;
}
// Assumes that counters[position] is a bar.
private int toNarrowWidePattern(int position, int offset)
{
int end = position + offset;
if (end >= counterLength)
return -1;
// First element is for bars, second is for spaces.
int[] maxes = { 0, 0 };
int[] mins = { Int32.MaxValue, Int32.MaxValue };
int[] thresholds = { 0, 0 };
for (int i = 0; i < 2; i++)
{
for (int j = position + i; j < end; j += 2)
{
if (counters[j] < mins[i])
{
mins[i] = counters[j];
}
if (counters[j] > maxes[i])
{
maxes[i] = counters[j];
}
}
double tr = ((double)mins[i] + (double)maxes[i]) / 2;
thresholds[i] = (int)Math.Ceiling(tr);
}
// There are no big spaces in the barcode -> only small spaces
thresholds[1] = Int32.MaxValue;
// For start and end symbols defined empirically threshold equals to 5
if (offset == STARTEND_LENGTH)
thresholds[0] = 5;
int bitmask = 1 << offset;
int pattern = 0;
for (int i = 0; i < offset; i++)
{
int barOrSpace = i & 1;
bitmask >>= 1;
if (counters[position + i] >= thresholds[barOrSpace])
{
pattern |= bitmask;
}
}
for (int i = 0; i < CHARACTER_ENCODINGS.Length; i++)
{
if (CHARACTER_ENCODINGS[i] == pattern)
{
return i;
}
}
return -1;
}
}
}
«Оптимизация» Zxing
Итак, у нас получилось распознавать один или несколько кодов на странице. Но на этом наши проблемы не закончились. Так как по условиям у нас может быть несколько кодов плюс необходимо сканировать 4 различных положения листа, алгоритм стал существенно «тормозить». Пришлось покопаться ещё, в результате чего обнаружилась следующая особенность:
Zxing на основании изображения создаёт экземпляр класса RGBLuminanceSource. В нём имеется массив байт, содержащий информацию о яркости каждого пиксела исходного изображения. Затем, на основании этой информации и порогового значения получается битовый массив.
Вот пример части кода конструктора класса RGBLuminanceSource:
Color c;
for (int y = 0; y < height; y++)
{
int offset = y * width;
for (int x = 0; x < width; x++)
{
c = bitmap.GetPixel(x, y);
var r = ColorUtility.GetRValue(c);
var g = ColorUtility.GetGValue(c);
var b = ColorUtility.GetBValue(c);
luminances[offset + x] = (byte)(0.3 * r + 0.59 * g + 0.11 * b + 0.01);
}
}
То есть в циклах используется медленная bitmap.GetPixel(x, y) для каждого пикселя изображения! Для небольших изображений с разрешением 200х300 пикселей (или близких к тому) такой подход вполне уместен и не вызывает задержек (учитывая, что распознаётся как правило только один код). Но в нашем случае изображение имеет высокое разрешение (до 3000 х 5000 пикселей), что еще и следует умножить на количество вариантов ориентации, и умножить на обработку множества страниц. Все это приводит к неприемлемым задержкам. Например, для одной страницы вышеуказанного разрешения объект класса RGBLuminanceSource создавался секунд за 8. Это, конечно, очень долго.
Пришлось дополнительно модифицировать этот код, забыть про GetPixel и перейти на работу по сканлиниям.
bmp = bitmap.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.ReadOnly, bitmap.PixelFormat);
for (var y = 0; y < bmp.Height; y++)
{
var row = (byte*)bmp.Scan0 + (y * bmp.Stride);
int offset = y * width;
for (var x = 0; x < bmp.Width; x++)
{
var b = row[(x * pixelSize)];
var g = row[(x * pixelSize) + 1];
var r = row[(x * pixelSize) + 2];
luminances[offset + x] = (byte)(0.3 * r + 0.59 * g + 0.11 * b + 0.01);
}
}
Этот шаг значительно ускорил алгоритм и позволил получить приемлемое время обработки.
Работа с PDF
Как уже было сказано выше, сканы купонов могут поступать как в виде файлов изображений, так и в PDF документе. Для превращения страниц pdf в изображения мы воспользовались библиотекой itextsharp.
Основной класс для работы с этой библиотекой — PdfReader. Экземпляр данного класса можно получить, например, следующим образом:
Кусочки кода ищите под спойлером.
var reader = new PdfReader(filePath)
После этого можно использовать его в коде:
for (var pageNumber = 1; pageNumber <= reader.NumberOfPages; pageNumber++)
{
var page = reader.GetPageN(pageNumber);
List<ImageRenderInfo> images;
try
{
images = FindImageInPDFDictionary(page);
}
catch (Exception)
{
// Переходим к следующей странице PDF документа
continue;
}
finally
{
reader.ReleasePage(pageNumber);
}
foreach (var img in images)
{
var image = RenderImage(img);
var result = ImageDecoder.Decode(image, allRotations);
if (result != null && result.Count > 0)
{
// Страница распозналась, можно использовать результат сканирования
}
}
}
С помощью этой функции ищем изображения на странице PDF документа
private static List<ImageRenderInfo> FindImageInPDFDictionary(PdfDictionary pg)
{
var result = new List<ImageRenderInfo>();
var res = (PdfDictionary)PdfReader.GetPdfObject(pg.Get(PdfName.RESOURCES));
var xobj = (PdfDictionary)PdfReader.GetPdfObject(res.Get(PdfName.XOBJECT));
if (xobj == null) return null;
foreach (var name in xobj.Keys)
{
var obj = xobj.Get(name);
if (!obj.IsIndirect()) continue;
var tg = (PdfDictionary)PdfReader.GetPdfObject(obj);
var type = (PdfName)PdfReader.GetPdfObject(tg.Get(PdfName.SUBTYPE));
if (PdfName.IMAGE.Equals(type))
{
var width = float.Parse(tg.Get(PdfName.WIDTH).ToString());
var height = float.Parse(tg.Get(PdfName.HEIGHT).ToString());
if (width > ImageDecoder.MinimalSideResolution || height >= ImageDecoder.MinimalSideResolution)
{
var imgRi = ImageRenderInfo.CreateForXObject(new Matrix(width, height), (PRIndirectReference)obj, tg);
result.Add(imgRi);
}
}
if (PdfName.FORM.Equals(type))
{
result.AddRange(FindImageInPDFDictionary(tg));
}
if (PdfName.GROUP.Equals(type))
{
result.AddRange(FindImageInPDFDictionary(tg));
}
}
return result;
}
Получаем объект типа Bitmap из объекта класса ImageRenderInfo
private static Bitmap RenderImage(ImageRenderInfo renderInfo)
{
try
{
var image = renderInfo.GetImage();
using (var dotnetImg = image.GetDrawingImage())
{
if (dotnetImg != null)
{
using (var ms = new MemoryStream())
{
dotnetImg.Save(ms, ImageFormat.Png);
return new Bitmap(dotnetImg);
}
}
}
}
catch (Exception)
{
}
return null;
}
В методе ImageDecoder.Decode реализуется логика нахождения кода в картинке.
Так получилось, что сейчас в мире существует множество разновидностей баркодов. Распознавание и генерация большинства из них реализована в библиотеках, доступных для разработчиков. Тем не менее, иногда можно наткнуться на оригинальный тип баркода, распознать который сходу не получится.
И тогда метод тщательного всматривания и использования хорошо спроектированной библиотеки с открытым исходным кодом помогает быстро получить результат.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий