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

[Dimmy]

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

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

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

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


P.S.

[Sangril]

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

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

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

Правильно ли я понял задачу? Тут просто есть множество проблем с растеризацией и вписыванием (5 пикселей все же очень мало). Ну и решение может быть не единственно.

[Михайло]

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

[Sangril]

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

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

[Михайло]

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

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

Я не говорил, что интеллектуальные приложения нельзя свести к какой-нибудь переборной задаче, я вроде как сказал, что данную переборную задачу нельзя считать интеллектуальной.

[Dimmy]

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

[Михайло]

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

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

[tumick]

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

Что инетерсно - мозг ведь решает эту задачу очень похожим способом. С той лишь разницей, что гипотезы эти проверяются не последовательно, а параллельно - все за один раз.

[Sangril]

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

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

Можно пытаться для точки вычислять радиус и перпендикуляр к нему (точнее интервал в который попадает перпендикуляр для радиусов >2.5), а потом попытаться пересечь интервалы у соседних точек.

[Dimmy]

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

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

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

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

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

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

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

[tumick]

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

HTTP Error 404 - Not Found

мы что? перебором узнаем?

Я не знаю, можно ли назвать перебором одновременное сравнение сигнала со всем множеством "хранимых" образцов. Последовательное сравнение - да, это перебор. Но принципиальной разницы я не вижу. Вы видите?

[Михайло]

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

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

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

Здесь наверное была картинка для регистрации в почте яндекс?

[Dimmy]

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

а в моей задаче: картинка, с кучей лишних линий, но приямоугольник только один. ширина 5пк , черный на белом.

[Dimmy]

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

как японцы их узнают?

[tumick]

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

Итак:

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

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

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

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

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

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

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

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

Бред.

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

Не путайте, процессоров много, из них можно собрать несколько видов конфигураций компов. Проблема только в конкретных объектах, точнее в дилерах. Вам, например, заплатят только за продвижение определенной линейки. А уж чтобы продать простой камень, расписываете характеристики так, будто там внутри живет сам ИИ. Примитивно и глупо.
Идиоты с мембраны.ру той же х-ной маются.

[tumick]

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

[Гость]

Сделал

[Dimmy]

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

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

По поводу алгоритма: поворачивать бревно на 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. Почему: работает воображение для того чтобы "натянуть" шаблон на картинку.

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

Алгоритм считаю неверным.

[victorst]

Алгоритм считаю неверным.

Поэтому много лет назад я отказался от решения перцептивных задач (распознавание изображений объектов, устной речи и т.д.). Я решил к этим задачам подойти с другой стороны. Нужно убрать из своей работы по созданию ИИ все то, что создает дополнительные трудности и общую трудоемкость только умножает. Последнее, от чего я отказался - понимания письменной речи на ЕЯ. Я сосредоточился на тех механизмах, которые могут использоваться наиболее часто. В их число входит и воображение (фантазия), и творчество, основанное на воображении.
В противном случае вычислительные и др. технические трудности просто не дадут возможности перейти на более абстрактный уровень обработки информации. Системы распознавания лиц террористов в аэропортах по изображениям видео и фотокамер при всей шумихе об успехах, демонстрируют огромный процент ошибок. Это как прогноз погоды. Если точность прогноза близка к 50%, то это вообще не прогноз.
Решив постепенно одни задачи ИИ, можно во всеоружии подступаться к задачам распознавания образов по изображениям.
Повторяю, я ничего никому не доказываю и не навязываю. Говорю только о своем мнении.