Статьи Погружение в матрицу: анализ структуры и методы распознавания QR-кода

Discussion in 'Статьи' started by c0n Difesa, 4 Jan 2011.

  1. c0n Difesa

    c0n Difesa Member

    Joined:
    1 Jan 2009
    Messages:
    133
    Likes Received:
    66
    Reputations:
    18
    [​IMG]

    В современном мире информация может представляться в самых причудливых формах. Причины на это могут быть разные и не всегда имеют стеганографическую подоплеку. У «человека разумного» буквально появился «третий глаз»: мобильный телефон стал неотъемлемым атрибутом каждого из нас. А что именно с его помощью мы попытаемся разглядеть, ты узнаешь из этой статьи.

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

    Однако прогресс не стоит на месте и в скором времени того объема информации, который способны перенести в себе линейные кодировки (до 30 цифровых символов), стало не хватать производителям бесконечно растущей продукции. Инженеры стали задумываться о способах расширения объемов кодируемых данных и результатом их деятельности стало появление на свет двумерных штрих-кодов, но вот сфера их применения, в силу специфики, перестала ограничиваться исключительно «пометкой» различной продукции. Теперь, представители семейства «матричных» активно используются в среде потребительской и теперь им находят все более интересные способы применения. И чтобы при случайной встрече с ними ты не смотрел на них, как на картинку с ребусом, мы научимся распознавать их не только по внешним признакам, но и напишем программный инструмент, который позволит тебе определить содержание контейнера с данными, а также поговорим о нестандартных способах использования матричного кодирования. Обо всем по порядку.


    Пришел. Увидел. Распознал.

    Чтобы не получить в конечном счете «кашу» из определений, предлагаю придерживаться общей классификации способов кодирования информации. Как уже было упомянуто вначале, разделяют два принципиально разных типа кодирования:

    1) Линейный (одномерный). Наиболее распространенный представитель - EAN-13 (в народе называемый «штрихкодом»).

    2) Двумерный. В свою очередь он делится на:

    2.1) многоуровневый (stacked);

    2.2) матричный (matrix).


    Многоуровневые коды нам не интересны, так как они представляют собой попросту «многослойный» линейный код. В свою очередь, матричные кодировки «упаковывают» информацию как по горизонтали, так и по вертикали, что позволяет радикально увеличить объем хранимых данных и, соответственно, снять ограничения на их тип - теперь становится возможным кодирование текстовых данных.

    Из всего многообразия матричных кодов нам интересен QR-код. Его повсеместная распространенность (одна только Япония использует эти кодировки с такой завидной популярностью, как, например, мы используем таблички с указанием названия улицы и номера дома) обусловлена прежде всего высокой степенью его распознаваемости и, как следствие, простотой распознающего оборудования. Кстати, аббревиатура QR образована от англ. «quick response»,что в переводе на великий и могучий означает «быстрый отклик».

    [​IMG]

    Быстро «откликнуться» конкретный экземпляр QR-кодов может на самое непривередливо оборудование. Так например, имея в наличии мобильный телефон или любой другой девайс с камерой практически любого разрешения, можно считать себя уже достаточно укомплектованным на охоту за QR-кодами. Если сфотографировать QR-картинку, прилагающуюся к статье (или открыть ее с диска и сделать банальный PrintScreen, но это выглядит менее эффектно), пропустить фотографию через одну из программ распознавания, то мы получим следующую строку:

    Xakep Online: http://xakep.ru

    Что делать с полученной информацией (перейти по ссылке на веб-ресурс, сохранить ссылочку в заметках или в контактах и т.п.) ты решишь самостоятельно.

    Программы для распознавания QR-кодов доступны практически под любые платформы, однако большинство из них рассчитано на мобильную аудиторию. Неудивительно, ведь в подавляющем большинстве случаев, когда мы можем встретить «белый квадрат с черными точками», у нас под рукой не окажется ничего кроме мобильного телефона. Большинство программ находятся в свободном доступе и являются бесплатными, однако мало кто из разработчиков делиться исходными кодами своего ПО. Может быть этот факт обусловлен отсутствием интереса конечного пользователя, а может быть производитель не хочет раскрывать деталей алгоритма распознавания для благополучного выхода на рынок своего программного обеспечения.

    [​IMG]

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


    Готовим инструменты

    Разрабатывать приложение будем под платформу .NET на языке C#. Выбор данного инструментария основан не только на удобстве и скорости разработке приложения, но и на получении многоплатформенного результата.

    По определению, скомпилированный под .NET Framework проект в силу ряда особенностей наделен свойствами кросплатформенности. Плюс ко всему, если скомпилировать полученный проект с поддержкой окружения .NET Compact Framework, мы получаем высокопроизводительное приложение, специально адаптированное для запуска на мобильных платформах. Указанная совместимость без дополнительных трудозатрат объясняется следующей особенностью: Microsoft .NET Compact Framework представляет собой несколько урезанную версию .NET Framework, поэтому в большинстве случаев от разработчика приложений под мобильные устройства не требуется лишних действий с исходными кодами с целью переноса функционала на десктопные платформы.

    Если с выбором инструмента создания ПО в общем все практически очевидно, то с инструментами для манипуляций с QR-кодом в частности дела обстоят несколько сложнее. В .NET Framework не имеется «нативных» средств для работы с матричными кодировками.

    В процессе поиска сторонних библиотек для работы с матричными кодами я столкнулся с веб-ресурсом восточной компании занимающейся профессиональной работой с изображениями и обработкой баркодов (двумерных кодов, к коим относится и QR). Результатами своей деятельности в виде демонстрационных версий компонент для кодирования-декодирования ряда двумерных представителей штрихкодов разработчики компании любезно делятся с посетителями. SDK доступно для скачивания и содержит библиотеки под разные платформы: Windows, *NIX, Windows Mobile, Symbian и iPhone (Mac OS). Для интересующей нас платформы Windows, а также для Windows Mobile, SDK предоставляется вместе с динамической библиотекой (.dll), что позволяет легко использовать его в проектах на .NET/VC/VB.

    Помимо манипуляций с QRCode библиотека также умеет работать с DataMatrix и PDF417. Так что, если у тебя возникнет желание расширить свой кругозор и поиграться с другими типа кодирования, то все нижеописанные действия в общем случае подходят и для указанных кодировок.


    Разбираем матрицу

    Рассмотрим общую структуру приложения, которое, как предполагается, будет декодировать QR-код.

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

    Code:
    unsafe public struct PTIMAGE
    {
    public int dwWidth;// ширина изображения в пикселях
    public int dwHeight;//высота изображения в пикселях
    public byte* pBits;//указатель на данные исходного изображения
    public byte* pPalette;// указатель на данные о палитре изображения (1,4,8 бит)
    public short wBitsPerPixel; //число бит на пиксель
    }
    SDK поддерживает большинство форматов файлов изображений. Учитывая тот факт, что большинство камер экспортируют снимки в наиболее распространенные форматы - проблем с несовместимостью быть не должно.

    Далее идет раздел описания функций, которые экспортируют библиотеки, входящие в состав SDK. Заострять внимание на их подключении мы не будем.

    Следующим этапом будет описание параметров библиотеки декодирования баркодов в структуре PTDECODEPARA.

    Структура PTDECODEPARA используется для определения параметров при декодировании баркода на изображении

    Code:
    public unsafe struct PTDECODEPARA
    {
    public int dwStartX;// начало координаты X в пикселях в окне поиска изображений для декодирования
    public int dwStartY; 
    public int dwEndX;
    public int dwEndY;
    public int dwMaxCount;//максимальное количество символов для поиска; если значение равно 0, то ищем все символы
    };
    Манипулируя со значением переменной dwMaxCount мы таким образом получаем возможность управлять производительностью приложения, фокусируя наш «декодировщик» на конкретных областях исходного изображения и избегая функционирования «в холостую».

    Следующая структура заполняется непосредственно после определения области изображения, в которой находится баркод.

    После декодирования структура PTBARCODEINFO содержит баркод с информацией

    Code:
    public unsafe struct PTBARCODEINFO
    {
    /*координаты четырех углов баркода в пикселях*/
    public int dwX1, dwY1;
    public int dwX2, dwY2;
    public int dwX3, dwY3;
    public int dwX4, dwY4;
    public byte* pData; //указатель на буфер, который содержит данные баркода
    public int dwDataLen; //длина данных (в байтах) баркода
    };
    Если ты внимательно посмотришь на картинку с QR-кодом, то сразу заметишь три выделяющихся квадратных области – это ориентиры для средств распознавания, своего рода «указатель» программе на то, что среди прочего набора пикселей на картинке присутствует QR-код.

    Главная функция нашего приложения проста до безобразия, поэтому в полном объеме приводить ее не будем, а сосредоточим внимание на следующих инструкциях:

    Code:
    static void Main(string[] args)
    {
    PtQRDecodeRegister("12345678901234567890");//использование ключа демонстрационной версии
    PtInitImage(ref image); // инициализация структуры изображения
    …
    if (OpenFileDlg.FileName != "")
    {
    FileName = OpenFileDlg.FileName;
    DecodeQR();
    }
    …
    }
    Как ты уже понял, непосредственно процесс распознавания скрывается в инструкциях функции DecodeQR(), которая после определения области QR-кода передает инструкции обработчику баркода, а он, в свою очередь, демонстрирует пользователю информацию, содержащуюся в картинке:

    Code:
    static private void DecodeQR()
    {
    …
    /*если операции загрузки изображения и определения наличия в нем баркода выполнены успешно*/
    if (PtLoadImage(FileName, ref image, 0) == PT_IMAGERW_SUCCESS)
    {
    if (PtQRDecode(ref image, ref DecodePara, ref BarCodeInfo) != PT_QRDECODE_SUCCESS)
    MessageBox.Show("An error occured while rocognition ");
    else
    ShowBarCodeInfo(ref BarCodeInfo);//передача полученной структуры функции-обработчику
    }
    …
    }
    //описание функции-обработчика, возвращающей строку QR-кода
    static public unsafe void ShowBarCodeInfo(ref PTTOTALBARCODEINFO BarCodeInfo)
    {
    if (BarCodeInfo.dwTotalCount <= 0)
    {
    MessageBox.Show("No barcode was found");
    return;
    }
    string str = "";
    //совокупность операций получения строки
    { …
    str = str + Encoding.Default.GetString(byteArray);//Encoding.GetEncoding("GB2312").GetString
    str = str + "\n\n";
    }
    str = str + '\0';
    MessageBox.Show(str);
    }
    Легкий «краш-тест» полученного приложения позволил выявить его сильные и слабы стороны.

    • процесс распознавания не зависит от положения QR-кода на картинке;

    • процесс распознавания не зависит от степени поворота QR-кода и его масштабу.

    Однако с распознаванием кодов в 3D все несколько хуже: искажение в соотношении сторон QR-кода может негативно сказаться на качестве определение его содержимого.

    [​IMG]

    Представленная библиотека предоставляет разработчику широкие возможности работы с матричными кодами. Имеются встроенные средства коррекции ошибок и восстановления поврежденных областей исходных изображений. Возможности изменения параметров точности распознавания позволяют программисту найти золотую середину в тандеме параметров «производительность/эффективность».

    [​IMG]

    Результат разбора пациента - строка "Xakep Online: http://xakep.ru":

    [​IMG]


    Перспективы.Decode()

    Рамки применения QR-кода ограничиваются исключительно фантазией своего интегратора. Банальный обмен контактными данными (адреса сайтов на картинке в каком-либо общественном месте, эффектная демонстрация данных визитки на черно-белой карточке, реклама и объявления, приглашения и др.) на фоне массы других способов уже кажется, как минимум, неоригинальным.

    Идея расширения видимой реальности с помощью подручных средств, коими являются мобильные телефоны, кажется уже не настолько далекой и требующей технического прогресса. А практичность данного вида представления информации для конечного потребителя заметна уже сейчас. Обладатель телефона, интересующийся, например, меню какого-либо ресторана (бара, кафе, памятника архитектуры, или любым другим зданием, содержащим QR-код, который несет полезную информацию), при наведении камерой на QR-область мог ознакомиться в реальном времени с меню, не посещая заведение. Или ознакомиться с расписанием маршрута проезжающего мимо общественного транспорта, содержащего «полезную картинку».

    Альтернативное кодирование информации может оказаться полезным в вещах, имеющих стеганографическую подоплеку. Например, QR-код можно спрятать в цветное изображение, которое при обесцвечивании и последующей обработке может «рассказать» гораздо больше, чем в «штатном» режиме. Хотя, даже сам факт использования матричной кодировки у непросвещенных людей может не вызвать подозрений. Надеюсь, ты теперь к таким не относишься.

    (c) c0n Difesa (defec.ru)
     
Loading...