Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нечеткие множества

Автор: B2_Russia 18.4.2004, 13:59

Здравствуйте, уважаемык форумчане! Давненько я вас не видел Нужен алгоритм либо метод приблизительного использования теории нечетких множеств применительно к определению похожести совокупности отрезков c эталонами. То есть я имею Некоторый набор отрезков (если хотите это граф) неизвестный (причем количество отрезков может быть не равно ни одному из эталонов и их расположение так же может не совпадать), а мне нужно проверить несколько эталонов на соответствие определяемому набору отрезков... На выходе должно быть, к примеру процент соответствия... Кто решит данную проблему, в перспективе обещаю, не пожалеете...

Автор: podval 18.4.2004, 19:35

А поточнее можно с условиями задачи? Нутром чую, что дело имеем с распознаванием. Но нельзя ли спокойно рассказать, что имеем и что надо? Может и без нечетких множеств обойдемся.

Автор: maxim1000 18.4.2004, 20:20

Цитата метод приблизительного использования теории нечетких множеств приблизительное использование теории... это круто даже для теории нечетких множеств Цитата Нутром чую, что дело имеем с распознаванием. причем, судя по всему, с распознаванием текста Цитата То есть я имею Некоторый набор отрезков (если хотите это граф) неизвестный (причем количество отрезков может быть не равно ни одному из эталонов и их расположение так же может не совпадать), а мне нужно проверить несколько эталонов на соответствие определяемому набору отрезков... после того, как обработаешь такое количество информации о задаче в голове остается только одна мысль: 1. вводим меру отличия между отрезками 2. каждому отрезку из первого набора ставим в соответствие отрезок из другого 3. считаем меры отличия для всех пар, складываем, получаем число 4. перебираем все возможные варианты таких соответствий, выбираем минимум

Автор: remax 18.4.2004, 22:18

А может нужно не нечеткие множества а нечеткая логика ? (Для тех, кто не в курсе - это когда вместо однозначных ответов да или нет использует такие категории как "скорее да, чем нет", "практически да" и т.п. )

Автор: B2_Russia 19.4.2004, 20:36

Да, господа, дело в распознавании текста причем рукописного... Что мы имеем: 1) Набор полилиний, концы которых представляют узлы (для тех кто не в курсе это места соединения 3 и более таких полилиний...). Каждый набор полилиний описывает граф описывающий 1 слово текста... 2) 200000 (приблизительно) слов русского языка представленных в виде аналогично распознаваемым (граф), но естесственно модифицированных под большинство почерков Что нужно: Нужно их сравнить!!!

Автор: maxim1000 20.4.2004, 17:13

а, может, как-то ввести понятие буквы... как мне кажется снижение количества возможных решений может хорошо сказаться на качестве распознавания... конечно, для слова способ, предложенный мной не подходит (его сложность приблизительно n!, а в слове куча линий) вообще, думаю, надо ввести правило упорядочивания отрезков и предусмотреть изменение порядка при разных написаниях слов (возможно, с помощью какой-нибудь вероятностной модели) чем удачнее будет выбрано правило, тем меньше придется рассматривать возможных отклонений, а значит, вычислительная сложность тоже будет меньше...

Автор: podval 20.4.2004, 20:33

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

Автор: maxim1000 21.4.2004, 10:53

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

Автор: B2_Russia 22.4.2004, 23:42

Да рубяты, вообще то нет ни одного толкового алгоритма выявления местоположения букв в слове... Все сводится восновном к некоторому перебору в некоторой обрасти... Так или иначе идея собственно не в этом... Слова как таковые мы уже знаем как распознавать, дело остается это все проконтролировать, то есть дублирующее распознавание... Конечно ветод проверки по словарю не особенно подходит хотябы потому что слов в этом словаре порядка 200000 и соответственно это крутовато для сегодняшних ПК. К счастью словарь есть возможность сузить по каким то уже известным параметрам распознаваемого слова. Вооот... ЧТо буквы поотдельности распознавать нельзя - это точно... Однако, но и ставить в соответствие ей какой-то процент тоже не совсем подходит... Все дело в том, что в большинстве случаев буквы сливаются и распознать их можно только по их сочетаниям а не поотдельности... Такие пироги. Кстати говоря метод предложенный podval-ом в нашей приватной беседе оказался вполне эффективным... Всвязи с этим появился правда следующий вопрос... Как сравнить 2 траектории движения, или точнее 2 полилинии? Они могут быть подобны, но при этом отличаться по длине, у какой то из них может отсутствовать элемент присутствующий в другой... ЗЫ: Нужен толковый человек для совместного проекта связанного с распознаванием рукописного текста!!!

Автор: maxim1000 23.4.2004, 10:35

Цитата Как сравнить 2 траектории движения, или точнее 2 полилинии? я уже где-то тут описывал сравнение двух последовательностей с помощью метода динамического программирования (и не только я, кажется) по-моему, он тут может очень пригодиться а в качестве общего подхода я бы предложил: 1. изучить какие искажения могут быть в одной последовательности по сравнению с другой 2. построить вероятностную модель этих искажений 3. оценивать вероятности того, что эти последовательности были сгенерированы одним источником

Автор: podval 23.4.2004, 19:48

Цитата Как сравнить 2 траектории движения, или точнее 2 полилинии? Накапливать отрицательную Log вероятность и брать траекторию с максимальным значением. Такое извращение принято, чтобы не умножать вероятности - слишком мелкие числа получаются Вобщем поищи ссылки по таким запросам: - Viterbi search (Viterbi decoding) algorithm; - beam search; - stack algorithm.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)