Dynamic Time Warping

Dynamic Time Warping (DTW) is a fabulous tool that I use in various applications with students in R2P2 Lab (https://uniter2p2.fr/  for ballistocardiography, pressure measures, gait analysis...).

Quoting wikipedia:

"In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences which may vary in time or speed. For instance, similarities in walking patterns could be detected using DTW, even if one person was walking faster than the other, or if there were accelerations and decelerations during the course of an observation."

In redCV we use a basic DTW. The objective is to find a mapping between all points of x and y series. In the first step, we will find out the distance between all pair of points in the two signals. Then, in order to create a mapping between the two signals, we need to create a path. The path should start at (0,0) and want to reach (M,N) where (M, N) are the lengths of the two signals. To do this, we thus build a matrix similar to the distance matrix. This matrix would contain the minimum distances to reach a specific point when starting from (0,0). DTW value corresponds to (M,N) sum value.

Results are pretty good for 1-D series.

Now, the question is can we use DTW in image processing? And the response is yes. Images can be considered as a long 1-D vector, and then we can compare two images, as x and y series, to find similarities  between them. 

Now imagine we must compare characters to measure similarity between shapes such as hand-writing productions for example: DTW gives us a direct measurement of the distance between characters. 

If the characters are identical, DTW equals to 0 as illustrated here:

Now consider b and d characters that are close but different by orientation. In this case, DTW value increases.

dtwFreeman.red and dtwPolar.red illustrate this technique for comparing shapes in image. dtwFreeman.red   is a fast version that use only Freeman code chain to identify external pixels of shapes to be compared. dtwPolar.red is more complete since the code associates Freeman code chain and polar coordinates transform to creates X and Y DTW series. Both programs use rcvDTW functions:  rcvDTWDistances,  rcvDTWCosts and  rcvDTWGetDTW.

These techniques were successfully used for a scientific project comparing cursive vs. script writing learning in French and Canadian children. Data were recorded with a Wacom tablet and then processed with Red and RedCV. Each child’s production was compared to a template, and DTW was calculated allowing to reduce the complexity to a sole value, and then allowing statistics on data.

All code is here: https://github.com/ldci/redCV/tree/master/samples/signal_processing. 

You can do great things with Red!

 

Giving voices to your apps

I'm starting to think about developing multimodal interfaces (vision and sound) for Red. With macOS it's quite easy because we can use the ‘say’ system command. For Windows and Linux, I'd be delighted if other developers came up with a similar solution.

Here (https://github.com/ldci/Voices) are a few examples of how to use this command with Red and Rebol 3.

This is an example of Red code:

#!/usr/local/bin/red-view
Red[
Author: "ldci"
needs: view
]
;--for macOS 32-bit (Mojave) 
;--new version 
voices:         []
languages: []
sentences: []
flag:                 1
filename:   %voices.txt
getVoices: does [call/shell/output "say -v '?'" filename]
loadVoices:  does [
vfile: read/lines filename
foreach v vfile [
tmp: split v "#" 
append sentences tmp/2
trim/lines tmp/1
append voices first split tmp/1 space
append languages second split tmp/1 space
]
a/text: sentences/1
f/text: languages/1
]
generate: does [
prog: rejoin ["say -v " voices/:flag " " a/text]
call/shell/wait prog
]
mainWin: layout [
title "Voices"
dp1: drop-down data voices
select 1
on-change [
flag: face/selected
f/text: languages/(face/selected)
a/text: sentences/(face/selected)
]
f: field center
button "Talk" [generate] 
pad 100x0 
button  "Quit" [quit]
return
a: area 450x50
do [unless exists? filename [getVoices] loadVoices]
]
view mainWin

And the GUI result

A very interesting approach is now proposed by Oldes for macOS and Windows: https://github.com/Oldes/Rebol-Speak/releases/tag/0.0.1

Minimalistic but efficient :

#!/usr/local/bin/r3

Rebol [

]

speak: import speak     ;--import module

with speak [

list-voices     ;--list all voices

say/as "Hello Red world!" 15             ;--english voice

say/as "Bonjour Red!" 166     ;--french voice

]

And a Windows equivalent of macOS say developed by Philippe Groarke: https://github.com/p-groarke/wsay?tab=readme-ov-file

And also Jocko's tests for Windows  and macOS: https://github.com/jocko-jc/red-tts

The code was initially developed for Rebol and is now updated for Red.

Using Unicode Characters with Red

 Unicode characters can be used with Red for making nice GUI apps. 

A sample code is here: https://github.com/ldci/Unicode/blob/main/Red/unicode5.red

But results are slightly different with macOS and Windows versions of Red.

With macOS, unicode characters are correctly displayed in a text-list (I mean with coloured characters).

This is not the case for Windows version with a black and white text-list.

This is probably related to a difference in backends for Red/View related to OS.

But, another difference is also observed when you use to-image function such as

button 200 "Copy to the clipboard" [

img: to-image cc

write-clipboard img

view [title "Image Copy" image 400x300 img button "Close" [unview]]

]

macOS gives an expected result with correct size and position.

Windows not: image is not correctly copied to the clipboard with correct size and position.

Why these differences? Not tested with Linux version of Red.

Thanks to qtxie for the fix :). Now macOS and Windows versions are similar.

Red team is very responsive !

Using Z-score with Red or Rebol 3

 Detecting anomalies (outliers) is a classical problem in statistics and computer science.

https://medium.com/@akashsri306/detecting-anomalies-with-z-scores-a-practical-approach-2f9a0f27458d 

Z-score can help to solve this kind of problems. Z-score is calculated as follow z = x - mean / SD  where x is an individual value in the distribution, mean is the average of all distribution values and SD is the standard deviation of the data.

When applied on Gaussian distribution of data, Z-score generates a new distribution with mean = 0.0 and SD = 1.0. This is important when you need to compare data with different scales. 

Then we can use a threshold to identify outliers. A threshold value is a  cutoff point that helps determine what is considered as an anomaly or outlier within the values distribution.  Many scientists use the Z-score to exclude values they consider to be outliers from the data: values greater than 2 SD or less than 2 SD will not be retained. 

But, we can also use Z-Score for extracting significant values from a noisy signal, with these general considerations: There is basic noise in the signal with a general mean and SD of all timeseries. There are data points that significantly deviate from the noise (peaks).

I've found a good explanation here:

https://stackoverflow.com/questions/22583391/peak-signal-detection-in-realtime-timeseries-data of how we can deal with this problem.

The basic idea is simple: if a datapoint in the series is a given x number of standard deviation away from a moving mean, the algorithm gives a signal (equal to 1 ) which means that the datapoint is emerging from the noisy signal.

This is a Red/Rebol 3 function which illustrates how to do.

zThresholding: function [
data      [block! vector!]
output    [block! vector!]
lag           [integer!]
threshold [decimal!]
influence [decimal!]
][
sLength: length? data
filteredY: copy data
;--Red 
avgFilter: make vector! reduce ['float! 64 sLength]
stdFilter: make vector! reduce ['float! 64 sLength]
;--R3
avgFilter: make vector! reduce ['decimal! 64 sLength]
stdFilter: make vector! reduce ['decimal! 64 sLength]

avgFilter/:lag: mean data lag
stdFilter/:lag: stdDev data lag
i: lag
while [i < sLenght][
n:   i + 1          ;--index of the next value
y:   data/:n
avg: avgFilter/:i
std: stdFilter/:i
v1: abs(y - avg)
v2: threshold * std
either v1 > v2 [
output/:n: pick [1 -1] y > avg
filteredY/:n: (influence * y) + ((1 - influence) * filteredY/:i)
][
output/:n: 0
]
avgFilter/:n: mean   (at filteredY i - lag) lag
stdFilter/:n: stdDev (at filteredY i - lag) lag
i: i + 1
]
filteredY
]

And the result for Red:

And Rebol3:

See for the code for Red and Rebol: 

https://github.com/ldci/redCV/blob/master/samples/signal_processing/peaks.red

https://github.com/ldci/R3/tests/blob/main/signalProcessing/zscoreFilter2.r3