Liu Xue
email: liuxue@nuaa.edu.cn

Tan Xiaoyang

Chen Songcan

Eyes Closeness Detection Using Appearance Based Methods

Keywords:

Human eye closeness detection has gained wide applications in human computer interface designation, facial expression recognition, driver fatigue detection, and so on. In this work, we present an extensive comparison on several state of art appearance-based eye closeness detection methods, with emphasize on the role played by each crucial component, including geometric normalization, feature extraction, and classification. Three conclusions are highlighted through our experimental results: 1) fusing multiple cues significantly improves the performance of the detection system; 2) the AdaBoost classifier with difference of intensity of pixels is a good candidate scheme in practice due to its high efficiency and good performance; 3) eye alignment is important and influences the detection accuracy greatly. These provide useful lessons for the future investigations on this interesting topic.

Introduction

As one of the most salient facial features, eyes, which reflect the individual's affective states and focus attention, have become one of the most important information sources for face analysis. Efficiently and accurately understanding the states of eyes in a given face image is therefore essential to a wide range of face-related research efforts, including human computer interface designation, facial expression analysis, driver fatigue detection [START_REF] Noor | A framework for measurement of humans fatigue level using 2 factors[END_REF] [START_REF] Eriksson | Eye-tracking for detection of driver fatigue[END_REF], and so on.

However, this task is challenging due to the fact that the appearance of eye regions can be easily influenced by various variations such as lighting, expression, pose, and human identity. To meet these challenges, numerous eye closeness detection methods have been proposed during past few decades [START_REF] Mitelman | A noninvasive, fast and inexpensive tool for the detection of eye open/closed state in primates[END_REF][4] [START_REF] Valenti | Accurate eye center location and tracking using isophote curvature[END_REF][6] [START_REF] Jiao | Real-time eye detection and tracking under various light conditions[END_REF][8] [START_REF] Li | Illumination invariant face recognition using near-infrared images[END_REF]. The ideas of these methods can be roughly categorized into two types, i.e., detecting the closeness of eyes directly through various pattern recognition methods or doing this indirectly by checking whether the eyes are actually open. Since an open eye in general exhibits more appearance evidence (e.g., visible iris and elliptical shape of eyelids), most methods (e.g., [START_REF] Wang | A novel approach for real time eye state detection in fatigue awareness system[END_REF][7] [START_REF] Orozco | Real-time gaze tracking with appearance-based models[END_REF]) understand the state of the eyes using this later philosophy, i.e., if the local evidence collected from the image supports the conclusion that the eyes are open, then they must be not closed. However, methods in this line may have their own problems. For example, for some subjects, their irises may be largely occluded by their eyelids. As a result, it would be very hard to reliably detect irises under this situation [START_REF] Valenti | Accurate eye center location and tracking using isophote curvature[END_REF].

In this paper, we adopt the first philosophy, i.e., detecting whether the eyes are closed directly using their appearance evidence. The major advantage of this lies in its efficiency and robustness [START_REF] Liu | Automatic eye state recognition and closed-eye photo correction[END_REF] [START_REF] Dehnavi | Design and implementation of a real time and train less eye state recognition system[END_REF]. Current development in computer vision has allowed for robust middle-level feature description for eye patches despite of various changes in appearance, and the remaining variations can be addressed with powerful machine-learning-based classifiers. However, this appearance-based strategy can be implemented in numerous ways and involves many practical considerations. Therefore, an evaluation of popular methods for eye closeness detection is needed.

The major contribution of this paper is to make an extensive comparative study on this approach from the engineering point of view. In particular, we investigated in-depth the influence of several crucial components of an eye closeness detection system, including eye patch alignment, feature extraction and classifiers. Four types of representative feature sets including gray-values, Gabor wavelets, Local Binary Patterns (LBP, [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF]), Histograms of Oriented Gradient (HOG, [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) are compared with respect to three types of classifiers, i.e., Nearest Neighbor (NN), Support Vector Machine (SVM) and AdaBoost on a large benchmark dataset. Both LBP and Gabor feature sets have been used for eye representation before [START_REF] Cheng | Eye state detection in facial image based on linear prediction error of wavelet coefficients[END_REF][15] [START_REF] Wang | Eye location and eye state detection in facial images with unconstrained background[END_REF] but HOG not. However, since these features represent different characteristics (local texture, global shape and local shape, respectively) of eyes, it is beneficial to use all of them. Indeed, our experimental results show that fusing various feature descriptors significantly improves the performance of eye closeness detection. In addition, we also show that properly eye patch alignment is important for the performance. These provide useful lessons for the follow-up investigations on this interesting topic.

Overall Architecture of Our System

The overall pipeline of our eye closeness detection system is given in Fig. 1. For a given test image, we first detect and crop the face portion using the Viola and Jones face detector [START_REF] Viola | Robust real-time face detection[END_REF], then the eyes are localized using the method introduced in [START_REF] Tan | Enhanced pictorial structures for precise eye localization under incontrolled conditions[END_REF]. After this, we crop the eye region and align it with those in the training set with method of [START_REF] Huang | Unsupervised joint alignment of complex images[END_REF]. On the aligned eye patch various feature sets are extracted and input into the classifier for final decision.

One of the key components of our system lies in the inclusion of eye patch alignment module. This is based on the observation that eyes in a face image may undergo various in-plane/out-of-plane pose changes, or scale changes. Although some feature descriptors are not sensitive to these, other feature sets (e.g., LBP, Gabor wavelets, and HOG) don't have built-in mechanism to handle such variations. Therefore, performing geometric eye normalization is necessary for these descriptors. However, one difficulty for this is that it is hard to find anchor points for eye patches and hence traditional anchor-points-based alignment method can not be applied. Here we adopt an information-theory geometric normalization method originally proposed for medical image registration, i.e., the congealing method [START_REF] Huang | Unsupervised joint alignment of complex images[END_REF]. This is an unsupervised image normalization method which learns a particular affine transformation for each image such that the entropy of a group of eye images is minimized. Fig. 2 gives some illustrations of eye patches normalized using this method, from which we can see that the locations of eyes are centered and their sizes are scaled. LBP Feature Local Binary Pattern (LBP) proposed by Ojala [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] is widely used feature descriptor for local image texture. The LBP descriptor has achieved considerable success in various applications such as face recognition and texture recognition, due to its capability to efficiently encode local statistics and geometric characteristics (e.g., spot, flat area, edge and corner) among neighborhood pixels and its robustness against noise by picking up only 'uniform patterns' for feature description. In this paper, we partition each 24 × 24 eye patch into 6 × 6 blocks and represent each block as a 59-dimensional histogram. Therefore for each eye patch we have a 944-dimensional LBP vector (16 × 59).

Gabor Wavelets Gabor wavelets were originally developed to model the receptive fields of simple cells in the visual cortex and in practice they capture a number of salient visual properties including spatial localization, orientation selectivity and spatial frequency selectivity quite well. They have been widely used in face recognition. Computationally, they are the result of convolving the image with a bank of Gabor filters of different scales and orientations and taking the 'energy image' (pixelwise complex modulus) of each resulting output image. The most commonly used filters in face recognition have the form,

Ψ µ,ν (z) = k µ,ν 2 σ 2 * exp(- k µ,ν 2 * z 2 2σ 2 ) * [exp(ik µ,ν, * z -exp(- σ 2 2 ))] (1)
where µ and ν define the orientation and scale of the Gabor kernels, z = (x, y), denotes the norm operator, and the wave vector k µ,ν is defined:k µ,ν = k ν e iϕµ , where k ν = k max /f ν and ϕ µ = µπ/8. k max is the maximum frequency, and f is the spacing factor between kernels in the frequency domain [START_REF] Lades | Distortion invariant object recognition in the dynamic link architecture[END_REF]. We use 40 filters with eight orientations and five scales on 24 × 24 eye patch, then down-sample the resulting vector by 16 to a 1440-dimensional vector.

HOG Feature The aim of Histogram of Oriented Gradients (HOG) feature proposed in [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] is to describe local object appearance and shape within an image by the distribution of intensity gradients or edge directions. To implement these descriptors, we first divide the eye patches into small connected cells of 4 × 4 in size, and for each cell a histogram (with 9 bins) of gradient directions is calculated, which is then undergone a contrast-normalization within each block, leading to better invariance to changes in illumination or shadowing. Through these steps, we have a 900-dimensional histogram for each patch.

The three aforementioned feature representations of an open eye and a close eye are illustrated in Fig. 3, respectively. One may notice that the LBP feature is good at characterizing detailed texture information of the image, and Gabor wavelets highlight the differences of eye images with different states with respect to global spatial frequency, while the local shape information is best described by the HOG feature.

The Classifiers

In this work, we use the Nearest Neighbor, SVM and AdaBoost as our classifiers. The nearest neighbor method is a simple and effective non-parametric classification method and used in this paper as our baseline.

Support Vector Machines Support Vector Machines (SVMs) is the state-ofthe-art large margin classifier which has gained popularity within visual pattern recognition. One problem we should handle is imbalance problem. That is, the number of images of closed eyes and open eyes is different1 , which tends to increase the bias of trained SVM classifier to the class with more samples. To overcome this, before training, we set the penalty respective coefficients for the positive and negative samples to be ω 1 = N + +N - 2N + ,ω 2 = N + +N - 2N -, where N + is the number of positive samples and N -is the number of negative samples. We used the LIBSVM package [START_REF] Chang | Libsvm: a library for support vector machines[END_REF] with RBF kernel for the SVM-related experiments.

AdaBoost with Pixel-Comparisons As a final classifier compared, we use the AdaBoost, it provides a simple yet effective approach for stagewise learning of a nonlinear classification function. In this work, we use the "difference of intensities of pixels" proposed in [START_REF] Baluja | Efficient face orientation discrimination[END_REF] as our features. More specifically, we used five types of pixel comparison operators (and their inverses) [START_REF] Baluja | Boosting sex identification performance[END_REF]:

1) pixel i > pixel j ;
2) pixel i within 5 units (out of 255) of pixel j ;

3) pixel i within 10 units (out of 255) of pixel j ; 4) pixel i within 25 units (out of 255) of pixel j ; 5) pixel i within 50 units (out of 255) of pixel j ;

The binary result of each comparison, which is represented numerically as 1 or 0, is used as features. Thus, for an image of 24 × 24 pixels, there are 2 * 5 * (24 * 24)(24 * (24 -1)) or 3312000 pixel-comparison features.

To handle the large number of features, we use Adaboost for feature selection while learning a strong classifier. This is done by mapping each feature to a weak classifier and then selecting the most discriminative weak classifier increasingly for an additive strong classifier at the same time. For more details, see [START_REF] Baluja | Efficient face orientation discrimination[END_REF]. In our experiments, 2000 weak classifiers are trained and some of them are randomly selected for evaluation in each iteration. We examined the performance achieved from evaluating 1%, 10% and 100% of all possible weak classifiers per iteration.

Experiments

Data and Settings

The data for our experiments are collected from Zhejiang University blinking video database [24]. There

Experimental Results

Fig. 5 (left) gives the overall performance of SVM and AdaBoost on our datasets in terms of Receiver Operating Characteristic (ROC) curves. From the results, we can see that the best performer is the SVM using HOG features. In particular, the AUC value of "HOG+SVM" achieves 97.7%, compared to 97.0% for AdaBoost with 2000 weak classifiers, while the next best performer is the "LBP+SVM". We also see that the LBP features are better than Gabor features for the task of eye closeness detection -their EER values are 5.13 and 7.49 respectively. One possible reason is that the LBP features give a detailed account on the appearance of eye regions while being insensitive to the lighting changes. Actually, when one screws up his eyes, it is really very difficult to make a decision on whether his eyes are closed or not. In these cases, the global shape feature represented by Gabor features is less discriminative than local texture/shape information characterized by the LBP/HOG features. Table 1 gives the overall comparative performance of various methods and feature sets (the recognition rate is obtained by fixing a threshold learned from the training set). The various nearest neighbor classifier-based schemes serves as the baseline. Again we see that "HOG+SVM" performs best in AUC value but the "LBP+SVM" wins in recognition rate. However, in terms of testing efficiency, the AdaBoost classifier performs faster by at least four times over SVM but with slightly worse ROC performance. This suggests that Adaboost with difference of pixel features is a very attractive candidate in practice due to the high efficiency it provides in testing.

Table 2 and Fig. 5 (right) give the comparative performance using various feature combination schemes. Since LBP, Gabor and HOG feature characterize different aspects of eye patches (i.e, local texture, global shape, and local shape, respectively), it would be useful to fuse the information from three of them. Feature combination could be performed either at the feature level or at the score level and our previous experience shows that score level fusion is simpler to implement (no need to handle the high dimensional problem due to feature concatenation) and usually leads to better results [START_REF] Tan | Fusing gabor and lbp feature sets for kernel-based face recognition[END_REF]. Hence we adopt the strategy Fig. 6(a) illustrates some of images which are correctly identified as closed eyes using the "HOG/LBP/Gabor+SVM" scheme. Notice that there is large amount of diversity exhibited in the appearance of these closed-eye images. Fig. 6(b) shows some false negative images (upper two rows) and some false positive images (bottom two rows). By carefully examining these images, we can see that they look even confusing to human beings when deciding whether these eyes are open or not. This helps us understand the challenges of eye closeness detection in the real world. Finally, we investigate the influence of eye patch alignment on the performance of the system. As Table 3 shows, adding the module of alignment improves the performance consistently over all the feature sets tested. Although the LBP feature is known to be rotation-invariant and the HOG feature is robust against slight perturbation in the image, they are not robust to general affine transformations. Indeed, Table 3 shows that it is beneficial to do geometric normalization for eye patches before extracting features from them.

Conclusions

In this paper, we systematically evaluate several feature sets and classifiers for the task of eye closeness detection. Our experimental results indicate that fusing various feature descriptors significantly improves the performance of the detection system while the AdaBoost classifier with pixel comparisons is a good candidate scheme in practice due to its high efficiency and satisfying performance. In addition, our results show that eye alignment is important and influences the detection accuracy greatly.

Fig. 1 .

 1 Fig. 1. The overall architecture of our eye closeness detection system.

Fig. 2 .

 2 Fig. 2. Illustration of eye patches normalized with the congealing method, where patches in the top two rows are original images of closed eyes and their corresponding normalized versions respectively, and patches in the bottom two rows are original images of open eyes and their corresponding normalized images, respectively.

Fig. 3 .

 3 Fig. 3. Illustration of original eye images, their LBP, Gabor wavelet and HOG feature representation, respectively (top row -open eye, bottom row -closed eye). Note that this is only for illustration purpose and the sizes of the eye images are different from those used in the experiments.

  are a total of 80 video clips in the blinking video database from 20 individuals, four clips for each individual: one clip for frontal view without glasses, one clip with frontal view and wearing thin rim glasses, one clip for frontal view and black frame glasses, and the last clip with upward view without glasses. We manually select images in each blinking process, including eye images of open, half open, closed, half open, open. In addition, images of the left and the right eyes are collected separately. Some samples of the dataset are shown in Fig.4. We can see that these images are blurred, with low resolution and may be occluded by glasses.

Fig. 4 .

 4 Fig. 4. Illustration of some positive (top two rows) and negative (bottom two rows) samples used for training.

Fig. 5 .

 5 Fig. 5. ROC curves of various feature and classifier (left), and of various feature fusion strategies using the SVM classifier (right). AUC values are given in the end of corresponding legend texts.

Fig. 6 .

 6 Fig. 6. (a)Illustration of images which are correctly identified as closed eyes (true positive), and (b)(upper two rows) images of closed eyes failed to be recognized (false negative) and (bottom two rows) images of open eyes incorrectly recognized as closed eyes (false positive). All the results are with "HOG + LBP + Gabor and SVM" scheme.

Table 1 .

 1 Comparative performance of various features and classifiersof score level fusion with z-score normalization in this work. We can see from the table that combining all of the three feature sets gives the best performance both in terms of ROC curve and in terms of recognition rate. It is worthy noting that although the performance of the widely used HOG feature is inferior to the LBP feature in terms of recognition rate, its EER score is higher than LBP, which indicates that the local shape features play an important role in the detection of eye closeness alone. Furthermore, combining the local shape features with local texture descriptor (LBP) significantly improves its performance.

	Approach		Recognition Rate(%) Time(m sec) AUC(%) EER(%)
		Gray	73.50	220.25	-	-
		LBP	91.21	195.97	-	-
	NN	Gabor	85.65	297.31	-	-
		HOG	91.88	268.62	-	-
		Gray	75.03	12.97	50.00	99.6
		LBP	95.42	14.65	97.27	5.13
	SVM	Gabor	91.45	12.77	97.04	7.49
		HOG	91.88	19.24	97.67	5.05
		1%	92.06	2.890	96.48	8.30
	AdaBoost(1000) 10%	92.91	2.912	96.52	8.71
		100%	92.31	2.980	96.50	8.45
		1%	92.37	2.943	96.67	7.65
	AdaBoost(2000) 10%	92.67	3.059	96.73	7.48
		100%	93.47	3.132	97.01	7.08

Table 2 .

 2 Comparative performance of various feature combination schemes (with the SVM classifier)

	Approach	Recognition Rate(%) AUC(%) EER(%)
	LBP	95.42	97.27	5.13
	Gabor	91.45	97.04	7.49
	HOG	91.88	96.67	5.05
	LBP+Gabor	94.69	97.69	5.94
	LBP+HOG	95.05	97.89	4.80
	Gabor+HOG	94.81	97.98	5.05
	LBP+Gabor+HOG	95.42	98.02	5.05

Table 3 .

 3 Comparison of recognition rate w/o eye alignment with SVM.

	Processing	LBP Gabor HOG
	Without alignment 92.7 89.2 89.5
	With alignment 95.4 91.5 91.9

In practice, it is much easier to collect images of open eyes than those of closed eyes.

Acknowledgements

The work was financed by the (key) National Science Foundation of China (61073112, 61035003).


Peng Cao

Shenghua Liu

Jinhua Gao

Huawei Shen

Jingyuan Li

Yue Liu

Xueqi Cheng

Finding Topic-related Tweets Using Conversational Thread

Keywords: Microblog, Search, Conversational Thread, SVMRank

Microblog has gained more and more users around the world, the popularity of which makes information spreading in microblog the most important and influential activities on the Internet. Therefore, search in microblog is of the most significant issue for both academic and industrial world. Search in webpages has been studied for several decades, but as for microblog it is still an open and brand new question for everyone. Search in microblog is more difficult than that in traditional webpages because of the sparseness of the messages. Search functions in current microblogging services simply match microblog messages with query words, which cannot guarantee the correlation between the retrieving messages and the users' intention. We introduce the concept of conversational thread to gain more information and improve the search result in microblog. We also use SVMRank to train a model to determine the rank of relevance of the queries and messages. Through a series of experiments, we proved that our method is easy to implement, and can improve the precision up to 29% in average.

Introduction

In the age of social web, the microblogging service as a media is prevalent, in which the posts carry massive information and spread aggressively through the Internet.

Twitter, as one of the most popular microblogging services generates up to 230 million tweets1 per day by September, 2011, according to Michael Abbott, Twitter's ex-VP of engineering. A tweet2 differs from a post in traditional blogs in that its content is typically restricted to a very short length, typically 140 bytes or characters [1]. A tweet is "real time", the value of which drops dramatically after it has been posted for more than a day or even a few hours [2]. Microblog users read tweets in their timelines, which are posted or forwarded by their friends. Furthermore, trending topics are another important feed to help users access interesting tweets. Both reading tweets from friends and trending topics are passive ways to get information. Nevertheless, there are requirements to find information with users' intension, such as web search engines. In this paper, we study on the ad-hoc search of tweets, to find topic-related tweets according to user's descriptions, which has become one of the most popular academic and industrial interests. The Text REtrieval Conference (TREC) 2011 proposed this problem as the microblog task for the first time.

Web search known as a traditional search problem has been studied for several decades. Although a collection of classical models and algorithms on crawling, indexing, ranking and evaluation, etc. have been proposed, there are still many challenging issues, especially in searching tweets:

1. Extremely short. The length of a tweet is too short to contain enough topical features. However, those topical tweets are not independently posted in the microblogging services. Thus, considering the context of tweets to enrich its topical features is a key to find the topic-related tweets. 2. Realtime. The tweets in a microblog are posted rapidly. Furthermore the microblog users may have different intensions from the traditional web search engine. They may want to know statuses of particular topics such as some news about famous stars, the newest progress of events, etc. On the contrary, a webpage search engine mostly helps user with the navigational (give me the url of the site I want to reach) or transactional (show me sites where I can perform a certain transaction, e.g. shop, download a file, or find a map) need [START_REF]A taxonomy of web search Andrei Broder IBM Research 4. Why We Twitter: Understanding Microblogging Usage and Communities Akshay Java, Xiaodan Song[END_REF]. The freshness is more important than the relevance in microblog search. Thus the results of ad-hoc tweet searching must be organized in time-reverse order. Thus the ad-hoc searching has a definite intention to find the status of a happening event or topic, so that tweets are called statuses sometimes. Because of the importance of the freshness the ad-hoc searching, therefore, should present the results in a time-reverse order. 3. User authority. In such a social media, users in the microblogging services play a significant role in the value of tweets' content. Thus the importance of a tweet is not only decided by its content, but also the authority of its author.

This paper focuses on searching new and interesting tweets relevant to a given topic description. A query time is also given for each query, indicating the exact time of the query issuance. The search is supposed to be conducted onsite, and those tweets later than the query time should not be returned. The conversation thread is a set of tweets and their replies. It is supposed that tweets in the same conversational thread are more relevant to the same topic than other tweets outside. We introduce the concept of conversational thread as a very useful tweets context to expand the extreme short content. We propose an enhanced BM25 to determine the relevance of the tweet and the query. Furthermore we bring the tweets' freshness and activities as features. We then use SVM rank to learn the importance of those features, and our ranking results are truncated and filtered by relevance orderly. Finally those truncated results are organized in reverse-time order. In the experiments, we use precision@30 for evaluation, and our approach achieves 29% more relevant and fresh results totally.

The rest of the paper is organized as follows. Section 2 describes the related work. Section 3 describes our main method to search and rank the search results. Section 4 describes our experiment results. We conclude in section 5.

Related work

The existing related work about microblog mainly focuses on users [4-8], information flow [9,10], and tweets' content [11][12][13][14]. [2-7] studied Twitter from the users' point of view, such as users' intentions, followers and friends, users' network, and the social features of Twitter, etc. [15] proposed a new ranking method RE(Reader Effective).

[9] proposed 2 new concepts stickiness and persistence to detect the information diffusion on twitter.

[10] judged the information flow among twitter users. [START_REF]Want to be Retweeted? Large Scale Analytics on Factors Impacting Retweet in Twitter Network Bongwon Suh[END_REF] proposed some important features of tweets via PCA(primary content analyze). [11] evaluated the credibility of tweets' content via training a classifier based on message-based features, user-based features, topic-based features and propagation-based features.

[12] used the instant content from Twitter to detect earthquakes timely, and collected the geographic and damage information from tweets' descriptions and users' locations as soon as possible. There were also many works focus on thread. [17] focused on the discovery of reply relationship in twitter and used simple features to train model to recover the conversational threads. [18] is the phD dissertation of the same author as [17] but gave the method and steps more detailed. [19] analyzed the statistical characteristics of Slashdot and summarized the patterns of threads in it.

Our work is to query the tweets' content to find relevant, interesting, and fresh tweets via different threads. We use the whole TREC corpus to study global features of tweets' such as content, hashtags, urls, post time, etc. Because the tweets in twitter are very short (no longer than 140 characters), there is little useful information in a single tweet and the relevant between a query and a tweet is difficult to determine. So we also introduce other tweets in the same thread to gain more information to improve the search result. We employ SVM ranking model to rank our query results. The model is trained on pair-wise labeled data.

Ad-hoc Search

The task of Microblog trec 2011 can be described as follow, given a query Q at time T, to find relevant tweets whose post times are no later than T to keep time reverse order(from newest to latest) to achieve high precision@30. A query is a simple topic described by some words. The corpus is some specified users' tweets on twitter during Jun. 23, 2011 and Feb. 8, 2011. The whole data set is crawled from Twitter with specified seeds. After extracting from the crawled html pages, we got the tweet ID, screen name, http status code, post time, tweet content as a one-line record for each tweet. We only focus on English tweets. After preprocessing the tweets we got 5,650,490 English from 16,141,812 in total.

SVM Rank is an efficient machine learning method to rank. It uses Support vector machine (known as SVM) to rank and the kernel function should be linear. We study the distribution of each feature and take the logarithm of the user activeness and retweetness of the tweets to make them follow the power-law. Because if the distribution follows power-law, it is linear in log-log scale and it fits the SVM perfectly. Table 1 shows the features we used to train our model.

Conversational Thread

Thread originates from Email network with obviously reply relationships. However there are also conversational threads in forums, BBS and blogs. We can also define thread in twitter similarly. A conversational thread in twitter is a rooted tree whose nodes are tweets. The children of each node(if any) is the reply tweet of it. We consider the tweets in a conversational thread to be relevant to each other and thus be more relevant to a topic than other tweets outside the tree. Thread is the implicit structure which is helpful to determine the relevance to a particular topic. 38,482 tweets in the corpus are labeled to be relevant or irrelevant to a particular topic. We crawled twitter data and get the conversational threads. We get 48,543 tweets in total to train and test our model. Figure 1 shows a typical conversation thread which has 9 tweets.

The height of a thread can be defined as the number of tweets in the longest replyto links. Table .2 shows the height distribution of threads. It is not surprising that most of the thread is only one node. There are 38469 threads in total and about 90.34% of them have only 1 tweet. However, the average height of threads higher than 1 is about 3.80. That is to say we can have (if any) nearly 4 tweets to complement a single tweet.

Enhanced BM25

As for measuring the content relevance, we proposed a scoring method for tweets based on BM25.

Let Q be a query that consists of query words q1, q2, q3, etc. In the BM25 model, the score B(Ti, Q) for tweet Ti is calculated in the following way.

1 1 1 ( , ) ( 1) ( , ) ( ) ( , ) (1 )
Q j i i j j i j i f q T k B T Q IDF q T f q T k b b avgtl = + = + -+
∑ where q j is the jth query word, |Q| is the total number of query words, avgtl is the average tweet length, and |T i | is the length of tweet T i . The function f(q j , T i ) indicates the frequency of the query word q j in tweet T i . The model parameters k 1 and b are 2.0 and 0.75 separately. IDF(q j ) is defined as follows. log 0.5

,

where n(q j ) is the number of tweets that contain query word q j . It is seen that the score of a tweet matching two different words is the same to that of another matching the same word twice, if the two query words have the same IDF value. Since tweets are extremely short, the word frequency actually does not count much, and matching different query words makes much more sense. Therefore, we need a way to boost such a case. The enhanced BM25 finally defines as follows with boosting where h j ,i is a 0-1 binary that indicates whether query word q j hits tweet i.

1 , 1 1 1 ( , ) ( 1) ( , ) ( ) ( , ) (1 )
Q Q j i i j i j j j i j i f q T k B T Q IDF q h T f q T k b b avgtl = = ⎛ ⎞ ⎜ ⎟ + ⎜ ⎟ = ⎜ ⎟ + -+ ⎜ ⎟ ⎝ ⎠ ∑ ∑

User Activeness

The activeness of Twitter users is measured by the number of tweets they posted during a period. An active user is more likely to share valuable information, since he got more used to collecting interesting information, and sharing it. Figure 2 illustrates distribution of the number of users over the number of tweets they posted. It shows that the majority of users posted only one tweet, while the most active one posted 570 tweets in the corpus. With the number of posted tweets less than 12, the distribution follows the power law.

Fig. 2. user activeness

Let u i represent the number of posted tweets of user i. Thus the feature score U i for user i is calculated as follows. ln , 12 ln12, 12

i i i i u u U u ≤ ⎧ = ⎨ > ⎩

Other Features

Tweet Length We use rule-based method known as WordNet is employed to deal with the stemming of nouns, verbs and adjectives. There are also lots of misspelled words in the tweets we also correct the words using method described in Wiktionary [20].

The length of a tweet is generally defined as the number of words after word stemming, skipping retweets, hashtags and urls. Figure 3 shows the tweets distribution over the length, which does not follow the power law. So we used the length directly as a feature. The times of retweetness In Twitter, the times of retweetness reflect the popularity of a tweet. The relationship between the times of retweetness and the number of tweets is shown in Figure 4. We can see that a large number of tweets that are retweeted once, while only a few have been retweeted more than 20 times. The distribution for those retweeted follows the power law. Because of the power-law distribution, we use ln(r i +1) to denotes where r i is the times of retweetness of tweet i. r i equals zero if it is not retweeted. URLs and Hashtags A tweet with urls usually contains more information than others. Thus the number of urls indicates the value of a tweet in our ranking model. Hashtags are designed to reflect the topic of a tweet, so we also consider them when determine the relevance. Since a hashtag maybe a combination of several words, we simply use substring match instead of whole word match as a query hits a hashtag. Similarly as the way we boost content match, the score is also boosted by multiplying the number of different query words got matched. The feature score H i of hashtags for tweet i is calculated as formula Where q j is the jth query word. |Q| is the total number of query words. And h j ,i is a 0-1 binary that indicates whether query word q j hits the hashtags in tweet i.

, , 1 1 ( ( )
)

Q Q i j j i j i j j H I D F q h h = = = ∑ ∑
Freshness Because of we must keep the reverse time order, the freshness of a tweet is very important and may be more important than relevant. We use it as a feature. If the query time is T and the ith tweet's post time is t i T, both are denoted by seconds from a given time point. We use ln(T-t i +1) to measure the freshness of the tweet. The smaller the value is, the fresher the tweet.

4

Experiments and Evaluations

From the TREC Microblogging 2011's official result, we have got about labeled 38,482 tweets. We crawl twitter to get tweets they replied to and merge them up to get 48,543 tweets in total. Because we have the reply relationship among the tweets we can easily restore the conversational threads. We join up all the tweets in the same thread as a longer tweet to denote each single original tweet. So after that, we have 38,482 longer tweets. We compare the result of our method with simple method that determines the tweets relevance simply by whether they contain particular keywords or not. There are 50 topics in TREC's task and we use labeled tweets on 30 topics to train our model (topic-id from 1 to 30) and the other 20 topics (topic-id from 31 to 50) to test. For each test topic we give top30 results and compare. Table 3 shows the result. Using conversational threads can improve the precision@30 by about 29% in average. If we use tree thread height as a feature, the result will be even better. The second column show the result.

Fig. 1 .

 1 Fig. 1. Conversational thread

Fig. 3 .

 3 Fig. 3. Tweet length

Fig. 4 .

 4 Fig. 4. Retweet Number distribution

Table 1 .

 1 Features used to train our model

Table 2 .

 2 The height of threads

	Height	Number of threads
	1	34754
	2	2172
	3	553
	4	298
	5	185
	6	124
	7	84
	8	62

Table 3 .

 3 Precision@30 compared with simple method and our method

	Topic-id	Our	method	Using	tree	Simple hit me-
		Presion@30	height a feature		thod
	31	2		4		1
	32	1		2		1
	33	8		8		0
	34	1		2		0
	35	1		1		3
	36	13		13		9
	37	0		0		1
	38	2		2		1
	39	8		8		7
	40	1		1		2
	41	1		1		1
	42	1		1		2
	43	4		5		2
	44	3		6		0

the posts named under Twitter

We borrow the name "tweet" to refer the posts in a general microblogging service.

Acknowledgements

This work was supported by the National Natural Science Foundation of China with grant number 60933005 and the National Basic Research Program of China with grant number 2012CB316303. This work was also partly supported by the National Information Security Foundation of China with grant number 242-2011F45.

Conclusion and Future Work

Microblog tweets are always very short, which hinders big difficulty to searching for relevant tweets. To handle the problem, this paper proposed to employ conversational thread structure to expand short tweets and use an enhanced BM25 formula to determine the relevant and thus can find relevant more easily.

In this preliminary work, we simply join up all the tweets in conversational thread without consider to merge up hashtags and urls. The further study on the whole frame of combine tweet words, hashtags and urls together seems to be a good try.


Chao Lee

Lihua Yin

Yunchuan Guo

A Cluster-based Multilevel Security Model for Wireless Sensor Networks

Keywords: wireless sensor network, multilevel security, information flow control

Wireless sensor network is one of the fundamental components of the Internet of Things. With the growing use of wireless sensor networks in commercial and military, data security is a critical problem in these applications. Considerable security works have been studied. However, the majority of these works based on the scenarios that the sensitivities of data in the networks are in the same. In this paper, we present a cluster-based multilevel security model that enforces information flow from low security level to high security level. The design of the model is motivated by the observation that sensor nodes in numerous applications have different security clearances. In these scenarios, it is not enough for just protecting the data at a single level. The multilevel security mechanism is needed to prevent the information flow from high level nodes to low level nodes. We give the formal description of the model and present a scheme to achieve it. In our model, sensor nodes are grouped into different clusters. In each cluster, the security clearance of sensor nodes must not be higher than the security clearance of the cluster head. We use cryptography techniques to enforce the information flow policy of this model. The higher level nodes can derive the keys of lower level nodes and use the derived key to get the information from lower-level nodes. abstract environment.

Introduction

The Internet of Things has trended to growing use in commercial and military areas. It has been paid more and more attentions [START_REF] Atzori | The Internet of Things: A survey[END_REF][START_REF] Weber | Internet of Things C New security and privacy challenges[END_REF]. Wireless sensor network (WSN) is one of the fundamental components of the Internet of Things, which has attractive many researchers [START_REF] Zhao | Wireless Sensor Networks: An Information Processing Approach[END_REF]. A typical wireless sensor network is composed of a large number of sensor nodes and one or several base stations, which are used to collect data from the sensor nodes. The base station broadcasts control messages to engage sensor nodes to do some specific tasks. In response, the sensor nodes send back the collected data to the base station. They use radio frequency channels to broadcast messages for communication. Since the communication among sensors is via radio, which is exposed in the air, wireless sensor networks are highly vulnerable to security attacks. Security requirements for sensor networks have attractive many attentions [START_REF] Wang | A survey of security issues in wireless sensor networks[END_REF][START_REF] Xiao | A survey of key management schemes in wireless sensor networks[END_REF][START_REF] Jr | A Survey on Key Management Mechanisms for Distributed Wireless Sensor Networks[END_REF]. However, the majority of these works are designed to provide uniform security across the network, which means that all the sensor nodes and information have the same security clearance and sensitivity. There are various scenarios that sensor nodes in WSNs play different security levels. For example, in a wireless sensor network operating in a battlefield, the data collected by platoon leader node can be read by battalion commander node but cannot be read by soldiers. The command broadcasted to all battalion commander nodes can be received by the nodes whose security clearances are higher than battalion commander, but can never be received by the nodes whose clearances are lower than it. Take metropolitan surveillance application as another example, the police can see all data, but citizens can only see a subset of the data. This type of applications with multiple priority groups demands different layers of sensed data and multilevel security model in sensor networks. This motivation is the main reason to develop multilevel security in WSNs.

In this paper, we propose a cluster-based multilevel security model to address the problem, in which all sensor nodes and cluster heads have different security clearances. The WSN is modeled as a tree, in which the base station is the root, and each cluster is the subtree. In each cluster, the security clearances of all nodes are lower than the clearance of the cluster head, and the clearances of nodes are decreased from the root to leaf. In our model, each information has a classification, and only the nodes whose clearance is higher than the classification can read and relay the information. We give the formal description of the model and achieve the prototype of it.

To achieve this model, we present a scheme to build the multilevel topology in each cluster, and a multilevel key computation scheme to enforce the information flow control. In this model, each node belongs to different security level. The cluster head election algorithm is used to elect cluster heads with different security levels. The key computation process is initialized by the base station. It computes the keys of all cluster heads according to the clearance of each cluster head. And the key of a sensor node in a cluster is based on the cluster head key and the sensor node's clearances. In other words, the keys are clearance-related. If an upper-level node S H wants to read an information which flows from a lower-level node S L and the information is encrypted by the key of S L , then S H must have the ability to derive the key of S L from its own key to decrypt the information.

The rest of this paper is organized as follows: Section 2 presents the related work. In section 3, we describe the systems containing multiple sensitive data and users with different access privilege. Our proposed multilevel security model is described in Section 4. Section 5 provides the achievement scheme of the model. Section 6 discusses our proposed scheme. Finally, the conclusion can be found in Section 7.

Related Work

In the past, the research of multilevel security (MLS) has mainly focused on operating systems, programs, and wired computer networks. For example, In [START_REF] Bell | Secure computer systems: mathematical foundations and model[END_REF], Bell and La Padula proposed the classical BLP model for operating system multilevel access control. In [START_REF] Lu | A Model for Multilevel Security in Computer Networks[END_REF], Lu and Sundareshan proposed a model to describe the mechanism that enforces the security policy and requirements for computer network. In [START_REF] Winjum | Multilevel security for ip routing[END_REF], Winjum and Berg described a MLS scheme for computer network routing information. Very recently, however, multilevel security communication in wireless sensor networks have begun to attract the attentions. In [START_REF] Teng | Multi-layer Encryption for Multi-level Access Control in Wireless Sensor Networks[END_REF], Teng proposed a multi-layer encryption(MLE) scheme for multilevel access control in wireless sensor networks. In this work, users with different security clearance are assigned different group keys. Lower level users' key are computed by an one-way hash function from the keys of higher level users. However, the scheme doesn't enforce the information flow from low-security to high-security in networks. In [START_REF] Panja | A Role-based Access in a Hierarchical Sensor Network Architecture to Provide Multilevel Security[END_REF], Panja proposed a scheme called role-based access in sensor networks which provides role-based multilevel security in sensor networks. Each group is organized in such a way that they can have different roles based on the context and thus can provide different levels of accesses. They organized the network using Hasse diagram then compute the key for each individual node and extend it further to construct the key for a group. In [START_REF] Lee | Design of an Architecture For Multiple Security Levels in Wireless Sensor Networks[END_REF], Lee and Singhal introduced the concept of multiple security levels (MSL), which segregates different security levels by using a different computing infrastructure. They proposed an architecture to achieve the MLS property based on MSL concept. They divided the network to several domains and guards. A security domain is a discrete network consisting of a set of nodes having the same security level. The guards monitor and control the information flows among different security domains. However, their scheme assumes that all the same security level nodes can join the same group without the consideration of the communication range.

System Description

Before we describe the WSN with different access privilege, let us give the definitions of some terms.

-Security Class: Security class is a sensitivity level of an entity (e.g. UNCLAS-SIFIED, CONFIDENTIAL, SECRET, TOP SECRET). Let SC denote the set of security classes, which corresponds to a set of disjoint classes of sensitivity level.SC = {L 1 , L 2 , . . . L n },where n is a finite integer. -Dominate Relation: We denote L i L j to say that the security class L i dominates(or covers) L j . L i L j holds whenever L j L i . We then define the relation by

L i L j ⇔ L i L j ∧ ∃L k ∈ SC.L i L k L j .
-Clearance: Clearance is the degree of trust associated with a subject. We define the clearance of a subject s is CL(s) = [L i , L j ] ∈ SC × SC, where L j L i , which means that s can read information at class L j or lower, and write information at class L i or higher. We denote CL ⊥ (s) = L i and CL (s) = L j .

-Classification: Classification is a security class assigned to an object which specifies the sensitivity of the object. We denote CF (o) = L i ∈ SC as the classification of o.

In our model, we assume the WSNs consisting of sensor nodes, cluster heads and base station. Sensor nodes, which are grouped into clusters, probe the environment to track the target, and then send the collected data to the cluster heads. Each sensor has limited resources and short radio transmission range. If some of them have more than one hop from the cluster, they send their data to relaying nodes in the cluster and finally communicate with the cluster head. Cluster heads have more resources than sensors. They can execute relatively complicated numerical operations than sensors and have much larger radio transmission range than sensor nodes. Each cluster head is assumed to be reachable to all sensors in its cluster. Cluster heads can communicate each other directly and relay data between its cluster members and the base station.

In the system, we consider two modes. One is data collection, and the other is command distribution. A login user gets the collected data or distributes command via the base station. Each node and user have security clearances [L i , L j ]. Any information transmitted over the WSN must be designated a security classification L k where L i L k L j according to the sensor's task. For example, a sensor whose clearance is [soldier, soldier] can just generate information of soldier classification, while a sensor whose clearance is [soldier, platoon commander] can generate information of soldier or platoon commander according to the task or the collected data sensitivity. In the data collection mode, if the information collected by a sensor node is designated the classification platoon commander, only the nodes whose clearances dominant the classification platoon commander can get and relay the information, the login user on the base station whose clearance cover platoon commander can read the data. In the distribution mode, a battalion commander whose clearance is [soldier, battalion commander] wants to distribute a command to all platoon commanders, the command is designated the classification of platoon commander, only the sensor whose clearance dominant platoon commander can receive the command, but all the soldier nodes cannot get the information. In the system, the information transmitted over the network can only be allowed to send to the node whose security level is equal or higher than with information classification. We assume appropriate network communication protocols designed to ensure reliable information transmission across the network.

A Multilevel Security Model for WSN

We first give the definition of information flow relation.

Definition 1 (Information Flow Relation) For subjects S , S ∈ S, and information i ∈ O. S i S defines information i can flow from S to S . The information flow relation is defined as follows:

S i S ⇔ CL ⊥ (S ) CF (i) CL (S )
For example, in a cluster, there are two sensors S and S . The clearance of S is [soldier, soldier]. Similarly, the clearance of S is [soldier, commander]. S can send information with soldier classification to S .

To build the multilevel security cluster, we present completely dominate relation.

Definition 2 (Completely Dominate Relation) For two sensors S , S ∈ S, we say CL(S ) completely dominate CL(S ) if and only if CL (S ) CL (S ) ∧ CL ⊥ (S ) CL ⊥ (S ). We denote it CL(S ) CL(S ).

Proposition 1

is a partial ordering relation.

Proof. It easy to see that is reflexive and antisymmetric. Below we just proof that is transitive.

Assume [L i , L j ] [L m , L n ] and [L m , L n ] [L r , L s ] , according to Definition 2, we have L i L m , L j L n , L m L r and L n L s . Since is transitive, we can get L i L r and L j L s . So [L i , L j ] [L r , L s ], is transitive.
Therefore is a partial ordering relation.

In our model, we represent each cluster by a tree T (V, E), where V represents a set of sensors and E represents a set of communication links. Each node is denoted by (ID, CL(ID)).

Definition 3 (Multilevel Security Cluster) We define a multilevel security cluster as tuples

M LSC = (CH, S, CL,

)
where CH is the cluster head. S is the set of sensor nodes (members) contained in the cluster. CL is clearance of subjects. is the completely dominate relation. A cluster is a multilevel security cluster if and only if:

(1) For ∀S , S ∈ S, S .parentID = x, S .parentID = y ⇒ x = y.

(2) S .parentID = S .ID ⇒ CL(S ) CL(S ).

We denote the set of multilevel security cluster by MSLCs.

The Condition (1) points out that a sensor node only has a unique parent node, as only one next-hop node to be allowed from lower level to upper level. When a node S joining a cluster, if there are more than one nodes S i , S j ,...,S m , and S S i , S S j , . . . , S S m , then S chooses the closest one to be its parent. The Condition (2) can ensure the secure information flow.

Lemma 1 In a multilevel security cluster, S , S ∈ S are two sensors, and S is the parent of S :

(1) In the data collection mode, information i can flow from S to S all the time. (2) In the command distribution mode, information i can flow from S to S only when CF (i) CL (S ).

Proof. In a multilevel security cluster, there must be CL(S ) CL(S ). That is CL ⊥ (S ) CL ⊥ (S ) ∧ CL (S ) CL (S ). In the data collecting mode, information i is generated by S , so CL ⊥ (S ) CF (i) CL (S ). We can easily get CL ⊥ (S ) CF (i) CL (S ). According to Defintion 1, i can flow S to S all the time. In the command distribution mode, we can get CL ⊥ (S ) -U is the set of users. Each login user whose clearance is [L i , L j ] can read collected data whose classification is not higher than L j , and write distribution command with classification not lower than L i . -P is the security policy (SC, ), which is defined by a lattice.

CF (i) CL (S ). If CF (i) CL (
-I is the information transmitted over the WSN.

is the information flow relation.

In Figure 1, we illustrate an example of our scheme. The topology of the network is generated by the method in Section 5. .(We will give the scheme of generating it in section 5).

Proposition 2

The information flow in the WSN-CMLSM is secure.

Proof. According to Lemma 1, we can easily prove it. Because of space constraint, we omit the details.

A Scheme to achieve the multilevel model

We proposed a scheme to provide multilevel security for wireless sensor networks. The scheme consists of two parts. We first organized the sensors as a cluster-based multilevel security topology. And then the hierarchical keys on the topology are computed to enforce the information flow from low to high.

Multilevel Security Clusters Building

Each sensor node performs Algorithm 1 to build the multilevel security clusters. It takes as input Range(S i , CHs) and Range(S i , S), which means the cluster heads and sensor nodes in the communication range of S i respectively. It outputs the routing information of S i . In the algorithm, we assume that each sensor can detect the sensors and cluster heads in its communication range. It choose the nearest cluster head which satisfies the CL(S i ) CL(CH) to the parent node. If it not exists the satisfied cluster head, the sensor node choose the nearest node which meets CL(S i ) CL(S ) to the parent node. The detail is shown in Algorithm 1.

Key computation scheme

We presente a key computation scheme to enforce the information flow policy discussed in Section 4.

One way of implementing such a policy is to encrypt the data with security classification L i ∈ SC with key K Li . And the easiest way of the key management is to hold all the security classification related keys of its direct or indirect child nodes. However, when the hierarchy is large, it is difficult for node to store all the keys. So we utilize dependent keys management approach to achieve the multilevel security policy. The base station uses one-way functions H 1 , H 2 , . . . H m to compute the dependent keys, where m is the maximum number of children per node. If a security class L j is directly covered by L i whose key is K i ; and if L j is the kth child of L i , then K j = H k (K i ). Moreover, if L j has more than one direct parents L 1 j , L 2 j , . . . , L m j , where L j is the c 1 th,. . . , c m th child of the parent L 1 j , L 2 j , . . . , L m j , then

K j = H c1 (H c1 (K L 1 j ), H c2 (K L 2 j ), . . . , H cm (K L m j )
). According to the scheme, the key belongs to high security class can derived from the key of low security class. The key of L i is denoted by K Li .Take Figure 2(a) as an example, let K i is the key of L i , where 1 ≤ i ≤ 7, then we can compute

K 2 = H 1 (K 1 ), K 3 = H 2 (K 1 ), K 6 = H 3 (H 3 (K 2 ), H 1 (K 3 )).
Sensor node key computation Since in each cluster, the sensor nodes are organized as a tree not a lattice, and the above cluster head key computation scheme is too energy consuming for sensor nodes, we compute the sensor node key as follows: Each node S i computes the hierarchical key through a one-way hash function

K h Si = H(K h Si.parent , S i .ID). Take Figure 2(b) as an example, K h S4 can be computed from K h S3 via K h S4 = H(K h S1 , S 4 .ID). 2.
In [START_REF] Blundo | Perfectly-secure key distribution for dynamic conferences[END_REF], Blundo et al, establish pair-wise keystone using a bivariate t-degree polynomial f (x, y) = t i,j=0 a ij x i y j , which has the property of f (x, y) = f (y, x).For example, node S and S compute the symmetric key to secure communication. let i and j are the ID of S and S respectively. Node S have f (i, y), and it computes the key f (i, j) to communicate with node S . Node S can derive f (j, i) through f (j, y). The sensor node computes the communication key by K c S = K h S ⊕f (S .ID, y), where f is the polynomial in [START_REF] Blundo | Perfectly-secure key distribution for dynamic conferences[END_REF], y is the IDs of the nodes that connected to S .

When sensor node S sends the data to the cluster head. It encrypts the data by K c S , and sends to its parent S . S can compute the K c S through f (S .ID, S .ID) and K h S = H(K h S , S .ID). S can get the information of S , and it forwards the message to its parent.

Theoretical analysis

Theorem 3 For security class L i and L j , if

L i L j , then K Li can be derived from K Lj . Proof. Assume L m , L n , • • • , L r , L s are between L i and L j , we can easily get K Lm = H(K Li ), K Ln = H(K Lm ), K Ln+1 = H(K Ln ), • • • , K Ls = H(K Lr ), so K Lj = H(H(H(...H(K i )...))). Therefore, if L i L j , K Lj can derive K Li .
Proposition 4 Information M is transited over the WSN, only the sensor node S satisfied CF (M ) CL (S ) can get the information.

Proof. The information M (CF (M ) = L m ) is encrypted by K Lm . When the information from the base station to sensors, only the cluster head satisfied L k CL (CH) can get the information, as K CH can derive from K Lm according to Theorem 3. The other cluster heads cannot get the information because of their inability to compute K Lm . The cluster heads satisfied L m CL (CH) send the information to their members. Since in MLSC, any sensor node S satisfies CL(S) CL(S.parent) and the hierarchical key is computed by the topology, if CF (M ) CL (S ),S can derive K Lm from K h S . Therefore, S can get the information of M . When the information is from the sensor to the base station, assume M is generated by a node S. In MLSC, the sensor's next hop must satisfy CL(S ) CL(S .parent), so M can only send through the path CF (M ) CL (S ), according to Theorem 3, the sensors can derive K Lm . the node CF (M ) CL (S ) is not on the routing path of M , and the K Lm cannot be derived, so only the sensor node S satisfied CF (M ) CL (S ) can get the information.

Because of space constraint, the details of simulation will be presented in a separate paper.

Summary

In this paper, we proposed a cluster-based multilevel security model for wireless sensor networks. We divided the sensors in different clusters and modeled each cluster as a tree. In each cluster, the clearance of the cluster head completely dominated its member's clearance. Each sensor node has a unique parent, and the clearance of the node is completely dominated by its parent. The information flow policy is proposed to ensure the information flow low level to high level. We present a scheme to achieve it. In our scheme, cryptographic technologies are employed to enforce the information flow policy. The high level node can derive keys of the low level nodes, while the low-level node cannot derive keys of the high level nodes. Therefore, information can only flow from low to high that satisfies the requirement of the scenarios that the sensor nodes have different sensitivities.

  S ), and CL(S ) CL(S ), then CL ⊥ (S ) CF (i) CL (S ), i can flow S to S . Otherwise, the flow is prevented. Definition 4 (Cluster-based Multilevel Security Model for WSN ) The WSN cluster-based multilevel security model is defined by WSN-CMLSM = (M SLCs, BS, U, P, I, ) where -M SLCs is the set of multilevel security clusters. -BS is the base station. All the C ∈ M SLCs connect to BS.

Fig. 1 . 1 ,

 11 Fig. 1. Cluster-based multilevel security model exmamle

Algorithm 1 : 2 if 6 end 7 end 8 if

 12678 Multilevel security clusters building algorithm Data: Range(Si, CHs),Range(Si, S) Result: Si.parentID 1 begin Range(Si, CHs) = ∅ then 3 foreach CH ∈ Range(Si, CHs) do 4 if CL(Si) CL(CH) then 5 Set Candidate CH ← CH; Set Candidate CH = ∅ then 9 Chosen CH = N earest(Set Candidate CH); 10 Si.parentID = Chosen CH.ID; Range(Si, S) do 15 if CL(Si) CL(S ) then 16 Set Candidate N ode ← S ; 17 Chosen N ode = N earest(Set Candidate N ode); 18 Si.parentID = Chosen N ode.ID; Cluster head key computation The keys of cluster heads are computed in the base station. Assume the base station has the knowledge of the relation of security class before the WSN deployment is reasonable. (SC, ) are organized as a lattice. Each security class has many direct successors and predecessors.

Fig. 2 .

 2 Fig. 2. Key computation scheme examples

Acknowledgment

This research is supported by the National High Technology Research and Development Program of China (863 Program) (2009AA01Z438), and the National Natural Science Foundation of China (61070186,61100186)


Zhixin Li

Zhiping Shi
email: shizhiping@gmail.com

Zhengjun Tang
email: zjtang@gxnu.edu.cn

Weizhong Zhao
email: zhaoweizhong@gmail.com

A Novel Model for Semantic Learning and Retrieval of Images

Keywords: semantic learning, automatic image annotation, continuous PLSA, aspect model, image retrieval

In this paper, we firstly propose an extended probabilistic latent semantic analysis (PLSA) to model continuous quantity. In addition, corresponding EM algorithm is derived to determine the parameters. Then, we apply this model in automatic image annotation. In order to deal with the data of different modalities according to their characteristics, we present a semantic annotation model which employs continuous PLSA and traditional PLSA to model visual features and textual words respectively. These two models are linked with the same distribution over all aspects. Furthermore, an asymmetric learning approach is adopted to estimate the model parameters. This model can predict semantic annotation well for an unseen image because it associates visual and textual modalities more precisely and effectively. We evaluate our approach on the Corel5k and Corel30k dataset. The experiment results show that our approach outperforms several state-of-the-art approaches.

Introduction

As an important research issue, Content-based image retrieval (CBIR) searches relative images of given example in visual level. Under this paradigm, various low-level visual features are extracted from each image in the database and image retrieval is formulated as searching for the best database match to the feature vector extracted from the query image. Although this process is accomplished quickly and automatically, the results are seldom semantically relative to the query example due to the notorious semantic gap [START_REF] Datta | Image retrieval: ideas, influences, and trends of the new age[END_REF]. As a result, automatic image annotation has emerged as a crucial problem for semantic image retrieval.

The state-of-the-art techniques of automatic image annotation can be categorized into two different schools of thought. The first one defines auto-annotation as a traditional supervised classification problem [START_REF] Carneiro | Supervised learning of semantic classes for image annotation and retrieval[END_REF][START_REF] Li | Automatic linguistic indexing of pictures by a statistical modeling approach[END_REF], which treats each word (or semantic category) as an independent class and creates different class models for every word. This approach computes similarity at the visual level and annotates a new image by propagating the corresponding class words. The second perspective takes a different stand and treats image and text as equivalent data. It attempts to discover the correlation between visual features and textual words on an unsupervised basis [1, 2, 7, 8 10, 11, 13, 15], by estimating the joint distribution of features and words. Thus, it poses annotation as statistical inference in a graphical model.

As latent aspect models, both PLSA [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF] and latent Dirichlet allocation (LDA) [START_REF] Blei | Latent Dirichlet allocation[END_REF] have been successfully applied to annotate and retrieve images. PLSA-WORDS [START_REF] Monay | Modeling semantic aspects for cross-media image indexing[END_REF] is a representative approach, which acquires good annotation performance by constraining the latent space. However, this approach quantizes continuous feature vectors into discrete visual words for PLSA modeling. As a result, its annotation performance is sensitive to the clustering granularity. In our previous work [START_REF] Li | Fusing semantic aspects for image annotation and retrieval[END_REF], we propose PLSA-FUSION which employs two PLSA models to capture semantic information from visual and textual modalities respectively. Furthermore, an adaptive asymmetric learning approach is presented to fuse the aspects of these two models. Consequently, PLSA-FUSION can acquire higher accuracy than PLSA-WORDS. Nevertheless, PLSA-FUSION also needs to quantize visual features into discrete visual words for PLSA modeling. In the area of automatic image annotation, it is generally believed that using continuous feature vectors will give rise to better performance [START_REF] Blei | Modeling annotated data[END_REF][START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF]. However, since traditional PLSA is originally applied in text classification, it can only handle discrete quantity (such as textual words). In order to model image data precisely, it is required to deal with continuous quantity using PLSA.

This paper proposes continuous PLSA, which assumes that each feature vector in an image is governed by a Gaussian distribution under a given latent aspect other than a multinomial one. In addition, corresponding EM algorithm is derived to estimate the parameters. Then, as general treatment, each image can be viewed as a mixture of Gaussians under this model. Furthermore, based on the continuous PLSA and the traditional PLSA, we present a semantic annotation model to learn the correlation between the visual features and textual words. An asymmetric learning approach is adopted to estimate the model parameters. We evaluate our approach on standard Corel datasets and the experiment results show that our approach outperforms several state-of-the-art approaches.

The rest of the paper is organized as follows. Section 2 presents the continuous PLSA model and derives corresponding EM algorithm. Section 3 proposes a semantic annotation model and describes the asymmetric learning approach. Experiment results are reported and analyzed in section 4. Finally, the overall conclusions of this work are presented in section 5.

Continuous PLSA

Just like traditional PLSA, continuous PLSA is also a statistical latent class model which introduces a hidden variable (latent aspect) z k (k 1, …, K) in the generative process of each element x j (j 1, …, M) in a document d i (i 1, …, N). However, given this unobservable variable z k , continuous PLSA assumes that elements x j are sampled from a multivariate Gaussian distribution, instead of a multinomial one in traditional PLSA. Using these definitions, continuous PLSA [START_REF] Li | Automatic image annotation with continuous PLSA[END_REF] assumes the following generative process:

1. Select a document d i with probability P(d i ); 2. Sample a latent aspect z k with probability P(z k |d i ) from a multinomial distribution conditioned on d i ;

3. Sample

x j ~ P(x j |z k ) from a multivariate Gaussian distribution N(x|μ k ,Σ k ) condi- tioned on z k .
Continuous PLSA has two underlying assumptions. First, the observation pairs (d i , x j ) are generated independently. Second, the pairs of random variables (d i , x j ) are conditionally independent given the latent aspect z k . Thus, the joint probability of the observed variables is obtained by marginalizing over the latent aspect z k , ( 1)

1 ( , ) ( ) ( | ) ( | ). K i j i k i j k k P d x P d P z d P x z = = ∑
A representation of the model in terms of a graphical model is depicted in Figure 1. The mixture of Gaussian is assumed for the conditional probability P(.|z). In other words, the elements are generated from K Gaussian distributions, each one corresponding a z k . For a specific latent aspect z k , the condition probability distribution function of elements x j is

1 / 2 1/ 2 1 1 ( | ) e x p ( ( ) ( (2 ) | | 2 T j k j k k j k D k P x z x x μ π - = - - ∑ ∑ ) ) , μ - k ( 2
)
where D is the dimension, μ k is a D-dimensional mean vector and Σ k is a D×D covariance matrix.

Following the maximum likelihood principle, P(z k |d i ) and P(x j |z k ) can be determined by maximization of the log-likelihood function

(3) 1 1 1 1 1 1 ( , )log ( , ), ( )log ( ) ( , )log ( | ) ( | ). N M i j i j i j N N M K i i i j k i j i i j k n d P d n d P d n d P z d P z = = = = = = = = + ∑∑ ∑ ∑∑ ∑ x x x x L
where n(d i , x j ) denotes the number of element x j in d i .

The standard procedure for maximum likelihood estimation in latent variable models is the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. In E-step, applying Bayes' theorem to (1), one can obtain

1 ( | ) ( | ) ( | , ) . ( | ) ( | ) k i j k k i j K l i j l l P z d P x z P z d x P z d P x z = = ∑ (4)
In M-step, for any d i , z k and x j , the parameters are determined as

1 1 1 1 ( , ) ( | , ) , ( , ) ( | , ) N M i j k i j j i j k N M i j k i j i j n d x P z d x x n d x P z d x μ = = = = = ∑ ∑ ∑ ∑ (5) 1 1 1 1 ( , ) ( | , )( )( ) , ( , ) ( | , ) N M T i j k i j j k j k i j k N M i j k i j i j n d x P z d x x x n d x P z d x μ μ = = = = - - Σ = ∑ ∑ ∑ ∑ (6) 1 1 ( , ) ( | , ) ( | ) . ( , ) M i j k i j j k i M i j j n d x P z d x P z d n d x = = = ∑ ∑ (7)
Alternating ( 4) with ( 5)-( 7) defines a convergent procedure. The EM algorithm terminates by either a convergence condition or early stopping technique.

3

Semantic Learning Model

Gaussian-Multinomial PLSA

In order to deal with the data of different modalities in terms of their characteristics, we employ continuous PLSA and traditional PLSA to model visual features and textual words respectively. These two models are linked by sharing the same distribution over latent aspects P(z|d). We refer to this semantic annotation model as Gaussianmultinomial PLSA (GM-PLSA), which is represented in Figure 2. Under this modeling approach, each image can be viewed as either a mixture of continuous Gaussian in visual modality or a mixture of discrete words in textual modality. Therefore, it can learn the correlation between features and words effectively and predict semantic annotation precisely for an unseen image.

Algorithm Description

We adopt asymmetric learning approach to estimate the model parameters because an asymmetric learning gives a better control of the respective influence of each modality in the latent space definition [START_REF] Monay | Modeling semantic aspects for cross-media image indexing[END_REF]. In this learning approach, textual modality is firstly chosen to estimate the mixture of aspects in a given document, which constrains the definition of latent space to ensure its consistency in textual words, while retaining the ability to jointly model visual features. The flow of learning and annotating is described in Figure 3. 7); compute Σ k with eq.( 8); end for (c) compute the likelihood of validation data L c with eq.( 3); end while 6. save μ k and Σ k .

In annotation stage, given visual features of each test image and the previously estimated parameters μ k and Σ k , the aspect distribution P(z k |d new ) can be inferred using the folding-in method. The posterior probability of each word in the vocabulary is then computed by ( 8)

1 ( | ) ( | ) ( | ). K new k new k k P w d P z d P w z = = ∑
As usual, we choose five words with the largest posterior probabilities as annotations of an unseen image.Having estimated the parameters of GM-PLSA, the stage of semantic retrieval can be put into practice directly. The retrieval algorithm takes as inputs a semantic word w q and a database of test images. After annotating each image in the test database, the retrieval algorithm ranks the images labeled with the query word by decreasing posterior probability P(w q |d new ).

Experimental Results

In order to test the effectiveness and accuracy of the proposed approach, we conduct our experiments on two standard datasets, i.e. Corel5k [START_REF] Duygulu | Object recognition as machine translation: learning a lexicon for a fixed image vocabulary[END_REF] and Corel30k [START_REF] Carneiro | Supervised learning of semantic classes for image annotation and retrieval[END_REF]. The focus of this paper is not on image feature selection and our approach is independent of visual features. We simply decompose images into a set of 32×32 blocks, then compute a 36 dimensional feature vector for each block, consisting of 24 color features and 12 texture features.

Results on Corel5k dataset

In this section, the performance is evaluated by comparing the captions automatically generated with the original manual annotations. We compute the recall and precision of every word in the test set and use the mean of these values to summarize the system performance. We report the results on two sets of words: the subset of 49 best words and the complete set of all 260 words that occur in the training set. The systematic evaluation results are shown in Table 1. From the table, we can see that our model performs much better than the first three approaches. Besides, the model performs slightly better than MBRM. We believe that the application of the continuous PLSA is the reason for this result. Several examples of annotation obtained by our prototype system are shown in Table 2. Here top five words are taken as annotation of the image. We can see that even the system annotates an image with a word not contained in the ground truth, this annotation is frequently plausible. Mean average precision (mAP) is employed as a metric to evaluate the performance of single word retrieval. We only compare our model with CMRM, CRM, MBRM and PLSA-WORDS, because mAPs of other models cannot be accessed directly from the literatures.

The annotation results ignore rank order. However, rank order is very important for image retrieval. Our system will return all the images which are automatically annotated with the query word and rank the images according to the posterior probabilities of that word. Table 3 shows that GM-PLSA is slightly better than other models. In summary, the experiment results show that GM-PLSA outperforms several previous models in many respects, which proves that the continuous PLSA is effective in modeling visual features.

Results on Corel30k dataset

The Corel30k dataset provides a much large database size and vocabulary size compared with Corel5k. Since Corel30k is a new database, we only compare our model with PLSA-WORDS. Figure 4 presents the precision-recall curves of PLSA-WORDS and GM-PLSA on the Corel30k dataset, with the number of annotations from 2 to 10. The precision and recall values are the mean values calculated over all words. From the figure we can see that GM-PLSA consistently outperforms PLSA-WORDS.

The superior performance of GM-PLSA on precision and recall directly results in its great semantic retrieval performance. From Table 4 we can also see the great improvements of GM-PLSA over PLSA-WORDS.

Table 4. Comparison of ranked retrieval results

Mean Average Precision on Corel30k Dataset

Models

All 950 words Words with recall ≥ 0 PLSA-WORDS 0.14 0.17 GM-PLSA 0.23 0.28

Overall, the experiments on Corel30k indicate that GM-PLSA is fairly stable with respect to its parameters setting. Moreover, since this annotation model integrates traditional PLSA and continuous PLSA, it has better robustness and scalability.

Conclusion

In this paper, we have proposed continuous PLSA to model continuous quantity and develop an EM-based iterative procedure to learn the conditional probabilities of the continuous quantity given a latent aspect. Furthermore, we present a semantic annotation model, which employ continuous PLSA and traditional PLSA to deal with the visual and textual data respectively. An adaptive asymmetric learning approach is adopted to estimate the model parameters. Experiments on the Corel dataset prove that our approach is promising for automatic image annotation. In comparison to pre-vious proposed annotation methods, higher accuracy and effectiveness of our approach are reported.

Fig. 1 .

 1 Fig. 1. Graphical model representation of continuous PLSA.

Fig. 2 .

 2 Fig. 2. Representation of the semantic annotation model GM-PLSA.

Fig. 3 .

 3 Fig. 3. The flow of learning and annotating algorithms of GM-PLSA.

Fig. 4 .

 4 Fig. 4. Precision-recall curves of PLSA-WORDS and GM-PLSA.

Algorithm 1 .

 1 Estimation of the parameters: α k 、μ k and Σ k Input: Visual features f n and textual words w m of training images. Output: Model parameters α k 、μ k and Σ k . Process: 1. random initialize the P(z k |d i ) and P(w m |z k ) probability tables; 2. while incr se in the likelihood of validation data ΔL t > T ) compute the likelihood of validation data L t ; end while 3. save α k = {P(w 1 |z k ), P(w 2 |z k ), …, P(w Mw |z k )}; 4. initialize μ k and Σ k ; 5. while increase in the likelihood of validation data ΔL c >T

t do ea for k 1, 2, …, K and all (d i , w j ) pairs in training documents do (a) {E step} compute P(z k |d i , w j ) with EM algorithm of traditional PLSA; end for (b) {M step} for k 1, 2, K and j 1, 2, …, M do compute P(w j |z k ) with M algorithm of traditional PLSA; E for k 1, 2, …, K and i 1, 2, …, N do end for compute P(z k |d i ) with EM algorithm of traditional PLSA; end for (cc do (a) {E step} for k 1, 2, …, K and all (d i , f j ) pairs in training documents do compute P(z k |d i , f j ) with eq.(4); end for (b) {M step} for k 1, 2, …, K, i 1, 2, …, N and j 1, 2, …, M do compute μ k with eq.(

Table 1 .

 1 Performance comparison on the task of automatic image annotation.

	Models	Translation	CMRM	CRM	MBRM	PLSA-WORDS	GM-PLSA
	#words with recall > 0	49	66	107	122	105	125
		Results on 49 best words, as in [7,8,10,11]
	Mean Recall	0.34	0.48	0.70	0.78	0.71	0.79
	Mean Precision	0.20	0.40	0.59	0.74	0.56	0.76
			Results on all 260 words
	Mean Recall	0.04	0.09	0.19	0.25	0.20	0.25
	Mean Precision	0.06	0.10	0.16	0.24	0.14	0.26

Table 2 .

 2 Comparison of annotations made by PLSA-WORDS and GM-PLSA.

	Image
	Ground Truth	mule, deer, buck, doe	sphinx, stone, statue, sculpture	branches, grass, frost, ice	, people sand , , water sky
	PLSA-WORDS	deer,mule,sculpture,	sculpture, stone,	clouds, fox, frost,	sky, beach, coast,
	Annotation	stone, rabbit	sky, hut, statue	snow, ice	sand, oahu
	GM-PLSA Annotation	deer, mule, grass, sculpture, sand	stone, sculpture, statue, sky, sand	, ice frost , , , snow clouds branches	beach, water, sky, sand, coast

Table 3 .

 3 Comparison of ranked retrieval results

		Mean Average Precision on Corel5k Dataset
	Models	All 260 words	Words with recall ≥ 0
	CMRM	0.17	0.20
	CRM	0.24	0.27
	MBRM	0.30	0.35
	PLSA-WORDS	0.22	0.26
	GM-PLSA	0.32	0.37

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Nos. 61165009, 60903141, 61105052), the Guangxi Natural Science Foundation (2012GXNSFAA053219, 2012GXNSFBA053166, 2011GXNSFD018026) and the "Bagui Scholar" Project Special Funds.