ceiling navigation

[Rickertsen2]

I was on a boat tonite looking up at the sky, when i had an idea. It goes something like this:Camera pointed toward ceiling + motion tracking algorithms = accurate absolute positioning. Ceilings are great because they will always be perpendicular to the camera and have very definite features such as recessed lights, square ceiling tile patterns, rafters etc. The motion tracking is greatly simplified because you are looking at a perpendicular plane!! What more could you ask for! I am not considering this for FIRST, but i would really like to try it out.

My next project:
2 globe motors
2 encoders
mini-itx PC
a medium sized SLA batt
webcam
a few horizontally facing sonar sensors
some homebrew speeed controllers
JAVA because i am too poor for windows and i don't know the first thing about native linux coding(although i would like to learn)

[coastertux]

Sounds cool! How are you planning to navigate within boundaries such as a field and around objects and other robots? Wouldn't some lights (such as halogens) "blind" the camera?

[Rickertsen2]

Originally Posted by coastertux

Sounds cool! How are you planning to navigate within boundaries such as a field and around objects and other robots? Wouldn't some lights (such as halogens) "blind" the camera?

This is not for FIRST. As for things blinding the camera, they generally only seem to do so in a localized area, which makes the lights even more distinguishable. Sonar or IR sensors will be used for obstacle detection. As far as things that occlude the ceiling go, i can either restrict the thing to an environment where ther arn't any or i can use a lense with a very narrow DOF and ignore areas that are out of focus. If the ceiling signal is completely lost, encoder or intertial dead reckoning can be used until it is reaquired. This is probably just another fantasy of mine as i already have too many projects, but i do have all the parts except a power supply for the ITX board.

[jdiwnab]

The ceiling isn't necessarly perpendicular to the robot. You're driving down a hallway. Theres a ramp. Robot goes up ramp, but becuase the camera is now pointed a little back, it goofs. And ceilings arn't all the same. There are many places with the rectangles for the ceiling as you say, but what if you want to go to Lowes with the bot. Their ceiling is much higher and is more werehouse style. Now you take your robot home with you ("He followed me home. Can I keep him mommy?" lol) and you have lower ceilings and no regular squares. Again, you have an attachment that moves around above your bot. It swings past the camera and confuses the bot. This could also be a freshmen waving his hands over the bot, or going under something.

While I think it is worth the effort to try it, I don't think it would be very practical. I think that if you are just tracking where you are, then a sensor on the floor, like optical mice, would work better. There are fewer variations that would mess it up. They are all right near the sensor (if you make it that way) and with a set distance, that size of objects can be determined and you can still calculate distances. If you have it close to the ground, you would need to either flip the bot or give it one of the few surfaces that you can't track. It still uses the same basic techniques, but would be more reliable. And might be more usable in an event if you so choose.

[Rickertsen2]

Originally Posted by jdiwnab

The ceiling isn't necessarly perpendicular to the robot. You're driving down a hallway. Theres a ramp. Robot goes up ramp, but becuase the camera is now pointed a little back, it goofs. And ceilings arn't all the same. There are many places with the rectangles for the ceiling as you say, but what if you want to go to Lowes with the bot. Their ceiling is much higher and is more werehouse style. Now you take your robot home with you ("He followed me home. Can I keep him mommy?" lol) and you have lower ceilings and no regular squares. Again, you have an attachment that moves around above your bot. It swings past the camera and confuses the bot. This could also be a freshmen waving his hands over the bot, or going under something.

While I think it is worth the effort to try it, I don't think it would be very practical. I think that if you are just tracking where you are, then a sensor on the floor, like optical mice, would work better. There are fewer variations that would mess it up. They are all right near the sensor (if you make it that way) and with a set distance, that size of objects can be determined and you can still calculate distances. If you have it close to the ground, you would need to either flip the bot or give it one of the few surfaces that you can't track. It still uses the same basic techniques, but would be more reliable. And might be more usable in an event if you so choose.

you bring up some very valid points. The reason i choose the ceiling over the floor is because it has more definite landmarks and becase larger areas of it can be seen at one time. I have considered the problems of varying ceiling heights and ramps. At least initially, i would only plan on operating the robot in certian areas all of which have ideal ceilings and no ramps. The exact pattern of the ceiling doesn't matter as long as long as it isn't completely homogenous. Rafters vs ceiling squares are fine so long as the depth of the rafters is neglidible compared to the height of the ceiling. The motion tracking algorithms i have in mind can deal with it.

Note that as far as x,y (but not rotation) coordinates go this sort of system gets less accurate the further away the ceiling is and is totally useless ourdoors.

[jdiwnab]

Many places that have a tile ceiling would also have a tile floor. And while you see more of the ceiling, the landmarks on the floor would be a lot if you get up close to them. As you say, the accuracy of the system drops as you raise the roof (bad joke, but I amuse myself), but the ground clearence would usually be about the same, very low compared to the ceiling. I just think you can get a better, more reliable, more flexable system with the floor. I would love to see it work no matter which way use choose. Now what would really be "out there" would be to navigate on the earth's magnetic fields..... Birds do it, so how hard can it be....

[Gdeaver]

You want to look up. A cruise missile looks down. Your thinking of terrain following systems. The US terrain following cruise missile is an interesting system and could have some civilian applications in machine vision. To bad the critical parts are tied up under national security. I believe Scientific American had a article on it a few years ago. Current machine vision has gone down the path of capturing more and more digital information from an image and throwing more and more computer horse power at it. The cruise missile is different. It takes an optical image and through optical and analog processing - filtering reduces the images information to just what is important. The edges and boundaries of objects which at the last stage are digitized and and compared to a processed image data base.

[Rickertsen2]

Originally Posted by jdiwnab

Many places that have a tile ceiling would also have a tile floor. And while you see more of the ceiling, the landmarks on the floor would be a lot if you get up close to them. As you say, the accuracy of the system drops as you raise the roof (bad joke, but I amuse myself), but the ground clearence would usually be about the same, very low compared to the ceiling. I just think you can get a better, more reliable, more flexable system with the floor. I would love to see it work no matter which way use choose. Now what would really be "out there" would be to navigate on the earth's magnetic fields..... Birds do it, so how hard can it be....

Ideally the floor would be much better. It is at a constant height, perfectly flat and can be shrouded from external illumination. My only problem with floors is that there is a lack of repeatable landmarks on most floor and you can't see a whole lot of them at once. The exception to this might be hardwood floors and those speckled tiled floors. Anything that has texture can be used for relative navigation (look at optical mice), but in order to have absolute navigation, you need some sort of distinguishable features that are unique to an area. They area of uniqueness doesn't have to bee to large becase you will only be pattern matching to previously stored images near the last known postion. You know that the robot can't have moved 500 feet in one second. I think it would really take some experimenting to see what the minimum amout of unique features is. Even concrete floors like those in home depot have things like cracks, scratches, and dirt.

------ edit --------
wow, apparently alot more distinguishable features than i thought in concrete.
[url]http://pictar.net/concrete.bmp[/url
This pic is of about a 6" section of the concrete in my garage. It was taken with a DVT legend 530 Smart Image sensor.
-------------------

I suppose the question is do i really need absolute navigation? In order to answer that i need to figure out what i need this navigation system if for in the first place. The truth is i really don't know. Its just an idea that popped into my head. In addition it would give me an excuse to build a SLAM robot that incorporates cool things like control loops, motion tracking/pattern reckognition etc. These are things that interest me. Perhaps the objective of the robot could just be to make a 2d map of its surroundings. This is probably something i will never build simply because i do not have time but it is fun to imagine anyway.

[Rickertsen2]

Originally Posted by Gdeaver

You want to look up. A cruise missile looks down. Your thinking of terrain following systems. The US terrain following cruise missile is an interesting system and could have some civilian applications in machine vision. To bad the critical parts are tied up under national security. I believe Scientific American had a article on it a few years ago. Current machine vision has gone down the path of capturing more and more digital information from an image and throwing more and more computer horse power at it. The cruise missile is different. It takes an optical image and through optical and analog processing - filtering reduces the images information to just what is important. The edges and boundaries of objects which at the last stage are digitized and and compared to a processed image data base.

Indeed. I have been investigating some of the algoritms used by motion trackers used for video compositing and they are very very very computationally intensive. I am starting to look for algorithms specifically designed for machine vision. I have a few of my own in mind, but i am no expert on the subject and do not know whether or not they will work.

I envision something that operates in a few steps
*grab a frame
*generate new images in that are in terms of things like change in color vs position space instead of color vs position space.
*look for well defined areas. record their position as well as characteristic like thier shape, size, contrast range and relative location to other features. Store these things.
*query database of previously detected features in the general vicinity that correspond to currently seen features.
*calculate position.

A semi- mechainical fix to this would be to mount the camera on a pendulum-like deivce, thus gravity would do the job of keeping the camera vertical. Plus, you could have the added bonus of knowing wheter the bot was on a hill or not by adding a pot to the axis of the pendulum.

[KenWittlief]

could you navigate off the floor, using the same concept as an optical mouse?

they seem to work well on just about any type of surface

[Gdeaver]

Last year there was a thread on optical mouse navigation. I believe the sticking point was the optics and illumination modifications. The mouse sensor is very sensitive to focus. As with the cruise missile the optics are the most critical parts.

[Alan Anderson]

Originally Posted by KenWittlief

could you navigate off the floor, using the same concept as an optical mouse?

As Rickertsen2 already mentioned, that only gives you relative motion tracking. The novel idea proposed here is to use the ceiling as a "map" in order to determine absolute orientation.

[Kevin Watson]

Originally Posted by Rickertsen2

I was on a boat tonite looking up at the sky, when i had an idea. It goes something like this:Camera pointed toward ceiling + motion tracking algorithms = accurate absolute positioning.

I'm surprised Evolution Robotics' Northstar hasn't been mentioned yet.

-Kevin

[Rickertsen2]

Originally Posted by Kevin Watson

I'm surprised Evolution Robotics' Northstar hasn't been mentioned yet.

-Kevin

Thats pretty nifty. It requires an external beacon target painter, but thats an acceptable compramise. This sort of system is simple enough that i think i can fairly easily manage it.