Widzenie Komputerowe

Widzący ludzie czerpią wiele informacji z widzenia. Ta część sztucznej inteligencji zwana "widzeniem komputerowym" (lub czasami "widzeniem maszynowym") zajmuje się nadaniem komputerom tej zdolności. Większość prac związanych z widzeniem komputerowym opiera się na przetwarzaniu dwuwymiarowych obrazów zebranych, z trójwymiarowych obrazów świata zebranych na przykład przez jedną lub więcej kamer telewizyjnych. Ponieważ obrazy są dwuwymiarowymi projekcjami trójwymiarowej sceny, proces obrazowania traci informacje. Oznacza to, że różne trójwymiarowe sceny mogą wytwarzać ten sam dwuwymiarowy obraz. Zatem problem wiernego odtworzenia sceny z obrazu jest w zasadzie niemożliwy. Jednak ludzie i inne zwierzęta radzą sobie bardzo dobrze w trójwymiarowym świecie. Wydaje się, że potrafią zinterpretować dwuwymiarowe obrazy powstałe na ich siatkówkach w sposób, który zapewnia im dość dokładne i użyteczne informacje o ich otoczeniu. Wzrok stereo przy użyciu dwojga oczu pomaga uzyskać informacje o głębi. Widzenie komputerowe również może korzystać ze 'stereopsis ", wykorzystując dwie lub więcej kamer o różnych lokalizacjach, patrząc na tę samą scenę. (Ten sam efekt można uzyskać, przesuwając jedną kamerę w różne pozycje.) Gdy używane są dwie kamery, na przykład utworzone przez nie obrazy są nieznacznie przesunięte względem siebie, a to przesunięcie można wykorzystać do obliczenia odległości do różnych części sceny. Obliczenia obejmują porównanie względnych lokalizacji na obrazach, które odpowiadają obiektom w scenie, dla których głębokość pomiary są pożądane. Ten "problem korespondencji" został rozwiązany na różne sposoby, z których jednym jest poszukiwanie wysokich korelacji między małymi obszarami na jednym obrazie z małymi obszarami na drugim. Raz "rozbieżność" położenia cechy obrazu w dwa obrazy są znane, odległość do tej części sceny, która spowodowała powstanie tej cechy obrazu, można obliczyć za pomocą obliczeń trygonometrycznych (do których nie będę tutaj wchodził.) Być może zaskakujące y, wiele informacji o głębokości można uzyskać z innych sygnałów oprócz widzenia stereo. Niektóre z tych wskazówek są nieodłączne od jednego obrazu i opiszę je w późniejszych rozdziałach. Co ważniejsze, podstawowa wiedza na temat rodzajów obiektów, które można zobaczyć na kontach odpowiada za dużą część naszej zdolności do interpretacji obrazów. Rozważmy na przykład obraz pokazany poniżej



Większość ludzi opisałaby ten obraz jako składający się z dwóch stołów, jednego długiego i wąskiego, a drugiego mniej więcej kwadratowego. Jeśli jednak zmierzysz rzeczywiste blaty na samym obrazie, możesz być zaskoczony, gdy zobaczysz, że mają dokładnie taki sam rozmiar i kształt! (Ilustracja opiera się na iluzji zwanej "przewracaniem stołu" przez psychologa Rogera Shepherda i jest adaptacją wersji Michaela Bacha ze schematu Shepherda. Jak zobaczymy, ta dodatkowa informacja składa się z dwóch rzeczy: wiedzy o procesie tworzenia obrazu w różnych warunkach oświetleniowych oraz wiedzy o rodzajach rzeczy i ich powierzchniach, które występują w naszym trójwymiarowym świecie. Gdybyśmy mogli wyposażyć komputery w tego rodzaju wiedzę, być może i oni byliby w stanie to zobaczyć.

Wskazówki z biologii

Nastąpił stały przepływ informacji tam i z powrotem między naukowcami próbującymi zrozumieć, w jaki sposób działa widzenie u zwierząt, a inżynierami pracującymi nad widzeniem komputerowym. Wczesny przykład pracy na skrzyżowaniu tych dwóch zainteresowań został opisany w artykule zatytułowanym "Co oko żaby mówi mózgowi żaby" autorstwa czterech naukowców z MIT. Kierując się poprzednimi pracami biologicznymi, Jerome Lettvin, HR Maturana, Warren McCulloch i Walter Pitts zbadali części mózgu żaby, które przetwarzają obrazy. Stwierdzili, że system wizualny żaby składał się z "detektorów", które reagowały tylko na pewne rodzaje elementów w jej polu widzenia. Miał detektory małych, ruchomych wypukłych obiekty (takie jak muchy) i nagłe przyciemnienie oświetlenia (które może być spowodowane przez zbliżającego się drapieżnika), które wraz z kilkoma innymi prostymi wykrywaczami dostarczyły żabie informacji o jedzeniu i niebezpieczeństwie. W szczególności system wizualny żaby najwyraźniej nie skonstruował kompletnego trójwymiarowego modelu sceny wizualnej. Jak napisali autorzy:

"Żaba wydaje się nie widzieć, a w każdym razie nie przejmuje się szczegółami stacjonarnych części świata wokół niej. Będzie głodował ,na śmierć ,otoczona jedzeniem, jeśli się nie porusza. Wybór jedzenia zależy od wielkości i ruchu. Skoczy, aby schwytać dowolny obiekt wielkości owada lub robaka, pod warunkiem, że porusza się jak on. Można ją łatwo oszukać nie tylko przez zwisające mięso, ale także przez każdy poruszający się mały przedmiot. Jej życie seksualne prowadzone jest za pomocą dźwięku i dotyku. Jej wybór ścieżek ucieczki odwrogów nie wydaje się być rządzony przez nic bardziej przebiegłego niż skakanie tam, gdzie jest ciemniej. Skoro jest ona równie dobra w domu na wodzie i na lądzie, dlaczego miałoby to mieć znaczenie, gdzie zapala się po skoku lub jaki konkretny kierunek obiera?"

Inne eksperymenty przyniosły dalsze informacje o tym, jak mózg przetwarza obrazy wizualne. Neurofizjolodzy David Hubel i Torsten Wiesel przeprowadzili serię eksperymentów, począwszy od około 1958 r., które wykazały, że niektóre neurony w korze wzrokowej ssaków reagowały wybiórczo na obrazy i części obrazów o określonych kształtach. W 1959 roku wszczepili mikroelektrody do pierwotnej kory wzrokowej znieczulonego kota. Odkryli, że niektóre neurony szybko czerwienieją, gdy kotowi pokazano obrazy małych linii pod jednym kątem, a inne neurony szybko czerwienią w odpowiedzi na małe linie pod innym kątem. W rzeczywistości mogliby stworzyć "mapę" tego obszaru mózgu kota, odnosząc lokalizację neuronu do kąta linii. Nazwali te neurony "prostymi komórkami" -w celu odróżnienia od innych komórek, zwanymi "komórkami złożonymi", które reagowały selektywnie na linie poruszające się w określonym kierunku. Późniejsze prace ujawniły, że inne neurony specjalizowały się w reagowaniu na obrazy zawierające bardziej złożone kształty, takie jak rogi, dłuższe linie i duże krawędzie. Stwierdzono, że podobne wyspecjalizowane neurony istniały również w mózgach małp. Hubel i Wiesel otrzymali Nagrodę Nobla w dziedzinie fizjologii lub medycyny w 1981 r. (Wspólnie z Rogerem Sperry′m za inne prace). Prace Hubela i Wiesela pomogły potwierdzić ich pogląd, że znajdowanie linii na obrazach jest ważną częścią procesu wizualnego. Jednak proste linie rzadko występują w naturalnych środowiskach, w których ewoluowały koty (i ludzie), więc dlaczego one (i my) mają neurony wyspecjalizowane w ich wykrywaniu? W rzeczywistości w 1992 r. neuronaukowcy Horacy B. Barlow i David J. Tolhurst napisali artykuł zatytułowany "Dlaczego masz detektory krawędzi?". Jako możliwą odpowiedź na to pytanie Anthony J. Bell i Terrence J. Sejnowski wykazali później matematycznie, że sceny naturalne można analizować jako ważone podsumowanie małych krawędzi, nawet jeśli same sceny nie mają wyraźnych krawędzi

Rozpoznawanie twarzy

Na początku lat sześćdziesiątych w swojej firmie w Palo Alto, Panoramic Research, Woodrow (Woody) W. Bledsoe (który później pracował nad automatycznym dowodzeniem twierdzeń na University of Texas), wraz z Charlesem Bisson i Helen Chan (później Helen Chan Wolf), opracował techniki rozpoznawania twarzy wspierane przez projekty CIA. Oto opis ich podejścia zaczerpnięty z pamiątkowego artykułu:

"Ten projekt [rozpoznawania twarzy] został nazwany człowiek-maszyna, ponieważ człowiek wyodrębnił ze zdjęć współrzędne zestawu funkcji, które następnie zostały użyte przez komputer do rozpoznania. Za pomocą GRAFACON lub RAND TABLET operator wyodrębni współrzędne takich elementów, jak środek źrenic, wewnętrzny kącik oczu, zewnętrzny kącik oczu, punkt wierzchołka wdów i tak dalej. Na podstawie tych współrzędnych obliczono listę 20 odległości, takich jak szerokość ust i szerokość oczu, od źrenicy do źrenicy. Operatorzy ci mogą przetwarzać około 40 zdjęć na godzinę. Podczas budowania bazy danych nazwisko osoby na zdjęciu było powiązane z listą obliczonych odległości i przechowywane na komputerze. W fazie rozpoznawania zestaw odległości porównano z odpowiednią odległością dla każdego zdjęcia, uzyskując odległość między zdjęciem a zapisem bazy danych. Zwracane są najbliższe rekordy."

Bledsoe kontynuował tę pracę z Peterem Hartem w SRI po odejściu z Panoramic w 1966 r. Następnie w 1970 r. na Stanfor ,student, Michael D. Kelly, napisał program komputerowy, który był w stanie automatycznie wykrywać rysy twarzy na zdjęciach i wykorzystywać je do identyfikowania ludzi. Zadaniem jego programu było, jak sam to określił,

"wybór z kolekcji zdjęć osoby wykonane kamerą telewizyjną, te zdjęcia przedstawiające tę samą osobę. . . . W skrócie, program działa poprzez wyszukiwanie lokalizacji takich elementów, jak oczy, nos lub ramiona na zdjęciach. . . . Interesującą i trudną częścią pracy opisanej w tej pracy jest wykrycie tych cech na zdjęciach cyfrowych. Metodę najbliższego sąsiada stosuje się do identyfikacji osobników po uzyskaniu zestawu pomiarów. "

Inną pionierską pracą w rozpoznawaniu twarzy był badacz wzroku Takeo Kanade, obecnie profesor na Uniwersytecie Carnegie Mellon. W przemówieniu z 2007 r. podczas jedenastej międzynarodowej konferencji IEEE na temat widzenia komputerowego zastanowił się nad swoją wczesną pracą w tej dziedzinie: "Napisałem mój program rozpoznawania twarzy w języku asemblera i uruchomiłem go na maszynie o czasie cyklu 10 mikrosekund i 20 kB pamięci głównej. Z dumą przetestowałem program z 1000 obrazów twarzy, co jest rzadkim przypadkiem w czasie, gdy testowanie przy użyciu 10 obrazów było nazywane eksperymentem na dużą skalę. " Programy do rozpoznawania twarzy z lat 60. i 70. miały kilka ograniczeń. Zazwyczaj wymagały, aby obrazy miały twarze o standardowej skali, pozie, wyrazie i iluminacji.

Komputerowa wizja trójwymiarowych obiektów stałych

System wczesnego widzenia

Lawrence G. Roberts , doktorant MIT ,student pracujący w Lincoln Laboratory był prawdopodobnie pierwszą osobą, która napisała program, który mógłby identyfikować obiekty na czarno-białych (w skali szarości) fotografiach oraz określać ich orientację i pozycję w przestrzeni. (Jego program był również pierwszym zastosowaniem algorytmu "ukrytej linii, tak ważnego w późniejszych pracach nad grafiką komputerową. Jako główny naukowiec, a później dyrektor biura ARPA ds. technik przetwarzania informacji, Roberts później odegrał ważną rolę w stworzenie ARPANETu, prekursora Internetu.) We wstępie do swojej rozprawy doktorskiej MIT z 1963 roku Roberts napisał:

"Problem maszynowego rozpoznawania danych obrazowych od dawna jest trudnym celem, ale rzadko podejmowano próby użycia czegoś bardziej złożonego niż znaki alfabetyczne. Wiele osób uważa, że badania nad rozpoznawaniem postaci byłyby pierwszym krokiem, prowadzącym do bardziej ogólnego systemu rozpoznawania wzorców. Jednak wiele prób rozpoznania postaci, w tym mojej własne, nie doprowadziły bardzo daleko. Wydaje mi się, że powodem tego jest to, że badanie abstrakcyjnych, dwuwymiarowych form prowadzi nas od technik, a nie w kierunku technik niezbędnych do rozpoznawania trójwymiarowych obiektów. Postrzeganie ciał stałych jest procesem, który może opierać się na właściwościach trójwymiarowych transformacji i prawach przyrody. Ostrożnie wykorzystując te właściwości opracowano procedurę, która nie tylko identyfikuje obiekty, ale także określa ich orientację i położenie w przestrzeni."

System Roberta najpierw przetworzył zdjęcie sceny, aby stworzyć przedstawienie rysunku linii. Następnie przekształcił rysunek linii w trójwymiarową reprezentację. Dopasowanie tej reprezentacji do zapisanej listy reprezentacji obiektów bryłowych pozwoliło jej sklasyfikować oglądany obiekt. Może również wytworzyć obraz komputerowo-graficzny obiektu, który można zobaczyć z dowolnego punktu widzenia. Naszym głównym zainteresowaniem jest sposób, w jaki Roberts przetworzył obraz fotograficzny. Po zeskanowaniu fotografii i przedstawieniu jej jako tablicy liczb (pikseli) reprezentujących wartości intensywności Roberts zastosował specjalne obliczenie, zwane później "Krzyżem Robertsa", w celu ustalenia, czy każdy mały kwadrat 2 x 2 w tablicy odpowiada część obrazu z nagłą zmianą intensywności obrazu. (Krzyż Robertsa był pierwszym przykładem czegoś, co później nazwano "operatorami gradientu"). Następnie reprezentował obraz "oświetlając" tylko te części obrazu, w których intensywność zmieniła się nagle i pozostawiając "ciemne" te części obrazu o mniej więcej jednolitej intensywności. Duże zmiany intensywności obrazu są zwykle związane z krawędziami obiektów. Tak więc operatory gradientu, takie jak krzyż Robertsa, są często nazywane "detektorami krawędzi". Program Robertsa był w stanie przeanalizować wiele różnych zdjęć ciał stałych. Skomentował, że "Cały proces rysowania obrazu do linii nie jest optymalny, ale działa na proste zdjęcia". Sukces Robertsa pobudził dalsze prace nad programami do ndingowania linii w obrazach i do łączenia tych linii w reprezentacje obiektów. Być może zagruntowane przez wybór stałych obiektów przez Robertsa, wiele późniejszych prac dotyczyło klocków zabawek (lub "cegieł", jak się je nazywa w Wielkiej Brytanii).

"Projekt Summer Vision"

Co ciekawe, Larry Roberts był studentem teorii informacji MIT, u profesora Peter Elias, nie Marvin Minsky. Ale grupa Minsky′ego wkrótce zaczęła również pracować nad widzeniem komputerowym. Latem 1966 roku matematyk i psycholog Seymour Papert, niedawno przybyły do MIT's Artifiial Intelligence Group, uruchomił "projekt letniej wizji". Jego celem było opracowanie zestawu programów, które analizowałyby obraz z "videsector" (rodzaj skanera), aby "faktycznie nazwać obiekty [takie jak kule, cylindry i bloki] poprzez dopasowanie ich do słownictwa znanych obiektów. " Jedną z motywacji tego projektu było "efektywne wykorzystanie naszych letnich pracowników do budowy znacznej części systemu wizualnego". Oczywiście problem budowy "znaczącej części układu wzrokowego" był znacznie trudniejszy niż się spodziewał Papert. Niemniej jednak projekt odniósł sukces, ponieważ rozpoczął ciągły wysiłek w badaniach komputerowych w MIT, który trwa do dziś. Po tych wczesnych próbach na MIT (i podobnych, w Stanford i SRI), badania widzenia komputerowego skupiły się na dwóch obszarach. Pierwszym było to, co można nazwać wizją "niskiego poziomu" {te pierwsze etapy przetwarzania obrazu które miały na celu zbudowanie reprezentacji obrazu jako rysunku linii, biorąc pod uwagę obraz, który był sceną zawierającą raczej proste obiekty. Drugi obszar dotyczył sposobu analizy rysunku linii jako zestawu oddzielnych obiektów, które można zlokalizować i zidentyfikowano. Ważną częścią widzenia na niskim poziomie było "przefiltrowanie obrazu", które zostanie opisane poniżej.

Filtrowanie obrazu

Pomysł filtrowania obrazu w celu uproszczenia go, korekty szumu i poprawy niektórych funkcji obrazu trwał już od dekady lub dłużej. W 1955 roku Gerald P. Dinneen przetwarzał obrazy w celu usunięcia szumu i poprawienia krawędzi. Russell Kirsch i koledzy eksperymentowali również z przetwarzaniem obrazu. (Czytelnicy, którzy zmanipulowali swoje zdjęcia cyfrowe na komputerze, skorzystali z niektórych z tych filtrów obrazu). Filtrowanie obrazów dwuwymiarowych nie różni się tak bardzo od filtrowania jednowymiarowych sygnałów elektronicznych {operacja powszechna. Być może najprostszą operacją, którą można opisać, jest "uśrednianie ", które rozmywa drobne szczegóły i usuwa przypadkowe plamki szumu. Podobnie jak we wszystkich operacjach uśredniania, uśrednianie obrazu uwzględnia sąsiednie wartości i łączy je. Weźmy na przykład tablicę obrazów pokazanych wartości natężenia na rysunku poniżej, zawierającym "okno uśredniające" 3 x 3 przedstawione pogrubioną czcionką.



Te wartości intensywności odpowiadają obrazowi, którego prawa strona jest jasna, a lewa strona jest ciemna, z ostrą krawędzią pomiędzy. (Przyjmuję konwencję, że duże liczby, takie jak 10 odpowiadają jasno oświetlonym częściom obrazu, a liczba 0 odpowiada czerni.) Operacja uśredniania przesuwa okno uśredniania na cały obraz, tak aby jego środek leżał kolejno nad każdym pikselem. Dla każdego umiejscowienia okna wartość intensywności w jego środku jest zastępowana (w wersji po przefiltrowaniu) średnią intensywnością wartości w oknie. (Proces przesuwania okna wokół obrazu i wykonywania obliczeń na podstawie liczb w oknie nazywa się splotem.) W tym przykładzie wartość 0 w środku okna zostałaby zastąpiona wartością 3,33 (być może zaokrągloną w dół do 3). Widać, że uśrednianie zaciera ostrą krawędź {z 10 zanikaniem do (zaokrąglenia) 7 zanikaniem do 3 zanikaniem do 0, gdy porusza się od prawej do lewej. Jednak intensywności w obrębie równomiernie oświetlonych regionów nie ulegają zmianie. Wspomniałem już o innej ważnej operacji filtrowania, Krzyżu Robertsa, służącej do wykrywania nagłych zmian jasności obrazu. Kolejny został opracowany w 1968 roku przez doktora, student w Stanford, Irwina Sobela. Raj Reddy nazwał go "Operatorem Sobela", który opisał to podczas kursu komputerowego w Stanford. Operator wykorzystuje dwa okna filtrowania - jedno wrażliwe na duże gradienty (zmiany intensywności) w kierunku pionowym i jedno na duże gradienty w poziomie kierunek. Pokazano je tu



Każdy z filtrów Sobela działa tak samo, jak filtr uśredniający, z tym wyjątkiem, że intensywność obrazu w każdym punkcie jest mnożona przez liczbę w odpowiedniej komórce okna filtrowania przed dodaniem wszystkich liczb. Suma wynosiłaby 0 w obszarach jednolitego oświetlenia. Jeśli pionowy filtr jest wyśrodkowany na pionowej krawędzi (prawą stroną jaśniejszą niż lewą), suma byłaby dodatnia. (Pozwolę ci pomyśleć o innych możliwościach.) Wyniki z dwóch okien filtrowania są łączone matematycznie, aby wykryć nagłe zmiany w dowolnym kierunku. Zaproponowano wiele innych bardziej złożonych i solidnych operacji przetwarzania obrazu, które wykorzystano do znajdowanai krawędzi, linii i wierzchołków obiektów na obrazach. Szczególnie interesującą z nich dla znajdowania krawędzi zaproponowali brytyjski neurolog i psycholog David Marr i Ellen Hildreth. Detektor krawędzi Marra-Hildretha wykorzystuje okno filtrowania zwane a "Laplacian of Gaussian (LoG)." (Nazwa powstaje, ponieważ operator matematyczny o nazwie "Laplacian" jest używany na krzywej w kształcie dzwonu zwanej "Gaussian", upamiętniającej dwóch słynnych matematyków, a mianowicie Pierre-Simona Laplace′a i Carla Friedricha Gaussa. Poniżej pokazano przykład liczb LoG w oknie filtrowania 9 x 9.



To okno jest przesuwane wokół obrazu, mnożąc numery obrazów i dodając je, w taki sam sposób, jak inne okna filtrowania, o których już wspomniałem. Jeśli liczby LoG są wykreślane jako "wysokości " powyżej (i poniżej) płaszczyzny, ciekawie wyglądające wyniki na powierzchni. Przykład pokazano poniżej. Ta funkcja LoG jest często nazywana, co nie jest zaskoczeniem, meksykańską czapką lub funkcją sombrero.



Marr i Hildreth użyli okna filtrowania LoG na kilku przykładowych zdjęciach. Jeden przykład wzięty z ich pracy. Zauważ, że obraz po prawej stronie ma białawe pasy otaczające ciemniejsze części obrazu. Detektor krawędzi Marra-Hildretha wykorzystuje drugą operację przetwarzania obrazu, która szuka przejścia od jasnego do ciemnego (i odwrotnie) na obrazie przetworzonym LoG, aby uzyskać ostateczny "rysunek linii", jak pokazano na rysunku



Poczyniono dalsze postępy w wykrywaniu krawędzi od czasu pracy Marra i Hildretha. Wśród obecnie najlepszych detektorów są detektory związane z jednym zaproponowanym przez Johna Canny′ego, zwanym detektorem krawędzi Canny. Jako neurofizjolog Marr był szczególnie zainteresowany tym, jak ludzki mózg przetwarza obrazy. W artykule z 1976 r. zasugerował, że pierwszy etap przetwarzania daje tak zwany "pierwotny szkic". Jak ujmuje to w podsumowaniu tego artykułu, argumentuje się, że pierwszym krokiem konsekwencji jest obliczenie prymitywnego, ale bogatego opisu zmian poziomu szarości obecnych na obrazie. Opis wyrażony jest w słowniku rodzajów zmian intensywności (KRAWĘDŹ, KRAWĘDZIE CIENIA, KRAWĘDZIE PRZEDŁUŻONE, LINIA, BLOB itp.)… Opis ten uzyskano z tablicy intensywności za pomocą technik stałych i nazywa się to szkicem pierwotnym. Marr i Hildreth przedstawili swój detektor krawędzi jako jedną z operacji, których mózg używa do wykonania pierwotnego szkicu. Stwierdzili, że ich teoria "wyjaśnia kilka podstawowych psychofizycznych odkryć i stanowi podstawę fizjologicznego modelu prostych komórek [nerwowych]". Obiecująca kariera Marra w badaniach nad wzrokiem zakończyła się, gdy w 1980 r. zapadł na raka. W ostatnich latach życia ukończył ważną książkę opisującą swoje teorie ludzkiego widzenia.

Przetwarzanie rysunków linii

Zakładając, może nieco przedwcześnie, że procedury wizji niskiego poziomu mogą wytworzyć wersję obrazu do rysowania linii, wielu badaczy przeszło do opracowania metod analizy rysunków linii do obiektów na obrazach. Adolfo Guzman-Arenas, student z AI Group Minsky′ego, skupił się na tym, jak podzielić rysunki liniowe sceny zawierającej bloki na składniki, które Guzman nazwał "body" i działał na komputerze PDP-6 grupy MIT AI. Dane wejściowe do SEE stanowiły liniowe przedstawienie sceny w kategoriach jej powierzchni, linii (gdzie dwie powierzchnie połączyły się) i wierzchołków (gdzie linie się połączyły). Analiza SEE sceny rozpoczęła się od posortowania jej wierzchołków na wiele różnych typów. Dla każdego wierzchołka, w zależności od jego rodzaju, ZOBACZ połączone powierzchnie płaskie za pomocą " links. "Połączenia między powierzchniami dowodzą, że powierzchnie te należą do tego samego obiektu. Na przykład niektóre połączenia dla sceny analizowanej przez SEE pokazano tu



ZOBACZ całkiem dobre wyniki na szerokiej gamie rysunków. Na przykład poprawnie znalazł wszystkie ciała w scenie pokazanej tu



Przez większość swojej pracy Guzman zakładał, że w jakiś sposób inne programy wygenerują potrzebne rysunki z rzeczywistych obrazów. Jak napisał w artykule opisującym swoje badania. Sama scena nie jest uzyskiwana z wizualnego urządzenia wejściowego ani z szeregu intensywności jasności. Zakłada się raczej, że miało miejsce jakieś wstępne przetwarzanie, a scena do analizy jest dostępna w formacie symbolicznym…pod względem punktów (wierzchołków), linii (krawędzi) i powierzchni (regionów).

Ponadto Guzman nie przejmował się tym, co można zrobić po podzieleniu sceny na ciała:

… nie może znaleźć w scenie "kostek" ani "domów", ponieważ nie wie, czym jest "dom". Kiedy SEE podzieli scenę na ciała, jakiś inny program będzie nad nimi pracował i zdecydował, który z nich te ciała to "domy".

Późniejsze rozszerzenia SEE, zgłoszone w ostatecznej wersji jego pracy, obejmowały pewne procedury przechwytywania obrazu. Ale obrazy były ze specjalnie przygotowanymi scenami, jakie niedawno opracował: Pierwotnie ZOBACZ pracował na ręcznie rysowanych scenach, "scenach idealnych" (rysunki linii). Później zbudował kilka drewnianych wielościanów (głównie nieregularnych), pomalowanych na czarno, starannie pomalowane krawędzie na biało, ułożył kilka z nich razem i zrobił zdjęcia scen. Zdjęcia zostały zeskanowane, znalezione krawędzie i przekazane ZOBACZ. Działało na nich całkiem nieźle. Chociaż ZOBACZYŁ raczej skomplikowane sceny, mogą także popełniać błędy i nie mogą zidentyfikować bloków z dziurami. Kolejną osobą, która zajęła się problemem artykulacji sceny, był David Huffman, profesor inżynierii elektrycznej w MIT. (Huffman był znany ze swojego wynalazku, czegoś, co nazwano "kodowaniem Huffmana", skutecznego schematu stosowanego obecnie w wielu aplikacjach obejmujących kompresję i transmisję danych cyfrowych). Huffmanowi przeszkadzało to co rozważono jako niepełną analizę Guzmana dotyczącą tego, jakie obiekty mogą odpowiadać rodzajom rysunków. Po odejściu z MIT w 1967 r., aby zostać profesorem informatyki i informatyki na Uniwersytecie Kalifornijskim w Santa Cruz, ukończył teorię przypisywania etykiet do linii na rysunkach brył trójściennych - obiektów, w których dokładnie trzy płaskie powierzchnie łączą się w każdym wierzchołku obiektu. Etykiety zależały od tego, w jaki sposób płaszczyzny mogą się łączyć w wierzchołku. Huffman zwrócił uwagę, że istnieją tylko cztery sposoby, w których trzy płaskie powierzchnie mogą połączyć się w jednym wierzchołku. Pokazano je poniżej



Oprócz tych czterech rodzajów wierzchołków scena może zawierać coś, co Huffman nazwał "węzłami T" - typy przecięcia linii spowodowane przez jeden obiekt w scenie zasłaniającej inny. Wszystko to powoduje powstanie wielu różnych rodzajów etykiet dla linii na scenie; etykiety te określają, czy linie odpowiadają krawędziom wypukłym, wklęsłym lub okluzującym. Huffman zauważył, że etykiety linii na rysunku mogą być lokalnie spójne (wokół niektórych wierzchołków), ale nadal globalnie niespójne (wokół wszystkich wierzchołków). Rozważmy na przykład słynny rysunek linii "niemożliwego obiektu" Rogera Penrose&primela pokazany tu



(Jest to niemożliwe, ponieważ żaden trójwymiarowy obiekt oglądany w "pozycji ogólnej" nie mógłby wytworzyć tego obrazu.) Żadna "prawdziwa scena" nie może mieć linii z dwiema różnymi etykietami. Max Clowes z Sussex University w Wielkiej Brytanii opracował niezależnie podobne pomysły, a schemat znakowania jest obecnie ogólnie znany jako znakowanie Huffmana-Clowesa. Następnie pojawia się David Waltz . W swojej pracy doktoranckiej na MIT z 1972 r. tezę rozszerzył o schemat znakowania linii Huffmana-Clowesa, aby umożliwić rysowanie linii scen z cieniami i możliwymi "pęknięciami" między dwoma sąsiadującymi obiektami. Ważnym wkładem Waltza było zaproponowanie i wdrożenie skutecznej metody obliczeniowej dla spełnienia ograniczenia, które wszystkie linie muszą mieć przypisaną jedną i tylko jedną etykietę (na przykład krawędź nie może być wklęsła na jednym końcu i wypukła na drugim.) Poniżej pokazano przykład rysunku linii, który program Waltza mógłby poprawnie podzielić na części



Podsumowując niektóre prace związane z przetwarzaniem rysunków linii w MIT, Patrick Winston mówi, że "Guzman był eksperymentatorem, teoretykiem Huffmana i encyklopedystą Waltzem (ponieważ Waltz musiał skatalogować tysiące skrzyżowań, aby poradzić sobie z pęknięciami i cieniami). ". W międzyczasie podobną pracę nad wyszukiwaniem, identyfikowaniem i opisywaniem obiektów w trójwymiarowych scenach wykonano w Stanford. Do 1972 r. doktor inżynierii elektrycznej Gilbert Falk mógł podzielić sceny rysunków liniowych na osobne obiekty, stosując techniki będące przedłużeniami Guzmana. A do 1973 r. doktor informatyki, Gunnar Grape dokonał segmentacji scen zawierających równoległościany i kliny przy użyciu modeli tych obiektów. Inną pracę nad analizą scen zawierających wielościany wykonał Yoshiaki Shirai podczas wizyty w AI Lab32 MIT i Alana Mackwortha w Laboratorium Psychologii Doświadczalnej na Uniwersytecie w Sussex.