JavaRush/Java блог/Архив info.javarush/Поиск центра неправильной фигуры на плоскости
fatfaggy
26 уровень

Поиск центра неправильной фигуры на плоскости

Статья из группы Архив info.javarush
участников
Всем привет. Решаю сейчас задачку одну простенькую. Условие звучит примерно так:
Дана матрица (двумерный массив), в которой каждый элемент представляет собой пиксель. Пиксели могут быть красного цвета, черного, либо какого-то другого цвета. Необходимо реализовать поиск на изображении эффекта "красных глаз". Если центр черных пикселей совпадает с центром красных пикселей - значит мы нашли "красный глаз".
Подразумевается, что границы диапазона красных пикселей шире границ диапазона черных. Так же, не рассматриваются варианты, если на изображении присутствуют красные и черные пиксели вне "глаза". Все, что вне "глаза" - будет другого цвета. Я планировал реализовать по (примерно) такому алгоритму. Два цикла, один вложенный в другой. Одним проходимся по Х, вторым - по Y. Как только нашли красный пиксель - фиксируем его координаты как начальные и ищем конечные координаты. Как только оказывается, что красные пиксели больше не появляются - фиксируем последний красный пиксель, который нам попадался, в качестве конечных координат диапазона красных пикселей. Аналогично и с черными пикселями. После чего делим диапазоны пополам и находим центры. Такой алгоритм будет достаточно неплохо работать с фигурами более-менее правильной формы (круга). И вот тут я решил усложнить себе задачу)) А именно, понять как улучшить алгоритм для фигур неправильной формы. Например, если у человека некоторые проблемы со зрением (в связи с чем форма глаза может быть неправильной), или фотка сделана была под углом, или еще какие-то ситуации... Беглый поиск вывел меня на статьи в википедии про центр масс и барицентр. Но там так много страшного и ужасного матана, что я решил пока отложить это и поинтересоваться у сообщества, как бы реализовали это вы? :)
Комментарии (3)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Joysi
Уровень 41
12 марта 2016, 20:04
Я не читал про ужасный матан и про эту задачу. Но пробовал бы решать ее следующим образом на реальных изображениях:
1) Сделав копию изображения применял бы несколько раз фильтр увеличения резкости, подобрав значение матрицы, чтобы он работал более контрастно. В результате чего красные и черные области более явно бы выделились.
2) На другой копии отфильтрованного изображения убрал бы цветовые составляющие Green/Blue. И нашел бы сплошные красные области + выделил бы центры в них. Центр искал бы перебрав все точки области и выбрав ту, у которой сумма квадратов расстояний ((x2-x1)**2 + (y2-y1)**2) до других точек своей области максимальна.
3) Далее смотреть чтобы центр красной области был просто в черной области.
А там уж эксперементировать дальше.

Поиск красных областей. Искал после фильтра резкости на полноцветовой картине (то есть RGB компоненты сохранены). Задал бы число (допустим b=1/25 от размера изображения). И искал бы квадрат в изображении (а лучше круг радиуса b) со следующими свойствами. Чтобы все точки в нем имели красную составляющую не менее 80%, а синюю и зеленую — не более 15% (цифры можно подбирать самому).

А дальше уже можно и усложнять и копать в сторону ФНЧ, ФВЧ, БИХ и КИХ фильтров и т.п. :) Успехов!

Немного саморекламы :)
Можешь работать с JPEG и т.п. файлами в Java примерно как тут:
info.javarush.ru/Joysi/2016/02/20/World-of-Bytes-1-%D0%A0%D0%B0%D0%B1%D0%BE%D1%82%D0%B0-%D1%81-%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F%D0%BC%D0%B8-.html
Joysi
Уровень 41
12 марта 2016, 20:21
В догонку про поиск областей. После найденного квадрата — ищем от его границ во внешние стороны, пока цвет точек будет удовлетворять тому же правилу, что и в цвете квадрата.

Но если вам интересны такого рода задачи. Люто и бешено советую почитать про АЗЫ цифровой обработки сигналов (там где матана — на уровне матриц и рядов, разложения Фурье и т.п.).
Причем можете изучать наглядно с прокачиванием программирования на Java. Написали фильтр — попропускали через него картинок и смотрите результат (наглядно видно что произошло в отличии от сухого чтения книжек). Далее оптимизируете код, чтобы результат был получен быстрее. Далее накручиваете сверху графический интерфейс в дальнейшем или веб-морду.

Если Вы — студент или ученик (я не знаю) — можно даже курсовые и т.п. делать на эту тему.
fatfaggy
Уровень 26
12 марта 2016, 22:33
оо, спасибо за ответы!)
думал уже, никого мой вопрос не заинтересует)