1 Introduction

Human motion is one of the more interesting fields of research. This could be because the mechanism of human motion is designed by nature. The study of human motion reveals information that can be used in diverse fields including psychology, sociology, and computer science. In the case of humans, motion analysis reveals a wealth of information about their nonverbal behaviors. For example, observing or imitating the gait of a walking person can reveal what the walker is feeling [1]. This is because the study of human motion is directly related to the study of human behavior, as various motions in our body occur as result of spontaneous behavior arising within us. Thus, the visual analysis of such motion often attempts to detect and identify agents, emotions, and even the physical and mental conditions of a body. This analysis is normally carried out by interpreting sequences of images involving human moves. This is also supported by the fact that human visual perception is very sensitive to motion patterns and could reveal abundant information about the different traits of a person. However, despite our continuous effort and study, the understanding of how exactly all these complex biological and psychological perceptions are encoded in a meaningful visual motion pattern that enables humans to identify other individuals is still in the stage of research [2].

Human gait refers to the rhythmic physical movement of body parts. It is said to be unique in the sense that humans have a distinctive ability to use it to identify their close friends and family easily. For instance, in an experiment done by Johansson [3], he placed light markers with small lights points to a subject’s main joints and recorded the action of walk so that the lights were highlighted against a dark background. With this demonstration, he proved that optical perception from the biological motion of relatively less light points were enough for a person to identify the motion pattern of a known walker.

Human gait is also unique because, just like many animal behaviors such as flying, swimming, or walking, it requires a pattern of rhythmic contraction of muscles that is controlled by a dedicated neuronal circuit called the central pattern generator [4]. Basically, each and every individual has a unique walking pattern; therefore, it can be considered to be one of the reliable sources for human recognition.

2 Related works

Human motion has been investigated internationally. As gait analysis does not require a person to face the sensors directly, it can be done without the knowledge of the subject. This is also a reason why many security agencies and defense units around the world work in this field [5]. Some similar investigation in human motion includes research by the Defense Advanced Research Project Agency, which financed a multi-institutional project on video observation with the primary objective of developing a computerized video processing technology that allows a single operator to observe activities over complex areas including war zone and noncombatant scenes. The project, named W4, used a mixture of figure analysis and tracing, and developed a prototype of individuals’ presences to empower it to identify and track multiple people as well as observe their actions, even in the presence of obstructions in an outdoor environment. Likewise, Hofmann et al. have developed a version that also extracts information from a person’s image, such as the shadows on his/her clothing, which leads to a more detailed signature. They have developed a prototype that can track people (by their gait) as they move through a laboratory building [6].

The field of gait analysis is a comparatively dynamic subject of research in the field of computer science. Many contributions are based on the analysis of walking motion in 2D images using several series of video frames and deploy several processing techniques to derive the features [7, 8]. Looking at these studies in detail, most focus on overall gait movement, but none focus on finding the relationship between the gaits of several individuals. Therefore, the aim of this research is to generate a unique numerical signature that is similar for the different gaits of a particular individual but different for different individuals.

The objective of our work is to investigate the feasibility of applying genetic programming (GP) to evolve unique signatures for human gaits. In addition, we explore the viability of using collaborative filter to solve two of the most serious drawbacks of GP in real-world problems: (1) non-determinism and (2) lack of generality of the evolved solutions.

3 Computational methodologies

This study employed several approaches and methodologies to achieve experimental results as follows.

3.1 Data acquisition

Acquiring the data of a human gait/walk is the first and major stage. It involves the detection of a moving human and generation of the skeleton frame from the captured data. For this step, we use the Microsoft Kinect for Windows as the sensing device. This device was chosen for our task because of its off-the-shelf availability, ability to detect human motion, and ability to generate a skeleton with 20 different joints from the detected human body [9]. Raw data obtained from the sensor are integer values of the X, Y and Z (3D) co-ordinates. But, we only employed X and Y (2D) co-ordinates for our study. The image in Fig. 1 shows the parameter that could be obtained from the Kinect sensor. The left side of Fig. 1 shows the joint position that could be ascertained from the Kinect sensor, whereas the image on the right side depicts the co-ordinate position in a 3D space. These data are further used to analyze the gait pattern of different individuals for the initial study. However, the accuracy of the acquired data depends upon the internal architecture of the sensor—we experienced random noise in the dataset and used a sliding (moving) window average to minimize it.

Fig. 1
figure 1

Possible joints that could be extracted from Kinect sensor (left), and the sensor direction and co-ordinate in 3D space (right) [10]

Full size image

3.2 Pre-processing

The next task after data acquisition is the pre-processing of the raw numerical data obtained from the Kinect. These raw data, comprising the skeleton joint coordinates, are first stored in the database and then processed to reduce the amount of noise. The data acquired from the sensor contain a significant amount of noise and flickering; therefore, the dataset needs to be filtered. This is done using a statistical model known as a sliding window average method [9]. This method is useful as it helps to smooth dataset while preserving the features (i.e., main frequencies, amplitudes, and gradients) of the dataset.

3.3 Feature extraction

Feature extraction is associated with the task of finding the general features that could be used as a set of terminals in the genetic program. To make the features more general and natural, we calculated some distinctive features such as the angle, angular displacement, angular velocity, distance, and relative change in distance between the joints. All these features were calculated from the preprocessed dataset for a few selected joints, namely, the arm, shoulder, leg, and hip [9]. Because features were calculated on a frame-by-frame basis, they were further minimized using an average operation.

3.4 GP

The fourth step involves the use of evolutionary approaches to train the system. GP was used to evolve the mathematical function (formula) of the extracted features (terminal symbols) of the gaits. This function should be optimal in that it has to be evaluated into values that are similar for the gait of the same person, yet different from the values of the gait of different persons [9]. For this task, we applied our in-house XML based GP framework (XGP) [11]. The main parameters of XGP are shown in Table 1, and a simple snapshot of GP manager is provided in Fig. 2.

Table 1 The main parameters of GP
Full size table
Fig. 2
figure 2

Screenshot of the GP Manager (top) and a fragment of the tree representation of a sample genetic program (bottom)

Full size image

The outputs from the XML GP are mathematical functions consisting of the terminals and function sets provided in the XML tree structure. Figure 2 shows a screenshot of XML GP Manager and a parse tree view of the generated genetic programs.

3.5 Collaborative filtering

GP is a powerful evolutionary computing technique, as it helps to uncover previously undefined methods in problem solving. However, there are two serious drawbacks when using GP for real-world problems: (i) non-determinism: because of the randomness incorporated to some extent in the main GP operations (i.e., initial population generation, selection, crossover, and mutation), different independent runs of GP result in different best-of-run solutions (functions). Even if their fitness values are the same, they may differ substantially in their contents. For instance, if we follow the empirical evidence in fitness convergence shown in Fig. 3, we could notice that the obtained solution for 20 different independent runs shows different characteristics; first, none of these obtained solutions are the same. Second, the required generation to evolve is different, which also means variation in runtime required for each evolution. Therefore, this evidence also clearly highlights the non-deterministic nature of the evolved solution. (ii) Lack of generality of the obtained solutions: some of the evolved formulas might be good for particular test sets but not others. Table 2 shows two random solutions with their fitness value on training or learning case, fitness value on test case, and number of nodes in evolved GP tree function. Since both solutions given in Table 2 have the same fitness value on training, they are equally good while training; however, during test cases fitness value of these evolved programs varies substantially. In short, different best-of-run solutions are almost equally good on learning set, but behave differently, either good or bad on test set. Additionally, even if their fitness values are the same during learning, the difference in the number of nodes shows that they vary significantly in their contents. Because in canonical GP, we usually deploy and use only one best-of-run solution, we do not know which one would be good for a given particular case of test set, which introduces additional challenges in finding generalized solution for a particular set of problem while adopting GP.

Fig. 3
figure 3

Fitness convergence characteristics for 20 independent runs of XGP; the dashed line represents the average fitness value convergence

Full size image
Table 2 Parameters of two sample best-of-run evolved solutions
Full size table

We investigate two approaches to address these issues, (1) averaging and (2) voting, which we referred to as collaborative filtering.

3.5.1 Averaging

The averaging concept for several genetic programs is implemented by selecting a number n of the best genetic programs from the pool of best genetic programs generated over r different runs during the training stage of our approach. In our experiment, we selected the n = 5 best genetic programs over r = 20 independent runs. During the test stage, the signature for classifying two persons (A and B) is calculated by averaging the signatures of these n best solutions. This signature is used as a threshold for the test. We believe that applying this method could help to create a generalized signature and a mechanism to establish a general solution from among several of the best genetic programs. This concept can be further expressed in the following equation:

$$ {\text{Id}} = \frac{{{\text{Gp}}_{1} + {\text{Gp}}_{2} + \cdots + {\text{Gp}}_{n} }}{n}, $$

where Id is the signature value for identification and Gp i is the i-th signature obtained from the best-of-run genetic programs.

3.5.2 Voting

In addition to averaging, we also experimented with the concept of voting for the final classification. This method can be considered as each gait undergoing a trail with different experts (in this case there are five experts, “represented” by the five best-of-run genetic programs). Each expert provides an opinion about the gait as to whether it is Person A’s or Person B’s. The final decision depends on the majority of the votes from the experts.

4 Experimental results

The experiment was conducted in a laboratory setup. Data were collected from two subjects who were requested to generate three different gait movements: (1) normal walk, (2) slow walk, and (3) fast walk. Note that the data for the two subjects were acquired one after another. The sensor was placed perpendicular to the walking direction at a distance of around 3–4 m.

The fitness convergence results for 20 independent runs of XGP are shown in Fig. 3. It is clear from the figure that some genetic programs progressed beyond the 58 generations, while others were able to achieve the terminating criteria (as shown in Table 1) in fewer generations. However, this differentiation does not make any significant distinction in the experimental results, as we only select the best genetic programs from the pool of evolved genetic programs. Furthermore, not all genetic programs can be expected to provide the best solution for all the cases. The dashed line indicates that the average fitness score improves from approximately 80 to 5, which highlights the evolving nature of the genetic programs and indicates that evolution is progressing.

Figure 4 illustrates the scaled signature using the average of the five best genetic programs, which is used as the basis for classifying persons A and B. Moreover, the signature is simplified by dividing them both by the lesser of both signatures which naturally results in signature values for B and A of 1 and greater than 1, respectively. This signature serves as a criterion for the classification of gaits of both subjects.

Fig. 4
figure 4

Scaled signature and classification criterion for Person A and Person B

Full size image

4.1 Experiments without collaborative filters

During the initial testing, we simply used the genetic program that had the lowest fitness value among several best evolved genetic programs. Figure 5 illustrates the result of classifying two persons without the collaborative filtering. Test 1 to Test 5 in Fig. 5 are the five new test cases we used to obtain classification results. For this initial result, we correctly classified three out of five tests (Test 2, Test 3, and Test 5) using the classification criterion in Fig. 4. However, we further experimented with the voting method. To be clear, Fig. 6 shows an implementation of voting only for Test 1, and Fig. 7 shows the final result using the voting method for all five test cases.

Fig. 5
figure 5

Results of each gait test without voting

Full size image
Fig. 6
figure 6

Signatures generated at the testing stage from multiple best-of-run genetic programs from the training phase for Test 1

Full size image
Fig. 7
figure 7

Results of each gait test when using the voting method

Full size image

4.2 Voting method

We implemented voting during the testing stage of our approach to improve the decision making regarding the recognition of the unknown gaits of two subjects (i.e., different from those used in the training stage). Figure 6 illustrates the use of voting to determine the classification of two gaits of two subjects. However, the figure only shows the calculation of one gait for each person using five different best-of-run genetic programs. As mentioned earlier, Fig. 6 shows voting for the first test case (Test-1) only, but we used the same approach for all other test cases (i.e., Test 2 to Test 5) to achieve the final results shown in Fig. 7.

Figure 6 illustrates the signature of the same gait of two subjects from five different best of run genetic programs. The figure shows that gaits are classified correctly by the second, third, and fifth best-of-run genetic programs, based on the classification criterion in Fig. 4. The first and fourth genetic programs still could not classify the gait correctly. However, because the voting result depends upon the majority; we consider the results of the second, third, and fifth voters as the final classification, and the final signature of the two subjects as the average of the signatures produced by the second, third, and fifth voters, as shown for Test 1 in Fig. 7. Note that all other test cases in Fig. 6 are the outcome of the same approach, although the full process is only shown for Test 1 in Fig. 6.

4.3 Tests with voting

The results for tests with voting are shown in Fig. 7. Note that each result shown in this chart (Test 1 to Test 5) are the results of the collaborative voting filter to determine the final classification. We can clearly visualize from Fig. 5 (the experimental test without voting) and Fig. 7 (the experimental test with voting) that the collaborative filter can increase the rate of gait classification obtained from two separate individuals. For our initial experiment using five different test cases for each person, the use of a collaborative filter achieves a classification rate of as much as 80 % (four out of five); however, this test dataset is too limited to definitively draw this conclusion. Testing on a larger dataset will be required and is a task for our future work.

5 Conclusion

In this work, we proposed the use of GP to evolve the signatures of human gaits. To address the drawbacks of genetic programming—non-determinism and lack of generality—we implemented collaborative filtering using several of the obtained best-of-run genetic programs.

Experimental results suggest that the collaborative filtering improves the quality of human gait recognition for two test subjects.

In our future work, we plan to include the evolution of the signatures of more than two subjects. Another plan is to determine a static signature for several gaits of the same individual that will differ between individuals. This study is constrained in the sense that the methodology has been tested using a relatively small dataset (five test cases for each person); therefore, one important remaining task is to test the approach using several other test cases to validate its robustness.