0
$\begingroup$

I have a problem wherein I have 2D points in an image that would be associated with a corresponding label/sequence number. For instance following are 4 such examples:

2D points

As you can see all of them have a certain sequence. As if a human were to read them (left to right, top to bottom) but in some cases, it's a little more complicated (see bottom right example above)

As of yet, I am using simple X-Y co-ordinate based sorting to figure out the sequence but it doesn't always work (imagine example top left above, but all the points are arranged at an angle) I'm trying to approach this from a machine learning angle and curious to know how would you do it.

Another challenge is there could be arbitrary number of such points (anywhere between 4 to 16)

We can for instance, use a Neural Network, or an SVM based classifier where the features would be normalized x,y co-ordinates, but I'm wondering if there's a simpler way to do it. Furthermore, I will have to use a lot of augmentations since the output has to be permutation invariant.

I have looked at Geometric Deep Learning based point segmentation methods like PointNet, PointCNN, and so forth but these methods mainly work with point clouds, and would be an overkill for my purpose.

Improve this question
$\endgroup$
3
  • $\begingroup$ To me it looks like you could cover this change of the labeling strategy (top-left vs. bottom-right) with a clustering method. First, look if there are clear clusters, if yes number each cluster separately, if no clear clusters then just label 'line-by-line'. If you can use a bit more domain knowledge (where do the points come from; where do the labels come from; ...) try to do that as well. $\endgroup$
    – Chillston
    Commented Dec 12, 2022 at 23:37
  • 1
    $\begingroup$ And a small heads up: You wouldn't want the output to be permutation invariant, but permutation equivariant (as you want your labels to permute similar to the points). Invariant would mean that you get the same result for permuted input. $\endgroup$
    – Chillston
    Commented Dec 12, 2022 at 23:41
  • $\begingroup$ Yes, would want it to be permutation equivariant +1 $\endgroup$
    – Mayur Kulkarni
    Commented Dec 23, 2022 at 18:02

1 Answer 1

Reset to default
0
$\begingroup$

One solution can be a computational geometric approach. First grid the plane of points with the desired size, denoted by $\epsilon$. Then, row by row, find the points (you can make an appropriate data structure, for example, KD-tree, to have an efficient search). Now, you can decide how many rows of gap are required between two sets of points that should be counted until starting a new line of points. Finally, according to this row index for each point, rank them from 1 to $n$, from left to right of each line (sort all points of each line based on their $x$ coordinate value).

There are two clear advantages to this method:

  1. it is easy to be implemented.
  2. it can be easily employed to work for any number of points.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .