2.  Verify  to some confidence  that indeed the region was the desired one. 
`3.  Bound the region accurately. 
`The outline  the plan generation,  scoring, and  execution  used  in the system 
`are  described  in the following  paragraphs. The  plans generated  by the system  are 
`typically  enhanced  versions  of  plans  like  the  telephone  finder.  Plan  scoring 
`proceeds as expected for such plans; allowances are made for the enhanced seman­
`tics of plan nodes. A "cost/confidence"  scoring function  is used, and various prac­
` itself. 
`tical simplifications are made that do not affect  the planning paradigm
`A n Example Plan  and  Its Execution 
`  13.2.3.  Ac­
`The system's  plans are  enhanced  plans, in  the sense  of Section
`tions can be AND,  OR or SEQUENCE actions, and shared plan structure and loops 
`are permitted.  Loops that contain  only internal, planning actions would never  ter­
`minate.  However, a loop with an OR node can terminate  (has an exit) if one of the 
`subactions of the OR is executable. A plan for locating a chair in an office  scene is 
`shown  in Fig. 13.7. In Fig. 13.7, the acquire­validate­bound  strategy is evident in 
`the two SEQUENCE subgoals of the Find Chair main goal, which is an AND goal. 
`The  loop in  the  plan  is evident,  and  makes  sense  here  because often  planning is 
`done for information gathering, not for real world actions. 
`As  noted  in  Section   13.2.3,   an  enhanced  plan  may  not  be  completely 
`specified.  If it is to be executed  one subgoal at a time  (no parallelism  is allowed), 
`sequences  of  subactions  must  be  determined  for  its  AND  and  OR  actions.  In 
`Garvey's planner,  these sequences  are determined  initially  on the basis of apriori 
`information,  but  the  partial  results  of  actions  are  "fed  back,"  so  that  dynamic 
`rescoring  and hence dynamic reordering  of goal sequences  is possible. For exam­
`ple, if one subgoal of an AND action fails, the AND action
` is  abandoned. Thus this 
`planner is to some degree incremental. 
`In  execution,  Fig.  13.7 might  result  in  the  sequence  of actions  depicted  in 
`Fig.  13.8. The  acquisition  phase  of  object  location  has  the  most  alternatives,  so 
`plan generation effort  is mainly spent there. Acquisition proceeds either directly or 
`indirectly. Direct acquisition is the classification  of input data gathered from  a ran­
`dom  sampling of a window  in the image; the input  data are rich enough  to allow 
`basic pattern recognition techniques to identify the source of individual pixels. 
`Indirect  acquisition  is  the  use  of  the  location  of  other  "objects"  (really 
`identified  regions)  in  the  scene  to  locate  the  desired  region. The  desired  region 
`might be found  by "scanning" vertically or horizontally from  the already identified 
`region,  for  instance. The  idea  is a planning  version  of  a common  one  (e.g.,  the 
`geometric  location  networks  of Section  10.3.2): use something already  located  to 
`limit and direct search for something else. 
`Plan Generation 
`A plan such as Fig. 13.7 is "elaborated" from  the basic Find Chair goal by re­
`cursively expanding goals. Some goals (such as to find a chair) are not directly exe­
`cutable; they need further  elaboration. Elaboration continues until all the subgoals 
`are  executable.  Executable  subgoals are  those  that  analyze  the  image,  run  filters 
`and detectors over parts of it, and generate decisions about the presence or absence 
`
`454 
`
`Ch.  13  Coal  Achievement 
`
`IPR2021-00921
`Apple EX1015 Page 466
`
`

`

`Fig.  13.7  An  enhanced  plan  to  locate  a  chair  in  an  office  scene.  Untied  multiple  arcs 
`denote  OR  actions,  arcs  tied  together  denote  AND  actions,  those  with  *'s  denote  SE­
`QUENCE  actions.  The  loop  in  the  plan  has  executable  exits. 
`
`IPR2021-00921
`Apple EX1015 Page 467
`
`

`

`.  V.  > 
`
`(a) 
`
`(b) 
`
`4^ 
`
`(c) 
`
`(d) 
`
`Fig.  13.8  The  plan  of  Fig.  13.7  finds  the  most  promising  execution  sequence  for  finding 
`the  chair  in  the  scene  of  Fig.  13.6:  find  the  seat  first,  then  scan  upwards  from  the  seat 
`looking  for  the  back.  Acquisition  of  the  seat  proceeds  by  sampling  (a),  followed  by 
`classification 
`(b).  The  Validation  procedure  eliminates  non­chair  points  (c),  and 
`the 
`Bounding  procedure  produces  the  seat  region  (d).  To  find  the  back,  scanning  proceeds  in 
`the  manner  indicated  by  (e)  (actually  fewer  points  are  examined  in  each  scan).  The  back 
`is acquired  and  bounded,  leading  to  the  final  location  of  the  chair  regions  (f). 
`
`456 
`
`Ch. 13  Coal Achievement 
`
`IPR2021-00921
`Apple EX1015 Page 468
`
`■
`

`

`(e) 
`
`(f) 
`
`Fig.  13.8 
`
`(com.) 
`
`of image phenomena. This straightforward  elaboration  is akin to macro expansion, 
`and  is not a very sophisticated  planning mechanism  (the program cannot  criticize 
`and  manipulate  the  plan,  only  score  it).  A fully  elaborated  plan  is presented  for 
`scoring and execution. 
`The  elaboration  process,  or  planner,  has  at  its  disposal  several  sorts  of 
`knowledge embodied  as modules  that can generate  subgoals for a goal. Some are 
`general  (to find something, find all its parts); some are less general  (a chair has a 
`back and a seat); some are quite specific,  being perhaps programs arising from  an 
`earlier interactive method­generation  phase. The elaborator  is guided by informa­
`tion stored about objects, for instance this about a tabletop: 
`
`PROPERTIES  RELATIONS 
`OBJECT 
`Table TOP  Hue:26­58 
`Supports Telephone 0.6 
`Sat.: 0.23­0.32 
`Supports Book 0.4 
`Bright.: 18­26  Occludes Wall 1 
`Height: 26­28 
`Orient.:­7­7 
`
`Here  the  orientation  information  indicates  a  vertical  surface  normal.  The 
`planner  knows that  it  has a method  of  locating  horizontal  surfaces,  and  the  plan 
`elaborator  can thus create a goal of direct acquisition by first locating a horizontal 
`plane. The relational information  allows for indirect acquisition plans. The elabora­
`tor puts direct and indirect alternatives under an OR node in the plan. Information 
`not used for acquisition  (height, color) may be used for validation. 
`Loops may occur in an elaborated  plan because each newly generated  goal is 
`checked against goals already  existing. Should  it or an equivalent  goal already ex­
`ist,  the existing goal  is substituted  for  the newly generated  one. Goals may  thus 
`have more than one ancestor, and may depend on one another. 
`
`Sec.  13.2  Planning  with  Costs 
`
`457 
`
`IPR2021-00921
`Apple EX1015 Page 469
`
`

`

`At  this stage, the planner  does not  use any planning parameters  (cost,  utili­
`ties,  etc.);   it is  strictly  symbolic.   As  mentioned  above,  important  information 
`about execution sequences in an enhanced plan is provided by scoring. 
`Plan Scoring and Execution 
`The scoring in the vision plan is a version of that explained in Sections 13.2.2 
`through  13.2.4. Each action  in  a  plan is assumed either to succeed  (S)
` in  locating 
`an object or to fail. Each action may report either success
` ("5"')   or failure.  An ac­
`tion is assumed  to report failure  correctly,  but possibly to be in error in reporting 
`success. Each action has three  "planning parameters" associated with it. They are 
`C, its "cost"  (in machine cycles), PC'S")  the probability of it reporting success, 
`and P  (S\  " 5 " ), the probability of success given a report of success. 
`As shown earlier, the product 
`P(S\"S")P("S") 
`is the probability  that  the action  has correctly  located  an object  and reported  suc­
`cess. This product is called the "confidence"  of the action. An action has structure 
`as shown in Fig. 13.9. 
`The score of an action is computed as 
`
`(13.19) 
`
`score = 
`
`^  
`confidence 
`
`(13.20) 
`
` to 
` of 
`
`The planner thus must minimize the score. 
`The  initial  planning  parameters  of  an  executable  action  typically  are  deter­
`mined by experimentation. The parameters of internal  (AND, OR,  SEQUENCE) 
`actions by scoring methods alluded to in Sections 13.2.2,
` 13.2.3,  and the Exercises 
`(there are a few idiosyncratic ad hoc adjustments.). 
`It may bear repeating that planning, scoring, and execution are not separated 
`temporally  in  this  sytem.  Scoring is used  after  the enhanced  plan  is generated
`derive a  simple  plan  (with  ordered  subgoals). Execution  can  affect  the scores
`nodes, and so execution can alternate with  "replanning"  (really rescoring  result­
`ing  in a  reordering).  Recall   the  example   of  failure   of an  AND   or  SEQUENCE 
`subgoal, which can immediately fail the entire goal. More generally, the entire goal 
`and ultimately the plan may be rescored. For instance, the parameters of a success­
`ful  action   are  modified   by  setting   the  cost   of  the  executed  action   to 0 and  its 
`confidence  to its second parameter,  P(S\"S"). 
`Given a  scored  plan, execution  is then easy; the execution program starts at 
`the top goal of the plan, working its way down the best path as defined by the scores 
`of  nodes   it  encounters.  When   an  executable  subgoal   is  found  (e.g.  "look   for a 
`green region"),  it  is passed to an evaluation function  that "runs" the action asso­
`ciated with the subgoal. 
`The  subgoal   is  either  achieved   or  not;  in  either  case, information  about
` its 
`outcome is  propagated  back   up  the  plan.  Failure   is  easy;  a  failed  subgoal   of  an 
`AND  or  SEQUENCE  goal fails  the  goal,  and  this  failure
`  is  propagated.  A  failed 
`subgoal of an OR goal is removed from  the plan. The use of success information  is 
`more complex,  involving  the adjustment  of confidences  and planning  parameters 
`illustrated above. 
`
`458 
`
`Ch.  13   Goal  Achievement 
`
`IPR2021-00921
`Apple EX1015 Page 470
`
`

`

`P  ("success") 
`
`1­P  ("success") 
`
`Detector  reports 
`"success" 
`
`Detector  reports 
`"failure" 
`
`P (object I "success" 
`
`\­P  (object|"success") 
`
`Object  present 
`
`Object  not 
`present 
`
`Correctly 
`decide object 
`present 
`
`Incorrectly 
`decide object 
`present 
`
`Fig.  13.9  This  is the  microslructure  of a  node  ("action''')  of  Garvey's  planning 
`system  in  terms  of  simple  plans.  Think  of  actions  as  being  object  detectors  which 
`announce  "Found"  or  "Not  Found."  Garvey's  planning  parameters  are 
`PO'Found")  and  P(Object  is  there|"Found").  Confidence  in  the  action  is  their 
`product;  it is the probability  of correctly  detecting  the object.  All other  outcomes 
`are lumped  together  and  not  used  for  planning. 
`
`After  the  outcome  of  a goal  is  used  to  adjust  the  parameters  of  other  goals, 
`the  plan  is rescored  and  another  cycle of  execution  performed.  The  execution  can 
`use knowledge  about  the image picked  up along the way by prior execution. This is 
`how  results  (such  as acquired  pixels)  are  passed  to later  processing  stages  (such  as 
`the validation  process). Such a mechanism  can even  be used  to remember  success­
`ful subplans for later  use. 
`
`EXERCISES 
`
`13.1  Complete  the computation  of outcome  probabilities  in the style of Section  13.2.2, 
`using  the  assumptions  given  there.  Check  your  work  by showing  (symbolically) 
`that  the probabilities  of getting to the terminal  actions  ("goal  states")  of the plan 
`sum to 1. 
`13.2  Assume  in Section  13.2.2  that  the results of  the  "table"  and  "telephone  shape" 
`detectors are not independent.  Formulate your assumptions and compute the new 
`outcome probabilities for Fig. 13.4. 
`
`Exercises 
`
`459 
`
`IPR2021-00921
`Apple EX1015 Page 471
`
`

`

`13.3  Show that 
`
`P(A 
`PKA\KBI\C)) 
`
`i( ni\C))­P(B\(AAC))P(A\C) 
`p(B]c) 
`
`13.4  Band  Care  independent  if PiB  A  C)  =  PiB)  PiC).  Assuming  that  Band  Care 
`independent, show that 
`
`P(B\C)  =  PiB) 
`PiiBAC)\A) 
`= 
`PiB\A)PiC\A) 
`PiB\iAf\C)) 
`=  PiB\A) 
`
`13.5  Starting from  the fact that 
`
`PiAABAi­O) 
`
`PiAAB)  =  PiAABAO 
`+ 
`show how P\s was computed in Section 13.2.2. 
`13.6  A sequence  DiN)  of
`  TV detectors  is used  to detect  an  object;  the detectors  either 
`succeed  or  fail.  Detector  outputs  are  assumed  independent  of each  other,  being 
`conditioned only on the object. Using previous results, show that the probability of 
`an object  being detected  by applying a sequence of N detectors D iN)  is recursively 
`rewritable  in  terms  of  the  output  of  the  first  detector  D\  and  the  remaining  se­
`quence D  iN—  1)  as 
`p(0lD(N))­P(DW)PiO\DiN^l)) 
`
`13.7  Consider scoring a plan containing an OR node (action).  Presumably, each subgoal 
`of the OR has an expected  utility.  The OR action is achieved as soon as one of the 
`subgoals is achieved. Is it possible.to order the subgoals for trial so as to maximize 
`the expected utility of the plan?  (This amounts to a unique "best" rewriting of the 
`plan to make it a simple plan.) 
`13.8  Answer question  13.7 for an AND node; remember  that  the AND will fail as soon 
`as any of  its  subgoals fails. 
`13.9  What  can you  say about  how  the cost/confidence  ratio of Garvey's  planner  is re­
`lated to the expected utility calculations of Section 13.2.2? 
`
`13.10  You are at Dandy Dan's used car lot.
` Consumer Reports says  that the a priori proba­
`bility that any car at Dandy Dan's is a lemon is high. You know, though, that to test 
`a car you kick its tire. In fact, with probability: 
`
`Pi"C" 
`
`| C)   :  a kick correctly announces "creampuff"  when the 
`car actually is a creampuff 
`P("C"|L)  : a kick incorrectly announces "creampuff"  when 
`the car is actually a lemon 
`:  the a priori probability that the car is a lemon 
`
`PiL) 
`
`Your  plan  for  dealing  with  Dandy  Dan  is shown  below; give  expressions  for  the 
`probabilities of arriving at the nodes labeled Si, S2, Fu
`  F2,   and  F3.  Give numeric 
`answers using the following values 
`
`Pi"C"\C)  =  0.5,  Pi"C"\L)  =  0.5,  PiL)  =  0.75 
`
`460 
`
`Ch.  13  Coal  Achievement 
`
`IPR2021-00921
`Apple EX1015 Page 472
`
`

`

`Kick  reports 
`"creampuff" 
`
`Kick  reports 
`"lemon" 
`
`Kick  reports 
`"creampuff" 
`
`Chevy is a 
`creampuff 
`
`Ex.  13.10 
`
`13.11  Two  bunches  of  bananas  are  in  a  room  with  a  monkey  and  a  box.  One  of  the 
`bunches  is lying  on  the  floor,  the  other  is  hanging  from  the  ceiling. One  of  the 
`bunches is made of wax. The box may be made of flimsy cardboard. Given that: 
`
`KWH)  =  0.2  :  probability that the hanging bananas are wax 
`=  0.8  :  probability that the lying bananas are wax 
`P(WL) 
`=  0.5  :  probability that the box is cardboard 
`P(C) 
`Uieat) 
`=  200: utility of eating a bunch of bananas 
`C(walk)  =   —10:  cost of walking a unit distance 
`C(push)  =  ­ 2 0: cost of pushing the box a unit distance 
`C(climb)  =   —20:  cost of climbing up on box 
`
`(a)  Analyze  two different  plans for  the monkey,  showing all paths and calcula­
`tions.  Give  criteria  (based  upon  extra  information  not  given  here)  that 
`would allow the monkey to choose between these plans. 
`
`Exercises 
`
`461 
`
`IPR2021-00921
`Apple EX1015 Page 473
`
`

`

`(b)  Suppose the monkey  knows that the probability that the box will collapse is 
`inversely  proportional  to  the  cost  of pushing  the  box  a unit  distance  (and 
`that  he  can  sense  this  cost  after  pushing  the  box  1  unit  distance).  For 
`example, 
`
`P(C)  =  1.0­  [C(push)  x  0.01] 
`P(C(push)  =  10) =  0.1 
`P(C(push)  =  20) =  0.1 
`P(C(push)  =  100) =  0.1 
`
`Repeat part (a)  (in detail). 
`
`REFERENCES 
`
`  versatile 
`
`AMBLER, A.  P.,  H.  G.  BARROW, C.  M.  BROWN, R.  M.  BURSTALL, and  R.  J.  POPPLESTONE. "A
`system  for computer  controlled assembly."  Artificial
` Intelligence  6, 2,  1975,  129­156. 
`BALLARD,  D.  H.  "Model­directed  detection  of  ribs  in  chest  radiographs."  TR11,  Computer  Science 
`Dept.,  U. Rochester,  March  1978. 
`BOLLES,  R.  C.  "Verification  vision  for  programmable  assembly."  Proc,  5th  IJCAI,  August  1977, 
`569­575. 
`BUNDY,  A. Artificial  Intelligence:  An   introductory  course.   New York: North  Holland,  1978. 
`DEGROOT,  M. H.  Optimal Statistical
` Decisions.  New York: McGraw­Hill,  1970. 
`FAHLMAN,  S.  E.  "A  planning  system  for  robot  construction  tasks."  Artificial Intelligence  5,  1,  Spring 
`1974,  1­49. 
`  SPROULL.   "Decision  theory  and  artificial  intelligence:  II. The  hungry  mon­
`FELDMAN,  J.  A.  and  R.  F.
`key."  Cognitive Science 1, 2,  1977,  158­192. 
`FELDMAN,  J.  A. and  Y.
`  YAKIMOVSKY.   "Decision  theory  and  artificial  intelligence:  I. A  semantics­based 
`  349­371. 
`region analyser."  Artificial Intelligence J, 4,  1974,
`FlKES,  R.  E. and  N.  J.
`  NILSSON.   "STRIPS:  A  new  approach  to  the  application  of  theorem  proving  to 
`problem  solving."  Artificial Intelligence 2, 3/4,  1971, 189­208. 
`FIKES,  R.  E.,  P.  E.
`  HART,   and  N.  J.
`  NILSSON.   "New  Directions  in  robot  problem  solving."  In  MI7, 
`1972a. 
`  NILSSON.   "Learning  and  executing  generalized  robot  plans." 
`  HART,   and  N.  J.
`FIKES,  R.  E.,  P.  E.
`Artificial Intelligence  J,  4,  1972b, 251­288. 
`GARVEY,  J.  D.  "Perceptual  strategies  for  purposive  vision."  Technical  Note  117,  AI Center,  SRI  Int'l, 
`1976. 
`MACKWORTH,  A.  K.  "Vision  research  strategy:  Black  magic,  metaphors,  mechanisms,  mini­worlds, 
`and  maps."  In  CVS,  1978. 
`MCCARTHY,  J.  and  P. J.
`  HAYES.   "Some  philosophical  problems  from  the  standpoint  of artificial  intelli­
`gence." In MI4,  1969. 
`NILSSON, N. J.
` Principles  of Artificial  Intelligence.  Palo Alto, CA: Tioga  Publishing  Company,  1980. 
`RAIFFA,  H. Decision Analysis.  Reading,  MA: Addison­Wesley,  1968. 
`SACERDOTI,  E.  D.  "Planning  in  a  hierarchy  of  abstraction  spaces."  Artificial  Intelligence  J,  2,  1974, 
`115­135. 
` Behavior.  New  York:  Elsevier,  1977. 
`SACERDOTI,  E. D. A Structure for  Plans and
`SHIRAI,  Y. "Analyzing  intensity  arrays  using knowledge  about  scenes." In  PCV,  1975. 
`
`462 
`
`Ch.  13  Coal
`
` Achievement 
`
`IPR2021-00921
`Apple EX1015 Page 474
`
`

`

`  MYCIN.   New  York:  American  Elsevier, 
`
`SHORTLIFFE,  E.  H.  Computer­Based  Medical  Consultations:
`1976. 
`SPROULL,  R.  F.  "Strategy  construction  using a synthesis  of heuristic  and  decision­theoretic  methods." 
`Ph.D.  dissertation,  Dept. of Computer  Science, Stanford  U.,  May  1977. 
`SUSSMAN, G. J. A Computer Model of Skill
` Acquisition.  New  York:  American  Elsevier,  1975. 
`TATE,  A.  "Generating  project  networks."  Proc,  5th  IJCAI,  August  1977, 888­983. 
`WARREN,  D.  H.  D. "WARPLAN:  A system  for  generating  plans."  Memo  76,  Dept.  of  Computational 
`Logic,  U. Edinburgh,  June  1974. 
`
`References 
`
`463 
`
`IPR2021-00921
`Apple EX1015 Page 475
`
`

`

`Some 
`Mathematical Tools 
`
`Appendix 1 
`
`A1.1  COORDINATE  SYSTEMS 
`
`A1.1.1  Cartesian 
`
`The  familiar  two­ and  three­dimensional  rectangular  (Cartesian)  coordinate sys­
`tems are the  most generally  useful  ones  in describing geometry for  computer vi­
`sion. Most common is a right­handed three­dimensional  system  (Fig. ALL). The 
`coordinates  of  a point  are  the  perpendicular  projections  of  its  location  onto  the 
`coordinate axes. The two­dimensional coordinate system divides two­dimensional 
`space  into  quadrants,  the  three­dimensional  system  divides  three­space  into oc­
`tants. 
`
`A1.1.2  Polar and Polar Space 
`
`Coordinate systems that measure locations partially in terms of angles are in many 
`cases more natural than Cartesian coordinates.  For instance, locations with respect 
`
`~T 
`
`x
`
`Fig.  Al.l  Cartesian  coordinate  systems. 
`
`465 
`
`IPR2021-00921
`Apple EX1015 Page 476
`
`

`

`to the pan­tilt head of a camera or a robot arm may most naturally be described us­
`ing angles. Two­ and three­dimensional polar coordinate systems are shown in Fig. 
`A1.2. 
`
`Cartesian Coordinates  Polar Coordinates 
`p  cos 9 
`x 
`p  sin 0 
`P 
`
`2)'A 
`
`bc2+y
`tan ­l 
`
`9 
`
`Cartesian Coordinates   Polar  Space Coordinates 
`(x, y,  z) 
`(p  cos £, p  cos
` 17,  p cos £) 
`(x2+y2  +  z 2)» 
`P 
`
`t 
`
`cos 
`
`cos ­1 
`
`cos ­1 
`
`In these coordinate systems, the Cartesian quadrants or octants in which points fall 
`are often  of interest  because many trigonometric functions  determine only an an­
`gle modulo  IT  12  or  TT   (one or two quadrants) and more information  is necessery to 
`determine  the quadrant.  Familiar examples are the inverse angle functions  (such 
`as arctangent), whose results are ambiguous between two angles. 
`
`A1.1.3  Spherical and Cylindrical 
`
`The spherical and cylindrical systems are shown in Fig. A 1.3. 
`
`x
`
`Fig.  A1.2  Polar  and  polar  space 
`coordinate  systems. 
`
`466 
`
`App.  7  Some  Mathematical  Tools 
`
`IPR2021-00921
`Apple EX1015 Page 477
`
`

`

`z 
`
`z 
`
`Fig.  A1.3  Spherical  and  cylindrical 
`coordinate  systems. 
`
`Cartesian Coordinates  Spherical Coordinates 
`x 
`p  sin 0  cos 9 . 
`y 
`p  sin 0  sin 9 = x  tan 0 
`z  p cos 0 
`
`tan" 
`
`cos ­l 
`
`Cartesian Coordinates  Cylindrical Coordinates 
`r cos 9 
`x 
`r  sin 9 
`y 
`
`(x2+y2)* 
`
`tan ­l 
`
`r 
`
`0 
`
`A1.1.4  Homogeneous  Coordinates 
`
`Homogeneous  coordinates  are  a very  useful  tool  in  computer  vision  (and  com­
`puter graphics)  because  they allow many important  geometric  transformations  to 
`be represented uniformly  and elegantly  (see Section A 1.7). Homogeneous coordi­
`nates are redundant: a point in Cartesian  «­space is represented by a line in homo­
`geneous  (n  +  1)­space.  Thus  each  (unique)  Cartesian  coordinate  point 
`corresponds to infinitely  many homogeneous coordinates. 
`
`Cartesian Coordinates 
`(x, y,  z) 
`
`Homogeneous Coordinates 
`(wx, wy, wz, w) 
`
`2. 
`w 
`
`(x, y,  z,  w) 
`
`Sec. A1.1  Coordinate  Systems 
`
`467 
`
`IPR2021-00921
`Apple EX1015 Page 478
`
`

`

`Here x, y,  z, and   w  are real numbers,  wx,  wy, and
`reals, and x/wand so on are the indicated quotients. 
`
`  wz  are  the products of the two 
`
`A1.2.  TRIGONOMETRY 
`
`A1.2.1  Plane Trigonometry 
`
`Referring  to Fig. A 1.4,  define 
`
`sine: 
`
`sin (A)  (sometimes sin A)  = — 
`
`cosine: 
`
`cos (A)  (or cos A)  =
`
`tangent: 
`
`tan (A)  (or tan A)  =  4 
`
`  — 
`c 
`
`c
`
`b 
`­1 ,  cos ­1 ,  tan ­1 ) 
`The inverse functions  arcsin,  arccos, and arctan  (also written  sin
`map a value into an  angle.   There are many useful  trigonometric identities; some of 
`the most common are the following. 
`
`/  >. 
`. 
`tan  \x)  = 
`
`\ 
`
`( 
`t  
`sin 6c)
`TT   =   ­tan(­x) 
`cos  U) 
`  —   sin  (x)  cos  (y)  + cos  (x)  sin  (y) 
`sin  (x  + y)
`  —   sin  (x)  sin  (y) 
`cos  (x  + y)  = cos  (x)  cos  (y)
`tan  (x)  +  tan  (y) 
`1  +  tan  (x)  tan(y) 
`
`tan  (x  ±   y)   — 
`
`In any triangle with angles A, B, C opposite sides a, b, c, the Law of Sines holds: 
`a 
`b 
`c 
`sin A 
`sin  B 
`sin  C 
`
`as does the Law of Cosines: 
`
`a2  =  b 2  + c 2 ­2bc  cos A 
`a  =  b cos  C  +  c cos B 
`
`468 
`
`App.  7  Some  Mathematical  Tools 
`
`C" 
`
`Fig.  A1.4  Plane right triangle. 
`
`IPR2021-00921
`Apple EX1015 Page 479
`
` 
`

`

`A1.2.2.  Spherical Trigonometry 
`
`The sides of a spherical  triangle  (Fig. A1.5)  are measured  by the angle  they sub­
`tend  at the  sphere center;  its angles  by the angle they  subtend  on  the face of the 
`sphere. 
`Some useful spherical trigonometric identities are the following. 
`sin A 
`sin  B  _  sin C 
`sin  a 
`sin  b 
`sin c 
`
`cos a  =  cosb  cose  +  smb  sine
`
`  cos ,4   = 
`
`cos b  cos (c  ±   9) 
`COS0 
`
`Where  tan 9 = tan b
` cos  A, 
`cos A  =   —cos  B  cos C +  sin B  sin C  cos a 
`
`A1.3.  VECTORS 
`
` a 
`
`Vectors are both a notational convenience and a representation of a geometric con­
`cept. The familiar  interpretation of a vector v as a directed line segment allows for
`geometrical  interpretation  of  many  useful  vector  operations  and  properties.  A 
`more general notion of an  ^­dimensional vector v =  (v
`l7  v 2, . . ..  v /;)  is that of an 
`/7­tuple abiding by mathematical laws of composition and transformation.  A vector 
`may be written horizontally  (a row vector) or vertically  (a column vector). 
`A point in «­space is characterized by its n coordinates, which are often  writ­
`ten as a vector.  A point at X,  Y, Z coordinates x, y,  and z is written as a vector x 
`whose  three  components  are  (x, y,  z).  Such  a  vector  may  be  visualized  as  a 
`directed  line  segment,  or  arrow,  with  its  tail  at  the  origin  of  coordinates  and  its 
`head at the point at  (x, y,  z). The same vector may represent instead the direction 
`in which it  points—toward  the  point  (x, y,  z) starting from  the origin. An  impor­
`tant  type of direction  vector  is the normal vector,  which is a vector in a direction 
`perpendicular to a surface, plane, or line. 
`Vectors of equal dimension are equal if they are equal componentwise. Vec­
`tors may be multiplied  by scalars. This corresponds  to stretching  or shrinking  the 
`vector arrow along its original direction. 
`
`Xx  =  (kX\,  kx2, 
`
`...,  A.x
`
`/7) 
`
`Sec. AT.3  Vectors 
`
`469 
`
`Fig.  A1.5  Spherical triangle. 
`
`IPR2021-00921
`Apple EX1015 Page 480
`
`

`

`Vector addition  and  subtraction  is denned  componentwise,  only between  vectors 
`of equal dimension. Geometrically,  to add two vectors x and y, put y's tail at  x's 
`head and the sum is the vector from  x's tail to y's head.  To subtract y from  x, put 
`y's head at x's head; the difference  is the vector from  x's tail to y's tail. 
`
`x  ±   y =  Gci  ±   y h  x 2  ±   y 2,  ...,  x n  ±   y„) 
`The length  (or magnitude)  of a vector is computed by an ^­dimensional version of 
`Euclidean distance. 
`
`2  +  • • •  + x n
`|x|=  (x, 2  +x 2
`2)» 
`A  vector of unit length  is a unit vector. The unit vectors in the three usual Carte­
`sian coordinate directions have special names. 
`
`i =  (1, 0, 0) 
`j =  (0,  1, 0) 
`k=  (0,0,  1) 
`The inner  (or scalar, or dot) product of two vectors is defined as follows. 
`  + x„y„ 
`x  • y =  |x||y|cos0  ­   x lyl  +  x 2y2  +   ­ • •
`Here  9  is  the  angle  between  the  two  vectors.  The  dot  product  of  two  nonzero 
`numbers is 0 if and only if they are orthogonal  (perpendicular). The projection of
`onto y (the component of vector x in the direction y) is 
`
` x 
`
`x  •  y 
`„ 
`ii 
`|x|cos0  =  ­ j ­ r­
`
`Other identities of interest: 
`
`x  •   y =  y  •  x 
`x ­ (y  +  z)  =  x ­y  +  x ­z 
`A(x­y)  =  (Xx)  ­ y=  x­  Uy) 
`2 
`x  x =  |x|
`
`The cross  (or vector)  product of two three­dimensional  vectors is defined  as 
`follows. 
`
`2y3  ­   x 3y2,  x 3y{  ­  x^ 3,  X\y 2  ­  x 2y{) 
`x  x  y =  (x
`Generally,  the cross product of x and y is a vector perpendicular  to both x and y. 
`The magnitude of the cross product depends on the angle 0 between  the two vec­
`tors. 
`
`|x  x  y|=  |x||y|sin0 
`Thus  the  magnitude  of  the  product  is zero  for  two nonzero  vectors if and  only if 
`they are parallel. 
`Vectors and matrices allow for the short formal expression of many symbolic 
`
`4 70 
`
`App.  7  Some  Mathematical  Tools 
`
`IPR2021-00921
`Apple EX1015 Page 481
`
`

`

`expressions.  One such  example  is the  formal  determinant  (Section  A 1.4)  which 
`expresses the definition  of the cross product given above in a more easily remem­
`bered form. 
`
`Also, 
`
`x  x  y =  det 
`
`i 
`
`*i 
`y\ 
`
`j  kj 
`x2 
`x 3 
`
`yi 
`
`y?> 
`
`x  X y =  ­y
`  X   x 
`X X ( y ± z)  =  x X y ± X X Z 
`X(x  x  y)  =  Xx x  y =
`  x   x Xy 
`i  x j  =  k 
`j  x  k =  i 
`k  x  i =  j 
`
`The triple scalar product is x • (y  x  z), and is equivalent  to the value of the 
`determinant 
`
`det 
`
`X] 
`y\ 
`Z) 
`
`x2 
`yi 
`*2 
`
`*3 
`^3 
`Z3. 
`
`The triple vector product is 
`xx  (y  x  z)  =  (x
`
`  •   z)y ­  (x
`
`  •  y)z 
`
`A1.4.  MATRICES 
`
` n  columns 
` if it has m rows and
`A matrix A is a two­dimensional  array of elements;
`it is of dimension  m x  «, and  the element  in the  /th  row and y'th column  may be 
`named  ay. If  m or  n  =  1, a row  matrix  or column  matrix  results,  which  is  often 
`called  a vector.  There  is considerable  punning  among  scalar,  vector  and  matrix 
`representations and operations when the same dimensionality is involved  (the
`1 matrix may sometimes be treated as a scalar, for instance). Usually, this practice 
`is harmless, but occasionally the difference  is important. 
`A matrix  is sometimes  most naturally  treated as a collection  of vectors, and 
`sometimes an m x   n  matrix Mis written as 
`M  =  [ai  a 2 
`
`• •  •   a„] 
`
`  1   x 
`
`Sec. ATA  Matrices 
`
`471 
`
`IPR2021-00921
`Apple EX1015 Page 482
`
`

`

`or 
`
`b, 
`b2 
`
`M  = 
`
`where the a's are column vectors and the b's are row vectors. 
`Two matrices A and B are equal if their dimensionality  is the same and they 
`are equal eiementwise. Like a vector, a matrix may be multiplied  (eiementwise) by 
`a scalar.  Matrix addition  and subtraction  proceeds eiementwise between  matrices 
`of like dimensionality. For a scalar
` A: and matrices A,  B, and C of
` like  dimensional­
`ity the following is true. 
`
`C  = AB  where an element  c
`
`A  =  B  ±   C 
`1  <  /  <  m, 
`if  a ij=  bij  ±   c L 
`Two matrices A  and  B are  conformable  for  multiplication  if the  number  of 
`columns of A equals the number of rows of
` B.  The product is defined as 
`fl *^y 
`u =  £  
`u  is defined by  c
`k 
`Thus  each  element  of  C is computed  as  an  inner  product  of  a  row  of A  with a 
`column of  B.  Matrix multiplication  is associative but not commutative in general. 
`The  multiplicative identity  in matrix algebra is called the identity matrix  /. /
` is  all 
`zeros except that all elements in its main diagonal have value
` 1  (ay =   1   if /=y, else 
`atj  = 0). Sometimes the n  x
`  n  identity matrix is written /„. 
` T  such  that  the 
`The  transpose  of an  m  x  n matrix  A is the  n  x  m matrix  A
` T . If A  T =A,Ais 
`ijth  element of A is they',/th element of A
`symmetric. 
`  n  matrix  ,4  is written^" 1. If it exists, then 
`The inverse matrix of an n  x
`AA~l  = A~ lA  =  / 
`If its inverse does not exist, an n  x
`  A? matrix is called singular. 
`With  k  and  p scalars,  and  A,  B,  and  C  m  x  n matrices,  the  following  are 
`some laws of matrix algebra (operations are matrix operations): 
`
`A  + B  = B  + A 
`(A  + B)  +  C = A  +  (B  +  C) 
`k(A  + B)  =  kA  +  kB 
`(k  + p)A  = kA  + pA 
`AB  j*  BA 
`in general 
`(AB)C  =  A(BC) 
`A(B  +  C)  =  AB  +AC 
`(A  + B)C  = AC  +  BC 
`
`472 
`
`App.  7  Some  Mathematical  Tools 
`
`IPR2021-00921
`Apple EX1015 Page 483
`
`

`

`AikB)  = k(AB)  =  (kA)B 
`
`lmA  =  Al n  =  A 
`{A  + B 1)  = A T+  B T 
`(AB)T=  B TAT 
`(AB)~l  =   B­
`]A~] 
`
`The determinant  of an  n  x  n matrix  is an important  quantity; among  other 
`things, a matrix with zero determinant is singular.  Let Ay be the (n
` —  1) x  («  —  1) 
`matrix resulting from deleting the /th row andyth column from an n  x
`  n  matrix A. 
`The determinant of a  1   x   1   matrix is the value of its single element. For n  >  1, 
`
`detA=Jt 
`
`i=\ 
`
`a­.j
`
`  (­D /+ydeti4tf 
`
`for  any j  between  1 and  n. Given  the  definition  of determinant,  the inverse of a 
`matrix may be defined as 
`
`K 
`
`,,J  
`
`( ­ l ) ^ d e t ^, 
`detA 
`
`In practice,  matrix  inversion  may be a difficult  computational  problem,  but 
`this  important  algorithm  has  received  much  attention,  and  robust  and  efficient 
`methods  exist  in the literature,  many of which  may also be used  to compute  the 
`determinant.  Many  of  the  matrices  arising  in  computer  vision  have  to  do  with 
`geometric  transformations,  and  have well­behaved  inverses corresponding  to the 
`inverse transformations. Matrices of small dimensionality are usually quite compu­
`tationally tractable. 
`Matrices are often  used  to denote  linear  transformations;  if
` a  row  (column) 
`matrix X of dimension  n  is post  (pre) multiplied by an n  x  n matrix A, the result X' 
`=  XA  (X'  =  AX)  is another  row  (column)  matrix,  each of  whose  elements  is a 
`linear combination  of the elements of
` X,  the weights being supplied by the values 
`of A.   By employing  the common  pun between row matrices and vectors, x'  =  xA 
`(x'  =  A x) is often written for a linear transformation  of a vector x. 
`An eigenvector of an n  x
`  n  matrix A is a vector v such that for some scalar
`(called an eigenvalue), 
`
` X 
`
`\A  =  \v 
`That is, the linear transformation  A operates on
` v  just as a scaling operation. A ma­
`trix has  n  eigenvalues, but in general they may be complex and of repeated values. 
`The computation  of eigenvalues and eigenvectors of matrices is another  computa­
`tional problem of major  importance, with good algorithms for general matrices be­
`ing complicated. The n eigenvalues are roots of the so­called characteristic polyno­
`mial resulting from setting a formal determinant to zero: 
`
`det  (A  ­  kl)  = 0. 
`
`Sec. ATA  Matrices 
`
`473 
`
`IPR2021-00921
`Apple EX1015 Page 484
`
`

`

`Eigenvalues  of matrices  up to 4