an essential component to the solution of the error correcting parsing
of the imperfect segmentation.
3.3.1 Building the Polygon Split Tree bottom-up
The starting point here is a complete segmentation whose region-
level structure conforms with the Polygon Map Grammars. Initially,
there is no level label assigned to each region. Therefore, we say all
polygons are atomic, so the input is an Atomic Polygon Map being
represented in an explicit polygon-edge-vertex data structure. The
algorithm consists of two steps that are briefly described below.
Algorithm: Search for edge hierarchy
1. construct the level equality and unequality systems for all the
edges. For three edges constitute a T-cross, two collinear edges
have the equal level, while the third edge has a lower level. Any
two edges of the map boundary naturally have the equal level.
2. search out the edges of map boundary. These edges have the
highest level that can be extracted from the level equality and
unequality system.
3. recursively search out the edges of all levels from high to low
one after another.
This algorithm results in the hierarchy of edges. The number of edge
levels minus one is the depth of polygon partitions.
Algorithm: Search for polygon hierarchy
This is a recursive procedure from the edges of the lowest level to the
edges of highest level, at each level initially all edges of this level are
put in a waiting list for handling as follows:
1. For each edge, search its brother edges that cut a larger polygon
into a number of smaller ones (see grammar productions).
2. For these brother edges, search their associated brother poly-
gons, and synthesize their father polygon including the long
edges. The relations between these brother polygons and their
father polygon are stored in data base.
3. Remove these processed brother edges from the waiting list, and
continue for the rest edges in the waiting list.
The algorithm will result in the largest father polygon. Because all the
polygon hierarchy relations are stored in data base, backtracking from
this largest polygon through low-level descendents will retrieve the
Polygon Split Tree. Upwardtracking from the lowest-level polygons
to higher ones will retrieve the Polygon Merge Tree.
3.3.2 Error-Correcting Parsing of Segmented Images
The starting point here is an initial segmented image resultant from
any existing low-level segmentation algorithm. All regions are closed.
A certain number of physical edges may be lost due to common lan-
duse of neighbouring polygons or inability of segmentatin algorithm
to detecting these edges. Therefore, there are not only T-crosses, but
also corners formed by the detected edges. These corners are called
Growth Vertices from each two possible prolongations can be hypoth-
esized. The task is to determine which prolongation should be selected
as recovered edge.
Algorithm: Error-correcting parsing
1. Search Growth Vertices that are significant corners on the poly-
gon boundaries.
2. Generate all possible hypotheses from these vertices, two pro-
longations from each growth vertex.
3. Run the strong heuristic rules according to priority of these rules
to select the most possible hypotheses and eliminate the alter-
natives. Update the hypothesis data base simulatenously.
936
Strong Rules:
1. If both two end points of a hypothesized edge are growth ver-
tices, these select this edge, and eliminate two alternatives.
2. Because any two alternative hypothesized edges should belong
to two different levels, select the edge with a higher level and
eliminate the other.
It should be pointed out that the second strong rule is a complex pro-
cedure, because the prerequisite is that the level for each hypothesized
edge must be known. Determination of the levels of all hypothesized
and existing edges can be done by an adapted version of the algorithms
for constructing Polygon Split Tree. The essential difference is that
there are X-crosses in this situation. In order to build the edge level
equality and unequality systems, for each X-crosses, we only store the
edge level equality of any two collinear edges (whatever existing or
hypothesized). The unequality will be resolved through T-crosses in
the larger context.
Fig.2 shows a parsing process starting from the errorneous segmented
image through error-correcting parsing till the Polygon Split Tree built
bottom-up, with our current implementations.
A note on Inference of Polygon Map Grammars
of such grammars involves structural induction
tion. Due to its complexity and our lack of
not address this problem here.
(Learning). Learning
and statistical estima-
sufficient practice, we do
4 CONCLUSIONS
The contribution of SSPILS as a general paradigm to vision research
is two-fold: (1) It clarifies the representations and dynamics of spa-
tial structure in vision and thus makes possible the structural generic
model-based image understanding. (2) It promotes the Explicit Com-
puter Vision as a foundation of computer vision in order to study the
vision problems in pure mathematical world and also to analyze the
quality of vision algorithms and systems. The Polygon Map Gram-
mars as a case of SSPILS sheds light on the further development of
techniques to image interpretation in remote sensing.
REFERENCES
BELow R.K., L.B.BookER (1991): Genetic Algorithms. Univer-
sity of California, San Diego.
DICKINSON S.J., A.P.PENTLAND, and A.ROSENFELD (1992): 3-D
Shape recovery using distributed aspect matching. IEEE Trans.
PAMI, Vol. 14, No.2, February.
EGENHOFER M.J., A.U.FRANK AND J.P.JACKSON (1989): A topo-
logical data model for spatial databases. Lecture Notes in Com-
puter Science Vol.409, Springer.
FISCHLER M. A., BoLLEs R. C. (1981): Random Sample Consen-
sus: À Paradigm for Model-Fitting with Applications to Image
Analysis and Automated Cartography. Comm. ACM, June, 1981,
PP. 381-395.
FORSTNER W. (1991a): Statistische Verfahren für die automatische
Bildanalyse und ihre Bewertung bei der Objekterkennung und -
vermessung. Habilitationsschrift, DGK C 370, München 1991.
FÖRSTNER W. (1991b): Object extraction from digital images.
Proc. Photogrammetrische Woche, Universität Stuttgart, 1991.
Fu K. S. (1982): Syntactic Pattern Recognition and Applications,
Prentice Hall, Englewood Cliffs, N. J. 1982.
Fua P., HANsoN A. J. (1989): Objective Functions for Feature
Discrinination: Theory. Proc. DARPA, Image Understanding
Workshop, 1989.
GEORGEFF M. P., WALLACE C. S. (1984): A General Selection
Criterion for Inductive Inference. Proc. of Advance in Art. In-
tell. Italy Sept. 1984, T. O'Shea (Ed.), Noth Holland, Amsterdam
1984.
KANADE T. (1991) (ed.): IEEE Trans.
Physics-based vision.
KURZWEIL R.(1990): The Age of Intelligent Machines. MIT Press,
pp.189.
PAMI Special Issue on
