си об'єктів - і припустимо, що класи лінійно віддільні. Рівняння розділяє гіперплощини має вигляд, де w - нормаль до гіперплощини. Півпростору, утворені цієї гиперплоскостью, задаються нерівностями і. Тобто для всіх точок одного класу буде виконано перше нерівність, а для точок іншого класу - друге. Таким чином, ми шукаємо вирішальну функцію у вигляді:
Ясно, що таких гіперплоскостей може існувати нескінченно багато. Щоб зрозуміти, яка саме потрібна нам, повернемося до оцінки ризику класифікації. В.Н. Вапніка була доведена теорема, що ризик класифікації може бути оцінений в термінах емпіричного ризику (порахувати на тренувальних даних) і доданка, що враховує складність класу функцій, з якого вибирається рішення:
Мінімізація ризику класифікації еквівалентна вирішення наступного квадратичної завдання:
Розміри навчальної вибірки слід оцінювати як мінімум кількома сотнями тисяч. Це робить стандартні чисельні методи квадратичного програмування (метод Ньютона, прямодвойственние методи внутрішньої точки та інші) технічно непридатними.
Нещодавно було запропоновано кілька цікавих алгоритмів вирішення цієї проблеми. Одні спираються на факт, що рішення задачі не зміниться, якщо з матриці викинути рядки і стовпці, відповідні нульовим множників Лагранжа. Інші пропонують вирішувати підзадачі фіксованого розміру, рухаючись в напрямку найбільшого спуску цільової функції. Для вирішення задачі оптимізації, що виникає при навчанні SVM, найбільш ефективним виявився метод, відомий як Sequential Minimal Optimization (SMO).
Відмінність SMO від інших алгоритмів полягає в тому, що на кожному кроці він вирішує мінімально можливу підзадачу. Так як у задачі присутній лінійне обмеження, то мінімальна кількість множників Лагранжа для спільної оптимізації дорівнює двом. А для двох множників завдання можна вирішити аналітично, не вдаючись до чисельних методів квадратичного програмування. Незважаючи на те, що доводиться вирішувати багато підзадач, кожна з них вирішується настільки легко, що спільне рішення задачі може бути знайдено дуже швидко. До того ж, при такому підході немає необхідності зберігати навіть частина гессіан в пам'яті. Саме це алгоритм і був обраний для вирішення задачі оптимізації, що виникає при навчанні SVM. [9, 10]
.3.2 Розробка алгоритму
Рис. 1.25 Блок-схема алгоритму
В основу мого алгоритму був узятий існуючий алгоритм «Швидке та ефективне текстове виявлення» розроблений в Університеті Дипломованого фахівця китайської Академії Наук, Пекін, Китай.
.3.2.1 Попередня обробка зображень
Це головна функція, вона включає в себе:
Знаходження розмірів зображення (ширина, висота);
Переклад зображення в «Grayscale» режим;
Стиснення зображень (для тих, чий розмір більше 600 пікселів по обидва боки);
Знаходження середнього відхилення інтенсивності по всьому зображенню.
Переклад зображення в «Grayscale» режим так званий «Сірий» режим обов'язковий, це спрощує пошук «контрастних» пікселів і середнього відхилення інтенсивності.
Зображення стискається до розмірів 600 пікселів по ширині або висоті, в залежності від його пропорцій.
Знаходження середнього відхилення інтенсивності пікселів необхідно для того щоб виявити «особливо контрастних сусідів» для кожного пікселя. Експериментально обчислено, що саме середнє значення відхилення дає більш ефективний результат, ніж середнє квадратичне.
.3.2.2 Пошук контрастних пікселів
Функція підраховує число «контрастних сусідів» для кожного пікселя внутрішній області малюнка (не лежать на кордоні малюнка) і поміщає результат в матрицю.
Експерименти показали, що число 35 як порогова різниця в интенсивностях двох пікселів цілком працездатний і дуже ефективно.
Розглянемо на прикладі:
2 Серпень
56 48
30 14
У центрального «червоного» пікселя різниця в інтенсивності більше 35 з п'ятьма «синіми» пікселями, тому цьому пікселю присвоюємо «контрастність» рівну 5. У кожному квадратику, для кожного пікселя, число його «особливо контрастних сусідів» не може перевершити 8.
.3.2.3 Формування списку передбачуваних текстових областей
Алгоритм передбачає, що розмір символу в шрифті лежить в проміжку від 8 до 32 пікселів.
Це основна функція, так звана «лічильник штріхованіем», аналог «штрихових Карт». Вона обчислює ступінь «штріхованіем» квадратного ділянки зображення розміром 24 на 24 пікселя.
Розглянемо докладніше:
Ця функція у віконці 24 на 24 пікселя в матриці вважає кількість пікселів, у яких число «особливо контрастних сусідів» одно 3 або 6. Це найважливіша частина. Число «особливо контрастних сусідів» може бути від 0 до 8, але нас цікавить тільки 3 або 6. Це пов'язано з тим, що символ - є набір вертикальних, горизонтальн...
