Spatial Knowledge in Image

Databases

Dr. D. S. GURU
dsg@[Link]

Department of Studies in Computer Science,

University of Mysore, Manasagangotri
Mysore-570 006, INDIA
1
 Archival
Image / Video
Intermediate Spatial
Databases Representation Topology

Transformation Indexing

Input Image / video

Database

Transformation Matching
Query Image / Video
Retrieved
Intermediate Images / Videos
Representation
Retrieval
3
4
5
 Official Letter
Personal Letter
Date: 18/01/03 24/06/2004
Place:Mysore Mysore
Dear ---,
To,
LMN,
-----, How are you? How is your family?
-----, I am fine and doing well in academics.
Fhh kilp ppp nmbn drr jdo iopyg drrho
Dear Sir, oysr srrg kkiyh edf if sfg uhtt ---------
-----------------------------

jjhfjkhk hjhgt ytruo ynb hjhjuiu jhjjhk

hljklj hgh gjk jjjk add bcbz jdii ww llj xkkj With Love
vhjv axrv deff aadf grrg sxfgg nj,b jjg -------------
To,
With warm regards, ------
--------
--------
Faithfully yours, --------
(XYZ)

6
Artificial Intelligence

7
PR&AI ACM

8
PR&AI ACM

9
 PRL

PAMI PR

10
 Body

Body
PRL

PR
PAMI

11
A Man

L S L

L L

H S

L L L L

An Animal

H – Head; L – Leg/arm; S – Stomach & Chest/ Stomach

12
Formally,
Spatial information is a feature associated with every object in space
i.e., • Each object has a unique reference in space
Some references are
• Latitude and Longitude
• Street addresses
• Visible physical features (Mountain top, river bank)
• Invisible human assigned areas
• Jurisdictional boundaries (Country lines, state or
national boundaries)

Symbolic image is an abstract representation

Involves identification of individual components and labeling

13
2D-String (Chang et al., PAMI, 1987)

< left/right/below/above
= at the same spatial location
: in the same position as

M1 M2 M3B

TPD H1 H2

S T W

(x-string, y-string)
(M1=T:P:D=S<M2=H1=T<M3:B=H2=W,
S=T=W<T:P:D=H1=H2<M1=M2=M3:B) 14
2D-H String
(Chang and Li, LA, 1988)
X X X X Y X
X X Y Y

X X X X XY XY XY

Y X X Z X Y X Y

X Y Y Y Y Z X Z Z
X

XY XY XYZ XYZ
XY XYZ XYZ

W Y
X Z

WXYZ

15
 B E B E B E

A C F A C F A C F

D D D

Q1Q3Q4 ABC EF D

Drawback of 2D H String
A E G Infix:
B AB C E DF G H
C H
D F Prefix

AB C E DF G H

1010 1111 1001 AB 0010 C 0010 E 0101 DF 1100 1000 G 1000 H

16
Adaptive 2D-H String (Chang and Lin, PRL, 1995)
A E G A E G A E G A E G
B B B B
C H C H C H C H
D F D F D F D F

1111 1111 10 1111 10 1001AB

A E G A E G A E G
B B B
C H C H C H
D F D F D F
1111 10 1001AB 11 1111 10 1001AB 11 0010C 1111 10 1001AB 11 0010C 01D
A E G
B
Finally,
C H
1111 10 1001AB 11 0010C 01D 1010EG 0110FH
D F
17
Global 2D String (Jungert, ICPR, 1988)

A%B: min(A)>min(B),
A<B: centre(A) < centre(B)
A A max(A)<max(B),
length(A)<length(B)
B B
A=B: centre(A) = centre(B)
A A [ B: min(A)=min(B),
A B length(A)<length(B)
B
A A ] B: max(A)=max(B),
A|B: edge to edge with length(A)<length(B)
A B

B
A A \ B: min(A)<min(B),
length(A)<=length(B)
B
Global operators
A A / B: max(A)>max(B),
length(A)<=length(B)
Edge to edge operator B

Local operators 18
Drawback:
The local operators and the derived binary relations cannot be stored in a
unified structure with global operators, into a global 2D string.

Generalized 2D String (Chang et al., IEEE TSE, 1989)

E
D
F
C

B
A

D|A=D|A=C=D|A=C=D=E A|B|D|D=C|D=C=F|D=F|D|E
|A=B=C=E|B=E|B|B=F|F

Drawback
Not ideally economic for complex images in terms of storage space efficiency and
navigation complexity in spatial reasoning 19
 2D C-String (Lee and Hsu, PR, 1990)
A% B
A<B B<A B% A
A A A
A
B B B B

B|A A
A A|B A A= B
B
B B
Notation Condition Meaning

A A/B B/A A A<B end(a) < begin(B) A disjoint B

A=B begin(A) = begin(B), A is the same as B
B B end(A) = end(B)
A|B end(A) = begin(B) A is edge to edge with B

A%B begin(A) < begin(B), A contains B and they have

end(A) > end(B) not the same bound
A A]B A A[B
A[B begin(A) = begin(B), A contains B and they have
B B end(A) > end(B) the same begin bound

A]B begin(A) < begin(B), A contains B and they have

end(A) = end(B) the same end bound

A B[A A B]A A/B begin(A) < begin(B) A is partly overlapping with B

< end(A) = end(B)
B B
20
Limitation

A B A B A B

C C
C

A<B%C

21
2D C+ String (Huang and Jean, PR, 1994)
5 3 5
9
A A B

A4 <2

A B A B

C C

A2<1B8%1C3 A4<3B4%1C1

Still uses the cutting mechanism

Length of string is O(m2)
22
2D-Z String (Lee and Chiu, PRL, 2003)
Similar to 2D C+ string, but avoids cutting
Makes use of ‘/’ operator
String length is O(m)
2D R String (Petraglia et al., Progress in Image Analysis and Processing, 1994)
Drawback
C
A
C
A B F G

F
B D
G

D
23
2D-Z String (Lee and Chiu, PRL, 2003)
Similar to 2D C+ string, but avoids cutting
Makes use of ‘/’ operator
String length is O(m)
2D R String (Petraglia et al., Progress in Image Analysis and Processing, 1994)
Drawback
C
A
C
A B F G

F
B D
G

D
24
Variants of 2D strings
Type Year Proposed by

2D String 1987 Chi-Kuo Chang, Qing-Yun Shi and Cheng-Wen Yan

2D+-String 1999 Bowon Kim and Kyhyun Um

2D H-String 1988 S. K. Chang and Y. Li

adaptive 2D H-String 1996 C. C. Chang and D. C. Lin

2D G-string 1988 E. Jungert and S. K. Chang

2D C-String 1990 S. Y. Lee and F. J. Hsu

2D C+-String 1994 P. W. Huang and Y. R. Jean

2D C-Tree 1998 F. J. Hsu, S. Y. Lee and B. S. Lin

2D B-String 1992 S. Y. Lee, M. C. Yang, and J. W. Chen

2D R-String 1993 G. Petraglia, M. Sebillo, M. Tucci and G. Tortora

2D RS-String 1996 P. W. Huang and Y. R. Jean

2D Z-String 2003 Anthony J. T. Lee, H. P. Chiu

25
Matching based on Strings
• Subsequence Matching
• Longest Subsequence Matching

• Exact matching : linear search

• Similarity matching: Non-polynomial

2D-string, Hash-oriented Algorithms

Static Hashing
•Retrieving the most similar symbolic pictures from pictorial database.
(Chang and Wu, Inform. Process. Management , 1992)
• Applications of geometric hashing to iconic database retrieval.
(Wu and Chang, PRL,1994)
Dynamic Hashing
•Perfect hash table algorithm for image databases using negative associated values
(Sabharwal and Batia, PR, 1995)
•Image databases and near perfect hash table
(Sabharwal and Batia, PR, 1997)

26
 Nine directional code (Chang, Inf. Sci. Eng. 1991)
3 2
4 A C

5 1 B F
0 G

6 8 D
7

A B C D F G

A -
• 9DLT Matrix B 7 -
• Principal Component Analysis C 1 2 -
(Chang and Wu, PRL, 1995) D 8 8 6 -
• Hashing
(Zhou and Ang, PRL, 1997) F 8 1 6 2 -
G 8 1 8 2 1 -
27
Exact Match Retrieval
An exact match retrieval scheme based upon principal component analysis
(Chang and Wu, PRL, 1995)
Similarity Retrieval
Retrieving similar pictures from a pictorial database by an improved hashing table
(Zhou and Ang, PRL, 1997)
41 types of spatial relationships

Relational Indices
h(n) Picture Indices

1 (A,B) 3 1 2 3
… …
5 (B,D) 9 1 4 6
… …
8 (B,E) 3 1 3 5
… …
11 (D,E) 3 1
…
Portion of the index structure of the database 28
Limitations of Nine directional codes
B A 3
4 2
A C D
5 1
B F F 0
G
C
6 8
D G 7

A B C D F G A B C D F G

A - A -

B 7 - B 5 -
C 1 2 - C 7 8 -
D 8 8 6 - D 6 6 4 -

F 8 1 6 2 - F 6 7 4 8 -
G 8 1 8 2 1 - G 6 7 6 8 7 -

29
Spatial Orientation Graph (Gudivada and Raghavan, ACM, IS, 1995)

C
C A
A

F F
B B
G
G

D
D

AB = 89°; DF = 87°; FG =145°;

BC = 50°; CD=80°;
AC = 13°; DG =43°;
BD=115°; CF = 72°;
AD=120°;
BF = 20°; CG =95°;
AF = 130°;
BG =175°;
AG =140°; 30
Similarity measure proposed by Gudivada and Raghavan

100.0  1 + cos() 
Similarity  Similarity +  
n1 (n1 − 1) / 2  2 

31
Triangular Spatial relationship
(Guru and Nagabhushan, 2001, PRL)

θ1 M1
M2 θ2
θ3
B
A M3

The triangular spatial relationship among the components A, B and C is represented by

a set of quadruples
{(La, Lb, Lc, θ3), (La, Lc, Lb, θ2), (Lb, La, Lc, θ3), (Lb, Lc, La, θ1), (Lc, La, Lb, θ2),
(Lc, Lb, La, θ1)}.

32
If (Li1, Li2, Li3, θ) is the quadruple to be chosen, then the labels Li1, Li2, and Li3
must satisfy one of the following conditions.

1. The labels Li1, Li2, and Li3 are distinct and Li1 > Li2 > Li3.
2. Li1 = Li2 and Li3 < Li1.
3. Li1 > Li2 and Li2 = Li3 and Dist(Comp(Li1),Comp(Li2)) 
Dist(Comp(Li1),Comp(Li3)).
4. Li1 = Li2 = Li3 and Dist(Comp(Li1), Comp(Li2))  M,
where,
M =Max( Dist(Comp(Li1), Comp(Li3)), Dist(Comp(Li2), Comp(Li3) ) ).
here,
Dist(A, B) : Computes the Euclidean distance between the
midpoints of A and B.

33
The θ is given by

 if 1  90 0
 = 1
 180 − 1 otherwise.

here,

where,
S1= Dist(Comp(Li1),Comp(Li3)),
S2= Dist(Comp(Li1),Comp(Li2))/2,
S3= Dist(Mid(Comp(Li1),Comp(Li2)), Comp(Li3)).
here,
Mid(X, Y) denotes the midpoint of the line joining the centroids of the
components X and Y.

34
TSR + B-tree (Guru et al., PRL, 2003)

Supports Similarity Match Retrieval

• Triangular Spatial Relationship based symbolic image representation

• Quadruple Generation

• Key Mapping : hashing

• B-tree for Symbolic Image Database Creation

• Logarithmic Time Complexity

35
 TSR + Statistical (Punitha and Guru, 2005, PRL)

Exact Match Retrieval

• The proposed model preserves TSR among the components in a symbolic

image by the use of quadruples

• A distinct and unique key called TSR key is computed for each distinct
quadruple

• The mean and standard deviation of the set of TSR keys computed for a
symbolic image are stored along with the total number of TSR keys as the
representatives of the symbolic image

• An exact match retrieval scheme based on the modified binary search

technique

• Logarithmic time complexity 36

Direction of Reference
(Punitha and Guru, IEEE TKDE, 2006)

An image with direction of Direction of reference in case of many

reference candidates

i.e., dist (Op , Oq ) = maxdist (Oi , O j ) i, j  1, 2, ..., k and Li  L j 

37
 If (xp, yp) and (xq, yq) are the co-ordinates of the centroids of Op and Oq respectively,
then we define,

 yq − y p 
 = tan −1  

..................... (1)
 xq − x p 
and
 yq − y p 
 = sin 
−1 

..................... (2)
 dist (O p , Oq ) 
The direction of the line joining Op to Oq is given by,

 +  if   0 and   0

 =  −  if   0 and   0 ............. (3)

 otherwise

38
Qualitative comparison of several methods (Punitha and Guru, PR, 2008)
Adopted Invariant to Similarity/ Handling Retrieval Extension
Representation exact match multiple towards
Data Structure Image Time
and Retrieval Transformation retrieval instances of Complexity Dynamic
Schemes objects Database

Chang et al., (1988) 2D string Not Invariant Similarity No NP Not Suitable

Chang and Li, (1988) 2D-H string Not Invariant Similarity No NP Not Suitable
Chang et al., (1989) 2D-G string Not Invariant Similarity No NP Not Suitable
Lee and Hsu, (1992) 2D-C string Not Invariant Similarity No NP Not Suitable
Huang and Jean, 2D-C+ string Not Invariant Similarity No NP Not Suitable
(1994)
Petraglia et al., (1996) 2D-R string Claimed as invariant Similarity No NP Not Suitable
but, sensitive to the reference point
Huang and Jean, RS-string Invariant Similarity No NP Not Suitable
(1996)
Gudivada, (1998) ΘR-string Invariant (Except translation) Similarity No O(n) Not Suitable

Petraglia et al., (2001) 2D-C string Not Invariant Similarity No NP Not Suitable

Lee and Chiu, (2003) 2D-Z string Not Invariant Similarity No NP Not Suitable
Chang and Wu, (1992) 2D string + Hashing Not Invariant Similarity Yes O(n) Not suitable

Wu and Chang, (1994) 2D string + Hashing Not Invariant Similarity Yes O(n) Not Suitable

Sabharwal and Bhatia, 2D string + Hashing Not Invariant Similarity Yes O(n) Not Suitable
(1995)
Sabharwal and Bhatia, 2D string + Hashing Not Invariant Similarity Yes O(n) Extendable
(1997)

39
Qualitative comparison of several methods (Punitha and Guru, PR, 2008)
Adopted Invariant to Similarity/ exact Handling multiple Retrieval Extension towards
Representation match retrieval instances of Dynamic Database
Data Structure Image Time
and Retrieval Transformation objects Complexity
Schemes

Chang and Wu, (1995) 9DLT Matrix + PCA Not Invariant Exact match Yes O(log n) Not Suitable

Chang and yang, (1997) 2D-C string + 9DLT Not Invariant Similarity No O(n) Not Suitable
Matrix

Zhou and Ang, (1997) 9DLT Matrix + Not Invariant Similarity Yes O(n) Not Suitable
Hashing

Zhou et al., (2001) A Square Matrix Invariant Similarity No O(n) Not Suitable

Gudivada and Raghavan, Spatial Orientation Invariant Similarity No O(n) Extendable

(1995) Graph

Wu and Cheng, 1997 G-tree Not Invariant Similarity Yes O(log n) Suitable

El-Kwea and Kabuka Spatial Graph Invariant Similarity No O(n) Extendable

(1999)

Sciascio et al., 2004 Spatial Graph Invariant Similarity Yes (With some O(n) Extendable
constraints)

Guru et al., 2003 TSR + B-tree Invariant Similarity No O(logr n) Suitable

NP: Non Polynomial

40
 Transformation-variant strategies
Courtesy: Wei-Horng Yeh, Ph.D Thesis, National Sun Yat-sen University, China, 2008 41
 From our Team

Transformation-invariant strategies

Courtesy: Wei-Horng Yeh, Ph.D Thesis, National Sun Yat-sen University, China, 2008 42
 Applications

• Fingerprint Retrieval

• Document Image Retrieval

• Online Signature Retrieval

• Face Retrieval

• Video Retrieval

43
Fingerprint Matching
Fingerprint matching (Germain et al., IEEE CSE, 1997)

Fingerprint indexing (Bhanu and Tan, PAMI, 2003)

Triplet of minutiae
Document Image Retrieval
Indexing and retrieval of document images
(Punitha et al., ICDCIT, 2006)

• Scheme based on 9 directional codes

• B-tree based indexing

Document Image Layout

 Results
(Punitha et al., ICDCIT, 2006)

Retrieval results for the query layout at the Retrieval results for the query layout
top left corner at the top left corner
Similarity retrieval of line drawing images
(Naveen and Guru, PReMI, 2007)

a b c

(a). A line drawing image, 2(b). A labeled image of 2(a) and

2(c).Symbolic representation 2(a).

Modified 9DLT for accommodating multiple instances

Retrieval results for a query image

Retrieval results for a query image

Signature Retrieval
 Online Signature Retrieval
(Guru et al., PReMI, 2007)

Online signature with nodes and edges Successive triangle matching

Retrieval performance with 15 database For 20 sample points and for 20 queries
and 10 query signatures per class for and 05 database signatures per class.
different sample points: for 15 sample
points
Face Retrieval
Face Retrieval
(Punitha and Guru, PR, 2008)

(a) (b) (c)

(d)

(a) A sample image (b) Manual annotation of the selected dominant points on the face
(c) Symbolic image of (a). (d) Symbolic image with labels

54
Results (Punitha and Guru, PR, 2008)

Query (a) 1 2 3 4 5

First five retrieved images from the indexed database for query image given in (a)

Query (b) 1 2 3 4 5
First five retrieved images from the indexed database for query image given in (b)

55
Fig. 14 Average number of comparisons v/s number of images in the database 56
Video Retrieval
3D-List: A Data Structure for video Query processing
(Liu and Chen, TKDE, 2002)

• An extension of 2D-strings to 3D-Strings

• Representing spatial and temporal relationships among the symbols in video
• 3D-List is formulated to match 3D-strings
• Vega video database system

The video query interface

Limitation of 3D strings

Video M: frames 1: 3

A A A
B

Video N: frames 1: 3

A
B B B

Two Different videos have the same 3D string

(Lee et al., PR, 2002) Iintroduced 3D C-String:

Observations

We have seen a tremendous amount of effort put in

towards perception and preservation of spatial
knowledge for better archival of images/videos.

However,

➢ The components of images / videos are assumed to be labeled

➢ Topological relationship such as overlap, disjoint, etc., are not

fully exploited

➢ No work has completely addressed the problem of handling

multiple occurrences of similar iconic objects.
Summary
Spatial Knowledge Representation

Family of 2D Strings (Chang S. K et al., 1987)

9DLT based approaches (Chang C.C., 1991)

Spatial Orientation Graph (Gudivada and Raghavan, 1995)

Triangular Spatial Relationship (Guru and Nagabhushan, 2001)

Direction of Reference (Punitha and Guru, 2006)

Applications

61