20 May 2008
Written by
Glasswalker (
)
Published on May 20th, 2008 @ 11:59:59 am, using 716 words, 432 views
I am having some problems with the vision system I am coding for the RoboChamps Amazed Challenge I talked about in a previous blog post. The system is coming together very nice, but now it is in the fine tuning that there appears to be an error somewhere in my logic. I will give below 2 samples of data, and an explenation of the algorithm (in pseudocode) so it is easily understood. Then below that I will describe the details of my problem. (and provide links to the actual source that accomplishes this).
Sample 1
..........
..1.1.....
..111.....
..1111....
...1.111..
.111.11.1.
.11..1..1.
.1111.111.
.1..1111..
..........
Sample 2
..........
.111......
.1.11.....
.11111....
..111222..
.11112222.
.111.2222.
.111.2222.
.111.22...
.111......
Algorithm:
Walk through each pixel, starting top left, ending bottom right, scanning horizontal rows.
For each Pixel:
If pixel is not "." then:
if it has no ID associated already:
Assign a new ID
Scan all immediately adjacent pixel (8 adjacent pixels):
for each pixel:
If it is the same number as the center pixel:
If it has an ID assigned already:
Mark the ID of the center, and the ID of the adjacent one, as related
If it has no ID assigned already:
Assign it as the same ID as the center one.
Now Clean up the relationships:
Walk through each "relationship" which has 2 values to start:
For each relationship:
Look through all other relationships farther ahead in the array than this one.
For each scanned relationship:
If this scanned relationship contains any int from the original relationship:
Append any new ints from the scanned one onto the end of the original one.
Delete the scanned relationship from the main list.
Then walk through each pixel again
for each pixel:
If this pixel's ID is not zero:
walk through each relationship
for each relationship:
If this pixel's ID exists in this relationship:
Set this pixels ID to the ID at index 0 of Relationship.
Now all pixels should be renumbered so all contiguous IDs are resolved.
Now walk through the pixels again
for each pixel:
If there is already a blob ID for this Pixel's ID, then
Is this pixel farther left than the lefthand edge of the blob?
IF so then update the blob's lefthand edge to be at this pixel
Is this pixel farther right than the righthand edge?
If so then update blobs righthand edge to be this pixel
Is this pixel farther up than the top edge?
if so then update blobs top edge to be this pixel
is this pixel farther down than the bottom edge?
if so update blobs bottom edge to be this pixel.
If there is not already a blob ID in the blob array for this Pixels ID then
Create a new blob ID in the blob array and give it this pixels ID.
Now we have an array of each distinct blob in the image
Each with an ID and a defined rectangular outer boundry for it.
The Problem:
In an image such as Sample 1, only one type of object is visible. It detects the blob perfectly, and puts an accurate bounding box around it.
In an image such as Sample 2, there are 2 adjacent blobs of different types.
This example tends to confuse my code, and instead it sees many small blobs of either all 1, all 2, or mixed 1 and 2 type pixels.
From what I can gather this should not be possible with my algorithm as described.
I have stepped through the code extensively and cannot find the problem. I am not sure if the issue is in the relational sorting, or if it is in another stage of the vision system.
Here are a couple images of the vision system in use in MSRDS environment. The images on the right show the actual scene, and on the left is what the robot is interpreting.
The first image shows a scene with 2 objects in it, and you can see how the detected bounding boxes are broken up and smaller
The second image shows a scene with only one, and suddenly detection is perfect (all I have done is slightly turn the robot, so it is the exact same object)
Also here are links to the source code:
This is the main algorithm for blob detection: http://pastebin.com/m5a4bea0a
(encompases all the above pseudocode besides the cleaning up relationships part)
And this is the cleanup relationships code: http://pastebin.com/m63b15850
05 May 2008
Written by
Glasswalker (
)
Published on May 5th, 2008 @ 09:35:03 am, using 444 words, 152 views
So I found out about this new project by microsoft a week or two ago. They launched it in late April. Called Microsoft Robotics Development Studio (MRDS). At first I thought it was a half baked way for MS to get into another market, but after looking at some of the technology behind the platform, it’s quite ingenious… It is really well made and well thought through.
The system is entirely centered around Visual Studio, developing for robots using any of the known .net languages (I am using C# for example). which really makes it easy to get into for existing developers. Also the entire system is done using Services, which is very nice (and very similar to current enterprise development trends right now).
Anyway, alongside the launch of the product, they launched a community driven contest. For anyone to participate in, free to download the software, and one other great feature I forgot to mention about MRDS… It allows 100% simulation of a real robot in a 3d environment. With full physics and everything. So you can write your code for the sim, test, debug, and play with it, then take that same code and it will run out of the box on the real thing. Very nice concept. Anyway the sim is included so no need to have a real robot to compete, because all the competitions are done in the simulated environment.
It’s very very cool. So I am working on my entry for the first challenge. We will see how it goes. Been a long time since I have written code for .net, so I am getting back up to speed there, and back in the day I worked with .net, I didn’t do any services stuff, (while I know about it from my IT work, I have never first hand coded in that paradigm). So It’s a bit of an adjustment for me.
Either way I am coming along alright. The first challenge is a maze, and I have the robot pretty reliably navigating the maze and avoiding obstacles. Now the main challenge is avoiding the traps placed throughout the maze, and finally improving efficiency and speed.
I have till the end of may, so we will see if I can win it.
(did I mention there are nice prizes for these challenges, in the form of REAL robots, that are worth a fair bit of money. Gives an opportunity for me to get a real robot to work on in the future that I normally wouldn’t be able to afford, so I hope I can win it!).
Well that’s all for now, I will update later as things progress!
31 March 2008
Written by
Glasswalker (
)
Published on March 31st, 2008 @ 03:33:27 pm, using 160 words, 204 views
Here’s an interesting thought… It would take a blu-ray disk about 1.2 kilometers in diameter to hold the entire internet…
That’s right, the whole bloody thing… (according to current estimates by google on the size of the entire internet).
That goes to show you where we are at in terms of storage technology…
So anyone want to build one with me?
We could put it in a giant flying saucer… And leave for a new planet with all the worlds collective knowledge! (and probably a ridiculous amount of porn lol)
On another note, if we used the tape storage technology used in the original Univac 1 in the 50s we could use a single piece of tape long enough to span 3 thousandths of a lightyear to hold the same amount of data. (so we would need 1200 of said tapes connected end to end to reach from here to the next nearest starsystem, alpha centauri).
Yup… I’m off to start downloading the internet…
02 January 2008
Written by
Glasswalker (
)
Published on January 2nd, 2008 @ 08:21:01 am, using 900 words, 183 views
Here are my notes so far in designing a PIC based audio system. I have reviewed some other peoples work on this subject, and I think I have come up with a relatively simple, and low cost solution for sound using only a PIC, an EEPROM and some resistors. (possibly an R/C filter on the output for noise filtering, and possibly an opamp if needed)
Here are my notes so far, please have a look and let me know your thoughts, comments, and suggestions. Any feedback is appreciated. I will hopefully begin actually building and testing this in the next day or two.
PIC Audio Planning Notes:
Data encoded as 4-bit Linear RAW PCM format, each 1 second sample
stored as a 32Kbit block allowing for 16x 1 Second clips to be stored
in a single 24xx512 EEPROM.
Each sample will be terminated with null (a continuous block of null bytes until the end of that sample's memory space) Termination allows the PIC to see the end of the actual sound, since in memory each "block" will start at a fixed address in the eeprom, and we only have a "play" and "stop" control. We don't need the pic needlessly bit banging out silence for no reason. So to terminate, the pic will either look for a consecutive block of 00 for a number of samples (to be determined) or the end of the 32kbit memory space, whichever comes first.
The PIC I am thinking of using is the 18F1320. This gives up to a 32Mhz internal oscillator using the built in PLL, so we can run the PIC nice and fast without any external components. The speed allows for a bit nicer decoding of the audio.
The PIC has 16 IO pins, of these 8 pins will be the digital audio out, 6 pins will be the control input, and 2 pins for the I2C bus to the EEPROM.
The control structure will use the 2 hardware interrupt pins for the 2 control inputs for Play and Stop. The stop int will simply vector into sleep mode. The play int will vector into a play routine which will read the 4 bit "Clip ID" from the other 4 control pins, and use that to pick the address on the EEPROM to start reading. It will read audio in 1 byte at a time, process it, send it out, then read the next, until it reaches valid termination, at which time the chip will sleep.
The output will be 8bit digital, which will be fed into a crude D/A converter built from an R2R Ladder (which should be suitable for our needs). This keeps cost of components low, and keeps it simple. The R2R ladder will feed an opamp which will likely be fine for direct drive of a headphone or speaker (with a pot in there for volume control) but if need be we can drive an opamp with it and bias the opamp for further control.
In order to get the 8 bit output, and maintain the best sound quality, we will take the 4 bit samples, and use linear interpolation from the 4bit value into an 8bit value and upsample the audio from 8Khz to 32Khz sample rate. This will eliminate (or severely reduce) the standard bad sounding quantization noise commonly seen in this type of setup. Overall this should allow for very nice sound with a minimal amount of storage space.
Basically the algorithm will look something (vaguely) like this:
INT_Play:
read in 4 bit sound_id from control pins
multiply 4bit sound_id by 32k to get start address for this sound
sample.
Set eeprom_address variable to this address
Init lastbyte to null
Loopstart:
is eeprom_address past the end of the current 32kbit sample block? if so goto INT_Stop
Read byte in from EEPROM
is byte null? if so incriment null counter
is null counter > the termination threshold? if so then goto INT_Stop
split byte into hibyte and lobyte (4 high bits and 4 low bits)
Shift Left 4 bits for both hibyte and lobyte (convert to 8bit value)
find difference from lastbyte to hibyte
diffdev = difference divided by 4
tempbyte1 = lastbyte + diffdev
tempbyte2 = lastbyte + diffdev x 2
tempbyte3 = lastbyte + diffdev x 3
sleep as needed for clock sync
output tempbyte1
sleep as needed for clock sync
output tempbyte2
sleep as needed for clock sync
output tempbyte3
sleep as needed for clock sync
output hibyte
find difference from hibyte to lobyte
diffdev = difference divided by 4
tempbyte1 = lastbyte + diffdev
tempbyte2 = lastbyte + diffdev x 2
tempbyte3 = lastbyte + diffdev x 3
sleep as needed for clock sync
output tempbyte1
sleep as needed for clock sync
output tempbyte2
sleep as needed for clock sync
output tempbyte3
sleep as needed for clock sync
output lobyte
lastbyte = lobyte
incriment eeprom_address
goto Loopstart
INT_Stop:
sleep the CPU
The various use of sleep in the above pseudocode are not actually "sleep" it will be timing loops to delay the cpu so that the outputs occur at a stable 32Khz rate. I will need to do math on the actual instruction cycles used at each stage and then add appropriate padding so that the delay between outputs is exactly 250 cycles. (hopefully 250 cycles is enough for the inteprolation algorithm I listed above)
This system allows me to store audio in 4bit 8Khz format, requiring only 32kbit per second, but upsample/interpolate so we can output at 8bit 32Khz audio, which is much nicer and smoother sounding.
Written by
Glasswalker (
)
Published on January 2nd, 2008 @ 08:14:27 am, using 884 words, 303 views
I am working on a DIY Laser Tag project that will be cheap and easy to build, and will have the featureset needed by the pro taggers.
Basically I am working on the electronics side for now, and will get into building a gun out of it once I have the electronics down.
I am developing it on a PIC16F73 (I have to upgrade to a PIC18 series chip, but I am more familiar with PIC16 so I started in that family, but now I have to port my code) as a main processor, and thinking of using a secondary Pic18 with an external EEPROM for sound playback. I will post more about this shortly as I have this circuit in development seperately and will integrate to this project when complete.
I allready have the basic routines developed, timing routines, and a prototype circuit put together. But I am now in the process of migrating it to a newer Pic18 and porting the code to C
I am developing my own protocol from scratch, but I got lots of ideas from the milestag site for basic modulation.
Here is what I have so far for my protocol definition:
IR Protocol sent over a 40Khz PWM Signal.
40Khz Carrier means 1 Wavelength = 25uS
Minimum Burst Length is 50 uS (cover 2 full cycles)
Our Burst Length (from here on referred to as T, or 1 Time Period) is equal to 500uS
Each packet will begin with a header, which is 4T in length.
There will be a gap between pulses of 1T
High bit will be represented by a pulse of 2T
Low bit will be represented by a pulse of 1T
Each packet will contain the following data:
- TeamID - 4bit
- PlayerID - 8bit
- Parameter - 8bit
Format: (H=Header T=TeamID I=PlayerID P=Parm ?=Parity Check Bits)
HTTTT?IIIIIIII?PPPPPPPP??
Min Packet Length = 52T = 26,000 uS
Max Packet Length = 88T = 44,000 uS
Max Packet Rate = 22 packets/second
if TeamID = 0 then playerid = system message
Player Shots Parameter is:
Type - 2bit (00=Normal Dmg, 01=Healing, 10=Ammo, 11=Shield)
Multiplyer - 2bit (00=1x. 01=5x. 10=10x. 11=25x)
Amount - 4bit (amount is multiplied by multiplyer)
Format: (T=Type M=Mult A=Amount)
TTMMAAAA
System Messages:
- Non-Player Damage (parm = amount)
- Full Health
- Full Ammo
- Full Armor
- Damage Booster (parm = duration in seconds)
- Invincibility (parm = duration in seconds)
- Revive Player
- Instant Kill Player
- Pause Player
- Issue Penalty to Player (parm = penalty code?)
- Set Gun Player ID
- Set Gun Team ID
- Activate Gun
- De-Activate Gun
- Set Gun Damage
- Set Gun Max Ammo (parm = amount)
- Set Gun Max Clips (parm = amount)
- Set Gun Max HP (parm*10 = amount)
- Set Gun Max Armor (parm*10 = amount)
- Set Gun Rate of Fire (parm = rounds/sec or rounds/burst if burst mode)
- Set Gun Burst Mode (parm = boolean)
- Set Gun Damage Type (00=Normal Dmg, 01=Healing, 10=Ammo, 11=Shield)
- Set Gun Shield Damage Mult (Parm/10 = Multiplier 0=no multiplier)
- Set Gun Current Ammo (parm = amount)
- Set Gun Current Clips (parm = amount)
- Set Gun Current HP (parm*10 = amount)
You can likely see the similarities so far with MT protocol. But I am trying to make this myself completely from scratch.
At this point though, I am just getting the signalling code done up, and working on a reciever circuit.
I want to eliminate as much noise as I can, and account for self hit correction. Any suggestions on that front would be greatly appreciated
I am planning on using a simple TSOP based reciever module to simpify the circuit.
My end goals for this system are pretty high, but we will see how far I get. Right now I am only working out the foundation of this system so of course all these features are only loose goals right now:
- Many customizable game modes (FFA,Team,CTF,And others)
- Game and Gun templates can be saved in eeprom on gun
- Variable Damage
- Variable ROF
- Variable Ammo/Clips/Reloads
- Healing / Grenades / Explosions / Ammo Refilling / Shields / Armor
- Very large fields (Up to 16 Teams with 255 players per team)
- Customizable Audio? (updatable through software from PC)
- A central controller unit (ala the Odin on FragTag)
- Wireless 2 way RF communication between guns with significant range and stability
- Wireless 2 way RF comms to central controller
I also plan on making a central “Hub” for a field which can run as an embedded PC with an RF module to talk to all the guns/controllers on the field. It could be usable as both a gathering point for statistics and scores as well as a webserver which hosts a field billing/management/statistics system so all a field needs is a Hub, some ethernet cable, and a PC. This would allow realtime monitoring and control of the game, statistics, and for realtime refereeing with or without line of sight. It also makes it easy for a field to setup, no need for getting software to handle registations or billing or any of that stuff, it could be a 1 box solution (plus guns)
Anyway, any feedback on any of this is greatly appreciated.
Thanks!
(will post more stuff as I make further progress…)
Written by
Glasswalker (
)
Published on January 2nd, 2008 @ 08:00:40 am, using 233 words, 114 views
I have been working on a PHP based neural net library (PHPNN) which is released under the GPL. The library is meant to facilitate artificial intelligence, and neural net research using simple web based APIs.
I am also working on a series of research platforms based around this library, and I am looking to extend it further. Unfortunately it has fallen by the wayside for now, so I have decided to release what I have (which is fully functional, and includes an XOR test to demonstrate it’s functionality, there is no documentation, but the code should be well documented for your reference).
This system supports multiple learning methods, and neural nets of varying structures and sizes to be created in a fully encapsulated object oriented model.
I will work on a new release version as I get more time, and add alot of new functionality and more optimization for performance and power.
If you are interested in a certain feature, or if you would like to help out let me know. Depending on interest, I may or may not pick this up sooner to get back on it.
Here is a link:
Link to the sourceforge project page
Any help to flesh this project out, or feedback on it would be appreciated.
(after all we need to complete our giant artificial intelligence if we are to have any chance when the wombats arrive!)
Permanent Link