Seiji Sugiyama
email: seijisan@sch.otani.ac.jp

Daisuke Yokozawa
email: dyokozawa@gmail.com

Atsushi Ikuta
email: a.ikuta@sch.otani.ac.jp

Satoshi Hiratsuka
email: hiratsuka@spice.ci.ritsumei.ac.jp

Miyuki Shibata

Tohru Matsuura

Simple Displaying Method for Genealogy with Assisted Reproductive Technologies

Keywords: Family Trees, Pedigrees, Sperm or Ovum Donor, Surrogate Mother, GEDCOM, WHIteBasE

In this research, a new layout style, 'Nodes of Effects and/or Way through for TYing Particular Elements (NeWTYPe)', for displaying genealogy with assisted reproductive technologies (ART) that include a sperm/ovum donor and/or a surrogate mother using our WHIteBasE method is proposed. The NeWTYPe is a node with symbols; 'Arrow', 'Pipe', and 'Arrow and Pipe'. Using the NeWTYPe, complex relations of the ART can be understood easily. Note that previous WHIteBasE method has perfectly been able to integrate each relation that includes a married couple and their children, and has been able to display complex relations with segment intersections and various layout styles easily, and also, our JaBBRoW method for abbreviating some jointed relations on the WHIteBasE has been proposed. As a result, displaying both regular complex genealogy and the ART can be realized simultaneously. Our improved software that can display the NeWTYPe automatically and seamlessly by only mouse operations is presented.

Introduction

There is a lot of genealogy display software these days [START_REF]The Generations Network: Genealogy, Family Trees and Family History Records on line[END_REF]- [START_REF] Genopro | [END_REF]. However, almost all of them cannot display complex relations perfectly. In the case of writing complex genealogy on paper media, one individual is written only once in most cases using segment intersections and various layout styles. In contrast, in the case of using the software, one individual is often displayed in multiple places because the software considers no complex layouts even if GEDCOM [START_REF] Gedcom Letter | [END_REF], a de facto standard for recording genealogy data exchange format, can store them perfectly. These displaying results are very difficult to understand complex relations correctly.

To cope with the difficulty, new genealogy display software has already been proposed on our previous research by using the WHIteBasE (Widespread Hands to InTErconnect BASic Elements) method [START_REF] Sugiyama | A Study of An Event Oriented Data Management Method for Displaying Genealogy: Widespread Hands to InTErconnect BASic Elements (WHIteBasE)[END_REF]. The WHIteBasE is a hidden node for integrating relations that include not only a married couple and their children but also information of those positions. As a result, one individual have been displayed only once using segment intersections easily. In addition, not only various layouts such as paper media have been displayed but also intuitive inputs and inspections such as map display systems have been realized [START_REF] Sugiyama | Displaying Genealogy with Various Layouts by using the "WHIteBasE" Method[END_REF], [START_REF] Sugiyama | Displaying Genealogy with Adoptions and Multiple Remarriages Using the WHIteBasE[END_REF]. Moreover, JaBBRoW (Joint ABBReviation for Organizing WHIteBasE) method has also been proposed for abbreviating a part of genealogy [START_REF] Sugiyama | Abbreviation Method for Some Jointed Relations in Displaying Genealogy[END_REF]. As a result, arbitrary relations with horizontal and vertical connections in genealogy can be abbreviated easily.

On the other hand, there is different complex relations these days such as Assisted Reproductive Technologies (ART) that include a sperm or ovum donor, and a surrogate mother [START_REF] Voon | An Overview of Computer-Aided Medical Pedigree Drawing Systems[END_REF]. This work said that ART symbols and pedigree lines can be displayed on many existing genealogy display software. However, these software cannot display regular complex relations with segment intersections perfectly mentioned above. In addition, these layout styles has slant lines between a parent generation and a child generation. Using slant lines makes displaying genealogy complicated in the case of using segment intersections. Displaying all situations both of regular genealogy and medical pedigree such as the ART cannot be realized using the existing medical line definitions.

In this paper, a new layout style, 'Nodes of Effects and/or Way through for TYing Particular Elements (NeWTYPe)', is added to the WHIteBasE method. The NeWTYPe is a node with symbols; 'Arrow', 'Pipe', and 'Arrow and Pipe'. Using the NeWTYPe, complex relations of the ART can be understood easily. As a result, displaying both regular complex genealogy and the ART can be realized simultaneously. Our improved software that can display the NeWTYPe automatically and seamlessly by only mouse operations is presented.

WHIteBasE and JaBBRoW

In this section, the WHIteBasE method and the JaBBRoW method that are our previous proposal [START_REF] Sugiyama | A Study of An Event Oriented Data Management Method for Displaying Genealogy: Widespread Hands to InTErconnect BASic Elements (WHIteBasE)[END_REF]- [START_REF] Sugiyama | Abbreviation Method for Some Jointed Relations in Displaying Genealogy[END_REF] are briefly introduced. A regular family relation between a married couple and their child is managed as an event by a Hidden Node, WHIteBasE as shown in Fig. 1. The connection model of WHIteBasE is shown in Fig. 2. WHIteBasE has three keyholes, S L , S R (Substance) and D (Descendant). Individuals have two keys, A (Ascendant) and M (Marriage). A can connect with D, and M can connect with S L or S R , where denote one family. For brothers and sisters, D is extended to multiple keyholes D j as shown in Fig. 3. For multiple remarriages, M is extended to multiple keys M k and plural WHIteBasEs are used as shown in Fig. 4. For adoptions, A is extended to multiple keys A l as shown in Fig. 5 where A p , one of A l , denotes ID for handling the biological parents, and the others denote IDs for handling social parents.

Fig. 6 shows the regular Japanese layout style. It includes a double horizontal segment MS (Marriage Segment), a vertical segment TS (Trunk Segment), a horizontal segment BSS (Brothers and Sisters Segment), and a vertical segment BS (Branch Segment). The ' ' denotes a male, and the ' ' denotes a female that are a couple connected by using MS. For various layouts, MS is extended to MS, MS v , and MS h named DB (Double Bend), and BSS is extended to BSS h , BSS v , and BSS l named HS (Hooked Segment), as shown in Fig. 7.

A set of W i that defines WHIteBasEs and a set of I j that defines Individual Nodes are represented by

W i = {S L , S R , D j , Q} I j = {M k , A l }        i = 0, 1, • • • , i max j = 0, 1, • • • , j max k = 0, 1, • • • , k max l = 0, 1, • • • , p, • • • , l max (1)
where i, j, k, l and i max , j max , k max , l max denote the IDs and their maximum values on the data table respectively, p denotes the ID for handling a biological parents, S L and S R denote the IDs for handling a couple, D j denote the IDs for handling descendants, M k denote the IDs for handling marriages, and A l denote the IDs for handling ascendants. Individuals are managed by using data table including names and annotation data. WHIteBasEs are managed by using data table separated from Individuals. A set of Q that defines coordinate values for each position managed by a WHIteBasE measured from the origin in the displaying area is represented by Q = {q b , q L , q R , q d , q cj , q aj , q vl , q vh , q m , q e , q tl , q rb } (2)

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p)
where q b denotes the WHIteBasE's position, q L , q R denote the parents' positions, q d denotes a junction's position between MS and TS, q cj denotes children's positions, q aj denotes junctions' positions between BSS and BS, q vl , q vh denote the corners on DB, q m , q e denote the corners on HS, q tl , q rb denote positions of top-left and bottom-right of all area managed by a WHIteBasE, as shown in Fig. 7 and Fig. 8. There are only four kinds of horizontal segments and four kinds of vertical segments in the WHIteBasE method. The positions of segment intersections can be calculated by using only 16 patterns of line crossing as shown in Figs. 9(a)-(p). The half arcs are displayed on the positions of segment intersections. The detailed information has already been written in our previous research [START_REF] Sugiyama | Displaying Genealogy with Adoptions and Multiple Remarriages Using the WHIteBasE[END_REF].

This algorithm is very fast because it skips when two WHIteBasEs' areas do not overlap. In addition, when adoptions are set, the segment style changes to the dashed segments named AS (Adopted Segment) and the arcs are not used.

One of advantages using WHIteBasE is the decreased reference volume. If the existing software is used, all of individuals connect with other individuals as shown in Fig. 10(a). In contrast, if the WHIteBasE is used, two reference links per a child decrease as shown in Fig. 10(b). Moreover, the users can understand the complex relations intuitively and can input and inspect them easily.

Fig. 11 shows the sample demonstrations by using our previous genealogy display software that can display complex relations with segment intersections automatically and seamlessly by only mouse operation [START_REF]Nerva-Antonine dynasty[END_REF].

In addition, the JaBBRoW method can be used for abbreviating a part of genealogy. A selected area of genealogy with abbreviation is managed as an event by a Hidden Boundary as shown in Fig. 12(a). When the area is compacted, the dotted rectangle becomes the solid rectangle as shown in Fig. 12(b). All of relations in genealogy can be maintained while compacting, and all of relations in the Hidden Boundary can be scaled down to the very small area.

JaBBRoW is defined using a set of hyper-graph G represented by

G = ( V, ) (3)
where denotes a hyper-edge given by

= { J 0 , J 1 , J 2 , • • • ∈ V | J i ∩ J j = 0, i = j } (4)
where J k (k = 0, 1, 2, • • •) denote a Hidden Boundary JaBBRoW, each JaBBRoW is a disjoint set, and one node is not managed by plural JaBBRoW. On the other hand, V denotes a set of each node inside the JaBBRoW represented by

V = { V 0 , V 1 } (5)
where V 0 and V 1 denote a set of Individuals and a set of WHIteBasE respectively represented by

V 0 = { I 0 , I 1 , I 2 , • • • , | I j / ∈ J k then I j / ∈ V 0 , k = 0, 1, 2, • • • } (6) V 1 = { W 0 , W 1 , W 2 , • • • , | W i / ∈ J k then W i / ∈ V 1 , k = 0, 1, 2, • • • } (7)
where I j are coordinate values on the ∑ world , and W i are coordinate values of only corner points in the WHIteBasE represented by

W i = {q b , q d , q vl , q vh , q m , q e |q b / ∈ J k then q d , q vl , q vh , q m , q e / ∈ W i , k = 0, 1, 2, • • •} . ( 8
) As a result, a set of each node inside the JaBBRoW is scaled in each J k . Note that q vl , q vh , q m , q e are not calculated when various layouts are not used. 3 Layout style for Assisted Reproductive Technologies

Existing Definitions

The common pedigree symbols have been defined in the medical pedigree [START_REF] Robin | Standardized Human Pedigree Nomenclature: Update and Assessment of the Recommendations of the National Society of Genetic Counselors[END_REF]. It is very important to discuss these symbols, however, it is not necessary to calculate segment positions for displaying these symbols because they are only symbols instead of displaying individuals' names. Therefore, only segment layout styles are considered for calculating segment intersections in this research.

There are five segment styles in the ART as shown in Figs. 13( (e) Couple contracts with a woman to carry a pregnancy using ovum of the woman carrying the pregnancy and donor sperm.

Problem of these definitions

It is necessary to draw slant lines between parents and a child in these definitions. It is thought that the reason why slant lines are necessary is to display parents and a donor on the same horizontal position and to display genetic relations with reproductive technologies. However, if the display distance between a couple and a donor is long and there is a lot of relations near the couple, the angle of slant lines becomes small and the segment layout becomes complicated because a lot of horizontal and vertical segments are crossing on the slant lines. In addition, it takes more times to calculate positions of segment intersections with slant lines than using only horizontal and vertical segments. Moreover, these definitions are special transcription specialized in medical pedigree and are not general. Surrogate ovum donor: Figs. 17(a)-(f) show surrogate ovum donor layouts where (a)-(f) also mean the same. In this case, the event has not only surrogate but also donor. Considering this meaning, both an arrow and a pipe symbol are used together. These layouts correspond to Fig. 13(d).

Planned Adoption: Figs. 18(a)-(f) show planned adoption layouts where (a)-(f) also mean the same. In this case, two arrows from two persons other than a couple and a child to the node are used. Note that all donor/surrogate persons of (a)-(f) are placed at the same vertical position. In contrast, Figs. 19(a)-(c) show the sample of different vertical positions. Both cases use two arrows and one pipe symbol. These layouts correspond to Fig. 13(e).

Generation Alignment: Fig. 20 shows the sample of generation alignment. Using the long size of individual's text-box vertically, the top position of a couple and a donor/surrogate person can be aligned even though the NeWTYPe is used.

Using Hooked Segments: Figs. 21(a)-(c) show the sample of sperm donor using Hooked Segments. Using these styles, various layouts with the NeWTYPe can be displayed. The other samples using Hooked Segments including ovum donor, surrogate only, surrogate ovum donor, and planned adoption, are similar to these samples, because the node is located on the BS using both regular layout, Direct segments, and Hooked segments. Therefore, the figures of the other samples are omitted in this paper.

W i = {S L , S R , D j , Q, N } . ( 9
)
If N = 0, the WHIteBasE is the normal mode that equals previous model.

If N = 1, 2, 3, the WHIteBasE changes the NeWTYPe mode and the keyhole D is covered, that means connecting descendants is not allowed as shown in Fig. 23 The horizontal segment (arrow) is single segment, however, the layout is similar to MS. Therefore, the same search method for segment intersections as shown in Figs. 9(a)-(p) can be used for the NeWTYPe in a little change of JaBBRoW 001 is WHIteBasE 008 and the descendant of JaBBRoW 001 is Individual 015. The stream line from WHIteBasE 008 to Individual 015 can be seen directly. Note that the JaBBRoW method does not change at all, however, the function of JaBBRoW can be used even though the NeWTYPe is used, because the difference between previous method and new method is only to add the NeWTYPe flag to the WHIteBasE. The definition of the JaBBRoW is the same as our previous research.

Conclusion

In this research, a new layout style, 'Nodes of Effects and/or Way through for TYing Particular Elements (NeWTYPe)', that includes 'Arrow', 'Pipe', and 'Arrow and Pipe', could be added to our previous WHIteBasE method.

As a result, not only regular complex genealogy with segment intersections but also the ART can be displayed simultaneously. Using the NeWTYPe layout, relations of the ART can be understood easily because slant segments are not used. In addition, the calculation time of the NeWTYPe is less than the case using slant segments. Moreover, the layout style of the NeWTYPe is not special transcription specialized in medical pedigree and this method has wide variety of use.

Future plan will be conducted to construct grid layouts on semi-automatic, displaying mythology genealogy, multi OS application, and new genealogy data format for automatic layouts.

Fig. 1 . 2 .

 12 Fig. 1. A regular family layout in genealogy Fig. 2. Connection model of WHIteBasE

Fig. 3 .Fig. 5 .Fig. 6 .

 356 Fig. 3. Brothers and sisters Fig. 4. Multiple Remarriages

Fig. 9 .Fig. 10 . 11 .

 91011 Fig. 9. Search pattern of segment intersections for various layouts

  (a) Selecting the area to compact (b) Compacted area

Fig. 12 .

 12 Fig. 12. Compacted and Recovered Operation by using the Hidden Node, JaBBRoW

Fig. 13 .

 13 Fig.13. Assisted Reproductive Technology Symbols and Definitions[START_REF] Robin | Standardized Human Pedigree Nomenclature: Update and Assessment of the Recommendations of the National Society of Genetic Counselors[END_REF]

  a)-(e)[START_REF] Robin | Standardized Human Pedigree Nomenclature: Update and Assessment of the Recommendations of the National Society of Genetic Counselors[END_REF] where 'D' denotes Donor, 'P' denotes Pregnant and 'S' denotes Surrogate, ' ' denotes woman, ' ' denotes man, and ' ' denotes sex unknown. The five layout styles (a)-(e) mean as the following: (a) Couple in which woman is carrying pregnancy using donor sperm. (b) Couple in which woman is carrying pregnancy using a donor egg and partner's sperm. (c) Couple whose gametes are used to impregnate a woman (surrogate) who carries the pregnancy. (d) Couple in which male partner's sperm is used to inseminate.

Fig. 14 .Fig. 15 .Fig. 16 .Fig. 17 .Fig. 18 .

 1415161718 Fig. 14. Sperm donor layouts using Regular Layouts and Direct Segments

Fig. 19 . 20 .Fig. 21 .

 192021 Fig. 19. Different Vertical Positions Fig. 20. Generation alignment

Fig. 22 .Fig. 23 .

 2223 Fig. 22. Symbols for the NeWTYPe

  (a). The numbers of N mean 'Arrow' (N = 1), 'Pipe' (N = 2), and 'Arrow and Pipe' (N = 3). The left individual that has connected with ascendant WHIteBasE denotes a child of reproductive treatment. The meaning of key M in the left individual changes to the NeWTYPe connection. One of this displaying style is shown in Fig. 23(b). In this case, the right individual in (a) equals to the individual 001 in (b), the left individual in (a) equals to the individual 002 in (b), and N = 1. If the top position of text box in the individual is lower than the vertical position of the WHIteBasE that is NeWTYPe mode, the NeWTYPe (arrow node) is displayed automatically.

Fig. 24 .Fig. 25 .

 2425 Fig. 24. Connection model of the WHIteBasE for planned adoptions

Fig. 26 (Fig. 26 .

 2626 Fig.26(a)shows the sample of five NeWTYPe test on WHIteBasE where Individuals 001/002 are a couple, Individual 004 is a sperm donor, Individual 006 is a ovum donor, Individual 008 is a surrogate mother, Individual 010 is a surrogate ovum donor, and Individuals 012/013 are the case of planned adoption. In this sample, a lot of arcs for segment intersections are automatically displayed. Fig. 26(b) shows the sample of five NeWTYPe test using JaBBRoW. The JaBBRoW 001 manages the five NeWTYPe area to abbreviate. The ascendant


Tapalina Bhattasali
email: tapolinab@gmail.com

Nabendu Chaki
email: nabendu@ieee.org

Khalid Saeed
email: khalids@wp.pl

Rituparna Chaki
email: rchaki@ieee.org

A K Choudhury

U-Stroke Pattern Modeling for End User Identity Verification through Ubiquitous Input Device

Keywords: U-Stroke, Smart Device, Touch Screen, Ubiquitous Input Device, Identity Verification

Identity verification on ubiquitous input devices is a major concern to validate end-users, because of mobility of the devices. User device interaction (UDI) is capable to capture end-users' behavioral nature from their device usage pattern. The primary goal of this paper is to collect heterogeneous parameters of usage patterns from any device and build personal profile with goodrecognition capability. This work mainly focuses on finding multiple features captured from the usage of smart devices; so that parameters could be used to compose hybrid profile to verify end-users accurately. In this paper, U-Stroke modeling is proposed to capture behavioral data mainly from smart input devices in ubiquitous environment. In addition to this, concept of CCDA (capture, checking, decision, and action) model is proposed to process U-Stroke data efficiently to verify end-user's identity. This proposal can draw attention of many researchers working on this domain to extend their research towards this direction.

Introduction

Nowadays, mobile devices become smarter by offering multiple types of computing services at any place and at any time. Ubiquitous input devices [START_REF] Ballagas | The smart phone: a ubiquitous input device[END_REF] (smart phone, tablet, phablet, PDA, laptop, netbook etc.) become rich source of personal data, due to its support towards "any" paradigm. Sensitive personal data (such as password, financial information, health records [START_REF] Bhattasali | Bio-authentication for layered remote health monitor framework[END_REF]), stored in mobile devices are growing day by day. As a result, they are becoming attractive target to be attacked. Accurate identity verification of end-user is becoming a major requirement to preserve confidentiality and integrity in uncontrolled environment.

Traditional authentication mechanism (PIN/Password based) can be easily compromised. Anyone can access all services and can misuse personal information stored in the device, if device is misplaced. Implicit authentication mechanism needs to be considered without affecting normal usage pattern to overcome existing weak authentication methods. Typing on computer keyboard is completely different from typing on smart devices having small keypads [START_REF] Maxion | Keystroke biometrics with number-pad input[END_REF] and sensors enabled touch screen. Today, user-friendly touch screens are widely used on many devices such as mobile phones, tablets, and computers. As smart devices can perform multiple tasks at the same time, data acquisition only during typing is not efficient to build user profile. Beside this, typing on touch-screen based smart devices becomes more error-prone compared to computer keyboard based typing. Only temporal data based keystroke analysis is not sufficient to build unique user profile for any ubiquitous device. Therefore, keystroke analysis needs to be merged with touch screen based gesture analysis to enhance success rate of identity verification. Keystroke dynamics is mainly considered for desktop computers [START_REF] Bhattasali | Bio-authentication for layered remote health monitor framework[END_REF]. Since touch devices comprise sensors to capture environmental changes, they offer more capabilities to authenticate users accurately. Ubiquitous devices consider a different type of Human to Machine (H2M) communication by changing traditional way of human-computer interaction (HCI).

The major contribution of this paper is to propose a novel H2UID (human to ubiquitous input device) interaction mechanism U-Stroke (ubiquitous stroke) that can be applied to any computing device. This type of H2M communication is considered here to verify identity of end-user either by using distinct model or authentication model. Here human to human verification (H2HV) is defined by proposed CCDA (capture, checking, decision, and action) processing model. Different types of U-Strokes and their multiple features are discussed here along with collected data through Android device, which may attract researchers to work on this domain in future.

The rest of the paper is organized as follows. Section 2 presents a brief survey of existing works on this domain. Section 3 describes proposed U-Stroke analysis to verify end-user identity through ubiquitous devices. Section 4 presents brief analysis part followed by conclusion in section 5.

Literature Survey

Researchers are very much interested to work on human computer interaction to be considered as a means of verification of end-user identity [START_REF] Maxion | Keystroke biometrics with number-pad input[END_REF][START_REF] Xu | Towards Continuous and Passive Authentication via Touch Biometrics: An Experimental Study on Smartphones[END_REF][START_REF] Shahzad | Secure Unlocking of Mobile Touch Screen Devices by Simple Gestures -You can see it but you cannot do it[END_REF][START_REF] Feng | Continuous mobile authentication using touchscreen gestures[END_REF][START_REF] Xu | TapLogger: Inferring User Inputs On SmartphoneTouchscreens Using On-board Motion Sensors[END_REF][START_REF] Frank | Touchalytics: On the Applicability of Touchscreen Input as a Behavioral Biometric for Continuous Authentication[END_REF][START_REF] Luca | Touch me once and I know it's you! Implicit Authentication based on Touch Screen Patterns[END_REF]. Nowadays, HCI interaction with ubiquitous computing device becomes popular. Instead of considering end user authentication by means of only PINs or passwords, researchers are working on this area in recent years. Related works can be considered from different aspects such as user's identity verification by keystroke dynamics, by finger movements and tapped information on sensor based touch screens. "Touch Sensor" is the predecessor [START_REF]Touch Screen[END_REF] of modern touch screens. In a few recent studies, touch-based biometrics is proposed for mobile devices instead of keystroke dynamics. There exists several finger gestures based authentication on touch screen of mobile devices. According to literature survey, very few works are based on continuous authentication on smart devices. Software like Touch logger can detect usage pattern of device owner and block unauthorized access to the device. Biometric touch information can be considered to enhance the security by using screen unlock. Interaction data are captured by sensors without affecting normal activities. If it is detected that the current end-user is different from the device owner, explicit access policy needs to be triggered. PIN authentication method is strengthened with sensor data and timings. Different parameters can be collected like acceleration values, touching pressure, touched area on the screen, different temporal values like key-hold time or inter-key time. Flexible authentication can be implemented without considering predefined text. After a learning phase, end -users are authenticated while entering normal text. Touch dynamics may extract features like priority of usage of left and right hand, one-hand or both hand, use of thumb or index finger, stroke size, stroke timing, stroke speed, and timing regularity. Another way of implicit authentication is through learning behavior of a user-based on sent and received text messages, phone calls, browser history, and location of the smart phone. Instead of entering text into a soft keyboard, gestures like sliding towards a special direction or taps are most efficiently used. Generally, target acquisition tasks are carried out with a stylus that is much smaller than the targets. Among various information processing model, Fitt's model is dependent on finger size and type of stroke [START_REF] Bi | FFitts law: Modeling Finger Touch with Fitts' Law[END_REF]. Complexity of Welford's model [START_REF] Welford | Speed and Accuracy of Movement And Their Changes with Age[END_REF] is high compared to Whiting's model, but Welford model is more efficient to define information processing task. A major challenge is to apply Fitts' law to finger input, which may not be efficient for small-sized targets. This is mainly due to "Fat Finger" problem. Fitts' law fails if targets are small. As finger touch on smart phones and tablets becomes popular, examining Fitts' law [START_REF] Bi | FFitts law: Modeling Finger Touch with Fitts' Law[END_REF] for finger touch attracts attention of many HCI researchers. Other information processing models [START_REF] Welford | Speed and Accuracy of Movement And Their Changes with Age[END_REF] are not utilized effectively to model touch gesture till date.

After studying various existing works on this domain, it can be said there is no suitable model exists till date, which can be applied to any device for end-user verification. Most of the touch screen based authentication techniques consider few parameters or includes the features that are only available to costly devices. Considering few strokes with few parameters may not give accurate result. However, processing too many parameters may slow down the procedure. In order to improve the efficiency and accuracy of end-user identity verification, proposed work mainly focuses on finding physical or virtual UDI parameters of individual users and build hybrid personal profiles for accurate identification of end-users through ubiquitous input devices.

Proposed Work

Any type of user to input device interaction is proposed as U-Stroke, which is analyzed to identify end-users to any device in ubiquitous environment. U-Stroke analysis considers typing on numerical keypad or QWERTY keypad of mobile phone, external keyboard of tablet, and physical keyboard of desktop or laptop as physical keystroke; typing on on-screen QWERTY keypad of smart devices or any interaction with touch screen as touch stroke. The concept of U-Stroke pattern is proposed to model any human interaction with ubiquitous input device (H2UID).

Definition (U-Stroke).

It is designed for any type of end-user to input device interaction (UDI) on user-friendly interface of smart devices {smart phone, tablet, phablet (phone + tablet)} in ubiquitous environment to validate H2M communication. U-Stroke is implicitly used to create hybrid profile of end-user (HPEU) for identification as well as verification.

Classification of proposed U-Stroke pattern is presented in figure 1. T-Stroke (Tap stroke) -If touch_down, and touch_up events occur due to the stroke similar to single click, double lick, long tap or short tap on touch screen and screen unlock, it is a type of T-Stroke. Probability of occurrence for touch_down event is high.

U-Stroke Pattern Modeling through Ubiquitous Input Device (UID)

This section presents detailed idea about how U-Stroke pattern processing model can be defined in terms of information processing model like Welford's model [START_REF] Welford | Speed and Accuracy of Movement And Their Changes with Age[END_REF]. Here proposed U-Stroke Pattern Processing Model is defined by CCDA (capture, checking, decision, and action) concept with self-loop to identify end-user. This CCDA concept is mapped to the identity verification of end-user. Capture process is mainly used to collect U-Stroke data. Checking process is mainly used to classify U-Stroke pattern. Decision process is used mainly to take decision. Action process is used to take necessary steps according to final decision. Short term memory is considered as local memory store and long term memory is considered as remote memory store. Self-loop (feedback) is used to update template profile. Figure 2 represents CCDA processing model for UID. Less complex computation such as checking only device owner's validity can be performed through short term memory store (local). Short term memory can store device owner's log file. However, other complex computations are performed through long term memory store (remote server) to reduce computational overhead from limited resource device. CCDA process model may slow down if multiple features are processed compositely. For this reason, composite features are separated before processing and then fused as a whole to speed up the process. Significant variation of user's profile is managed by frequent update of template through feedback path of CCDA processing model.

End-User Identity Verification by U-Stroke Pattern Processing Model

In this section, identity verification procedure of end-users through ubiquitous input devices is briefly presented. Definition of end-user identity verification is given below.

Definition (n class H2HV).

A type of H2UID interaction based on U-Stroke pattern processing model CCDA, is classified into two sub-classes-distinction class (1: m verification, where n = m) and authentication class (1:2 verification, where n = 2).

In 1: m distinction logic (where m = number of enrolled end-users), identity of valid end-user is accurately determined among all other end-users. In 1:2 authentication logic (1st class valid user, 2nd class invalid user), identity of claimed owner of the device is determined. U-Stroke can produce raw events at every few milliseconds. One single operation generates a series of raw events to create secure hybrid profile of end-user (HPEU).

1:2 authentication logic can be processed on ubiquitous input device, depending on its capacity. Only owner's usage patterns are stored in short term memory of CCDA for verification. 1: n distinction logic is processed on web server, where usage patterns of n number of enrolled users are stored in long term memory of CCDA for verification. H2HV works in two phases-initial phase and verification phase.

Initial phase includes U-Stroke data acquisition task, multiple features extraction and processing, learning of data-set from environment and template generation. Verification phase includes U-Stroke data collection for claimed identity, multiple features extraction and processing, classification, fusion, match logic, decision logic. Capture process of CCDA model includes data acquisition task, multiple features extraction and processing, learning of data-set from environment and template generation of H2HV. Checking process of CCDA model includes classification, fusion, match logic. Decision process of CCDA includes decision logic and finally action needs to be taken according to security rule. Here main focus is given to data collection from touch screen enabled smart phones or tablets. However, U-Stroke pattern can be collected from any type of devices from traditional desktop computer to smart phone. timestamp -Absolute time of recorded action is measured in milliseconds. Timestamp depends on clock resolution of used devices [START_REF] Killourhy | The Effect of Clock Resolution on Keystroke Dynamics[END_REF].It is measured by Android API Date.getTime() [START_REF] Rogers | Android Application Development[END_REF]. Device clock is characterized by sampling rate of 1ms. position (X-coordinate, Y-coordinate) -On screen X-axis and Y-axis values of location of each touch point are recorded. When end-user touches the screen, one fin-ger_touch point (part of fingertip) is created. It is measured by Android API Im-ageView.getLocationOnScreen() [START_REF] Rogers | Android Application Development[END_REF]. pressure-Finger pressure ranges from 0 to 1. 0 implies no pressure and 1 implies normal pressure on the screen. However, few touch points hold the same value of finger pressure. Finger pressure force can be obtained by multiplying pressure and size of each touch point. It is measured by Android API Motion-Event.getPressure() [START_REF] Rogers | Android Application Development[END_REF]. To enhance usability of finger pressure data, values of pressure are expanded 1000 times. covered area-Part of fingertip touched on the screen is considered as size of fin-ger_touch point. It is measured by Android API MotionEvent.getSize().The area covered by fingertip varies with the size of the finger or type of the finger. Mapping of H2HV procedure with CCDA model is presented in table 1.

Multiple Features Collected for

Conclusion

Existing works focus on either traditional keystroke logic or touch-stroke logic. We are designing a system model, which is capable to identify user at any place. This paper determines various patterns to build strong hybrid profile of end-users that is capable to reduce false detection, which is very harmful in uncontrolled environment.

For touch stroke based authentication, multiple features are collected through userfriendly interface of Android device. This is useful to enhance the flexibility of enduser verification. Multiple features are processed separately and then fused to build user profile. Requirement of computational power is minimized by proposing CCDA model running on the background of limited resource mobile device. Proposed logic can process multiple features in a way that end-user can be identified accurately with less time and computational overhead. User profiles are frequently updated by selfloop. Procedural logic of proposed CCDA model is given in paper and result shows that owner of Spice Dual Core Phablet can be successfully identified through coarse grained features (along with fine grained features consideration) with high accuracy and less resource consumption. Detailed analysis is not given here due to shortage of space. Target of our proposed work is to apply end-user verification (H2HV) on cheap smart devices that can be used by any people within budget. Work is on to evaluate the performance of proposed model compared to other well-known works on this domain. Various security features, scalability, processor and memory overhead, battery consumption, and timeliness are also need to be considered to implement U-Stroke analysis in ubiquitous environment. Hopefully, direction of this research will be valuable for the further research on this domain.

Fig. 1 .

 1 Fig. 1. U-Stroke Pattern

Fig. 2 .

 2 Fig. 2. CCDA Processing Model for UID CCDA processing model of UID enables effective modeling of end-user's usage pattern from U-Stroke and creation of hybrid profile of end-user after extracting multiple features. Considering more than one feature can enhance accuracy level of classification. End-User's usage pattern is monitored multiple times to avoid malicious use. Less complex computation such as checking only device owner's validity can be performed through short term memory store (local). Short term memory can store device

  Capture Process of CCDA Model. At first, H2UID interaction captures U-Stroke data according to device usage. Event e in U-Stroke consists of multiple parameters. Capture process of CCDA processing model includes raw data collection. U-Stroke raw data includes {activity, timestamp, X-coordinate, Y-coordinate, pressure, area covered}. Figure 3 represents U-Stroke analysis framework to verify identity of end-user in ubiquitous environment.

Fig. 3 .

 3 Fig. 3. U-Stroke Analysis for End-User Identity Verification (H2HV)

Table 1 .

 1 Mapping of H2HV Procedure with CCDA Model

	begin
	check H2HV phase
	if H2HV phase:= initial then,
	enable CCDA(capture)
	else if H2HV phase:= verification then,
	enable CCDA (capture, checking, decision, action)
	if n=m in H2HV then, // n number of end-users needs to be
	checked for H2HV and m number of enrolled user
	activate 1:m distinction model
	else if n=2 in H2HV then,
	activate 1:2 authentication model
	end

Table 2

 2 represents procedural logic of CCDA model to identify end-users in ubiquitous environment through any device.

Table 2 .

 2 Procedural Logic of CCDA for H2HV Stroke or Z-Stroke with two fingers. It is seen from the collected raw data that there exists relation between two sets. Set 1 includes {activity, position (Xcoordinate, Y-coordinate), timestamp} and set 2 includes {pressure, area}. Set 1 is considered as fine-grained set, whereas set 2 is considered as coarse-grained set. Coarse grained set member "area" is proportional to finger-tip size of end-user. Fingertip size of thumb is greater than index. Frequency of use of thumb and index fingers are higher compared to other fingers. As multiple features are considered, FTA (failure to acquire) and FTE (failure to enroll) rate for H2UID interaction are almost equal to zero compared to other behavioral usage pattern analysis. However, probability of error for device usage (like V-Keystroke, W-Stroke, T-Stroke) is directly proportional to the size of fingertip. Fat finger also affects FTE and FTA parameters. Table3represents sample of U-Stroke raw data. Table4represents few strokes of U-Stroke pattern for user U1. To build strong profile of user U1 all raw data are collected such as T-Stroke, S-Stroke, and then are grouped according to type of stroke and are processed separately. Finally outputs of all features are fused to generate final decision.

	begin
	process capture()
	begin
	collect_UStroke(P-KeyStroke, T-KeyStroke)	// data collection
	aggregate X (activity, time, position x , position y , pressure, area) // data of
		raw event
	fragment X into {X 1 , X 2 , ...,X n } based on time // feature extraction and
		processing
	construct feature vector F
	fragment F into {f 1 , f 2 , ...,f n }
	map X {X 1 , X 2 , ...,X n } to F {f 1 , f 2 , ...,f n }
	learn_context ( CCDA self loop)
	find frequency (used pattern)
	store_template(F)
	update(CCDA feedback)
	if template_size<= local_storge then,
	encode and store (short_term_memory)
	else
	encode, transmitted through secure protocol and store (long_term_memory)
	end
	process checking()
	begin
	calculate_closeness (U, F) // U enrolled user's feature vector during veryfi-
	cation, F feature vector stored at template
	evaluate similarity_score() and assign to to s
	fusion()

Table 3 .

 3 U-Stroke Raw Data Collected from Two End-Users

Table 4 .

 4 Few Strokes of U-Stroke Pattern for User U1

	User-		Fine Grained Features			Coarse Grained
	ID							Features
		Activity	Timestamp	X-		Y-	Pressure	Area
			(ms)		coordinate		coordinate
	U1	0	4893336544	272		269	0.21	0.04444445
	U1	0.5	4893336790	262		271	0.32	0.04444445
	U1	0.5	4893336795	123		327	0.28	0.04444445
	U1	0.5	4893336952	98		336	0.17	0.13333336
	U1	0	4893337798	108		339	0.48	0.04444445
	U2	0	4626934695	138		242	0.71	0.15555558
	U2	0.5	4626934713	140		241	0.71	0.1777778
	U2	0.5	4626934727	180		225	0.71	0.20000002
	U2	0.5	4626934744	230		220	0.71	0.1777778
	U2	1	4626934790	293		216	0.55	0.13333336
		Stroke	Timestamp(ms)	X	Y	Pressure	Area
		T-Stroke	78864458	73 541	0.1	0.070588
		S-Stroke (right)	79073654	125 656 0.133333 0.109804
		S-Stroke (left)	79137343	433 595 0.133333 0.129412
		S-Stroke(up)	79107024	392 600 0.141176 0.133333
		S-Stroke (down)	79168990	405 351	0.2	0.160784
		W-Stroke	79203117	244 271 0.233333 0.156863
		Z-stroke	59021345	240 481 0.266667 0.133333
		P-Stroke	37581872	394 55 0.137255	0.2
	Compared to existing works [15, 16], proposed model works well by collecting heter-
	ogeneous data, reduces resource consumption by using CCDA model, and works well
	for low-cost devices for considering only basic sensor features. Here only 1:2 authen-
	tication model is considered, where user U1 is treated as valid end-user (owner) of the
	device, whereas user U2 is treated as invalid one. Figure 4 represents end-user identi-
	fication through coarse-grained features. It is seen that inter-user variability between
	user U1 and U2 is much higher than intra-user variability that can identify owner U1
	of Spice Dual Core Phablet efficiently.

Fig. 4. Coarse-grained Features for End-User Identification H2HV

Remote healthcare application is considered as a use case

[START_REF] Bhattasali | Bio-authentication for layered remote health monitor framework[END_REF]

of our proposed work. In this case, data owner (patients or local caregivers) can use smart device to upload health related data towards remote web server or cloud server. Similarly healthcare professionals from remote locations can access health related data of patients through smart devices at any time. Here authentication through ubiquitous input device is most important step to validate remote health service. Our proposed model works on this direction.

Acknowledgement

This research work was partially supported by University of Calcutta grant no. UGC/452/DST Purse and Bialystok University of Technology grant no. S/WI/1/2013.


Teodora Dimitrova-Grekow

Marcin Jarczewski
email: m.jarczewski@o2.pl

Identification Effectiveness of the Shape Recognition Method based on Sonar

Keywords: shape recognition, sonar signal, features extraction, signal analysis, mobile robotics

Sonars are among the most popular navigation elements used in autonomous vehicles. Beside their well known properties, they have unexplored specifics offering interesting information. In this paper, we present the results of an experiment with the drawbacks of sonars. Our approach combined the regular information obtained from a sonar system with information deriving from measurement aberration. The experiments with an ultrasonic range measurement system of a mobile robot showed that the usually neglected sonar drawbacks could be unusually helpful. This paper emphasizes the effectiveness of identification, which was calculated based on the ratio of the quantities of parallelepipeds to cylinders. The experimental results are presented. Further work aims to implement this idea on a robot on an HCR base. Another possibility is also suitable implementation of map building with a relative degree of confidence.

Introduction

Sonar sensors are famous for their robustness and unambiguous acting for quite narrow and strictly defined work conditions. To obtain satisfying accuracy in distance measurement, one has to pay attention mainly to the applied sensor, the send signal, and the method of processing the received echo-information. All attempts to identify objects using sonar have to deal with the following problems:

physical properties of objects: size, shape, material of which the object is made, the surface of the object; relationship between the sensor and the object, such as distance, angle; complexity and number of objects to recognize; repositioning, the physical properties of objects at a time; external factors, such as temperature and humidity.

The most common way to use ultrasonic sensors today are sonar arrays, containing from 3 to 16 and more sensors. In contrast to a quite irrelevant, single sonar sensor measurement, a data sequence from a sonar array allows compensation of the drawbacks of the acoustic signals to some level. In this paper, we present a complimentary attempt: in addition to the classical signal recovery and ridding of bad echoes, we sorted them and brought them into use. In our experiment, we tested shape distinguishing using simple objects, such as cylinders and parallelepipeds. A set of shape recognition rules was set and implemented in a real-time system: NXT robot. The tests have proved the off-line assumptions and calculations.

An important aspect of the study was to estimate the possibility of not only identifying the objects, but also their exact orientation and collocations. Hence, building maps to a relative degree of confidence [START_REF] Dimitrova-Grekow | A hybrid algorithm for self location[END_REF] is a future aim.

Related Work

The most popular uses of ultrasonic signals are distance establishment and obstacle detection [START_REF] Castilloa | A sonar approach to obstacle detection for a vision-based autonomous wheelchair[END_REF], localization [START_REF] Choi | Autonomous topological modeling of a home environment and topological localization using a sonar grid map[END_REF] and avoidance [START_REF] Lenser | Visual sonar: Fast obstacle avoidance using monocular vision[END_REF]. It should not be forgotten, though, that sonar sequences contain much information about the environment [START_REF] Ohtani | Shape recognition for transparent objects using ultrasonic sensor array[END_REF] from such sources as inferential echo signals from all possible reflection surfaces in the environment the robot is acting in [START_REF] Kiyoshi | Obstacle arrangement detection using multichannel ultrasonic sonar for indoor mobile robots[END_REF].

Although the sonar possesses a set of well known advantages, such as its wide accessibility, relative good accuracy and low costs, its main disadvantage are connected with the conical emission area of the signal. That is the orgin of faked measurements occurring in the signal sequences. The more complex the structure of the environment, the more additional complicating and disturbing echoes arise. That complicates too much for direct use of sonar data for object recognition or topological localization. An well-known way to solve these problems is using neural networks [START_REF] Vossiek | An ultrasonic multi-element sensor system for position invariant object identification[END_REF], [START_REF] Dror | Three-dimensional target recognition via sonar: a neural network model[END_REF], [START_REF] Kuc | Biomimetic sonar locates and recognizes objects[END_REF], genetic algorithms [START_REF] Baba | 3D shape recognition system by ultrasonic sensor array and genetic algorithms[END_REF], Fuzzy Artmap [START_REF] Streilein | A neural network for object recognition through sonar on a mobile robot[END_REF], Hough transform [START_REF] Yap | SLAM in large indoor environments with low-cost, noisy, and sparse so-nars[END_REF] or an extended Kalman filter [START_REF] Joong-Tae | Sonar Sensor-Based Efficient Exploration Method Using Sonar Salient Features and Several Gains[END_REF]. Researches involved the analysis of a two objects based on Continuously Transmitted Frequency Modulated ultrasonic sensor [START_REF] Worth | An approach to object recognition using CTFM sensing[END_REF].

All these methods require quite many calculations and the real-time work of sonar-based systems at times significantly slows down. But on the other hand all these approaches consider only ultrasonic echoes, neglecting measurements in which a non echo comes back etc.

In our work, we took into account not only the 'regular' information, delivered from sonar sensors, but also 'hidden' information. We acted on signal features, which were the result of the specific interaction between the sonar sensor and certain objects. In comparison to the mentioned methods, we used minimal computation, simultaneously keeping a very high identification effectiveness of shape recognition.

The first information about use of sonar shortcomings are described in [START_REF] Dimitrova-Grekow | Sonar Method of Distinguishing Objects Based on Reflected Signal Specifics[END_REF]. In this article, we present enriched experience and extended explanation of the identification effectiveness using our shape recognition method.

System Structure

We present a complimentary attempt: beside the classical signal recovery and ridding of the bad echos, we sorted them and brought them in use. In our experiment, we tested shape distinguishing using simple objects, such as cylinders and parallelepipeds. A set of shape recognition rules was set and implemented in a real-time system: NXT robot. Each of the mobile robots was used as an independent data collecting vehicle. So far, the tests have proved the offline assumptions and calculations.

Considering the specificity of sonar signals, the first stage of research involved data processing (Fig. 1). The information gathered from the sonar system was treated in different ways while searching for the most relevant interpretation. The robot route is straight passing beside the obstacles. The robot maintains a path parallel to the wall.

Observing the collected data gathered from the sonar sensors, we noticed a number of interesting dependencies between the received reflections and the history of scanning. Finally, a set of object features enabling effective object recognition emerged. This can be considered the separate second stage of the study. The most essential features are described in the next section. We used a simple set of objects: two types of solids -parallelepipeds and cylinders. The tests shown in the third section were done on several different sizes of each type. The final, third stage of our system was developing recognition rules, which had been applied to the real-time test vehicle and proved the primary idea -to get more than the usual noise using only very simple tools.

In our experiments, we achieved over 80% accuracy in shape recognition. The experimental results are shown in the last section. The further work aims an implementation in mobile robot localization. A hybrid location method is being developed to test the pattern recognition approach in real-time conditions. Its main point is building a relative confidence degree map to defining the vehicle location. The method is described generally at the end of the article.

Simple Shape Recognition Method

The most common approach to shape recognition is to consider shape context. The features used in this methodology are based on complex data related directly to the analyzed objects. We present a shape recognition method that also uses indirect data, such as reflections, which we called "glitters" in this paper. To implement our approach, we consider the following steps: (1) primary data collection, (2) initial features extraction, (3) final features extraction (4) shape recognition rules building.

For all these phases, the robot passed a distance D scanning the environment along its path and gathering data (Fig. 1).

Primary Data Collection

Walking a certain distance, the experimental vehicle collects a set of distance measurements. The raw data are processed twice: a First, the raw sonar data it was smoothed so that the registered shapes became sharper and more reliable. The results of this smoothing was very appreciable and observable if one visualizes the data stream.

b Simultaneously, all data exceptions and irregularity were counted exactly, related, and compared.

All data irregularities were removed (Fig. 2). Among the registered values, there were many 'glitters' -reading exceptions observed by comparison with neighboring ones. Their quick smoothing facilitated further processing of the received signal. Simultaneously, these irregularities were statistically assessed.

Initial Features Extraction

The first features extraction was based on regularly shaped data, obtained from double smoothed sonar sequences. The secondary correction was focused on larger 'exceptions' and smoothing of the discovered shapes (Fig. 2). The socalled 'exceptions' were a result of overlapping echoes from various objects and measurements made in sequence. This will be especially useful in the future development of the system in the navigation area.

The very first phase of the research used a single object scene: the robot scanned and saved data from a single object. It was indispensable to extract all the necessary information for effective object recognition. After many observations, based on the acoustic rules and simplification derived from the chosen work conditions, several important dependencies were found. The adjustment scheme was empirically determined during the experiments and was part of a continued refinement-cast. The primary consideration allowed to appoint one of the most important features, used in further features determination.

Minimal measured distance: D M IN The meaning of this parameter is useful for detecting if it is an edge, side or cylinder. The minimal value itself is very important, but it becomes meaningful only after colligation with 10 to 30 contiguous distances.

Final Features Extraction

The main idea of our approach is based on investigating the irregularities in sonar measurements, taking into account the sequences in which they appear and the rules of this irregularity. The extracted features were used for building the shape recognition rules. Every file with data saved from the sonar was interpreted as a vector. The most important selected characteristics were:

Wall-greater distances: D OV -percentage of measurements greater than the distance to the wall N W

The source of such values can be different: NXT sonars use value '255' as an error measurement; normally it should mean 255 cm, but in fact it means non-response was registered; even if the obstacle is so near that the reflections of the send signal cannot reach the receiver. The total value of D OV is calculated as follows:

D OV = (N 255 + N GW ) N (1)
Where:

N 255 -number of '255' values, N GW -number of values greater than the distance to the wall, N -total number of measurements.

Alien echos: D N R -percentage of measured distances less than N W although no object is displaced at the spot Obviously, this is the result of delayed or side reflections:

D N R = N LLW N (2)
Where:

N LLW -number of values less than the distance to the wall, cached in the object's free space.

Shape Recognition Rules

A set of D N R = f (D OV ) characteristics for ca. several hundred vectors were built. Some of them will be shown in the next section. A linear dependence (Fig. 3), which was implemented and loaded on the robot for online tests, resulted from the characteristic families. This is the most important, next to the extraction of features, step in the process of object recognition. When the optimal set of features has been selected, it is time to create a classifier. There are three different methods:

1. The concept of similarity -the simplest and most common approach, known as 'template matching'. 2. Probabilistic approach: includes methods based on the Bayesian decision rule, maximum likelihood or density estimation.

Building of decision limitations based on optimizing some error criteria:

Fisher's linear discriminant, multilayer perceptions, decision tree.

Our approach was based on the first method. We studied the features extracted out in the previous subsection, as well as their behavior and relations to each other. This allowed us to discriminate parallelepipeds and cylinders with minimum calculations. An optimization of these observations is proof of the simple reliance between D OV and D N R . Example of the dependency D N R = f (D OV ) is visualized in Fig. 3. The optimal clustering generated a linear function which was different for every group of objects. In fact, a rule generalizing these differences can be found. Objects clustering was determined by linear function F CL (x) = ax + b. Points located on the same side of the line belong to the same cluster.

Finding the best function consists of several steps:

1. Defining points in a certain distance from each other on the x and y axes: the parameters D OV and D N R got integer values from 0 to 100. Thus, we assumed that if the distance between two points is greater than 1, it is a sufficient condition to set an optimal line. 2. Then, a collection of lines for each of these points is appointed. Or for each point a dozen simple lines are determined. They all differ by a factor. The difference between the lines is 2. In a single group, at least a few thousand had been checked. 3. By evaluating the test collection, the best of the lines was selected.

Identification Effectiveness

Because of observations of various orientations of the parallelepipeds, the difference in the number of scanned cylinders and parallelepipeds was significant. Therefore, in order to ensure objective evaluation, a secondary factor S was introduced, depending on the total number of cylinders C, and the total number of parallelepipeds P . In this way, we could save the S = P/C. Thanks to the difference in the number of measurements, it will not affect final effectiveness.

The effectiveness of R identification was calculated based on the ratio of the quantity of parallelepipeds to cylinders on the same side of the line. Indexes O stand for objects over the line and U for those under. So, for both cases R U and R O we obtain:

R U = S U (S U + C U P ) (3)
R O = C O P S O + C O P (4)
Hence, we get R 1 :

R 1 = (R U C U P + S U S + C + R O C O P + S O S + C )100 (5)
Later, you could make the opposite assumptions that under the line there are cylinders and over parallelepipeds:

R 2 = 1 -R 1 (6)
And finally:

R = max(R 1 , R 2 ) (7)

Tests and Experimental Results

Through the experiments we conducted, we found that the most appropriate way to obtain satisfactory and relevant shape recognition requires splitting the measurements into several groups, considering the minimum read distance. This range clustering was determined during the hundreds of tests. We generalized several variants considering the specific effectiveness for separate distance fractions and the complex effectiveness for the total experiment.

Here we present an optimal division of the distance ranges, where the complex effectiveness manifest stability. Groups, to which we assigned individual points were: a) 8 -25 cm, b) 26 -40 cm, c) 41 -60 cm, d) 61 -80 cm, e) 81 -120 cm.

In the realization of this study, we conducted over 500 tests divided into two sets:

-Teaching set -used exclusively for deriving proprer clustering for the objects, -Testing set -serving only for the evaluation of clustering effectiveness. The results of the clustering function derive are shown as a set of graphs. The tests, repeated several hundred times, proved the calculated accuracy. When interpreting them, you should take into account that for the largest distances (> 100cm) most of the test objects were hardly 'visible' thus parameters D OV and D N R were almost the same. Figure 4 shows the end selected separating lines or clustering function F CL () for all five distance groups. The dependency between the function parameters are not the center of attention for this issue. To make things more clear, X-points are all unrecognized or incorrectly recognized figures.

The lowest effectiveness of the clustering function F CL () was 74.05% -refers to the nearest group of objects (Fig. 5). Its main weaknesses were parallelepipeds parallel to the robot path. The best effectiveness 96.15% was reached in the third group 41-60 cm. The linearity is changing is non linear, but possesses a logical rule: The hardware unfortunately disallows work with longer distances. The focus of this paper was identification effectiveness, which was calculated using the ratio of the number of parallelepipeds to cylinders. We considered not only the 'regular' information, delivered from sonar sensors, but also 'hidden' information and acted on signal features, which were the result of the specific interaction between the sonar sensor and certain objects.

The results of our experience with sonar drawbacks substantiate the developed method of simple shape recognition. Our approach combines the regular information obtained from the sonar system with measurements of aberration derivative. This original approach minimizes calculations for real-time implementation.

We presented a shape recognition rule: linear function F CL () expressing the dependencies between the sonar signal features in the described conditions. The average accuracy we achieved was 86.28%. The tests on the robot Lego Mindstoms NXT proved the effectiveness of function F CL ().

Our further plans are to find general rules for shape distinguishing and also position recognition, which we partly touched on in our studies.

We intend to explore new features based on acoustic signal dependencies and additionally to increase the number of ultrasonic receivers. Further work also aims to use a new mobile robot on the HCR base, which will allow to implement this shape recognition method in building building a relative degree of confidence maps.

Fig. 1 .

 1 Fig. 1. Stages of the system

Fig. 2 .

 2 Fig. 2. Raw sonar measurements and real objects

Fig. 3 .

 3 Fig. 3. Distinguishing parallelepipeds and cylinders

Fig. 4 .

 4 Fig. 4. Clustering functions for different data groups: a) 8-25 cm; b) 26-40 cm; c) 41-60 cm; d) 61-80 cm; e) 81 -125 cm

Fig. 5 .

 5 Fig. 5. Effectiveness for the distance groups

Acknowledgments. This paper is supported by the S/WI/1/2013.


Rahma Boucetta
email: boucetta.rahma@gmail.com

Telerobotic Surgery: Fuzzy Path Planning Control for a Telerobotic Assistant Surgery

Keywords: Telerobotic Surgery, Dynamic Model, Path Planning, Fuzzy Logic, Laparoscopic Surgery

A strategy of path planning with fuzzy logic for a telerobotic assistant surgery is presented in this paper. Telerobotic surgery occurred a long track in its short history. While teleconsultation proceeds to be used today, the advent of high speed communications and increased computational competence is making long distance remote control of operating instruments, called telepresence surgery, a reality. Based on laparoscopic technology, telerobotic surgery was tested first on animals and, more recently, on humans with success. The technology offers several advantages, including improved accuracy and the capability to bring difficult procedures to rural and remote locations where trained surgeons are not available. A dynamic model is computed first for the telerobots using Lagrange formulation. A fuzzy control strategy is used in order to validate the path planning method and the theoretical developments in motion constraints analysis. The paper is ended with a conclusion.

Introduction

Surgery has evolved from the early rough days of trepanation and battlefield amputations to modern procedures such as complex neurosurgeries and minimally invasive laparoscopic interventions. However, the surgeon is virtually useless without his tools, and it is perhaps the development of these tools, which has directly lead the evolution of surgery. While several tools such as scalpels, stitches, loops, anaesthesia and antiseptics have each amplified the set of possibilities for procedures, some of the newest tools to enter the surgical instrumentation are robots and computers. While the advantages of computer and robotic assistance in surgery, in terms of improved accuracy and control may seem evident, one of the most interesting and useful applications of this technology is to perform surgeries remotely. Patients in rural and remote locations often do not have access to advanced surgical care due to an absence of qualified personnel [START_REF] Anvari | Reaching the rural world through robotic surgical programs[END_REF]. This is the case in both wartime battlefields and third world countries, and many remote areas as Canada country. Surgical care in these emplacements is either impossible or requires transportation to an urban center upon long distances. The prime essays at remote care were really what would be appealed teleconsultation. The 1960s saw the beginning of electronic transmission of radiological films, while the 1970s brought the ability for medicaster to consult with experts remotely over video-conference systems [START_REF] Benger | A review of telemedicine in accident and emergency: The story so far[END_REF]. In a surgical implementation of teleconsultation, a remote video-conferencing system was set up in the operating room and was linked to an expert physician at an urban center [START_REF] Rovetta | Remote Control in Telerobotic Surgery[END_REF]. This apart surgeon did not actively participate in the process, but instead suggested advice or guidance to the attending surgeon at critical points. At best, electronic remote control of the video camera was available, but little else. While accurate benefits in terms of transmitting expertise and training inexperienced surgeons could be realized with this setup, true remote surgical control was impossible. This changed with the advent of a robotic system tested at assisting in laparoscopic procedures. Laparoscopic surgery uses a miniature camera (i.e., laparoscope) and small surgical tools which are introduced into the body via tiny incisions and controlled through external manipulators. Minimally invasive surgery performed using laparoscopy provided various advantages to the patient : less pain, a shorter hospital stay, better cosmetic outcome and faster recovery [START_REF] Broeders | Robotics revolutionizing surgery: the Intuitive Surgical[END_REF]. Unfortunately, this surgical technique, in its original conception, had several shortcomings. The laparoscope produced only a 2-dimensional view of the surgical area, and hand-eye coordination was difficult due to the need to look at a monitor instead of ones hands. Even, the laparoscope was held by an assistant, and therefore direct was taken out of the hands of the surgeon. Perhaps most importantly yet, laparoscopy, by its very nature, introduced amplification of vibration, loss of degrees of freedom (dof) in manipulation, and the brought the requirement for making non-intuitive motions when performing a process [START_REF] Broeders | Robotics revolutionizing surgery: the Intuitive Surgical[END_REF]. To cross the inherent limitations of laparoscopic surgery, research supported by the US Defense Departments Star Wars program was undertaken in the early 1990's to develop a master-slave tele-manipulator, consisted on a computer and robotic instrumentation intervened between the surgeon and the patient [START_REF] Broeders | Robotics revolutionizing surgery: the Intuitive Surgical[END_REF]. The original goal of this technology was to allow actual manipulation of surgical instruments by telepresence surgery [START_REF] Bowersox | Use of an intuitive telemanipulator system for remote trauma surgery: An experimental study[END_REF]. This technology is hoped to be useful in performing remote trauma surgeries on the battlefield or outer space, where surgeons could not venture [START_REF] Bowersox | Use of an intuitive telemanipulator system for remote trauma surgery: An experimental study[END_REF]. Unfortunately, while a system was developed, it missed the required dof necessary for efficient surgery, and its large size stopped expanded use. In 1994, a private company developed the da Vinci robot system. This robot builds on traditional laparoscopic technology, rectifying some of its faults while introducing the capacity for remote manipulation. The first refinement is that the camera platform is stable, and can be controlled by the surgeons feet or voice commands, eliminating the need for an assistant. Second, visualization is greatly enhanced with a 3-dimensional magnified system to simulate natural vision, or alternately 2-dimensional displays positioned near the hand controls [START_REF] Costello | Installation of telerobotic surgery and initial experience with telerobotic radical prostatectomy[END_REF]. Moreover, since physical manipulation of the controls is processed by a computer, shaking can be digitally filtered out preventing excessive error. Finally, the use of motion scaling, which reduces large movements to fine ones, allows surgeons to perform actions which were previously impossible due to their delicacy [START_REF] Costello | Installation of telerobotic surgery and initial experience with telerobotic radical prostatectomy[END_REF]. Early telepresence surgery research was extremely limited, and being hampered by technical limitations, was carried out only on animal models. Advanced manipulation techniques were not possible due to lack of adequate computational power and communication bandwidth. An early procedure was performed in 1993 by issuing keyboard and mouse commands to manipulate an echographic sonde, biopsy needle and scalpel over a transatlantic fiber optic telephone link to remove a cyst from a pigs liver. Unfortunately, transfer of real-time video over the wired network was technologically impossible at the time due to bandwidth constraints; consequently, relatively expensive satellite links were required [START_REF] Rovetta | Remote Control in Telerobotic Surgery[END_REF]. One of the leading difficulties in developing clinically viable telerobotic surgery has been the requirement of minimal time lag between the issuing of commands, actual surgical action, and reception of visual confirmation on the screen. This lag is influenced by multiple factors including time required for converting video and movements into the appropriate signals and the inherent delay in the communication network itself. Experiments have determined that the acceptable limit for safe surgery is 330ms [START_REF] Marescaux | Transatlantic robot-assisted telesurgery[END_REF]. Even with the satellite video link in early experiments, overall delays of approximately 2s [START_REF] Rovetta | Remote Control in Telerobotic Surgery[END_REF] were inherent in the technology, obviously far from acceptable for a real-time surgical procedure. Accordingly, it was estimated that feasible distances for remote surgery could not exceed several hundred kilometers [START_REF] Marescaux | Robotic surgery: potentials, barriers and limitations[END_REF]. This was, however, disproved in subsequent years. This paper is composed of the following sections : after an introduction, the dynamic model is computed in the second paragraph using the Lagrange equations. The development of a fuzzy path planning control is given by the next section to analyse the telerobotic surgery behavior. the paper is ended with a conclusion.

2 Dynamic Modelling of the Surgical Robot

Concepts

Safety, control convenience, and flexibility for use in an ample variety of surgical applications were important factors in determining the manipulator design. In laparoscopic applications, rigid instruments are inserted into the patient's body through small cannulas slotted into the abdominal wall. This settlement creates a swivel effect, so that the instrument has only four significant motion dof (three rotations and depth of penetration) centered at the gate. Only very constrained lateral motions are acceptable. If a robot is keeping an instrument, its motions obey these constraints, necessary. A conventional industrial robot can, of course, be programmed move an instrument about such a fulcrum. Unfortunately, such motions usually require a lot of manipulator joints to make large, tightly coordinated excursions. Thus, even relatively slow end-effector motions can require rapid joint motions. Any control or coordination failure can thereby represent a potential safety hazard both for the patient and for the surgeon. Simply slowing down the actuators can cause the entire functioning of the robot to be painfully boring. Consequently, manipulator designs that require only low velocity actuation are preferred, they do not have motion singularities in the normal working volume, and permit simple stable controls. Similarly, the motions required to perform a task should be reasonably intuitive for the surgeon. Even if the control computer is handling all the details, it is desirable not to surprise the surgeon with unanticipated complex motions. Finally, a great agreement of modularity allow us to reconfigure the system for different procedures. The 4 dof Robotic Arm chosen in our study delivers fast, accurate, and repeatable movement. The robot features are the Z-base rotation, the single X-plane shoulder, the X-elbow, the X-wrist motion, and a functional gripper. The dynamic model of the surgical robot was developed using the Lagrange formulation. The robot is described by Figure 1, using a right-handed inertial frame (B 0 -f rame) represented by (X 0 , Y 0 , Z 0 ), and three right-handed body frames (B i -f rame) represented by (X i , Y i , Z i ), where i is the number of dof i = 1..4. The positive direction of the first angle θ 1 is decided by a right handed rotation about positive Z axis, the others angles θ 2 , θ 3 and θ 4 are about X axis respectively.

Each vector V 0 in the B 0 -f rame can be transformed into a vector V i in the B i -f rame by the following relation where R 0,i is the rotation matrix of the B i -f rame relative to the B 0 -f rame determined as

q 0 = R 0,i .q i (1)
R 0,1 =   C 1 -S 1 0 S 1 C 1 0 0 0 1   , R i,i+1 =   1 0 0 0 C i+1 -S i+1 0 S i+1 C i+1   (2)

Dynamics

The dynamic behavior can be generated using the Lagrange formulation given by the expression as

d dt ( ∂L ∂ qi ) - ∂L ∂q i = Γ (3)
where L, the lagrangian, that is the difference between kinetic and potential energies given by L = T -V . T is the kinetic energy of the overall system and V is the potential energy due to the internal deformation of the robot that is equal to zero. So, the Lagrangian becomes equal to the sum of the kinetic energies of the moving bodies. The kinetic energy of each body with mass M i has the general expression as follows

T i = 1 2 (M i V 2 Gi + Ω T i I (i) Ω i ) (4)
where V Gi is the translation velocity vector of the center of inertia of the moving link i and has the following form

V (0) Oi+1 = V (0) Oi (R i ) + Ω (0) i (R i ) ∧ ----→ O i O i+1 (R i ) (5)
and Ω (0) i (R i ) is the rotation velocity vector given by

Ω (0) i (R i ) = Ω(i-1) i (R i-1 ) + [R i-1,i ] T Ω (0) i-1 (R i-1 ) (6)
The dynamic model can be deduced from the computation of the kinetic energies and the derivation of Lagrange equations. It has the following expression

M θ + K θ2 + C θ θ = Γ (7)
where M , K and C are the inertial, centrifugal and coupling forces matrices, respectively. To simulate the surgical robot model, the real dimensions values are given as L 2 = 0.175m, L 3 = 0.28m, M 2 = 0.64kg, and M 3 = 0.6kg.

Fuzzy Path Planning Control

A fuzzy controller (FC) consists of a set of linguistic conditional statements that are derived from human operators, and which represent knowledge about the system being controlled. These statements define a set of control actions using if-then rules. The FC can be considered as a fuzzy reasoning process to manifest itself in the form of qualitative information about the process, and this information is articulated in the if-then rules, [START_REF] Passino | Fuzzy Control[END_REF]. The first step to be performed by the FC is to fuzzify each input, which is done by associating each input with a set of fuzzy variables. In order to give semantics of a fuzzy variable a numerical sense, a membership function is assigned to each variable. The form of a membership function can be either discrete or continuous, and its range is varied from zero to one. Two types of continuous membership functions commonly adopted in fuzzy logic control are triangle and exponential forms. Fuzzified inputs are then associated with knowledge base of the fuzzy controller, containing a set of control rules. By matching the fuzzified inputs with each control rule activates a set of control actions. Since the control actions are in the fuzzy sense, defuzzification is required to transform fuzzy control actions into an exact output value of the controller, [START_REF] Passino | Fuzzy Control[END_REF].

3 illustrates the block diagram of a direct fuzzy controller applied to the flexible manipulator. Control rules process the error between hub angle and its desired value (e) and the change in error (ce) to synthesize a change in control for improving system performance and vibration suppression. Membership functions are chosen triangular and symmetric. The universes of discourse are divided to 7 fuzzy sets for the inputs and 7 fuzzy sets for the output and chosen between [-1, +1]. So, scaling gains are introduced to normalize the control system. Knowledge rule-base is composed of 7 × 7 = 49 rules.

Simulation Results

The models of master-slave surgical robots are inserted in a simulink file. The fuzzy controllers are then established and placed in the closed loop of the robots. The consign signals are chosen to put the end-point in a desired position. The slave receive the same information after a second. Simulation results are given by the next figures 4, 5 and 6. The first Z-angle θ 1 for the master and the slave robots are stables and reach consign slowly without overshoots. The second X-angle θ 2 is more fast for the master robot and slow with some fluctuations for the slave robot. The third X-angle θ 3 is very fast with some overshoots for the master robot, and slow and stable for the slave robot. The slave robot easily pursuit the master robot in its path planning in spite of the delay between the robots operations.

Conclusion

This paper deals with telerobotic surgery. The main task is to determine a dynamic model of a serial surgical robot using the Lagrange formulation. A fuzzy path planning control is then developed to command a master-slave robot for a surgery application. Simulations results are given to compare different outputs variations. This work can be improved with other types of controllers and real environment in the near future.

Fig. 1 .

 1 Fig. 1. 4-dof Surgical Robot architecture.

Fig. 2 .

 2 Fig. 2. Cinematics of the Surgical Robot.

Fig. 3 .

 3 Fig. 3. Diagram of Fuzzy Controller.

Fig. 4 .

 4 Fig. 4. Responses and first angle θ1.

Fig. 5 .

 5 Fig. 5. Responses and second angle θ2.

Fig. 6 .

 6 Fig. 6. Responses and third angle θ3.