13.3.10.1 Discrete Relaxation 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 AIVision 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: UBCTechnical 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-TRJanuary 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

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 .