40 lines
4.7 KiB
TeX
40 lines
4.7 KiB
TeX
|
\subsection{Branches Extraction and Matching}
|
||
|
|
The branches extraction part was allocated to both groups. The skeleton we have extracted are composed of points. A skeleton point can be of different types:
|
||
|
|
\begin{enumerate}
|
||
|
|
\item a extremity point which only have one neighbor, i.e. this point is involved in only one edge of the skeleton.
|
||
|
|
\item a regular point which have two neighbors, i.e. this point is involved in only two edges of the skeleton.
|
||
|
|
\item a junction point which have at least three neighbors, i.e. this point is involved in three edges or more than three edges.
|
||
|
|
\end{enumerate}
|
||
|
|
|
||
|
|
In the cases of extremity points and junction points, we consider that the point is irregular. To extract the branches of the skeleton, we start from each irregular point and we follow the edges starting from this irregular point until we find another irregular point (junction or extremity).
|
||
|
|
|
||
|
|
Let us consider two irregular points $P_1$ and $P_5$ such as there is a path $P_1$, $P_2$, $P_3$, $P_4$, $P_5$ linking these two irregular points together. As a result, $P_1$, $P_2$, $P_3$, $P_4$, $P_5$ is a branch of the skeleton. However, the algorithm will also find $P_5$, $P_4$, $P_3$, $P_2$, $P_1$ as a branch of the skeleton. To avoid having each branch two times, we added a new branch to the branches set only if the contrary branch is not already in the set.
|
||
|
|
|
||
|
|
Once we extract all the branches on two correspoding skeletons, we would like to match these branches together thanks to the keypoints found on each picture. For this purpose, we would like to assign to each keypoint a branch of the skeleton. We will consider that both skeletons have the same number of branches. If not, the matching between branches would not be perfectly possible.
|
||
|
|
|
||
|
|
To determine the correspoding branch of a keypoint, we use the euclidian distance. Each keypoint is assigned to the nearest branch of the skeleton. As a branch is composed of segments, we will define the distance between a point and a branch as the shortest distance between this point and all the segments composing the branch. Thus, the nearest branch of a point is the branch that contains the nearest segment to the point.
|
||
|
|
|
||
|
|
The distance between a point and a segment is defined as following:
|
||
|
|
\begin{enumerate}
|
||
|
|
\item if the projection of the point is on the line that contains the segment, then the distance between the point and the segment is the distance between the point and its projection.
|
||
|
|
\item if the projection of the point is not on the line that contains the segment, then the distance between the point and the segment is the shortest distance between the distance between the point and each extremity of the segment.
|
||
|
|
\end{enumerate}
|
||
|
|
|
||
|
|
Once each keypoint has been associated to a branch, we use the matching between keypoints from the two pictures and, for each picture, the matching between keypoints and branches to deduce the matchings between the branches from the two skeletons.
|
||
|
|
|
||
|
|
$$\begin{matrix}
|
||
|
|
\text{Keypoints 1} & \longleftrightarrow & \text{Keypoints 2} \\
|
||
|
|
\updownarrow & & \updownarrow \\
|
||
|
|
\text{Branches 1} & & \text{Branches 2}
|
||
|
|
\end{matrix}$$
|
||
|
|
|
||
|
|
To compute the matches between branches, we define a matching a square matrix $M$ which size is the number of branches of each skeleton.
|
||
|
|
|
||
|
|
Let $KP_1$ and $KP_2$ be two matching keypoints, respectively from $Picture_1$ and $Picture_2$. Let $Skeleton_1$ and $Skeleton_2$ be the extracted skeletons of $Picture_1$ and $Picture_2$. Let $Branch_1$ be a branch of $Skeleton_1$, $Branch_2$ a branch of $Skeleton_2$. We assume that $KP_1$ is associated to $Branch_1$ and $KP_2$ is associated to $Branch_2$. Since $KP_1$ and $KP_2$ are matching keypoints, a vote is given to a match between $Branch_1$ and $Branch_2$.
|
||
|
|
|
||
|
|
Each time a vote is given to a match between $Branch_i$ and $Branch_j$, the element $m_{i,j}$ of $M$ is incremented. Once each pair of matching keypoints has voted, the branches are matching using the matching matrix.
|
||
|
|
|
||
|
|
Let $Branch_i$ be a branch of $Skeleton_1$ and $M$ be the matching matrix between branches of $Skeleton_1$ and the branches of $Skeleton_2$. The index $j$ of the matching branch $Branch_j$ with $Branch_i$ is defined such as the element $m_{i,j}$ of $M_{i,\cdot}$ is maximal.
|
||
|
|
|
||
|
|
In pratice, the skeletons we try to match have never the same number of branches: some differences may the algorithm unable to give good results. The test report details the differences between skeletons. We thought about solutions, such as merging short branches with others. We could also ask the user to click on matching branches. In this case, there is no need to detect keypoints anymore. Another solution is to ask the user to click on noising branches that often appears on extremities of the skeleton.
|