advertisement

advertisement

Information about Qualitative Spatial Reasoning: Cardinal Directions as an Example

My presentation of Dr. Frank's 1995 paper. Not suitable as a substitute for reading the original work, but the visualizations may be helpful.

advertisement

Outline 2

Outline • Introduction 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? • Method: An algebraic approach 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? • Method: An algebraic approach • Two cardinal direction systems 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? • Method: An algebraic approach • Two cardinal direction systems - Cone-shaped directions 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? • Method: An algebraic approach • Two cardinal direction systems - Cone-shaped directions - Projection-based directions 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? • Method: An algebraic approach • Two cardinal direction systems - Cone-shaped directions - Projection-based directions • Assessment 2

Outline • Introduction • Motivation: Why qualitative? Why cardinal? • Method: An algebraic approach • Two cardinal direction systems - Cone-shaped directions - Projection-based directions • Assessment • Research envisioned 2

Introduction Geography utilizes large scale spatial reasoning extensively. • Formalized qualitative reasoning processes are essential to GIS. • An approach to spatial reasoning using qualitative cardinal directions. 3

Motivation: Why qualitative? Spatial relations are typically formalized in a quantitative manner with Car tesian coordinates and vector algebra. 4

Motivation: Why qualitative? 5

Motivation: Why qualitative? 5

Motivation: Why qualitative? 5

Motivation: Why qualitative? “thirteen centimeters” 5

Motivation: Why qualitative? Human spatial reasoning is based on qualitative comparisons. 6

Motivation: Why qualitative? Human spatial reasoning is based on qualitative comparisons. 6

Motivation: Why qualitative? Human spatial reasoning is based on qualitative comparisons. “longer” 6

Motivation: Why qualitative? Human spatial reasoning is based on qualitative comparisons. “longer” • precision is not always desirable 6

Motivation: Why qualitative? Human spatial reasoning is based on qualitative comparisons. “longer” • precision is not always desirable • precise data is not always available 6

Motivation: Why qualitative? Human spatial reasoning is based on qualitative comparisons. “longer” • precision is not always desirable • precise data is not always available • numerical approximations do not account for uncertainty 6

Motivation: Why qualitative? 7

Motivation: Why qualitative? • For malization required for GIS implementation. 7

Motivation: Why qualitative? • For malization required for GIS implementation. • Interpretation of spatial relations expressed in natural language. 7

Motivation: Why qualitative? • For malization required for GIS implementation. • Interpretation of spatial relations expressed in natural language. • Comparison of semantics of spatial terms in different languages. 7

Motivation: Why cardinal? 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): • direction north, northwest 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): • direction north, northwest • topological disjoint, touches 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): • direction north, northwest • topological disjoint, touches • ordinal in, at 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): • direction north, northwest • topological disjoint, touches • ordinal in, at • distance far, near 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): • direction north, northwest • topological disjoint, touches • ordinal in, at • distance far, near • fuzzy next to, close 8

Motivation: Why cardinal? Pullar and Egenhofer’s geographical scale spatial relations (1988): • direction north, northwest • topological disjoint, touches • ordinal in, at • distance far, near • fuzzy next to, close Cardinal direction chosen as a major example. 8

Method: An algebraic approach 9

Method: An algebraic approach • Focus on not on directional relations between points... 9

Method: An algebraic approach • Focus on not on directional relations between points... • Find rules for manipulating directional symbols & operators. 9

Method: An algebraic approach • Focus on not on directional relations between points... • Find rules for manipulating directional symbols & operators. Directional symbols: N, S, E, W... NE, NW... Operators: inv ∞ () 9

Method: An algebraic approach • Focus on not on directional relations between points... • Find rules for manipulating directional symbols & operators. Directional symbols: N, S, E, W... NE, NW... Operators: inv ∞ () • Operational meaning in a set of formal axioms. 9

Method: An algebraic approach Inverse Composition Identity 10

Method: An algebraic approach Inverse P2 P1 Composition Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) P1 Composition Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition P2 P1 P3 Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition P2 dir(P1,P2) P1 P3 Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition P2 dir(P1,P2) dir(P2,P3) P1 P3 Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition P2 dir(P1,P2) dir(P2,P3) P1 P3 dir(P1,P2) ∞ dir(P2,P3) dir (P1,P3) Identity 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition P2 dir(P1,P2) dir(P2,P3) P1 P3 dir(P1,P2) ∞ dir(P2,P3) dir (P1,P3) Identity P1 10

Method: An algebraic approach Inverse P2 dir(P1,P2) inv(dir(P1,P2)) P1 Composition P2 dir(P1,P2) dir(P2,P3) P1 P3 dir(P1,P2) ∞ dir(P2,P3) dir (P1,P3) Identity P1 dir(P1,P1)=0 10

Method: Euclidean exact reasoning 11

Method: Euclidean exact reasoning • Comparison between qualitative reasoning and quantitative reasoning using analytical geometry 11

Method: Euclidean exact reasoning • Comparison between qualitative reasoning and quantitative reasoning using analytical geometry • A qualitative rule is called Euclidean exact if the result of applying the rule is the same as that obtained by analytical geometry 11

Method: Euclidean exact reasoning • Comparison between qualitative reasoning and quantitative reasoning using analytical geometry • A qualitative rule is called Euclidean exact if the result of applying the rule is the same as that obtained by analytical geometry • If the results differ, the rule is considered Euclidean approximate 11

Two cardinal system examples Cone-shaped Projection-based N NW NE NW N NE W E W Oc E SW SE SW S SE S “relative position of points “going toward” on the Earth” 12

Directions in cones N NW NE W E SW SE S 13

Directions in cones N • Angle assigned to nearest NW NE named direction • Area of acceptance increases W E with distance SW SE S 13

Directions in cones N NW NE W E SW SE S 13

Directions in cones N NW NE W E SW SE S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: W E SW SE S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE SW SE S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE SW SE S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol: e⁸(N)= N 14

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 15

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 15

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 15

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W 0 E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 15

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n e(N) ∞ inv (N) 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n e(N) ∞ inv (N) 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n e(N) ∞ inv (N) 16

Directions in cones N Algebraic operations can be NW NE performed with symbols: • 1/8 turn changes the symbol: W 0 E e(N)=NE • 4/8 turn gives the inverse symbol: SW SE e⁴(N)= inv(N) = S S • 8/8 turn gives the identity symbol, 0: e⁸(N)= N = 0 • Composition can be computed with averaging rules: e(N) ∞ N = n e(N) ∞ inv (N) 16

Cone direction composition table 17

Cone direction composition table 17

Cone direction composition table Out of 64 combinations, only 10 are Euclidean exact. 17

Projection-based directions 18

Projection-based directions W E 18

Projection-based directions N S 18

Projection-based directions NW NE SW SE 18

Projection-based directions • With half-planes, only trivial NW NE cases can be resolved: NE ∞ NE = NE SW SE 18

Projection-based directions NW N NE W Oc E SW S SE 19

Projection-based directions • Assign neutral zone in the NW N NE center of 9 regions W Oc E SW S SE 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E SW S SE 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S • Composition combines each projection: 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S • Composition combines each projection: NE ∞ SW = 0 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S • Composition combines each projection: NE ∞ SW = 0 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S • Composition combines each projection: NE ∞ SW = 0 S ∞ E = SE 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S • Composition combines each projection: NE ∞ SW = 0 S ∞ E = SE 19

Projection-based directions Algebraic operations can be NW N NE performed with symbols: W Oc E • The identity symbol, 0, resides in the neutral area. SW S SE • Inverse gives the symbol opposite the neutral area: inv(N) = S • Composition combines each projection: NE ∞ SW = 0 S ∞ E = SE 19

Projection composition table 20

Projection composition table 20

Projection composition table Out of 64 combinations, 32 are Euclidean exact. 20

Assessment 21

Assessment • Both systems use 9 directional symbols. 21

Assessment • Both systems use 9 directional symbols. • Cone-shaped system relies on averaging rules. 21

Assessment • Both systems use 9 directional symbols. • Cone-shaped system relies on averaging rules. • Introducing the identity symbol 0 increases the number of deductions in both cases. 21

Assessment • Both systems use 9 directional symbols. • Cone-shaped system relies on averaging rules. • Introducing the identity symbol 0 increases the number of deductions in both cases. • There are fewer Euclidean approximations using projection-based directions: 21

Assessment • Both systems use 9 directional symbols. • Cone-shaped system relies on averaging rules. • Introducing the identity symbol 0 increases the number of deductions in both cases. • There are fewer Euclidean approximations using projection-based directions: ‣ 56 approximations using cones 21

Assessment • Both systems use 9 directional symbols. • Cone-shaped system relies on averaging rules. • Introducing the identity symbol 0 increases the number of deductions in both cases. • There are fewer Euclidean approximations using projection-based directions: ‣ 56 approximations using cones ‣ 32 approximations using projections 21

Assessment 22

Assessment • Both theoretical systems were implemented and compared with actual results to assess accuracy: 22

Assessment • Both theoretical systems were implemented and compared with actual results to assess accuracy: ‣ Cone-shaped directions correct in 25% of cases. 22

Assessment • Both theoretical systems were implemented and compared with actual results to assess accuracy: ‣ Cone-shaped directions correct in 25% of cases. ‣ Projection-based directions correct in 50% of cases. 22

Assessment • Both theoretical systems were implemented and compared with actual results to assess accuracy: ‣ Cone-shaped directions correct in 25% of cases. ‣ Projection-based directions correct in 50% of cases. - 1/4 turn off in only 2% of cases 22

Assessment • Both theoretical systems were implemented and compared with actual results to assess accuracy: ‣ Cone-shaped directions correct in 25% of cases. ‣ Projection-based directions correct in 50% of cases. - 1/4 turn off in only 2% of cases - deviations in remaining 48% never greater than 1/8 turn 22

Assessment • Both theoretical systems were implemented and compared with actual results to assess accuracy: ‣ Cone-shaped directions correct in 25% of cases. ‣ Projection-based directions correct in 50% of cases. - 1/4 turn off in only 2% of cases -deviations in remaining 48% never greater than 1/8 turn • Projection-based directions produce a result that is within 45˚ of actual values in 80% of cases. 22

Research envisioned 23

Research envisioned Formalization of other large-scale spatial relations using similar methods: 23

Research envisioned Formalization of other large-scale spatial relations using similar methods: • Qualitative reasoning with distances 23

Research envisioned Formalization of other large-scale spatial relations using similar methods: • Qualitative reasoning with distances • Integrated reasoning about distances and directions 23

Research envisioned Formalization of other large-scale spatial relations using similar methods: • Qualitative reasoning with distances • Integrated reasoning about distances and directions • Generalize distance and direction relations to extended objects 23

Conclusion 24

Conclusion • Qualitative spatial reasoning is crucial for progress in GIS. 24

Conclusion • Qualitative spatial reasoning is crucial for progress in GIS. • A system of qualitative spatial reasoning with cardinal directions can be formalized using an algebraic approach. 24

Conclusion • Qualitative spatial reasoning is crucial for progress in GIS. • A system of qualitative spatial reasoning with cardinal directions can be formalized using an algebraic approach. • Similar techniques should be applied to other types of spatial reasoning. 24

Conclusion • Qualitative spatial reasoning is crucial for progress in GIS. • A system of qualitative spatial reasoning with cardinal directions can be formalized using an algebraic approach. • Similar techniques should be applied to other types of spatial reasoning. • Accuracy cannot be found in a single method. 24

Subjective impact A new sidewalk decal designed to help pedestrians ﬁnd their way in New York City. 25

Questions? Qualitative Spatial Reasoning: Cardinal Directions as an Example Andrew U. Frank 1995 26

Research Article Qualitative spatial reasoning: cardinal directions as an example ANDREW U. FRANK Department of Geoinformation, Technical University of ...

Read more

... cardinal directions, a completely qualitative ... spatial reasoning: cardinal directions as an example ... Qualitative spatial reasoning: cardinal ...

Read more

Qualitative Spatial Reasoning: Cardinal Directions as an Example1 ... for example cardinal directions are ... "Qualitative Spatial Reasoning about Cardinal ...

Read more

Qualitative Spatial Reasoning: Cardinal ... Reasoning: Cardinal Directions as an Example} ... cardinal directions, a completely qualitative ...

Read more

Qualitative Spatial Reasoning: Cardinal Directions as an Example1 AndrewU.Frank DepartmentofGeoinformation ... Two Examples of Systems of Cardinal Directions

Read more

Qualitative Spatial Reasoning with Cardinal ... Qualitative spatial reasoning ... 4 • Two Examples of Systems of Cardinal Directions Two examples ...

Read more

... Qualitative Spatial Reasoning: Cardinal ... cardinal directions as an example of spatial ... qualitative spatial reasoning with cardinal ...

Read more

... Qualitative Spatial Reasoning: Cardinal ... Reasoning: Cardinal Directions as an Example ... increasing interest on qualitative spatial ...

Read more

Qualitative Spatial Reasoning about Cardinal ... spatial properties. The most common examples are ... reasoning with cardinal directions between point ...

Read more

## Add a comment