213
PENERAPAN TEKNIK COMB INE D TOPOLOGICAL PATTERN AND GEOMETRIC SHAPE MATCHING UNTUK PENARIKAII LAYOUT AKOMODASI KAPAL DjauharManfaat* i
ABSTRAK Dalam prosesdesaintata letak (layout) ruangandalam bidang aplikasi, sepertiteknik sipil, arsitektur dan perkapalan,terdapatbanyaksistemCaseBasedDestgn(CBD). CBD adalahsebuahpendekatandalamdesain dimanauntuk menghasilkandesainbaru desainermenggunakanataumemodifikasikasus-kasusdesainlama (design cases).Dalam sistem CBD, pattern matchingadalatrsalahsatu proseskunci dari prosespenarikan kasus-kasusdesain.BeberapasistemCBD yang adamenggunakantek,rik symbolicpattern matching urfittk menarik desainlayout. Kelematrandari teknik ini ialah bahwasistemtidak dapatmenarik deskripsi snuktrn dari lryout, misalnya dalam bentuk image, topologi dan geometri.Beberapasistem CBD yang lain telatr menggunakantetrll.ik image dan topologi, tetapi belum ada yang menggunakanteknik geometri. Dalam makalatr ini, sebuah tek.aik combined topological paltern and geometric shape matching untrk proses penarikan desain lryout akomodasikapal dipresentasikan.Hasil dari. beberapapercobaanimplementasi teknik tersebut dalam sebuah sistem komputer unhrk menarik kasus-kasusdesain lryout tersebut dan mengurutkantingkat kesamaanantaramerekadengansebuahlayout templatd(input) juga disajikan. Dari hasil percobaandapatdisimpulkanbahwasistemkomputerdapatsecaraefektif menunjangprosespenarikan deqin layout yang lebih komperhensif,karena selain pola topologi, benhrk geometri dari lryout jnga dipertimbangkan. Kata kqnci: tata letak (layout), sistemCaseBasedDesign,pattern matching,topologicalpattern matching, geometric shape matching, combined topological pattern and geometric shape matching, penarikandesainIayout
ABSTRACT In the layout designprocessin different applicationareas,suchas civil engineering,architectureand naval architecture,there are different CaseBasedDesign (CBD) systems.CBD is a desigrrapproachwhere utilise or modiS existinglayout designcases.In CBD systems,pattemmatchingis one of key desigrrers processesin casewithdrawal. Someof the existing CBD systemsuse symbolicpatternmatching techniques to withdraw layout design cases.One of the weaknessesof thesetechniquesis that the systemscannot withdraw structural descriptionsof layouts, e.g., in the form of images,topological pattemsand geometic shapes.Someother systemshavealreadyusedimage-basedandtopologicalpatternmatchingtechniques,but they have not used the geometic shapematchingtechnique.In this paper,a combinedtopological pattern and geometric shape matching technique for withdrawal of ship accommodationlayout design casesis presented.Someexperimentalresultsof implementingthis tecbniquewithin a computersystemto withdraw layout design casesand order their similarities with an input layout template are also shown. From the results,it can be concludedthat the computersystemcan effectively supportthe layout desigrrwithdrawal sinceit involvesnot only the topologicalpattem,but also the geometric processmore comprehensively, shapeoflayouts. Keywords: laiout, CaseBasedDesignsystems,pattemmatching,topologicalpatternmatching,geometric shapematching,combinedtopologicalpattem and geomefficshapematching,layout desigt casewithdrawal
*
JurusanTelcnikPerkapalan,FTK ITSSurabaya
Vol. 14,No. 4, Nopember2003- MajalahIPTEK
1. PENDAHT]LUAIY Dalam mengawali proses desain layout ruangan akomodasi kapal, desainer sering menggunakan diagram(dalamhal ini bubblediagram ataudiagram gelembung)dan sketsa untuk menghasilkansuatu desain layout awal. Dalam pembuatan diagram, desainer menggambar diagram kedekatan antar ruang yang hasilnya dikenal sebagaipola topologi (topological pattern) dari layout tersebut. Dalam pembuatan sketsa, desainer menggambarkan ruangan-ruangan besertabentukgeometri(geometric slnpe) masing-masingberdasarkanpola topologi tersebut, sehinggga desainer mengkombinasikan pola topologi dan bentuk geometri dari layout. Dengan demikian, apabila desain layout lama digunakansecaralangsungsebagaipemecahanawal untuk proses desain baru, maka dua manfaat didapatkan,yaitu: o
Tugas desainer unfuk membuat suatu desain Iayout baruberkurang,dan
o
Desainer dapat memanfaatkankombinasi pola topologi danbentukgeometri dari layoutlama.
Selanjufrrya, dalarn proses desain sebuah layout baru" desainer pada umurnnya teringat atau menggunakansatu atau lebih desain layout lama yang ada dan sesuai dengan permasalahandesain layout yang akan dipecahkannya.Dalam hal ini, desainermembandingkandan menentukantingkat kesamaanantaradesainlayout lama dengansebuah sketsa sebagai ilustrasi dari apa yang ada dalam benak desainer.Jadi disadari atau tidak, desainer sebenarnyatelah melakukan proses yang dikenal denganpattern matchingantarasketsasebagaiinput dengandesainlayout-layouflama. Terdapat banyak sistem yang CBD mengimplementasikan proses pattern matching untuk tujuan penarikandesainlayout lama atauyang biasa dikenal dengan layout case retrieval, dan pattern matching ini merupakansuatuproseskunci dalamcaseretrieval tersebut(Manfaatdkk. 1996). Ada beberapa teknik pattern matching yang digunakan. Misalnya, sistem ASA (Architectural Symbolic Assistant) (Giretti dkk. 1994\, SEED (Flemming dkk. 1997), FABEL (VoF dkk. l99a) MajalahIPTEK - Vot. t+, No. 4, Nopember2003
dan sistem yang dikembangkanoleh Gross dkk. (1994) menggunakan teknik symbolic pattern matching untuk menarik desain layout bangunan rumah atau gedung, sementara sistem yang dikembangkan oleh Manfaat dan Buana (2002) menggunakan teknik yang sama tetapi untuk penarikan desain layout ruang akomodasi kapal. Jenis pattern matching ini digunakan untuk mendapatkan tingkat kesamaan simbolik dan numerik dari atribut-atribut lryout, bukan struktur layout, misalnya dalam bentuk topologi, bentuk geometri,imagedanlainlain. ASA menggunakanrule-based approach, berupa theory rule sets, untuk menganalisis dan mengklasifikasikan bentuk layout berdasarkan kelas-kelaspola topologi (pola hubungan antar ruang) dan pola hubungan antara numgan untuk akses (misalnya koridor) dengan ruang-numg lainnya. Untuk tujuan iri, theory rule sets dari sebuahinput layout design case di-matched dengan theoryrule setsdari kelas-kelasyang adadari kedua jenis polatersebut. Dalam SEED, sebuahloyout design case diindeks dengansebuahhirarki problem specifications yang meliputi objects (misalnya,komponentoyout) yang dicirikan dengan suatu kumpulan pasangan attribute-value (misalnya, ukuran, frrngsi dan luas, dengannilai masing-masing).Untuk menarik design ccEes,hirarki problem specifications dari sebuoh perrrasalahandesainlayout baru di-matched dengan hirarki problem specifications dat'r design caltes, objek denganobjek dan atribut denganatribut. Dalam FABEL, kumpulanpasanganattribute-value yang merepresentasikan spesifikasi desain (ukuran, firngsi, luas dan lain-lain) ruang-ruang dari pennasalahandesainlayout baru di-matched dengan kumpulan sejenis dan design cases.Dalam sistem Gross dkk. (1994), diagram matching dilalokan. Dalam hal ini hand-drawndiagrams yang diga:nbar oleh desainer di-matched dengan sebuah katalog diagram dari design ccses. Sementaraitu, sistem yang dikembangkanoleh Manfaat dan Buana eAOz) menggunakan attribute-value matching unhrk membandingkanantara spesifikasi desain (ukuran utama, tipe, kecepatankapal dan lain-lain) dari
2t5
sebuahpermasalahandesainlayout akomodasikapal baru dengan spesifikasi desain kapal-kapal lama (ship design cases)untuk tujuan penarikan layout ruangakomodasikapal-kapaltersebut. Sistem FABEL, disamping symbolic pattern matching, juga menggunakanteknik image-based matching dan topological pattern matching untuk menarik desain layout rumah. Selain itu terdapat juga sistemyang dikembangkanoleh Manfaat dkk. (20020 dan INSPIRE (Intelligent Spatial Design Retrieval) (Pangastuti2001) yang menggunakan teknik topological pattern matching unttrk menarik desain layout ruang akomodasi kapal, dimana INSPIRE juga mempertimbangkanarah hubungan antarruang. Dalam makalah ini akan dibahas sebuah teknik combinedtopological pattern utd geometricshape matchfng untuk penarikan desain layout rumg akomodasikapal. Teknik ini tidak digunakandalam sistem-sistemCBD tersebutsebelumnya,sehingga teknik ini akan memberikankontribusi baru yang signifikan dan lebih komperhensifdalam penarikan desain layout lama. Unftrk lebih memahami karakteristik dan kemampuan dari sistem yang menggunakantopological pattern matching, yait;.t yang relevan dengan teknik kombinasi yang diketengahkan dalam makalah ini, maka dalam Tinjauan Pustaka (Bab 2) sistem FABEL, sistem yang dikembangkanoleh Manfaat dkk. (2002) dan INSPIRE akan dibahassecarasingkat.Dalam Bab 3 akan dibatrasmetodologi yattg menguraikansecaf,a detail teknik kombinasi ini, sementaradalamBab 4 disajikan hasil-hasil implementasi dan 4pembahasannya. Akhirnya, makalahini akanditutup dengansebuahsimpulandalamBab 5. 2. TINJAUAN PUSTAKA Sepertiyang telah dijelaskandalam Bab l, sistem CBD yang menggunakan teknik yang relevan dengan teknik yang disajikan dalam makalah ini adalah FABEL, sistem yang dikembangkanoleh Manfaat dkk. (2002) dan INSPIRE yang menggunakanteknik topological pattern matching. Oleh karena itu, dalam bab ini karakteristik dan
kemampuan ketiga sistem ini dalam ,konteks topological pattern matching akan dibahas secara singkat. Dalam FABEL, untuk merepresentasikanpola topologi, satusub-sistemnya yang dinamakanTOPO (Coulon 1995) digunakan.TOPO mampu menarik hubungantopologi obyek-obyek dari layout cases berdasarkan pada suatu query (suatu input permasalahan desain oleh desainer) rmtuk mengkoreksi, memperluas atau merinci query tersebut. Dalam TOPO, suatu hubungan topologi direpresentasikanoleh stntu grap& yang berisi nodes yang merepresentasikanobyek-obyek dan edges yang merepresentasikanhubungan antar obyek tersebut. Oleh karena itu, pembandingan hubungantopologi dilakukan denganpembandingan graphs tersebut.Untuk pembandingangraph .inr TOPO menerapkansebuahmacimumcliquefinding algorithm, suatu jenis algorimra graph matching yangdidefinisikanolehBarrowdanBurstall(L976). Teknik topologi dalam FABEL khusus digunakan unttrk mendukung penyelesaian masalah penempatan obyek dalam layout seperti layout kantor. FABEL menggunakanTOPO untuk menarik case desain layout yang dapat memecahkansuafu permasalatran penempatanobyek dalam layout. Qleh karena itu, sistem ini tidak digunakan untrk membandingkan semua hubungan topologi dari ruangsuatulayout secarafangsung. Berbeda denganFABEL yang memfokuskanpada pembandinganhubungantopologi dari obyek suatu permasalahanpeletakanobyek suatu lryout, teknik topologicalpattern matchingyang digunakandalam sistem yang dikembangkan oleh Manfaat dklc (2002) dan INSPIRE difokuskan pada pola semua kedekatan antar ruang dalam suatu layout. Disamping itu, hal lain yang membedakanteknik keduasistemtersebutdenganteknik FABEL adalah bahwa teknik FABEL menggunakan mmimum clique /inding algorithm yang didefrnisikan oleh Barrow dan Burstall (1976),sementarateknik yang digunakankedua sistemtersebutadalahassociation
Vol. 14,No. 4, Nopember2003- MajalahIPTEK
graph technique seperti yang didefrnisikan oleh BallarddanBrown (1982). Sementara itu, perbedaan antara sistem yang dikembangkanoleh Manfaat dkk. (2002) dengan INSPIRE terletak pada pendekatanyang digunakan untuk mengukur tingkat kesamaanpola hubungan topologi antar layouf. Sistem pertama melakukan proses pattern matching antar pola ini tanpa mempertimbangkan arah hubungan antar ruang dalam layout (misalnya, barat, timur, utara dan selatan), sedangkan dalam INSPIRE arah-arah tersebut dipertimbangkan.Keturtungandari sistem pertamaadalahtingkat kesamaanantara dua layout yang dibandingkan lebih tinggi dari pada yang dihasilkan oleh INSPIRE karenajumlah pasangan ruangan yang bersesuaian fungsinya yang membentuk pola hubungan topologi yang sama anwa kedua layout tersebutlebih banyak.Namun, kelemahan dari sistem pertama dibandingkan dengan INSPIRE adalah bahwa jika dua layout dibandingkan(misalnya layout I dan 2), maka arah hubunganantarasetiapduaruanganyangberdekatan yang mempunyaifrrngsi-fungsitertentu padalayout 1 dapat berbeda dengan arah setiap dua ruangan yang berdekatanpadalqtout 2 denganfungsi-fungsi yang samasepertidalamloyout 1. Dengandemikian, dalamkonteks arahhubunganantarruangan,sistem pertamatersebutkurang presisi dalam memperoleh basil pattern matching, meskipun dalam konteks perolehantingkat kesamaanmaksimum antara dua layout sistemtersebutsudahsangatmemadai. 3. METODOLOGI Seperti yang disebutkan dalam Bab 1, dalam makalah ini diketengahkan teknik combined topological pattern wtd geometric shape matching untuk mendapatkankesamaanbentukgeometriantar ruangan, disamping kesamaanpola topologinya, sehingga hasil pattern matching akan lebih komprehensifdibandingkandenganyang dihasilkan oleh sistem yang hanya menggunakantopological pattern matching.Metodologi dari penerapanteknik ini diuraikandalambab ini.
MajalahIPTEK - Vol. 14,No. 4, Nopember2003
3.1 Langkah-Langkah Teknik Combined Topological Pattern and Geometric Shape Matching
Untuk mendapatkanhasil akhir pattern matching, teknik ini menggunakan dua langkah: i)
Proses topological pattern matching; untuk menghasilkantingkat kesamaanpola topologi antara dua layout, sehinggapasangannumgan yang bersesuaianfungsinya dari kedua layout yang mempunyaipola kedekatanantar ruangan (topologi) yang samadidapatkan.
ii) Proses geometric shape matching; untuk mengukur kesamaan bentuk geometri antara setiappasanganruanganyang didapatkandiatas. Dengan menjumlahkan ukuran-ukuran yang dihasilkanunfirk semuapasanganruangan,maka ukuran keseluruhankesamaanbenhrk geometi antaradualayout dapatdihasilkan.
Untuk memungkinkan proses pattern matching diatas direalisasikan, maka desain layout har-us direpresentasikandalam aspek-aspek topological pattern dangeometricshape.Oleh karenaitu, dalam bab ini representasilayout dalam kedua aspek ini akan diuraikan, dilanjutkan dengan uraian tentang keduatek,nkp attern matching diatas. 3.2 RepresentasiDesain Layout 3.2.1 Pola topotogi (topological pattern)
Dalam teknik yang diketengahkandalam makalah iru associationgraph techniqueyang didefinisikan oleh Ballard dan Brown (1982) digunakanuntuk proses topological pattern matching. Teknik ini menggunakansuatu stnrktur data yang dinamakan associationgraph danclique-finding algorithm.
Untuk menjelaskanteknik tersebut,maka beberapa istilah yang berkaitan dengan svatu graph perlu didefinisikan. Suatu graph berisikan kumpulan nodesV, kumpulanproperties P dari nodestersebu dan kurnpulan relations R yang mendefinisikan pasangan dari nodes. Suatu contoh dari suatu graph diberikandalamGambarl. Node representasi vl dan v3 mempturyaiproperty pl, v2 dan v4
2t7 mempunyaiproperty p2, danedgesantaruvl dan v2 dan antara v2 dan v3 masing-masingmempunyai relalion rl, dan antara v3 dan v4 dan antarav4 dan v I masing-masingmempurryairelation 12. Pr
Fr
adalah sebuahdiagram pohon dimana settapnode mempunyaiduanode lain sebagaianaknya.Sebuah contoh sederhanadiberikan dalam Gambar2. Garis penuh dari benhrk objek dalam Gambar Za adalah batas(kontour) dari bentukini. Benhrk ini kemudian dibagi menjadi beberapasegitiga, yang bertujuan akhir untuk menyederhanakan bentuk ini me4iadi sebuah quadrilaterah suatu bentuk dimana kontournyaterdiri dari empatgaris.
,r"
Gambar1. Representasisebuahgraph(Ballard dan Brown 1982). Pola topologi dari layout direpresentasikandalam graph bentuk diatas, dimana node merbpresentasikan ruangan dan edge merepresentasikan hubungankedekatanantarruang, yaifu dua nrangansaling berbatasan.Sementaraitu, sebagaiproperty dari ruangan adalah fungsi dari ruangan. 3.2,2 Bentuk geometri (geometricshape) Untuk proses geometric shape matching antara setiappasangannrangan yang dihasilkandari proses topological pattern matching, teknik planar shape matching yang dikembangkanoleh Leu dan Huang (1988) digunakan.Pemilihanteknik ini didasarkan pada salahsatukarakteristikutamanya,yraitubahwa representasidan proses matching bentuk geometri objek tidak tergantungpada lokasi dimana bentuk tersebutdipandangatau dikenal denganistilahviewindependent. Dalam teknik planar shape matching, untuk representasibentuk geometri suatu objek, terdapat tiga asnmsi, yaitu (i) objek bidang datx Qtlanar), (ii) garis kontournyatertutup,dan (iii) garis tersebut tidak saling berpotongan. Untuk proses shape matching, suatu bentuk objek direpresentasikan dalam suatu sb:uktur binary tree dimana nodes didalamnya merepresentasikan segitiga-segitiga hasil dari penyederhanaan atau pembagian Qnrtition) dari bentuk tersebut.Sebuahbinary tree
tt
- - - - - ''" '
- .tt'
^\
c*
D' E+ (b)
Gambar2. Partisi bentuk: (a) Suatubentuk terpartisi dalamsegitiga;(b) Hasil binary tree dari partisi pada gambar(a) (Leu dan Huang 1e88). Pada langkah pertamadari penyederhanaanbentuk dalam Gambar 2a, tiga segitiga (C, D dan E) dihasilkan. Dengan menggabungkan sisi setiap segitigatersebutdan menggantinyadenganalasdari setiapsegitigatersebut(garis-garisputus selaingaris S), maka akan menyederhanakanbentuk tersebut menjadi sebuahquadrilateraL Langkah berikutnya adalahmembagiquadrilateral tersebutdengangaris S menjadi dua segitiga,yaitu A dan B. Penentuan arahgaris pembagiS ini didasarkanpadaperbedaan luas yang paling besar antara dua segitiga hasil pembagian quadrilateraL Dengan demikiaq jika arah garis pembagi S dalam Gambar 2a ditentukan berlawanan,makadiagrampohon dalam Gambar2b akanberubah. Setelahpenyederhanaan benhrk dalam Gambar 2a menjadi beberapasegitigadilahrkan, sebuahbinry rree dibenhrk (ihat Gambar 2b). Node akar dari Vol. 14,No. 4, Nopember2003- MajalahIPTEK
2t8
diagram pohon ini adalatr garis pembagi S dan keduaanakdari S adalatrsegtiga A dan B. Segitiga C dan D masing-masingterletak atau melekatpada sisi kiri dan kanan dari segitigaA. Oleh karena itu, dalam diagram kedua segitiga tersebut merupakan anaksebelahkiri dankanandari segitigaA. Demikian pula, segitigaE melekatpadasisi kiri dari segrtiga B, sementara tidak ada segitiga yang melekatpadasisi kanan segitigaB. Oleh karena itq dalam diagram, segitigaE adalahanak sebelah kiri dari segitiga B, sementaraanak sebelahkanan dari segitigaB adalahkosong. Tanda "+" drn ',-" dalam diagram pohon dalam Gambar 2b menunjukkan apakah sebuah segitiga terletak di dalamatau di luar segitigainduknya.Jika "+", maka sebuahsegitiga terletak di luar segitiga induknya, dan sebaliknya. Disamping tanda-tanda . tersebut,tiga atibut berikut ini juga dicantumkan dalam setrapnode: o o o
Luas segitiga. Perbandinganantara tinggi (ft) dan alas (a) segitrga:h/a. Perbandinganantara proyeksi sisi kiri segitiga padaalassegitiga(b) danalassegitiga(a): b/a.
3.3 Topological pottern Matching SepertitelahdisebutkandalamSub-Bab3.2.1,untuk proses topological pattern matching, association graph teclmiqueyang didefinisikanoleh Ballard dan Broum (19S2) digunakan. Hal ini karena kemampuan teknik ini dalam mencari semua isomorphisms (kemiripan) antara subgraptu dari suatu graph dengan subgraplu dari graph lan (Ballard dan Brown l9S2). Teknik tersebut menghasilkan"the best match', antara &a graph, sementarateknik-teknik yang lain mendefinisikan grqph isomorphismantara6n graphyang bertujuan untuk menemukan kemiripan yang eksak (exact match) antar graph dimana nodes atau arcs tidak bolehhilang dari siarfi, graph ataugraphyang lain. Jika diberikan duagraph yang didefinisikandengan (Vr, P, R) dan (V2, P, R), untuk membandingkandua graph tersebut sebuah association graph G digambar. Association graph adalah suatu graph MajalahIPTEK - Vol. 14,No. 4, Nopember2003
yang nodes-nyaadalah pasangannodes dari dua graph yang dibandingkan yang mempunyai kesamaanproperties, dan edges menghubungkan nodes daxi association graph tersebut yang menunjukkankeadaanyang compatibl,e.pengertian compatible disini adalah bahwa jika node l, misalnya, denganproperty x dihubungkan dengan node2 denganproperty y dalamgraph I (Vr, p, -R), maka dalam graph 2 (V2, p, R) terdapat node 1,, misalnya, dengan property x yang dihubungkan dengannode2' denganproperty y. Unhrk menggambarG, gambarsebuahnode dari G denganlabel (v1,v2)untuk setiapv1 dalam V1 danv2 dalam Vz dengan syarat bahwa v1 dan v2 hanrs mempunyai kesamaan property p dalam p. Selanjutnya, hubungkan dua node (v1,v2) dan (v'r,v'z) dari G yang menunjukkan keadaanyang compatible sesuai dengan R (yaitu r(vr,v'r) = r(v2,v'2)). Sebagaicontohpembuatansuatuansociation graph, petimbangkan dua layout sederhana dariicatering decks kapal penumpangdimana pola topologinya akan dibandingkan (lihat Gambar 3). Untuk membuatassociationgraph tersebut,langkah awal yang harus dilakukan adalah membuat nodes daigraph tersebutdenganmemasangkannodes(ruang_ ruang) dari kedua layout dimana ruang_ruang tersebutmempunyaiproperties yang sama.Dalam contoh ini frurgsi dari ruang dijadikan sebagai properties. Fungsidari ruangbiasanyadiekspresikan dengannama dari ruang tersebut. Sebagaicontoh, dua ruang yaitu gatteyl dan galley2, memprmyai fungsi yang sama yaitu galley. Jadi hasil dari langkahawal tersebutadalahnodes(Al : A2), (Bl : B2) dan seterusnya.Langkah selanjutnya adalatr menghubungkan dua nodes yang menunjr*kan keadaan yang compatible, artinya keduanya memiliki jenis hubunganyang sama.Dalam hal ini kedekatanantarruang digunakansebagaihubungan. Sebagaicontoh,ruang Ai berdekatandenganruang Bl padalayout l, dan ruangA2 berdekatandengan ruang 82 pada layout 2. Jadt dalam association graph, node (Al: .4,2)dihubungkandengannode (Bl : B2). Association graph yarrrg dihasilkan dihurjul.kandalamGambar4.
219
TopologicalPatterns
LayouE s1
R1
./
-\
A1
P1
\ D1
_.2 G1
Ship1
s2
R2
o'I"lo,
G2
P2
Ship2
f--l
space
O node
-
Adjacency
Gambar 3. Dua layout sederhanauntuk pembuatansuatuassosiationgraph (Manfaat 1998). antara dua layout dalam Gambar 3. Dengan demikian, dapat diamati disini bahwa jika drnlayout yang dibandingkan mempunyai jumlah ruangan yang lebih banyak atau lebih sedikit dari dua layofi dalam Gambar 3 dan pola topologinya juga berbeda, maka association graph yang dihasilkan juga akan berbeda. 3.4 Geometric Shape Matching Gambar4. Suatu assosiation graph yang dihasilkan dari pembandingan dua layout dalam Gambar 3 (Manfaat 1998). Dari dua graph dalam Gambar 3' hasil pembandinganterbaik (the best match\ antara kedua graph ini dapat didefinisikan dengan menggunakan suatu a"esociation graph. Hal ini dapat dicapai denganmenemukan kumpulan terbanyak dati nodes 1'ang berkorespondensi dalam association graph l'ang semua hubungan antar nodes-nya compatible. lni berarti mencari kumpulan nodes denganjumlah terbanyak yang secaratotal terhubung yang disebut dengan suatttclique (Ballard dan Brown 1982).Jadi ini merupakan masalah untuk menemukan suatu clique dengan jumlah nodes terbanyak' Sebagai contoh, pada association graph dalan Gambar 4 clique dengan jumlah nodes terbanlak adalah kumpulannodes(Al: A2), (81 : B2), (D1 : D2) dan (Sl : 52) yang rnenunjukkan "the best match"
Sepertitelah disebutkandalam Sub-Bab 3.2.2, untuk proses geometric shape matehing teknik planar shape matching yang dikembangkan oleh Leu dan Huang (1988) digunakan Teknik in juga viewindependent karena memungkinkan transfonnasi pandanganantara bentuk objek yang dibandingkan, yang membuat proses matching tidak terpengaruh (invariant) terhadaprotasi, penskalaan,translasi dan skewing. Dalam teknik diatas proses matching antara dua bentuk objek direalisasikandengan membandingkan representasi diagram pohon (binary tree) kedaa bentuk objek tersebut.Dalam hal ini, kedua diagram tersebut dibandingkan dari level teratas sampai keduanya (top-down). Artinya, terbawah dibandingkan node per node dad.node akar ke nodes pada tingkat-tingkat dibawahnya sampai dengan nodes pada tingkat terbawah. Prosespembandingan
Vol. 14,No. 4, Nopember2003- MajalahIPTEK
kedua diagram tersebut dilakukan sesuai dengan urutan breadth-first-search (Leu dan Huang lggg). Dalam cara ini, langkah pertama adalah membandingkan nodes akar dari kedua diagram. Kemudian, proses berlanjut dengan membandingkan
proses topological pattern matching, maka semua ukuran perbedaan yang dihasilkan dijumlahkan untuk mendapatkansuatu ukuran perbedaanbentuk keseluruhanantankeduaIayout.
anak-anak sebelah kiri dari kedua node akar tersebut, dilanjutkan dengan anak-anak sebelah kanan dari kedua node akar tersebut, kemudian anak-anak sebelah kiri dari anak-anak sebelah kiri dari kedua node akar tersebut,dan seterusnya.
Secaramatematis,perbedaanbenhrkdari dua objek atauduadiagrampohonTA danTB,yaitudIT.TA,TB), dimanapasangan-pasangan nodes yang bersesuaian adalah[A(t), B(I)], [A(2), B(2)J, ..., [A(n); B(n)J, dapatdirumuskansepertidalampersamaan (l).
Gambar 5 menunjukkan sebuah contoh sederhana dari proses pembandingan dua diagram pohon. Jika
dt(TA,T B) = | an\.a1D, B(i))
terdapat diagram I dan 2 dalarn Gambar 5a. maka perbandingan kedua diagram sesuai dengan urutan
dimana: aryaiArS, B(i)J adalahperbedaan antara nodesA(i) danB(i) atauyang dapat dirumuskan sepertidalampersamaan (2).
breadth-first-search diilustrasikan dalam Gambar 5b. Dalam setiap perbandingan dua node, perbedaan node atau benhrk objek, dengan memperhatikan
on[N1i;, Nliy]= lrr1il I a1i)x weight[N6{rh6 / a(, x weight[Nfi)]+ bfi)/ a(i) x weight[N6{+)b0/a(, x weight[Ng]
enpat akibut dari setiap node yang telah dijelaskan diatas, ditentukan dan ditambahkan kedalam perbedaan node kumulatif yang telah didapatkan sejauh ini. Dengan dernikian, hasil pembandingan kedua diagram (bentuk objek) adalah perbedaan bentuk kumulatif terakhir, yang mengindikasikan nilai perbedaanantara kedua bentuk tersebut.Untuk pembandingan dua layout, uraian diatas adalah
........(2) dimana: N(i), N(il = sebuah node dalam diagram pohon1,2.
untuk sepasangruangan yang bersesuaianfungsinya. Dengan juga membindingkan bentuk-bentuk
h(i), h(j) = tinggi segitiga dau;inodesN(t), N(i)
pasangan ruangan lainnya yang dihasilkan dari
Diagram pohon I
_/\
/\ f'l i( 7i'fi't( Diagram pohon 2
(a)
Pembandingan antara diagram pohon I dan sesuaiurutan breadth-firs t-searc h.
Ket: (-)
->
: Pembandingannode. : Arah dari urutan
(b)
Gambar5. Perbandingan duadiagrampohonsesuaiurutanbreadth-/irst-search. MajalahIPTEK - Vol. 14,No. 4, Nopember2003
..............( l)
-? 221 a(i), a(j) : alas segitiga dari nodes N(i),
N(il. b(i), b(j) = proyeksi sisi kiri pada alas segitigadainodes N(t), N(il. Weight[N(i)J, WeightIN(ilJ = perbandingan antara luas dari nodes N(i), N(il dan luas total bentukobjekdari diagrampohonl, 2. Penggunaansalah satu tanda (T) tergantungpada atibut tanda dari kedua node. Jika kedua atribut tanda berbeda, maka tanda "+" digunakan; sebaliknya,tanda"-" digunakan. 4. HASIL DAN PEMBAHASAI\I Teknik combinedtopologicalpattern and geometric shapematchingyang diketengahkandalammakalah ini tela! diimplementasikandalam sebuah sistem komputer. Implementasi ini menggunakan Harlequin LispVorks (Common Lisp and CLOS) (The Harlequin Group Limited 1994) yang dioperasikandalam sebuahPC - PentiumtV. Untuk mengevaluasi association graph technique dan plano shape matching yang digunakan,hasil-hasil matching antara sebuah layout template sebagai input dan enam buah layout akomodasidari enam buah kapal barang (general cargo) denganukuran utama yang hampir sama (lihat Gambar 6) yang disimpandalamsistemdisajikandalamTabel l. Dalam Tabel 1, pertama-tama layouts hasil topological pattern matching diurutkan dari yang mempunyai jumlah pasangan ruangan-nrangan dalam clique yang paling banyak (paling sama terhadapinput) di trutan teratassampaidenganyang paling sedikit (paling berbeda terhadap input) di urutanterbawah.Dalam hal ini, shiy06 mempunyai tingkat kesamaantertinggi terhadap input dengan jumlah pasangannxmgan sebanyak ll pasang, diikuti secaraberurutan olehship03, ship-05,ship02, ship-0| dan ship-04, masing-masingdengan jumlah pasangan ruangansebanyak 9,8,7,6 dan 6 pasang.Pasangan-pasangan nranganyang dihasilkan juga disajikandalamtabeltersebut.
Setelah layouts hasil matching diunrtkan berdasarkan hasil topological pattern matching, perbedaanbentuk geometri dari setiap pasangan nranganyang dihasilkandiukur dan kemudianrmtuk setiap layout ukuran-ukuran perbedaan ini diakumulasikan untuk mendapatkanukuran total perbedaanbentuk geometri arfiar layout. Sebagai contoh, ukuran total ini dari hasil matching antara ship06 denganinput adalahsebesar 0.10996.Dalam hal ini, semakin besar ukuran ini, maka semakin berbeda(tingkat kesamaannya rendah) antaralayout case daninput, dansebaliknya.Untuk dua ataulebih layout yang mempunyaitingkat kesamaantopologi yang samaterhadapinput Qumlahpasangan ruangan dalam clique sama), maka untuk ukuran total perbedaan bentuk geometri, layouts tersebut diurutkan dari yang mempunyaiukuran yang paling kecil (paling sama terhadapinput) sampai dengan yang paling besar (paling berbedaterhadapinput). Sebagaicontoh, ship-|| dan shipI4 mempunyai skor kesamaantopologi terhadapinput yang sma, yaitu 6. Shiyll mempunyai ranking yang lebih tinggi dibandingkandenganship-04, karenaukuan total perbedaan bentuk geometri untuk ship|l (2.3070q lebih kecil dari pada untuk ship-04 (3.06230). Hasil-hasil di atasmenunjukkanbahwa assoeiation graph techniquedanplant shapematchingbekerja secaraefektif. Teknik+eknik ini dapat menemukan kesamaanmaksimum antar layouts, yaitu jumlatl maksimum pasangan-pasangannrangan yang dihasilkan dan trkuran total perbedaan bentuk geometri yang paling kecil dari d.ualayout. Hasilhasil di ataspadaumumnyajuga mencerminkancara manusia membandingkan dan menentukan kesamaan antara dua layouts baik dalam aspek topological pattern maupun geometric shape, dimanamerekacenderunguntuk mencari kesantaan maksimum antara drn layouts. Jadi, teknik-teknik diatas dapat mensimulasicara manusia mengenali pola-polalayout.
Vol. 14,No. 4, Nopember2003- MajalahIPTEK
222
layout tenplaE
Prorbion . Storr
Representasl graph
Clcw 1
Lauitott
C rcw 2. e
II
5
(,a
Elghc
opcnrns
gI G.lh,
! !
lrlcsirootn
E
Cruw3
Crcw4
Ship-01
g{pO2
Reprcsentasi graph
Representaslgraph
R€prE enta3lg[aph
MajalahIPTEK - Vol. 14,No. 4, Nopember2003
$lFoa
RrDruscnt.lgr.ph
gtb{3
f.pr.Jatrdt
s{3
Dh
frfc,.ilelfaptr
IGtermgm: PS Lv C Crxr Ms EO $ Gl
:hovisim Stsc :I,alu.nlry :Crnr : Crangway : Iv[esmom ; ngineopcoing : Store : Caltey
L B
ct CE
co QM
Cn' lv[c
:L&r : Boyr : Codc : CtiefEryineer : CtiefOfrcer : Quarterldaster : CO2Room : Machines
TR
st
II
On Bt RR
s
: TallyRoom : Saloon : Iaundry : Oilnan : Boatswain : RefigeratedRoom : Sail
Gambtr 6. Sebuahlayout tenplae rlnn€aambtahlayout akomodasidari enambuahkapal barang(general cogo) besertarepreeenbsigrqh
Y ol. l4,No. 4, Nopember 2003- ndajalah IPTEK
Tabell.
f#X#{;ffr#'E:
"::3 :?;:;JiH'H,fftrT
enam buah tavoutakomodasi darienarn
Kuangan- ruangan hasil matchingantara layout tempiatedan
$ryry-Gangway
0.I 0996
Machines- Machines Messroom- Messroom
0.00000
EngineOpening- EngineOpening Ladder- Ladder
Ship06
ll
t6r.z- cook l&2
Boysl&2 - Boyst&2 Crew3&4- Crew3&4 Crewl&2 - Crewl&2
5.356t6E-09 4.84676E-09
0.00000 7.57476E-W 5.70739E-W s.70739E-@ 7.57476E-@
Galley- Gailey
0.00000
Lu-to.V- LavatoryI Mechine
-
7.49t97E-@
Maahi---
Messroom-Messroom Ladder-Ladder ... LooK f &z - Cook l&2
Ship03
9
eoyrtez- sonr&2
Cook l&2 - Cook Quarta Master- euarter Master I urcw J&4 - Crew3
-lqAA*
0.06436 0.05958 0.29302 0.29302
uoo|( tdtz - cook
Boryl&2 - Boysl&2 Crewl&2 - Crewl&2 Galley- Galley Lavatory- Lavatory Gangway- Gangway
Ship0l
6
Messroom - Mcsroom Crew3&4- Crew4 Crev l&2 - Crew2 Galley - Galley
Lavatory-Lavatory 9*gtlv
- Gangway
Ladder. Laddel-2
Ship04
6
Crew3&4- Crew3 Crcw l&2. Crew I Galley.Galtey ?rovision Storc. provisionStore
MajalatrIPTEK - Vol. 14,No. Nopember , 2003
0.23221 6.793674 0.270332 t.09795 0.n2258 0.232298
9.60987
0.232208
Lavatory- Lavatory
crcw3&4- crew3&4
0.99572
0.068778
Cret*l&2-Crew I
7
7.57476E-W
0.49286
EngineOpening- EngineOpening Ladder- Ladder
Ship02
0.00000
7.57476E-09
uangway - oangway
Laddt
ar:7o6s
f | |
5.70739E-09
Galley- Gailey CO2 Room - CO2 Room
8
0.0@00
I
T--;;;ffi
Crerrt3&4- Crew3&,4 Crewl&2 - Crewl&2
Ship05
0.10996
f
r.68738
**, 0.42710 n r<1ro
t.55t76 0.03527 0.02760 0.t4s26 0.t9756
2.30700
0.34955
2.541s1 0.21560 0.rI333 0.06739 0.r t080 0.0t367
3.06230
225
I
3 I
l
manusia juga Disamping itu, cenderung mengurutkantingkat kesamaanantarlayouts.Dalam kaitan ini, sistemyang telah dikembangkanmampu rmtuk mengurutkantingkat kesamaantersebut.Jadi, sistem ini juga mencerminkan cara manusia mengurutkan tingkat kesamaantersebut. Dengan urutan tingkat kesamaan, sistem ini dapat memberikaninformasi kepadadesaineruntuk dapat lebih membantu desainer dalam memilih suatu layout case tertenht yang dapat digunakansebagai desainawal untuk prosesdesainbaru.
deskripsi struktur dari layouts. Disamping itu, dengandimanfaatkannyadesain-desainlayout iama dengan menggunakanteknik ini, terdapat suafu kemajuanatau inovasi dalam desain,karenaproses desain akan dapat secara signifikan dipercepat; desainermengawali proses desain dengan sebuah desainlayout lama, tidak dari nol. Alhirnya, teknik kombinasi ini mendukungjenis atau cara penarikan layout caseyang saatini tidak dapat dilakukan oleh sistem-sistem CBD yangada.
Keistimewaanlain dari teknik yang diketengahkan dalammakalahini adalah:
UCAPAN TERIMA KASIH
.
Mempercepat proses desain bentuk struktur layout, karena desainermemulai prosesdesain dengan sebuah benhrk sbuktur loyout lama, tidak dari nol.
.
Menghasilkanbentuk stnrktur layout baru yang lebih optimal, karena pada dasamya desainer mengawaliprosesdesaindengansebuahlayout lamayang telah optimal sebelumnya.
.
Meminimalkanjumlah kesalahanyang mungkin timbul dalam melakukanprosesdesain,karena tugas desaineryang berkurang seiring dengan digunakannya Iayout lana.
5. SIMPTJLAN Dalam makalah ini, sebuah teknik combined topological pattern and geometric shape matching amtar layouts akomodasi kapal barang (general cwgo) telah disajikan.Teknik ini mendukungproses pengenalanpola-pola layouts, yang memungkinkan penarikan(retrieval) deskripsi struktur dari desaindesainlayout dalam bentuk topologi dan geometri. Secara kfiusus, teknik geometric shape matching memungkinkan ienarikan bentuk geometri dari layours. Teknik ini dapat memberikan dukungan yang signifikan bagi desaineruntuk menarikdesaindesain layout dari sistem komputer dimana bentuk geometrinyasamaatau serupadenganbentuk yang diinginkan oleh desainer.Dengan demikian, teknik kombinasi memungkinkan desainer untuk mendapatkaninfonnasi yang lebih lengkap tentang
Penulis menyarnpaikanterima kasih yang sebesarbesarnyakepada Dirbinlitabmas, Ditjen, DIKTI, Depdiknas atas penyediaandana unfirk penelitian yang hasil-hasilnyatelah dituliskan dalam makalah ini melalui Program Penelitian Hibah Bersaing X tatun200212003. DAFTAR ACUAN Ballard, D.H. dan Brown, C. M. (1982), Computer Vision, Prentice-Hall,lnc., EnglewoodCliffs. Barrow, H.G. dan Burstall,R.M. (1976),Subgraph Isomorphism RelationalStructuresand Maximal Cliques, Information Processing Letters, 4, pp.83-84. Coulon,C.-H. ( I 995),AutomaticIndexing,Retrieval and Reuse of Topologies in Architectwal Lcyouts,dalamM. Tan dan R. Teh (eds.),The Global Designstudio- Proceedingsof the 6th International Conferenceon Compter Aided Architectural Design Futures '95 (Singapore), Centre for Advanced Studiesin Architecture,National University of Singapore, pp.577-586. Flemming,U., Aygen, 2., Coyme,R. dan Snyder,J. (1997), Case-BasedDesign in A Sofiwme EnvironmentThatSupportsthe Early Plnses,in ML. Maher dan P. Pu (eds.), Issues and Applications of Case-Based Reasoning in Design, Lawrence Erlbaum Associates, Hillsdale,NJ.
Vol. 14,No. 4, Nopember2003- MajalahIPTEK
226
Giretti, A., Spalazzi,L. dan Lemma, M. (1994), A.S.A.-An InteractiveAssistantto Architecmral Design,dalamJ.S.GerodanF. Sudweeks(eds.), Artificial Intelligence in Design '94, Kluwer AcademicPublishers,pp. 93-108. Gross, M., Zimring, C. dan Do, E.(1994), Using Diagratns to Access A Cose Base of Architectural Design, dalam J.S. Gero dan F. Sudweeks (eds.), Artificial Intelligence in Design '94, Kluwer Academic Publishers, pp.129-144. Leu, J. G. dan Huang,I. N. (1988),Planar Shape Matching Based on Binary Tree Shape Representation,Pattern Recognition 2l(6), pp.607-622. Manfaat,D. (1998),Computer-based Approachto Effective Utilisation of Spatial Layout Design Experience, Thesis for Degree of Doctor, University of Strathclyde,Glasgow, Scotland, I.JK. Manfaat,D. dan Buana,IG. N. S. (2002),Rancang Bangun Sistem PerancanganEfektif Layout Kapal Niaga dengan Teknik Case Based Reasoning dan Knowledge Base, Laporan Penelitian Tahun I, Program Penelitian Hibah Bersaing,Dirbinlitabmas,Ditjen. Dikti Tahun 2002/2A$.
MajalahIPTEK -Vol. 14,No. 4, Nopember2003
Manfaat, D., BuanaoI G. N. S. dan Wibowo, T-
(2002), Analisis Pemilihan Layout Kapal
dengan Telvtik
Topological
Matching,Prosiding Seminar Nasional dan Aplikasi Teknologi Kelautan, TeknologiKelautanITS, Surabaya,hal. I-55 68. Manfaat,D., Duffu,A. H. B. danLee,B. S.( Review of Pattern Matching Approaches, Knowledge Engineering Review t pp. 161-189. Pangastuti,R. (2001), Penerapan Teknik Relationship Pattern Matching Pemanfaatan Desain Tataletak Akomodasi Anak Buah Kapal 1000 Orang, Laporan Tugas Akhfu, Teknik Perkapalan, Fakultas T Kelautan,ITS Surabaya. The HarlequinGroup Limited (1994), Lisp User'sGuide. VoB, A., Coulon,C.-H., Grather,W., Linoursti" Schaaf, J., Bartsch-Sporl, 8., Bonrcr, Tammer,E.C., Durschke,H. dan Ifua@, (1994), Retrieval of Similar Very Hybrid Approach in FABEL, dalm Gero dan F. Sudweeks (eds.), Inteligence in Design '94, Kluwer Publishers,pp. 625-640.
