Information Theory in Computer Graphics and Visualization

彬彬

Information Theory in Computer Graphics and Visualization

Mateu Sbert

University of Girona

Miquel Feixasy

University of Girona

Ivan Violaz

University of Bergen

Jaume Rigaux

University of Girona

Miguel Chover{

Jaume I University

Abstract

We present various applications of information theory for computer

graphics, based on the use of information measures such as entropy

and mutual information. Some application areas are hierarchical radiosity,

pixel supersampling, best view selection, scene exploration,

ambient occlusion, mesh saliency, mesh simplification, and scientific

visualization.

1 Course Description

We present a half-day course to review several applications of information

theory for computer graphics and visualization. Information

theory tools, widely used in scientific fields such as engineering,

physics, genetics, neuroscience, are also emerging as

useful transversal tools in computer graphics and related fields.

We introduce the basic concepts of information theory and how

they map into the application areas. Application areas in computer

graphics are viewpoint selection, mesh saliency, scene exploration,

ambient occlusion, geometry simplication, radiosity, adaptive raytracing

and shape descriptors. Applications areas in visualization

are view selection for volume data, flow visualization, ambient occlusion,

time-varying volume visualization, transfer function definition,

time-varying volume visualization, multimodal fusion, isosurface

similarity maps and quality metrics. The applications fall

broadly into two categories: the mapping of the problem to an information

channel, as in viewpoint applications, and the direct use

of measures as entropy, Kullback-Leibler distance, Jensen-Shannon

divergence, and f-divergences, to evaluate for instance the homogeneity

of a set of samples or being used as metrics. We also discuss

the potential applications of information bottleneck method

that allows us to progressively extract or merge information in a

hierarchical structure.

2 Course Organizer

Mateu Sbert.

e-mail: mateu@ima.udg.edu

ye-mail:feixas@ima.udg.edu

ze-mail:ivan.viola@uib.no

xe-mail:rigau@ima.udg.edu

{e-mail:chover@uji.es

3 Proposed Length

Half-day, Beginner level.

4 Intended Audience and Prerequisites

We target the course primarily at computer graphics and visualization

researchers and practitioners. In addition, information theory

practitioners will learn about the presented applications. We will

stress the common aspects of the applications to clearly see the kind

of problems information theory tools can help solving.

The reader is expected to have a basic background in computer

graphics. Information theory basics are presented and selfcontained

in this course.

5 Syllabus

1. Introduction to Information Theory (60 minutes)

Presenter: Miquel Feixas

Information theory deals with the transmission, storage, and

processing of information, and is applied to fields such as

physics, statistics, biology, neurology, and learning. It has

been successfully applied to areas closely related to computer

graphics, such as medical imaging and computer vision.

We present the concept of information channel and the most

basic information-theoretic measures: Shannon entropy (information

content or uncertainty of a random variable), conditional

entropy (uncertainty in a communication channel),

Kullback-Leibler distance between two probability distributions,

mutual information (shared information in a communication

channel) and its different alternative decompositions,

and entropy rate (average information content per symbol

in a stochastic process). Some important inequalities, such

as Jensen-Shannon inequality, log-sum inequality, and data

processing inequality, together with information bottleneck

method, are also reviewed. Finally, other divergence measures

and generalized entropies are briefly introduced.

To facilitate the understanding and applicability of the previous

information measures and methods, several simple examples

and algorithms, such as the entropy of a sequence of

characters and the information channel between stimuli and

responses, will be introduced.

2. Applications in Computer Graphics

Presenter: Mateu Sbert

a. Unified Viewpoint Framework for Polygonal Models

(30 minutes)

Viewpoint selection is an emerging area in computer graphics

with applications in fields such as scene exploration, imagebased

modeling, and volume visualization. Best view selection

algorithms are used to obtain the minimum number of

views to understand or model an object or scene. This application

has a high pedagogical value as helps us to understand

and reinforce all the information-theoretic concepts introduced

in the first part of the course.

We present a unified framework for viewpoint selection and

mesh saliency based on the definition of an information channel

between a set of viewpoints and the set of polygons of an

object. Both conditional entropy and mutual information are

shown to be powerful tools to deal with viewpoint selection,

object exploration, viewpoint similarity and stability, viewbased

ambient occlusion, and view-based saliency. Viewpoint

mutual information can be extended by incorporating

importance factors such as saliency and stability. Applications

to non-photorealistic rendering, molecular visualization,

and mesh simplification are also reviewed.

b. Applications to Global Illumination, Shape Recognition

and Image Processing (45 minutes)

We introduce scene complexity measures and their application

to radiosity. Radiosity is a viewpoint independent global

illumination technique that discretizes the scene into small

polygons or patches to solve a transport system of equations.

The way the scene is discretized is critical for the efciency of

the result. First, we dene a scene information channel, which

allows us to study the interchange of information between

the patches. From the study of this channel, several renement

oracles, i.e., criteria for subdividing the geometry, are

obtained, aimed at maximizing the transport of information.

We also present adaptive ray-tracing. This technique is aimed

at tracing more rays only where they are needed. Informationtheoretic

measures, such as Shannon entropy, Tsallis entropy,

and f-divergences, will be used to dene adaptive renement criteria.

Another application of information-theoretic measures is to

obtain different shape descriptors based on the complexity of

the object. Shape descriptors are important when classifying

and retrieving objects from databases. Inner and outer complexity,

obtained from mutual information calculation with

uniformly distributed lines, can be used to classify different

families of 2D and 3D objects.

A short overview of basic image processing techniques will

also be given. Algorithms of image processing, such as splitand-

merge segmentation and image registration, will be presented

as paradigmatic examples for the basic concepts of entropy,

mutual information, data processing inequality, and information

bottleneck method.

Break (15 minutes)

3. Applications in Visualization

Presenter: Ivan Viola

a. Visualization and Information Theory (20 minutes)

Visualization and interaction can be seen as an information

communication platform between a human and digital data

capturing certain phenomenon, its structure or process. Information

theory at the same time provides tools to quantify the

efficiency of transmitted information in a channel. From the

theoretical perspective information theory can be used to assess

the visualization efficiency or evaluate the visualization

parameters under which the information transfer is most efficient.

b. Information Theory in Scientific Visualization (55 minutes)

We discuss specific applications of information theory in volume

visualization. Viewpoint entropy and viewpoint mutual

information, as measures for viewpoint quality, can be

adapted for volume data by evaluating the volume elements

visibility instead of polygonal visibility discussed earlier. We

can consider the information contained in a volume in various

ways: as a set of voxels, iso-surfaces, or volumetric objects.

Visibility of these elements yields characteristic viewpoints.

Application in specific medical diagnostic scenarios will underline

utility of automatic view selection for user guidance.

Time varying data imposes an additional challenge on view

selection. We will discuss view selection for entire sequence

and camera path generation to allow for expressive viewpoints

during playback. Besides the view selection, information theory

tools can serve as steering mechanism for defining other

visualization parameters. Instead of a set of viewpoints, one

can define a set of representative iso-surfaces in a dataset. Illustrative

exploded views concept can also accommodate information

theory tools for defining an axis of explosion, as

well as the explosion partitioning based on similarity. In

multimodal volume visualization, the data fusion can be controlled

with information-theory measures. The transfer function

specification is a challenging task. With measures derived

from Kullback-Leibler distance this time-consuming process

can be efficiently assisted.

6 Course Presenter Information

Mateu Sbert is a full professor in Computer Science at the University

of Girona, Spain. He received a M.Sc. in Theoretical

Physics (1977) at the University of Valencia, a M.Sc. in Mathematics

(1983) at UNED University (Madrid) and a Ph.D. in Computer

Science at the Universitat Politcnica de Catalunya. His research interests

include the application of Monte Carlo, Integral Geometry

and Information Theory techniques to Computer Graphics and Visualization.

He has authored or co-authored more than 150 papers,

participated in four Eurographics tutorials, and served as a member

of program committee in international conferences.

Miquel Feixas is an associate professor in Computer Science at

the University of Girona, Spain. He received a M.Sc. in Theoretical

Physics at the Universitat Autnoma de Barcelona (1979)

and a Ph.D. in Computer Science at the Universitat Politcnica de

Catalunya (2002). His research is focused on the application of

Information Theory techniques to Computer Graphics and Visualization.

He has co-authored more than 50 papers, served as a member

of program committee in international conferences, and participated

in a Eurographics tutorial on Applications of Information

Theory to Computer Graphics.

Ivan Viola is an associate professor at University of Bergen, and

scientific adviser at Christian Michelsen Research (CMR), Bergen,

Norway. He received M.Sc. in 2002 and Ph.D. in 2005 from Vienna

University of Technology, Austria. His research is focused

on illustrative visualization for communication of complex scientific

data. Viola co-authored several scientific works published in

international journals and conferences such as IEEE TVCG, IEEE

Visualization, and EuroVis and acted as a reviewer and IPC member

for conferences in the field of computer graphics and visualization.

He is member of Eurographics, NorSIGD, IEEE Computer Society,

VGTC, and ACM SIGGRAPH.

7 Description of the Course Notes

The course notes include a copy of each presenter slides, a complete

bibliography for each of the topic areas, and a document

on the basics of information theory. This document is excerpted

from the book “Information Theory Tools for Computer Graphics”,

M. Sbert, M. Feixas, J. Rigau, M. Chover, and I. Viola, Synthesis

Lectures on Computer Graphics and Animation, Morgan &

Claypool Publishers, 2009 (http://dx.doi.org/10.2200/

S00208ED1V01Y200909CGR012).

Acknowledgements

This work was supported in part by Grant Numbers TIN2010-

21089-C03-01 from the Spanish Government and 2009-SGR-643

from the Catalan Government, by the VERDIKT program (#

193170) of the Norwegian Research Council, and by the strategic

funding for the MedViz research network (# 911597 P11) obtained

from Helse Vest.

C.R.CAN

发了那么多，我都不知道该用哪个给你回帖了，呵呵

晃晃

路过、路过、快到鸟，列位请继续...ing

菜刀吻电线

顶!学习了!阅!

C.R.CAN

百度的叫度娘，网易的叫易娘，新浪内部还在为是叫新娘还是浪娘而争论不休！……不管你们是企鹅的额娘，豆瓣的伴娘，还是华为的伪娘，都要记得，淘宝才是你们的亲娘啊！亲！！

晃晃

呵呵，很好，方便罗。

菜刀吻电线

凡系斑竹滴话要听；凡系朋友滴帖要顶

菜刀吻电线

已阵亡的 蝶 随 风 舞 说过  偶尔按一下 CTRL A 会发现 世界还有另一面

晃晃

再看一看，再顶楼主

晃晃

既来之，则看之！