#c #algorithm #image-processing
#c #алгоритм #обработка изображений
Вопрос:
Имея 1-битное черно-белое полутоновое изображение в качестве входных данных, мне нужно извлечь угол, используемый для позиционирования точек, как показано в примере ниже:
Мой предполагаемый подход состоит в том, чтобы определить все изолированные области ниже определенного порога (я могу предположить, что все точки находятся в области 20×20) и составить список всех центральных точек этих точек. Второй шаг — выполнить преобразование Хафа для этих конкретных точек, чтобы найти интересные углы. Основная проблема заключается в том, что это, похоже, генерирует довольно много точек, делая преобразование Хафа (i) медленным и (ii) давая ложные срабатывания, которые, в свою очередь, нуждаются в фильтрации.
Я не могу избавиться от ощущения, что я все усложняю, и я упускаю из виду простое элегантное решение этой проблемы. Какие-либо идеи или подходы, которые я, возможно, упустил из виду?
Комментарии:
1. Простая идея: получить координаты центров всех маленьких черно-белых кругов.
2. Интересная проблема — попробуйте поискать в Google «алгоритм удаления экрана». Этот метод выглядит интересно google.co.uk /…
3. Я изучу эти публикации. Однако большинство из них, похоже, сильно полагаются на фильтрацию, не принимая во внимание угол расположения точек.
4. Просто небольшая проблема: изображение выше — это не 1-битное черно-белое изображение, а уменьшенное изображение в оттенках серого с некоторыми линиями, нарисованными на нем.
5. Да, извините, я отредактировал его в Photoshop, чтобы добавить к нему строки, и немного уменьшил его, чтобы показать мой предполагаемый вопрос.
Ответ №1:
БПФ
Попробуйте выполнить преобразование Фурье для изображения. На экране будут появляться очень резкие частотные пики. С помощью этих пиков вы получите частоту и угол экрана довольно точно даже на зашумленном изображении.
Я только что преобразовал ваше изображение обратно в изображение в оттенках серого:
Затем я запускаю 2D fft над ним:
Яркие точки в (20,27) и его зеркальных положениях являются очень сильными пиками, на порядки сильнее, чем что-либо еще на изображении. Эта кривая показывает спектр мощности в строке 20:
Таким образом, частота экрана в направлении y составляет приблизительно 193/20 = 9,7 пикселей (высота изображения 193), а в направлении x 263/27 = 9,7 пикселей. Это расстояние между точками в каждом направлении, и для вычисления осей обычно требуется немного тригонометрии. Положение пика можно более точно интерполировать из спектра мощности Фурье, используя область вокруг пиков, если это необходимо. Пики также можно накладывать друг на друга для уменьшения шума.
Производительность?
БПФ — довольно быстрое преобразование для вычисления (по крайней мере, по сравнению с Hough amp; al.), Но для больших изображений это занимает много места и времени. Вы можете использовать его для нескольких небольших областей (например, 10 точек в поперечнике), что также поможет вам, если экран неровный. По крайней мере, в этом случае это будет быстро. На моем компьютере требуется 418 us для запуска 2D-БПФ с разрешением 128×128 пикселей.
Примечания по БПФ
Читатели, не знакомые с преобразованием Фурье, должны знать о том факте, что я использовал несколько неаккуратных формулировок выше и в комментариях. Само преобразование является «преобразованием Фурье», FFT — это всего лишь один алгоритм (стандарт де-факто в обработке изображений) для выполнения дискретного преобразования Фурье (DFT).
Одна вещь, которая обычно сбивает людей с толку при вычислении БПФ и сравнении результатов с литературой, — это положение нулевой частоты на изображении. В большинстве учебников нулевая частота (фактически сумма значений пикселей изображения) находится в центре изображения. Большинство библиотек БПФ помещают нулевую частоту в верхний левый угол (как в моем примере).
Итак, в учебниках компоненты нулевой частоты обычно расположены близко к центру преобразованного изображения. В большинстве библиотек БПФ низкие частоты расположены близко к каждому углу изображения. (Обычно существуют функции с именами, подобными fftshift для преобразования между этими двумя представлениями.)
FT — это сложное преобразование. Если преобразуется вещественный сигнал (например, одно изображение), в результирующем преобразованном изображении будет много симметрии. Обычно это не очень важно, но иногда его можно использовать для ускорения работы или экономии памяти.
Сложность одномерного БПФ равна O (n log n). В двумерном случае БПФ сначала выполняется для каждого столбца, а затем для каждой строки и, таким образом, O (x y log y y x log x) = O (x y (log x log y)) или O (n ^ 2 log n) для квадратного изображения. Современные компьютеры очень быстры с БПФ (и могут быть увеличены еще больше с помощью графических процессоров), но большие БПФ с тысячами точек в каждом направлении являются предупреждающим признаком использования неправильного алгоритма.
Комментарии:
1. Я новичок в преобразованиях Фурье, поэтому я еще не рассматривал это, но я обязательно изучу это дальше и сделаю некоторые реализации. Вывод фактической частоты и угла из частот x и y должен быть тривиальным. Большое спасибо за эту информацию!
2. Вы должны поворачивать и наклонять изображение, чтобы увидеть, как ведут себя пики БПФ. На практике это довольно просто, но трудно объяснить. Если вы хотите интерполировать пики частоты, пики могут быть аппроксимированы параболой в журнале спектра мощности. (Будьте осторожны, не пытайтесь найти этому математическое обоснование, оно просто работает …) Если вам нужна библиотека fft, fftw является наиболее распространенной.
3. @DrV Это действительно хороший ответ, вы не возражаете, если я спрошу вас, есть ли ссылка или книга, где я могу узнать больше о том, как использовать БПФ и приложения к изображениям?
4. @CaptainCodeman Спасибо. Я предлагаю вам начать с поисковой системы, используя слова «обработка изображений с преобразованием Фурье». Существует все больше и меньше математических объяснений, которые вы можете выбрать в зависимости от того, насколько вы знакомы с математикой. Это может помочь, если вы сначала попытаетесь изучить 1-d преобразование Фурье, если вы с ним не знакомы. И возьмите Matlab, Pylab или что-то эквивалентное, чтобы вы могли легко экспериментировать. Я также добавлю некоторые дополнительные комментарии о БПФ в свой ответ.
5. @CaptainCodeman Поскольку вы знаете основы и имеете базовое представление, вам, вероятно, лучше всего работать в Интернете. Есть много хороших и много плохих примеров, вы узнаете из обоих. Обратите внимание на оконные функции, которые обычно не слишком хорошо освещаются в примерах. Кроме того, если у вас на изображении нерегулярная сетка, FT не является хорошим инструментом. Большинство приложений FT для обработки изображений представляют собой простые фильтры свертки, анализ изображений (как в этом вопросе ) выполняется не так часто. Для фундаментального понимания сначала ознакомьтесь с версией 1D.
Ответ №2:
Это всего лишь идея, я на самом деле не пробовал:
- Выполняйте эрозию, пока не останется 1 пиксель на блок точек
- соедините каждую точку с ближайшей линией (я имею в виду, просто запомните параметры линии, не рисуйте ее)
- после того, как вы соедините несколько точек (вам нужно найти оптимальное количество), вы сможете усреднить угол линий, соединяющих точки
Комментарии:
1. Рассматривая идею эрозии, это также должно быть в состоянии изолировать точки, которые привязались к своим соседям, что решило бы совсем немного. Проведем несколько экспериментов и сообщим об этом.