KABA FAKSİMİLE VERİLERİNİN GÖNDERİLMESİNDE GEREKSİZLİK AZALTICI BASİT ALGORİTMALAR

UDK : 621.397.12

Kaba Faksimile Verilerinin Gönderilmesinde Gereksizlik Azaltıcı Basit Algoritmalar*

Yazan : Peter A. STERN SIEMENS AG, MÜNİH

Çeviren: Dr. Güney GÖNENÇ ODTÜ

ÖZET

Daktilo yazısı harfler için tarama sıklığını azal tan fakat ayrıntıların kaybolmasına yol açma yan basit algoritmalar verilmiştir. Tarama sık lığı yeteri kadar yüksekse faksimile iletim hı zının nasıl 4 kat azaltılabildiği bilgisayar ben zetimi ile gösterilmiştir.

SUMMARY

Simple algorithms are ıntroduced with which one can reduce the resolution of type written letters without eliminating isolated details. Com puter simulations show how the transmission rate of facsimile can be reduced by a factor 4 given a sufficiently high resolution.

1. GİRİŞ

Daktilo yazısının pratik sayısal (digital) faksi milesi (tıpkıbasım) en azından mm başına 5 çizgilik bir tarama sıklığı gerektirir. Böylece 0,2 mm genişliğindeki ince ayrıntıların gönderil mesi ve alıcıda belirlenmesi mümkün olur. Ne var ki böyle ince ayrıntılar ancak arasıra orta ya çıkmaktadır. Böylece, tarama sıklığının ya tay ve düşey doğrultularda yarıya indirilmesi ve böylece bit hızının 1/4 e indirilmesi olanaklı görünmektedir. Ancak genellikle böyle «zorla mayla» yapılan azaltmalarda bazı kapalı çevre lerin tanınması için gerekli olan ince ayrıntılar kaybolacaktır. Örneğin konumu, özgün (origi nal) kafesteki atlanan çizgilerden birinin üstüne rastlamış 0,2 mm kalmlıkh bir ince çizgi böyle' (*) Nachrıchtentechnische Zeitschrift, Cilt 26, Sayı 9 (Eylül 1973), s. 417 420.

ce kaybolur. Karakter tanıma ile ilgili olarak bu konu Endres'ce tartışılmıştır [1].

Bu yazıda tartışılacak olan yöntemler, her iki doğrultuda 2 oranında tarama azaltılmasına (ve sonuç olarak 4 oranında bit hızı azaltılmasına) olanak veren, ama arasıra ortaya çıkan önemli ince ayrıntıların yok olmasına da izin vermeyen algoritmalar olacaktır. Bu ayrıntılar bir miktar kahnlaştınlmış ve kaydırılmış olacaklardır, ne var ki bu, çoğu kez sakıncalı olmayacaktır. înce bir ayrıntının kalınlaştırılmasına, elbette ancak bu ayrıntı civardaki başka ince ayrıntılarla ka rışmıyor ise izin verilebilir. Örneğin, 0,2x0,2 mm lik bir satranç tahtası örüntüsü bu koşul lar altında ayırdedilemez duruma düşer, ancak bu türden ince ayrıntılar daktilo yazısının gön derilmesinde gereksizdir. Ayrık durumdaki ince ayrıntıların kalınlaştırılıp kaydırılması, gereksiz

lik azaltılmasının görünür bir biçimde ortaya çıkması olmaktadır.

Daktilo yazısı harflerdeki (küçük harflerin or talama yüksekliği yaklaşık 2,5 mm) gereksizli ğin, harflerin okunabilirliğini ortadan kaldıra cak kadar çok bozulma (distorsiyon) yaratmak sızın, azaltılabileceği bilgisayar benzetimi (com puter simulation) ile görülmüştür. Öte yandan «zorlama» yöntemiyle yapılan bir azaltma, bazı harfleri tanınmayacak hale getirebilen bozulma lara yol açabilmektedir.

Bu yazıda anlatılan yöntemlere bazı bakımlar dan benzeyen bir deterministik gereksizlik azalt ma yöntemi P. Stucki [2] tarafından verilmişti. Stucki'nin yöntemi ana olarak şudur: Her satır da noktalar birer atlayarak örneklenip gönde rilir. Atlanmış noktalar, alıcı tarafta, alman noktalar üstüne özel bir «kalıp »(şablon) yerleş tirilmek ve atlanmış noktayı eğer örüntüye (pat tern) uyuyorsa varsaymak yoluyla doldurulur (Stucki bu kalıplara «hata trominolan» adını veriyor). Böylece elde edilen azalma 2 oranın dadır. Alıcıda bir gecikme devresi gerekli olmak tadır. Keskinlik (resolution) azalması doğuran başka gereksizlik azaltma yöntemleri [3] ve [4] te verilmiştir.

2. ALGORİTMALAR

Özgün tarama kafesi ve alıcıdaki tarama kafesi sırasıyla Şekil la ve lb de görülmektedir. Al goritmaları açıklayabilmek için özgün kafeste 7 noktayı P, ile gösterelim (i = 0,1, ..., 6). Po ta rayıcı kafanın şimdiki (içinde bulunulan andaki) konumu olsun. Demek ki P, aynı tarama satı rındaki bir önceki nokta ve P3 bir önceki sa tırdaki komşu noktadır. Alıcı tarama kafesinde P, Iere karşılık gelen noktalar Q, noktalarıdır (i = 0,1, . ., 6). P, ve Q, ikili fonksiyonlardır: Örneklenen nokta karaysa bu fonksiyonun değe ri 1, beyazsa 0 dır.

Algoritmalara geçmezden önce iki önemli kabul yapacağız.

1. Satırlar birer atlanarak, her satırda da nok talar birer atlanarak gönderilecektir.

2. Kanalda hata söz konusu değildir.

Demek ki Şekil lb deki alıcı kafesinde çift sayı lı Q; ler gerçekten gönderilen noktalara karşı lık gelen noktalardır. Bu noktalar her iki doğ rultuda da birer satır atlanarak elde edilen ve şekilde kalın siyah çizgilerle gösterilen «indir genmiş kafessin üzerinde bulunurlar. Kanalda hata olmadığından alınan ve gönderilen nokta lar (çift sayılı Q; ler) birbirinin aynısıdır. Tek sayılı Q, ler gönderilmeyen (demek ki alınma yan) ara noktalardır ki bunların, tarama kes

kinliğinin özgündekinin aynısı olması için, dol durulması gerekmektedir.

°> Tarama doğrultusu b)

fi fi fi ,1

Q, \0.

ı

Şekil 1. Tarama kafesleri, (a) özgün, (b) alıcı.

Alıcıda, yazıcı kafa, aslında bütün kafesteki her noktaya dokunmaktadır; ama kafa sadece indir genmiş kafesteki noktaların (çift sayılı Q; ler) üstünden geçerken bir bitlik bilgi (information)

alınmaktadır. Tek sayılı Qt ler için bir renk sap tanması gereklidir. Tarayıcı kafa (özgün ka feste) Po da iken yazıcı kafa Qo da dahil ön ceki bütün noktaları doldurabilir. Kara mı be yaz mı olacağını şimdilik belirtmeksizin iletil meyen Q1( Q3, Q5 noktalarının Qo la aynı renk te olduklarını kabul edeceğiz:

Q. = Q, = Q« = Q o

(D

Bu dört nokta için «indirgenmiş kare»nin köşe lerini oluşturuyor diyeceğiz.

Geriye, Qo in ve sonuç olarak indirgenmiş kare nin öteki üç köşesinin hangi renkte olacağına karar vermek kalıyor. Bu karan veren algorit malar iki türe ayrılabilir. Birinci türden algo ritmalarda, Qo, sadece indirgenmiş karedeki dört örnekleme noktasının bir fonksiyonudur:

0 o = f (Po. P,. P3, P5)

(2)

İkinci türden algoritmalarda, Qo, sadece bu dört noktanın değil, fakat çevredeki iletilen noktala rın da (indirgenmiş kafeste) fonksiyonudur:

Qo = f(P0, P,, P3, P5;Q2, Q4, Q6)

(3)

Şekil 2 de bu eşitliğe uygun verici görülmekte dir. P, ler özgün örnekleme noktalandır; Q; ler ise iletilen noktalar olup bunlar hem de f ( . ) fonksiyon üretecine geri beslenmektedirler. TD özgün kafese ilişkin nokta gecikmesi, tL ise öz gün kafese ilişkin satır gecikmesidir. örneğin P5, Po a göre bir satır periyodu ve bir nokta periyodu kadar gecikmelidir (Şekil la). Tam pon (buffer) devresi çıkış bit hızını giriş bit hızının 1/4 üne ayarlar.

Şekil 2. (3) eşitliğine göre verici. TP : nokta gecikmesi, TL : satır gecik mesi, T : tampon (buffer), K : kanal.

iletilmeyen noktaları da (tek sayılı Q( ler) dol duran alıcı Şekil 3 te görülmektedir. TD ve TL vericideki periyodlann aynısıdır. Gj üreteci ilgi li anahtarı l/2tL frekansında, G2 üreteci de l/2xp frekansında kapatıp açar. Özgün kafesteki Po (Şekil la) ile alıcı kafesteki O,, (Şekil lb) bir. birine karşılıklı gelmekte iseler de, yazıcı kafa tarayıcı kafaya göre bir satır artı bir periyod gecikmelidir. Böylece Qo iletilen noktası alın dığında (Şekil 3), bir yandan hemen FAK çıkı şma aktarılmakta ve Q5 noktası olarak yazıl makta (Şekil lb), öte yandan bir örnekleme pe riyodu kadar geciktirilip Q3 olarak yazılmakta dır. Bu nokta tüm bir satır kadar daha gecik tirilip Qt olarak, ilâveten bir örnekleme periyo du kadar daha geciktirilip Qo olarak yazılır. «İndirgenmiş kare»nin dört köşesi böylece (1) eşitliğine göre doldurulmuş olur.

Şekil 3. Alıcı. G,: satır frekansının yarı değerini üre tir (alınan her satır bir kez tekrarla nır), G2 : nckta frekansının yarı değerini üretir (alınan her nokta bir kez tek rarlanır), T : tampon (buffer), K: kanal, FAK: faksimile çıkışı.

Birinci türden algoritmalara (2 eşitliği) örnek olarak şu özel durumu gözönünc alıyoruz :

Qn =

(4)

Bu algoritma tarama kafesinin her iki doğrul tuda yarıya indirilmesi olduğundan (örnekleyi cı, noktaları ve satırları birer atlayarak almak tadır), buna «zorlama» azaltma yöntemi diyo ruz. İlerde göreceğimiz gibi bu algoritma ince ayrıntıların kaybolmasına yol açmaktadır. Örne ğin, eğer beyaz zemin üzerinde Po ile P2 arasın daki Pj den geçen çok ince bir kara çizgi var sa, o zaman (4) algoritmasında bu çizgi yoko lacaktır. Bu durumda, P, noktası, Po ve P2 ye göre bir «tekil nokta» olmuş olur. Böyle «tekil nokta»ların varlığı halinde ince ayrıntıların kay bolmasını engellemek üzere, ikinci türden algo ritmaların bir özel halini ortaya atacağız.

Alıcıda ortaya konan şeklin sadece özgün nok taların değil, iletilen noktaların da bir fonksiyo nu olması halinde (3 eşitliği), «tekil nokta »yi şöyle tanımlayacağız : Eğer bir önceki iletilen

Q2 noktası ile, özgün kafesteki şu anda örnek lenen Po noktası aynı renkte iseler ve bir önce ki örneklenen Pt noktasının rengi Po m rengi nin tersi ise yatay doğrultuda bir «tekil nok ta» vardır diyeceğiz. Matematiksel olarak,

Po = Q2 ve P, = Po

(5a)

ise «yatak tekillik» vardır diyoruz.

Benzer şekilde ,eğer,

Po = Q4 ve P3 = Po

(6a)

ise «düşey tekillik» ve,

Po = QÖ ve P5 =="?„

(7a)

ise «köşegenel tekillik» vardır diyeceğiz.

Şimdi, ikinci türden algoritmaların (3 eşitliği) bir özel hali olarak aşağıdaki algoritmayı or taya atıyoruz: Eğer bir yatay tekillik varsa, şimdiki iletilen nokta Qo, tekil nokta Pj ile aynı renkte (değerde) olacak; eğer yatay tekillik yok sa, Qo, şimdiki örneklenen nokta Po ile aynı renkte olacak. Matematiksel olarak, eğer (5a) doğruysa, o zaman :

Qo = P,

(5b)

eğer (5a) doğru değilse, o zaman :

Qo = Po olacak.

Benzer şekilde, eğer bir düşey tekillik varsa, ya ni (6a) eşitliği doğruysa, o zaman :

Q., = P,

(6b)

t,ba) eşitliği yanlışsa, o zaman :

0P

(6c)

olsun Eğer köşegenel tekillik varsa, yani (7a) eşitliği doğruysa ,o zaman :

0 o = P5

(7b)

(7a) eşitliği yanlışsa, o zaman :

O =P

(7c)

^o

Âo

olsun.

Yukardaki üç tipten tekilliğin iki çeşit birlikte olma durumunu içeren özel ikinci tür algorit maların benzetimi yapılmıştır. Bu algoritma şöy ledir :

a. Yatay ve düşey tekilliklerin herhangi birinin ya da ikisinin birden bulunması durumu. Eğer (5a) ya da (6a) eşitliklerinden biri ya da her ikisi birden doğru ise (mantıksal «ya da» işle mi) o zaman iletilen nokta Qo, P, noktasına ya da P, noktasına ya da her ikisine birden eşit olsun. Mantıksal bir bağıntı olarak bunu şöy le belirleyebiliriz:

Eğer (5a ya da 6a) doğru ise, o zaman:

Qo = (P, ya da Po)

(8)

0,. = Po

b. Yatay, düşey ya da köşegenel bir tekilliğin, ya da bunlardan herhangi ikisinin, ya da üçü nün birden bulunması durumu.

Eğer (5a ya da 6a ya da 7a )doğru ise, o zaman:

Qo = (P, ya da P3 ya da P5)

(9)

daktilo küçük harflerinin, bilgisayarla benzetim lenmiş çıktıları görülmektedir. Örnekleme inceli ği 6 2/3 satır/mm ye eşdeğerdir. Özgün örnek leme kafesinin bir parçası da şekilde gösteril miştir

Aynı harflerin «zorlama» (4 eşitliği) yöntemiy le gereksizlik azaltılmasına uğratıldıktan sonra ki durumları, Şekil 4 (II) de görülmektedir. Bilgi kaybı örneğin «a» harflerinde görülmek tedir. Kapalı kısımlar açık hale gelmiştir, üste lik birinci «a» da açık bir kısım kapanmıştır. Aslında, bu harfin artık «a» mı yoksa «e» mi olduğu anlaşılamamaktadır.

"Jröusseau

rousse&u

b)

T I'dd V

C ııt.1

IUI enn J K

n

"

Eğer Pj, P3 ve P5 sayfa üzerinde zaman zaman bulunabilecek olan gerçekten tekil noktalar ise, o zaman bunlar algoritma etkisiyle büyütülecek ve biraz kaydırılacaklar, fakat kaybolmayacak lardır, öte yandan, bir doğrultudaki noktalar (diyelim ki yatay), ince bir satranç tahtası örün tüsü biçiminde, bir siyah bir beyaz sıralanmış iseler, o zaman alman şekil aynı doğrultuda üç katı büyümüş bir satrançlı örüntü olacaktır.

3. BİLGİSAYARLA BENZETİM VE SONUÇ LARI

Birinci türden algoritmalarla örnek olarak (4) eşitliğini, ikinci türden algoritmalara örnek ola rak da (8) ve (9) eşitliklerini benzetimledik. Şe kil 4 (1) de «cayetano» sözcüğünü oluşturan

y Ö i.

.

Şekil 4. Çeşitli algoritmaların uygulandığı dak tilo yazısı sözcükler (bilgisayar benze timi ile elde edilmiştir). ÖK: örnekle me kafesi. I. Özgün sözcük (original), II. «zorlama» yöntem (4 eşitliği), III. (8) eşitliğine uygun yöntem, IV. (9) eşitliğine uygun yöntem.

Bilgi kaybı, veya ince ayrıntıların yokolması, yatay ya da düşey doğrultuda tekilliklerin var lığını gözonüne alan algoritma (8 eşitliği) ile azaltılabilir. Şekil 4 (III) de her iki «a» harfi nin de alt tarafları gerektiği gibi kapanmış du rumdadır, fakat üst tarafları halâ kapalıdır. Ya tay ve düşey tekillikler yanında köşegenel te killik de gözonüne alınırsa (9 eşitliği), harflerin çevrelerinde iyileşme olmaktadır: Artık kapalı olması gereken çevreler kapalı ,açık olması ge rekenler açıktır. Şekil 4 (IV) te bu durum gö rülmektedir. Burada, yalnızca .harflerin köşele rinde bir düzensizlik vardır, bu da tüm yazıya biraz bulanık bir görünüm vermektedir. Tara ma inceliği 6 2/3 satır/mm den daha büyük ol muş olsaydı köşelerdeki bu düzensizlik yoko lacaktı, ama o zaman daha yalın olan algorit manın (8 eşitliği), verdiği sonuçlar da iyileşmiş olacak ve daha karmaşık algoritmaya (9 eşit liği) gerek kalmayacaktı. Bu nedenle Po in çap raz olarak üstünde ve sağındaki (Şekil la) te killik gibi tekillikler gözonüne alınmamıştır.

bir azalma elde edilebilmektedir; alıcıda bir ge cikme devresi gereklidir. Bizim yöntemimizde 4 oranında bir azalma sağlanmaktadır ve ince ayrıntılar kaybolmamakta sadece bozulmakta dır. Ancak daha fazla donanım gereklidir: Ve ricide uç gecikme ve bir tampon (buffer) dev resi, alıcıda bir gecikme ve bir ters tampon dev resi gerekli olmaktadır. Stucki yönteminde ise tampon devresi gerekmemektedir.

Teşekkür :

Yazar, yardımlarından ötürü Dr. W. E. Hein lein'e teşekkürü borç bilir.

KAYNAKLAR

4. SONUÇ

Gönderilen noktanın geri beslenmesine (3 eşit liği) dayanan iki algoritmanın (8 ve 9 eşitlikle ri), örnekleyici sıklığının yeteri kadar olması ve ince ayrıntıların sadece ara sıra ortaya çıkma sı halinde, daktilo yazılarının gönderilmesinde gönderme hızının azaltılması yönünden etkili olduğu gösterilmiştir. Bu iki algoritmayla elde edilen sonuçlar tarama sıklığına bağlıdır; (9) eşitliğiyle daha fazla tarama sıklığı gerekmek tedir, fakat tarama sıklığı arttınlınca da (8) eşitliği yeterli duruma gelmektedir ve başka te killiklerin hesaba katılmasına gerek kalmamak tadır. Gönderme hızında, böylece, 4 kat bir azal ma sağlanmaktadır.

Bu sonucu Stucki'nin yöntemiyle karşılaştırmak ilgi çekicidir. Örüntünün yeniden yapımı, bu yöntemde, alıcıda gerçekleştirilmektedir. Oysa bu iş, burada anlatılan yöntemde vericide ger çekleştirilmekledir. Buradaki yöntem, meteoro loji hizmetleri gibi tek verici fakat çok sayıda alıcı kullanan faksimile (tıpkıbasım) sistemleri açısından, daha üstündür [5]. Stucki yöntemin de, geribesleme sözkonusu olmadığından, ince ayrıntılar genellikle kaybolmakta ve 2 oranında

1. Endres, W.: Über die Redundanzverminde rung bei der Zeichenerkennung. Nachrichten teehn. Z., Cilt 16 (1963), s. 529 535.

2. Stucki, P.: Efficient transmission of grap hics using polyomino filtering at the recei ver. IEEE Trans. Aerospace and Electronic Systems, AES 6, (1970 Kasım), Sayı 6, s. 811 814.

3. Smith, I. R.; Schilling, Donald L.: Comp ressions of Bandwidth requirements for a certain elass of band limit funetions. IEEE Trans. COM 20 (1972 Nisan) Sayı 2, s. 104 114.

4. Spencer, D. R.; Huang, Thomas: Bit plane encoding of continuoustone pictures. Smyp. Computer Processing in Communications, Polytechnic Inst. of Brooklyn, 1969 Nisan, s. 101 120.

5 Straiton, J. C.: Weather Bureau facsimile: Today, the future, problems. Proc. IEEE Internat. Convention on Communications, Boulder Colo., 1969, s. 11.11 11.14.