О возможности применения эвристических алгоритмов для автоматического распознавания значений счетчиков посещаемости интернет-ресурсов

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 738. 52
Д.С. Курушин
Пермский государственный технический университет
А. Г. Санникова, А.М. Левченко
Пермский государственный университет
О ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ ЗНАЧЕНИЙ СЧЕТЧИКОВ ПОСЕЩАЕМОСТИ ИНТЕРНЕТ-РЕСУРСОВ
Рассмотрен эвристический подход к распознаванию символов на счетчиках посещаемости интернет-ресурсов. Задача рассматривается как пошаговое распознавание сначала типа счетчика, потом отображенного на нем значения. Распознавание основано на считывании значений яркости контрольных точек, уникальных для каждого счетчика и каждого символа.
При выполнении задачи мониторинга активности пользователей некоторых интернет-ресурсов, а также положения этих ресурсов в различных поисковых системах возникает необходимость автоматизированного сбора информации с графических счётчиков, размещающихся на рассматриваемых сайтах.
Принцип работы всех счетчиков посещений заключается в выполнении внешней программы при загрузке страниц сайта. При загрузке счетчика выполняется внешняя программа, при этом ей передаются так называемые переменные окружения.
В качестве учебного пособия решается вполне реальная задача по графическому распознаванию символов (OCR) на материале графических счётчиков посещений/кликов/позиции в поисковых системах и различных индексов цитирования.
Решение описанной задачи приводится на концептуальном уровне, без реализации в программном коде. Основными критериями к решению задачи являются алгоритмическая простота решения и простота реализации.
Используемые подходы, средства реализации. Ключевым является момент определения алгоритма распознавания графической информации (OCR). На данный момент известно два принципиальных метода распознавания: эвристический и использование искусственной нейронной сети [1, 2].
Эвристические алгоритмы в OCR позволяют на основе существующей модели (набора символов, требований к их написанию и т. д.) показать вероятность совпадения испытуемой модели (распознаваемого изображения) и существующей модели посредством сравнения их признаков на предмет совпадения.
Нейронные сети — в частности, персептрон — позволяют по итогам процесса, называемого обучением нейронной сети, достаточно точно классифицировать поступающие на вход изображения БЕЗ эталонной модели [3].
Плюсом нейронных сетей в сравнении с эвристическим алгоритмом является большая устойчивость к искажениям входных данных. Недостаток метода — сложность в реализации и конфигурировании (обучении).
В нашем случае для решения задачи выбран эвристический алгоритм, т.к. количество использованных в счётчиках шрифтов ограничено, и все символы имеют заранее известное написание, жёстко связанное с типом счётчика. Также решение задачи упрощается тем, что для каждого типа счётчика заранее известна область расположения значимой информации (область распознавания).
Логика решения задачи описана при помощи ключевых диаграмм UML с необходимыми комментариями.
Решение задачи. На рис. 1 представлена диаграмма активности, отражающая работу с каждым сайтом списка.
Первый пункт (получение изображений с сайта) выполняется по следующему алгоритму: для списка всех сайтов выбираются URL, список этих URL обходится и для каждого URL при помощи утилиты wget, по протоколу HTTP загружаются все изображения типов GIF и PNG, имеющиеся на странице.
Затем для каждого изображения определяется разрешение при помощи утилиты file, и изображения с разрешением, отличным от 8831, удаляются. Отобранные изображения заносятся в базу данных с указанием необходимой информации.
Рис. 1. Диаграмма активности
Определение типа счётчика на изображении производится при помощи контрольных точек (Point, параметр IsTextArea = false), заранее определённых в программе (справочник типов). Для каждого изображения определяется цвет контрольных точек, после чего полученный набор значений сравнивается с цветами соответствующих точек у типов. В качестве типа счётчика выбирается тот тип, у которого выше процент совпадений- при совпадении менее 80% изображение не обрабатывается (происходит переход к следующему).
На изображениях с установленным типом счётчика производится распознавание текста при помощи эвристического алгоритма, описанного на рис. 2.
По окончании обработки всех изображений производится формирование отчёта по данному сайту.
Рис. 2. Диаграмма активности процесса распознавания символов
При выделении области распознавания производится обрезка изображения по прямоугольнику, заданному ключевыми точками области распознавания (Point. IsTextArea = true), заранее определёнными в справочнике типов.
Приведение к чистому чёрно-белому изображению без градаций производится на основе люма-преобразования (цвет каждого пиксела меняется по формуле 0,3xR + 0,59*G + 0,11 XB) с последующей нормализацией гистограммы. После этого делается анализ гистограммы на преобладание тёмного/светлого (фильтр по порогу 50%) с автоматической инверсией изображения в случае преобладания тёмного. Последний шаг — пороговое преобразование (в нашем случае — по порогу в 35%) с приведением нижней части гистограммы к минимальному значению, а верхней — к максимальному.
Затем область распознавания делится на сегменты, соответствующие отдельным цифрам, по детерминатору — столбцу фоновых (белых) пикселов. Если деление по детерминатору даёт слишком большие сегменты (обычно — более 6 пикселов), производится вторичное деление с помощью эвристического алгоритма: изображение последовательно делится на сегменты шириной от минимальной ширины цифры данного счётчика до максимальной — до тех пор, пока распознавание полученных сегментов не даст корректный результат.
24 454 24 454 244 244 344 244
Рис. 3. Эвристическое деление на примере счётчика SpyLog
В общем случае при OCR разумно уменьшение разрешения сегментов распознавания до рабочего (обычно 5*7, для кириллических букв — до 8*8) — но в нашей задаче такое преобразование неактуально, т.к. высота цифр на счётчиках не превышает 9 пиксел, и графическое преобразование даст только дополнительный шум на изображении.
Все изображения отдельных цифр (рис. 3) проверяются по списку точек, определяющих значение цифры для данного типа счётчика. На основании процента совпадения с эталонами определяется цифра, изображённая в данном сегменте.
После определения всех цифр на изображении полученный набор преобразуется в число, которое записывается в БД как значение данного счётчика (для отдельных счётчиков значений может быть несколько- они определяются поочерёдно по тому же алгоритму).
На рис. 4 представлена диаграмма классов для решения данной задачи. Базовый класс, от которого наследуются все последующие -Base с полем ID и методом getID, предназначенный для корректной интеграции с БД.
Класс Point (поля X, Y, Type- методы — getXY, getType) используется для хранения информации о ключевых точках: их координаты и тип счётчика, к которому они относятся. Порождает класс Point-TypeDefiner (доопределённое поле Color, метод — getColor), в котором хранится информация о точках, определяющих тип счётчика по цвету.
Следующий класс — Site (поле URL) используется для хранения информации о рассматриваемых сайтах.
Рис. 4. Диаграмма классов
Класс Image (поля ImageData и Resolution, метод getResolution) используется для хранения информации об изображениях, полученных с сайта. Порождает три класса: Counter (поле Type, методы get-Type, toBW, detectDataArea), использующийся для хранения информации об изображениях, распознанных как счётчики (метод toBW используется для перевода изображения в чёрно-белый вид, detect-DataArea — для определения области, в которой расположены цифры для распознавания), класс DataArea (единственный метод — split — используется для разделения области распознавания на сегменты, соответствующие цифрам) и класс GraphicNumber (поле Value, методы Recognize и getValue).
Класс Type (метод getType) используется для хранения информации о типе счётчика.
На рис. 5 представлена e-r диаграмма, показывающая модель данных, используемых в нашей задаче.
Основная сущность — сайт (Site). Представляет собой список сайтов, с которыми будет работать программа. Включает в себя его уникальный идентификатор (ID, Integer) и адрес страницы, на которой находятся счётчики (URL, Text).
Изображение (Image) — сущность, отвечающая за хранение полученного с этой страницы счётчика. Включает в себя уникальный идентификатор (ID, Integer) — ссылку на тип счётчика (ID_Type, Integer) — ссылку на сайт, с которого взято изображение (ID_Site, Integer), адрес изображения в интернете (URL, Text) — дату получения изображения (Date, Datetime) — собственно изображение (Data, Binary) и распознанное в ходе выполнения программы значение счётчика на изображении (Value, Integer).
Point
Ю PK
ID type
X
Y
Color
IsTextArea
Site
ID PK
URL
Image
Ю PK
ID_Type
ID Site
URI
Date
Data
Value
Type
ID PK
TypeName
Рис. 5. E-R диаграмма
Тип (Type) — сущность, определяющая тип счётчика (Яндекс, SpyLog, HotLog, LiveInternet и т. д.) включает уникальный идентификатор (ID, Integer) и имя типа (TypeName, Text).
Точка (Point) — сущность, хранящая информацию о ключевых точках, отвечающих за определение типа счётчика и области распознавания в данном типе. Включает уникальный идентификатор (ID, Integer), ссылку на определяемый тип (ID_Type, Integer), координаты точки на изображении (X, Y, Integer), информацию о цвете этой точки (Color, Integer) и о классе определяемых точкой данных: тип счётчика или область распознавания (IsTextArea, Boolean).
Пример работы. Рассмотрим работу алгоритма распознавания на примере четырёх счётчиков (LiveInternet, MyCounter, one. ru, mail. ru), взятых с сайта (http: //cn. jino-net. ru/).
Счётчики, полученные с сайта (порядок соответствует указанному (рис. 6).
Рис. 6. Счётчики LiveInternet, MyCounter, one. ru, mail. ru
При определении типа счётчика используется 7 контрольных точек (рис. 7) с координатами (0,5) — (4,5) — (4,28) — (41,0) — (41,28) —
(71,3) — (72,30).
Расположение контрольных точек на данных счётчиках:
-Ф--Ф- V А
-Л-
-ф- -контрольные точки? — счётчик
Рис. 7. Контрольные точки, определяющие тип счётчика
Таким образом, для определения счётчиков контрольные точки должны иметь следующие цвета:
1. ЫувШвгпвР. все точки — ##аа00.
2. МуСоиМег:
(0,5) — #0-
(4. 5) — #0000^Г-
(4. 28) — #a5bde7-
(41. 0) — #0-
(41. 28) — #ЙНН-
(71. 3) — #ЙНН-
(72. 30) — #0.
3. one. ru:
(0,5) — #3c3c3c-
(4. 5) — #fefefe-
(4. 28) — #fefefe-
(41. 0) — #3c3c3c-
(41. 28) — #fefefe-
(71. 3) — #757 575-
(72. 30) — #3c3c3c.
4. mail. ru:
(0,5) — #Ь0Ь0Ь0-
(4. 5) — #585 858-
(4. 28) — #707 070-
(41,0) — #Ь0Ь0Ь0-
(41,28) — #707 070-
(71,3) — #585 858-
(72,30) — #484 848.
После определения типа счётчика производится распознавание значений счётчика.
Рассмотрим процесс распознавания на примере счётчика Ьіуєіп-їєгпєї (рис. 8, 9). Данный счётчик имеет три области расположения данных, задаваемых контрольными точками (5,5- 65,9), (5,13- 65,17) и (5,21- 65,25) соответственно.
5?5 ВВВ
а_ч эчи л ппэ
Рис. 8. Контрольные точки, определяющие область распознавания
ЕПЕ ЗЕВ ІЧ ЭЧП П «ШЭ
Рис. 9. Выделенные области распознавания
После выделения отдельных областей данных программа разделяет область распознавания на сегменты, соответствующие отдельным цифрам. В случае со счётчиком Ьіуеіпіегпеї это происходит по детерминатору — пустому столбцу (рис. 10).
Рис. 10. Деление области распознавания на сегменты, соответствующие отдельным цифрам
На счётчиках Ьіуєіпїєгпєї каждая цифра имеет размеры 5*5 и однозначно определяется по цвету шести контрольных точек: (0,1), (0,3), (2,2), (2,4), (4,1), (4,3).
На рис. 11 показаны контрольные точки распознавания цифр. Точки, обозначенные зелёным, должны иметь белый цвет- точки, обозначенные красным — чёрный. Видно, что одинаковые комбинации контрольных точек не встречаются — таким образом, все цифры определяются однозначно.
Рис. 11. Цифры счётчиков LiveInternet и определяющие их контрольные точки
На последнем этапе алгоритм распознавания переводит набор распознанных цифр (в нашем случае — 2, 0, 2, 9, 9, 8) в число (202 998) и записывает его в соответствующее поле объекта, содержащего распознанное изображение.
В настоящей работе рассмотрен пример реализации системы оптического распознавания значений счетчиков посещаемости и рейтинга интернет-ресурсов. Задача решена с использованием методов объектно-ориентированного и E-R моделирования. Программный продукт реализован на языке java.
Библиографический список
1. Future Challenges in Handwriting and Computer Applications / Suen C.Y. [et al.] // 3rd International Symposium on Handwriting and Computer Applications. — Montreal, 1987. — May, 29.
2. The State of the Art in On-line Handwriting Recognition / Tap-pert, Charles C. [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — Vol. 12, No 8. — August, 1990. — Р. 787.
3. LeNet-5, Convolutional Neural Networks.
Получено 09. 07. 2009

ПоказатьСвернуть
Заполнить форму текущей работой