VIEWGLE: Fast Extraction of Similar Partial Images
for Querying Viewing Parameters
Ai Gomi*Takayuki Itoh*Koji Koyamada**

Shohei Hido**(*) Ochanomizu University(**) Kyoto University
E-mail: {gomiai, itot}@itolab.is.ocha.ac.jp

Abstract

to investigate various definition of the similarity. Various

This paper presents a technique for quickly extracting target

visual criteria can be applied to calculate the similarity, such asparts of pre-stored high-resolution images, where the extracted

color signature [4], color characteristics [5][6], and perspective

parts are similar to an input small image. Our technique first[7]. Some mathematical schemes, such as Wavelet [8] or vector

quickly extracts thousands of candidates of target parts byquantization [9], are also useful for image similarity

rough similarity estimation, and then calculates similarity

estimation.

values between the candidates and input images. The techniqueSince many of image retrieval techniques focus on similarity

then generates response surface interpolating the similarity

estimation between equally-sized images, partial image

values on an image space, and finally discovers optimal target

retrieval is also an interesting topic. Most of partial image

parts by searching for the maximum similarity on the response

retrieval techniques extract rectangular parts from pre-stored

surface. We have not guaranteed the 100% accuracy of thelarge-scale images, and compares the extracted parts with input

partial image retrieval yet, but the technique realizes nearly

images.

real-time retrieval from large-scale images contains millions ofcompares RGB values pixel-by-pixel to examine the similarity,

pixels. The technique can be used to various applications, but

but it is very time-consuming for large-scale images. Some of

we especially expect to apply for querying viewing parameters.

fast template matching techniques, such as sequential similarity

Well-known templatematching

technique [10]detection algorithm [11] and coarse-to-fine search [12], have

1. Introduction

been also well-known. Kimura et al. archived nearly real-time

Since digital cameras, camera-embedded cellular phones, andand accurate partial image retrieval [13], but their test cases are

the Internet have got drastically popular, it got easier to create

still much smaller than image sizes of recent consumer-purpose

or obtain digital images. There are currently huge numbers ofdigital cameras.

large-scale images in our daily life, so recently requirements

Another issue of template-matching techniques is retrieval offor efficiently retrieving those images have been increasing.

“similar but different” objects. Specific object retrieval

Some popular image retrieving systems refer keywords

techniques [14,15,16] are also interesting topics in the view of

associated to the pre-stored images [1,2]. However, the systems

this issue, but again, their test cases are not enough large as

have some problems, because vocabulary associated from theimage sizes of recent digital cameras.

images strongly depends on sense of person, and it is difficult
to associate words to images adequately for every people.
One solution to solve such problem is retrieval of images not

Against well-known template matching approach to find thetarget partial images, the technique aims the discovery of“similar but different” partial images in the high-resolution

only by referring keywords, but also by analyzing visual

images. The technique first generates clusters of adjacent

property such as color distribution and shapes of contents.

similarly-colored

Many of such technique require input images, then compare theconnecting the centers of clusters of dominant three colors.

visual property between the input images and pre-stored query

Fast triangle similarity calculation successfully extracts small

images, and finally return the most similar image as output. For

numbers of candidates of target parts. The technique thenexample, QBIC[3] is one of the first commercial image query

applies known image similarity calculation technique, andsystem, which accepts similar images and sketches as input

generates a response surface interpolating the similarity values.

information.

The surface is used to discover the optimal target part that

Capability of similarity-based image retrieval techniques
depend on definitions of the similarity. Therefore it is desirable

pixels,andthengenerates

triangles

brings the maximum similarity.
This technique has a potential to be applied to various

applications. We are especially interested in query of viewing

traffic signs, can be examined by inputting images ofparameters of the small images, by searching for target parts

displays or signs. This application is interesting for traffic

from high-resolution images placed in virtual 3D spaces.

analysts or map developers.
We think that such scenarios queries viewing parameters from2. Overview

large-scale (ex. panoramic) images. Accelerated retrieval

2.1 Algorithmic overview

techniques are desirable for such purposes because theHere we formalize the problem of extraction of similar partial

scenarios assume real-time usage or huge number of images.

images as follows:

However, these scenarios do not assume fully-automated1.

Let the input small image as I, and the high-resolution

processes, so we think it is still useful even if the techniques do

image as I’.

not guarantee 100% accuracy of retrieval results. That is why

Let an arbitrarily extracted rectangular part of I’ as I”,

we aimed computation time rather than 100% accuracy.

2.

whose upper-left corner locates at (x,y), width is w, and3.

height is h.

3. Implementation

Calculate the similarity between I and I”, and discover I’’

3.1 Color reductionthat brings the maximum similarity value.

Various known image similarity calculation methods can be

Since known image similarity calculation techniques areapplied to partial image retrieval, but currently we apply asomewhat costly, the technique may take huge calculation timecolor-based similarity calculation algorithm. It first generates

if we apply every possible values of x, y, w, and h, to extract I”.

the clusters of similarly-colored pixels by K-means method

This paper discusses the technique for quick extraction of thewhich classifies them into K clusters. The algorithm we applied

optimal I”, consists of the following two steps.

is as follows:[Step 1] This step quickly extracts candidates of target parts by

1.

Spread all pixels in an image onto a RGB-space.

rough similarity estimation.

2.

Reasonably choose the centers of K clusters.

[Step 2] This step calculates similarity values between I and

3.

Classify all pixels into the cluster whose center is theclosest in the RGB space.

multiple the candidates of I”, and generates a response surface
interpolating the similarity values. The response surface brings

4.

Recalculate the positions of centers of generated clusters.

the optimal I” that brings the maximum similarity value.

5.

Terminate if the centers of new clusters are enough close

Here, features of our technique are as follows:•

Low computation time for large-scale images•

Discovery of “similar but different” parts, such as

to the previous positions, otherwise return to 3.

slightly larger, smaller, brighter, or darker parts.
We have not guaranteed the accuracy of our technique yet, but
the next section appeals that partial image retrieval techniques
are useful in some scenarios even though they are not 100%
accurate.

2.2 Scenarios
Partial image retrieval techniques have potentials to use forvariety of applications, but we especially expect to use for thefollowing scenarios:•

If the technique is implemented to digital cameras, it canfocus on specific objects or persons, even though the••

Figure 1. (Upper) input images. (Lower) posterized images

cameras are intermittently used and therefore well-knownby k-means method. (Left) a scene of shining day. (Right) a

video-based retrieval technique cannot be used.

scene of rainy day.

Collecting images taken by various people at the sameplace and comparing with image database, users canCurrently we assume that K, number of clusters, arespecific which camera angles were preferable there. This

pre-defined or given by a user. After terminating the above

application is especially interesting for some specificalgorithm, our implementation assigns same color IDs to thebusiness, including civil developers and tour conductors.

pixels belonged to each cluster, and then decomposes the

Visibility of civil objects, such as advertising displays orclusters according to adjacency of pixels and assigns labels tothe decomposed clusters, to obtain same-colored regions of thez Algorithm for comparing triangles

image.

Each center of gravity of the triangle T in the input image I is

The process can bring same clustering results from images

defined as R1(xR1,yR1), R2(xR1,yR2), and R3(xR3,yR3), in thewhich have slightly different tones, such as same scenes whereimage coordinate of I. Similarly, each center of gravity of theweather or sunshine direction varies. Figure 1 shows thetriangle T’ in the retrieved image I’ is defined as R111’’’ii(x,y ),i R1’i R1’i

example of the veriety of tones, where upper images are input

R2’i(xR2’i,yR2’i), and R3’i(xR3’i,yR3’i), in the image coordinate ofimages and lower images show the clustering results by

I’. In this case, R1 and R1’i, are the centers of the same-coloredposterinzing the images as 15 colors. The upper-right image isclusters. Similarly, R2 and R2’I, and R3 and R3’I, are the centerstaken by a shiny day and the upper-left is rainy. Comparingof the same-colored clusters. At first, our implementation

lower-left and lower-right images, it can be observed that same

compares each of ‘x and y’-coordinate value, as shown in

objects in both images are categorized into the same clusters.

Figure 3.

As described in Section 2.1, our technique first roughly
extracts candidate target parts from the large-scale images, andxthen calculates the similarity values between the input imagesyand the candidate parts. Posterized images are used for the bothR2(xR２,yR２)

yR2

processes. In the second process, our technique calculates
distances between same-colored regions of I and I’’, andobtains average distance values as errors between I and I”. We

yR1

use the inverse number of the average distances as similarity

R1(xR1,yR1)

values. The algorithm is similar to the implementation
introduced in [8].

R3(xR3,yR3)

yR3

3.2 Rough similarity calculation

xR1

Step 1 of the technique applies rough similarity calculation

xR2

xR3

Figure 3. The position of the centersR.

scheme. It first applies clustering and labeling described in 2.2
to I and I’, and generate a triangle T, connecting centers of thelargest three regions, R1, R2, and R3, as shown in Figure 1(left).

If each coordinate x and y of R1, R2, and R3 in I are ordered as

It then extracts regions from I’, which have same colors with

the inequation (1),R1, R2, and R3. It then generates all possible triangles T’i,
connecting three regions in I’, where those combination ofx R1 ≤ x R 2 ≤ x R3 , y R1 ≤ y R 2 ≤ y R3

three colors are same as T, as shown in Figure 1(right). It

the triangles T’i which are satisfied the inequation (2):calculates similarity between T and each of T’i, by simply

x R1′i ≤ x R 2′i ≤ x R3′i , y R1′i ≤ y R 2′i ≤ y R 3′i

calculating angles between each edge of T and each of T’i .

(1)

(2)

Though the number of T’i may be very large, its computation

And then similar triangles T’I, satisfying the inequation (3), aretime is generally small. If T’i is enough similar to T, theextracted from them. Here value S is a threshold specified by atechnique extracts a rectangular region around T’i as I’’, auser.

candidate of the target part.

x R 2 ′i − x R 1 ′ix R 2 − x R1−
x R1 − x R 3
x R 1 ′i − x R 3 ′i

入 力 画 像 I R1

T

< S

，

R2
R3

y R 1′i − y R 2 ′iy R1 − y R 2−<S
yR3 − yR2
y R 3′ − y R 2 ′Input image I

i

i

(3)

Since triangle comparison is dealt with only by theHigh-resolution image I’
Figure 2. Triangle T in the input image I, and triangle T’i inhigh-resolution image I’.

combination of four simple inequations, our implementation
can quickly find similar triangles.

3.3 Optimal part discovery using response
surfaces
Step 2 calculates image similarity between I and I” using the
known technique described in 2.2. Since the candidates are justroughly extracted, it often happens that the optimal I” islocated among the candidates. The known image similarity
calculation is somewhat costly, and therefore it is notpreferable to calculate the similarity between I and every
possible I” around the candidates. Here we discuss how to
obtain the optimal I” by the small number of image similarity
calculation and its interpolation.
Optimal point

similarity

Figure 5. (Upper-left) Input image I. (Lower-left) Output
image I”. (Right) Retrieval image I’.
Least square surface

xi

Figure 4. Response surface method.
Response surface method is a well-known technique todiscover the optimal solution from small number of samplingvalues. Usually the method approximates the function of

Figure 6. Similar images at the candidate positons.

parameters and the response value as two-dimensional
polynomial equation described as equation (4).
nny = β 0 + ∑ β i xi + ∑ β ii x + ∑ β ij xi x j
i =0

i =0

0

n

2
i

(4)

i< j

100

200

300

0
10
20

Calculating the similarity between I and I”, the techniquesubstitutes the parameters and the similarity values to (4). Herey is the similarity value, and x0 to x3 are parameters (x,y,w,h) of
I”. The values of β , β i , β ii , β ij can be calculated because (1)becomes simultaneous equations of these variables. The

30

Optimal point

40(18,190)506070

response surface generally has a peak of the response value, as
shown in Figure 4, which is to be easily discovered. The
technique returns the output image with parameters (x,y,w,h)that brings the maximum similarity value.

4. Experiments
Figure 5 shows an example of the input(131×189pixels),
retrieval(326×375pixels), and output (113×164pixels) images.
Step 1 generated 54621 triangles in the retrieval image;
however, computation time for similarity calculation between
the triangles was only 2.7 seconds. The step selected only 11
triangles as candidate positions. Figure 6 shows the images
extracted at the candidates.

Figure 7. Discovery of optimal point using response surface.
Step 2 calculates the similarity of images between I and 11
images shown in Figure 6, and then applies the response
surface method to obtain the output image. Figure 7 shows thesimilarity values of 11 images, and the optimal point obtained
from the response surface. Here sizes of spheres denote thesimilarity values, and axes denote x- and y-coordinates of I”.
Figure 5 (Lower-left) shows the output image at the optimal
point shown in Figure 7. The result shows that the techniquesuccessfully discovered an enough similar partial image bysmall number of similarity calculation and optimal point
finding, in a small computation time.

0

retrieval

0(1037x691pixels), and output (71x291pixels) images, which

50

Figure

8

shows

the

input

(67x272pixels),

attempted the retrieval of a specific person from a large-scale

200

400

600

800

1000

100

image. Step 1 generated 324 triangles and computation time forsimilarity was only 0.25 seconds. 23 images at the selected
triangles advanced for step 2.

150
200

Optimal point
Optimal point(545,260)

250
300
350

Figure 10. Discovery of optimal point using response
surface.

Figure 8. (Upper-left) Input image I. (Lower-left)
Output image I”. (Right) High-resolution image I’.

Figure 11. (Upper-left) Input image I. (Lower-left)
Output image I”. (Right) High-resolution image I’.

1550
0

1600

1650

1700

1750

1800

1850

1000

100
900

200

800

300700400600Figure 9. Similar images at the candidate positons.

500500600400In this case, colors of cloth worn by person must be different
from background colors, but it may conditionally fail. To solve
this problem, we would like to extract not only by colors ofobject but also by the shape, as a future work. As shown in
Figure 10, candidate positions in this test divide into three

300

700

200

800

100

900
0

1000 1550

1600

1650

1700

1750

1800

1850

areas. We should independently apply the response surfaces for

Figure 12. Discovery of optimal point using response

the three areas, but current our implementation requires manual

surface.

work for the division. Its automation is also our future work.
Third experiment is shown in Figure 11, where input(183x380pixels),

hight-resolution(3456x2304pixels),andoutput (349x919pixels) images. Step 1 generated 72930[10]http://www.netnam.vn/unescocourse/computervision/861.h

triangles in the high-resolution image, but the computationtm

time for similarity calculation was only 0.79 seconds. The step[11] E. I. Barnea and H.F.Silverman, A class of Algorithms forselected only 16 triangles as candidate positions. Figure 12

Fast Digital Image Registration, IEEE Transactions onshows the similarity values of the candidates and the optimal

Computers, Vol. C-21, pp. 179-186, Feb 1972.

point obtained from the response surface.

[12]http://www.cs.ou.edu/~atiq/papers/mhtc-ijamt.pdf[13] A. Kimura, T. Kawanishi, K. Kashino, Similarity-based

5. Conclusion

Partial Image Retrieval Guaranteeing Same Accuracy asThis paper presented a technique for quick extraction of

Exhaustive Matching, IEEE 2004 International Conference on
Multimedia & Expo. (ICME2004), 2004.

similar partial images from high-resolution images.
Our experiment proofed that the technique is very quick, but[14] T. Hattori, H. Kitajima, T. Yamasaki, Face Pattern

not sometimes accurate as s shown in Figure 7. One challenge

Recognition And Extraction From Multi

is improvement of accuracy while the technique preserves theProceedings of ICEIS 2003 (Fifth International Conference on

computational efficiency. Reasonable combination with other

Enterprise Information Systems), ACM, AAAI and IEEE,

techniques,pp.92-99, 2003.

such

as

shape-basedsimilarity

calculation,

Persons Scene,frequency analysis, and specific object extraction, is an[15] R. Fergus, P. Perona, A. Zisserman, Object Class

interesting future work for us.

Recognition

As mentioned in the Section 1, we are interested in using

by

Unsupervised

Scale-Invariant

Learning,

Proceedings of the IEEE Conference on Computer Vision andthis technique for query of viewing parameters of images. If

Pattern Recognition, pp. 264-271, 2003.

the high-resolution image is located in a virtual 3D space (i.e.

[16] S. Helmer, D. G. Lowe, Object Recognition with Many

360-degree cylinder image for QuickTime VR [17]) and there

Local Features, Generative Model Based Vision 2004 (GMBV

are actually similar parts to the input image, the technique can2004).

suggest the viewing parameters of the input image. Also, if we[17] S. E. Chen, QuickTime VR: An Image-based Approach tohave high-resolution images taken at near points, we can obtain

Virtual Environment Navigation, ACM

intermediate images by applying View Morphing [18]. Such

29-38, 1995.

application should be challenging but interesting future work[18] S. M. Seitz, C. R. Dyer, View Morphing, ACM

for us.

SIGGRAPH ’96, pp. 21-30, 1996.

References[1] http://bsearch.goo.ne.jp/[2] http://images.google.com/[3] C. Faloutsos, R. Barber, M. Flickner, W. Niblack, D.
Petkovic, and W. Equitz. Efficient and Effective Querying by
Image Content. Journal of Intelligent Information Systems, Vol.
3, No. 3, pp. 231-262, 1994.
[4] Y. Rubner., Perceptual Metrics for Image Database
Navigation, PhD thesis, Stanford University, May 1999.
[5]http://chihara.aist-nara.ac.jp/people/95/masano-h/research-j.
html (in Japanese)[6]http://criepi.denken.or.jp/jp/pub/annual/1998/98seika30.pdf[7]http://www.simplex.t.u-tokyo.ac.jp/theses/2001m-yatagawa_eiji.pdf (in Japanese)[8]http://www.taf.or.jp/publication/kjosei_18/pdf/071.pdf(inJapanese).
[9] K. Inoue, K. Urahama, Similarity Search of Videos byUsing Reference Images, Journal of the Institute of Electronics,
Information, and Communication, Vol. J84-D-II, No. 7, pp.
1533-1536, 2001. (in Japanese)

SIGGRAPH ’95, pp.