An icon image is chosen to relate to the idea or action either by resemblance (picture), or by analogy (symbol), or by being selected from a previously defined and learned group of arbitrarily designed images (sign). To assure the correct interpretation of an icon image, there are three requirements:

	. the right image,
	. the right caption,
	. the right context.

Iconic languages have their problems and drawbacks. As pointed out by Lodding, some icons are inherently ambiguous, some can only be interpreted within a certain context. As pointed out by Korfhage [KORFHAGE86], since there is no commonly accepted universal set of icons, icons may evolve in time. Therefore, the design process of icons must be well thought out. Lodding suggests the design process of icons be divided into three distinct steps or phases: a) choosing the representation, b) rendering the design, and c) testing the resulting icon.

As mentioned above, visual languages can be designed based upon the concept of generalized icons, which are dual representations of objects consisting of a logical part and a physical part. Generalized icons can be further classified into object icons and process icons. The main concepts concerning generalized icons are defined below.

An iconic system is a structured set of related icons. A complex icon can be composed from other icons in the iconic system, and therefore express a more complex visual concept. An iconic sentence (called visual sentence by Lakin, iconic sentence or action sentence by Tanimoto [TANIMOTO86], and iconic statement by Korfhage) is a spatial arrangement of icons from an iconic system. A visual language is a set of iconic sentences constructed with given syntax and semantics. Syntactic analysis of visual language (spatial parsing) is the analysis of the spatial arrangement of icons (i.e. an iconic sentence) to determine the underlying syntactic structure. Finally, semantic analysis of visual language (spatial interpretation) is the interpretation of an iconic sentence to determine its underlying meaning.

SELECT Pilot,CoPilot FROM PlanArr
WHERE Airline = 'Delta' AND FlightNo = 463;

This example illustrates how iconic sentences can be constructed using iconic operators, which denote either logical conjunction (vertical combination of icons) or logical disjunction (horizontal combination of icons). In Section 1.4, such iconic operators will be defined formally. It should also be noted that a query icon can become either an object icon (when its attributes are specified) or a process icon (when its attributes are given question marks), depending upon the actual query instance.

The second example illustrates the construction of an iconic system for a pictorial database. Figure 1.3 shows an actual SEASAT picture. By applying picture processing and pattern recognition algorithms, certain shiplike objects in this picture can be reduced to object icons. Some more complex objects, such as the shorearea, can be reduced to complex icons. The picture now becomes a picture consisting in part of the real picture, in part of object icons. These icons are related hierarchically to constitute a tree structure.

The icon rules R specify icons as the dual representation by a set of logical objects and a physical object. Several examples will be presented below.

Example 1: For the image database shown in Figure 1.3, the formal iconic system is G1 ( {c1,c2}, {po,p1,p2,p3,p4}, {xo,x1,x2,x3,x4}, xo, R1), where the icon rules R1 are:

r1:	xo ::= ({x1,x2}, po)
r2:	x1 ::= ({x3,x4}, p1)
r3:	x2 ::= (  { }  , p2)
r4:	x3 ::= (  {c1} , p3)
r5:	x4 ::= (  {c2} , p4)

In the above, rule r1 specifies an icon xo with the logical part {x1,x2} and the physical part po. Both x1 and x2 are icon names in S. Therefore, rule r1 says x1 and x2 are subicons of the icon xo. Rule r2 is similar to rule r1. Rule r3 specifies an icon x2, whose logical part is the null object, and physical part is p2. In other words, x2 is really a "pure image". Rule r4 specifies an icon x4, whose logical part is {c1} and physical part is p3. The object c1 is an element of VL, and is used as a "label" for the physical image p3.

The iconic system can be seen to be a special type of picture grammar [FU74]. The icon grammar rules can also be expressed as commands in an iconic language (see [CHANG85] for a proposed language IPL). We give the following examples to illustrate elements of an interactive iconic language. In what follows, a command line is indicated by a colon. The system response, if any, follows the command line.

: X = ICON( Xm, Xi)	create an icon X with logical
				part Xm and physical part Xi

: X			display contents of icon X
  ( Xm, Xi )

: VL(X)			display logical part of X
  Xm

: VP(X)			display physical part of X
  Xi

: MAT(Xm)		materialization of logical part Xm
  Xi				as physical part Xi

: DMA(Xi)		dematerialization of physical part Xi
  Xm				as logical part Xm

x4 = ICON(   {c2} , p4)
x3 = ICON(   {c1} , p3)
x2 = ICON(   { }  , p2)
x1 = ICON( {x3,x4}, p1)
xo = ICON( {x1,x2}, po)

Example 2: Suppose we have a book organized as chapters containing sections, as illustrated in Figure 1.4.

The formal iconic system is G2 ( {COM}, {e,p2,p3,p4}, {xo,x1,x2,x3,x4}, xo, R2), where the icon rules R2 are:

r1:	xo ::= ({COM,x1,x2}, e)
r2:	x1 ::= ({COM,x3,x4}, e)
r3:	x2 ::= (  { }  ,p2)
r4:	x3 ::= (  { }  ,p3)
r5:	x4 ::= (  { }  ,p4)

The command VL(xo) will display the logical part of icon xo, and the system will respond by evaluating and displaying COMm({x1,x2}). The iconic operator COM has two parts: COMm for the logical operator, and COMi for the physical operator (see the following section). In this example, the COMm operator is applied to the icon set {x1,x2} to yield {x1, x2}. Therefore, VL(xo) is equivalent to listing the content of "directory" xo. On the other hand, the command VP(xo) will generate a blank picture, because the physical part of xo is "e".

The command VP(x2) will display the physical part of icon x2, and the system will respond by displaying p2, the content of "file" x2. On the other hand, the command VL(x2) will generate no output, because x2 does not have a logical part.

From these examples, it can be seen that an icon can be a pure physical picture ({}, PICTURE), a pure logical label ({LABEL},e), a complex icon constructed from subicons ({OP, x1,...,xn}, PICTURE), or a complex icon related to subicons with unspecified method of construction ({x1,...,xn}, PICTURE). Therefore, an icon can be one of the following types:

elementary icon:

if is empty. In other words, is subset of VL, so that is of the form ( {labels}, image ). The labels could denote names of objects, procedures (including user-defined procedures, system function calls, etc.), or operators, so that the elementary icon can be an object icon, a process icon, or an operator icon.

There are special elementary icons. An image icon is one where is empty, so is of the form ( { }, image ). A label icon is one where the physical part is null, so is of the form ({labels}, e). Finally, a null icon is of the form ({ }, e).

complex icon:

if is not empty. A complex icon points to other icons and defines icon relations. We can further distinguish the following types:

composite icon: if is not empty. The icon x is of the form ({OP,}, image), where are subicons or logical objects, and "OP" is an iconic operator which operates on the subicons to create a new icon. The inclusion of iconic operators as logical objects gives greater flexibility and notational convenience in the specification of the logical part of a composite icon. The location attributes of the subicons will determine the order in applying the iconic operator.

structural icon: if is empty. The icon is of the form ({}, image). In other words, is related to , but the mechanism for composing from is unspecified.

(2) Vertical Combination VER:

VER((Am,Ai), (Bm,Bi))
= (VERm(Am,Bm), VERi(Ai,Bi))
= (CONCEPT-MERGE(Am,Bm), VER-COMBINE(Ai,Bi))

(3) Horizontal Combination HOR:

HOR((Am,Ai), (Bm,Bi))
= (HORm(Am,Bm), VERi(Ai,Bi))
= (CONCEPT-MERGE(Am,Bm), HOR-COMBINE(Ai,Bi))

(4) Contextual Interpretation CON:

CON((Am,Ai), (Bm,Bi))
= (CONm(Am,Ai,Bm,Bi), CONi(Ai,Bi))
= (CONTEXT(Am,Ai,Bm,Bi), Ai)

(5) Indexing IDX:

IDX(Am,Ai)
= (IDXm(Am), IDXi(Ai))
= (CONCEPT-REDUC(Am), IMAGE-REDUC(Ai))

(6) Clustering CLU:

CLU( (c1,e),...,(cm,e),({},p1),...,({},pn) )
= { (ci,pj):  }

(7) Cross-Indexing CRO:

CRO( (Am,Ai), (Bm,Bi) )
= ( IDX(A), IDX(B) )

(8) Similarity Operator SIM:

SIM(X,Y) = (SIMm(Xm,Ym), SIMi(Xi,Yi))

Explanation: Similarity operator returns a "true" icon (true-m, true-i), or a "false" icon (false-m, false-i). True/false icons are pure icons. If SIM(X,Y) depends only on SIMi(Xi,Yi), the similarity operator tests the physical similarity of two images. On the other hand, if SIM(X,Y) depends only on SIMm(Xm,Ym), the similarity operator tests the logical similarity of two images. The logical similarity of icons allows for variations of icon images. For example, (stop,\h'0.2i') and (stop,\h'0.2i') are considered similar by logical similarity. (diner,\h'0.2i'), (diner,\h'0.2i'), (diner,\h'0.2i') are also considered similar by logical similarity. If a similarity operator returns (true-m,false-i) or (false-m,true-i), it is considered meaningless.

(9) Existence Operator EXI:

EXI(X,Y) = (EXIm(Xm,Ym), EXIi(Xi,Yi))

Explanation: The existence operator tests for the existence of X in Y, and returns a true/false icon. We can test for the existence of the logical object Xm within Ym, or the existence of the physical object Xi within Yi, or both.

The generic iconic operators discussed above can be used to construct arbitrarily complex icons. These operators are generic, in the sense that their semantics are not completely specified. For specific formal iconic systems, we can use "custom-made" iconic operators to interpret complex icons.

Now we come to the general definition of picture processing grammar:

A picture-processing grammar G is a quintuple(S,V,C,g,P), where S is the set of basic symbols, V is the set of vocabulary symbols, C !supset V is the set of categorical symbols, g is a function from V S into the set of natural numbers, and P is the set of grammar rules. Each rule is of the from

where , the number of parameters of the associate vector is equal to , and f is a partially computable function from , whose completion is also computable. It is required that .

According to the definition, rule 1) can be rewritten in general form as

h-dash[(4,3,1),(5,3,1)] := point(4,3,1) & point(5,3,1)

A picture processing grammar may have a hierarchical structure as defined below:

A picture processing grammar G=(S,V,C,g,P) is called hierarchical if and only if there is a nontrivial partition of the rules P into blocks , n>1, such that if appears as the left-hand symbol of a rule in , then it will never appear as a right-hand symbol of any rule in , provided that j<i.

The parsing algorithm of the languages generated by hierarchical picture processing grammar is then as follows:

        1) Partition the set of rules P into hierarchical blocks ,
        2) i  1,
        3) Apply rules in  in any sequence to reduce the picture.  
When no more reduction is possible, go to the next step,
        4) If i=n or the picture has been reduced to a categorical symbol, 
stop.  Otherwise let  and go to step 3). 

The picture processing grammar described above was successfully applied to analyze hand-written numericals, where the grammar rules are divided into four groups. The first level rules are used to reduce a picture consisting of points to one consisting of horizontal strips. Imperfect strips can be recognized by adjusting to fill gaps. The second level rules are used to reduce the picture to one consisting of vertical lines (V-L) and horizontal lines (H-L). In the third level, L-shaped, U-shaped, and O-shaped figures are described. Finally, in the fourth or last level, the ten numerals are described in terms of their component parts.

Precedence grammar [CHANG 70] is another spatial parsing grammar and can be used for 2-D mathematical expression analysis and printed page format analysis. Precedence grammars are in fact more suitable for the syntactic analysis of iconic sentences, because iconic sentences are constructed using elementary icons and iconic operators. Let us start explaining it by giving a simple example. Suppose we have a mathematical expression a + ( b ). The structure specification scheme is then defined to describe these mathematical expressions. Assume that some or all primitive components are operators, each of them is uniquely associated with a region, a rectangular area on a 2-D plane, mathematically written as where are coordinates of region centroid. A pattern U is a finite collection of primitive components whose regions are disjoint. A frame F of a pattern U is the smallest region containing all primitive components of U.

The structure tree is then constructed by comparing precedence of operators in a pattern and dividing the pattern into one or several subpatterns. Further division are carried out on those sub-patterns. Figure 1.5(b) is the structure tree of expression a + ( b ) and Figure 1.5(a) is the frame partition corresponding to Figure 1.5(b). The operators "(" and ")" are grouped together because they are regarded as an operator pair. The structure specification scheme is then defined as finite collection of these division rules. Thus we have following formal definition:

A well-formed structure of a pattern U is a tree T whose nodes (or node-name) are operator sequences and regions such that

        1) The root of the tree is the frame F of U,
        2) Every primitive component of U appears as a member of some operator 
sequence that is a terminal node of T, and the set of all operator sequences 
of T is U,
        3) If a region is a terminal node, then it is a non-essential region 
with respect to some division rule,
        4) If a region is a non-terminal node, then its successor nodes 
constitute a division of it with respect to some division rule,
        5) If operator  and region R are successor nodes of some 
node and operator  is a successor node of R, then  dominates 
 or  procedes  or they are of equal precedence. 

According to above definition the structural parsing is carried out by first grouping the primitive components of U into operator sequences, and then building up a structural tree T of U. To build up a structure tree T of U we let be the frame of U. Let be all the operator sequences of U. Construct two precedence matrices M1 and M2 as follows: M1(i,j) is ">" if dominates , "<" if dominates , and blank otherwise. M2(i,j) is ">" if precedes , "<" if precedes , "=" if they are of equal precedence, and blank otherwise. All comparisons are done with respect to . By using these two matrices M1 and M2, we choose to divide with respect to , such that is in and is not dominated by any other in and can be divided with respect to into essential and non-essential regions that contain all other w's in .

In the example shown in Figure 1.5(b), the operator "+" is not dominated by any other operator. Therefore, it is selected as the first operato be applied tor to divide the frame.

In an iconic sentence, the iconic operators are often "invisible". resultant icon image. Therefore, in analyzing an iconic sentence, such "invisible" operators must be restored, so that the technique of spatial dominance and precedence analysis described above can be applied.

We can first find the minimum enclosing rectangles (MERs) of the elementary icons in an iconic sentence. By comparing the MERs, invisible operators can be restored. For example, the most commonly used iconic operators are COM, HOR and VER. If two MERs coincide to a considerable degree, then the operator COM is added. If one MER is on top of another MER, then the operator VER is added. If one MER is to the left of another MER, then the operator HOR is added. Precedence matrices M1 and M2 are then constructed to order the iconic operators. Care must be taken to discard "double" iconic operators which are created in comparing the MERs, so that the input iconic sentence can be analyzed correctly. If we don't use the precedence analysis technique, a general parsing algorithm must be used to parse the iconic sentence according to G.

For example, head icon xo of Example 1 of Section 3 can be evaluated as follows:

1)	xo
2)	INT1({x1,x2}, po)
3)	INT1({INT2({x3,x4}, p1),x2}, po)
4)	INT1({INT2({INT4({c1}, p3),x4}, p1),
            x2}, po)
5)	INT1({INT2({INT4({c1}, p3),INT5({c2},
            p4)}, p1), x2}, po)
6)	INT1({INT2({INT4({c1}, p3),INT5({c2}, 
            p4)}, p1),INT3({},p2)}, po)



If all the INTi's are identical, we have



7)	INT({INT({INT({c1}, p3),INT({c2}, p4)}, 
            p1),INT({},p2)}, po)

Procedure INT(A, B)
begin
  draw physical image B to scale;
  while there is another element u in set A
  begin
    if u is of the form INT(C,D) 
       then INT(C,D)
       else draw logical object u to scale 
       within image B;
  end
end

This INT operator creates an image icon ({}, image) using the above recursive procedure. It will first draw image po. Within po, the sub-regions for p1 and p2 will be redrawn with greater detail. Within p1, the sub-regions for p3 and p4 will be redrawn with even greater detail. Moreover, p3 will be marked with label "c1", and p4 will be marked with label "c2".

In iconic indexing, we can use the generic iconic indexing operator IDX_j to replace the INT_j operator, so that we can reduce a complex icon specified by a formal iconic system into a simpler icon. This new icon can then serve as an index to the original complex icon. Continuing with the above example, the expression in (6) can be replaced by,

8) IDX1({IDX2({IDX4({c1}, p3),IDX5({c2}, p4)}, p1),IDX3({},p2)}, po)

The general form of the indexing operator IDX has been defined in sub-section (9) of Section 4. We now give a specific indexing operator IDX_j, which will behave differently for different rule-index-set.

IDXj(A,B)
begin
  if j is in rule-index-set
    then return(union of logical part of 
                icons in A, B)
    else return({}, e)
end

Now we can generalize the concept of similarity among icons. Suppose X is a complex icon, and Y is a simpler icon. The two icons are similar, if SIM(IDX(X),Y) is true. The icon Y can also be considered to be an index of X. In icon-oriented information retrieval, we can use Y to retrieve similar icons in the set {W: SIM(IDX(W),Y) is true}.

It can be seen that iconic indexing is a powerful tool to construct indexes from a formal iconic system. For a different application domain, we can define the appropriate indexing operators IDX_j, to create a specific indexing technique.

The formal iconic system G1 for this menu page is given by:

 ::= ({,,}, ""^""^"")
 ::= (, "")
 ::= (, "")
 ::= (, "")

The following iconic operators are defined:

() = for i=1,2,3, selects a subicon in menu icon ,

() for i=1,2,3, invokes and executes process pi.

Therefore, , and are , and is a complex icon. The user can first select an icon from the menu (using the operator). The operator can then be applied to invoke and execute the selected process. Conceptually, the iconic operator is a unary operator, returning a null icon.

A more complex, two-page menu system is illustrated in Figure 1.7.

The formal iconic system G2 for the two-page menu system is given by:

 ::= (({,}), ({,}))
 ::= ({,},""^"")
 ::= ({,}),""^"")
 ::= (, "")
 ::= (, "")
 ::= (, "")
 ::= (, "")

The following iconic operators are defined:

({X,Y}) connects two object icons X and Y. ({X,Y}) gives the logical relationship that icon Y is after icon X, and ( {X,Y} ) is the sketch with two icon sketchs for X and Y connected by a directed arc from X to Y.

(X) gives the first subicon in the complex icon X.

(X) gives the next icon which is logically connected to X.

(X) selects the subicon in complex icon X.

As before, the iconic operators can operate on the icons of this formal iconic system G2 to realize the menu-driven user interface. Other types of menu-driven user interfaces can be specified similarly.

We need to show MAT() = {} and DMA() = {}.

Similarly, we can show DMA() = {}.

Structural icons can be regarded as composite icons with an implicit operator STC. Therefore, if is a structural icon, we have

For composite icon , the part is formally denoted by {OP, }. By that we mean , but we will formally write {OP, }. If really generates a new meaning, then the composite icon becomes once more an elementary icon, i.e.

If the purity conditions hold, this newly composed icon is also a pure icon. The implications of the purity-preserving conditions are the following: