See also Graph Matching Theoretical Issues.

*Southwell, R.V.*,

**Stress-Calculation if Frameworks by the Method of
Systematic Relaxation of Constraints, I and II**,

*RoyalE(151)*, No. 872, 1935, pp. 56-95.
The beginning of relaxation.
BibRef
**3500**

*Kitchen, L.*, and
*Rosenfeld, A.*,

**Discrete Relaxation for Matching Relational Structures**,

*SMC(9)*, No. 12, December 1979, pp. 869-874.
BibRef
**7912**

*Yamamoto, H.[Hiromichi]*,

**A Method for Deriving Compatibility Coefficients for
Relaxation Operators**,

*CGIP(10)*, No. 3, July 1979, pp. 256-271.

Elsevier DOI
BibRef
**7907**

*Narayanan, K.A.*,

**A remark on the paper, 'A method of deriving compatibility coefficients
for relaxation operators'**,

*CGIP(14)*, No. 4, December 1980, pp. 391.

Elsevier DOI
**0501**

See also Method for Deriving Compatibility Coefficients for Relaxation Operators, A.
BibRef

*Henderson, T.C.*,

**A Note on Discrete Relaxation**,

*CVGIP(28)*, No. 3, December 1984, pp. 384-388.

Elsevier DOI Univ. Utah.
A discussion of discrete relaxation in terms of Boolean inequalities.
BibRef
**8412**

*Ullmann, J.R.*,

**Discrete Optimization by Relational Constraint Satisfaction**,

*PAMI(4)*, No. 5, September 1982, pp. 544-551.
Matching applied to random structures determine all vectors which
optimize a set of functions.

See also Parallel Recognition of Idealised Line Characters.
BibRef
**8209**

*Ullmann, J.R.*,

**Relational Matching**,

*PDA83*(147-170).
*Discrete Relaxation*. This introduces a constraint structure that enables a 3D model to
be matched directly to a 2D image, using discrete relaxation.
BibRef
**8300**

*Peleg, S.[Shmuel]*,

**Classification by Discrete Optimization**,

*CVGIP(25)*, No. 1, January 1984, pp. 122-130.

Elsevier DOI Discrete relaxation technique that can be applied to the standard problems.
BibRef
**8401**

*Peleg, S.*,
*Nathan, A.*,

**Classification and Tracking Using Local Optimization**,

*SMC(13)*, 1983, pp. 1158-1162.
BibRef
**8300**

*Waltz, D.*,

**Understanding Line Drawings of Scenes with Shadows**,

*PsychCV75*(19-91).
BibRef
**7500**

And:

**Generating Semantic Descriptions from Drawings of Scenes
with Shadows**,

*Ph.D.*Thesis (EE), November 1972,
BibRef
*MIT AI-TR*-271.

WWW Link. This procedure is not described as a discrete relaxation method, but
that is the best way to understand the process. Junctions are given
all possible labels as determined by an exhaustive analysis of how
physical (three-dimensional, tri-hedral) junctions can appear in a
two-dimensional image. An iterative (relaxation) procedure eliminates
all incompatible labels (i.e. those that cannot exist because
corresponding labels do not exist on the adjacent vertex). He
described the procedure in a sequential manner (assign all labels to
one vertex, assign all labels to an adjacent vertex, check these two
for compatibility along the edge between them, and remove incompatible
labels from each, add a third vertex and check compatibilities, etc.),
but could be applied in parallel as a discrete relaxation procedure.
This work also shows the advantages of a complete analysis of
problems, since many can be reduced to simple cases with proper
analysis.
BibRef

*Freuder, E.C.*,

**Synthesizing Constraint Expressions**,

*CACM(21)*, No. 11, November 1978, pp. 958-966.
BibRef
**7811**

Earlier:
*MIT AI Memo*-370, July 1976.
This paper explored constraint satisfaction techniques as a means to limit the
need for complete combinatorial search techniques. The basic
constraint satisfaction technique is to start from a set of variables
(objects) with a set of unary constraints (or property values) on the
possible values (labels or assignments). Higher order constraints
(relations between objects) such as binary, 3-ary, etc. are either
given or synthesized from the lower order constraints. An n-ary
constraint specifies the final solution to the problem where all n
variables are labeled. The binary constraints are given by the
problems statement, but the others are synthesized by his algorithm.
This work draws heavily on the path consistency work in
Montanari (

See also Networks of Constraints: Fundamental Properties and Applications to Picture Processing. ) and the
arc-consistency work in Waltz(

See also Understanding Line Drawings of Scenes with Shadows. ).
BibRef

*Freuder, E.C.[Eugene C.]*,

**On the Knowledge Required to Label a Picture Graph**,

*AI(15)*, No. 1-2, November 1980, pp. 1-17.

Elsevier DOI
BibRef
**8011**

Earlier:

**Information Needed to Label a Scene**,

*AAAI-80*(18-20).
BibRef

*Freuder, E.C.[Eugene C.]*,

**Knowledge-Mediated Perception**,

*PR(12)*, 1980, pp. 219-236.
This reference is clearly inaccurate.
BibRef
**8000**

*Freuder, E.C.*,

**Structural Isomorphism of Picture Graphs**,

*PRAI-76*(248-256).
BibRef
**7600**

*Freuder, E.C.*,

**A Computer System for Visual Recognition Using Active Knowledge**,

*MIT AI-TR*-345, June 1976.
BibRef
**7606**
*Ph.D.*Thesis (EE).

WWW Link.
BibRef

And:
*IJCAI77*(671-677).
Decide where in the image to look
according to the current state of analysis.
BibRef

*Freuder, E.C.*,

**Active Knowledge**,

*MIT AI*Vision Flash 53, October 1973.
BibRef
**7310**

*Mackworth, A.K.*,
*Freuder, E.C.*,

**The Complexity of Some Polynomial Network Consistency Algorithms for
Constraint Satisfaction Problems**,

*AI(25)*, No. 1, January 1985, pp. 65-74.

Elsevier DOI
BibRef
**8501**

*Mackworth, A.K.*,
*Freuder, E.C.*,

**The complexity of constraint satisfaction revisited**,

*AI(59)*, No. 1-2, January 1993, pp. 57-62.

Elsevier DOI
BibRef
**9301**

*Freuder, E.C.*,

**Combining Backtrack and Relaxation: Extended Preclusion**,

*PRAI-78*(14-18).
BibRef
**7800**

*Freuder, E.C.[Eugene C.]*, and
*Wallace, R.J.[Richard J.]*,

**Partial constraint satisfaction**,

*AI(58)*, No. 1-3, 1992, pp. 21-70.

Elsevier DOI
BibRef
**9200**

*Nudel, B.[Bernard]*,

**Consistent-Labeling Problems and their Algorithms:
Expected-Complexities and Theory-Based Heuristics**,

*AI(21)*, No. 1-2, March 1983, pp. 135-178.

Elsevier DOI
BibRef
**8303**

*Nudel, B.*,

**Solving the General Consistent Labeling (or Constraint Satisfaction)
Problem: Two Algorithms and Their Expected Complexities**,

*AAAI-83*(292-296).
BibRef
**8300**

*Kumar, V.*,

**Algorithms for Constraint-Satisfaction Problems: A Survey**,

*AIMag(13)*, No. 1, Spring 1992, pp. 32-44.
*Survey, Relaxation*.
*Survey, Constraint Satisfaction*.
*Relaxation, Survey*.
*Constraint Satisfaction, Survey*.
BibRef
**9200**

*Mulder, J.A.*,
*Mackworth, A.K.*, and
*Havens, W.S.*,

**Knowledge Structuring and Constraint Satisfaction:
The Mapsee Approach**,

*PAMI(10)*, No. 6, November 1988, pp. 866-879.

IEEE DOI
*System: Mapsee*.
This paper discusses Mapsee-1, -2, and -3 and thus serves as the
primary reference for information about them. The conclusion is
that schema-based representations with hierarchical (arc)
consistency is best for a structured approach to
visual knowledge.
This set of systems illustrates the power of a schema based
representation and a hierarchical constraint satisfaction algorithm.
All three use a general segmentation of the image into regions and
lines segments. Constraints are given to each feature based directly
on its appearance. Mapsee-1 was a basic implementation of constraint
satisfaction (arc-consistency) with no hierarchy in the representation
and weak representations of constraints. Mapsee-2 added schemata as a
means to improve the descriptive capabilities with hierarchical
descriptions of the objects. This leads to a hierarchical arc
consistency algorithm. Mapsee-3 provided a uniform representation for
objects and relations between them (as schemata) and a more powerful
representation of alternatives in the arc consistency algorithm.

See also Discrimination Vision.

See also Consistency in a Network of Relations.
BibRef
**8811**

*Havens, W.S.*,
*Mackworth, A.K.*,

**Representing Knowledge of the Visual World**,

*Computer(16)*, No. 10, October 1983, pp. 90-96.
BibRef
**8310**

*Havens, W.S.*,

**A Procedural Model of Recognition for Machine Perception**,

*Ph.D.*Thesis, 1978.
BibRef
**7800**
*UBC*
BibRef

*Reiter, R.[Raymond]*, and
*Mackworth, A.K.[Alan K.]*,

**A Logical Framework for Depiction and Image Interpretation**,

*AI(41)*, No. 2, December 1989, pp. 125-156.

Elsevier DOI
BibRef
**8912**

And:

**The Logic of Depiction**,

*RBCV-TR*-87-18, June 1987, Toronto.
*System: Mapsee*. This proposes a theory to formalize domain knowledge and is
illustrated by specifying some general examples. Intended to
provide a framework to analyze Mapsee and understand
constraint satisfaction techniques.

See also Consistency in a Network of Relations.
BibRef

*Provan, G.M.*,

**An Analysis of Knowledge Representation Schemes for High Level Vision**,

*ECCV90*(537-541).

Springer DOI
BibRef
**9000**

Earlier:

**The Vision Constraint Recognition System: Analysing the Role of
Reasoning in High Level Vision**,

*CVWS87*(170-175).
*Recognize General Objects*. Using a truth maintenance system, find all occurrences of a given
figure in a scene. Scenes are composed of
overlapping rectangles.
BibRef

*Mulder, J.A.[Jan A]*,

**Discrimination Vision**,

*CVGIP(43)*, No. 3, September 1988, pp. 313-336.

Elsevier DOI
BibRef
**8809**

Earlier:

**Using Discrimination Graphs to Represent Visual Interpretations
that Are Hypothetical and Ambiguous**,

*IJCAI85*(905-907).
Extensions of Mackworth's work. Mapsee-3. How to deal with a large
number of ambiguous interpretations.
BibRef

*Mackworth, A.K.*,

**Consistency in a Network of Relations**,

*AI(8)*, No. 1, February 1977, pp. 99-118.

Elsevier DOI
BibRef
**7702**

Earlier:
*UBC*Technical Report, 75-3, 1975.
Constraint satisfaction problems are typically solved by
back-tracking search methods. This paper explores applying the
ideas from [

See also Understanding Line Drawings of Scenes with Shadows. ] to more general problems in AI. The basic
idea is to eliminate many inconsistent assignments before applying
the standard (e.g. tree-searching) techniques.
BibRef

*Mackworth, A.K.*,

**Use of Constraints for Interpreting Three-Dimensional Scenes**,

*Ph.D.*Thesis, Univ. of Sussex, 1974.
BibRef
**7400**

*Mackworth, A.K.*,

**Vision Research Strategy: Black Magic, Metaphors, Mechanisms,
Miniworlds, and Maps**,

*CVS78*(53-59).
BibRef
**7800**

*Mackworth, A.K.*,

**On Reading Sketchmaps**,

*IJCAI77*(598-606).
BibRef
**7700**

*Mackworth, A.K.*,

**On Seeing Things, Again**,

*IJCAI83*(1187-1191).
BibRef
**8300**

*Mackworth, A.K.[Alan K.]*,

**The logic of constraint satisfaction**,

*AI(58)*, No. 1-3, 1992, pp. 3-20.

Elsevier DOI
BibRef
**9200**

*Hancock, E.R.*, and
*Kittler, J.V.*,

**Discrete Relaxation**,

*PR(23)*, No. 7, 1990, pp. 711-733.

Elsevier DOI
BibRef
**9000**

And:

**A Bayesian Interpretation for the Hopfield Network**,

*ICNN93*(341-346).
Hopfield network model.
BibRef

*Kasif, S.[Simon]*,

**On the Parallel Complexity of Discrete Relaxation in
Constraint Satisfaction Networks**,

*AI(45)*, No. 3, October 1990, pp. 275-286.

Elsevier DOI
BibRef
**9010**

*Montanari, U.[Ugo]*,
*Rossi, F.[Francesca]*,

**Constraint Relaxation May Be Perfect**,

*AI(48)*, No. 2, March 1991, pp. 143-170.

Elsevier DOI
BibRef
**9103**

*Montanari, U.[Ugo]*,

**Heuristically guided search and chromosome matching**,

*AI(1)*, No. 3-4, September 1970, pp. 227-245.

Elsevier DOI
BibRef
**7009**

*Montanari, U.[Ugo]*,

**Networks of Constraints: Fundamental Properties
and Applications to Picture Processing**,

*Information Science(7)*, No. 2, 1974, pp. 95-132.
BibRef
**7400**

And:
*CMU-CS-TR*January 1971.
BibRef

*Aiello, M.*,
*Lami, C.*,
*Montanari, U.*,

**Optimal Matching of Wheat Chromosomes**,

*CGIP(3)*, No. 3, September 1974, pp. 225-235.

Elsevier DOI
BibRef
**7409**

*Montanari, U.*,

**Optimization Methods in Image Processing**,

*IFIP74*(727-732).
BibRef
**7400**

*Montanari, U.*,

**Recent Progress in Picture Processing and Scene Analysis**,

*ICPR74*(513-516).
BibRef
**7400**

*Montanari, U.*, and
*Reddy, R.*,

**Computer Processing of Natural Scenes: Some Unsolved Problems**,

*IJCAI71*(Paper 12).
BibRef
**7100**

*Mohr, R.[Roger]*, and
*Henderson, T.C.[Thomas C.]*,

**Arc and Path Consistency Revisited**,

*AI(28)*, No. 2, March 1986, pp. 225-233.

Elsevier DOI Also has a ECAI paper and a NATO-ASI paper with similar information.
Optimal arc consistency algorithm, simple and effective (from the ad).
BibRef
**8603**

*Han, C.C.*,
*Lee, C.H.*,

**Comments on Mohr and Henderson's Path Consistency Algorithm**,

*AI(36)*, No. 1, August 1988, pp. 125-130.

Elsevier DOI One of the algorithms is in error, it is corrected.
BibRef
**8808**

*Kuner, P.*, and
*Ueberreiter, B.*,

**Pattern Recognition by Graph Matching Combinatorial Versus
Continuous Optimization**,

*PRAI(2)*, 1988, pp. 527-542.
BibRef
**8800**

*Samal, A.*,
*Henderson, T.*,

**Parallel Split-Level Relaxation**,

*PRAI(2)*, 1988, pp. 425-442.
BibRef
**8800**

Earlier: A2, A1:
*ICPR88*(I: 220-222).

IEEE DOI
BibRef

And:

**2-D Scene Analysis Using Split-Level Relaxation**,

*ICPR86*(195-197).
BibRef

*Liu, H.H.*,
*Young, T.Y.*,
*Das, A.*,

**A Multilevel Parallel Processing Approach to Scene Labeling Problems**,

*PAMI(10)*, No. 4, July 1988, pp. 586-590.

IEEE DOI
BibRef
**8807**

*Tsao, E.C.K.*,
*Lin, W.C.*,

**Constraint Propagation Neural Networks for Huffman-Clowes
Scene Labeling**,

*SMC(21)*, 1991, pp. 1536-1548.
BibRef
**9100**

*Gu, J.[Jun]*, and
*Wang, W.[Wei]*,

**A Novel Discrete Relaxation Architecture**,

*PAMI(14)*, No. 8, August 1992, pp. 857-865.

IEEE DOI
BibRef
**9208**

*Wilson, R.C.*,
*Hancock, E.R.*,

**Structural Matching by Discrete Relaxation**,

*PAMI(19)*, No. 6, June 1997, pp. 634-648.

IEEE DOI
**9708**

*Evaluation, Relaxation*. Bayesian framework for discrete relaxation.
An evaluation of several approaches.
Null Labeling by optimization;
Constraint Filtering (

See also Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques. );
The graph-editing procedure (

See also Distance Measure between Attributed Relational Graphs for Pattern Recognition, A. ) performs best.
BibRef

*Wilson, R.C.[Richard C.]*, and
*Hancock, E.R.[Edwin R.]*,

**Gauging Relational Consistency and Correcting Structural Errors**,

*CVPR96*(47-54).

IEEE DOI
*Evaluation, Matching*. Graph editing performs best.
BibRef
**9600**

*Wilson, R.C.[Richard C.]*,
*Hancock, E.R.[Edwin R.]*,

**An integrated approach to grouping and matching**,

*CIAP95*(62-67).

Springer DOI
**9509**

BibRef

*Wilson, R.C.*,
*Hancock, E.R.*,

**A Bayesian Compatibility Model for Graph Matching**,

*PRL(17)*, No. 3, March 6 1996, pp. 263-276.
*Bayes Nets*.
BibRef
**9603**

Earlier: A2, A1:

**A Bayesian framework for hierarchical relaxation**,

*ICPR94*(B:7-12).

IEEE DOI
**9410**

BibRef

*Wilson, R.C.[Richard C.]*,
*Hancock, E.R.[Edwin R.]*,

**Graph matching with hierarchical discrete relaxation**,

*PRL(20)*, No. 10, October 1999, pp. 1041-1052.
**9911**

BibRef

Earlier:

**Graph Matching by Configurational Relaxation**,

*ICPR94*(B:563-566).

IEEE DOI
BibRef

*Wilson, R.C.[Richard C.]*,
*Hancock, E.R.[Edwin R.]*,

**Relational Matching with Dynamic Graph Structures**,

*ICCV95*(450-456).

IEEE DOI
BibRef
**9500**

Earlier:

**Relational matching with active graphs**,

*CAIP95*(334-341).

Springer DOI
**9509**

BibRef

*Wilson, R.C.*,
*Hancock, E.R.*,

**Sensitivity Analysis For Structural Matching**,

*ICPR96*(I: 62-66).

IEEE DOI
**9608**

(Univ. of York, UK)
BibRef

*Wilson, R.C.[Richard C.]*,
*Evans, A.N.[Adrian N.]*,
*Hancock, E.R.[Edwin R.]*,

**Relational Matching by Discrete Relaxation**,

*IVC(13)*, No. 5, June 1995, pp. 411-421.

Elsevier DOI
BibRef
**9506**

Earlier:
*BMVC94*(xx-yy).

PDF File.
**9409**

BibRef

*Yamamoto, K.[Kazuhiko]*,

**Optimization Approaches to Constraint Satisfaction Problems in
Computer Vision**,

*IVC(13)*, No. 5, June 1995, pp. 335-340.

Elsevier DOI
BibRef
**9506**

Earlier:
*BMVC94*(xx-yy).

PDF File.
**9409**

BibRef

*Ibson, M.C.*,
*Zapalowski, L.*,

**On the Use of Relaxation Labelling in the Correspondence Problem**,

*PRL(4)*, 1986, pp. 103-109.
BibRef
**8600**

*Ishikawa, H.[Hiroshi]*,

**Exact Optimization for Markov Random Fields with Convex Priors**,

*PAMI(25)*, No. 10, October 2003, pp. 1333-1336.

IEEE Abstract.
**0310**

Solving large combinatorial optimization problem.
BibRef

*Ishikawa, H.[Hiroshi]*,

**Total Absolute Gaussian Curvature for Stereo Prior**,

*ACCV07*(II: 537-548).

Springer DOI
**0711**

BibRef

*Ishikawa, H.[Hiroshi]*,

**Transformation of General Binary MRF Minimization to the First-Order
Case**,

*PAMI(33)*, No. 6, June 2011, pp. 1234-1249.

IEEE DOI
**1105**

Transform high-order MRF to first-order with same minima as original.
energy minimization.
BibRef

*Yu, J.G.[Jin-Gang]*,
*Xia, G.S.[Gui-Song]*,
*Samal, A.[Ashok]*,
*Tian, J.W.[Jin-Wen]*,

**Globally consistent correspondence of multiple feature sets using
proximal Gauss-Seidel relaxation**,

*PR(51)*, No. 1, 2016, pp. 255-267.

Elsevier DOI
**1601**

Feature correspondence
BibRef

Springer DOI

BibRef

*Yang, D.*,
*Kittler, J.V.*,

**MFT Based Discrete Relaxation for Matching High Order
Relational Structures**,

*ICPR94*(B:219-223).

IEEE DOI
BibRef
**9400**

*Ishikawa, S.*,
*Kato, K.*,

**Associating an Image by Network Constraint Analysis**,

*ICPR92*(I:730-733).

IEEE DOI
BibRef
**9200**

*Nishihara, S.*,
*Ikeda, K.*,

**A Solution Algorithm for the Consistent Labeling Problem Using the
Structure of Constraints**,

*ICPR86*(198-200).
BibRef
**8600**

*Montalvo, F.S.*,

**Human Vision Paradox Implicates Relaxation Model**,

*IJCAI77*(656).
BibRef
**7700**

*Montalvo, F.S.*,
*Weisstein, N.*,

**An Empirical Method that Provides a Basis for the Organization
of Relaxation Labeling Processes for Vision**,

*IJCAI79*(595-597).
BibRef
**7900**

*Nishihara, S.*,
*Ikeda, K.*,

**A Constraint Synthesizing Algorithm For The Consistent Labeling Problem**,

*ICPR84*(310-312).
BibRef
**8400**

*Shapiro, L.G.*,

**Solving Consistent Labeling Problems Having The Separation Property**,

*ICPR84*(313-315).
BibRef
**8400**

Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in

Matching Using "Tree" Searching Techniques, Heuristic Search .

Last update:May 10, 2021 at 18:51:10