GRAFIKA, PRZETWARZANIE I ROZPOZNAWANIE OBRAZÓW Przetwarzanie obrazów Obraz Katedra Technik Programowania Rys. p. 420 WETI tel. (347-)20-96 Grafika Rozpoznawanie obrazów przetwarzaniem obrazów i Opis rozpoznawaniem obrazów. GRAFIKA KOMPUTEROWA " " Obrazowanie schematów " " GRAFIKA KOMPUTEROWA " " " S " Synteza obrazów realistycznych " Wizualizacja modelowanych zjawisk " Animacja " Plastyka LITERATURA: PRZETWARZANIE OBRAZÓW 1. R. A. Earnshaw (ed.): Fundamental Algorithms for Computer " Dyskretyzacja obrazów Graphics. Springer, Berlin 1985. " Polepszanie jako 2. J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, R. L. Phillips: " Urealnianie obrazów Wprowadzenie do grafiki komputerowej. WNT, Warszawa 1995. " Rekonstrukcja obrazów 3. J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes: Computer Graphics: " Kompresja obrazów Principles and Practice, Second Edition. Addison-Wesley, Reading 1990. " 4. G. Hgron: SynthŁse d image: algorithmes lmentaires. Dunod " informatique, Paris 1985. 5. M. Jankowski: Elementy grafiki komputerowej. WNT, Warszawa 1990. ROZPOZNAWANIE OBRAZÓW 6. T. Pavlidis: Grafika i przetwarzanie obrazów. WNT, Warszawa 1987. " Opis obiektów 7. J. Zabrodzki (red.): Grafika komputerowa, metody i narz dzia. WNT, " Klasyfikacja obiektów Warszawa 1994. " Porównywanie obrazów Gda sk 2000 " Analiza struktury 2 BARWA (KOLOR) SPOSOBY PREZENTACJI OBRAZÓW W GRAFICE KOMPUTEROWEJ: "(380,780) nm. " GRAFIKA RASTROWA " Dwa rodzaje receptorów w ludzkim oku: Tworzenie obrazu polega na wyznaczeniu kolorów poszczególnych pikseli " i naniesieniu tych kolorów w odpowiednich miejscach poleceniem write(c). barwnych - widzenie skotopowe (nocne); " czopki Sposoby reprezentacji obrazów: barwy - widzenie fotopowe (dzienne). " tablice (mapy bitowe) type Image = array [0..mx,0..my] of Color " Teoria Younga - Helmholtza " drzewa czwórkowe " drzewa binarne Kompresja: " (), " metody bez utraty informacji: " ł(), " " metody arytmetyczne " (). " " bezstratne metody kompresji danych graficznych, run length encoding RLE) " " Zjawisko metameryzmu " " metody transformat, np. JPEG (ang. Joint Photographic Experts Group) " metody fraktalne " Modele syntezy barw: Formy danych obrazowych: " model RGB ang. red + green + blue - czerwony + zielony + niebieski, " obrazy kolorowe type Color = record red, green, blue: integer end synteza addytywna, stosowany w monitorach kolorowych; " obrazy szare (wielopoziomowe) type Color = integer " type Color = Boolean " modele CMY i CMYK ang. cyan + magenta + yellow (+ black) - " GRAFIKA WEKTOROWA synteza subtraktywna, stosowane w poligrafii; " modele YUV, YIQ i YCbCr - luminancja + dwie chrominancje, Tworzenie obrazu polega na narysowaniu poszczególnych obiektów plot(x,y,c), vector(x1,y1,x2,y2,c). " modele HSV i HLS ang. hue + saturation + value (lightness) - hue hue: red yellow green cyan blue magenta Sposoby reprezentacji obrazów: 0 60 120 180 240 300 " zbiór linii type Image = list of Line Formy danych obrazowych: " model CIE XYZ (franc. Commission Internationale de l'Eclairage), " type Line = record x,y:integer; c:Color; chain: list of 0..7 end " modele CIE LUV i CIE LAB - inne modele teoretyczne CIE; " type Line = list of record x,y:integer; c:Color end " model TekHVC - model teoretyczny opracowany w firmie Tektronix, 3 4 " Metody falkowe Metody kompresji danych graficznych przepustowy L " (ang. run length encoding RLE) i lustrzany do niego filtr górnoprzepustowy H. 1+, 1 , 1|, 2+, 2 , 2|, ..., n+, n , n|, In. Kompresja polega tu na skwantowaniu kolorów pikseli obrazów " Metody transformat i+1+ H 2:1 f& Umm o rozmiarze mm (dla JPEG: m=8). H 2:1 f& Wykonanie zadanej transformacji T na poszczególnych blokach Umm: i+1 L 2:1 Vmm=TUmm (dla JPEG: DCT). Ii f& Dokonanie kwantyzacji K wyników transformacji Vmm: i+1| H 2:1 Wmm=KVmm (dla JPEG: wi,j = [vi,j / qi,j ], gdzie wi,j, vi,j, qi,j L 2:1 wiersze elementami macierzy Wmm, Vmm i Qmm, przy czym Qmm jest L 2:1 Ii+1 kolumny " Metody fraktalne f& Linearyzacja skwantowanych wyników transformacji Wmm (dla JPEG: metoda ZIGZAG). Fraktalem f& JPEG: metoda Huffmana). Rys. Kompr iterated function system). f& Dekompresja skwantowanych wyników transformacji Wmm f& ków transformacji Vmm na podstawie " iterated function system) skwantowanych wyników transformacji Wmm (dla JPEG: vi,j = wi,j qi,j, gdzie vi,j, wi,j, qi,j Vmm, " partitioned iterated function system) Wmm i Qmm, przy czym Qmm f& Wykonanie zadanej transformacji odwrotnej T-1 na poszczególnych Vmm: Umm=T-1Vmm (dla b) a) JPEG: odwrotna DCT). x' = 0.85 x + 0.04 y + 0 y' = 0.04 x + 0.85 y + 1.6 16 11 10 16 24 40 51 61 17 18 24 47 66 99 99 99 12 12 14 19 26 58 60 55 18 21 26 66 99 99 99 99 x' = 0.2 x 0.26 y + 0 14 13 16 24 40 57 69 56 24 26 56 99 99 99 99 99 y' = 0.23 x + 0.22 y + 1.6 14 17 22 29 51 87 80 62 47 69 99 99 99 99 99 99 18 22 37 56 68 109 103 77 99 99 99 99 99 99 99 99 24 35 55 64 81 104 113 92 99 99 99 99 99 99 99 99 x' = 0.15 x + 0.28 y + 0 49 64 78 87 103 121 120 101 99 99 99 99 99 99 99 99 y' = 0.26 x + 0.24 y + 0.44 72 92 95 98 112 100 103 99 99 99 99 99 99 99 99 99 Rys. Macierze kwantyzacji Q88 x' = 0 x + 0 y + 0 y' = 0 x + 0.16 y + 0 dla luminancji i dla chrominancji. Rys. Linearyzacja metod m=8). 5 6 Dyskretyzacja obrazów rzeczywistych GEOMETRIA DYSKRETNA " Próbkowanie - wybór dyskretnej siatki (rastra) do przedstawienia obrazu. piksela piksela piksela " P P P " piksela piksel P piksela ą &! P P i kwadratowej siatki próbkowania (rastra) o boku h: P. ł "k Q1,r " &! P "Fr k Q1, r ( ) ( )ł piksela piksela piksela ł ł "r > ąh "P "Fr &! ł & ł , P P P ł ł ( ) ( ) ł"k Q2 ,r " &!2 P "Fr k Q2 ,r łł gdzie " Fr &! - brzeg obszaru &!, Fr &! = &! )" &!2 , wspólny bok. &! &!, &! = &! *" Fr &!, " &!2 &!, &!2 = {P "&!} , " k Q, r Q i o promieniu r. ( ) Definicje linii: Stwierdzenie 1: " P1, P2, ..., Pn "k"{1, 2, .., n-1} piksele &! i kwadratowa siatka próbkowania (raster) o boku h Pk i Pk+1 " P1, P2, ..., Pn "k"{1, 2, .., n-1} 2 ą= , wówczas próbkowanie piksele Pk i Pk+1 2 " " Stwierdzenie 2: " &! i kwadratowa siatka próbkowania (raster) o boku h 10 ą= , wówczas próbkowanie Definicje konturu: 2 " B-konturem danego zbioru pikseli nazywamy zbiór wszystkich pikseli " Konturem (n-konturem) danego zbioru pikseli nazywamy zbiór " Kwantowanie - odwzorowanie kolorów w zbiór dyskretny. dobra 256 64 " Zbiór pikseli jest spójny (n-spójny) obrazy szare 8 b/piksel 6 b/piksel obrazy kolorowe 24 b/piksel 18 b/piksel " Zbiór pikseli jest b-spójny , ang. dither 7 8 Krzywe dyskretne Odcinek dyskretny " " " tnej: " " Definicja odcinka: " " Odcinkiem P1 P2 a) d)
b)
" c) (0, 1, 2, ...). " Rys. " a) w tym drugim odcinku. b) c) krzywa, w której dla dwóch dowolnych pikse , druga bez); a) b) c) E d) A e) Ć d) E E A E Ć ce je. A E A E A E A E Ć A E A E A E A E A E Metody rysowania krzywych dyskretnych: A E A E Ć Ć Ć " numeryczne A E Ć Ć A E Ć E A E A E A Ć A " podstawowe, parametryczne. E A E A E A Ć A " y = f(x) lub paramet- E A E A A E A rycznych x = x(t), y = y(t) wykorzystywanych w geometrii euklidesowej, E A A A Ć " A A A E A " A A A E A " warunkowe A A A E A " kowego (ang. midpoint), porównawcze Jordana. A A A A " F(x, y) = 0 stosowanego do opisu krzywej w geometrii euklidesowej, " " A i E A i E " strukturalne A i E " run length slice). A i E nie jest spójna; " e) odcinek E A " " 9 10 Algorytmy rysowania odcinków: Algorytm podstawowy " numeryczne " y = m * x + b m b - wyraz wolny " dwa przypadki: " podstawowy m | > 1 m =1 | " DDA - Digital Differential Analyser) ą " warunkowe m | < 1 m | < 1 | | ą rysowanego " Bresenhama m. m | > 1 m = -1 | " midpoint) " porównawczy Jordana " lokrokowy) Gilla " |m| > 1 zamiast równania y = m * x + b " strukturalne x = m' * y + b', 1 b gdzie m' = , b' = - , przy czym wówczas |m'| d" 1, m m " Metzgera-Bronsa " . run length slice) ye - ys " |m| d" 1 xe `" xs, m = , b = ys - m * xs. xe - xs (ang. antialiasing): " numeryczne nie omawiane tutaj parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. " warunkowe zmienne procedury: m, b:real; inc, dx, dy:integer; dx := xe-x; dy := ye-y; " z upr dla |dx| e" |dy| (czyli |m| d" 1): " Wu m := dy/dx " b := y-m*x; inc := sgn(dx); while x `" xe do begin Oznaczenia: (xs , ys xe , ye) - koniec odcinka. plot(x, y); x := x+inc; y := round(m*x+b) end; plot(xe,ye) 11 12 DDA - Digital Differential Analyser) Algorytm Bresenhama Ą " 0X ą " [0, ]. 4 " dla |m|d" x o ą1 ! y o ąm. ą 1 " dla |m y o ą1 ! x o ą . albo . m Rys. Kryterium wyboru kolejnego piksela dla d odcinek 2 idealny " d1>d2 ! rysowany " y m = górny piksel kandydat, d 1 Rys. Dla |m|d"1 Zmiana " d1 x o 1 dolny piksel kandydat, " x=1 " d1=d2 ! rysowany y o m ostatnio dwa dowolny z pikseli narysowany piksele kandydatów. piksel kandydaci " xi, yi. parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. zmienne procedury: z, zinc:real; inc, dx, dy:integer; dx := xe-x; dy := ye-y; xi+1:= xi +1 przy wyborze dowolnego z pikseli kandydatów, dla |dx| e" |dy| (czyli |m| d" 1): ńły +1 przy wyborze górnego piksela kandydata, yi + 1:= ł i z := y; yi przy wyborze dolnego piksela kandydata. ół inc := sgn(dx); zinc := dy/|dx " Wynik porównania d1>d2 decyduje o wyborze kolejnego piksela while x `" xe do do rysowania: d1 = y-yi = m*(xi+1)+b-yi. begin d2 = (yi+1)-y = (yi+1)-m*(xi+1)-b. plot(x, y); x := x+inc; " d1>d2 d1-d2. z := z+zinc; y := round(z) d1-d2 = 2*m*(xi+1)+2*b-2*yi-1. end; Ą " 0X ą " [0, ] plot(xe,ye) 4 "x = xe-xs d1-d2) = sgn("x*(d1-d2)). " Oznaczenie: pi = "x*(d1-d2) = b = ys-m*xs = 2*"x*m*(xi+1)+2*"x*b-2*"x*yi-"x = "y = "x*m = 2*"x*m*(xi+1)+2*"x*ys-2*"x*m*xs-2*"x*yi-"x = = 2*"y*(xi+1)+2*"x*ys-2*"y*xs-2*"x*yi-"x. pi jest zawsze . 13 14 " d1>d2 ! d1-d2>0 ! pi>0 ! wybór górnego piksela kandydata, midpoint) Ą d1" 0X ą " [0, ]. 4 d1=d2 ! d1-d2=0 ! pi=0 ! wybór dowolnego piksela kandydata, ą w algorytmie przyj albo . " pi: x0=xs, y0=ys p0 = 2*"y*(x0+1)+2*"x*ys-2*"y*xs-2*"x*y0-"x = = 2*"y*xs+2*"y+2*"x*ys-2*"y*xs-2*"x*ys-"x = Rys. Kryterium wyboru kolejnego odcinek = 2*"y-"x. idealny przypadku: o wyborze kolejnego piksela " Modyfikacja warto pi: xi+1-xi = 1 funkcji F(x,y)= a*x+b*y+c pi+1-pi = 2*"y*(xi+1-xi)-2*"x*(yi+1-yi) = yi+1-yi " {0,1} = 2*"y-2*"x*(yi+1-yi) = = ostatnio dwa narysowany piksele ńł2 * ("y - "x) pi e" 0 (yi - yi = 1), +1 piksel kandydaci ł2 * "ypi < 0 (yi + 1 - yi = 0). kandydatami. ół " xi, yi. xi+1:= xi +1 przy wyborze dowolnego z pikseli kandydatów, parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. ńłyi +1 przy wyborze górnego piksela kandydata, yi + 1:= ł yi przy wyborze dolnego piksela kandydata. zmienne procedury: p, pinc, pdec, dx, dy:integer; dx := xe-x; dy := ye-y; ół dla dx e" dy e" 0: p := 2*dy-dx; " Równanie ogólne prostej: F(x,y)=0, gdzie F(x,y)=a*x+b*y+c. pinc := 2*dy; -c * (y - y ) -c * (x - x ) pdec := 2*(dy-dx); Dla dwóch punktów prostej: a = , b = . x * y - x * y x * y - x * y while x `" xe do begin c = xe*ys - xs*ye a = ye - ys, b = -(xe - xs). plot(x, y); a, b, c . x := x+1; if p < 0 then p := p+pinc " xs , ys) i jego koniec (xe , ye else begin y := y+1; p := p+pdec end F(x,y end; plot(xe,ye) F(x0,y0) = F(xs,ys) = 0 oraz F(xe,ye) = 0. 1 1 " Oznaczenie: fi := [F(xi+1, yi+ )] = [a*(xi+1) + b*(yi+ ) + c] = 2 2 b b = a*xi + b*yi + c + a + [ ] = F(xi,yi) + a + [ ]. 2 2 fi jest zawsze . 15 16 1 Algorytm porównawczy Jordana " F(xi+1,yi+ ) > 0 ! fi e" 0 ! wybór górnego piksela kandydata, Ą 2 " Za 0X ą " [0, ]. 1 2 F(xi+1,yi+ ) < 0 ! fi < 0 ! wybór dolnego piksela kandydata, ą 2 , albo . 1 F(xi+1,yi+ ) = 0 ! wybór dowolnego piksela kandydata, 2 przyj fi = 0. odcinek idealny " fi: b x0=xs, y0=ys f0 = F(x0,y0) + a + [ ] = Rys. Kryterium wyboru 2 kolejnego piksela dla b = F(xs,ys) + a + [ ] = F(x0,y0) = F(xs,ys) = 0 2 ostatnio trzy rysowany jest ten piksel, b narysowany piksele = a + [ ]. piksel kandydaci 2 " xi, yi. " fi: fi+1-fi = F(xi+1,yi+1) - F(xi,yi) = 1. xi+1:= xi +1 = a*(xi+1-xi) + b*(yi+1-yi) = xi+1-xi = 1 przy wyborze prawego piksela kandydata, yi+1:= yi = a + b*(yi+1-yi) = yi+1-yi " {0,1} 2. xi+1:= xi przy wyborze górnego piksela kandydata, ńła b fi e" 0 (yi - yi = 1), +1 = yi+1:= yi +1 łafi < 0 (yi +1 - yi = 0). ół 3. xi+1:= xi +1 przy wyborze prawego górnego piksela kandydata. yi+1:= yi +1 " Równanie ogólne prostej: F(x,y)=0, gdzie F(x,y)=a*x+b*y+c. parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. -c * (y - y ) -c * (x - x ) Dla dwóch punktów prostej: a = , b = . x * y - x * y x * y - x * y zmienne procedury: f, df, dx, dy:integer; dx := xe-x; dy := ye-y; Przyjmuj c = - (xe*ys - xs*ye b = xe - xs, a = -(ye - ys). dla dx e" dy e" 0: df := dy-dx; a, b, c . f := df+(dx div 2); { f := dy-((dx+1) div 2);} while x `" xe do begin " Oznaczenia: f := F(xi,yi), F(x0,y0) = F(xs,ys) = 0, plot(x, y); x := x+1; f1 := F(xi+1,yi) = f+a, if f < 0 then f := f+dy f2 := F(xi,yi+1) = f+b, else begin y := y+1; f := f+df end f3 := F(xi+1,yi+1) = f+a+b. end; plot(xe,ye) 17 18 " |f1|<|f2| & |f1|<|f3| ! wybór prawego piksela kandydata, |f2|<|f1| & |f2|<|f3| ! wybór górnego piksela kandydata, " |f3|<|f1| & |f3|<|f2| ! wybór prawego górnego piksela kandydata, 1 |f1|<|f2| & |f1|=|f3| ! wybór prawego lub prawego górnego piksela, " 0X ą " (0, arctg ]. |f2|<|f1| & |f2|=|f3| ! wybór górnego lub prawego górnego piksela, 4 ą " f2 e" f3 e" f1 |f1|<|f2| & |f1|<|f3| ! |f1|<|f3| ! wybór prawego piksela kandydata, |f2|<|f1| & |f2|<|f3| ! |f2|<|f3| ! wybór górnego piksela kandydata, 0 0 0 0 0 0 0 1 0 0 1 0 parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. zmienne procedury: f1, f2, f3, dx, dy:integer; dx := xe-x; dy := ye-y; 0 1 0 0 1 0 0 0 dla dx e" 0 & dy e" 0: f1 := -dy; " while (x `" xe) or (y `" ye) do begin 0000 0001 0010 0100 1000 plot(x, y); pi<0 pi<0 pi<0 pi<0 pie"0 f3 := f1+dx; f2 := f3+dy; pi+2"y<0 pi+2"y<0 pi+2"y<0 pi+2"ye"0 pi+2"y-2"x<0 if |f1| < |f3| then begin x := x+1; f1 := f1-dy end pi+4"y<0 pi+4"y<0 pi+4"ye"0 pi+4"y-2"x<0 pi+4"y-2"x<0 else if |f2| < |f3| then begin y := y+1; f1 := f2-dy end pi+6"y<0 pi+6"ye"0 pi+6"y-2"x<0 pi+6"y-2"x<0 pi+6"y-2"x<0 else begin x := x+1; y := y+1; f1 := f3-dy end end; plot(xe,ye) 0000 0001 0010 0100 1000 pi < -6"y d" pi < -4"y d" pi < -2"y d" pi < d" pi 0 " f2 e" f3 e" f1 |f1|<|f3| ! -f1" pi |f2|<|f3| ! f2<-f3 ! wybór górnego piksela kandydata, pi <-6 * "y ńł8 * "y pi+4 - pi = ł8 * "y - 2 * "x pi e"-6 * "y ół parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. " zmienne procedury: f1, f2, f3, dx, dy:integer; dx := xe-x; dy := ye-y; dla dx e" 0 & dy e" 0: f1 := -dy; 0000 0001 0010 0100 1000 while (x `" xe) or (y `" ye) do 0000 0000 0000 0000 0000 begin 1000 0001 0001 0010 0100 plot(x, y); 0100 0010 0100 1000 f3 := f1+dx; f2 := f3+dy; 0010 0001 0010 if f3 < -f1 then begin y := y+1; f1 := f3 end; 0001 0001 if -f3 < f2 then begin x := x+1; f1 := f1-dy end end; plot(xe,ye) 19 20 parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. Algorytm strukturalny Metzgera-Bronsa zmienne procedury: p, pinc, pdec, dx, dy, m2, m4, m6, xe2:integer; dla dx e" 4*dy e" 0: dx := xe-x; dy := ye-y; p := 2*dy-dx; pinc := 8*dy; pdec := 8*dy-2*dx; 3 2 1 kodowany jako cyfra ósemkowa m2 := -2*dy; m4 := -4*dy; m6 := -6*dy; xe2 := xe-2; while x < xe2 do {rysowanie (dx+1) div 4 czwórek} jakim jest ten piksel dla begin 4 0 poprzedzajacego go piksela. if p < m6 then {0000} begin plot(x, y); plot(x+1, y); plot(x+2, y); plot(x+3, y); 5 6 7 p := p+pinc ósemkowych zwanego kodem end else begin 3 if p < m2 then 1 Rys. if p < m4 then {0001} 1 2 0170213 begin plot(x, y); plot(x+1, y); 0 7 0 plot(x+2, y); plot(x+3, y); y := y+1 end " else {0010} begin plot(x, y); plot(x+1, y); " plot(x+2, y); y := y+1; plot(x+3, y) end " else if p < 0 then {0100} begin plot(x, y); plot(x+1, y); y := y+1; plot(x+2, y); plot(x+3, y) " end Ą else {1000} " 0X ą " [0, ]. begin plot(x, y); y := y+1; plot(x+1, y); 4 plot(x+2, y); plot(x+3, y) ą end; albo p := p+pdec end; x := x+4 end; "y jedynek i "x-"y zer ("y = ye-ys, "x = xe-xs). if x d" xe then {rysowanie (dx+1) mod 4 pikseli} begin if x < xe then " Oznaczenia: begin if x d" xe2 then łu łł łułł łułł łu łł h1(u) = , (u) = u - lub = u - , (u) = . 2 1(u) ł2śł 2 begin plot(x, y); x := x+1; ł2śł ł2śł ł2śł ł ł ł ł ł ł ł ł if p e" 0 then y := y+1 end; " Podstawienie warto i := 0, plot(x,y) a0 := "y, A0 := "1", end; b0 := "x-"y, B0 := "0". plot(xe,ye) end 21 22 " ai Ai z bi Bi. parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. zmienne procedury: A, B:string; w:Boolean; a, b, dx, dy:integer; dx := xe-x; " Podstawienie: dy := ye-y; ci := max(ai,bi), ci=ai ! Ci := Ai, Di := Bi, dla dx e" dy e" 0: a := dy; b := dx-dy; A := "1"; B := "0"; di := min(ai,bi), ci`"ai ! Ci := Bi, Di := Ai, w := false; {true} ci e" di. ci while a `" 0 do " Di ri = Ci (rie"1). begin di while a < b do )D (ri ) łC łdi begin " ri ! 1(ri . ł ł i iCi ł łł if w then A := A+B else A := B+A; w := not w; b := b-a " ri end; ai+1 := ci mod di Ai+1:= Cih1([ri ]+1)DiCih2([ri ]+1) i repeat bi+1 := di - (ci mod di Bi+1:= Cih1([ri ])DiCih2([ri ]). if w then B := A+B else B := B+A; w := not w; i := i+1. a := a-b until a < b end; for i := 1 to b do parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. for j := 1 to length(B) do zmienne procedury: A, B:string; w:Boolean; a, b, dx, dy:integer; dx := xe-x; begin dy := ye-y; dla dx e" dy e" 0: plot(x,y); a := dy; b := dx-dy; A := "1"; B := "0"; x := x+1; if B[j] = '1' then y := y+1 end; while a `" 0 do plot(xe,ye) begin w := false; {true} if a < b then begin swap(a,b); swap(A,B) end; repeat if w then B := A+B else B := B+A; w := not w; a := a-b until a < b; if w then A := A+B else A := B+A; b := b-a end; for i := 1 to b do for j := 1 to length(B) do begin plot(x,y); x := x+1; if B[j] = '1' then y := y+1 end; plot(xe,ye) 23 24 parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. (ang. run length slice) zmienne procedury: a, b, a2, ba2M, ba2D, l, i, j, dx, dy:integer; dx := xe-x; 1 dy := ye-y; dla dx e" 2*dy > 0: " 0X " (0, arctg ]. 2 a := dy; b := dx-dy; l := a; a2 := a+a; ba2M := b mod a2; ba2D := b div a2; albo plot(x,y); for i := 1 to a do begin for j := 1 to ba2D do begin x := x+1; plot(x,y) end; l := l+ba2M; if l e" a2 then begin l := l-a2; x := x+1; plot(x,y) end; = "y jedynek i ą = "x-"y zer ("y = ye-ys, "x = xe-xs). x := x+1; y := y+1; plot(x,y);
for j := 1 to ba2D do begin x := x+1; plot(x,y) end; " 0ą2i-1 1 0ą2i , " l := l+ba2M; i=1 if l e" a2 then begin l := l-a2; x := x+1; plot(x,y) end 2 gdzie = ą, Ai = A1... An , An = AA...A end "ą j " j=1 i =1 n ąi ąi ą ą parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. = ą div (2) lub +1 = ą div (2)+1, przy czym 2 2 zmienne procedury: a, b, a2, baD, baM2, ba2M, ba2D, l, i, j, dx, dy:integer; dla dx e" 2*dy > 0: dx := xe-x; dy := ye-y; j-1 ł łą j-1 a := dy; b := dx-dy; l := a; ą ą = roundł 2 j - ł ą = j - 2 + ł div (2). lub ł ł ł "ąk "ąk j j ł łł ł łł a2 := a+a; ba2M := b mod a2; ba2D := b div a2; k =1 k=1 baD := ba2D+ba2D; baM2 := ba2M+ba2M; if ba2M > a " then begin baD := baD+1; baM2 := baM2-a2 end;
plot(x,y); 0ą2i-1 1 0ą2i , gdzie Ai = A1... An , An = AA...A , " " i=1 i=1 n for j := 1 to ba2D do begin x := x+1; plot(x,y) end; l := l+ba2M; if l e" a2 then begin l := l-a2; x := x+1; plot(x,y) end; ńł ą div (2)dla j + ą mod (2) < 2, ąj = ł x := x+1; y := y+1; plot(x,y); ół ą div (2) +1 dla j + ą mod (2) e" 2, for i := 2 to a do begin j = (ą(j-1) +) mod (2), for j := 1 to baD do begin x := x+1; plot(x,y) end; czyli 1 = , l := l+baM2; ńł j + ą mod (2)dla j + ą mod (2) < 2, if l e" a2 then begin l := l-a2; x := x+1; plot(x,y) end; j+1 = ł x := x+1; y := y+1; plot(x,y); ół j + ą mod (2) - 2 dla j + ą mod (2) e" 2, end; for j := 1 to ba2D do begin x := x+1; plot(x,y) end; if l+ba2M e" a2 then begin x := x+1; plot(x,y) end 25 26 odcinków dyskretnych (ang. aliasing) antialiasing) " bezwagowe próbkowanie powierzchni Rys. Bezwagowe próbkowanie powierzchni odpowiada Metody usuwania odcinków " " wagowe próbkowanie powierzchni " antialiasing) Rys. Model odcinka antialiased). 27 28 antialiasing) antialiasing) Ą Ą " 0X ą " [0, ]. " 0X ą " [0, ]. 4 4 Piksele rysowane parami w pionie. Piksele rysowane parami w pionie. m " " xi, yi. xi Rys. Kryterium wyboru kolejnych pikseli: xi+1:= xi +1 " k>0 ! kolejne dwa piksele yi ńły +1 dla [a(i+1)] > [ai], gdzie a = tgą, odcinek rysowane w tych samych ki yi + 1:= ł i idealny wierszach (yi, yi-1), yi dla [a(i+1)] = [ai]. ół " k<0 ! kolejne dwa piksele rysowane w wierszach o " a(i+1)-[a(i+1)], yi+1, yi), a(i+1)+[a(i+1)]. " k=0 ! kolejny piksel (tylko " x, y, c, cmax jeden) rysowany ostatnio trzy piksele narysowane kandydaci x, y c / cmax (gdzie c, cmax w górnym wierszu (yi), piksele (dwie pary) cmax " xi, yi. " ai-[ai] ([2na+0,5]i) mod 2n. xi+1:= xi +1 " d true tylko wtedy, ńły + 1 dla k<0, yi + 1:= ł i gdy poprzednia operacja na zmiennej d yi dla ke"0. ół " k, parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. k. n {liczba bitów dla typu integer}, " x, y, c, cmax nm {n-m>0, gdzie 2m }, x, y c / cmax (gdzie c, cmax em {2m-1}; " Zami k k*"x. zmienne procedury: dx, dy, d, dinc:integer; dx := xe-x; dy := ye-y; parametry procedury: x, y, xe, ye:integer; x := xs, y := ys, xe := xe, ye := ye. dla dx e" dy e" 0: d := 0; zmienne procedury: kdx, dx, dy:integer; dx := xe-x; dy := ye-y; dinc := ((dy shl n)+(dx shr 1)) div dx; dla dx e" dy e" 0: while x `" xe do kdx := 0; begin while x `" xe do plot(x, y, em - (d shr nm) , em); begin if d `" 0 then plot(x, y+1, d shr nm, em); plot(x, y, dx-kdx, dx); x := x+1; d := d+dinc {mod 2n}; if kdx `" 0 then plot(x, y-1, kdx, dx); if overflow(d) then y := y+1 x := x+1; end; kdx := kdx-dy; plot(xe, ye, em, em) if kdx < 0 then begin y := y+1; kdx := kdx+dx end end; plot(xe, ye, 1, 1) 29 30 Oktanty (ósemki) 3 2 dla orientacji dodatniej orientacja orientacja 4 1 ujemna dodatnia 5 8 (orientacja ujemna - zgodnie z ruchem dla orientacji wskazówek zegara, orientacja dodatnia - ujemnej 6 7 przeciwnie do ruchu wskazówek zegara). (xc,yc) = (0,0) : " " zmiennoprzecinkowe if y > 0 then if x > 0 then if x > y then Octant := 1 else Octant := 2 else if y > -x then Octant := 3 else Octant := 4 " podstawowy else if x < 0 then if x < y then Octant := 5 else Octant := 6 " parametryczny else if y < -x then Octant := 7 " else if y `" 0 then Octant := 8 " warunkowe else if x `" 0 then Octant := 1 else Octant := 0 Funkcja StartOctant(xs,ys,xe,ye) wykorzystuje ten algorytm do wyznaczenia " Bresenhama xs,ys xe,ye). Funkcja ta " midpoint) pewne zmienne globalne dla potrzeb funkcji Octant. " porównawczy Jordana " Algorytm wyznaczania numeru oktantu na podstawie E S r > 1) rysowanym przy orientacji dodatniej: case Octant of 1: if x > y then Octant := 1 else Octant := 2; wyznaczonej przez punkt E, C 2: if x > 0 then Octant := 2 else Octant := 3; rysowany przy orientacji dodatniej. 3: if y > -x then Octant := 3 else Octant := 4; Uwaga: 4: if y > 0 then Octant := 4 else Octant := 5; 5: if x < y then Octant := 5 else Octant := 6; Oznaczenia: (xs , ys (xe , ye 6: if x < 0 then Octant := 6 else Octant := 7; (xc , yc 7: if y < -x then Octant := 7 else Octant := 8; 8: if y < 0 then Octant := 8 else Octant := 1 end Funkcja Octant(x,y) wykorzystuje ten algorytm do wyznaczenia oktantu aspect ratio) wynosi 1. piksel v piksela (x,y). Funkcja ta zwraca numer oktantu tego piksela lub zero, gdy u . v u " Uwaga: xc , yc) i promieniu r r xc , yc). y*xe > ye*x ! 31 32 Algorytm podstawowy Algorytm parametryczny " Ogólna zasada: " Równ xc,yc) = (0,0) i promieniu r: x = r*cos, y = r*sin, " [0, 2*Ą) " o " = const. " rodku (xc,yc) = (0,0) i promieniu r: x2 + y2 = r2 " xi,yi xi = r*cosi, yi = r*sini, 3 2 xi+1,yi+1) ma Dla orientacji dodatniej i dla oktantów: 4 1 1] " 1, 8: y x:= [ r2 - y2 + , xi+1 = r*cosi+1 = r*cos(i+") = 2 5 8 = r*cosi*cos" - r*sini*sin" = 1] " 2, 3: x zmniejszane o 1, y:= [ r2 - x2 + , = xi*cos" - yi*sin", 2 6 7 yi+1 = r*sini+1 = r*sin(i+") = 1] " 4, 5: y zmniejszane o 1, x:=-[ r2 - y2 + , 2 = r*cosi*sin" + r*sini*cos" = 1] = xi*sin" + yi*cos", " y:=-[ r2 - x2 + . 2 " " Uwaga: r 1 r " "" d"1 " d" (np. 200* r r 1 function sqr(u:integer):longint; begin sqr:=longint(u)*longint(u) end " = . r parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, zmienne procedury: c, s, u, v, z:real; xe := xe-xc, ye := ye-yc, zmienne procedury: rr:longint; xe := xe-xc, ye := ye-yc, dla wszystkich oktantów: xc := xc, yc := yc. dla oktantów nr 1 i 8: xc := xc, yc := yc. if StartOctant(x,y,xe,ye) `" 0 then if StartOctant(x,y,xe,ye) in [1, 8] then begin begin u := 1.0 / sqrt(sqr(x) + sqr(y)); c := cos(u); s := sin(u); rr := sqr(x) + sqr(y); v := x; z := y; repeat repeat plot(x+xc, y+yc); plot(x+xc, y+yc); y := y+1; u := v*c-z*s; z := v*s+z*c; v := u; x := round(sqrt(rr-sqr(y))) x := round(v); y := round(z) until not (Octant(x,y) in [1, 8]) until Octant(x,y) = 0 end end 33 34 Algorytm Honga Algorytm Bresenhama 1 " Dla algorytmu parametrycznego: xi+1 = xi*cos" - yi*sin", " d" " r yi+1 = xi*sin" + yi*cos". " Oznaczenie: poprzedniego w kierunku albo . k := [log2 r r. 1 1 " 2k-1 d" r < 2k & 2-k < d" 2-k+1 " =2-k < . Rys. Kryterium wyboru r r d1 dwa kolejnego piksela dla piksele " " kandydaci d2 " d1>d2 ! rysowany lewy piksel kandydat, ostatnio 1 (-1)n x2*n 1 (-1)n x2*n+1 " d1narysowany cosx = 1- x2 +..+ +... sinx = x - x3+..+ +... prawy piksel kandydat, piksel 2! (2 * n)! 3! (2 * n + 1)! " d1=d2 ! rysowany 1 " x H" 1- *x2, sinx H" x "=2-k, dowolny z pikseli 2 kandydatów 1 xi+1 = xi*(1- *(")2) - yi*" = xi -xi*2-(2k+1) -yi*2-k, 2 " xi, yi. 1 yi+1 = xi*" + yi*(1- *(")2) = xi*2-k+yi-yi*2-(2k+1). 2 ńłxi - 1 przy wyborze lewego piksela kandydata, n xi +1:= ł xi " przy wyborze prawego piksela kandydata. ół shr, shl - operacje przesuwania arytmetycznego w prawo i lewo. yi+1:= yi +1 przy wyborze dowolnego z pikseli kandydatów, parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, " Wynik porównania d1>d2 decyduje o wyborze kolejnego piksela zmienne procedury: k, n:integer; u, v, z:longint; xe := xe-xc, ye := ye-yc, do rysowania: d1 = xi - r2 - (yi +1)2 , d2 = r2 - (yi +1)2 - (xi -1). dla wszystkich oktantów: xc := xc, yc := yc. if StartOctant(x,y,xe,ye) `" 0 then " d1>d2 ! xi - r2 - (yi +1)2 > r2 - (yi +1)2 - (xi -1) begin u := sqr(x) + sqr(y); k := 0; ! 2 * xi -1 > 2 * r2 - (yi + 1)2 (...)2 (xi > 0) while u `" 0 do begin u := u shr 2; k := k+1 end; ! (2*xi-1)2 > 4*(r2-(yi+1)2) {k := trunc(log2(sqrt(sqr(x)+sqr(y))))+1;} n := 2*k+1; v := x; z := y; v := v shl n; z := z shl n; ! 4*xi2-4*xi+1 > 4*(r2-(yi+1)2) repeat ! 4*xi2-4*xi+2 > 4*(r2-(yi+1)2) / 2 plot(x+xc, y+yc); ! 2*xi2-2*xi+1 > 2*(r2-(yi+1)2) u := v-x-(z shr k); z := z-y+(v shr k); v := u; x := v shr n; y := z shr n ! xi2+xi2-2*xi+1 > 2*(r2-(yi+1)2) until Octant(x,y) = 0 ! xi2+(xi-1)2 > 2*(r2-(yi+1)2) end ! xi2+(yi+1)2-r2 > r2-(xi-1)2-(yi+1)2 F(x,y) = x2+y2-r2 ! F(xi,yi+1)+F(xi-1,yi+1) > 0 35 36 " Oznaczenie: pi := F(xi,yi+1)+F(xi-1,yi+1). midpoint) pi jest zawsze . " " d1>d2 ! pi>0 ! wybór lewego piksela kandydata, poprzedniego w kierunku albo . d1d1=d2 ! pi=0 ! wybór dowolnego piksela kandydata, w algorytmie Rys. Kryterium wyboru ten przypadek nigdy nie zajdzie. dwa kolejnego piksela dla piksele " pi: kandydaci o wyborze kolejnego p0 = F(x0,y0+1)+F(x0-1,y0+1) = x0=xs, y0=ys piksela decyduje znak = F(xs,ys+1)+F(xs-1,ys+1) = ostatnio narysowany F(x,y)=x2+y2-r2 = xs2+(ys+1)2-r2+(xs-1)2+(ys+1)2-r2 = piksel 2+y 2-r 2=0 = xs2+ys2+2*ys+1-r2+xs2-2*xs+1+ys2+2*ys+1-r2 = x = 4*ys-2*xs+3. kandydatami. " pi: " Przyjmi xi, yi. pi+1-pi = F(xi+1,yi+1+1)+F(xi+1-1,yi+1+1)-F(xi,yi+1)-F(xi-1,yi+1) = = xi+12+(yi+1+1)2-r2+(xi+1-1)2+(yi+1+1)2-r2+ ńłxi - 1 przy wyborze lewego piksela kandydata, -xi2-(yi+1)2+r2-(xi-1)2-(yi+1)2+r2 = xi +1:= ł xi przy wyborze prawego piksela kandydata. = xi+12-xi2+(xi+1-1)2-(xi-1)2+2*((yi+1+1)2-(yi+1)2) = ół yi+1:= yi +1 przy wyborze dowolnego z pikseli kandydatów, xi2-xi2+(xi-1)2-(xi-1)2+2*((yi+2)2-(yi+1)2) = ńł ł = = 4*yi+6 dla wyboru prawego piksela, " Oznaczenie: ł ł 1 1 1 1 (xi-1)2-xi2+(xi-2)2-(xi-1)2+2*((yi+2)2-(yi+1)2) = ół fi := F(xi- ,yi+1)- = (xi- )2 +(yi+1)2 -r2 - = xi2 -xi +yi2 +2*yi +1 -r2. 2 4 2 4 = 4*yi-4*xi+10 dla wyboru lewego piksela. 1 1 " Uwaga: fi := F(xi- ,yi+1) - 2 4 parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, zmienne procedury: p:integer; xe := xe-xc, ye := ye-yc, " Kryterium wyboru kolejnego piksela: 1 dla oktantu nr 1: xc := xc, yc := yc. " F(xi- ,yi+1)>0 ! fi e" 0 ! rysowany lewy piksel kandydat, 2 if StartOctant(x,y,xe,ye) = 1 then 1 begin " F(xi- ,yi+1)<0 ! fi < 0 ! rysowany prawy piksel kandydat, 2 p := 4*y-2*x+3; 1 repeat " F(xi- ,yi+1)=0 ! rysowany dowolny z pikseli kandydatów - 2 plot(x+xc, y+yc); ten przypadek nigdy nie zajdzie. if p < 0then p := p+4*y+6 else begin p := p+4*(y-x)+10; x := x-1 end; y := y+1 until Octant(x,y) `" 1 end 37 38 2 Algorytm porównawczy Jordana " Pocz fi: x 2 + y 2 - r = 0 Ó! " Za 1 1 f0 := F(x0,y0)- = F(xs,ys)- = xs2 -xs +ys2 +2*ys +1 -r2 = 2*ys -xs +1. 4 4 poprzedniego w kierunku , albo . " fi: Rys. Kryterium wyboru 1 1 1 1 fi+1-fi := F(xi+1- ,yi+1+1) - - F(xi- ,yi+1) + = trzy kolejnego piksela dla 2 4 2 4 piksele kandydaci = xi+12 -xi+1 +yi+12 +2*yi+1 +1 -r2 -xi2 +xi -yi2 -2*yi -1 +r2 = rysowany jest ten piksel, = xi+12-xi2-xi+1+xi+yi+12-yi2+2*(yi+1-yi) = ostatnio narysowany funkcji F(x,y)=x2+y2-r2 piksel = (xi+1+xi-1)*(xi+1-xi)+(yi+1+yi+2)*(yi+1-yi) = najmniejsza. = (xi+1+xi-1)*(xi+1-xi)+2*yi+3 = yi+1 = yi+1 xi+1 = xi 2 * yi + 3 ńł " xi, yi. = ł2 * yi - 2 * xi + 5 xi+1 = xi-1 ół 2 * yi+1 +1 ńł 1. xi+1:= xi - 1 = przy wyborze lewego piksela kandydata, ł2 * yi+1 - 2 * xi+1 + 1 yi+1:= yi ół 2. xi+1:= xi przy wyborze górnego piksela kandydata, yi+1:= yi +1 3. xi+1:= xi - 1 przy wyborze lewego górnego piksela kandydata. yi+1:= yi +1 parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, zmienne procedury: f:integer; xe := xe-xc, ye := ye-yc, " Oznaczenia: f := F(xi,yi), F(x0,y0) = F(xs,ys) = 0, dla oktantu nr 1: xc := xc, yc := yc. f1 := F(xi-1,yi) = f -2*xi +1, if StartOctant(x,y,xe,ye) = 1 then f2 := F(xi,yi+1) = f +2*yi +1, begin f3 := F(xi-1,yi+1) = f -2*xi +2*yi +2. f := 2*y-x+1; repeat plot(x+xc, y+yc); " |f1|<|f2| & |f1|<|f3| ! wybór lewego piksela kandydata, y := y+1; |f2|<|f1| & |f2|<|f3| ! wybór górnego piksela kandydata, if f < 0 then f := f+2*y+1 |f3|<|f1| & |f3|<|f2| ! wybór lewego górnego piksela kandydata, else begin x := x-1; f := f+2*(y-x)+1 end |f1|<|f2| & |f1|=|f3| ! wybór lewego lub lewego górnego piksela, until Octant(x,y) `" 1 |f2|<|f1| & |f2|=|f3| ! wybór górnego lub lewego górnego piksela, end w al 39 40 " f2 e" f3 e" f1 |f1|<|f2| & |f1|<|f3| ! |f1|<|f3| ! wybór lewego piksela kandydata, 3 2 " xc,yc) i |f2|<|f1| & |f2|<|f3| ! |f2|<|f3| ! wybór górnego piksela kandydata, promieniu r 4 1 jednego oktantu (np. nr 1). Otrzymane dla tego 5 8 x, y parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, (x,y), 6 7 (y,x), (-y,x), (-x,y), (-x,-y), (-y,-x), (y,-x), (x,-y). zmienne procedury: f1, f2, f3:integer; xe := xe-xc, ye := ye-yc, dla oktantu nr 1 lub 2: xc := xc, yc := yc. Elipsa if StartOctant(x,y,xe,ye) in [1, 2] then 3 2 begin " xc,yc) i f1 := -2*x+1; p i q 4 1 repeat plot(x+xc, y+yc); 5 8 x, f3 := f1+2*y+1; f2 := f3+2*x-1; y if |f1| < |f3| then begin x := x-1; f1 := f1-2*x+1 end 67 (x,y), (-x,y), (-x,-y), (x,-y). else if |f2| < |f3| then begin y := y+1; f1 := f2-2*x+1 end else begin x := x-1; y := y+1; f1 := f3-2*x+1 end until not (Octant(x,y) in [1, 2]) end procedure Ellipse(xc, yc, p, q: integer); var x, y: integer; pp, qq, pp2, qq2, f, fx, fy: longint; " f2 e" f3 e" f1 begin |f1|<|f3| ! -f1x := p; y := 0; |f2|<|f3| ! f2<-f3 ! wybór górnego piksela kandydata, pp := p*p; qq := q*q; pp2 := 2*pp; qq2 := 2*qq; f := pp - p*qq + qq div 4; fx := qq2*p; fy := 0; while fx > fy do {oktant nr 1 (oraz nr 4, 5, 8)} parametry procedury: x, y, xe, ye, xc, yc:integer; x := xs-xc, y := ys-yc, begin zmienne procedury: f1, f2, f3:integer; xe := xe-xc, ye := ye-yc, plot(x+xc, y+yc); plot(-x+xc, y+yc); dla oktantu nr 1 lub 2: xc := xc, yc := yc. plot(-x+xc, -y+yc); plot(x+xc, -y+yc); y := y+1; fy := fy+pp2; if StartOctant(x,y,xe,ye) in [1, 2] then if f < 0 then f := f+fy+pp begin else begin x := x-1; fx := fx-qq2; f := f-fx+fy+pp end f1 := -2*x+1; end; repeat f := f - (fx+fy) div 2 + qq - pp - (qq-pp) div 4; plot(x+xc, y+yc); repeat {oktant nr 2 (oraz nr 3, 6, 7)} f3 := f1+2*y+1; f2 := f3+2*x-1; plot(x+xc, y+yc); plot(-x+xc, y+yc); if f3 < -f1 then begin y := y+1; f1 := f3 end; plot(-x+xc, -y+yc); plot(x+xc, -y+yc); if -f3 < f2 then begin x := x-1; f1 := f1-2*x+1 end x := x-1; fx := fx-qq2; until not (Octant(x,y) in [1, 2]) if f > 0 then f := f-fx+qq end else begin y := y+1; fy := fy+pp2; f := f-fx+fy+qq end until x < 0 end 41 42 { var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); } Znajdowanie konturu procedure AllContourTracing; " Konturem danego zbioru pikseli nazywamy zbiór wszystkich pikseli var x,y: coordinate; begin for x:=minx to maxx do for y:=miny to maxy do if pixel[x,y] then if (pixel[x 1,y]=empty) or (pixel[x+1,y]=empty) or (pixel[x,y 1]=empty) or (pixel[x,y+1]=empty) then pixel[x,y]:=contour end; pikseli i jego kontur. procedure neighbour(var nx,ny:coordinate; x,y:coordinate; s:direction); " Znajdowanie wszystkich konturów dowolnego zbioru pikseli: begin procedura AllContourTracing. case s of 0: begin nx:=x+1; ny:=y end; 1: begin nx:=x+1; ny:=y 1 end; 2: begin nx:=x; ny:=y 1 end; " Znajdowanie pojedynczego konturu spójnego podzbioru zbioru pikseli: 3: begin nx:=x 1; ny:=y 1 end; procedura ContourTracing. 4: begin nx:=x 1; ny:=y end; 5: begin nx:=x 1; ny:=y+1 end; 6: begin nx:=x; ny:=y+1 end; 7: begin nx:=x+1; ny:=y+1 end end 7 6 5 end; piksel piksel spoza 4 konturu zbioru 1 2 3 piksela konturu. 43 44 { var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); } procedure ContourTracing(bx,by:coordinate; bs:direction); " varx,y,nx,ny: coordinate; " - s: direction; begin mi poziomymi. if pixel[bx,by] then exit; { punkt (bx,by bs:= bs mod 8 - bs mod 2; neighbour(nx,ny,bx,by,bs); if pixel[nx,ny] then exit bx,by s:=bs; kontur. Fragmenty repeat konturu styczne do bs:= (bs+7) mod 8; linii poziomych nie if bs=s then begin traktowane jako pixel[bx,by]:=contour; exit liniami poziomymi. end; neighbour(nx,ny,bx,by,bs) until pixel[nx,ny] if odd(bs) then bs:= (bs+1) mod 8 else bs:= (bs+2) mod 8; { znajdowanie konturu } x:=bx; y:=by; konturu styczny do linii poziomej. repeat pixel[x,y]:=contour; repeat s:= (s+1) mod 8; neighbour(nx,ny,x,y,s) dla którego until pixel[nx,ny] procedura x:=nx; y:=ny; AllContourFilling if odd(s) then s:= (s+5) mod 8 else s:= (s+6) mod 8 until (x=bx) and (y=by) and (s=bs) end; z tego konturu pikseli oznaczonych nanie tej procedury. 45 46 { var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); } " (przez sianie) - procedure AllContourFilling; var x,y: coordinate; above,below: integer; oddintsect: Boolean; begin procedure Fill(x, y: Integer); { x, y for y:=miny to maxy do begin begin if pixel[x,y] = empty then oddintsect:=false; begin x:=minx; pixel[x,y] := interior; while x maxx do Fill(x+1,y); Fill(x,y-1); Fill(x-1,y); Fill(x,y+1) if pixel[x,y] end then end begin if oddintsect then pixel[x,y]:=interior; x:=x+1 end else begin 118 if (pixel[x-1,y-1]=contour) or (pixel[x,y-1]=contour) 4 3 2 procedury Fill(x,y) 107 6 5 4 then above:=1 else above:=0; if (pixel[x-1,y+1]=contour) or (pixel[x,y+1]=contour) 6 5 0 1 y 9 7 0 1 then below:=1 else below:=0; 6 2 3 czarne cyfry - poziom repeat 8 2 3 rekurencji). if (pixel[x+1,y-1]=contour) and (pixel[x,y-1] then above:=above+1; if (pixel[x+1,y+1]=contour) and (pixel[x,y+1] x then below:=below+1; x:=x+1; until (pixel[x,y] or (x maxx); if odd(above) and odd(below) then oddintsect:= not oddintsect; if odd(above) below) then end end end; 1 9 1 1 1 1 procedury 5 6 7 8 ContourFilling(x,y) 0 0 0 0 y 0 1 2 3 1 4 100 110 czarne cyfry - poziom rekurencji). x 47 48 { var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour); } procedure ContourFilling(x,y: coordinate); " procedure filling(x,y: coordinate; dy: integer); Definicja: var ax,ay,bx,by: coordinate; afind,bfind: Boolean; " Szkieletem Sk&! zbioru &! begin if pixel[x,y]=empty then repeat ł A `" B ł ł"A "Fr &! ł ax:=x; ay:=y+dy; P "Sk &! ! P "&! AP = BP ł ł bx:=x; by:=y-dy; "B "Fr &! ł ł "C "Fr &! CP e" AP ł łł while pixel[ax,ay]=empty do ax:=ax-1; if ax x then ax:=ax+1; " while pixel[bx,by]=empty do bx:=bx-1; Definicja: if bx x then bx:=bx+1; " Piksel konturu nazywamy powtarzalnym afind:=pixel[ax,ay]=empty; jeden z trzech warunków: bfind:=pixel[bx,by]=empty; 1. pixel[x,y]:=interior; 2. x:=x+1; 3. while pixel[x,y]=empty do begin pixel[x,y]:=interior; if (pixel[x,ay]=empty) and (pixel[x-1,ay] Definicja: then begin if afind " Szkieletem danego zbioru pikseli jest zbiór pikseli, otrzymany w wyniku then filling(ax,ay,dy) else afind:=true; " Szkieletem jest zatem zbiór otrzymany w wyniku wykonania algorytmu: ax:=x repeat end; if (pixel[x,by]=empty) and (pixel[x-1,by] until then begin if bfind then filling(bx,by,-dy) " else bfind:=true; bx:=x A A A A A A A A C end; X A X pierwszemu ( ) i trzeciemu*) X K x:=x+1 B B B A B ( ) warunkowi. B B C end; 0 90 0 90 180 270 0 90 180 270 if afind and bfind then filling(ax,ay,dy); if bfind then begin x:=bx; y:=by; dy:=-dy end " X - piksel powtarzalny konturu; K - piksel konturu; else begin x:=ax; y:=ay end " A, B, C - grupa pik until not (afind or bfind) end; begin " aga zatem jedynie sprawdzenia if pixel[x,y] then exit; repeat x:=x-1 until pixel[x,y] x:=x+1; filling(x,y,1) " end; " eniania: procedura Thinning. 49 50 { var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour, skeleton); } { var pixel: array[minx..maxx, miny..maxy] of (empty, interior, contour, skeleton); } procedure Thinning; procedure DefThinning; var x,y,nx,ny: coordinate; q,r,s: direction; finish, pattern, first, second: Boolean; var x,y,nx,ny: coordinate; e,i,m: byte; s: direction; finish, pattern: Boolean; begin begin repeat repeat finish:=true; s:=0; finish:=true; repeat AllContourTracing; for y:=miny to maxy do for x:=minx to maxx do for y:=miny to maxy do for x:=minx to maxx do if pixel[x,y]=contour then if pixel[x,y]=interior then begin begin neighbour(nx,ny,x,y,s); e:=0; i:=0; m:=0; if pixel[nx,ny]=empty then for s:=0 to 7 do { konstrukcja wzorców } begin pattern:=false; begin r:=(s+2) mod 8; e:=e shl 1; i:=i shl 1; m:=m shl 1; repeat neighbour(nx,ny,x,y,s); neighbour(nx,ny,x,y,r); if pixel[nx,ny]=empty if pixel[nx,ny]=empty then then e:=e or 1 begin first:=false; second:=false; else begin i:=i or 1; q:=(s+1) mod 8; if pixel[nx,ny] then m:=m or 1 repeat end neighbour(nx,ny,x,y,q); end; { if pixel[nx,ny] then first:=true; pattern:=(i=m) or { q:=(q+1) mod 8 (((i and $70) and ((i and $07) and ((e and $88)=$88)) or until (q=r) or first; (((i and $1C) and ((i and $C1) and ((e and $22)=$22)) or q:=(r+1) mod 8; (((i and $01) and ((i and $7C) and ((e and $82)=$82)) or repeat (((i and $40) and ((i and $1F) and ((e and $A0)=$A0)) or neighbour(nx,ny,x,y,q); (((i and $10) and ((i and $C7) and ((e and $28)=$28)) or if pixel[nx,ny] then second:=true; (((i and $04) and ((i and $F1) and ((e and $0A)=$0A)) or q:=(q+1) mod 8 { until (q=s) or second; (((i and $41) and ((m and $80) and ((e and $08) and pattern:= first and second (((e and $41)=0) or (((i and $30) and ((i and $06) or end; (((i and $05) and ((m and $02) and ((e and $20) and r:=(r+2) mod 8 (((e and $05)=0) or (((i and $C0) and ((i and $18) or until (r=s) or pattern; (((i and $14) and ((m and $08) and ((e and $80) and if pattern then pixel[x,y]:=skeleton (((e and $14)=0) or (((i and $03) and ((i and $60) or else pixel[x,y]:=contour (((i and $50) and ((m and $20) and ((e and $02) and end (((e and $50)=0) or (((i and $0C) and ((i and $81) end; if pattern then pixel[x,y]:=skeleton else finish:=false for y:=miny to maxy do for x:=minx to maxx do end; if pixel[x,y]=contour then for y:=miny to maxy do for x:=minx to maxx do begin pixel[x,y]:=empty; if pixel[x,y]=contour then pixel[x,y]:=empty finish:=false else if not finish and (pixel[x,y]=skeleton) then pixel[x,y]:=interior end; until finish; s:=(s+2) mod 8 for y:=miny to maxy do for x:=minx to maxx do until s=0 if pixel[x,y]=interior then pixel[x,y]:=skeleton until finish end; end; 51 52 12 12 Filtracja 12 13 123 konturu z zaznaczonymi " Filtry liniowe - 2 2 pikselami powtarzalnymi. 2 3 3 1 " 1 2 definicji, z którego wynika 2 3 1 1 1 1 1 1 1 2 1 1 1 1 12 23 " 1 1 1 1 2 1 2 4 2 1 0 1 1 1 1 1 1 1 1 2 1 1 1 1 2 - piksel figury - piksel konturu " Filtry górnoprzepustowe w - piksel powtarzalny konturu 0 0 0 0 0 0 " gradient Robertsa -1 0 0 0 0 -1 0 1 0 0 1 0 1 1 1 1 2 2 1 1 2 3 3 2 1 -1 -1 -1 -1 0 1 otrzymany w wyniku cyklicznego 1 2 3 2 3 2 1 " maska Prewitta 0 0 0 -1 0 1 odrzucania punktów konturu nie 1 2 2 1 2 3 2 1 1 1 1 -1 0 1 1 2 2 1 1 2 2 1 nymi (wg definicji szkieletu) 1 2 1 1 2 2 1 procedura DefThinning. Cyfry 1 2 2 1 1 2 2 1 -1 -2 -1 -1 0 1 -2 -1 0 1 2 2 1 1 2 1 " maska Sobela 0 0 0 -2 0 2 -1 0 1 1 2 3 3 2 1 1 1 1 2 3 2 1 1 2 1 -1 0 1 0 1 2 1 2 3 2 2 2 2 2 2 2 3 2 1 1 2 2 1 1 1 1 1 1 1 2 2 1 - piksele figury 1 2 2 1 1 2 1 -1 -1 1 -1 1 1 -5 -5 3 1 2 2 1 1 2 2 1 - piksele szkieletu " wykrywanie -1 -2 1 -1 -2 1 -5 0 3 1 1 1 1 1 1 1 1 1 -1 1 1 3 3 3 3 4 1 3 5 4 1 0 -1 0 -1 -1 -1 1 -2 1 3 4 7 5 4 1 " laplasjan -1 4 -1 -1 8 -1 -2 4 -2 otrzymany w wyniku wykonania 3 4 6 6 6 5 1 0 -1 0 -1 -1 -1 1 -2 1 3 5 2 2 3 5 4 1 3 4 2 1 2 3 5 1 " Filtry nieliniowe procedura Thinning. Cyfry 3 5 1 3 5 4 1 " 3 4 5 1 2 3 5 1 (np. pierwiastek sumy kwadratów pionowej i poziomej maski Prewitta) pikseli jako konturu. 3 7 5 1 3 5 1 " medianowy, maksymalny, minimalny 3 4 7 5 4 4 4 4 4 4 5 4 1 " operacje logiczne 3 7 6 6 6 6 6 6 6 6 6 5 1 " adaptacyjne 3 5 2 2 2 2 2 2 2 2 3 5 1 - piksele figury 3 4 5 1 3 5 1 3 5 2 1 2 3 4 1 - piksele szkieletu 2 2 1 2 2 1 " spoza zbioru. " 53 54 " " " x,y i biegunowy r " x,y,z; sferyczny R r z. Y x Z Z x r * cos X x r cos = = *
zz y r sin y r * sin = * = r = cos * y y x R * sinŚ = sinŚ r y R *sin * Ś Ś R R z R cosŚ = * y x X Y X x Y r r x y x' x ł łł ł łł X Y " p' = , p = ł ł y'śł yśł ł ł ł ł dwuwymiarowej: " " b: p' = I * p + b 1 0 ł łł " b: p' = I * p + b gdzie I = ł0 1śł 1 0 0 x' x ł ł ł łł ł łł ł łł ł0 ł ł gdzie I = 1 0śł p'= y'śł, p = yśł " q p' = D * p + (I - D) * q ł śł ł śł ł śł cos ł - sin ł0 0 1śł ł z'śł ł zśł łł ł ł ł ł ł ł gdzie D = łsin cos śł ł ł " q: p' = D * p + (I - D) * q łd d d łł " k q: p' = k * I * p + (1 - k) * q xx xy xz łd śł gdzie D = d d przy czym: duv , " q: p' = -I * p + 2 * q yx yy yz uv ł śł u v ł ł " q1, q2: p' = G * p + h łd zx d zy d zz śł uv ł - x1)2 - ( y2 - y1)2 2 * (x2 - x1) * ( y2 - y1) 1 (x2 łł " k q: p' = k * I * p + (1 - k) * q G = , (x2 - x1)2 + ( y2 - y1)2 ł2 * (x2 - x1) * ( y2 - y1) ( y2 - y1)2 - (x2 - x1)2 śł ł ł " z=a: p' = F * p + h łł ł łł ł łł 1 0 0 0 x0 2 * (x2 * y1 - x1 * y2 ) ł- ( y2 - y1) x1 x2 ł łł ł łł ł łł h = przy czym q1 = , q2 = ; ł ł0 ł0śł ł x2 ł (x2 - x1)2 + ( y2 - y1)2 ł - x1 śł, y1śł ł y2 śł gdzie F = 1 0śł, h = q = y0 śł ł ł ł ł ł ł śł ł śł ł śł ł-1 0 2 * a 1 0 0 ł0 0 0śł łaśł ł z0 śł łł ł łł ł łł ł łł ł ł ł ł ł ł dla osi x=a: G = , h = ; dla osi y=b: G = , h = ł śł ł0 -1śł ł2 * bśł 0 1śł ł 0 ł ł ł ł ł ł ł ł " " rzut perspektywiczny z punktu q ł z0 - a ł z=a: p' = F * ł * (p - q) + qł + h ł ł z0 - z ł łł 55 56 z Obrazy trójwymiarowe " Fij(x,y) := (yi-yj)*x - (xi-xj)*y + xi*yj - xj*yi, Pk := (xk,yk). " " d"xd"2 & " P1, P2: F12(x,y) = 0. 0d"yd"2 & 0d"zd"2 (" 0d"xd"1 & 0d"yd"1 & 2d"zd"3. xy " P1 " szkieletow P2): F12(x,y) < 0, dla punktów po lewej stronie: F12(x,y) > 0. D(2,0,0), E(1,1,2), F(0,1,2), G(0,2,2), H(2,2,2), I(2,0,2), J(1,0,2), " P0: (x1-x2)*x + (y1-y2)*y - (x1-x2)*x0 - (y1-y2)*y0 = 0. EFGHIJ, EJNM, EMLF, KLMN, ABGFLK, AKNJID. " konstruktywna (ang. constructive solid geometry) (obiekty elementarne + " dwa odcinki P1P2 i P3P4 ! sgn(F12(x3,y3)) `" sgn(F12(x4,y4)) & sgn(F34(x1,y1)) `" sgn(F34(x2,y2)). jednostkowy (tzn. 0d"xd"1 & 0d"yd"1 & 0d"zd"1) *" " Q = (x,y " czwórkowego (figury); np. dla 0d"xd"4 & 0d"yd"4 " xmind"xd"xmax & ymind"yd"ymax. & 0d"zd"4: (0,0,0,0,(0,0,0,0,0,0,1,0),0,1,0). " wskazówek zegara P1, P2,... Pn: "i"{1,2,..n} Fi(i mod n + 1)(x,y) < 0. " " anych zgodnie z ruchem wskazówek zegara P1, P2,... Pn: " " z punktu Q " := "i=1..n "PiQP(i mod n + 1) ( = 360 (c). a) b) c) ! Q = 0 ! Q " " analiza zwrotów wektorów normalnych dla wie " Q1Q2 " " " algorytm Ricciego; " algorytm Appela; " " " " " Definicja: " " Punkt P=(xp,yp) l P y = yp, x < xp) przetnie l. poziomymi. Definicja: " Odcinek a odcinek b " a b b a y l y Rys. Ilustracja P definicji a) b) c) d) P' c x x 57 58 Wyznaczanie cieni Rys. Wyznaczanie cieni. " dwukrotne rozstrzyganie problemu a) b) c) d) ekran " " face: " const n n " odbicia: Io type z l type faces = array [1..n] of record colour:integer; polygon:polygons end; Rys. Zjawisko odbicia. var background n - wersor normalny do powierzchni e ą var face: faces; l - wersor kierunku padania promieni z - wersor kierunku odbicia zwierciadlanego " e type location = (outside {a}, inside {b}, other {c,d}); " rozproszone: kr*Io* kr*Io*(nl) " Funkc " zwierciadlane: kz*Io*cosm kz*Io*(ze)m m"[1,200] function Position(x1,y1,x2,y2: integer; var polygon: polygons): location; " kt*Io " " Eo procedure Rectangle(x1, y1, x2, y2, colour: integer); I = (kt + kr*(nl) + kz*(ze)m) * Io, gdzie Io = Eo r2 " r procedure HiddenFace(x1, y1, x2, y2, first, last: integer; var face: faces); var x, y, i: integer; begin " brak cieniowania if first < 1 then first := 1; if last > n then last := n; for i := first to last do " metoda Gourauda case Position(x1, y1, x2, y2, face[i].polygon) of " outside: begin { nic nie rób } end; inside: begin { kadr w kolorze i " Rectangle(x1, y1, x2, y2, face[i].colour); exit {procedure} " end; other: begin tej samej linii poziomej co dany punkt. x := (x1+x2) div 2; y := (y1+y2) div 2; " metoda Phonga - interpolacja wersorów normalnych; HiddenFace(x1, y1, x, y, i, last, face); " HiddenFace(x1, y+1, x, y2, i, last, face); HiddenFace(x+1, y1, x2, y, i, last, face); " h na HiddenFace(x+1, y+1, x2, y2, i, last, face); exit {procedure} " end end; {case} Rectangle(x1, y1, x2, y2, background) " end; {procedure} 59 60 " splines) Modelowanie krzywych i powierzchni Modelowanie krzywych: " funkcja sklejana p n n ł ł p, przy czym funkcja " krzywe Bziera: p0,n (t) = ł ł * ti * (1- t)n-i * pi dla t "[0,1], " ł ł ta, jak i jej p pi - punkty kontrolne. i=0ł i łł " " funkcje B-sklejane md"n, t0d" t1d"...d" tmd"...d" tnd" tn+1d"...d" tn+m+1 " p0, pn: p0,n(0) = p0, p0,n(1) = pn. 1 dla t "[ti ,ti+1], ńł " styczna w punkcie p0 do odcinka p0p1: p'0,n(0) = n*(p1-p0). n0,i (t) = ł0 dla t "[ti ,ti+1], i = 0..n + m ół " styczna w punkcie pn do odcinka pn-1pn: p'0,n(1) = n*(pn-pn-1). " mie i = 0..n + m - k t - ti tk +i+1 - t nk,i (t) = * nk (t) + * nk " p0,n(t) = (1-t)*p0,n-1(t) + t*p1,n(t). tk +i - ti -1,i tk +i+1 - ti+1 -1,i+1(t), k = 0..m " wielomiany Bernsteina bn,i (t) i Fergusona fn,i (t) : " funkcje B-sklejane nm,i (i=0..n) n n n ł ł q(t ) = * nm,i (t). "a i p0,n (t) = (t) * pi , bn,i (t) = ł ł * ti * (1 - t)n-i dla i = 0..n, "b n,i ł ł i =0 i sklejanych stopnia m ł łł i=0 nmi (t ) = 0 dla t "[ti ,ti +m+1], , n n [tm, tn+1] i sklejanych dla nmi (t ) e" 0 dla dowolnego t , p0,n (t) = (t) * qi , fn,i (t) = (t) dla i = 0..n, , "f "b n,i n,k tm+1,.., tn: i=0 k =i n " "n (t) = 1 dla t "[tm ,tn+1]. n mi , " n k ł ł ł -1 ł i =0 fn,0(t) = 1, fn,i (t) = ł ł * ł ł * (-1)k +i * tk dla i = 1..n, " łk ł ł ł k - i " ł łł ł łł k =i " unormowanie: i pi = dla i = 0..n, q0 = p0, qi = pi - pi-1 dla i = 1..n, "q k " krzywe sklejane k =0 krzywe opisane parametrycznie funkcjami sklejanymi, przy czym bn,i (t) = fn,i (t) - fn,i+1(t) dla i = 0..n - 1, bn,n (t) = fn,n (t). " wyznaczanie punktów krzywej: " algorytm de Casteljau: p0,n(t) = (1-t)*p0,n-1(t) + t*p1,n(t) n t "[tm ,tn+1], for i := 0 to n do ri := pi; " krzywe B-sklejane: q(t ) = (t ) *pi , "n , mi for j := 1 to n do pi - punkty kontrolne. i =0 for i := 0 to n-j do ri := ri + t * (ri+1 - ri); " zmiana punktu pi t"[ti, ti+m+1]. p0,n(t) := r0. " wyznaczanie punktów krzywej: " algorytm Hornera: (t < 0,5) n n ł ł t ł łi " algorytm de Boora-Coxa dla t"(tk, tk+1): l := 1; k := 1; p0,n (t) = (1 - t)n * ł ł * * pi ł ł " ł ł i 1 - t ł łł for i := 0 to m do ri := pk-m+i; ł łł c := t / (1-t); s := pn; i=0 for j := 1 to m do for i := 1 to n do for i := 0 to m-j do ri := ri + (t-ti+j)/(ti+m+1-ti+j) * (ri+1 - ri); begin l := l*(1-t); k := k*(n-i+1)/i; s := c * s + k * pn-i end; q(t) := r0. p0,n(t) := l * s. " algorytm Hornera: (t > 0,5) n n k n ł ł 1- t ł łi p0,n (t) = tn * ł ł * * pn-i l := 1; k := 1; ł ł " q(t ) = (t ) *pi = (t ) *pi dla t "(tk ,tk +1) ł ł "n , "n , mi mi c := (1-t) / t; s := p0; i=0ł i łł ł t łł i =0 i = k -m for i := 1 to n do begin l := l*t; k := k*(n-i+1)/i; s := c * s + k * pi end; p0,n(t) := l * s. 61 62