Сравнение контуров — распространённая задача, возникающая, например, при решении проблемы поиска заданного объекта на изображении (template matching)
template matching — сравнение шаблона — поиск заданного объекта на изображении.
Самый простой вариант сравнения пары контуров — это рассчитать их моменты.
Момент — это суммарная характеристика контура, рассчитанная интегрированием (суммированием) всех пикселей контура.
момент (p,q) определяется формулой:
n
m(p,q) = Summ I(x,y) x^p y^q
i=1
, где
p и q — порядок возведения в степень соответствующего параметра при суммировании.
n — число пикселй контура
Исходя их определения, можно сделать вывод, что
момент m00 — равен длине пикселей контура (вернее сказать — площадь, но так как мы рассматриваем не полигон, а границу, то уместно вести речь о длине)
#define cvContourMoments( contour, moments ) \
cvMoments( contour, moments, 0 )
/* Calculates all spatial and central moments up to the 3rd order */
CVAPI(void) cvMoments( const CvArr* arr, CvMoments* moments, int binary CV_DEFAULT(0));
— рассчёт всех моментов контура
array – растровое изображение (одноканальное, 8-битное 2D-массив элеметов с плавающей точкой) или массив ( 1xN или Nx1 ) 2D-точек (Point или Point2f ).
moments – возвращаемые моменты
binary – если задан, то все ненулевые пиксели исходной картинки интерпретируются, как 1. (только для изображения)
/* Retrieve particular spatial, central or normalized central moments */
CVAPI(double) cvGetSpatialMoment( CvMoments* moments, int x_order, int y_order );
CVAPI(double) cvGetCentralMoment( CvMoments* moments, int x_order, int y_order );
CVAPI(double) cvGetNormalizedCentralMoment( CvMoments* moments,
int x_order, int y_order );
/* Spatial and central moments */
typedef struct CvMoments
{
double m00, m10, m01, m20, m11, m02, m30, m21, m12, m03; /* spatial moments */
double mu20, mu11, mu02, mu30, mu21, mu12, mu03; /* central moments */
double inv_sqrt_m00; /* m00 != 0 ? 1/sqrt(m00) : 0 */
}
CvMoments;
В версии для C++ используется класс cv::Moments():
//! raster image moments
class CV_EXPORTS_W_MAP Moments
{
public:
//! the default constructor
Moments();
//! the full constructor
Moments(double m00, double m10, double m01, double m20, double m11,
double m02, double m30, double m21, double m12, double m03 );
//! the conversion from CvMoments
Moments( const CvMoments& moments );
//! the conversion to CvMoments
operator CvMoments() const;
//! spatial moments
CV_PROP_RW double m00, m10, m01, m20, m11, m02, m30, m21, m12, m03;
//! central moments
CV_PROP_RW double mu20, mu11, mu02, mu30, mu21, mu12, mu03;
//! central normalized moments
CV_PROP_RW double nu20, nu11, nu02, nu30, nu21, nu12, nu03;
};
//! computes moments of the rasterized shape or a vector of points
CV_EXPORTS_W Moments moments( InputArray array, bool binaryImage=false );
typedef const _InputArray& InputArray;
/*!
Proxy datatype for passing Mat's and vector<>'s as input parameters
*/
class CV_EXPORTS _InputArray
Т.о., сравнение двух контуров можно свести к сравнению их моментов.
Онако, моменты, найденные по простой формуле, приведённой выше, имеют существенные недостатки:
— они не позволяют сравнить контуры одинаковой формы, но разных размеров, поэтому их, сначала нужно нормализовать (операция эквализации контуров (приведение к единой длине) — позволяет добиться инвариантности к масштабу).
— зависят от системы координат, а значит не позволят определить повёрнутую фигуру.
Поэтому, лучше использовать нормализованные инвариантные моменты.
CVAPI(double) cvGetCentralMoment( CvMoments* moments, int x_order, int y_order );
— вычисление центральных моментов (central moments):
n
mu(p,q) = Summ I(x,y) (x-Xc)^p (y-Yc)^q
i=1
, где Xc, Yc — центр масс:
m10 m01
Xc = --- , Yc = ---
m00 m00
CVAPI(double) cvGetNormalizedCentralMoment( CvMoments* moments,
int x_order, int y_order );
— вычисление нормализованных центральных моментов (normalized central moments):
/* Calculates 7 Hu's invariants from precalculated spatial and central moments */
CVAPI(void) cvGetHuMoments( CvMoments* moments, CvHuMoments* hu_moments );
— вычисления Hu invariant moments
— это линейная комбинация центральных моментов (идея состоит в том, что комбинируя различные нормализованные центральные моменты возможно создать инвариантное представление контуров, не зависящее от масшаба, вращения и отражения (h1) ):
Используя Hu моменты, можно попробовать сравнить два объекта
//! matches two contours using one of the available algorithms
CV_EXPORTS_W double matchShapes( InputArray contour1, InputArray contour2,
int method, double parameter );
/* Compares two contours by matching their moments */
CVAPI(double) cvMatchShapes( const void* object1, const void* object2,
int method, double parameter CV_DEFAULT(0));
#define cvMatchContours cvMatchShapes
— сравнение двух контуров по их моментам (Hu)
object1 — первый контур или изображение (градации серого)
object2 — второй контур или изображение (градации серого)
method — метод сравнения:
Очень интересный материал! Хорошо, что освещается именно математический вопрос в сравнении контуров изображений.
Хотелось бы узнать, что конкретно подразумевается под контурами здесь, это действительно набор необязательно связанных точек (которые переведены в бинарный вид с помощью детектора границ Канни, например), или замкнутая последовательность пикселей, или незамкнутые отрезки, или все попадает под определение?
Нужна формула для аналогичного подхода, но обладающая чувствительностью к масштабированию.
Использую всякие варианты домножения на периметр, площадь и прочие параметры контура, но они меня не устраивают, хочется более устойчивое решение.
Комментарии (6)
RSS свернуть / развернутьAstrgan
noonv
Хотелось бы узнать, что конкретно подразумевается под контурами здесь, это действительно набор необязательно связанных точек (которые переведены в бинарный вид с помощью детектора границ Канни, например), или замкнутая последовательность пикселей, или незамкнутые отрезки, или все попадает под определение?
grafity3
noonv
Использую всякие варианты домножения на периметр, площадь и прочие параметры контура, но они меня не устраивают, хочется более устойчивое решение.
ursoft2004
ursoft2004
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.