A Footprint Extraction and Recognition Algorithm Based on Plantar Pressure

A Footprint Extraction and Recognition Algorithm Based on Plantar Pressure

Chao ZhangSu Pan Yaowu Qi Yudan Yang 

Changchun University, Changchun 130000, China

Department of Orthopedics, the Second Hospital of Jilin University, Changchun 130041, China

China railway Changchun railway bus co., LTD, Changchun 130062, China

Scientific Research Center, China-Japan Union Hospital of Jilin University, Changchun 130033, China

Corresponding Author Email: 
yangyudan@jlu.edu.cn
Page: 
419-424
|
DOI: 
https://doi.org/10.18280/ts.360506
Received: 
28 April 2019
|
Accepted: 
2 August 2019
|
Published: 
25 November 2019
| Citation

OPEN ACCESS

Abstract: 

Plantar pressure, an important index in gait analysis, has been widely adopted for clinical diagnosis and sports science. It is of great significance to accurately measure the plantar pressure. In this paper, the data of plantar pressure are collected with the flexible force sensor, and then filtered by a self-designed filtering algorithm with time window. Then, an 8-neighborhood connected-component labeling algorithm was proposed to segment and cluster the plantar pressure images. Finally, the footprints were recognized based on the plantar pressure and shape of footprints. The experimental results show that the proposed footprint extraction method extracted 99% of plantar pressure data accurately under normal walking conditions, and the proposed footprint recognition method recognized more than 97% of footprints in a correct manner.

Keywords: 

footprint recognition, plantar pressure, clustering, image segmentation

1. Introduction

Plantar pressure, an important index in gait analysis, has been widely adopted for clinical diagnosis and sports science. Based on plantar pressure, it is possible to identify abnormal gaits, assess the seriousness of foot disease and evaluate the rehabilitation condition. Thus, it is of great significance to accurately measure the plantar pressure.

Traditionally, plantar pressure is measured by methods like pedography, sole barograph, pressure insole and force measuring platform. With the development of computer technology, pressure sensors have been applied to collect plantar pressure. Flexible force sensor is the most convenient and accurate pressure sensor, capable of capturing plantar pressure in real time and displaying it in an intuitive manner.

The application of large-area flexible force sensor can acquire both static and dynamic plantar pressures. The data thus collected accurately mirror the gait features of the subject. The main problem with the gait analysis using large-area flexible force sensor lies in the processing of the collected plantar pressure.

To solve the problem, this paper designs a plantar pressure platform based on flexible force sensor to collect plantar pressure data, puts forward an 8-neighborhood connected-component labeling algorithm to segment and cluster the plantar pressure images, and proposes a dynamic footprint recognition algorithm based on plantar pressure. The proposed platform and methods were verified through experiments.

2. Literature Review

Flexible force sensor has been widely used in pressure insoles, plantar pressure switches, etc. Chu et al. [1] obtained the walking trajectories of left and right foot with a large-area flexible force sensor, clustered the data on plantar pressure by k-means clustering (KMC), and then differentiated between the two feet based on the angle of the heel-toe vector. Redd and Bamberg [2] marked the hardware of pressure insoles before collecting the plantar pressure of each foot, eliminating the need to extract or recognize footprints.

With the aid of plantar pressure switches, Daliri [3] collected the single support time (left stance), single support time (right stance) and double support time, extracted the minimum, maximum, mean and standard deviation from the three time series, and distinguished healthy people from patients using the support vector machine (SVM) algorithm. Takayanagi et al. [4] classified normal gait from abnormal gait based on four parameters, namely, walking speed, double support time, gait balance ability, and static phase time. [5] Gopalakrishna et al. [5] adopted fuzzy logic algorithm to calculate various gait parameters of plantar pressure.

Bacarin et al. [6] obtained the static and dynamic features of plantar pressure with a single flexible force sensor, and recognized different people based on the two features. Before collecting the dynamic plantar pressure, the measuring points were determined through walking training. Then, the dynamic plantar pressure of each foot was measured by the sensor according to the expected walking speed. Jang et al. [7] segmented the plantar pressure of each step by the KMC, rotated the footprint image to determine six feature points by scan lines, and recognized footprints based on the coordinates of feature points.

Powell et al. [8] predicted the possible trajectories of footprints based on the feature parameters of one foot and the process parameters between two feet in the walking process. The feature parameters were identified based on the travel direction and position. Ferber et al. [9] studied human behavior perception with large-area flexible force sensor, and recognized footsteps based on walking direction and coordinates of key positions, revealing that footstep recognition based on plantar pressure is suitable for normal walking with a small direction angle.

Pataky and Goulermas [10] statistically segmented and analyzed images on plantar pressure. Oliveira et al. [11] presented a computational framework for automatic foot classification, using digital images on plantar pressure. Some scholars meshed plantar pressure images through pedobarographic analysis, and applied it successfully to monitor the plantar pressure of social network users [12]. Crea et al. [13] analyzed the standing plantar pressure images in the frequency domain.

3. Algorithm Design

3.1 Data acquisition and outlier removal

Currently, the plantar pressure collected by flexible force sensor has been widely applied in health care and rehabilitation, as well as gait analysis. The application effect hinges on the authenticity and reliability of the collected data. Since the walking habits are different from person to person and prone to external influence, it is necessary to standardize the collection procedure of plantar pressure. In this paper, a plantar pressure platform (Figure 1) is designed based on flexible force sensor.

Figure 1. The proposed plantar pressure platform

In our platform, plantar pressure can be collected while the previously collected data are being processed. The collected data often contain outliers, i.e. the noises from system hardware and the flexible force sensor. The noises fall into three categories: Gaussian noise, impact noise and jitter noise. Before using the plantar pressure, the outliers must be filtered out on the platform from the collected data [14].

In data acquisition, a pressure value is collected at each sensing point of the flexible force sensor. The collected pressure is divided to 256 levels, and displayed as the corresponding RGB value. The greater the pressure, the darker the displayed color. The inverse is also true. The plantar pressure P(t) collected by the flexible force sensor at time t can be expressed as:

 $P ( \mathrm { t } ) = \left[ \begin{array} { c c c } { p _ { 11 } ( t ) } & { \cdots } & { p _ { 1 N } ( t ) } \\ { \vdots } & { \ddots } & { \vdots } \\ { p _ { M 1 } ( t ) } & { \cdots } & { p _ { M N } ( t ) } \end{array} \right]$           (1)

where, Pij(t) is the pressure collected at sensing point (i, j) at time t; M and N are the row number and column number of sensing point on the flexible force sensor, respectively.

According to the features of the flexible force sensor, the plantar pressure collected by the sensor can be regarded as a dynamically changing digital image, with P(t) being the pixel value. Hence, the collected data can be filtered by digital image filtering algorithms.

Despite its similarity to digital image, the collected data have time features in each frame. When the flexible force sensor collects plantar pressure, not all sensing points feel the pressure at the same time. Thus, there might be only a few nonempty pressure points in a frame of collected data. Before filtering out the outliers, each pressure point should be judged whether it is an outlier, based on the previous and subsequent frames.

Drawing on hybrid image filters, this paper designs a new filtering algorithm with time window to remove the outliers. This algorithm firstly identifies the outliers based on the previous and subsequent frames, and then eliminates the outliers with a hybrid image filter. The specific steps of this algorithm are as follows:

Step 1. Judge whether each pressure point is an outlier. If yes, go to Step 2 to determine if it is a noise. Otherwise, go on to judge the next pressure point. Below is the criterion of outlier judgement: with the current pixel as the center, generate a 3×3 window and count the number of valid pressure points in the window; if the number is greater than the preset threshold (here, the threshold is set to 4), then the current pixel is a valid point; otherwise, it is an outlier.

Step 2. Select the previous and subsequent N frames (here, N is set to 5), i.e. a total of 2N frames. With the outlier identified in Step 1 as the center, generate a 3×3 window in each frame, forming a 3D filter window. Then, count the number of valid pressure points in each window; if the number is greater than the present threshold (here, the threshold is set to 4), count that number in the window of the next frame. In this way, the total number of valid pressure points of the 2N frames can be obtained. If the total number is greater than a preset threshold (here, the threshold is set to 5), then the current pixel is a valid point. After that, adopt the hybrid image filter to screen the 3×3 window of the current frame. If the total number is not greater than the threshold, set the pressure value at the current point to zero, and return to Step 1 to filter the next pressure point.

Step 3. Repeat the above steps until all the frames have been filtered.

Figure 2 illustrates the workflow of the proposed filtering algorithm.

Figure 2. The workflow of the proposed filtering algorithm

The filtering performance of our algorithm was evaluated by signal-to-noise ratio (SNR). The SNR of an image refers to the ratio of the power spectrum of the signal to the noise. Since the power spectrum is difficult to calculate, the ratio of the variance of the signal to the noise is usually taken as an equivalent to the SNR. Therefore, the first step to compute the SNR is to calculate the local variance of each pixel in the image. Then, the maximum and minimum of all local variances are considered as the signal variance and the noise variance, respectively. Then, the variance ratio between the two could be computed and converted to decibels. Finally, the variance ratio can be modified as:

$S N R = 10 \log \frac { \sum _ { t } \sum _ { r o w } \sum _ { c o l } ( \text {Output-Origin} ) ^ { 2 } } { \sum _ { t } \sum _ { r o w } \sum _ { c o l } ( \text {Noise-Origin} ) ^ { 2 } }$        (2)

where, Output is the filtered output image; Origin is the original noise-free image; Noise is the image with additive noises.

Each image was added with a pulsating noise at the percentage of p and a Gaussian noise with the standard deviation of σ. For comparison, each noisy image was processed by the modified trimmed mean (MTM) filter, the intrinsic mode function (IMF) filter and out algorithm, respectively [15]. The denoising results of the three methods are compared in Table 1 below.

Table 1. Comparison of the three methods in denoising effects

Algorithm

SNR (dB) p=4, σ =5

SNR (dB) p=5, σ =8

MTM

-8.43

-10.61

IMF

-9.17

-11.18

Our algorithm

-11.89

-12.50

3.2 Footprint extraction

In image processing, the purpose of pixel classification is to identify the region in which the adjacent pixels are of the same value. In this paper, the pixel classification is performed to find out the pressure concentration region (PCR) of each frame, based on the adjacent pressure points from the binary pressure matrix. Then, the PCRs of different frames were matched. If the preset requirement is met, then the PCRs are ascribed to the same class, i.e. to the same footprint. The data of plantar pressure can be displayed as images (Figure 3).

Figure 3. An example of plantar pressure image

Because the plantar pressure is dynamically changing in the walking process, it is not suitable to use common clustering algorithms to extract the footprint in each step and segment the plantar pressure image. Under normal conditions, walking is movement with high regularity, which is reflected in the pace, step length and step width. Based on the regularity, the plantar pressure image was segmented under three empirical conditions:

Condition 1: In normal walking, the step length and step width both change in a reasonable range.

Condition 2: The length and width of feet of a healthy person are in a reasonable range (Figure 4).

Condition 3: In normal walking, the interval between frames of the same footstep falls within a reasonable range.

Figure 4. An example of the length and width of feet of a healthy person

In this paper, the plantar pressure image is segmented in three steps: binarize the plantar pressure data of each frame; classify the binary data with the 8-neighborhood connected-component labeling algorithm [16]; allocate the classification results to different classes under the three empirical conditions. The specific steps are as follows:

Step 1: Scan the plantar pressure data of each frame in turn, map the pressure data to the image matrix, and binarize the image matrix.

Step 2: Classify the binary matrix with the 8-neighborhood connected-component labeling algorithm, divide the plantar pressure data of each frame into different classes, compute the geometric center of each class, and record the start timestamp of each class.

Step 3: Cluster each class according to its geometric center and the preset thresholds (e.g. foot length, foot width, and interval of start timestamp), and iteratively separate each footprint.

Under the three empirical conditions, the interval between the PCRs of the same footstep in normal walking should be smaller than the length of a normal footstep, the footprint area fused by these PCRs should fall in the area range of normal footprints, and the footprint width fused by these PCRs should also fall in the width range of normal footprints. In each frame, there should be not spatial overlap between footsteps. In addition, the interval of start timestamps between the PCRs of the same footstep should fall within the normal range.

In practical operations, the length, area, and width of a normal step are 26cm, 185cm2 and 10cm, respectively; the interval of start timestamps between the PCRs of the same footstep is 126ms.

In this paper, the minimum bounding rectangle (MBR) is used to cluster the PCRs and fully utilize the shape features of the MBR. The information of each footstep can be obtained once all the frames are iterated.

3.3 Dynamic recognition of footprint

Both gait information and kinematic information are collected by the large-area flexible force sensor. To compute the two types of information accurately and in real time, this paper puts forward a dynamic footprint recognition algorithm based on plantar pressure.

The center of pressure (COP) trajectory reflects the integrity of plantar pressure. Let $\left( X _ { l 1 } , Y _ { l 1 } \right) , \left( X _ { l 2 } , Y _ { l 2 } \right) , \ldots , \left( X _ { l n } , Y _ { l n } \right)$ be the coordinates of all the valid pressure points on the first footprint of the left foot, and Fln be the force corresponding to each coordinates. The coordinates $\left( X _ { l p } , Y _ { l p } \right)$ at the COP of a frame of the left foot can be expressed as:

$X _ { l p } = \frac { \sum F _ { l n } * X _ { l n } } { \sum F _ { l n } }$      (3)

$Y _ { l p } = \frac { \sum F _ { l n } * Y _ { l n } } { \sum F _ { l n } }$        (4)

Then, the start frame of the first footprint of the left foot was extracted, and the all the coordinate points of the COP of that foot of frame t were found. Those of the COP of the first footprint of the right foot were obtained in a similar manner.

Here, the direction of each footprint is determined based on the position relationship between the forefoot and arch, and the left and right feet are differentiated based on the position relationship between the inner arch and the outer arch.

The dynamic footprint recognition algorithm is implemented in the following steps:

Step 1: Extract the plantar pressure data of each footstep based on the corresponding start timestamp, end timestamp and the coordinates interval in the data field of the flexible force sensor. Binarize the data and fill them into the footstep image matrix, and convert the matrix to a binary image.

Step 2: Magnify the small binary image through bilinear interpolation, and filter the magnified image with median filter, creating a binary magnified image.

Step 3: Find the MBR of the binary magnified image by the convex hull algorithm, and identify the angle between the horizontal and vertical directions of the footprint.

Step 4: Rotate the binary magnified image by the angle obtained in Step 3, and perform the nearest neighbor interpolation.

Step 5: Perform morphological image processing on the rotated image, and smooth and filter the processed image. 

Step 6: Extract the outer edge of the processed image by the edge detection algorithm, and compute the MBR by the convex hull algorithm.

Step 7: Scan the long-axis direction of the MBR, record the footprint width in the short-axis direction, and the coordinates of the upper and lower boundary points. Take the coordinates as the vertical values, the upper boundary of the MBR as the benchmark, and the distance between the upper and lower boundary points as the pixel distance of the upper boundary of the MBR.

Step 8: Compress the range of the horizontal axis and the vertical axis to the range of the footprint length and the footprint width, highlighting the peaks and throughs of the fitted curve.

Step 9: Judge the footprints of left and right feet according to extreme values of fitting curve.

4. Experiments and Results Analysis

4.1 Verification of footprint extraction accuracy

The accuracy of footprint extraction was mainly measured by the start timestamp, end timestamp and the range of coordinates of the footprints in each footstep. These parameters were selected because they are the only metrics of the clustering and segmentation effects of the plantar pressure data for each footprint.

A total of 67 subjects were selected for the experiment. All their feet are normal. The test site was divided evenly into rows and columns. A random row (column) was selected from the site, and some rectangular boxes were marked, slightly larger than the footprints, on that row (column). The distance, step length and step width between the rectangular boxes were similar.

Each subject was asked to step on the rectangular boxes in turn. The experimental process was fully monitored by a camera. After the experiment, the landing and departure time of each step was extracted from the video shot by the camera. Then, the start and end timestamps of the footprints in each step were compared, using the 8-neighborhood connected-component labeling algorithm. On this basis, the authors evaluated whether the footprint range is consistent with the rectangular boxes marked in advance. The comparison of footprint segmentation is shown in Table 2.

A long-time walking test was carried out to further verify the accuracy of the start and end timestamps of the footprints after segmentation. Each subject was asked to work normally in the test site for 3~5min. Then, the start and end timestamps of all footprints were computed by the 8-neighborhood connected-component labeling algorithm. Finally, the computed results were compared with those in the video. The number of correct and erroneous frames were counted to evaluate the clustering accuracy (Table 3).

Table 2. The comparison of footprint segmentation

Step number

Parameters

Footprint position

Calculated position

Recorded start and end timestamps

Calculated start and end timestamps

1

(10, 10) (25, 30)

(11, 9) (26, 29)

1000, 2100

1000, 2100

2

(15, 20) (20, 35)

(14, 21) (20, 34)

2100, 3000

2100, 3000

3

(65, 35) (40, 25)

(65, 36) (41, 26)

3200, 4000

3200, 4000

4

(10, 80) (40, 75)

(11, 81) (41, 76)

4100, 4800

4100, 4800

5

(85, 60) (30, 35)

(86, 60) (30, 36)

4900, 5250

4900, 5250

6

(30, 35) (50, 80)

(31, 36) (51, 79)

5350, 5700

5350, 5700

7

(105, 70) (30, 65)

(106, 79) (30, 66)

5860, 6050

5860, 6050

8

(110, 90) (70, 95)

(111, 91) (71, 96)

6200, 6600

6200, 6600

9

(70, 30) (140, 65)

(71, 31) (141, 66)

7200, 7600

7200, 7600

10

(100, 35) (50, 95)

(101, 36) (51, 96)

8600, 9200

8600, 9200

 
Table 3. The comparison of footprint segmentation for the long-time walking test

Walking time

Sampling frames

Number of erroneous frames

Accuracy rate

3 min

19000

112

99.41%

4 min

26000

137

99.47%

5 min

32000

151

99.53%

As shown in Table 3, the segmentation accuracy of our algorithm was 99%, indicating that our algorithm can accurately segment the start and end timestamps and coordinates of each footstep in the normal walking process.

4.2 Verification of footprint recognition accuracy

A total of 67 subjects were selected and asked to walk normally, slowly, rapidly or at a random speed on the plantar pressure platform, according to the prior process. The plantar pressure of each subject was measured, and used to recognize the left and right feet. The recognition accuracy is listed in Table 4.

Table 4. The accuracy of footprint recognition

Walking speed

Right foot recognition rate

Left foot recognition rate

Average recognition rate

Normally

0.986

0.988

0.987

Slowly

0.987

0.989

0.988

Rapidly

0.976

0.976

0.976

Random speed

0.968

0.966

0.967

As shown in Table 4, the recognition rate of left foot, that of right foot and the average recognition rate were higher in the three normal gait situations than the random speed situation. Through analysis, it is learned that some subjects failed to land their heels first in the random speed test, which pushes up the recognition error.

5. Conclusions

This paper collects the data of plantar pressure with the flexible force sensor. Then, the collected data were filtered by a self-designed filtering algorithm with time window. Inspired by the theory of plantar dynamics, an 8-neighborhood connected-component labeling algorithm was proposed to segment and cluster the plantar pressure images. Finally, the footprints were recognized based on the plantar pressure and shape of footprints. The experimental results show that the proposed footprint extraction method and footprint recognition method achieved desired segmentation and recognition rates.

Acknowledgement

This paper was supported by the Jilin Provincial Development and Reform Commission Project “Research on the Health Assessment System of Human Biological Lines Based on Dynamic Gait” (Project Number: 2019C048-6); the Changchun University Fund Project “Research on Human Health System Based on the Plantar Micrology” (Project Number: ZK201806); and the Jilin Provincial Science and Technology Development Project “The Role of Bacterial DNA and Self-Mitochondrial DNA in Severe Multiple Fractures with Acute Lung Injury by Regulating Caveolin-1 and Neutrophil Membrane Surface TLR9” (Project Number: 20180414060GH).

  References

[1] Chu, Y.H., Cheng, C.H., Tang, P.F., Lin, K.H. (2012). Effects of age and step direction on behavioral performances and center-of-pressure characteristics of volitional stepping in older and young adults. Biomedical Engineering: Applications, Basis and Communications, 24(3): 207-216. http://dx.doi.org/10.4015/S1016237212500032

[2] Redd, C.B., Bamberg, S.J.M. (2012). A wireless sensory feedback device for real-time gait feedback and training. IEEE/ASME Transactions on Mechatronics, 17(3): 425-433. http://dx.doi.org/10.1109/TMECH.2012.2189014

[3] Daliri, M.R. (2012). Automatic diagnosis of neuro-degenerative diseases using gait dynamics. Measurement, 45(7): 1729-1734. http://dx.doi.org/10.1016/j.measurement.2012.04.013

[4] Takayanagi, N., Sudo, M., Fujii, M., Sakai, H., Morimoto, K., Tomisaki, M., Niki, Y., Tokimitsu, I. (2018). Foot pressure analysis of gait pattern in older Japanese females requiring different personal care support levels. Journal of Physical Therapy Science, 30(3): 461-466. http://dx.doi.org/10.1589/jpts.30.461

[5] Gopalakrishna, K.P., Mothiram, K.P., Srinivasan, S. (2001). A new method of analysis of standing foot pressure images for detection of the plantar ulcers in early-stage diabetic neuropathy. Frontiers of Medical and Biological Engineering: The International Journal of the Japan Society of Medical Electronics and Biological Engineering, 11(1): 31-43. http://doi.org/10.1163/156855701750383178

[6] Bacarin, T.A., Sacco, I.C., Hennig, E.M. (2009). Plantar pressure distribution patterns during gait in diabetic neuropathy patients with a history of foot ulcers. Clinics, 64(2): 113-120. http://dx.doi.org/10.1590/S1807-59322009000200008

[7] Jang, W.Y., Lee, D.Y., Jung, H.W., Lee, D.J., Yoo, W.J., Choi, I.H. (2018). Inter-segment foot motion in girls using a three-dimensional multi-segment foot model. Gait & Posture, 63: 184-188. http://dx.doi.org/10.1016/j.gaitpost.2018.05.007

[8] Powell, D.W., Long, B., Milner, C.E., Zhang, S. (2012). Effects of vertical loading on arch characteristics and intersegmental foot motions. Journal of Applied Biomechanics, 28(2): 165-173. http://dx.doi.org/10.1123/jab.28.2.165

[9] Ferber, R., Hettinga, B.A. (2016). A comparison of different over-the-counter foot orthotic devices on multi-segment foot biomechanics. Prosthetics and Orthotics International, 40(6): 675-681. http://dx.doi.org/10.1177/0309364615584660

[10] Pataky, T.C., Goulermas, J.Y. (2008). Pedobarographic statistical parametric mapping (pSPM): A pixel-level approach to foot pressure image analysis. Journal of Biomechanics, 41(10): 2136-2143. http://dx.doi.org/10.1016/j.jbiomech.2008.04.034

[11] Oliveira, F.P., Sousa, A., Santos, R., Tavares, J.M.R. (2012). Towards an efficient and robust foot classification from pedobarographic images. Computer methods in Biomechanics and Biomedical Engineering, 15(11): 1181-1188. https://doi.org/10.1080/10255842.2011.581239

[12] Li, B., Guo, C., Ning, T. (2018). An improved bacterial foraging optimization for multi-objective flexible job-shop scheduling problem. Journal Européen des Systèmes Automatisés, 51(4-6): 323-332. https://doi.org/10.3166/JESA.51.323-332 

[13] Crea, S., De Rossi, S.M.M., Donati, M., Reberšek, P., Novak, D., Vitiello, N., Lenzi, T., Podobnik, J., Munih, M., Carrozza, M.C. (2012). Development of gait segmentation methods for wearable foot pressure sensors. In 2012 Annual International Conference of the IEEE Engineering in Medicine and Biology Society, pp. 5018-5021. http://dx.doi.org/10.1109/EMBC.2012.6347120

[14] Bakker, M., Wicherts, J.M. (2014). Outlier removal and the relation with reporting errors and quality of psychological research. PLoS One, 9(7): e103360. http://dx.doi.org/10.1371/journal.pone.0103360

[15] Wang, J., Liu, Y., Zhang, C., Jiao, Y. (2009). Model for router-level Internet topology based on attribute evolution. IEEE Communications Letters, 13(6): 447-449. http://dx.doi.org/10.1109/LCOMM.2009.090437

[16] Lang, F., Yang, J., Li, D., Zhao, L., Shi, L. (2013). Polarimetric SAR image segmentation using statistical region merging. IEEE Geoscience and Remote Sensing Letters, 11(2): 509-513. http://dx.doi.org/10.1109/LGRS.2013.2271040