6DOF Positioning System - PS3 Eye and fiduciary markers

[PatimPatam]

Hi Chriky, very interesting project indeed, I really hope you can make it work; can't wait to try my first VR laser tag ride! I arrived here from this other thread:
http://www.mtbs3d.com/phpBB/viewtopic.php?f=120&t=15040

I'm a .Net developer, done some computer vision, raytracing and opengl stuff back when i was at uni, but I'm a bit rusty on that front right now.. Anyway I believe some of the things you're working on could be used to solve a completely different problem which has been bugging me since i heard about the Oculus Rift: Proper 6 DOF tracking for games in a "sitting in front of the computer / sitting on the sofa with a controller" scenario. Basically something similar to what the TrackIR offers, but which actually works when you turn your head/torso more than 45 degrees. Ideally should work when turning the whole 180 degrees looking back, and also when looking straight up or down (90 degrees).

Personally I think this should be the default setup for every FPS-VR game out there: aiming with the right hand, movement with the left hand, and independent 6 DOF viewpoint with the HMD. Carmack himself admitted that it would be great if you could strafe slightly with your head, or tilt forward to look around corners, etc. Unfortunately we all know gyroscopic trackers like the Hillcrest are not good to get accurate positioning..

So I was thinking this could be solved by using 1 or 2 PS3-eyes and attaching several LED markers all around the HMD (in the corners: front, sides and back, and maybe on top/underneath as well). It would be really cool if you had the time/energy to try this with your custom image recognition software, if not I think i might give it a go myself, starting by programming something similar to what you've shown in the videos. The fact that the Rift is very square-ish could be used in our favor too, as solving the planar P4P problem should be easier than the general P3P. I also thought that in order to simplify the process and get more precision, I could use optical recognition only to find the positioning x-y-z and leave the yaw-pith-roll to a gyro tracker like the Hillcrest.

Once the whole tracking bit is working, the next step would be integrating it with an existing game that supports 6 DOF like Arma2, maybe using FreeTrack. Unfortunately i don't think Doom 3 BFG will support this.. Another possibility would be to modify an open-source engine like Quake 3 to be able to map the camera translation; i am not so confident on this one but I could try I guess!

Sorry for the long ramblings.. if you made it this far, any thoughts?

[brantlew]

Well it seems the goal of Chriky is the same goal you have - he's just thinking in terms of a larger scale. Scaling down would be trivial. I think a single camera implementation with just a small marker array (maybe even just a single quad) would work fine for the seated scenario - no need for added complexity. Particularly if you augment the rotational components with an inertial tracker.

[PatimPatam]

Well while it's true that scaling down Chriky's system could solve the seated scenario, i believe that would still be overkill, not the other way around!

I think it would be much more convenient for the average user to wear a HMD with integrated markers and simply sit in front of a camera than having to mount LED boards on the ceiling of the living room and wearing a camera on top of the HMD.

EDIT: Also, I doubt a small marker array would be enough even if seated: say the camera is pointing up towards the ceiling and your array, what happens if you look straight down to your feet turning 90 degrees or more? (my guess is the camera is going to be pointing the TV or the fridge!)


From a technical point of view the pattern recognition bit would be quite different too.

[Chriky]

Sorry for the lack of updates I've been ridiculously busy with work, I'll get back to you though PatimPatam

[Fredz]

Also, I doubt a small marker array would be enough even if seated: say the camera is pointing up towards the ceiling and your array, what happens if you look straight down to your feet turning 90 degrees or more? (my guess is the camera is going to be pointing the TV or the fridge!)

You need at least 7 points that are always visible from the camera to correctly calculate the orientation of the points. If you know the intrinsic parameters of the camera (FOV, aspect ratio, skew) only five should be needed.

Have a look here for more details : http://en.wikipedia.org/wiki/Fundamenta ... er_vision)

And here for a more robust solution with at least eight points : http://en.wikipedia.org/wiki/Eight-point_algorithm

You should also consider correcting the distortion from the lens using software radial distortion correction : http://en.wikipedia.org/wiki/Distortion ... correction

OpenCV has imlementations for these kinds of algorithm.

[EdZ]

IIRC, that only applies to homogenous points. You can cut that down if the points can be distinguished, e.g. by colour. A known triangle of 3 primary coloured points can be located and oriented in all cases except for edge-on (where one axis is ambiguously positive or negative). A fourth distinguishable marker should eliminate this.

For the 'markers on HMD' setup, you might be able to get away with two triads: a primary coloured (R G B) one on the front, and a triad on the back with mixed colours (rg bg rb). This should be easy to make with monochrome and bi-coloured LEDs, and distinguishing markers can be done simply by comparing colour channels. This does, however, assume that the markers do not occlude each other, and that there are always at least 3 visible, and that the markers are fixed with respect to each other (tricky if they were attached to the back of an adjustable headband).

[PatimPatam]

@Chriky
Don't worry, take your time to think about it if you're busy!

@EdZ
Thanks for the advice, good point about the fixed distance markers.

[Zaptruder]

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.

I've been thinking this would be the ideal solution to all the translation problems - but what's the reason that the community hasn't gone this direction yet? Is the processing latency to resolve the space and the direction just too high right now? Can this be reduced by calibrating the space (i.e. spinning around the cameras to create a virtual map of the space before use)? Or is it more a case of the device (and its attendant wires) simply been impractical for mounting onto HMDs at this point in time?

[Namielus]

Really liking alot of the ideas here.
I agree about calibrating the room. I am no expert but it seems logical to me.Less calculations for the computer if a model is generated, then simply tracked, rather than constantly having to analyze and generate a model of the room and movements on the fly.

Im really hoping to see fast progress in developing a good foundation for having entire rooms tracked.

I was toying with a pulley system a few years back dreaming about vr, if the rope gives way to your exact weight,and move in a slow loop, you would feel like you are climbing even tho you are just staying in the same position in space.
If you had a room with that rope, you could sort of climb up and down into other rooms, sometimes with a really high fall.

With Galvanic vestibular stimulation maybe you could feel like the rope was swinging.

[Chriky]

@ PatimPatam

The main reason I (or I guess 'we', in other threads) decided that moving camera/fixed patterns was better than moving patterns/fixed camera is that it allows you to go fully wireless with a backtop computer. What you describe is exactly how TrackIR works; it is essentially the same system it just has the added requirement of getting the sensor information back over to the user (to the HMD essentially) after working out the position. If you want totally wireless you either need wireless data transmission or you need all the sensors mounted on the user. The problem with wireless data transmission is you are in a latency race with your nervous system. You have to get the updated image to the eyes ~20ms after the brain tells the muscles to move. It's not impossible but its not trivial.

@ Zaptruder

Yes, it is basically the complexity of the algorithms. Complexity both in terms of how conceptually hard some of them are to understand, and therefore work with and complexity in the technical sense of them having to crunch serious numbers to come to a solution. Remember with all these videos they are normally designed to make sure their PhD passes viva and not to give an honest warts and all presentation. Most of them don't run in real time, or if they do do it on 4 fast cores and manage ~60ms. Most of them can't deal with jerky movements. I'd summarise the start of the art on video odometry by saying the science has been done but its probably one hardware generation at least from being real world usable. It has military applications (drones) though so it seems like there's some funding for it.

---------

Doing a bit more work on my project again now. I realised I jumped needless far from the original idea and if I retain the triangular grid, and just colour the LEDs in straight lines, the algorithm for reconstructing the grid in screen space should be much easier.


You still get the benefit of having 6 different types of outer pattern, and the step of connecting closest of same colour is pretty safe (breaks at extremely low angles). I am just writing a Python test bed now where I can try out algorithms quickly. I'll post the code when I'm done in case others want to have a bash.

[brantlew]

Cool. Glad to see you're still working on it.

[FingerFlinger]

@Chriky

Do you have any personal experience with visual odometry? I ordered another PS3 Eye, and I'm going to start playing around with it.

Also, when you are talking about wireless latency, are assuming that the video data is being streamed, or just the positional data? If you do your image processing on-board and then send the results to your backtop, I don't see the latency being a huge issue... Now, getting a microcontroller to do that much number crunching is a different story, but I guess you could dedicate another PC to the task.

I look forward to seeing more of your progress (and code!)

[Namielus]

I am very much a layman here, so sadly I cant contribute much on the technical side.
I am just wondering;
If you have accelerometers, magnetometers, gyrometers or such, combined with a camera tracking
led markers, or even printed ones, couldnt the latency of the camera be accounted for?
The accelerometer tracks immidiate motion, while the camera is looking into the world with a certain frames-per-second
telling the tracking unit where it is in space. Just to correct for drift and improve
accuracy over time. It could account for its own latency in terms
of sending image to computer and processing image.
As long as something starts moving exactly when you move it, the precision could be secondary
within reason?

Sort of a quality control that happens 60 times per second or more.

[brantlew]

@Namielus: It's often the other way around. The cameras typically have the lower latency. It may not be obvious from the specs because you might be comparing a 120Hz sensor against a 60fps camera. But in that race - the camera wins because it's almost perfectly noise free. The sensor on the other hand has to be noise filtered which increases the latency at least 2x (depending on the application).

[Namielus]

okay I see, thanks

[PatimPatam]

@Chriky
Thanks for the reply, maybe i didn't explain myself very well but i was actually not thinking about wireless.. It would definitely be much better, but in the case of seated play i was mentioning not essential i believe.

Even in that scenario (seated and wired, or standing without turning like in Carmack's demo) i think it would still be a great benefit to have 6 DOF without the lame 45 degree restriction of the trackIR. So i'm giving it a go, see what i can come up with

Looking forward to your progress too!

[cadcoke5]

Chirky said
The main reason I (or I guess 'we', in other threads) decided that moving camera/fixed patterns was better than moving patterns/fixed camera is that it allows you to go fully wireless with a backtop computer.

Laptops have been getting more powerful with less draw over time, but how long would you expect the laptop battery to last if it has the kind of computer power you want?

I really hope the overall system is flexible enough to allow a variety of tracking methods. Since many people have a newer computer, they may have an older computer laying around unused. That extra computer may be ideal for plugging the tracking cameras into. It can do the processing and then relay the results to either another fixed computer, or your on-board computer.

Oh, one other idea to mention. Regarding the camera on the user system, to get targets on your walls and ceiling, you could do projection. Slide projectors are dirt cheep, if not free. You could project a slide of the pattern you want. Another alternative is to just use the lens system and focus it on a small circuit board with your LED's mounted to aim their light towards the lens. I just thought of the issue of chromatic aberration. The monochromatic LED's will each be affected differently, depending on the color and location. That would cause their relative locations to shift.

One more related idea. Red and green lasers are fairly cheap. A system to project dots from them would make much crisper targets than the projected LED's. Diffraction gratings, or even a hologram type of system (a holographic optical element) could project multiple patterns around the room.

Joe Dunfee

[divide]

@Chriky: Coming from this topic; you could use the PS3 Eye+PTAM source code by Klein, it would give markerless 3d tracking with 25-35ms latency (considering PS3 Eye+PTAM latency).
Latest gyros and accelerometers data could also be integrated to the PTAM tracking to go down to 8ms latency on top of that (no filtering required on such a tiny timeframe).

[Chriky]

Do you have any personal experience with visual odometry? I ordered another PS3 Eye, and I'm going to start playing around with it.

I don't have any experience except playing around myself (I mean I didn't study it at uni or anything) but I have understood a few papers. Glad you've got the Eye; let me know if you need any help getting going with it.

Coming from this topic; you could use the PS3 Eye+PTAM source code by Klein, it would give markerless 3d tracking with 25-35ms latency (considering PS3 Eye+PTAM latency).

PTAM is on my list of things to try out but I am still finding it hard to get the time for geekery at the moment
I would think that 30ms is too much latency to avoid motion sickness though; bear in mind all that latency is before any game code runs. I guess its something we'll just have to try out and see. The demos are certainly impressive enough to warrant some experiments

[FingerFlinger]

Take this with a grain of salt, as I can't remember precisely who said it, but my understanding is that 50-70 ms is tolerable for gross translational tracking. Rotational is more finicky.

[Chriky]

That's from muscles moving to light hitting the retinas though, isn't it? We're talking about 30ms between muscles moving till just having an orientation matrix. After we've got that you still need to render a whole scene, and then even after you've produced the pixels, you then need the screen to actually fill the liquid crystals with your new frame. Carmack was saying that just that last bit (screen filling) takes about 20ms. The Rift's tracking stage only takes 4ms (assuming its got Carmack's custom 250Hz firmware).

[divide]

PTAM is on my list of things to try out but I am still finding it hard to get the time for geekery at the moment
I would think that 30ms is too much latency to avoid motion sickness though; bear in mind all that latency is before any game code runs. I guess its something we'll just have to try out and see. The demos are certainly impressive enough to warrant some experiments

...hence why I proposed to add the latest gyros/accel data (latest 20ms timeframe) after PTAM to go down to 8ms latency
However as mentionned above I bet latency is specially critical for rotation, a bit less for translation since you usually have way more visual difference by rotating 1 degree than by translating 1 inch.

[Chriky]

After being distracted briefly by working on tracking walking with the Hydra, this evening I finally did a bit more work on this project. Firstly I mocked up a room to walk around that could simulate what a PS3 Eye would see if it was mounted on your head looking at the ceiling and you moved around naturally.



The good news is that it is very rare to angle you head enough to cause significant distortion to the image the PS3 Eye sees.

I grabbed four of the camera images and made a Python program to help writing the algorithm to reconstruct the triangles. This is where I had got stuck before so this setup makes it really easy to try stuff out before trying to code it properly in C++.

If anyone else wants to have a go I have attached the code. You need to provide an implementation for the function draw in the file draw_grid.py. The file contains an explanation for what you get passed in and what you should output. To test your algo you should run the other file, grid_algo.py. There is a demo algo that just draws a cross on every point;



You need pyglet installed on your Python for it to work (btw pyglet only works on 32bit Python). The easier way to get it is to set up easy_install then go to the Scripts folder in the Python dir and run easy_install pyglet.

[cybereality]

Cool. Making progress.

[Chriky]

This is the result of connecting each point to the closest point of the same colour;



You can see it makes mistakes in the corners where there is a "line" consisting of a single point

[android78]

all of the error lines you've shown have one end connected to a point that has 3 lines already connected. can't you just filter out the one that least fits a straight line with the other lines attached to the point?

[zalo]

I noticed that sometimes your crosses/lines don't always land in the center of the blobs, and I'd like to improve your blob/point detection algorithm but doing all that voodoo with Python is too crazy for me.

What I do is
Initialize values in my points for Position Sum (sum of all pixel's positions that make up point), and Pixel Counter (number of pixels in point) to 0.
1. iterate through each pixel (normally)
2. If I come across a pixel with a brightness value over the threshold I
a. Check in my point array if there are any points nearby (increase search radius according to "Pixel Counter")
I. If there are, I add this pixel's position to the point's position sum, and increment the point's "pixel counter" by 1 (more on this later).
b. If there are no points nearby, I make a point with a position sum of this pixel, and a "pixel counter" of 1.
3. Rinse repeat for all pixels.

Then, when I want to get the point's position, I take the position sum (sum of all positions of pixels that make up point), and divide by the point's "pixel counter" to get the average position of the point. Not only will this always land my point at the centroid of the blob, but it will do so with sub-pixel accuracy.

I don't know how you do it currently, but here's my implementation in Processing (Java) using the PS3 Eye SDK: http://pastebin.com/ftdSmw59
Note that the value for searching nearby pixels is a set to "200" (ln 57). It's usually better to set it to some relation of Blob.z (Pixel Counter), but I was testing some things out in this iteration.

[brantlew]

Glad you're back on this Chriky. Very interested to see where this goes.

[Chriky]

@ zalo

The Python stuff doesn't do any point detection actually I just outputted a load of coordinates semi manually. The actual point detection algorithm is accurate to about 1 pixel at 800x600 resolution (so, 2.5x subpixel accuracy for the raw 320x240 feed). I deliberately didn't do this too accurately for this bit though because the grid detection algorithm has to work with some noise. If you want to check whether three points are in line, there has to be some tolerances basically

This is my code for the LED detection part of the code;

Code: Select all

while(_running)
{
	CLEyeCameraGetFrame(_cam, frameBuffer);
	cvCvtColor(frame, grey, CV_RGB2GRAY);
	cvInRangeS(grey, cvScalar(45, 45, 45), cvScalar(255, 255, 255), white);
	cvFindContours(white, mem, &contours, sizeof(CvContour), CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE, cvPoint(0,0));
	std::vector<LED> newLEDs;
	for (ptr = contours; ptr != NULL; ptr = ptr->h_next) {
		LED led;
		CvRect rec = cvBoundingRect(ptr);
		cvSetImageROI(frame, rec);
		cvSetImageROI(grey, rec);
		led.raw_colour = cvAvg(frame);
		cvMul(grey, grey, grey, 0.02);
		cvMoments(grey, conMom);
		led.pos = cvPoint2D64f( (conMom->m10 / conMom->m00) + (double)rec.x,
		                        (conMom->m01 / conMom->m00) + (double)rec.y  );
		led.colour = snapColour(led.raw_colour);
		newLEDs.push_back(led);

		cvResetImageROI(frame);
		cvResetImageROI(grey);
	}
}

Basically it does this;
- Convert image to grey scale
- Threshold above certain value
- Now we have binary image where LEDs are white
- Find contours on this image
- Now we have got the separate LEDs (roughly)
- Loop through each contour
- Get the bounding box
- Get the average colour of box on the colour image
- Snap colour to one of red, green, blue or white
- Square all the values in the grey scale image (kind of like increasing contrast)
- Get the centre of mass of box on the grey scale image

[Namielus]

Am I getting this right? I am trying to put together different models to visualize all the concepts in a realistic enviroment. I just made a simple oculus rift, since nobody really knows what it will end up looking like I didnt put too much into it.

I would like to understand clearly how this is supposed to be implemented in practice, so I can renderer in a real world scenario.

[zalo]

How efficient is that "find contours" function? It looks like it's overkill for point tracking, especially since you're just using it to get a bounding box afterwards.

Also, for grid reconstruction, take the two points of the same color that are closest together, get the angle between them, and determine if all the other points lie near that angle. If you have any points of that color left over, start over with the two closest unpaired points of that color.

[Chriky]

@ Namielus

Yeah that's right except the triangles would be a bit bigger - in my model they were ~16cm apart.

@ zalo

It's pretty fast; complexity wised its O(n) in the number of pixels, microsecond wise its fast enough to go at 187FPS on one core. I haven't really tested it beyond that. It just splits a binary image up into its connected components - I don't think its overkill because you have to do this to get all the different LEDs. I don't know of any faster algorithms, there probably are some out there but it hasn't become a bottleneck yet.

Finding the closest together points of the same colour almost always works (only breaks at really tight angles which I don't care about). You can't do it for every colour in another rare case of there being only two of a certain colour, in opposite corners of the image (this also means you can't do it recursively). However you should be able to do so by using the lines you build up to split the image up into sections, as you know that no colour-line segments will cross each other.

[Chriky]

I have got it finding the coloured strips properly now. The algorithm is pretty much what zalo suggested...
- Find closest together same colour pair
- Extend this line segment to edges of screen
- Delete any points on (within 10px) of this
- Start again
- If line segment crosses any you already have, ignore it



After you have the lines, you can sort the points top-to-bottom (or left-to-right if the colour lines are more horizontal). The problem is now connecting the nodes between the coloured lines. I have a few ideas that I'll attempt tomorrow.

[cybereality]

Cool.

[zalo]

That's really cool! I'm pleasantly surprised at how fast your implementation is. (Mine adds another iteration for every point that it finds, drops below the 125fps (I'm limited to in processing) for more than 3 points.

So far, it looks like you can get absolute yaw, pitch, roll, and z-axis translation from your current setup.
For the XY translation, do you plan on inter-frame tracking or the internal varieties? (I'm more in favor of internal varieties for error cases).

Also, if you do a reverse transform of the points (back to grid form), you might find that the fact the neighboring points are located ~60 degrees off the main line to be of use. That should give you a good starting angle from which you can reuse your old algorithm.

Good luck however you plan on doing internal varieties.

[Chriky]

Ok so I scrapped the design with colours in straight lines. After trying for ages I couldn't come up with a way of stopping it mis-connecting between the colours. It was stable enough getting the parallel lines, but it was impossible to stop an off-by-one error making the triangles between them at shallow angles. Also, more importantly, it didn't have enough capacity for encoding IDs using white LEDs.

I went through what must have been 15 different designs which all either failed at too shallow an angle, or didn't allow enough variation to encode global positions. I made a physical board with accurately drilled holes to help test out patterns and this evening I think I finally came up with one that will work.

The board looks like this;



On a full ceiling the coloured triangles would just repeat like that.

The LEDs within each coloured triangle are so much closer to each other than the LEDs between two different ones of the same colour that it is practically impossible to mis-connect them. The fact that each block is made of up several LEDs gives you the three directions of the grid. You can follow these lines to connect up between R, G and B blocks.

The real advantage of this design is that these blocks then enclose ten white LEDs which can be used to encode 1024 different IDs. By drawing a line between different pairs of points in the surrounding dots, you can check for the existence of a white LED in every position (to get the centre, you have to count the LEDs across the middle and then subtract off other ones that can be checked individually).



As straight lines remain straight under projections, all of this works in screen space. You draw a line segment and see if any of the white points are very close to it.

These hexagons are 28cm across so 1024 different ones means each ID will only repeat several metres apart. Basically it should be a reasonable simple algorithm to work out this much information;



At this point it would just look up the real world 3D location of Hexagon #87 for example, see its LEDs are at (-3.123m, 2.0m, 5.626m)... etc etc and then run the PnP solver to get the camera pose.

I'm going to France this weekend so won't be able to code it up for a while, but I am finally confident I have a design that will work.

[brantlew]

Sounds good. I was curious whether you were still working on this.

It seems like you are going through a lot of trouble to be able to establish global positioning from a single frame (with no other context) - thus the LED encoding scheme. Would it be easier just to use an iterative algorithm and frame-to-frame context to trace movement within the global space? I realize that would restrain it in some ways, but it would also free it to scale indefinitely.

[Chriky]

This is designed for a system where a real world location maps 1:1 to a virtual world location, with physical walls and objects where there are virtual ones. In a situation like I think there are two reasons you need to do something like this;

1. Where do you start? It's not ok to just boot the game like you do with Doom 3 BFG and say, ok where-ever I am in the real world, I'm now looking north and standing at (0, 0, 0) in the game, let's update the position from here. You have to boot up and immediately know where you actually are relative to physical objects. This would require some kind of identifiable marker to start you off, even if you then tracked away from that with an iterative method.

2. What if you glitch/miss a bit? If you have a repeating pattern that you are tracking, what happens if your camera is occluded for a bit or the frame rate chokes for a second? You might think you have moved 1cm but you have actually moved 20cm. There would be no way of knowing this had happened until you ran straight into a wall.

Having said all that, this system would "track" to a certain extent because after you have used up all 1024 IDs you have to start repeating them, so at every ID you pick the one that is closest your last location. As there are so many IDs you couldn't possibly "skip" between IDs and lose your global position. You could also hold back 20 or so IDs to be truly globally unique even in an enormous arena.

[cybereality]

Looking good man. Would love to see a video of this working.

[zalo]

I recently came across fiber optic ceiling illumination systems and I thought you might be interested. Instead of using an led at every point and having a wiring nightmare, you could use a strand of fiber optic cable at every point and have a fiber optic cable nightmare. The idea is that you use a centralized illuminator and a stationary color wheel to get different colors.

[youtube]http://www.youtube.com/watch?v=BncUBQst0-4[/youtube]
In this video, it's a moving color wheel of course.

It might cost a little more, but it would ultimately be safer than an electrical mess. Plus, it reduces the failure probabilities to a single component, as opposed to hundreds of leds.