20 May 2008
Vision Systems... There must be an easier way to take over the world!
)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
Permanent Link