Slagle, J.R.,
Lee, R.C.T.,
Applications of Game Tree Searching Techniques to
Sequential Pattern Recognition,
CACM(14), 1971, pp. 103-110.
BibRef
7100
Haralick, R.M., and
Shapiro, L.G.,
The Consistent Labeling Problem: Part I,
PAMI(1), No. 2, April 1979, pp. 173-184.
BibRef
7904
And:
The Consistent Labeling Problem: Part II,
PAMI(2), No. 3, May 1980, pp. 193-203.
BibRef
Earlier:
The Consistent Labeling Problem and Some Applications to
Scene Analysis,
ICPR78(616-619).
BibRef
And:
The Consistent Labeling Problem,
PRAI-78(173-178).
Explore how the problem is done and various operators that
can make it faster.
BibRef
Shapiro, L.G., and
Haralick, R.M.,
Structural Descriptions and Inexact Matching,
PAMI(3), No. 5, September 1981, pp. 504-519.
BibRef
8109
Earlier:
Algorithms for Inexact Matching,
ICPR80(202-207).
Relaxation, Evaluation. Use of Null nodes.
This paper discusses structural description
methods (using parts and interrelationships of the parts), and
matching techniques based on tree searching (backtrack alone,
forwardchecking, and looking ahead). Two kind of matching are
described: exact where every relation matches and inexact that is
not perfect, only good enough (a mapping such that the weighted sum
of the corresponding relations is greater than some given threshold,
and the weighted sum of non-matching elements is less than a
threshold). Finding the best match is more complex: how do you
compare 2 matches when there are good and bad points to each?
Searching eliminates impossible (unlikely) paths by considering not
only the error in the matches found so far but the minimum error
that can occur in the future assignments as constrained by the past
labels. Forward checking looks at all future labels, looking ahead
only considers the next set of assignments. A look ahead by two
assignments is the same as discrete relaxation. The forward checking
produces the best results mostly because of the extra computation of
the lookahead operations. When more errors are introduced the
problem becomes much harder. A major conclusion of the paper is that
the inexact matching (consistent labeling) problem is much harder
than the exact matching problem.
BibRef
Shapiro, L.G.,
Inexact Matching in ESP3,
ICPR76(759-763).
BibRef
7600
Haralick, R.M.,
Ullmann, J.R., and
Shapiro, L.G.,
Computer Architecture for Solving Consistent Labeling Problems,
Computer Journal(28), No. 2, 1985, pp. 105-111.
BibRef
8500
Haralick, R.M.[Robert M.], and
Elliott, G.L.[Gordon L.],
Increasing Tree Search Efficiency for Constraint Satisfaction Problems,
AI(14), No. 3, October 1980, pp. 263-313.
WWW Version.
HTML Version.
BibRef
8010
Earlier:
IJCAI79(356-364).
BibRef
Rubin, S.[Steve],
Natural Scene Recognition Using Locus Search,
CGIP(13), No. 4, August 1980, pp. 298-333.
WWW Version.
BibRef
8008
Rubin, S., and
Reddy, R.,
The Locus Model of Search and its Use in Image Interpretation,
IJCAI77(590-595).
BibRef
7700
And:
DARPA77(12-14).
Locus, or beam search applied to vision.
BibRef
Rubin, S.[Steve],
The ARGOS Image Understanding System,
Ph.D.Thesis (CS), 1978.
BibRef
7800
CMU-CS-TR-Report, CMU CS Dept.
BibRef
Earlier:
DARPAN78(159-162).
Pose Estimation.
Color.
Viewpoint Constraint. The matching method used in HARPY speech program applied to vision,
recognition at the basic region level. It requires a detailed model
to specify what is possible.
BibRef
Boyer, K.L.,
Vayda, A.J., and
Kak, A.C.,
Robotic Manipulation Experiments Using Structural Stereopsis
for 3D Vision,
IEEE_EXPERT(1), Fall 1986, pp. 73-94.
This reports on results of the work that is
covered in the next paper, but is a less technical vision article.
BibRef
8600
Boyer, K.L., and
Kak, A.C.,
Structural Stereo for 3-D Vision,
PAMI(10), No. 2, March 1988, pp. 144-166.
IEEE Abstract.
WWW Version.
BibRef
8803
Earlier:
Symbolic Stereo from Structural Descriptions,
CAIA85(82-87).
There is a lot in the paper, primarily it is a matching method. The
comparison technique is described in information theoretic terms,
but is basically standard, the difference is a triangle function
with a peak for no difference between the two and a limit on where
zero is reached. The search method is standard tree search, start
with the ones that have the fewest options (get the set of best
matches and take them only if they are good enough), also there is
a nice NIL mapping technique -- NIL is the match of last resort (i.e. at
the end of every path in the search tree) but is added to the possible
matches only if no other match is good enough. The system uses an
information theoretic distance measure (essentially the probaability that
two corresponding elements will have the given difference).
BibRef
Vayda, A.J., and
Kak, A.C.,
A Robot Vision System for Recognition of Generic Shaped Objects,
CVGIP(54), No. 1, July 1991, pp. 1-46.
WWW Version.
BibRef
9107
Earlier:
INGEN: A Robot Vision System for Generic Object Recognition,
CADBV91(166-175).
A generic object (parallelepipeds and cylinders) recognition system,
that extracts object hypotheses, geometric reasoning to find size
and detect geometric inconsistencies and recognition to reject
hypotheses which have little support. Uses range data.
BibRef
van der Helm, P.A.,
Leeuwenberg, E.L.J.,
Avoiding explosive search in automatic selection of simplest pattern
codes,
PR(19), No. 2, 1986, pp. 181-191.
WWW Version.
0309
BibRef
Newborn, M.,
Unsynchronized iteratively deepening parallel alpha-beta search,
PAMI(10), No. 5, September 1988, pp. 687-694.
IEEE Abstract.
WWW Version.
0401
BibRef
Schaeffer, J.,
The history heuristic and alpha-beta search enhancements in practice,
PAMI(11), No. 11, November 1989, pp. 1203-1212.
IEEE Abstract.
WWW Version.
0401
BibRef
Powley, C.,
Korf, R.E.,
Single-agent parallel window search,
PAMI(13), No. 5, May 1991, pp. 466-477.
IEEE Abstract.
WWW Version.
0401
BibRef
Kaindl, H.,
Shams, R.,
Horacek, H.,
Minimax search algorithms with and without aspiration windows,
PAMI(13), No. 12, December 1991, pp. 1225-1235.
IEEE Abstract.
WWW Version.
0401
BibRef
Yang, G.Z.[Guang-Zheng],
The search algorithms stimulated by premise set in the syntactic
knowledge system,
PR(26), No. 1, January 1993, pp. 17-22.
WWW Version.
0401
BibRef
Paglieroni, D.W.,
Ford, G.E.,
Tsujimoto, E.M.,
The Position-Orientation Masking Approach To Parametric
Search For Template Matching,
PAMI(16), No. 7, July 1994, pp. 740-747.
IEEE Abstract.
WWW Version.
BibRef
9407
Reinefeld, A.,
Marsland, T.A.,
Enhanced Iterative-Deepening Search,
PAMI(16), No. 7, July 1994, pp. 701-710.
IEEE Abstract.
WWW Version.
BibRef
9407
Ben-Arie, J., and
Meiri, A.Z.,
3D Objects Recognition by Optimal Matching Search
of Multinary Relations Graphs,
CVGIP(37), No. 3, March 1987, pp. 345-361.
WWW Version.
Recognize Three-Dimensional Objects.
BibRef
8703
Earlier:
3-D Objects Recognition by State Space Search:
Optimal Geometric Matching,
CVPR86(456-461).
BibRef
And:
Optimal Recognition of 3-D Objects By Search: Generic Models,
ICPR86(100-103).
3D shape matching, using heuristics to limit the cost of the search.
(Ignore the grammar problems in the title.)
BibRef
Ben-Arie, J., and
Meiri, A.Z.,
Three-Dimensional Object Recognition by Two-Dimensional Inclined
Shapes Matching with Area Ratios Method,
Draftfall 1984. (Technion - Israel) The
interesting thing is the ratio of the area of the lobe to the
whole area. This is the feature used in the comparison.
Everything else is straightforward.
BibRef
8400
Kuno, Y.,
Okamoto, Y.,
Okada, S.,
Robot vision using a feature search strategy generated from a 3D object
model,
PAMI(13), No. 10, October 1991, pp. 1085-1097.
IEEE Abstract.
WWW Version.
0401
BibRef
Earlier:
Object Recognition Using a Feature Search Strategy Generated
from a 3-D Model,
ICCV90(626-635).
IEEE DOI Link
BibRef
Spirkovska, L.,
Three-Dimensional Object Recognition Using Similar Triangles
and Decision Trees,
PR(26), No. 5, May 1993, pp. 727-732.
WWW Version.
BibRef
9305
Ishida, T.,
Real-Time Bidirectional Search:
Coordinated Problem-Solving in Uncertain Situations,
PAMI(18), No. 6, June 1996, pp. 617-628.
IEEE Abstract.
WWW Version.
9607
Search.
BibRef
Chaudhury, S.,
Acharyya, A.,
Subramanian, S.,
Parthasarathy, G.,
Recognition of Occluded Objects with Heuristic Search,
PR(23), No. 6, 1990, pp. 617-635.
WWW Version.
BibRef
9000
Chaudhury, S.,
Subramanian, S.,
Parthasarathy, G.,
Recognition of Partial Planar Shapes in Limited Memory Environments,
PRAI(4), 1990, pp. 603-628.
BibRef
9000
Ishida, T.,
Korf, R.E.,
Moving-Target Search: A Real-Time Search for Changing Goals,
PAMI(17), No. 6, June 1995, pp. 609-619.
IEEE Abstract.
WWW Version.
BibRef
9506
Cho, C.J.,
Kim, J.H.,
Recognizing 3-D Objects by Forward Checking Constrained Tree Search,
PRL(13), 1992, pp. 587-597.
BibRef
9200
Stewart, B.S.,
Liaw, C.F.,
White, III, C.C.,
A Bibliography of Heuristic Search Research Through 1992,
SMC(24), 1994, pp. 268-293.
BibRef
9400
Chung, K.L.,
Wu, J.G.,
Lan, J.K.,
Efficient Search Algorithm on Compact S-Trees,
PRL(18), No. 14, December 1997, pp. 1427-1434.
9806
BibRef
Cantoni, V.,
Cinque, L.,
Guerra, C.,
Levialdi, S.,
Lombardi, L.,
2-D Object Recognition by Multiscale Tree Matching,
PR(31), No. 10, October 1998, pp. 1443-1454.
WWW Version.
9808
BibRef
Raman, A.[Anand],
Andreae, P.[Peter],
Patrick, J.[Jon],
A Beam Search Algorithm for PFSA Inference,
PAA(1), No. 2, 1998, pp. 121-129.
BibRef
9800
Messmer, B.T.[Bruno T.],
Bunke, H.[Horst],
A New Algorithm for Error Tolerant Subgraph Isomorphism Detection,
PAMI(20), No. 5, May 1998, pp. 493-504.
IEEE Abstract.
WWW Version.
9806
BibRef
Earlier:
Fast error-correcting graph isomorphism based on model precompilation,
CIAP97(I: 693-700).
WWW Version.
9709
BibRef
Earlier: A2, A1:
Efficient attributed graph matching and its application to image
analysis,
CIAP95(44-55).
Springer DOI Link
9509
BibRef
Messmer, B.T.[Bruno T.],
Bunke, H.[Horst],
A decision tree approach to graph and subgraph isomorphism detection,
PR(32), No. 12, December 1999, pp. 1979-1998.
WWW Version.
BibRef
9912
Joseph, S.H.,
Analysing and reducing the cost of exhaustive correspondence search,
IVC(17), No. 11, September 1999, pp. 815-830.
WWW Version.
BibRef
9909
Pridmort, T.P.,
Joseph, S.H.,
Integrating visual search with visual memory in a knowledge directed
image interpretation system,
BMVC90(xx-yy).
PDF Version.
9009
BibRef
Silvela, J.,
Portillo, J.,
Breadth-first search and its application image processing problems,
IP(10), No. 8, August 2001, pp. 1194-1199.
IEEE DOI Link
0108
BibRef
Wang, J.K.[Jian-Kang],
Li, X.B.[Xiao-Bo],
Controlled accurate searches with balloons,
PR(36), No. 3, March 2003, pp. 827-843.
WWW Version.
0301
BibRef
Breuel, T.M.,
On the use of interval arithmetic in geometric branch and bound
algorithms,
PRL(24), No. 9-10, June 2003, pp. 1375-1384.
WWW Version.
0304
BibRef
Breuel, T.M.[Thomas M.],
A Comparison of Search Strategies for Geometric Branch and Bound
Algorithms,
ECCV02(III: 837 ff.).
HTML Version.
0205
BibRef
Breuel, T.M.[Thomas M.],
Implementation techniques for geometric branch-and-bound matching
methods,
CVIU(90), No. 3, June 2003, pp. 258-294.
WWW Version.
0307
BibRef
Sun, C.M.[Chang-Ming],
Pallottino, S.[Stefano],
Circular shortest path in images,
PR(36), No. 3, March 2003, pp. 709-719.
WWW Version.
0301
BibRef
Earlier:
Circular Shortest Path on Regular Grids,
ACCV02(852-857).
BibRef
Appleton, B.[Ben],
Sun, C.M.[Chang-Ming],
Circular shortest paths by branch and bound,
PR(36), No. 11, November 2003, pp. 2513-2520.
WWW Version.
0309
BibRef
Sun, C.M.[Chang-Ming],
Appleton, B.[Ben],
Multiple Paths Extraction in Images Using a Constrained Expanded
Trellis,
PAMI(27), No. 12, December 2005, pp. 1923-1933.
IEEE DOI Link
0512
Extract multiple paths, rather than a single optimal path.
(
See also Finding the Best Set of K Paths through a Trellis with Application to Multitarget Tracking. )
BibRef
Undeger, C.,
Polat, F.,
Real-Time Edge Follow: A Real-Time Path Search Approach,
SMC-C(37), No. 5, September 2007, pp. 860-872.
IEEE DOI Link
0710
Real-time path searching. Compared to real-time A*.
BibRef
Undeger, C.,
Polat, F.,
Real-Time Moving Target Evaluation Search,
SMC-C(39), No. 3, May 2009, pp. 366-372.
IEEE DOI Link
0904
BibRef
Ris, M.[Marcelo],
Barrera, J.[Junior],
Martins, Jr., D.C.[David C.],
U-curve: A branch-and-bound optimization algorithm for U-shaped cost
functions on Boolean lattices applied to the feature selection problem,
PR(43), No. 3, March 2010, pp. 557-568.
Elsevier DOI Link
WWW Version.
1001
Boolean lattice; Branch-and-bound algorithm; U-shaped curve; Feature
selection; Subset search; Optimal search
BibRef
Dwyer, T.[Tim],
Hurst, N.[Nathan],
Merrick, D.[Damian],
A Fast and Simple Heuristic for Metro Map Path Simplification,
ISVC08(II: 22-30).
Springer DOI Link
0812
Shortest path.
BibRef
Boffy, A.,
Tsin, Y.,
Genc, Y.,
Real-Time Feature Matching using Adaptive and Spatially Distributed
Classification Trees,
BMVC06(II:529).
PDF Version.
0609
BibRef
Serratosa, F.[Francesc],
Sanromà, G.[Gerard],
Sanfeliu, A.[Alberto],
A New Algorithm to Compute the Distance Between Multi-dimensional
Histograms,
CIARP07(115-123).
Springer DOI Link
0711
BibRef
Serratosa, F.[Francesc],
Sanromà, G.[Gerard],
An Efficient Distance Between Multi-dimensional Histograms for
Comparing Images,
SSPR06(412-421).
Springer DOI Link
0608
BibRef
Serratosa, F.[Francesc],
Sanfeliu, A.[Alberto],
Vision-Based Robot Positioning by an Exact Distance Between Histograms,
ICPR06(II: 849-852).
WWW Version.
0609
BibRef
And:
A Fast and Exact Modulo-Distance Between Histograms,
SSPR06(394-402).
Springer DOI Link
0608
To determine if the image is familiar.
BibRef
Serratosa, F.[Francesc],
Sanfeliu, A.[Alberto],
Matching Attributed Graphs:
2nd-Order Probabilities for Pruning the Search Tree,
IbPRIA05(II:131).
Springer DOI Link
0509
BibRef
Wahl, E.[Eric],
Hirzinger, G.[Gerd],
A Method for Fast Search of Variable Regions on Dynamic 3D Point Clouds,
DAGM05(208).
Springer DOI Link
0509
BibRef
Thayananthan, A.,
Stenger, B.,
Torr, P.H.S.,
Cipolla, R.,
Learning a Kinematic Prior for Tree-Based Filtering,
BMVC03(xx-yy).
HTML Version.
0409
Tree based evaluation for tracking.
BibRef
Stenger, B.,
Thayananthan, A.,
Torr, P.H.S.,
Cipolla, R.,
Filtering using a tree-based estimator,
ICCV03(1063-1070).
IEEE DOI Link
0311
BibRef
Huber, D.F.[Daniel F.],
Hebert, M.[Martial],
3D Modeling Using a Statistical Sensor Model and Stochastic Search,
CVPR03(I: 858-865).
IEEE Abstract.
HTML Version.
0307
BibRef
And:
CREST03(125-126).
0309
BibRef
Kovtun, I.[Ivan],
Partial Optimal Labeling Search for a NP-Hard Subclass of (max,+)
Problems,
DAGM03(402-409).
HTML Version.
0310
BibRef
Hao, H.W.[Hong-Wei],
Liu, C.L.[Cheng-Lin],
Sako, H.,
Comparison of genetic algorithm and sequential search methods for
classifier subset selection,
ICDAR03(765-769).
IEEE Abstract.
0311
BibRef
Tabibi, O.D.[Omid David],
Netanyahu, N.S.[Nathan S.],
Verified Null-move Pruning,
UMD-- TR4406, October 2002.
WWW Version.
WWW Version.
BibRef
0210
Jepson, A.D.[Allan D.],
Mann, R.[Richard],
Qualitative Probabilities for Image Interpretation,
ICCV99(1123-1130).
IEEE DOI Link Probabilistic pruning of search tree.
BibRef
9900
Greenspan, M.A.[Michael A.],
The Sample Tree:
A Sequential Hypothesis Testing Approach to 3D Object Recognition,
CVPR98(772-779).
IEEE Abstract.
BibRef
9800
Chung, H.Y.,
Cheung, P.Y.S.,
Yung, N.H.C.,
Adaptive search center non-linear three step search,
ICIP98(II: 191-194).
IEEE DOI Link
9810
BibRef
Commike, A.Y.,
Hull, J.J.,
Syntactic pattern classification by branch and bound search,
CVPR91(432-437).
IEEE Abstract.
0403
BibRef
Tanimoto, S.L.,
Machine Vision as State-Space Search,
MVAAS88(XX-YY).
Search Techniques. Model vision as a search. Describe search techniques.
BibRef
8800
Breuel, T.M.[Thomas M.],
Geometric Aspects of Visual Object Recognition,
MIT AI-TR-1374, May 1992.
BibRef
9205
Ph.D.thesis, MIT, 1992.
WWW Version.
BibRef
Breuel, T.M.,
Higher-Order Statistics in Object Recognition,
CVPR93(707-708).
IEEE Abstract.
BibRef
9300
Breuel, T.M.,
Fast Recognition Using Adaptive Subdivisions of Transformation Space,
CVPR92(445-451).
IEEE Abstract. This algorithm is faster than the alignment and Hough methods.
BibRef
9200
Breuel, T.M.,
Model Based Recognition Using Pruned Correspondence Search,
CVPR91(257-262).
IEEE Abstract. Reduce potentially exponential time algorithms to polynomial time by
requiring the matching of features to convex regions.
BibRef
9100
Breuel, T.M.[Thomas M.],
An Efficient Correspondence Based Algorithm for 2D and 3D
Model Based Recognition,
MIT AI Memo-1259, October 1990.
BibRef
9010
Breuel, T.M.[Thomas M.],
Indexing for Visual Recognition from a Large Model Base,
MIT AI Memo-1108, August 1990.
WWW Version.
BibRef
9008
Breuel, T.M.,
Adaptive Model Base Indexing,
DARPA89(805-814).
BibRef
8900
Blostein, S.D.,
Huang, T.S.,
A Tree Search Algorithm for Target Detection in Image Sequences,
CVPR88(690-695).
IEEE Abstract.
BibRef
8800
Brailovsky, V.L.,
A probabilistic estimate of clustering,
ICPR90(I: 953-956).
IEEE DOI Link
9006
BibRef
Earlier:
On use of predictive probabilistic estimates for selecting best
decision rules in the course of a search,
CVPR88(469-475).
IEEE Abstract.
0403
BibRef
Gennery, D.B.,
A Feature-Based Scene Matcher,
IJCAI81(667-673), (JPL).
Match 2 scene descriptions - set of feature vectors, differ by
unknown transformation. Method: search by sequentially matching
features of one scene to those of the other scene. Computer
transformations and probability of match - use these to prune tree.
Search: choose of possible match for one element (try all), choose
a consistent match for the next element, etc. Standard search
problems. Examples are on small numbers.
BibRef
8100
Smith, D.R.[David R.],
Search Strategies for the ARGOS Image Understanding System,
DARPAN79(42-46).
Extension of the ARGOS system.
BibRef
7900
Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in
Tabu Search .