The electrical activity of brain or EEG signal is very complex data system that may be used to many di erent applications such as device control using mind. It is not easy to understand and detect useful signals in continuous EEG data stream. In this paper, we are describing an application of data compression which is able to recognize important patterns in this data. The proposed algorithm uses LempelZiv complexity for complexity measurement and it is able to successfully detect patterns in EEG signal.
The Electroencephalography (EEG) plays a big role in diagnosis of brain diseases, and, also, in Brain Computer Interface (BCI) system applications that helps disabled people to use their mind to control external devices. Both research areas are growing today.
The EEG records the electrical activity of the brain using several sensors placed on a scalp . Di erent mental tasks produce indiscernible recordings but they are di erent. Di erent brain actions activate di erent parts of the brain. The most di cult part is the de nition of an e cient method or algorithm for detection of the di erences in recordings belonging to the di erent mental tasks. When we de ne such algorithm we are able to translate these signals into control commands of an external device, e.g. prosthesis, wheelchair, computer terminal, etc. The types of brain waves distinguished by their di erent frequency ranges are recognized as follows.
{ Delta ( ) waves lie within the range from approximately 0.5 up to 4 Hz. The
amplitude of this waves is varying and have been associated with deep sleep
and present in the waking state.
{ Theta ( ) waves lie within the range from 4 to 7.5 Hz. The amplitude varies
about 20 V. Theta waves have been associated with access to unconscious
material, creative inspiration and deep meditation.
{ The frequency of the Alpha ( ) waves lies within the range from 8 to 13
Hz, the amplitude varies between 30 and 50 V. It is reduced or eliminated
by opening the eyes, by hearing unfamiliar sounds, by anxiety, or mental
concentration or attention.
{ Beta ( ) waves are the electrical activities of the brain varying within the
frequency range from 14 to 26 Hz. The amplitude is about 5 up to 30 V.
Beta waves has been associated with active thinking, active attention, focus
on the outside world, or solving concrete problems. A high-level beta wave
may be acquired when a human is in a panic state.
{ Gamma ( ) waves have frequency range above 30 Hz, can be used to
demonstrate the locus for right and left index nger movement, right toes, and the
rather broad and bilateral area for tongue movement [
Carlo Matteucci and Emil Du Bois-Reymond, were rst people who register the
electrical signals emitted from muscle nerves using a galvanometer and
established the concept of neurophysiology. The rst brain activity in the form of
electrical signals was recorded in 1875, by Richard Caton (1842{1926), a
scientist from Liverpool, England, using a galvanometer and two electrodes placed
over the scalp of a human. From here EEG stand to, Electro that referring to
registration of brain electrical activities, Encephalon that referring to emitting the
signals from a brain, and gram or graphy, which means drawing. Then the term
EEG was henceforth used to denote electrical neural activity of the brain [
In 1920, Hans Berger, the discoverer of the existence of human EEG signals,
began his study of human EEG. In 1910, Berger started working with a string
galvanometer and later he used a smaller Edelmann model. After the year 1924,
he used larger Edelmann model. Berger started to use the more powerful Siemens
double coil galvanometer (attaining a sensitivity of 130 V/cm) in 1926. In 1929
Berger made the rst report of human EEG recordings with duration from one to
three minutes on photographic paper and, in the same year, he also found some
correlation between mental activities and the changes in the EEG signals [
The rst biological ampli er for the recording of brain potentials was built
by Toennies (1902{1970). In 1932 the di erential ampli er for EEG recording
was later produced by the Rockefeller foundation. The potential of a
multichannel recordings and a large number of electrodes to cover a wider brain region
was recognized by Kornmuller. Berger assisted by Dietch (1932) applied Fourier
analysis to EEG sequences, which was developed during the 1950s [
After that the EEG analysis and classi cation take grow and development every day. The application of the EEG signals to diagnosis of the brain diseases and to control external devices for disabled people such as wheel chair, prosthesis, etc. Today, several techniques for analysis and classi cation the EEG signal exists, by using EEG multichannel recording according to 10/20 International electrodes standard, which is used in Brain Computer Interface (BCI). 3
In this section we present some of related works for EEG data analysis using di erent techniques such as Non-negative Matrix Factorization (NMF), Normalized Compression Distance (NCD), and Lempel-Ziv (LZ) complexity measure, and Curve Fitting (CF).
Lee et al. presented a Semi-supervised version of NMF (SSNMF) which
jointly exploited both (partial) labeled and unlabeled data to extract more
discriminative features than the standard NMF. Their experiments on EEG
datasets in BCI competition con rm that SSNMF improves clustering as well as
classi cation performance, compared to the standard NMF [
Shin et al. have proposed new generative model of a group EEG analysis,
based on appropriate kernel assumptions on EEG data. Their proposed model
nds common patterns for a speci c task class across all subjects as well as
individual patterns that capture intra-subject variability. The validity of the
proposed method have been tested on the BCI competition EEG dataset [
Dohnalek et al. have proposed method for signal pattern matching based on
NMF, also they used short-time Fourier transform to preprocess EEG data and
Cosine Similarity Measure to perform query-based classi cation. This method
of creating a BCI capable of real-time pattern recognition in brainwaves using
a low cost hardware, with very cost e cient way of solving the problem [
Mehmood, and Damarla applied kernel Non-negative Matrix Factorization
to separate between the human and horse footsteps, and compared KNMF with
standard NMF, their result conclude that KNMF work better than standard
NMF [
Sousa Silva, et al. veri ed that the Lempel and Ziv complexity measurement
of EEG signals using wavelets transforms is independent on the electrode position
and dependent on the cognitive tasks and brain activity. Their results show that
the complexity measurement is dependent on the changes of the pattern of brain
dynamics and not dependent on electrode position [
Noshadi et al. have applied Empirical mode decomposition (EMD) and
improved Lempel-Ziv (LZ) complexity measure for discrimination of mental tasks,
their results reached 92.46% in precision, and also they concluded that EMD-LZ
is getting better performance for mental tasks classi cation than some of other
techniques [
Li Ling, and Wang Ruiping calculated complexity of sleeping stages of EEG
signals, using Lempel-Ziv complexity. Their results showed that nonlinear feature
can re ect sleeping stage adequately, and it is useful in automatic recognition of
sleep stages [
Krishna, et al. proposed an algorithm for classi cation of the wrist movement
in four directions from Magnetoencephalography (MEG) signals. The proposed
method includes signal smoothing, design of a class-speci c Unique Identi er
Signal (UIS) and curve tting to identify the direction in a given test signal.
The method was tested on data set of the BCI competition, and the best result
of the prediction accuracy reached to 88.84 % [
Klawonn, et al. have applied Curve Fitting for Short Time Series biological
data to remove noise from measured data and correct measurement errors or
deviations caused by biological variation in terms of a time shift etc. [
The main property in the similarity is a measurement of the distance between two
objects. The ideal situation is when this distance is a metric [
In our experiment we do not deal with the measure of the complexity. We create a list of the LZ sequences from the individual subsequence. One list is created for each data le with turtle commands of the compared les.
The comparison of the LZ sequence lists is the main task. The lists are compared to each other. The main property for comparison is the number of common sequences in the lists. This number is represented by the sc parameter in the following formula, which is a metric of similarity between two turtle commands lists.
SM =
sc min(c1; c2) (1) Where { sc { count of common string sequences in both dictionaries. { c1; c2 { count of string sequences in dictionary of the rst or the second data trial.
The SM value is in the interval between 0 and 1. The two documents are equal if SM = 1 and they have the highest di erence when the result value of SM = 0. 5
The data for our experiments was recorded in our laboratory. We have used 7 channels from recorded data. The signal data contains records of the movement of one nger from four di erent subjects. Every subject performed a press of a button with left index nger. The sampling rate was set to 256 Hz. The signals were band pass ltered from 0.5 Hz to 60 Hz to remove unwanted lower and higher frequencies and noise. The data was then processed, that we extract each movement from the data as well as 0.3s before the movement and 0.3s after the movement.
The pre-processed data contains 4606 data trials { 2303 data trails with nger movement and 2303 trails without nger movement. We divided it into seven groups, one group for each sensor. In our experiment we are using 75% of data for training and 25% for testing. Each group contains part of training and testing data part. The training part for one sensor contains 492 trials { 246 data trails with nger movement and 246 trails without nger movement. The testing part contains 166 trails { 83 trails with nger movement and 83 trails without nger movement. The we have used for further model validation. 5.1
After recording and ltering of the EEG data we apply polynomial curve tting for data smoothing. The tting will remove noise from the data and t the data trend.
Consider the general form for a polynomial tting curve of order j: f (x) = a0 + a1x + a2x2 + a3x3 + : : : + aj xj = j X akxk k=1
We minimized the total error of polynomial tting curve with least square approach. The general expression for any error using the least squares approach is: err =
X(dj )2 err = (y1 f (x1))2 + (y2 f (x2))2 + : : : + (yj
f (xj ))2 n err = X i=1 yi a0 +
j X akxk k=1 !!2 where: { n is count of data points in one move, { i is the current data point being summed, { j is the polynomial order. (2) (3) (4) (5) 30 20 10 0
Sensor1 data part1
20
40
60
80
100
120
140
160
Consider we have control on a turtle on computer screen, this turtle must be
respond on a sequence of commands. These commands: forward command, is
moving the turtle in front direction a few number of units, right command
rotate turtle in clockwise direction a few number of degrees, Back command and
Left command are cause same movement but in opposite way. The number of
commands to determine, how much to move is called input commands,
depending on the application. When moving the turtle under input commands it leave
trace, this trace represent the desired object, as in Figure 3. represent simple
example for drawing on screen by steering the turtle with four commands
forward, right, left, and back command [
The recorded data trail were ltered with band pass lter and divided into individual sensor trails. For each trial we calculated polynomial tting curve with 15th order and total error minimization with least square approach. The 15th order is enough exible to smooth data, remove unwanted noise, and to keep the trend of data. After smoothing data we converted calculated curve values into text using Turtle graphics. For the turtle we used 128 commands in two right quadrants { rst and fourth. Each command represents one angle { a data trend direction. We used only two quadrants { the rst and fourth, because the time line goes from left to right and the signal does not go backwards into past. After this steps, were prepared a LZ subsequences list from turtle graphics commands list from previous step using LZ complexity for each test EEG trial. Similarities to all train trails using Eq. 1 were calculated for every test trail. Then we selected a group of training trails with similarity S satisfying following condition S Tmin ^ S Tmax for every test trail. The condition threshold values are depicted in Table 1 for all sensors. This selected group of trials is used for calculation in which category belongs the tested trial. This was calculated as a ratio of trials with movement to total count of selected trials in group, using the formula:
C = mt ct Where: { mt is a count of trails, which are marked as trail with movement, { ct is a count of trials in selected group, which satisfy condition.
The tested trail is marked as trail, which belongs to category with movement trails if C 0:5 and as a trail without movement otherwise. These steps were performed separately for all categories of data { with movement and without movement { and all sensors.
The values of Tmin and Tmax represent the shortest range R in which classi er has correctly identi ed maximum trials of both categories, with movement and without movement, with emphasis to maximum correctly identi ed trial with movement, where Tmin 2 [0; 1] and Tmax 2 [0; 1] and Tmin < Tmax, for example: R(Tmin; Tmax) 2 [0:15; 0:2] Our experiment is focused on successful detection of both data categories, data with movement and data trial without movement. Our data was divided into seven data parts. Each part contains trails from one sensor. Each data parts has two subparts. The rst data subpart contains training data { 75% of trials with movement and without movement. The other part is used as testing data sub part. This is used for our model validation. It contains 25% of trials with movement and without movement.
In our experiment we are able to detect movement of index nger with success detection rate between 56.02% and 58.78%. The best results we reach up on sensor S5 (58.78%) and S2, S4 (58.43%). The worst result is for sensor S7 (56.02%). The detection results and their corresponding threshold values for all sensor are in Table 1.
Detection rate in trials with movement varies between 36.14% (S6) and 72.28% (S7). Detection rate in trials with no movement varies between 39.75% (S7) and 77.10% (S6).
Most of the values taken by minThreshold are around 0.30 and maxThreshold values are situated around value 0.50. We made our experiments on our EEG data recorded in our laboratory from four di erent subjects performing the same task { pressing a button with index nger. The EEG data was recorded using 7 channels recording machine with sampling frequency 256 Hz. The signals were band pass ltered from 0.5 Hz to 60 Hz to remove unwanted frequencies and noise. The signals record the movement of one nger. After removing unwanted frequencies and noise we preprocessed data with polynomial curve tting with 15th order, turtle graphic { conversion from number into text and Lempel-Ziv complexity { similarity measurement.
In this paper we applied a successful approach for index nger movement detection. Our suggested approach use polynomial tting curve for smoothing recorded data and Lempel-Ziv complexity for measuring similarity between trails. Our approach is able to correctly detect EEG trail of index nger with success rate between 56.02% and 58.78%. The best results we reach up on sensor 58.78% and 58.43%. The worst result is for sensor 56.02%. Detection rate in trials with movement varies between 36.14% and 72.28%. Detection rate in trials with no movement varies between 39.75% and 77.10% .
The method proposed in this work seems to be able to detect trails with and without movement with overall successful rate more than 56.02%. It can be applied to the use on real data.
This work was partially supported by the Grant of SGS No. SP2014/110, VSBTechnical University of Ostrava, Czech Republic, and was supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070) and by the Bio-Inspired Methods: research, development and knowledge transfer project, reg. no. CZ.1.07/2.3.00/20.0073 funded by Operational Programme Education for Competitiveness, co- nanced by ESF and state budget of the Czech Republic.