Modelling Distributed Priors by Gibbs Random Fields of Second Order
Проведен анализ потенциалов гиббсовских случайных полей для моделирования априорных вероятностных характеристик формы объекта. Показано, что при помощи этих полей второго порядка можно описывать как простые формы, так и пространственные отношения между ними, что позволяет распознавать сложные формы...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/82920 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Modelling Distributed Priors by Gibbs Random Fields of Second Order / B. Flach, D. Schlesinger // Управляющие системы и машины. — 2011. — № 2. — С. 14-24. — Бібліогр.: 14 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860104321930100736 |
|---|---|
| author | Flach, B. Schlesinger, D. |
| author_facet | Flach, B. Schlesinger, D. |
| citation_txt | Modelling Distributed Priors by Gibbs Random Fields of Second Order / B. Flach, D. Schlesinger // Управляющие системы и машины. — 2011. — № 2. — С. 14-24. — Бібліогр.: 14 назв. — англ. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Проведен анализ потенциалов гиббсовских случайных полей для моделирования априорных вероятностных характеристик формы объекта. Показано, что при помощи этих полей второго порядка можно описывать как простые формы, так и пространственные отношения между ними, что позволяет распознавать сложные формы как сочетания более простых.
The potentials of Gibbs random fields are analyzed for the shape prior modeling. It is shown that the expressive power of second order GRFs is already sufficient to express simple shapes and spatial relations between them simultaneously. This allows to recognize complex shapes as spatial compositions of simple parts.
Проведено аналіз потенціалів гібсовських випадкових полів для моделювання апріорних ймовірнісних характеристик форми об’єкту. Показано, що завдяки цим полям другого порядку можна описувати як прості форми, так і просторові відношення між ними, що дозволяє розпізнавати складні форми як композицію більш простих.
|
| first_indexed | 2025-12-07T17:30:06Z |
| format | Article |
| fulltext |
14 УСиМ, 2011, № 2
UDC 004.93’1
B. Flach, D. Schlesinger
Modelling Distributed Shape Priors by Gibbs Random Fields of Second Order
Проведен анализ потенциалов гиббсовских случайных полей для моделирования априорных вероятностных характеристик
формы объекта. Показано, что при помощи этих полей второго порядка можно описывать как простые формы, так и простран-
ственные отношения между ними, что позволяет распознавать сложные формы как сочетания более простых.
The potentials of Gibbs random fields are analyzed for the shape prior modeling. It is shown that the expressive power of second order
GRFs is already sufficient to express simple shapes and spatial relations between them simultaneously. This allows to recognize com-
plex shapes as spatial compositions of simple parts.
Проведено аналіз потенціалів гібсовських випадкових полів для моделювання апріорних ймовірнісних характеристик форми
об’єкту. Показано, що завдяки цим полям другого порядку можна описувати як прості форми, так і просторові відношення
між ними, що дозволяє розпізнавати складні форми як композицію більш простих.
1. Introduction
Motivation and goals
The recognition of shape characteristics is one
of the major aspects of visual information process-
ing. Together with colour, motion and depth proces-
sing it forms the main pathways in the visual cortex.
Experiments in cognitive science show in a
quite impressive way, that humans recognise
complex shapes by decomposition into simpler
parts and interpreting the former as coherent spa-
tial compositions of these parts [7]. Corresponding
guiding principles for the decomposition are iden-
tified from these experiments as well as from re-
search in computer vision (see e.g. [9]). The for-
mulation of these principles relies however on the
assumption that the objects are already segmented
and thus concepts like convexity and curvature
can be applied.
From the point of view of computer vision it is
desirable to use shape processing and modeling in
the early stages of visual processing. This allows
to control e.g. segmentation directly by prior as-
sumptions or by feedback from higher processing
layers. This leads to the question whether compos-
ite shape models can be represented and learned in
a topologically fully distributed way. The aim of
the presented work is to study this question for
probabilistic graphical models.
Related work
All mathematically well principled shape mod-
els for early vision can be roughly divided into the
following two groups.
Global models treat shapes as a whole. Promi-
nent representatives are variational models and
level set methods in particular. A shape is de-
scribed up to its pose by means of a level set func-
tion defined on the image domain. Cremers et.al.
have shown in [2] how to extend these models for
scene segmentation. Recently we have shown how
to use level set methods in conjunction with
MRFs [4]. Global shape models are well suited
e.g. for segmentation and tracking if the number
of objects is known in advance and a good initial
pose estimation is provided.
Semi global models consider shape characteris-
tics in local neighbourhoods and go back to the
ideas of G. Hinton on «product of experts» as well
as of Roth and Black on «fields of experts» (see
[6, 11] and citations therein). Mathematically
these models are higher order GRFs of a certain
type − additional auxiliary variables are used to
express mixtures of local shape characteristics in
usually overlapping neighbourhoods. Marginalisa-
tion over these auxiliary variables results in GRFs
of higher order. The work of Kohli, Torr et.al.
[10, 8] demonstrates how to introduce such higher
order Gibbs potentials directly and to use them for
segmentation in hierarchical Conditional Random
Fields (CRF). However, it is not clear how to
learn the graphical structure for such models.
Contributions
We will show that Gibbs Random Fields of the
second order have already sufficient expressive
power to model complex shapes as coherent spa-
tial compositions of simpler parts. Obviously,
these models have to have a significantly more
complex graphical structure than just simple lat-
tices. Moreover, the graphical structure itself be-
УСиМ, 2011, № 2 15
comes a parameter which has to be learnt together
with the Gibbs potentials for each considered
shape class.
From the application point of view these mod-
els have advantages especially in the context of
scenes with an unknown number of similar objects
(i.e. all objects are instances of a single shape
class). Moreover, such models can be easily com-
bined for scenes with instances of different shape
classes.
The structure of the paper is as follows. In sec-
tion 2 we introduce the GRF model for composite
shapes and discuss the inference and learning tasks.
The latter means to learn the Gibbs potentials and
the graphical structure itself. The section 3 gives
experiments exploring the expressive power of the
model − first we separately show its ability to ex-
press spatial relations between segments and its
ability to model simple shapes. Then we demon-
strate its capability to model composite shapes
including structure learning. Finally, we show
how to combine such models for the discrimina-
tion of shape classes.
2. The shape model
Probability distribution
We begin with the description of the prior part
of our shape model. Let 2D be a finite set of
nodes t D , where each node corresponds to an
image pixel. Let 2A be a set of vectors used
to define a neighbourhood structure on the set of
nodes, i.e. a graph: two nodes t and t are con-
nected by an edge if =t t a A . To avoid dou-
ble edges we require = 0A A (we use unary
potentials as well). The resulting graph is obvi-
ously translational invariant and the elements of
a A define subsets aE E of equivalent edges,
where = ( , ) ae t t E if =t t a . A simple exam-
ple is shown in Fig. 1.
Given a class of composite shapes, we denote
the set of its parts enlarged by an extra element for
the background by K. A shape-part labelling
:y D K is a mapping, that assigns either a
shape-part label or the background label ty K to
each node t D . A function :au K K is de-
fined for each difference vector a A . Its values
( , )au k k are called Gibbs potentials. A corre-
sponding probability distribution is defined over
the set of shape-part labellings as follows:
1
( ) = exp ( , ),
( )
a
a t t
a Att E
p y u y y
Z u
(1)
where Z denotes the partition sum (we omit the
unary terms for better readability). This p.d. is
homogeneously parametrised – all edges in an
equivalence class aE have the same potentials.
Fig. 1. Left: example of a translational invariant graphical structure.
Equivalence classes of edges Ea are coloured by different
colours. The set A is represented by bold edges outgoing from
the central node. Right: Gibbs potentials for an edge from Ea.
Note that the parameters au of this model are
unique up to additive constants for a given p.d.
under fairly general assumptions − the only possi-
ble equivalent transformations (aka re-parametri-
sations) consist in adding a constant () =au
= () constau . This will be shown in appendix А.
Therefore, we assume from here that the Gibbs
potentials for each a A are normalised to sum to
zero:
,
( , ) = 0ak k
u k k
.
It is important to notice that a homogeneously
parametrised GRF on a finite domain 2D is
not necessarily homogeneous. A p.d. ( )p y for
labellings :y D K is called homogeneous if its
marginals for congruent subsets coincide. This
inhomogeneity, if present, usually reveals at the
domain boundary. It is easy to verify that the con-
verse is true at least for chains: a homogeneous
Markov model on a finite chain admits a homoge-
neous parametrisation.
The appearance model is assumed to be a
«simple» conditional independent model. The
probability to observe an image :x D C (C is
some colour space) given a shape-part labelling y is
( | ) = ( | ).t t
t D
p x y p x y
(2)
16 УСиМ, 2011, № 2
In the light of the current popularity of CRFs it
might well be asked, why we decided to favour a
GRF here. Both variants are identical with respect
to inference. Differences occur for learning. We
can imagine that shape-part labellings can be used
as latent variable layers for complex object seg-
mentation models. Recently, empirical risk mini-
misation learning has been suggested for struc-
tured SVM models with latent variables [13]. This
shows that the learning of graphical models with
latent variables is possible for both variants −
GRFs and CRFs. However, since we want to stu-
dy the expressive power of the model in its pure
form, we need a prior p.d. and moreover, we want
to be able to learn such models fully unsupervised,
which is possible for GRFs but not for CRFs.
The inference task
Informally, the inference task can be under-
stood as follows. Given an observation (i.e. an im-
age), it is necessary to assign values to all hidden
variables. We pose the segmentation task as a
Bayesian decision task. Let y be the true (but un-
known) segmentation and ( , )C y y be a loss func-
tion, that assigns a penalty for each possible deci-
sion y. The task of Bayesian decision is to mini-
mise the expected loss
( ; ) = ( | ) ( , ) .min
yy
R y x p y x C y y
(3)
We use the number of misclassified pixels
t
tt yyyyC 1, (4)
as the loss function. It leads to the max-marginal
decision
= ( = | ) .maxt t
k
y p y k x t D (5)
Hence, it is necessary to calculate the marginal
posterior probabilities for each node t D and
label k K . Currently this task is infeasible for
GRFs. Several approximation techniques based e.g.
on belief propagation or variational methods have
been suggested for this task (see e.g. [12] for an
overview). Unfortunately none of them guarantees
convergence to the exact values of the sought-
after marginal probabilities. To our knowledge,
the only scheme which does it is sampling, which
is however known to be slow [3].
Estimation of Gibbs potentials
The learning task comprises to estimate the un-
known model parameters given a learning sample.
We assume that the latter is a random realisation
of i.i.d. random variables, so that the Maximum
Likelihood estimator is applicable.
The following situations are distinguished de-
pending on the format of the learning data. If the
elements of the sample have the format ( , )x y then
the learning is called supervised. If, instead, they
consist of images only then the learning is called
fully unsupervised. To cope with variants in-bet-
ween as well, i.e. partial labellings Vy , we con-
sider the elements of the training sample to be
events of the type |= ( , ) = {( , ) | = }V V Vx y y x y yB .
We start with the learning of unknown poten-
tials u. For simplicity we consider the case when
only one event B is given as the training sample.
According to the Maximum Likelihood principle,
the task is
( ; ) = ( ) ( | ) .max
uy
p u p y p x y
B
B (6)
Taking the logarithm and substituting the
model (1), (2) gives
( ) = log exp[ ( , )] ( | )
log( ( )) .max
a t t
y a Att Ea
u
L u u y y p x y
Z u
B (7)
It is easy to prove, that the derivative with re-
spect to the potentials is a difference of expecta-
tions of some random variable ( , ; )an k k y with
respect to the posterior and prior p.d.
( | ; )
( ; )
/ ( , ) = [ ( , ; )]
[ ( , ; )].
a p y u a
p y u a
L u k k n k k y
n k k y
BÅ
Å
(8)
The random variables ( , ; )an k k y are defined by
( , ; ) =
a
a
tt E
n k k y
1{ = , = }t ty k y k (9)
and represent co-occurrences for label pairs
( , )k k along the edges in aE for a labelling y.
Combining these random variables into a random
vector , the gradient of the log-likelihood can
be written as
( | ; ) ( ; )( ) = [ ] [ ].p y u p y uL u BE E (10)
УСиМ, 2011, № 2 17
The exact calculation of the expectations in (8)
is not feasible. Therefore, we suggest to use a sto-
chastic gradient ascent to maximise (7). The learn-
ing algorithm is an iteration of the following
steps:
1. Sample y and y according to the current
a-posteriori probability ( | ; )p y uB and a-priori pro-
bability ( ; )p y u respectively.
2. Compute ( , ; )an k k y and ( , ; )an k k y by (9)
for each a A , ,k k K .
3. Replace the expectations in (8) by their reali-
sations and calculate new potentials u.
For the sake of completeness we would like to
mention that the learning of the appearance mod-
els ( | )p c k can be done in a very similar manner.
It is even simpler from the computational point of
view because the normalising constant Z does not
depend on these probabilities. Therefore it is not
necessary to sample labellings according to the a-
priori probability distribution ( )p y . Only a-poste-
riori sampled labellings are needed to perform the
corresponding stochastic gradient step.
Estimation of the interaction structure
A very important question not discussed so far
is the optimal choice of the neighbourhood struc-
ture A. Unfortunately, no well founded answer to
this question is known at present. One option is to
use an abundant set of interaction edges, e.g. to
assume that the set A consists of all vectors
2
1 2= | | , | |A a a d a d within a certain
range. Despite of the computational complexity
this would lead to models with high VC dimen-
sion and possibly − as a result − to weak discrimi-
nation. It is therefore important to investigate the
possibility to identify the neighbourhood structure
A from a given training sample. A possible variant
of a corresponding formal task reads as follows.
Given a training sample the task is to find the best
neighbourhood structure A of given size | |=A m
according to the Maximum Likelihood principle
,( , ) maxu AA A
L u A . This task is however not fea-
sible – an exhaustive search over all possible sets
A would be computationally prohibitive, and,
moreover, the likelihood can be calculated only
approximatively. Therefore we rely on a greedy
approximation which we will consider in two
variants − one of them successively includes new
elements into the neighbourhood structure start-
ing from = {0}A and the other successively re-
moves elements from this structure starting from
2
1 2= | | , | |A a a d a d .
For the first variant we use a greedy search for
the interaction edges suggested by Zalesny and
Gimel'farb in the context of texture modelling [14,
5]. Starting from the set = {0}A , i.e. a model with
unary potentials, new edges are iteratively chosen
and included into A as follows. First, the optimal
set of potentials *
A Au U is determined for the
current set A as described in the previous subsec-
tion. Here A denotes the subspace of potentials
on the edges in A (we may assume that the Gibbs
potentials are zero on all other edges). If a bigger
neighbourhood A is considered, then clearly, the
gradient of the (log) likelihood with respect to Au
in the point *
Au will be orthogonal to the subspace
A. The proposal is to include the vector
\a A A with the largest gradient component
2
\
,
= [ ( , ; , ) ( , ; )]a A A a a
k k
a argmax n k k u n k k u
B .(11)
Optionally the Kullback–Leibler divergence can
be used instead of the Euclidean distance.
The second variant of structure estimation pro-
ceeds in opposite order. Starting with the neigh-
bourhood structure 2
1 2= | | , | |A a a d a d ,
elements of A are successively removed. The aim
is to remove in each step the element with the
smallest impact on the maximal likelihood
\
\
( ) ( ) .max max minA A a
a Au uA A a
L u L u
(12)
It is impossible to estimate this expression in
the point * = ( )A u AA
u argmax L u using the gradient
of the likelihood (like in the first variant) because
of *( ) = 0AL u . It is nevertheless possible to esti-
mate this expression based on *
Au . For the sake of
simplicity we show this for the situation of super-
18 УСиМ, 2011, № 2
vised learning. The likelihood maximisation with
respect to the Gibbs potentials reads
{< , > log exp < ( ), >}max
A
A A A A
u y
u y u (13)
for this case. Here we have used the following no-
tations. The set of all Gibbs potentials (.,.)au ,
a A is considered as a vector Au . A realisation
of the random vector A (see (10)) is denoted by
φ ( )A y . Finally, ψA denotes the corresponding
vector of statistics resulting from the training
sample. Designating log ( )AZ u by ( )AH u , the
expression in (13) is nothing but the Fenchel con-
jugate *(ψ )AH . It is known that for exponential
families the latter can be written as
* (ψ ) = inf{ ( ) log ( ) | [ ] =
ψ , }
A p A
y
A
H p y p y
p
E
E
(14)
(see e.g. [12, 1]), where we denoted the expecta-
tion w.r.t. a probability distribution p by pE and
the set of all probability distributions on labellings
y by . This means to find the p.d. with maximal
entropy among all distributions having expecta-
tion ψA of the random vector A .
Removing an element a from the neighbour-
hood structure A can be equivalently expressed by
the linear constraints 0au . Considering the task
(13) with these additional constraints, it can be
shown by the use of Fenchel duality (see e.g. [1])
that the corresponding conjugate function *(ψ )AH
can be written as
* (ψ ) = { ( ) log ( ) | [ ] =inf inf
ψ , },
a
A p A
z p y
A a
H p y p y
z p
E
E
(15)
where az is an arbitrary vector of the subspace a.
Therefore, the difference in (12) is equal to
* * * * *(ψ ) (ψ ) = (ψ ) (ψ )A A A A aH H H H z and
can be estimated by the gradient of *H in ψA .
The latter gradient is nothing but the vector of
Gibbs potentials *
Au .
The convex, lower semi-continuous function
*(ψ )AH is not differentiable in general. Therefore
its sub-differential may consist of more than one
subgradient Au . This corresponds to the non-
uniqueness of the Gibbs potentials. We have how-
ever shown that the Gibbs potentials are unique up
to additive constants for the model class consid-
ered in this paper (see Appendix А).
Summarising, the difference in (12) can be es-
timated by au , that leads to the following gre-
edy removal strategy for elements of the neighbour-
hood structure A. Given a current neighbourhood
structure A, estimate the optimal Gibbs potentials
*
Au and remove the element a A with the small-
est value of au .
3. Experiments
Modelling spatial relations between segments
The first experiment investigates the ability of
the model (1), (2) to reflect spatial relations be-
tween segments, i.e. scene parts, which are too
large to capture their shape by a neighbourhood
structure of reasonable size. We used the three
images shown in the first row of Fig. 2 as training
examples. Each scene should be segmented into
three segments: = { , , }K sky trees grass . The appear-
ance models ( | )p c k for the segments were as-
sumed as mixtures of multivariate Gaussians (four
per segment). A model with «full» neighbourhood
structure − all vectors 2
1 2| | , | |a a d a d
with = 20d was used in this experiment. A «sim-
ple» but anisotropic Potts model on the 8-
neighbourhood was chosen as a baseline for com-
parison.
Semi-supervised learning was applied by fixing
the segment labels in the rectangular areas shown
by rectangles during learning. Both the a-priori
models (the potentials and the direction specific
Potts parameters for the baseline model) and the
appearance models (mixture weights, mean values
and covariance matrices) were learned.
The difference of the models can be clearly
seen by observing labellings generated a-priori by
the learned models, i.e. without input images.
Some of them are shown in the second and third
row for the model with complex neighbourhood
structure and the baseline model respectively. It
УСиМ, 2011, № 2 19
can be seen, that the spatial relations between
segments (like e.g. «above», «below» etc.) were
correctly captured by the complex model, whereas
it is clearly not the case for the Potts model.
Fig. 2. Modelling spatial relations between segments. The first row
shows input images and regions with fixed segmentation.
The middle and bottom row show labellings generated by
the learned a-priori models (segment labels are coded by
colour): the images in the middle row were generated by the
model with full neighbourhood, whereas the images in the
bottom row were generated by the baseline model
The consequences can be clearly seen from the
following experiment. We fixed the prior models
obtained in the previous experiment (semi-super-
vised learning) for both variants (the complex
prior and the Potts prior) and learned the parame-
ters of the Gaussian mixtures completely unsuper-
vised. Fig. 3 shows labellings (i.e. segmentations)
sampled at the end of the learning process by the
corresponding a-posteriori probability distribu-
tions (obtained with the learned appearances) for
the complex a-priori model and the Potts a-priori
model in the first and the second row respectively.
The advantages of the complex model are clearly
seen. These results can be explained as follows.
There are twelve Gaussians in total to interpret the
given images. For the learning process it is «hard
to decide» which of the Gaussians belongs to
which segment. Using the compactness assump-
tion only is obviously not enough to separate
segments from each other. If the complex model is
used instead, the learning process starts to gener-
ate labellings according to the a-priori probability
distribution, i.e. labellings which reflect the cor-
rect spatial relations between the segments. This
forces the unsupervised learning of the appearance
models into the right direction.
Fig. 3. Segmentation results obtained after fully unsupervised
learning of the appearance part of the model. Upper row −
model with full neighbourhood, bottom row − baseline model
Modelling simple shapes
This group of experiments demonstrates the
ability of the model to represent simple shapes as
well as to perform shape driven segmentation.
This experiment is prototypical e.g. for a class of
image recognition tasks in biomedical research.
Fig. 4 (upper left) shows a microscope image of
liver cells with stained DNA. Thus, only the cell
nuclei are visible. The task is to segment the im-
age into two segments − «cells» (which have
nearly circular shape) and «background» (the rest
20 УСиМ, 2011, № 2
including artefacts). Hence, two labels are used.
The «full» neighbourhood structure with d = 12
was used (it approximately corresponds to the
mean cell diameter). Again, we used a baseline
model for comparison − a GRF with 4-neighbour-
hood and free potentials. The appearances for
grey-values were assumed to be Gaussian mix-
tures (two per segment) in both models.
Fig. 4. Modelling and segmentation of simple shapes. Upper left −
input image, upper right − a labelling generated a-priori by the
learned complex model. Final segmentations are shown in the
bottom row: left − baseline model, right − complex model
First, semi-supervised learning was performed
(like in the previous experiment with trees) in or-
der to learn the prior distributions for labellings as
well as the appearances for both, the complex and
the baseline model. A labelling generated a-priori
by the learned complex model is shown in Fig. 4
(upper right). The final segmentations according
to the max-marginal decision (see equation (5))
are shown in the bottom row of the same figure.
The differences are clearly seen. The shape prior
captured in the complex model led to the correct
segmentation − the artefacts were segmented as
background, whereas the baseline model produces
a wrong segmentation because neither the appear-
ance nor a simple «compactness» assumption nor
even their combination allow to differentiate be-
tween cells and artefacts.
A structure estimation for simple shapes
In order to investigate the structure identifiabil-
ity of shape models we have used an artificial
model which generates simple «blobs». The
neighbourhood structure consists of 8 elements.
The group of the first four elements with coordi-
nates (0,1), (0,–1), (1,1), and (–1,1) describes a
standard 8-neighbourhood. The remaining four
vectors are scaled versions of the first (scale factor
5). The Gibbs potentials on the short vectors are
supermodular and express the correlation of the
labels on the edges of this type
if = ,
( , ) =
else.
k k
u k k
(16)
The Gibbs potentials on the long edges con-
sist of an submodular and a modular part
( , )u k k 1 2= ( , ) ( , )u k k u k k , where the submo-
dular part 1u is just the negative version of the
potentials on the short edges and expresses an
anti-correlation of the labels on these edges. The
modular part
2
if = = 0,
( , ) = if = = 1,
0 else ,
k k
u k k k k
(17)
is used to influence the density of the blobs. A la-
belling (fragment) sampled by this model
( = 0.35 , = 0.5 ) is shown in Fig. 5. Both heu-
ristic approaches for structure estimation dis-
cussed in the previous section where applied for
the supervised version, i.e. using a labelling gen-
erated by the known model as a learning sample.
Fig. 5. Shape estimation for a simple shape model. Left − labelling
generated by the known model, right − histogram of the es-
timated structures
УСиМ, 2011, № 2 21
The first approach −
iterative growth of the
structure − was run 40
times. The estimated
structures resulting
from these runs are
shown in Fig. 5 as a
grey-coded histogram.
As a stochastic gradi-
ent ascend is used for
the learning of the po-
tentials, each run may
result in a different
structure. The histo-
gram shows however,
that the structure esti-
mation is essentially
correct. All trials of
the second approach −
iterative shrinking of
the neighbourhood
structure − resulted much to our surprise in one
and the same estimated structure − the correct one.
We conclude from these experiments that the
neighbourhood structure of a shape model is iden-
tifiable (at least in principle) from labellings gen-
erated by the model.
Modelling composite shapes
The previous experiments have shown that
second order GRFs can model both, spatial rela-
tions between segments and simple shapes. Now
we are going to demonstrate the capability of the
model to capture both properties simultaneously.
This opens the possibility to represent complex
shapes as spatial compositions of simpler parts.
To demonstrate this, we use an artificial example
shown in Fig. 6 (upper left). It was produced ma-
nually and corrupted by Gaussian noise. Accord-
ingly, the model was defined as follows. The label
set K consists of seven labels, each one corres-
ponding to a part of the modelled shape (as well
as one for the background). The appearance mod-
els kcp |( ) for the labels are Gaussians with
known parameters. In this experiment we applied
the growth variant for the estimation of the inter-
action structure as described in section 2.
Fig. 6 (upper row, center) shows a labelling
generated by the learned prior model. It is clearly
seen that both, spatial relations between object
parts and part shapes are captured correctly.
The bottom row of Fig. 6 displays labellings
generated during the process of structure learn-
ing at time moments, when the interaction struc-
ture learned so far was not yet capable to cap-
ture all needed properties. As it can be seen, the
model was able to learn spatial relations be-
tween the segments more or less correctly even
for a small numbers of edges (5 edges − bottom
left). More relations are learned as the number
of edges grows (bottom middle and right). Fi-
nally, 20 difference vectors were necessary to
capture all relations (out of 1200 possible for
the maximal range of d = 24).
Fig. 6 (upper right) shows the estimated neigh-
bourhood structure. The endpoints of all edges
from central pixel are marked by colours (the im-
age is magnified for better visibility). A certain
structure can be seen in this image. The 8-neigh-
bourhood edges (black) reflect compactness and
adjacency relations of the object parts. The lear-
ned potentials on these edges represent strong la-
bel co-occurrences. Most of the other vectors are
Fig. 6. Composite shape modelling. Upper row from left: input image, labelling generated a-priory by the
learned model, estimated interaction structure. Bottom row: labellings generated by models during
learning
22 УСиМ, 2011, № 2
responsible for the shapes of
the parts. The potentials on
the red edges express char-
acteristic breadths, and the
potentials on the green edges
− characteristic lengths of
the parts. The potentials on
these edges mainly represent
anti-correlations, forcing label
values to change along cer-
tain directions. The blue
pixels in the figure reflect
relative positions of object
parts.
Composite shape recog-
nition
The final experiment demonstrates possibilities
to combine composite shape models. The aim is to
obtain a joint model which can be used for detec-
tion, segmentation and classification of objects in
scenes populated by instances of different shape
classes like e.g. the example in Fig. 7. We con-
clude from the previous experiments, that the ap-
pearance model can be re-learned in a fully unsu-
pervised way if the prior shape model is discrimi-
native. Hence, the most important question is,
how to combine the prior models. We propose a
method for this that is based on the following ob-
servation. It is not necessary to have an example
image (or an example segmentation) in order to
learn the model if the aposteriori statistics
( | , )( , ) = [ ( , )]a p y u ak k k k E B (18)
for all difference vectors a A and label pairs
( , )k k are known − the gradient of the likelihood
(equation (8)) reads then
( ; )/ ( , ) = ( , ) [ ( , ; )].a a p y u aL u k k k k n k k y E (19)
Let us consider this in a bit more detail for a
simple example − just two shapes like in Fig. 7.
Let us assume that the both models are learned,
i.e. both the potentials and statistics are known for
both models and for all difference vectors a. Ob-
viously, it is not easy to combine the potentials of
both shape models in order to obtain new ones for
a model that generates such collages. It is however
very easy to estimate the needed aposteriori statis-
tics for the joint model given the aposteriori statis-
tics for both shape models. Summarizing, the
scheme to obtain the parameters of the joint model
consists of two stages:
1. compute the aposteriori statistics for the joint
model and
2. learn the model according to (19) so that it
reproduces this statistics.
As the second stage is standard, we consider
the first one in more detail. Let us denote the label
sets corresponding to the shape parts by K1 and K2
for the first and for the second shape type respec-
tively. Let b1 and b2 be the background labels in
the corresponding shape models and b be the
background label in the joint one. Consequently,
the label set of the latter is 1 2K K b (see the
middle part of Fig. 8).
First of all we enlarge the label sets of each
shape model by labels that are not present in this
model but present in the joint one. Thereby the
statistics for the new introduced labels (for all dif-
ference vectors a) are set to zero (see Fig. 8, left
and right). Informally said, these extended aposte-
riori statistics correspond to the situations that the
joint model is learned on examples, in which only
labels of one particular shape are present. The
aposteriori statistics for the joint model is then ob-
tained as a weighted mixture of the two extended
ones and an additional uniformly distributed com-
ponent. The latter is added in order to avoid zero
probabilities (which would lead to obvious techni-
Fig. 7. Shape segmentation and classification. Left − input image, right − segmentation (part-
labels are encoded by different grey values)
УСиМ, 2011, № 2 23
cal problems for the Gibbs Sampler). Summarising,
the aposteriori statistics of label pairs for a differ-
ence vector a of the joint model is:
1 1 1
1 0
1
1
2 2 2
2 0
2
2
1 1 1
1
2 2 2
2 0
0
( , ) if and ,
and = ,
= and ,
( , ) if and ,
( , ) and = ,
= and ,
( , )
( , ) if = and =
otherwise.
a
a
a
a
a
w k k w k K k K
k K k b
k b k K
w k k w k K k K
k k k K k b
k b k K
w b b
w b b w k b k b
w
(20)
with some weights 0 1 2w w w , where the indices
1 and 2 correspond to the particular shape model.
Given these statistics the joint model is learned
according to (19).
Fig. 8. Estimation of the aposteriori statistics for the joint model.
Left and right: extended statistics for shape models. Middle:
the joint model − statistics marked green and red are inherited
from the components. Others are set to a small constant
For the experiment in Fig. 7 two composite
shape models were learned separately. The test
image in Fig. 7 (left) is a collage of both shape
types. Note that the appearance of all shape parts
is identical, so they are not distinguishable with-
out the prior shape model. Fig. 7 (right) shows the
final segmentation. It is seen that all objects were
correctly segmented and recognised − although
both composite shape classes share some similarly
shaped parts − they were not confused.
4. Conclusions
The notation of shape is often understood as an
object property of global nature. We followed a
different direction by modelling shapes in a dis-
tributed way. We have demonstrated that the ex-
pressive power of second order GRFs allows to
model spatial relations of segments, simple shapes
and moreover, both aspects simultaneously i.e.
composite shapes which are understood as coherent
spatial compositions of simpler shape parts.
We have shown that complex shapes can be
recognized even in the situation, when their parts
are not distinguishable by appearance. However,
in our learning experiments we used training im-
ages, where they are distinguishable. Thus, an im-
portant question is, whether it is possible to per-
form unsupervised decomposition of complex
shapes into simpler parts during the learning
phase, i.e. to learn shape models from images,
where the desired spatial relations between shape
parts are not explicitly present. Another important
issue is the learning of the interaction structure. It
would be very useful to have a well grounded ap-
proach for this.
Acknowledgments
We would like to thank Georgy Gimel'farb
(University of Auckland) for the fruitful and in-
structive discussions which have been particularly
valuable with regard to structure learning.
One of us (B.F.) was supported by the Czech
Ministry of Education project 1M0567. D.S. was
supported by the Deutsche Forschungsgemeinschaft,
Grant FL307/2-1. Both authors were partially
supported by Grant NZL 08/006 of the Federal
Ministry of Education and Research of Germany
and the Royal Society of New Zealand.
1. Borwein J.M., Lewis A.S. Convex Analysis and Nonli-
near Optimization of CMS Books in Mathematics.
Springer, 2000.
2. Cremers D., Sochen N., Schnörr C. A multiphase dy-
namic labeling model for variational recognition-dri-
ven image segmentation // IJCV 66(1). – P. 67–81
(January 2006).
3. Flach B., Schlesinger D. Combining shape priors and
MRF-segmentation // da Vitoria Lobo et al., (ed)
S+SSPR 2008. – P. 177–186. Springer (2008).
4. Gimel’farb G.L. Texture modeling by multiple pair-
wise pixel interactions // IEEE Trans. Pattern Anal.
Mach. Intell. – P. 1110–1114 (1996).
5. Hinton G.E. Training products of experts by minimiz-
ing contrastive divergence. Neural Computation. –
14(8). – P. 1771–1800 (2002).
6. Hoffman D.D. Visual Intelligence: How We Create
What We See. W.W. Norton & Company (2000).
7. Associative Hierarchical CRFs for Object Class Image
Segmentation / L. Ladicky, C. Russell, P. Kohli, P.H. Torr
// Proc. IEEE 12. Intern. Conf. on Computer Vision (2009).
8. Liu H., Liu W., Latecki L.J. Convex shape decomposi-
tion // CVPR. – P. 97–104 (2010).
24 УСиМ, 2011, № 2
9. Ramalingam, S., Kohli, P., Alahari, K., Torr, P. Exact
inference in multi-label CRFs with higher order
cliques // CVPR. – 2008. – P. 1–8 (2008).
10. Roth S., Black M.J. Fields of Experts // Intern. J. of
Computer Vision. – 82(2). – P. 205–229 (2009).
11. Sokal A.D. Monte Carlo Methods in Statistical Me-
chanics: Foundations and new Algorithms. Lectures
notes (1989).
12. Wainwright M.J., Jordan M.I. Graphical models, expo-
nential families, and variational inference // Foundati-
ons and Trends in Machine Learning 1(1–2). – P. 1–305
(2008).
13. Yu C.N.J., Joachims T. Learning Structural SVMs with
Latent Variables // Intern. Conf. on Machine Learning
(ICML) (2009).
14. Zalesny A., Gool L.V. Multiview Texture Models // Proc.
of the IEEE Conf. on Computer Vision and Pattern
Recognition. – 2001. – P. 615–622. IEEE Computer
Society (2001).
Appendix А
Equivalent transforms for homogeneously paramet-
rised GRFs
As we have already seen, the probability distribution (1)
for shape part labellings y can be equivalently written as
0 0( ) exp ( ) ( ; )
( , ) ( , ; ) ,
k
a a
a A kk
p y u k n k y
u k k n k k y
(21)
where = \{0}A A . We call two parametrisations u, u
equivalent, if the corresponding probability distributions are
identical. It follows that the difference =v u u of equiva-
lent potentials fulfils
0 0( ) = ( ) ( ; )
( , ) ( , ; ) = const.
k
a a
a A kk
V y v k n k y
v k k n k k y
(22)
We will conclude that all functions
av are constant under
fairly general conditions. We perform the proof in two steps.
First we show that the pairwise functions
av , = 0a are
modular and can be written as a sum of unary functions. In a
second step we will conclude the claimed statement under
fairly general conditions for the graph (D, E).
Let us consider an arbitrary non-zero vector a A of the
neighbourhood structure and an arbitrary edge ( ) att E . Let
1 2,k k be two arbitrary labels in the node t and
1 2,k k be two
arbitrary labels in the node t . Let
11 12 21 22, , ,y y y y be four
labellings with respective values
1 1( , ),k k
1 2( , ),k k
2 1( , ),k k
2 2( , )k k on the nodes ,t t such that they coincide on all other
vertices. We consider the equation
11 22 12 21( ) ( ) ( ) ( ) = 0.V y V y V y V y (23)
It is easy to see that this equation reduces to
1 1 2 2
1 2 2 1
( , ) ( , )
( , ) ( , ) = 0.
a a
a a
v k k v k k
v k k v k k
(24)
This holds for arbitrary four-tuples of labels and it fol-
lows that the function
av is modular and can be written as a
sum of two unary functions
( , ) = ( ) ( ).a a av k k v k v k (25)
These arguments can be applied for every element
a A . Consequently, ( )V y can be written as
0 0( ) = ( ) ( ; )
[ ( ) ( ; ) ( ) ( ; )],
k
a a a a
a A k
V y v k n k y
v k n k y v k n k y
(26)
where we have omitted the tildes. Note that
( ; ) = ( , ; )a ak
n k y n k k y denotes the number of vertices with
an outgoing edge of type a for which the labelling y has the
value k. Therefore in general
0 ( ; ) = ( ; )an k y n k y .
Let us consider an arbitrary vertex t and two labellings
yy ~, which coincide on all vertices but t. It follows from
( ) ( ) = 0V y V y that
0 ( ) ( ) ( ) = const.a a
a A a A
t a D t a D
v k v k v k
(27)
We assign a vector ( )z t with dimension 2 | | 1A to
every vertex t D with components
0
1 ift ,
( ) = 1, ( ) =
0 else
1 ift ,
and ( ) =
0 else.
a
a
a D
z t z t
a D
z t
(28)
If the domain D contains a subset of nodes t such that
their vectors ( )z t span the whole vector space of dimension
2 | | 1A , then, clearly, considering equation (27) for each of
them, we obtain
0 ( ) = const.v k (29)
( ) = const.av k (30)
( ) = const.av k
(31)
for all a A .
© B. Flach, Center for Machine Perception, Czech Technical
University, Technická 2, 166 27 Prague 6, Czech Republic,
D. Schlesinger, Institute for Artificial Intelligence, Dresden
University of Technology, Germany, 2011
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-82920 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | English |
| last_indexed | 2025-12-07T17:30:06Z |
| publishDate | 2011 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Flach, B. Schlesinger, D. 2015-06-11T20:01:50Z 2015-06-11T20:01:50Z 2011 Modelling Distributed Priors by Gibbs Random Fields of Second Order / B. Flach, D. Schlesinger // Управляющие системы и машины. — 2011. — № 2. — С. 14-24. — Бібліогр.: 14 назв. — англ. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82920 004.93’1 Проведен анализ потенциалов гиббсовских случайных полей для моделирования априорных вероятностных характеристик формы объекта. Показано, что при помощи этих полей второго порядка можно описывать как простые формы, так и пространственные отношения между ними, что позволяет распознавать сложные формы как сочетания более простых. The potentials of Gibbs random fields are analyzed for the shape prior modeling. It is shown that the expressive power of second order GRFs is already sufficient to express simple shapes and spatial relations between them simultaneously. This allows to recognize complex shapes as spatial compositions of simple parts. Проведено аналіз потенціалів гібсовських випадкових полів для моделювання апріорних ймовірнісних характеристик форми об’єкту. Показано, що завдяки цим полям другого порядку можна описувати як прості форми, так і просторові відношення між ними, що дозволяє розпізнавати складні форми як композицію більш простих. We would like to thank Georgy Gimel'farb (University of Auckland) for the fruitful and instructive discussions which have been particularly valuable with regard to structure learning. One of us (B.F.) was supported by the Czech Ministry of Education project 1M0567. D.S. was supported by the Deutsche Forschungsgemeinschaft, Grant FL307/2-1. Both authors were partially supported by Grant NZL 08/006 of the Federal Ministry of Education and Research of Germany and the Royal Society of New Zealand. en Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Оптимизационные задачи структурного распознавания образов Modelling Distributed Priors by Gibbs Random Fields of Second Order Моделирование априорных вероятностных характеристик формы объектов при помощи гиббсовских случайных полей второго порядка Моделювання апріорних ймовірнісних характеристик форми об’єктів за допомогою гібсовських випадкових полів другого порядку Article published earlier |
| spellingShingle | Modelling Distributed Priors by Gibbs Random Fields of Second Order Flach, B. Schlesinger, D. Оптимизационные задачи структурного распознавания образов |
| title | Modelling Distributed Priors by Gibbs Random Fields of Second Order |
| title_alt | Моделирование априорных вероятностных характеристик формы объектов при помощи гиббсовских случайных полей второго порядка Моделювання апріорних ймовірнісних характеристик форми об’єктів за допомогою гібсовських випадкових полів другого порядку |
| title_full | Modelling Distributed Priors by Gibbs Random Fields of Second Order |
| title_fullStr | Modelling Distributed Priors by Gibbs Random Fields of Second Order |
| title_full_unstemmed | Modelling Distributed Priors by Gibbs Random Fields of Second Order |
| title_short | Modelling Distributed Priors by Gibbs Random Fields of Second Order |
| title_sort | modelling distributed priors by gibbs random fields of second order |
| topic | Оптимизационные задачи структурного распознавания образов |
| topic_facet | Оптимизационные задачи структурного распознавания образов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/82920 |
| work_keys_str_mv | AT flachb modellingdistributedpriorsbygibbsrandomfieldsofsecondorder AT schlesingerd modellingdistributedpriorsbygibbsrandomfieldsofsecondorder AT flachb modelirovanieapriornyhveroâtnostnyhharakteristikformyobʺektovpripomoŝigibbsovskihslučainyhpoleivtorogoporâdka AT schlesingerd modelirovanieapriornyhveroâtnostnyhharakteristikformyobʺektovpripomoŝigibbsovskihslučainyhpoleivtorogoporâdka AT flachb modelûvannâapríornihimovírnísnihharakteristikformiobêktívzadopomogoûgíbsovsʹkihvipadkovihpolívdrugogoporâdku AT schlesingerd modelûvannâapríornihimovírnísnihharakteristikformiobêktívzadopomogoûgíbsovsʹkihvipadkovihpolívdrugogoporâdku |