2

Міністерство транспорту та зв’язку України

Д ержавний департамент з питань зв’язку та інформатизації

О деська національна академія зв’язку ім. О.С. Попова

К афедра мереж і систем поштового зв’язку

В.І. Голуб, В.І. ЗАГРЕБНЮК, Л.О. Ящук

Розпізнавальні системи

поштового зв’язку

Навчальний посібник

для вищих навчальних закладів зв’язку

За редакцією доктора технічних наук, професора Л.О. Ящука

Одеса, 2009

Зміст

Вступ 4

1. Принципи побудови систем розпізнавання графічних зображень 6

1.1. Загальні відомості 6

1.2 Перетворення зображень у цифрову форму 9

1.2.1 Дискретизація та квантування зображень 9

1.2.2 Бінарний спосіб подання цифрових зображень в пам’яті ЕОМ 11

1.3 Попереднє оброблення зображень 14

1.3.1 Редагування яскравості 14

1.3.2 Фільтрація зображень 16

1.3.3 Бінаризація зображень 20

1.3.2 Способи видалення завад на бінаризованих зображеннях 24

1.4. Мінімізація поворотів поштових відправлень у системах розпізнавання поштових індексів 25

1.5 Пошук та захоплення поштового індексу 41

Контрольні питання 45

Список рекомендованої літератури 46

2. Системи розпізнавання стилізованих цифр 47

2.1. Загальні відомості 47

2.1.1 Характеристика систем оптичного розпізнавання символів 47

2.1.2 Характеристики стилізованих цифр 50

2.2. Виділення і запис ознак стилізованих цифр 53

2.3. Класифікація стилізованих цифр 60

Контрольні питання 62

Список рекомендованої літератури 63

3. Системи розпізнавання нормалізованих цифр 64

3.1. Загальні відомості 64

3.2. Виділення і запис ознак нормалізованих цифр 67

3.3. Класифікація нормалізованих цифр 68

Контрольні питання 70

Список рекомендованої літератури 71

4. Системи розпізнавання штрихових кодів 72

4.1. Загальні відомості 72

4.2. Засоби зчитування штрихових кодів 85

4.3. Декодування штрихових кодів 89

Контрольні питання 93

Список рекомендованої літератури 93

5. Адаптація алгоритмів розпізнавання до афінних спотворень графічних зображень 95

5.1. Загальна характеристика афінних спотворень графічних зображень 95

5.2. Визначення параметрів афінних спотворень графічних зображень 98

5.3. Урахування параметрів афінних спотворень в алгоритмах 104

розпізнавання графічних зображень 104

Контрольні питання 111

Список рекомендованої літератури 111

6. Оптимізація показників якості розпізнавання графічних зображень 113

6.1. Показники якості розпізнавання графічних зображень 113

6.2. Застосування критерію мінімального ризику при розпізнаванні графічних зображень рукописних цифр 116

6.3. Приклад застосування критерію мінімального ризику при розпізнаванні графічних зображень 120

Контрольні питання 124

Список рекомендованої літератури 124

7. Організація автоматизованого оброблення поштових відправлень на базі розпізнавальних систем поштового зв’язку 125

7.1. Організація автоматизованого сортування поштових відправлень 125

7.2. Організація автоматизованого обліку і контролю пересилання поштових відправлень 137

7.3. Забезпечення розпізнавання поштових індексів у реальному часі 144

Контрольні питання 151

Список рекомендованої літератури 151

Вступ

Розпізнавання образів (явищ, об’єктів, ситуацій, сигналів) – найбільш розповсюджена задача, якою люди й тварини займаються практично все своє життя.

Як людина пізнає зображення, звуки, кольори, запахи, як собака відрізняє „своїх” від „чужих”, як перелітні птахи знаходять шляхи своєї щорічної міграції? Ці і тисячі подібних питань є прикладами задач розпізнавання образів.

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

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

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

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

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

Нерівномірність навантаження по годинах, добах, тижнях, місяцах, періодах, наявність так званих святкових і сезонних потоків призводили до суттєвих затримок оброблення поштових відправлень, зниження ефективності та продуктивності праці сортувальниць.

Проблема сортувальниць стала в один ряд з виниклою на початку ХХ століття проблемою „телефонних панночок”, для вирішення якої були створені автоматичні телефонні станції.

Розробка систем автоматичного сортування письмової кореспонденції в багатьох промислово розвинених країнах світу, в тому числі в СРСР, почалася у 60-х роках ХХ століття.

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

Поштовий індекс – це цифровий або буквено-цифровий еквівалент поштової адреси.

На відміну від поштової адреси, яка містить інформацію про географічне найменування і місце розташування того чи іншого населеного пункту в явному і, як правило, надмірному виді, поштовий індекс містить цю інформацію у закодованому і надто стислому виді, наприклад, за допомогою застосовуваних нині в Україні п’ятизначних десяткових цифрових індексів можна закодувати 10⁵ = 100000 найменувань населених пунктів України, що багаторазово перевищує їх фактичну кількість.

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

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

Останнім часом все більш широке застосування знаходять системи розпізнавання так званих штрихових кодів, в яких значення цифр індексу подані сполученнями штрихів і проміжків різної ширини.

У даному навчальному посібнику наведено викладення основних задач, що виникають при побудові розпізнавальних систем поштового зв’язку.

1. Принципи побудови систем розпізнавання графічних зображень

1.1. Загальні відомості

Будь яка система розпізнавання оперує не реальними об’єктами а їх відображенням на певну множину ознак, що характеризують деяку сукупність різних об’єктів. Це відображення називають образом. Загалом розпізнавання образів подається у виді перетворень, наведених на рис.1.1.

Рисунок 1.1 – Подання розпізнавання образів у виді перетворень

Множина образів X_k (k = 1 … l) може відноситись до тієї чи іншої області дослідження, наприклад, цифрові зображення, звукові сигнали, діагнози хвороб й т. ін.

Зазначені образи піддаються аналізу, в процесі якого виконується їх опис мовою зазделегідь вибраної системи ознак. Як ознаки можуть бути фізичні параметри образів (маса, габарити, форма, температура); їх відносні характеристики (великий – малий, високий – низький, товстий – тонкий); характерні ознаки (друкований, рукописний) й т.ін.

Вибір системи ознак – складна і відповідальна задача і поки що неформалізована, тобто не існує загальних методів вибору системи ознак. У загальному випадку потужність множини ознак повинна забезпечувати розбиття множини образів на підмножини (класи еквівалентності), що не перетинаються. Одержана таким чином множина значень Y_i (i = 1 … m) ознак (множина описів образів або суттєвих ознак) класифікується, тобто кожен образ відноситься до того чи іншого заздалегідь визначеного основного класу Z_j (j = 1 … n) відповідно до деяких вирішальних правил або визначається, що він не відноситься до жодного з цих класів, тобто класифікується як додатковий заздалегідь невизначений клас Z₀.

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

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

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

Рисунок 1.2 – Ймовірний характер перетворень у процесі розпізнавання образів

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

Зазначені обставини призводять до суттєвого ускладнення розпізнавальних систем поштового зв’язку й обумовлюють доцільність їх побудови на базі персональних ЕОМ.

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

Кожне зображення R, що розпізнається, характеризується набором ознак r₁, r₂, …, r_m, які вибираються на основі статистичних досліджень, досвіду, зручності виділення та інших факторів.

Різні алгоритми розпізнавання цифр використовують як ознаки штрихи (горизонтальні, вертикальні, нахилені); контури (замкнені, розімкнені); кількість перетинів знака вертикальними, горизонтальними чи нахиленими лініями; топологічні ознаки (початок і кінець ліній, розгалуження і з’єднання ліній, перетинання ліній); метричні ознаки (відстані між елементами знака, розміри окремих елементів).

При розпізнаванні графічної інформації, зокрема, цифр поштового індексу, використовуються поняття подібності і відмінності образів, що розпізнаються. Набір ознак r₁, r₂, …, r_m, кожна з яких приймає певні дискретні значення, створює деякий m-вимірний векторний простір ознак, кожна координата якого являє одну ознаку, а кожна точка – один образ. Якщо увести певну міру близькості між точками цього m-вимірного векторного простору (наприклад, евклідову чи відстань Хеммінга), то подібність або відмінність образів буде визначатися значенням цієї відстані.

Образи з малою відмінністю ознак займають малий (компактний) об’єм простору ознак, а з великою – великий об’єм цього простору, не мають чітких меж (розпливчасті). Найбільш компактними є зображення цифр поштового індексу, нанесені друкарським способом, найбільш розпливчатими – нанесені людиною від руки. На рис. 1.3 наведено приклад ланцюжка переходів образів з одних класів в інші.

Рисунок 1.3 – Приклад переходів образів з одних класів в інші

Задача побудови дієздатної розпізнавальної системи неминуче потребує різкого звуження характеристичних об’ємів рукописних цифр у просторі ознак.

Для спрощення розпізнавальних систем поштового зв’язку уводяться деякі обмеження на місцеположення, розміри і (або) форми написання цифр індексу. Найбільшого поширення набули системи распізнавання так званих стилізованих і нормалізованих цифр індексу. У системах розпізнавання стилізованих рукописних цифр уводяться обмеження на місцеположення, розміри і форми написання цифр, у системах розпізнавання нормалізованих рукописних цифр – тільки на місцеположення і розміри цифр.

Основними показниками якості розпізнавання є ймовірності правильного розпізнавання Р_пр, помилкового розпізнавання Р_пом і відмови від розпізнавання Р_відм, сума яких дорівнює одиниці, як сума ймовірностей повної групи подій.