Similarity Measurement Using Polygon Curve Representation and Fourier
Descriptors for Shape-based Vertebral Image Retrieval

D. J. Lee\*^a^, Sameer Antani^b^, and L. Rodney Long^b^

^a^ Dept. of Electrical and Computer Engineering, Brigham Young
University, Provo, Utah 84602

^b^ Communications Engineering Branch, National Library of Medicine, MS
55, 8600 Rockville Pike, Bethesda, MD 20894

ABSTRACT

Shape-based retrieval of vertebral x-ray images is a challenging task
because of high similarity among the vertebral shapes. Most techniques,
such as global shape properties or scale space filtering, lose or fail
to detect local details. As the result of this shortfall, the number of
retrieved images is so high that the retrieval result is sometimes
meaningless. To retrieve a small number of best matched images, shape
representation and similarity measurement techniques must distinguish
shapes with minor variations. The main challenge of shape-based
retrieval is to define a shape representation method that is invariant
with respect to rotation, translation, scaling, and the curve starting
point shift. In this research, a polygon curve evolution technique was
developed for smoothing polygon curves and reducing the number of data
points while preserving the significant pathology of the shape. The x
and y coordinates of the simplified boundary points were then converted
into a bend angle versus normalized curvature length function to
represent the curve. Finally, the Fourier descriptors of the shape
representation were calculated for similarity measurement. This approach
meets the invariance requirements and has been proved to be efficient
and accurate.

1.  Shape Representation, Shape Similarity, Vertebral Image, Shape-based
    Image Retrieval, Curvature Function, Fourier Descriptors, X-ray
    Image

1\. introduction

Manual indexing and retrieval for biomedical content such as x-ray
images from a large image database is a prohibitively labor intensive
task. An automated or computer-aided retrieval system will greatly
improve the image retrieval process. Medical images, especially images
created by digitizing film x-rays of human cervical and lumbar spines,
generally have low contrast and low image quality. Traditional image
matching techniques based on grayscale image distance or correlation are
computationally expensive and not meaningful for the retrieval of x-ray
images. Shape-based techniques are more suitable than grayscale- or
feature-based techniques for this task. A completed shape-based image
retrieval system includes contour noise removal, shape representation,
similarity measurement, and fast indexing. The biggest challenge of
shape-based retrieval is to mathematically describe the shapes and to
derive a similarity measurement to compare the shapes.

Shape-based retrieval of vertebral x-ray images is a challenging task
because of highly similar shape properties. Figure 1 shows a cervical
x-ray image with a shape contour outlined in blue. The shape
representation methods need to work with planar closed curves as shown
in Figure 1. While reducing the number of redundant data points to
minimize the computation requirement, the shape representation method
should also preserve local details so that highly similar shapes can
still be distinguished and ranked. Because x-ray images are not always
taken in a fixed position, the shape representation methods should also
represent the shape in a geometrical invariant manner so that the
similarity between two shapes can be calculated disregard the variations
in rotation, translation, and scaling. Moreover, shape data are
extracted from a grayscale image and recorded as a sequence of x and y
coordinates. Another important requirement for an efficient shape
representation method is that the starting point shift of the curve
should not have any effects on similarity measurement.

\* <djlee@ee.byu.edu>; phone 1 801 422 5923; fax 1 801 422 0201

There are many different techniques to describe the shapes for
content-based image retrieval applications. Global shape properties such
as size, perimeter, convex perimeter, elongation, roughness, and
compactness, etc., can be used for measuring similarity ^1^. Invariant
moments have also been used for discriminating shapes ^2^. Multi-stage
modification using invariant moments has shown very good results ^3^.
Other methods using higher order moments include generalized complex
moments ^4^ and Zernike moments ^5^. Multi-scale shape representation
has been used to smooth and simplify the contours ^6-8^. The curvature
function was then used to analyze the smoothed curve in order to
determine the critical points on the curve for comparing curve segments
or token. Another polygon curve representation method is done in the
tangent space, also called turn function. This method uses curve
evolution to remove small variations and less significant features and
then represents the curve in tangent space ^9-11^. Shapes or contour
points can also be described in frequency domain ^12-13^. The contour
points of a polygon must be represented using turn function or bend
angle function so that they are invariant to translation, rotation, and
scaling. Fourier descriptors can then be used to measure shape
similarity ^14^ because it is invariant to starting point shift of the
polygon curve.![](media/image1.wmf){width="1.9597222222222221in"
height="2.120833333333333in"}

![](media/image2.png){width="1.4980314960629921in"
height="1.1244094488188976in"}![](media/image3.png){width="1.497244094488189in"
height="1.1244094488188976in"}![](media/image4.png){width="1.4984251968503937in"
height="1.1244094488188976in"}![](media/image5.png){width="1.497244094488189in"
height="1.1244094488188976in"}The input to the shape representation
algorithms is a collection of boundary points recorded as a sequence of
x and y coordinates. The shape contours must be extracted from the
database image before building the database for indexing. Most
techniques such as global shape properties, scale space filtering lose
or fail to detect the local details. As the result of it, the number of
retrieved images is so high that the retrieval result is sometimes
meaningless. Shape representation and similarity measurement techniques
for shape indexing must be able to distinguish shapes with minor
variations. Figure 2 shows four typical vertebral contours with very
similar shape properties.

In this paper, a new polygon curve evolution technique was developed for
smoothing polygon curves and reducing number of data points while
preserving the significant pathology of the shape. The x and y
coordinates of the smoothed boundary points were then converted into a
bend angle verses normalized curvature length function to represent the
curve. Finally, the Fourier descriptors of the shape representation were
calculated for similarity measurement. Shape similarity measure was
designed so that the input shapes can be compared against the shapes in
the database and the similarity scores can be obtained to evaluate the
performance. Twenty randomly selected shapes were used for evaluation.
Shapes that are similar were grouped together and categorized. The
performance was evaluated by examining the number of retrievals in the
same group. In this paper, the pre-procession and shape representation
techniques will be discussed in Section 2. Section 3 describes the
Fourier descriptors and similarity measurement. Data and result will be
analyzed in Section 4 and the conclusions and future work will be
presented in Section 5.

ii\. Curve Evolution AND SHape Representation

Polygon curves were generated by segmenting the x-ray images and
recorded the results in a sequence of x and y coordinates. Many data
points on the contour are redundant or edge noise and must be removed.
Curve evolution has been used to describe shapes in different levels of
detail ^9-11^. A modified version of curve evolution technique has been
developed and implemented to eliminate insignificant shape features such
as short straight line segments.

## Curve Evolution

Curve evolution has been used to reduce the influence of noise and to
simplify the shapes by removing irrelevant and keeping relevant shape
features. This was achieved by iteratively comparing the relevance
measure of all vertices on the polygon. Higher relevance value means
that the vertex has larger contribution to the shape of the curve. For
each of these iterations, the vertex that has the lowest relevance
measure was removed and a new segment was established by connecting the
two adjacent vertices. The relevance measure can be expressed and
calculated as

$K(s_{1},s_{2}) = \frac{\beta(s_{1},s_{2})l(s_{1})l(s_{2})}{l(s_{1}) + l(s_{2})}$

Equation 1

, where β is the turn angle and *l* is the normalized length. The
relevance measure is in direct proportion to the turn angle and the
length of the curve segment. As illustrated in Equation 1, Figure 3 (a)
shows a vertex that has lower relevance measure than (b) because of
shorter length and has lower relevance measure than (c) because of
smaller turn angle.

![](media/image6.png){width="6.2492125984251965in"
height="1.8744094488188976in"}Equation 1, while works well for
describing shapes in different levels of detail, starts losing the
significant pathology of the shapes as the number of data points
decreases. Figure 4 shows the results of curve evolution using
Equation 1. The original shape contour has 172 data points as shown in
Figure 4 (a). It was reduced to 30 points and 20 points using Equation 1
as shown in Figures 4 (b) and 4 (c), respectively. Several critical
points were lost when the number of data points was reduced to 30
(Figure 4 (b)). The situation got even worse when the number of data
points was reduced to 20 points (Figure 4 (c)). After removing vertices
with low relevance measure using Equation 1, the remaining vertices can
hardly represent the original shape correctly.

A new relevance measure equation was developed to remove short and
straight line segments so that the critical points can be detected and
preserved. This new curve evolution technique effectively reduces the
data points and keeps significant shape features. It removes the
vertices that have short length and/or their turn angles are close to
180 degrees (straight line). Equation 1 was modified and expressed in
Equation 2 in order to achieve this task.

$K(s_{1},s_{2}) = \frac{|(\beta(s_{1},s_{2}) - \text{180})|l(s_{1})l(s_{2})}{l(s_{1}) + l(s_{2})}$

Equation 2

As shown in Figure 5, Equation 2 keeps data points that are critical to
preserving detail pathology of the shape. The critical vertices that
represent the concave and convex points of the shape were preserved even
when the number of data points was reduced to 20 points (Figure 5 (b).
More local details were preserved using Equation 2.

![](media/image7.png){width="4.166535433070866in"
height="1.8755905511811024in"}

**2.2 Shape Representation**

![](media/image8.png){width="1.9165354330708662in"
height="1.9165354330708662in"}![](media/image9.png){width="1.9200787401574804in"
height="1.9200787401574804in"}![](media/image10.png){width="1.9200787401574804in"
height="1.9200787401574804in"}Because x-ray images could be taken from
different angles and locations and their size varies, the shape
representation must be invariant to translation, rotation, and scaling.
The bend angle was calculated so that the clockwise turn gives a
negative angle whereas a counter clockwise turn gives a positive angle
as shown in Figure 6 (a). This method represents a closed polygon curve
*C (m vertices)* as Θ(*l*), bend angle as a function of normalized
accumulated length *l*. Because it does not contain orientation
information, this representation meets the rotation invariant
requirement. Normalized length makes it independent to the polygon size
so that it meets scaling invariant requirement. Figure 6 (b) shows the
function Θ(*l*) of a 20-point bend angle function. The x-axis represents
the normalized length. The only problem left is the starting point shift
invariant requirement and it can be taken care of by the shift invariant
property of the power spectrum. Data used for calculating the power
spectrum of the bend angle function Θ(*l*) were sampled at a fixed
length interval. For example, if twenty data points are used for
calculating the power spectrum, then the data will be sampled at an
interval of 0.05 of the total length. Figure 6 (c) shows the sampling
data of the bend angle function for calculating Fourier Descriptors for
similarity measurement.

III\. Fourier Descriptors and Similarity Measurement

In this section, detail algorithms for calculating Fourier Descriptors
will be discussed. The similarity measure for comparing Fourier
Descriptors is also included in this section.

**3.1 Fourier Descriptors**

$\Theta(l) = \mu_{0} + \sum_{n = 1}^{\infty}{(a_{n}}\text{cos}\text{nl} + b_{n}\text{sin}\text{nl})$
The Fourier expansion of Θ(*l*) is expressed as .

Equation 3

, where a~n~ and b~n~ are coefficients for each frequency component.
Since Θ(*l*) is a step function, *μ~0~, a~n~, and b~n~ can be derived
as*

$\begin{array}{r}
\text{                              }\mu_{0} = - \pi - \frac{1}{L}\sum_{k = 1}^{m}\lambda_{k}\theta_{k}\text{           } \\
a_{n} = - \frac{1}{n\pi}\sum_{k = 1}^{m}{\theta_{k}\text{sin}\frac{2{\pi n\lambda}_{k}}{L}}\text{          }b_{n} = \frac{1}{n\pi}\sum_{k = 1}^{m}{\theta_{k}\text{cos}\frac{2{\pi n\lambda}_{k}}{L}} \\
\text{where}\text{  }\lambda_{k} = \sum_{i = 1}^{k}l_{i}\text{    and   L} = \sum_{i = 1}^{m}l_{i} = \text{ the total length }
\end{array}$

Equation 4

The power spectrum of the bend angle function is invariant to the shift
in length (*l* in this case). Because of this property, Fourier
descriptors of a bend angle function (function of normalized length)
meet all invariant requirements for shape description for shape-based
retrieval. The power spectrum (*A~n~*) and phase angle information
(*F~jk~*) can be calculated as follow ^14^:

$\begin{array}{r}
A_{n} = \sqrt{a_{n}^{2} + b_{n}^{2}}\text{    and  }\alpha_{n} = \text{tan}^{- 1}(\frac{b_{n}}{a_{n}}) \\
F_{\text{jk}} = j^{}\alpha_{k} - k^{}\alpha_{j}\text{   where }j^{} = j\text{/gcd}(j,k) \\
\text{gcd:}\text{greatest}\text{ common divisor}
\end{array}$

Equation 5

**3.2 Similarity Measurement**

Similarity measures were derived based on the *l~2~-norm* of the shape
features. In other words, query is measured (scored) based on an
appropriate distance measure in the feature space. This can be expressed
as follow. Suppose the significant shape features are selected and
recorded as a one-dimensional vector and are expressed
as$S_{A} = \lbrack a_{1},a_{2},a_{3}, \cdot \cdot \rbrack$ and
$S_{B} = \lbrack b_{1},b_{2},b_{3}, \cdot \cdot \rbrack$. The distance
measure between two vectors in the feature space can be calculated as

$\left\| d \right\|_{2} = \left| S_{A} - S_{B} \right|^{2} = \sqrt{\sum_{i = 1}^{n}\left| a_{i} - b_{i} \right|^{2}}$

Equation 6

Based on Equation 6, the difference (dissimilarity) between two sets of
Fourier descriptors can be measured as :

$\begin{array}{r}
D_{A}\lbrack c,c'\rbrack = (\sum_{}^{}\left| A_{k} - A_{k}^{'} \right|^{2})^{\text{1/2}}\text{  for the amplitude or  } \\
D_{\alpha}\lbrack c,c'\rbrack = (\sum_{}^{}\left| F_{\text{kj}} - F_{\text{kj}}^{'} \right|^{2})^{\text{1/2}}\text{ for the phase angle}
\end{array}$ Equation 7

,where *A~k~* represents the amplitudes of the Fourier Descriptors and
*F~kj~*. The difference between the amplitudes (D~A~) can be normalized
and rescaled to between 0 and 100.

$S_{A}\lbrack c,c'\rbrack = \text{100} - D_{A}\text{  }(\text{where D}_{A} \in \left\{ \text{0, 100} \right\}$
Equation 8

The similarity between two curves can then be measured as S~A~=100-D~A~
so that a score of 100 denotes that the curves are identical and 0 means
they are the least similar curves. Only D~A~ was used because the phase
angle difference D~α~ contains the phase information that is not needed
for calculating the similarity measure. Figure 7 shows the two shapes
that were used for testing the Fourier descriptors algorithm. The small
one (blue) is the original shape that is shown in Figure 4 (a) and the
large one (red) is the same shape but was rotated by 20 degrees and
rescaled by 1.2. The staring point of the data points on the contour was
shifted by 10. Table 1 shows that the similarity measures stay constant
even with all the above alterations. One of the data point was also
moved to test the similarity measurement sensitivity. The similarity
dropped to 98.3516 when one data point was moved by (20, 20).

![](media/image11.png){width="2.0in" height="2.0in"}

  --------------------------------------------- -------------------------
  Changes from the original                     Similarity Measure

  20 degree rotation                            99.99999

  1.2 scaling                                   99.99999

  10 starting point shift                       100.0

  Combination of all three                      99.99999

  One point moved by (20,20)                    98.3516
  --------------------------------------------- -------------------------

Table 1. Similarity measures after the alternations.

![](media/image12.png){width="2.0in"
height="2.0in"}![](media/image13.png){width="2.75in"
height="2.0in"}Figure 8 (a) shows the sampling data of the bend angle
function of the altered shape (large). The two bend angle functions are
almost identical because of the invariant properties of the bend angle
function. The only difference between the two bend angle functions is
the small shift in the x-axis (along the contour length) which was
caused by the starting point shift. The shift in the x-axis can be taken
care of by the Fourier power spectrum's shift invariant property. Figure
8 (b) shows the Fourier descriptors of the two bend angle functions.
Even with a starting point shift in the bend angle functions, the
Fourier descriptors stayed the same.

IV\. Data analysis

The developed shape description and similarity measurement algorithms
were tested on 20 selected vertebral image contours. The testing showed
very promising results. Table 2 below shows the retrieval results
represented as ranked similarity measures. The testing was performed by
selecting one at a time of the twenty shapes as the inquiry and
comparing it against the rest of the shapes in the database. In Table 2,
Row 1 represents the shape that was chosen as the inquiry (from 1 to
20). Each column represents the retrieval result. Shapes with higher
similarity measure were ranked higher and were placed closer to the top.
For example, when using Shape #8 as the inquiry, Shape #7 had the
highest similarity measure and was ranked the best match (to Shape #8).
Shape #7 was followed by Shapes #6, #5, #9, and so on. Depending on the
inquiry shape, the ranking was slightly different. However, the overall
retrieval result was proved to be very accurate. Figure 9 shows the
retrieval result with shape contours when Shape #8 was used as the
inquiry.

![](media/image14.png){width="6.5in" height="3.0062992125984254in"}

As shown in Table 2, shapes can be grouped together as being similar.
Shapes #8, #7, #6, and #5 are very similar to one another and can be
grouped together. The next close group consists of Shapes #9, #17, and
#10. Other groups include (#2, #12, #14, and #11), (#1 and #3), and
(#18, #16, #20, and #19). Shapes in the same group tented to stay very
close together in the ranking. Shapes #4, #13, and #15 are very
different from others. However, the algorithms did find Shape #3 as the
closest match to Shape #4.

![](media/image15.png){width="6.666535433070866in"
height="2.666535433070866in"}

V. Conclusions

In this research, a new curve evolution equation was derived and
implemented to reduce the number of data points, to smooth the shape
contour, and at the same time preserve the significant pathology of the
shape. The bend angle verse the normalized length function was used to
represent the shapes. This shape representation method meet the
rotation, scaling, and translation invariant requirements for comparing
shape contours extracted from vertebral x-ray images. Fourier
descriptors were calculated to take care of the contour starting point
shift problem so that the shape similarity could be measured. The
*l~2~-norm* was then calculated to measure the difference between two
sets of Fourier descriptors to measure the difference between two shapes
for similarity ranking. The testing has shown accurate result and has
proved that shape-based vertebral x-ray image retrieval from an image
database is feasible.

VI\. ACKnowledgement

*This research was supported in part by an appointment to the NLM
Research Participation Program sponsored by the*

*National Library of Medicine and administered by the Oak Ridge
Institute for Science and Education.*

References

1.  Y. H. Ang, Z. Li, and S. H. Ong. "Image Retrieval based on
    Multidimensional Feature Properties." *In Proceedings of IS\\&T/SPIE
    Conference on Storage and Retrieval for Image and Video Databases
    III*, Vol. SPIE 2420, pp. 47-57, 1995.

2.  Ming-Kuei Hu, "Visual Pattern Recognition by Moment Invariants",
    *IRE Transaction on Information Theory*, vol. 8, pp. 179-187, 1962.

3.  A.K. Jain and A. Vailaya. "Shape-Based Retrieval: A Case Study with
    Trademark Image Databases." *Pattern Recognition*, vol. 31(9):pp.
    1369-1390, 1998.

4.  Y-S. Kim and Kim W-Y. "Content-Based Trademark Retrieval System by
    using Visually Salient Feature." *In Proc. of IEEE Conf. on Computer
    Vision and Pattern Recognition*, pp. 307-312, 1997.

5.  H.H.S. Ip, D. Shen, and K.K.T. Cheung. "Affine Invariant Retrieval
    of Binary Patterns Using Generalized Complex Moments." *In Second
    International Conference on Visual Information Systems
    (VISUAL\'97)*, pp. 301-308, 1997.

6.  A. Del Bimbo and P. Pala. "Shape Indexing by Multi-Scale
    Representation." *Image and Vision Computing*, vol. 17(3-4): pp.
    245-261, 1999.

7.  Ann Bengtsson and Jan-Olof Eklundh, "Shape Representation by
    Multiscale Contour Approximation", *IEEE Transactions on Pattern
    Analysis and Machine Intelligence*, vol. 13 (1), pp. 85-93, Jan.
    1991.

8.  Farzin Mokhtarian and Alan K. Mackworth, "A Theorey of MIltiscale,
    Curvature-Based Shape Representation for Planar Curves", *IEEE
    Transactions on Pattern Analysis and Machine Intelligence*, vol. 14
    (8), pp. 85-93, Jan. 1992.

9.  L.J. Latecki and R. Lakämper, "Application Of Planar Shape
    Comparison To Object Retrieval In Image Databases". *Pattern
    Recognition*, 35(1), pp.15-29, 2002.

10. L.J. Latecki and R. Lakämper, " Shape Description and Search for
    Similar Objects in Image Databases", *State-of-the-Art in
    Content-Based Image and Video Retrieval*, Kluwer Academic
    Publishers, 20001.

11. Esther M. Arkin, L. Paul Chew, Daniel P. Huttenlocher, Klara Kedem,
    and Joseph S. B. Mitchell, "An Efficient Computable Metric for
    Comparing Polygon Shapes", *IEEE Transactions on Pattern Analysis
    and Machine Intelligence*, vol. 13 (3), pp. 209-216, March 1991.

12. Milan Sonka, Vaclav Hlavac, and Roger Boyle, *Image Processing,
    Analysis, and Machine Vision,* Second Edition, pp. 240-248,
    Brooks/Cole Publishing Company, 1999.

13. Rafael Gonzalez and Richard Woods, *Digital Image Processing*,
    pp.655-659, Prentice Hall, 2002.

14. Charles Zahn and Ralph Roskie, "Fourier Descriptors for Plane Closed
    Curves", *IEEE Transaction on Computer*, vol. C-21 (3), March 1972.