Tikalon Header Blog Logo

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.

Queensland pitch drop experiment.jpg

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.

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:

  1. James Piascik, Reza Oboodi and Devlin M. Gualtieri, "Flow Sensor With Wide Dynamic Range," US Patent No. 6,196,070, March 6, 2001.
  2. David J. Fleet and Yair Weiss, "Optical Flow Estimation," in Paragios et al., "Handbook of Mathematical Models in Computer Vision." 2006.
  3. Kenneth Sebesta and John Baillieul, "Animal-Inspired Agile Flight Using Optical Flow Sensing," arXiv Preprint Server, March 13, 2012.
  4. Fundamental Law of High Speed Flying Maneuverability Discovered, The Physics arXiv Blog, March 16, 2012.
  5. 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.
  6. 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.