mit.eduLecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01wLecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '01Lecture 3 --- 6.837 Fall '016.837 LECTURE 31.Topics in Imaging2. No Slide3. No Slide 4. No Slide5.Area Fill Algorithms?6.Parity Fill7.Winding Number8.Boundary Fills9.Let's Watch it in Action10.Serial Recursion is Depth-First11.At Full Speed12.A Flood-Fill13.Flood-Fill in Action14.Self-Starting Fast Flood-Fill Algorithm15.Fill East16.Working Algorithm17.4-Way adn 8-Way Connectedness18.Code for an 8-Way Connected Flood Fill19.More 8-Way Connectedness20.Flood-Fill Embellishments21.Monochrome and Color Dithering21a.Classical Halftoning21b.Halftoning with Pixel Patterns22.When do we need dithering?23.Quantization and Thresholding24.The Secret... Noise25.Dither Noise Patterns26.Ordered Dither27.Error Diffusion28.Lossy Image Compression29.LZW Compression29a.LZW Compression30.Transform Coding31.DCT example31aDCT examples31b.DCT examples31c.DCT examples31d.DCT examples32.Next Time Lecture 3 Outline 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/index.html [9/13/2001 6:42:31 PM]Topics in ImagingA wee bit ofrecursionFilling AlgorithmsDitheringDCTs Lecture 3 Slide 1 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide01.html [9/13/2001 6:43:15 PM]Area Fill Algorithms?Used to fill regions after their boundary or contour has beendetermined.● Handles Irregular boundaries ● Supports freehand drawings● Deferred fills for speed (only fill visible parts)● Allows us to recolor primitives● Can be adapted for other uses (selecting regions) ● Unaware of any other primitivespreviously drawn.● Later we'll discuss filling areasduring rasterization● Lecture 3 Slide 5 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide05.html [9/13/2001 6:43:19 PM]Parity FillProblem:For each pixel determine if it is inside or outside of a given polygon.Approach:from the point being tested cast a ray in an arbitary direction● if the number of crossings is odd then the point is inside● if the number of crossings is even then the point is outside● Very fragile algorithm● What if ray crosses a vertex?● What if ray falls on an edge?● Commonly used in ECAD● Suitable for H/W● Lecture 3 Slide 6 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide06.html [9/13/2001 6:43:21 PM]Winding NumberImagine yourself watching a point traverse the boundary of the polygon in acounter-clockwise direction and pivoting so that you are always facing at it.Your winding number is the number of full revolutions that you complete.If you winding number is 0 then you are outside of the polygon, otherwise you are inside.Lecture 3 Slide 7 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide07.html [9/13/2001 6:43:28 PM]Boundary FillsBoundary fills start from a point known to be inside of a regionand fill the region until a boundry is found.A simple recursive algorithm can be used: public void boundaryFill(int x, int y, int fill, intboundary) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; int current = raster.getPixel(x, y); if ((current != boundary) && (current != fill)) { raster.setPixel(fill, x, y); boundaryFill(x+1, y, fill, boundary); boundaryFill(x, y+1, fill, boundary); boundaryFill(x-1, y, fill, boundary); boundaryFill(x, y-1, fill, boundary); } } Lecture 3 Slide 8 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide08.html [9/13/2001 6:43:30 PM]Let's Watch it in ActionFirst, you should guess how you expect the algorithm to behave. Thenselect a point on the figure's interior. Did the algorithm act as youexpected?Lecture 3 Slide 9 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide09.html [9/13/2001 6:43:32 PM]Serial Recursion is Depth-FirstSo the fill algorithm will continuein one direction until a boundary isreached.It will then change directionsmomentarily and attempt tocontinue back in the originaldirection.Will parallel execution of thealgorithm behave the same way?Lecture 3 Slide 10 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide10.html [9/13/2001 6:43:35 PM]At Full SpeedTo the right is the same algorithm operating at full speed.Left-button click inside one of the regions to start the fill process. Click the right button toreset the image to its original stateLecture 3 Slide 11 6.837 Fall '01Lecture 3 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture03/Slide11.html [9/13/2001 6:43:37 PM]A Flood-FillSometimes we'd like a area fill algorithm that replaces all connected pixels of a selectedcolor with a fill color. The flood-fill algorithm does exactly that. public void floodFill(int x, int y, int fill, intold) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; if (raster.getPixel(x, y) == old) { raster.setPixel(fill, x, y);
View Full Document
Unlocking...