Spir-o-Spell, an optimized MI-based BCI Speller

Brain-computer interfaces (BCIs) have played a crucial role in establishing or improving the way LIS (Locked-In Syndrome), ALS (Amyotrophic Lateral Sclerosis), and other similarly affected patients communicate with others. While most BCI research efforts are focused on signal acquisition and processing hardware and software, BCI spellers are vital in the final step of the communication process in which brain signals are transformed into written or spoken language. Generally, BCI spellers are computer programs that interpret brain signals acquired by a BCI system and convert them into letters/characters. This is especially important for patients who have lost all movement ability and have no other way to communicate (such as in Total LIS patients).

Based on the various types of brain signals, BCI spellers use different EEG paradigms such as Event-Related Potentials (ERP), including P300 and SSVEP, or Sensorimotor Rhythms (SMR), also called Motor Imagery (MI). The work described in this post builds on the SMR-based paradigm. SMRs seem to be the best signal type for BCI spellers for LIS patients considering that other methods require at least some limited functional muscular activity. One of the most successful and well-known MI-based BCI spellers is Hex-o-Spell proposed in 2006 by Blankertz et al (https://www.researchgate.net/publication/45488894_The_Berlin_brain-computer_interface_presents_the_novel_mental_typewriter_Hex-O-Spell), which has served as the basis for many other variations such as Cake Speller, Center Speller, Oct-o-Spell, and more.

The Spir-o-Spell BCI speller proposed here, also based on the original Hex-o-Spell, presents an attempt to optimize the arrangement of the characters in the ‘typewriter’ and, ultimately, improve the LPM (letters per minute) performance. Spir-o-Spell aims to achieve this goal in two ways:

1. Arranging the characters based on the frequency of use in the English language (can be adapted for any language)
2. Arranging the characters to minimize the steps (and, consequently, the time) of selection

Cornell’s frequency of use table will serve as basis for the placement of English letters in the Spir-o-Spell: http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html.

The 4 additional characters proposed by Blankertz et al (space “_”, period “.”, question mark “?”, and backspace “<”) seem to be the minimum necessary for a complete sentence construction. Research on MI shows that when subjects are asked to imagine limb movement, an accurate SMR signal is detected in 75% of cases. This suggests that the backspace character will be used to rectify an incorrect character selection approximately 25% of the time, making it the most used character in this context.

Since an average standard English sentence contains 17 words (https://techcomm.nz/Story?Action=View&Story_id=106), and one word contains, on average, 4.79 letters (http://norvig.com/mayzner.html), the frequency of the “space” character is (16) / (17 x 4.79 + 1 + 16) = 16.26% (16 spaces between words, 1 punctuation mark at the end of the sentence). Modifying the above calculation for punctuation marks, the average frequency of the period is 1.12% and that of the question mark is 0.10%. (https://en.wikipedia.org/wiki/English_punctuation).

As a result, the overall ranking of the 30 characters (26 letters and 4 other characters) is shown in Table 1.

In the original Hex-o-Spell speller, these 30 characters are grouped in 6 hexagons with 5 characters per group and one empty space that allows the subject to return to the previous selection step. Thus, to choose a certain character, the speller indicator will move N + M steps where N is the number of steps to select the group and M is the number of steps within that group to reach the desired character (all movement is in clockwise direction). For instance, to choose the letter N, it takes 3 steps to first select the desired group and then 3 more steps inside the group for a total of 6 steps.

The first optimization aimed to rearrange the characters in the Hex-o-Spell speller based on the frequency of use; in order to evaluate the performance of the new configuration and compare it to the original one, the number of steps needed to reach each character has been multiplied by the frequency of the character in the English language and the (weighted) average steps to select a character has been calculated.

The arrangement of the characters based on their frequency of use in the English language has a significant effect on the performance of the speller, decreasing the average number of steps to choose a character from 7.31 to 4.15, a reduction of 43%.

The next step in this analysis is to determine if there exists another combination of groups and characters/group that further optimizes the selection process. The optimal solution would be one in which the characters are selected using the minimum number of steps possible. Let’s simplify the graphic representation of the Hex-o-Spell and try to identify a pattern in the number of steps needed to select a character. For ease of understanding, the 6 groups will be shown in a linear configuration (instead of hexagonal) and the number of steps to reach each position is shown inside the squares.

This simplified representation indicates that there is only one position that can be selected with 2 steps (group 1, char 1), two positions with 3 steps (grp1-char2 and grp2-char1), three positions with 4 steps (grp1-char3, grp2-char2, and grp3-char1), and so on. Also, it is interesting to observe that the positions of the characters needing the same number of steps follow a spiral pattern approaching the center of the diagram. The red lines connecting positions requiring the same number of steps show clearly that this speller configuration uses all available positions for the 2-step up to 6-step sets for a total of 15 positions (1 of 2-step + 2 of 3-step + 3 of 4-step + 4 of 5-step + 5 of 6-step = 15 positions or characters).

However, there is a disruption of this rule for the 7-step positions: there are only 5 of them instead of 6. The reason is that the first 7-step position has to be grp2-char5 because there are no more available positions in group 1. This means we can add 5 more characters to the 7-step sets (20 total including previous sets), while the 21^st character (U as per table 2), will have to be placed in an 8-step position, adding one unnecessary step to the spelling process. To avoid this, it will be necessary to add one more character at the end of group 1 increasing the number of characters from 5 to 6.

The anomaly follows with the 8-step positions set, which appears to be limited at both ends of the spiral: there are two positions missing in groups 1 (char 7) and 2 (char 6) at the beginning of the spiral and one position missing at the end of the spiral as a potential new group (grp 7, char 1). The missing positions limit the number of 8-step positions to 4 instead of 7, causing the unnecessary addition of one step (from 8 to 9) for 3 characters.

Following this logic and adding single positions and new groups to reduce the number of steps where possible, the final result looks like the diagram below:

In the above diagram, all various sets with the same number of steps have been fully utilized before moving up to the next set and all sets (except of the 9-step set) spiral down inward and reach the center of the diagram. There is no need to add more 9-step positions since only 30 positions are needed for the entire set of characters. Based on the spiral shape of this diagram and following the naming pattern of previous spellers, the proposed name for this BCI speller is Spir-o-Spell.

The table below is a comparison of the new and optimized speller compared to the original and the modified Hex-o-Spell:

The frequency- and step-optimized Spir-o-Spell results in an average of 4.01 steps/char which is a further improvement of 3.6% compared to the modified Hex-o-Spell.

The final version of Spir-o-Spell is shown in the figure below:

After receiving a MI signal from the user, the first group of 8 characters will appear at the center of the speller for a certain amount of time (to be determined for the specific user), while the other groups will fade away or be greyed out. If no signal is received during this time, the second group will appear at the center and the first group will be moved back to the original position and greyed out. If the desired character is included in the group shown at the center, the user will send a MI signal through the BCI system. Once the signal is received, the characters of that specific group will be displayed one at a time at the center of the diagram for the same period of time. If no second signal is received by the user, the process will continue with the next character until the desired letter has been selected. After the selection of the character, the process will restart from the first group to select the next character. The procedure will thus need only one type of signal to start and select characters, but it is also possible to use two different signals (such as left hand – right foot) for the same purpose.

Following the above reasoning, it is possible to design optimized BCI spellers for sets with various numbers of characters. The first step of the process would be to find the initial number of groups: this is done by adding the integers starting from 1 until there are enough positions to hold all characters. For instance, for a 40-character set, the initial number of groups will be 9 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45). This number contains 5 excess positions (45 positions vs 40 characters); to reduce it to the necessary 40, the excess positions will be removed by eliminating one position in each group starting from the lowest one. In this case, the last group (having only one position) will be eliminated (1 – 1 = 0 positions) and the other 4 groups will be reduced to 1, 2, 3, and 4 positions respectively. The resulting speller will have therefore 8 groups of positions: group 1 – 9 positions, group 2 – 8 positions, group 3 – 7 positions, group 4 – 6 positions, group 5 – 4 positions, group 6 – 3 positions, group 7 – 2 positions, and group 8 – 1 position for a total of 40.

A comparison between Spir-o-Spell and Hex-o-Spell of the total number of steps necessary to spell real word sentences up to 30 characters (about 6 words) can be simulated in the spreadsheet below (error corrections are excluded).