dijital topoloji | Topolojik bir oluşum!

Bir oyun oynuyoruz ve topolojinin ilerlemesine katkıda bulunuyoruz. Oyunumuzun ismi Nice Neighbors.

Chris Staecker tarafından tasarlanmış olan bu oyun, yukarıda gördüğünüz gibi dairelerin içinde bulunan bazı noktalar ve bunları birleştiren çizgilerden oluşuyor. Yapmanız gereken, mavi noktaları birbirlerinin üstüne taşımak (dikkat edelim: dairelerle birlikte değil, sadece noktaları taşımak) ama tabii öyle rastgele değil. İşte kurallar: Noktaları yalnızca onlara bitişik olan bir noktaya taşıyabilirsiniz, yani noktalar evlerinden yalnızca bir nokta kadar uzağa gidebilirler. Ayrıca bunu yaparken tüm çizgilerin mavi kalmasına dikkat etmeniz gerekiyor. Kırmızı bir çizgi ile karşılaşıyorsanız yanlış bir hamle yapıyorsunuz demektir. Kazanmak için oyun sonunda ez az bir dairenin boş kalması ve tüm çizgilerin mavi olması gerekiyor.

Hemen denemek isteyenleri buraya alalım ve oyunun altında yatan matematiksel gerçekleri ve Staecker’ın oyunu tasarlama amacını anlamaya çalışalım.

Öncelikle oyun dijital topoloji ile ilişkili olduğundan, burada anlatılan bazı kavramlara ihtiyacımız olacak. Bu nedenle kısaca bir göz gezdirmekte fayda var.

$X$ bir dijital görüntü olsun. Eğer aşağıdaki özelliklere sahip bir $f:X\rightarrow X$ fonksiyonu varsa $X$ indirgenebilirdir (reducible) denir:

(a) $f$ örten değildir.
(b) Her $x\in X$ pikseli için $x$ ile $f(x)$ bitişiktir.
(c) Eğer $x$ ve $y$ bitişik ise $f(x)$ ve $f(y)$ de bitişiktir.

Böyle bir $f$ fonksiyonu yoksa, $X$ görüntüsü indirgenemezdir (irreducible) denir.

Yukarıda verilen iki dijital görüntüyü ele alalım. (Soldaki görüntüde 4-bitişiklik, sağdakinde ise 8-bitişiklik kullanıldığına dikkat edelim.) Olası tüm indirgemeler yapıldığında, son halleri aşağıdaki iki indirgenemez görüntü olacaktır. Bunu yaparken görüntünün topolojisinin değişmediğine, yani delikler (holes) ve bağlantılılık (connectivity) ile ilgili özelliklerinin aynı kaldığına dikkat edelim.

Eğer $f$ ‘yi, Nice Neighbors oyunundaki gibi, bir çizgenin köşelerini yeniden düzenleyen bir dönüşüm olarak düşünürsek, yukarıdaki koşulların şu anlama geldiğini görebiliriz:

(a’) Yapacağınız hamle sonrasında en az bir köşe noktası boş kalmalıdır.
(b’) Her nokta sadece bitişiği olan bir noktaya taşınabilir.
(c’) İki bitişik köşe, yaptığınız hamle sonrasında da bitişik olarak kalmalıdır.

Staecker ve öğrencileri hangi çizgelerin indirgenebilir, hangilerinin indirgenemez olduğu sorusuna yanıt bulmak istiyorlardı. Bunu yaparken, “verilen bir çizgenin bir dijital görüntünün çizgeleştirilmiş hali olup olmadığı” açık sorusuna hiç bulaşmamak için tüm çizgeleri ele alma yolunu seçmişlerdi. İşte oyunun tasarlanma amacı da buydu. (İlham kaynağının, John Tantalo’nun, amacı bir çizgeyi düzlemsel hale getirmek olan Planarity oyunu olduğunu belirtmekte fayda var.) Nice Neighbors’da kazanılan her çizge, o çizgenin indirgenebilir olduğunun ispatıdır. (a’) ve (b’) özellikleri zaten oyunun kuralları arasındadır. Hata yaptığınızı gösteren kırmızı çizgi ise aslında (c’) özelliğinin sağlandığını garanti eder. Nasıl mı?

Soldaki çizge ile işe başladığımızı varsayalım. Ortadaki çizgedeki kırmızı çizgi, aslında bitişik olması gereken iki noktanın, yaptığımız hamle sonrasında bitişik olmayacağı konusunda bir uyarıdır. Yani bu hamleyi yaparsak (c’) koşulu sağlanmamış olur. Fakat en sağdaki çizge, her 3 koşulu da sağladığından soldaki çizgenin indirgenmiş halidir.

Oyun oldukça işe yaramış ki, 2 ay içerisinde 9 noktaya kadar olan indirgenemez grafiklerin bir listesini çıkarmayı başarmışlar.

“İyi matematik sadece cevapları bulmakla değil, onları açıklamakla da ilgilenir. Cevapları bulmuş olmak benim için tatmin edici, ancak bu cevapların neden doğru olduğunu hala anlamadığım hissinden kurtulamıyorum. Umarım birileri bir gün her şeyi çözer.“

diyor Staecker. İşte bu da, bu konular üzerinde çalışmaya hevesli olanlar için bir çağrı niteliğinde olsun.

Kaynaklar
1) P. Christopher Staecker, Nice Neighbors: A Brief Adventure in Mathematical Gamification, Math Horizons 23(4), 5-7, 2016.

Görüntü işleme günümüzde hızla gelişen teknolojilerden biridir ve fotoğraf veya belgelerin taranıp dijital ortama aktarılmasından tutun da yüz tanıma sistemleri, radar, astronomi ve radyolojiye kadar uzanan geniş bir kullanım alanı vardır. Dijital topoloji, dijital görüntülerin topolojik özelliklerinin incelenmesine dayanan ve inceltme (thinning), bağlantılı bileşen etiketleme (connected component labeling) gibi görüntü işleme tekniklerine matematiksel bir temel sunan bir alandır. Bu yazıda, ikili görüntü dizileri için bu topolojik fikirlerin nasıl uygulanabileceğinden bahsedeceğiz. İkili görüntü dizileri, grilik seviyesindeki (grayscale) bir görüntüden eşikleme (tresholding) yöntemi ile elde edilir. Yani kabaca, arka planın ve arka plandan ayrılmak istenen nesnenin gri ton seviyesi hakkında edinilen bilgiye göre bir eşik değeri belirlenir ve daha sonra bu değerin altındaki gri seviyelerine 0, üstündekilere ise 1 değeri atanır. (Dijital topolojinin bir genelleştirmesi olan bulanık dijital topolojide bu değerler $[0,1]$ aralığında değişebilir.)

İki boyutlu bir dijital görüntüde her piksel bir latis noktası (yani koordinatları tam sayı olan bir nokta) ile ilişkilendirilebilir. Yani iki boyutlu bir dijital görüntü $\mathbb{Z}\times \mathbb{Z}$ ‘nin sonlu bir alt kümesi olarak düşünülebilir. Bir $p=(x,y)$ latis noktası için, $p$ ‘nin 4-komşularının kümesi,

$N_4(p)=\{(x-1,y),(x+1,y), (x,y-1), (x,y+1)\}$

biçiminde; 8-komşularının kümesi ise,

$N_8 (p)=N_4 (p)\cup \{(x-1,y-1),(x+1,y+1), (x-1,y+1), (x+1,y-1)\}$

biçiminde tanımlıdır.

Eğer $q\in N_n (p)$ $(n=4,8)$ ise, $q$ ile $p$ noktaları n-bitişiktir denir. Eğer birbirine n-bitişik olan $s_1\in S_1$ ve $s_2\in S_2$ noktaları varsa, $S_1$ ve $S_2$ kümeleri n-bitişiktir (n-adjacent) denir.

Tanım: S latis noktalarının bir kümesi olsun.
(1) Eğer S, birbirine n-bitişik olmayan iki altkümeye bölünemezse, S kümesi n-bağlantılıdır denir.
(2) S’nin herhangi diğer bir noktasına n-bitişik olmayan n-bağlantılı, boştan farklı bir alt kümesine, S’nin n-bileşeni denir.

Yukarıdaki küme 8-bağlantılı bir kümedir çünkü birbirine 8-bitişik olmayan iki altküme bulmak mümkün değildir. Ayrıca bu kümenin, farklı renklerle gösterilmiş olan 3 tane 4-bileşeni vardır. (Örneğin siyah noktalardan oluşan altküme, hem 4-bağlantılıdır hem de diğer renklerdeki hiçbir noktaya 4-bitişik değildir. Bu nedenle kümenin 4-bileşenlerinden biridir.)

İki boyutlu dijital resim tanımını vermeden önce, bir dijital resimdeki nokta türlerinden ve bunların arasındaki ilişkilerden söz edelim.

Tanım: Değeri 1 olan bir piksele karşılık gelen bir latis noktasına siyah nokta; değeri 0 olan bir piksele karşılık gelen bir latis noktasına ise beyaz nokta denir.

Dijital topolojide beyaz ve siyah noktalar için farklı bitişiklik türleri kullanılır. Örneğin, beyaz noktalar için 8-bitişiklik kullanılıyorsa (yani, iki beyaz noktanın bitişik olması, 8-bitişik olmaları anlamına geliyorsa), siyahlar için 4-bitişiklik kullanılır. Ya da tersine, siyahlar için 4-bitişiklik kullanılıyorsa beyazlar için 8-bitişiklik kullanılır. Bunun sebebi, her iki nokta türü için aynı bitişiklik bağıntısı kullanıldığında paradoks ortaya çıkmasıdır. Bu durumu aşağıdaki şekil üzerinden açıklayalım.

Tüm noktalar için 8-bitişiklik bağıntısını kullandığımızı kabul edersek, siyah noktalar kümesi ve beyaz noktalar kümesinin bağlantılı olduğunu söyleyebiliriz. Bu durumda sanki elimizde siyah noktalardan oluşan bir Jordan eğrisi varmış gibi düşünürsek, bu eğrinin beyaz noktalar kümesinin bağlantılılığını bozmaması, yani düzlemi iki parçaya ayırmaması matematiksel bir paradoksa yol açar.

Şimdi de tüm noktalar için 4-bitişikliği kullandığımızı kabul edelim. Bu durumda siyah noktalar kümesi tamamen bağlantısız olur çünkü, hiçbir siyah nokta birbirine bağlantılı olmadığından kümenin tüm bağlantılı bileşenleri tek nokta kümeleridir. Beyaz noktalar kümesinin ise iki tane bağlantılı bileşeni vardır. (Bunlardan biri siyah noktalar ortasındaki tek beyaz noktadan oluşan kümedir.) Burada tamamen bağlantısız bir küme, beyaz noktalar kümesini ayırmış oldu ki bu da mantığa aykırı bir durum. (Yani kabaca, siyah noktalar arasında boşluklar varmış ama yine de beyazlar birbirinden ayrılıyormuş gibi düşünebiliriz.)

Tanım: $\mathcal{P}=(\mathbb{Z}^2,m,n,B)$ dörtlüsüne iki boyutlu dijital resim (ya da (m,n) dijital resim) denir. Burada, $B\subseteq \mathbb{Z}$ , $(m,n)=(8,4)$ ya da $(m,n)=(4,8)$ ‘dir. $B$ ‘nin noktaları siyah noktalar, $\mathbb{Z}^2 \setminus B$ ‘nin noktaları ise beyaz noktalar olarak adlandırılır.

(Yukarıdaki tanımda kabaca, $B$ kümesi görüntüdeki nesne, $\mathbb{Z}^2 \setminus B$ ise arka plan olarak düşünülebilir.)

$\mathcal{P}$ ‘de iki siyah nokta için m-bitişiklik; iki beyaz nokta ve bir beyaz bir siyah nokta için ise n-bitişiklik kullanılır. (Yani örneğin bir beyaz ve bir siyah noktanın bitişik olması, onların n-bitişik olması anlamına gelir.)

*Bir (4,8) dijital resimde bitişik noktalar*

S kümesi, siyah ve/veya beyaz noktalardan oluşan bir küme olsun. Eğer S, birbirine bitişik olmayan iki kümeye ayrılamıyorsa, S kümesi bağlantılıdır denir. S’nin herhangi bir diğer noktasına bitişik olmayan, bağlantılı, boştan farklı bir alt kümesine, S’nin bir bileşeni denir. Tüm siyah noktalar kümesinin bir bileşeni siyah bileşen; tüm beyaz noktalar kümesinin bir bileşeni ise beyaz bileşen olarak adlandırılır.

$X$ ve $Y$ , $\mathcal{P}$ ‘de birer noktalar kümesi ve $X$ bağlantılı olsun. Eğer $Y$ ‘nin her noktası $V\setminus X$ ‘in sonlu bir bileşeni tarafından içeriliyorsa $\bf{X}$ , $\bf{Y}$ ‘yi çevreler (X surrounds Y) denir.

C bir siyah bileşen olsun. C’ye bitişik ve C ile çevrelenmiş olan bir beyaz bileşene C’de bir delik (hole) denir. Dijital resimde bir siyah bileşen bir nesneye, delikler ise o nesnedeki deliklere karşılık gelir.

Yukarıdaki şekli bir (8,4) dijital resim olarak düşünürsek siyah bileşenin iki deliği olacaktır. (Dikkat edersek, beyaz noktalar için 4-bitişiklik bağıntısı kullanıldığından, siyah bileşenin içinde kalan beyaz noktaların kümesi bağlantılı değildir ve iki bileşenden oluşur.) Fakat aynı şekil bir (4,8) dijital resim olarak düşünüldüğünde siyah bileşenin yalnızca bir deliği olur. (Çünkü bu kez, beyaz noktalar için 8-bitişiklik bağıntısı kullanıyoruz ve bu nedenle içeride beyaz noktalar tek bir bileşenden oluşuyor.)

Hiçbir siyah noktaya bitişik olmayan bir siyah nokta izole nokta olarak adlandırılır. Bir ya da daha fazla beyaz noktaya bitişik olan bir siyah noktaya sınır noktası, sınır noktası olmayan bir siyah noktaya ise iç nokta denir. Bir siyah bileşenin sınırı (sırasıyla, içi) tüm sınır (sırasıyla, iç) noktalarının kümesine eşittir.

(4,8) dijital resimde p ve q izole noktalar iken, (8,4) dijital resimde yalnızca p bir izole noktadır.

Yukarıda şekilde kare ve halka ile çevrili olan noktalara bakalım. Eğer bir (8,4) dijital resim üzerinde çalışıyorsak, sadece kare ile çevrili noktalar sınır noktası olacaktır. Fakat bir (4,8) dijital resim üzerinde çalışıyorsak, bir beyaz ve bir siyah nokta için 8-bitişiklik bağıntısı kullanıldığı için hem halka hem de kare ile çevrili noktalar birer sınır noktası olur.

$\mathcal{P}=(\mathbb{Z}^2,m,n,B)$ bir dijital resim olsun. Bu durumda $D\subseteq B$ olmak üzere, $\mathcal{P}$ ‘den $D$ ‘deki noktaların silinmesiyle elde edilen dijital resim $\mathcal{P}^\prime=(\mathbb{Z}^2,m,n,B\setminus D)$ ‘dir. (Diğer bir ifadeyle, $\mathcal{P}$ dijital resmi $\mathcal{P}^\prime$ resmine $D$ ‘deki noktaların eklenmesiyle elde edilir.)

Peki, elimizdeki dijital resmin topolojisini koruyacak şekilde bir nokta silme işlemi nasıl yapılmalıdır? Bunun için önce aşağıdaki kavramlara bir bakalım.

Bir şeklin iskeleti (ya da, topolojik iskeleti), o şeklin, sınırlarından eşit uzaklıkta olan ince bir halidir.

Görüntü inceltmenin amacı, dijital resmin siyah noktaları kümesini bir iskelete indirgemek ve bunu yaparken şeklin topolojisini korumaya dikkat etmektir. (Görüntü inceltmeye topolojik olmayan yaklaşımlar da yapılmıştır.) Stefanelli ve Rosenfeld yaptıkları çalışmada dijital resmin topolojisini koruyan (yani, bir siyah bileşeni iki ya da daha fazla parçaya bölmeyen, ortaya yeni bir beyaz bileşen çıkmasına veya iki beyaz bileşenin birleşmesine sebep olmayan) algoritmalar geliştirmişlerdir.

Bunu yaparken ise aşağıdaki kriteri kullanmışlardır:

(*) $\mathcal{P}=(\mathbb{Z}^2,m,n,B)$ bir dijital resim olsun. Bir $D\subseteq B$ altkümesindeki noktalar silindiğinde, resmin topolojisinin korunması için gerek ve yeter koşul aşağıdaki özelliklerin sağlanmasıdır:
1) $\mathcal{P}$ nin her siyah bileşeni, $\mathcal{P}^\prime$ nün sadece bir siyah bileşenini içerir.
2) $\mathcal{P}^\prime$ nün her siyah bileşeni $\mathcal{P}$ nin sadece bir beyaz bileşenini içerir.
(Burada $\mathcal{P}^\prime=(\mathbb{Z}^2,m,n,B\setminus D)$ olduğunu hatırlayalım.)

p bir siyah nokta olmak üzere, eğer p’nin silinmesi dijital resmin topolojisini koruyorsa (yani kriter (*)’da verilen koşullar sağlanıyorsa), p’ye bir basit nokta denir. Demek ki p’nin bir basit nokta olması için gerek ve yeter koşul p silindiği zaman siyah bileşenlerin ve beyaz bileşenlerin sayısının değişmemesidir. Basit noktaların aşağıdaki karakterizasyonu hem (8,4) hem de (4,8) dijital resimler için geçerlidir.

Teorem 1: $\mathcal{P}=(\mathbb{Z}^2,m,n,B)$ bir (8,4) ya da (4,8) dijital resim, p izole olmayan bir sınır noktası ve $B^\prime=B\setminus \{p\}$ olsun. Bu durumda aşağıdakiler denktir:
(1) p bir basit noktadır.
(2) p noktası, $N(p)\cap B^\prime$ kümesinin sadece bir bileşenine bitişiktir.
(3) p noktası, $N(p)\setminus B$ kümesinin sadece bir bileşenine bitişiktir.
(Burada $N(p)=N_8 (p)\cup \{p\}$ biçiminde tanımlıdır.)

Şimdi Teorem 1’i kullanarak yukarıdaki dijital resimde p noktasının basit nokta olup olmadığını inceleyelim. İlk olarak bir (8,4) dijital resim üzerinde çalıştığımızı düşünelim. $N(p)\cap B^\prime$ kümesi aslında p’nin tüm siyah 8-komşularının kümesidir ve siyah noktalar için 8-bitişiklik kullanıldığı için bu küme bağlantılıdır. O halde (2) koşulu sağlanır ve p bir basit noktadır. Fakat aynı şekli bir (4,8) dijital resim olarak ele alırsak p bir basit nokta olmaz. Bunu da (3) koşulu üzerinden görmeye çalışalım. Öncelikle $N(p)\setminus B$ kümesinin, p’nin tüm beyaz 8-komşularının kümesi olduğunu söyleyebiliriz. Bu küme iki bileşenden oluşur ve bir beyaz bir siyah nokta için 8-bitişiklik kullanıldığından, p her iki bileşene de bitişiktir yani (3) koşulu sağlanmaz. Dikkat edersek burada p’nin silinmesi aslında iki beyaz bileşenin birleşmesine sebep olarak dijital resmin topolojisini bozuyor.

Son olarak bir algoritmanın topolojiyi koruması için yeterli koşulun ne olması gerektiğini ifade eden bir teoremle konuyu noktalayalım. Bunun için kuzey sınır noktası ve bitiş noktası kavramlarına ihtiyacımız olacak.

p=(x,y) bir siyah nokta olsun. Eğer (x,y+1) noktası bir beyaz nokta ise p’ye bir kuzey sınır noktası denir. Sadece bir siyah noktaya bitişik olan siyah noktaya bitiş noktası denir.

Teorem 2: $\mathcal{P}=(\mathbb{Z}^2,m,n,B)$ bir (8,4) ya da (4,8) dijital resim olsun. Bu durumda bitiş noktası olmayan basit kuzey sınır noktalarının (paralel) silinmesi dijital resmin topolojisini korur.

Yukarıdaki (8,4) dijital resimde halka içindeki noktalar teoremin koşullarını sağlar. Bu noktalardan herhangi sayıda silindiğinde kriter (*)’da verilen koşulların sağlandığını yani topolojinin korunduğunu kolayca görebiliriz.

Teorem 2 sadece kuzey değil; doğu, batı ve güney sınır noktaları için de geçerlidir. (Doğu, batı ve güney sınır noktalarını tanımlarken, kuzey sınır noktası tanımındaki (x,y+1) noktasını, sırasıyla, (x+1,y), (x-1,y), (x,y-1) noktaları ile değiştirmek yeterlidir.) Fakat nokta sadece bir yönden silinmelidir. Örneğin aşağıdaki (8,4) dijital resimde kuzey sınır noktası olan p’yi ve batı sınır noktası olan q’yu sildiğimizde iki beyaz bileşeni birleştirmiş oluruz ve bu nedenle de şeklin topolojisi korunmaz. (Burada p ve q bitiş noktası olmayan basit noktalardır, yani Teorem 2’nin koşulları sağlanır.)

Teorem 2, her bir taraftan sırasıyla nokta silerken de kullanılabilir. Örneğin önce kuzey sınır noktasını silip elde ettiğimiz yeni resimde güney sınır noktalarını bulup silebiliriz. Daha sonra ise doğu ve batı yönlerinde devam ederiz. (Bu algoritmalar sınır izleyen/border sequential algoritma olarak adlandırılır.)

Bu yazıda Kong ve Rosenfeld’in Digital topology: Introduction and Survey makalesinden yararlanarak Dijital Topoloji’nin bazı temel kavramlarını hem anlamaya hem de anlatmaya çalıştım. İki boyutlu dijital topoloji üzerinde 60’lı yılların sonundan buyana çalışılmakta olduğu göz önünde bulundurulursa, burada bahsedilenlerin sadece kısa bir giriş niteliğinde olduğu anlaşılacaktır. Daha fazlasını öğrenmek isteyenler için ise yalnızca bu makalede verilmiş olan kaynaklar bile fazlasıyla yeterli olacaktır.

*Ek öğretiler: https://www.youtube.com/watch?v=laC11NIQq8E
https://www.youtube.com/watch?v=LzIkT785iD8

Topolojik bir oluşum!

Tag Archives: dijital topoloji

Oyun Sevenlere: Nice Neighbors

Dijital Topoloji 101: Bazı Temel Kavram ve Sonuçlar