*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.

WWW Link.
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.

WWW Link.
**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.

WWW Link. 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.

WWW Link. 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.

WWW Link.
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.

WWW Link.
BibRef
**8501**

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

**The complexity of constraint satisfaction revisited**,

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

WWW Link.
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.

WWW Link.
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.

WWW Link.
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.

WWW Link.
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.

WWW Link.
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.

WWW Link.
BibRef
**9200**

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

**Discrete Relaxation**,

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

WWW Link.
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.

WWW Link.
BibRef
**9010**

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

**Constraint Relaxation May Be Perfect**,

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

WWW Link.
BibRef
**9103**

*Montanari, U.[Ugo]*,

**Heuristically guided search and chromosome matching**,

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

WWW Link.
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.

WWW Link.
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.

WWW Link. 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.

WWW Link. 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.

WWW Link.
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.

WWW Link.
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 .

Last update:Sep 25, 2017 at 16:36:46