Talk Overview

(1)

Object Pose Solution Computer Vision In Action kd-trees

Color Quantization Point Models Visibility Map Space Filling Curves

Home Page

Title Page

JJ II

J I

Page1of65

Go Back

Full Screen

Spatial Data Structures for Computer Graphics

http://www.cse.iitb.ac.in/∼sharat November 2008

(2)

Home Page

Title Page

JJ II

J I

Page1of65

Go Back

Full Screen

Close

Spatial Data Structures for Computer Graphics

Acknowledgements:

Joint work with Biswarup Choudhury and Rhushabh Goradia

(3)

Home Page

Title Page

JJ II

J I

Page1of65

Go Back

Full Screen

Spatial Data Structures for Computer Graphics

Acknowledgements:

Joint work with Biswarup Choudhury and Rhushabh Goradia Most examples are from ViGIL IIT Bombay.

(4)

Home Page

Title Page

JJ II

J I

Page2of65

Go Back

Full Screen

Close

Talk Overview

Exhibit B: Which picture do you like?

ß Background about this talk

(5)

Home Page

Title Page

JJ II

J I

Page2of65

Go Back

Full Screen

Talk Overview

ß Background about this talk ß Application in Vision

• Exhibit A: kd-trees

(6)

Home Page

Title Page

JJ II

J I

Page2of65

Go Back

Full Screen

Close

Talk Overview

ß Application in Imaging

• Exhibit B: Octrees

(7)

Home Page

Title Page

JJ II

J I

Page2of65

Go Back

Full Screen

Talk Overview

ß Application in Imaging

• Exhibit B: Octrees

ß Application in Graphics

• Exhibit C: Space Filling Curves, Compressed Oc- trees

(8)

Home Page

Title Page

JJ II

J I

Page3of65

Go Back

Full Screen

Close

Background

Level 2 Level 3

Level 1

Visible

Visible Visible

Visible NODE N

Exhibit C: Visibility Map

• Why this talk: Role of tradi- tional CS and CSE in graphics

(9)

Home Page

Title Page

JJ II

J I

Page3of65

Go Back

Full Screen

Background

Level 2 Level 3

Level 1

Visible

• Not a theory talk (algorithms are correct, but may not be op- timal in a big-Oh sense)

(10)

Home Page

Title Page

JJ II

J I

Page3of65

Go Back

Full Screen

Close

Background

Level 2 Level 3

Level 1

Visible

• Use of images, and points as primitives in computer graphics

(11)

Home Page

Title Page

JJ II

J I

Page3of65

Go Back

Full Screen

Background

Level 2 Level 3

Level 1

Visible

• Please feel free to interrupt and ask questions at any stage

(12)

Home Page

Title Page

JJ II

J I

Page3of65

Go Back

Full Screen

Close

Background

Level 2 Level 3

Level 1

Visible

• Please feel free to interrupt and ask questions at any stage

• Vision, Graphics, and Imaging: Forward and Inverse Problems

(13)

Home Page

Title Page

JJ II

J I

Page4of65

Go Back

Full Screen

Talk Overview

4 Background about this talk ß Application in Vision

• Exhibit A: kd-trees ß Application in Imaging

• Exhibit B: Octrees ß Application in Graphics

(14)

Home Page

Title Page

JJ II

J I

Page5of65

Go Back

Full Screen

Close

Problem Definition: Object Pose

Object Pose: Given images of a static object, how to create the illu- sion of realistic motion of the object along any arbitrary path — com- posed realistically in arbitrary environments?

(15)

Home Page

Title Page

JJ II

J I

Page5of65

Go Back

Full Screen

Problem Definition: Object Pose

[Play Video]

(16)

Home Page

Title Page

JJ II

J I

Page6of65

Go Back

Full Screen

Close

Problem Definition: Object Pose

(17)

Home Page

Title Page

JJ II

J I

Page7of65

Go Back

Full Screen

1. Object Pose Solution

Image Acquisition (Studio) Path specification (Run-Time)

Computing Shape Computing Color

(18)

Home Page

Title Page

JJ II

J I

Page7of65

Go Back

Full Screen

Close

1. Object Pose Solution

Clearly, we need to compute the shape and color from previously ac- quired close by images .... nearest neighbour computation in two dimensions

(19)

Home Page

Title Page

JJ II

J I

Page7of65

Go Back

Full Screen

1. Object Pose Solution

Clearly, we need to compute the shape and color from previously ac- quired close by images .... nearest neighbour computation in two dimensions [Play Video]

(20)

Home Page

Title Page

JJ II

J I

Page8of65

Go Back

Full Screen

Close

View Interpolation via Visual Hull

Start

(21)

Home Page

Title Page

JJ II

J I

Page9of65

Go Back

Full Screen

The Visual Hull

Carve Carve again

(22)

Home Page

Title Page

JJ II

J I

Page10of65

Go Back

Full Screen

Close

2. Computer Vision In Action

Hull Compared to the real thing

(23)

Home Page

Title Page

JJ II

J I

Page11of65

Go Back

Full Screen

More details on the method

Question: Can we use the studio pictures ALSO for color computation?

(24)

Home Page

Title Page

JJ II

J I

Page12of65

Go Back

Full Screen

Close

Color Computation

Requires solution to: Given images of an object captured under a set of lighting conditions, how to efficiently render the scene under new illumination configurations?

(25)

Home Page

Title Page

JJ II

J I

Page13of65

Go Back

Full Screen

Color Computation

Requires solution to: Nearest Neighbors, and Bi-chromatic Nearest Neighbors

(26)

Home Page

Title Page

JJ II

J I

Page14of65

Go Back

Full Screen

Close

Output Frame

(27)

Home Page

Title Page

JJ II

J I

Page15of65

Go Back

Full Screen

3. kd-trees

• Dimension of data is k (but common to say k-d tree of dimension 3 instead of 3d-tree).

• kd-trees are binary trees

• Designed to handle spatial data in a simple way

• For n points, O(n) space, O(logn) height (if balanced), supports range and nearest-neighbor queries.

• Node consists of

– Two child pointers,

– Satellite information (such as name).

– A key: Either a single float representing a coordinate value, or a pair of floats (representing a dimension of a rectangle)

(28)

Home Page

Title Page

JJ II

J I

Page16of65

Go Back

Full Screen

Close

Basic Idea Behind kd-trees

Construct a binary tree

• At each step, choose one of the coordinate as a basis of dividing the rest of the points

• For example, at the root, choose x as the basis

– Like binary search trees, all items to the left of root will have the x-coordinate less than that of the root

– All items to the right of the root will have the x-coordinate greater than (or equal to) that of the root

• Choose y as the basis for discrimination for the root’s children

• And choose x again for the root’s grandchildren

Note: Equality (corresponding to right child) is significant

(29)

Home Page

Title Page

JJ II

J I

Page17of65

Go Back

Full Screen

Example: Construct kd-tree Given Points

• Coordinates of points are (35,90), (70,80), (10,75) (80,40), (50,90), (70,30), (90,60), (50,25), (25,10), (20,50), and (60,10)

• Points may be given one a time, or all at once.

• Data best visual- ized as shown below

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(30)

Home Page

Title Page

JJ II

J I

Page18of65

Go Back

Full Screen

Close

Example: kdtree Insertion

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90)

(60,10) (10,75)

(35,90)

(31)

Home Page

Title Page

JJ II

J I

Page19of65

Go Back

Full Screen

Nearest Neighbors: The scenario

• “Find the nearest Pizza Hut.” (Compare with the McDonald problem).

• Assume kd-tree T given, and C is the region associated with a node.

• Input p is a point

• Searching for point p in T helps

– In one dimension, T is very useful: the closest neighbor is from the set of nodes visited (MANY nodes are pruned)

– In higher dimensions, T is not as useful (the closest neighbor may be far away).

• Nevertheless, pruning is possible.

• General strategy: Collect partial results, judicial traversal, and prune.

(32)

Home Page

Title Page

JJ II

J I

Page20of65

Go Back

Full Screen

Close

What If We Locate Point?

00 11

00 11 00 11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(25,10)

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90)

(60,10) (10,75)

(35,90)

We visit (35,90) , (70,80), . . . , and fall off (70,30)

Closest point is nowhere near this path. We must visit both subtrees.

(33)

Home Page

Title Page

JJ II

J I

Page21of65

Go Back

Full Screen

Nearest Neighbor: Pruned version

• Maintain the rectangle r associated with a node

• Compute a lower bound on the distance from the query q to the rectangle

– Distance between q and any point in r is at least lowerbound(r, q)

– Do not compute all distances between q and every point in r

• lowerbound() helps because if the lower bound is larger than the distance computed so far, we do not consider many points

• Must compute lowerbound() quickly

(34)

Home Page

Title Page

JJ II

J I

Page22of65

Go Back

Full Screen

Close

Nearest Neighbor: Pruned Version

f l o a t lowerbound ( Rectangle r , P o i n t p ) {

i f ( r . i n s i d e ( p ) ) r e t u r n 0 ;

i f ( r . l e f t ( p ) ) r e t u r n r . minX − p . x ; . . .

}

R e s u l t process ( KDNode k , i n t cd , Rectangle r , R e s u l t r e s ) { i f ( k == n u l l ) r e t u r n r e s ;

i f ( lowerbound ( r , query ) >= r e s . d i s t a n c e ) r e t u r n r e s ; . . .

}

• If the lower bound is larger than the distance computed so far, exit!

• Otherwise compute the distance with the current node

• Process the two children in order!

(35)

Home Page

Title Page

JJ II

J I

Page23of65

Go Back

Full Screen

Pruned Version: Root (35,90)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(40,50))

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(36)

Home Page

Title Page

JJ II

J I

Page24of65

Go Back

Full Screen

Close

Pruned Version: (70,80)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(37)

Home Page

Title Page

JJ II

J I

Page25of65

Go Back

Full Screen

Pruned Version: (80,40)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(38)

Home Page

Title Page

JJ II

J I

Page26of65

Go Back

Full Screen

Close

Pruned Version: (70,30)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(39)

Home Page

Title Page

JJ II

J I

Page27of65

Go Back

Full Screen

Pruned Version: (50,25)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(40)

Home Page

Title Page

JJ II

J I

Page28of65

Go Back

Full Screen

Close

Pruned Version: (60,10)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90)

(60,10) (10,75)

(35,90)

(41)

Home Page

Title Page

JJ II

J I

Page29of65

Go Back

Full Screen

Pruned Version: (10,75)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(42)

Home Page

Title Page

JJ II

J I

Page30of65

Go Back

Full Screen

Close

Pruned Version: (25,10)

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(43)

Home Page

Title Page

JJ II

J I

Page31of65

Go Back

Full Screen

Pruned Version: Answer

00 11

00 11 00

11

00 11

00 11 00

11

00 11

(10,75)

(20,50)

(25,10)

(70,30)

(35,90) (50,90)

(70,80)

(60,10) (50,25)

(80,40) (90,60)

(70,80)

(80,40)

(70,30) (20,50)

(25,10)

(90,60) (50,90) (10,75)

(35,90)

(44)

Home Page

Title Page

JJ II

J I

Page32of65

Go Back

Full Screen

Close

Which Nodes Are Processed?

(70,80)

(80,40)

(70,30)

(50,25) (20,50)

(25,10)

(90,60)

(50,90)

(60,10) (10,75)

(35,90)

(45)

Home Page

Title Page

JJ II

J I

Page33of65

Go Back

Full Screen

Any Improvement Possible?

• Nine nodes examined. Can we do better?

• Yes, if decision to pick a node is based on dynamic changing costs instead of initial left-right decision.

• Use a priority queue. (Seven nodes examined instead of nine)

(46)

Home Page

Title Page

JJ II

J I

Page34of65

Go Back

Full Screen

Close

Talk Overview

4 Background about this talk 4 Application in Vision

• Exhibit A: kd-trees ß Application in Imaging

• Exhibit B: Octrees ß Application in Graphics

(47)

Home Page

Title Page

JJ II

J I

Page35of65

Go Back

Full Screen

4. Color Quantization

• By “quantization,” here we mean the process of changing the given N number of colors to K colors. In the picture below, an image with N=33694 colors is changed to one with K=64 colors.

(48)

Home Page

Title Page

JJ II

J I

Page35of65

Go Back

Full Screen

Close

4. Color Quantization

• Why? Lightweight; thus easy to transmit, store, share

(49)

Home Page

Title Page

JJ II

J I

Page35of65

Go Back

Full Screen

4. Color Quantization

• Mechanics? Create as output a lookup table

• Can be done in any color space

(50)

Home Page

Title Page

JJ II

J I

Page35of65

Go Back

Full Screen

Close

4. Color Quantization

• Mechanics? Create as output a lookup table

• Can be done in any color space

• Basic challenge: Efficient implementation of reverse lookup table,

(51)

Home Page

Title Page

JJ II

J I

Page36of65

Go Back

Full Screen

Digression: Web Safe Colors

• 216 colors have been ac- cepted as “safe” to display.

Some of these colors are gray

• Each channel can take only values 00, 33, 66, 99, CC, and FF

• Figures shows the colors organized in descending RGB values. Value at top left is FFFFFF; first item in the second row has the value FFCCFF

(52)

Home Page

Title Page

JJ II

J I

Page37of65

Go Back

Full Screen

Close

Uniform Quantization

• First find the maximum and minimum range and allo- cate numbers R, G, and B such that R*G*B<=K

• Uniformly divide the range.

For example, the range [r_min,r_max] is divided into R parts.

• Map these R values to ac- tual colors. For example, if R=4, then we might chose 1, 2, 4 and 8

(53)

Home Page

Title Page

JJ II

J I

Page37of65

Go Back

Full Screen

Uniform Quantization

• Advantages:

(54)

Home Page

Title Page

JJ II

J I

Page37of65

Go Back

Full Screen

Close

Uniform Quantization

• Advantages: Easy to implement

• Drawbacks:

(55)

Home Page

Title Page

JJ II

J I

Page37of65

Go Back

Full Screen

Uniform Quantization

• Advantages: Easy to implement

• Drawbacks: Distribution of colors is ignored resulting in banding

(56)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Close

Popularity Algorithm

• Multi-pass algorithm

(57)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Popularity Algorithm

• Count number of cells having a particular set of color, and take the top K colors

(58)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Close

Popularity Algorithm

• But first quantize the colors (2³²→ 2¹⁵)

(59)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Popularity Algorithm

• Second pass: For each pixel, find the “closest” color

(60)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Close

Popularity Algorithm

• Advantages:

(61)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Popularity Algorithm

• Advantages: Easy to implement, popular colors show up in the resulting image

(62)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Close

Popularity Algorithm

• Disadvantages:

(63)

Home Page

Title Page

JJ II

J I

Page38of65

Go Back

Full Screen

Popularity Algorithm

• Disadvantages: Expensive; clusters of ‘unpopular’ but significant colors are ignored

(64)

Home Page

Title Page

JJ II

J I

Page39of65

Go Back

Full Screen

Close

Median-Cut Algorithm

• Goal: Adaptively subdivide color block into K parts so that each sub-block has the same number of colors