SIGIR 2007 Proceedings

Poster

On the Importance of Preserving the Part-Order in Shape Retrieval
A. Schuldt as@tzi.de B. Gottfried bg@tzi.de O. Osterhagen ole@tzi.de O. Herzog herzog@tzi.de

University of Bremen Centre for Computing Technologies (TZI) Am Fallturm 1, D-28359 Bremen

ABSTRACT
This paper discusses the importance of part-order-preservation in shape matching. A part descriptor is introduced that supports both preserving and abandoning the order of parts. The evaluation shows that retrieval results are improved by almost 38% if the original ordering is preserved.

Categories and Subject Descriptors
I.2.10 [Vision and Scene Understanding]: Shape

In order to reduce the runtime complexity it is a tempting solution to abandon the original ordering of parts. It seems, however, quite obvious that proceeding this ways leads to a certain loss of information. This can be explained by the observation that many ob ject categories comprise similar parts. What distinguishes them is how the parts are arranged along the ob jects' outlines. The main ob jective of this paper is therefore to measure the influence of preserving the part-order on the retrieval performance.
a0 a1 b1 b0 b1 a1a0 b0

General Terms
Algorithm, Experimentation, Performance

Keywords
Content-based image retrieval, shape, part-order, polygon, qualitative shape representation, bipartite arrangements

1.

INTRODUCTION

Comparing the shapes of ob jects is a challenging task in content-based image retrieval. A prominent problem consists in finding an optimal mapping between two shapes. It is a well-known result that such mapping algorithms are quite expensive in terms of runtime complexity. This is due to two factors that have to be taken into account when dealing with shapes: approximation and part order. To a certain degree approximating shapes does not much influence human perception of the respective ob jects [1]. Hence, each approach should be able to cope with different degrees of approximation. As an example, regarding polygons this means that it must be possible to compare objects with a different number of line segments. Furthermore, during the matching process the ordering of parts should be maintained (ordering constraint). To comprehend these points the reader is asked to have a look at Fig. 1. The graph illustrates how the two polygons' line segments are mapped onto each other. Thereby, it occurs that multiple line segments are mapped onto a single one and vice versa. Furthermore, it is worth mentioning that the ordering constraint is fulfilled as the graph does not comprise any intersections.
Copyright is held by the author/owner(s). SIGIR'07, July 23­27, 2007, Amsterdam, The Netherlands. ACM 978-1-59593-597-7/07/0007.

Figure 1: Mapping the line segments of two p olygons onto each other with part-order-preservation First of all, Sect. 2 introduces the qualitative shape description used -- a part-based approach for polygons. Section 3 shows how this approach performs in both cases, when abandoning the ordering of parts and when sticking to the ordering. Finally, Sect. 4 summarises the main result.

2.

A QUALITATIVE DESCRIPTION FOR SHAPES AND THEIR PARTS

With regard to the research question it has to be ensured that, apart from the ordering constraint, no other parameters are changed. Hence, a descriptor has to be found that can be applied to both whole shapes as well as parts of shapes. Certainly, it makes sense to restrict oneself to a descriptor with a low computational complexity. We choose a method that is based on a qualitative relational system, namely on bipartite arrangements [2]. As this particular approach is intended to characterise polygons, we regard their polygonal line segments as the shapes' parts. These parts are characterised as follows. Bipartite arrangements are based on the so-called orientation grid [5], that is depicted in Fig. 2 (left). It consists of three rectangularly aligned auxiliary lines that are induced on a reference segment. They divide the two-dimensional

771


SIGIR 2007 Proceedings

Poster

plane into six sectors, in which a point can be located. The positions of line segments can then be characterised qualitatively. This extension is straightforward as each line segment has a start and an end point. Both can be located in any of the orientation grid's six sectors (which theoretically makes 62 = 36 arrangements). The number of relations can be reduced by the omission of symmetries and intersections [2]. The remaining 23 bipartite arrangements, in short BA23 , are illustrated in Fig. 2 (right).

% 100

0

spring

% 100

truck

70

MPEG class

car

fly

0 70

MPEG class

3

4 pj

pl pk

2

5

Table 1: The retrieval results for all 70 MPEG classes when abandoning (top row) and preserving (b ottom row) the ordering constraint Table 1 lists the individual retrieval results for all 70 MPEG classes (ordered alphabetically). The results for almost all classes improve when the part-order is preserved. The highest increase is achieved by comparatively simple shapes (e. g., truck and car). Their limited range of relations makes it almost impossible to distinguish them just by the overall frequencies of their bipartite arrangements. Then, the relations' order plays an important role when perceiving these shapes. By contrast, for classes with relations which are rather seldom found in other classes the ordering constraint might even be obstructive (e. g., spring and fly): confining oneself to the frequency of relations allows for a broader bandwidth of shapes within one class.

1

6

pi

Figure 2: The orientation grid (left) and the 23 distinguishable bipartite arrangements (right) In order to characterise a polygon completely, all n line segments are related to each other. This results in a matrix of n2 relations. A more compact description can be obtained by computing the frequencies with which the BA23 relations occur in this matrix. This reduces the space complexity from quadratic to constant, because there is a fixed number of possible relations. The histogram deduced from the complete matrix thereby refers to the whole polygon. In this way the original ordering of parts is completely abandoned. By contrast, it is also possible to characterise single line segments. This can be achieved by computing the histogram of a single row within the matrix (which refers to just one line segment). In this case it is possible to preserve the original part order. Therewith, the same approach can be applied to both whole shapes and single parts.

4.

CONCLUSION

Testing the importance of part-order-preservation in shape matching shows that the ordering of parts actually improves retrieval results by 38% in the MPEG test data set. This result mainly relies on the fact that ob ject categories frequently comprise similar parts and are just distinguished by how these parts are arranged along the ob jects' outlines. Acknowledgement. This research is funded by the German Research Foundation (DFG) within the Collaborative Research Centre 637 "Autonomous Cooperating Logistic Processes: A Paradigm Shift and its Limitations" (SFB 637) at the University of Bremen, Germany.

3.

EVALUATION

In order to compare the retrieval results when preserving and abandoning the ordering constraint, we apply part B of the well-known core experiment CE-Shape-1 [3] for the MPEG-7 standard. With its database of 1400 silhouette images (70 classes, each comprising 20 instances) this test is especially designed for the evaluation of shape retrieval. Using each image as a query it is measured how many other shapes from the same class are found1 . The BA23 histogram of the overall shape, which abandons the original order of line segments, achieves a retrieval result of 43.70%. To evaluate the retrieval performance with part-orderpreservation each line segment is characterised by its own BA23 histogram. The line segments of two polygons are then efficiently mapped onto each other by a consistent labelling approach [4]. This test setup results in 60.28%. Thus, preserving the part-order outperforms the other method by about 17 percentage points, or almost 38%. This result underlines the importance of part-order-preservation.
1 Since the classes are semantically grouped a retrieval rate near 100% is most unlikely if only shape information is used

5.

REFERENCES

[1] F. Attneave. Some Informational Aspects of Visual Perception. Psychological Review, 61:183­193, 1954. [2] B. Gottfried. Shape from Positional-Contrast -- Characterising Sketches with Qualitative Line Arrangements. Deutscher Universitats-Verlag, 2007. ¨ [3] L. J. Latecki, R. Lak¨mper, and U. Eckhardt. Shape a Descriptors for Non-rigid Shapes with a Single Closed Contour. In IEEE CVPR, pages 424­429, 2000. [4] B. Nudel. Consistent-Labeling Problems and their Algorithms: Expected-Complexities and Theory-based Heuristics. Artificial Intel ligence, 21:263­313, 1983. [5] K. Zimmermann and C. Freksa. Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge. Applied Intel ligence, 6:49­58, 1996.

772