Link to home
Start Free TrialLog in
Avatar of chemicalx001
chemicalx001

asked on

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:

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!
Avatar of ozo
ozo
Flag of United States of America image

Are you thinking of something like nearest neighbor clustering?
Avatar of chemicalx001
chemicalx001

ASKER

I don't know. :)

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.
ideally, I would search the frame, find each marker, and store them in an array so i can forEach process them.
SOLUTION
Avatar of ozo
ozo
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
the squares will be all different orientations. I have found a function that looks for black squares, here:

stackoverflow.com/questions/11532078/how-can-i-detect-registration-markers-on-paper-using-opencv

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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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?
... 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.
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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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?
Here is an example image, which i probably should have supplied before!

I have this:

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


and i need to get to this:

http://i59.tinypic.com/2dm9gtl.jpg
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start 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
                O
           Z         O

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

Sara
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.