Probabilistic Computing for Efficient Robotic Vision in Space
Computation can be made more energy efficient by allowing a larger chance for erroneous results. Can we make vision algorithms that exploit such probabilistic computing?
In space robotics, the computational efficiency of algorithms is at a prime: tasks such as autonomous landing or rover navigation require a quick and efficient determination of actions, given an amount of energy and processing capacity that is much more restricted than in earth-based scenarios.
In this study we focus on a novel integrated software and hardware approach for reducing the computational effort and energy expenditure of computer vision algorithms. It is based on local sampling on the software side and probabilistic computing on the hardware side.
Specifically, on the software-side, the Advanced Concepts Team of the European Space Agency will study random local sampling techniques that reduce the number of necessary computations at the cost of a slightly lower accuracy. On the hardware-side, a research group with expertise in probabilistic computing will study such computing as a means of saving energy at the cost of occasional errors in the calculations. Both aspects are further explained below.
Software – efficient and robust algorithms
Visual attention models could form a successful strategy for reducing the computational effort of computer vision algorithms. The central idea of visual attention models is that they devote most of the processing to the most relevant parts of the image. Surely, the main challenge is to automatically determine what is `relevant'. Several models have been devised that can determine relevant parts of an image, but many of them extensively process the entire image for determining regions of interest, inadvertently still leading to a large computational burden [1, 2, 3].
In order to achieve a higher computational efficiency, many attention models perform visual tasks on the basis of a restricted number of local samples [4,5,6,7]. In particular, these studies focus on informed sampling, in which the information from the current sample is used to select the next. This can lead to large computational efficiencies, but also often creates a challenging Partially Observable Markov Decision Problem (POMDP). Such a POMDP is currently difficult to solve, and the mentioned studies either make strong assumptions on the task  or have to train a model for each different task .
In this study the more straightforward strategy of random sampling is employed. It has been demonstrated that in some cases random sampling suffices to obtain speedups in the order of a 100 times with an unnoticeable cost in accuracy [8,9,10,11]. Below a figure illustrates this for an application of pitch and roll estimation of an Unmanned Air Vehicle that processes local image samples to find the horizon line. The y-axis represents the absolute error in each estimate, the x-axis the number of samples, with full sampling on the far right. It can be observed that most performance is gained after a 1000 samples the performance does not noticeably improve. Extracting only 1000 samples results in a speed-up of 14 times for a small image of 160 x 120 pixels (a border of 10 pixels is used in these specific experiments).
Hardware – probabilistic computing
If one accepts that vision algorithms can gain in efficiency by using only part of the information in an image, one can extend this reasoning to the hardware involved in the calculations to save even more time / energy. In typical processor hardware considerable amounts of energy are spent on obtaining correct calculation results, e.g., for adding or multiplying numbers. In probabilistic computing [12,13,14], the energy spent by the processing units is lowered, resulting in an increase of the probability that some operations might go wrong. Fortunately, it has been shown that the amount of energy saved is significantly larger than the amount of probability traded in  - see the figure below. As a consequence, in theory, large energy gains (in the order of 5 times) can be obtained at a minimal cost in calculation errors.
Different applications of probabilistic computing have been investigated. The study in  focused on the application of probabilistic computing to the calculation of the Fourier transform, showing that for human subjects the probabilistic reconstruction
is visually identical to the error-free one. Another study involved the application of probabilistic computing to Continuous Restricted Boltzmann Machines (CBRM) . Such CBRMs normally require the generation of pseudo-random numbers.
Instead, in  probabilistic computing naturally provided random numbers.
This study proposes to perform research on probabilistic computing in a different context, namely that of a vision algorithm for robotics. The main idea behind the application is that a slight loss in accuracy in the computations of the vision algorithms can still lead to robust and successful retrieval of information on the environment.
2012-01 - The study: " Probabilistic computing for efficient robotic vision in space " will officially start in the course of 2012.
 L. Itti, C. Koch, E. Niebur, A model of saliency-based visual attention for rapid scene analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence 20 (11) (1998) 1254 - 1259.
 U. Rajashekar, L. Cormack, A. Bovik, Image features that draw ¯x- ations, in: 10th IEEE International Conference on Image Processing (ICIP 2003), Barcelona, Spain, Vol. 3, IEEE Computer Society, 2003,pp. 313-316.
 A. Torralba, A. Oliva, M. Castelhano, J. M. Henderson, Contextual guidance of eye movements and attention in real-world scenes: the role of global features in object search, Psychological Review 113 (4) (2006) 766-786.
 J. Denzler, C. Brown, Information theoretic sensor data selection for active object recognition and state estimation, IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (2) (2002) 145-157.
 N. Sprague, D. Ballard, Eye movements for reward maximization, in: S. Thrun, L. Saul, B. SchÄolkopf (Eds.), Advances in Neural Information Processing Systems 16, MIT Press, Cambridge, MA, 2004.
 G. de Croon, E. Postma, H. van den Herik, A situated model for sensory-motor coordination in gaze control, Pattern Recognition Letters 27 (11) (2006) 1181-1190.
 S. Jodogne, J. Piater, Closed-loop learning of visual control policies, Journal of Artificial Intelligence Research 28 (2007) 349-391.
 L. Xu, E. Oja, A new curve detection method: Randomized hough transform, Pattern Recognition Letters 11 (1990) 331 - 338.
 J. Shotton, J. Winn, C. Rother, A. Criminisi, Textonboost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation, in: ECCV 2006, 2006.
 C. Barnes, E. Shechtman, A. Finkelstein, D. Goldman, Patchmatch: A randomized correspondence algorithm for structural image editing, in: ACM Transactions on Graphics (Proc. SIGGRAPH), 2009.
 de Croon, G.C.H.E., de Weerdt. E., de Wagter, C., Remes, B.D.W. "The appearance variation cue for obstacle avoidance.", in the IEEE conference on Robotics and Biomimetics 2010 (ROBIO 2010).
 Probabilistic Arithmetic and Energy Efficient Embedded Signal Processing (Received Best Paper Award.) Jason George, Bo Marr, Bilge E. S. Akgul and Krishna V. Palem. Proceedings of the Intl. Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), Seoul, Korea, October 23-25, 2006.
 Probabilistic Computing with Future Deep Sub- Micrometer Devices : A Modelling Approach, Hamid, Nor H, Murray, Alan F, Laurenson, David, Roy, Scott Cheng, Binjie, Symposium A Quarterly Journal In Modern Foreign Literatures, 2005, pages: 2510-2513
 Error Immune Logic for Low-Power Probabilistic Computing, Marr, Bo, George, Jason, Degnan, Brian, Anderson, David V., Hasler, Paul, VLSI Design, 2010, pages 1-10
 Stereo based navigation in unstructured environments, Mark, W. van der, Groen, F.C.A., & Heuvel, J.C. van den (2001). In IEEE Instrumentation and Measurements Conference (pp. 2038-2042). Budapest, Hungary.
 Learning long-range vision for autonomous off-road driving, R. Hadsell, P. Sermanet, J. Ben, A. Erkan, M. Scoffier, K. Kavukcuoglu, U. Muller, and Y. LeCunn
 Advances in computational stereo, M.Z. Brown, D. Burschka, and G.D. Hager. In IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 8, 2003.
 A region based stereo matching algorithm using cooperative optimization, Zeng-Fu Wang, Zhi-Gang Zheng, 2008 IEEE Conference on Computer Vision and Pattern Recognition, pp.1-8.