Szybkie metody dopasowywania obrazów w stereowizji.pdf

Politechnika Wrocławska

Wydział Elektroniki

Instytut Cybernetyki Technicznej

Praca magisterska

Szybkie metody dopasowywania obrazów

w stereowizji

Autor:

Olaf Burdziakowski

Opiekun: dr Marek Wnuk

Wrocław 1999

1. Szybkie metody dopasowywania obrazów w stereowizji

1.1 Sprecyzowanie tematu

W chwili podjęcia pracy (luty 1998) temat był określany w następujący sposób:

„Należy przeanalizować znane metody dopasowywania obrazów pod kątem ich

realizacji sprzętowej i przetwarzania równoległego, a następnie zaimplementować i zbadać

wybrane ich elementy. Można wykorzystać komputer wizyjny IC40 z magistralami VME i VIB,

programowane filtry linowe IMSA110 i uniwersalne układy logiczne (FPGA).”

Wymienione możliwości sprzętowe wynikały z istniejących w laboratorium robotyki

elementów systemu wizyjnego. Już w trakcie prac, w związku z kolejnymi wynikami, dzięki

finansowaniu z grantu KBN, aparatura została wzbogacona o wieloprocesorowy system DSP,

co umożliwiło implementację algorytmu stereowizji w sposób równoległy.

1.2 Cel pracy

Celem pracy jest stworzenie systemu wizyjnego, dostarczającego danych potrzebnych

do lokalizacji w nieznanym, zmiennym środowisku. System powinien pozwalać na nawigację

robotom poruszającym się z prędkościami zbliżonymi do tych, w jakich funkcjonują ludzie.

System powinien, na podstawie obrazu z kamer, generować mapę głębi obrazu w

możliwie krótkim czasie.

1.3 Wyzwania związane z przetwarzaniem obrazu

Przetwarzanie obrazu jest zadaniem bardzo pracochłonnym ze względu na:

• Ilość danych - np. dla obrazu 320x240 punktów przy dziesięciu podwójnych obrazach na

sekundę daje 1,28MB na sekundę danych wejściowych i tyle samo wyjściowych. Dane te

trzeba umieć odebrać, zapamiętać, przetworzyć i wysłać.

• Skomplikowanie algorytmów. Jak bardzo skomplikowane jest przetwarzanie obrazu

można sobie wyobrazić, uświadamiając sobie fakt, że, według aktualnego stanu wiedzy,

prawie połowa mózgu ludzkiego zajmuje się szeroko pojętym przetwarzaniem obrazu. Nie

istnieją aktualnie urządzenia mogące równać się mocą obliczeniową z ludzkim mózgiem,

więc wymagania stawiane systemom wizyjnym, powinny być odpowiednio mniejsze.

1.2

1.4 Dobór sprzętu do postawionych zadań

1.4.1 Jednostka obliczeniowa

Przy generowaniu mapy głębi obrazu jest możliwie wykorzystanie obliczeń

równoległych. Dlatego warto się zastanowić nad wykorzystaniem procesorów do tego

przystosowanych.

Zaletą pojedynczych jednostek obliczeniowych jest prostsza (w porównaniu z

równoległymi) architektura, programowanie, niższa cena. Obserwując postęp w dziedzinie

mikroprocesorów można dojść do wniosku, iż lepiej poczekać rok czy dwa na szybszy

procesor, niż trwonić czas i pieniądze na inwestycje w procesory równoległe.

Odpowiadając na przedstawione argumenty warto podkreślić, że wymagania

nakładane na systemy wizyjne zaniża się ze względu na możliwości sprzętowe. Rozwój

mikroprocesorów może się nagle zatrzymać, przecież gdzieś istnieje granica „podkręcania”

zegarów, choć nikt nie wie gdzie. Podstawową wadą zwiększania wydajności przez

przyspieszenie zegara procesora, jest uzależnienie postępu wyłącznie od rozwoju technologii

półprzewodnikowej. Ponadto, zwiększanie częstotliwości występujących w układach, stoi w

bezpośredniej sprzeczności z wymogami EMC ( Electromagnetic Compatibility ) zarówno w

związku z generowaniem zakłóceń, jak i odpornością na nie.

Z drugiej strony, wzrost mocy obliczeniowych procesorów nie przeszkadza - dopełnia

-prowadzone badania, w dziedzinie optymalizacji ideowej i sprzętowej algorytmów.

Gdybyśmy nawet posiadali układ zdolny podołać stawianym zadaniom, to system

wizyjny obliczający mapę głębi obrazu, zapewne będzie tylko jedną ze składowych

rozbudowanego systemu percepcji, a ten z kolei może być jednym z modułów przetwarzania

w robocie, więc i tak potrzebna jest architektura pozwalająca na rozbudowę.

Na temat ceny warto dodać, że istnieją procesory sygnałowe przystosowane do pracy

równoległej w cenach zbliżonych do pospolitych procesorów. Wzrost wydajności przy

połączeniu dwóch procesorów może nie jest satysfakcjonujący, ale przy czterech, ośmiu...

1.4.2 Zasoby procesorów

Po wyborze procesorów równoległych, trzeba zdecydować się na konkretną jednostkę.

Zanim podejmie się taką decyzję, trzeba zdawać sobie sprawę z tego, iż zadanie nie da się

podzielić na dowolnie małe, niezależne kroki. Istnieje pewne minimum zasobów, które należy

umieścić na jednej jednostce obliczeniowej:

• wystarczająca ilość pamięci, potrzebnej do wykonania podstawowego zadania;

• wystarczająca prędkość potrzebna do wykonania algorytmu;

• wystarczająca prędkość komunikacji między procesorami, potrzebna do koordynacji

działań i przesyłania obrabianych danych;

• wystarczająca prędkość wymiany danych ze światem zewnętrznym.

1.3

1.5 Wybór algorytmu

W przypadku stereowizji dwukamerowej, mapę głębi tworzy się na podstawie

rozbieżności zobrazowania ( disparity ) obiektu na dwuwymiarowych obrazach z obu kamer.

Mapę rozbieżności można tworzyć na kilka sposobów:

• Najpierw rozpoznając obiekty na obrazach lewym i prawym, następnie próbując je

skorelować ze sobą. Ta metoda, w przypadku popranej identyfikacji, daje lepsze wyniki

(nie zaszumione) od pozostałych, ponadto dostarcza dodatkowych danych o obrazie.

Niestety identyfikacja obiektów jest bardzo skomplikowana, aby rozpoznawać dobrze

należałoby posiadać jakąś bazę wiedzy, przeglądać ją, uaktualniać w nowym środowisku.

Ten sposób jest praktycznie niewykonalny.

• Można, modyfikując poprzednią metodę, wydzielać tylko wybrane cechy obrazu (np.

krawędzie, proste figury geometryczne, koncentracje barw...), a następnie próbować

dopasować je na obu obrazach. Ta metoda jest wykonalna, niestety przy bardziej

skomplikowanych obrazach może zawodzić, a ponadto trudno ją zrównoleglić.

• Kolejna metoda znacznie różni się od poprzednich. Zakłada ona, iż kamery są dobrze

skalibrowane. Wtedy każda n-ta linia obrazu lewego odpowiada n-tej linii obrazu prawego.

Znajdując dopasowanie pikseli jednej linii do drugiej, tworzy się mapę głębi obrazu. To

podejście jest niezależne od zawartości obrazu oraz pozwala stosunkowo łatwo się

zrównoleglić.

Ze względu na opisane właściwości, wybrany został trzeci z wymienionych sposobów,

uwzględniający implementację równoległą.

1.6 Połączenie algorytmu z możliwościami sprzętowymi

Należy dobrać wymagania algorytmu do możliwości sprzętowych i odwrotnie. Ta

interakcja powinna być uwzględniana zarówno podczas zakupu sprzętu, jak i w trakcie

implementacji. Np. szerokość obrazu powinna być możliwie duża, ale ograniczona ze

względu na złożoność algorytmu i zasoby procesora. Aby podołać tym rekurencyjnym

zależnościom, dokonano zakupu kontrolnego, w celu przetestowania możliwości

sprzętowych, a dopiero po uwzględnieniu wyników testu zdecydowano się na całościowy

zakup. Wyniki tego rozpoznania są omówione w dalszej części pracy.

1.7 Opis ideowy systemu wizyjnego

1.7.1 Opis algorytmu

Podstawowym założeniem jest poprawne skalibrowanie układu kamer [1]. Jeżeli ten

warunek jest spełniony, to każda n-ta linia obrazu lewego, odpowiada n-tej linii obrazu

prawego [2,3], co obrazuje rysunek 1.

1.4

n-ta linia obrazu lewego

n-ta linia obrazu prawego

Obraz lewy

Obraz prawy

Rysunek 1. Odpowiadające sobie linie obrazu lewego i prawego.

Dalej algorytm opisany jest dla dwóch linii. Wszystkie pary linii traktowane są w ten sam

sposób.

Należy znaleźć przypisanie punktów jednej linii do punktów drugiej. Dopasowanie to

powinno być monotoniczne, tzn. nie powinno zawierać przyporządkowań wzajemnie się

przecinających. Przykład poprawnego przyporządkowania przedstawia rysunek 2.

n-ta linia obrazu lewego

n-ta linia obrazu prawego

Rysunek 2. Przykład dopasowania dwóch linii

Osie optyczne kamer

Odwrócona kolejność

Obraz

Baza

Prosta przecinająca bazę

Rysunek 3. Przykład odwrócenia kolejności obiektów na obrazach.

Kamera prawa

1.5

Kamera lewa

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: