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

Есть мысль посчитать "коэффициент равномерности". То есть насколько клетка равномерна. Если коэффициент низкий, значит на ней что-то находится. Но вот как его посчитать? Ничего в голову не лезет.

Пробовал считать "коэффициент отклонения", то есть насколько в текущий момент клетка отличается от начального. Но при изменении освещения всё падает...

Просто есть куча ньюансов, например, тень от соседней фигуры. Или высокая фигура смотрится в камере "залазящей" на соседнюю клетку.

Вид сверху. Освещение яркое. Веб камера (низкие помехи)

Можете предложить другие решения?

Скинул бы несколько кадров c камеры, чтоб понятнее было как что выглядит в реале.

А, ну да, заработался совсем. Вот: 

Тут красным я обозначил места, где находятся фигуры, а синим - артефакты, мешающие нормальному распознованию

Это сообщение отредактировал(а) Bitter - 5.4.2008, 14:18

Присоединённый файл ( Кол-во скачиваний: 62 )
 1.jpg 66,00 Kb

В таком виде задача очень сложная.

Если это можно, поменяй фигуры объёмные и вертикальные на плоские и горизонтальные, как в книгах по шахматам. Избавишься от теней и легче распознать.

А это все качество, которое может выдать веб-камера? К примеру, черное-на-черном непросто увидеть даже человеку, не то, что программе...

можно пытаться анализировать равномерность закраски клеточки
(для начала можно дисперсию посмотреть)
хотя качество, конечно, плоховато...

Не, она может выдать и цветное. Это я так её настроил, чтобы обрабатывать по оттенкам. Всё в принципе получилось. Черное на черном анализируется по блику от лампы, тени фильтрую (они серые), а чтобы найти белые на белом, надо повизиться с контрастом, чтобы фигуры стали ярче клетки. Но это всё дело случая: а что если фигуры другого цвета или матовые? 



Эта мысль меня посетила первой. Я в вопросе так и написал


Не пойму как его считать.




Не, фигуры настоящие должны быть. Это не учебная программа. Она должна без ошибок работать с настоящими шахматами.

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

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

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

Ок, а какие выводы уже делать на основе этой величины? На сколько она отклоняется от среднего? Или как?

Просто я на данный момент считаю "коэффициент отклонения" по такому алгоритму:
1. В начала запоминаем состояние клеток без фигур.
2. Когда нужно распознать занятость, вычисляю разность текущих пикселей от запомненых, предварительно сглаживая с соседними. (То есть считаю отклонение для сглаженной клетки).
3. Считаю коэффициент - кол-во отклонившихся пикселей делим на общее кол-во пикселей в клетке. Отклонившимися считаются те, разность которых превысила заданный порог.
4. В итоге получаем значение от 0 до 1. Где 0 - Абсолютно не изменившаяся клетка.

В принципе похоже на то, что ты предложил или нет?

Недостаток этого в том, что тени и прочая фигня тоже делают коэффициент высоким. Приходится применять всякие фильтры... 

Кстати я вот только что придумал: может можно как-то разбивать клетку на группы изменившихся пикселей. Тогда в случае с тенью групп будет 2-3, а в случае с фигурой больше.
Что-то не очень, да?

в принципе, похоже

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

впрочем, всё это сильно базируется на равномерности закраски пустой клетки, что не совсем точно (частенько там бывает "деревянная" текстура), но попробовать можно

У меня как раз такая на белых клетках. Если присмотреться, то на более тёмных белых видно. Это я просто яркость повысил...

Я вот подумал. Если взять шахматную доску в целом, то есть как чередование черных и белых клеток, то её тоже можно назвать равномерной, так как рисуно равномерно повторяется. А если вычислять по дисперсии, то результат будет плохим. Ведь среднее между черным и белым - серое, а каждая клетка отличается ровно на половину.

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

Есть мысли как это сделать? То есть как определить степень распределения по заданному пространству?

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

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

Происходит перемещение. Делаем новую фотографию новой ситуации, накладываем сетку, сравниваем с первоначальным.

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

Результатами пока похвастаться не могу, не все еще готово.

Кстати, могу вот ссылку дать в помощь
http://courses.graphicon.ru/main/vision/lections

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

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

Удачи!

Dzo, интересно, но чё-то я кое что не понял.

1. Что значит "накладываем сетку"?  И как Вы потом эти сетки сравниваете?

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

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

Кстати, я перемещение отслеживаю так: 
1. Определяем занятость клеток
2. Определяем цвета фигур
3. Смотрим какая фигура передвинулась.

Есть две проблемы в этом. 

1. Рокировка. Но она тоже заметна, так как меняются сразу 4 клетки
2. Замена пешки на ферзя, при достижении противоположного края доски. Но это тоже не проблема, если предположить, что пешка меняется только на ферзя.