Держите одну строку из многих, которые начинаются с одной точки

Question

Я работаю над проектом с OpenCV и python, но застрял на этой небольшой проблеме.

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

Моя переменная, в которой хранится информация (координаты обеих конечных точек) всех первоначально обнаруженных линий выглядит следующим образом:

var = [[Line1_EndPoint1, Line1_EndPoint2],
       [Line2_EndPoint1, Line2_EndPoint2],
       [Line3_EndPoint1, Line3_EndPoint2],
       [Line4_EndPoint1, Line4_EndPoint2],
       [Line5_EndPoint1, Line5_EndPoint2]]

где LineX_EndPointY (номер строки «X», конечная точка «Y» этой строки) имеет тип [x, y], где x и y - координаты этой точки на изображении.

Может кто-нибудь подсказать мне, как решить эту проблему.

Вы можете изменить данные линий хранятся. Если вы вносите изменения, объясните, пожалуйста, вашу структуру данных и как она создается

Пример таких данных:

[[[551, 752], [541, 730]], 
 [[548, 738], [723, 548]],
 [[285, 682], [226, 676]],
 [[416, 679], [345, 678]],
 [[345, 678], [388, 674]],
 [[249, 679], [226, 676]],
 [[270, 678], [388, 674]],
 [[472, 650], [751, 473]],
 [[751, 473], [716, 561]],
 [[731, 529], [751, 473]]]

Python код будет заметен.

Answer 1

A Numpy решение

Тот же результат, что и в моем первом ответе, может быть достигнут только на основе Numpy.

Сначала определите 2 функции:

1. Вычислить квадрат длины строки:

    def sqLgth(line):
        p1, p2 = line
        return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
   

2. Преобразовать вектор ( 1D массив) в массив столбцов ( 2D массив с одним столбцом:

    def toColumn(tbl):
        return tbl.reshape(-1, 1)
   

Оба будут использоваться позже.

Затем действуйте следующим образом:

1. Получите количество строк:

    lineNo = var.shape[0]
   

2. Создайте индексы строк (содержимое lineInd столбец в массиве точек (будет создан позже)):

    id = np.repeat(np.arange(lineNo), 2)
   

3. Сгенерировать «индикаторы начала» (1 - начало, 2 - конец) , чтобы упростить анализ любых промежуточных распечаток:

    origin = np.tile(np.array([1, 2]), lineNo)
   

4. Вычислить длину строки (содержимое столбца lgth в точках ):

    lgth = np.repeat([ sqLgth(line) for line in var ], 2)
   

5. Создайте список точек с некоторыми дополнительными данные (последовательные столбцы содержат origin , lineInd , x , y и lgth ):

    points = np.hstack([toColumn(origin), toColumn(id),
        var.reshape(-1, 2), toColumn(lgth)])
   

6. Вычислите «массив критериев» для сортировки:

    r = np.core.records.fromarrays(points[:, 2:].transpose(),
        names='x, y, lgth')
   

7. Сортировка точек (по x , y и lgth ):

    points = points[r.argsort()]
   

8. Вычислить «обратные уникальные индексы» для точек:

    _, inv = np.unique(points[:,2:4], axis=0, return_inverse=True)
   

9. Shift inv на 1 позицию:

    rInv = np.roll(inv,1)
   

   Будет использоваться на следующем шаге для получения предыдущего элемента.

10. Создать список индексов строк для удаления:

    toDrop = points[[ i for i in range(2 * lineNo)
        if inv[i] == rInv[i] ], 1]
    

    Индексы строк (в массиве points ) - это индексы повторяющихся точек (элементы в inv равно предыдущему элементу).

    Индекс столбца ( 1 ) - указывает lineInd столбец.

    Результат целиком ( toDrop ) - список индексов «владеющих» строк (содержащих повторяющиеся точки).

11. Сгенерировать resu lt: var удалено из строк, выбранных на предыдущем шаге:

    var2 = np.delete(var, toDrop, axis=0)
    

Чтобы распечатать сокращенный список строк, вы можете запустить:

for line in var2:
    print(f'{line[0]}, {line[1]}')

Результат:

[551 752], [541 730]
[548 738], [723 548]
[345 678], [388 674]
[249 679], [226 676]
[731 529], [751 473]

Чтобы полностью понять, как работает этот код:

• выполнить каждый шаг отдельно,
• распечатать результат,
• сравните его с распечатками из предыдущих шагов.

Иногда полезно распечатать отдельно даже некоторые выражения (части инструкций), например var.reshape(-1, 2) - преобразование вашего var (формы (10, 2, 2) ) в массив точек 2D (каждая строка представляет собой точку).

Весь результат конечно, точно так же, как и в моем первом ответе, но, как вы писали, у вас был небольшой опыт работы с Pandas, теперь вы можете сравнить оба метода и увидеть случаи, когда Pandas позволяет чтобы сделать что-то более простое и интуитивно понятное.

Хорошими примерами являются, например, сортировка по некоторым столбцам или поиск повторяющихся строк. В Pandas это вопрос одной инструкции с подходящими параметрами, тогда как в Numpy вам нужно использовать больше инструкций и знать различные детали и уловки, как просто сделать то же

Answer 2

Я решил, что проще написать решение на основе Pandas. Причины в том, что:

• Я могу использовать имена столбцов (код лучше читается),
• Pandas API более мощный, хотя и работает медленнее, чем «чистый» Numpy.

Действуйте следующим образом:

1. Преобразуйте var в DataFrame:

    lines = pd.DataFrame(var.reshape(10,4), columns=pd.MultiIndex.from_product(
        (['P1', 'P2'], ['x','y'])))
   

   Начальная часть строк :

        P1        P2     
         x    y    x    y
    0  551  752  541  730
    1  548  738  723  548
    2  285  682  226  676
    3  416  679  345  678
   

2. Вычислите квадрат длины каждой строки:

    lines[('', 'lgth')] = (lines[('P1', 'x')] - lines[('P2', 'x')]) ** 2\
        + (lines[('P1', 'y')] - lines[('P2', 'y')]) ** 2
    lines.columns = lines.columns.droplevel()
   

   Я намеренно «остановился» на квадратах длины, потому что этого достаточно для сравнения длин (вычисление root не изменит результат сравнения).

   Обратите внимание, что первый уровень MultiIndex для столбцов был нужен только для express облегчения интересующих столбцов. В дальнейшем они не понадобятся, поэтому я его отбросил.

   На этот раз я поместил полное содержимое строк :

         x    y    x    y    lgth
    0  551  752  541  730     584
    1  548  738  723  548   66725
    2  285  682  226  676    3517
    3  416  679  345  678    5042
    4  345  678  388  674    1865
    5  249  679  226  676     538
    6  270  678  388  674   13940
    7  472  650  751  473  109170
    8  751  473  716  561    8969
    9  731  529  751  473    3536
   

3. Следующим шагом является вычисление точек DataFrame, где все точки (начало и конец каждой строки) находятся в одних и тех же столбцах вместе с длиной (квадратом) соответствующей строки:

    points = pd.concat([lines.iloc[:,[0, 1, 4]],
        lines.iloc[:,[2, 3, 4]]], keys=['P1', 'P2'])\
        .sort_values(['x', 'y', 'lgth']).reset_index(level=1)
   

   Теперь я использовал ilo c для указания столбцов (первый раз для начальных точек и второй для конечных точек). Чтобы упростить чтение этого DataFrame, я передал ключи , чтобы включить «индикаторы происхождения», а затем отсортировал строки.

   Содержимое:

        level_1    x    y    lgth
    P2        5  226  676     538
    P2        2  226  676    3517
    P1        5  249  679     538
    P1        6  270  678   13940
    P1        2  285  682    3517
    P1        4  345  678    1865
    P2        3  345  678    5042
    P2        4  388  674    1865
    P2        6  388  674   13940
    P1        3  416  679    5042
    P1        7  472  650  109170
    P2        0  541  730     584
    P1        1  548  738   66725
    P1        0  551  752     584
    P2        8  716  561    8969
    P2        1  723  548   66725
    P1        9  731  529    3536
    P2        9  751  473    3536
    P1        8  751  473    8969
    P2        7  751  473  109170
   

   Обратите внимание, например, что точка 226, 676 встречается дважды. В первый раз это произошло в строке 5 , а во второй - в строке 2 (индексы в var и строках ).

4. Чтобы найти индексы удаляемых строк, запустите:

    toDrop = points[points.duplicated(subset=['x', 'y'])]\
        .level_1.reset_index(drop=True);
   

   Чтобы легче понять, как работает этот код, запустите его шаг за шагом и проверьте результаты каждого шага.

   Результат:

    0    2
    1    3
    2    6
    3    8
    4    7
    Name: level_1, dtype: int64
   

   Обратите внимание, что левый столбец выше является только индексом (это не имеет значения). Реальная информация находится в правом столбце (значения).

5. Чтобы показать строки, которые следует оставить, выполните:

    result = lines.drop(toDrop)
   

   и получите:

         x    y    x    y   lgth
    0  551  752  541  730    584
    1  548  738  723  548  66725
    4  345  678  388  674   1865
    5  249  679  226  676    538
    9  731  529  751  473   3536
   

   Приведенный выше результат не содержит, например:

   • строка 2 , поскольку точка 226, 676 встречается в строке 5 ,
   • строка 3 , поскольку точка 345, 678 встречается в строке 4 ,

   Просто эти строки ( 2 и 3 ) были удалены, потому что они длиннее, чем обе упомянутые вторые строки (см. более ранние частичные результаты).

Может быть, этого достаточно, или, если вам нужно отбросить "дублированные" строки из var (исходный массив Numpy) и сохранить результат в другой переменной, запустите:

var2 = np.delete(var, toDrop, axis=0)