数理解析研究所講究録
第 1744 巻 2011 年 185-188

185

Image Recognition and Retrieval
by Using Distance Information
Jinhee Chun

Natsuda Kaothanthong**Takeshi Tokuyama*

Abstract
Image retrieval system is a system for retrieving images from a large database of digital images suchas searching images on the Web. In this paper proposes an image retrieval system to perform shapebased image query by using distance description
refined by an exact geometric matching method.
In geometric pattern recognition and information
retrieval, shape descriptions based on geometric invariants play an important roles to differentiate one
shape to the others. Distributional pairwise distances is one of such description methods that is
applied in image recognition [5, 7, 9]. However, it
is known that the set of pairwise distances is notenough to describe the differeces of one shape tothe others. Though the pairwise distance is unable
to uniquely describe the object, efficiency in pattern matching by using distance distribution is an
attractive feature in practical use. Suppose that wehave a database contaning a set of $N$ shapes, andwe would like to find all shapes that resemble to agiven query data . Then, the shape description
using distance can find the set $X(Q)$ of shapes withthe same shape description as in $O(\log N)$ timeor $O(1)$ average time.
Our method needs $O(Kt+|X(Q)|)$ time, whereis the time complexity for pattem matching andis the number of candidates retrieved, which improves naive $O(Nt)$ time using solely the geometricmethod without losing the output qual$itymatching$
$Q$

$Q$

$t$

$\overline{-4-}$

Figure 1: A counter example of 4 points settion for several decades. Content-base image re$t$

trival(CBIR) has become an active topic of image
search research fild over the last few year[3].There
1is a growing interest in finding images in large col$t$$s$1
lections
or from a remote database [8]. A contentbased image query is a system that searches similar
images according to the feature of the input image.
Color and texture are features that are basicallyused. In this paper, we use object’s shape boundary as a query to search for similar images. The
distribution of pairwise distances among boundry points is a basic method used for describing
the shape. It can also be applied to a data structure such as hash table in order to support efficientquery. However, there is a pairwise distance example that the original points location is not able touniquely recofigure as shown in Figure 1. In additttion, Skiena et al.[6] showed counter examples forttthe one-dimensional case.
$f$$1\langle$

$u$

$r$
$c$

$\mathfrak{c}$

$r$

$c$

$t$

$t$

$c$

$r$

$u$

From such ambiguity of the distance distribution,$K$

we propose an image retrieval system which inte-$w$grates geometric pattern matching in order to meathe similarity of the two shapes boundary. Inorder to avoid comparing the query’s shape boundaary to every object’s shape boundary in the data
, our propose system consists of two stages as.
in Figure 2. Screening Process is used for
retrieving a set of candidates according to the disbance distribution; and Refining Process is used forthe similarity of the two boundary point
by applying a geometric pattern matching.
$gs$$s^{\urcorner}ure$$0$

1Introduction

Image recognition has been a topic of active
research in image search and pattem recogni*Graduate School of Information Science, Tohoku University, (jinhee,natsuda,tokuyama)@dais.is.tohoku.ac.jp.

$\urcorner et$$s|$$\urcorner hown$
$s$

$r|$

$t_{\dot{(}}$$\backslash omputing$$c|$$\backslash ets$
$s|$

186
2.2

Screening Process

The shape signature of the query boundary
is computed from the distance multiplicity
vector $M(Q)$ . $W(Q)$ is used for retrieving the dis$W(Q)$tanoe multiplicity vector of images which the key is$W(Q)$ . Then, the set of elements which is denoted
by $X(Q)=\{x_{1}, \ldots, x_{i}\},$ $|X(Q)|=i$ is retrieved
Figure 2: System Outline$M(x_{i})$ representsfrom the hash table. $M(x_{1}),$the distance multiplicity vector of the elements in$X(Q)$ . To select the candidates set $Y(Q),$dis2 Propose Methodtance is used to compute the similarity between
We propose a two stages algorithm for retrieving $M(Q)$ and the distance multiplicity vector of eacha set of images according to the query boundary element in $X(Q)$ which is computed bypoints. The algorithm consists of a screening pro$L_{\infty}= \max_{1\leq i\leq k}(|M_{q}(i)-M_{x_{l}}(i)|)$cess and a refining process. In the screening process, the set of similar shapes is retrieved from the where $l=1,$. Theelements with thehash table according to the shape signature which shortest
distance are selected as the candidate
are computed from the distance distribution. Since set $Y(Q)$ .
the hash table is used in the screening process, theThe time complexity for obtaining a set of candishape signature for each image in the database is dates from the dictionary is $O(1)$ . To compute thepreprocessed. The similarity of the query’s shape similarity of the query’s distance multiplicity vecboundary and the boundary from the result ob- tor to each distance multiplicity from $X(Q)$ takes
tained from the screening process is computed by $O(|X(Q)|)$ time.
applying the alignment scheme for the geometricpattem matching which is computed in the refin- 2.3 Refinig Process
ing process.
In this process, the randomized alignment
scheme [1] of the geometric pattem matching
2.1 Preprocessing
method is used to measure the similarity of thetwo boundary point sets and by counting theIn order to obtain the distance multiplicity vecnumber of coincide points in order to remove thetor, $n(n-1)/2$ pairwise distances among theirrelevant images from the candidates $Y(Q)$ .
given boundary point$=p_{1},$
whereFirst,
the sample edge sets
and $|P|=n$ is computed. Then the distance is$R\in$$S\in P$ andcounted and stored according to the length interare selected according to the binwhereval of bins which are equally divided. The distanoe multiplicity vector is denoted by $M(P)=$$j= \arg(\min_{1\leq i\leq k}|M_{p}(i)-M_{q}(i)|)$$(M_{p}(1), \ldots, M_{p}(k))$ .
The shape signature, which
represents a key in the dictionary, is denoted by The selected bin. Then, an
is denoted by$W(P)=\{w_{1}, \ldots,w_{k}\}$ whereedge $ss’$ is aligned with an edge $rr’$ , in this way, thetransformation $T=T[s, s’; r,r’]$ is obtained. The$i=1,$
boundary point is transfromed according to thetransformation as shown in Figure3(c). Finally,
While computing $M(P)$ , the set of sample the number of coincide points
is computededges
are randomly selected by counting the boundary points of that fall inand stored with corresponse to the length interval the radius from each point in $T(P)$ as shown inof each bin.
Figure3(c).
The time complexity for computing the shapesignature for all images in the data set is $O(Nn^{2})$ ,coincide $(p_{i},q)$ ,where $N$ is the number of images.
$\ldots,$$L_{\infty}$$K^{th}$$i$$\ldots,$$L_{\infty}$

$P$

$P$

$P$

$Q$

$\ldots,p_{n}$$S$$R=\{r_{1}r_{1}’, \ldots, r_{c}r_{c}’\},$$\{s_{1}s_{1}’, \ldots, s_{c}s_{c}’\},$$Q$$B_{j}$$k$$B_{j}$$w_{i}=\lfloor\log(M_{p}(i)\rfloor,$$k$$B^{8el}$$P$$\ldots,$

$T$

$c$

$mult_{\epsilon,r}$$S=\{s_{1}s_{1}’, \ldots, s_{c}s_{c}’\}$$Q$$\alpha$$mult_{\epsilon,r}= \sum_{i=1}^{n}\sum_{j=1}^{m}$

$=$

187

.. .... .....
. ..
. ..

..

$\ldots\ldots$$\bullet$$\ldots$$\ldots$$\ldots$$\bullet$. .
$\bullet$$\dot{Q}$$P$(a) Given point sets $P$ and $Q$$\Theta---\phi$$9_{\backslash }$$o_{\sim}$’or’$\backslash \backslash \backslash \backslash Q’\backslash \backslash$$-\prime p$$/$$\backslash \backslash \otimes’\vee$$”$$\backslash e$$d$be time for pattern matching, where $t=$as shown in Theorem 2.2. If we consider a pattern matching between the two boundary point sets, $O(Nt)$ time complexity is needed
to compare a query boundary point to every point
set in the data set. Since the refining process is, theonly work on $Y(Q)$ set which the size istime complexity for matching the two point sets is$t$$\delta N$ノ$\backslash$$6_{\backslash ^{\backslash }\sim}\backslash \langle$

Let$O(m|B^{\epsilon el}|)$$Q$$O(\delta Nt)$$\backslash o$$\int$$R_{l}$$S_{l}$.

Theorem 2.3 The image retrieval by using thepattem matching can be computed in $O(\delta Nt)$ in twoprocesses.

$\backslash \backslash \Theta^{\vee^{-}}\nearrow^{-}$(b) Sample points $komP$ and $Q$

3

Experimental Results

1,134 images seIn this experiment,
lected from MPEG7 Shape-l Partdataset (http: //www. imageprocessingplace. com/$rootBles_{-}V3/$ image-databases.htm). The selected(c) Coincide points between
andimages are from 59 classes. 256 boundary points
are uniformly selected from the outer boundary
Figure 3: Refining candidates algorithm
which is extracted from the binary image. The
programming language is C#.
Table 1 shows the experimental result from the$p_{i}\in T(P)$ and $q_{j}\in Q$
screening process and Table 2 shows the experimental result from the refining process. The F-measurecoincidedenotes the test’s accuracy. When comparing the$ss’$An edgeis aligned to every edge in . For all result from both process, the F-measure is 13.93%
edges in , the largest number of coincide points is increased from the screening process. Figure 4
the similarity measurement of the boundary points shows examples of result images from the screening process. Figure 5 shows result from the refining$P$and .
In an approximiate pattern matching approach, process of the query in Figure 4.
the sample points
is transformed according to$T=T[s, s’;r, r’]$ . The number of coincide points is Table 1: Result from retrieving images from hashcounted from each point in $T(S)$ .
table
The time complexity for computing the similarity measurement between $T(P)$ andof the pattern matching is $O(mn)$ where $|P|=n,|Q|=m$ .
However, the total time complexity can be reduced
to $O(m)$ by using geometric hashing or $O(m\log n)$time by using nearest neighbor search.
$B$$T(P)$$Q$$T(P)$$Q$$(p_{i}, q_{i})=\{\begin{array}{l}1, dist (p_{i}, q_{i})\leq\alpha,0, Else\end{array}$

$R$

$S$

$Q$

$S$

$Q$

Theorem 2.1 The pattem matching can be solvedin $O((n+m)|B^{sel}|^{2})$ time.

4Conclusion

Theorem 2.2 The approximate pattem matching
can be solved in $o(m|B^{sel}|^{2})$ time. If we take a conWe propose a two stages image retrieval systemstant number of sample edges, the time complexity which applied a geometric pattern matching. The
is reduced to $O(m|B^{sel}|)$ .
first stage is called a screening process which is used

188

Table 2: Refining result from the candidates re-Figure 5: Examples of shapes with large number ofcoincide points[3] R. DATTA, D. JOSHI, J. LI, AND J.
WANG, Image retrieval: Ideas, influences, andtrends of the new age,ACM Comput. Surv.,
vol.40 (2) (2008),pp.5: 1-5:60.

[4] L. GUTH AND N. H. KATZ, On the Erdos Distinct Distance Problem in the Plane. preprint,Nov.

Figure 4: Example of results from the screening
process[5] R. OSADA, T. FUNKHOUSER, B. CHAZELLE,AND D. DOBKIN, Shape distributions, ACM

Trans. Graph., 21 (2002), pp. 807-832.

for retrieving a set of candidates from the hash table. The second stage is called a refining process
which is used to remove irrelevant images from theset of candidates obtained from the screening process. The total time complexity for all process is$O(Kt+|X(Q)|)$ . Our propose method improve thenaive $O(Nt)$ time using solely the geometric matching method.

References
AKUTSU,TAMAKI,AND[1] T.
H.
T. TOKUYAMA, Distribution of distances
and triangles in a point set and algorithms
for computing the largest common point sets,
Discrete and Computational Geometry, 20(1998), pp. 307-331.
[2] M. BOUTIN AND G. KEMPER, On reconstructing n-point configurations from the distnbution of distances or areas, Advances in Applied
Mathematics, 32 (2004), pp. 709 –735.

[6] S. S. SKIENA, W. D. SMITH, AND P. LEMKE,
Reconstructing sets from interpoint distances(extended abstmct), in Proceedings of theSixth Annual Symposium on ComputationalGeometry, 1990, pp. 332-339.
[7] S. YANG, Symbol recognition via statistical integmtion of pixel-levd constmint histogmms:
A new descriptor, IEEE Transactions on Pattem Analysis and Machine Intelligence, 27(2005), pp. 278-281.

[8] D. ZHANG AND G. LU, Review of shape representation and description techniques, PatternRecognition, 37 (2004), pp. 1-19.
[9] J. ZHANG AND L. WENYIN, A pixel-levd statistical structural descriptor for shape measure
and recognition, International Conference onDocument Analysis and Recognition, 0 (2009),
pp. 386-390.