Математическая практическая задача, можно отнести к ИИ

Здесь находятся темы форума, утратившие актуальность

Модератор: Администраторы

Математическая практическая задача, можно отнести к ИИ

Сообщение Dimmy » Чт май 11, 2006 8:50:29

Может я уже и постарел, но есть следующая задача.
Ее можно отнести к ИИ т.к. тут есть хоть чуть но распознавание образов...

Суть:
Есть картинка - что-то намулеванное. И на этой картинке - прямоугольник,толщиной в 5 пикселей черного цвета. Он может быть под наклоном к листу.

Как найти координаты вершин прямоугольника? Дело в том что на рисунке могут быть и другие линии, но прямоугольник - все один.

Интересует алгоритм. На любом языке. Можно схематично.
Напр-р:
for x:=1 to bmp.width do
a:=bmp.pixel[x,y]... и т.д.


P.S. :oops:
Vivere est cogitare!
"Во время работы в одиночестве человек в идеале находится в состоянии, которое психологи называют потоком."
Осознать необъятное, объять неосознанное (с) Dimmy, 2008
Делать возможным то, что другие считают невероятным (с) Dimmy, 2009
"Когда люди предпочитают верить, а не знать - наступает время шарлатанов." Академик Эдуард Кругляков.
Главная задача ИИ — не выиграть у игрока, а красиво ему отдаться. (с) Тимур Бухараев, Nival
«Никогда не ошибается тот, кто ничего не делает» Т. Рузвельт

...хожу сам по себе :)
ИзображениеИзображение
Dimmy
Эксперт ИИ
 
Сообщения: 555
Зарегистрирован: Пт янв 14, 2005 17:11:17
Откуда: РнД

Re: Математическая практическая задача, можно отнести к ИИ

Сообщение Sangril » Чт май 11, 2006 12:26:10

Dimmy писал(а):Суть:
Есть картинка - что-то намулеванное. И на этой картинке - прямоугольник,толщиной в 5 пикселей черного цвета. Он может быть под наклоном к листу.

Как найти координаты вершин прямоугольника? Дело в том что на рисунке могут быть и другие линии, но прямоугольник - все один.


Давайте все-таки сформулируем задачу.
Есть матрица значений 0 и 1 представляющая собой изображение.
Найти в этой матрице фигуру, при нужном повороте в которую можно вписать горизонтальный прямоугольник из нулевых пикселей 5ти пикселей высотой. Указать координаты точек, перешедших в вершины прямоугольника.

Правильно ли я понял задачу? Тут просто есть множество проблем с растеризацией и вписыванием (5 пикселей все же очень мало). Ну и решение может быть не единственно.
Sangril
Заинтересованный
 
Сообщения: 63
Зарегистрирован: Пн июл 04, 2005 19:17:50

Сообщение Михайло » Чт май 11, 2006 15:38:36

Но эта задача не является даже приложением к ИИ. Это простая переборная задача.
Я специалист по неопределенности!
Аватара пользователя
Михайло
Полноправный участник
 
Сообщения: 904
Зарегистрирован: Пт окт 07, 2005 15:20:05
Откуда: Нижний Тагил

Сообщение Sangril » Чт май 11, 2006 16:03:28

Михайло писал(а):Но эта задача не является даже приложением к ИИ. Это простая переборная задача.


А почему вы считаете, что "приложения к ИИ" нельзя свести к простой переборной задаче?
Sangril
Заинтересованный
 
Сообщения: 63
Зарегистрирован: Пн июл 04, 2005 19:17:50

Сообщение Михайло » Чт май 11, 2006 20:41:17

Sangril писал(а):
Михайло писал(а):Но эта задача не является даже приложением к ИИ. Это простая переборная задача.


А почему вы считаете, что "приложения к ИИ" нельзя свести к простой переборной задаче?


Я не говорил, что интеллектуальные приложения нельзя свести к какой-нибудь переборной задаче, я вроде как сказал, что данную переборную задачу нельзя считать интеллектуальной.
Я специалист по неопределенности!
Аватара пользователя
Михайло
Полноправный участник
 
Сообщения: 904
Зарегистрирован: Пт окт 07, 2005 15:20:05
Откуда: Нижний Тагил

1

Сообщение Dimmy » Пт май 12, 2006 8:19:47

это не переборная задача.
каким это образос вы переберете все и найдете лежащий на боку прямоугольник среди просто отрезков???
Vivere est cogitare!
"Во время работы в одиночестве человек в идеале находится в состоянии, которое психологи называют потоком."
Осознать необъятное, объять неосознанное (с) Dimmy, 2008
Делать возможным то, что другие считают невероятным (с) Dimmy, 2009
"Когда люди предпочитают верить, а не знать - наступает время шарлатанов." Академик Эдуард Кругляков.
Главная задача ИИ — не выиграть у игрока, а красиво ему отдаться. (с) Тимур Бухараев, Nival
«Никогда не ошибается тот, кто ничего не делает» Т. Рузвельт

...хожу сам по себе :)
ИзображениеИзображение
Dimmy
Эксперт ИИ
 
Сообщения: 555
Зарегистрирован: Пт янв 14, 2005 17:11:17
Откуда: РнД

Re: 1

Сообщение Михайло » Пт май 12, 2006 15:06:31

Dimmy писал(а):это не переборная задача.
каким это образос вы переберете все и найдете лежащий на боку прямоугольник среди просто отрезков???

Перебрать все координаты левой верхней точки (x,y) прямоугольника и все прямоугольники с размерами a и b. 1<a<m-x, 1<b<n-y, где m и n - размеры картинки. Примерно так перебирается "горизонтальный" прямоугольник.
Для прямоугольников, расположенных под углом к "горизонту", нужно еще ввести для перебора угол альфа. -90<альфа<90 град.
Я специалист по неопределенности!
Аватара пользователя
Михайло
Полноправный участник
 
Сообщения: 904
Зарегистрирован: Пт окт 07, 2005 15:20:05
Откуда: Нижний Тагил

Re: 1

Сообщение tumick » Пт май 12, 2006 15:28:36

Михайло писал(а):Примерно так перебирается "горизонтальный" прямоугольник.


Что инетерсно - мозг ведь решает эту задачу очень похожим способом. С той лишь разницей, что гипотезы эти проверяются не последовательно, а параллельно - все за один раз.
Мозг - это такой орган, с помощью которого мы думаем, что мы думаем.
Аватара пользователя
tumick
Серьёзный посетитель
 
Сообщения: 149
Зарегистрирован: Пт мар 10, 2006 12:27:57
Откуда: Киев

Re: 1

Сообщение Sangril » Пт май 12, 2006 15:54:01

Михайло писал(а):Перебрать все координаты левой верхней точки (x,y) прямоугольника и все прямоугольники с размерами a и b. 1<a<m-x, 1<b<n-y, где m и n - размеры картинки. Примерно так перебирается "горизонтальный" прямоугольник.
Для прямоугольников, расположенных под углом к "горизонту", нужно еще ввести для перебора угол альфа. -90<альфа<90 град.


Все может быть не так просто - возможно моя переформулировка неверна. И достаточно ли поворачивать на 1 градус (для больших картинок не очевидно). Надо решать задачу о погрешностях - вычислять для размера картинки количество центров и мин. повороты, чтобы погрешность быля меньше пикселя.

Можно пытаться для точки вычислять радиус и перпендикуляр к нему (точнее интервал в который попадает перпендикуляр для радиусов >2.5), а потом попытаться пересечь интервалы у соседних точек.
Sangril
Заинтересованный
 
Сообщения: 63
Зарегистрирован: Пн июл 04, 2005 19:17:50

1

Сообщение Dimmy » Пт май 12, 2006 17:02:42

это неверные решения. почему? сейчас поясню.

мы УЗНАЕМ образ прямоугольника.

Вот как по вашему, китайцы и японцы свои чудо-иероглифы перебором вычисляют??? :) Ага Щаззззз. :P

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

Вот например вот это чудо http://passport.yandex.ru/digits?idkey= ... 55b371ca3a
мы что? перебором узнаем? Не в жизь! :)

Только забудьте о нейросетях. на приведенном примере http://passport.yandex.ru/digits?idkey= ... 55b371ca3a
ни одна нейросеть не поможет.

Вот инетерсны еще идеи, кроме перебора по нахождению просто прямоугольника.
Vivere est cogitare!
"Во время работы в одиночестве человек в идеале находится в состоянии, которое психологи называют потоком."
Осознать необъятное, объять неосознанное (с) Dimmy, 2008
Делать возможным то, что другие считают невероятным (с) Dimmy, 2009
"Когда люди предпочитают верить, а не знать - наступает время шарлатанов." Академик Эдуард Кругляков.
Главная задача ИИ — не выиграть у игрока, а красиво ему отдаться. (с) Тимур Бухараев, Nival
«Никогда не ошибается тот, кто ничего не делает» Т. Рузвельт

...хожу сам по себе :)
ИзображениеИзображение
Dimmy
Эксперт ИИ
 
Сообщения: 555
Зарегистрирован: Пт янв 14, 2005 17:11:17
Откуда: РнД

Re: 1

Сообщение tumick » Пт май 12, 2006 17:57:56

Dimmy писал(а):Вот например вот это чудо http://passport.yandex.ru/digits?idkey= ... 55b371ca3a


HTTP Error 404 - Not Found

Dimmy писал(а):мы что? перебором узнаем?


Я не знаю, можно ли назвать перебором одновременное сравнение сигнала со всем множеством "хранимых" образцов. Последовательное сравнение - да, это перебор. Но принципиальной разницы я не вижу. Вы видите?
Мозг - это такой орган, с помощью которого мы думаем, что мы думаем.
Аватара пользователя
tumick
Серьёзный посетитель
 
Сообщения: 149
Зарегистрирован: Пт мар 10, 2006 12:27:57
Откуда: Киев

Re: 1

Сообщение Михайло » Сб май 13, 2006 4:15:58

Dimmy писал(а):Вот как по вашему, китайцы и японцы свои чудо-иероглифы перебором вычисляют??? :) Ага Щаззззз. :P

Вы сказали, что прямоугольник толщиной 5 пикселей, я так понял он без искажений, т.е. без белых точек на линиях.

Dimmy писал(а):Вот например вот это чудо http://passport.yandex.ru/digits?idkey= ... 55b371ca3a
мы что? перебором узнаем? Не в жизь! :)

Здесь наверное была картинка для регистрации в почте яндекс?
Я специалист по неопределенности!
Аватара пользователя
Михайло
Полноправный участник
 
Сообщения: 904
Зарегистрирован: Пт окт 07, 2005 15:20:05
Откуда: Нижний Тагил

1

Сообщение Dimmy » Сб май 13, 2006 9:14:04

да. ссылка на яндексовую картинку при регистрации.

а в моей задаче: картинка, с кучей лишних линий, но приямоугольник только один. ширина 5пк , черный на белом.
Vivere est cogitare!
"Во время работы в одиночестве человек в идеале находится в состоянии, которое психологи называют потоком."
Осознать необъятное, объять неосознанное (с) Dimmy, 2008
Делать возможным то, что другие считают невероятным (с) Dimmy, 2009
"Когда люди предпочитают верить, а не знать - наступает время шарлатанов." Академик Эдуард Кругляков.
Главная задача ИИ — не выиграть у игрока, а красиво ему отдаться. (с) Тимур Бухараев, Nival
«Никогда не ошибается тот, кто ничего не делает» Т. Рузвельт

...хожу сам по себе :)
ИзображениеИзображение
Dimmy
Эксперт ИИ
 
Сообщения: 555
Зарегистрирован: Пт янв 14, 2005 17:11:17
Откуда: РнД

1

Сообщение Dimmy » Сб май 13, 2006 9:34:38

и кстати, раз уж затронул, а как же быть вообще с иероглифами?

как японцы их узнают?
Vivere est cogitare!
"Во время работы в одиночестве человек в идеале находится в состоянии, которое психологи называют потоком."
Осознать необъятное, объять неосознанное (с) Dimmy, 2008
Делать возможным то, что другие считают невероятным (с) Dimmy, 2009
"Когда люди предпочитают верить, а не знать - наступает время шарлатанов." Академик Эдуард Кругляков.
Главная задача ИИ — не выиграть у игрока, а красиво ему отдаться. (с) Тимур Бухараев, Nival
«Никогда не ошибается тот, кто ничего не делает» Т. Рузвельт

...хожу сам по себе :)
ИзображениеИзображение
Dimmy
Эксперт ИИ
 
Сообщения: 555
Зарегистрирован: Пт янв 14, 2005 17:11:17
Откуда: РнД

Сообщение tumick » Сб май 13, 2006 18:18:02

Хорошо, предлагаю вариант решения. Это никакое не ноу-хау, поскольку "подсмотрено" у мозга человека. Реализаций этого алгоритма тоже существует много. Честно говоря, я даже удивился, что народ так вяло на эту задачу отреагировал - она ведь сравнительно простая (на сегодня), и давно решена. Причём разными способами. Приведу вкратце тот из них, который (ИМХО) наиболее напоминает обработку сигнала зрительной корой. Сетчатку с её тремором и прочими эффектами - не рассматриваем, так как по условию задачи раст чёрно/белый, даже без оттенков серого.

Итак:

1) В каждой точке исходного растра размещаем "пиксельный датчик".

2) Показания датчика определяются так: берём "бревно" - чёрный прямоугольник размером 10х5, помещаем его центр масс в точку расположения датчика (горизонтально) и вращаем на 180°, с интервалом например в 5° (выбор интервала зависит от толщины линий искомого прямоугольника и и желаемой точности решения задачи). На каждой итерации вращения "накладываем" наше бревно на исходный растр, и определяем "степень соответствия" (т.е. среди всех пикселей растра, "накрытых" бревном хотябы наполовину, подсчитываем количество чёрных). Показанием "датчика" в данной точке будем считать значение угла, при котором "степень соответствия" максимальна. Если при нескольких разных углах она одинакова и это значение максимально - то такой датчик имеет сразу несколько показаний, ни одно из них не отбрасываем, все запоминаем.

3) Для каждого значения угла А в диапазоне от 0 до 90°, с шагом в 5° (о шаге см. выше) формируем сетку. Сетка состоит из всех прямых, образующих с положительной полуосью Х угол А (для определённости - против часовой стрелки), а также перпендикуляных им, причём отстоящих друг от друга на 1 пиксель, и пересекающих исходный растр отрезком длиной не менее 5 пикселей. Для каждого конкретного угла А такую сетку назовём "семейством" А.

4) В каждом семействе, построенном в предыдущем пункте, на каждую прямую этого семейтсва вешаем "линейный датчик". Показания датчика отпределяются так: максимальная продолжительность (в пикселях) отрезка, в каждом пикселе которого показания пиксельного датчика совпадают с углом А (или А+90° - для перпендикулярных прямых сетки).

5) Проходим снова по прямым и оставляем показания только тех линейных датчиков, для которых показания датчика этой прямой, двух предыдущих и двух последующих прямых семейства - сходны. (2+1+2=5 пикселей, ширина линии по условию задачи). Остальные обнуляем.

6) Теперь всё готово, находим наши прямоугольники. Все, которые на растре есть. Дальше очевидно, или ещё расписать?..

P.S. Если требуется найти один, и известно что он на картинке только один - задача будет решаться более точно, так как "кандидатов" может возникать несколько, и мы из них всех выбираем тот, оценка которого по показаниям "датчиков" максимальна.

P.P.S. Ресурсоёмкость этого метода решения очень высока. Что поделать, у мозга нейронов вон сколько, а у компьютера процессор всего один :(
Мозг - это такой орган, с помощью которого мы думаем, что мы думаем.
Аватара пользователя
tumick
Серьёзный посетитель
 
Сообщения: 149
Зарегистрирован: Пт мар 10, 2006 12:27:57
Откуда: Киев

Сообщение Левич » Вс май 14, 2006 11:53:05

tumick

>>>Хорошо, предлагаю вариант решения. Это никакое не ноу-хау, поскольку "подсмотрено" у мозга человека.

Похоже, нужно просто мозги вам вправить.

>>> Это даёт нам возможность распознать квадрат, даже если он находится на заднем плане и частично перекрыт другими фигурами. Вот как раз эту "дорисовку" я считаю первичной зрительной абстракцией, которую хотелось бы реализовать на практике на первом этапе.

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

>>> В каждой точке исходного растра размещаем "пиксельный датчик".

А растр само по себе как явление не несет информации? Зачем датчик?

>>> P.S. Если требуется найти один, и известно что он на картинке только один - задача будет решаться более точно, так как "кандидатов" может возникать несколько, и мы из них всех выбираем тот, оценка которого по показаниям "датчиков" максимальна.

Бред.

>>> P.P.S. Ресурсоёмкость этого метода решения очень высока. Что поделать, у мозга нейронов вон сколько, а у компьютера процессор всего один

Не путайте, процессоров много, из них можно собрать несколько видов конфигураций компов. Проблема только в конкретных объектах, точнее в дилерах. Вам, например, заплатят только за продвижение определенной линейки. А уж чтобы продать простой камень, расписываете характеристики так, будто там внутри живет сам ИИ. Примитивно и глупо.
Идиоты с мембраны.ру той же х-ной маются.
ом рам
Левич
Заинтересованный
 
Сообщения: 20
Зарегистрирован: Вт апр 04, 2006 21:41:21

Сообщение tumick » Вс май 14, 2006 12:37:44

Народ, в который раз уже прошу - уберите отсюда этого гиганта мысли! :evil: :evil: :evil:
Мозг - это такой орган, с помощью которого мы думаем, что мы думаем.
Аватара пользователя
tumick
Серьёзный посетитель
 
Сообщения: 149
Зарегистрирован: Пт мар 10, 2006 12:27:57
Откуда: Киев

Сообщение Гость » Вс май 14, 2006 20:56:50

Сделал
Гость
 

1

Сообщение Dimmy » Пн май 15, 2006 9:57:16

tumick писал(а):Народ, в который раз уже прошу - уберите отсюда этого гиганта мысли! :evil: :evil: :evil:


С одной стороны согласен, с другой - нет.
Критика - полезна.
Только в других словах...

По поводу алгоритма: поворачивать бревно на 5 гр - это один цикл.
второй цикл - длина ребра.
третий (все вложенные) - это ширина.
четвертый - это изменение координаты Х левого нижнего угла "бревна".
пятый - эито изменение координаты У.

4 и 5-ый для того, так как мы не уверены, что расположение бревна в центре масс даст достаточно верный ответ, не факт, что бревно "наложится" на искомый прямоугольник как шаблон.

К чему это пишу: BMP размером 800x600 хотя бы.
1) 360/5 = 72 итерации первого цикла
2) 1..600 (хотя бы)
3) 1..500 (хотя бы)
4) 1..800
5) 1..600

итого 72*600*500*800*600 = 10368000000000.

И на каком процессоре такое считать будем?.. :)
По поводу работы мозга. Считаю что он действует не так. Не много не так.

Любой объект, "узнаваемый" на картинке уже заложет в памяти человека, и идет соответствие.

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

Причем обрачу внимание, что есть люди, которые с трудом это делают. Этот называется какой-то болезнью.

Алгоритм считаю неверным.
Vivere est cogitare!
"Во время работы в одиночестве человек в идеале находится в состоянии, которое психологи называют потоком."
Осознать необъятное, объять неосознанное (с) Dimmy, 2008
Делать возможным то, что другие считают невероятным (с) Dimmy, 2009
"Когда люди предпочитают верить, а не знать - наступает время шарлатанов." Академик Эдуард Кругляков.
Главная задача ИИ — не выиграть у игрока, а красиво ему отдаться. (с) Тимур Бухараев, Nival
«Никогда не ошибается тот, кто ничего не делает» Т. Рузвельт

...хожу сам по себе :)
ИзображениеИзображение
Dimmy
Эксперт ИИ
 
Сообщения: 555
Зарегистрирован: Пт янв 14, 2005 17:11:17
Откуда: РнД

Re: 1

Сообщение victorst » Пн май 15, 2006 10:16:21

Dimmy писал(а):Алгоритм считаю неверным.
Поэтому много лет назад я отказался от решения перцептивных задач (распознавание изображений объектов, устной речи и т.д.). Я решил к этим задачам подойти с другой стороны. Нужно убрать из своей работы по созданию ИИ все то, что создает дополнительные трудности и общую трудоемкость только умножает. Последнее, от чего я отказался - понимания письменной речи на ЕЯ. Я сосредоточился на тех механизмах, которые могут использоваться наиболее часто. В их число входит и воображение (фантазия), и творчество, основанное на воображении.
В противном случае вычислительные и др. технические трудности просто не дадут возможности перейти на более абстрактный уровень обработки информации. Системы распознавания лиц террористов в аэропортах по изображениям видео и фотокамер при всей шумихе об успехах, демонстрируют огромный процент ошибок. Это как прогноз погоды. Если точность прогноза близка к 50%, то это вообще не прогноз.
Решив постепенно одни задачи ИИ, можно во всеоружии подступаться к задачам распознавания образов по изображениям.
Повторяю, я ничего никому не доказываю и не навязываю. Говорю только о своем мнении.
AIGL - язык ИИ: http://www.aigl.org
Аватара пользователя
victorst
Полноправный участник
 
Сообщения: 1073
Зарегистрирован: Вс янв 09, 2005 22:36:18
Откуда: Россия, г.Омск

След.

Вернуться в Архив тем

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


cron


Rambler's Top100 Каталог ресурсов ListTop.Ru Каталог сайтов Союз образовательных сайтов Parenting.ru - Родители семья дети ребенок

     Сайт "Искусственный интеллект" - программирование ИИ от разработчика: общение, статьи, ссылки.