Qualitative and quantitative sensor fusion for indoor navigation

A system and method for determining the location of a mobile device is provided. Such a method includes receiving an interior map, determining a first location to be an absolute location of a mobile communication device, locating the absolute location at a first position on the interior map, relocating the mobile communication device to a second location, estimating the second location of the mobile communication device based on an output of one or more sensors and modifying, using a computer-based system, the estimated second location based on a comparison of the estimated second location to the interior map.

BACKGROUND

Embodiments relate generally to indoor location determination.

Navigation systems using Global Positioning System (GPS) receivers can provide location information accurate to within a few meters, which is sufficient for providing driving instructions. For applications involving navigating on foot through a smaller space, such as within an indoor location, GPS systems may not provide sufficient accuracy to provide a walking user with navigation directions. Further, it may be difficult, if not impossible to receive GPS satellite signals inside of a facility. Wireless local area networks have become increasingly prevalent, and location systems using Wireless Fidelity (WIFI) routers have been used to determine locations with accuracies of tens to hundreds of meters. Although WIFI signals are easily received indoors, WIFI derived location information may not provide sufficient accuracy for assisting users to navigate within a facility.

BRIEF SUMMARY

The capability to determine the location of a mobile communication device in a facility such as the interior of a building is provided. Embodiments relate to systems and methods of determining a location for a mobile communication device and updating the location as the mobile communication device is moved within the facility.

In an embodiment, a system for indoor navigation is provided. The system includes an interior mapping system that stores a database of interior maps and an absolute location system that determines a first position of a mobile communication device to be an absolute location. The interior mapping system associates the absolute location with a position on an interior map. The system further includes a sensor system configured to estimate a second location of the mobile communication device subsequent to a relocating of the mobile communication device from the first position. In addition, a location modifier system can modify the estimated second location based on a comparison of the estimated second location to the interior map.

In an embodiment, a method of determining a location using an indoor map is provided. The method can be implemented on a computer and includes receiving an interior map and determining a first location to be an absolute location of a mobile communication device. The method includes locating the first position on the interior map, and relocating the mobile communication device to a second location, where an estimate is made of the second location of the mobile communication device based on an output of one or more sensors. The estimated second location is then modified based on a comparison of the estimated second location to the interior map.

In an embodiment, a computer program product is provided. The computer program product is a non-transitory computer readable storage medium on which a computer readable program code for interior navigation is embodied. The embodied computer readable code includes first computer readable program code for causing the computer to receive an interior map, second computer readable program code for causing the computer to determine a first location to be an absolute location of a mobile communication device, and third computer readable program code for causing the computer to locate the absolute location with a first position on the interior map.

The computer readable code further includes fourth computer readable program code for causing the computer to estimate the second location of the mobile communication device based on an output of one or more sensors in response to the mobile station being relocated to the second location, and fifth computer readable program code for causing the computer to modify the estimated second location based on a comparison of the estimated second location to the interior map.

The accompanying drawings, which are incorporated herein and form part of the specification, illustrate embodiments of the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the relevant art(s) to make and use the invention.

DETAILED DESCRIPTION

While embodiments described herein are illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those skilled in the art with access to the teachings provided herein will recognize additional modifications, applications, and embodiments within the scope thereof and additional fields in which the invention would be of significant utility.

The embodiments described herein are referred in the specification as “one embodiment,” “an embodiment,” “an example embodiment,” etc. These references indicate that the embodiment(s) described can include a particular feature, structure, or characteristic, but every embodiment does not necessarily include every described feature, structure, or characteristic. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is understood that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.

Embodiments relate to determining the location of a mobile device within a confined space. Mobile communication devices such as smart phones and personal data assistants (PDA) have facilities for accessing and displaying graphical information, and contain sensors that can collect information about the surrounding environment. The mobile devices can also be configured to interpret the information collected from the sensors. As will be described in further detail below, embodiments leverage these facilities to enable a user of a mobile communication device to obtain location information within a confined space.

II. System Overview

FIG. 1is a diagram of a navigation system100, according to an embodiment. In the example shown inFIG. 1, navigation system100includes a facility mapping server110, a facility map database112, active beacons106a,106b, and106c, passive localization devices108a,108b, and108c, a network120, and a mobile communication device114.

Facility mapping server110and facility map database112are components of an interior map delivery system. Facility map database112stores map data for a location, e.g., the interior of a building. The map data stored in facility map database112includes coordinate data and descriptive information for the facility and can include layout information giving coordinate data for pathways that can be traversed by persons within the location. In addition, map database112can store attributes associated with a position including images of specific areas of a building.

Facility mapping server110responds to requests for map data by retrieving data from facility map database112and delivering map data to the map requesting device such as mobile communication device114.

Navigation system100can include active beacons, represented by106a, and106b, and106c, that generate and transmit signals. The active beacons of navigation system100are located at various coordinates within the location. Active beacons106a-106cgenerate signals that each have a distinctive signature that include information such as the generated signal strength of the signal and an identifier, where such information is encoded into the signal. The identifier allows a receiver of the signal to correlate the signal to the particular active beacon that transmitted the signal. For each active beacon, facilities map database112stores information describing the expected signal signature expected at one or more coordinates within the facility. Examples of active beacons include, without limitation, radio frequency transmitting device such as Wireless Fidelity (WIFI) routers configured to have a unique Media Access Control (MAC) address and active radio frequency identification (RFID) beacons.

Passive localization devices108a,108b, and108care located at various coordinates within the location. Passive location devices include an associated distinctive signature, where the signatures of passive location devices are detected by a reading device, e.g., bar code scanner, mobile communication device with scanning capabilities. Passive location devices include, for example, without limitation, one or two dimensional bar codes, such as barcode1302and QR code1304(shown inFIG. 13), and passive RFID tags. Facility map database112can store information describing the signature associated with the passive location devices, and information describing the coordinates of the location of the passive location device within the building. Alternatively, the location information can be encoded into the signature of the passive location device so that database queries to receive location information for the passive location device are not necessary.

Navigation system100determines the location of mobile communication device114, which can be carried by a user to various locations in the facility. Mobile communication device114may include sensors for reading the signatures of passive localization devices108aand108b, and facilities for receiving the signals transmitted by one or more active beacons106a,106b, and106c. Mobile communication device114can also be configured to request map data from mapping server110and to determine and display its location on an interior map of the facility. In some embodiments, mobile communication device114has the option to op-in to the detection and reading of signature, where personal or payload data is not captured or is removed to protect user privacy. Further, data received and/or transmitted by mobile commination device114need not include any payload information, but only that necessary to identify the location of a passive or active beacon device. In some embodiments, no personal data need be transmitted, and privacy protections are provided for any user data including, for example, anonymization of personally identifiable information, aggregation of data, filtering of sensitive information, encryption, hashing or filtering of sensitive information to remove personal attributes, time limitations on storage of information, or limitations on data use or sharing.

Network120connects the components of navigation system100to provide a communications path between mobile communication device114, mapping server110, and active beacons106a-106c. Network120can include one or more networks, such as a local area network (LAN), a wide area network (WAN), the Internet, or a combination thereof. The connections of the components to network120can be wired, wireless, or a combination of wired and wireless connections.

III. Mobile Device for a Navigation System

A mobile device, according to an embodiment will be described with reference toFIGS. 2, 3A, and 3B.

Referring first toFIG. 2, mobile communication device114includes one or more sensors for determining the orientation and movement of mobile communication device114, according to an embodiment. Mobile communication device114can include an accelerometer202capable of measuring acceleration imparted to the mobile communication device114. In an embodiment, accelerometer202measures components of acceleration along three independent axes.

Referring now toFIG. 3A, an example axis system for accelerometer202is shown, according to an embodiment. Accelerometer202has a fixed relationship to the mobile communication device114, and measures acceleration along axes x, y, and z. In an embodiment, the x axis for accelerometer202is parallel to a width dimension along the face of mobile communication device114, the y axis for accelerometer202is perpendicular to the x-axis and is oriented along the face of mobile communication device114. The z axis for accelerometer202is perpendicular to the x and y axes and extends outward from the face of mobile communication device114. The accelerometer may have other orientations within the device provided that the orientation of the axes is known and that the component axes for measuring acceleration are independent (i.e. the three axes do not all lie in a single plane).

Mobile communication device114can include a compass for determining magnetic north. In the illustrated embodiment, mobile communication device114includes magnetometer204that generates information describing the vector direction of the magnetic field present at the location of mobile communication device114. Mobile communication device uses information modeling the pattern of the earth's magnetic field at various locations on earth, and information describing the latitude and longitude of a location, to determine the direction of true north from the information obtained magnetometer204.

In another embodiment, mobile communication device114includes gyroscope216and is configured to generate orientation information based on output signals generated by the gyroscope.

In an embodiment, mobile communications device114includes sensors for obtaining information from active beacons. For example, mobile communication device114can include a radio frequency receiver206capable of receiving RF signals from a radio frequency signal transmitter. For example RF receiver206can be a WIFI receiver cable of receiving transmissions from a wireless router. In an embodiment, receiver206can receive transmissions from active RFID beacons. In an embodiment, mobile communication device114can include an audio sensor222capable of sensing and/or receiving sounds either from ambient sources, an active sound beacon, or voice commands or input.

In an embodiment, mobile communication device114includes sensors for obtaining information from passive localization devices. For example, mobile communication device114can include an optical sensor208to implement a camera for capturing a query image whereby the query image can be compared to stored reference images of locations in the facility to derive a location for the mobile communication device. Mobile communication device114can be configured to use optical sensor208to scan codes, such as one or two dimensional barcodes located in a facility and to obtain location information based on interpreting the barcodes.

In an embodiment, RF receiver206can include a device that includes an RFID transmitter for transmitting to a passive RFID tag and/or a RFID receiver for reading signature information returned from a passive RFID tag.

In an embodiment, mobile communication device114can also include transceiver220for communicating with external devices. In an embodiment, transceiver220is a wireless transceiver for transmitting and receiving information from devices connected to network120of navigation system100shown inFIG. 1.

Mobile communication device114further includes a logic unit214that implements a control system that determines the function and operation of the mobile communication device. Logic unit214may be implemented using hardware or software or a combination of hardware and software arranged and configured to implement functionality in accordance with various embodiments. Software, sensor data, and information such as the final and intermediate results of calculations can be stored in memory218included in mobile communication device114.

In an embodiment, mobile communication device114includes one or more input devices212that receive input data from a user and provide the input data in a form readable by logic unit214. Input device212may include, without limitation, devices such as a keypad, touch screen, pointer device, or microphone to allow speech input.

Operation of multiple embodiments of a navigation system will be described with reference toFIGS. 1, 2, and 4.

FIG. 4illustrates navigation system400, according to an embodiment. Navigation system400includes interior mobile mapping system410, absolute location system420, location modifier system430, location determining system440, and location display system450.

In an embodiment, interior mobile mapping system410is configured to respond to requests for map information in support of other components of navigation system400. Interior mobile mapping system410responds to requests for map information, for example, by querying interior mobile mapping system410using information from the request.

Referring now toFIGS. 1 and 2, interior mobile mapping system410of mobile communication device114can be configured to implement navigation system400, including the transmitting of a request for map information to facility mapping server110, using transceiver220, and network120. Facility mapping server110retrieves the map information from facility map database112and transmits the retrieved map information to mobile communication device114. Interior mobile mapping system410, in conjunction with mobile communication device114stores map information in mobile mapping database414of the interior mapping system.

In an embodiment, the map information describes the interior layout for a facility and includes, without limitation, coordinate information describing the location, including information such as descriptive names for rooms, corridors, and walkways within the location, the coordinates of landmarks and significant areas (e.g. front desk, elevators, and stairwells) within the location, and coordinates and parameters associated with active beacons and passive localization devices within the location.

A. Absolute Location System

Navigation system400includes an absolute location system420that determines a position for a mobile communication device114by capturing sensor information from location based devices at known coordinates in a building, according to an embodiment. Absolute location system420includes a beacon sensor system422, a passive sensor system424, a user input system426, and an absolute location determining system428.

In an embodiment, beacon sensor system422is configured to collect information from active beacons using sensors, such as those in mobile communication device114, to determine a first location for mobile communication device114using active localization.

Active beacons generate and transmit signals that can be received by mobile communication device114. The transmitted signals are characterized at least by a signal strength transmitted by the active beacon, and by the inclusion of a distinctive signature that allows the identification of the transmitting source of each signal received by mobile communication device114. In an embodiment, an active beacon can be a device such as a wireless router or other WIFI device that transmits a radio frequency signal. The transmitted WIFI signal can include identifying information such as an SSID that distinguishes the wireless transmitter from all other WIFI transmitters within range of mobile communication device114. In some embodiments, such identifying information need not include any payload information, but only that necessary to identify the location of a passive or active beacon device. Further, in some embodiments, no personal data need be transmitted, and privacy protections are provided for any user data including, for example, anonymization of personally identifiable information, aggregation of data, filtering of sensitive information, encryption, hashing or filtering of sensitive information to remove personal attributes, time limitations on storage of information, or limitations on data use or sharing.

In an embodiment, beacon sensor system422of mobile communication device114is configured to receive one or more active beacon signals and to extract the signature information from a received signal. The mobile device can also be configured to measure the received signal strength from the one or more beacons.

Beacon sensor system422is configured to retrieve information describing the expected signal strength of the one or more received active beacon signals by sending a request for map information to mobile mapping system410. The request can include identifying information based on the signature information extracted by beacon sensor system422. In response to receiving the request from beacon sensor system422, interior mapping system server412queries interior mobile mapping database414to obtain identifying information for the one or more active beacons.

FIG. 6illustrates an example data table for storing active beacon information, according to an embodiment. Records602a,602b,602d, and602deach contain signal strength information for active beacons106a,106b,106c, and106drespectively. Fields604can include information describing the signal strength for a respective active beacon at various points within a location.

In response to the query from interior mapping system410, database414can return the expected signal strength information for the one or more active beacons to interior mapping system410by retrieving one or more records from table600corresponding respectively to the signature information from an active beacon received at mobile communication device114. In an embodiment, interior mapping system server412is configured to send the retrieved signal strength information to beacon sensor system422.

Beacon sensor system422can be configured to determine coordinates of an estimated position based on a comparison of the measured signal strength information from the active beacons and the expected signal strength information retrieved from the mobile mapping system410. In an embodiment, the determination of the coordinates of the estimated position includes a determination of the estimated uncertainty of the position determined from the signal strength information.

In an embodiment, passive sensor system424is configured to collect information from one or more passive localization devices using sensors in mobile communication device114and to estimate coordinates based on the collected passive localization device information. An example embodiment will be described that employs bar codes as the passive localization device.

Referring again toFIG. 1, bar codes108aand108bare located at different locations within a building. In an embodiment, mobile communication device114is configured to optically scan bar codes, such as bar codes108aor108busing optical sensor208and to retrieve information encoded in the bar code. In an embodiment, the bar code information can contain an identifier for the bar code. Passive sensor system424can be configured to request the location of the bar code by sending a request to mobile mapping system410that includes the identifying information scanned from the bar code.

In response to receiving the request from beacon sensor system422, interior mapping system server412queries interior mobile mapping database414with the identifying information from the bar code scanned by passive sensor system424to obtain the associated location information of the bar code.

FIG. 7illustrates an example data table700for storing passive beacon, e.g., bar code, information in accordance with an embodiment. Records702a,702b, and702c, each contain information for a respective bar code marker affixed to a position within a location. Field704for each record includes location information such as coordinates at which the bar code marker is affixed.

In an embodiment, a bar code can include information describing the coordinates of the bar code. Passive sensor system424can be configured to determine a location for the bar code by interpreting the bar code, and therefore the step of retrieving the coordinates of the bar code using identifying information can be omitted.

In an embodiment, passive sensor system424determines the estimated location of the mobile device to be the location determined for the barcode. Passive sensor system424can be configured to determine an accuracy for the position determined by the passive location system. In an embodiment, the passive location system can be configured to determine that the accuracy for passive locations is appreciably higher than the accuracy of positions determined by beacon sensor system422.

In an embodiment, passive sensor system424can be configured to determine an estimated location of the mobile device using image comparison. For example, mobile communication device114can be configured to capture an image of an interior location using optical sensor208. In an embodiment, passive sensor system424can be configured to send a request for a stored captured image of the interior location from mobile mapping database414that may include corresponding location information associated with the stored captured image.

Absolute location determining system428receives estimated position information generated by one or more of beacon sensor system422, passive sensor system424, and user input system426to determine estimated coordinates for mobile communication device114. User input system426, in an embodiment, receives information from a user, such as through mobile communication device114that relates to a specific location.

Location determining system440receives information from location modifier system430and absolute location system420to determine an estimated location for mobile communication device114. In an embodiment, location determining system440can be configured to store estimated positions for mobile communication device114in location database445. Location determining system can be implemented as part of a server system, such as mapping server110, or in a client device such as mobile communication device114, or as a combination client/server approach using both a server system, such as mapping server110, and a client device, such as mobile communication device114.

Location display system450can be configured to display an estimated location determined for mobile communication device114. In an embodiment, location display system450can be configured to display an interior map on display device210. Location display system450can be configured to generate a request for information surrounding an estimated position for mobile communication device114from mobile mapping system410. In response to the request, interior mapping system server412retrieves information describing the facility layout from the mobile mapping database414and returns the retrieved map information to location display system450. Location display system450can be configured to display the estimated position for mobile communication device114as a location plotted on display device210of mobile communication device114.

FIG. 9illustrates an example interior map900according to an embodiment. Interior map900shows layout of pathways that a user can traverse in the interior of a location. For example, interior map900graphically depicts the position and extent of rooms such as offices902a,902b, and902d, lobby area902c, conference room902d, corridors904a,904b, and904c, stairwell906, elevators908a,908b,908c, and908d, building entry points910a,910b, and910c, front desk912, and interior doors914aand914b. Interior map900also indicates a present position of mobile communication device114at region920. The dashed circle surrounding region920indicates the range of values for the estimated position determined by absolute location determining system428. In an embodiment, location display system450is configured to generate a request for information surrounding an estimated position for mobile communication device114from mobile mapping system410. In response to the request, interior mapping system server412retrieves information describing the building layout from mobile mapping database414and returns the retrieved map information to location display system450as a position plotted on display device210of mobile communication device114. In an embodiment, location display system450can display an estimate of the uncertainty in the estimated position for mobile communication device114.

User input system426can be configured to receive user input information for determining absolute location information for mobile communication device114. In an embodiment, user input system426receives information from one or more input devices212of mobile communication device114. For example, mobile communication device114can be configured to display a user interface for receiving user input identifying an initial location of the mobile communication device114and to receive information from a user input device such as a keypad or touch screen selecting the initial position.

Absolute location system420can be configured to retrieve map information from mobile mapping system410and to send the map information to mobile communication unit114to display an interior map for the location. In an embodiment, a user can select a position displayed on the map as a first location. For example, mobile communication device114may provide a touch screen as an input device and can receive a touch signal from user input system426indicating a selection of the representation on display210of front desk912in lobby902cas the current location for mobile communication device114.

In an embodiment, absolute location determining system428can receive input from user input system426to resolve uncertainties in the location determined by a component such as beacon sensor system422or passive sensor system424. Referring again toFIG. 9, interior map900shows an estimated position920that overlaps with office902b, lobby area902c, and corridor904a. In an embodiment, a user input system426can receive a touch screen input indicating which of the areas within estimated position920represents an accurate location for mobile communication device114. For example, the user can indicate by touching the area of the map presented on display210that the user and mobile communication device114are actually in corridor904a.

B. Location Modifier System

Location modifier system430determines information for modifying the estimated location information determined by absolute location system430. In an embodiment, the current location of mobile communication device114changes as the user moves through the building. The location of the user is constrained by the layout of the building. For example, a user can walk within a room or through a corridor in a building and can use exits, doorways, elevators, and stairwells. However, the user is constrained from passing through solid objects such as room walls, structural members and other non-traversable objects positioned within the interior. In addition, a user traversing the building by walking cannot traverse from one location to another in a shorter time period than allowed by the user's walking or running speed.

A location modifier system suitable for practicing embodiments of the invention will be described below with reference toFIGS. 2, 3A, 3B, 4, and 5. Location modifier system includes navigation sensor system432and motion and event detection system434as subsystems.

Navigation sensor system432receives input from one or more sensors within mobile communication device114and generates information describing the orientation and acceleration of mobile communication device114.

In an embodiment, navigation sensor system432receives input from accelerometer202and magnetometer204that generates output signals to indicate the orientation and acceleration of mobile communication device114.

The acceleration on mobile communication device114is produced by the operation of the force of gravity on the device combined with the acceleration exerted by forces that create motion of the device. As a user walks though the interior of a location carrying mobile communication device114, the force of gravity exerts an essentially constant acceleration g, in a downward direction g having a magnitude of about 9.81 meters per second2(m/s2). The user's motion while walking on a level surface generates an acceleration component in the direction of motion of the user as well as components in other directions (for example an upward component of motion of the user) characteristic of the user's stride while walking through the building.

Navigation sensor system432is configured to receive acceleration data from accelerometer202that indicates the components of acceleration of the mobile communication device along the x, y, and z axes shown inFIG. 3A. As discussed above, the x, y, and z axes are fixed relative to mobile communication device114.

In an embodiment, navigation sensor system432is configured to determine components of acceleration along the x, y, and z axes that are due to the force of gravity, which acts along axis g pointing downwards and to determine components of acceleration due to motions imparted to mobile communication device resulting from the user's walking motion. For example, the navigation sensor system432can be configured to distinguish between the components of acceleration due to gravity along the x, y, and z axes from components of acceleration due to the user's motion while walking through the interior of a location using frequency information contained in the accelerometer signal. The acceleration components due to gravity are constant values for a given orientation of mobile communication device114, while the components of acceleration due to user walking motions are time varying components for a given orientation of mobile communication device114.

In an embodiment, navigation sensor system432receives compass information from magnetometer204and generates information identifying the direction of true north based on the received magnetometer sensor information. Gyroscope216may be used to accurately determine relative orientation changes over short durations. Gyroscope data may be combined with the magnetometer and accelerometer data to produce accurate estimates of absolute orientation.

In an embodiment, navigation sensor system432is configured to convert orientation and acceleration values measured in the device based coordinate system into a geographic based coordinates.FIG. 3Bshows an example geographic based coordinate system having an x′ axis that points in the direction of true north, a y′ axis oriented perpendicular to the x′ axis in a horizontal plane, and a vertical z-axis parallel to the direction of the earth's gravitational field, according to an embodiment.

In an embodiment, navigation sensor system432can be configured to determine the orientation and acceleration components in a geographic coordinate system, such as the x′, y′, z′ coordinate system show inFIG. 3B, by using mathematical coordinate transform algorithms known in the art from the acceleration components measured using the accelerometer, and the directions of true north measured using the magnetometer signal, and from information describing the direction of the g-axis in the x, y, z coordinate system determined from the accelerometer data and relative orientation changes obtained from the gyroscope. Navigation sensor system432can be configured to generate signals representing the acceleration of mobile communication device114in a geographic coordinate system.

Motion and event detection system434receives acceleration signals output by navigation sensor system432and generates output signals that identify events and motion information for mobile communication device114. In an embodiment, motion and event detection system generates signals indicating the direction of motion of the mobile communication device, steps made by a user walking through the location while carrying the mobile device, and one or navigational events occurring while walking through a location, including, but not limited to turns, stair climbing, and riding of elevators.

FIG. 5illustrates functional components of motion and event detection system434, according to an embodiment. Motion and event detection system434includes a step identifying unit502, a step size determining unit504, a direction determining unit506, a dead reckoning unit508, a turn detection unit510, a stairway detection unit512, and an elevator detection unit514.

Step identifying unit502, step size determining unit504, direction determining unit506, and dead reckoning unit508are each configured to perform a pedometer function that detects motion by identifying and counting user's steps, determines the direction of the user's motion and step size, and determines the user's change in position while walking.

Step identifying unit502can be configured to identify a user step by analyzing a signal that describes the acceleration of mobile communication device114while being carried on the person of a user.

Walking motions generate an acceleration pattern that includes vertical acceleration peaks generated as the each foot contacts the floor or ground. In an embodiment, step identifying unit502is configured to identify peaks in a signal provided by navigation sensor system432corresponding to the vertical (z′ axis) component of acceleration due to the motion of the mobile device sensor. Step identifying unit502can be configured to store step information and time stamp information for each step.

Table810shown inFIG. 8shows an example table for storing step information, according to an embodiment. As can be appreciated fromFIG. 8, step identifying unit502can be configured to store time stamp information indicating the time associated with each step detected by step identifying unit502.

Step size determining unit is configured to determine the size of steps identified by step identifying unit. In an embodiment, step size determining unit can be configured to receive a step size manually input or selected by a user via input device212. Step size determining unit can be configured to store manually entered step size information in a data table stored in memory, and to retrieve and transmit the step size information in response to a request from another system such as absolute location system420.

FIG. 8shows an example data table820storing data that can be suitable for storing step size data in location database445in an embodiment.

Records802a,802b,802c,802d, and802eeach contain records describing a step size determination. Field804of each record indicates the step size determined using step size determining unit504. Field806contains step rate information calculated by measuring the number of steps detected and counted over an interval by step identifying unit502. Field808contains information indicating the method used to make the step size determination. Fields810and812contains information describing the start and stop coordinates used for calculating the step size. In an embodiment, coordinate fields810and812can also include information allowing an estimate of the accuracy of the position information contained in the respective fields. Field814of table820includes time stamp information indicating the time and date for the step size determination.

Record802aholds data for user Jim that describes a manually entered step size. Field804of record802acontains information indicating a step size of 0.9 meters, while method field808indicates that the step size was manually entered. Field814contains time stamp information indicating the time and date at which the step size was entered.

In an embodiment, step size determining unit504can be configured to determine or update the step size using position information determined by the location database445. The user's step size can be calculated by dividing the distance covered by the user by the number of steps used to cover the distance.

Referring again toFIG. 8, record802bof table820contains information stored by step size determining unit504during a step size determining operation. In an embodiment, step size determining unit504retrieves pairs of stored values of the coordinates information determined by location determining system440, and the step count and frequency information for the user's steps in traveling between the two coordinates as determined and stored by step identifying unit502, and computes a value for the step size. Step size determining unit then stores the value for step size and other relevant parameters in table820.

For example, field804of record802bcontains the value of the step size determined by step size determining unit504. Field806of record802bcontains the step count and step rate information for the steps used in the step size determination. Method field808of record802bindicates that the step size was determined by calculation. Fields810and812contain the coordinate information for the start and stop positions used to determine the step size, and indicate that the start and stop positions were determined using bar codes and positional estimation using an active beacon and compass. Field814of record802bindicates the time and date for the step size determination.

In an embodiment, step size determining unit can be configured to use the data stored in table820as historical step size data, and to retrieve the historical step size data stored in table820for use in subsequent step size determinations.

In an embodiment, step identifying unit502and step size determining unit504, alone or in combination, can be configured to implement a training mode. For example, the step size determining unit504can be configured to collect acceleration patterns generated while the user paces off a known distance when the user selects a calibration mode using user input device212. The step size determining unit504can also be configured to receive user input describing the distance paced off and the number of steps taken by the user. The collected acceleration pattern information can be stored for retrieval by step identifying unit502to be used in a pattern comparison operation to identify steps by the user, while the step count and distance information can be stored and used during step size determining operations by step size determining unit504.

Referring again toFIG. 8, record802eof table820illustrates an example of data stored in a calibration mode operation in an embodiment. In record802e, field804contains the step size value determined during the calibration operation, field806contains step rate information indicating that 11 steps were taken in 35 seconds during the calibration operation, field808indicates that the step size determination was made during a calibration operation, and fields810and812indicate that the user traveled 10 meters during the calibration operation.

In an embodiment, step size determining unit504can be configured to correlate step size with step rates when determining a current step size. For example, step size determining unit504can be configured to determine a current step rate by determining the time interval between steps identified by step identifying unit502. Step size determining unit504can be configured to retrieve historical step size data stored in table820, and to determine the current step size based on previously determined step sizes that are associated with step rates that are close matches for the current step rate.

Direction determining unit506is configured to determine the direction of motion of the user as the user walks through the building. In an embodiment, direction determining unit determines the direction of motion of the user from signals generated by the user corresponding to acceleration of the mobile device in the horizontal direction (x′/y′ plane inFIG. 3B) including corresponding acceleration information from a navigation sensor system, e.g., navigation sensor system432. The compass and gyroscope data may be combined with the acceleration data to produce absolute heading.

Dead reckoning unit508computes a modification to the absolute position determined by absolute location system420that reflects the motion of the user. In an embodiment, dead reckoning unit508is configured to estimate the distance traveled from a previously determined position using step count information generated by step identifying unit502, step size information generated by step size determining unit504, and direction of motion information generated by direction determining unit506and estimates a change in position produced by a user's walk through the interior. Dead reckoning unit508generates an output signal corresponding to the estimated change in position.

Turn detection unit510identifies changes of direction in the user's motion that constitute turns. In an embodiment, turn detection unit receives a signal generated by direction determining unit506indicating the estimated direction of motion. Turn detection unit can be configured to identify turns by detecting changes in the direction of motion of travel. For example, turn detection unit can identify that a turn has occurred when the change in the direction of motion exceeds a threshold value. In another embodiment, turn detection can identify that a turn as occurred when the rate of change of the direction of motion exceeds a threshold value.

In an embodiment, stairway detection unit512analyzes accelerometer data generated by navigation sensor system432to detect acceleration patterns that indicate that a user carrying mobile communication device114is climbing or descending stairs.

The acceleration component pattern for a user walking up steps differs from the acceleration component pattern generated while walking on a horizontal surface. In particular, the vertical components for the motion of acceleration are increased for each step during climbing and descending stairs. In an embodiment, stairway detection unit512can be configured to identify increases in the vertical components of the acceleration signal generated by navigation sensor system432. In another embodiment, stairway detection unit512can be configured detect that a user is climbing a stairwell by using the result of a comparison of the acceleration component pattern to a stored patterns obtained for the user while climbing or descending stairwell.

Similarly, the acceleration component pattern for a user riding an elevator differs from the acceleration component pattern generated while walking on a horizontal surface. In particular, the horizontal components generated while riding on the elevator are small, while the vertical components indicate momentary upward or downward acceleration as the elevator starts to move, and then a momentary deceleration in the opposite direct as the elevator comes to a stop. In an embodiment, elevator detection unit514can be configured to recognize the characteristic acceleration and deceleration pattern for a user riding on an elevator and to generate an output signal indicating that the user of mobile communication device114is on an elevator. For example, elevator detection unit514can be configured detect that a user is riding in an elevator using the result of a comparison of the acceleration component pattern to a stored patterns obtained for the elevator. In an embodiment, elevator acceleration/deceleration patterns can be stored as map data in facility map database112, and can be stored for retrieval by elevator detection unit514in mobile mapping database414.

In an embodiment, location determining system440is configured to receive a first position for mobile communication device114determined by absolute location system420, and to receive location modifying information determined from one or more components of location modifier system430. Further, location determining system440is configured to receive map information from mobile mapping system410to determine a second location for mobile communication device114.

For example, location determining system440can be configured to provide an update to the first position for mobile communication device114to obtain a second position for mobile communication device114using sensor information that reflects motion of the user in the interior of the location.

In an embodiment, location determining system440obtains a signal generated by dead reckoning unit508of motion/event detection system434. Location determining system440can be configured to increment position information determined by the absolute location system420with the position change data generated by dead reckoning unit508to obtain an estimated second location.

Location determining system440can refine the second location determined using position change information with information determined from map information data retrieved from mobile mapping system410.

Referring again toFIG. 9, dashed circle930represents a second location computed by updating position920based on direction of movement along path932as determined by dead reckoning unit508. The area of uncertainty indicated in the region enclosed by dashed circle930includes office902e, conference room902b, and corridors904aand904b. Location determination unit can determine from the retrieved map information, that there are no entrances allowing a user to enter office902eor corridor904bthat can be reached along path932and therefore can constrain the second location to be within the regions of circle930that lie within conference room902band corridor904a.

In an embodiment, location determining system440can be configured to receive event detection information generated by one or more event detection units of motion and event detection system434to refine the estimated second position determined for mobile communication device114.

Referring again toFIG. 9, dashed circle940indicates an estimated second location determined by location determining system440. Dashed circle904overlaps with cubicles902f,902g, and corridor904c. In an embodiment, location determining system440can utilize turn event information detected by turn detection unit510to apply a constraint to the second position determined940.

For example, as the user travels along path942, turn detection unit510detects the turn to the west and generates a corresponding output signal. Location determining system440can determine that the westward turn is not possible if the previous second location was within cubicles902for902g, and that a current second location for mobile communication device114must be near the door between corridors904cand904a.

In an embodiment, location determining system440can apply a constraint to the second location using output signals generated by the stairway detection unit512and elevator detection unit514. For example upon receiving a signal generated by stairway detection unit512indicating that the user of mobile communication device114is traversing a stairway, location determining system440can constrain the location of mobile communication device114to stairwell906near the estimated second location950. In response to receiving a signal generated by elevator detection unit514, location determining system440can constrain the location of the user to be inside elevator908anear estimated second location950.

Navigation system100can be configured to perform methods in accordance with embodiments of the invention. The description of the methods includes a description of additional features of the mobile communication device114and navigation system400according to embodiments.

Methods in accordance with embodiments will be described with respect to navigation system100ofFIG. 1and mobile communication device114ofFIGS. 1, 4 and 5, without limitation.

FIG. 10is a flowchart of an exemplary method1000for determining a location of a mobile device in an interior space. For ease of explanation, method1000is described with respect to navigation system100ofFIG. 1and mobile communication device114ofFIGS. 1, 4 and 5, but embodiments of the method are not limited thereto.

Method1000begins at step1002with the receiving of an interior map. In an embodiment, facility mapping server110and facility map database112access map data for an interior space, e.g., a building, where the map data can include layout information, coordinate information, and images associated with various interior positions. Facility mapping server110responds to requests for map data by retrieving data from facility map database112and where the map requesting device such as mobile communication device114, receives the interior map.

Method1000continues in step1004with determining a first location to be an absolute location for a mobile communication device. In an embodiment, mobile communication device114includes absolute location system420that is configured to determine an absolute location for mobile communication device114. As discussed above, absolute location determining system428can be configured to obtain an absolute location for mobile communication device114in various ways. For example, mobile communication device114can obtain location information using a passive localization system, such as bar code108b, by scanning bar code108bwith an optical sensor. Further location information can be obtained through the use of beacon sensor system422to obtain a location for the bar code108band to determine the position of bar code108bto be the absolute location of mobile communication device114. As discussed above, embodiments of mobile device can use QR codes as components of a passive location system.

Method1000continues in step1006by locating the absolute location of the mobile station on an interior map. In an embodiment, location display system450is configured to retrieve map information from interior mobile mapping database414that may also include an interior map that can be displayed on display device210of mobile communication device114. Location determining system440is configured to receive the first location determined by absolute location system420and to determine the corresponding position on the interior map.

Method1000continues in steps1008and steps1010with relocating the mobile communication device to a second location and sensing the second location of the mobile communication device based on an output of one or more sensors. In an embodiment, a user carries mobile communication device114from the first location to a second location while walking through the interior of a building. Mobile communication device114can be configured to determine the motion of the device based on one or more sensors onboard the mobile communication device. For example, as described above mobile communication device114can include navigation sensor system432that is configured to determine the motion and orientation of the mobile communication device114. Location determining system440can be configured to determine an estimated second location for the mobile device based on the information generated by navigation sensor system432.

In an embodiment, mobile communication device114includes a location modifier system430configured to use accelerometer, magnetometer, and gyroscope sensors to determine a direction of motion of the mobile communication device, and to implement a pedometer to determine a count of the steps to move from the first location to the second location.

Method1000continues in step1012with modifying the estimated second location based on a comparison of the estimated second location to the interior map. As described above, location determining system440is configured to apply constraints based on interior map information. For example, if there are two possible estimated locations, where one of those locations would require the user to travel through an obstacle such as a wall, location determining system can determine from interior map information that such a possible location is removed from consideration. Method1000concludes after step1012.

FIG. 11is a flowchart of an exemplary method1100for determining an absolute location for a mobile communication device using active localization, according to an embodiment.

In step1102of method1100, a process of capturing signature information for one or more active beacons using a sensor is performed. In an embodiment, mobile communication device receives a signal generated by an active beacon. For example, the received signal can be from a WIFI transmitting device that is located within receiving range of the location of the mobile communication device. The WIFI signal is a radio frequency signal that has a signature that includes the signal strength at the absolute location of mobile communication device114and a MAC address associated with the transmitting device.

In step1104of method1100, expected signature information for the one or more active beacons corresponding to receiving locations in an interior is retrieved. In an embodiment, the map information stored in mobile mapping database414includes information describing the signal signature information, e.g. the MAC address and expected signal strength information for the WIFI transmitting devices for locations in the interior of a facility. As described above, beacon sensor system422can be configured to retrieve the signature information from mobile mapping database414. In some embodiments, such signature information need not include any payload information, but only that necessary to identify the location of a passive or active beacon device. Further, in some embodiments, no personal data need be transmitted, and privacy protections are provided for any user data including, for example, anonymization of personally identifiable information, aggregation of data, filtering of sensitive information, encryption, hashing or filtering of sensitive information to remove personal attributes, time limitations on storage of information, or limitations on data use or sharing.

Method1110continues in step1106with determining a first location for a mobile device by comparing the captured signature information with the retrieved signature information. In an embodiment, beacon sensor system422is configured to determine a location by comparing the received signatures for the one or more WIFI transmitter devices to the signature data retrieved from interior mobile mapping database414. Beacon sensor system422determines an estimated location to be the position where the measured signatures for the one or more beacons best match the retrieved signature information.

FIG. 12is a flowchart of an exemplary method1200for determining an absolute location for a mobile communication device using passive localization, according to an embodiment.

In step1202of method1200, a process of capturing identifying information from a passive location device using a sensor is performed. In an embodiment, mobile communication device114scans a passive location device such as a bar code1302or a QR code1304bearing device (shown inFIG. 13) affixed to a location in a facility. In an embodiment, passive sensor system424can be configured to retrieve information encoded in the passive location.

In step1204of method1200, retrieving location information for the passive location device is performed. In an embodiment, location information is encoded into passive sensor information. For example, bar code1302and QR code1304each encode information describing the location as “First Floor Conference Room.”

In an embodiment, the information encoded in the passive location device is an identifier for the passive location device. Passive sensor system424can be configured transmit a request to interior mobile mapping system410that includes the identifier, where interior mobile mapping system410can be configured to retrieve location information associated with the passive location device identifier and transmit the location information to passive sensor system424, or mobile communication device114.

Method1200continues in step1206with determining a first location for a mobile communication device based on the location information for the passive localization device. Beacon sensor system424can be configured to accept the location for the passive localization device as an absolute location for mobile communication device114.

V. Example Computer System Implementation

FIG. 14illustrates an example computer system1400in which embodiments, or portions thereof, may be implemented as computer-readable code. For example, the mobile communication device shown inFIGS. 1 and 2, including modules for implementing the functions and methods shown inFIGS. 4, 5, 10, 11, and 12can be implemented in computer system1400using hardware, software, firmware, tangible computer readable media having instructions stored thereon, or a combination thereof and may be implemented in one or more computer systems or other processing systems. Hardware, software, or any combination of such may embody any of the modules and components inFIGS. 1-5.

If programmable logic is used, such logic may execute on a commercially available processing platform or a special purpose device. For example, logic unit214of mobile communication device114can be implemented using programmable logic. One of ordinary skill in the art may appreciate that embodiments of the disclosed subject matter can be practiced with various computer system configurations, including multi-core multiprocessor systems, minicomputers, and mainframe computers, computer linked or clustered with distributed functions, as well as pervasive or miniature computers that may be embedded into virtually any device.

For instance, at least one processor device and a memory may be used to implement the above described embodiments. A processor device may be a single processor, a plurality of processors, or combinations thereof. Processor devices may have one or more processor “cores.”

Processor device1404may be a special purpose or a general purpose processor device. As will be appreciated by persons skilled in the relevant art, processor device1404may also be a single processor in a multi-core/multiprocessor system, such system operating alone, or in a cluster of computing devices operating in a cluster or server farm. Processor device1404is connected to a communication infrastructure1406, for example, a bus, message queue, network, or multi-core message-passing scheme.

Computer system1400also includes a main memory1408, for example, random access memory (RAM), and may also include a secondary memory1410. Secondary memory1410may include, for example, a hard disk drive1412, removable storage drive1414. Removable storage drive1414may comprise a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash memory, or the like. The removable storage drive1414reads from and/or writes to a removable storage unit1418in a well known manner. Removable storage unit1418may comprise a floppy disk, magnetic tape, optical disk, etc. which is read by and written to by removable storage drive1414. As will be appreciated by persons skilled in the relevant art, removable storage unit1418includes a computer usable storage medium having stored therein computer software and/or data.

Computer system1400(optionally) includes a display interface1402(which can include input and output devices such as keyboards, mice, etc.) that forwards graphics, text, and other data from communication infrastructure1406(or from a frame buffer not shown) for display on display unit1430.

In alternative implementations, secondary memory1410may include other similar means for allowing computer programs or other instructions to be loaded into computer system1400. Such means may include, for example, a removable storage unit1422and an interface1420. Examples of such means may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units1422and interfaces1420which allow software and data to be transferred from the removable storage unit1422to computer system1400.

Computer system1400may also include a communications interface1424. Communications interface1424allows software and data to be transferred between computer system1400and external devices. Communications interface1424may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, or the like. Software and data transferred via communications interface1424may be in the form of signals, which may be electronic, electromagnetic, optical, or other signals capable of being received by communications interface1424. These signals may be provided to communications interface1424via a communications path1426. Communications path1426carries signals and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link or other communications channels.

In this document, the terms “computer program medium” and “computer readable medium” are used to generally refer to storage media such as removable storage unit1418, removable storage unit1422, and a hard disk installed in hard disk drive1412. Computer program medium and computer readable medium may also refer to memories, such as main memory1408and secondary memory1410, which may be memory semiconductors (e.g. DRAMs, etc.).

Computer programs (also called computer control logic) are stored in main memory1408and/or secondary memory1410. Computer programs may also be received via communications interface1424. Such computer programs, when executed, enable computer system1400to implement embodiments as discussed herein. In particular, the computer programs, when executed, enable processor device1404to implement the processes of embodiments of the present invention, such as the stages in the methods illustrated by flowcharts1000,1100, and1200ofFIGS. 10, 11, and 12, respectively, and discussed above. Accordingly, such computer programs represent controllers of the computer system1400. Where embodiments are implemented using software, the software may be stored in a computer program product and loaded into computer system1400using removable storage drive1414, interface1420, and hard disk drive1412, or communications interface1424.

Embodiments of the invention also may be directed to computer program products comprising software stored on any computer readable medium. Such software, when executed in one or more data processing devices, causes a data processing device(s) to operate as described herein. Embodiments of the invention employ any computer useable or readable medium. Examples of non-transitory computer readable media include, but are not limited to, primary storage devices (e.g., any type of random access memory), secondary storage devices (e.g., hard drives, floppy disks, CD ROMS, ZIP disks, tapes, magnetic storage devices, and optical storage devices, MEMS, nano-technological storage device, etc.). Other computer readable media include communication mediums (e.g., wired and wireless communications networks, local area networks, wide area networks, intranets, etc.).

As would be understood by a person skilled in the art based on the teachings herein, several variations of the above described features determining the location of a mobile communication device in a facility can be envisioned. These variations are within the scope of embodiments of the present invention. For example, one skilled in the art can envision several variations to facility and interior mapping systems illustrated inFIGS. 1 and 4. For the purpose of illustration only and not limitation, one variation is provided herein.

For example, in a variation of the invention, storage of map information may be maintained primarily on facility mapping server110and facility map database114. Mobile mapping system410can be configured to request map information from facility mapping server110in response to request from the location determining modules of navigation system400.