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

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

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

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

Присоединённый файл ( Кол-во скачиваний: 34 )
 ______.png 79,41 Kb

Вот как раз нет! На твоем рисунке график и сетка имеют различные цвета. Полный бред не использовать эту информацию. Оси, правда, сливаются с сеткой, но можно их отделить по факту нахождения слева\внизу. А график выделить - элементарно по цвету.
А где там аномальные пикселы? Те, что разбросаны серыми точечками? Если да, можно, во-первых, отфильтровать тупой маской 3*3 (ну или побольше, если они больше чем 1 пиксел), или просто удалить все, что не синее (график), черное (надписи) и оси (серые линии слева и внизу).

Dmitrii,  Вроде задачка выглядит простой.  Хотя накрутить можно много.

1. Да бинаризация. Чтобы убрать шум от задней стороны листа. Надо воспользоваться адаптивной.  Я бы взял готовый вариант из какой нибудь распознавалки текста если конечно там не совсем тупой вариант. 
2.  Дальше бы мат морфологией подавил маленькие точки.
3. Поиск сетки. Вижу два алгоритма. 
 а) посчитать интегральные проекции и поиск пиков. Проблема в том что пики могут быть разных высот. И надо дополнять. 
 б) поиск перекрестков.  Берем патерн и двигаем его по всему изоброжению.
010 123
111 456
010 789
в позициях 2 4 5 6 8 должно быть больше черных пикселей чем в 1 3 7 9.
Позиция это некоторый квадрат, к примеру пиксель или 4 пикселя. Или квадрат со стороной 1.5 пикселя. И считать сумму или точнее интеграл. 
Найдя эти перекрестки будет понятно где именно сетка расположена.

4. Восстановление графиков там где график сливается с сеткой и был удален. Тоже применяем мат морфологию.

Если бы все графики были синими, задача как раз и заключается в том, чтобы написать такой алгоритм, который сможет удалять решетку с любых графиков. Синих, красных, черных и так далее. Т.е. алгоритм не имеет понятия какого цвета график, какого цвета решетка, и т.д.
Можно поподробнее про маску? Как я понял смысл в проходе по матрице и апроксимации цвета в каждом квадрате 3х3. Или как? Да, черные точки именно то, что я называл аномальными пикселами. Т.е. мелкие артефакты, которые могли возникнуть в результате сканирования. 

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

а потому морфологией можно не только подавить шум, но и координатную сетку (нужно только выбрать соответствующие значения), конкретно здесь, скорее всего, пригодится эта операция: http://en.wikipedia.org/wiki/Erosion_(morphology)

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

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

Что касается бинаризации, то, как мне кажется, ее использование необходимо, ибо писать универсальный алгоритм для цветных и grayscale изображений для меня проблематично) Для бинаризации выбрал алгоритм Бернсена с постпроцессингом, согласно статье он обладает универсальными показателями качество/время(осталось найти его более подробное описание).

p.s. Извините за такие, может быть, туповатые вопросы, но в институте нам не читали ни одного курса по обработке изображений. Только чистое программирование, вот сейчас приходится в этом копаться самому  

Это сообщение отредактировал(а) Dmitrii - 28.7.2010, 15:35

Присоединённый файл ( Кол-во скачиваний: 26 )
 _________.png 8,15 Kb

По поводу бинаризации. Не надо быть категоричным. 
Бинаризация дает инвариантность относительно цвета. Т.е алгоритм не надо настраивать на определенный цвет. Это большой плюс. С другой стороны используя информацию о цвете даст преимущество так как определенный класс задач можно решить точнее.
Любые априорные данные дают преимущество. Такими данными может быть цвет толщина линий периодичность.

если под утоньшением подразумевается уменьшение толщины линий до, например, единицы, то не совсем: erosion просто "срезает" слой заданной толщины с границы тела. Если тело было слишком тонким, оно вообще пропадёт. Утоньшение больше смахивает на алгоритмы скелетизации - там (условно) толщина срезается только с толстых частей



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

Из всего выше написаного определил для себя план, по которому это чудо должно работать.
Будем предполагать, что график является идеально позиционированным(оси под углом 90 градусов, ось абсцисс горизонтальна).Если это условие не выполняется, то это уже другая песня, но и с этим я думаю потом можно будет справиться.
Просим пользователя установить цвет фона, это можно сделать простым способом, а-ля "пипетка".
Потом ищем оси, т.е. нижнюю и левую прямые линии, и ограничиваем область нашей работы выше и правее этих линий, дабы не стереть надписи и оси.
Далее, предлагаем пользователю указать, отличается ли график(-и) от сетки по цвету, толщине.
1) Если график отличается по цвету, то закрашиваем все пикселы, яркость которых ниже определенного порога, в нашей "рабочей" области цветом фона. Либо можно также использовать пипетку для определения цвета графика, тогда задача вообще элементарна.
2) Если график отличается по тольщине, то применяем мат.морфологию(по вашему совету).
3) Если же график не отличается по толщине или цвету, придется изобретать велосипед)) Здесь у меня полный тупик) Пробег по изображению с маской не представляю возможным, ибо толщина линий решетки на каждом графике своя. Единственным свойством сетки по которой ее можно будет отделить от графика, это параллельность линий, как это можно использовать пока я не придумал.

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

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



Для начала нужно определить направления осей, судя по примерам, проще найти правую и верхнюю границы. Например для определения вертикального направления можно пробежаться по строкам и записать самые правые координаты нефоновых точек, потом отбросить какой-то процент снизу (из-за чисел) и аппроксимировать их прямой по тому же МНК. А поворачивать график, возможно, и не стоит - всё-таки любой поворот приносит искажения.



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



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

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

Опять таки, извеняюсь, но мало что понял. Почему вектор исследовать легче и проще, нежели растр в данном типе задач? Там легче найти параллельные прямые входящие в сетку или нижнюю и левую прямые? Я совсем запутался) 
p.s. Может быть потому, что не знаю как выглядит представление векторного изображения в программном виде, и чем оно отличается от растра))

Это сообщение отредактировал(а) Dmitrii - 29.7.2010, 14:54

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