Кто-нибудь знает более эффективный способ выполнить парное сравнение сотен траекторий? - PullRequest
Новая
       78

Кто-нибудь знает более эффективный способ выполнить парное сравнение сотен траекторий?

0 голосов
/ 25 марта 2020

Итак, у меня есть два разных файла, содержащих несколько траекторий в квадрате карты (512x512 пикселей). Каждый файл содержит информацию о пространственном положении каждой частицы в треке / траектории (координаты X и Y) и к какой траектории / траектории принадлежит это место (TRACK_ID). Моей целью было найти способ сгруппировать похожие траектории между обоими файлами. Я нашел хороший способ сделать это (сравнение дистанционной кластеризации), но код слишком медленный. Мне просто интересно, есть ли у кого-нибудь предложения по ускорению.

Мои файлы выглядят примерно так:

enter image description here

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

  • сгруппируйте все точки по дорожке, используя функцию pandas.groupby для file1 (growth_xml) и file2 (shrinkage_xml) )
  • для каждой траектории в growth_xml (l oop) Я сравниваю с каждой траекторией в growth_xml
  • , если они соответствуют заданным мною критериям расстояния Фреше (оператор if) Я сохраняю оба трека в новой таблице. вы можете увидеть дополнительное условие фильтра, которое я назвал delay, но я думаю, что это не важно, чтобы объяснить здесь.

очень просто: 

def distance_clustering(growth_xml,shrinkage_xml):

coords_g = pd.DataFrame() # empty dataframes to save filtered tracks
coords_s = pd.DataFrame()

counter = 0  #initalize counter to count number of filtered tracks

for track_g, param_g in growth_xml.groupby('TRACK_ID'):

    # define growing track as multi-point line object 
    traj1 = [(x,y) for x,y in zip(param_g.POSITION_X.values, param_g.POSITION_Y.values)]

    for track_s, param_s in shrinkage_xml.groupby('TRACK_ID'):

        # define shrinking track as a second multi-point line object 
        traj2 = [(x,y) for x,y in zip(param_s.POSITION_X.values, param_s.POSITION_Y.values)]

        # compute delay between shrinkage and growing ends to use as an extra filter
        delay = (param_s.FRAME.iloc[0] - param_g.FRAME.iloc[0])

        # keep track only if the frechet Distance is lower than 0.2 microns

        if frechetDist(traj1, traj2) < 0.2 and delay > 0:

            counter += 1

            param_g = param_g.assign(NEW_ID = np.ones(param_g.shape[0]) * counter)
            coords_g = pd.concat([coords_g, param_g])

            param_s = param_s.assign(NEW_ID = np.ones(param_s.shape[0]) * counter)
            coords_s = pd.concat([coords_s, param_s])

coords_g.reset_index(drop = True, inplace = True)
coords_s.reset_index(drop = True, inplace = True)
return coords_g, coords_s

Основная проблема в том, что в большинстве случаев у меня более 2 тысяч треков (!!), и эта парная комбинация длится вечно. Мне интересно, есть ли простой и более эффективный способ сделать это. Возможно, выполняя попарную комбинацию в нескольких небольших областях вместо всей карты? не уверен ...

1 Ответ

0 голосов
/ 30 марта 2020

Вы пытались сделать матрицу (DeltaX, DeltaY) lookUpTable для расстояния парной комбинации. Чтобы набрать c LUT один раз, потребуется некоторое время, или вы можете записать его в файл и загрузить при запуске al go. Тогда вам нужно будет только взглянуть на правильный случай, чтобы каждый раз иметь результат вместо cal c.

Вы также можете сделать полиномиальную регрессию для расстояния cal c, оно будет менее точным но определенно быстрее

...