Распознавание образов
В последние годы распознавание образов находит все большее
применение в повседневной жизни. Распознавание речи и
рукописного текста значительно упрощает взаимодействие
человека с компьютером, распознавание печатного текста
используется для перевода документов в электронную форму.
Популярно мнение, что распознавание, как и прочие алгоритмы
искусственного интеллекта, есть черная магия, недоступная
простым смертным. На самом же деле алгоритмы, лежащие в основе
распознавания, довольно очевидны, нужно лишь зайти чуть
издалека и определиться с терминами.
Базовым является неопределимое понятие множества. В
компьютере множество представляется набором неповторяющихся
однотипных элементов. Слово "неповторяющихся" означает, что
какой-то элемент в множестве либо есть, либо его там нет.
Универсальное множество включает все возможные для решаемой
задачи элементы, пустое не содержит ни одного.
В классической постановке задачи распознавания (странно
называть классической науку, которой от силы несколько
десятилетий:) универсальное множество разбивается на
части-образы. Образ какого-либо объекта задается набором его
частных проявлений. В случае с распознаванием текста в
универсальное множество войдут все возможные знаки, в образ
"Ы" - все возможные начертания этой буквы, а программа
распознавания занимается тем, что на основе небольшого набора
примеров начертаний каждой буквы (обучающей выборки)
определяет, какую из них символизирует введенная
закорючка.
Методика отнесения элемента к какому-либо образу называется
решающим правилом. Еще одно важное понятие - метрика, способ
определения расстояния между элементами универсального
множества. Чем меньше это расстояние, тем более похожими
являются символы, звуки - то, что мы распознаем. Обычно
элементы задаются в виде набора чисел (а как еще?), а метрика
- в виде функции. От выбора представления образов и реализации
метрики зависит эффективность программы, один алгоритм
распознавания с разными метриками будет ошибаться с разной
частотой (право на ошибку для программ распознавания так же
характерно, как и для людей).
Хорошо показывает принцип работы распознавания образов
элементарный алгоритм на основе метода множества эталонов. На
входе его имеется обучающая выборка - набор примеров A'ij для
каждого образа Ai, метрика d и сам распознаваемый объект x. С
помощью метрики вычисляем расстояние от x до каждого элемента
обучающей выборки d(x, aij) и находим условное расстояние d(x,
Ai) как расстояние от x до ближайшего элемента из Ai. Элемент
x относится к образу, который окажется ближе всех.
Практически тут требуется найти минимум расстояния по
каждому классу и еще раз взять минимум. Любители трогать
руками могут взять в качестве представления элемента пару
координат, в качестве метрики - расстояние по теореме
Пифагора, и набросать программку, которая будет выполнять
описанную операцию над массивом точек двухмерного пространства
и отображать это в графике.
Еще один элементарный алгоритм - метод k-ближайших соседей.
Как следует из названия, в нем вводится дополнительный входной
параметр, целое число k. Тут все еще проще - берется k
ближайших к x элементов обучающей выборки и подсчитывается,
сколько из них принадлежит к какому образу. К какому образу
принадлежит больше, к тому относится и x.
В обоих алгоритмах может возникнуть неопределенная ситуация
- когда x будет находиться на одинаковом расстоянии от
нескольких образов. В таком случае программа должна либо
спросить у пользователя, к какому образу относить элемент,
либо тихо бросить жребий. Это зависит от требований к точности
с одной стороны, и удобству использования с другой, лучше
всего реализовать оба варианта.
Несмотря на чрезвычайную простоту, описанные алгоритмы
вполне применимы на практике. Существует множество других
методов, более сложных, и теоретические работы по данной теме
могут повергнуть в трепет своей монументальностью (кроме того,
большая их часть написана на английском), но и программы на
элементарных алгоритмах, толково реализованные, могут выдавать
неплохие практические результаты.
Дмитрий БОРОДАЕНКО,
forever@mad.scientist.com
http://www.ocrai.narod.ru E-Mail: grigorlukashenko@mail.ru последнее обновление: 26;03;2001
Psend kept free because of these great sponsors.a..
|
Other Sponsors
electrical connectors,
Mangosteen Juice,
real estate short sale,
Jupiter FL real estate,
|
Furniture Markdown
Great Deals on furniture - Free Shipping!
Discount Furniture
Daybeds
Metal Beds
Platform Beds
Futons
|
Y-Net Wireless Internet
Denver area high speed wireless privider.
Colorado High Speed Internet,
Wireless Internet Denver,
VOIP Denver CO,
T1 provider Denver,
Denver Wireless ISP ,
Denver Internet Access,
|
|
Dog House Technologies
Doghouse Techonologies is located in Tampa Bay FL and offer professional web design, ecommerce development and custom application design for the internet.
Tampa Bay Web Design,
E-Commerce Web Design,
Tampa Bay Search Engine Marketing,
Tampa Web Hosting,
Florida Web Design,
Custom Application Development,
Search Engine Optimization,
|