Applications of Information Theory to Computer Graphics

(1)

07 ^Prague Czech Republic E U R O G R A P H I C S

Applications of Information Theory to Computer Graphics

Ivan Viola Mateu Sbert

Miquel Feixas Jaume Rigau

Miguel Chover

07 ^Prague Czech Republic E U R O G R A P H I C S

(2) Information Theory Basics

Miquel Feixas Jaume Rigau Mateu Sbert

3 Information Theory

Ŷ Claude Elwood Shannon, 1916-2001

Ŷ A mathematical theory of communication. The Bell System Technical Journal, July, October 1948 Ŷ Transmission, storage and processing of information Ŷ Applications:

Ŷ Physics, computer science, mathematics, statistics, economics, biology, linguistics, neurology, learning, etc Ŷ Medical image processing, computer vision, robot motion, etc Ŷ Shannon entropy measures the information content or

uncertainty of a random variable

Ŷ Mutual information measures the information transfer in a communication channel

4 Shannon Entropy

Ŷ Discrete random variable X

X : {x ₁ , x ₂ , … , x _n } , p _i = p(x _i ) = Pr { X = x _i } Shannon entropy of X : uncertainty, information

Ŷ How difficult it is to guess the values of a random variable

Ŷ Homogeneity or uniformity of a probability distribution

i n

i

i p

p X

H ( ) log

¦ 1

Shannon Entropy

Ŷ Properties

Ŷ Ŷ

Ŷ Binary entropy n X H ( ) log 0 d

¦

¦ ^m

i

i i m

i

i H Y i q q

q X H

1 1

log )

( )

(

Information Channel

Ŷ Information channel

Ŷ Conditional entropy Ŷ Joint entropy

Ŷ Mutual information:

dependence, correlation, shared information

¦¦

n

i m

j

i j

ij p

p X

Y H

1 1 log |

)

| (

j i

ij n

i m

j

ij p q

p p

Y X H X H Y X I

log

)

| ( ) ( ) , (

1 1

¦¦

i j i

ij p p

p _|

X Y

p _i q _j

p _{j | i}

¦¦

n

i m

j

ij

ij p

p Y

X H

1 1

log )

,

(

(2)

7 Information Channel

Ŷ Properties

Ŷ Ŷ Ŷ Ŷ Ŷ

) ( )

| (

0 d H X Y d H X

H(X|Y)

I(X;Y) H(Y|X)

H(X) H(Y)

)

| ( ) ( ) ,

( X Y H X H Y X

H

) , ( X Y ) I ( ) ( ) ,

( X Y H X H Y

H

0 ) , ( ) ,

( X Y I Y X t

I

) ( ) ,

( X Y H X

I d

8 Inequalities

Ŷ Jensen’s inequality: if f(x) is a convex function

Ŷ Log-sum inequality

Ŷ Data processing inequality : if X o ^Y o ^Z is a Markov chain, then

)]

( [ ]) [

( E X E f X

f d

¦

¦ ¦

¦ ^¸

¹

¨ ·

©

t § _n

i i n

i n i

i i i i n

i i

b a b a

a a

1 1 1

1 log log

) , ( ) ,

( X Y I X Z

I t

9 Relative Entropy

Ŷ Kullback-Leibler distance

Ŷ Properties Ŷ Ŷ

¦ ⁿ

i j

i i

KL q

p p q p D

1 log )

||

(

0 )

||

( p q t D _KL

}) {

||

} ({

) ,

( X Y D KL p ij p i q j

I

10 Jensen-Shannon Divergence

Ŷ Jensen-Shannon divergence

Ŷ Properties

Ŷ Concavity of entropy:

Ŷ

¦

¦ ^¸

¹

¨ ·

©

§ ^N

i

i i N

i i i N

N p p H p H p

JS

1 1

1 1 ,..., ; ,..., ) ( )

( S S S S

0 ) ,...,

; ,...,

( 1 N p 1 p N t

JS S S

¦ ¦ ^¸

¹

¨ ·

©

N §

i

N

i i i i KL i N

N p p D p p

JS

1 1

1 1 ,..., ; ,..., ) ||

( S S S S

) , ( ))

| ( ),...,

| ( );

( ),..., (

( p x ₁ p x p y x ₁ p y x I X Y

JS _n _n

11 f-Divergences

Ŷ Family of convex functions based on a convex function f

Ŷ Kullback-Leibler distance

Ŷ Chi-square distance

Ŷ Hellinger distance

¦ X x

KL q x

x x p p q p

D ( )

) log ( ) ( )

||

(

¦

X

x q x

x q x q p

D p

) (

)) ( ) ( ) ( ,

( ²

F 2

¦

X x

h p q p x q x

D ( ( ) ( ) ) ²

2 ) 1 , (

2 ¦ ¸¸

¹

· ¨¨ ©

§

X x

f q x

x f p x q q D p

) (

) ) ( ( ) ,

( - D _f (p,q) is convex on (p,q) - D _f (p,q) 0

- D _f (p,q) = 0 p=q

12 Continuous Channel

Ŷ Continuous entropy

Ŷ Continuous mutual information

Ŷ I ^c (X,Y) is the least upper bound for I(X,Y) Ŷ Refinement can never decrease I(X,Y)

dx x p x p X H

S

c ( ) ³ ( ) log ( ) ^lim ^' ^o ⁰ ^H ⁽ ^X ^' ⁾ ^z ^H ^c ⁽ ^X ⁾

y dxdy p x p

y x y p

x p Y X I

S S c

) ( ) (

) , log ( ) , ( ) ,

( ³ ³

) , ( ) , (

lim 0 I X ^' Y ^' I ^c X Y

o

'

(3)

13 Information Bottleneck Method (IBM)

Ŷ Tishby, Pereira and Bialek, 1999

Ŷ Find a compressed signal that needs short encoding (small ) while preserving as much as possible the information on the relevant signal ( )

Xˆ )

Xˆ , X ( I

) Y , Xˆ ( I

X ^p ⁽ ^xˆ ^| ^x ⁾ ^Xˆ ^p ⁽ ^y ^| ^xˆ ⁾ Y

) xˆ ( p ) Xˆ , X (

I I ( Xˆ , Y )

) Y , X ( I

14 Agglomerative IBM

Ŷ Goal: find a clustering that minimizes the loss of mutual information

Ŷ Clustering or merging: loss of mutual information

Ŷ The quality of each cluster is measured by the Jensen- Shannon divergence between the individual distributions in the cluster

))

| ( ),...,

| ( );

( / ) ( ),..., ( / ) ( ( ) (

) , ( ) , (

1 1 p x p x m p x p y x p y x m

x p JS x p

Y X I Y X I

¦ ^m

k

x k

p x p

1 ) ( )

(

x ˆ

15 Generalised Entropy

Ŷ Harvda-Charvát-Tsallis entropy (HCT)

Ŷ Generalised mutual information H ₁ (X) { lim _{D o1} H _D (X) k p _i

i 1

¦ n ^ln ^p ⁱ

k ! 0, D R \ {1}

H _D (X ) k 1 i

p D i 1

¦ n

D 1

I _D ( X, Y ) 1

1 D 1 ^ij

p D j D 1 i D 1

p q

j 1

¦ m i 1

¦ n

§

©

¨ ¨

· ¹

¸ ¸

07 ^Prague Czech Republic E U R O G R A P H I C S

(3) Refinement Criteria for Radiosity

Jaume Rigau Miquel Feixas Mateu Sbert

Radiosity Method

Ŷ The radiosity method solves the problem of illumination in an environment of diffuse surfaces Ŷ Continuous radiosity equation

S F x y B y dA y

x x E x

B ⁽ ⁾ ⁽ ⁾ ^U ⁽ ⁾ ³ ⁽ ^, ⁾ ⁽ ⁾

) , cos ( ) cos

,

( ₂ V x y

y r x F

xy y x

S T T

T x

T y

r xy

y

x

Radiosity Method

Ŷ Discrete radiosity equation

Ŷ Form factor properties Ŷ Reciprocity

Ŷ Energy conservation

¦

n p

j j ij i i

i E F B

B

1 U

ji j ij

i F A F

A

1 ¦ ^p 1 n

j

F ij

³ ³ A i A j y x i

ij F x y dA dA

F A 1 ( , ) T x

T y

r xy

y

x A i

A j

(4)

19 Form Factor Computation

Ŷ Analytical solutions

Ŷ Between two spherical patches Ŷ Monte Carlo computation

Ŷ Uniform area sampling Ŷ Uniformly distributed lines

S j

ij A

F A

A j

A i

¦ ^N

k k k j

ij F x y

A N F

1 ) , 1 ( ˆ

i ij

ij N

F ˆ N Local lines

A j

A i

Global lines

A j

A i

20 Refinement Criteria for HR

Ŷ In hierarchical radiosity (HR), the mesh is generated adaptively

Ŷ Oracles based on Ŷ Transported power

Ŷ Kernel smoothness H U i A i F ij B j

H

U ij j j

av ij av ij ij

i max( F ^max F , F F ^min ) A B

21 Ŷ The scene is modelled as an information channel

X Y

p _i q _j p _{j | i}

X Y

a _i a _j F _{i j}

p ij

ij i F a Scene Information Channel

22 Scene Information Channel

T i

i A

a A

j ij ij n

i n

j i S

P

S a

F F a H

H I

p p

log

1 1

¦¦

Scene mutual information

i n

i i

P a a

H

p

log

¦ 1

Positional entropy

?

ij n

j ij n

i i

S a F F

H

p p

log

1 1 ¦

¦

Scene entropy

23 Continuous Mutual Information

Ŷ By discretising a scene, a distortion or error is introduced: information loss

Ŷ From discrete to continuous Ŷ ¦ o ³

Ŷ F _ij o F(x,y) Ŷ a _i = A _i / A _T o 1 / A _T

dxdy y x F A y x A F

I _T

S

x y S

T c

s 1 ( , ) log( ( , ))

³ ³

24 Monte Carlo Computation

4. Scene visibility complexity

x

y T y

T x

Total area = A _T Lines cast = K

Line segments = N

¦ _¸ ^¸

¹

· ¨ ¨

©

| §

N

xy y x c T

S r

A

I N

1 2

cos log cos

1 S T T

contribution of

each segment

(5)

25 Dicretisation Error

Ŷ Two basic results

Ŷ If any patch is subdivided, I _S increases or remains the same Ŷ I _S ^c is the least upper bound to I _S

Ŷ Discretisation error S t 0

c

S I

I

690 .

S 0

I I S 2 . 199 I S 2 . 558 I S 2 . 752 273

. 3

c

I S

26 Ŷ Mutual information matrix

Information Transfer

information transfer between patches i and j I ij

information transfer from patch I ⁱ i

j ij n

i n

j ij i S

p p

a log F F a I

1 1

¦¦

¦¦³ ³ ^p ^p i j n

i n

j A A T

T

dxdy y x F A y x A F

1 1

)) , ( log(

) , 1 (

c

I S

27 Discretisation Error Between Two Patches

ij c ij

ij I I

G

0 ) , 1 ( log ) , 1 (

) , ( log ) , 1 (

1 1

1 t

»

» »

»

¼ º

«

« «

«

¬ ª

¸ ¸

¹

· ¨ ¨

©

§

¸ ¸

¹

· ¨ ¨

©

§

¸ ¸

¹

· ¨ ¨

© §

¸ ¸

¹

· ¨ ¨

©

§

|

¦

ij ij

ij

N

k k k ij N

k k k ij

k k N

k k k ij T

j i ij

y x N F y x N F

y x F y x N F A

A G A

Monte Carlo integration

log-sum inequality

Ŷ Discretisation error between two elements: loss of information transfer

28 MI-based Oracle

Ŷ From radiosity equation and kernel-smoothness- based oracle

Ŷ Ŷ

Ŷ to MI-based oracle Ŷ

¦

n p

j j ij i i

i E F B

B

1 U

H

U ij j j

av ij av ij ij

i max( F ^max F , F F ^min ) A B

H G U U ij j i ij j

c ij

i ( I I ) B B

Oracles for HR

Kernel- smoothnes-

based

MI-based

2684000 rays - 19000 patches - 10 lines FF

MI-based Oracle for HR

2684000 rays - 19000 patches - 10 lines FF

(6)

31 Generalised MI-based Oracle

D=0.50 - 10 lines FF 2684000 rays - 19000 patches

32 Generalised MI-based Oracle

D=0.50 - 10 lines FF - 9268000 rays - 10000 patches

33 f-Divergence-based Oracles

Kernel-Smoothness Kullback-Leibler

Chi-Square Hellinger

10 lines FF - 2684000 rays - 19000 patches

07 ^Prague Czech Republic E U R O G R A P H I C S

(4) Refinement Criteria for Ray-Tracing

Jaume Rigau Miquel Feixas Mateu Sbert

35 Adaptive Sampling

Ŷ Adaptive control of the sampling rate

Ŷ Image-Space

Ŷ Intensity Comparison Ŷ Intensity Statistics Ŷ Object-Space

Ŷ Hybrid (image+object spaces)

Pr {S _T [S t,S t]} 1 D

[Purgathofer, 87]

[Tamstorf and Jensen, 97]

C(S) S ^max S min

S max S min

[Mitchell, 87]

p g 1 d ^min d max [Simmons and Séquin, 00]

36 Pixel Measures

Point-sampling-based technique for image synthesis Capture the pixel radiance

Finite set of samples

Information is lost Artifacts

Stochastic RT random walk

Noise Erroneous information

Information Theory Entropy Information measure

Refinement tree Refinement criterion

More samples!

Regions with high inhomogeneity illumination

Adaptive sampling

Where?

Measure!

(7)

37 Pixel Colour Quality

T d i

c(r,g,b)

pixel channel entropy

Number of samples

Q c

w c Q ^c

¦ cc

w c

¦ cc

Q c

H c

log N s

pixel colour quality

Channel perception coefficient

Colour system pixel channel quality

H c i

p c log

i 1 N s

¦ ^p ⁱ ^c

For each channel

i

p c colour fraction of a ray

US cruiser Saba Rofchaei and Greg Ward

38 Pixel Colour Contrast

d i

c(r,g,b)

C c

w c c C ^c

¦ cc

w c c

¦ cc

pixel colour contrast For each channel

C c 1 Q ^c

pixel channel contrast Pixel channel

colour average For each channel

i

p c colour fraction of a ray

T

Cabin Cindy Larson

39 Pixel Geometry Contrast

pixel geometric entropy

C g 1 Q ^g Q g

H g

log N _s pixel geometric contrast

i

p g geometric fraction of a ray

pixel geometric quality

H g i

p g log

i 1 N s

¦ ^p ⁱ ^g

cos T d 2

d i

c(r,g,b) T

Class room Peter Shirley

Combination coefficient C c G _C ^c 1 G C ^g Combination of colour and geometry pixel contrast

40 Quality Map

8 rays per pixel

Map of geometric

quality

Map of colour quality

Contrast Map

Contrast C ^g

Contrast C c

8 rays per pixel

Supersampling

Uniform with 32 rays per pixel

8 rays per pixel G=0.9

Average rays per pixel: 32

(8)

43 Entropy-based Adaptive Sampling

H ( X ) q i log q _i

i 1 m

¦ ^{q H} ⁱ ⁽ ^Y ⁱ

i 1 m

¦ ⁾

information acquired

hidden information image information

• q _i { colour probability of pixel i

• H(Y _i ) { entropy of each root pixel

• H(X) { entropy of the whole image

The decomposition of H can be recursively extended to the subpixels Grouping property of Entropy

44 Contrast Tree

p 0

p ₁

p ₂ c 3

c 1

c ₂ q ₁

q ₂

q 3

k 2

n=2 n=0

n=1

n=3

k ₀

k 1

n>3

n

C c w ^c n c

C

cc ¦ ^q ⁿ ^c C C n ^c G C n ^c 1 G ^g n c _n is the final colour of a region q _n is the importance of a node

p _n is the probability of the tree-branch k=(k _o ,…,k _n-1 )is the tree-path

ⁿ

q p _"

" 1 n1

^| ^c ⁿ

r n1

N

45 Results

Classic contrast

… and weighted by importance q

Variance-based contrast Entropy-based contrast Importance-weighted contrast

contrast weighted by channel coulour average maximum recursive level = 4 4 regions, 8 rays/region, avg = 60

groups of 8 rays, avg = 60 D =0.1, d=0.025

4 regions, 8 rays/region, avg = 60 G ⁼¹

Entropy Importance

Classic Variance

46 Results

Classic contrast

Contrast map G=0.9

Average rays per pixel: 185

47 f-Divergences

Ŷ f-Divergences as refinement criteria in RT ?

Ŷ Distributions

Ŷ {p} = Luminance L of N _S -samples Ŷ {q} = Uniform 1/N _S

Ŷ Homogeneity: D _f (p,q)

Ŷ Weights for D _f Ŷ Importance: avg(L _i ) Ŷ Convergence: 1/N _S

D f (p,q) q(x) f p(x) q(x)

§

© ¨ ·

¹ ¸

xX

¦

48 f-Divergence-based Adaptive Sampling

q i

1 N _s

1 N _s L D _f ( p,q) H

p i

L i

L j j 1 N

s

¦ ¦ ^N

i i s

s

N L L

1

1 Kullback-Leibler Chi-Square Hellinger

1 N _s L D _KL (p,q) H 1

N _s L D _F ² (p,q) H 1

N _s L D h ² (p,q) H 1

N _s L D _f (p,q) H Luminance

distribution

Luminance average

Uniform

distribution

(9)

49 Results

Confidence Test Chi-Square Kullback-Leibler Hellinger

07 ^Prague Czech Republic E U R O G R A P H I C S

(5) Viewpoint Selection and Mesh Saliency

Miquel Feixas Mateu Sbert Francisco González

51 Introduction

Ŷ Viewpoint selection is an emerging area in computer graphics with applications in fields such as scene understanding, volume visualization, image-based modeling, and molecular visualization

Ŷ We present a unified framework for viewpoint selection and mesh visibility / saliency / simplification based on an information channel between a set of viewpoints and the polygons of an object

Ŷ Tools: entropy, mutual information, Jensen-Shannon divergence

Ŷ This framework is based on the geometric characteristics of the object, but it can be extended to other characteristics

Ŷ It is also valid for any set of viewpoints in a closed scene

Ŷ What is a good viewpoint? Depending on our objective, the best viewpoint can be the most representative one or the most unstable one (maximally changes when it is moved within its close neighborhood) or …

Ŷ Representative views can help us to understand the object

Ŷ Unstable views enable us to obtain critical viewpoints to capture the structure of the object

52 Background and Related Work

Ŷ Information Theory

Ŷ Discrete random variable X

X : {x ₁ , x ₂ , … , x _n } , p(x _i )= Pr { X = x _i } Ŷ Shannon entropy of X : uncertainty, ignorance

Background and Related Work

Ŷ Information Theory Ŷ Information Channel Ŷ Conditional Entropy Ŷ Mutual Information

Ŷ Jensen-Shannon inequality

X Y

{ p(x)} { p(y)}

{ p(y|x)}

Background and Related Work

Ŷ Related Work

Ŷ Heuristic measure Plemenos et al. [1996]

Ŷ Viewpoint Entropy

Ŷ Kullback-Leibler distance

Ŷ Origins Rigau et. al [2000], Vázquez et al. [2001-2006], Sbert. Et al

[2005]

(10)

55 Viewpoint Information Channel

Ŷ We formalize the viewpoint selection using an information channel

Ŷ This framework is based on geometric characteristics

V O

{ p(v)} { p(o)}

{ p(o|v)}

56 Viewpoint Information Channel

Ŷ Viewpoint Mutual Information Ŷ Conditional Entropy

Ŷ Mutual Information: degree of correlation, dependence

Ŷ H(v) depends on the polygonal discretization

Ŷ MI converges to a finite value when the mesh is infinitely refined

Ŷ Low values: representative views Ŷ High values: highly coupled views

57 Viewpoint Information Channel

Ŷ Viewpoint Mutual Information evaluation (I)

Worst View Spheres

Best View

HM VE VMI

58 Viewpoint Information Channel

Ŷ Viewpoint Mutual Information evaluation (II)

Heuristic Entropy VMI

- +

Model

59 Viewpoint Information Channel

Ŷ Viewpoint Similarity and Unstability Ŷ Viewpoint Similarity

Ŷ Any clustering over V V or O O reduce I(V,O)

Spheres

ˆ ˆ

60 Viewpoint Information Channel

Ŷ Viewpoint Similarity and Unstability Ŷ Viewpoint Unstability

Spheres ŶThe maximum change in view that occur when the camera position is shifted within a small neighborhood

Stable Unstable Unstability Spheres

(11)

61 Viewpoint Information Channel

Ŷ Selection of n Best Views

Ŷ Objective: to select the minimal set of representative views Ŷ Ideal proposal: n views that maximize their JS (to capture the

maximum information of the object)

Ŷ Greedy strategy: to select successive views that maximize JS

62 Viewpoint Information Channel

Ŷ Viewpoint Clustering Ŷ Clustering algorithm

Ŷ Select the n best views

Ŷ Assign each viewpoint to the nearest best viewpoint

Two clusters Five clusters

63 Scene Exploration

Ŷ Exploratory Tour

Video

64 Scene Exploration

Ŷ Guided Tour

Video

Mesh Visibility

Ŷ Reversion of the Channel

Ŷ Channel is reversed using the Bayes theorem

Ŷ I(V,o) is the polygonal mutual information

Ŷ Degree of correlation between the polygon o and the set of viewpoints

Mesh Visibility

Wireframe Visibility Triangle Visibility Vertice Ambien t Occlusion

Big guy Coffeecup Chesnut tree Lady of Elche

(12)

67 Mesh Visibility

12 42 162 642

640 x 480

PROJ ECTION RESOLUTION

NUMBER OF VIEWPOINTS

1280 x 960 2560 x 1920 5120 x 3840

68 Mesh Visibility

Ogre Model Chesnut Tree Model

Ambien t Occlusion Mesh Visibility

69 Mesh Visibility

Demo

70 Mesh Visibility

Demo

71 Mesh Visibility

Ŷ Applications

Ŷ Important viewpoints

Ŷ Importance at the viewpoint space

Ŷ Selection according to geometry and saliency

72 Mesh Visibility

Ŷ Applications

Ŷ Relighting for Non-Photorealistic Rendering

Ŷ Warping a color palette texture to the viewpoint sphere

Ŷ Color ambient occlusion + NPR technique

(13)

73 Mesh Visibility

Ŷ Applications

Ŷ Relighting NPR + Coloroid Palettes

74 Mesh Visibility

Demo

75 Mesh Saliency

+ ^Saliency -

Coffeecup Angel Lady of Elche Hebe

76 Viewpoint Saliency

+ ^Saliency -

Most Salient Least Salient Saliency Spheres

Importance-based Viewpoint Mutual Information

Model Importance Map

Importance-based VMI Sphere Importance-based VE Sphere

Importance-based Viewpoint Mutual Information

Saliency VMI Spheres

Saliency-based Best N Views

(14)

79 View-based Object Recognition

Ŷ System features

Ŷ VMI Sphere View-based Shape descriptor Ŷ Rigid registration system Rotations (ș, ĳ) Ŷ 642 viewpoints

Ŷ Fixed & Floating Sphere Ŷ Metric

Ŷ Interpolator Nearest Neighbour

¦ ^N

i i

i b

a B A MSE

1 ) 2

( ) , (

Floating Fixed

80 View-based Object Recognition

METRIC

TRANSFORMATION

INTERPOLATOR FLOATING

FIXED

REGISTED SPHERE

R(ș) R(ĳ)

81 View-based Object Recognition

Ŷ Results

VMI Spheres Models

82 View-based Object Recognition

Ŷ Results

07 ^Prague Czech Republic E U R O G R A P H I C S

(6) View Selection in Scientific Visualization

Ivan Viola University of Bergen

Norway

84 View Selection for Volume Data

Viewpoint quality = visibility of data

Visibility computation

Information-theoretic measures for characteristic viewpoint estimation

Viewpoint entropy

Mutual information

View selection approaches for

3D scalar fields

3D + time scalar fields

Objects in volume data

(15)

85 View Selection for Set of Iso-Surfaces [Takahashi et al. Vis05]

86 View Selection for Scalar Volumes (+ Time) [Bordoloi and Shen Vis05]

87 Dynamic Views for Time-Varying Volumes [Ji06 and Shen Vis06]

07 ^Prague Czech Republic E U R O G R A P H I C S

Focus of Attention

View Selection for Volumetric Objects

Focus of Attention

Importance distribution among objects controls:

Characteristic view computation

Interactive focusing

Characteristic view computation

View rating image and object weights

For every object + context

Interactive focusing

Visual emphasis and cutaways

Changing the focus among objects

Goal

Input: known and classified volumetric data

High level request: show me object X

Output: guided navigation to object X

(16)

91 Focusing Considerations

Characteristic view

Emphasis of focus object

Guided navigation between characteristic views

92 Framework

importance distribution v

1

v

2

v

3

o

1

o

2

o

3

visibility estimation

image-space weight

p(v

1

)

p(v

n

) p(o

1

|v

1

)

p(o

m

|v

n

)

p(o

1

) p(o

m

)

...

I(v

i

,O) = p(o Ȉ

j j

|v

i

) log

m

p(o

j

|v

i

)

p(o

j

)

...

information-theoretic framework for optimal viewpoint estimation

o

2

object selection by user v o

1

o

2

o

3

object-space distance weight

characteristic viewpoint estimation

o

2

up-vector information

93 o

2

o

3

o

1

importance distribution

p(v

n

) p(o

m

|v

n

)

p(o

1

) p(o

m

)

...

o

1

o

2

o

3

object selection by user

o

1

o

2

o

3

v

viewpoint transformation

v o

1

o

2

o

3

cut-away and level of ghosting

o

3

o

1

o

2

o

3

focus discrimination

characterist i interactive focus of attention

o

1

o

2

o

3

up-vector information

Framework

94 Characteristic Views

Overview

All objects are visible

Visibility of objects is balanced

Characteristic view of focus object

High visibility for focus object

If possible other objects also visible

o2o3 o1 importance distribution

v

1

v2v3

o1 o2 o3 visibility estimation image-space weight

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

I(vi,O) = p(oȈjj|vi) log

m p(op(oj|vj)i)...

...

information-theoretic framework for optimal viewpoint estimation

o1 o2 o3 object selection by user

v o1

o2 o3 object-space distance weight

o1o2 o3 v viewpoint transformation

v o

1

o2 o3 cut-away and level of ghosting

o3 o1

o2 o3 focus discrimination

characteristic viewpoint estimationinteractive focus of attention

o1 o2 o3 up-vector information

95 Characteristic View Estimation

importance distribution v

1

v

2

v

3

o

1

o

2

o

3

visibility estimation

image-space weight

p(v

1

)

p(v

n

) p(o

1

|v

1

)

p(o

m

|v

n

)

p(o

1

) p(o

m

)

...

I(v

i

,O) = p(o

j

|v

i

) log

j

m

p(o

j

|v

i

)

p(o

j

)

... ...

...

information-theoretic framework for optimal viewpoint estimation

o

2

object selection by user v o

1

o

2

o

3

object-space distance weight

characteristic viewpoint estimation

o

2

up-vector information

characteristic viewpoint estimation

view rating

96 View rating

v 1

v 2

v ₃

v ₄

v ₅ v 6

v ₇ v 8 o ₁

o 2

o 3

v

1

v2 v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vj)i)...

...

v o1

v o

1

o3 o1

For every view

For every object

(17)

97 View Rating

o

2o3

o1 importance distribution v1

v

2

v

3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

o2 o

3

cut-away and level of ghosting

o

3

o

1

o

2

o3 focus discrimination

Visibility

High

Low

Location in image

In image center

Outside center

Distance to the viewer

Object close to the viewer

Far from the viewer

98 View Rating Weights

v

1

v2 v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

v o

1

o3 o1

object-space distance weight

image-space weight

99 Characteristic Viewpoint Estimation

importance distribution v

1

v

2

v

3

o

1

o

2

o

3

visibility estimation

image-space weight

p(v

1

)

p(v

n

) p(o

1

|v

1

)

p(o

m

|v

n

)

p(o

1

) p(o

m

)

...

... ...

I(v

i

,O) = p(o

j

|v

i

) log

j

m

p(o

j

|v

i

)

p(o

j

)

... ...

...

information-theoretic framework for optimal viewpoint estimation

o

2

object selection by user v o

1

o

2

o

3

object-space distance weight

characteristic viewpoint estimation

o

2

up-vector information

characteristic viewpoint estimation

characteristic views

100 Characteristic Views

Overview

All objects are visible

Visibility of objects is balanced

Characteristic view of focus object

High view rating (visibility) for focus object

If possible other objects also visible

v

1

v2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vj)i)...

...

v o1

v o

1

o3 o1

Obtaining Characteristic Views

Sets of views and objects are random variables

Views V=(v ₁ , v ₂ , v ₃ , ... , v _n )

Objects O=(o ₁ , o ₂ , o ₃ , ... , o _m )

View rating (visibility, weights)

Information channel between VĺO

Conditional probability p(o _j |v _i )

Mutual information between V and O expresses degree of dependance

o

2o3

v

2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

o2 o

3

o

3

o

1

o

2

Obtaining Characteristic Views

v

1

v2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

v o

1

o3 o1

Viewpoint mutual information is dependance between v _i and O

High values = high dependance

Small number of objects

Low average visibility

Low values = low dependance

Maximum objects visible

Object visibility is balanced

Minimal VMI determines the best view

(18)

103 Probability Transition Matrix

o

2o3

v

2

v

3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

o2 o

3

o

3

o

1

o

2

p(v ₁ ) p(v ₂ ) p(v ₃ )

...

p(v _n )

p(o ₁ ) p(o ₂ ) p(o ₃ ) ... p(o _m ) p(o ₁ |v ₁ ) p(o ₂ |v ₁ )

p(o ₁ |v ₂ )

...

p(o _m |v _n )

...

p(o _m |v ₁ )

p(o ₁ |v _n )

probability of the viewpoint

marginal probability of the object view rating of object o _j from viewpoint v _i

104 Viewpoint Mutual Information

v

1

v2 v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

v o

1

o3 o1

Degree of correlation v _j ļO

¦ j j

i j i

j

i p o

v o v p

o p O

v

I ( )

)

| log (

)

| ( )

, (

p(v ₁ ) p(v 2 ) p(v 3 )

...

p(v _n )

p(o 1 ) p(o 2 ) p(o 3 ) ... p(o m ) p(o ₁ |v ₁ ) p(o ₂ |v ₁ )

p(o 1 |v 2 )

...

p(o _m |v _n )

...

p(o m |v 1 )

p(o ₁ |v _n )

105 Characteristic Views

Overview

All objects are visible

Visibility of objects is balanced

Characteristic view at focus object

High view rating for focus object

If possible other objects also visible

o

2o3

v

2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vji))...

...

v o1

o2 o

3

o

3

o

1

o

2

106

¦

j

k

k k

j j

i j i

j i

o im o p

v o v p

o p O

v I

) ( ) (

)

| log (

)

| ( )

, (

Incorporating Importance

v

1

v2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vj)i)...

...

v o1

v o

1

o3 o1

importance distribution

o ₁ o ₂ o ₃

107 Resulting Characteristic Viewpoints

108 o

2

o

3

o

1

importance distribution

p(v

n

) p(o

m

|v

n

)

p(o

1

) p(o

m

)

...

o

1

o

2

o

3

object selection by user

o

1

o

2

o

3

v

viewpoint transformation

v o

1

o

2

o

3

cut-away and level of ghosting

o

3

o

1

o

2

o

3

focus discrimination

characterist i interactive focus of attention

o

1

o

2

o

3

up-vector information

Interactive Focus of Attention

(19)

109 Emphasis of Focus Object

Levels of sparseness

representation

0 importance max

dense

importance distributionô¹ô²ô³ v1

v

2

v

3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

o2 o

3

o

3

o

1

o

2

110 Emphasis of Focus Object

Cut-aways to unveil internal features

Labeling to add textual information

vessels

intestine kidneys

v

1

v2 v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(oj|vi)

p(oj)...

...

v o1

v o

1

o3 o1

111 Guided Navigation Between Objects

o

2o3

v

2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vji))...

...

v o1

o2 o

3

o

3

o

1

o

2

Decreasing importance of Object X

De-emphasis of Object X

Change to overview

Increasing importance of Object Y

Emphasis of Object Y

Change to characteristic view of Y

112 Refocusing

o ¹ o ² o ³

v ^c

v ¹ v ²

v

1

v2v3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vj)i)...

...

v o1

v o

1

o3 o1

Characteristic

view 1 Characteristic

view 2 Overview

Refocusing

o ¹ o ² o ³

v ^c

v ¹ v ²

o ¹ o ²

o

2o3

v

2

v

3

p(v1)

p(vn) p(o1|v1)

p(om|vn)

p(o1) p(om)

...

m p(op(oj|vji))...

...

v o1

o2 o

3

o

3

o

1

o

2

Applications of Information Theory to Computer Graphics

07 Prague Czech Republic E U R O G R A P H I C S