GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (2)След. > >>   Поиск:  
 Автор Тема: Распознование образов в одномерном пространстве - от простого к сложному
Следопыт
Сообщений: 35
Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 18:27

Недавно появился топик о проблеме распознования дискретного изображения квадратика на двумерном поле с помощью НС. При смещении изображения на один пиксел в любую сторону, НС неизбежно начинает понижать степень узнаваемости. Проблема решается разными алгоритмами предварительной корректировки. Однако это не решает 100% данную проблему.
Я предлагаю для упрощения задачи перейти от двухмерного массива данных к одномерному, что позволить "отработать" методы распознования.

Пример:
дан дискретный массив:
00000001010111001100000
распознать три идущих подряд еденицы (111)

Метод скользящего окна не предлагать!


[Ответ][Цитата]
Следопыт
Сообщений: 35
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 18:38
Sorry, медленный инет, два топика получилось. Рабочий вариант здесь.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 18:48
Цитата:
Автор: Следопыт


Недавно появился топик о проблеме распознования дискретного изображения квадратика на двумерном поле с помощью НС. При смещении изображения на один пиксел в любую сторону, НС неизбежно начинает понижать степень узнаваемости. Проблема решается разными алгоритмами предварительной корректировки. Однако это не решает 100% данную проблему.
Я предлагаю для упрощения задачи перейти от двухмерного массива данных к одномерному, что позволить "отработать" методы распознования.

Пример:
дан дискретный массив:
00000001010111001100000
распознать три идущих подряд еденицы (111)

Метод скользящего окна не предлагать!



Ну это не совсем тоже, что решает ИНС. Вы пытаетесь точный квадратик найти, а ИНС нужна, что бы распознать не совсем точный квадрат, а "похожий" на него.

Что же касается вашей задачи: Это целое направление алгоритмики (причем не ИИ).
Называется patterns matching. Очень серьёзная тема. Усложнять можно до "опупения".
Вы предлагаете самый простой вариант этой задачи. Есть решения за линейное время.
Если не ошибаюсь, они сам патерн переводят в автомат и начинает сравнивать по нему. Это предотвращает проверки лишних символов (эквивалент отсечению в minmax алгоритме, если кому так проще представить)
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 18:51
кроме того, таким способом вы не только квадрты распознаете! важно ведь и размерность бывшей матрицы. Да и к слову, ИНС тоже работает с одномерным массивом (т.е. она не знает, сколько мерность у образа)
[Ответ][Цитата]
Следопыт
Сообщений: 35
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 18:55
Цитата:
Автор: daner
Что же касается вашей задачи: Это целое направление алгоритмики (причем не ИИ).
Называется patterns matching. Очень серьёзная тема. Усложнять можно до "опупения".
Вы предлагаете самый простой вариант этой задачи. Есть решения за линейное время.
Если не ошибаюсь, они сам патерн переводят в автомат и начинает сравнивать по нему. Это предотвращает проверки лишних символов (эквивалент отсечению в minmax алгоритме, если кому так проще представить)


А поподробнее можно? Если не в тягость знаниями поделится, с примерами и т.п.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 19:03
Цитата:
Автор: Следопыт
А поподробнее можно? Если не в тягость знаниями поделится, с примерами и т.п.

А вы думаете я помню наизусть все алгоритмы которые я когда-то учил? вы слишком хорошего обо мне мнения.
Нет, простите, не помню. да и алгоритмы не в одну строчку.
Но это вещи стандартные, так что поищите в интернет, там должно быть масса примеров и прочего.

Вот посмотрите здесь. Тут и ссылки на алгоритмы есть.
http://en.wikipedia.org/wiki/String_searching_algorithm
[Ответ][Цитата]
Следопыт
Сообщений: 35
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 19:16

Да дело не в том, чтоб ссылку дать, а помочь себе и другим разобратся.
Вот поиск строки предлагаете. Разберемся подробнее.
Вы утверждали, что НС с этим справится, ибо сети всеравно, она незнает с каким массивом она работает... Однако! Получается что можно и наоборот: двумерный массив представить в виде одной строки, а распозноваемый образ как искомую строку.
Неплохой способ, кстати для поиска черного квадратика.
Но для немного_отличающихся образов, и одномерных тоже, побитовое сравнение не даст искомого результата.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 19:34
Цитата:
Автор: Следопыт
Да дело не в том, чтоб ссылку дать, а помочь себе и другим разобратся.

Нет, спасибо сказать... мне надо будет, я пойду по этой же ссылки, и начну разбираться. Если сложность алгоритмов не доказывать, то сами они не супер какие сложные.

Цитата:
Автор: Следопыт
Вы утверждали, что НС с этим справится, ибо сети всеравно, она незнает с каким массивом она работает...

Я такого не утверждал. Я просто констатировал, что ИНС тоже работает с одномерным массивом.

Цитата:
Однако! Получается что можно и наоборот: двумерный массив представить в виде одной строки, а распозноваемый образ как искомую строку.

Что то, я вас не понимаю. А почему "наоборот"? Вы до разве другое "до этого" предлагали?

Цитата:
Неплохой способ, кстати для поиска черного квадратика.
Но для немного_отличающихся образов, и одномерных тоже, побитовое сравнение не даст искомого результата.

Верно. Но это вы же задачу дали. Я кстати, об этом уже написал выше. Вы просто пропустили. А для "немного_отличающихся", надо применять не четкое сравнение. Кстати, на форуме это уже обсуждалось и алгоритмов в инете для этого тоже не мало.

Разница между ИНС и таким подходом в том, что ИНС сама по себе универсальна. Т.е. взял ИНС, взял ОБРАЗ/Ы обучил ИНС (ну с доп. настройками) и все. А в том, что вы предлагаете, надо заранее знать, что ищем квадратик. Можно конечно искать вообще предлагаемый образ. Но опят таки, тут решений стандартных тьма будет. Каждый хорош и плох по своему.

Хочу заметить, я не предлогал, как именно решать проблему смещённого квадрата (т.е. свое мнение по этому поводу, я написал в другом топике). Здесь, вы дали конкретную задачу, а я дал конкретное решение (т.е. ссылку на него).

П.С.
Если вам ссылки на известные подходы не нравятся, то я тогда не пойму что вам надо? Совместными усилиями колесо очередное изобрести? Тогда я пасс.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 19:40
Вообще, то что Вы описываете сильно смахивает на поиск подстроки в строке. Для этого существует довольно много алгоритмов.
Можете посмотреть здесь:
http://algolist.manual.ru/search/esearch/
http://rsdn.ru/article/alg/textsearch.xml
Да и вобще через гугл можно оч много всякого по этой теме найти.
[Ответ][Цитата]
Следопыт
Сообщений: 35
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 19:56
Цитата:
Автор: daner
Я такого не утверждал. Я просто констатировал, что ИНС тоже работает с одномерным массивом.

Ага, здесь я ошибся
Цитата:
Автор: daner
Что то, я вас не понимаю. А почему "наоборот"? Вы до разве другое "до этого" предлагали?

Я неправильно понял высказывание, поэтому ошибочка вышла.

А вот дальше:
Цитата:
Автор: daner
Разница между ИНС и таким подходом в том, что ИНС сама по себе универсальна. Т.е. взял ИНС, взял ОБРАЗ/Ы обучил ИНС (ну с доп. настройками) и все. А в том, что вы предлагаете, надо заранее знать, что ищем квадратик. Можно конечно искать вообще предлагаемый образ. Но опят таки, тут решений стандартных тьма будет. Каждый хорош и плох по своему.


НС неуниверсальна уже тем, что она сама по себе просто неможет элементарно найти искомый объект, хотя в распозновании она справляется более-менее. Цель моя найти альтернативу - распознать обьект, вне зависимости от месторасположения его на матрице.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 03 янв 08 20:35
Цитата:
Автор: Следопыт
Цитата:
Автор: daner
Разница между ИНС и таким подходом в том, что ИНС сама по себе универсальна. Т.е. взял ИНС, взял ОБРАЗ/Ы обучил ИНС (ну с доп. настройками) и все. А в том, что вы предлагаете, надо заранее знать, что ищем квадратик. Можно конечно искать вообще предлагаемый образ. Но опят таки, тут решений стандартных тьма будет. Каждый хорош и плох по своему.

НС неуниверсальна уже тем, что она сама по себе просто неможет элементарно найти искомый объект, хотя в распозновании она справляется более-менее. Цель моя найти альтернативу - распознать обьект, вне зависимости от месторасположения его на матрице.

Я не имел ввиду, что ни универсальны, в плане что решают что хочешь. Т.е. да универсальны, как подход, но реально конечно нет.

Под универсальностью, я имел ввиду другое. Я говорил о том, что ИНС обучается.
Т.е. не мы задаём, что такое "похоже", а сеть сама пытается это определить.
Ведь в сущности, есть алгоритм "близких соседей". Т.е. обучение заключается в том, что ты просто сохраняешь все обуч. образы в базе. Потом берёшь тестовый образ, сравниваешь со всеми обуч.образами и выбираешь самый близкий, по какому-то кретерию (наприм. расстояние хемминга). Но это эвристический подход. А ИНС она не требует от вас эвристики, она ее сама ищет.
[Ответ][Цитата]
Buggy
Сообщений: 28
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 04 янв 08 0:40
Цитата:
Автор: daner


Я не имел ввиду, что ни универсальны, в плане что решают что хочешь. Т.е. да универсальны, как подход, но реально конечно нет.

Под универсальностью, я имел ввиду другое. Я говорил о том, что ИНС обучается.
Т.е. не мы задаём, что такое "похоже", а сеть сама пытается это определить.
Ведь в сущности, есть алгоритм "близких соседей". Т.е. обучение заключается в том, что ты просто сохраняешь все обуч. образы в базе. Потом берёшь тестовый образ, сравниваешь со всеми обуч.образами и выбираешь самый близкий, по какому-то кретерию (наприм. расстояние хемминга). Но это эвристический подход. А ИНС она не требует от вас эвристики, она ее сама ищет.


Создать ИНС которая распознаст объекты, на которые её обучили прощще простого. Меня вот интересует фраза "А ИНС она не требует от вас эвристики, она ее сама ищет". Если можно поподробней.
Ведь дело не в распозновании образа, дело в том как вобще сконструировать такую ИНС которая бы сказала что данный образ присутствует в данной матрице среди других образов.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 04 янв 08 3:26
Цитата:
Автор: Buggy
Создать ИНС которая распознаст объекты, на которые её обучили прощще простого. Меня вот интересует фраза "А ИНС она не требует от вас эвристики, она ее сама ищет". Если можно поподробней.
Ведь дело не в распозновании образа, дело в том как вобще сконструировать такую ИНС которая бы сказала что данный образ присутствует в данной матрице среди других образов.

Эвристика -- есть оценочная функция. Т.е. функция которая дает оценку чему-то. Вот если мы жёстко зададим функцию похожести как расстояние хемминга, то это будет наша эвристика при распознавании образа. Что делает ИНС в процессе обучения? Она подбирает функцию разделитель для нескольких классов (образов). Т.е. другими словами, она "придумывает" функцию похожести, т.е. эвристику сравнения.
Вот это я и хотел сказать. Не смотря на то, что теоретически ИНС эквивалентны МТ, т.е. могут решать все что угодно, и теоретически, они могут представить любую функцию разделитель, на самом деле есть некоторые сложности с этим делом.
Во-первых, алгоритм обучения влияет на скорость. Кому интересно обучать сеть черти сколько лет? с другой стороны, размер сети... Вся эта теория для бесконечных сетей. Думаю не надо объяснять что это значит? И в третьих, само пространство должно соответствовать задачи. Нельзя распознать самовар перед вами или просто чайник, если пространство на котором идет определение ... например запахи!
Поэтому, для того что бы сеть распознавала объекты внутри образа, надо производить трансформации. Как об этом уже и говорилось.

Но хочу заметить. ИНС -- не единственный способ машинного обучения. Есть и другие и их не мало. Да и вообще, не всегда нужно именно обучение. Иногда достаточно и эвристики, на основе которой можно просто сравнить требуемые образы.
[Ответ][Цитата]
Nikolay
Сообщений: 26
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 04 янв 08 9:34
Цитата:
Автор: Следопыт


Недавно появился топик о проблеме распознования дискретного изображения квадратика на двумерном поле с помощью НС. При смещении изображения на один пиксел в любую сторону, НС неизбежно начинает понижать степень узнаваемости. Проблема решается разными алгоритмами предварительной корректировки. Однако это не решает 100% данную проблему.
Я предлагаю для упрощения задачи перейти от двухмерного массива данных к одномерному, что позволить "отработать" методы распознования.

Метод скользящего окна не предлагать!


Вот публикации, которые возможно вызовут Ваш интерес:

Казанович Я.Б., Борисюк Р.М. (2005) Осцилляторная нейросетевая модель слежения
за движущимся объектом. Нейроинформатика-2005. VII Всероссийская
научно-техническая конференция, т. 1. Москва, МИФИ. с. 25-35.

Более свежая:

Казанович Я.Б., Борисюк Р.М. Нейросетевая модель слежения за несколькими
объектами (1. Институт математических проблем биологии РАН, Пущино, Московская область, yakov_k@impb.psn.ru , 2. Центр теоретической и вычислительной нейробиологии, Университет г. Плимут, Плимут, Великобритания, rborisyuk@plymouth.ac.uk).

Аннотация.
Психологические эксперименты показывают, что человек способен одновременно следить за пятью независимо перемещающимися зрительными объектами. В данной работе предлагается нейросетевая модель этого феномена. Модель работает с набором идентичных зрительных объектов, движущихся в заданном поле. На начальном этапе функционирования при неподвижных объектах модель выбирает в фокус внимания подмножество объектов, которые исходно заданы как целевые. Остальные объекты считаются дистракторами, отвлекающими внимание от слежения за целевыми объектами. В дальнейшем при движении объектов модель должна по возможности сохранять начальное разделение объектов на целевые и дистракторы. Идея реализации модели состоит в использовании многослойной осцилляторной сети, в которой каждый слой предназначен для слежения за одним целевым объектом. Будет показано, что одновременное слежение за несколькими объектами может быть реализовано при подходящем выборе синхронизующих/десинхронизующих взаимодействий между слоями. Результаты имитационного моделирования показывают, что в случае непересекающихся объектов вероятность ошибки слежения (принятие дистрактора за целевой объект или целевого объекта за дистрактор) возрастает при увеличении числа дистракторов. Такая зависимость имеет место и в психологических экспериментах. Кроме того, будет описано поведение модели в случае работы с пересекающимися объектами.

Одновременное сопровождение 5 выделенных движущихся объектов на фоне других мешающих объектов, наверное, покруче, чем распознавание одного перемещающегося квадрата. Но ведь решена! Но это совсем другая сказка! Статьи доступны в яндексе. Успехов!
[Ответ][Цитата]
daner
Сообщений: 4593
На: Распознование образов в одномерном пространстве - от простого к сложному
Добавлено: 04 янв 08 14:21
Nikolay, я не большой специалист по ИНС. Но в последнее время на форумах стали много говорить об осцелирующих нейронах.
Можете в двух словах, описать разницу между обычными нейронами (Розенблата, Хеба и т.д.) и вот этими осцилирующими.
Понятно, что в интернете можно найти все это, но хотелось бы просто кратко, понять разницу, не вдаваясь в детали.
[Ответ][Цитата]
 Стр.1 (2): [1]  2След. > >>