Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
17.05.2014
Sayfa 1
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Genetik Algoritmalar, Fonksiyonel Ağlar ve En Küçük Kareler Yaklaşımı ile 3 Boyutlu
Nokta Bulutlarının Bezier Eğri ve Yüzeyi Uydurma
Özet: Bu çalışma eğri ve yüzey uydurma problemini ilgilendiriyor. Biz özellikle Bezier
eğrileri ve yüzeyleri ile donatılmış 3 boyutlu nokta bulutlarının durumuna odaklanmaktayız.
Bu eğriler ve yüzeyler parametrik olduğu için, biz veri noktalarının uygun bir parametre alma
sorunu ile karşılaşıyoruz. Diğer taraftan, fonksiyonel kısıtlamaların eklenmesi klasik uydurma
yöntemlerinin çözüm sunamadığı yeni elemanlar getirir. Bu sorunları çözmek için bu
makalede iki Yapay Zekâ (YZ) tekniği dikkate alınmıştır: (1) eğri/yüzey parametreleştirmeleri
için genetik algoritmaların kullanımı önerilmektedir. (2) fonksiyonel kısıtlamalar sorunu için
fonksiyonel ağlar düzeni uygulanır. Her iki yöntem, Bezier eğri ve yüzeyi uydurmada uygun
metotları sağlamak için en küçük kareler yaklaşım yöntemi ile birleştirilir. Bu yöntemlerin
performansını göstermek için, 3B nokta bulutları üzerindeki bazı uygulama örnekleri
verilmiştir.
1.
Giriş
Veri ölçme için eğriler ve yüzeyler uydurma; araba gövdesi, gemi tekneleri, uçak gövdesi ve
diğer serbest şekilli nesnelerin üretimi gibi gerçek problemlerde önemli rol oynar. Ters
mühendislikteki tipik bir geometrik problem, nesnenin yüzeyinden alınan sık veri noktalarının
sınır temsilli CAD modele çevirim işlemidir [17, 19]. Bilgisayar destekli geometrik tasarımda
(CAGD) uydurma için alışılmış modellerin çoğu Bezier, Bspline ve NURBS gibi serbest
şekilli parametrik eğriler ve yüzeylerdir.
Eğri/yüzey uydurma yöntemleri esasen en küçük kareler yaklaşım şemasına dayalıdır. Bu
yaklaşım (ölçülmüş veri serileri belirlidir) veriye çok yaklaşan (en iyi uydurma) fonksiyonu
bulmaya çalışan bir klasik iyileştirme tekniğidir. Bize np veri noktaları kümesinin {(xi,yi)}
i=1,…,np verildiğini kabul edelim. Biz f(xi) ≈ yi gibi bir f fonksiyon bulmayı istiyoruz. Tipik
bir yaklaşım f’nin hesaplanması gereken bazı parametrelere bağlı olan belirli bir fonksiyonel
yapısı olduğunu farz etmektir. Bu yöntem verideki uyan noktalar ile fonksiyon tarafından
üretilen noktalar arasındaki yatay eksen farklarının karelerinin toplamını S (kalanlar olarak
adlandırılır) azaltan parametre değerlerini bulmak içindir.
.
(1)
İyi bilinir ki eğer f fonksiyonu doğrusal ise, problem doğrusal eşitlik sistemine doğru
yaklaşıyor gibi önemli ölçüde basitleştirir. Buna karşılık, biz genel iyileştirme (serbest)
problemini çözme ihtiyacı duyduğumuzdan beri eğer bu fonksiyon doğrusal değilse problem
daha da zorlaşır.
17.05.2014
Sayfa 2
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Bu çalışmada, biz f’nin serbest şekilli parametrik eğri veya yüzey olduğu durumu
düşünüyoruz. Önceki halinde, biz aşağıdaki C(t) eğrisine sahiptik:
.
(2)
Pj = (Pjx, Pjy, Pjz) vektör katsayılarıdır (genellikle kontrol noktaları olarak adlandırılırlar),
{Bj(t)}j=0,…,M ; C(t) parametrik eğrisinin temel fonksiyonlarıdır (harmanlama fonksiyonları) ve
t parametredir, genellikle sınırlı aralıklarda [α, β] tanımlıdır. Bu makalede vektörler koyu
renkli olarak yazılmıştır. Şimdi biz her bir kartezyen (x, y, z) elemanları için, veri noktalarını
gösteren karesi alınmış hataların toplamını azaltmayı (1)’e göre hesaplayabiliriz. Fakat bizim
her bir (xi, yi, zi) i=1,…,np veri noktası ile ilişkilendirilmiş ti parametre değerine ihtiyacımız
var:
Pj , j=0,…,M katsayıları (xi, yi, zi) i=1,…,np veri noktaları tarafından verilen bilgilerden
belirlenmelidir. Bu hataların eleman bazında azaltılmasının performansı veri kümesi
üzerindeki, veri noktaları ile 3B uzaydaki model tarafından verilen uygun noktalar arasındaki
öklit uzaklığının toplam bazındaki azaltılmasının performansına eşittir. Bu problem önemsiz
olmaktan uzaktır: bizim eğriler ve yüzeyler parametrik olduğu için biz veri noktalarının uygun
parametre alma problemi ile karşılaşıyoruz. [1]’de belirtildiği gibi uygun parametre seçimi
topolojiyi yeniden oluşturma ve yüzey uygunluğu için zorunludur. Mevcut birçok yöntem
kendisi ile kesişen gürültülü yüzeyler gibi istenilmeyen yüzeyler uyduran topolojik
problemleri vardır. Genellikle, otomatik yüzey uydurma algoritmaları [2,13] parametrik yüzey
uydurmadan önce örnek noktalar arasındaki bağlantı bilgisine ihtiyaç duyar. Eğer koordinat
verisi organize olamamış veya seyrekse bu görev giderek zorlaşır. Bağlantıyı hesaplayan
birçok teknik üretilen yüzeyin topolojisini değiştirebilen boşlukları ve delikleri önlemek için
sık veri kümesine ihtiyaç duyar. Bu yüzden, temel fonksiyonların Pj katsayılarına ek olarak
veri noktalarına uygun parametre değerleri ti=1,…,np bizim formülümüzde bilinmeyen olarak
gözükür. Harmanlama fonksiyonu Bj(t) t’de doğrusal olmadığından dolayı, hataların en küçük
kareler azatlımı doğrusal olmayan bir problem [20] olur. Bu problemler ile uygulamada sıkça
karşılaşılır ve veri noktalarının geniş kümeleri için bilinmeyenli sayısı yüksektir.
Son zamanlardaki makaleler gösteriyor ki yapay zekâ (AI) tekniği uygulamaları bu problemle
ilgili olağanüstü sonuçlar elde edebilir [7,10,11,14,15,16]. Bu yöntemlerin çoğu birkaç çeşit
sinir ağlarına dayanır. Bunlar ya standart sinir ağlarıdır [10] veya Kohonen’s SOM (kendi
kendini organize etmiş haritalar) ağları [1,11] ya da Bernstein Temel Fonksiyonu (BBF)
ağlarıdır. Bazı durumlarda, ağ özellikle veri sıralamada ve dörtgen topolojili kontrol
17.05.2014
Sayfa 3
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
tepelerinin ızgaralarını oluşturmada kullanılır. Bu ön hazırlık aşamasından sonra, herhangi bir
standart yüzey imar yöntemi (yukarıda referans olarak verilenler gibi) uygulanmalıdır. Diğer
durumlarda, sinir ağı yaklaşımı parçalı diferansiyel eşitliklerle [1] veya diğer yöntemler ile
birleştirilir.
Bu problemi çözecek olan bizim stratejimiz yapay zeka tekniklerinin bu grubuna aittir. İleride
anlatılacağı üzere, biz bir hibrit metot öneriyoruz. Bu hibrit metod veri noktaları için ti
parametre değerlerini arayan genetik algoritmalarını birleştirir, en iyi en küçük kareleri
oluşturan Pj katsayılarını ve genetik algoritma tarafından üretilen parametre değerleri kümesi
için ilgili hatayı hesaplar. Bu süreç belirli bir sonlandırma durumuna ulaşıncaya kadar tekrar
tekrar uygulanır. Bu yöntem hakkındaki detaylar bölüm 2 ve 5’te verilecektir.
Genetik algoritma yaklaşımı eğri ve yüzey uydurmada (özellikle, eğri/yüzey
parametreleştirme probleminde) iyi çalışıyor olmasına rağmen, ne bu yöntem ne de standart
sinir ağları noktaların farklı kümelerinden ziyade matematiksel eşitliklerle açıklanan ek
fonksiyonel kısıtlamalarını izah edemez. Hâlbuki bu durum bilgisayar grafik ve CAGD
alanında oldukça normaldir. Örneğin, biyomedikal resimler sık sık çapraz kısımların
dizisinden üretilir, üç boyutlu hacimler paralel yüzeyli nesnelerin kesişmesinden üretilir.
Hatta eğer kullanıcı geniş bir veri noktaları kümesine sahipse, herhangi ek bilgi (kesişen
kısımlar veya ekleme/yaklaşma yüzeyi üzerindeki eğrinin diğer çeşitleri gibi) problemi
oldukça basitleştirir. Bu tür fonksiyonel bilgiler, verilen problem için oldukça faydalıdır,
uygulanmış alanlarda nadiren kullanılır. Muhtemelen ana sebep bazı kısıtlamalardan doğan
fonksiyonel eşitlik çözümünün zorluğudur (fonksiyonel eşitlik hakkındaki bilgi için [6]). Bu
makalede, yeni bir formül, fonksiyonel ağlar, bazı kısıtlamalar göz önünde bulundurularak
Bezier yüzey uydurma çözümü için uygulanır.
2.
Genetik Algoritmalar
Genetik algoritmalar (GA) [9] evrim ve doğal ayıklama prensipleri üzerine kurulu olan arama
yöntemleridir. Bunlar en uygun çözümleri aramada, sonlu uzunluktaki kelime katarları gibi
kodlanmış çözümlerin gerçekleştirildiği yerlerdeki iyileştirme problemlerinde kullanılabilir.
Genetik algoritmalar Michigan Üniversitesinde John Holland tarafından geliştirildi [12] ve
global arama sezgiselleri (global search heuristics) veya meta-sezgiselleri (meta-heuristics)
olarak kategorize edilir[3]. Tekniğin bir grubu Tabu Arama, Tavlama Benzetimi yada
Tekrarlayan Yerel Arama gibi yörünge metotlarını ve Genetik Algoritmalar, Karınca
Kolonileri, Parçacık Yığını Optimizasyonu gibi nüfus temelli metotları kapsar.
Genetik Algoritmalar potansiyel çözüm kümelerinden oluşan nüfuslarla ilgilenir. Örneğin
algoritma her bir birey potansiyel çözümü temsil ettiği her bir tekrar için n bireylerin
popülasyonuna Pop(iter) = {x1(iter),…,xn(iter)} bakar. Normalde başlangıç iterasyonu
rastgele seçilir. Fakat çözüm hızını artırmak için belirli problemler için bazı bilgiler başlangıç
iterasyonunu oluşturmada kullanılabilir. Başlangıç popülâsyonun büyüklüğü dikkate alınması
gereken en önemli hallerden biridir ve birçok uygulamada kritik olabilmektedir. Eğer
büyüklük aşırı derecede küçükse, algoritma çok çabuk sonuca ulaşacaktır. Eğer aşırı derecede
17.05.2014
Sayfa 4
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
büyükse algoritma bilgisayar kaynaklarını boşu boşuna israf edecektir. Popülâsyon büyüklüğü
ya sabit ya da değişken olabilir. İdeal popülasyon büyüklüğü hakkındaki bir araştırma [8]’de
bulunabilir. Popülasyondaki her bir birey, örneğin potansiyel çözüm, genetik sunum
kullanarak gösterilmek zorundadır. Genellikle ikilik sunum kullanılır, fakat diğer yöntemler
de mümkündür. Potansiyel çözümlerin her biri uygunluk fonksiyonun ortalaması tarafından
değerlendirilmek zorundadır; bu değerlendirmenin sonucu birey uyumunun ölçümüdür.
Bu algoritma tekrarlamalı bir süreçtir. Bu süreçte birey adaptasyonuna ve bazı genetik
operatörlere (çaprazlama ve mutasyon) dayalı seçme süreci (üreme) kullanarak yeni
popülasyonlar elde edilir. En iyi adaptasyona sahip bireyler genetik değişim ve mutasyon ile
yeni bireyleri oluşturmada daha çok şansa sahiptir. Üreme operatörü taraflı olarak birey
uygunluk değerlerine orantılı olarak yuvaları ağırlaştırılmış bir rulet çarkı uygulanabilir.
Seçim süreci n kere tekrarlanır ve seçilmiş bireyler daha sonraki genetik operatör hareketleri
için geçici yeni popülasyonu oluşturur.
Üremeden sonra yeni geçici popülâsyonun bazı üyeleri dönüşümler geçirirler. Çaprazlama
operatörü, popülasyonun rastgele seçilen iki bireyinden parçaları birleştirme ile iki yeni birey
oluşturur (yavrular). Genetik algoritmada çaprazlama operatörü belirli olasılık ile rastgele
uygulanır. İyi bir genetik algoritma performansı yüksek çaprazlama olasılığının seçimine
ihtiyaç duyar. Mutasyon tek bir bireyde küçük değişiklik ile yeni bireyin oluşması olan
birimsel dönüşümdür. Bu durumda, iyi bir algoritma performansı düşük bir mutasyon
olasılığının seçimine ihtiyaç duyar (popülasyon büyüklüğüne ters orantılı). Mutasyon
operatörü garantiler ki bütün arama uzayı araştırmanın sıfır olasılığına sahip değildir.
Genetik algoritmaların şaşırtıcı basitliğine rağmen, genetik algoritmalar çeşitli uygulama
alanlarında optimizasyon problemlerini çözen güçlü bir araç olarak tanınır. Bu problemlerin
örnekleri taşıma problemleri, kablo yönlendirme, gezgin satıcı problemi gibi çok çeşitli
alanlarda bulunur [9]. Bilgisayar destekli çizim (CAD) dergisi 2003ün 35 özel basımını
genetik algoritmalara tahsis etti [18], ve açık biçimde B-spline polinomları ile veri oluşturma
konulu bir makale içermektedir [21]. Bu çalışmada, biz CAGD için çok daha uygun olan
parametrik modelleri düşünüyoruz.
Tablo 1. Çaprazlama operatörü
Ebeveyn 1
0.123
0.178
0.274
0.456
0.571
0.701
0.789
0.843
0.921
0.950
Ebeveyn 2
0.086
0.167
0.197
0.271
0.367
0.521
0.679
0.781
0.812
0.912
çapraz nokta
Yavru 1
0.123
0.178
0.274
0.271
0.367
0.521
0.679
0.781
0.812
0.912
Yavru 1
0.123
0.178
0.271
0.274
0.367
0.521
0.679
0.781
0.812
0.912
kromozomlar sıralı
17.05.2014
Sayfa 5
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Yavru 2
3.
0.086
0.167
0.197
0.456
0.571
0.701
0.789
0.843
0.921
0.950
Veri Bağlantısı için Genetik Algoritmaları Kullanma
Veri noktalarına eğrileri/yüzeyleri uydurmada genetik algoritmaları kullanmak için birkaç
durum göz önünde bulundurulmalıdır. Öncelikle tipik bir GA, onun kullanımından önce
tanımlanması gereken iki elemana ihtiyaç duyar: problemin her bir potansiyel çözümünün
genetik temsili ve çözümün kalitesinin ölçümü (genellikle uygunluk fonksiyonu olarak anılır).
Bizim problemde, biz parametre değerlerinin veri noktalarına atanması süreci ile
ilgileniyoruz, böylece biz gerçek kodlu genetik algoritmanın kullanımını öneriyoruz. Bu
algoritmada bireyin genetik temsili gerçek bir np boyutlu vektör olacaktır. Vektörde her bir
koordinat veri noktasına atanmış parametre değerini temsil eder. Görevin kalitesini ölçmeye
yarayan uydurma fonksiyonu, uydurma sürecinin hata fonksiyonuna bağlı olacaktır.
Başlangıç popülasyonu olarak rastgele üretilmiş parametre vektörlerin (bireyler) kümesini
düşünüyoruz. Algoritmanın arama alanını genişletmek için popülasyon büyüklüğü geniş
olmalıdır; ancak bu parametre artarsa hesaplama süresi de artar. Her iki durum arasında bir
karşılaştırmaya ihtiyaç duyulur. Algoritma bireylerin yeni popülasyonlarını elde etmek için üç
genetik operatör kullanır: seçme, çaprazlama ve mutasyon. Bizim durumda, seçme operatörü
taraflı olarak birey uygunluk değerleri oranında yuvaları ağırlaştırılmış bir rulet çarkı olarak
oluşturulur. Bireyin içinde rastgele çaprazlama noktası seçen tek noktalı çaprazlama operatörü
kullanırız. Daha sonra operatör bu noktadan sağa ve sola iki ebeveyn kromozomu değiştirir ve
sonunda elde edilen vektörleri yeni iki yavru üretmek için sıralar. Bu süreç Tablo 1’de
gösterilmiştir.
Mutasyon yöntemi olarak biz çözümün vektör parametresindeki en kötü uyma hatalı k
pozisyonunu seçmeyi ve seçilen parametrenin değerini vektör içindeki önceki ve sonraki
parametrenin aritmetik ortalaması ile değiştirmeyi öneriyoruz, şöyle ki
.
Hatırlatma ki, tk-1 < tk < tk+1, ve bundan dolayı hiçbir sıralama yöntemine ihtiyaç duyulmaz.
Bu genetik operatörleri kullanarak, algoritmanın genel yapısı Tablo 2’de gösterilmiştir.
17.05.2014
Sayfa 6
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Tablo 2. Genetik algoritmanın genel
yapısı
Bu süreç belirli bir sonlandırma durumuna ulaşıncaya kadar tekrar eder (böylece başarılı
nesiller oluşur). Yaygın sonlandırma kriterleri şöyledir: düşük bir eşik değerini karşılayan
veya belirli bir nesil sayısına ulaşan veya başarılı tekrarlamaların daha iyi sonuçlar
üretemediği bir çözüm bulunur.
4.
En İyi En Küçük Kareler Yaklaşımı
3B veri noktaları kümesinin Di = (xi, yi, zi) , i = 1,…, np olduğunu varsayalım. Biz
yöntemimizi x’lerin koordinatları için daha ayrıntılı olarak tarif edeceğiz (y’ler ve z’ler de
benzerdir). Hedef; X = (x1,…, xnp)T sütun vektörüne duyarlı olan farklı en küçük karelerdeki
en iyi uymayı veren Pjx , j = 0,…,M katsayıları hesaplamaktır. Burada (.)T transpoz
anlamındadır. Burada
modelini kullanıyoruz ki ti (i=1,…, np) veri
noktalarına atanmış parametre değerleridir ve Bj(t) modelin bilinen harmanlama
fonksiyonudur. Sütun vektörünün Bj = (Bj(t1),…, Bj(tnp))T , j = 0,…,M olduğunu varsayalım ve
aşağıdaki sistemim çözümü Pjx katsayılarını verir:
Katsayı matrisinin elemanları ve bağımsız terimler sonlu-boyutsal vektörler arasındaki
standart öklit skalar çarpımıyla hesaplanır. Bu sistem [4] karesi alınmış hataların toplamını
azaltma ile sonuçlanır. Bu hatalar bölüm 1de gösterildiği gibi veri noktalarının xi
17.05.2014
Sayfa 7
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
koordinatlarına atfedilir.
Bütün xi, yi, zi koordinatlarını düşünecek olursak, aynı katsayı
matrisli üç doğrusal sistemin çözümü
eğrisi için en iyi en küçük
kareler yaklaşımını sağlar. Parametrik şekildeki yüzeyler için CADG’da çok yaygın olan
tensör ürün yüzeyi
kullanılır. Pi,j katsayıları
3B’daki kontrol noktalarıdır, dörtgen topolojide sıralanmıştır. Bi(u), Bj(v) fonksiyonları
eğrileri temsil etmek için kullanılan aynı temel fonksiyonlardır. Örneğin Bernstein
polinomları ve B-spline parçalı polinomları. u ve v parametreleri [um, uM] x [vm, vM]
dikdörtgensel alan (u ve v için kendi alanının kartezyen çarpımı) üzerinde değerlenir. Eğer
Bi(u) ve Bj(v) Bezier temel fonksiyonları ise, (M+1).(N+1) iki değişkenli polinomlar
Bi,j(u,v) = Bi(u) . Bj(v), i=0,…,N, j=0,…,M karesel alan [0, 1]x[0, 1] üzerinde u ve v’de
polinomların doğrusal vektör alanı için vektör temeli oluşturur. 3B’de (xl,k, yl,k, zl,k) noktaların
dörtgensel yapılı bir bulutu verilirse, l=1,…, npu, k=1,…, npv , ve (ul, vk) parametre
değerlerinin bir kümesi buluttaki veri noktaları ile bire-bir ilişkilidir, öyle ki bu noktalar
parametre alanında bir kartezyen küme oluşturur, noktaları uydurarak eğri oluşturmaya
benzeyen farklı bir formül. En iyi en küçük kareler tensörü (4) sistemi kullanarak elde
edilebilen noktaları uyduran yüzeyi oluşturur. Bu sitemde B’nin rolü daha önce tanımlanan
Bi,j(u,v) tarafından kabul edilir.
5.
Örnekler
Bu bölümde bizim yöntemlerin performansını göstermeyi hedefleyen iki örnek tartışılır.
5.1.
Bezier Eğrisi Uydurma
Birinci örnek olarak biz parametrik sunumu Denklem (2)’de verilen d derecenin Bezier
eğrisini düşünüyoruz. Formülde d derecesinin temel fonksiyonu şöyle tanımlanır:
Bu örnekte 8 tane 3B noktanın kümesini d=4 olan derecenin Bezier eğrisini uydurmak için
seçtik. Bilinmeyenler 23 sayısal değerlerdir: 8 veri noktası ile ilişkili 8 parametre değerli bir
vektör, artı 15 katsayı (4 dereceli eğrinin 5 kontrol noktasının her birinin koordinatı için 3 ).
Genetik algoritma için veri şu şekilde ayarlandı: 100 parametre vektörlü başlangıç
popülasyonu seçeriz. Her biri rastgele değişmeyen [0,1] dağılımından üretilmiş, artarak
sıralanmış 8 elemana sahiptir. Daha sonra başarılı nesiller üretmek için Tablo 2’de gösterilen
yöntemi uygularız. Bu örnekte, çaprazlama ve mutasyon operatörleri sırasıyla pc = 0.90 ve
pm = 0.20 olasılıklarıyla uygulanır. Bir çift ebeveyn kromozomları için tipik bir çıktı Tablo
1’de gösterilir, bir sonraki nesilde 2 yeni yavru oluşur. Bizim sonlandırma durumu ise, bu
adımlar 20 başarılı tekrarlama için sonuçlar daha fazla değişiklik oluşturmayıncaya kadar
tekrar eder. Bu örnekte, en ideal uydurma aşağıdaki sonuçlara sahip olan 76. adımda elde
17.05.2014
Sayfa 8
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
edilir: popülasyondaki ortalama hata 2.0875 olmasına rağmen, popülasyondaki hata (en iyi
oluşturulmuş parametre vektöründeki maksimum nokta hata) 1.8774. Son nesil için
çaprazlama ve mutasyon adedi sırasıyla 46 ve 24 tür. Elde edilen ideal parametre vektörü [0,
0.0131, 0.0583, 0.3556, 0.5384, 0.7138, 0.7899, 1]. Bu örnek için hesaplama zamanı 4.16
saniye (matlabda, Pentium 4, 3 GHz).
Şekil 1 Bezir eğrisi uydurma örneği: (soldaki) kontrol noktaları (yıldızlar) boyunca Bezier
eğrisi ve veri noktaları (küreler); (sağdaki) nesiller boyunca ortalama (düz çizgi) ve en iyi
(noktalı çizgi) öklit hatalarının evrimi
Şekil 1de (soldaki) veri noktalarını (kürelerle temsil ediliyor), dördüncü-derece 3B Bezier
eğrisi uydurmayı ve onun 5 kontrol noktasını (yıldızlar) gösterir. Şekil 1de (sağdaki) başarılı
nesiller boyunca her bir nesil için parametre vektörlerinin ortalama (düz çizgi) ve en iyi
(noktalı çizgi) öklit hatalarının evrimini gösterir. Hatırlatma ki en iyi hata başlangıçta hızlıca
küçük olur, azalma oranı daha sonraki nesiller için yavaşlar.
5.2.
Bezier Yüzeyi Uydurma
Biz şimdi u’da N ve v’de M dereceli parametrik bir Bezier yüzeyi düşünüyoruz ki temsili şu
şekildedir:
17.05.2014
Sayfa 9
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Burada temel fonksiyonlar (Bernstein polinomları) yukarıdaki gibi tanımlanır ve Pi,j
katsayıları yüzey kontrol noktalarıdır. Bu örnekte biz u ve v için aşağıdaki parametre değerleri
ile üretilmiş kübik Bezier yüzeyinden 256 veri noktası alıyoruz: veri noktalarının u’ları için
biz [0, 0.2] ve [0.8, 1] aralığında eşit uzaklığa sahip 8 parametre değerinin iki grubunu
seçiyoruz. Benzer şekilde v’ler içinde. Bilinmeyenler 3x16=48 sayısal katsayılar (16 kontrol
noktasının her biri için 3 koordinat) ve 256 veri noktaları ile ilişkili olan kümelerin çarpımı
tarafından birleştirilen iki parametre vektörü U ve V (16 büyüklüğün her biri). Bu, toplamda
80 sayısal bilinmeyen yapar.
Yöntem için girdi parametreleri şu şekildedir: popülasyon büyüklüğü: 200; pc = 0.95; pm =
0.20; sonlandırma kriteri = 30 ardışık nesilden sonra iyileşme yok. Başlangıçta biz 200 U
vektörlü ve 200 V vektörlü popülasyona sahibiz. Her biri rastgele Uniform[0,1] dağılımlı
parametre değeri atanarak kuruldu ve her bir vektörün içinde onlar sıralıdır. En iyi çözüm,
sonuçları şu şekilde olan 198. nesilde elde edilir: çizimdeki en küçük hata: 0.9891; ortalama
hata: 1.2314; son nesil için çaprazlama (ve mutasyon) adedi: 103 (59); cpu zamanı (Pentium
4, 3GHz, Matlab): 33.81 saniye.
Şekil 2 (soldaki) veri noktalarını ve kübik Bezier yüzeyi uydurmayı gösterir. Şekil 2’de (sağüst) biz, tekrarlamalar boyunca her bir nesil için ortalama hatanın (düz çizgi) ve en iyi
(noktalı çizgi) uzaklık hatanın evrimini gösteriyoruz. u ve v için ideal parametre değerleri
Şekil 2’de (sağ-alt) resmedilir. Burada uydurma süreci, veri noktalarına atanan parametre
değerlerinin dağılımını nasıl kavradığı görülebilir. Birim kare parametre alanının köşelerinde
yoğunlaşmak için elde edilen parametre değerlerinin eğiliminden bahsetmek faydalıdır.
Böylece girdi bilgileri oldukça iyi ayarlanır.
17.05.2014
Sayfa 10
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Şekil 2 Bezir yüzey uydurma örneği: (soldaki) kübik Bezier yüzeyi ve veri noktaları; (sağüst): nesiller boyunca ortalama (düz çizgi) ve en iyi (noktalı çizgi) öklit hatalarının evrimi;
(sağ-alt): parametrik alan üzerindeki ideal parametre değerleri
6.
Fonksiyonel Ağlar
Seyrek veri parametreleştirmenin problemini çözmek için alternatif bir yöntem, komşu tepeler
veya düğümler arasındaki istenilen bağlantılı ve önceden tanımlı 2B-ağı varsaymaktır. Ara
değeri bulma algoritması koordinat veri kümesini eşlemek için ağdaki düğümleri tekrarlı
olarak ayarlamakta kullanılır. Bu ara değeri bulma bazı ek bilgilerin mevcut olduğunu
sağlayan kaba yaklaşımı ile değiştirilebilir. Örneğin bazı uygulama durumlarında biz ya sınır
eğrilerini ya da yüzeyin bazı 3B çapraz seçimini belirleyebiliriz. Bazen, bazı eğriler veri
noktalarının kümesi yerine onların matematiksel fonksiyonlarıyla tanımlanır (bu durum
genellikle sonlu ötesi ara değerini bulma olarak bahsedilir). Bu durum sinir ağları yöntemine
uyarlanamayabilir [14]. [5]’de yazarlar fonksiyonel ağlar (functional networks) olarak
adlandırılan klasik sinir ağlarının güçlü bir eklentisini öneriyorlar. Bu yöntem fonksiyonel
kısıtlamaların bu çeşidi ile başa çıkabilir. Fonksiyonel ağlar (FN) formülü yüzey oluşturma
problemlerine başarılı şekilde uygulanıyor [7, 15].
Şekil 3 (soldaki) Denklem (6)’da ki parametrik yüzeyler için fonksiyonel ağın gösterimi;
(sağdaki) eşdeğer fonksiyonel ağ
17.05.2014
Sayfa 11
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Bu makalede biz bazı fonksiyonel kısıtlamalara maruz kalan Bezier yüzeyin durumunu
düşünüyoruz. Özellikle, S(u,v) Bezir yüzeyini bulmaya çalıştığımızı kabul edelim. Yüzeyin
u=u0 ve v=v0 izoparametrik eğrileri f(u)={f0(u), f1(u),…, fm(u)} ve f*(v)={f0*(v), f1*(v),…,
fm*(v)} fonksiyonlarının (fonksiyonların aynı aileye ait olmasına gerek yok; aşağıdaki örneğe
bakınız) kümelerinin doğrusal kombinasyonlarıdır. Başka bir deyişle, biz fonksiyonel
eşitliklerin sistemini karşılayan S(u,v) yüzeyleri arıyoruz.
Burada {αj(u); j=0,1,…,n} ve {βi(v); j=0,1,…,m} katsayılarının kümesi, genelliği
kaybetmeksizin, doğrusal olarak bağımsız fonksiyonların kümeleri kabul olarak edilebilir. Bu
problem Şekil 3’te (solda) verilen ilk bakışta sinir ağına benzeyen grafiksel gösterimi kabul
eder. Oysaki sinir ağları açısından önceki tanım şu problemleri getirir:
1. Sinir ağlarındaki sinir fonksiyonları aynıdır, halbuki bizim örnekte sinir fonksiyonları
farklıdır. Örneğin biz çarpma ve toplama operatörlerini (şekil 3te (solda) ‘x’ ve ‘+’
sembolleri) bulmalıyız.
2. Sinir ağlarında öğrenilen ağırlıklar vardır. Bu ağırlıklar fonksiyonel ağlarda
gözükmez; bunun yerine sinir fonksiyonları öğrenilir.
3. Sinir ağlarının sinir çıktıları farklıdır; halbuki bizim şemada, örnekteki bazı sinir
çıktıları rastlayandır. (bu şekil 3 (soldaki) S(u,v) çıktının durumudur.). Bu gerçek
çözülmesi gereken fonksiyonel eşitliklerin kümesine yönlendirir.
Bu ve diğer dezavantajlar sinir ağları yönteminin geliştirilmesi gerektiğini önerir. Bu
makalede, biz fonksiyonel ağlar kullanarak bunu yapacağız. Özellikle, bu problemin çözümü
şu şekilde verilir ([4]e bak):
Burada Pij keyfi vektör matrisi P nin elemanlarıdır. Şöyle ki, S(u,v) tensör ürün yüzeyidir.
Sonuçlanan fonksiyonel ağ Şekil 3de (sağda) resmedilmiştir.
7.
Bezier Yüzey Uydurma için Fonksiyonel Ağlar Kullanımı
Bu bölümde fonksiyonel ağlar yaklaşımı yüzey uydurma problemini çözmek için en küçük
kareler yöntemi ile birleştirilir. Bu makalede biz Bezier yüzeylerine odaklanırız, öyle ki
{fi(u)}i ve {fj*(v)}j fonksiyonlarının ailesi her ikisi de Bernstein polinomlarıdır. Şekil 4
fonksiyonel ağların çözebileceği problemlerin tipik bir örneğini gösteriyor. Biz bazı verilen
eğrilerin yaklaşık ara değerini bulan ve 3B veri noktalarının verilen kümesini en iyi
yaklaştıran (Şekil 4 (sağda) kırmızı küreler ile gösterilir) Bezier yüzeyini arıyoruz. Bu
17.05.2014
Sayfa 12
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
örnekteki fonksiyonel kısıtlamalar çapraz kısımların şeklinde verilir, Şekil 4de (sol üst ve
orta) gösteriliyor: u yönünde 5 kısım eğri, farklı derecelerin polinomları olarak tanımlanır, v
yönünde 6 kısım eğri, Bezier eğrileri olarak tanımlanır. Biz Şekil 4de (sol alt) gösterildiği gibi
veri noktalarının dikdörtgensel yapıya sahip olmadığını belirtiriz. Burada verilen noktaların
(u,v) koordinatları parametrik alanda gösterilir. Genellikle biz veri noktalarının fonksiyonel
kısıtlamalarını gidermek için tetiklenen hedef yüzeye (Şekil 4e (sağ) bak) ait olduğunu
ummayız. Bu kısıtlamalar bizim formülde fonksiyonel eşitliklerin sistemleri tarafından
tanımlanır. Birkaç isteğe bağlı kısıtlamanın uygulamada uyumsuz olabileceğini hatırlatalım.
Böyle durumlarda, fonksiyonel eşitlikleri sonuçlandırma çözüm getirmez, böylece
fonksiyonel eşitliklerin sistemi uyumluluk şartlarının rolünü oynar [15].
Şekil 4 Bezier yüzey uydurma örneği: (sol, üst ve orta) eğri kısıtlamaları; (sol alt) parametrik
alan üzerindeki veri noktalarının koordinatları; (sağ) tahmini veri noktaları ile uydurulmuş
Bezier yüzeyi
En küçük kareler yöntemi öğrenme süreci boyunca şimdi uygulanır. Süreçte sinir
fonksiyonları tahmin edilir (öğrenilir). Bunu yapmak için, her bir fi sinir fonksiyonu { φi0,…,
φimi } verilen aile içindeki fonksiyonların doğrusal kombinasyonları ile benzetilir. Böylece,
benzetilmiş sinir fonksiyonu şu şekilde olur:
17.05.2014
Sayfa 13
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
Burada x i’ninci sinir ile ilişkili olan girdilerdir. Bizim durumda, bu adım u ve v’ye bağlı olan
{(xk, yk, zk)}k=1,…,K üçlülerinin verilen sırasından x(u,v), y(u,v), z(u,v) sinir fonksiyonlarını
tahmin etmeyi azaltır. Burada x(uk,vk)= xk ve devamıdır. Böylece biz karesi alınmış hatalar
fonksiyonunun toplamını oluştururuz (Denklem (3)’e bakınız):
Burada biz her bir x, y, z değişkeni için bir hata fonksiyonu düşünmek zorundayız. Bu bir
önceki ifadedeki µ tarafından üstlenilir, böylece (8) µ = x, y ve z için üç farklı denklem olarak
düşünülmelidir. İdeal değer aşağıdaki için elde edilir:
Bu örnekte biz veri noktalarının iki kümesini düşünüyoruz: 64 veri noktalı birinci küme (onlar
sinir fonksiyonlarının öğrenmesinde kullanılacağı için eğitim noktaları olarak adlandırılır). Bu
noktalar [0, 1] x [0, 1] kare üzerinde eşit dağıtılmış olan parametrik koordinatlıdır. Ve aynı
yolda üretilmiş 256 veri noktalarının daha büyük kümesi (test noktaları olarak adlandırılır).
Eğitim noktalarını uydurmak için, biz (8)’de ki { φi(u)} i=0,1,..,I ve { ψi(v)} j=0,1,..,J fonksiyonlar
için u ‘da (sırasıyla v) I (sırasıyla J) dereceli Bernstein polinomlarını kullandık. Elbette, I ve J
için her farklı seçim çözülmesi gereken yeni bir sistem (9) oluşur. Özellikle, biz 2den 6ya
kadar I ve J için değerleri aldık. Bütün durumlar için sistem (9) ile uyumluluk eşitliliklerini
çözmek için, biz verilen eğrilerin ara değerlerini bulan ve veri noktalarına en iyi yaklaşımı
sunan (I,J) dereceli Bezier yüzeyini hesaplayabiliriz. Modelin kalitesini test etmek için, biz 64
eğitim noktası için 2den 6ya kadar I ve J için ortalamayı, minimumu, maksimumu ve karesi
alınmış öklit hatalarının kök ortalamasını (RMS) hesapladık. En iyi seçenek I=J=3 içindir ki
Şekil 4’deki gösterilen kübik Bezier yüzeyine karşılık gelir (hatalar şu şekildedir: maksimum:
2.1457; minimum: 0.0052; ortalama: 0.3564; RMS: 0.0795). Biz hatta hatalı çizimi kontrol
etmek için modelin çapraz onaylamasını uyguladık. Biz 256 test noktasının karesi alınmış
hataların kök ortalamasını (RMS), ortalamayı ve maksimumu hesapladık. Son değerler
karşılaştırılabilir ve hatalı çizim olmadığını gösterir. Bütün hesaplamalar Pentium 4, 3Ghz,
Mathematica v5.2 üzerinde gerçekleştirildi.
8.
Sonuçlar ve Gelecek Çalışmalar
Bu makalede biz iki Yapay Zekâ tekniğinin kullanımını öneriyoruz: (1) eğri/yüzey
parametreleştirme problemi genetik algoritmalar uygulanarak çözülür; (2) fonksiyonel
kısıtlayıcılar problemi fonksiyonel ağlar kullanarak ele alınır. Her iki yöntem eğri ve yüzey
17.05.2014
Sayfa 14
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
uydurma için uygun metotlar oluşturmada en küçük kareler yaklaşımı yöntemi ile birleştirilir.
Bezier eğriler ve yüzeyler yardımıyla 3B nokta bulutları üzerindeki onların bazı uygulama
örnekleri verilir (çapraz bölüm kısıtlamalarının durumu dâhil).
Bizim ilerideki çalışmalarımız veri uydurma için B-spline veya NURBS gibi parçalı polinom
modellerinin göz önüne alınmasını, düğüm vektörleri ile ilgili hesaplamalı süreçte bazı
değişikliklerle beraber, içerir. Bu vektörler bu modeldeki diğer parametrelerdir. Farklı
modellere veri uydurma için uzaklık hata fonksiyonu çoklu göreceli minimumlu bir davranış
sunduğu görülüyor. Bu global olan en ideale ulaşmayı daha çok zorlaştırır. Arama sürecinin
nasıl geliştirileceği üzerindeki bazı fikirler bizim gelecekteki çalışmamızın bir parçasıdır.
Yazarlar referans numarası ALFA II-0321-FA olan Avrupa Birliği projesi, referans numarası
#TIN2006-13615 olan İspanya Eğitim ve Bilim Bakanlığı projesi ve SistIng-Alfa projesinden
aldıkları parasal destek için teşekkür eder.
Referanslar
1. Barhak, J., Fischer, A.: Parameterization and reconstruction from 3D scattered points based
on neural network and PDE techniques. IEEE Trans. on Visualization and Computer Graphics
7(1), 1–16 (2001)
2. Bradley, C., Vickers, G.W.: Free-form surface reconstruction for machine vision rapid
prototyping. Optical Engineering 32(9), 2191–2200 (1993)
3. Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual
comparison. ACM Computing Surveys 35(3), 268–308 (2003)
4. Castillo, E., Iglesias, A.: Some characterizations of families of surfaces using functional
equations. ACM Transactions on Graphics 16(3), 296–318 (1997)
5. Castillo, E., Cobo, A., Gomez-Nesterkin, R., Hadi, A.S.: A general framework for
functional networks. Networks 35(1), 70–82 (2000)
6. Castillo, E., Iglesias, A., Ruiz-Cobo, R.: Functional Equations in Applied Sciences.
Elsevier Pub., Amsterdam (2005)
7. Echevarr´ıa, G., Iglesias, A., G´alvez, A.: Extending neural networks for B-spline surface
reconstruction. In: Sloot, P.M.A., Tan, C.J.K., Dongarra, J.J., Hoekstra, A.G. (eds.)
Computational Science - ICCS 2002. LNCS, vol. 2330, pp. 305–314. Springer, Heidelberg
(2002)
8. Goldberg, D.E.: Optimal Initial Population Size for Binary-Coded Genetic Algorithms,
TCGA Report No.85001. University of Alabama (1985)
9. Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning.
Addison-Wesley, Reading (1989)
17.05.2014
Sayfa 15
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
10. Gu, P., Yan, X.: Neural network approach to the reconstruction of free-form surfaces for
reverse engineering. Computer Aided Design 27(1), 59–64 (1995)
11. Hoffmann, M., Varady, L.: Free-form surfaces for scattered data by neural networks. J.
Geometry and Graphics 2, 1–6 (1998)
12. Holland, J.H.: Adaptation in Natural and Artificial Systems. Michigan Press, Ann Arbor
(1975)
13. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Surface reconstruction
from unorganized points. In: Proc. of SIGGRAPH92, vol. 26(2), pp. 71–78 (1992)
14. Iglesias, A., G´alvez, A.: A New Artificial Intelligence Paradigm for Computer-Aided
Geometric Design. In: Campbell, J.A., Roanes-Lozano, E. (eds.) AISC 2000. LNCS (LNAI),
vol. 1930, pp. 200–213. Springer, Heidelberg (2001)
15. Iglesias, A., Echevarr´ıa, G., G´alvez, A.: Functional networks for B-spline surface
reconstruction. Future Generation Computer Systems 20(8), 1337–1353 (2004)
16. Knopf, G.K., Kofman, J.: Free-form surface reconstruction using Bernstein basis function
networks. In: Dagli, C.H., et al. (eds.) Intelligent Engineering Systems Through Artificial
Neural Networks, vol. 9, pp. 797–802. ASME Press (1999)
17. Pottmann, H., et al.: Industrial geometry: recent advances and applications in CAD.
Computer-Aided Design 37, 751–766 (2005)
18. Renner, G., Ekrt, A.: Genetic algorithms in computer aided design. Computer-Aided
Design 35, 709–726 (2003)
19. Varady, T., Martin, R.: Reverse Engineering. In: Farin, G., Hoschek, J., Kim, M. (eds.)
Handbook of Computer Aided Geometric Design. Elsevier Science, Amsterdam (2002)
20. Weiss, V., Andor, L., Renner, G., Varady, T.: Advanced surface fitting techniques.
Computer Aided Geometric Design 19, 19–42 (2002)
21. Yoshimoto, F., Harada, T., Yoshimoto, Y.: Data fiting with a spline using a realcoded
algorithm. Computer-Aided Design 35, 751–760 (2003)
17.05.2014
Sayfa 16
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
17.05.2014
Sayfa 17
Download

2007-Free trim calculation using genetic algorithm