ALGORITMA LABELING CITRA BINER DENGAN PERFORMANSI OPTIMAL PROCESSOR-TIME

Abstract

In the literature, some labeling algorithms of nxn binary image, which are generally claimed as optimal, are only optimal with regards to the algorithmic aspect but not to the architectural aspect. Aside from this, the complexities obtained are not pure because the constant still depends on the value of n. This paper presents a labeling algorithm, which reaches purely Processor-Time optimal performance. This means that the optimal performance is not only reached considering its algorithm but also its architecture and "pure" means that the complexity obtained does not depend on the value of n. The algorithm complexity obtained is O(cn) using O(n) number of processors. In this paper the justification of complexity obtained is given and the performance comparison with other existing algorithms is discussed. Abstract in Bahasa Indonesia : Beberapa algoritma labeling untuk citra biner nxn yang diklaim optimal dalam literatur pada umumnya hanya optimal ditinjau dari aspek algoritmanya saja namun tidak optimal ditinjau dari dari aspek arsitektural. Disamping itu, kompleksitas-kompleksitas yang dihasilkan tersebut tidak murni karena masih mengandung konstanta yang tergantung harga n. Pada paper ini diperkenalkan suatu algoritma labeling dengan performansi optimal Processor-Time murni. Ini berarti optimal tidak hanya dicapai dari sisi algoritma namun juga dari sisi arsitektur dan murni karena kompleksitas yang didapat tidak mengandung konstanta yang tergantung harga n. Kompleksitas algoritma yang didapat tersebut adalah O(cn) dengan menggunakan O(n) prosesor. Pada paper ini diberikan pembuktian terhadap kompleksitas yang didapatkan dan perbandingan performansinya dengan beberapa algoritma yang ada. Kata kunci : Pengolahan citra, Labeling, Citra biner, Performansi optimal Processor-Time.