1
$\begingroup$

I will present a stripped-down version of a pattern recognition problem that I wish to solve. I would like references to machine learning algorithms and/or problem representations to address this kind of problem. Supervised learning algorithms are probably the most appropriate, because training data is very easy to generate.

Imagine we had several square sheet of paper, with potentially different sizes, and each sheet has a marker in each corner. We lay down these sheets on a table with arbitrary positions and orientations, and in arbitrary order. In general, some corners will be occluded because they will lie behind other sheets of paper.

An example scenario may look like the one below (left), where I have denoted visible markers as solid circles, and occluded markers as hollow circles. To aid visualization, I have also added in edges: solid for visible and dashed for occluded. enter image description here Now let's say we have a system (e.g. overhead camera + algorithm) that can recover the x-y position of each visible marker, but nothing else. We do not know how many squares there are in reality. The recovered data would look like the right side of the above image.

The problem is to recover which markers belong to the same square.

$\endgroup$
  • $\begingroup$ This doesn't seem so much like "learning" as figuring out: there ought to be at least one solution and, if you provide additional criteria for choosing among multiple solutions, one best solution. A useful preprocessing step might include a generalized Hough transform (to detect squares), as described in a related thread about detecting circular shapes in images. Incidentally, did you intend that "what we recover" does not match the dots in "An example layout"? $\endgroup$ – whuber Jun 13 '17 at 21:35
  • $\begingroup$ @whuber Good catch - fixed! $\endgroup$ – MGA Jun 13 '17 at 21:38
1
$\begingroup$

We can assume here that no two squares of paper share a vertex. Furthermore, no three points are collinear, and triples of points that form a 90 degree angle and have the same sidelengths must correspond to a square. These are reasonable assumptions if the squares are randomly distributed with any continuous density. Solving this problem is very expensive. First you'd look for all quadruples of points that form a square. After finding these squares, you can delete them, and look for all remaining triples of points, that form a 90 degree angle between themselves and have the same sidelengths. Remove those, and start look for pairs. This now becomes very difficult. First off, a square needs at least 3 points to be uniquely determined, so that in situations where a pair of points form a square that can be occluded by more than one square, we don't have a unique way of assigning a square. Next, it's not clear which pairs of points can form a square. There will be situations where multiple pairs of points could potentially form squares, depending on the allowed occlusions.

$\endgroup$
  • $\begingroup$ These are good points. Your algorithm starts well, but then it pessimistically seems to forget about important constraints (such as restrictions imposed by the order of the squares from bottom to top) and perhaps exaggerates some of the difficulties. I think, though, you're basically right. One serious issue that comes to mind is that some very large squares could occur, and thereby be responsible for occluding the vertices of many others, without any of the vertices of those large squares being visible at all. That is going to lead to highly indeterminate solutions. $\endgroup$ – whuber Jun 13 '17 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.