biomimetic robotics and machine learning https://blog.brml.org Patrick van der Smagt's previous blog // now go to argmax.ai Tue, 27 Jun 2017 13:53:07 +0000 en-US hourly 1 https://wordpress.org/?v=4.8 58152007 paper on human hand biomechanics https://blog.brml.org/human-hand-biomechanics/ https://blog.brml.org/human-hand-biomechanics/#respond Thu, 09 Jan 2014 12:34:20 +0000 http://blog.brml.org/?p=276 Admitted, the paper is not so new: it was written in 2011 and the Springer publication path is particularly careful. But it is out, in the 2014 STAR book “The Human Hand as an Inspiration for Robot Hand Development“.

The paper, written by Georg Stillfried, lays out a highly accurate method to measure the kinematics of the human hand. The model is based on magnetic resonance images of the hand—a convoluted way of getting a model, but it does give you a rather accurate position of the bones of the hand in various positions.

Screen Shot 2014-01-09 at 12.15.23Why would one want to do this?  There is a good reason: our fingers are optimised to grip. To hold an object, and manipulate it once it is in the hand.  To do that we want to (a) exert enough force without too much effort and without discomfort, and (b) get optimal sensory, cq. tactile, feedback.  This is done by putting the “flat” part of our fingertips together.  To do that, our thumb is constructed to move towards the fingertips of the four fingers; but also the fingers are constructed such that they “move towards”  the thumb.  Your average robotic hand does not do that!  So, we wanted to understand the complete kinematics, in order to solve this problem for once and for all, and to allow robot hand designers to construct more useful robotic hands.

To gather the data, I started doing these recordings in an MRT tube many years ago. It is a tiresome ordeal: lie still with your hand for a few minutes per image, for many images in a row, adding up to many hours of agony. Any idea how loud the inside of an MRT scanner is? Anyway, Marcus Settles, co-author of the paper, needed many adaptations to the settings of his complex machine to get a good separation between bone and non-bone tissue, which was what I was interested in.

Screen Shot 2014-01-09 at 12.09.31I quickly grew tired of scanning, so we got a medical student doing that, who also did the segmentation from bone and surrounding tissue. Again tedious, taking many hours of semi-automatic segmentation. Later on we developed methods for automatic segmentation, not just since the student left but also since manual segmentation is not very reproducible, and the errors introduced there could influence our final results considerably.

Once we had the bones, how can this be used to create a kinematic model of the hand?  Georg worked with a object localisation method developed by Uli Hillenbrand, which finds known objects (i.e., bones from a reference image) in other (3D) images.  Tricky is finding the right rotation along the long bone axis, but ample parameter tuning solved that issue.

Ending up with a number of bones, the work was then completed by parameter optimisation. In the model, a multi-DoF (robot-type rotary) joint is defined between each pair of subsequent joints, and that joint must be defined with respect to its exact location, and which of its axes is rotated about.

The model ends up with 25 degrees of freedom.  That is nice: looks like 5 per finger. The joints, as said, are robotic-type joints, not the original sliding joints you find in biology (another paper by Georg focuses on that).

Enjoy our “new” paper here.

 

Screen Shot 2014-01-09 at 12.22.38

 

Note that the study is not complete. What we left out is the influence of passive movement. If you exert forces with your fingers, their positions change more and more as you increase forces, or when objects are moved in our hands. We understand that there is an exponential force–position relationship (see also this previous post) and that will give you a working hypothesis, but these measurements do not include such data.

]]>
https://blog.brml.org/human-hand-biomechanics/feed/ 0 276
new paper on grip stiffness https://blog.brml.org/new-paper-on-grip-stiffness/ https://blog.brml.org/new-paper-on-grip-stiffness/#respond Wed, 11 Dec 2013 14:14:01 +0000 http://blog.brml.org/?p=235 journal.pone.0080889.g001Our paper on human grip stiffness was finally published in PLOS ONE. The related research, performed by Hannes Höppner, showed that there is a linear relationship between grip force F and grip stiffness k(F).  Meaning, when I grip twice as firmly, also the stiffness k(F) of my fingers goes up by a factor two: k(F) = c F.

This means that, in the end, the grip is twice as “stable”. Since, when the stiffness increases, the force \Delta F needed to move my fingers \Delta x away increases by that amount. I.e., \Delta F = k \Delta x.

This in itself is not a shocking result. It is arguably caused by the biomechanical structure of the fingers: the material (tendons, ligaments) that make out the movement and stiffness of our fingers have exponential properties. When you pull at these, the force you need to do so increases exponentially with the displacement. It is a simple mathematical equation to show that that means, that force and stiffness are linearly related.

But the paper shows more than this fact, which was previously discovered by other authors. It shows that, depending on the position of the wrist, you can influence the constant between force and stiffness.  In effect, we have a wrist position where our fingers are used optimally—and, as the paper shows, we exploit it!

]]>
https://blog.brml.org/new-paper-on-grip-stiffness/feed/ 0 235
on publication practice https://blog.brml.org/on-publication-practice/ https://blog.brml.org/on-publication-practice/#comments Fri, 20 Sep 2013 09:24:42 +0000 http://blog.brml.org/?p=188 Update / June 2014: this wonderful blog http://gowers.wordpress.com/2014/04/24/elsevier-journals-some-facts/ tells you far, far more than mine on the issue.  Read it.

Update / Dec. 2013: Elsevier seems to reinforce their effort to discourage open access publishing.  A paper sharing platform, academia.edu, has been forced by Elsevier to take down certain publications.  Read the full story at http://svpow.com/2013/12/06/elsevier-is-taking-down-papers-from-academia-edu

Then, Elsevier contacted universities—read the story on U Calgary in Canada at http://svpow.com/2013/12/17/elsevier-steps-up-its-war-on-access/—–to take down papers from their websites.  This expression of mental poverty can only be the beginning of the end.

“In 2012 I decided to step back as editor of a machine learning journal published by a large Dutch publishing house, because of their publication practice. I had been with the journal for over 15 years, serving various board roles. I had and have nothing against that particular journal itself, nor against its board; indeed, its contents is generally good and it is one of the respected (indeed the oldest) journals on machine learning. But there the behaviour of the publishing house, which I consider to be very counterproductive for research, made me take this step.”

Let me explain my reasons for not liking science publication practice (but joining anyway). Scientific results are typically published like this:

  1. published research is, in most cases, funded by public money. That means, in general, the people working on research (in universities or research centres) are usually funded through government institutions;
  2. in order to inform colleagues and—where possible—the general public about the work, and of course to have one’s name associated with exciting results, a researcher (team) writes an as complete as possible article on the work, and attempts to publish it in the most suitable/most visible forum.  In short, the researchers publish a paper;
  3. other researchers hopefully pick up on the (great!) work and use that in their own research, and refer to it in their papers.

So far, so good. But there is a catch.  Whenever my co-workers want to publish a paper with me, one of the first questions is, “where shall we publish it”?  Or,

Which is the most suitable forum? Choosing a forum which counts has a few strings attached. As a researcher, you have to optimise two parameters: (1) the visibility of the paper (and therefore, of you); and (2) the credit that you receive.

It would be simple to publish on website-based forums. Free to put it there, free to read for all. But then this kind of publication does not include quality checks: anyone can publish anything, so finding good quality is difficult. Authors would not reach their readers.

Instead, journals have installed a peer-review system. Each submitted paper is sent out to two or three reviewers who are asked to read the paper, take it apart, comment on it, and send back their comments. The goal of the journal is to get good papers, which are often read (and therefore, often cited in other papers). The better the paper, the higher the number of cites, the better the journal.

The Institute for Scientific Information (ISI), now owned by Thomson Reuters, is a highly acclaimed organisation which indexes scientific publications. It looks for the most-cited papers, the most-cited researchers, and what not. What comes out of this is, for instance, the ISI IF, which we all call the “Impact Factor”.  How much impact does a journal, a researcher, a paper, etc. have?  Some ball park figures: 5 cites to a paper is not really much; hundred+ is quite good. There are “excellent” journals with impact factors of several tens; there are “bad” journals with impact factors below 0.1. These factors are then computed into the i10-index or h-index for researchers.

Why do I need a high impact factor? Well, it is one of the few numbers that researchers compare themselves which, and which is important for finding a better (research) job, getting grants, etc. Look up a researcher, look at the impact factor, and you have something to stick to.

Now, if you are a researcher and you want to publish, where would you? Right: in the journal with the highest impact factor that accepts your paper.

Again, so far, so good.

Now there is one slight snag. Journals—with a few exceptions—belong to commercial publishing houses. They are there to make money. This financial obligation usually result in putting a price to reading a paper, much like selling books. Go to any journal, e.g., Nature. You will find many articles, with an example picture, an abstract. And a link “purchase PDF” for  getting the paper itself for a price around €30.

Research institutions normally have subscriptions to a large number of journals. A typical price for a journal is several (to tens) thousand € per year; so, a library would spend millions (some accurate figures: 19 UK universities spent £14.4 million (excluding VAT) on subscriptions to journals published by Elsevier alone. – See more at: http://access.okfn.org/2014/04/24/the-cost-of-academic-publishing/#sthash.CCkzJBTC.dpuf) per year on journal subscriptions.

Unlike for books, journal authors receive no money for publishing a paper. Indeed, in some cases both the authors and the readers have to pay.

Now, it is understandable that the costs related to publishing must be paid. Even though there is very little printing to be done, still there is advertisement, manuscript handling, computing and communication costs, etc. I cannot begin to put a price tag on this, and it is irrelevant how high it is.

But is it correct that the results of publicly funded research is only available at a price? Maybe the general public is not directly interested in most research papers, but what about less wealthy universities? What about researchers in developing countries? These have no access to such paywall-protected publications.

What are the alternatives? There is a recent surge of open-access journals. These journals reverse their publication charges: in their case, the publishing author (i.e., institution) pays a fee, typically between 1500 and 4000 Euro, to publish a paper; the paper can then be read free of charge. Well-known examples are PLOS and Frontiers, except that: independent researchers have no chance to publish there, nor do researchers from developing countries.

Can’t we get rid of paid journals?

how the review process plays a role

Most reviews that I am involved in are blind: I know who the authors of the paper are, but they do not know the reviewers. That allows me to speak freely and bluntly to the authors; but on the downside, I may be biased by the authors, since very often I know them personally, or have a preconceived opinion about their work.

An alternative approach, which is sometimes used, is a double-blind review: neither the reviewer nor the author see the name of the other. That may seem to solve the problem—but only seemingly, since even there one can often, based on previous publications, guess who the authors are.

A way out would be to use a double-open approach, in which reviewers are acknowledged and, better still, reviews or commentaries are published. The workload for the reviewer is higher, of course—but would that not lead to better reviews?

An improvement on the double-open approach would be to use a grading system, in which everyone—with names being named, of course—can comment on or grade papers online. This will not only lead to majority voting, but also to accreditation of accreditors. Of course, blind votes must be prevented.

Wikipedia lists such ventures under en.wikipedia.org/wiki/Open_Peer_Commentary, of which Behavioral and Brain Sciences, a journal initiated by (the legendary open-access promoter) Stevan Harnad, was a brilliant example. The journal “Papers in physics” uses a comparative approach, I think, but I don’t know that journal (nor the field) so I cannot comment on it.  arXiv shows a free publication platform which is universally accepted in computer science, maths, and physics.

A suggestion would therefore be, that a “journal” would consist of an open access web platform where logins are given to accredited users (that step requires some thinking). Each user can post an article or a commentary to an article, and a rating system will lead to something like an impact factor for the paper. Can a person build a reputation on reviewing only? I think not; the effort in writing a scientific article is much higher, while its impact (=influence on others) is much more profound, and should be honoured accordingly. Yet, only publishing without engaging in discussions is not right, too.

Advantages: fair reviews; but also a better understanding of the papers, since commentaries of peers are included. And, much more impact of papers since those papers which are controversial or important will have high grades. High grades are better earned in such a way than by being referred to from papers in obscure conferences!

Can we get rid of publication paywalls?

Caveat lector: impact factors and researcher index vary tremendously per research area. For instance, in medical fields, paper turnarounds are very short, and an impact factor of 3 is very low. In engineering it is the other way around: 3 is very high, while people often publish on conferences which do not count in the ISI system—a “lost” publication w.r.t. impact.

Nature is one of the journals with the highest impact factor; near 40. Everyone wants to publish there!

This is, for instance, true for engineering conferences. If you publish a paper, you must pay the conference price, typically around €600, which typically includes conference attendance, conference catering, and paper publishing. If your reader wants to read it, again the standard €30 fee must be paid. So… the publisher earns from both sides. IEEE is a good example.

Indeed, publishing houses often have paywall exceptions for developing countries, based on bilateral agreements etc. That may include some, but leaves out others, as well as the general public!

Again waivers exist for certain developing countries, etc.

From the website it seems that Cambridge University Press seem to have decided to close its traditional open access, and now papers cost a daring $45.

]]>
https://blog.brml.org/on-publication-practice/feed/ 3 188
nonlinearity killed the cat https://blog.brml.org/brain-makes-movement/ https://blog.brml.org/brain-makes-movement/#comments Sat, 07 Sep 2013 06:28:10 +0000 http://blog.brml.org/?p=70 or: how our brain makes movement

When you move your arm, how does your brain make it end up where it should?  How can one play tennis so accurately? A musical instrument so quickly? The principle of movement generation in the human body looks very complex but is deceptively simple. In fact, it can be deduced quite straightforward by collecting and analysing a bunch of facts. Here are some key observations.

the premises

0. the brain is there to generate movement.  This may not be immediately apparent if you think of your own brain.  But look at it this way: every thought is aimed at optimising, in some way, a current or future movement, or learn from previous movements. Non-moving species don’t have brains (or neurons). And, as an exquisite example, the sea squirt shows: after it stops swimming around and settles on a rock, it digests its own brain (its cerebral ganglion, to be precise, explained below).

1. neural signals are slow. They travel through your nerves at speeds up to 100m/s.  This means that, a fast signal from your thumb muscles to your spine takes about 10ms. Sounds fast, doesn’t it? But it isn’t: in that time, your arm may have moved quite a bit. Look at how fast a professional pitcher moves his arm: the ball has speeds up to 170km/h or about 45m/s, meaning 45cm in 10ms. A fast move of only 20% of that would still mean 9cm of movement, before information arrives at the spinal cord.

Add to that the signal going back from your spine to your muscles plus the time to process the signal in the spinal cord, it at least doubles the delay. So we are talking more than 20ms. Now you still have to add the time for the muscles to react, ball park figure: 30ms. To cut a long story short: if you move fast, the time your neurons are able to react you will be quite a bit down the road. So, there is no way for your neurons to quickly correct movement errors it made—it must be good from the beginning.

2. muscle signals are noisy. Muscle movement is coded through two types of sensors: Golgi tendon organs (“GTO”) and muscle spindles. Muscle spindles give out signals related to the length of the muscle.  GTO signal the force in the tendon. Now, both of these are rather noisy signals. There is compelling evidence that, instead of these proprioceptive sensors, our body uses sensors in the skin to code the position of our joints. And you will have observed it: if you arm feels numb waking up from an uncomfortable position, you can’t move it without looking at it. Not because the muscles don’t work, but because your body is unable to tell where your arm is! Medically speaking, deafference is a very rare condition but a few cases of deafferented patients have been reported. In all cases, they lead to severe movement disabilities.

3. our movement is never unstable.  Chances are that you have never played with low-level control of a robot. I did, but I did not enjoy it. It is a lot of fiddling to get the parameters right; and if you don’t, the robot may well blow up in your face. Literally!  If your feedback controller, which amplifies an error signal with some factor, is wrong, that amplification may go the wrong way and magnify rather than dampen a vibration. The same can happen if you try to move a robot where it should not go: if it tries to reach a position but it cannot, because there’s a wall, it will increase its error over (short!) time and oscillate into disaster. This is one of the reasons why engineers never operate robots without emergency button—they know what can happen.

Animals don’t have emergency buttons. Sure, it would be silly to determine who presses whose; but really, in an intact specimen, movement will never become unstable. Why not? The solution is damping. Somehow, our musculoskeletal system is set up in such a way that everything is “soft” and yielding enough that we can easily absorb movement energy where necessary. How and how much precisely is a topic of research for biomechanics, and of a later blog. But this also means that the system is very forgiving for control errors. If our neurons give an imprecise command, our muscles and tendons will make sure it will be right enough.

4. our movements are precise enough. I mean fast movements, meaning: such movements which you do not constantly adapt and correct by looking, feeling, etc. For instance, returning a ball with a tennis racket. Or moving your legs for the next step. Moving your fingers to the next key. Hitting a golf ball. Catching, throwing, … All of them movements where a certain amount of precision is required, and with a bit of training we can do it.

You can turn this argumentation around and say, these tasks are all set up in such a way that our precision suffices. That is just as true. We could not type on a keyboard where the keys are 0.1mm apart. But the key observation is: we need not learn each and every possible movement that we make. Rather, we can interpolate very well, and thus learn many a task very rapidly. If you know how to do something at a point a, and you can do it at b, you are pretty well off doing it in the middle between a and b.

Of course, practice (= learning) improves accuracy. But still, after only a few tries we can deal with many, apparently challenging, tasks. Challenging for robots, for sure.

a bit on brain structure

the human brain

Brain structures seem to vary considerably between species. You will find many internet sources describing brain structure, but let me summarise as follows. Mammals have a cerebral cortex, the “grey matter”, of a few mm thick. It is folded in the brain, so there’s actually quite a lot of it. The most commonly known part of that is the neocortex, that part of the brain we relate to our thinking, behaviour, etc., and having large parts dedicated to motor (movement) and sensor (feeling, seeing, …) processing. Underneath the cortex is the white matter, which mostly acts as a communication centre, intelligently transmitting signals from one part of the cortex to the other.

The neocortex is only to be found in mammals. It was quite a surprise to me to learn that experiments with decorticated animals show that the cortex is not necessary to generate movement.  If you disable the cortex, a cat or dog can move almost just as well.  It is therefore rather likely that the motor cortex models and weighs movements, to subsequently make decisions based thereon. This has not been found in humans, by the way: with the cortex gone, there is little movement but not none.

In some experiments we did and reported in Nature, we were able to listen to neurons in a human motor cortex firing away as our participant, Cathy, observed a robot moving left and right, or when she tried to move it herself by thinking about doing the movement. Some neurons

simple brain dissectionThen there is the basal ganglia and the thalamus, located between the brain stem and the cortex.  The basal ganglia seems to be responsible for making movements, or filter out unwanted movements.  The effect of Parkinson’s disease (the inability to initiate movement) and Huntington’s disease (the inability to prevent unwanted movement) on the basal ganglia is well known and clearly indicates their function.  The Thalamus gates to and fro the brain stem, which then relays the movement to the spinal cord.  Through the spinal cord the muscle fibers are controlled.

The major role of the cerebellum seems to be supervised learning of motor patterns. But also decerebellation does not lead to complete movement loss. An individual with cerebellar lesions may be able to move the arm to successfully reach a target, and to successfully adjust the hand to the size of an object. However, the action cannot be made swiftly and accurately, and the ability to coordinate the timing of the two subactions is lacking. The behaviour will thus exhibit decomposition of movement—first the hand is moved until the thumb touches the object, and only then the hand is shaped appropriately to grasp the object.

putting them together

To best predict a movement which one has never done before—remember, all your sensory states play a role: what you see, what you feel, the weight of your clothes, the temperature, …  it’s never precisely the same—one needs a model.  This model tells you that, if my sensory state is a(t), and I want to go to sensory state a(t+1), I must use muscle activation f(a(t)).

Sounds simple.  But do not forget that, at the root, a(t) contains thousands or millions of signals, and f(a(t)) must activate thousands of motor units. On top of that, muscles are very nonlinear things: if you put in twice the activation, you do get an amount of force depending on where the muscle was, how stiff, what the other muscles do, etc. All in all, a very large collection of nonlinear things.  A model describing this must be very nonlinear, right?

Wrong.  The problem is inversion. The data you obtain describes how sensory state is changed by a movement. What you need is to find which movement to make to obtain a certain sensory state change. Meaning, you need to invert your model.  Inverting nonlinear models is difficult and, in many cases, impossible or unstable. Small errors in the model or data can lead to large errors in the behaviour—as in the robotics example above.

The only way out is to have a linear model. Because it allows for the following behaviour: if I have a model f1(a) for doing something from my sensor state a, and I have a model f2(b) for doing something from my sensor state b, then I can just use [f1(a)+f2(b)]/2 to get good behaviour in the middle. In fact, it’s the only method which generalises over all sensor states.

So this would mean that, if the result of a neuromuscular activation c is a movement x, then doubling that activation gives me 2x. Well, approximately at least. How can that be? After all, we are talking about several hundreds of control variables to activate a muscle, and many thousands to move an arm.

The answer lies in the structure of the muscles, in combination with how the spinal cord controls them. My answer is, I don’t know, precisely. But I do know that movements are, in principle, linear in the neuromuscular domain.

And now one can also hypothesise the role of the cerebellum. These movement models, between which we interpolate our movement, are stored in the cerebellum. Learning a movement more accurately means, that a larger number of cerebellar microzones are allocated to that particular movement, and that the interpolation between these become finer.  After all, we are not completely linear.

I am talking about afferent, i.e., feedback, nerves. The fastest nerves, the Ia and Ib afferent nerves, feed signals from the Golgi tendon organs (GTO) cq. muscle spindles back to the spinal cord at 70–100m/s. Type II feedback signals from the muscle spindles to the spinal cord, reacting on length change are a bit slower: about 35–70m/s. Finally, skin signals are transmitted through type III afferents at 10–30m/s. See E. Kandel, J. Schwartz, T. Jessell, Principles of neural science, McGraw-Hill, 2000.

In fact, we measured delays of approximately 25ms between the activation of a wrist muscle spindle and the activation of the corresponding muscle.

Please quantify! I hear you say. That is not easy. This paper says something about that, but it does not try to find a signal-to-noise ratio. Just believe me, these sensors are too noisy. And on top of that: please remember that there is a lot of flexible tissue between the sensors and the joint itself; they do not measure where the movement is. That is another source of error, and even a highly accurate technical sensor could not solve that.

Published in the following papers:

  1. Edin BB, Quantitative analyses of dynamic strain sensitivity in human skin mechanoreceptors. J Neurophysiol 92(6):3233–3243, 2004
  2. Johnson KO, Closing in on the neural mechanisms of finger joint angle sense. Focus on “quantitative analysis of 
dynamic strain sensitivity in human skin mechanoreceptors”. J Neurophysiol 92(6):3167–3168, 2004
  3. Edin BB, Cutaneous afferents provide information about knee joint movements in humans, J Physiology 531(1): 289–297, 2001

There will probably be more papers, but I happen to know these:

  1. Ghez C, Gordon J, Ghilardi MF (1995) Impairments of reaching movements in patients without proprioception. II. Effects of visual information on accuracy. J Neurophysiol 73:361-372
  2. Gordon J, Ghilardi MF, Ghez C (1995) Impairments of reaching movements in patients without proprioception. I. Spatial errors. J Neurophysiol 73:347-360
  3. Rothwell JC, Traub MM, Day BL, Obeso JA, Thomas PK, Marsden CD (1982) Manual motor performance in a deafferented man. Brain 105 (Pt 3): 515-542

Yes, that includes humans, of course. We’re in the Animalia kingdom, our phylum is Chordata, class Mammalia, order: Primates.

Nasty business, really, to deactivate the cortex of such an animal, but there it is. These two, and some more recent, papers describe that these animals exhibit little change in their movement—except that males cannot mate anymore. Think of that.

  1. Culler E, Mettler FA (1934) Conditioned behavior in a decorticate dog. Journal of Comparative Psychology 18:291-303
  2. Bjursten LM, Norrsell K, Norrsell U (1976) Behavioural repertory of cats without cerebral cortex from infancy. Experimental Brain Research 25:115-130

Doya K (2000). “Complementary roles of basal ganglia and cerebellum in learning and motor control”. Curr. Op. Neurobiology 10 (6): 732–739. doi:10.1016/S0959-4388(00)00153-7. PMID 11240282.

The scientifically interesting paper Holmes, G (1939). The cerebellum of man. Brain, 62, 1–30 describes a few clinical cases related to shot wounds.

One counts in the order of 250.000 muscle fibers in the biceps muscle, for instance. See this publication, which you can read online, or others which unfortunately are behind a paywall.  But then, one motor unit—i.e., one alpha motor neuron and the muscle fibers it controls—has between 10 (eye) and 1000 (thigh) muscle fibers.  So, you can count a few hundred motor units, therefore a few hundred motor neurons, per large muscle.

This is, in fact, very much but not precisely in line with the old models described in Marr DA (1969), A theory of cerebellar cortex, J. Physiol. 202, 437–470 and Albus JS (1971), A theory of cerebellar function, Math. Biosci. 10, 25–61.

]]>
https://blog.brml.org/brain-makes-movement/feed/ 2 70
about smoothing data https://blog.brml.org/different-data-differences/ https://blog.brml.org/different-data-differences/#respond Tue, 20 Aug 2013 21:25:53 +0000 http://blog.brml.org/?p=15 A boring post.

Suppose some system can be (partly) described by x(t), e.g., the position of the wrist of a person over time.   When measuring position x(t), one obtains data \overline x(t) = x(t) + \varepsilon(t).  This leads to catastrophes when a derivative must be determined.  A standard way to compute the derivative is given by

    \[x'(t_i) = {x(t_i) - x(t_{i-1}) \over t_i - t_{i-1}}\]

which delivers the actual derivative for \lim  t_i - t_{i-1} \rightarrow 0\dots by definition.

But when the signal has noise \epsilon, the situation is radically different.  If we use the same, numerical, approach to find derivatives, we find that 

    \[\overline x'(t_i) = {(x(t_i)+\epsilon(t_i)) - (x(t_{i-1})+\epsilon(t_{i-1}) \over t_i - t_{i-1}} = x'(t_i) + {\epsilon(t_i) - \epsilon(t_{i-1}) \over t_i - t_{i-1}}.\]

 Now, since we assume that \epsilon is normally distributed noise, it can be as positive as negative, and when \epsilon ranges from \epsilon_\mathrm{min}<0 to \epsilon_\mathrm{max}>0, then the extra term \epsilon(t_i) - \epsilon(t_{i-1}) has twice that range.

So, differentiation of a noisy signal doubles the noise!

The filter

Consider what happens when differentiating such a signal twice, to get the acceleration: double double means four times as much noise.  Clearly, this is not the way to go.

A student, who is (made) aware of this fact, will then go on to smooth or filter the original signal.  A good idea.  Terminology here is discipline-dependent and often leads to confusion.  An engineer, who has enjoyed a control theory class, will try to build a low-pass filter, which is an input-output system passing low signal frequencies, while blocking higher frequencies.  The engineer will look at the data \vec x as a summation of frequencies, thus describing x without its index t.  A computer scientist, however, will rather look at a sequence of single measurements x(t), and thus does not directly consider frequencies as a mode of describing the signal.

The engineer’s view has a strong advantage: by looking at the complete data \vec x, one can analyse which “band” of frequencies, occurring in the signal, are desired, and which can be considered noise.  The correct choice of filter (typically, your engineer will like some version of a Butterworth filter, which is the closest you can get to an ideal filter with amplification 1 at desired frequencies and 0 elsewhere;  Mr. Butterworth was a perfectionist) will take out those (high) frequencies related to noise, and leave the rest in tact.

So far for the theory.  In practice, there is a small snatch with the above: when running a process (let’s say, controlling a robot in real time) the data are not available in a whole, but one data point comes in after the other.  So, indeed I get data points \overline x(t), and I do not want to wait to gather enough data, in order to apply my filter.

delay-free filtering

That is, in fact, the crux: can smooth out a signal delay-free?  Yes, and it is relatively easy.  The idea is to make a model of the data, and use that to predict the next step.  The following approach is very applicable to robotic movement, as movement can be well described using polynomials of low order (in fact, up to 5 for fast movements [why 5?  What is fast?  I will cover that elsewhere.])

A standard approach to smoothing out data is a Moving-Average (MA) filter.  The basic principle is simple: the smoothed value y is set to y(t)={1\over n}\sum_{i=-n/2}^{n/2-1} \overline x(t+i).  It works, but has a disadvantage: it lags.  Even if we only take data from the past, i.e.,  y(t)={1\over n}\sum_{i=-n+1}^{0} \overline x(t+i).

What does this do?  In fact, it fits the data \overline x(t) to a straight line, and—in the second case above, where only past points are taken—extrapolates from that.  A linear model is good, if the underlying data x is linear, and the noise \overline x - x isn’t (with respect to n, the number of points we smooth over).  But otherwise?  It will fail.

The bad news: for the kind of (movement) data we are talking about, the linear assumption does not hold. We need to find a better model. An elegant method was described in 1957, by which orthogonal polynomials fit a set of data until an error level is obtained which is around the variance of the data .  Orthogonal polynomials means that, a higher order can be added without having to recompute the previous parameters.  The solution that is found, in a predictive form, is

    \[y(t) = \sum_{i=0}^{n} \overline a_i t^{i};\]

a_i are parameters found from optimisation.  A very attractive method, obtaining the same, was published in 1964 ; in this paper, it is shown that the parameters C of the equation

    \[y(t) = \sum C_i \overline x_i\]

can be precomputed, independent of the data x, leading to a very efficient implementation.

The standard implementation of this well-known Savitzky-Golay (“SG”) filter introduces a delay.  After all, it predicts the value of the data at the centre point, using data points -n\dots n.  But with some tricks, it can be made predictive, too.  How?  A first, not quite correct, approach is to, well, pretend you’re half blind: match the polynomial only on the first half of the data, and predict the “middle” from there.  A method which, dumb as it is, gives acceptable results.

The right way is to recompute the SG parameters—the C_i above—to predict the last rather than the middle data point for the polynomial.  In fact, an elegant solution was published in .  It computes the parameters differently and more efficiently, and that we can use to make a “predictive” filter.  Here’s an implementation of a piece of code doing the promised work: psgolayp.  (My sincere apologies that it is written in Matlab.  I don’t like Matlab all that much, but for historical reasons it came out this way.  I promise it may be the last piece of Matlab posted here.)

So now never come to me again with a moving average filter.

]]>
https://blog.brml.org/different-data-differences/feed/ 0 15
about this blog https://blog.brml.org/hello-world/ Mon, 19 Aug 2013 18:53:27 +0000 http://blog.brml.org/?p=1 This blog will express my personal opinions, at best. Or even less. It has no relationship whatsoever with any company or organisation that employs or employed me. You can find a bit about my scientific background by looking at my papers, most of which you will find at http://brml.org/people/smagt/ \sqrt2

Papers are something good: one must really be careful, since your peers (often friends) will read them, review them, and judge you on it. But papers are something bad: you must worry about the right journal, the right publisher, impact points… all of which one would rather ignore, but that is not always possible.

I have learned to dislike publication practice, as it often leads to abuse; both by the publishers as by the published. So… here you will find “unpublished” thoughts and results, or sometimes  perhaps prepublished ones. Will see.

]]>
1