View source

Stereopsis or {{w|Stereo vision}} is a process where two or more cameras can be utilized to determine range or depth of field.  The result of the 2 cameras are two slightly different images.  Objects are matched in the two pictures and the difference in position relative to each other (horizontal disparity) is used to determine their depth or range from the cameras.  If distance between the two cameras is known, simple trigonometric functions can be used to calculate the distance between the cameras and objects in view.
Stereopsis is most commonly referred to as depth perception.  Sometimes more than two cameras can be used.  This is referred to as Multi-View Stereopsis.  With more viewers more data can be processed, and the possibility of more accurate distance calculations.  Some strategies of determining depth or ranging targets employ moving the viewers to more than one location.  Again collecting data from multiple locations can aid in the accuracy of determining depth.


<p align="center">
[[Image:2webcams.jpg|right|thumb|380px|2 webcams on motorized mount]]
</p>

== Robotic relevance ==
Stereopsis can be used in mobile robotics to ovoid obstacles. With the right software inexpensive [[webcams]] can be utilized as avoidance sensors or even 3D modeling and mapping. Raw images sent to your robot are not necessarily very useful. The images must be "interpreted" in order to provide useful sensor data.  Stereopsis range maps, object recognition, 3D models, are all examples of interpreted or processed data. These are things we do all the time, without even consciously thinking about it, and yet machine vision is a very young field of study.

==Natural Examples of Stereo Vision== 
[[Image:owl.gif|thumb|left]]

Many examples can be found in nature of stereo vision.  Predators typically have 2 eyes on the same plane, while prey often have eyes on opposite sides of the head.  Having eyes on opposite sides of the head provide a much greater field of view. Geese for example can see what is behind them.  While cats and owls have eyes one the same plane, which decreases field of view but is better for getting depth, or ranging prey. 

[[Image:stereopsis_duck_owl.jpg|thumb|right|420px|predators vs prey]]


If you have ever seen an owl move its head from side to side, the owl is using this process to collect more range information.  As it moves its head back and forth, images are collected and processed to create an extremely accurate range map.  The owl can use this to determine the exact location of a mouse relative to its current position, which aids in hunting.  You can even see people doing it unconsciously.   


Try an experiment. Ask someone, "Exactly, how far away is that point" and point to some arbitrary location. Then try to closely observe what they do. Here are some of the actions I have noticed people doing after asking them:
* They move their head back and forth slightly (like an owl).
* If the object is far enough away they will move their entire body a few steps to the left or right
* They will look near their feet and find something they know the length of. Typically they will look at their foot (it's usually easy to find). They will begin counting with an imaginary foot, stacking invisible feet all the way to the target point.
* They will squint out one eye then the other.

[[Image:cross_eyes.jpg|thumb|left|420px|The muscle flexes, the eyes focus]] 

Another interesting fact is infants don't have depth perception, but develop it within 2 months. I thought this might be the process of their brain developing this faculty. But, I read later that it had more to do with an eye muscle, which is not strong enough at this period to pull and focus the eye inward.  This was very surprising. I thought it was a brain function that figured out the horizontal disparity and that our eyes were parallel.  I believe now that we cross our eyes on an object of interest, and the amount that these small muscles flex pulling our eyes together corresponds to the closeness of the object.  The brain is an amazing organ, it balances all kinds of disparate information with ease.

There are times when this function does not work.  Head trauma can affect this ability to converge images and range distance.
Popularized in cartoons, but hopefully not experienced, being hit on the head can produce double vision. I thought that this might be the brain's faculties dealing with trauma. And the reason that we see double is that this is the natural state. Since we have two eyes, we would see the two disparate images if the brain wasn't constantly trying to correspond and converge everything.

[[Image:cross_eyed_cameras.jpg|thumb|right|420px|This could be a possible implementation of the same process. The reason for a single pivoting camera would be just cost savings. A motor and encoder would be all that is needed.]]

== Correspondence Problem ==
The {{w|correspondence problem}} is the issue of matching the same object in two different pictures. You might think that this problem is trivial to solve. Humans do it near instantaneously and all the time.  I found it much more difficult than I expected. The algorithms I used either were too error prone, or not fast enough to keep up with the video input. Filters can be used to simplify the problem of matching. A little research on the web came up with the following filters and algorithms:

== Filters and Algorithms ==
Software filters and algorithms can be used to process the raw information from the webcams into meaningful information for a robot.
Algorithms and filters can assist in edge detection, object recognition, map construction, and ranging.  

{|class="wikitable"  border="1" cellpadding="4" cellspacing="0"
|-
|'''Orignal'''
|'''Sobel Filter'''
|
|-
|[[Image:s2.jpg]]
|[[Image:s1.jpg]]
| A {{w|Sobel operator}} can be used for edge detection. Vertical lines extracted from this filter could be used for ranging distance.  But the corresponding vertical lines would still need to be found in the left and right views. The {{w|Sobel operator}} uses some matrix math and I have found it a little computationally demanding. But this may be just my bad implementation :P<<TODO - retrieve timings>>
|-
|'''Original'''
|'''Average Blur'''
|
|-
|[[Image:b1.jpg]]
|[[Image:b2.jpg]]
|Average filter is the averaging of the pixels within a given area. Here, I chose to use vertical averaging tiles (10 X 60 pixels), because I was much more interested in vertical lines.  Vertical lines are of use when the cameras are mounted on a horizontal plane.  Vertical lines are used to find the horizontal disparity in stereopsis.
|-
|[[Image:a1.jpg]]
|[[Image:a2.jpg]]
|This is the same average filter being applied to the left webcam.
|-
|
|[[Image:c1.jpg]]
|Here the two filtered segments are being compared side by side.
|-
|
|[[Image:histogram.jpg]]
|Here a color histogram is superimposed over the average filter segments. You can see how much the cameras vary in color range an luminosity.
|}





==Other Visual Queues for Ranging Distance==

{|class="wikitable"  border="1" cellpadding="2"
|-
!Image Clipping 
!Proximity to Horizon  
!Relative Sizes
!Parallax Motion 
|-
|align="center"|[[Image:object_clipping.jpg]] 
|align="center"| [[Image:horizon_proximity.jpg]]
|align="center"| [[Image:relative_size.jpg]]
|align="center"| [[Image:parallax.jpg]]
|-
| Object A is in front of object B.  We only know this because of the assumed shape/color of Object A and B.  Machines and current algorithms do not seem to be very good at "assuming".
| Object A appears to be in front of object B since object B is closer to the horizon.
| If object A and object B are the same type of object, then relative sizes would make object A closer and object B farther away.
| Object A travels further than object B in the moving frame of view.  So, object A is closer than object B. If the camera's traveling distance is known, the distance to the two objects can be derived using some simple trigonometry. 
|}



==Stereopsis Test 1 "Doing things by hand"==
Enough theory already ! Let's start some experiments !

=== Defining an area to compare for matching===
In this simplified view we will go through the steps of an algorithm to find depth using stereopsis.
I chose a very simple test to get the first example done.  This is a small piece of electrical tape (4" X 1/2") on a relatively plain canvas panel.  The canvas panel covers storage area in the basement. Before the experiment, it is good to collect some measurements.
*Black Tape 4" X 1/2"
*Distance from camera to tape 49"
*Field of view of the camera at 49" Horizontal 37", Vertical 26"
*Camera pixel width 320
*Camera pixel height 240

[[Image:simple_red.jpg]]
[[Image:dimension.jpg]]
[[Image:head1.jpg|thumb|320px|right|lokibot's stereo camera head]]

[[Image:simple_red_strip_missing.jpg]]

[[Image:simple_red_strip.jpg]]

I captured the two images from each camera and loaded them in Photoshop.

[[Image:matching.gif]]


Here I matched the segments together, counting the pixel offset.  The pixel offset corresponds to the distance the item matched was from the cameras.

==Stereopsis Test 2 "First program"==

[[Image:left0.jpg]]
[[Image:right0.jpg]]

{{#ev:youtube|6uVIH6KsIKI|425}}

== Track VS Match ==
Instead of trying to figure out which object corresponds to which object in two different frames of video, I thought wouldn't be easier to track an object as the camera moved. Then use the parallax effect to estimate range.  First, the points of interest in the video frame are found quickly with some very simple algorithms. For example, the first 100 brightest points in a search area.  Now if the camera was moved a known amount, the points will move a relative amount proportional to the distance from the camera.  I will have to change or build another head for Loki, which has a single camera which can slide to the left and right.

==Who knew the Cylons might be right?==
I thought the Cylons kept missing the humans with lasers all the time because of their little eye going back and forth.  Who knew they were ranging the target?  Now it all makes sense.
[[Image:cylon.gif|thumb|How far away are you target? I'm working on my horizontal disparity map.]]


==Working with Horizontal Section Histogram==
[[Image:histogram2.jpg]]

I am working with histograms now taken from a horizontal cross section of in this case several frames.
These are some of my observations :
* On a "still picture" the red, green, and blue values of a single pixel vary +/-4 in a range from 1 - 255 this would be considered "noise" and should probably be filtered out.
* If I let an histogram be processed from multiple frames the histograms line becomes about 8 pixels thick.  This is expected from the noise level. Again this should be factored out.
* After the noise has saturated the histogram line it appears to be completely stable, and ready for tracking

Questions:
*How to track - if the image is expected to shift to the left at various (minuscule) values what is the best strategy to find the differences?  Start with old line (factor noise), move left until another saturated line is found?

*Once horizontal disparity is found can a group be bound together to form an object on the same plane?

[[Image:160frames.jpg]]


[[Image:157frames.jpg]]


==Head Gimble==
{{#ev:youtube|L6VJOS-ZJvI|425}}
{{#ev:youtube|P6Y1BqlYYLw|425}}
{{#ev:youtube|QsUWDXhggB4|425}}

==Bibliography==
*[http://findarticles.com/p/articles/mi_g2602/is_0001/ai_2602000187 Depth Perception Encyclopedia of Childhood and Adolescence]

==References==
*{{w|Range imaging}} {{w|correspondence problem}}
*[http://engineering.ucsb.edu/~mmllee/research/prgs0816.html Multiple Camera Calibration for 3D positioning]
*[http://research.microsoft.com/vision/cambridge/i2i/MSRC_SDK/default.html Microsoft robotics stereo vision C# SDK]
*[http://www.ii.metu.edu.tr/~ion528/demo/lectures/6/2/2/index.html great applets of various image processing techniques]
*[http://en.wikipedia.org/wiki/Edge_detection Wikipedia edge detection]
*[http://www.nix3d.com/edgeDetect.php Nic Sievers interesting edge detection work]
*[http://www.pages.drexel.edu/~weg22/edge.html Tutorial from Bill Green]
*[http://www.tomgibara.com/computer-vision/canny-edge-detector Tom Gibara great java implementation]
*[[Edge detection]]
*[http://en.wikipedia.org/wiki/Scale-invariant_feature_transform SIFT Key point algorithm]
*[http://www.jhlabs.com/ip/blurring.html Great Gaussian and other blurring tutorial]
*{{w|Corner detection}}
*[http://www.roborealm.com/help/Moravec.php Moravec Interest Operator]
*[http://www.cim.mcgill.ca/~dparks/CornerDetector/mainApplet.htm Great Applet demo for Corner Detection]
*[http://www.cim.mcgill.ca/~dparks/CornerDetector/index.htm Corner Detection Site]
*[http://sourceforge.net/projects/javavision java machine vision toolkit]
*[http://www.cs.cmu.edu/~cil/v-source.html CMU's Computer visions software list]
*[http://daoi.sourceforge.net/ Disparity Analysis of Images in Java]
*[http://www-cs.engr.ccny.cuny.edu/~zhu/CooperativeVision.html cooperative vision and panoramic cameras]
*[http://perception.inrialpes.fr/Soft/calibration/index.html TELE2 allows to calibrate a camera from a special purpose calibration object.]
*[http://alg.ncsa.uiuc.edu/tools/docs/i2k/manual/ncsa/d2k/modules/projects/i2k/tools/Stereo.html Stereopsis tool StereoFrame]
*[https://jai.dev.java.net/binary-builds.html#Release_builds JAI Java Advanced Imaging builds including (native) support]
*[http://users.ecs.soton.ac.uk/msn/book/new_demo/corners/ Computer Vision Demonstration Website - Harris + Java]
*[http://vision.middlebury.edu/stereo/code/ Stero at middlebury edu]
*{{w|ImageJ}} a public domain, Java-based image processing program developed at the National Institutes of Health
*[http://java.sun.com/developer/onlineTraining/javaai/ official JAI tutorial which does not work well]
*[http://java.sun.com/products/java-media/jai/forDevelopers/jai1_0_1guide-unc/Graphics.doc.html JAI review]
*[http://poseidon.csd.auth.gr/LAB_RESEARCH/Latest/SecurityBiometrics.htm Security Biometrics]
*[http://sluggish.uni.cc/sentience/sentience.htm Sentience]
*[http://sluggish.uni.cc/sentience/sentience.htm Sentience]
*[http://www.asiawriters.com/ freelance writing opportunities]
*[http://code.google.com/p/sentience/ Google Code PSentience]
*[*[http://www.roborealm.com/links/vision_software.php roborealm list of links]