Teknoloji

Hough dönüşümü: bilgisayar çizgileri oylayarak buluyor

Kabarcık odası fotoğraflarında doğan Hough dönüşümü, her pikseli oy kullanan bir seçmene çevirerek çizgi ve daireleri buluyor; işte oylamanın mantığı.

19 Kasım 20268 dk okuma
Hough dönüşümü: bilgisayar çizgileri oylayarak buluyor

Kabarcık odası denen düzenekte yüklü bir parçacık sıvının içinden geçerken ardında küçük kabarcıklardan bir iz bırakır ve bu izler fotoğraflanır. Fotoğraftaki kabarcıkların hangi doğru üzerinde dizildiğini makineye buldurmak, 1960'ların başında Paul V. C. Hough'un patentinin konusuydu; patent 1962'de verildi. Bu patent, bugün yol şeridi takibi gibi işlerde de karşımıza çıkan Hough dönüşümünün atası sayılıyor.

Tekniğin ilginç yanı, çizgiyi doğrudan "aramaması". Bunun yerine her noktaya, kendisinden geçebilecek çizgiler adına oy kullandırıyor ve en çok oyu toplayan çizgiyi birinci ilan ediyor. Bu yazıda önce bu oylamanın nasıl işlediğine, sonra Hough'un fikrini bugünkü biçimine getiren 1972 makalesine, en sonda da yöntemin sınırlarına ve nerelerde kullanıldığına bakıyoruz.

Reklam

Kabarcık odasından patente

Hough'un patenti ABD'de 3,069,654 numarasıyla, "Method and means for recognizing complex patterns" (karmaşık örüntüleri tanıma yöntemi ve araçları) başlığıyla kayıtlı. Google Patents sayfasına göre başvuru 25 Mart 1960'ta yapılmış, patent 18 Aralık 1962'de verilmiş. Metin, buluşun özellikle görüş alanından geçen atom altı parçacık izlerinin incelenmesine uygulanabileceğini söylüyor; izler yaklaşık 0,01 inç aralıklı küçük kabarcıklardan oluşuyor. Sistem karmaşık deseni doğru parçalarına ayırıyor ve koordinatları manyetik banda yazarak bilgisayar çözümlemesine hazırlıyor.

Patent bir yöntem ve bir donanım tarif ediyor. Fikri bugünkü, daha kullanışlı biçimine getiren iş ise yaklaşık on yıl sonra Stanford Research Institute'tan iki araştırmacıdan geldi.

Sorun: noktalar çok, doğrular çok daha fazla

Richard O. Duda ile Peter E. Hart, Communications of the ACM'in 1972 Ocak sayısında (cilt 15, sayı 1, sayfa 11-15) yayımladıkları "Use of the Hough Transformation to Detect Lines and Curves in Pictures" makalesine sayısallaştırılmış resimlerde düz çizgi bulmanın tekrar eden bir sorun olduğunu söyleyerek başlıyor. En basit çözüm, bütün nokta çiftlerinden geçen doğruları sınamak. Yazarlara göre n nokta için gereken hesap yaklaşık n² ile orantılı ve büyük n için engelleyici olabiliyor.

Makale, Hough'un yönteminin bu hesabı nasıl hafiflettiğini anlatıyor. Duda ve Hart, Rosenfeld'in (kaynakçada 1969 tarihli "Picture Processing by Computer" kitabı) Hough'a ait zekice bir yöntemi anlattığını yazıyor; kaynakçada Hough için patent, yani US 3,069,654 gösteriliyor. Yöntem, her nokta için parametre uzayında bir doğru çizip aynı noktadan geçen doğruları aramaya dayanıyor; böylece "aynı doğru üzerindeki noktaları bul" sorunu "kesişen doğruları bul" sorununa çevriliyor. Hough, doğruları eğim ve kesişim noktasıyla tarif etmeyi seçmişti.

Oylamanın mantığı

Benzetmeyi şöyle kurabiliriz. Bir salonda her piksel bir seçmen olsun. Seçmenin önünde, kendisinden geçen bütün olası çizgilerin listesi duruyor ve her biri için "bu çizgi benim üstümden geçiyor" diyerek bir oy pusulası bırakıyor. Salonun öbür ucunda her çizgi için bir sandık var. Aynı doğrunun üzerindeki piksellerin hepsi aynı sandığa oy atacağı için o sandık dolacak; tesadüfen bir araya gelmiş noktaların oyları ise sandıklara dağılıp kalacak. Sayım yapılınca en kabarık sandıklar, resimdeki gerçek çizgilerdir.

Bu sandıkları adreslemek için çizgiyi iki sayıyla tarif etmek gerekiyor. Duda ve Hart eğim ve kesişim parametrelerinin ikisinin de sınırsız olduğunu, dikeye yakın bir çizgide eğimin ve kesişimin keyfi olarak büyüyebileceğini yazıyor ve yerine "normal parametrelemeyi" öneriyor: çizgiye başlangıç noktasından inen dikmenin uzunluğu ρ ve bu dikmenin açısı θ. Denklem x cos θ + y sin θ = ρ. θ yarım dönüşle sınırlandırılınca her çizgi, θ-ρ düzleminde tek bir noktaya karşılık geliyor.

Sonuç güzel bir simetri: resimdeki bir nokta, parametre düzleminde bir sinüs eğrisi çiziyor; aynı doğru üzerindeki noktaların eğrileri ise tek bir noktada kesişiyor. Makale bu ilişkiyi dört özellik olarak sıralıyor; üçüncüsü, aynı doğru üzerindeki noktaların eğrilerinin ortak bir noktadan geçmesi. Böylece "aynı doğru üzerindeki noktaları bul" problemi, "kesişen eğrileri bul" problemine dönüşüyor.

Pratikte parametre düzlemi hücrelere bölünüyor. Her nokta için eğrinin geçtiği hücrelerin sayacı bir artırılıyor, bütün noktalar bittikten sonra sayısı yüksek hücrelere bakılıyor. Makaleye göre sayacı k olan bir hücre, k noktanın ilgili doğrunun (nicemleme hassasiyeti içinde) üstünde olduğunu gösteriyor. Hesap, nokta sayısıyla doğrusal artıyor: her nokta için yalnızca nicemlenmiş açı sayısı kadar doğru ele alınıyor, bütün nokta çiftleri taranmıyor.

Evde deneyebileceğiniz küçük bir hesap

Aşağıdaki küçük hesap bizim kurgumuz, makaledeki örnek değil. (1,1), (2,2) ve (3,3) noktalarını düşünün; üçü de y = x doğrusunda. Her nokta için ρ = x cos θ + y sin θ değerini dört açıda hesaplayın. 0 ve 90 derecede ρ değerleri 1, 2, 3 çıkar; 45 derecede yaklaşık 1,41, 2,83 ve 4,24. Yalnız 135 derecede üç noktanın üçü de ρ = 0 verir. Üç oyun aynı sandığa düştüğü bu tek hücre, doğrunun adresidir. Noktaların biri doğrunun dışına kayarsa bu hücrede yalnızca iki oy kalır.

Duda ve Hart'ın kutu deneyi

Yazarlar yöntemi, televizyon monitöründeki bir kutunun görüntüsünde denedi. Sayısallaştırılmış görüntüden basit bir farklandırma işlemiyle yoğunluğun belirgin değiştiği noktaları ikili bir resme çıkardılar. Verilerin ayrıntılarını makaleden aktarıyoruz:

AyarMakaledeki değer
Resim boyutu120 × 120
Açı örneklemesi20 derecelik adımlarla 9 açı
ρ ekseni86 hücre, hücre başına 2 birim
Tepe eşiği35 oy
Bulunan tepe9 yerel en büyük değer

Dokuz tepe kutunun gerçek kenarlarının bir kısmına denk geldi. Ama iki önemli çizgi bulunamadı: biri çok az nokta içerdiği için, öbürü iki açı adımının arasına düştüğü için. Üstelik makaleye göre eşiği, üst sol kenarı yakalamak için gereken 24'e indirmek anlamsız bir sahte çizgiyi de getirirdi. Yani dönüşümün verdiği cevap ayara bağlı; 20 derecelik açı adımını da yazarlar sayaç dizisi küçük kalsın diye seçtiklerini belirtiyor ve daha çok çizgi bulmak için daha ince bir adım gerekeceğini ekliyor.

Kenar algılama ile ilişkisi

Hough dönüşümü ham fotoğrafa değil, "bu piksel muhtemelen bir kenar" diye işaretlenmiş noktalara oy kullandırıyor. Duda ve Hart kendi deneylerinde bunu basit bir farklandırma ile yaptı. Bugün bu aşama için sıkça başvurulan yollardan biri, John Canny'nin 1986'da IEEE Transactions on Pattern Analysis and Machine Intelligence dergisinde (cilt 8, sayı 6, sayfa 679-698) yayımladığı "A Computational Approach to Edge Detection" çalışmasına dayanan Canny kenar algılayıcı. Canny'nin özeti, en uygun algılayıcının basit bir uygulamasında görüntünün Gauss ile yumuşatıldığını ve gradyan büyüklüğünün tepe noktalarının kenar olarak işaretlendiğini söylüyor. Wikipedia, Canny algılayıcısını kenar algılamanın en yaygın yöntemlerinden biri olarak niteliyor. Zincir böylece iki halkalı: önce kenar noktaları çıkıyor, sonra bu noktalar çizgi için oy veriyor.

Daireler ve parametre sayısının bedeli

Aynı fikir doğrularla sınırlı değil. Duda ve Hart makalenin son bölümünde daireyi (x − a)² + (y − b)² = c² olarak yazıp a, b, c üç parametresinin oluşturduğu uzayda her noktanın bir koni çizdiğini anlatıyor. Çok sayıda koni tek bir noktada kesişiyorsa, o noktanın koordinatlarıyla tarif edilen daire bulunmuş demek. Yazarlar aynı zamanda bir uyarı da düşüyor: sayaç dizisi parametre uzayının tamamını nicelediği için hesabın parametre sayısıyla üstel biçimde büyüdüğünü, bu yüzden parametre sayısının az olmasının çok önemli olduğunu yazıyor. Doğru için iki, daire için üç parametre bu yüzden iki ayrı dünya.

ŞekilParametre sayısı ve uzay
Doğru2 parametre (θ, ρ), iki boyutlu sayaç dizisi
Daire3 parametre (a, b, c), üç boyutlu sayaç dizisi

Wikipedia'nın Hough dönüşümü maddesine göre fikri keyfi şekillere genelleyen çalışma Dana H. Ballard'ın 1981 tarihli "Generalizing the Hough transform to detect arbitrary shapes" makalesi ve tekniğin bilgisayarlı görüde yaygınlaşması bu çalışmayla anılıyor.

Üç noktadan geçen farklı açılardaki doğrular ve her birine başlangıç noktasından inen dikme; Hough dönüşümünün ilk adımının çizimi
Üç noktadan geçen farklı açılardaki doğrular ve her birine başlangıç noktasından inen dikme; Hough dönüşümünün ilk adımının çizimi — Mike1024, Public domain (Wikimedia Commons)

Sınırlar: gürültü, sahte tepeler, hesap yükü

Duda ve Hart makalelerinde sınırları da açıkça sıralıyor. Sonuçlar hem θ hem ρ nicemlemesine duyarlı: daha ince hücreler daha iyi çözünürlük verir ama hesap süresini artırır ve birbirine yakın doğrulara denk gelen hücrelerin öbeklenmesi sorununu doğurur. İkincisi, teknik noktaların bitişik olup olmadığına bakmıyor; resmin başka bir yerindeki ilgisiz noktalar en uygun çizginin konumunu bozabilir ve anlamsız doğrusal gruplar da "çizgi" diye çıkabilir. Yazarlar yaklaşımın "sahne çözümlemesinde kavramsal olarak basit bir adımı hesap açısından verimli biçimde yapmanın yolu" olarak görülmesi gerektiğini söylüyor; çizgilerin bitişik olması gibi ek bilgiler varsa anlamsız sonuçları ayıklamak için kullanılabilir.

Hesap yükü için en bilinen çare, Nahum Kiryati, Yuval Eldar ve Alfred M. Bruckstein'in Pattern Recognition dergisinde (cilt 24, sayı 4, 1991, sayfa 303-316) yayımlanan "A Probabilistic Hough Transform" makalesinden geliyor. Haifa'daki Technion'dan (İsrail Teknoloji Enstitüsü) bu üç araştırmacı, görüntüdeki kenar noktalarının yalnızca rastgele seçilmiş küçük bir kısmı Hough dönüşümüne girdi olarak verilse bile başarımın çoğu zaman çok az bozulduğunu, böylece çalışma süresinin ciddi biçimde kısalabildiğini gösteriyor. Yani seçmenlerin hepsi sandığa gitmiyor; küçük bir örneklem oy kullanıyor. Bu fikir "olasılıksal Hough" adıyla anılıyor.

Bugün nerede kullanılıyor?

Kullanım alanlarından biri yol şeritleri. Bristol Üniversitesi'nden David Hanwell ve Majid Mirmehdi, ICPRAM 2012 konferansında sundukları "Detection of Lane Departure on High-Speed Roads" çalışmasında, hızlı yollarda şeridi izleyip sürücüyü yanlışlıkla şerit değiştirmeye karşı uyaran bir sistem anlatıyor. Özetlerine göre sistem, klasik Hough dönüşümünün, ortak bir kaybolma noktası olan yol çizgilerini bulmaya uygun yeni bir türevini basit bir şerit modeli ve genişletilmiş Kalman süzgeciyle birleştiriyor; veri Jaguar Land Rover'ın deneysel bir aracından alınmış. Burada dönüşüm tek başına yetmiyor: kameraya özgü bilgi (kaybolma noktası) ve zaman içinde izleme sürece katılıyor.

Ultralytics'in Türkçe sözlüğü ise Hough dönüşümünün bilgisayarlı görüdeki kullanımına sudoku gibi ızgara çizgilerinin çıkarılmasını, çelik kiriş geometrisinin ölçülmesini, madeni para gibi dairesel nesnelerin bulunmasını ve belgelerde tablo sınırlarının çıkarılmasını sayıyor. Hackaday'in bu hafta yayımlanan yazısı da tekniğin saf biçiminin gerçek sahnelerde yavaş kaldığını ve gürültüyü daha iyi karşılayan iyileştirmelerin bu yüzden geliştirildiğini anlatıyor.

Açık soru

Duda ve Hart'ın 1972'de gösterdiği eşik ikilemi, yani "kaç oy bir çizgi sayılır?" sorusu makalede açıkça görülüyor: eşik düşünce sahte çizgiler çıkıyor, yükselince gerçek çizgiler gözden kaçabiliyor. Hanwell ve Mirmehdi'nin şerit sistemi ise dönüşümü kaybolma noktası ve zaman içinde izleme gibi başka bilgilerle destekliyor. Açık kalan soru şu: oylama tek başına yeterli olmadığında, hangi ek bilgi hangi sahnede ona en iyi eşlik eder? Bunu her uygulama kendi verisiyle yeniden ölçmek zorunda.

Fotoğraf: ENERGY.GOV, Public domain, Wikimedia Commons

Haberi beğendin mi?
PaylaşWhatsAppXFacebook
Teknoloji Masası

Bu içerik, Yudum Teknoloji Masası editör ekibi tarafından derlenip yayına hazırlanmıştır. Güncel gelişmeler için haber akışını takip edebilirsiniz.

Reklam
50,4455,3466,55İstanbul16°

Yudum Dünyası

Kaf Dağı'nın eteğinde bir köy var.

Karakterini yarat, meydanda dolaş, buradakilerle yüz yüze tanış. Tarayıcında, ücretsiz.

  • 🧑 Karakterini yarat
  • 🎲 Kahvede bir el at
  • 🏠 Grubunla ev kur
Günün testiAlışveriş tipin ne?Kampanya avcısı mısın, listeci mi, anlık mı? Altı soruda alışveriş huyunu söylüyoruz — sonunda küçük bir…
Günün burcuAkrepBugün Akrep burcu için içsel gücünüzün ve sezgilerinizin ön plana çıktığı, kendinizi daha net ifade…

Günün sorusu

"Çalıkuşu" romanının yazarı kimdir?

Haftanın düellosu
Yudum DünyasıKaf Dağı'nın eteğinde bir köy seni bekliyor.Ücretsiz katıl →