(PDF) A Coded Cooperative Networking MAC protocol in non transparent multihop WiMAX network

                    IJCSI         International Journal of Computer Science Issues Volume 7, Issue 3, No 9, May 2010 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 © IJCSI PUBLICATION www.IJCSI.org   IJCSI proceedings are currently indexed by: © IJCSI PUBLICATION 2010 www.IJCSI.org IJCSI Publicity Board 2010 Dr. Borislav D Dimitrov Department of General Practice, Royal College of Surgeons in Ireland Dublin, Ireland Dr. Vishal Goyal Department of Computer Science, Punjabi University Patiala, India Mr. Nehinbe Joshua University of Essex Colchester, Essex, UK Mr. Vassilis Papataxiarhis Department of Informatics and Telecommunications National and Kapodistrian University of Athens, Athens, Greece EDITORIAL In this third edition of 2010, we bring forward issues from various dynamic computer science areas ranging from system performance, computer vision, artificial intelligence, software engineering, multimedia , pattern recognition, information retrieval, databases, security and networking among others. As always we thank all our reviewers for providing constructive comments on papers sent to them for review. This helps enormously in improving the quality of papers published in this issue. IJCSI will maintain its policy of sending print copies of the journal to all corresponding authors worldwide free of charge. Apart from availability of the full-texts from the journal website, all published papers are deposited in open-access repositories to make access easier and ensure continuous availability of its proceedings. The transition from the 2nd issue to the 3rd one has been marked with an agreement signed between IJCSI and ProQuest and EBSCOHOST, two leading directories to help in the dissemination of our published papers. We believe further indexing and more dissemination will definitely lead to further citations of our authors’ articles. We are pleased to present IJCSI Volume 7, Issue 3, May 2010, split in eleven numbers (IJCSI Vol. 7, Issue 3, No. 9). The acceptance rate for this issue is 37.88%. We wish you a happy reading! IJCSI Editorial Board May 2010 Issue ISSN (Print): 1694-0814 ISSN (Online): 1694-0784 © IJCSI Publications www.IJCSI.org  IJCSI Editorial Board 2010 Dr Tristan Vanrullen Chief Editor LPL, Laboratoire Parole et Langage - CNRS - Aix en Provence, France LABRI, Laboratoire Bordelais de Recherche en Informatique - INRIA - Bordeaux, France LEEE, Laboratoire d'Esthétique et Expérimentations de l'Espace - Université d'Auvergne, France Dr Constantino Malagôn Associate Professor Nebrija University Spain Dr Lamia Fourati Chaari Associate Professor Multimedia and Informatics Higher Institute in SFAX Tunisia Dr Mokhtar Beldjehem Professor Sainte-Anne University Halifax, NS, Canada Dr Pascal Chatonnay Assistant Professor MaÎtre de Conférences Laboratoire d'Informatique de l'Université de Franche-Comté Université de Franche-Comté France Dr Yee-Ming Chen Professor Department of Industrial Engineering and Management Yuan Ze University Taiwan Dr Vishal Goyal Assistant Professor Department of Computer Science Punjabi University Patiala, India Dr Natarajan Meghanathan Assistant Professor REU Program Director Department of Computer Science Jackson State University Jackson, USA Dr Deepak Laxmi Narasimha Department of Software Engineering, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia Dr Navneet Agrawal Assistant Professor Department of ECE, College of Technology & Engineering, MPUAT, Udaipur 313001 Rajasthan, India Prof N. Jaisankar Assistant Professor School of Computing Sciences, VIT University Vellore, Tamilnadu, India IJCSI Reviewers Committee 2010  Mr. Markus Schatten, University of Zagreb, Faculty of Organization and Informatics, Croatia  Mr. Vassilis Papataxiarhis, Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece  Dr Modestos Stavrakis, University of the Aegean, Greece  Dr Fadi KHALIL, LAAS -- CNRS Laboratory, France  Dr Dimitar Trajanov, Faculty of Electrical Engineering and Information technologies, ss. Cyril and Methodius Univesity - Skopje, Macedonia  Dr Jinping Yuan, College of Information System and Management,National Univ. of Defense Tech., China  Dr Alexis Lazanas, Ministry of Education, Greece  Dr Stavroula Mougiakakou, University of Bern, ARTORG Center for Biomedical Engineering Research, Switzerland  Dr Cyril de Runz, CReSTIC-SIC, IUT de Reims, University of Reims, France  Mr. Pramodkumar P. Gupta, Dept of Bioinformatics, Dr D Y Patil University, India  Dr Alireza Fereidunian, School of ECE, University of Tehran, Iran  Mr. Fred Viezens, Otto-Von-Guericke-University Magdeburg, Germany  Dr. Richard G. Bush, Lawrence Technological University, United States  Dr. Ola Osunkoya, Information Security Architect, USA  Mr. Kotsokostas N.Antonios, TEI Piraeus, Hellas  Prof Steven Totosy de Zepetnek, U of Halle-Wittenberg & Purdue U & National Sun Yat-sen U, Germany, USA, Taiwan  Mr. M Arif Siddiqui, Najran University, Saudi Arabia  Ms. Ilknur Icke, The Graduate Center, City University of New York, USA  Prof Miroslav Baca, Faculty of Organization and Informatics, University of Zagreb, Croatia  Dr. Elvia Ruiz Beltrán, Instituto Tecnológico de Aguascalientes, Mexico  Mr. Moustafa Banbouk, Engineer du Telecom, UAE  Mr. Kevin P. Monaghan, Wayne State University, Detroit, Michigan, USA  Ms. Moira Stephens, University of Sydney, Australia  Ms. Maryam Feily, National Advanced IPv6 Centre of Excellence (NAV6) , Universiti Sains Malaysia (USM), Malaysia  Dr. Constantine YIALOURIS, Informatics Laboratory Agricultural University of Athens, Greece  Mrs. Angeles Abella, U. de Montreal, Canada  Dr. Patrizio Arrigo, CNR ISMAC, italy  Mr. Anirban Mukhopadhyay, B.P.Poddar Institute of Management & Technology, India  Mr. Dinesh Kumar, DAV Institute of Engineering & Technology, India  Mr. Jorge L. Hernandez-Ardieta, INDRA SISTEMAS / University Carlos III of Madrid, Spain  Mr. AliReza Shahrestani, University of Malaya (UM), National Advanced IPv6 Centre of Excellence (NAv6), Malaysia  Mr. Blagoj Ristevski, Faculty of Administration and Information Systems Management - Bitola, Republic of Macedonia  Mr. Mauricio Egidio Cantão, Department of Computer Science / University of São Paulo, Brazil  Mr. Jules Ruis, Fractal Consultancy, The Netherlands  Mr. Mohammad Iftekhar Husain, University at Buffalo, USA  Dr. Deepak Laxmi Narasimha, Department of Software Engineering, Faculty of Computer Science and Information Technology, University of Malaya, Malaysia  Dr. Paola Di Maio, DMEM University of Strathclyde, UK  Dr. Bhanu Pratap Singh, Institute of Instrumentation Engineering, Kurukshetra University Kurukshetra, India  Mr. Sana Ullah, Inha University, South Korea  Mr. Cornelis Pieter Pieters, Condast, The Netherlands  Dr. Amogh Kavimandan, The MathWorks Inc., USA  Dr. Zhinan Zhou, Samsung Telecommunications America, USA  Mr. Alberto de Santos Sierra, Universidad Politécnica de Madrid, Spain  Dr. Md. Atiqur Rahman Ahad, Department of Applied Physics, Electronics & Communication Engineering (APECE), University of Dhaka, Bangladesh  Dr. Charalampos Bratsas, Lab of Medical Informatics, Medical Faculty, Aristotle University, Thessaloniki, Greece  Ms. Alexia Dini Kounoudes, Cyprus University of Technology, Cyprus  Mr. Anthony Gesase, University of Dar es salaam Computing Centre, Tanzania  Dr. Jorge A. Ruiz-Vanoye, Universidad Juárez Autónoma de Tabasco, Mexico  Dr. Alejandro Fuentes Penna, Universidad Popular Autónoma del Estado de Puebla, México  Dr. Ocotlán Díaz-Parra, Universidad Juárez Autónoma de Tabasco, México  Mrs. Nantia Iakovidou, Aristotle University of Thessaloniki, Greece  Mr. Vinay Chopra, DAV Institute of Engineering & Technology, Jalandhar  Ms. Carmen Lastres, Universidad Politécnica de Madrid - Centre for Smart Environments, Spain  Dr. Sanja Lazarova-Molnar, United Arab Emirates University, UAE  Mr. Srikrishna Nudurumati, Imaging & Printing Group R&D Hub, Hewlett-Packard, India  Dr. Olivier Nocent, CReSTIC/SIC, University of Reims, France  Mr. Burak Cizmeci, Isik University, Turkey  Dr. Carlos Jaime Barrios Hernandez, LIG (Laboratory Of Informatics of Grenoble), France  Mr. Md. Rabiul Islam, Rajshahi university of Engineering & Technology (RUET), Bangladesh  Dr. LAKHOUA Mohamed Najeh, ISSAT - Laboratory of Analysis and Control of Systems, Tunisia  Dr. Alessandro Lavacchi, Department of Chemistry - University of Firenze, Italy  Mr. Mungwe, University of Oldenburg, Germany  Mr. Somnath Tagore, Dr D Y Patil University, India  Ms. Xueqin Wang, ATCS, USA  Dr. Borislav D Dimitrov, Department of General Practice, Royal College of Surgeons in Ireland, Dublin, Ireland  Dr. Fondjo Fotou Franklin, Langston University, USA  Dr. Vishal Goyal, Department of Computer Science, Punjabi University, Patiala, India  Mr. Thomas J. Clancy, ACM, United States  Dr. Ahmed Nabih Zaki Rashed, Dr. in Electronic Engineering, Faculty of Electronic Engineering, menouf 32951, Electronics and Electrical Communication Engineering Department, Menoufia university, EGYPT, EGYPT  Dr. Rushed Kanawati, LIPN, France  Mr. Koteshwar Rao, K G Reddy College Of ENGG.&TECH,CHILKUR, RR DIST.,AP, India  Mr. M. Nagesh Kumar, Department of Electronics and Communication, J.S.S. research foundation, Mysore University, Mysore-6, India  Dr. Ibrahim Noha, Grenoble Informatics Laboratory, France  Mr. Muhammad Yasir Qadri, University of Essex, UK  Mr. Annadurai .P, KMCPGS, Lawspet, Pondicherry, India, (Aff. Pondicherry Univeristy, India  Mr. E Munivel , CEDTI (Govt. of India), India  Dr. Chitra Ganesh Desai, University of Pune, India  Mr. Syed, Analytical Services & Materials, Inc., USA  Dr. Mashud Kabir, Department of Computer Science, University of Tuebingen, Germany  Mrs. Payal N. Raj, Veer South Gujarat University, India  Mrs. Priti Maheshwary, Maulana Azad National Institute of Technology, Bhopal, India  Mr. Mahesh Goyani, S.P. University, India, India  Mr. Vinay Verma, Defence Avionics Research Establishment, DRDO, India  Dr. George A. Papakostas, Democritus University of Thrace, Greece  Mr. Abhijit Sanjiv Kulkarni, DARE, DRDO, India  Mr. Kavi Kumar Khedo, University of Mauritius, Mauritius  Dr. B. Sivaselvan, Indian Institute of Information Technology, Design & Manufacturing, Kancheepuram, IIT Madras Campus, India  Dr. Partha Pratim Bhattacharya, Greater Kolkata College of Engineering and Management, West Bengal University of Technology, India  Mr. Manish Maheshwari, Makhanlal C University of Journalism & Communication, India  Dr. Siddhartha Kumar Khaitan, Iowa State University, USA  Dr. Mandhapati Raju, General Motors Inc, USA  Dr. M.Iqbal Saripan, Universiti Putra Malaysia, Malaysia  Mr. Ahmad Shukri Mohd Noor, University Malaysia Terengganu, Malaysia  Mr. Selvakuberan K, TATA Consultancy Services, India  Dr. Smita Rajpal, Institute of Technology and Management, Gurgaon, India  Mr. Rakesh Kachroo, Tata Consultancy Services, India  Mr. Raman Kumar, National Institute of Technology, Jalandhar, Punjab., India  Mr. Nitesh Sureja, S.P.University, India  Dr. M. Emre Celebi, Louisiana State University, Shreveport, USA  Dr. Aung Kyaw Oo, Defence Services Academy, Myanmar  Mr. Sanjay P. Patel, Sankalchand Patel College of Engineering, Visnagar, Gujarat, India  Dr. Pascal Fallavollita, Queens University, Canada  Mr. Jitendra Agrawal, Rajiv Gandhi Technological University, Bhopal, MP, India  Mr. Ismael Rafael Ponce Medellín, Cenidet (Centro Nacional de Investigación y Desarrollo Tecnológico), Mexico  Mr. Supheakmungkol SARIN, Waseda University, Japan  Mr. Shoukat Ullah, Govt. Post Graduate College Bannu, Pakistan  Dr. Vivian Augustine, Telecom Zimbabwe, Zimbabwe  Mrs. Mutalli Vatila, Offshore Business Philipines, Philipines  Dr. Emanuele Goldoni, University of Pavia, Dept. of Electronics, TLC & Networking Lab, Italy  Mr. Pankaj Kumar, SAMA, India  Dr. Himanshu Aggarwal, Punjabi University,Patiala, India  Dr. Vauvert Guillaume, Europages, France  Prof Yee Ming Chen, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan  Dr. Constantino Malagón, Nebrija University, Spain  Prof Kanwalvir Singh Dhindsa, B.B.S.B.Engg.College, Fatehgarh Sahib (Punjab), India  Mr. Angkoon Phinyomark, Prince of Singkla University, Thailand  Ms. Nital H. Mistry, Veer Narmad South Gujarat University, Surat, India  Dr. M.R.Sumalatha, Anna University, India  Mr. Somesh Kumar Dewangan, Disha Institute of Management and Technology, India  Mr. Raman Maini, Punjabi University, Patiala(Punjab)-147002, India  Dr. Abdelkader Outtagarts, Alcatel-Lucent Bell-Labs, France  Prof Dr. Abdul Wahid, AKG Engg. College, Ghaziabad, India  Mr. Prabu Mohandas, Anna University/Adhiyamaan College of Engineering, india  Dr. Manish Kumar Jindal, Panjab University Regional Centre, Muktsar, India  Prof Mydhili K Nair, M S Ramaiah Institute of Technnology, Bangalore, India  Dr. C. Suresh Gnana Dhas, VelTech MultiTech Dr.Rangarajan Dr.Sagunthala Engineering College,Chennai,Tamilnadu, India  Prof Akash Rajak, Krishna Institute of Engineering and Technology, Ghaziabad, India  Mr. Ajay Kumar Shrivastava, Krishna Institute of Engineering & Technology, Ghaziabad, India  Mr. Deo Prakash, SMVD University, Kakryal(J&K), India  Dr. Vu Thanh Nguyen, University of Information Technology HoChiMinh City, VietNam  Prof Deo Prakash, SMVD University (A Technical University open on I.I.T. Pattern) Kakryal (J&K), India  Dr. Navneet Agrawal, Dept. of ECE, College of Technology & Engineering, MPUAT, Udaipur 313001 Rajasthan, India  Mr. Sufal Das, Sikkim Manipal Institute of Technology, India  Mr. Anil Kumar, Sikkim Manipal Institute of Technology, India  Dr. B. Prasanalakshmi, King Saud University, Saudi Arabia.  Dr. K D Verma, S.V. (P.G.) College, Aligarh, India  Mr. Mohd Nazri Ismail, System and Networking Department, University of Kuala Lumpur (UniKL), Malaysia  Dr. Nguyen Tuan Dang, University of Information Technology, Vietnam National University Ho Chi Minh city, Vietnam  Dr. Abdul Aziz, University of Central Punjab, Pakistan  Dr. P. Vasudeva Reddy, Andhra University, India  Mrs. Savvas A. Chatzichristofis, Democritus University of Thrace, Greece  Mr. Marcio Dorn, Federal University of Rio Grande do Sul - UFRGS Institute of Informatics, Brazil  Mr. Luca Mazzola, University of Lugano, Switzerland  Mr. Nadeem Mahmood, Department of Computer Science, University of Karachi, Pakistan  Mr. Hafeez Ullah Amin, Kohat University of Science & Technology, Pakistan  Dr. Professor Vikram Singh, Ch. Devi Lal University, Sirsa (Haryana), India  Mr. M. Azath, Calicut/Mets School of Enginerring, India  Dr. J. Hanumanthappa, DoS in CS, University of Mysore, India  Dr. Shahanawaj Ahamad, Department of Computer Science, King Saud University, Saudi Arabia  Dr. K. Duraiswamy, K. S. Rangasamy College of Technology, India  Prof. Dr Mazlina Esa, Universiti Teknologi Malaysia, Malaysia  Dr. P. Vasant, Power Control Optimization (Global), Malaysia  Dr. Taner Tuncer, Firat University, Turkey  Dr. Norrozila Sulaiman, University Malaysia Pahang, Malaysia  Prof. S K Gupta, BCET, Guradspur, India  Dr. Latha Parameswaran, Amrita Vishwa Vidyapeetham, India  Mr. M. Azath, Anna University, India  Dr. P. Suresh Varma, Adikavi Nannaya University, India  Prof. V. N. Kamalesh, JSS Academy of Technical Education, India  Dr. D Gunaseelan, Ibri College of Technology, Oman  Mr. Sanjay Kumar Anand, CDAC, India  Mr. Akshat Verma, CDAC, India  Mrs. Fazeela Tunnisa, Najran University, Kingdom of Saudi Arabia  Mr. Hasan Asil, Islamic Azad University Tabriz Branch (Azarshahr), Iran  Prof. Dr Sajal Kabiraj, Fr. C Rodrigues Institute of Management Studies (Affiliated to University of Mumbai, India), India  Mr. Syed Fawad Mustafa, GAC Center, Shandong University, China  Dr. Natarajan Meghanathan, Jackson State University, Jackson, MS, USA  Prof. Selvakani Kandeeban, Francis Xavier Engineering College, India  Mr. Tohid Sedghi, Urmia University, Iran  Dr. S. Sasikumar, PSNA College of Engg and Tech, Dindigul, India  Dr. Anupam Shukla, Indian Institute of Information Technology and Management Gwalior, India  Mr. Rahul Kala, Indian Institute of Inforamtion Technology and Management Gwalior, India  Dr. A V Nikolov, National University of Lesotho, Lesotho  Mr. Kamal Sarkar, Department of Computer Science and Engineering, Jadavpur University, India  Dr. Mokhled S. AlTarawneh, Computer Engineering Dept., Faculty of Engineering, Mutah University, Jordan, Jordan  Prof. Sattar J Aboud, Iraqi Council of Representatives, Iraq-Baghdad  Dr. Prasant Kumar Pattnaik, Department of CSE, KIST, India  Dr. Mohammed Amoon, King Saud University, Saudi Arabia  Dr. Tsvetanka Georgieva, Department of Information Technologies, St. Cyril and St. Methodius University of Veliko Tarnovo, Bulgaria  Dr. Eva Volna, University of Ostrava, Czech Republic  Mr. Ujjal Marjit, University of Kalyani, West-Bengal, India  Dr. Prasant Kumar Pattnaik, KIST,Bhubaneswar,India, India  Dr. Guezouri Mustapha, Department of Electronics, Faculty of Electrical Engineering, University of Science and Technology (USTO), Oran, Algeria  Mr. Maniyar Shiraz Ahmed, Najran University, Najran, Saudi Arabia  Dr. Sreedhar Reddy, JNTU, SSIETW, Hyderabad, India  Mr. Bala Dhandayuthapani Veerasamy, Mekelle University, Ethiopa  Mr. Arash Habibi Lashkari, University of Malaya (UM), Malaysia  Mr. Rajesh Prasad, LDC Institute of Technical Studies, Allahabad, India  Ms. Habib Izadkhah, Tabriz University, Iran  Dr. Lokesh Kumar Sharma, Chhattisgarh Swami Vivekanand Technical University Bhilai, India  Mr. Kuldeep Yadav, IIIT Delhi, India  Dr. Naoufel Kraiem, Institut Superieur d'Informatique, Tunisia  Prof. Frank Ortmeier, Otto-von-Guericke-Universitaet Magdeburg, Germany  Mr. Ashraf Aljammal, USM, Malaysia  Mrs. Amandeep Kaur, Department of Computer Science, Punjabi University, Patiala, Punjab, India  Mr. Babak Basharirad, University Technology of Malaysia, Malaysia  Mr. Avinash singh, Kiet Ghaziabad, India  Dr. Miguel Vargas-Lombardo, Technological University of Panama, Panama  Dr. Tuncay Sevindik, Firat University, Turkey  Ms. Pavai Kandavelu, Anna University Chennai, India  Mr. Ravish Khichar, Global Institute of Technology, India  Mr Aos Alaa Zaidan Ansaef, Multimedia University, Cyberjaya, Malaysia  Dr. Awadhesh Kumar Sharma, Dept. of CSE, MMM Engg College, Gorakhpur-273010, UP, India  Mr. Qasim Siddique, FUIEMS, Pakistan  Dr. Le Hoang Thai, University of Science, Vietnam National University - Ho Chi Minh City, Vietnam  Dr. Saravanan C, NIT, Durgapur, India  Dr. Vijay Kumar Mago, DAV College, Jalandhar, India  Dr. Do Van Nhon, University of Information Technology, Vietnam  Mr. Georgios Kioumourtzis, University of Patras, Greece  Mr. Amol D.Potgantwar, SITRC Nasik, India  Mr. Lesedi Melton Masisi, Council for Scientific and Industrial Research, South Africa  Dr. Karthik.S, Department of Computer Science & Engineering, SNS College of Technology, India  Mr. Nafiz Imtiaz Bin Hamid, Department of Electrical and Electronic Engineering, Islamic University of Technology (IUT), Bangladesh  Mr. Muhammad Imran Khan, Universiti Teknologi PETRONAS, Malaysia  Dr. Abdul Kareem M. Radhi, Information Engineering - Nahrin University, Iraq  Dr. Mohd Nazri Ismail, University of Kuala Lumpur, Malaysia  Dr. Manuj Darbari, BBDNITM, Institute of Technology, A-649, Indira Nagar, Lucknow 226016, India  Ms. Izerrouken, INP-IRIT, France  Mr. Nitin Ashokrao Naik, Dept. of Computer Science, Yeshwant Mahavidyalaya, Nanded, India  Mr. Nikhil Raj, National Institute of Technology, Kurukshetra, India  Prof. Maher Ben Jemaa, National School of Engineers of Sfax, Tunisia  Prof. Rajeshwar Singh, BRCM College of Engineering and Technology, Bahal Bhiwani, Haryana, India  Mr. Gaurav Kumar, Department of Computer Applications, Chitkara Institute of Engineering and Technology, Rajpura, Punjab, India  Mr. Ajeet Kumar Pandey, Indian Institute of Technology, Kharagpur, India  Mr. Rajiv Phougat, IBM Corporation, USA  Mrs. Aysha V, College of Applied Science Pattuvam affiliated with Kannur University, India  Dr. Debotosh Bhattacharjee, Department of Computer Science and Engineering, Jadavpur University, Kolkata-700032, India  Dr. Neelam Srivastava, Institute of engineering & Technology, Lucknow, India  Prof. Sweta Verma, Galgotia's College of Engineering & Technology, Greater Noida, India  Mr. Harminder Singh BIndra, MIMIT, INDIA  Dr. Lokesh Kumar Sharma, Chhattisgarh Swami Vivekanand Technical University, Bhilai, India  Mr. Tarun Kumar, U.P. Technical University/Radha Govinend Engg. College, India  Mr. Tirthraj Rai, Jawahar Lal Nehru University, New Delhi, India  Mr. Akhilesh Tiwari, Madhav Institute of Technology & Science, India  Mr. Dakshina Ranjan Kisku, Dr. B. C. Roy Engineering College, WBUT, India  Ms. Anu Suneja, Maharshi Markandeshwar University, Mullana, Haryana, India  Mr. Munish Kumar Jindal, Punjabi University Regional Centre, Jaito (Faridkot), India  Dr. Ashraf Bany Mohammed, Management Information Systems Department, Faculty of Administrative and Financial Sciences, Petra University, Jordan  Mrs. Jyoti Jain, R.G.P.V. Bhopal, India  Dr. Lamia Chaari, SFAX University, Tunisia  Mr. Akhter Raza Syed, Department of Computer Science, University of Karachi, Pakistan  Prof. Khubaib Ahmed Qureshi, Information Technology Department, HIMS, Hamdard University, Pakistan  Prof. Boubker Sbihi, Ecole des Sciences de L'Information, Morocco  Dr. S. M. Riazul Islam, Inha University, South Korea  Prof. Lokhande S.N., S.R.T.M.University, Nanded (MH), India  Dr. Vijay H Mankar, Dept. of Electronics, Govt. Polytechnic, Nagpur, India  Dr. M. Sreedhar Reddy, JNTU, Hyderabad, SSIETW, India  Mr. Ojesanmi Olusegun, Ajayi Crowther University, Oyo, Nigeria  Ms. Mamta Juneja, RBIEBT, PTU, India  Dr. Ekta Walia Bhullar, Maharishi Markandeshwar University, Mullana Ambala (Haryana), India  Prof. Chandra Mohan, John Bosco Engineering College, India  Mr. Nitin A. Naik, Yeshwant Mahavidyalaya, Nanded, India  Mr. Sunil Kashibarao Nayak, Bahirji Smarak Mahavidyalaya, Basmathnagar Dist-Hingoli., India  Prof. Rakesh.L, Vijetha Institute of Technology, Bangalore, India  Mr B. M. Patil, Indian Institute of Technology, Roorkee, Uttarakhand, India  Mr. Thipendra Pal Singh, Sharda University, K.P. III, Greater Noida, Uttar Pradesh, India  Prof. Chandra Mohan, John Bosco Engg College, India  Mr. Hadi Saboohi, University of Malaya - Faculty of Computer Science and Information Technology, Malaysia  Dr. R. Baskaran, Anna University, India  Dr. Wichian Sittiprapaporn, Mahasarakham University College of Music, Thailand  Mr. Lai Khin Wee, Universiti Teknologi Malaysia, Malaysia  Dr. Kamaljit I. Lakhtaria, Atmiya Institute of Technology, India  Mrs. Inderpreet Kaur, PTU, Jalandhar, India  Mr. Iqbaldeep Kaur, PTU / RBIEBT, India  Mrs. Vasudha Bahl, Maharaja Agrasen Institute of Technology, Delhi, India  Prof. Vinay Uttamrao Kale, P.R.M. Institute of Technology & Research, Badnera, Amravati, Maharashtra, India  Mr. Suhas J Manangi, Microsoft, India  Ms. Anna Kuzio, Adam Mickiewicz University, School of English, Poland  Dr. Debojyoti Mitra, Sir Padampat Singhania University, India  Prof. Rachit Garg, Department of Computer Science, L K College, India  Mrs. Manjula K A, Kannur University, India  Mr. Rakesh Kumar, Indian Institute of Technology Roorkee, India TABLE OF CONTENTS 1. A Coded Cooperative Networking MAC protocol in non transparent multihop Pg 1-9 WiMAX network Lamia Chaari, Lotfi Kamoun 2. Authentication and Secure Communication in GSM, GPRS, and UMTS Using Pg 10-16 Asymmetric Cryptography Wilayat Khan, Habib Ullah 3. Touching Syllable Segmentation using Split Profile Algorithm Pg 17-26 L.Pratap Reddy, T.Ranga Babu, N.Venkata Rao, B.Raveendra Babu 4. Information Security and Sender's Rights Protection through Embedded Public Key Pg 27-34 Signature Vineeta Khemchandani, G. N. Purohit 5. Non linear Image segmentation using fuzzy c means clustering method with Pg 35-40 thresholding for underwater images G. Padmavathi, M. Muthukumar, Suresh Kumar Thakur 6. A Theoretical Approach to Link Mining for personalization Pg 41-44 K. Srinivas, L. Kiran Kumar Reddy, A. Govardhan 7. Image Compression Algorithms for Fingerprint System Pg 45-50 Preeti Pathak IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 1 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 A Coded Cooperative Networking MAC protocol in non transparent multihop WiMAX network Lamia CHAARI, Lotfi KAMOUN University of SFAX, Electronic and Technology Information Laboratory, TUNISIA diversity offered by cooperation between wireless Abstract terminals. Diversity increases capacity and provides IEEE 802.16j mobile multi-hop relay (MMR) was proposed to robustness against fading. The most common diversity gain coverage extension and throughput enhancement. The methods are spatial diversity using multiple antennas, objective of this work, is to suggest a coded cooperative temporal diversity using automatic repeat request schemes networking MAC protocol in non transparent multihop WiMax or block interleaving with error correction, and frequency network. The proposed design takes in consideration network diversity using frequency spreading, frequency hopping, coding approach between relays. We try to address the division of an IEEE 802.16j frame into different zones. We suggest a or orthogonal frequency division multiplexing techniques. frame structure that supports 3 hops non transparent TTR mode. Cooperative diversity refers to the class of techniques Related work and the 802.16j capability are also deeply where diversity benefits are gained via the sharing of discussed. information between multiple cooperating terminals in a Keywords: Cooperative, network coding, frame, multihop, wireless network. Several relaying cooperative strategies IEEE 802.16j, MAC. [15] for wireless relay networks are proposed:  decode- and-forward [17, 18],  amplify-and-forward [19, 47], 1. Introduction  compress–and-forward [20],  selection relaying scheme [16, 22 25]. Cooperative communication (CooCom) [1, 2 ,3 ,4 ,5, 53] is a recent paradigm for wireless relay networks [ 6, 7,  opportunistic relaying scheme[ 16, 26], 8, 9, 10], proposed as a way to improve wireless network  coded cooperation (CC) [27, 28], reliability and capacity. The main technical benefits  Space-time CC [29, 30] coming along with cooperative communications are higher coverage, improved spectrum usage, lower energy In decode and forward method a cooperating node consumption, increased location estimation accuracy, etc.). first decodes signals received from a source and then The broadcast nature of the wireless medium is the main relays or retransmits them. The receiver at the destination enabler of cooperative communications. uses information retransmitted from multiple relays and Coocom enables single-antenna nodes in a multi-user the source (when available) to make decisions. Perfect environment to share their resources to jointly transmit regeneration at the relays may require retransmission of information in order to achieve an improvement in overall symbols or use of forward error correction (FEC) performance and reap some of the benefits of multiple- depending on the quality of the channel between the input, multiple-output (MIMO) [11, 50, 51] systems. The source and the relays. This may not be suitable for a delay classical relay channel model [6,12,13,14, 21, 52] is limited networks. In amplify and forward each cooperating comprised of three terminals a source that transmits node receives the signals transmitted by the source node information, a destination that receives information, and a but don’t decode them. These signals in their noisy form relay that both receives and transmits information in order are amplified to compensate for the attenuation suffered to enhance communication between the source and between the source-to-relay links and retransmitted. The destination. Cooperation is a generalization of the relay destination requires knowledge of the channel state channel to multiple sources with information to transmit between source-to-relay links to correctly decode the that also serve as relays for each other. Combinations of symbols sent from the source. relaying and cooperation are known as cooperative In compress and forward the received signal is only communications. quantized instead of being fully decoded, the quantized This is realized via the application of cooperative symbols are not directly repeated in phase 2 they are diversity techniques that take advantage of the spatial compressed by Wyner-Ziv coding [31]. The selection IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 2 www.IJCSI.org relaying schemes choose the strategy with best achievable combinations of communication links between performance based upon channel measurements between cooperating terminals are also deeply presented in the the cooperating terminals. In an opportunistic relaying literature [54]. scheme (ORS) only the best relay is allowed to cooperate Recently, network coding [33, 34, 35,] as well has with the source. If channel conditions are not statistically received a lot of attention for its potential advantages in equal for all relays, ORS may be unfair among relays. improving throughput and enhancing robustness for multi- That is, relays with the worst channel conditions are never source systems. The basic principle of network coding is selected and all the cooperation is performed by a reduced to linearly combine multiple independent information set of relays. This can induce a negative effect in the flows into one flow to transmit. There have been several network behavior as one (or more) relays can waste all the proposals for applying network coding to multi-source battery energy for the sake of cooperation. relaying networks, with or without cooperation. The The coded cooperation provides cooperation diversity interaction between Cooperation and Network Coding [36] by distributed Forward Error Correction (FEC) coding and has recently received a significant deal of attention, as a considers the result of the error check for its relaying combination of the two brings novelty, flexibility and decision. If a user is not able to correctly decode the improved performance. However, there is a lack of studies partner’s bits it forwards its own data during the second about real-world scenarios. phase. The Space-time CC exploit spatial diversity Multihop relaying is already part of the standards available among a collection of distributed terminals that currently being developed for wireless broadband systems relay messages for one another in such a manner that the [37] such as 802.16j [38] and 802.16m [39], which is an destination terminal can average the fading, even though it indication of growing consensus on the effectiveness of is unknown a priori which terminals will be involved. In cooperative communication. However, at this stage, there particular, a source initiates transmission to its destination, are many open issues regarding good 802.16j relay and many relays potentially receive the transmission. network solutions: Those terminals that can fully decode the transmission  While there have been a few initial studies on utilize a space-time code to cooperatively relay to the IEEE 802.16j MMR networks, not much is really destination. known about the performance of such systems. Many other strategies have been proposed. In [32] This makes it very difficult to have clear ideas of new cooperative strategy for ad hoc networks that are the potential of this technology. more spectrally efficient than classical Decode & Forward  The current standard does not specify how the (DF) protocols was proposed. Using analog network radio resource allocation will be done. coding was suggested in order to improve spectral  Some initial studies on the design of 802.16j efficiency of the cooperative system by relaxing the system have been carried out. The issues relative orthogonally constraint, though preserving the practical to the planning of multiple relays is still open. half-duplex constraint. Although all these schemes employ different techniques to No previous work has specifically look to the process the relayed data, all of them employ at least two implementations issues of a coded cooperative networking phases per cooperation cycle separated for the reason that MAC protocol over 802.16j systems. More specifically, wireless terminals cannot transmit and receive the focus of this contribution is to propose a coded simultaneously at the same time and frequency. While in cooperative networking MAC protocol in fixed broadband the first phase the users exchange their data, in the second wireless access systems with multihop relay Wimax phase the users help each other by relaying the data/signal. networks, which we denoted it CCNMACMHRwimax “Coded The emerging IEEE 802.16j standard may allow w/o relay Cooperative Networking MAC protocol for Multihop transmissions in the second phase. Relay Wimax networks”. Such proposal require firstly a The cooperative connectivity of a wireless relay deep research on coding schemes [40, 41] used for network is defined as the set of communication links combining, on relaying techniques used for mutually between pairs of terminals that are used in the exchanging data, on multiple access methods to limit transmission of an information signal from a source interference and overhead, on cooperation aware resource terminal to a destination terminal. Relay terminals are allocation such as selecting partners[ 42, 43] and defined to cooperate with the source terminal when they cooperation level [44, 45] , on routing methods [46] in transmit a signal that helps the destination terminal to multi-hop cooperative networks. Secondly we must focus successfully decode the original information signal. The on the practical issues for cooperative networking when ways that cooperating terminals can be connected to each trying to apply cooperation in an existing standard, such as other in wireless relay networks, the constraints imposed IEEE 802.16j networks. by the availability of different system resources and the IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 3 www.IJCSI.org Researches on cooperative mechanisms at MAC layer transparent mode relays is to facilitate capacity are commonly related to WLAN networks [55, 56, 57, 58] increases within the BS coverage area. This type of and only some works for WMAN networks [59,60]. relay is of lower complexity, and only operates in a In [61] the authors propose A user scheduling and centralized scheduling mode and for topology up to radio resource allocation algorithm for two-hop wireless two hops. relay networks in order to efficiently integrate various - In Non-transparent mode: The RSs generate their cooperative diversity schemes for the emerging IEEE own framing information or forward those provided 802.16j based systems. The analysis of the system with by the BS depending on the scheduling approach (i.e., this scheduler shows that a simple cooperative diversity distributed or centralized). They can support larger scheme which dynamically selects the best scheme coverage areas and hence are mainly used to provide between conventional relaying and direct transmission is increased coverage. Fig.2 illustrates the two modes. promising in terms of throughput and implementation Table 1 below gives a comparison between the transparent complexity. and non-transparent relay modes [63, 64, 65]. The paper is organized as follows. In this section we have briefly reviewed related work. A reasonably detailed 1 2 3 description of the 802.16j capability based on the current draft is presented in section 2. In Section 3, Frame structure for MMR in non transparent mode with tunneling and network coding approach is proposed. Finally, the paper is concluded in section 4. 2. IEEE 802.16j capabilities Fig.1 IEEE 802.16j basic system architecture The IEEE 802.16j is an amendment to the IEEE 802.16e standard to enable the functionalities of interoperable RSs and BSs. The IEEE 802.16j standard is currently being developed for increasing the coverage area of the IEEE 802.16e standard via the deployment of fixed or nomadic relay terminals. In this section, the key system features and the capabilities of the IEEE 802.16j MR network are overviewed. The discussion will focus on two particular aspects the different relay modes that are defined and the frame structure that is proposed. 2.1 Relay mode The basic system architecture considered by IEEE 802.16j is shown in Fig.1, where two kinds of radio links are identified: access link and relay link. BS that is capable of supporting multi-hop relay is called MR-BS. The access link is the radio link that originates or terminates at an MS, which is either a downlink (DL) or an uplink (UL), defined in IEEE 802.16-2004. The relay link is the radio link between an MR-BS and an RS or between a pair of RSs, which can be either uplink or downlink [68]. Based on the functionality of an RS, IEEE 802.16j has classified the RS functionality into two modes: transparent and non- transparent. - In the transparent mode[62, 63], the RSs do not forward framing information, and hence do not increase the coverage area of the wireless access system; consequently, the main use case for IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 4 www.IJCSI.org There are two types of non-transparent relays available in 802.16j: Time-division Transmit and Receive (TTR) relay and Simultaneously Transmit and Receive (STR) relay. The TTR relay act in the access zone as BS and in relay zone it acts as relay. For this work, we have considered the non-transparent mode with two TTR relays nodes. 2.2 Frame structure for MMR As the frame structure defined in the earlier IEEE 802.16e standards was designed for single-hop wireless networks, modifications were required to support relay network architectures. The IEEE 802.16e have adopted orthogonal frequency-division multiple access (OFDMA) as the primary channel access mechanism for non-line-of-sight (NLOS) communications in the frequency bands below 11 GHz. The basic unit of resource for allocation in OFDMA is a slot, which comprises a number of symbols in time domain, and one subchannel in frequency domain. The base station divides the timeline into contiguous frames, each of which further consists of a downlink (DL) and an uplink (UL) subframe. For the case where MR-BS supports more than two-hop relay, the DL and UL sub-frames shall include at least one access zone and may include one or more relay zone to enable RS operating in either transmit or receive mode. The DL/UL access zones are dedicated for transmission between MSs and their access stations (MR-BS or RS), and they are fully compatible with the 802.16e frame structure. The DL/UL relay zones are dedicated for transmission between Fig.2 Transparent and Non-transparent relay modes architecture MR-BS and the RS or between two RS. In each relay zone, Table 1: Transparent and Non-transparent relay modes BS and RS can stay in the mode of transmission, reception or being idle. However, it is not expected to have BS or Transparent RS Non-Transparent RS switch from one mode to the other within the same RS zone. In order to give wireless device sufficient time to Coverage No Yes switch from one mode to another, the corresponding time extension gap (e.g., TTG and RTG) is inserted between two Number of hops 2 >2 consecutive sub-frames. The IEEE Std. 802.16j specifies the following gaps: Inter RS cell NA High interference - R-TTG: RS transmit/receive transition gap between HO between RSs None Yes uplink access zone and uplink relay zone in RS frame between DL access zone and DL relay zone in RS frame Performance In BS coverage: In BS coverage: - R-RTG: RS receive/transmit transition gap between High same as16e Outer uplink access zone and uplink relay zone in RS frame. Outer BS BS coverage: coverage: - medium The case where each DL and UL sub-frame comprises of RS Cost Low High more than one relay zones is shown in Fig. 3. Scheduling Centralized only Centralized/ distributed IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 5 www.IJCSI.org Time Frame K Frame K+1 DL Sub-Frame UL Sub-Frame R-RTG R-TTG TTG RTG TTG Access Relay Relay Relay Access Relay Relay Relay Zone Zone Zone Zone Zone Zone Zone Zone 1 2 n 1 2 m FCH DL-MAP R-FCH DL-R-MAP Preamble DL-MAP UL-MAP Preamble DL-R-MAP UL-R-MAP Mid- amble Fig.3 Frame Structure for MMR The frame structure design is more challenging in the time and possibly, frequency. The immediate drawback is new mobile multihop relay based (MMR) network an increase in interference, particularly in the preamble architecture, as numerous dimensions of design constraints and control channels. Clearly, power control and and challenges have been introduced. In the literature frequency reuse, which largely are left up to frame structure design has received some attention In manufacturers, are crucial to non-transparent relaying. [48][49] a generic frame structure to support mobile Further, non-transparent relays likely are more multihop relay (MMR) operation of IEEE 802.16j, while sophisticated (and thus, more expensive) than transparent. maintaining the backward compatibility with the legacy Therefore, our challenge is to design a transmission 802.16e mobile stations was proposed and analyzed. mechanism suitable for wireless multi-hop networks, The packet construction mechanism in IEEE which linearly combine information flows from (BS, RS1, 802.16/16e standard, which was designed for handling RS2) into one flow to transmit. traffic solely on a per-connection basis, cannot apply on The IEEE 802.16j is also devoted to defining a new the relay link directly, as it may render a potential MAC message family (called R-MAC) between the bottleneck and preponderantly limit the overall network MRBS and the subordinate RSs. A fundamental part of capacity. As a solution, in [58] the authors propose two the R-MAC is what can be regarded as a tunnel connection, schemes at the MAC layer, namely MPDU concatenation which is identified by a special tunnel CID (T-CID). In and MSDU aggregation. what way to use these tunnels is not specified in 802.16j D2 [59]. In this work we take in consideration Hop by Hop Tunnel Establishing (HHTE). In HHTE, RSi receives 3 Frame structure for MMR in non the MPDU from MS, MR-BS or RSj decodes it, and transparent mode with tunneling and determines that it needs to be processed by each hop. RSi network coding approach encapsulates the MPDUs and sends it. Although the tunneling is optional, tunneling simplify the relaying process in multi-hop environment. This section provides design frame structure for multi In order to explain our approach, we consider the relay hops (MR-BS, RS1, RS2) in non transparent mode. topology illustrated by figure 1 which corresponds to 3 The proposed design takes in consideration network hops non transparent mode. We try to address the division coding approach between relays. An envisioned topology of an IEEE 802.16j frame into different zones. We suggest is illustrated in figure 1, wherein RSs help MR-BS the frame structure shown in fig.4 to support 3 hops non communicate with those MSs that are either too far away transparent TTR mode. We consider that MR-BS has the from the MR-BS. In other hand RSs can also have their data flow X0 to transmit to MS3 and each relay node RSi own traffic to MSs. In this case, both the MR-BS and the has a data flow denoted Xi to be transmitted to the MS3. relay transmit control data at the beginning of the frame. Moreover, the MS3 terminal has the data flows Y0 and Yi This way, the MS can synchronize with the relay, which is to send respectively to MR-BS and RSi. The different synchronized with the MR-BS. interval time are denoted (T1, T2, T3,T4, T5, T6). The main drawback in the non-transparent case is that In table 2 we illustrate the data flows assigned and now the relay and BS are transmitting simultaneously in exchanged between the different hops. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 6 www.IJCSI.org Table 2: Data flow for support 3 hops non transparent mode T1 T2 T3 T4 T5 T6 RS2  MS3 MR-BS  RS1  RS2 MS3  RS2 RS2  RS1 RS1  RS2 RS1 RS1 MR-BS RS1 MR-BS X2k, X1(k-1) , X0k (X0k xor Y0(k-1)), Y2k, Y1(k) , Y0(k) , Y1(k) (Y0k xor X0k), X0(k-1) (X1k ) Y0(k) (X1k ) Time Frame K Frame K+1 DL Sub-Frame UL Sub-Frame DL Access – DL Relay1 DL Relay2 - UL Access - DL Relay1 DL Relay2RTG- Interval Interval Interval Interval Interval Interval TTG T1 T2 T3 T4 T5 T6 UL-R-MAP DL-R-MAP FCH Ranging R-FCH DL-MAP TX (for Rx MSs) Rx RX (from MSs) (from Subchannel Tx (for (from Receive from Transmit Preamble RS1) RS1) RS1) to serve mobile stations UL-MAP DL-R-MAP MR-BS mobile stations DL-MAP UL-R-MAP DL-R-MAP FCH R-FCH DL-MAP TX (for MSs) Tx to RX (from MSs) RX (from Tx to Rx MR-BS & R2 Receive from Relay 2) MR-BS & R2 Transmit Preamble (fron Based on mobile stations Receive from Based on to serve UL-MAP MR- DL-R-MAP network Relay 2 network Relay 1 mobile BS) coding coding stations DL-MAP FCH DL-MAP TX (for TX (to MSs) RX (from MSs) Relay 1) Transmit Receive from Transmit Preamble to serve Rx mobile stations to relay 1 Rx UL-MAP (from (from Relay 2 mobile stations RS1) RS1) DL-MAP Fig.4 Frame Structure for support 3 hops non transparent mode. In order to enhance the reliability of the wireless link, retransmission protocols have been widely adopted in IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 7 www.IJCSI.org wireless systems. Usually, they assume that lost packets ON SELECTED AREAS IN COMMUNICATIONS, VOL. 26, within a cell have to be retransmitted from the NO. 7, SEPTEMBER 2008. [8] Ivana Maric, Roy Yates, “Static and Dynamic Cooperative corresponding BS based on the ARQ protocol. In this Multicast for Maximum Network Lifetime”, Allerton case, The MR-BS receives twice the data flow Y0k (in Conference on Communications, Control and Computing, framek and frame(K +1)) and the RS2 receives twice the Monticello, IL, Sept. 2004. data flow X0k (in T3 and T6) this is can avoid the [9] Simone Frattasi, “Link Layer Techniques Enabling repeated retransmissions performed by the BS that Cooperation in Fourth Generation (4G) Wireless Networks, reduce latencies to receive packets correctly. thesis, International Doctoral School of Technology and Science Aalborg University, 26 September 2007 [10] Furuzan Atay, “Cooperative Diversity Relaying Techniques 4 Conclusions in Wireless Communication Networks”, thesis, Faculty of Graduate Studies and Research,The Ottawa-Carleton Institute for In this paper, we have presented a coded cooperative Electrical and Computer Engineering (OCIECE) Department of Systems and Computer Engineering, January 2009, 199 pages. networking MAC protocol in non transparent multihop [11] Chris T. K. Ng, J. Nicholas Laneman, Andrea J. Goldsmith, WiMax. The proposed solution takes in consideration “The Role of SNR in Achieving MIMO Rates in Cooperative network coding approach between relays. The suggested Systems, Information Theory Workshop ITW '06 Punta del Este, frame structure supports 3 hops non transparent TTR Uruguay, 13-17 March 2006, page(s): 288-292, ISBN: 1-4244- mode. 0035-X. In IEEE 802.16 based multi-hop networks many [12] Abbas El Gamal, “Capacity Theorems for Relay Channels”, Department of Electrical Engineering, Stanford University, April, issues are still open both in PHY and MAC layer and 2006 specially those taken in consideration cross layer [13] Ivana Marié, Andrea Goldsmith, Gerhard Kramer and interaction. Key issues such as multi-hop frame structure, Shlomo Shamai Shitz, “On the capacity of interference channels scheduling mechanism, support for QoS and many other with one cooperating transmitter”, EUROPEAN requirements are under consideration. In future work, we TRANSACTIONS ON TELECOMMUNICATIONS, 2008; will consider more extensive simulation to compare our 19:405–420 Published online 24 April 2008 in Wiley InterScience. scheme with other schemes. [14] Katti, Sachin Maric, Ivana Goldsmith, Andrea Katabi, Dina Medard, Muriel MIT, “Joint Relaying and Network Coding in Wireless References Networks”, Information Theory, 2007. ISIT 2007. IEEE International Symposium , Nice, 24-29 June 2007, page(s): 1101-1105, ISBN: 978-1-4244-1397-3. [1] Andrea Conti, Jiangzhou Wang, Hyundong Shin, Ramesh [15] Stefan Valentin, Hermann S. Lichte, Holger Karl, Annavajjala, and Moe Z. Win, “Wireless Cooperative Networks”, Guillaume Vivier, Sébastien Simoens Josep Vidal and Adrian EURASIP Journal on Applied Signal Processing, special issue Agustin, “Cooperative wireless networking beyond store-and- published in volume 2008, 142 pages. forward: Perspectives in PHY and MAC design”, Wireless [2] Anna Scaglione, Dennis L. Goeckel and J. Nicholas Personal Communications, Vol. 48, No. 1, pp. 49-68, Jan. 2009. Laneman, “Cooperative Communications in Mobile Ad-Hoc [16] S. Valentin, H. S. Lichte, H. Karl, I. Aad, L. Loyola, and J. Networks: Rethinking the Link Abstraction”, book chapter in Widmer, "Opportunistic relaying vs. selective cooperation: Distributed Antenna Systems: Open Architecture for Future Analyzing the occurrence-conditioned outage capacity," in Proc. Wireless Communications, edited by Honglin Hu, Yan Zhang, 11th ACM International Conference on Modeling, Analysis and jijun Luo, june 2006, © Taylor and Francis Group Simulation of Wireless and Mobile Systems (MSWiM), Oct. [3] Ramesh Chembil Palat, “Performance Analysis of 2008. Cooperative Communication for Wireless Networks, thesis, [17] Luo, J. Blum, R.S. Cimini, L.J. Greenstein, Faculty of Virginia Polytechnic Institute and State University, L.J. Haimovich, A.M., “Decode-and-forward cooperative December 8, 2006, 164 pages. diversity with power allocation in wireless networks” , IEEE [4] Maric, I.; Yates, R.D, “Cooperative multihop broadcast for Global Telecommunications Conference, GLOBECOM '05, Dec. wireless networks” , Selected Areas in Communications, IEEE 2005, Louis, MO St, Volume: ISBN: 0-7803-9414-3. Journal on, Volume 22, Issue 6, Aug. 2004 Page(s): 1080 - 1088 [18] Sadek, A.K.; Weifeng Su; Liu, K.J.R., “Performance [5] J. Nicholas Laneman, COOPERATIVE DIVERSITY Models, analysis for multi-node decode- and-forward relaying in Algorithms, and Architectures, Book chapter: Cooperation in cooperative wireless networks”, IEEE International Conference Wireless Networks: Principles and Applications. Springer, 2006, on Acoustics, Speech, and Signal Processing, 2005. Proceedings. pp. 163-188. (ICASSP apos;05). [6] John Boyer, “Cooperative Connectivity Models and Bounds Volume 3, Issue , 18-23 March 2005. for Wireless Relay Networks”, thesis, Ottawa-Carleton Institute [19] YINDI JING AND HAMID JAFARKHANI, for Electrical and Computer Engineering Department of Systems “ Beamforming in Wireless Relay Networks”, Information and Computer Engineering Carleton University, Ottawa, Ontario, Theory and Applications Workshop, jan 2008, page(s): 142-150, Canada, 2007, 258 pages. ISBN: 978-1-4244-2670-6. [7] Suhas Mathur, Lalitha Sankar, Narayan B. Mandayam, [20] Simoens, S. Vidal, J. Munoz, O. , “Compress-And- Coalitions in Cooperative Wireless Networks, IEEE JOURNAL Forward Cooperative Relaying in MIMO-OFDM Systems”, IEEE 7 th workshop: Signal Processing Advances in Wireless IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 8 www.IJCSI.org Communications, SPAWC '06. , 2-5 July 2006, Cannes, page(s): [34] Yalin Evren Sagduyu, Anthony Ephremides, “ON 1-5, ISBN: 0-7803-9711-8. NETWORK CODING FOR STABLE MULTICAST [21] Ivana Maric, Roy D. Yates, Gerhard Kramer, “The Strong COMMUNICATION”, Military Communications Conference, Interference Channel with Unidirectional Cooperation”, in Proc. MILCOM 2007. IEEE Volume , Issue , 29-31 Oct. 2007. Information Theory and Applications (ITA), Inaugural [35] Andrea Munari, Francesco Rossetto, Michele Zorzi, “On the Workshop, Feb. 2006. viability of a Cooperative-Network Coding Protocol in Clustered [22] Furuzan Atay Onat, Yijia Fan, Halim Yanikomeroglu, H. Networks”, Military Communications Conference, 2008. Vincent Poor, “Threshold Based Relay Selection in Cooperative MILCOM Nov 2008. IEEE Wireless Networks”, Global Telecommunications Conference, [36] Dereje H. Woldegebreal Stefan Valentin, Holger Karl, IEEE GLOBECOM Dec 2008. pages 1-5, ISSN: 1930-529X, “Outage Probability Analysis of Cooperative Transmission ISBN: 978-1-4244-2324-8. Protocols without and with Network Coding: Inter-User [23] Yindi Jing Jafarkhani, H., “Single and Multiple Relay Channels based Comparison”, International Workshop on Selection Schemes and their Diversity Orders”, Communications Modeling Analysis and Simulation of Wireless and Mobile Workshops, May 2008. ICC Workshops '08. Beijing, page(s): Systems Chania, Crete Island, Proceedings of the 10th ACM 349-353, ISBN: 978-1-4244-252-0. Symposium on Modeling, analysis, and simulation of wireless [24] Y. Jing and H. Jafarkhani, "Single and Multiple Relay and mobile systems , Greece , 2007, Pages: 36 – 44, ISBN:978- Selection Schemes and Their Achievable Diversity Orders," to 1-59593-851-0. appear in IEEE Transactions on Wireless Communications. [37] 802.16™ IEEE Standard , "Local and metropolitan area [25] J. Nicholas Laneman, David N. C. Tse, Gregory W. networks Part 16: Air Interface for Fixed Broadband Wireless Wornell, “Cooperative Diversity in Wireless Networks: Efficient Access Systems", 3 Park Avenue, New York, NY 10016-5997, Protocols and Outage Behavior”, IEEE TRANSACTIONS ON USA, IEEE Computer Society and the IEEE Microwave Theory INFORMATION THEORY, VOL. 50, NO. 12, DECEMBER and Techniques Society Sponsored by the LAN/MAN Standards 2004, 19 pages. Committee, October 2004, Print: SH95246, PDF: SS95246. [26] Jose Lopez Vicario, Albert Bel, Antoni Morell and Gonzalo [38] IEEE 802.16 Working Group Officers, " 802.16j-06/026r3, Seco-Granados, “Outage Probability vs. Fairness Trade-off in Baseline Document for Draft Standard for Local and Opportunistic Relay Selection with Outdated Metropolitan Area Networks, Part 16: Air Interface for Fixed CSI”, EURASIP JOURNAL ON WIRELESS and Mobile Broadband Wireless Access Systems Multihop COMMUNICATIONS AND NETWORKING. Accepted 20 Relay Specification, 2007-04-10. January 2009. [39] IEEE 802.16m-08/003, the Draft IEEE 802.16m System [27] Hunter, T. E. and A. Nosratinia: 2002, ‘Cooperation Description Document, 2008-01-23. diversity through coding’. In: Proc. IEEE Int. Symposium on [40] Su Yi, Babak Azimi-Sadjadi, Shivkumar Kalyanaraman, Information Theory (ISIT). p. 220. Vijaynarayanan Subramanian, “Error Control Code Combining [28] Todd E. Hunter, Aria Nosratinia, “Diversity through Coded Techniques in Cluster-based Cooperative Wireless Networks”, Cooperation”, IEEE TRANSACTIONS ON WIRELESS, IEEE International Conference on Communications, 16-20 May COMMUNICATIONS, VOL. 5, NO. 2, FEBRUARY 2006, 2005, Vol 5, On page(s): 3510- 3514, ISBN: 0-7803-8938-7. pages 283 289. [41] Stefan Valentin, Tobias Volkhausen, Furuzan Atay Onat, [29] Yackoski, J.; Lu Zhang; Bo Gui; Chien-Chung Shen; Halim Yanikomeroglu, and Holger Karl, “ Decoding-based Cimini, L.J., “ Realistic Evaluation of Cooperative Relaying channel estimation for selective cooperation diversity protocols”, Networks Using Decentralized Distributed Space-Time Block IEEE 19th International Symposium: Personal, Indoor and Coding”, Communications Workshops ICC, IEEE International Mobile Radio Communications, PIMRC, Cannes, France Sept Conference, 19-23 May 2008. 2008. Page(s): 1-6, ISBN: 978-1-4244-2643-0. [30] J. Nicholas Laneman, , and Gregory W. Wornell, [42] Lu Zhang and Leonard J. Cimini Jr., “Power-Efficient “Distributed Space–Time-Coded Protocols for Exploiting Relay Selection in Cooperative Networks Using Decentralized Cooperative Diversity Distributed Space-Time Block Coding”, Hindawi Publishing in Wireless Networks”, IEEE TRANSACTIONS ON Corporation, EURASIP Journal on Advances in Signal INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER Processing, Volume 2008. 2003, page(s) 2415 2426. [43] Aggelos Bletsas, Ashish Khisti, David P. Reed, “A simple [31] Zhixin Liu; Stankovic, V.; Zixiang Xiong, “Wyner-Ziv cooperative diversity method based on network path selection”, coding for the half-duplex relay channel”, IEEE International IEEE Journal Selected Areas Communcation Vol 3, March 2006. Conference on [44] Zongpeng Li and Baochun Li, “Improving Throughput in Acoustics, Speech, and Signal Processing, (ICASSP apos;05), Multihop Wireless Networks”, IEEE TRANSACTIONS ON Volume 5, Issue , 18-23 March 2005, Page(s): v/1113 - v/1116. VEHICULAR TECHNOLOGY, VOL. 55, NO. 3, MAY 2006. [32] Nadia Fawaz, David Gesbert and Merouane Debbah, [45] Stefan Valentin, Holger Karl, “Effect of user mobility in “When Network Coding and Dirty Paper Coding meet in a coded cooperative systems with joint partner and cooperation Cooperative Ad Hoc Network”, IEEE TRANSACTIONS ON level selection”, In Proc. of IEEE Wireless Communications and WIRELESS COMMUNICATIONS, 2008, 6 pages. Networking Conference (WCNC), March 2007. [33] Ajay Gopinathan, Zongpeng Li, “Optimal Layered [46] Lu Zhang and Leonard J. Cimini, Jr., “ Hop-by-Hop Multicast with Network Coding: Mathematical Model and Routing Strategy for Multihop Decode-and-Forward Cooperative Empirical Studies”, 16th International Symposium on Modeling, Networks”, IEEE Wireless Communications and Networking Analysis, and Simulation of Computer and Telecommunication Conference, WCNC, April 2008. Systems (MASCOTS 2008), Baltimore, Maryland, USA, [47] Deqiang Chen, Kambiz Azarian, and J. Nicholas Laneman, September 8-10, 2008. IEEE Computer Society 2008, ISBN “A Case For Amplify-Forward Relaying in the Block-Fading 978-1-4244-2818-2 , page(s) 71-80. Multi-Access Channel”, IEEE Transactions on Information Theory 54(8), (2008). IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 9 www.IJCSI.org [48] Koon Hoo Teo, Zhifeng Tao and Jinyuan Zhang, Anfei Li, IEEE Communications & networking conference , IEEE WCNC, “Adaptive Frame Structure for Mobile Multihop Relay (MMR) 5-8 April 2009 , Budapest Hungary. Network”, Information, Communications & Signal Processing, [63] Vasken Genc, Seán Murphy, John Murphy, “Performance 2007 6th International Conference on Volume , Issue , 10-13 Analysis of Transparent Relays in 802.16j MMR Networks”, Dec. 2007 Page(s):1 - 5 IEEE 6th International Symposium on Modeling and [49] Tao, Z.; Li, A.; Teo, K.H.; Zhang, J., "Frame Structure Optimization in Mobile, Ad Hoc, and Wireless Networks and Design for IEEE 802.16j Mobile Multihop Relay (MMR) Workshops, WiOPT, 1-3 April 2008, page(s): 273-281, ISBN: Networks", IEEE Global Telecommunications Conference 978-963-9799-18-9. (GLOBECOM), ISBN: 978-1-4244-1043-9, pp. 4301-4306, [64] VASKEN GENC, SEAN MURPHY, YANG YU, AND November 2007 JOHN MURPHY, “IEEE 802.16J RELAY-BASED WIRELESS [50] Giuseppe Caire, Nihar Jindal, Mari Kobayashi,, Gif-sur- ACCESS NETWORKS: AN OVERVIEW”, IEEE Wireless Yvette, « Multiuser MIMO Downlink Made Practical: Communications • October 2008. Achievable Rates with Simple Channel State Estimation and [65] Masato okuda, Chenxi zhu, Dorin viorel, “Multihop relay Feedback Schemes”, Submitted to IEEE Trans. Information extension for wimax networks – An overview and benefits of Theory, Nov. 2007, 46 pages. IEEE 802.16j standard”, FUJITSU SCIENTIFIC & [51] Helmut Bolcskei, Rohit U. Nabar, Ozgur Oyman, “Capacity TECHNICAL JOURNAL FSTJ, Special Issue 1: Fujitsu's Scaling Laws in MIMO Relay Networks”, IEEE Mobile WiMAX Solutions, 2008-4 Vol.44, No.3. TRANSACTIONS ON WIRELESS COMMUNICATIONS, [66] Mike Hart & Jung Je Son,“Harmonized definitions and VOL. 5, NO. 6, JUNE 2006, page(s) 1433-1445. terminology for 802.16j Mobile Multihop Relay”, IEEE 802.16 [52] Yalin Evren Sagduyu, Anthony Ephremides, “A Game- Broadband Wireless Access Working Group, IEEE 802.16j- Theoretic Look at Simple Relay Channel”, ACM/Kluwer Journal 06/014r1. of Wireless Networks, vol. 12, no. 5, pp. 545-560, Oct. 2006. [53] J. Nicholas Laneman, “Cooperative Diversity in Wireless Networks: Algorithms and Architectures”, Thesis in Electrical First Author Dr Lamia CHAARI was born in Sfax, Engineering Tunisia, in 1972. She received the engineering and PhD at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY, degrees in electrical and electronic engineering from Sfax September 2002 national engineering school (ENIS) in TUNISIA. Actually [54] John Boyer, David D. Falconer, Halim Yanikomeroglu, she is an assistant professor in multimedia and informatics “Cooperative Connectivity Models for Wireless Relay higher institute in SFAX She is also a researcher in Networks”, electronic and technology information laboratory (LETI). Wireless Communications, IEEE Transactions on Volume 6, Her scope of research are communications, networking Issue 6, June 2007 Page(s):1992 - 2000 and signal processing which are specially related to [55] Hermann S. Lichte and Stefan Valentin, “ Implementing MAC Protocols for Cooperative Relaying: A wireless and new generation networks. Compiler Communications, Networks and Systems (SIMUTools), Mar. 2008, Best paper award. Second Author Pr Lotfi Kamoun was born in Sfax Tunisia, [56] Yalin Evren Sagduyu, “MEDIUM ACCESS CONTROL 25 January. 1957. He received the electrical engineering AND NETWORK CODING FOR WIRELESS degree from the Sciences and Techniques Faculty in INFORMATION FLOWS”, Thesis, 2007, Department of Tunisia. Actually he is a Professor in Sfax national Electrical and Computer Engineering. engineering school (ENIS) in TUNISIA. He is the director of [57] Pei Liu, Zhifeng Tao, Sathya Narayanan, Thanasis Korakis, electronic and technology information laboratory (LETI). His and Shivendra S. Panwar, “CoopMAC: A Cooperative MAC for scope of research are communications, networking, Wireless LANs”, IEEE JOURNAL ON SELECTED AREAS IN Software radio and signal processing which are specially COMMUNICATIONS, VOL. 25, NO. 2, FEBRUARY 2007. related to wireless and new generation networks. [58] Tao, Z.; Teo, K.H.; Zhang, J., "Aggregation and Concatenation in IEEE 802.16j Mobile Multihop Relay (MMR) Networks", IEEE Mobile WiMAX Symposium, pp. 85-90, March 2007 [59] Junkai Zhang Suili Feng1 We Ye Hongcheng Zhuang, MAC Performance Evaluation of IEEE 802.16j, 2008 International Symposium on Information Science and Engieering. [60] Peters, S.W.; Heath, R.W.;The future of WiMAX: Multihop relaying with IEEE 802.16j, Communications Magazine, IEEE Volume47, Issue 1, January 2009 Page(s):104 - 111 [61] Basak Can, Halim Yanikomeroglu, Furuzan Atay Onat, Elisabeth De Carvalho and Hiroyuki Yomo, “Efficient Cooperative Diversity Schemes and Radio Resource Allocation for IEEE 802.16j”, IEEE Wireless Communications and Networking Conference, WCNC , March 31 2008-April 3 2008, page(s): 36-41, ISSN: 1525-3511, ISBN: 978-1-4244-1997-5 [62] Vasken Genc, Sean Murphy, John Murphy, “Analysis of Transparent Mode IEEE 802.16j System Performance with Varying Numbers of Relays and Associated Transmit Power”, IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 10 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Authentication and Secure Communication in GSM, GPRS, and UMTS Using Asymmetric Cryptography Wilayat Khan1 and Habib Ullah2 1 Department of Electrical Engineering, COMSATS Institute of IT, Wah Cantt, 47040, Pakistan 2 Department of Electrical Engineering, COMSATS Institute of IT, Wah Cantt, 47040, Pakistan service providers. These parties would never want their Abstract resources and services to be used by unauthorized users. With its great features like providing access to users at anytime and anywhere in the world, mobile communication has been very The services like online banking, e-payment, and e/m- attractive among the users as well as operators and service commerce are already using the Internet. The financial providers. However, despite of several advantages, mobile institutions like banks and other organizations would like communication has also been facing many security problems. In their customers to use online services through mobile 2G and 3G technologies like GSM, GPRS and UMTS, the architectures comprise of mainly three nodes; the mobile station devices keeping the wireless transaction as secure as (MS), Visitor Location Register/Serving GPRS Support Node possible from the security threats. Smart cards (e.g. SIM (VLR/SGSN), and Home Location Register /Authentication card) have been proposed for applications like secure Center (HLR/AuC). These nodes are involved to encrypt/decrypt access to services in GSM to authenticate users and secure the data and authenticate the user (MS) in GSM, GPRS and payment in Visa and MasterCard [2]. Wireless UMTS. To provide security services like authentication and transactions are facing several security challenges. secure communication, the mechanism has been moved from Wireless data passing through air interface face almost the symmetric cryptography to, despite of its complexity, same security threats as the wired data. However, the asymmetric cryptography. To reduce the signaling overhead and limited wireless bandwidth, battery, computational power add some other security features, we propose a new generalized and memory of wireless devices add further limitations to approach in this paper. This is based on asymmetric cryptography for user/network authentication and the security mechanisms implementation [3]. communication encryption in GSM/GPRS and UMTS with reduced signaling overhead. The use of mobile communication in e/m-commerce has Keywords: GSM, GPRS, UMTS, Authentication, Security, increased the importance of security. An efficient wireless Asymmetric Key Cryptography. communication infrastructure is required in every organization for secure voice/data communication and users authentication. Among the main objectives of an 1. Introduction efficient infrastructure is to reduce the signaling overhead and reduce the number of updating Home Location Wireless and mobile communication systems are very Register/Authentication Center (HLR/AuC) while the famous among the customers as well the operators and Mobile Station (MS) changes its location frequently [3]. service providers. Unlike wired networks, the wireless networks provide anywhere and anytime access to users. In this paper, we propose an approach based on public key The Global System for Mobile Communications (GSM) cryptography which mainly focuses on user and network occupy almost 70% of the wireless market and is used by authentication with reduced signaling overhead and meet millions of subscribers in the world [1]. other security requirements like non-repudiations, safety from denial-of-service attacks and integrity of In the wireless services, secure and secret communication authentication signaling messages. is desirable. It is the interest of both, the customers and the IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 11 www.IJCSI.org The rest of the paper is organized as follows. Section 2 3. Authentication and Ciphering in GSM and gives a brief overview of GSM systems architecture and GPRS section 3 discusses authentication protocol used in GSM/GPRS. Section 4 describes authentication and There are various security threats to networks [6]. Among communication encryption in UTMS. Some related work these threats are Masquerading or ID Spoofing where the is discussed in section 5. In section 6, we propose a new attacker presents himself as to be an authorized one, approach for user and network authentication and unauthorized use of resources, unauthorized disclosure communication encryption. Finally, after short discussion, and flow of information, unauthorized alteration of a conclusion is drawn. resources and information, repudiation of actions, and denial-of-service. The GSM network incorporates certain security services for operators as well as for their 2. GSM Overview subscribers. It verifies subscribers’ identity, keeps it secret, keeps data and signaling messages confidential and GSM, the Group Special Mobile, was a group formed by identifies the mobile equipments through their European Conference of Post and Telecommunication International Mobile Equipment Identity (IMEI). In the Administrations (CEPT) in 1982 to develop cellular next subsections, we explain subscribers’ authentication systems for the replacement of already incompatible and data confidentiality as they are closely related to our cellular systems in Europe. Later in 1991, when the GSM topic [5]. started services, its meaning was changed to Global System for Mobile Communications (GSM) [1]. The entire architecture of the GSM is divided into three subsystems: Mobile Station (MS), Base Station Subsystem (BSS) and Network Subsystem (NSS) as shown in Figure 1. The MS consists of Mobile Equipment (ME) (e.g. mobile phone) and Subscriber Identity Module (SIM) which stores secret information like International Mobile Subscriber Identity Module (IMSI), secret key (Ki) for authentication and other user related information (e.g. certificates). The BSS, the radio network, controls the radio link and provides a radio interface for the rest of the network. It consists of two types of nodes: Base Station Controller (BSC) and Base Station (BS). The BS covers a specific geographical area (hexagon) which is called a cell. Each cell comprises of many mobile stations. A BSC controls several base stations by managing their radio resources. The BSC is connected to Mobile services Switching Center (MSC) in the third part of the network NSS also called the Core Network (CN). In addition to MSC, the NSS consists of several other databases like Visitor Location Register (VLR), HLR and Gateway MSC (GMSC) which connects the GSM network to Public Switched Telephone Network (PSTN). The MSC, in cooperation with HLR and VLR, provides numerous functions including registration, authentication, location updating, handovers and call routing. The HLR holds administrative information of subscribers registered in the GSM network with its current location. Similarly, the Figure 1. Components overview of GSM VLR contains only the needed administrative information of subscribers currently located/moved to its area. The Equipment Identity Register (EIR) and AuC contains list of valid mobile equipments and subscribers’ authentication information respectively [1, 5]. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 12 www.IJCSI.org 3.1 Subscribers Identity Authentication The HLR sends the triplet including Kc, RAND and SRES to VLR. The VLR sends the RAND challenge to MS and As mentioned above, the SIM card holds IMSI, phone ask to generate an SRES and send it back. The mobile number, authentication key Ki, subscriber-relevant data station creates an encryption key Kc and SRES using and security algorithms like authentication algorithm (A3). algorithms A3 and A8 with the inputs secret key Ki and The HLR also stores a copy of Ki and IMSI etc. RAND challenge. It stores Kc to use it for encryption and sends SRES back to the VLR. The VLR compares SRES In GSM, the users are first identified and authenticated with the one sent by HLR. If they match, the then the services are granted. The GSM authentication authentication succeeds otherwise it fails [1, 4, 5]. protocol consists of a challenge-response mechanism. The authentication is based on a secret key Ki which is shared 3.2 User Data and Signaling Protection between HLR and MS. After a visited MS gets a free channel by requesting BS, it makes a request for its The encryption key Kc is used by both of the parties location update to MSC through BSC. The MSC, in (home system and mobile station) to encrypt the data and response, asks MS for its authentication. signaling information using A5 algorithm. The encryption is done by mobile equipment not the SIM because SIM In the entire authentication process, the three main actors does not have enough power and processing capacity [1, are the MS, MSC/VLR and HLR/AuC as given in Figure 4, 5]. 2. The mobile station sends its Temporary Mobile Subscriber Identity (TMSI) to VLR in its request for authentication. The MS uses its real identity IMSI when it 4. Authentication and Ciphering in UMTS is switched on for the first time but the temporary identity TMSI is used later. The TMSI is used to provide The UMTS, in fact, is the result of evolution in GSM anonymity to the user identity. After getting the IMSI of network through GPRS. The GSM networks are capable the mobile station from the old VLR using TMSI, the of voice communication using Circuit Switched (CS) VLR sends IMSI to the corresponding HLR/AuC. The technique while GPRS adds Packet Switched (PS) HLR/AuC uses authentication algorithm (A3) and technique through the use of some extra nodes like ciphering key generation algorithm (A8) to create the Serving GPRS Support Node (SGSN) and Gateway GPRS encryption key (Kc) and Signed RESult (SRES) Support Node (GGSN). The UMTS, incorporating GPRS respectively. nodes and UMTS Terrestrial Radio Access Network (UTRAN), provides both circuit switched and packet switched services with enhanced multimedia applications. As stated in 3GPP specification [7], the circuit switched services are provided by VLR and the packet switched services are provided by SGSN. The UMTS, like GSM/GPRS, uses the concept of Authentication Vector (AV) but unlike GSM/GPRS, the AV comprises of five components: the random challenge (RAND), the expected response (XRES), key for encryption (CK), integrity key (IK) and the authentication token (AUTN). The VLR/SGSN requests HLR/AuC for authentication. The HLR/AuC computes the AV and is sent back as a response to VLR/SGSN without any encryption applied to it. After the authentication is completed, the cipher key CK is used to encrypt the user data and signaling information. Similarly, to preserve the integrity of the important control signals, integrity key (IK) is used. The GSM Consortium actually provided security to GSM Figure 2. The GSM authentication architecture systems relying on security through obscurity where they believed that the algorithms used in GSM would be very hard to break if they were kept secret. Therefore, the GSM specifications and protocols were kept secret away from public to be studied and analyzed by scientific community. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 13 www.IJCSI.org But, eventually, the GSM algorithms were accessed by between VLR and HLR is secured using the VLR-HLR scientific community and now GSM is vulnerable to many public key (V_HPuK). The messages are encoded with this attacks [6, 7, 10]. key by any of the endpoints. At the receiving end, the corresponding private key V_HPrK is used for decryption. In GSM/GPRS and UMTS, the links between MS-VLR and VLR-HLR faces many security threats due the use of After the channels are assigned, the users are authenticated conventional symmetric key encryption and mutual trust through the exchange of messages among the nodes: MS, of the parties. The VLR and HLR just rely on mutual trust VLR and HLR as shown in Figure 3. The MS (SIM on they have on each other. mobile station) sends an Identity Message to VLR which includes the identity data (e.g. IMSI of the user) encrypted To implement public key cryptography, a well defined with MS-VLR’s public key (MS_VPuK). The VLR decodes network infrastructure is needed. The Public Land Mobile it using corresponding private key (MS_VPrK) and extracts Network (PLMN) operators are the main candidates for the required information. The VLR encrypts it again with this to develop PKI in their systems. The 3G networks like VLR-HLR link public key (V_HPuK) and forwards it to the UMTS which offers services with very high data rates is corresponding HLR in Authentication Information the most favorable for the operators to incorporate PKI message. After it is decoded using VLR-HLR link private services to their customers. To verify the authenticity of key (V_HPrK), the HLR sends the user’s public key public keys, there should be a trusted third party, the (MSPuK) back to the VLR in an Authentication Certification Authority (CA), to issue digital certificates to Acknowledgment message. The VLR sends a random the users. These certificates are to be stored in the challenge RAND to the MS encrypted with the user’s SIM/USIM of the mobile station. The Mobile Execution public key (MSPuK) in Authentication Request message. Environment (MExE) is an application execution The MS decodes the random number, encrypts it with its environment which allows application programming and own private key and sends it back along with SK and IK creating a Java Virtual Machine (JVM) in the MS. Based to VLR in Authentication Response message. The VLR on the importance of secure transactions and the fact that decrypts this message using the user’s public key and networks operators are the big candidates for PKI checks if the random number is the same. If it is equal to implementation, it seems feasible to use public-private key the random number held by VLR, it will indicate the user pair for intra-PLMN signaling as well as for secure e/m- authenticity as it has been signed by the user with his own transaction. A new approach, with the introduction of private key. asymmetric key cryptography, has been adopted in [8]. Public key cryptography is computationally extensive. Therefore, it slows down the data rate. It can be better 5. Related Work utilized when it is used for secret keys transmission. The SIM on the MS creates secret key (SK) and in case of Asymmetric key approach supported by MExE is another reason to be favorable for operators to deploy Public Key Infrastructure (PKI) in their systems. The asymmetric key cryptography for authentication and encryption, as mentioned in [8], is described below. Identity Message EMS_VPuK(IMSI) 5.1 Asymmetric Cryptography in GSM/GPRS and Auth. Information UMTS EV_HPuK(IMSI) Auth. Acknowledge As in GSM/GPRS, we consider the same three nodes: MS, MSPuK VLR and HLR/AuC. These nodes preserve the same roles Auth. Request MSPuK(RAND) for all the three systems: GSM, GPRS and UMTS, involved in the process of authentication and encryption. Auth. Response MSPrK(RAND|| EMS_VPuK(SK||IK)) The nodes VLR and HLR hold the same pair of public- private keys, V_HPrK and V_HPuK, which facilitates the key distribution process because other interconnected networks would need only one public key for Figure 3. Authentication process using public key cryptography corresponding VLR-HLR transactions. A second option could be to use separate public-private key pairs but it will further complicate the key distribution process. The link IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 14 www.IJCSI.org UMTS an integrity key (IK) for the integrity of signaling messages. These two keys are concatenated, encrypted with VLR’s public key (MS_VPuK) and are sent to the VLR V_HPrK: VLR-HLR link’s private key V_HPuK: VLR-HLR link’s public key in the Authentication Response message. After the authentication is successful, the data and signaling M_VPrK: MS-VLR link’s private key information are encrypted with the keys SK and IK to M_VPuK: MS-VLR link’s public key preserve the confidentiality and integrity of both the data HPrK: HLR private key and signals. HPuK: HLR public key The public key cryptographic approach discussed in the MPrK: Mobile station’s private key above paragraphs is an obvious way of authentication and MPuK: Mobile station’s public key securing the communication especially when it is used in financial transactions like e/m-commerce. In this approach, five messages are exchanged to authenticate the user and to share the keys which brings signaling Figure 4(a). Set of public keys used overhead. In this approach, the user (MS) is authenticated by the network before giving the service but it does not authenticate the network. One can rely only on the fact that both, the MS and the HLR, have the same secret key MS VLR HLR Ki. This can be considered a weak network authentication, but it will fail if the key Ki is stolen or accessed by a third party. The denial-of-service attack is possible if the Identity Message attacker changes the authentication signaling (signal Auth. Information integrity). In the next section, we propose a general solution with reduced signaling for all the three systems Auth. Acknowledge GSM, GPRS and UMTS to reduce the drawbacks discussed above. Forward Auth. Acknowledge 6. Authentication and Encryption in GSM, GPRS and UMTS Using Public Key Cryptography Figure 4(b). Authentication process using public key cryptography Due to slow data rates, the public key encryption offers, it is not encouraged to be used for communication encryption. Instead, it is preferred for authentication and Authentication Acknowledge = MPuK secret key distribution to be used in symmetric key Forward Authentication Acknowledge = EMPuK (RAND) encryption of the communication. To encrypt the data and signaling, special secret and integrity keys like SK and IK The symbol ‘||’ represents the concatenation of two may be used respectively for communication encryption elements. The MS creates secret keys SK, IK and a and signaling integrity. random challenge RAND. It starts the authentication exchange by sending an Identity Message to the visited In this section, we present a solution based on public key VLR. This message includes concatenation of RAND, SK cryptography. This relies on the same concept of public- and IK encrypted with public key M_VPuK. The IMSI and private keys as mentioned in the section 5. The three main Ki encrypted with public key HPuK is also part of the entities, MS, VLR and HLR, are using four pairs of Identity Message as shown in Figure 4(b). Unlike the public-private keys as shown in Figure 4(a). approach in [8], the secret keys SK and IK are sent in the first message. These three entities exchange four messages with each other as shown in Figure 4(b). The detail of the elements The VLR uses the corresponding private key M_VPrK to in each of these messages is decode the part of the message and extract the needed information RAND, SK and IK. The VLR forwards the Identity Message = EM_VPuK (IK||SK||RAND) || EHPuK (IMSI|| Ki) rest of message (EHPuK(IMS||Ki)) unchanged in Authentication Information = EHPuK (IMS||Ki) Authentication Information message to the HLR. The keys IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 15 www.IJCSI.org SK and IK are used later for confidentiality and integrity 7. Conclusions of both the data and signals respectively. Wireless communication, having great features, is The HLR decodes the Authentication Information message attractive among users as well service providers. With the with its private key HPrK and gets the IMSI and Ki sent increase in its use, security problems of confidentiality, from MS. The secret key Ki is used as a random challenge integrity, and authentication are also increasing. The for user/MS authentication. The MS and the HLR have the mechanism to solve these problems has changed to public same secret key Ki. The HLR compares the received Ki key cryptography from symmetric key cryptography. The with its own Ki. If they match, the user is authenticated. It available public key cryptographic approaches are good in is difficult for a third party to change this secret without security point of view but they are computationally being detected by HLR. The HLR can easily detect it extensive as well as have more signaling overhead. using IMSI of the requesting user sent in the Identity Furthermore, these approaches do not provide integrity of Message. the initial authentication messages and authentication of the network. Using the IMSI, the HLR finds the corresponding user’s public key MPuK and is sent to VLR in the Authentication In this paper, we proposed an enhanced model based on Acknowledge message. This message acts as an indication the public key cryptography. In this model, utilizing the to the VLR that the user has been authenticated by the real benefits of public key encryption, user as well as HLR. The VLR uses the public key MPuK to encrypt the network authentication is provided. The integrity of the RAND challenge received from MS in the Identity signaling used during the user and network authentication Message. The MS decrypts it with its own private key. is ensured. The secret keys for data encryption and The result is compared with the RAND stored at MS. If signaling integrity are distributed using public keys. These they are equal, the VLR is authenticated as it ensures the benefits are achieved with fewer signals reducing the MS that the VLR is the only entity having the MS-VLR signaling overhead. link’s private key M_VPrK. As noted before, although, public key cryptography is This approach includes all the benefits of the previous computationally very extensive which requires large systems. It keeps the user’s identity secret, the encryption processing power, battery, and memory, but still the keys are distributed, users and network both are approach we proposed is efficient to use than the others. authenticated. This entire process requires four signaling The rapid developments in Integrated Circuits (IC) and messages reducing the signaling overhead. Smart Cards (e.g. SIM) technologies, high speed communication systems (e.g. UMTS), and significance of An attack denial-of-service may be possible if the attacker secure transactions (e.g. e/m-commerce) make the changes the signaling contents based on which the user conditions more favorable to use public key cryptography. and network authenticates each other. For example, if the encrypted content of RAND challenge is modified or if References IMSI or Ki is changed during transmission, the network [1] Yong Li, Yin Chen, and Tie-Jun MA, “Security in GSM”, and user authentication will fail even if the user and Retrieved March 18, 2008, from http://www.gsm- network are legitimate. To cope with this problem, Digital security.net/gsm-security-papers.shtml. Signature [9] can be used. The end-to-end integrity of the [2] N. T. Trask and M. V. Meyerstein, “Smart Cards in authentication parameters should be ensured because the Electronic Commerce”, A SpringerLink journal on BT end entities, the VLR/HLR and the MS, make the decision Technology, Vol. 17, No. 3, 2004, pp. 57-66. [3] N T Trask and S A Jaweed, “Adapting Public Key of authentication. Therefore, to ensure the integrity of Infrastructures to the Mobile Environment”, A SpringerLink message contents at the ends, hashing (H) function journal on BT Technology, Vol. 19, No. 3, 2004, pp. 76-80. combined with encryption may also be used. For example [4] Cheng-Chi Lee, Min-Shiang Hwang, and I-En Liao, “A New the elements IMSI and KI may be hashed using the secret Authentication Protocol Based on Pointer Forwarding for key Ki and the resulted message digest is sent in the Mobile Communications”, A Wiley InterScience journal on Identity Message. This will ensure the HLR that the Wireless Communications and Mobile Computing, Published parameters IMSI and Ki have not been altered during online, 2007. transmission. [5] Vesna Hassler and Pedrick Moore, “Security Fundamentals for E-Commerce”, Artech House London Inc., 2001, pp. 356-367. [6] Mohammad Ghulam Rahman and Hideki Imai, “Security in Wireless Communication”, A SpringerLink journal on IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 16 www.IJCSI.org Wireless Personal Communications, Vol. 22, No. 2, 2004, pp. 213-228. [7] 3GPP. 3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; Mobile Execution Environment (MExE); Service Description, Stage I. Technical Specification 3G TS 22.057 version 5.2.0 (2001- 10), 2001. Wilayat Khan graduated with a B.Sc. in Computer Systems Engineering from the NWFP University of Engineering & Technology, Pakistan in 2007. He earned his MS degree from the Royal Institute of Technology (KTH) Sweden in Information and Communication Systems Security in 2009. In his MS theses, he designed a strong authentication protocol for handheld devices. In 2009, he started his carrier as a teacher at the Department of Electrical Engineering, COMSATS Institute of IT, Wah Campus, Pakistan. He has published a number of papers on wireless and mobile networks and security in international journals and conference proceedings. His research interests include wireless & mobile networks, protocol design for mobile devices, authentication, web security and smart cards security. Habib Ullah graduated in B.Sc. Computer Systems Engineering from the NWFP University of Engineering & Technology, Pakistan in 2006 and earned M.Sc. degree in Electronics and Computer Engineering from the Hanyang University, Seoul Korea with a thesis focusing on comparative study: the evaluation of shadow detection methods. He started teaching in 2009 at the department of Electrical Engineering, COMSATS Institute of IT, Wah Campus, Pakistan. He has various publications focusing on background modeling and shadow detection. His research interests include information security, pattern recognition, behavior modeling and object segmentation etc. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 17 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Touching Syllable Segmentation using Split Profile Algorithm L.Pratap Reddy1, T.Ranga Babu2, N.Venkata Rao3 and B.Raveendra Babu 4 1 Department of Electronics and Communication Engineering, JNTUH College of Engineering, Hyderabad - 500085, Andhra Pradesh, India 2 Department of Electronics and Communication Engineering, RVR & JC College of Engineering, Guntur - 522019, Andhra Pradesh, India 3 Department of Electronics and Communication Engineering, Sri Vasavi Engineering College, Tadepalligudem - 534101, Andhra Pradesh, India 4 Department of Computer Science and Engineering, RVR & JC College of Engineering, Guntur - 522019, Andhra Pradesh, India Abstract the field of language technology based research. The most challenging task of a character recognition system is Automated content creation from printed or written form associated with segmentation of individual components of the of ancient and later versions of documents is the major script with maximum efficiency. This process is relatively easy area of OCR research. Achieving accurate results under all with regard to stroke based and standard scripts. Cursive scripts possible conditions remains as a challenging task. The first are more complex possessing a large number of overlapping and step in this process is to achieve maximum efficiency in touching objects, where in the statistical behavior of the topological properties are to be studied extensively for achieving character segmentation, which inturn reflects in OCR highest accuracy. Certain amount of similarity exists between accuracy. unconstrained hand written text as well as South Indian scripts in terms of topology, component combinations, overlapping and Script topology plays a dominant role in the segmentation merging characteristics. The concept of syllables and their process. Structural features describe the patterns of formulations is an additive complexity with regard to Indian topology and geometry while exploring global and local scripts. In this paper the statistical behavior of the cursive script, properties. White spaces and pitch information are the Telugu, is presented. The topological properties in terms of useful primitive parametric data of any segmentation zones, component combinations, behavioural aspects of syllables system. The notion of detecting vertical white space are studied and adopted in the segmentation process. The statistical behaviour of cursive components are evaluated. Split between successive characters is an important concept Profile Algorithm is proposed while handling touching while dissecting images of machine print and even in hand components. The proposed algorithm is evaluated on different written documents. Apart from this, other topological fonts and sizes. The performance of the proposed algorithm is features like height, width and orientation etc., are useful compared with two approaches methods viz aspect ratio and parameters. In case of fixed width characters, pitch syllable width approaches. information provides effective segmentation. However, Keywords: Segmentation, Connected Components, Syllable variable width characters are found in almost all scripts Segmentation, Touching Syllable, Split Profile Algorithm. due to large number of font designers. As a result, various segmentation approaches are proposed [1] in literature to handle this complexity. 1. Introduction Structural properties of natural language script are another Document image analysis and Optical Character useful piece of information, to be adopted while choosing Recognition (OCR) systems are under continuous research the segmentation approach. Scripts can be further for decades. The transformation of paper media into the classified as stroke based, cursive and hybrid. searchable and revisable text format gives a great boost in Segmentation of stroke based scripts can be performed by IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 18 www.IJCSI.org making use of properties like horizontal, vertical and slant in [4]. The connected component approach proposed in line information. this work is mainly concentrated on defining specific rules Segmentation approaches that are to be adopted for using height and width parameters of bounding box.. The cursive scripts are complex when compared with stroke adjacency relationships between bounding boxes, their based scripts. Character shapes of these scripts posses size and aspect ratios are explored for splitting variable widths and sizes, originated from a combination mechanisms. Segmentation effectiveness is reported with of more than one component. The topological or structural high degree of accuracies even at low computational properties of individual components and their associative requirements. Extension of connected component nature with other components transform the final shape, approaches is proposed in [5] by G.Seni and E.Cohen for occasionally leading to overlapping and touching segmentation of hand written words in a document image. phenomena. Segmentation issues of these scripts are to be addressed by considering common statistical properties The CJK script models are more predominant in strokes along with specificities of the respective class of and relationships among the strokes are well structured formulations. On the other hand, hybrid model is [6]. Latin text, European language models describe the associated with a set of strokes as well as curves. The dominance of strokes. The linear property of strokes is primitive shape (glyph) is to be treated as the main focus explored in using profile based approach while of this model. segmenting characters of all the above scripts. North Indian scripts are hybrid in nature, combining 2. Review strokes and curves, where strokes are dominated by curves. Linear spatial relationship in the form of Various segmentation methods adapted in document shirorekha (a straight line combining components) can be image processing are described [1] by Richard G.Casey found within the topological structure. The resultant form and Eric Lecolinet. Profile based approach proposed [2] of this linear relation is treated as zone, which is used to by K.Ohta which is considered as a simple and effective establish correlation among strokes and curves within the method for segmenting a print line. These approaches are syllables. The top zone of the character resembles stroke reported to be effective for non-cursive writing systems like geometry. The positional information of zone is and still found their applications even in handwritten identified by finding the linear region from the profile recognition systems. Detection of white spaces can be function of script line. Segmentation is achieved by effectively carried out on a structured text image. exploring the statistical properties [7,8,9,10,14] of zone Identification and extraction of vertical strokes is made information using profile based methods. simple using this method. Analysis of peaks and valleys of profile patterns extended the scope of profile method for Arabic and South Indian scripts are dominated by curve partial adaptation into touching character segmentation. In like components. In Arabic scripts, the formation of [1], the profile was first obtained and then the ratio of character is nonlinear and base line is identified by the peak second derivative of this pattern to its height is used as a of vertical profile function[11]. South Indian scripts are criterion for identifying segment separation. The peak of derived from the writing style on palm leaves, resembling the derivative, which is associated with projection minima cursive nature in machine print as well as hand written. converge the splitting points along the thin horizontal lines. The process of character formulations resulting from component combinations with zero width joiner and some A peak-to-valley function is proposed in [3] by Y.Lu with times with non joiner leading to overlapping phenomena. further improvements. Spatial domain characteristics Character formation in these scripts (also known as based on the topological features of the script are explored. syllable) deals with two part glyphs in certain cases, Valleys between successive peaks are extracted from the deviating from the linear process. Notable number of non- profile function. An average function is used to identify linear combinations exists in these scripts. Segmentation is the extract segment point with a specific reference to to be addressed by taking into consideration of all touching characters. A selection criterion of the processes, linear and non-linear combinations. In this segmentation boundary is associated with discriminating context, the statistical behavior of component shapes function of topological features of individual within the boundaries of text line, any word and even a characteristics. syllable, influences the segmentation strategies. In South Indian scripts, curves are more predominant and Bounding box approach [4] is proposed by M.Cesar and extraction of zone information is complex. Syllable is R.Shinghal as an alternative to profiling method. They formed by a set of curves with high degree of similarity reported that the method is effective on stroke based script. among them. The individual components in the syllable are Splitting and merging of character component is reported IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 19 www.IJCSI.org extracted and associated relationship is studied using zone proposed [13] by Pratap et al, presented in Fig. 1 and is information. The extraction of zone information is adopted in the present phase. complex because of the non-linear distribution of glyphs in the upper and bottom regions. Common properties are Topology of the syllable can be decomposed into reported in [12,13] by extensive statistical evaluation of component like glyph objects. One base symbol object, the profile function. also treated as essential component, is the minimum topology. In a complex conjunct syllable a maximum of Profile method [11] found its use not only in printed text four other components will be positioned, as in the above but also in hand written text. Handwritten profile figure. The number of components may vary in between 1 information of the script line is used to identify the linear and 5. However the topological features in the form of portions of the script characters. The profile information zones is difficult to extract due to the inherent nature of of a word differs from that of a line. At the same time, zero width joiner and non joiners between components. multiple word combinations of a script line posses linear This phenomenon reflected in the form of touching behavior in the profile patterns. Extensive statistical syllables that are predominant in various font sizes. evaluation of various script lines is necessary while formulating rules in the zone identification process. Using the above model, syllable segmentation and Similar studies are extended to syllable segmentation in classification of touching syllable is carried out in phase 2 the present paper. A detailed description of segmentation and 3 respectively. In the last phase, segmentation of model is presented in the following section. touching syllable is addressed with the help of SPA. Topology of various syllable components is studied after splitting the profile. Prediction of segmentation threshold 3. Segmentation Model is carried out in the separation process of touching syllables. The segmentation model in this paper explored the statistical patterns of profile vector which signifies the 3.1 Line and Zone Separation topology and geometry of printed text with specific reference to cursive script of Telugu. Preprocessing steps Different scripts posses varied structural features. like binarisation, skew correction are carried out on the However machine printed document images are structured document image before proceeding to segmentation in nature with a similarity around script line distribution. algorithm. The linear property from pixel distribution of Horizontal projection Profile (HPP) is adopted for line segmentation. HPP is obtained using Eq.(1) N H PP (i )   f (i, j ) (1) j 1 where i = 1,2,3,.. M (Height of the object) j = 1,2,3….N (Width of the object) White spaces between text lines are treated as delimiters in ideal case. However under the influence of noise the Fig. 1 Canonical Syllable Model. profile distribution between lines reflects the random nature of noise information. In the present case, we Four phases are proposed in the segmentation process. considered ideal scenario, where the noise component is First phase deals with line segmentation and extraction of negligible. Starting point and ending point of script line is zone information, second phase deals with syllable found with certain amount of black pixel distribution, segmentation, third phase addressed the classification of using which the lines are segmented. segmented syllables into touching and non-touching Pixel distribution of script line is studied on various objects and fourth phase is emphasised on segmentation of document images. Certain amount of linear behavior is touching objects using Split Profile Algorithm (SPA). found in the form of peaks and valleys, reflecting the zone information. The geometry of individual syllable does not In the first two phases, connected component approach is match with zones, which is also the case with certain adopted for segmentation of syllable. Syllable model words where as multiple combinations of words found to IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 20 www.IJCSI.org be linear. One peak in the first half of profile distribution Fig. 3 Line & Zone separation fro horizontal profile. is observed. This peak matched with zone separation line between top and middle zones. However zone separation line between middle and bottom zone is reflected in the form of maximum slope in the later half of the profile formation. The detailed algorithm for Line and Zone separation is listed below Step 1 Extract horizontal profile vector for the whole Fig. 4 Zone Information of text sample. document image. Step 2 Divide the Lines profile vector which consists of starting and ending of the line in the image and 3.2 Syllable Segmentation mark them as top line and bottom line respectively. Step 3 Extract first line from the document image In an ideal scenario, individual glyph components (Fig.1) Step 4 Divide the script line profile vector into two halves can be decomposed using zone information. The canonical along the length. space is extracted from the text document using connected Step 5 Find the row with peak value of black pixel density component approach with a reported [13] segmentation in the first half of the profile vector and mark it as efficiency of 95.72%, without addressing the touching Head Line. syllables. Similar approach is adopted in the present phase. Step 6 Find the rows with peak values of black pixel The component objects that are separable, are identified density in the later half of the profile vector. with the help of labeling approach. Grouping of core and Step 7 Find the slope of the valley from the row in Step 6 non-core components are carried out while segmenting with respect to the successive row. syllable objects. These objects may include touching Step 8 The row with the maximum slope of the valley is syllables also. The syllable segmentation is given below identified as the base Line. Step 9 Extract the Top-Middle-Bottom zones of the script The detailed algorithm is as follows: line. Get the zone information for different script lines. Step 1 Extract the zone information for different script lines. Original document image is presented in Fig.2 Step 2 Label the pixels by scanning them from left to right Segmentation of lines and extraction of zone information, in each row and row after row. as defined in steps 1-5, is presented in Fig.3 and Fig.4. Step 3 Find adjacent labels and connect the labels to form basic components. Step 4 Find unique labels and extract component with unique labels Step 5 Identify whether it is core component or non-core component using zone information Step 6 Merge the non-core components with core components using zone information. Step 7 Extract the Syllable from the input text image and draw the bounding box. Fig. 2 Original Document Image. The concept of core component and other components in a syllable as proposed by Pratap Reddy et al. [13] is a reflective mechanism of the topology and geometry with regard to Telugu script. This property is explored in steps 1-7 and the result is presented in Fig.5. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 21 www.IJCSI.org Fig. 5 Segmented Syllables of document image. Fig. 7 Syllables classified as Touching syllable using Aspect Ratio 3.3 Classification of Correctly Segmented Syllables In the process of improving segmentation efficiency, it is required to classify the correctly segmented syllables against the others. The syllable objects, extracted from the previous stage are a combination of touching and non- touching syllable objects. Aspect ratio (the relation between component height and width) is a simple approach adopted for this purpose which is defined in Eq.(2). Fig. 8 Height and width variation of Syllable. Component Width Topology of the script is so complex, at times height and Aspect Ratio(A) = (2) width of a syllable posses large variations as described in Component Height Fig.8 The optimum threshold ThASP is defined in Eq.(3) The variables A,B,C define the height of top zone, middle zone and bottom zone layers. P,Q,R variables are  N computed as A+B, B+C, A+B+C respectively. It is quite A( i )  interesting to see that the syllable height may have varying Th ASP   i 1  (3)  N  combination among B, P, Q, R. Similarly two different   specifications can be made with regard to syllable width M, defined as core width and N, as modifier width. Two ThASP is an averaging function of the relationship between possibilities always exist. The width of the syllable may be component objects, which is used as a threshold value. M or some times extends to M + N depending on the type The syllable object with A ≥ ThASP is treated as touching of modifiers. The value of M and N differs for each core syllable. Segmented output after adaptation of aspect ratio component as well as modifiers. The possible combination is presented in Fig.6 and Fig.7. of aspect ratio finally leads to 8 different types for each type of core component. There are 36 different types of core components, where the width and sizes differs slightly. In addition to that another 13 modifiers exists. The entire complexity can be visualised in the form of classification error leading to isolated syllables pushed into touching syllables. This error influences segmentation efficiency up to a large extent. Fig. 6 Syllables classified as Single Syllable using Aspect Ratio. While resolving the segmentation problem and to reduce the classification error, it is necessary to identify effective classification mechanism. As per the evaluation in [15] the syllable groups and their frequency statistics reveal the fact that modifier combinations are only 16% of the text information. Large numbers of syllable groups are focused around core width. Average syllable width is one of the parameter for better judgment. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 22 www.IJCSI.org (Anupama, Gowthami and Priyanka) reveals the fact that The optimum threshold for classification of syllable large number of overlapped characters is present in small objects is redefined as ThSYW (Average Syllable Width), sized font structures. Some syllables with large width may and is given in Eq.4 be classified as touching syllable. They will play a major role on segmentation efficiency. Connected component  N  approach fails in segmenting the touching characters for   W (i)  (4) T h SYW   i 1  the reasons explained above.  N      To handle this problem we propose an alternative method, Split Profile Algorithm, where the profile information of The outcome of the classifier using ThSYW is presented in the touching syllable will be split into two parts and the Fig.9 & Fig.10. It is observed that the error is now reduced geometric features are studied for identification of further, while classifying touching syllable only. touching labels. Two parameters are introduced in the algorithm. The first one ‘Horizontal Split Threshold’ (STH) which is used to identify the splitting index of the text line segment. The second one ‘Vertical Split Threshold’ (STV), to identify the segment boundary of touching syllable. Horizontal split threshold is defined as Fig. 9 Syllables classified as Single Syllable using Syllable Width. STH = Head Line + ((Bottom Line – Head Line)/2) Vertical split threshold is defined as STV = 2nd transition point from low to high in the lower part of the profile Either the top segment or bottom segment can be considered for extraction of syllable index. The topology of the touching characters is mostly associated with Fig. 10 Syllables classified as touching syllable using Syllable Width. positional structure of glyph like components. In this context one of the line segments will provide positional After careful analysis on 38,419 syllables (12,14,16 &19 information of the above components. Vertical profile of font sizes) of Anupama font, it is found that segmentation the respective portions of line segments is plotted for this efficiency is 91.39% for Aspect ratio, where as 94.48% purpose. The profile part with multiple segments is used for Syllable width. An improvement of 3 % is observed. for defining segmentation index. From the statistical study For Gowthami font (30,871 syllables) segmentation it is observed that the starting point of the second efficiency is observed as 86.63% and 89.20% for aspect component is the most likely predicted segment boundary ratio and syllable width respectively. In the case of from STV. The split profile algorithm which was applied is Priyanka font average efficiency is observed as 81.73% as follows and 87.32% respectively. The algorithm for SPA 3.4 Split Profile Algorithm Step 1 Get the horizontal profile of the syllable Step 2 Split the horizontal profile using ‘STH’ The topology of the syllable, where cursive nature is more Step 3 Get the vertical profile for the lower part of the predominant, provides information about the placement and image. their relationship among the glyphs. The syllables are Step 4 Split the touching syllable by using Vertical Split formed with the placement of glyph(s) with varying style Threshold ‘STV’ index from the scaled profile and sizes. In certain occasions one syllable may overlap obtained from step 3. with the next syllable. This situation may appear at different zones of the syllable, resulting in complex behavior. The statistical analysis on different fonts IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 23 www.IJCSI.org Fig. 11 Vertical Profile of the First Syllable Fig. 13 Vertical Profile of the Second Syllable. Fig. 12 Scaled Vertical Profile for the lower part of the First Syllable. Figure 14. Scaled Vertical Profile for the lower part of the Second Syllable Table 1: Output for the first syllable after SPA Table 2: Output for the second syllable after SPA IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 24 www.IJCSI.org STH and the split profile STV. Segmented syllables after adaptation of STV are presented in Table 1 and 2. Fully segmented syllables after the Split Profile Algorithm is presented in Fig.15. Various combinations of touching syllables, which lie in various zone combinations are studied with the help of above algorithm. Fig. 15 Segmented Syllables of text sample after SPA SYLLABLE BASED SEGMENTATION SYLLABLE BASED SEGMENTATION 100.5 100.0 % of Segmentation 100.0 99.5 % of Segm entation 95.0 99.0 90.0 98.5 85.0 98.0 80.0 97.5 75.0 97.0 70.0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Syllable w idth & SPA No of Samples Syllable w idth & SPA No of Samples Syllable Width Syllable Width Aspect Ratio Aspect Ratio Fig. 18 ANUPAMA for size 16. Fig. 16 ANUPAMA for size 12. SYLLABLE BASED SEGMENTATION SYLLABLE BASED SEGMENTATION 100.5 101.0 100.0 % of Segmentation % of Segmentation 100.0 99.5 99.0 99.0 98.5 98.0 98.0 97.0 97.5 97.0 96.0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Syllable w idth & SPA No of Samples Syllable Width & SPA No of Samples Syllable w idth Syllable Width Aspect Ratio Aspect ratio Fig. 17 ANUPAMA for size 14. Fig. 19 ANUPAMA for size 19. The first bounding box of the touching syllable in the Efficiency comparisons between Split Profile Algorithm, earlier Fig.10 is considered for evaluation. Fig.11 and Syllable width and Aspect Ratio are presented in Fig.16 to Fig.13 depict the complete profile of the two syllables, Fig.19 where as Fig.12 and Fig.14 is presented with scaled vertical profile of the linear segment after applying the IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 25 www.IJCSI.org 4. Results Font Size 12 14 16 19 The proposed algorithm is evaluated on 1,11,582 syllables of Anupama, Gowthami, and Priyanka font. Segmentation Font Type Segmentation efficiency is carried out on font sizes of 12,14,16 and 19. Syllable segmentation efficiencies of aspect ratio, syllable width Anupama 92.98 100.00 99.96 100.00 and Split Profile Algorithm for Anupama font is presented in figures 15 to figures 18. SPA outperform with 100% Gowthami 88.95 99.77 99.26 99.40 segmentation efficiency on the sample set of size 14, 16 and 19. The syllable width based approach is observed Priyanka 76.68 97.55 99.67 99.96 with average segmentation efficiency of 98%. The aspect ratio based approach is observed with segmentation efficiency ranging from 97.93% to 98.04%. For font size 12, SPA is observed with maximum segmentation 5. Conclusions efficiency of 92.98% against 84.15% and 76.12% with syllable width and aspect ratio respectively. However, Topology and geometry is observed to be one of the when evaluated on samples of font sizes 12,14,16 and 19, important information of any script. Extensive study of the the average segmentation efficiency of SPA is observed as statistical properties with regard to topology is crucial 92.98%, 100%, 99.96% and 100% where as syllable width while improving segmentation accuracy. In this paper an approach is observed as 84.15%, 98.65%, 98.77% and attempt is made towards this direction on popular cursive 98.98% and aspect ratio is found to be 76.12%, 97.93%, script Telugu. Profile function is considered for separating 97.63% and 98.04% respectively. Comparison of the linear region over non linear portions in the script line segmentation efficiencies for different fonts and sizes as well as touching syllables. A general approach presented in Table 3, 4 and 5 (connected component approach) on these scripts is compared with the proposed Split Profile Algorithm. The Table 3: Aspect Ratio highest performance of average segmentation efficiency with SPA is observed as 99.98%, 99.47% and 99.05% on Font Size 12 14 16 19 ANUPAMA, GOWTHAMI and PRIYANKA fonts respectively. Experimental evaluation of the proposed Font Type Segmentation efficiency algorithm on small font sizes is in progress. Extension of the proposed algorithm at the level of segmentation and Anupama 76.12 97.93 97.63 98.04 classification with apreori knowledge is in progress. Gowthami 73.75 95.00 92.95 95.42 References [1] Richard G.Casey and Eric Lecolinet, “A survey of methods and strategies in character segmentation” IEEE Transctions Priyanka 50.44 85.13 97.72 98.98 on Pattern Analysis and machine Intelligence, vol. 18, No. 7, pp. 690–706, July 1996. [2] K. Ohta, I. Kaneko, Y. Itamoto, and Y. Nishijima, Table 4: Syllable Width “Character Segmentation of Address Reading/Letter Sorting Machine” for the Ministry of Posts and Font Size 12 14 16 19 Telecommunications of Japan, NEC Research and Development, vol. 34, no. 2, pp. 248-256, Apr. 1993 [3] Y. Lu, "On the Segmentation of Touching Characters," lnt'l Font Type Segmentation efficiency Conf. Document Analysis and Recognition, Tsukuba, Japan, pp. 440-443, Oct. 1993. Anupama 84.15 98.65 98.77 98.98 [4] M. Cesar and R. Shinghal, ”Algorithm for Segmenting Handwritten Postal Codes,” Int’l J. Man Machine Studies, Gowthami 76.89 97.01 96.68 97.14 vol. 33, no. 1, pp. 63-80, July 1990. [5] G. Seni and E. Cohen, "External Word Segmentation of Off- Line Handwritten Text Lines," Pattern Recognition, Priyanka 62.21 91.41 98.61 99.52 vol. 27, no. 1, pp. 41-52, Jan. 1994. [6] K.W. Gan, K.T. Lua, “A new approach to stroke and feature point extraction in Chinese character recognition”. Pattern Recognition Letters, Vol. 12 , no. 6, pp 381-386 , June 1991 Table 5: Split Profile Algorithm IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 26 www.IJCSI.org [7] B. B. Chaudhuri, U. Pal, “A complete printed Bangla OCR M.S. degree in Electronics & Control Engineering from Birla system” Pattern Recognition, vol.31, No. 5, pp. 531- 549, Institute of Technology and Science, Pilani, India in 1999 and March 1998. M.Tech. degree in Electronics and Communication Engineering with specialization in Digital Electronics and Communication [8] Veena Bansal, R. M. K. Sinha, “Integrating knowledge Systems from Jawaharlal Nehru Technological University College sources in Devanagari text recognition system”, IEEE of Engineering (Autonomous), Anantapur, India in 2004. From Transactions on Systems, Man, and Cybernetics, Part A : 1992 to 2003 he was worked as faculty member in the Department Systems and Human, vol. 30, no. 4, pp 500-505, July 2000. of Electronics and Communication Engineering at different [9] M. K. Jindal, G. S. Lehal, R. K. Sharma, “A Study of educational institutions and from 2003 he is working as Assistant Touching Characters in degraded Gurmukhi Script”, World Professor in the Department of Electronics and Communication Engineering at R.V.R & J.C. College of Engineering, Guntur, India. Academy of Science, Engineering and Technology, vol.4,pp Currently he is working in the area of Image Processing, Natural 121-124, 2005 Language Processing, Pattern Recognition and pursuing his Ph.D. [10] U. Pal and Sagarika Datta, “Segmentation of Bangla in Jawaharlal Nehru Technological University Hyderabad, India. Unconstrained Handwritten Text”, Proceedings of the He is a Life member of ISTE, IETE, CSI and IACSIT. Seventh International Conference on Document Analysis and Recognition (ICDAR 2003),August 2003. N.Venkata Rao received his B.E degree in Electronics and [11] Liana M. Lorigo, Venu Govindaraju, “Offline Arabic Communication Engineering from Bangalore University, India in Handwriting Recognition: A Survey” IEEE Transactions on 1985 and M.Tech. degree in Electronics Pattern Analysis and Machine Intelligence, vol. 28, no. 5, and Communication Engineering with specialization in Instrumentation and Control pp. 712-724, May 2006 Systems from Jawaharlal Nehru [12] Pratap Reddy L, Satyaprasad L, ASCS Sastry, “Middle Technological University, Kakinada, India in Zone Component Extraction and Recognition of Telugu . He has 22 years of teaching experience as Document Image”, Ninth International Conference on Assistant Professor, Associate Professor, Document Analysis and Recognition,(ICDAR 2007), Vol 2, Professor and he is currently working as pp 584 – 588, September 2007. Professor in the Department of Electronics [13] Pratap Reddy, L. Sastry, A.S.C. Rao, A.V.S. Venkat Rao, and Communication Engineering, Sri Vasavi Engineering College, Tadepalligudem, India. He has published 7 N., “Canonical syllable segmentation of Telugu document research papers in various National, Inter National conferences. images”, TENCON 2008 - IEEE Region 10 Conference , pp Currently he is working in the area of Natural Language 1-5, Nov-2008. Processing, Image Processing, Pattern Recognition and pursuing [14] M. K. Jindal, R. K. Sharma, G. S. Lehal “Segmentation of his Ph.D. He is a Life member of ISTE and IETE. touching characters in upper zone in printed Gurmukhi script”, ACM Annual Bangalore Compute Conference, B.Raveendra Babu received his M.S Article No.: 9, 2009 . degree in Software Systems from Birla [15] L. Pratap Reddy, "A New Scheme for Information Institute of Technology and Science, Pilani, IN 1997, M.Tech degree in Computer Interchange in Telugu through Computer Networks", Ph.D. Science and Engineering from Anna thesis, Department Electronics and Communication, University, Chennai IN 2000, Ph.D degree JNTUniversity, Hyderabad, INDIA, May 2001. from S.V.University, India in 1992. He has 26 years of teaching experience as L.Pratap Reddy received his B.E degree in Assistant Professor, Associate Professor, Electronics and Communication Engineering Professor and he is currently heading the from Andhra University, India in 1985, Department of Computer Science and Engineering at RVR & JC M.Tech. degree in Electronic Instrumentation College of Engineering, Guntur. India. He is presently Chairman, from Regional Engineering College, Board of studies for Computer Science and Engineering, Acharya Warangal, India in 1988 and Ph.D. degree Nagarjuna University, India. He has published more than 20 from Jawaharlal Nehru Technological research publications in various National, Inter National University, Hyderabad, India in 2001. From conferences, proceedings and Journals. His research areas of 1988 to 1990 he was lecturer in Department of interest include VLDB, Image Processing, Pattern analysis and Electronics and Communication Engineering at Bangalore Institute Wavelets. He is a life member for ISTE and CSI, member for ACM of Technology, Bangalore, India, from 1991 to 2005 he was faculty and IEEE Computer society. member at JNTU College of Engineering, Kakinada, India. Since 2006 he is with Department of Electronics and Communication Engineering and presently he is Professor and Head of the department at JNTUH College of Engineering, Hyderabad, India. His current activity in research and development includes, apart from telecommunication engineering subjects, Image Processing, Pattern Recognition and Linguistic processing of Telugu language. He published more than 50 research publications in various National, Inter National conferences and Journals. He is active member in professional bodies like ISTE, IE, IETE, and CSI. T.Ranga Babu received his B.E. degree in Electronics and Communication Engineering from University of Madras, India in 1992, IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 27 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Information Security and Sender’s Rights Protection through Embedded Public Key Signature Vineeta Khemchandani1, Prof G.N.Purohit2 1 Department of Computer Applications, JSS Academy of Technical Education NOIDA, Uttar Pradesh, 201301, India 2 AIM & ACT, Banasthali University P.O, Banasthali Vidyapith, Rajasthan, 304022, India Abstract think of new security requirements like Information security is not just to provide an protecting the rights of originator against authenticity and integrity to the data, but there is also a tampering and illegal distribution of the need to seek identity, rights of use and origin of information by the intended recipient, as an ill information, which may require some degree of intentioned authorized recipient can modify and process re-engineering. Rarely security technologies like digital signatures can be simply “plugged in” redistribute the decrypted information. without streamlining the process. In this paper we address the problem of information security and It is well known that cryptography deals with protecting the rights of originator of the structured unauthorized access but there are functional document from ill-intentioned recipient who can limitations like requirement of global clock modify the received decrypted information. At sender synchronization, handshaking and costly tamper end, a public key signature is generated using SHA-1 proof hardware. Digital watermarking is a or SHA-2. Signature is embedded into raster image of the document using non-invertible robust public key technique based on digital signal processing watermarking technique based on orthogonal signals which inserts extra signal to digital contents for concepts. The document is then encrypted with public discouraging illicit modification and distribution key of the receiver using RSA algorithm to achieve of information and to authenticate watermarked confidentiality and authorization. The proposed contents. But, digital watermarking has the scheme uses correlation analysis to detect embedded following limitations: - signature to authenticate message. This scheme also uses Gauss-Jordan method to derive the signature from the watermarked image to verify ownership. The (a) No transmission security – due to lack of study is corroborated with result and application of the public key algorithms. proposed technique to prevent forgery and alteration (b)Text information - Due to binary block format in e-cheque document. of the text, embedding new bits in the text may Keywords: Digital Signature, watermarking, introduce irregularities that are visually Information Security, Rights Protection, cheque noticeable. alteration, signature forgery. This paper presents a technique, which contains 1 Introduction strengths of digital signature and digital watermarking both so as to provide a secure Over the past few years there has been transmission of messages. Thus the rights of tremendous growth in computer networks sender on digital content are protected. Figure 1 especially in the field of World Wide Web. This illustrates an approach that uses raster phenomenon coupled with the exponential representation of the document in which digital increase of computer performance, has facilitated signature is embedded as watermark. Public key on-line business operations like shopping, signature protects the document from any trading, cheque truncation, bill presentment. Due intruder, while embedding it as resilient, non- to massive use of personal computers, network invertible and robust watermark prevents non- and the Internet, new features of security are in trusted receiver to modify the contents of the need. In addition to confidentiality, document. authentication, integrity and control, one must IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 28 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Figure 1 Public Key Cryptosystem with embedded digital signature The rest of the paper is organized as follows. 2.1 Digital Signatures Section 2 presents digital signatures and watermarking, section 3 describes digital Digital signatures have been accepted in several signature generation and embedding procedures, national and international corporations, banks section 4 contains detection of watermark to and government agencies. The fundamental prove authenticity, and section 5 contains process involved in digital signature is a hash verification of watermark to prove ownership, function. A number of hash functions are experimental results are then discussed in section proposed in the literature. The MD5 message 6 for the purpose of performance evaluation. digest algorithm,[2] was developed by Ren Conclusion will be given in section 7. Rivest at MIT. MD5 generates a 128 bits message digest out of a variable length message. 2 Digital Signatures and Another hash algorithm SHA (Secure Hash Watermarking Algorithm) was developed by National Institute of Standards and Technology (NIST) and published as a federal information processing The ownership protection, authentication and standard [3] in 1993.Revised version of SHA is integrity of structured document is necessary and implemented in C language and referred as SHA- important. Encryption and digital signature 1 [4]. It generates 160 bits message digest. SHA- techniques protect against eavesdroppers, for 1 has achieved level of Standard because it sure, but the main attacks are likely to be from generates 32 bits longer message digest than validly connected end-users who go on to MD5, using a brute force technique for a given redistribute the received data more than they are digest the difficulty in achieving message is of entitled to. Digital signature uses “Public-Key the order of 2160 operations in comparison to 2128 Cryptography” which employs an algorithm operations in MD5.In the draft FIPS 180-2 NIST using two different but mathematically related published SHA-2 as a new version of secure “keys” one for creating signature, and, another hash algorithm. SHA-2 offers, SHA-1, SHA- for verifying signature. Compare this to 256, SHA-384 and SHA-512. In other words information hiding the cryptographic signature is SHA-2 may have outputs160, 256, 384, and 512 embedded into the information itself. bits of message digest. However, SHA-2 Watermarking [1] is a security technique in algorithm uses fixed and predefined parameters context of protecting content of information from that may be vulnerable to attack. authorized user. It is as old as paper production is and protects rights of author/originator. This technique is basically used to identify any Digital signature can save the message from third processing and modification in the contents. parties [5] but once an encrypted message is at receiver end, an ill-intentioned receiver can IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 29 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 easily decrypt, modify and distribute the spectrum signal are modulated with 128 bits of message for commercial benefits. This means the the owner’s secret key. Adding modulated signal sensitive information in these messages cannot back to the image generates the watermark be protected from modification and redistribution signal. Inverting spectrum signal, which is then from the authorized receiver using encryption, added to the image, generates watermark signal. access restriction and hiding information behind Drawbacks of this scheme are (1) it requires firewalls. original image to detect the watermark and (2) Every time new binary key is needed to protect 2.2 Digital Watermarking new image. A digital watermark is a distinguished piece of Natrajan presented a paper for watermarking of information that is adhered to the data that it is digital images to detect or verify ownership [13]. intended to protect. Several embedding In this method most common RSA & DSS public techniques [1, 6-8] have been specially key signature generation algorithms are used to developed for use with text but most of these generate public and private keys of user. This techniques either change word or line spacing or method involves computing message digest make change on the character boundary which using MD5 of image I of M rows and N require original document to detect watermark to columns. Message digest is encrypted with authenticate sender. These techniques cannot be private key to generate digital signature. Low simply used to embed digital signature due to order bits of DS are modulated to as watermark involvement of integrity issues with digital and inserted back into the image. signature applications. We can summaries that, in order to protect Tao Chen, et al suggests a combined digital document integrity and rights of owner on the signature and digital watermarking scheme [9] document the crypto signature should be content for image authentication and content protection. based and public in order to avoid the large In this scheme content dependent random k bits number of secret keys. Secondly such a scheme are extracted from N blocks of image to obtained should not require original document to detect K X N bits signature, which is embedded back to and verify the ownership and should be the image using secret key. Due to requirement computationally inexpensive. of large number of keys this method cannot be used in applications requiring transmission of The goal of this work is to design a cipher model data. that contains strengths of digital signature and digital watermarking both to provide secure structured document transmission and to detect Ding Huang presents a text watermarking and verify ownership to prevent alteration and technique [10] that expands and shrinks widths forgery. The approach uses raster representation between words to represent inter word distance, of the document in which digital signature is as sine wave. In this method sine wave is coded embedded as watermark. Public key digital as watermark. This technique cannot be used to signature protects the document from third party send confidential message, as it does not use any while embedding it as watermark prevents non- key. trusted receiver to modify the contents of document. Chang & Chang presented a sender-buyer protocol [11] where digital signature containing sender, buyer and trading information is 3. Embedding Digital Signature embedded in the image as barcode image. This scheme protects the embedded trading message 3.1 Image representation of a message and ensures integrity of image but does not authenticate the sender, as digital signature is not The process starts with calculating size of the based on content of the information. text information and then converting it into its digital image representation. Input text is stored Cor et al [12] proposed secure spread spectrum in string format before conversion. Size of the watermarking scheme. A two-dimensional text is calculated in the form of an invisible spectrum signal is generated. 128 low bits of the drawing in the context of memory device. The IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 30 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 height and width are calculated as shown in figure 2.. Figure 2: Image size Measurement memory are grabbed into a vector of size width * Image height = (Ascent+ Descent+ bearing) * height. No. of lines in text message (1) 3.2 Generation and Embedding of Digital Image width = = Max (x [i]); 0<= i <=no. of signatures lines (2) True color RGB model is used to represent This process starts with calculating a message image as a bit frame of size width*height, where, digest from two-dimensional message signal M each square represents a value of bit as function f of m rows and n columns. One-way hash (x, y). function H operates on input message M of arbitrary length and returns a fixed length hash {f (x, y) = [0,1], | x= 0 to width, y = 0 to eight} value h, i.e. H (M) = h. It has additional  (3) characteristics as follows: A total number of 32 frames for a single image (i) Given M it is easy to compute h, are used [14]. The first 8 frames represent (ii) Given h it is hard to compute M / such that H transparency; the next 24 frames (8 per color) are (M ⁄ ) = h used to represent Red, Green and Blue colors (iii) Given M it is hard to compute another respectively. The binary values (0 or 1) in message M ⁄ such that H (M) = H (M ⁄ ). corresponding bits from each of the 32 bit planes result in a binary number to represent pixel’s Several methods are developed to find hash intensity level from 0 to 2 32 –1 (full intensity). function [2-4]. Here SHA-I algorithm is used to generate unique 160 bits. For each bit, in all 32 bit frames, value of function f(x, y) is set to 0 to create a white Then RSA algorithm is used to encrypt fixed background image. length message digest using owner’s private key to generate owner’s public key signature vector {f (x, y) = 0 | x= 0 to width, y = 0 to height} [5]. Since RSA algorithm is based on the fact (4) that there is insufficient way to factorize very large number, deducing the RSA key, therefore, Value of function f (x, y) is manipulated at a requires very high computer processing time. specific location in all the bit frames to draw text RSA algorithm has also become de facto pattern on the background image. Intensity of the standard for industrial strength and built into image is set in all 32-bit frames to get a specific many of the software products like Netscape pixel value [15-17]. Values of pixels stored in Navigator and Internet Explorer. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 31 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Other blocks of m rows can be selected pseudo Next, the bits of digital signature are modulated randomly to embed additional watermarks using and transformed to compute watermark signal. same Xs signal. All Xs and corresponding Length of the watermark signal may be same as reference vectors are stored for detection that of digital signature or it may be based on purpose. first, middle or last bits of the digital signature as long as they are consistent. This selection is 3.3 Encrypting watermark signal based on the criteria that too small Watermark signal is vulnerable to attack and too large RSA algorithm [5] is used to further encrypt watermark signal takes large computer power. watermarked signal M/ using public key (d, n) of the receiver to achieve data integrity and Embedding watermark signal Xs into message M confidentiality over network involves selecting a random block of m non- overlapping continuous rows and averaging M = {f ⁄ (x, y) | x = 0 to width, y = 0 to height} these m rows to find average row vector R C = Md mod n (8) referred to as reference vector. Original watermark signal Xs is orthogonalized with respect to vector R to make inserted signal independent from the reference signal and 4. Detection of Watermark to prove eliminate cross talk [18]. Thus, the vector Ws/ authenticity constructed out of W entries by modulating digital signature is [12, 19, 20] The message received is decrypted using private key (e, n) of the receiver to assure for the sender that only authorized receiver can access message Ws ⁄ = Xs – (Xs. R) R (5) and data in the message has not been modified during transmission. To assure the receiver that A gain factor is calculated from Ws / across all m message has come from the authentic sender. rows to ensure that strength of the watermark The watermark inserted in the message is varies smoothly. detected. Ii = c cos (2 π i / m) Ws ⁄ (6) M = Ce mod n (9) Value of c is adjusted to maintain quality metric A detection criterion is established using PSNR to minimum 30 DB, to avoid white visible correlation analysis [19, 20]. Watermark is marks on message signal. This small scaled detected using the reference vector R and the version of the Ws⁄ is added back to m rows of the watermark vector Xs sent with message itself. Xs original signal to generate watermarked signal M is orthogonalized with respect to R to obtain Ws. / , where value of the bit function f / (x, y) is Watermarked message is scanned from starting given as. in blocks of m rows. An average vector is calculated from each block and orthogonalized with respect to reference vector R to find im im expected watermark vector EWs. EWs is correlated with the watermark vector Ws to test  f ( xr , y)   f ( xr, y)  I ( xr  i, y) 7(a) r i r i relative closeness. i 1 i 1  f ( x r , y )   f ( xr, y ) 7(b) EWs.Ws r 0 r 0 cos   (10) h 1 h 1 | EWs || Ws |  f ( xr , y )   f ( xr , y ) 7(c) r i  m 1 r i  m 1 If correlation coefficient is above a threshold w h e re 0  ra n d o m (i)  w- m value (between 0.5 & 1) then received document IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 32 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 contains the watermark and assumed to have sent by an authentic sender. Hundreds of random watermarks are synthesized with the same spectral properties as Xs. Correlation of each of these watermarks is computed with watermarked image. If later and former correlations are far apart it is likely that image contains watermark. 5 Verification to prove ownership (12) Figure 3 presents the procedure to protect rights of sender by deriving watermark from the Gauss Jordan method is applied to equation (12) watermarked image of the signal. Signature to find components of vector Xs., where mr is derivation will prove ownership of the sender if length of vector R. Digital signature S of sender message is redistributed. At the same time it will is constructed from Xs after removing all restrict authorized receiver to illegally modify modulations and transformations. If, S and Xs the message because in case of modification are same, ownership of the sender is proved. extracted signature will not match with the original signature of the sender. 6 Implementation and Results In this section we present the simulation results Claimant can prove the ownership by presenting by implementing orthogonal signals based original image and the position where watermark public-key watermarking algorithm.. We used a was inserted. Gain factor is constructed by 32-bit RGB model to represent the cheque image subtracting original image from watermarked using JAVA advanced imaging classes. We used image and orthogonal watermark Ws / is also SHA-1 algorithm to find message digest and constructed. RSA algorithm to encrypt message digest. We orthogonalized signature with respect to average vector found from selected block and embedded a scaled version of orthogonalized signature back to the selected block. PSNR was set to minimum 30 DB to avoid white noise. Overall image was encrypted with public key of the recipient to achieve confidentiality and integrity. Signature was detected using correlation analysis. Figure 4 shows 32-bit raster image of the document. Figure 5 shows watermarked image with PSNR 76DB and figure 6 shows the decrypted image. This image is used to detect the watermark using Figure 3: Detection & verification of signature correlation. Vector triple product is applied to find value of The performance of the proposed algorithm is Xs from equation (5). shown in figure 7. Correlation factor is found corresponding to the true signature derived from the original document and corresponding to the (Xs R) R = (Xs . R ) R – (R. R ) Xs 100 randomly selected signatures. The (11) correlation factor corresponding to true signature is between 0.9 and correlation factor corresponding to false signatures is negative or below 0.6. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 33 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Figure 4: Original Cheque Image Figure 5: Image of with embedded signature (PSNR -76.98141537143279) Figure6 6: Received & Decrypted image Figure 7: Correlation spread of watermarked image. Central spike corresponds to true signature and other points to randomly generated candidate signature IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 34 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 7 Conclusions [10] Ding Huang, “ Inter word distance changes represented by sine waves for watermarking text images”, IEEE transaction Circuits System Video tech Most of the trading, banking and investment (12), 1237-1245, 2001. applications are based on exchanging structured [11] Ji-Hong Chang and Long-Wen Chang, “ A New documents over global network. For technical Image copyright Protection Algorithm Using Digital excellence and business values of these Signature of Trading Message and Bar Code applications, security of information and Watermark”, Image and Vision Computing 03 New sender’s rights on information plays an essential Zeeland Proceedings, 26-28, November, 2003. role in overall transmission system. [12] Con et al ,”Secure Spread Spectrum Cryptography alone can be an effective solution Watermarking for Multimedia”, pp 1-33, Copyright, to all these problems but in most of instances in NEC Research Institute, Tech Report95-10. the form of costly and specialized hardware to [13] Balas Natrajan, “ Robust Public-Key create tamper proof devices. In this paper we Watermarking of Digital Images”, Computer Systems have presented a software-based approach, Laboratory, HPL, 97-118, October 1997. which combines digital signature technology [14] D.F.Rogers and J.A.Adams , “ Mathematical with robust watermarking technique to achieve Elements for Computer graphics”, TATA-McGraw- authenticity, confidentiality, integrity and Hill, Edition,2002. restricting alteration and forgery in information. [15] Daniel Sage & Michael Unser , “ Teaching Image The proposed technique is tested to prevent Processing programming in JAVA”, IEEE Signal Processing Magazine, November 2003, pp 40-52. forgery of signature and alteration of information in cheques. [16] D. Sage, M User, “ Easy JAVA Programming for Teaching Image Processing”, Proc. Of the 2001 IEEE International Conference on Image Processing (ICIP01) , Thessalonica, Greece, 2001, Vol. 3, pp 298- References 301. [1] Frank Hartung and Martin Kutter , “ Multimedia [17] D. Roman, M. Fischer and J. Cubillo , “Digital Watermarking techniques”, Proceeding of the Vol. image Processing-An Object-Oriented approach,” 87, No. 7, July, 1999. IEEE trans. Educ., Vol. 4, pp. 331-333,1998. [2] Rivest. R , “The MD4 Message Digest Algorithm [18] William K. Pratt, ”Digital Image Processing, 1320” MIT and RSA Data Security Inc, April 1992. (Fourth Edition), ” pages 147 - 164. Copyright © 2007 John Wiley & Sons, Inc. [3] National Institute of Standards and Technology, Fips 180, Federal Information Processing Standards, [19] B.P.Lathi, “Modern Digital and Analog Secure Hash Standard (SHS), April 1993. communication system,” Oxford University Press, third edition, 1998, pp 406-416. [4] D.Eastlake .3rd, P.Jones.US , “ Secure Hash Algorithm-1(SHA-1), September,2001. [20] Rafael.C Gonzalez, Richard. E.Woods , “ Digital image processing “Person education, seventh [5] W. Stalling , “ Cryptography and network edition(2001), pp111. Security Principles and Practice, 4th Edition”, Prentice Hall. [6] J.T. Brassil, S. Low and N.F. Maxemchak , “ Electronic Marking and Identification Techniques to Discourage Document copying”, IEEE journal on Selected Areas of Communication,,Vol.13, No. 8,October 1995. [7] J.T. Brassil, S.Low and N.F.maxemchak , “ Cpoyright Protection for the Electronic Distribution of text Documents”, proceeding of the IEEE [8] N.F. maxemchak and S.Low, “ Marking Text Documents”, Proceeding of the IEEE International Conference on Image Processing, Washington. DC, October 26-29, 1997, pp 13-16. [9] Tao Chen, Jingchun Wang and Yonglei Zhou, “ Combined Digital Signature and Digital Watermarking scheme for Image Authentication”, in proc IEEE, international Conferences on Info-Tech& Info-Net (ICII2001), Vol 5, pp78-82, 2001. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 35 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Non linear Image segmentation using fuzzy c means clustering method with thresholding for underwater images Dr.G.Padmavathi, Mr.M.Muthukumar and Mr. Suresh Kumar Thakur. Abstract The theory of fuzzy sets have immediately found The quality of underwater images is directly affected by water its potential application in the fields of pattern recognition medium, atmosphere, pressure and temperature. This emphasizes and image processing. The fuzzy c-means algorithm the necessity of image segmentation, which divides an image into generalizes a hard clustering algorithm called the c-means parts that have strong correlations with objects to reflect the actual information collected from the real world. Image algorithm, which was introduced in the ISODATA segmentation is the most practical approach among virtually all clustering method [6]. The (hard) c-means algorithm aims automated image recognition systems. Clustering of numerical to identify compact, well-separated cluster. data forms the basis of many classification and system modelling algorithms. The purpose of clustering is to identify natural The paper is organized as follows: Section II groupings of data from a large data set to produce a concise discusses the need for image segmentation. Section III representation of a system's behaviour. In this paper we propose presents the proposed fuzzy c means clustering algorithm fuzzy c means clustering method with thresholding for underwater for segmenting underwater images using thresholding. The image segmentation. This paper focuses on comparison of fuzzy c simulation results with different non–linear parameter means clustering algorithms with proposed method for underwater images. To evaluate the nonlinear image region evaluation are presented in section IV. Finally, conclusions segmentation, quantitative statistical measures have been used, are given in section V. such as the gray level energy, discrete entropy, relative entropy, mutual information and information redundancy. The assessment II NEED FOR UNDERWATER IMAGE measures will further quantify the impact from image SEGMENTATION segmentation. The objective assessment approach has the potential to solve other image processing issues.The proposed method gives desirable results on the basis of energy, entropy, Image segmentation is a major step for automated mutual information, redundancy, percentage of simplification and object recognition systems. In many cases, image computer efficiency for underwater images. processing is affected by illumination conditions, random noise and environmental disturbances due to atmospheric Keywords underwater images, fuzzy c means clustering, energy, pressure or temperature fluctuations. The quality of entropy and mutual information underwater images is directly affected by water medium, atmosphere medium, pressure and temperature. This I INTRODUCTION emphasizes the necessity of image segmentation, which Image segmentation is a major step for automated divides an image into parts that have strong correlations object recognition systems. In many cases, image with objects to reflect the actual information collected from processing is affected by illumination conditions, random the real world. noise and environmental disturbances due to atmospheric Due to unstableness in underwater surroundings, pressure or temperature fluctuation. Region segmentation is object recognition in underwater is no means an easy task. a crucial step towards automatic segmentation of images. Light changing or current flow of underwater surroundings Under some severe conditions of improper illumination and often occur rapidly, so the features (shape or color etc) of unexpected disturbances, the blurring images make it more object may vary in short time and the segmentation process difficult for target recognition, which results in the may not give proper results [2]. Therefore subsequent necessity of segmentation. The underwater images have object recognition results are not reliable. The next session quality degradation due to water dispersion and explains the algorithm taken for implementation. atmospheric fluctuations. Segmentation is thus needed to clarify feature ambiguity against stochastic disturbances. III PROPOSED FUZZY C MEANS CLUSTERING Region segmentation splits images into regions based on METHOD WITH THRESOLDING similarity measures, such as pixel intensities, locations and The fuzzy c means clustering method with thresholding is textures or combinations. It categorizes an image into the combination of fuzzy algorithm, c means clustering and separate parts, which correlates with objects involved. thresholding algorithm. Fuzzy clustering IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 36 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 The goal of a clustering analysis is to divide a given set of data or objects into a cluster, which represents subsets or a If none of the cluster centers ( c =1, 2,…, k) changes in i group [6]. The partition should have two properties: step 4 stop; otherwise go to step 3.  Homogeneity inside clusters: the data, which belongs to one cluster, should be as similar as C-means algorithm possible. The criterion function used for the clustering process is: n 2 x k vi  Heterogeneity between the clusters: the data, which belongs to different clusters, should be as J ( v )    k x  ci , k 1 different as possible. The membership functions do not reflect the actual data distribution in the input and the output spaces. They where v i is the sample mean or the center of samples of cluster i, and v={v1,v2,…,vc}. may not be suitable for fuzzy pattern recognition. To build membership functions from the data available, a clustering In the hard clustering process, each data sample is technique may be used to partition the data, and then assigned to only one cluster and all clusters are regarded as produce membership functions from the resulting disjoint collection of the data set. In practice there are many clustering. cases, in which the clusters are not completely disjoint and the data could be classified as belonging to one cluster “Clustering” is a process to obtain a partition P of a set almost as well to another. Therefore, the separation of the E of N objects Xi (i=1, 2,…, N), using the resemblance or clusters becomes a fuzzy notion, and representation of the disemblance measure, such as a distance measure d. A data can be more accurately handled by fuzzy clustering partition P is a set of disjoint subsets of E and the element methods. It is necessary to describe the data in terms of Ps of P is called cluster and the centers of the clusters are fuzzy clusters. The criterion function used for fuzzy C- called centroids or prototypes. Many techniques have been means clustering is developed for clustering data. In this paper c-means c n 2 J (v )    u x k v i m clustering is used. It’s a simple unsupervised learning , ik method which can be used for data grouping or i 1 k 1 classification when the number of the clusters is known. It consists of the following steps: where: Step 1: Choose the number of clusters - K x ,...... x  ‘n’ data sample vectors; 1 n Step 2: Set initial centers of clusters c1, c2,…, ck; v ,...... v  ‘c’ denotes cluster centers (centroids); 1 c Step 3: T u u cxm matrix, where u is the i-th membership ik ik Classify each vector x1  [ x11 , x12 ,.... xln] into the value of the k-th input sample xk, and the membership values satisfy the following closest center c i by conditions: Euclidean distance measure: x c i i  min x ci i Step 4: Recompute the estimates for the cluster centers c Let i T c = [c , c ,.... c ] i i1 i2 ln , c be computed by: im x  cluster (i x lim ) c  im li N i The Fuzzy Logic Toolbox command line function, fcm, starts with an initial guess for the cluster centers, where N i is the number of vectors in the i-th cluster. which are intended to mark the mean location of each Step 5: cluster. The initial guess for these cluster centers is most likely incorrect. Next, fcm assigns every data point a membership grade for each cluster. By iteratively updating IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 37 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 the cluster centers and the membership grades for each data ii) Second, segmentation algorithm is point, fcm iteratively moves the cluster centers to the right applied for underwater image. location within a data set. iii) Third, the non linear objective assessment is applied for fuzzy c means Thresholding algorithm, for evaluation of underwater This iteration is based on minimizing an objective images. function that represents the distance from any given data point to a cluster center weighted by that data point's The reconstruction of an image has the dimensions membership grade. Here fuzzy c means clustering [3] is of 256 pixel intensity. The images in this contain a wide used based on thresholding. It works better than ostu variety of subject matters and textures. Most of the images method [4]. In normal fuzzy c means clustering the used are ship wreck, moor chain and mine in sonar images. segmented part cannot be seen clearly. For that reasons, The non linear assessment applied must be less value for an thresholding is applied to extract the segmented image part. better image segmentation. Hence, the annexure I gives the clarity of underwater images after applying the thresholding method, this have To estimate the quality of the reconstructed proposed in this paper. Aneexure I gives the original images, following non linear objective assessment underwater images and image after applying fuzzy c means parameters are used. clustering and fuzz c means clustering method with The different non linear objective assessment parameters threshold. used for evaluation are , i.) Energy ii.) Relative Entropy (RT) iii.) Discrete Entropy (DE) iv.) Mutual Information (MI) v.) Normalized Mutual Information (NMI) vi.) Redundancy(RD) i.) Energy The gray level energy indicates how the gray levels are distributed. It is formulated as, E ( x)  i 1 p ( x) x Fig 1 original underwater Fig 2 After applying FCM Titanic image where E(x) represents the gray level energy with 256 bins and p(i) refers to the probability distribution functions, which contains the histogram counts. The energy reaches its maximum value of 1 when an image has a constant gray level [2]. ii.) Relative Entropy Suppose that two discrete probability distributions of the images have the probability functions of p and q, the rela.tive entropy of p with respect to q is then defined as the Fig 3 After Applying FCMT summation of all possible states of the system, which is formulated as, From the figure it can be observe that the p (i ) d  i 1 p (i) log 2 k difference between the normal fuzzy c means clustering and fuzzy c means threshold for underwater images. The q (i ) fuzzy c means threshold method gives better image when compare to normal fuzzy c means clustering. iii.) Discrete Entropy (DE) The discrete entropy is the measure of image IV. EXPERIMENTAL SETUP AND EVALUATION information content, which is interpreted as the average To test the accuracy of the segmentation algorithms, three uncertainty of information source. It is calculated as the steps are followed. summation of the products of the probability of outcome multiplied by the log of the inverse of the outcome i) First, an underwater image is taken as probability, taking into considerations of all possible input. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 38 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 outcomes {1, 2, …, n} in the event {x1, x2, …, xn}, where I ( X ;Y ) n is the gray level; p(i) is the probability distribution, RD  considering all histogram counts. It is formulated as H ( X )  H (Y ) k 1 k where H(X) and H(Y) are entropies of two images and I(X; H ( x)   p (i ) log 2   p (i ) log 2 p (i ) Y) is the mutual information. i 1 p (i ) i 1 For image processing, the discrete entropy is a measure Table 1 Performance evaluation using fuzzy c means how many bits needed for coding the image data, which is clustering method a statistical measure of randomness. The maximal entropy occurs when all potential outcomes are equal. When the outcome is certainty, the minimal entropy occurs which is equal to zero. The discrete entropy represents average amount of information conveyed from each individual image. iv.) Mutual Information (MI) The notion of the mutual information can be applied as another objective metric. The mutual information acts as a symmetric function, which is formulated as, Pxy ( X , Y ) I ( X , Y )   PXY ( X , Y ) log 2 XY Px ( X ) Py (Y ) Pxy ( X , Y )   Px ( X ) log 2 P ( X )   Pxy ( X , Y ) log 2 x x. y Px ( X ) Py Y )  H (X ,)  H (X |Y) where I(X; Y) represents the mutual information; H(X) and H(X|Y) are entropy and conditional entropy values. It is interpreted as the information that Y can tell about X is equal to the reduction in uncertainty of X due to the existence of Y. At the same time, it also shows the relationship of the joint and product distributions. The results are shown in Table v.) Normalized Mutual Information (NMI) Like that more number of underwater images are taken The normalized mutual information is a well for experimentation and the results are give desirable for defined measure covering contents from both discrete fuzzy c means clustering method with thresholding. entropies and mutual information. It is formulated as I ( X ;Y ) From table, in image segmentation, the less value NMI  of the non linear objective assessment like energy, relative H ( X ), H (Y ) entropy, discrete entropy, mutual information, normalized where I(X, Y) is the mutual information; H(X) and H(Y)are mutual information, redundancy and computer efficiency the discrete entropies gives the Fuzzy C Means threshold (FCM threshold) Table 1 shows the performance evaluation of original method is better for underwater images when compare to image and segmented image using non linear objective Fuzzy C Means (FCM) clustering. When compare to assessments like energy, entropy and mutual information. original image fuzzy method gives simplified value. The percentage of simulation is also calculated. Its varied from vi.) Redundancy (RD) 52% to 95% and the computer efficiency is also calculated Another symmetric information measure can be using time in seconds. When compare to all performance used to indicate redundancy in image segmentation. It evaluation it can be say that fuzzy c means threshold reaches the minima of zero when all variables are method give most suitable results when compare to fuzz c independent. It is formulated as means method. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 39 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Dr. Padmavathi Ganapathi is the Professor and V CONCLUSION Head of Department of Computer Science, The quality of underwater images is directly Avinashilingam University for Women, affected by water medium, atmosphere medium, pressure Coimbatore. She has 21 years of teaching and temperature. This emphasizes the necessity of image experience and one year Industrial experience. Her areas of interest include Network security segmentation, which divides an image into parts that have and Cryptography and real time communication. strong correlations with objects to reflect the actual She has more than 80 publications at national and information collected from the real world. Image International level. She is a life member of many segmentation are most practical approaches among professional organizations like CSI, ISTE, AACE, WSEAS, ISCA, and UWA. She has five virtually all automated image recognition systems. funded projects from UGC and DRDO Clustering of numerical data forms the basis of many Mr.M.MuthuKumar. received the diplomo in classification and system modelling algorithms. The ECE.from Arsan Ganesan Polytechnique College purpose of clustering is to identify natural groupings of Sivaksi and B.E (EIE) degrees from KCET virudhunagar in 2004 and 2007 respectively.he is data from a large data set to produce a concise currently working as a Research staff in representation of a system's behaviour. In this paper the Department of Computer Science in proposed fuzzy c means threshold clustering method gives Avinashilingam University for women and has desirable results when compare to FCM method by using two year of research experience. His research interests are image and signal processing. he has non linear assessment like energy, relative entropy, discrete 6 publications at national level and international entropy, mutual information, normalized mutual level.. information, redundancy and computer efficiency when Mr.SK.Thakur is the Joint Director at Directorate compare to fuzzy c means method for underwater images... of Naval Research & Development, DRDO HQ, New DelhiDeputy Director at Sectt. of Naval Research Board, New Delhi. He has More than REFERENCES 25 years of experience as a Naval Officer with [1]. Wen-Xiong Kang, Qing-Qiang Yang, Run-Peng Liang, "The Indian Navy. Experience in Policy Making & Comparative Research on Image Segmentation Algorithms," First Goal Monitoring, Project Development & International Workshop on Education Technology and Computer Science, Monitoring, Equipment Maintenance & testing, pp.703-707, , vol. 2, 2009. Finance & Budgeting, Liaison with indigenous & [2].Zhengmao ye, “objective assessment of Nonlinear Segmentation foreign firms, Crisis & planned Management, Approaches to Gray Level Underwater Images”, ICGST-GVIP Journal, pp. Personnel & Administration; and 39-46, No.2, Vol. 9, April 2009. Instructor/Teacher as Directing Staff; and [3] Y. Ye, Z. Ye, J. Luo, P. Bhattacharya, H. Majlesein, R. Smith, "On Research & Development aspects.Experience of Linear and Nonlinear Processing of Underwater, Ground, Aerial and working with Research Personnel/Senior Satellite Images", IEEE International Conference on Systems, Man and professors of IITs/IISc and Scientists from Cybernetics, pp.3364-8, Oct.10-12, 2005. various R&D Institutions.and member of broad [4] R. Gonzalez, R. Woods, “Digital Image Processing,” 2nd Edition, casting engineer society, new Delhi, member of Prentice-Hall, 2002. IEEE and stragetic electronic group. [5] Mr. S. K. Korde Mrs. K.C. Jondhale, “Hand Gesture Recognition System Using Standard Fuzzy C-Means Algorithm for Recognizing Hand Gesture with Angle Variations for Unsupervised Users”, IEEE, First International Conference on Emerging Trends in Engineering and Technology, pp. 681-685, Nov 11 2008. [6] Rumiana Krasteva “Bulgarian Hand-Printed Character Recognition Using Fuzzy C-Means Clustering”, Bulgarian Academy of sciences problems of engineering cybernetics and robotics, 53, pp. 112-117, 2002. [7] Weina Wang, Yunjie Zhang, Yi Li and Xiaona Zhang, “The Global Fuzzy C-Means Clustering Algorithm”, Proceedings of the 6th World ` Congress on Intelligent Control and Automation, pp.33604-3607, June 21 - 23, 2006,. [8] A.H.Hadjamthi, M.M.Hmayanpour and S.M.Ahadi, “Robust weighted fuzzy c means clustering”, IEEE International Conference on Fuzzy Systems, pp. 306-311, 2008. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 40 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 ANNEXURE I Underwater image results for fuzzy c means clustering method with thresholding Original underwater images Underwater image after applying FCM Underwater image after applying FCM threshold IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 41 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 A Theoretical Approach to Link Mining for personalization K.Srinivas1, L.Kiran Kumar Reddy2 and Dr.A.Govardhan3 1 Department of Computer Science and Engineering, Geethanjali College of Engineering and Technology Hyderabad, Andhra Pradesh 500007, India 2 Department of Computer Science and Engineering, SLC’S IET Hyderabad, Andhra Pradesh 500028, India 3 Department of Computer Science and Engineering, Jawaharlal Nehru Technological University, Jagtial, Andhra Pradesh 505327, India constructed link, such as a join operation between tables Abstract stored in a database. An emerging challenge for data mining is the problem of mining richly structured datasets, where the objects are linked in some way. Many real-world datasets describe a variety of object types 2. Link Mining linked via multiple types of relations. These links provide additional context that can be helpful for many data mining tasks. Link mining is a newly emerging research area that is at Links among the objects may demonstrate certain patterns, the intersection of the work in link analysis [4; 5], which can be helpful for many data mining tasks and are usually hypertext and web mining [3]. Links have more hard to capture with traditional statistical models. Recently there has been a surge of interest in this area, fuelled largely by generically relationships, among data instances are interest in web and hypertext mining in personalization. ubiquitous. These links often exhibit patterns that can Keywords: Link mining, Clustering, categorizer, Indexer, indicate properties of the data instances such as the Personalization. importance, rank, or category of the object. In some cases, not all links will be observed. Therefore, we may be interested in predicting the existence of links between 1. Introduction instances. In other domains, where the links are evolving over time, our goal may be to predict whether a link will There are different traditional data mining tasks such as exist in the future, given the previously observed links. By association rule mining, market basket analysis and cluster taking links into account, more complex patterns arise as analysis commonly attempt to find patterns in a dataset well. This leads to other challenges focused on characterized by a collection of independent instances of a discovering substructures, such as communities, groups, or single relation. This is consistent with the classical common sub graphs. Traditional data mining algorithms statistical inference problem of trying to identify a model such as association rule mining, market basket analysis, given a random sample from a common underlying and cluster analysis commonly attempt to find patterns in distribution. Data which is storing in data warehouse a dataset characterized by a collection of independent contains heterogeneous data. A key challenge for data instances of a single relation. This is consistent with the mining is tackling the problem of mining richly structured, classical statistical inference problem of trying to identify heterogeneous datasets. These datasets are typically multi- a model given a independent, identically distributed (IID) relational; they may be described by a relational database, sample. One can think of this process as learning a model a semi-structured representations such as XML, or using for the node attributes of a homogeneous graph while relational or first-order logic. However, the key ignoring the links between the nodes. Link mining tasks commonalities are that the domain consists of a variety of are broadly categorized into following tasks. They are object types and objects can be linked in some manner. In this case, the instances in our dataset are linked in some 1. Object-Related Tasks way, either by an explicit link, such as a URL, or by a (a) Link-Based Object Ranking (b) Link-Based Object Classification IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 42 www.IJCSI.org (c) Object Clustering (Group Detection) use of linkage information, such as anchor text and (d) Object Identification (Entity Resolution) neighbouring text around each incoming link, better 2. Link-Related Tasks categorization results can be achieved. (a) Link Prediction User Interface 3. Graph-Related Tasks (a) Sub graph Discovery (b) Graph Classification Results (c) Generative Models for Graphs In personalized web mining, which is considering Observer Query Filter different types of categorical domains. Personalization can be achieved through link mining by dynamically constructing user-profiles [1]. Classifier Regular Query Search 3. Proposed Algorithm to Construct Dynamic user Profiles using Link Mining In this algorithm, thesis is concentrating on the hyperlinks Profile Manager Personalization Filter of the web and different attributes of the link such as time spent on each link, link type, link category etc. Process User Profile Step 1: Get the log file (From server) Step 2: Extract the Links and time spent browsing the links Step 3: Check for the relevance of the document (t is time of viewing the document, th threshold Personal Details time, If t > th the document is relevant) Step 4: Categorize the documents that are found relevant Fig. 1 Architecture for creating dynamic user profiles. Step 5: Increase the score for the categories in Profile In the given architecture (figure 1) there are different In the above algorithm active time and passive time should modules with the following functionality. be considered. If any user is visiting a link then finding Observer deals with the details of obtaining the about how much time he/she is actively reviewing that link information we need to build the user profile. Like, (active time) or just visited that link and if he/she Input Query disconnects or away out of the desk should be considered Links the user is visiting (passive) to calculate the threshold time. Time the user is spending on each link Length of the content of the link Type of the link (PDF, doc, txt, images, audio, 4. Architecture for constructing user Profiles video) A closely related line of work is hypertext and web page classification. This work has its roots in the information Classifier deals with the methodology for query retrieval (IR) community. A hypertext collection has a rich classification, where our aim is to classify queries onto a structure that should be exploited to improve classification commercial taxonomy of Web queries with approximately accuracy. In addition to words, hypertext has both 6000 nodes. Given such classifications, one can directly use them to provide better search results as well as more incoming and outgoing links. Traditional IR document focused ads. The problem of query classification is models do not make full use of the link structure of extremely difficult owing to the brevity of queries. hypertext. In the web page classification problem, the web Observe, however, that in many cases a human looking at is viewed as a large directed graph. Our objective is to the search query and the search results does remarkably label the category of a web page, based on features of the well in making sense of it. For instance, in the example current page and features of linked neighbours. With the IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 43 www.IJCSI.org above, sending the query “SD450" to a Web search engine of rare queries, whose correct classification is likely to be brings pages about Canon cameras, while “nc4200" brings particularly beneficial. pages about Compaq laptops, hence to a human the intent Profile Manager takes Classifier’s inputs and uses them is quite clear. Of course, the sheer volume of search to refine/adapt/update the user profile. queries does not lend itself to human supervision, and therefore we need alternate sources of knowledge about User Profile contains the details and interests of the user. the world. Search engines index colossal amounts of information, and as such can be viewed as large repositories of knowledge. Following the heuristic 5. Conclusions described above, we propose to use the search results themselves to gain additional insights for query Query classification is an important information retrieval interpretation. To this end, we employ the pseudo task. Accurate classification of search queries can relevance feedback paradigm, and assume the top search potentially be useful in a number of higher-level tasks results to be relevant to the query. Certainly, not all results such as Web search and ad matching. Since search queries are equally relevant, and thus we use elaborate voting are usually short, by themselves they usually carry schemes in order to obtain reliable knowledge about the insufficient information for adequate classification query. For the purpose of this study we first dispatch the accuracy. To address this problem, we proposed a given query to a general Web search engine, and collect a methodology for using search results as a source of number of the highest-scoring URLs. We crawl the Web external knowledge. To this end, we send the query to a pages pointed to by these URLs, and classify these pages. search engine, and assume that a plurality of the highest- Finally, we use these result-page classifications to classify ranking search results is relevant to the query. Classifying the original query. Our empirical evaluation confirms that these results and then allows us to classify the original using Web search results in this manner yields substantial query with substantially higher accuracy. There has been a improvements in the accuracy of query classification. Note growing interest in learning from linked data between that in a practical implementation of our methodology objects. Tasks include hypertext classification, within a commercial search engine, all indexed pages can segmentation, information extraction, searching and be pre-classified using the normal text- processing and information retrieval, discovery of authorities and link indexing pipeline. Thus, at run-time we only need to run discovery. Domains include the world-wide web, the voting procedure, without doing any crawling or bibliographic citations, criminology and bio-informatics, classification. This additional overhead is minimal, and to name just a few. Learning tasks range from predictive therefore the use of search results to improve query tasks, such as classification, to descriptive tasks, such as classification is entirely feasible at run-time. the discovery of frequently occurring sub-patterns. There are other different data mining challenges in link mining Another important aspect of our work lies in the choice of such as identify of the, Link discovery, common relational queries. The volume of queries in today's search engines patterns, where these topics lie in research area. follows the familiar power law, where a few queries appear very often while most queries appear only a few References times. While individual queries in this long tail are rare, [1] Personalized Web Search by Mapping User Queries to together they account for a considerable mass of all Categories- Fang Liu Clement Yu Weiyi Meng Department searches. Furthermore, the aggregate volumes of such of Computer Science, Department of Computer Science, queries provide a substantial opportunity for income Department of Computer Science, University of Illinois at through on-line advertising. For frequent queries, Chicago University of Illinois at Chicago SUNY at Binghamton Chicago. searching and advertising platforms can be trained to [2] D. Jensen. Statistical challenges to inductive inference in provide good results, including auxiliary data such as linked data. In Seventh International Workshop on Artificial maps, shortcuts to related structured information, Intelligence and Statistics, 1999 S. Zhang, C. Zhu, J. K. O. successful ads, and so on. “Tail" queries, however, simply Sin, and P. K. T. Mok, “A novel ultrathin elevated channel do not have enough occurrences to allow statistical low-temperature poly-Si TFT,” IEEE Electron Device Lett., learning on a per-query basis. Therefore, we need to vol. 20, pp. 569–571, Nov. 1999. aggregate such queries in some way, and to reason at the [3] S. Chakrabarti. Mining the Web. Morgan Kaufman, 2002. level of aggregated query clusters. A natural choice for [4] Personalized Web Search by Mapping User Queries to such aggregation is to classify the queries into a topical Categories- Fang Liu Clement Yu Weiyi Meng Department taxonomy. Knowing which taxonomy nodes are most of Computer Science, Department of Computer Science, Department of Computer Science, University of Illinois at relevant to the given query will aid us to provide the same Chicago University of Illinois at Chicago SUNY at type of support for rare queries as for frequent queries. Binghamton Chicago. Consequently, in this work we focus on the classification IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 44 www.IJCSI.org [5] D. Jensen. Statistical challenges to inductive inference in linked data. In Seventh International Workshop on Artificial Intelligence and Statistics, 1999S. Zhang, C. Zhu, J. K. O. Sin, and P. K. T. Mok, “A novel ultrathin elevated channel low-temperature poly-Si TFT,” IEEE Electron Device Lett., vol. 20, pp. 569–571, Nov. 1999. [6] Beitzel, S., Jensen, E., Chowdhury, A., Grossman, D., and Frieder, O. 2004. Hourly analysis of a very large topically categorized web query log. In Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM Press, Sheffield, United Kingdom, 321-328. [7] Broder, A., P., Fontoura, M., Gabrilovich, E., Josifovski, V., and Reidel, L.2008. Search advertising using Web relevance feedback. In CIKM’08. [8] Gabrilovich, E. and Markovitch,S.2007. Harnessing the expertise of 70,000 human editors: Knowledge-based feature generation for text categorization. Journal of Machine Learning Research 8,2297-2345. K.Srinivas is a Ph.D. student and received Mater of Technology in Computer Science and Engineering from Jawaharlal Nehru Technological University in 2005 and Bachelor of Engineering in computer science and Engineering from Swami Ramananda Teerth Marathwada University in 2000. He is working as Associate Professor in Geethanjali College of Engineering and Technology and worked as Assistant Professor in Arkay College of Engineering and Technology affiliated to Jawaharlal Nehru Technological University. His main research interests include Data Mining and Information Retrieval. L.Kiran Kumar Reddy received M.Tech. in Computer Science and Engineering in 2006 and B.E. in Computer Science and Engineering from Swami Ramananda Teerth Marathwada University in 2000. He is working as Associate Professor in Satyam Learning Campus’s Institute of Engineering and Technology and worked as Assistant Professor in Arkay College of Engineering and Technology. He is doing research in Data Mining and Information Retrieval. Dr.A.Govardhan received Ph.D. degree in Computer Science and Engineering from Jawaharlal Nehru Technological University in 2003 M.Tech. from Jawaharlal Nehru University in 1994 and B.E. in from Osmania University in 1992. He is Working as a Principal of Jawaharlal Nehru Technological University, Jagitial. He has Published around 50 papers in various national and international Journals/conferences. His research of interest includes Data Mining, Information Retrieval, Search Engines. IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 45 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Image Compression Algorithms for Fingerprint System Preeti Pathak CSE Department, Faculty of Engineering, JBKP, Faridabad, Haryana,121001, India Abstract minutiae based automatic identification technique first Fingerprint-which have been used for about 100 years are the locates the minutiae point and matches their relative oldest biometric signs of identity. Humans have used fingerprints placement in a given finger and the stored template, for personal identification for centuries and the validity of shown in figure 1. fingerprint identification has been well established. In fact, fingerprint technology is so common in Human Identification that it has almost become the synonym of biometrics. Fingerprints are believed to be unique across individuals and across fingers of same individual. Even identical twins having similar DNA, are believed to have different fingerprints. The analysis of fingerprints for matching purposes generally requires the comparison of several features of the print pattern. These include patterns, which are aggregate characteristics of ridges, and minutia points, which are unique features found within the patterns. is also necessary to know the structure and properties of human skin in order to successfully employ some of the imaging technologies. A major approach for fingerprint recognition today is to extract Fig. 1: Fingerprint Recognition System minutiae from fingerprint images and to perform fingerprint matching based on the number of corresponding minutiae pairings. One of the most difficult problems in fingerprint recognition has The fingerprint image may be obtained from a thumb pad been that the recognition performance is significantly influenced fingerprint scanner device scanning at 500 dpi [2] . A by fingertip surface condition, which may vary depending on good quality fingerprint contains between 60 and 80 environmental or personal causes. Addressing this problem this minutiae, but different fingerprint have different number paper propose some extra features that can be used to strengthen of minutiae. A fingerprint image essentially consists of a the present approaches followed in developing Fingerprint set of minutiae on the plane. Minutiae are the recognition system. To increase security and accuracy we can use Infrared technique and technique to assign a score value to each of terminations and bifurcations of ridge lines in a extracted minutiae. fingerprint image. In order to extract these minutiae, we have to undergo the operation linearization followed by the process of thining. Thus, the set minutiae those are Key Terms– Biometric, Minutiae, Binarization, Thinning, Median Filter. well defined and more prominent then the rest are given higher relevance and importance in the process of minutiae matching. 1. Introduction Biometric authentication has been receiving extensive attention over the past decade with increasing demands in automated personal identification . Biometric is to identify individuals using physiological or behavioral characteristics, such as fingerprint, face, iris, retina, palm-print, etc. Among all the biometric techniques, fingerprint recognition [1] is the most popular method Fig.2 : Terminations and bifurcations of ridge lines in a fingerprint and is successfully used in many applications. Typical image fingerprint recognition methods employ feature-based image matching, where minutiae (i.e., ridge ending and ridge bifurcation) are extracted from the registered fingerprint image and the input fingerprint image, and 2. System Architecture the number of corresponding minutiae pairings between the two images is used to recognize a valid fingerprint The fingerprint recognition system is shown in figure3. It image [1].The feature-based matching provides an consists of four components effective way of identification for majority of people.The IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 46 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 1. User Interface (with Infrared Sensor) the regions that can not be reliable recovered. The enhanced fingerprint image is fed to the minutiae 2. System Database extractor again. The task of authentication module is to authenticate the identity of the person who intends 3. Enrollment Module to access the system. The person to be authenticated indicates his / her identity and places his / her finger on the fingerprint scanner ; a digital image of his her 4. Authentication Module fingerprint is captured ; minutiae pattern is extracted from the captured fingerprint image and fed to a Infrared matching algorithms which matches it against the Sensor person’s minutiae templates stored in the system database to establish the identity To increase security and accuracy we can use Infrared technique and technique to assign a score value to each of extracted minutiae. Fig 3 : System Architecture The user interface provides mechanisms for a user to indicate his/her identity and input his/her fingerprints into the system. Here along with finger print scanner the Infrared Sensor will be used. The system database consists of a collection of records, each of which corresponds to an authorized person that has access to the system. Each record contains the following fields which are used for authentication purpose:  User name of the person , Fig. 4: Block diagrams of Enrollment ,Verification, Identification Task  Minutiae templates of the person’s fingerprint, and other information (e.g., specific user 3. Development of proposed system privileges). Alongwith thermal parameter. Proposed system consist of following sub modules - The task of enrollment module is to enroll persons and their fingerprints into the system database. 3.1 Normalization When the fingerprint images and user name of a person to be enrolled are fed to the enrollment module, a minutiae extraction algorithm is first By normalizing an image, the colors of the image are applied to the fingerprint images and the minutiae spread evenly throughout the gray scale. A normalized patterns are extracted. A quality checking algorithm image is much easier to compare with other images, and is used to ensure that the records in the system the quality of the image is easier determined. database only consist of fingerprints of good quality, Normalization is a pixel-wise operation that does not in which a significant number (default value is 25) change the clarity of the ridge and valley structures . of genuine minutiae may be detected. If a fingerprint Normalization reduces the variations in gray level values image is of poor quality, it is enhanced to improve along ridges and valleys, which facilitates the subsequent the clarity of ridge/vally structures and mask out all processing steps. Let I(x; y) denote the grayscale value at pixel (x; y), M and IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 47 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 V, the estimated mean and variance of grayscale values in this 64 X 64 window, respectively, and N(x; y), the Median filtered normalized grayscale value at pixel (x; y). For all the Pixels in the window, the normalized image is defined as: * * * * 4 * V 0  (T ( x, y)  M 2 * * * M0 , ifI ( x, y)  M N(x, y) = V (1) Center value (previously 97) is replaced by the median of all nine values. Note that for the first (top) example, the V 0  (T ( x, y)  M2 M0  , ifI ( x, y)  M median filter would also return a value of 5, since the V ordered values are 1, 2, 3, 4, 5, 6, 7, 8, 9. For the second (bottom) example, though, the mean filter returns the value 16 since the sum of the nine values in the window is 144 and 144 / 9 = 16. This illustrates one of the In Eq. (1) , M0 and V0 are the desired mean and variance celebrated features of the median filter: its ability to Values , respectively. Normalization is a pixel-wise remove 'impulse' noise (outlying values, either high or Operation and does not change the clarity of the ridge and low). The median filter is also widely claimed to be Valley structures . For our experiments, we set the values of 'edge-preserving' since it theoretically preserves step both M0 and V0 to 100. The values of M0 and V0 should edges without blurring. However, in the presence of be the same across all the training and test sets [7]. noise it does blur edges in images slightly. 3.2 Median Filter Median filtering is a simple and very effective noise removal filtering process. Its performance is particularly good for removing shot noise. Shot noise consists of In image processing it is usually necessary to perform strong spike like isolated values. high degree of noise reduction in an image before performing higher-level processing steps, such as edge detection. The median filter is a non-linear digital Shown below are the original image and the same image filtering technique, often used to remove noise from after it has been corrupted by shot noise at 10%. This images or other signals. The idea is to examine a sample means that 10% of its pixels were replaced by full white of the input and decide if it is representative of the signal. pixels. Also shown are the median filtering results using This is performed using a window consisting of an odd 3x3 and 5x5 windows; three (3) iterations of 3x3 median number of samples. The values in the window are sorted filter applied to the noisy image; and finally for into numerical order; the median value, the sample in the comparison, the result when applying a 5x5 mean filter center of the window, is selected as the output. The to the noisy image. oldest sample is discarded, a new sample acquired, and the calculation repeats. Median filtering is a common step in image processing. It is particularly useful to reduce speckle noise and salt and pepper noise. Its edge-preserving nature makes it useful in cases where edge blurring is undesirable. The median filter is also a spatial filter, but it replaces the center value in the window with the median of all the pixel values in the window. The kernel is usually square but can be any shape. An example of median filtering of a single 3x3 window of values is shown below. Fig 5: a) Original image; b) Added Shot Noisy at 10\% Unfiltered values 3.3 Binarization (Regional Average Threshold) 6 2 0 3 97 4 Making an image binary, transforms the gray scale 19 3 10 image into a binary image (black and white). Either a global or In order: 0, 2, 3, 3, 4, 6, 10, 15, 97 localized threshold value IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 48 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 is used. Gray level images cannot be operated on for the 2. The algorithm finds out (x,y) location of the determination of key features as the range of values of first block pixel which is not processed yet in pixel intensities very widely. So it is very difficult to the original binary image. discriminate conspicuously the valleys from the ridges, 3. A black pixel is inserted into thinned image at as well as ridges bifurcations from ridge endings. Hence (x,y) location (gray pixels) and the black pixel some half toning technique needs to be applied on the is removed from the original binary image at the finger print image. A popular technique is that of location. Threshold of Binarization [3] [4] [5]. Then algorithm looks at the ridge continuity , if In many image-processing applications it is desired to there is ridge continuity , it follows the ridge. convert the the gray images into white and black (bi- level) image. Thesholding involves looking at each pixel 3.5 Noise Removal and deciding whether it can be converted into white (0) or black (255), the decision is made by comparing the numerical pixel value against a fixed number called a After applying thining algorithm we are lift with an threshold level (T). If any pixel of image(x ,y) is less image that still has got some noise , i.e. some ridges than the threshold level (T), the pixel is set to zero are not of one pixel width or some other noise , this (background point), otherwise it is set to 255 (object module is used to remove this noise point). In this we check if in the neighborhood of a pixel there are more than five pixels. Less than five pixels Algorithm: imply that this pixel is a ridge end or bifurcation or some part of a ridge. More than five pixels imply 1. Divide the image into 4*4 regions. that this pixel is associated with some noise. 2. Calculate the average of gray level in the first 4*4 region. 3.6 Depuration 3. Threshold the leftmost region of 4*2 by using average gray level calculated in stage2. The image obtained from previous module still not 4. Move the 4*4 operation window by 2 pixels to suitable for minutie detection . This module removes the right . If right edge of the image is reached , some more defects .Depuration of the ridge map then move the window 4 pixels up and return to involves removal of the spurious elements, the left edge . identified as undesirable spikes, and to join the 5. Repeat stage 2 to stage 4 until the entireimage is broken lines using a smoothening procedure . This processed by RAT(Regional average depuration process is carried out by simple rules thresholding). like .  To remove small isolated lines. 3.4 Thinning  To merge all the lines who have end points with similar direction and the distance between them Hear thinning algorithm is based on ridge following. is small. Such an algorithm has a better probability of enhancing the required properties of image . Ridges exist in all Algorithm : finger prints and they form the features either by ending (ridge endings) or by forking bifurcations . In our work 1. First identify the pixel which is a ridge end. we are using black pixels as the ridges in fingerprints. 2. Then find out another black pixel in the 7*7 The current work uses thining algorithm which deals matrix neighborhood of this pixel. with just black pixels, which are between two white 3. If this pixel exists then we find out the slope of pixels [2] [3] [5]. two respective ridges at their respective ridge ends in 7*7 matrixes. Algorithm: 4. If the slopes obtained are comparable then join ridge ends by using DDA algorithm. 1. The image is read from bottom left to the right side line by line and the algorithm always tries to find day any of black pixels in the original 3.7 Minutiae Extraction image . Because it is obvious that any of black pixels may be constituent of ridge. Minutiae extraction was carried out using the crossing number approach. Crossing number of pixel ‘p’ is IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 49 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 defined as half the sum of the differences between pairs The number of minutiae in a given area is also limited of adjacent pixels defining the 8-neighborhood of ‘p’. therefore the minutiae density must also be kept in check. Mathematically in eq .(2). In order to filter out these false minutiae a 3 level- filtering process is applied: cn( p )  1 2  | val ( p i 1..8 i mod 8 )  val ( pi  1) | (2) Level 1: Removes the false ridge endings created as a result of the application of minutiae extraction algorithm Where p0 to p7 are the pixels belonging to an ordered at the ends of the thinned image. sequence of pixels defining the 8-neighborhood of p and val (p) is the pixel value. Level 2: Removes the first five types of minutiae mentioned above using the rule based morphological minutiae filtering approach given by . Level 3: This stage limits the maximum number of minutiae present in the thinned image to a pre-specified threshold. A minutiae m is described by the triplet m={x, y, θ}, where x, y indicate the minutiae location coordinates and θ denotes the minutiae orientation, which is the Fig.6: cn (p)=2,cn (p)=3 and cn (p)=1 representing a orientation evaluated for the minutiae location from the nonminutiae region, a bifurcation and a ridge ending orientation image obtained during the enhancement process. The minutiae type is not being used during the Crossing numbers 1 and 3 correspond to ridge endings matching process since minutiae type can be inverted and ridge bifurcations respectively. An intermediate due to enhancement and binarization steps [6]. ridge point has a crossing number of 2. The minutiae obtained from this algorithm must be filtered to preserve only the true minutiae. The different types of false minutiae introduced during minutiae extraction include spike, bridge, hole, break, Spur, Ladder, and Misclassified Border areas. (See figure 7) Fig. 8: Filtered and Unfiltered Minutiae Sets In this process we use text files as databases. We consider three text files for storing the bifurcation information , the ridge information , and the thermal parameters respectively. Every time a new fingerprint image is operated upon , a set of two text files are generated along with another file for keeping information about the person whose fingerprint is under checking. In Fig. 7: Types of false minutiae case of verification , the text files generated are matched AB with the existing ones and the numbers of matches are CD displayed. EF A. Spike, B. Bridge, C. Hole, D.Break, E. Spur F. Ladder 3.8 Minutiae Matching IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010 50 ISSN (Online): 1694-0784 ISSN (Print): 1694-0814 Let T and I be the representation of the template and more reliable . This system needs some extra cost input fingerprint, respectively. Let the minutiae sets of and more processing time, but one can not the two fingerprints be given by: compromise with the security. T  {m1, m 2,.........., mn} I  {m'1, m'2,.........., m' n} References (3) mi  {xi, yi,i}, i  1.....m [1] D.Maltoni, D.Maio, A.K.Jain, and Prabhakar, “Hand book mj  {x' j , y ' j , ' j}, j  1.....n of fingerprint Recognition “. Springer,2003 [2] V.Espinosa-Duro., “Minutiae detection algorithm for fingerprint recognition”, IEEE Aerospace Electron . Syst. Mag. A minutia mj’ in I and a minutia mi in T are 17(3),7-10,2002 considered to be matched if their spatial and [3] D. Manolescu, “Feature extaction – a pattern for orientation differences are within specified information retrieval”, In Proceedings of the 5th Pattern Languages of Programming, Monticello, Illinois, USA, August thresholds ro and θo. Minutia matching was 1998. carried out by using the approach given in . In [4] A.K.Jain, “ Fundamentals of Digital Image Processing”, this approach the minutiae sets are first PHI, ISBN-13:978-013336150 registered using a derivative of the Hough [5] Dario Maio, Davide Maltoni, “Direct Graay-Scale Minutiae transform followed by fingerprint matching Detection In Fingerprints”, IEEE Transactions on Pattern using spatial and orientation-based distance Analysis and Machine Intelligence v.ol. 9 n.o.l, pp., 27-40, January 1997 computation. The matching algorithm returns a percentage match score, which is then used to [6] F.A.Afsar, M.Arif and M.Hussain, “Fingerprint Identification and Verification System using Minutiae Matching”, take the match-no match decision based on the National conference on Emerging Technologies 2004 security criterion[6]. [7] Bhupesh Gour, T. K. Bandopadhyaya, Sudhir Sharma, “Fingerprint Feature Extraction Using Midpoint ridge Contour method and Neural Network”, IJCSNS International Journal 4. Result and discussion of Computer Science and Network Security, VOL.8 No.7, July 2008 To study the performance of the proposed work, we consider the database containing 350 images. There are 10 different impressions per finger. Here we About the Author assume that images should be of good quality with at least 500 dpi and noise level, if any, of the image The Author, Preeti Pathak, working as Lecturer in Department, Faculty of Engineering, JBKP, Faridabad, India. She has received should be removed by the preprocessing. The her M.Tech (Comp. Sc. & Tech) from Maharishi Dayanand performance of the system has shown the efficiency University, Rohtak along with two other Master degrees, M.Sc. in about 97% in 5.8 seconds .It has been seen that Physics from Agra University, Agra and M.C.A. (Master in when the core point is correctly located, the Computer Applications) from IGNOU, New Delhi, INDIA. She translation invariant property of features is satisfied has also served as Lecturer in other Eng. Colleges like BSA and and the rotation handled in the matching stage is Arravali Eng. College Faridabad. She has been involved in many very fast. As result of which the matching process Training, Seminars and conferences. She has also presented her becomes very fast. Technical Papers in Two International Conferences and two National Conferences. She has also completed her Training on “Selected Topics in Software Engineering” sponsored by AICTE and HRD of India held in March 18-24, 2010 at IIT, Kharagpur. She has begged many such Certificates and achievements in her 5. Conclusion educational career. Her research interest includes Software Engineering, Fuzzy System, Image Processing and Computer The paper presents different steps involved in the Networks & Internet Technology. development of a fingerprint based person identification and verification system. And the proposed fingerprint recognition system uses both frequency and orientation information available in fingerprint. Due to this , the existing system become IJCSI CALL FOR PAPERS NOVEMBER 2010 ISSUE Volume 7, Issue 6 The topics suggested by this issue can be discussed in term of concepts, surveys, state of the art, research, standards, implementations, running experiments, applications, and industrial case studies. Authors are invited to submit complete unpublished papers, which are not under review in any other conference or journal in the following, but not limited to, topic areas. See authors guide for manuscript preparation and submission guidelines. Accepted papers will be published online and authors will be provided with printed copies and indexed by Google Scholar, Cornell’s University Library, ScientificCommons, CiteSeerX, Bielefeld Academic Search Engine (BASE), SCIRUS and more. Deadline: 30th September 2010 Notification: 31st October 2010 Revision: 10th November 2010 Online Publication: 30th November 2010  Evolutionary computation  Software development and  Industrial systems deployment  Evolutionary computation  Knowledge virtualization  Autonomic and autonomous systems  Systems and networks on the chip  Bio-technologies  Context-aware systems  Knowledge data systems  Networking technologies  Mobile and distance education  Security in network, systems, and  Intelligent techniques, logics, and applications systems  Knowledge for global defense  Knowledge processing  Information Systems [IS]  Information technologies  IPv6 Today - Technology and  Internet and web technologies deployment  Digital information processing  Modeling  Cognitive science and knowledge  Optimization agent-based systems  Complexity  Mobility and multimedia systems  Natural Language Processing  Systems performance  Speech Synthesis  Networking and telecommunications  Data Mining For more topics, please see http://www.ijcsi.org/call-for-papers.php All submitted papers will be judged based on their quality by the technical committee and reviewers. Papers that describe research and experimentation are encouraged. All paper submissions will be handled electronically and detailed instructions on submission procedure are available on IJCSI website (www.IJCSI.org). For more information, please visit the journal website (www.IJCSI.org) © IJCSI PUBLICATION 2010 www.IJCSI.org IJCSI The International Journal of Computer Science Issues (IJCSI) is a refereed journal for scientific papers dealing with any area of computer science research. The purpose of establishing the scientific journal is the assistance in development of science, fast operative publication and storage of materials and results of scientific researches and representation of the scientific conception of the society. It also provides a venue for researchers, students and professionals to submit on- going research and developments in these areas. Authors are encouraged to contribute to the journal by submitting articles that illustrate new research results, projects, surveying works and industrial experiences that describe significant advances in field of computer science. Indexing of IJCSI: 1. Google Scholar 2. Bielefeld Academic Search Engine (BASE) 3. CiteSeerX 4. SCIRUS 5. Docstoc 6. Scribd 7. Cornell’s University Library 8. SciRate 9. ScientificCommons © IJCSI PUBLICATION www.IJCSI.org