Как отсортировать контуры по расстоянию каждого с каждым?

На исходном изображении с помощью функции findContours() получен вектор контуров и вектор иерархической связи между ними:
std::vector > contours; std::vector hierarchy; cv::findContours(src_mat, contours, hierarchy, cv::RETR_TREE, cv::CHAIN_APPROX_SIMPLE);
Для быстрого доступа требуется сформировать сортированный список расстояний центральных точек каждого контура к центральным точкам других контуров из того же набора. Отдельный список нужен для того, чтобы сохранить связи в векторе, определяющем иерархию. Как это реализовать средствами OpenCV?

Ответ

Для решения этой задачи удобно использовать матрицу. В целом, предлагаемый к рассмотрению подход совершенно не привязан к сортировке именно по расстоянию между центральными точками контуров. Можно использовать такой показатель, как например разница площадей контуров (проще говоря, соотношение размеров) или любой иной параметр, представляющий из себя некую числовую разницу одного контура с другим.
Для начала требуется создать матрицу, содержащую значение желаемого параметра. Пусть это будет расстояние между центральными точками каждого контура к каждому.
const int vct_sz = contours.size(); const cv::Scalar def_val(0); cv::Mat val_mat(vct_sz, vct_sz, CV_64F, def_val);
Константа vct_sz - это просто количество контуров в исходном векторе. def_val - значение расстояния по умолчанию.
for(int row = 0; row < vct_sz; ++row) { const cv::RotatedRect rc1 = cv::minAreaRect(contours.at(row));
for(int col = 0; col < vct_sz; ++col) { if(row == col) continue;
if(val_mat.at(col,row) != 0) { val_mat.at(row,col) = val_mat.at(col,row);
} else { const cv::RotatedRect rc2 = cv::minAreaRect(contours.at(col));
val_mat.at(row,col) = (double)cv::norm(rc1.center - rc2.center); } } }
Теперь матрица значений val_mat полностью заполнена. Если её схематично нарисовать, то обнаружится примерно следующее:

В таблице индексы и строк, и колонок полностью соответствуют индексам в векторе контуров. Фактически, матрица получилась с зеркальным отражением данных. В какой-то мере это избыточно, но возможность моментального доступа к данным подчас окупает. В принципе можно и не заполнять зеркально, но матрица уже инициализирована double, поэтому экономии никакой не будет.
Остаётся лишь сортировка. Разумеется, что если отсортировать значения непосредственно в val_mat, то потеряется связь между индексами матрицы и индексами в векторе контуров. Во избежание этого строится матрица индексов:
cv::Mat idx_mat; cv::sortIdx(val_mat, idx_mat, cv::SORT_EVERY_ROW + cv::SORT_ASCENDING);
Теперь idx_mat будет содержать индексы матрицы val_mat, но отсортированные по значениям в строках последней:

На этом всё. Доступ по возрастающему расстоянию между проверяемым контуром и всеми остальными можно осуществлять через созданные матрицы:
// Индекс проверяемого контура. const int contour_idx = 0;
for(int i = 0; i < vct_sz; ++i) { const int &idx = idx_mat.at(contour_idx,i);
// Ближайший по расстоянию от проверяемого контур. const std::vector &contour = contours.at(idx);
// Расстояние от проверяемого до ближайшего контура. const double &distance = val_mat.at(contour_idx, idx); }