13.3.10 Discrete Relaxation Methods

Chapter Contents (Back)
Object Recognition. Constraint Satisfaction. Matching, Relaxation. Relaxation, Discrete.

Davis, L.S.,
Hierarchical Relaxation for Shape Analysis,
PRIP78(275-279). Discrete relaxation applied to a multilevel grammar specification of shapes. Apply the relaxation at all levels and eliminate assignments at upper or lower levels when a subpart or superpart is removed.
See also Hierarchical Relaxation for Waveform Parsing. BibRef 7800

Kitchen, L.[Leslie], Rosenfeld, A.[Azriel],
Scene Analysis Using Region-Based Constraint Filtering,
PR(17), No. 2, 1984, pp. 189-203.
Elsevier DOI BibRef 8400
Earlier: DARPA82(230-242). BibRef
And: UMD-CS TR-1150, DAAG-53-76C-0138, February 1982. Discrete relaxation (which is important for parallel representations (implementations)) applied to a graph matching problem. Desire to have a complete graph, but this is not practical due to increased cost (especially for hardware implementation), therefore use sparse graph - proximity and very large regions are used. Give initial interpretations, filter on unary constraints (intrinsic properties). Generate all pairs on the graph arcs and filter these (use these to filter the node labels). BibRef

Jacobus, C.J., Chien, R., and Selander, J.,
Motion Detection and Analysis of Matching Graphs of Intermediate Level Primitives,
PAMI(2), No. 6, November 1980, pp. 495-510. Similar to Harlow, Baker, Underwood, Dudani(
See also Aircraft Identification by Moment Invariants. ), et al. Using features tends to reduce possibilities of matching elements (unique features occur), and generally they can be consistently located. This matching is done at the 2-D level, 3-D is derived later, but the features can be used in the 3-D descriptions process. Lines, vertices, and regions are encoded in a graph structure which is used in the matching. Use highly descriptive unique points to seed the match and have a set of parallel processes at each seed grow out and compete or merge with others - apply standard relaxation (e.g., Waltz:
See also Understanding Line Drawings of Scenes with Shadows. ) filtering to propagate out. The matching method depends very much on the descriptive method for its power. BibRef 8011

Blake, A.,
Relaxation Labeling: The Principle of 'Least Disturbance',
PRL(1), 1983, pp. 385-391. BibRef 8300

Blake, A.,
The Least Disturbance Principle amd Weak Constraints,
PRL(1), 1983, pp. 393-399. BibRef 8300

Radig, B.M.[Bernd M.],
Image Sequence Analysis Using Relational Structures,
PR(17), No. 1, 1984, pp. 161-167.
Elsevier DOI BibRef 8400
Hierarchical Symbolic Description and Matching of Time Varying Images,
ICPR82(1007-1010). Generate various descriptions using maximal cliques and match these cliques at the higher levels (cliques to cliques). Use relational structures for matching. Find cliques and use to find similar cliques in other image. Clique: completely connected subset. Group into objects (almost always cliques) and detect similar cliques in the image. A long formal description of relational structures, but little on actual examples and results. BibRef

Radig, B.M., Kraasch, R., Zach, W.,
Matching Symbolic Descriptions for 3D Reconstruction of Simple Moving Objects,
ICPR80(1081-1084). BibRef 8000

Gu, J., Wang, W., and Henderson, T.C.,
A Parallel Architecture for Discrete Relaxation Algorithm,
PAMI(9), No. 6, November 1987, pp. 816-831. BibRef 8711

Ankenbrandt, C.A., Buckles, B.P., Petry, F.E.,
Scene Recognition Using Genetic Algorithms with Semantic Nets,
PRL(11), 1990, pp. 285-293. BibRef 9000

Boyce, J.F., Feng, J., Haddow, E.R.,
Relaxation Labelling and the Entropy of Neighborhood Information,
PRL(6), 1987, pp. 225-234. BibRef 8700

Koo, J.Y., Park, K.H., Kim, M.,
Improving the Labeling Accuracy by a New Probabilistic Relaxation Labeling,
PRL(3), 1985, pp. 399-402. BibRef 8500

Kirousis, L.M.[Lefteris M.],
Fast parallel constraint satisfaction,
AI(64), No. 1, October 1993, pp. 147-160.
Elsevier DOI Motivated by line labeling systems. BibRef 9310

Cruz-Barbosa, R.[Raul], Vellido, A.[Alfredo],
Semi-supervised geodesic Generative Topographic Mapping,
PRL(31), No. 3, 1 February 2010, pp. 202-209.
Elsevier DOI 1001
Semi-supervised learning; Geodesic distance; Generative Topographic Mapping; Label propagation BibRef

Cruz-Barbosa, R.[Raśl], Bautista-Villavicencio, D.[David], Vellido, A.[Alfredo],
On the Computation of the Geodesic Distance with an Application to Dimensionality Reduction in a Neuro-Oncology Problem,
Springer DOI 1111

Bao, B.K.[Bing-Kun], Ni, B.B.[Bing-Bing], Mu, Y.D.[Ya-Dong], Yan, S.C.[Shui-Cheng],
Efficient region-aware large graph construction towards scalable multi-label propagation,
PR(44), No. 3, March 2011, pp. 598-606.
Elsevier DOI 1011
Region-aware; Large scale; Multi-label propagation BibRef

Bao, B.K., Li, T., Yan, S.C.,
Hidden-Concept Driven Multilabel Image Annotation and Label Ranking,
MultMed(14), No. 1, January 2012, pp. 199-210.

Bai, L.[Liang], Wang, J.B.[Jun-Bin], Liang, J.[Jiye], Du, H.Y.[Hang-Yuan],
New label propagation algorithm with pairwise constraints,
PR(106), 2020, pp. 107411.
Elsevier DOI 2006
Cluster analysis, Semi-supervised clustering, Label propagation algorithm, Pairwise constraint, Spectral clustering BibRef

Olsson, C.[Carl], Gerosa, D.[Daniele], Carlsson, M.[Marcus],
Relaxations for Non-Separable Cardinality/Rank Penalties,
Computational modeling, Robustness, Optimization, Standards BibRef

Gong, R.[Rui], Gimel'farb, G.L.[Georgy L.], Nicolescu, R.[Radu], Delmas, P.[Patrice],
Towards structural analysis of solution spaces for ill-posed discrete 1D optimisation problems,
Earlier: A2, A1, A3, A4:
Concurrent propagation for solving ill-posed problems of global discrete optimisation,
WWW Link. 1302
optimisation BibRef

Zheng, H.X.[Hai-Xia], Ip, H.H.S.[Horace H. S.], Tao, L.[Liang],
Adjacency Matrix Construction Using Sparse Coding for Label Propagation,
Global12(III: 315-323).
Springer DOI 1210

Kang, F.[Feng], Jin, R.[Rong], Sukthankar, R.[Rahul],
Correlated Label Propagation with Application to Multi-label Learning,
CVPR06(II: 1719-1726).

Cucchiara, R., Lamma, E., Mello, P., Milano, M., Piccardi, M.,
3D object recognition by VC-graphs and interactive constraint satisfaction,

Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in
Discrete Relaxation Theoretical Issues .

Last update:Jun 17, 2024 at 21:38:11