An algorithmic approach to detect generalization in sketch maps from sketch map alignment

Abstract

Sketch maps are valuable tools used across various disciplines including spatial cognition, environmental psychology, and spatial reasoning. A common approach to evaluate sketch maps in research is to align and compare them with metric maps. However, sketch maps are highly abstract and contain generalized information causing difficulty in their alignment. Current approaches to study sketch maps cannot handle generalized information. They require a one-on-one correspondence between features in the metric map and features in the sketch map. But memory is often generalized. This paper makes two contributions to the research on sketch maps: (i) we present an algorithmic approach to detect generalization in sketch maps (ii) we present an online tool that creates a generalized metric map corresponding to features in sketch maps. Previously, we identified nine types of generalization in sketch maps. In this paper, we develop formal operators to detect these generalizations and implement them as an online tool. We evaluated our algorithm with a set of 11 sketch maps containing 84 instances of generalization. The results indicated that our algorithm consistently detects instances of generalization in sketch maps.

1 Introduction

Sketch maps are hand-drawn abstract representations of spatial information considered to be externalization of one’s acquired spatial knowledge. They have wide-ranging applications across multiple domains. In environmental psychology, sketch maps are used to analyze how individuals perceive their environment [1–3]. Oftentimes, they are integrated with traditional GIS approaches to do spatial analysis such as analyzing human emotions [4–6]. They are also used as a Volunteered Geographic Information tool to collect data for urban planning, disaster management, etc. [7–10]. One common process that sketch maps go through is manual alignment with metric maps or any target environment. This is because sketch maps, being hand-drawn and subject to individual differences, are often incomplete, distorted, fragmented, and generalized representations of the environment. Therefore, a 1:1 alignment with a metric map is crucial to ensure that sketched data are understood and comparable in a standardized manner. Manually aligning corresponding features is a tedious and error-prone process because in real-world experiments it is rare that all features in a sketch map have a 1:1 relationship with features in a metric map. During sketching, people do not follow any consistent rules of generalization, resulting in an inconsistently generalized sketch map wherein some features are not generalized, some are omitted, some features are merged, and others are collapsed to a point. An unbiased alignment requires systematic identification and resolution of these generalizations in sketch map.

Our earlier work [11] on generalization in sketch maps identified nine distinct types of generalization [11]. In the current paper, we present an algorithmic approach to automatically detect and resolve these generalizations which may contain 1: 1, 1: M, or even M: N alignments. To resolve the 1: M or M: N alignments, we generalize the metric map to match the specific sketch map resulting in a 1: 1 alignment. Our approach to deal with generalization can be used in many different existing sketch map analysis approaches. We tested our algorithm on a set of 11 sketch maps containing 84 generalized features and found that our algorithm detected all generalizations, unlike human raters who failed to identify generalizations in complex sketch maps. The algorithm has been implemented as an online tool and integrated with the sketch map analysis method “SketchMapia” [12].

We present sketch map analysis as a use case where generalization in sketch maps is a significant problem and requires consistent identification. Following this, we provide an overview of related works (section 2). A detailed explanation of our algorithmic implementation can be found in section 3. Evaluation of our algorithm is presented in section 4 followed by the conclusion (section 5).

1.1 Use case 1: Sketch map analysis

Several studies have demonstrated that sketch maps are reliable predictors of spatial learning and navigation performance [13–15]. While sketch map contains extensive information on an individual’s spatial knowledge, analyzing this information is complicated. Some of the existing methods for sketch map analysis are measuring completeness [1] by manually counting features, qualitative accuracy by checking whether the same topological relations hold between aligned features in sketch map and metric map [16, 17], and quantitative measures such as overall configurational accuracy [18, 19] using bi-dimensional regression. All these methods are based on a pairwise comparison requiring a one-on-one alignment between features in the sketch map and features in the metric map. For example, a landmark drawn as a single polygon with the label "school" in the sketch map must be aligned with a single polygon in the metric map, even if the actual school consists of many buildings and is represented in the metric map as a set of polygons (Fig 1).

[Figure omitted. See PDF.]

Yellow features are generalized leading to an unclear alignment.

The lack of a standardized procedure to resolve generalization in sketch maps may result in biased analysis. Fig 1 shows a metric map along with two probable sketch maps. While some features in these maps have 1: 1 correspondence, other features (highlighted in yellow) are obviously generalized. It is unclear how these features are to be aligned. For instance, one could align feature "S15" in sketch B labeled as ’shops’ with either one of "33", "34", or "35" in the metric map or one could also align "S15" to "33", "34", and "35" together, but then it becomes a 1: M alignment. As there exists no approach to resolve generalization in sketch maps, researchers may focus only on a subset of features that has a one-on-one match ignoring the generalized content leading to information loss. Our algorithm reduces the laborious manual task of resolving generalization by converting group alignments to 1:1 alignment.

2 Related works

2.1 Generalized features: An issue in sketch map alignment

Generalization is an inherent characteristic of sketch maps that undermines their usability. In the field of sketch map analysis, the simplest method of analyzing a sketch map is to count the number of features drawn relative to the metric map termed "completeness” [1]. Completeness is relatively easy to measure manually without software support. However, when a sketch map contains generalized features, even a simple task such as counting features becomes complicated to do manually in a consistent manner. For instance, in Fig 1, it is unclear whether to consider houses in sketch A as complete or incomplete. Gardony map drawing analyzer [18] is perhaps one of the most widely used software for analyzing sketch maps using bi-dimensional regression [19–21]. While it can handle incomplete sketch maps at present, it lacks the functionality to work with generalized sketch maps. SketchMapia [12] proposes seven qualitative aspects [22] of sketch maps that are not affected by cognitive distortions for measuring the qualitative accuracy of a sketch map. At its current state, SketchMapia also computes these measures only for features aligned in a 1:1 manner. The proposed approach to resolve generalization can be integrated with SketchMapia for converting group alignments to 1:1. To conclude, apart from the fact that only very few software exist for analyzing complex sketch maps, none of the existing software can handle generalized information.

While matching generalized spatial data to detailed spatial data has been done for geo-referenced data [23] e.g. maps of different scales, the same procedure cannot be followed in the case of sketch map, because geo-referenced data have the advantage of similar shapes and other geometric properties for matching. These properties are not preserved in the sketch map. Matching sketched data to georeferenced data relies mostly on qualitative properties [24] between the two maps such as the topology of streets [25], and left-right relations of landmarks to streets [26]. Numerous applications that require aligning spatial data in the sketch map to geo-referenced data have pointed out the issue of limited matching, primarily due to the generalized content within the sketch map [12, 24]. Wolter et. al [27] have explicitly mentioned that M: N alignments in sketch maps need to be addressed for querying spatial databases using hand drawn sketches efficiently. Wallgrün et.al [28] limited their focus on 1:1 alignments for qualitative matching of spatial information due to the computational complexity posed by 1: M or M: N alignments.

Other potential applications of sketch maps are also constrained by the absence of tools to manage generalized content in sketch maps. Geographic Information Systems (GIS) have been used for storing local indigenous knowledge for flood risk mapping [7, 9, 29], or disaster management tasks [30]. However, this knowledge often exists in fragmented and generalized forms, posing challenges for conventional GIS system designed to work with geo-referenced data. Participatory GIS initiatives [6, 8, 31] frequently employ mapping tools to gather sketch map as overlays on base maps. Integrating data from different sketch maps becomes challenging due to each sketch map being generalized differently. Thus, establishing a standard approach to resolve generalization discrepancies in sketch maps would greatly benefit a wide range of applications relying on sketch maps.

2.2 Types of generalization in sketch map

We define generalization as the level of geometric detail in the sketched features. The fewer the details in a sketch map, the more it is generalized. In our previous work [11, 16], we identified nine types of generalization by analyzing 108 sketch maps of a small urban area of approximately 3 sq. km. Out of the nine types, seven types are relevant for resolving generalization in sketch map alignment. The other two are: omission of streets and omission of buildings referring to features present in metric map but omitted in sketch map resulting in 1: 0 alignment which does not necessitate any modification in feature geometry. Fig 2 shows a symbolic representation of the seven identified generalizations with a brief explanation of each generalization type.

[Figure omitted. See PDF.]

As a part of our previous work [11], we conducted a user study to test if individuals can manually detect generalizations in sketch maps if they are made aware of the different generalization types. Ten sketch maps of three different real-world locations were created where generalizations were systematically introduced in the sketch maps. Our 5 participants (4 males and 1 female) showed a high agreement on which features are matching, generalized or missing with an inter-rater agreement scores above 0.90 with a significant p-value less than 0.005. Despite the high agreement rate, there were many instances when participants failed to identify the generalization in the sketch map. The algorithmic approach presented here automatically identifies each of the generalizations and thus outperforms the human raters as sketch maps get too complex.

2.3 Existing algorithms on generalization operators

Though generalization in sketch maps is an unaddressed problem, it is extensively researched in the field of cartography. In our earlier work [11], we conducted a detailed study on the differences and similarities between cartographic generalization and sketch map generalization. In McMaster and Shea’s work [32] on cartographic generalization, they delineate cartographic generalization into three main tasks: why to generalize (the purpose of the map), devising conditions indicating when to generalize and identifying the necessary spatial transformations indicating how to generalize. In the context of sketch map generalization, the metric map is generalized to have 1:1 alignment (why). The metric map is generalized if a generalization is detected in a sketch map (when). The nine generalization types identified earlier [11] form the generalization operators (how). This manuscript translates our previous theoretically identified operators (how) into an algorithm.

Cecconi [33] draws a difference between generalization operators and generalization algorithms. Generalization operators outline the desired transformation whereas the generalization algorithm provides the step-by-step procedure and method to execute the desired generalization. This also implies that generalization operators are theoretical concepts independent of any particular data model, unlike generalization algorithms that are designed to work with specific input data format. We opted for a vector-based representation of data for our algorithm as it is best suited to represent the sketch map data that predominantly consists of linear and aerial objects [34].

A single generalization operator such as collapse or amalgamation can have multiple algorithms [35–38] in cartographic generalization depending on the spatial context, each having its own advantages and disadvantages. In our current work, we demonstrate a single algorithm for each of the seven generalization operators (Fig 2). Some of our generalization operators such as collapse and amalgamation (Fig 2) share names with their cartographic counterparts, but the algorithm is different in the case of resolving sketch map generalization. This is because the intention behind the two types of generalization is significantly different. While algorithms catering to cartographic generalization have to take into account a number of conflicts that might occur during scale reduction, such as proximity conflict, size conflict, etc, our algorithm gives more importance to arriving at 1:1 alignment between the sketch map and the metric map.

3 An algorithm to detect generalization in sketch maps

Our algorithm detects generalization in sketch maps from alignment data and applies the necessary generalization operator to the metric map resulting in a 1:1 correspondence between metric map features and sketch map features.

3.1 Input data for the algorithm

Features in the metric map and sketch map are fed as input to the algorithm in a vector format (geoJSON): lines for linear features such as streets, polygons for aerial features like buildings, and points for representing one-dimensional features. Every feature in both maps must have a unique ID. The lines representing the street network must be topologically correct, starting and ending at junctions with precise snapping. For a roundabout to be detected, the line segments forming the roundabout loop should have some curvature to it.

Additionally, the algorithm requires alignment data as input. The alignment data is a table (Table 1) containing pairwise IDs of corresponding features in sketch and metric map. Fig 3 shows sketch maps A and B aligned to their metric map and Table 1 the corresponding alignments.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

3.2 Heuristics of the algorithm

The algorithm derives the cardinal relationship between aligned features (one-to-one, one-to-many, or many-to-many) and the feature types of the aligned features (point, linear, or polygonal features) from the input alignment data and deduces the generalization type following the decision tree in Fig 4. The generalization type is stored in the last column of Table 1.

[Figure omitted. See PDF.]

The algorithm requires the aligned features to be of the same feature type. When the aligned features are of different types, the algorithm rejects the alignment and proceeds with the next pair of aligned features. One exception to this is when a polygon feature in metric map is aligned to a point feature in sketch map (refer section 3.2.2 for details).

In the next step, the metric map features are categorized into non-generalized (1:1 relationship), missing (1:0 relationship), or generalized (m:1 or n:m relationship) initially. This is not the final classification as some non-generalized features despite having 1: 1 relationship might have geometrically changed in a way that affects the topology. Such generalizations could be identified only at later stages of the algorithm. The following sections show how the exact generalization type is determined under two cases: Generalization in streets (section 3.2.1) and Generalization in buildings (section 3.2.2), with subcases for each: many-one, many-many, and special cases.

3.2.1 Generalization in streets.

Other than omission, our previous study identified two generalization types related to streets: Omission-merge, Abstraction to show existence, and two other related to streets forming junctions: Junction-merge and Roundabout-collapse. Our algorithm further sub-categorizes omission merge into two: Omission-merge (many-one) and Omission-merge (many-many) and Abstraction to show existence in streets into Abstraction to show existence in streets (many-one) and Abstraction to show existence in streets (many-many).

* Sub-case: Many-to-one. The algorithm checks the connectivity of the aligned street segments. If one street segment in the sketch map is aligned to more than one but connected street segments in the metric map, then the algorithm detects it as Omission-merge (many-one) and merges the connected street segments in metric map into one street segment (Fig 5).

[Figure omitted. See PDF.]

If one street segment in the sketch map is aligned to more than one but disconnected street segments in the metric map, then the algorithm detects it as Abstraction to show existence in streets (many-one). The geometry of the street segments is not merged and it is rather treated as one feature in the sketch map corresponding to a group of features in the metric map for further analysis (Fig 5).

* Subcase: Many-to-many. On analyzing the connectivity of street segments, if more than one connected street segment in the sketch map is aligned to more than one connected street segment in the metric map, the algorithm detects it as Omission-merge (many-many) and merges the connected street segments to form a single street in both metric map and sketch map resulting in a one-to-one alignment (Fig 6).

[Figure omitted. See PDF.]

If more than one disconnected street segment in the sketch map is aligned to more than one disconnected street segment in the metric map, it is identified as Abstraction to show existence in streets (many-many). The geometry of the street segments is not modified and they are treated as a group of features aligned to another group of features by assigning a group ID (Fig 6).

* Special Cases:

While most of the generalizations could be detected using the cardinal relationship between aligned features and their feature type, more heuristics identifying Junction-merge and Roundabout-collapse are required.

* Roundabout-collapse: Fig 7 shows how the street segments are aligned in the case of Roundabout-collapse. It can be seen that street segments S1, S2, S3 and S11 have a one-to-one match whereas street segments 20, 21, 22 and 23 are missing in the sketch map. Thus, the streets S1, S2, S3 and S11 would have been classified as no generalization initially based on the cardinal relationship between aligned features (1:1). To detect Roundabout-collapse, from the missing streets, streets with curvature are segregated. Once, we have the curved streets, the algorithm tries to detect if some of the curved streets form a closed loop or a polygon in metric map. If a closed loop or a polygon is present, then the streets touching the closed loop/polygon are segregated. If the corresponding street segments in the sketch map form a junction, the algorithm detects it as a case of Roundabout-collapse and the closed loop/polygon is replaced by its center point. The vertices of the street segments S1, S2, S3 and S11 are extended till this center point forming a junction instead of the roundabout.

[Figure omitted. See PDF.]

3.2.1.1 Junction-merge. Fig 8 shows how the street segments (S11,S2, S3, S1) are aligned in the case of a junction merge. It is a one-to-one alignment in linear features labeled as no generalization initially. To detect Junction-merge, one needs to compare the entire street network in a metric map with the entire street network in the sketch map. Having a closer look at the Junction-merge in Fig 8, it can be assumed that it is the missing street ‘10’ in metric map, that causes the two junctions to merge. Hence, the streets that are present in the metric map but are missing in the sketch map are identified. Subsequently, we identify other streets in the metric map that are connected to this missing street. If the corresponding streets in the sketch map form a single junction, the algorithm identifies it as a Junction-merge. The two junctions are merged into one by replacing the missing street with its center point, followed by connecting the endpoints of other streets that formed two junctions previously to this center point, resulting in a single junction.

[Figure omitted. See PDF.]

3.2.2 Generalization in buildings.

In our previous work, we identified three types of generalization in buildings: Collapse, Amalgamation, and Abstraction to show existence.

* Subcase: Many-to-one. If one polygon in a sketch map is aligned with many polygons in the metric map, then the algorithm identifies it as a case of Amalgamation. If the generalization is classified as an Amalgamation, we compute a convex hull on the multiple polygons aligned in the metric map to arrive at a single polygon (Fig 9). This polygon then has a one-to-one relationship with the polygon in the sketch map for further analysis.

* Subcase: Many-to-many. If many polygons in a sketch map are aligned with many polygons in the metric map, then the algorithm identifies it as Abstraction to show existence in buildings. No geometric modifications are made to the features in the metric map (Fig 10) but a group ID is assigned to the group of features in both metric map and sketch map.

* Special Case: A polygonal feature in a metric map aligned to a point feature in a sketch map is detected as Collapse. The center point of the polygon under consideration in the metric map is computed which replaces the polygon (Fig 11).

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

As a final output, the algorithm produces two different generalized versions of the original metric map, each corresponding to the two sketch maps–Sketch A and Sketch B. Note that the aligned features in the metric map and sketch map share the same id in Fig 12.

[Figure omitted. See PDF.]

3.3 Implementation of the algorithm

We implemented our algorithm as an online tool in SketchMapia [12], an ongoing project focusing on the analysis of sketch maps. SketchMapia has provisions for digitizing and aligning metric maps and sketch maps. The features of interest in the metric map are decided by the researcher manually depending on their experimental setup used to collect sketch maps. Once features are digitized and aligned in SketchMapia, our online tool can be utilized to detect generalization in sketch maps. Our tool produces four different types of output:

* It produces a list containing the number of times a particular generalization type has been identified in a sketch map.

* It produces a downloadable CSV file containing the information on which feature IDs in the metric map are mapped to which feature IDs in the sketch map along with the identified generalization type that each feature has undergone.

* It produces a color-coded sketch map and metric map that highlights the generalized features as yellow and non-generalized features as green in the sketch map; missing features as red in the metric map.

* It results in a geometrically modified generalized metric map that has a one-on-one correspondence with a sketch map for further analysis.

4 Evaluation of the algorithm

We evaluated our algorithm to check if it detects all generalizations in a sketch map by comparing the results from our online tool to that of the results from our previous study conducted using human raters [11]. We assume that having a high agreement with our human raters implies that the algorithm can detect the generalizations in sketch maps of various spatial configurations consistently.

4.1 Data

We used the same set of 11 sketch maps and their corresponding metric maps from our previously conducted user study [11]. The sketch maps corresponded to four different real-world locations. The 11 sketch maps had 328 features in total with 250 non-generalized and 78 generalized features. As our algorithm also detects omission merge (many-many), we include additional 6 generalizations in the present study resulting in a total of 84 generalized features.

4.2 Method

Sketch maps and their corresponding metric map were digitized to translate them into vector format. We aligned the features in the sketch map to those in the metric map using the functionalities available in SketchMapia. Our online tool resulted in four different outputs as mentioned in section 3.3. The same procedure was repeated for all ten sketch maps. We focused on two of the outputs: a color-coded sketch map and the CSV file containing information on which features in the sketch map have been aligned to which features in their metric map, as well as their generalization type. As the other two outputs from the web application are based on this CSV file, we assumed the reliability of the CSV file would also ensure the reliability of the other two outputs. The color-coded map from the web application along with the output CSV file was compared to that of the color coding done by the participants in our previous study wherein they classified sketched features into generalized (yellow), non-generalized (green) or missing (red). Fig 13 shows the color-coded maps from our online tool along with the maps marked by the five participants for one of the sketch maps. The following considerations were made while analyzing the differences between the algorithm and human raters:

* The generalization types: Omission Merge and Omission Merge (many-many) were not directly marked by the participants. These two generalization types are consequences of missing streets and generalized side streets respectively. Hence, if a participant has marked a feature as missing in the metric map, and if the missing street leads to the merging of streets, we perceive that omission merge has been identified by participants.

* Similarly, if participant has identified abstraction to show existence in side streets and if this leads to merging of the main streets, we perceive that omission merge (many-many) has been identified by the participants.

[Figure omitted. See PDF.]

4.3 Results

Table 2 shows the generalization types introduced in each of the sketch maps along with whether they were identified by the five participants and the algorithm.

[Figure omitted. See PDF.]

Tick mark indicates that the particular generalization was identified and a cross mark indicates that the generalization was not identified.

The numbers 0 to 10 in Table 2 represents the different sketch maps. Within each sketch map, a number of generalizations were introduced. For instance, sketch map 0 had two instances of amalgamation, one instance of collapse, one instance of abstraction to show existence in buildings, one instance of roundabout collapse and one instance of omission merge.

We computed the percentage agreement between our web application and that of the majority of the participants in identifying generalization as shown in Table 3. Our algorithm has 100% agreement with the majority in nine out of the eleven sketch maps. In sketch maps 5 and 9, the agreement was 88.8% and 83.3% respectively as participants failed to identify generalization in these cases. From Table 2, it can be seen that in sketch map 5, omission merge has not been identified by the majority of participants. In sketch map 9, junction merge has not been identified by any of the participants. When examining the data on a participant-by-participant basis, it is evident that none of the participants were able to identify all of the 84 generalizations.

[Figure omitted. See PDF.]

We also looked at the total number of generalization instances introduced in the sketch map and the percentage identified by participants and our algorithm. Table 4 shows that while some generalization types such as junction merge was identified the least number of times- 71% of the total instances introduced, our algorithm identified every instance of it. In the case of other generalizations such as Roundabout Collapse, Abstraction to show existence in buildings and Collapse, all of the introduced instances were identified by both the participants and our online tool.

[Figure omitted. See PDF.]

4.4 Discussion

The following observations can be made from the evaluation of our algorithm.

The differences in sketch map 5 and 9 are not due to an error in the implementation but rather due to participants failing to consistently color code the sketch maps. Sketch maps easily become too complex for people, and thus participants sometimes forgot to mark all the features in the sketch map as either green or yellow sometimes leaving them unclassified. These errors happen in a manual process.

It was observed that not all generalizations were identified equally by the participants: junction merge was identified the lowest number of times (Table 4). In sketch map 9, none of the participants identified a junction merge, while our algorithm detected it (Table 2). This indicates that our algorithm is consistent in its strategy to detect generalizations even in complicated networks of streets, unlike human raters who either fail to notice such complex generalizations or change their strategy when moving from one sketch map to the other.

Some of the generalizations such as Abstraction to show existence in streets and Omission-merge have more than one consequence in the resulting map. While participants are able to identify the generalization, they fail to observe its consequences. Our algorithm can not only detect a generalization but also capture all its consequences. This is also one of the reasons we see a difference between the implementation and human raters in sketch map 5.

Regarding the computational efficiency of our algorithm, categorization of all the sketched features based on its feature type and further sub-categorization of it based on cardinality of the aligned features enables parallel processing to resolve generalization in sketch map. This parallelization significantly reduces the time complexity as the algorithm need not wait till it resolves the generalization of one feature before moving on to the next. In terms of space complexity, both the input–metric map, and sketch map and the resulting generalized map are in GeoJSON format as required by the online tool- SketchMapia. As GeoJSON format is not the most efficient way of storing spatial data due to the lack of indexing of features and has larger file size compared to the other spatial formats such as shapefile, there is still room for increasing the efficiency if very large sketch maps need to be analyzed. The algorithm can be implemented to accept input in shapefile format, to expedite the process. On the other hand, sketch maps are not likely to have more than 30 to 50 features, minimizing the performance concerns.

5 Conclusion

Comparing sketch maps to metric maps and analyzing their quality has been a challenge, in particular because features in sketch maps turned out to be generalized and thus not easily comparable to corresponding features in the metric map. This paper presents a new algorithmic approach to compare generalized sketch maps to a metric map by (i) automatically detecting the type of generalization, (ii) transforming the features such that corresponding features in maps can be analyzed.

We compared the software results to expert ratings. The high percentage of agreement in identifying the generalization types with our human raters shows the reliability of our algorithm in detecting generalization in sketch maps. In addition to detecting generalization in the sketch map, it also generates a metric map with most of the features having 1:1 correspondence with features in the sketch map. This would further reduce the information loss occurring due to a lack of procedure to deal with generalized content. Though the evaluation of the algorithm is done using systematically created sketch maps, our algorithm can detect generalization in sketch maps from real-world experiments as well.

We integrated our online tool with SketchMapia, a sketch map analysis software. Previously, analyzing sketch maps using SketchMapia required manually digitizing the metric map for each sketch map, a time-consuming process. Researches often had to repeat this process for tens or hundreds of sketch maps, leading to errors and inefficiency. Our tool streamlines this task by digitizing the metric map only once, regardless of the number of sketch maps. Our algorithm generates different metric maps corresponding to each sketch map from the original map and alignment data. This approach can also be applied to other software like Gardony map drawing analyzer, addressing similar challenges with generalization handling. There are also use cases other than sketch map analysis which would benefit from our algorithm. In studies related to qualitative constraint networks for sketch maps, the proposed algorithm would enable qualitative matching between metric maps and sketch maps at different levels of generalization. When combined with participatory GIS methods, our algorithm can help to integrate data from different sketch maps having different levels of generalization in a consistent manner. We believe that our algorithm to resolve generalization in sketch maps would be a valuable addition to a wide range of applications that utilize sketch maps.

Citation: Manivannan C, Krukar J, Schwering A (2024) An algorithmic approach to detect generalization in sketch maps from sketch map alignment. PLoS ONE 19(6): e0304696. https://doi.org/10.1371/journal.pone.0304696

About the Authors:

Charu Manivannan

Roles: Conceptualization, Data curation, Formal analysis, Investigation, Software, Validation, Visualization, Writing – original draft

E-mail: [email protected]

Affiliation: Institute for Geoinformatics, University of Münster, Münster, Germany

ORICD: https://orcid.org/0000-0002-5916-7281

Jakub Krukar

Roles: Conceptualization, Methodology, Supervision, Writing – review & editing

Affiliation: Institute for Geoinformatics, University of Münster, Münster, Germany

Angela Schwering

Roles: Conceptualization, Funding acquisition, Methodology, Project administration, Supervision, Writing – review & editing

Affiliation: Institute for Geoinformatics, University of Münster, Münster, Germany

ORICD: https://orcid.org/0000-0002-4185-1464

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

References

1. Billinghurst M, Weghorst S. Use of sketch maps to measure cognitive maps of virtual environments. Proc—Virtual Real Annu Int Symp. 1995;(April 1995):40–7.

2. Gieseking JJ. Where we go from here: The mental sketch mapping method and its analytic components. Qual Inq. 2013;19(9):712–24.

3. Lynch K. The image of the city. MIT press; 1964.

4. Curtis JW, Shiau E, Lowery B, Sloane D, Hennigan K, Curtis A. The prospects and problems of integrating sketch maps with geographic information systems to understand environmental perception: A case study of mapping youth fear in Los Angeles gang neighborhoods. Environ Plan B Plan Des. 2014;41(2):251–71.

5. Curtis JW. Integrating sketch maps with GIS to explore fear of crime in the urban environment: A review of the past and prospects for the future. Cartogr Geogr Inf Sci. 2012;39(4):175–86.

6. Jakobi Á, Pődör A. GIS-based statistical analysis of detecting fear of crime with digital sketch maps: A Hungarian multicity study. ISPRS Int J Geo-Information. 2020;9(4):229.

7. Klonner C, Usón TJ, Marx S, Mocnik F-B, Höfle B. Capturing flood risk perception via sketch maps. ISPRS Int J Geo-Information. 2018;7(9):359.

8. Klonner C, Hartmann M, Dischl R, Djami L, Anderson L, Raifer M, et al. The sketch map tool facilitates the assessment of OpenStreetMap data for participatory mapping. ISPRS Int J Geo-Information. 2021;10(3):130.

9. Brandt K, Graham L, Hawthorne T, Jeanty J, Burkholder B, Munisteri C, et al. Integrating sketch mapping and hot spot analysis to enhance capacity for community-level flood and disaster risk management. Geogr J. 2020;186(2):198–212.

10. Cheung W, Houston D, Schubert JE, Basolo V, Feldman D, Matthew R, et al. Integrating resident digital sketch maps with expert knowledge to assess spatial knowledge of flood risk: A case study of participatory mapping in Newport Beach, California. Appl Geogr. 2016;74:56–64.

11. Manivannan C, Krukar J, Schwering A. Spatial generalization in sketch maps: A systematic classification. J Environ Psychol. 2022;83:101851.

12. Schwering A, Wang J, Chipofya M, Jan S, Li R, Broelemann K. SketchMapia: Qualitative Representations for the Alignment of Sketch and Metric Maps. Spat Cogn Comput. 2014;14(3):220–54.

13. Rising HH. Testing the reliability of sketch maps for multi-sited design studies. Civ Eng Archit. 2016;4(6):213–20.

14. Blades M. The reliability of data collected from sketch maps. J Environ Psychol. 1990;10(4):327–39.

15. Rovine MJ, Weisman GD. Sketch-map variables as predictors of way-finding performance. J Environ Psychol [Internet]. 1989 Sep;9(3):217–32. Available from: https://linkinghub.elsevier.com/retrieve/pii/S0272494489800362

16. Schwering A, Krukar J, Manivannan C, Chipofya M, Jan S. Generalized, Inaccurate, Incomplete: How to Comprehensively Analyze Sketch Maps beyond Their Metric Correctness. In: LIPIcs, Volume 240, COSIT 2022. 2022.

17. Skubic M, Blisard S, Bailey C, Adams JA, Matsakis P. Qualitative analysis of sketched route maps: translating a sketch into linguistic descriptions. IEEE Trans Syst Man, Cybern Part B. 2004;34(2):1275–82. pmid:15376871

18. Gardony AL, Taylor HA, Brunyé TT. Gardony Map Drawing Analyzer: Software for quantitative analysis of sketch maps. Behav Res Methods. 2016;48(1):151–77. pmid:25673320

19. Kitchin RM. Using bidimensional regression to analyse cognitive maps. Swansea Geogr. 1993;30:33–50.

20. Tobler WR. Bidimensional Regression. Geogr Anal [Internet]. 2010 Sep 3;26(3):187–212. Available from: https://onlinelibrary.wiley.com/doi/10.1111/j.1538-4632.1994.tb00320.x

21. Friedman A, Kohler B. Bidimensional regression: assessing the configural similarity and accuracy of cognitive maps and other two-dimensional data sets. Psychol Methods. 2003;8(4):468. pmid:14664683

22. Wang J, Schwering A. Invariant spatial information in sketch maps—a study of survey sketch maps of urban areas. J Spat Inf Sci [Internet]. 2015;(11). Available from: http://josis.org/index.php/josis/article/view/225

23. Mustière S, Devogele T. Matching networks with different levels of detail. Geoinformatica. 2008;12:435–53.

24. Chipofya MC, Schultz C, Schwering A. A metaheuristic approach for efficient and effective sketch-to-metric map alignment. Int J Geogr Inf Sci. 2016;30(2):405–25.

25. Jan S, Schwering A, Chipofya M, Wang J. Qualitative Representations of Schematized and Distorted Street Segments in Sketch Maps. In 2014. p. 253–67. http://link.springer.com/10.1007/978-3-319-11215-2_18

26. Chipofya M, Schwering A, Schultz C, Harason E, Jan S. Left-right relations for qualitative representation and alignment of planar spatial networks. Lect Notes Comput Sci (including Subser Lect Notes Artif Intell Lect Notes Bioinformatics). 2015;9414(May 2016):435–50.

27. Wolter, Diedrich and Richter, Kai-Florian and Wallgrün JO. Using SparQ for matching sketch maps. In: Understanding and Processing Sketch Maps@ COSIT [Internet]. 2011. p. 55. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=a646b512f01ef2ed574f24457f168ac26c1834e3

28. Wallgrün JO, Wolter D, Richter K-F. Qualitative matching of spatial information. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2010. p. 300–9.

29. Membele GM, Naidu M, Mutanga O. Examining flood vulnerability mapping approaches in developing countries: A scoping review. Int J Disaster Risk Reduct [Internet]. 2022 Feb;69:102766. Available from: https://linkinghub.elsevier.com/retrieve/pii/S2212420921007275

30. Hadlos A, Opdyke A, Hadigheh SA. Where does local and indigenous knowledge in disaster risk reduction go from here? A systematic literature review. Int J Disaster Risk Reduct [Internet]. 2022 Sep;79:103160. Available from: https://linkinghub.elsevier.com/retrieve/pii/S221242092200379X

31. Lindner C, Degbelo A, Vassányi G, Kundert K, Schwering A. The SmartLandMaps Approach for Participatory Land Rights Mapping. Land [Internet]. 2023 Nov 10;12(11):2043. Available from: https://www.mdpi.com/2073-445X/12/11/2043

32. Brainerd McMaster R and KSS. Generalization in digital cartography. 1992.

33. Cecconi A. Integration of cartographic generalization and multi-scale databases for enhanced web mapping. ETH Zurich; 2003.

34. Blaser AD. A study of people’s sketching habits in GIS. Spat Cogn Comput [Internet]. 2000;2(4):393–419. Available from: http://link.springer.com/10.1023/A:1015555919781

35. Su B, Li Z, Lodwick G. Morphological Models for the Collapse of Area Features in Digital Map Generalization. Geoinformatica [Internet]. 1998;2(4):359–82. Available from:

36. Shen Y, Ai T, Li J, Huang L, Li W. A progressive method for the collapse of river representation considering geographical characteristics. Int J Digit Earth [Internet]. 2020 Dec 1;13(12):1366–90. Available from:

37. Haunert J-H, Sester M. Area Collapse and Road Centerlines based on Straight Skeletons. Geoinformatica [Internet]. 2008;12(2):169–91. Available from:

38. Regnauld N. Algorithms for the amalgamation of topographic data. In: Proceedings of the 21st International Cartographic Conference, Durban, South Africa. 2003. p. 10–6.