Программа поиска эллипсов и определения их параметров МНК
Привет! Я новичок на Харбре. Меня зацепила статья от 2011 года: «Детектирование эллиптических частиц на микрофотографии. Новый алгоритм поиска эллипсов на изображении».
Вот комментарий к этой статье (Mrrl 27 дек 2011 в 07:49): «А почему эллипс строится по 6 точкам? Уравнение ведь однородное. Для кривой второго порядка всегда хватало 5 точек, коэффициенты ищутся решением однородного уравнения. В качестве шестой точки есть смысл добавить точку, которая эллипсу заведомо не принадлежит, и записать для нее F (x, y)=1 — тогда придется решать более привычное неоднородное уравнение. А если действительно нужен точный результат, то нужно брать все точки, лежащие вдоль линии приблизительно найденного эллипса (лучше бы с весами), и подать их на вход метода наименьших квадратов. Он позволит определить параметры с точностью до десятых долей пикселя (а то и точнее)».
Мной разработана программа на Матлаб в которой реализована схема, предложенная Mrrl.
Краткое описание программы и результатов ее применения к конкретному примеру из цитированной выше статьи.
Загружаем RGB картинку из статьи:
Превращаем в серое изображение:
Фильтруем DOG фильтром и переводим серое в бинарное, не заморачиваясь с порогом. Просто порог больше ноля.
На картинке много мусора, зато нет разрывов в эллипсе и весь эллипс здесь представлен целиком. С помощью морфологических операций удаляем пиксели на контурах объектов, не позволяя объектам разбиться. Остающиеся пиксели составляют скелет изображений.
С помощью функции regionprops находим связные области, координаты областей, удаляем мелочь на изображении и находим граф.
С помощью функции cyclebasis находим замкнутые фигуры и их координаты. Мелкие отбрасываем. Получили несколько кандидатов на звание «Эллипс». Подключаем к делу МНК.
Используем все точки каждого объекта для нахождения координат эллипса приближающих данные наилучшим образом.
xi, yi — столбцы координат i-го объекта.
Общее уравнение кривой 2-го порядка
A*xi2 + 2*B*xi*yi+C*yi2 + 2*D*xi+ 2*E*yi+ 1 = 0
Для нахождения коэффициентов уравнения решаем переопределенную систему линейных уравнений методом МНК
ab=[xi.^2 xi.*yi yi.^2 xi yi]; b=ones (size (xi',2),1); sb=ab\b;
A=sb (1); B=sb (2)/2; C=sb (3); D=sb (4)/2; E=sb (5)/2; F=-1;
С помощью функции h=fimplicit (@(xh, yh) sb (1)*xh.^2+sb (3)*yh.^2+…); находим координаты приближающего эллипса
xhh=h.XData'; yhh=h.YData';
Для отбраковки кандидатов вычисляем дисперсию приближения данных [xi yi] вычисленными значениями [xhh yhh].
dst=dist ([xhh yhh],[xi yi]»);
mdst=min (dst»)»;
disper=sum (mdst.^2)/(max (size (mdst))-1)
В качестве эллипса оставляем фигуру с минимальной дисперсией.
Вычисляем параметры эллипса методом инвариантов:
http://www.mathprofi.ru/kak_privesti_uravnenie_linii_2_poryadka_k_kanonicheskomu_vidu.html
ab1 и ab2 — полуоси эллипса, x0 и y0 — координаты центра, alfa — угол наклона оси.
ab1 ab2×0 y0 alfa 66.051 74.004 129.63 83.043 -63.906 |
Вычисляем периметр эллипса
perimetr=sum (sqrt (diff (xhh).^2+diff (yhh).^2))= 440.3419
Площадь эллипса S = π * ab1 *ab2= 15356
Проверка точности вычисления параметров
Для проверки точности вычисления периметра параметрически зададим окружность
(частный случай эллипса с равными осями)
t=(0:.001:1)*2*pi; x=80*cos (t)+300; y=80*sin (t)+300;
Найдем параметры эллипсов с помощью нашей программы
Точность определения полуосей и координат центра вполне удовлетворительна.
Программа вычислила perimetr = 502.7046
Проверим точность perimetr = 2*pi*R; R =80.01
Отсюда pi=perimeter/(2*R)= 502.7046/(2×80.01)= 3.1415. (Точное pi=3.1416….)
Оценим влияние размеров фигуры на точность вычисления дисперсии.
Параметрически зададим 5 эллипсов с полуосями a=(5, 10, 20, 40, 80) и с отношением осей 2:1.
t=(0:.001:1)*2*pi; x=a*cos (t)+x0; y=a/2*sin (t)+y0;
Вычислим дисперсии
Повернем эллипсы на 45 градусов и повторим вычисления
Дисперсия немного погуливает в зависимости от размеров эллипса и от ориентации. Возможно это обусловлено тем что данные xy принимают только целочисленные значения, а вычисленные xy представлены с точностью double. Замечено что дисперсии далеких по форме от эллипсов при не больших размерах сравниваются с дисперсиями эллипсов. Возможно причина похожая.
