6DOF Positioning System - PS3 Eye and fiduciary markers

This is for discussion and development of non-commercial open source VR/AR projects (e.g. Kickstarter applicable, etc). Contact MTBS admins at customerservice@mtbs3d.com if you are unsure if your efforts qualify.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

I am currently working on a system for 6DOF positioning using the PS3 Eye. For people who don't know, the PS3 Eye is a very cheap (£11) webcam designed for use with the PS3 that thanks to a driver from Code Laboratories can be used on the PC as well. It is notable for having a very, very high maximum frame rate of 187FPS (~5ms latency).

My system is going to work very similarly to how Augmented Reality systems work; by using known patterns (called fiduciary markers) the camera's position in 3D space can be worked out from the image that it can see. The main challenge is designing a process for doing this that is stable and fast.

Here is a picture of my current setup;
Image

and the results of my current code;
Image

At the moment I am just using the position of three of the lights (RGB), to calculate up to four possible poses for the camera (pose = position + orientation), that's the white boxes in the 3D scene.

The next step is work out which one of these is right. You do that by seeing where a fourth point known would be under these possible positions. You can then do the same thing with another set of three points (calculate 4 possible poses, pick the correct one) to get another estimate for the camera's position (in an ideal world, all these poses would be exactly equal). If you then take the average of all your poses, you should get a reasonably accurate estimation of the camera pose, and importantly, the averaging doesn't introduce any inter-frame dependency (and therefore latency).

The next stage for me now is to make a better LED board - this current one is very messy and therefore inaccurate. I still don't know for sure that the system will work well in the end, but it is progressing well at the moment.
User avatar
cybereality
3D Angel Eyes (Moderator)
Posts: 11407
Joined: Sat Apr 12, 2008 8:18 pm

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by cybereality »

Awesome man! This is looking really good. Would be cool if you could make a video when you get things working good.
User avatar
cadcoke5
Binocular Vision CONFIRMED!
Posts: 210
Joined: Mon May 24, 2010 8:43 pm
Location: near Lancaster, PA USA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by cadcoke5 »

A number of years ago, I had come across the CMUCam (http://www.cmucam.org) and had wondered about its usefulness in tracking. I never pursued it. But, here is a portion of their description that I edited down. It sound quite flexible, but I am concerned about the ability to process 8 frames per second. It is open source, so changes to the processor or other aspects may be viable. Note that much of this is way over my head.
The CMUcam4 is a fully programmable embedded computer vision sensor. The main processor is the Parallax P8X32A (Propeller Chip) connected to an OmniVision 9665 CMOS camera sensor module.
Features

Fully open source and re-programmable using the Propeller Tool
Arduino Shield Compatible
w/ Supporting Interface Libraries and Demo Applications for the Arduino and BASIC Stamp
VGA resolution (640x480) RGB565/YUV655 color sensor
Image processing rate of 8 frames per second
Onboard Image Processing (QQVGA 160x120)
Track user defined color blobs in the RGB/YUV color space
Segmented (thresholded) image capture for tracking visualization (over serial or to flash card)
80x60 image resolution
Monochrome color space
Histogram generation (up to 128 Bins)
Arbitrary image clipping (windowing)
µSD/µSDHC flash card slot with FAT16/32 full file system driver support
w/ Directory and File manipulation

Joe Dunfee
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

I didn't really want to put out a video until I got the averaging stuff done, so this is still pretty rough...

Ignore the incorrect solutions, they are very jittery; the correct solution is the one one the left. If you look at the camera's POV in the top left you can work out which one it is.

This is only with the raw results of 3 points, and I just have to estimate the lights' real world positions with a ruler, which is why there is some jitter, however it is not too bad. With this setup, I can make it average four calculations for the same solution, which should make it much better. In the final solution, I will be using five points each time, which gives you 20 different ways to calculate the answer. I will also construct it very carefully so I know their actually positions exactly. Hopefully by averaging 20 results it will be totally stable. Also note that some of the jitter is genuine because I was holding the board on the edge and waving it about.

[youtube]http://www.youtube.com/watch?v=_ccLQtdlErI[/youtube]

For the first few seconds before I move the board, you can see that the correct solution is almost completely still. This demo is running at 120FPS.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

@ cadcoke5

Thanks, I love open hardware projects like that. It looks pretty good for robot vision with the build in processing, but as you point out the 8FPS means it probably can't be used for VR.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

Great progress in a short amount of time.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

Thanks it has been going pretty well. I probably won't be able to do much this week because I'll have a lot of work at my job.

The week after that though, I'm on holiday and should have my new lights, so I am hoping to move it on quite a bit then.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

Are you still planning on ceiling mounted lights? It certainly has the best properties in terms of visibility and scaling, but it's a little harder to mount. In theory you could use wall mounted - or even floor markers but it would require a lot more markers in total to get the same performance.
LeeN
Cross Eyed!
Posts: 140
Joined: Sat Jul 17, 2010 10:28 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by LeeN »

Are you using perspective vanishing points to compute thr rotation matrix and then plane intersection to compute distance or are you using another technique?
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

Are you still planning on ceiling mounted lights? It certainly has the best properties in terms of visibility and scaling, but it's a little harder to mount. In theory you could use wall mounted - or even floor markers but it would require a lot more markers in total to get the same performance.
In a way, yes its going to be ceiling mounted in that all my design effort is aiming towards a system that could be used for Holodeck/VR Laser Quest/VR Deathmatch sort of thing. Basically against me, I want low latency, accurate, wireless, multi-user and large area; but on my side I have ability to totally control the environment. This last part is really the key to getting everything fast enough. I have thought a little bit about how you could make it easy to do at home, but its not what I'm aiming for at the moment.

However, I'm trying to keep it as generic as possible at the moment, hence "positioning" not "head-tracking".
Are you using perspective vanishing points to compute thr rotation matrix and then plane intersection to compute distance or are you using another technique?
I am treating it as the "P3P Problem" - Perspective 3 Point problem. I made this picture to help explain;
Image
You use the fact that you know the point's actual location in the world, and their position on the image plane, and the image plane's position relative to the camera location, to calculate the pose of the camera.

This problem (also called PnP when more than 3 points are used) is pretty well studied in computer vision. Despite what TrackIR claim they have not got "patented Math" to solve it :roll: there are lots of papers out there and I am testing different solutions. The best bet so far seems to be Kneipel-et-al's algorithm because it is so fast. It is a bit sensitive to noise but the speed means you can afford additions to make it more stable. However, in general the problem is not that hard, it's really just trigonometry, I think it was first solved in about 1860 :)

I'll post a more detailed explanation about how my particular system works this evening, together with a new video.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

Unless you are trying to program this on an embedded processor, I would be surprised if you had speed problems with any of these algorithms on modern CPU's. They had to come up with all kinds of tricks in the 70's and 80's, but these days you can usually just code the formal math and not worry about performance.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

The only bit that is slow is the machine vision/image processing stuff, I have already dipped below 187FPS a few times with some tests. To run in a home for example, you might want to use adaptive threshold to pick out features, but I found the OpenCV implementation of it too slow.
LeeN
Cross Eyed!
Posts: 140
Joined: Sat Jul 17, 2010 10:28 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by LeeN »

So it sounds like you are using the 4 points to do 2 to 4 PnPs. That sounds like it would solve the mirror issue with PnP that limits the pitch of trackir (in addition to their use of reflectors on VectorClip) which is why TrackIR is not good for VR head tracking.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

I added the code to identify the correct solution from the 4 possibilities. I also put in some averaging stuff, but it is still too shaky.

The disappearing/major glitches are due to me not bothering to write multi-threaded code properly, not from actual accuracy errors.

[youtube-hd]http://www.youtube.com/watch?v=2EgHCtqeys0[/youtube-hd]
LeeN
Cross Eyed!
Posts: 140
Joined: Sat Jul 17, 2010 10:28 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by LeeN »

Looks very promising!

When I was testing TrackIR I noticed the noise came from the way they computed the 2d positions. It seemed that with slow movement I would see the coordinates pop as intensity of the pixels changed. I made this worse when I started trying to compute an offset for the position of the eyes.

If it's not something similar it could be from the ps3 eyes cmos mixed with small movements causing the bottom pixels to be slightly ahead in time.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

So I made a new board with a triangular RGB grid, and also tweaked the point detection algorithm to make it a bit more accurate, however I am having trouble with the algorithm for identifying the triangles.

This is the board...
Image

Here are two example shots (small window is actual camera view, large one is extracted points scaled x2.5)
Image
Image

This last image shows the problem with identifying the triangles. It is not as simple as finding the closest together R, G, B points because of the perspective. A safe first step is to connect each point to the closest point that is a different colour, however it is not always safe to connect the next closest one, even ignoring points that lie on the same line.

I am trying to reconstruct the lines in the bottom image here...
Image

I was planning on putting white lights inside the triangles to ID each one uniquely, this is why I need to break the sections of the image up. I am sure it is possible to do, it is just not that obvious.

I have a few ideas I could try out but I think it might be easier to redesign the board pattern with a target (easy and fast) algorithm in mind - one that is robust to extremes of perspective. I have four colours of LEDs to play with; there are plenty of different things to try. I am currently thinking that something like using the R/G for X/Y lines like they did in the Scalable VR Environments paper might be a better starting point.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

It seems like you could use the inherent geometry of triangles to solve this. For example, consider the red point in column 3 (third line). If you connect closest points you will end up with three collinear points. But what if you do this?

1. Pick any dot.
2. Pick the closest dot that is not the same color. This has to be an edge of a triangle.
3. Now pick the closest dot that is not the same color of the first two dots and also not collinear. That has to be a valid triangle right?
4. Repeat. You can probably construct the whole graph this way.
5. You might also be able to speed up the search by projecting lines along known triangles edges to target your search towards expected points locations. Maybe that will save you from doing n^2 distance calculations.

I believe that you have plenty of geometry available to determine this plane without resorting to lots of extra markers. Just my 2 cents :)
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

No #3 doesn't always work unfortunately. In the bottom triangle, the closest red dot to the bottom green and blue is the one at the top.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

I guess that's true.

I still postulate that there is enough information to interpret this plane, but I don't have the answer off the top of my head. Maybe some sort of constraint satisfaction search? Also I guess there is a density gradient to the points. High density to low density defines a sort of axis which might be helpful. And it looks like there is additional point radius information which could be used. Surely somewhere in the academic literature this has been solved before...
LeeN
Cross Eyed!
Posts: 140
Joined: Sat Jul 17, 2010 10:28 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by LeeN »

I'm not sure there is a solution for this, it's kind like a moire pattern where things start looking correct when they are not.

The best I can come up with is the fact that the center of a triangle is intersected by lines created by 2 dots of the same color. So if you connect dots of the same color that do not intersect another dot the places where the lines intersect is the center of your triangle. This works in your case but the problem occurs with the reds at opposite ends of your pattern, they can connect with out intersecting another point, the only thing is the line that is created doesn't perfectly intersect with other lines from other colors.
foisi
Cross Eyed!
Posts: 105
Joined: Wed Sep 22, 2010 3:47 am
Location: Toulouse, France

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by foisi »

Maybe if you do the solution of Brantlew but you don't start with a random dot but with the ones who give the shortest distance (in your example you start with the triangle on the top) and you add the constraint that a line cannot cross another line ?
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

You really just need to find a single triangle. The first triangle is a blind search, but once you figure out that first triangle, you know the orientation of the plane and the grid is such a regular pattern that you should be able to project vectors outwards from that triangle to search for the other grid points.

You may be able to use this type of logic to test "triangle hypothesis". For example, construct a possible triangle and then project vectors along the edges. If two of the triangles edges don't line up with a series of points then you know that your triangle hypothesis is incorrect.


Edit: or how about this. We actually have quadrilaterals to deal with, not just triangles so do this... Create a triangle hypothesis. Now "mirror" the triangle over and look for the 4th point that should form the quad. This quad should have no other points in the interior or along the edges. If there are other points within the quad, then your triangle hypothesis is wrong.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

I'm nowhere near proving this... but I've got a hunch that if you find the convex hull of the points (like, imagine them as pegs and putting an elastic band around them), then any edge between different colours is valid...

Then you could delete a single point from the perimeter set and go again recursively. I think it works for these points sets can anyone think when that wouldn't work/why that would work?

EDIT ---------

Nope, doesn't work by itself; if the green dot on the far right was missing, it would go wrong.
User avatar
Fredz
Petrif-Eyed
Posts: 2255
Joined: Sat Jan 09, 2010 2:06 pm
Location: Perpignan, France
Contact:

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Fredz »

You could also start from a proven technique for optical head tracking like this one :
http://www.abs-tech.com/produto.php?id_produto=918

It's used for shutter glasses and the camera must be able to see all the markers, but you could make a combination of them, for example four sets with the same arrangement but a different color. You'd need to find a configuration for which at least one set is always visible wathever the orientation of the head is. For this you could write some software that generates images for many viewpoints and test if all the markers of at least one set are visible in all the images.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

How about this...

1. Pick a random dot.
2. Pick the next 3 closest dots to form a quad.
3. If any dot sits along an edge of the quad then the quad is invalid. Otherwise the quad is valid and you have two valid triangles.

I think it works with that dataset. You don't even need the color information except to split the quad properly. The one place where I can see it breaking down is if you chose 4 points that formed a Y junction. But I'm not sure that is possible and if so you could constrain it to only pick convex quads.
User avatar
AngelJ
Cross Eyed!
Posts: 102
Joined: Wed Jul 06, 2011 9:47 pm

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by AngelJ »

brantlew wrote:How about this...

1. Pick a random dot.
2. Pick the next 3 closest dots to form a quad.
3. If any dot sits along an edge of the quad then the quad is invalid. Otherwise the quad is valid and you have two valid triangles.

I think it works with that dataset. You don't even need the color information except to split the quad properly. The one place where I can see it breaking down is if you chose 4 points that formed a Y junction. But I'm not sure that is possible and if so you could constrain it to only pick convex quads.
I like the idea of using quads. It seems like it should work for some of them, but I don't think it'll work for all of them since quads are often not composed of the 4 closest points:

Image

Sorry, I know this diagram's a little hard on the eyes.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

AngelJ wrote:I like the idea of using quads. It seems like it should work for some of them, but I don't think it'll work for all of them since quads are often not composed of the 4 closest points:
Helpful diagram. Step 3 is designed to eliminate invalid quads that occur when the proximity clause (step 2) fails.
User avatar
AngelJ
Cross Eyed!
Posts: 102
Joined: Wed Jul 06, 2011 9:47 pm

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by AngelJ »

brantlew wrote:
AngelJ wrote:I like the idea of using quads. It seems like it should work for some of them, but I don't think it'll work for all of them since quads are often not composed of the 4 closest points:
Helpful diagram. Step 3 is designed to eliminate invalid quads that occur when the proximity clause (step 2) fails.
Yeah, it shouldn't report any invalid quads, but I'm wondering if some of them would have to be constructed by other means (maybe by projecting vectors as you mentioned earlier) since they never fall inside one circle.
User avatar
cybereality
3D Angel Eyes (Moderator)
Posts: 11407
Joined: Sat Apr 12, 2008 8:18 pm

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by cybereality »

Maybe a dumb question, but why do you need more than 3 lights?
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

Two reasons that I know of. For one it allows you to roll and pitch the head angle sharply and still track position. A single triangle would go out of camera view - assuming you use one camera which is the simpler and cheaper option. Secondly, Chriky mentioned that he was going for a general solution for an arena-style room where you would need to track over extended ranges.
repsilat
One Eyed Hopeful
Posts: 2
Joined: Mon Jul 02, 2012 6:27 pm

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by repsilat »

With this small grid, every time you get three co-linear points of different colours they must be the edges of two triangles. You want to find as many of those as you can, because they're guaranteed to be part of the solution. This almost completely solves the two examples given, and it's probably going to turn up a triangle or two. If things aren't really easy from there then you're in trouble :)

If this isn't enough you can look for almost-parallel lines or common vanishing points, depending on the angle of the scene. Note that parallel lines always have the same colour-order, and that's a good way to filter out bad solutions. This is more than enough to solve the examples.

As a last resort: Probably mentioned earlier, but any line directly between two "A"-coloured points bisects a line between a "B"-coloured and a "C"-coloured. It should look like a lot like a bisection in screen-space too, and that's two easy triangles if you're really desperate. At this point you're almost certainly fine, though, especially using the stuff you've already done.

Some comments on your earlier work:
brantlew wrote:1. Pick any dot.
2. Pick the closest dot that is not the same color. This has to be an edge of a triangle.
This isn't actually foolproof at low angles, but it still might be a part of a useful solution - you may not see those angles in practice, and you'd certainly be forgiven for not reconstructing inputs you considered "extreme".

A quick comment on the grid layout, too - the colour pattern is rotationally symmetric, so if only some of the lights are visible you may not be able to uniquely reconstruct the view direction. It probably won't matter in this setup because the angle of the camera will be restricted, but if you want to do something "freer" you'll need something else.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

Thanks for all the feedback and ideas everyone.

Just to clarify (I've spread posts about this across three different threads I think) what I am trying to make is a system that can be used for VR Laser Tag. My target specs are...

- 6DOF positioning
- Wireless
- Accurate (~1deg and 1mm)
- Low latency (~10ms)
- Large area (~1000 sq m)
- Several users (~20)
- Cheap (£100s not £1000s)

My basic design is a room with the ceiling and possibly walls covered with coloured LEDs. The users (as many as you want) would then have cameras mounted on their HMDs looking up. I want to design a specific pattern for the LEDs so that it is possible to write a function that maps directly from the camera's view image to a pose in global 3D space. I want to avoid any kind of 'tracking' at all costs. Because it has to be multi user, I can't afford any system that can 'drift off track'. To sum it up, people need to be able to run through doorways at speed :)

To give an idea of the solution I am aiming for, imagine wallpapering a whole room with pieces of paper with AR markers on like this - http://www.ravenshoegroup.com/blog/wp-c ... RSGAG1.jpg - with every marker different. Given any view, you would be able to work out exactly where the camera was in the room from what markers it could see, and how they were distorted.

I want a system that works like that but is cheap and fast :D
This isn't actually foolproof at low angles
This is right; even this basic first step is sometimes invalid. With this in mind, I have come up with a new design that I think will work pretty well, and is better in a few ways. I think if the coloured grid looks like this...
Image

People can chip in for the algorithm for identifying the grid on this, but I looks like something much simpler will work. There are several options, from doing a rough line detection algorithm to doing a closest-of-the-same-colour type thing. The angle you have to look at to make two reds closer incorrectly than correctly is very very shallow; so shallow that it would probably break down in other ways at that point (with lights blocking each other).

The advantage of this design is it allows for a lot more unique patterns even without considering neighbouring cells. Whereas the proposed triangle solution had 8 base IDs and 4096 if you could see a triangle and all its neighbours, this design could fit four white lights inside and has varying corner colours, giving 96 base IDs, or 24,000 if you can see two neighbours.
Image

I will remake a demo board with this design then try out some algorithms again.
Last edited by Chriky on Wed Jul 04, 2012 4:13 pm, edited 1 time in total.
profvr
One Eyed Hopeful
Posts: 44
Joined: Thu Jun 07, 2012 7:22 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by profvr »

Hi, there is a potentially more elegant solution to your problem, which is just to abandon the regularity of your grid (unless that's a design feature!).

Here is a paper from last year's IEEE VR conference Random Dot Markers, Uchiyama and Saito which tracked markers made up of random dots. By detecting structure from relative lengths of edges, it is possible to identify the individual points and then track the plane from that. You can generate lots of these markers and plaster the ceiling of a 1000m2 space (I like the scale of your ambition!)

You said earlier in the thread that you don't want to "track" but does that mean you don't want to track between frames? Whilst it is important to be able to reinitialise the tracking from any one frame, tracking between frames is usually faster, but also helps preserve robustness (e.g. you can assume that a pair of markers is rigid between frames, and thus you can exclude certain transformations in the next frame).

If you wanted a simple way forward with the current markers, I would suggest searching for the grid lines, not individual triangles.

E.G.

1. Find closest pair of points and find line segment between them
2. Find all other points that lie close to that line.
3. Sort the points on these lines and ONLY accept lines that go RGBRGB - diagonals will repeat the same colour
4. Repeat this for all closest pairs

5. This gives you a set of hypotheses about grid lines that you need to filter. The longest ones should be the grid lines, and they'll fall in to two sets. Each set should converge to a single vanishing point.

6. From the grid you can then identify the plane.

You might want to apply some lens correction first so your grid lines are straight.

You can make this robust to missing markers (dead leds, occasional bad filtering), by relaxing the assumption about colour ordering, and accepting lines with "gaps".

You also said you wanted people to move fast; have you thought about camera blur? Blur is bad (its blur) and good (the direction of the blur could tell you the velocity of the camera!). But you can combat it by flashing the LEDs so they are illuminated for a fraction of the camera exposure. They would need to be bright though. If they weren't bright enough and if you had an IMU on the camera you could try deblurring the image.
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

Yes I was intending to avoid any tracking between frames, but I'd be interested to hear reasons why you think inter-frame tracking would be better. If you can arbitrarily reset the tracking, why wouldn't you just calculate it directly each frame? Purely for speed reasons?

I do also want to make a totally separate trackerless system using PTAM; it's incredibly good, probably the best I've seen but it isn't stable enough to deal with big movements I don't think. All of those systems can drift gradually off over several minutes of fast, erratic motion (which running around would be).

As for blur, I did a test and I couldn't get them to blur at all really, even violently shaking the camera. It looked blurred on the screen but if you saved out an individual frame it was still pretty clear. It's running at 187FPS with a very low exposure, but I don't know exactly what the total exposure time is.
profvr
One Eyed Hopeful
Posts: 44
Joined: Thu Jun 07, 2012 7:22 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by profvr »

You can get a few speed ups and potentially more reliability.

If your ambition is to track a large area, you'll need multiple marker panels. A good hypothesis is that the marker you see on the image was in the last image, and thus you can more reliably detect/match it. If you detect one maker in the frame, you can use the structure of markers you saw in the last frame, to hypotheses which other markers are in the frame. If there is very little motion, you can even just track individual points.

If there is lots of motion then you do have to assume you'll have to start again. This is a weakness with PTAM-like processes that can fail badly when they lose track under significant motion. I wouldn't call that random dot marker, PTAM-like though. The basic method (if I recall correctly) is to cluster dots, find the centroid and then measure the sets of length from the detected points to the centroid. This set of lengths can be used as an identity.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

@profvr: thanks for the guidance

@Chriky: Just thinking about this for an individual setup (possible consumer product). Obviously ceiling mounts have the best properties in terms of signal simplicity and visibility, but they are not as convenient to set up. I wonder if a roll-up floor mat could be built with the LED pattern. It would have a central "play region" without lights that you would be confined to and the camera would have to mounted to point downwards at an angle. The mat could be rolled up and stored when not in use so the physical setup would be simple and non-permanent. The technical problem is a bit harder because of your body in the frame and the physical size limits of the mat but it seems possible in principle. Would there be any advantage to this over a Kinect or Hydra type system?
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

I think the best consumer product would be a RIFT with two PS3 Eyes mounted directly in front of the eyes. You could ideally get one of the replacement lens that are available to match the FOV as closely as possible. Although it would be quite pixelated (480x640 per eye) it could do that at 75FPS which isn't too bad.

If you have two cameras looking at the same scene, and you know their relative positions then you have way more information about the scene and trackerless algorithms perform really, really well.

Stuff like this...
[youtube-hd]http://www.youtube.com/watch?v=zqTz_o4-nZ4[/youtube-hd]

I think if you had stereo cameras running at a decent frame rate, you probably wouldn't need any markers. You could just have a single one that would allow the view to reset any drift every time it came into view.

A system like this would allow firstly for awesome AR, and secondly for VR, where people could walk freely around their own flat in a VR environment, where the 3D scene or actual video feed could be faded in for safety if the user was about to walk into something.
User avatar
brantlew
Petrif-Eyed
Posts: 2221
Joined: Sat Sep 17, 2011 9:23 pm
Location: Menlo Park, CA

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by brantlew »

Chriky wrote:I think the best consumer product would be a RIFT with two PS3 Eyes mounted directly in front of the eyes.
That's a good idea. I wonder how variable the performance would be based on the density and positions of objects? It seems like a flat empty room would perform worse than a room sprinkled with furniture. Also I wonder if reflective surfaces would disrupt the sensors?
User avatar
Chriky
Binocular Vision CONFIRMED!
Posts: 228
Joined: Fri Jan 27, 2012 11:24 am

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by Chriky »

I think it can deal with reflective surfaces ok, and yes they tend to be better with lots of corners around. I finally remembered the name its called "visual odometry", specifically "stereo visual odometry".

Here's another good video, there are plenty of others in related videos on Youtube...
[youtube-hd]http://www.youtube.com/watch?v=wI1kd3acQcI[/youtube-hd]
WiredEarp
Golden Eyed Wiseman! (or woman!)
Posts: 1498
Joined: Fri Jul 08, 2011 11:47 pm

Re: 6DOF Positioning System - PS3 Eye and fiduciary markers

Post by WiredEarp »

Good point about the stereo cameras, however, I suspect that the increased processing load of trackerless might impact on the latency?
Post Reply

Return to “VR/AR Research & Development”