Быстрая сегментная матрица смежности - PullRequest
Новая
       16

Быстрая сегментная матрица смежности

0 голосов
/ 16 августа 2011

Скажем, у меня есть два изображения A и B одинакового размера.Скажем, у меня также есть две сумки сегментов bag_A и bag_B 2D-сегментов, из изображений A и B соответственно.

2D-сегмент определяется как набор местоположений (пикселей) на изображении и может быть представлен двоичным изображением того же размера, что и исходное изображение, где пиксель равен true, если пиксельнаходится внутри сегмента, и false, если он находится снаружи.

Скажем, я хочу увидеть, какие сегменты из bag_A перекрываются с какими сегментами из bag_B, и закодировать результат в матрице смежности, поэтомучто:

  • adjacency_matrix(segment_from_A,segment_from_B) равно true, если сегменты перекрываются.
  • adjacency_matrix(segment_from_A,segment_from_B) равно false в противном случае.

Мой вопросКакой эффективный способ быстро вычислить эту матрицу смежности?

Скажем, я определяю N и M как% сегментов в bag_A и bag_B соответственно.Есть ли способ вычислить матрицу смежности в меньше , чем O(N*M) "в среднем"?(например, с равномерным распределением сегментов по пространству и размеру)?Если да, то как?

Мой вывод:

Я считаю, что есть способ сделать это с помощью hashing, возможно, предварительно обработав данные враспределить сегменты в ведра.Я думаю, что могу определить сегмент для каждого местоположения на каждом изображении, где два или более сегмента этого изображения перекрываются.Тогда я, вероятно, мог бы просто вычислить смежность между сегментами между двумя изображениями, и из этого я мог получить смежность между bag_A и bag_B как-то "напрямую".Тем не менее, я не уверен, сработает ли это (вероятно, я скоро попробую) или как оценить ожидаемое время работы для него.

Кроме того, когда стоило бы вычислять смежность с помощью хеширования, а не путем сравнения всех возможных пар напрямую?

Бонус: Особенности реализации

В конечном итоге я ищу решение, которое бы работало в MATLAB или из него.

1 Ответ

1 голос
/ 16 августа 2011

Первые показы: на самом низком уровне я бы закодировал данные сегмента как биты в целых числах (или массив целых чисел) и реализовал окончательное сравнение как операцию И, чтобы определить, перекрываются ли они.

Для оптимизации более высокого уровня, чтобы уменьшить количество сравнений, я бы построил квадродерево для битовых карт сегмента, где ветвь, присутствующая в квадродереве, представляет, что где-то в этом квадранте битовой карты присутствует истинный бит (и т. Д. Рекурсивнодо некоторого произвольного минимума).При желании вы можете получить более изящные данные, например, закодировать число истинных битов в каждой ветви дерева квадрантов.

Тогда я бы хешировал квадри для получения блоков.Внутри корзины вы можете быстро исключить, что не может быть совпадением, если их квадри не совпадают.Наконец, я бы использовал низкоуровневую операцию И, чтобы найти те, которые действительно перекрываются.

...