Jak ulepszyê procedurë? (odc. 11.) --------------------------------- DETEKCJA I WYZNACZANIE KRAWËDZI Na pewno zetknëliôcie sië juû w programach do obróbki grafiki z takimi opcjami, jak: EMBOSS, RELIEF MAP, EDGE DETECT, czy LAPLACIAN. Nie wszyscy jednak wiecie, ûe efekty te (i to w czasie rzeczywistym) moûemy bez problemów wykonywaê w asemblerze. Daje to szansë wykorzystania ich w demie. Miklesz/Damage Sekret szybkoôci polega tu na paru uproszczeniach, które choê uniemoûliwiajâ wykonanie na przeksztaîconym obrazie analizy iloôciowej (polegajâcej na wykryciu krawëdzi i odtwarzaniu wyodrëbnionych czâstek), to jednak pozwalajâ na osiâgniëcie bardzo dobrego efektu wizualnego. Na poczâtek dawka teorii, która jest konieczna do zrozumienia idei detekcji krawëdzi. Istota krawëdzi... ****** tu koniecznie rysunek (rys. 1) ***************** Wbrew pozorom zdefiniowanie krawëdzi nie jest takie îatwe, poniewaû, jak sië juû za chwileczkë przekonacie, krawëdzie obrazu mogâ wystëpowaê (i najczëôciej wystëpujâ) pod bardzo róûnymi postaciami. Jakimi? Zazwyczaj krawëdú utoûsamiamy z przejôciem (zmianâ jasnoôci) od fragmentu obrazu ciemniejszego do jaôniejszego i odwrotnie. Zdecydowanie najproôciej jest zidentyfikowaê bardzo skokowâ, gwaîtownâ zmianë, na przykîad takâ, jaka wystëpuje na obrazach dwukolorowych. Niestety, na ogóî zmiana ta jest trochë pîynniejsza, tak jak na rys. 1a. Jeszcze jeden odrëbny rodzaj przejôcia to punktowe lub liniowe ôciemnianie (ewentualnie rozjaônianie). Doskonaîym przykîadem takiej zmiany jasnoôci moûe tu byê obraz pîytek chodnikowych. Odpowiedni wykres na rys. 1b. Czasami zauwaûyê teû moûemy przejôcia, które sâ krawëdziami dwóch patternów. Przykîad takiego obrazu zostaî umieszczony na rys. 1c. Okazuje sië, ûe dla kaûdego z przedstawionych przeze mnie typów przejôê do poprawnej obróbki potrzebny jest inny algorytm. Na szczëôcie jednak okazuje sië, ûe wiëkszoôê krawëdzi, jakie spotykamy, ma wykres zmian jasnoôci zbliûony do rys. 1a, a to oznacza, ûe analizë obrazu moûemy ograniczyê do tego wîaônie rodzaju przejôê. Choê na pierwszy rzut oka wydaje sië, ûe okreôlenie linii podziaîu miëdzy dwoma obiektami jest trudne, to przy zastosowaniu róûniczkowania funkcji poziomu jasnoôci punktów sprawa staje sië îatwiejsza. Do roboty! Analiza zmian jasnoôci ( ***** tu rysunek (rys. 2) ******) Juû na poczâtku istnienia problemu analizy obrazu zauwaûono, ûe po obliczeniu pierwszej pochodnej funkcji, która opisuje nam zmiany szaroôci obrazu, dostaniemy do rëki narzëdzie, umoûliwiajâce w miarë dokîadne wyznaczenie przebiegu linii krawëdzi. Przypatrzcie sië rys. 2a. Zauwaûcie, ûe kiedy z powrotem przedstawimy pierwszâ pochodnâ jako obraz, otrzymamy coô w rodzaju bardzo efektownie wyglâdajâcej pîaskorzeúby, którâ znamy z programów typu ImageFX. Po zróûniczkowaniu sygnaîu wystarczy wykorzystaê odpowiedni próg detekcji podczas binaryzacji i mamy juû obraz krawëdzi (rys. 2b). Dodatkowâ zaletâ tego rozwiâzania jest fakt, ûe dla bardziej rozmytych krawëdzi (îagodniejsze przejôcie) maksimum pierwszej pochodnej ma niûszâ wartoôê. Jeszcze bardziej jednoznaczne wyniki daje zastosowanie drugiej pochodnej (rys. 2c). W tym wypadku krawëdú odpowiada wprost miejscu zerowemu drugiej pochodnej. Oczywiôcie na obrazie komputerowym trudno jest wyznaczaê pochodnâ. Jednakûe wystarczajâco dobrym przybliûeniem pochodnej sâ lokalne gradienty. Wiëcej o gradientach za miesiâc, a teraz juû pora na... Asembler! Po dawce teorii mogë przystâpiê do omówienia algorytmu, który umoûliwia wykonywanie w czasie rzeczywistym efektu Emboss (Relief Map) w asemblerze. Obraz analizowaê bëdziemy linia po linii, poruszajâc sië od lewego górnego rogu do prawego górnego rogu, a nastëpnie o linië w dóî. I tak do koïca obrazka. Zakîadam, ûe analizujemy obraz o 256 stopniach szaroôci. Algorytm pozwala na obróbkë ekranu bez drugiego bufora! Wszystko odbywa sië w tym samym obszarze pamiëci! 1. Pobieramy wartoôê jasnoôci punktu. Radzë obrazek wejôciowy trzymaê w postaci "Chunky", co przyspiesza obliczenia (nie musimy dokonywaê konwersji). 2. Dublujemy sobie gdzieô (np. w innym rejestrze danych) otrzymanâ przed chwilâ wartoôê. Przyda sië przy analizie nastëpnego punktu... 3. Odejmujemy od niej wartoôê jasnoôci punktu poîoûonego bezpoôrednio po lewej stronie aktualnego punktu. Wykorzystujemy do tego wartoôê otrzymanâ w kroku pierwszym. 4. Otrzymanâ róûnicë, naleûâcâ do przedziaîu: <-256;+255>, przesuwamy o jeden bit w prawo (ze znakiem) otrzymujâc przedziaî: <-128;+127>. 5. Dodajemy do róûnicy 128, otrzymujâc wartoôê naleûâcâ do przedziaîu: <+000;+255>. 6. Zapisujemy jasnoôê punktu w miejsce, z którego pobraliômy jasnoôê poczâtkowâ w kroku pierwszym. 7. Przechodzimy do analizy nastëpnego punktu, aû do koïca obrazka. Póúniej ewentualnie dokonujemy konwersji: Chunky2Planar. Dziô uczynië wyjâtek i zamieszczë gotowâ procedurë: Emboss: ;Procedura "Emboss'ujâca" obraz. moveq #$7F,d0 ;Poczâtkowa jasnoôê (w zasadzie dowolna). moveq #$0,d1 ;Kasujemy rejestr d1. moveq #$0,d2 ;Kasujemy rejestr d2. move.w #160*128-1,d6 ;Ekran o rozmiarach 160*128, dla przykîadu... Loop: ;Gîówna pëtla. move.b (a0),d1 ;Pobieramy punkt z pod a0-adres punktu na ekranie. move.w d1,d2 ;Dublujemy go w d2. sub.w d0,d1 ;Odejmujemy poprzedniâ wartoôê jasnoôci. asr.w #1,d1 ;Dzielimy przez dwa, zmniejszajâc przedziaî. add.w #$80,d1 ;Dodajemy 128, aby otrzymaê wartoôê: <000;255>. move.b d1,(a0)+ ;Zapisujemy przeksztaîcony punkt. move.w d2,d0 ;Przepisujemy zbuforowanâ jasnoôê punktu do d0. dbf d6,Loop ;Powtarzanie pëtli. rts ;Wyjôcie z procedury. Jak widzicie, caîâ "mâdrâ" teorië sprowadziê moûemy do kilku linijek kodu maszynowego! Radzë poeksperymentowaê z podanym przeze mnie algorytmem. Czasem (na przykîad w wypadku maîych róûnic jasnoôci) nie warto przesuwaê wartoôci o bit w prawo, gdyû otrzymujemy wtedy jedynie mniej kontrastowy obraz. Polecam teû wykorzystanie funkcji Emboss (Relief Map) w wypadku efektów dynamicznych (rotator, wektorówka teksturowana itp.). Maîo wzruszajâcy jest nieruchomy obrazek, który nagle zamienia sië w pîaskorzeúbë... Przeksztaîcenia Na koniec podajë parametry przeksztaîceï, jakie zaprezentowaîem na ilustracjach. Moûna je wykorzystaê w programach majâcych funkcjë Convolution (na przykîad ImageFX). Wiëcej o podobnych macierzach napiszë za miesiâc. Ûyczë miîego "embossowania"! Przeksztaîcenie: Emboss High, macierz: 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 Przeksztaîcenie: Emboss Low, macierz: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 (***** tu rysunki (rys. 3) (rys. 4) (rys. 5) (rys. 6) (rys. 7) (rys. 8) Piszâc ten odcinek, opieraîem sië czëôciowo na informacjach, zawartych w ksiâûce pt. "Komputerowa analiza obrazu" (FotoBit Design), autorstwa Leszka Wojnara i Mirosîawa Majorka.