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

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:

stackoverflow.com/questions/7050164/image-segmentation-split-and-merge-quadtrees

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 :)

thanks!

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:

stackoverflow.com/question

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 :)

thanks!

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.

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

http://tinypic.com/view.php?pic=23ih5l4&s=8#.VSVB9vnF-2V

I need to find that pattern, in a video frame.

there will, eventually, be multiple of them.

I suspect this will be very slow though...

It will always be white dots on a black background, perhaps i can search that somehow?

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.

stackoverflow.com/question

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.

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.

' 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?

The markers will often be on a angle in any axis. So each square may not appear entirely square due to the perspective.

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.

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.

How could I do that in c++? Would it be computationally heavy?

I have this:

http://i58.tinypic.com/wwdw0l.jpg

and i need to get to this:

http://i59.tinypic.com/2dm9gtl.jpg

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.

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 trialI'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
O
Z O
S O O
O
O O
```

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).

Sara

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!

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.

http:#a40712624

http:#a40712716

http:#a40712777

http:#a40714407

http:#a40714658 Accept

http:#a40714604

http:#a40714816

http:#a40714935

Algorithms

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.