HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY
SCHOOL OF ELECTRONICS AND TELECOMMUNICATION
FINAL PROJECT
DATA STRUCTURE
AND ALGORITHMS
Topic:
HAND POSE RECOGNITION
Student: VU HOANG LONG 20182926
NGUYEN LE TRUNG 20186076
LE NGOC HA 20182916
Class: ET-E4 - K63
Instructor: Assoc. Prof. Dr. TRAN THI THANH HAI
Hanoi, June 22, 2021
HAND POSE RECOGNITION
[Link], [Link], [Link]
June 22, 2021
3
List of Figures
1 Hand poses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Input data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Data through functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4
Contents
I Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1 Functional Requirement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Non-funtional Requirement . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
II Data Flow Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
III Data Structure and Algorithms . . . . . . . . . . . . . . . . . . . 10
3 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Algorithms and Special Functions . . . . . . . . . . . . . . . . . . . . . . . 11
IV Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
V Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
VI Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5
Handpose Recognition [Link], [Link], [Link]
ABSTRACT
Nowadays, within the development of smart technology, associated with the
the explosion of artificial intelligence and big data, the hand-controlling-related
topic is one of the most interesting areas to make the life become smarter and
better. Particularly, when integrating those related technologies into devices,
it helps people to control those things easily, with a impossibly wonderful ex-
perience. For example when you just roll your hand, the 5m-away curtain will
automatically close or open immediately, if your smart home package was inte-
grated the technology like that. Or when applied in medical, the robotic hand,
which was integrated the hand recognition technology, will do exactly the same
what doctors do, with a smaller scale, to perform microsurgery with minimized
risks. Accordingly, we choose one related topic to do as our final project, so
that throughout this project we will profoundly understand the fountain con-
cepts of what we have learned in subject Data Structure and Algorithms and
apply them, also to become more familiar with the hand recognition technology
and go further with our interest.
Throughout this report, we have covered almost the detailed techniques of
how we code and obtain the final result matched with the requirement. The
report was divided into five parts: the first and foremost part Part I: Introduc-
tion leads us to deep into the project; Part II: Data Flow Diagram is about
how the data was formed and handled throughout each code block step by step;
Part III: Data Structure and Algorithms shows how we apply this subject’s
knowledge to store and process given data; Part IV: Result performs how the
code runs and gives results; and the last part Part V: Conclusion sums up
what we have done.
Due to the limitation of time and the requirement, we only use given data
which we have found from the link listed in the Reference part. Anyway, the
final obtained results are so spectacular as the requirement. Our contribution
is insignificant compared to what people have done in this topic or something
likes that. However, we hope that throughout our project, this little achieve-
ment helps us to understand more about the related concepts, also improve our
programming skills, and in some way, it makes us feel so happy about what we
have done. During the procedure we work on the project, sometimes we stuck
in difficulties like bugs or unexpected results, nevertheless, it is very kind of you
that you are always ready to help us overcome those drawbacks and accomplish
our achievement.
Sincerely,
Long-Trung-Ha.
6
[Link], [Link], [Link] Handpose Recognition
Part I
Introduction
Throughout the project, we work with the data set of hand pose, which are connected
joints captured by a sensor. Each joint is a point in 3D space with 3 coordinates (x,
y, z). A hand pose with 21 joints will be stored as a row of 64 elements of a text file:
the first element is the ID of hand pose (normally corresponding to the time stamp) and
the following 63 elements are 21x3 coordinates of 21 joints. Hand pose are widely used
for hand gesture recognition in many applications such as human machine interaction
(Virtual reality, Augmented Reality) or Robotics (grasping), etc.
Figure 1: Hand poses
1 Functional Requirement
Following the requirements, our program has all the below features
1. Joints of hand pose are defined as a struct named handJoint:
• 3 coordinates: x, y z
• ID of joint
• An array of joints is connected to it
2. Hand poses are defined as a struct named handPose:
• Timestamp of the hand pose
• Array of 21 joints, each joint is a struct handJoint defined above
3. Has a function to read row by row a txt file as described above, return a pointer that
points to an array of struct handPose storing handPoses charged from the file.
7
Handpose Recognition [Link], [Link], [Link]
4. Has a function that calculates the Euclidian distance of every pair of joints of a
handPose. The function returns a pointer that points to 2D array, each element of
the array (i,j) is Euclidian distance between ith joint and jth joint.
5. Has a function that calculates the movement of each joint between two times. The
function takes two handPoses at timestamp t1 and t2 as input, returns a pointer
that points to an 1D array of size 21 elements, each element i of the array is the
Euclidian distance of the ith joint at timestamp t1 and ith joint at timestamp t2.
6. Has a function to sort the array obtained from (5) and return the sorted array and
the ID of the joint that moves the most.
7. Represents a handpose as a binary tree, has a struct Node to represent each joint
of hand pose.
8. Has a function to insert nodes into the tree, returns the pointer that point the root
node (corresponding to 0th joint)
9. Has functions to traversal the tree in pre-order, in-order and post-order
10. Has a function that determines longest path of the tree. The function returns to the
array storing the ID of node belonging to the longest path.
2 Non-funtional Requirement
1. The source code should be divided clearly into particular-purpose functions so that
it will be easy to maintenance and edit.
2. The complex data structure types as tree or class should be defined as general-
datatype classes to be easy to call back the related functions and reuse, the others
are defined as structs.
3. The output results should be clear to evaluate.
8
[Link], [Link], [Link] Handpose Recognition
Part II
Data Flow Diagram
After storing hand poses as struct handPose, we obtained the required data after
handling it by the corresponding functions:
Figure 2: Input data
Figure 3: Data through functions
9
Handpose Recognition [Link], [Link], [Link]
Part III
Data Structure and Algorithms
3 Data Structure
To store hand poses, we define a struct named handPose:
struct handPose {
double timeStamp;
handJoint jointArray[21];
//overloading cout << function here
};
Where handJoint is a struct stores the coordination of each joint and its ID, also a graph
of its connected joints :
struct handJoint {
double x;
double y;
double z;
int ID_joint;
vector<int> connected_joint() {
Graph g;
return g.output_connected_joint_ID(ID_joint);
}
//overloading cout << function here
};
In here, Graph is a class to store the set of connected joints and some related function
to access and handle data
class Graph {
private:
int numVer;
vector<int>* list;
public:
void add_edge(int jointA, int jointB);
Graph();
void print_connected_joint(int ID_joint);
};
We also use data structure binary tree to stored handPoses, as required in the assign-
ment. The defined tree has all the needed functions to modify and traverse the tree:
template<class T>
class BST {
private:
class Node {
public:
10
[Link], [Link], [Link] Handpose Recognition
T data;
Node* left, right;
};
Node* root;
public:
BST();
Node* Insert(T data);
void Preorder();
void PostOrder();
void InOrder();
};
Accordingly, the structure handPose BST is defined to store the array of joints and its
timestamp
struct handPose_BST {
double timeStamp;
BST<handJoint> jointArray;
//overloading cout << function here
};
4 Algorithms and Special Functions
Following the sixth requirement, we define function sort() using Selection Sort Algo-
rithm, also swap() and reverse() from algorithms.h library
int sort(double distance[]) {
int moveMost_ID;
//find max value
double maxvalue = distance[0];
for (int i = 1; i < 21; i++) {
if (maxvalue < distance[i]) maxvalue = distance[i];
}
for (int i = 1; i < 21; i++) {
if (distance[i] == maxvalue) moveMost_ID = i;
}
//sort
for (int i = 0; i < 20; i++) {
for (int j = i + 1; j < 21; j++) {
if (distance[i] < distance[j]) {
swap(distance[i], distance[j]);
}
}
}
return moveMost_ID;
}
We also have function readFile() to read data from file .txt; getData() to re-
turn data to the corresponding data types such as handPose, pointer handPose* ,
11
Handpose Recognition [Link], [Link], [Link]
handPose BST , pointer handPose BST* ; and functions movement() and euclid-
ian distance() to calculate the corresponding required parameters; or overloading op-
erator to display out the special datatypes, which will be shown in the attached link
to the source code. Due to the limitation of the length of the report and the simplicity of
those function, we do not discuss about them here.
12
[Link], [Link], [Link] Handpose Recognition
Part IV
Results
The results also can be obtains when you run our attached code from the corresponding
link and choose the right testing function.
Link to the attached source code: click here or click here
13
Handpose Recognition [Link], [Link], [Link]
Part V
Contribution
Coding: [Link]
Debugging: [Link], [Link]
Making Report: [Link]
Making Slide: [Link], [Link]
Presenting: The Entire Team
14
[Link], [Link], [Link] Handpose Recognition
Part VI
Conclusion
Comprehensively, our program seems to work well, while all the functions run under the
expected time and give out the right results, matched with the requirement. Respectfully,
the working procedure gives us the familiarity of how hand recognition technique operates
in practice, also helps us to raise up our programming level. Hopefully, our project will
also helps others who want to become more familiar with this topic in the first step of
beginning.
On the way we gain my goal, without a great guide, we an not easily get it. Sincere
thanks to our instructor [Link] Thi Thanh Hai, who lighten the procedure
step by step, so that we can get the right path to accomplish our achievement with the
minimized consumed effort. Due to the limitation of time, perhaps our presentation is
not the perfect one. Anyway,we are really looking forward to receive your feedback on
our project so that we know our lackages and do better on the next time.
This project is also a significant buffer for our future orientation. Along with your
dedicated guides, we have profoundly found our interest of the computer vision fields,
which momentously promote to try to build up a whole practical training model, as well
as we have done with this little project.
One again, thank you very much for your devotion.
Thank you!
15
Handpose Recognition [Link], [Link], [Link]
Reference
1. [Link] Tien Hoa, Thesis Template. HUST, 2020.
16