| Tikalon Blog is now in archive mode.
An easily printed and saved version of this article, and a link
to a directory of all articles, can be found below: |
|
This article |
| Directory of all articles |
Optical Flow
March 22, 2012
I wrote about
flow in a
previous article (Rheometry, November 3, 2011). The science of flow is called
rheology, from the
Greek word, ρεω ("rheo"), meaning flow. The
Greek philosopher,
Simplicius (c.490 - c.560) is responsible for the expression,
παντα ρει (everything flows), which is often ascribed to the different the Greek philosopher,
Heraclitus of Ephesus (c.500 BC). This expression is the
logo of the
The Society of Rheology.
A graphic illustration that everything does flow, at least some things that you wouldn't expect.
The pitch drop experiment of the University of Queensland was started in 1927 to measure the viscosity of solid pitch.
Eight drops have since fallen, allowing an estimate that pitch has more than 200 billion times the viscosity of water at room temperature.
(University of Queensland Photo by John Mainstone, via Wikimedia Commons)
Flow sensing is an area of major commercial importance. Most
industrial processes require
liquids to be metered out in certain proportions to make a desired product. There are so many different type of liquids, and so many different flow rates, that a good fraction of the Internet is used to catalog fluid flow sensors. You can buy sensors to monitor the flow of
blood (as in
dialysis machines), or the flow of strong
acids.
One of my
inventions solved a particular problem in flow sensing. My colleagues and I designed a sensor that would operate accurately over a range of very small flow rates to very high flow rates; that is, it had a high
dynamic range.[1] The hardest part of this invention was convincing the
engineers that it would work. One of their summer
interns had a
computer model that showed poor performance. The model was wrong, which reinforces the maxim, "if anything can go wrong, it will go wrong faster with computers."
Although
light rays could be considered to be a flow of
photons, the term,
optical flow, is reserved for another principle. Optical flow is the perceived motion of components of a scene caused by the relative motion between the observer and the scene. In the 1940s, when the term was first coined, it had a
psychological context. Nowadays, with ubiquitous
computer graphics and
image processing, the term is used mostly in
computer science.
An important application of optical flow is for
motion estimation, which is important in
video signal compression for deciding what parts of an image need to be updated more frequently.
Robotics, in particular the area of
micro air vehicles, utilizes optical flow for
navigation and
object tracking.
If you lock ten
computer scientists in ten separate rooms for a reasonably extended period, with an ample supply of
caffeinated drinks and
high-carbohydrate snacks, they will produce ten different methods of detecting optical flow in a
video stream. That's because the concept is simple, but its implementation can take many forms, depending on how you approach the problem. A good
tutorial on various methods appears in reference two.[2]
Flying through the
wild, blue yonder is easy, but the future of
unmanned aerial vehicles finds them flying close to the ground where obstacle avoidance is a major issue. What makes this navigation problem worse is that the onboard vision and computing resources of such vehicles are limited by their size and
power supply. As has been found in
biomimetic systems, clues from the ways that
nature does such things are usually beneficial. If you're interested in directed flight, a
bird does this with only a
bird brain.
It's conjectured that flying animals might use optical flow in their navigation through cluttered landscapes, such as
forests. A recent
arXiv paper by
Kenneth Sebesta and
John Baillieul of
Boston University examines how optical flow can be used for motion control of robotic air vehicles.[3,4] This is a draft of a paper that's been submitted to the
51st IEEE Conference on Decision and Control, scheduled for December 10-13, 2012, in
Hawaii.
I think it would be improper to actually classify this research as
biomimicry. In the case of
spider silk, for example, you can use
laboratory instruments to analyze the
material and attempt to copy it. In the case of bird navigation, it would be hard to interview a bird to discover the mental process by which he does it. That being said, since the proof of the pudding is in the eating,[5] if optical flow is shown to be a valid control method for flight, then there should be research done in this area.
For obstacle avoidance, the principle is simple. You're more likely to collide with an object in your
field of view when its
area is getting very large, very fast. Sebesta and Baillieu have gone a little farther by calculating the time to collision to points in the field of view, as shown in the figure, which quantifies the flight towards a
tree. The flier doesn't need to concern itself about the nature of the object, it just needs to wend a path through the region of least resistance.
Optical flow calculation of time to tree contact. Fig. 7 of reference 3, via arXiv Preprint Server. [3)]
Not surprisingly, highly cluttered environments need to be navigated at lower speeds. Sebesta and Baillieu reference unpublished work by Karaman and Frazzoli that demonstrates that there is a critical speed that can't be exceeded for a bird to fly through a forest. If this speed is exceeded by just a bit, it can't navigate sufficiently well to fly through because it lacks its required
turning radius.[6]
Such a limit will likely be a feature of robotic air vehicles, so the best recourse for high speed flight is to optimize this turning radius. In summary, it appears that using optical flow in a control loop is a viable method of robotic air vehicle navigation.
References:
- James Piascik, Reza Oboodi and Devlin M. Gualtieri, "Flow Sensor With Wide Dynamic Range," US Patent No. 6,196,070, March 6, 2001.
- David J. Fleet and Yair Weiss, "Optical Flow Estimation," in Paragios et al., "Handbook of Mathematical Models in Computer Vision." 2006.
- Kenneth Sebesta and John Baillieul, "Animal-Inspired Agile Flight Using Optical Flow Sensing," arXiv Preprint Server, March 13, 2012.
- Fundamental Law of High Speed Flying Maneuverability Discovered, The Physics arXiv Blog, March 16, 2012.
- The maxim, "The proof of the pudding is in the eating," appears in Miguel de Cervantes, "Don Quixote de la Mancha," Part I, Book IV, chapter ten.
- S. Karaman and E. Frazzoli, "High-speed Flight through an Ergodic Forest," MIT Preprint, 2011 (as referenced in [3]).
Permanent Link to this article
Linked Keywords: Flow; rheology; Greek language; Ancient Greek; philosopher; Simplicius; panta rhei; παντα ρει (everything flows); Heraclitus of Ephesus; logo; The Society of Rheology; pitch drop experiment; University of Queensland; viscosity; pitch; water; room temperature; Wikimedia Commons; industrial process; liquid; blood; dialysis machine; acid; invention; dynamic range; engineer; intern; computer model; light ray; photon; optical flow; psychology; psychological; computer graphics; image processing; computer science; motion estimation; video signal compression; robotics; micro air vehicle; navigationvobject tracking; computer scientist; caffeinated drink; carbohydrate loading; high-carbohydrate snack; video stream; tutorial; U.S. Air Force song; wild, blue yonder; unmanned aerial vehicle; power supply; biomimetic system; nature; bird; bird brain; forest; arXiv; Kenneth Sebesta; John Baillieul; Boston University; 51st IEEE Conference on Decision and Control; Hawaii; biomimicry; spider silk; laboratory instrument; material; field of view; area; tree; turning radius; US Patent No. 6,196,070; Miguel de Cervantes, "Don Quixote de la Mancha," Part I, Book IV, chapter ten.