# US 2014/0153789 A1 · Building boundary detection for indoor maps > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0153789 A1 - Document ID: US20140153789A1 - Status: Published application - Kind: A1 - Application number: 13/773,409 - Filed: 2013-02-21 - Published: 2014-06-05 - Earliest claimed: 2012-11-30 - Assignees: QUALCOMM Incorporated - Applicants: Qualcomm Incorporated - Inventors: Abhinav SHARMA; Chandrakant Mehta; Aravindkumar Ilangovan; Saumitra Mohan Das - Web page: https://patentgrep.com/patent/US20140153789A1 ## CPC - G06V 30/422: Technical drawings; Geographical maps - G01C 21/206: {specially adapted for indoor navigation} - G06T 7/12: Edge-based segmentation - G06V 10/44: Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components - G06V 20/176: {Urban or other man-made structures} - G09B 29/106: {using electronic means} - G06T 2207/30184: Infrastructure - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G09B: EDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS (devices for psychotechnics or for testing reaction times A61B5/16; games, sports, amusements A63; projectors, projector screens G03B) ## Abstract A computer-implemented method for detecting a boundary of a building from an indoor map includes providing an electronic raster image of the indoor map. A floor plan included in the map is a first color and a background of the image is a second color. The method includes scanning the image a first time in a plurality of directions and coloring pixels of the image a third color as they are scanned the first time until a pixel is detected that is not the second color. Then the image is scanned a second time in at least two directions. The second scan includes marking a pixel a fourth color for each third color to non-third color and each non-third color to third color transition. The resultant pixels of the fourth color represent the boundary of the building. ## Claims ### Claim 1 A computer-implemented method for detecting a boundary of a building from an indoor map, the method comprising: providing an electronic raster image of the indoor map, wherein a floor plan included in the map is a first color and a background of the image is a second color; scanning the raster image a first time in a plurality of directions and coloring pixels of the raster image a third color as they are scanned the first time until a pixel is detected that is not the second color; and scanning the raster image a second time in at least two directions and marking a pixel a fourth color for each third color to non-third color and each non-third color to third color transition, wherein the pixels of the fourth color represent the boundary of the building. ### Claim 2 (depends on 1) The method of claim 1, wherein pixels of the raster image are arranged into a plurality of rows and columns, wherein scanning the raster image the first time in a plurality of directions includes coloring pixels of each column in a first direction until a pixel is detected in each respective column that is not the second color. ### Claim 3 (depends on 2) The method of claim 2, wherein scanning the raster image the first time in a plurality of directions includes coloring pixels of each row in a second direction until a pixel is detected in each respective row that is not the second color. ### Claim 4 (depends on 1) The method of claim 1, further comprising converting the raster image to a two-tone binary image. ### Claim 5 (depends on 1) The method of claim 1, wherein scanning the raster image the first time in the plurality of directions includes scanning the raster image in a first direction, a second direction, a third direction, and a fourth direction, wherein the first direction is orthogonal to the second direction, the second direction is orthogonal to the third direction, and the third direction is orthogonal to the fourth direction. ### Claim 6 (depends on 5) The method of claim 5, wherein the first direction is from top to bottom of the raster image, the second direction is from left to right of the raster image, the third direction is from bottom to top of the image, and the fourth direction is from right to left of the raster image. ### Claim 7 (depends on 1) The method of claim 1, wherein scanning the raster image a second time in at least two directions, includes scanning the raster image in a first direction and a second direction, wherein the first direction is orthogonal to the second direction. ### Claim 8 (depends on 7) The method of claim 7, wherein the first direction is one direction selected from the group consisting of: from top to bottom and from bottom to top of the raster image, and wherein the second direction is one direction selected from the group consisting of: from left to right and from right to left of the raster image. ### Claim 9 (depends on 1) The method of claim 1, further comprising: receiving a vector-based image of the indoor map; overlaying the indoor map with a door layer; and generating the electronic raster image of the indoor map based on the indoor map overlaid with the door layer, wherein overlaying the indoor map with the door layer closes off openings in the building prior to scanning the raster image the first time. ### Claim 10 (depends on 1) The method of claim 1, further comprising filling gaps in the building boundary. ### Claim 11 (depends on 1) The method of claim 1, further comprising reducing the number of lines included in the boundary of the building. ### Claim 12 (depends on 11) The method of claim 11, wherein reducing the number of lines includes merging at least two adjacent lines together if a length of one of the two adjacent lines is less than a line length threshold. ### Claim 13 (depends on 12) The method of claim 12, wherein reducing the number of lines includes merging the at least two adjacent lines together if one of the two adjacent lines is less than the line length threshold and if an angle between the two adjacent lines is less than an angle threshold. ### Claim 14 (depends on 13) The method of claim 13, wherein reducing the number of lines further includes increasing the line length threshold if a total number of lines included in the boundary of the building is greater than a predetermined value. ### Claim 15 (depends on 13) The method of claim 13, wherein reducing the number of lines further includes increasing the angle threshold if a total number of lines included in the boundary of the building is greater than a predetermined value. ### Claim 16 (depends on 15) The method of claim 15, wherein reducing the number of lines further includes increasing the angle threshold if the angle threshold is less than an upper angle limit, and if not, increasing the line length threshold and reducing the angle threshold to a lower angle limit. ### Claim 17 (depends on 1) The method of claim 1, further comprising generating position assistance data for a mobile station, wherein the generation of position assistance data is limited to the building boundary so as to reduce the assistance data size and the processing times. ### Claim 18 A computer-readable medium including program code stored thereon for detecting a boundary of a building from an indoor map, the program code comprising instructions to: provide an electronic raster image of the indoor map, wherein a floor plan included in the map is a first color and a background of the image is a second color; scan the raster image a first time in a plurality of directions and to color pixels of the raster image a third color as they are scanned the first time until a pixel is detected that is not the second color; and scan the raster image a second time in at least two directions and marking a pixel a fourth color for each third color to non-third color and each non-third color to third color transition, wherein the pixels of the fourth color represent the boundary of the building. ### Claim 19 (depends on 18) The computer-readable medium of claim 18, wherein pixels of the raster image are arranged into a plurality of rows and columns, wherein the program code further includes instructions to scan the raster image the first time in a plurality of directions includes first program code to color pixels of each column in a first direction until a pixel is detected in each respective column that is not the second color and second program code to color pixels of each row in a second direction until a pixel is detected in each respective row that is not the second color. ### Claim 20 (depends on 18) The computer-readable medium of claim 18, wherein the program code further comprises instructions to fill gaps in the building boundary. ### Claim 21 (depends on 18) The computer-readable medium of claim 18, wherein the program code further comprises instructions to reduce the number of lines included in the boundary of the building. ### Claim 22 (depends on 21) The computer-readable medium of claim 21, wherein the instructions to reduce the number of lines includes instructions to merge at least two adjacent lines together if a length of one of the two adjacent lines is less than a line length threshold. ### Claim 23 (depends on 22) The computer-readable medium of claim 22, wherein the instructions to reduce the number of lines includes instructions to merge the at least two adjacent lines together if one of the two adjacent lines is less than the line length threshold and if an angle between the two adjacent lines is less than an angle threshold. ### Claim 24 (depends on 18) The computer-readable medium of claim 18, wherein the program code further comprises instructions to generate position assistance data for a mobile station, wherein the generation of position assistance data is limited to the building boundary so as to reduce the assistance data size and the processing times. ### Claim 25 A map server, comprising: memory adapted to store program code for detecting a boundary of a building from an indoor map; and a processing unit adapted to access and execute instructions included in the program code, wherein when the instructions are executed by the processing unit, the processing unit directs the map server to: provide an electronic raster image of the indoor map, wherein a floor plan included in the map is a first color and a background of the image is a second color; scan the raster image a first time in a plurality of directions and to color pixels of the raster image a third color as they are scanned the first time until a pixel is detected that is not the second color; and scan the raster image a second time in at least two directions and marking a pixel a fourth color for each third color to non-third color and each non-third color to third color transition, wherein the pixels of the fourth color represent the boundary of the building. ### Claim 26 (depends on 25) The map server of claim 25, wherein pixels of the raster image are arranged into a plurality of rows and columns, wherein the program code further includes instructions to direct the map server to scan the raster image the first time in a plurality of directions includes first program code to color pixels of each column in a first direction until a pixel is detected in each respective column that is not the second color and second program code to color pixels of each row in a second direction until a pixel is detected in each respective row that is not the second color. ### Claim 27 (depends on 25) The map server of claim 25, wherein the program code further comprises instructions to direct the map server to fill gaps in the building boundary. ### Claim 28 (depends on 25) The map server of claim 25, wherein the program code further comprises instructions to direct the map server to reduce the number of lines included in the boundary of the building. ### Claim 29 (depends on 28) The map server of claim 28, wherein the instructions to reduce the number of lines includes instructions to merge at least two adjacent lines together if a length of one of the two adjacent lines is less than a line length threshold. ### Claim 30 (depends on 29) The map server of claim 29, wherein the instructions to reduce the number of lines includes instructions to merge the at least two adjacent lines together if one of the two adjacent lines is less than the line length threshold and if an angle between the two adjacent lines is less than an angle threshold. ### Claim 31 (depends on 25) The map server of claim 25, wherein the program code further comprises instructions to direct the map server to generate position assistance data for a mobile station, wherein the generation of position assistance data is limited to the building boundary so as to reduce the assistance data size and the processing times. ### Claim 32 A system for detecting a boundary of a building from an indoor map, the system comprising: means for providing an electronic raster image of the indoor map, wherein a floor plan included in the map is a first color and a background of the image is a second color; means for scanning the raster image a first time in a plurality of directions and coloring pixels of the raster image a third color as they are scanned the first time until a pixel is detected that is not the second color; and means for scanning the raster image a second time in at least two directions and marking a pixel a fourth color for each third color to non-third color and each non-third color to third color transition, wherein the pixels of the fourth color represent the boundary of the building. ### Claim 33 (depends on 32) The system of claim 32, further comprising means to fill gaps in the building boundary. ### Claim 34 (depends on 32) The system of claim 32 further comprising means to reduce the number of lines included in the boundary of the building. ### Claim 35 (depends on 34) The system of claim 34, further comprising means for merging at least two adjacent lines together if a length of one of the two adjacent lines is less than a line length threshold. ### Claim 36 (depends on 34) The system of claim 34, further comprising means for merging at least two adjacent lines together if one of the two adjacent lines is less than the line length threshold and if an angle between the two adjacent lines is less than an angle threshold. ### Claim 37 (depends on 32) The system of claim 32, further comprising mean for generating position assistance data for a mobile station, wherein the generation of position assistance data is limited to the building boundary so as to reduce the assistance data size and the processing times.