Knowledge Propagation in Large Image Databases Using
Neighborhood Information
Michael E. HOULE
1

1Vincent ORIA

2

Shin’ichi SATOH
2National Institute of Informatics, Japan

1Jichao Sun

2

New Jersey Institute of Technology, USAMotivation

KProp – Influence Graph

KProp – Stabilized Status

Practical methods for the indexing and querying of large-scale image databases often requirethat the images be annotated with semantic information beforehand. Unfortunately, due to thehigh costs associated with human annotation, or
the unavailability of cameras with GPS functionality or other special devices, the number of labeled objects is often severely limited. Existing
solutions to adding semantic information are labor intensive and not always accurate. The aimof this research is to reduce the level of humanintervention in the semantic annotation processof images.

KProp propagates labels from labeled data objects to new data objects that resemble themthrough an influence graph derived from neighborhoods of the objects.
• Draw self-edges for labeled objects.
• If an unlabeled object is one of the k-NN of alabeled object, draw an edge from the labeled
object to the unlabeled.
• Draw bi-directional edges between two unlabeled
objects if either is one of the other’s K-NN.

• It can be proved that in equation Sq = PSq−1, S

will converge in finite steps, as long as thedamping factor 0 < df < 1.
• If we interpret the final score matrix by sorting
each row in non-increasing order, we can obtainranked lists of labels, with the first entries
corresponding to the maximum likelihood
assignment of labels to objects.
Bush10 Blair 01

Bush0.73
0.05f
S = Bush
0.630.11
0.16 0.59 Blair
0.35 0.32 BushApproach

Objective
A few occurrences of each object of interest(e.g., a person) would be labeled manually.
The problem is to determine the labels (e.g.,names) of all other occurrences of objects in thedatabase.

Experiments• KProp is compared with Query-based baseline

KProp – Label Propagation• Scores measuring the degree of association

between labels and objects are computed
iteratively. Only labeled objects with the label
being propagated are given initial scores of 1 (allothers are given initial scores of 0). Compute theinitial score matrix S0 from the graph.

(Bestmatch), SVM and LapSVM using threedatasets: ALOI-100 (simple objects), MNIST(handwritten digits) and Google-23 (faces).
• KProp performs consistently better than theothers in ALOI-100 and MNIST. In Google-23, it
is outperformed by SVM when the label size issufficiently large.
• The relative performance of KProp can beexplained in terms of the transitivity of object
relationships.
9590

 10
0 1 00
S0 = 0 0 0 0
00

Average recall (%)

We propose a new method, KProp, that seeks
to propagate labels from initially annotated dataobjects to new data objects that resemble them,according to a user-supplied measure of similarity. KProp builds an influence graph derived
from neighborhoods of the objects with respect
to the similarity measure, and then propagatesknowledge scores through the graph from those
nodes corresponding to objects with apriori semantic annotations.

85
80
KPropBestmatchSVM
LapSVM

75
70
123
Label size

45(a) ALOI-10085• Each object’s score is computed by averaging all• Query-based baseline: The label of an unlabeled

object is decided by its nearest labeled neighbor.

its incoming neighbors’ scores. Compute thepropagation matrix P from the graph.
• Adjacency matrix:

1 0 0 0 0 0
0 1 0 0 0 0
1 0 0 1 0 0
1 0 1 0 0 1

0 1 0 0 0 10 0 0 1 1 0

75
Average recall (%)

Existing Solutions

80
70
65
60
55
50
KPropBestmatchSVM
LapSVM

45
40
35
12

• Row normalized:

methods: Labeled objects are treated as training
set and each of the unlabeled objects isclassified.

1000 00
 0 1 0 0 0 0 
 0.5 0 0 0.5 0 0 
0.33 0 0.33 0 0 0.33

0 0.5 00 0 0.5
000 0.5 0.5 055



1
00000
 0 1 0 0 0 0 
 0.45 0 0 0.45 0 0 
0.297 0 0.297 0 0 0.297

0 0.45 0
00 0.4500
0 0.45 0.45 050
45403530KPropBestmatch
SVMLapSVM

25201• The score propagation can be performed by

iterative matrix multiplication of the propagation
matrix P and the score matrix S: Sq = PSq−1.
連絡先:

560

• The propagation matrix P (damping factor df = 0.9 isapplied to non-self edges):4(b) MNIST

Average recall (%)• Supervised or semi-supervised learning

3
Label size

Michael E. HOULE(フフー ル マ イ ケ ル )/国立情報学研究所
客員教授
 : 03 - 4212 - 2538
t : 03 - 3556 - 1916
B : meh @ nii.ac.jp

2

3
Label size(c) Google-23

45