Projects

Projects

ARTISIS : ARTIficial intelligence for image syntheSIS

Context

Image synthesis (also called rendering) consists in computing an image from a virtual 3D scene. It is a widespread technique used in many fields such as cinema, advertising, industrial design and so on. Rendering is a light transport simulation problem, defined by a Fredholm integral equation called the rendering equation [Kaj86]. The rendering equation is difficult to solve so many numerical methods have been proposed. The Path-Tracing algorithm [Kaj86] is a straightforward Monte-Carlo method which successfully solves the rendering equation. Many sampling techniques have been proposed to improve Path-Tracing, however the algorithm can still be very inefficient for scenes with complex illumination conditions. The Metropolis Light Transport algorithm [VG97] is an adaptation of the Metropolis algorithm [Met+53] to light transport. It is a Monte-Carlo Markov Chain method which handles complex scenes more efficiently than Path-Tracing. It is classically used in modern renderers. In the artificial intelligence field, the Metropolis algorithm, also known as Simulated Annealing [AK89; Hwa88], is a popular and robust algorithm for optimization problems. Alternatively, there exists a certain number of state of the art algorithms used in optimization that are not necessarily known by the rendering community. For instance Evolutionary Algorithms, and in particular for discrete problems, Genetic Algorithms [Hol92; Mit98], are also known for their robustness and their efficiency. In this project, the main idea is to investigate how artificial intelligence algorithms other than the Simulated Annealing can be used for rendering images.

Aim and novelty

The main objective of the project is to experiment evolutionary optimization algorithms applied to the rendering problem. We believe this can be a win-win collaboration between the two fields. In the rendering field, it would bring alternative methods to compute the rendering equation. In the evolutionary optimization field, it would bring new applications of existing algorithms and allow possibilities of creating new techniques (for example, new mutation and crossover operators specially designed for the rendering equation). More precisely, in this project, we are interested in two kinds of artificial intelligence algorithms. First, we would consider optimization algorithms (in particular, Genetic Algorithms) to compute the rendering equation. Rendering is an integration problem generally solved numerically by random sampling (Monte- Carlo integration). More advanced algorithms, such as Metropolis Light Transport, try to generate a sampling distribution which fits the integration problem, i.e. an optimization problem. In [LM03], Laskey and Myers compared several stochastic search algorithms classically used in artificial intelligence and a Metropolis-inspired algorithm. In this project, we would follow the opposite approach: investigate how AI algorithms can solve a problem usually solved with Metropolis. We have already implemented and compared such AI and Metropolis algorithms for solving a simplified “Metropolis problem” [CE05] and obtained encouraging results. In a second part of the project, we would consider using decision making algorithms classically used in the artificial intelligence field, for the rendering problem. Indeed, rendering algorithms are generally implemented using various decision strategies and heuristics, which are also studied in the artificial intelligence field. For example, an image is generally rendered using a fixed number of samples per pixel, however lighting conditions can greatly differ between image areas. Consequently, it may be more efficient to allocate the samples non-uniformly (i.e. compute more samples in complex areas), which can be done by using AI decision algorithms such as multi-armed bandit [ACBF02]. We have already tested this idea for an optimization problem and we think it would be applicable to the rendering problem too.

Bibliography

Artificial intelligence

[ACBF02] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. “Finite-time analysis of the multiarmed bandit problem”. In: Machine learning 47.2-3 (2002), pp. 235–256.

[Dug+16] Joris Duguépéroux, Ahmad Mazyad, Fabien Teytaud, and Julien Dehos. “Pruning playouts in Monte- Carlo Tree Search for the game of Havannah”. In: The 9th International Conference on Computers and Games (CG2016). Leiden, Netherlands, June 2016.

[Hol92] John H Holland. “Genetic algorithms”. In: Scientific american 267.1 (1992), pp. 66–72.

[Lie+15] Arnaud Liefooghe, Sébastien Verel, Fabio Daolio, Hernan Aguirre, and Kiyoshi Tanaka. “A feature- based performance analysis in evolutionary multiobjective optimization”. In: 8th International Con- ference on Evolutionary Multi-Criterion Optimization (EMO 2015). Vol. 9019. Lecture Notes in Computer Science. 2015, pp. 95–109.

[Mit98] Melanie Mitchell. An introduction to genetic algorithms. MIT press, 1998.

[TD15] Fabien Teytaud and Julien Dehos. “On the tactical and strategic behaviour of MCTS when biasing random simulations”. In: ICGA Journal 38.2 (June 2015), pp. 67–80.

[Tey10] Fabien Teytaud. “A new selection ratio for large population sizes”. In: Evostar. Istanbul, Turkey, Apr. 2010.

Computer graphics

[CE05] David Cline and Parris Egbert. A Practical Introduction to Metropolis Light Transport. Tech. rep. Brigham Young University, 2005.

[Deh+08] Julien Dehos, Eric Zéghers, Christophe Renaud, François Rousselle, and Laurent Sarry. “Radiomet- ric compensation for a low-cost immersive projection system”. In: 15th ACM Symposium on Virtual Reality Software and Technology. VRST ’08. Bordeaux, France, Oct. 2008, pp. 130–133.

[Deh+14] Julien Dehos, Eric Zéghers, Laurent Sarry, François Rousselle, and Christophe Renaud. “Immersive front-projection analysis using a radiosity-based simulation method”. In: Virtual Reality 18.2 (June 2014), pp. 117–128.

[Jak10] Wenzel Jakob. Mitsuba renderer. http://www.mitsuba-renderer.org. 2010.

[Kaj86] James T. Kajiya. “The Rendering Equation”. In: SIGGRAPH Comput. Graph. 20.4 (Aug. 1986), pp. 143–150.

[PH10] Matt Pharr and Greg Humphreys. Physically Based Rendering, Second Edition: From Theory To Implementation. 2nd. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2010.

[VG97] Eric Veach and Leonidas J. Guibas. “Metropolis Light Transport”. In: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. SIGGRAPH ’97. New York, NY, USA: ACM Press/Addison-Wesley Publishing Co., 1997, pp. 65–76.

Metropolis

[AK89] Emile Aarts and Jan Korst. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. New York, NY, USA: John Wiley & Sons, Inc., 1989.

[Hwa88] Chii-Ruey Hwang. “Simulated annealing: theory and applications”. In: Acta Applicandae Mathemat- icae 12.1 (1988), pp. 108–111.

[LM03] Kathryn Blackmond Laskey and James W. Myers. “Population Markov Chain Monte Carlo”. In: Machine Learning 50.1 (2003), pp. 175–196.

[Met+53] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. “Equations of state calculations by fast computing machines”. In: J. Chem. Phys. 21 (1953), pp. 1087–1091.