quadtree image segmentation search

Hi, I am using opencv to search an image frame for a specific pattern of dots, get the bounding box, ID it by the dot pattern and get the orientation..

I do this by saying: If contours.size() = number of dots, go ahead and process.

So, in a black image with one such cluster, I can find the contours, get the orientation and all is well.

BUT, in an actual video frame (which is what it will eventually be), or when there are multiple clusters of dots, this obviously won't work, as there will be many more than 7 contours found.

I THINK the way to do this, is to use quadtree image segmentation, split the image, and on each split, search each region for the 7 dots.

If they are found, attempt processing.
if not, split again, and so on.

Does this sound right?

i am looking at this c++ implementation:


but i can't figure out how to actually use it!

If someone could explain where to implement my processing code, it would be much appreciated!

Or, conversely, a different approach :)

Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Are you thinking of something like nearest neighbor clustering?
chemicalx001Author Commented:
I don't know. :)

It is a series of fiducial markers, made from dots, like this:


I need to find that pattern, in a video frame.
there will, eventually, be multiple of them.
chemicalx001Author Commented:
ideally, I would search the frame, find each marker, and store them in an array so i can forEach process them.
OWASP: Threats Fundamentals

Learn the top ten threats that are present in modern web-application development and how to protect your business from them.

When you say "like" what distinguishes a pattern like that, from a pattern unlike that?
chemicalx001Author Commented:
It is square, I guess....  My plan was to split the image, search each split region for 6 dots and then check if the resulting shape is square.

I suspect this will be very slow though...

It will always be white dots on a black background, perhaps i can search that somehow?
If the square is always oriented the same way, you might cluster the x components and y components separately, then cross the clusters.
Or with the nearest neighbor approach it might suggest Manhattan distance rather than Euclidean distance for your nearness metric, or maybe an exponent less than 1.
chemicalx001Author Commented:
the squares will be all different orientations. I have found a function that looks for black squares, here:


But there could well be times when the dots are visible but the square backgrounds are not. If there is another way, that would be much better.
If they have different orientations, could they also have different sizes?
Could they be easier to recognize in a Fourier space?
Are there few enough dots to take them in pairs and search for completions of a square based on those corners?
Or maybe you could convolve the image with the image rotated by 90 degrees.
chemicalx001Author Commented:
They are the same size, but some are close and some far away, so they are different in pixel coordinates.

' take them in pairs and search for completions of a square based on those corners' - I like this idea!

Any thoughts on how i would go about that?

I am not sure if you know opencv, but basically i run a search on a thresholded image for contrast points, or contours.
Each contour is made up of an array of points, and the contours themselves are stored in their own vector array.

My code currently gets the centroid of each contour and stores those.

So, if i have a large array of centre-points, how would i search for completion of a square within them?
chemicalx001Author Commented:
... also, to sadly make it even more difficult...

The markers will often be on a angle in any axis. So each square may not appear entirely square due to the perspective.
Are there many points that don't belong to a square?  If you allow arbitrary transforms, then almost any convex set of 4 points might be part of a projection of a square.
chemicalx001Author Commented:
I should be able to threshold the image enough that it is practically just my squares of points.  But there will be a few of them.
So the code needs to identify each as a separate marker.  They will all have the same number of points, and each can be contained in a four sided polygon.
If you have two opposite corners at {x0,y0} and  {x1,y1}
then the other corner points of an undistorted square would be at
{(x0+x1+y1-y0)/2, (y1+y0+x0-x1)/2} and {(x0+x1+y0-y1)/2, (y1+y0+x1-x0)/2}
If the square is only slightly distorted, then the other corners should be near those points.

If you have more than one square, would they be transformed the same way?
If so, finding one may help you to inverse transform the others.

Were all the dots perfect circles of the same size before the projection?
If so, the shapes and sizes of the circles may help to undo the transform before finding the squares.
chemicalx001Author Commented:
So I could loop through the points, see if there are enough points next to each, and if so, choose a pair and check for square using that method?

How could I do that in c++? Would it be computationally heavy?
chemicalx001Author Commented:
Here is an example image, which i probably should have supplied before!

I have this:


and i need to get to this:

If I were you I would approach it entirely differently, possibly extending the solution you sought in your other question on finding the a point between two points.

Looking at the image you have posted. Here are a few things to notice:

Say there are four clusters, Or even an arbitrary number of points (scanned from the entire image). Assume, points in a cluster are named as A, X, B, C, D and Z

X is the special dot that is the 5th point in your other question - the point that lies on one of the four EDGEs of the square - and not corner.
Z is the point in center.

A cluster will be a set of 6 points strictly satisfying all following geometric relations.

- There will be three lines in each cluster, (one line = three dots with same slope).
  A, X, B will be one line
  A, Z, D will be a line
  B, Z, C will be a line

- A, B, C, D, Z will form at least 8 triangles (a triangle is three points where the 3 angles add up to ~180)
   A, B, C
   A, B, Z
   B, Z, C
  and so on

It shouldn't be difficult to scan an arbitrary array of say N points and find clusters of 6 points that strictly satisfy each of these geometric relations.
For so few sets of points that well separated, I'd think that nearest neighbor clustering should suffice to find the clusters, and taking the points furthest from the centre of the cluster could be sufficient to identify the corners.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
I'd think that nearest neighbor clustering should suffice to find the clusters

yes, that is true. you could use normal Euclidian measure for building the clusters. see the following link for nearest neighbor clustering in c++: http://docs.opencv.org/modules/flann/doc/flann_fast_approximate_nearest_neighbor_search.html

if you want to use an iterative method which is less general than clustering you could try to program the following steps:

1. find all points and put them to an array.
2. convert each point {x,y} to the form {length, angle} where length is the vector length of the point and angle is the angle from point {0, 0}.
4. define the maximum distance MSD between two points belonging to the same square. this also should be valid for squares directed to a different axis. MSD is a threshold used to exclude points from current cluster.
3. sort the points of array by length units. you may tray length unit == MSD/2. for same length unit, use the angle as second sort criterion.
5. use the first point in array as start point S.
6. search the next points until you have found at least 5 points which are near enough to start point to be part of the square. you may stop the search if you have reached a point which has a length greater than length of start point + MSD.
7. if the points found are exactly 6 points, you may check if the points form a square of the desired pattern.
8. if you have a different count of points you may check for the following cases:
8a. you have two or more valid squares which are very close together:

           Z     O O
           Z         O

S    O  O
O         O

Open in new window

S would be the top-left point of a square but points Z belong to a different square and need to be excluded from the current selection. you could do that by sorting the selection by angle and take the first 6 points after reordering.

8b.  some points of the selections are not part of a valid square. if that case is possible, it could be very difficult to find the solution, depending on how near the invalid points could be located.

8c. the start point itself is not a valid part of the square. that is easy to decide if the selection contains less than 6 points or if the pattern doesn't match. if it is more than 6 points, this case was handled in 8b.

9. if you have found a square, draw the polygon, and eliminate all points of the square from array. if the start point was invalid eliminate it from array.
10. repeat steps 3 to 9. next start point is first point of array (if there are at least 6 points left).

chemicalx001Author Commented:
Ok i got it. Using opencv i can:

Find contours.
Find the moments and therefore the centrepoint of each contour.
Use kMeans clustering to find the nearby points.
Get the bounding box of each cluster.

If i threshold the image the right way, this might be enough. if not i can check each cluster for square-y attributes.

thanks for your help!
evilrixSenior Software Engineer (Avast)Commented:
I've requested that this question be closed as follows:

Accepted answer: 0 points for chemicalx001's comment #a40714935

for the following reason:

This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.