技术领域technical field
本发明涉及行人航位推算技术和室内地图构建技术，尤其涉及一种通过智能手机传感器以众包方式采集大量行人行走轨迹信息，自动构建室内平面图的方法。The invention relates to pedestrian dead reckoning technology and indoor map construction technology, in particular to a method for automatically constructing an indoor floor plan by collecting a large amount of pedestrian walking trajectory information in a crowdsourcing manner through smart phone sensors.
背景技术Background technique
随着定位和导航技术的发展，各种基于位置的服务对地图的需求越来越大。室外地图的构建和绘制经过多年的发展已拥有一套成熟的方法，由专业测绘人员通过专业设备采集数据，再通过专业地理软件处理并绘制地图。但是室内地图的构建和绘制一直是迄待解决的问题，也是阻碍基于位置的服务在室内获得广泛应用的主要因素之一。目前室内地图的构建主要是由测绘人员测量室内数据并绘制地图或者基于建筑设计结构图绘制平面图。这些方法尽管能够进行部分楼宇的地图创建和绘制，但是由于高成本及私密性等原因，多数室内环境无法采用专业方法进行地图绘制，而建筑设计结构图也往往由于各种原因无法获得，从而导致大量室内环境无可用地图，室内定位与导航也无法实施。With the development of positioning and navigation technology, various location-based services have an increasing demand for maps. After years of development, the construction and drawing of outdoor maps has a mature method. Professional surveyors collect data through professional equipment, and then process and draw maps through professional geographic software. However, the construction and drawing of indoor maps has been a problem to be solved, and it is also one of the main factors hindering the widespread application of location-based services indoors. At present, the construction of indoor maps is mainly done by surveyors measuring indoor data and drawing maps or drawing floor plans based on architectural design structure drawings. Although these methods can create and draw maps of some buildings, due to high cost and privacy, most indoor environments cannot be mapped by professional methods, and architectural design structural drawings are often unavailable for various reasons, resulting in There are no available maps for a large number of indoor environments, and indoor positioning and navigation cannot be implemented.
近年来，随着手机传感技术的发展，加速度计、磁力计、气压计等传感器已成为智能手机的标配，极大促进了基于智能手机的行人活动识别和行人航位推算技术以及室内导航技术的发展。通过对智能手机传感器数据的采集和处理可以获得行人当前活动状态以及行动轨迹，根据大量普通用户在室内的行动轨迹，结合复杂数据分析算法，就可以获得室内区域的房间和走廊结构，从而自动构建出室内平面图，以利用基于位置的服务在室内的广泛应用。In recent years, with the development of mobile phone sensing technology, sensors such as accelerometers, magnetometers, and barometers have become standard equipment for smartphones, which greatly promotes pedestrian activity recognition and pedestrian dead reckoning technology based on smartphones, as well as indoor navigation. technology development. Through the collection and processing of smartphone sensor data, the current activity status and action trajectory of pedestrians can be obtained. According to the indoor action trajectory of a large number of ordinary users, combined with complex data analysis algorithms, the room and corridor structure of the indoor area can be obtained, thereby automatically constructing Create indoor floor plans to take advantage of the wide application of location-based services indoors.
发明内容Contents of the invention
本发明提出一种新的普遍适用的采用众包方式的基于智能手机传感器的室内平面图自动构建方法。该方法包括如下步骤：The present invention proposes a new universally applicable method for automatically constructing an indoor floor plan based on a smart phone sensor in a crowdsourcing manner. The method comprises the steps of:
A.由于采用众包方式进行室内平面图构建，因此需要大量用户参与。参与用户随身携带智能手机，智能手机集成加速度计、磁力计、气压计、卫星导航系统接收器以及WiFi适配器。智能手机及各传感器处于开启状态，并后台运行数据采集处理软件。A. Due to the crowdsourcing method for indoor floor plan construction, a large number of user participation is required. Participating users carry their smartphones with them, which integrate accelerometers, magnetometers, barometers, satellite navigation system receivers, and WiFi adapters. The smart phone and each sensor are turned on, and the data acquisition and processing software is running in the background.
B.采用众包方式进行数据采集并产生大量用户行走轨迹。本步骤在用户智能手机端执行，需要大量用户参与，每个用户智能手机端执行以下步骤：B. Use crowdsourcing to collect data and generate a large number of user walking trajectories. This step is performed on the user's smartphone, which requires a large number of users to participate. Each user's smartphone performs the following steps:
B1.智能手机中的卫星导航系统接收器实时监测卫星信号，当从接收到卫星信号变为接收不到卫星信号时，该位置作为建筑入口和轨迹起始点，进入B2步骤；B1. The satellite navigation system receiver in the smart phone monitors the satellite signal in real time. When the satellite signal is received and the satellite signal is not received, the location is used as the building entrance and the starting point of the track, and enters the B2 step;
B2.实时采集智能手机中各传感器数据：通过加速度计采集加速度数据；通过磁力计采集磁场强度数据；通过气压计采集气压数据；对采集到的数据进行平滑降噪处理；B2. Real-time collection of sensor data in smart phones: Acceleration data collection through accelerometer; magnetic field strength data collection through magnetometer; air pressure data collection through barometer; smooth noise reduction processing for the collected data;
B3.根据加速度数据，判断用户是否处于行走状态，如果是，则执行B4步骤；B3. According to the acceleration data, it is judged whether the user is in a walking state, and if so, then perform the B4 step;
B4.根据加速度数据识别出行走中的每一步并估算步长；根据磁场强度数据结合加速度数据计算行走方向；根据前一步位置，结合当前步长和行走方向得到新的位置；采集当前位置的WiFi AP列表及信号强度；把每一步位置当成一个轨迹点，连接所有轨迹点构成行人该段时间的行走轨迹；B4. Identify each step in walking according to the acceleration data and estimate the step length; calculate the walking direction according to the magnetic field strength data combined with the acceleration data; obtain a new position according to the previous step position, combined with the current step length and walking direction; collect the WiFi of the current position AP list and signal strength; each step position is regarded as a track point, and all track points are connected to form the pedestrian's walking track during this period;
B5.根据气压数据计算得到海拔高度数据，根据海拔高度数据和加速度数据进行行人活动识别，确定用户是否通过楼梯、直梯或者扶梯进行上楼或下楼；如果是，则将该位置标记在行走轨迹中，并作为新的楼层和新的轨迹起始点；B5. Calculate the altitude data based on the air pressure data, conduct pedestrian activity recognition based on the altitude data and acceleration data, and determine whether the user is going up or down through stairs, straight ladders, or escalators; if so, mark the location on the walk In the trajectory, and as the new floor and the starting point of the new trajectory;
B6.判断行走轨迹中的每个轨迹点是否为转向点(左转、右转、后转)，如果是转向点，则在该点对行走轨迹进行分割，得到一系列轨迹线段；B6. judge whether each track point in the walking track is a turning point (turn left, turn right, turn back), if it is a turning point, then the walking track is segmented at this point to obtain a series of track segments;
B7.将所有行走轨迹数据发送到中央服务器进行处理；B7. Send all walking trajectory data to the central server for processing;
C.行走轨迹聚类及平面图自动构建，本步骤在中央服务器执行，包括以下步骤：C. Walking trajectory clustering and floor plan automatic construction, this step is executed on the central server, including the following steps:
C1.接收来自大量用户智能手机的大量行走轨迹线段；C1. Receive a large number of walking trajectory line segments from a large number of users' smart phones;
C2.根据每个转向点位置前后的WiFi信号变化，确定该转向点是否为房间门口；连续两个房间门口之间的轨迹线段属于房间类型轨迹线段，其它的则属于走廊类型的轨迹线段；C2. According to the WiFi signal changes before and after each turning point position, determine whether the turning point is a room door; the trajectory line segment between two consecutive room doorways belongs to the room type trajectory line segment, and the others belong to the corridor type trajectory line segment;
C3.使用聚类算法对房间类型的轨迹线段和走廊类型的轨迹线段分别进行聚类，一个类为一个区域；C3. Use a clustering algorithm to cluster the trajectory line segments of the room type and the trajectory line segments of the corridor type respectively, and one class is an area;
C4.如果区域为房间类型，则提取其中的轨迹线段包含的所有轨迹点，利用α-shape方法确定房间形状和大小；C4. If the area is a room type, then extract all the trajectory points contained in the trajectory segment, and use the α-shape method to determine the shape and size of the room;
C5.如果区域为走廊类型，则利用主成分分析法确定数据变化的主方向和次方向，从而确定走廊的长和宽；C5. If the area is a corridor type, use the principal component analysis method to determine the main direction and secondary direction of the data change, so as to determine the length and width of the corridor;
C6.根据确定的房间和走廊的位置、形状和大小绘制室内各层平面图，同时将确定的直梯、扶梯和楼梯的位置在图中进行标记。C6. According to the determined location, shape and size of the rooms and corridors, draw the plan of each floor in the room, and mark the determined positions of the elevators, escalators and stairs in the drawing.
本发明的有益效果是能够在仅使用智能手机和普通用户非主动参与的情况下采集手机传感器数据并进行处理，自动构建近似的各楼层室内平面图。和现有技术相比，本发明根据海拔高度数据和加速度数据进行行人活动识别，确定用户是否通过楼梯、直梯或者扶梯进行上楼或下楼，从而能够进行多楼层的室内平面图构建；本发明根据行人轨迹中转向点位置前后的WiFi信号变化结合聚类算法，确定房间门口的位置，从而构建出较准确的房间位置及大小；采用主成分分析法，本发明能够确定走廊的长度和宽度。该方法无需借助专业人员和专用设备，能够解决大规模室内平面图构建难以及需要专业人员参与且成本高的问题，有利于室内基于位置的服务的广泛应用。The beneficial effect of the present invention is that it can collect and process the sensor data of the mobile phone under the condition of only using the smart mobile phone and the non-active participation of ordinary users, and automatically construct an approximate indoor floor plan of each floor. Compared with the prior art, the present invention conducts pedestrian activity recognition based on altitude data and acceleration data, and determines whether the user is going up or down through stairs, straight ladders or escalators, so that multi-floor indoor floor plans can be constructed; the present invention According to the WiFi signal changes before and after the turning point in the pedestrian trajectory combined with the clustering algorithm, the position of the door of the room is determined, thereby constructing a more accurate room position and size; using the principal component analysis method, the present invention can determine the length and width of the corridor. This method does not require professionals and special equipment, can solve the problems of difficulty in constructing a large-scale indoor floor plan and requires the participation of professionals and high cost, and is conducive to the wide application of indoor location-based services.
附图说明Description of drawings
图1是系统实施图Figure 1 is a system implementation diagram
图2是行人上下楼识别算法Figure 2 is the recognition algorithm for pedestrians going up and down stairs
图3(a)是根据WiFi信号变化确定的可能的房间门口位置点Figure 3(a) is the possible room door location determined according to the WiFi signal change
图3(b)是根据WiFi信号变化并通过聚类算法确定的房间门口位置点Figure 3(b) is the position of the door of the room determined by the clustering algorithm according to the change of WiFi signal
图4(a)是利用主成分分析法获得的走廊长度Figure 4(a) is the corridor length obtained by principal component analysis
图4(b)是利用主成分分析法获得的走廊宽度Figure 4(b) is the corridor width obtained by principal component analysis
具体实施方式detailed description
本方法采用众包方式进行室内平面图的自动构建，需要大量普通用户参与。每个参与用户随身携带智能手机，智能手机集成加速度计、磁力计、气压计、卫星导航系统接收器以及WiFi适配器。加速度计能够实时测量手机的三轴加速度，磁力计能够实时测量手机所在位置的三轴磁场强度，气压计能够测量手机所处位置的气压值从而计算出海拔高度，卫星导航系统(GPS或者北斗)接收器能够接收导航卫星的信号并获得当前地理位置坐标，WiFi适配器可以测得所处环境中的WiFi接入器及其信号强度。用户参与过程中，智能手机及各传感器处于开启状态，后台运行数据采集处理软件，采集处理后的数据发送到服务器端进行集中处理和地图构建。图1显示了该采用众包方式的基于手机传感器的室内平面图自动构建方法的基本过程。This method uses crowdsourcing to automatically construct the indoor floor plan, which requires the participation of a large number of ordinary users. Each participating user carries a smartphone with an integrated accelerometer, magnetometer, barometer, satellite navigation system receiver, and WiFi adapter. The accelerometer can measure the three-axis acceleration of the mobile phone in real time, the magnetometer can measure the three-axis magnetic field strength of the mobile phone's location in real time, the barometer can measure the air pressure value of the mobile phone's location to calculate the altitude, and the satellite navigation system (GPS or Beidou) The receiver can receive the signal of the navigation satellite and obtain the current geographic location coordinates, and the WiFi adapter can measure the WiFi access device and its signal strength in the environment. During the user participation process, the smart phone and each sensor are turned on, and the data collection and processing software runs in the background, and the collected and processed data is sent to the server for centralized processing and map construction. Figure 1 shows the basic process of the method for automatically constructing indoor floor plans based on mobile phone sensors using crowdsourcing.
步骤1：智能手机中的卫星导航系统接收器实时监测卫星信号，当从接收到卫星信号变为接收不到卫星信号时，即卫星信号丢失，则表明此时由室外进入室内，将该位置作为建筑入口和轨迹起始点，进入步骤2；Step 1: The satellite navigation system receiver in the smart phone monitors the satellite signal in real time. When the satellite signal is received and the satellite signal is not received, that is, the satellite signal is lost, it means that the person enters the room from the outside at this time. Building entrance and trajectory starting point, go to step 2;
步骤2：实时采集智能手机中各传感器数据。通过加速度计采集三轴加速度数据，采样频率为50Hz，即20ms一次；通过磁力计采集磁场强度数据，采样频率为50Hz，即20ms一次；通过气压计采集气压数据，采样频率为5Hz，即200ms一次。由于手机内置传感器本身的非精确性、人行走中身体晃动对传感器数据的干扰、以及周围环境的影响，采集到的传感器数据具有一定噪声，一次采用简单移动平均算法(Simple Moving Average，SMA)对数据进行平滑处理以降低噪声干扰；Step 2: Collect sensor data in the smartphone in real time. Collect triaxial acceleration data through the accelerometer, the sampling frequency is 50Hz, that is, once every 20ms; collect magnetic field strength data through the magnetometer, the sampling frequency is 50Hz, that is, every 20ms; collect air pressure data through the barometer, the sampling frequency is 5Hz, that is, every 200ms . Due to the inaccuracy of the built-in sensor of the mobile phone, the interference of the sensor data caused by the shaking of the human body during walking, and the influence of the surrounding environment, the collected sensor data has certain noise. The data is smoothed to reduce noise interference;
步骤3：根据采集到的加速度数据，判断用户是否处于行走状态，如果加速度值高于预定行走阈值，则确定人处于行走状态，执行步骤4；Step 3: According to the collected acceleration data, determine whether the user is in a walking state, if the acceleration value is higher than the predetermined walking threshold, determine that the person is in a walking state, and perform step 4;
步骤4：根据平滑后的加速度数据和磁场强度数据可以进行行人行走步态识别、步长估计和方向估计。对行走步态的识别是从加速度曲线中识别出行走周期，并基于此进行步长计算。对于加速度曲线中行走周期的识别，可以将一个行走周期划分成静止状态、波峰状态和波谷状态，使用状态转换的方法来识别行走周期。静止状态、波峰状态和波谷状态则采用状态阈值来判断。识别出一个完整的行走周期后，采用卡尔曼滤波结合步长和垂直加速度的关系以及相邻两步步长之间的关系对步长进行估计。首先根据步长和行走过程中躯干的垂直位移之间的关系，通过该行走周期中加速度数据计算得到基础步长，然后将卡尔曼滤波应用于基础步长，进而得到更加精确的步长估计。方向确定使用加速度计和磁力计共同完成。首先通过三轴加速度数据和重力加速度计算出手机的俯仰角和翻滚角，然后将通过磁力计测得的基于手机坐标系的三轴磁场强度转成基于大地坐标系的三轴磁场强度，使用大地坐标系中x和y方向的磁场强度，即可确定行人方向。Step 4: According to the smoothed acceleration data and magnetic field strength data, pedestrian walking gait recognition, step length estimation and direction estimation can be performed. The identification of walking gait is to identify the walking cycle from the acceleration curve, and calculate the step length based on this. For the identification of the walking cycle in the acceleration curve, a walking cycle can be divided into a static state, a peak state and a valley state, and the state transition method is used to identify the walking cycle. Static state, peak state and trough state are judged by state threshold. After identifying a complete walking cycle, the Kalman filter is used to estimate the step length by combining the relationship between the step length and the vertical acceleration and the relationship between the step lengths of two adjacent steps. First, according to the relationship between the step length and the vertical displacement of the trunk during walking, the basic step length is calculated through the acceleration data in the walking cycle, and then the Kalman filter is applied to the basic step length to obtain a more accurate step length estimation. Orientation determination is accomplished using both accelerometers and magnetometers. First, the pitch angle and roll angle of the mobile phone are calculated through the three-axis acceleration data and the acceleration of gravity, and then the three-axis magnetic field strength based on the mobile phone coordinate system measured by the magnetometer is converted into the three-axis magnetic field strength based on the earth coordinate system, using the earth The direction of the pedestrian can be determined by the magnetic field strength in the x and y directions in the coordinate system.
获得当前步长和当前方向后，根据上一步位置，即可计算出当前位置。采集当前位置的WiFi AP列表及其信号强度。将每一步位置当成一个轨迹点，连接所有轨迹点构成行人该段时间的行走轨迹。每个轨迹点可表示为：{t，(x，y)，o，r}，t表示行人在该位置的时间，(x，y)为当前位置坐标，o表示当前方向，r表示在该位置采集的AP列表及信号强度。After obtaining the current step length and current direction, the current position can be calculated according to the position of the previous step. Collect the list of WiFi APs at the current location and their signal strength. Treat each step position as a trajectory point, and connect all the trajectory points to form the walking trajectory of the pedestrian during this period. Each trajectory point can be expressed as: {t, (x, y), o, r}, t represents the time when the pedestrian is at the position, (x, y) is the coordinates of the current position, o represents the current direction, and r represents the The AP list and signal strength of location collection.
步骤5：直梯、楼梯和扶梯是楼宇中的重要标志，也是室内平面图中的重要信息。根据气压计数据可以计算得到海拔高度，根据海拔高度和加速度数据进行行人活动识别，能够确定行人是否通过楼梯、直梯或者扶梯进行上楼或下楼，从而识别出楼梯、直梯和扶梯的位置，标记在行走轨迹中，同时将直梯、楼梯或扶梯的出口作为新一楼层的新的轨迹起始点。对行人采用直梯、楼梯和扶梯上下楼方式的识别采用两级识别算法，算法流程如图2所示，包含以下步骤：Step 5: Ladders, stairs and escalators are important signs in a building and important information in interior plans. According to the barometer data, the altitude can be calculated, and the pedestrian activity recognition can be carried out according to the altitude and acceleration data. It can determine whether the pedestrian goes up or down through the stairs, straight ladders or escalators, so as to identify the location of the stairs, straight ladders and escalators. , mark it in the walking track, and at the same time, take the exit of the straight ladder, staircase or escalator as the new starting point of the track for the new floor. A two-level recognition algorithm is used to identify pedestrians who use straight ladders, stairs and escalators to go up and down stairs. The algorithm flow is shown in Figure 2, including the following steps:
1)一级识别，根据海拔高度数据识别出平走、直梯上楼、直梯下楼、楼梯扶梯上楼、楼梯扶梯下楼。首先采用移动平均算法对海拔高度数据进行平滑，对平滑后的海拔高度数据做线性拟合，得出海拔高度数据的变化斜率h。假设Hu为直梯上楼的经验阈值，Hd为直梯下楼的经验阈值，H0为上下楼的经验阈值。若h≥Hu，则为直梯上楼；若H0≤h＜Hu，则为楼梯或扶梯上楼；若-H0＜h＜H0，则为平走；若-Hd＜h＜-H0，则为楼梯或扶梯下楼；若h＜-Hd，则为直梯下楼；1) First-level identification, according to the altitude data, it can identify horizontal walking, straight stairs going upstairs, straight stairs going downstairs, stairs and escalators going upstairs, and stairs and escalators going downstairs. First, the moving average algorithm is used to smooth the altitude data, and the linear fitting is performed on the smoothed altitude data to obtain the change slope h of the altitude data. Assume thatHu is the experience threshold for going up the stairs,Hd is the experience threshold for going down the stairs, andH0 is the experience threshold for going up and down the stairs. If h≥Hu , it is straight stairs; if H0 ≤h<Hu , it is stairs or escalators; if -H0 <h<H0 , it is horizontal; if -Hd <h<-H0 , it is stairs or escalators going downstairs; if h<-Hd , it is straight stairs going downstairs;
2)二级识别，根据三轴加速度数据识别出扶梯上楼、楼梯上楼、扶梯下楼、楼梯下楼。首先求加速度量级根据一级识别的结果，如果是扶梯或楼梯上楼，若am＜Au则为扶梯上楼，若am＞Au则为楼梯上楼；如果是扶梯或楼梯下楼，若am＜Ad则为扶梯下楼，若am＞Ad则为楼梯下楼；Au和Ad分别为楼梯上楼和楼梯下楼的量级阈值。2) Second-level recognition. According to the three-axis acceleration data, the escalator goes up, the stairs go up, the escalator goes down, and the stairs go down. First find the magnitude of the acceleration According to the results of the first-level recognition, if it is an escalator or stairs going upstairs, if am < A u, it is an escalator goingupstairs , if am > Au , it is a stair going upstairs; if it is an escalator or stairs going downstairs, if am <A d means that theescalator is going downstairs, and if am >Ad means that the stairs are going downstairs; Au and Ad are the magnitude thresholds of the stairs going up and the stairs going down, respectively.
步骤6：根据加速度数据和磁场强度数据，判断行走轨迹中的每个轨迹点是否为转向点(左转、右转、后转)。计算每个轨迹点的方向和前一轨迹点的方向差值Δ。如果Δ超过转向阈值，则认为发生了转向动作。考虑到可能出现连续小转向累积成大转向的情况，将连续若干次Δ值求和得到∑Δ，如果∑Δ超过转向阈值，也认为发生了转向动作。在每个被判定为转向点的轨迹点对行走轨迹进行一次分割，从而将一条连续的行走轨迹分割成若干条轨迹线段。Step 6: According to the acceleration data and the magnetic field strength data, it is judged whether each track point in the walking track is a turning point (turn left, turn right, turn backward). Calculate the difference Δ between the direction of each track point and the direction of the previous track point. If Δ exceeds the steering threshold, a steering maneuver is considered to have occurred. Considering that continuous small steering may accumulate into a large steering, the sum of several consecutive Δ values is calculated to obtain ΣΔ, and if ΣΔ exceeds the steering threshold, it is also considered that a steering action has occurred. The walking trajectory is divided once at each trajectory point determined as a turning point, so that a continuous walking trajectory is divided into several trajectory segments.
步骤7：智能手机端将本次行走产生的所有轨迹线段数据发送到中央服务器；中央服务器接收来自不同用户智能手机的大量行走轨迹线段；Step 7: The smart phone terminal sends all the trajectory line segment data generated by this walk to the central server; the central server receives a large number of walking track line segments from different users' smart phones;
步骤8：轨迹线段分成房间类型和走廊类型。确定轨迹线段的类型，需要首先识别出行人轨迹中的房间门口位置。由于人进门或出门时通常会有转向动作，因此检查行人轨迹中的每个转向点位置，判断该位置是否是房间门口。对于房间门口位置判断这里采用两级识别算法，包含以下步骤：Step 8: The trajectory segment is divided into room type and corridor type. To determine the type of trajectory line segment, it is necessary to first identify the location of the room door in the pedestrian trajectory. Since people usually have a turning action when entering or leaving the door, the position of each turning point in the pedestrian trajectory is checked to determine whether the position is the door of the room. For the judgment of the position of the door of the room, a two-level recognition algorithm is used here, including the following steps:
1)一级识别，由于房间内部和走廊的WiFi信号通常不同，因此通过检测每个转向点位置前后的WiFi信号变化，计算信号指纹之间的曼哈顿距离作为变化值，如果变化值超过阈值，则认为当前转向点处于房间门口，如图3(a)所示；1) First-level recognition. Since the WiFi signals inside the room and in the corridor are usually different, by detecting the WiFi signal changes before and after each turning point position, the Manhattan distance between the signal fingerprints is calculated as the change value. If the change value exceeds the threshold, then It is considered that the current turning point is at the door of the room, as shown in Figure 3(a);
2)二级识别，对一级识别得到的所有房间门口位置点利用基于密度的聚类算法(DBSCAN)进行聚类，得到n个聚类区域。n个聚类区域对应n个聚类中心，将每个聚类中心半径R(R为经验值)范围内的转向点标记为门口位置点，完成对门口位置点的二次识别，如图3(b)所示。2) Second-level recognition, using the density-based clustering algorithm (DBSCAN) to cluster all the room door positions obtained by the first-level recognition to obtain n clustering areas. The n clustering areas correspond to n clustering centers, and the turning points within the radius R of each clustering center (R is an empirical value) are marked as the doorway location points to complete the secondary identification of the doorway location points, as shown in Figure 3 (b) shown.
由于每条轨迹的起点都是走廊，因此每检测到两个连续的房间门口位置则表示行人的一次进门动作和一次出门动作，这两个轨迹点之间的轨迹线段就属于房间类型。如果最终检测到的房间门口数量为偶数，表明本次行走在走廊结束，则其余轨迹线段为走廊类型；如果检测到的房间门口数量为奇数，表明本次行走在房间结束，则从最后一个房间门口位置开始到轨迹结束的轨迹线段也属于房间类型，其余轨迹线段为走廊类型。Since the starting point of each trajectory is a corridor, every detection of two consecutive room door positions indicates an entry action and an exit action of a pedestrian, and the trajectory line segment between these two trajectory points belongs to the room type. If the number of detected room doorways is even, it indicates that this walk ends in the corridor, and the rest of the trajectory line segment is a corridor type; if the number of detected room doorways is odd, it indicates that this walk ends in the room, then from the last room The trajectory line segment from the door position to the end of the trajectory also belongs to the room type, and the rest of the trajectory line segments belong to the corridor type.
步骤9：中央服务器使用聚类算法，分别对房间类型和走廊类型的轨迹线段所包含的轨迹点进行聚类，形成若干房间类型区域和若干走廊类型区域；Step 9: The central server uses a clustering algorithm to cluster the trajectory points contained in the trajectory segments of the room type and the corridor type, respectively, to form several room type areas and several corridor type areas;
步骤10：如果聚类区域为房间类型，则提取该区域内的轨迹线段包含的所有轨迹点，通过该区域的轨迹点得到点集的边界形状即为我们需要的房间形状。轨迹点集边界形状有凸包和凹包两种常见多边形。考虑到直接取凸包或者凹包形状作为房间边界误差较大，需要一个介于凸包和凹包之间的形状来表示房间边界。所以采用α-shape方法来构建房间形状和大小，具体包含以下步骤：Step 10: If the clustering area is a room type, extract all the trajectory points contained in the trajectory line segment in this area, and the boundary shape of the point set obtained through the trajectory points in this area is the room shape we need. The boundary shape of trajectory point set has two common polygons, convex hull and concave hull. Considering that there is a large error in directly taking the shape of the convex or concave hull as the room boundary, a shape between the convex hull and the concave hull is needed to represent the room boundary. Therefore, the α-shape method is used to construct the shape and size of the room, which specifically includes the following steps:
1)为轨迹点数据集求取Delaunay三角网M；1) Obtain the Delaunay triangulation M for the track point data set;
2)对于M中的所有边，计算边的长度以及该边的邻接三角形集合，其中邻接2个三角形的边为内部边，邻接1个三角形的为边界边，邻接0个三角形的边为计算过程中会退化的边；2) For all sides in M, calculate the length of the side and the set of adjacent triangles of the side, where the side adjacent to 2 triangles is the internal side, the side adjacent to 1 triangle is the boundary side, and the side adjacent to 0 triangles is the calculation process The edge that will degenerate in ;
3)将所有长度大于L的边界边加入队列(L为预设的长度限制，用于排除三角网M中的无效边)，循环下列过程：从队列中取出一条边E，E具有唯一邻接三角形T；找出T中另外两条边E′和E″，从它们的邻接三角形集合中删除T；将E′和E″中新形成的长度大于L的边界边加入队列；将E标记为无效边，若E′和E″有退化的，也标记为无效边；3) Add all boundary edges whose length is greater than L to the queue (L is the preset length limit, used to exclude invalid edges in the triangular network M), and cycle the following process: take an edge E from the queue, and E has a unique adjacent triangle T; find out the other two edges E' and E" in T, and delete T from their adjacent triangle sets; add the newly formed boundary edges of E' and E" whose length is greater than L to the queue; mark E as invalid Edges, if E′ and E″ are degenerate, are also marked as invalid edges;
4)收集所有有效边界边，则得到该聚类所代表的房间形状。4) Collect all effective boundary edges, then get the room shape represented by the cluster.
步骤11：如果聚类区域为走廊类型，则利用主成分分析法(Principle ComponentAnalysis-PCA)确定轨迹点变化主方向u1和次方向u2，从而确定走廊的长和宽，如图4(a)和4(b)所示，包括以下步骤：Step 11: If the clustering area is a corridor type, use Principal Component Analysis (Principle Component Analysis-PCA) to determine the main direction u1 and the secondary direction u2 of the track point change, so as to determine the length and width of the corridor, as shown in Figure 4(a ) and 4(b), including the following steps:
1)假设轨迹点数据集为X＝{(xi，yi)|i＝1，2，...m}，m为轨迹点个数。首先对轨迹点数据进行预处理，采用用Z-score标准化方法对数据进行归一化处理，经过处理后的数据符合标准正态分布；1) Assume that the track point data set is X={(xi ,yi )|i=1, 2,...m}, m is the number of track points. First, preprocess the trajectory point data, and use the Z-score standardization method to normalize the data. The processed data conforms to the standard normal distribution;
2)计算X的协方差矩阵P＝XXT/m，对P进行奇异值分解得到特征向量U＝[u1 u2 …un]，其中u1是P的主特征向量，u2为次特征向量；2) Calculate the covariance matrix P=XXT /m of X, and perform singular value decomposition on P to obtain the eigenvector U=[u1 u2 …un ], where u1 is the main eigenvector of P, and u2 is the secondary Feature vector;
3)向量u1和u2构成X的一个新基，对于轨迹点数据集X，是X在维度u1上的投影长度，是X投影到u2维度上的长度，这两个长度分别对应走廊区域的长和宽。3) The vectors u1 and u2 form a new base of X, for the track point data set X, is the projected length of X on dimension u1 , is the length of X projected onto the u2 dimension, and these two lengths correspond to the length and width of the corridor area respectively.
步骤12：根据确定的房间和走廊的位置、形状和大小绘制室内各层平面图，同时将确定的直梯、扶梯和楼梯的位置在图中进行标记。Step 12: According to the determined location, shape and size of the rooms and corridors, draw the plan of each floor in the room, and mark the determined positions of the elevators, escalators and stairs in the figure.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610710437.3ACN106448431A (en) | 2016-08-24 | 2016-08-24 | Mobile phone sensor-based indoor planar graph construction method adopting crowdsourcing mode |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610710437.3ACN106448431A (en) | 2016-08-24 | 2016-08-24 | Mobile phone sensor-based indoor planar graph construction method adopting crowdsourcing mode |
| Publication Number | Publication Date |
|---|---|
| CN106448431Atrue CN106448431A (en) | 2017-02-22 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610710437.3APendingCN106448431A (en) | 2016-08-24 | 2016-08-24 | Mobile phone sensor-based indoor planar graph construction method adopting crowdsourcing mode |
| Country | Link |
|---|---|
| CN (1) | CN106448431A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108668245A (en)* | 2018-04-13 | 2018-10-16 | 哈尔滨工业大学 | An indoor positioning method based on WiFi and geomagnetic field database |
| CN109798900A (en)* | 2019-03-08 | 2019-05-24 | 珠海格力电器股份有限公司 | Indoor positioning method and device of air sensor and air sensor |
| CN110132266A (en)* | 2019-05-05 | 2019-08-16 | 深圳市荣盛智能装备有限公司 | Floor discrimination method, device, electronic equipment and storage medium |
| CN110647600A (en)* | 2018-06-26 | 2020-01-03 | 百度在线网络技术（北京）有限公司 | Three-dimensional map construction method and device, server and storage medium |
| CN110907981A (en)* | 2019-12-09 | 2020-03-24 | Oppo广东移动通信有限公司 | Positioning mode control method and device and electronic equipment |
| CN111311748A (en)* | 2020-02-19 | 2020-06-19 | 广东小天才科技有限公司 | Indoor stereogram construction method and device, terminal equipment and storage medium |
| CN111368014A (en)* | 2019-12-23 | 2020-07-03 | 广东小天才科技有限公司 | A method for generating motion trajectory, terminal device and storage medium |
| CN111750851A (en)* | 2019-09-10 | 2020-10-09 | 广东小天才科技有限公司 | A method, device and intelligent device for identifying moving mode between floors |
| CN112401877A (en)* | 2020-10-27 | 2021-02-26 | 中国电力科学研究院有限公司 | Method and system for monitoring behavior state of target object |
| CN113848878A (en)* | 2021-08-24 | 2021-12-28 | 深圳大学 | Construction method of indoor and outdoor 3D pedestrian road network based on crowd-source data |
| CN114125696A (en)* | 2020-08-31 | 2022-03-01 | 华为技术有限公司 | Construction method, positioning method and device of fingerprint map of multi-floor building |
| CN114111784A (en)* | 2021-10-26 | 2022-03-01 | 杭州电子科技大学 | Crowdsourcing-based automatic construction method and system for indoor corridor map |
| WO2023005865A1 (en)* | 2021-07-28 | 2023-02-02 | 华为技术有限公司 | Method for constructing indoor map and related apparatus |
| CN116184312A (en)* | 2022-12-22 | 2023-05-30 | 泰州雷德波达定位导航科技有限公司 | Indoor crowdsourcing fingerprint library construction method based on semantic Wi-Fi |
| CN116224341A (en)* | 2022-09-08 | 2023-06-06 | 北京交通大学 | Method and system for constructing indoor floor plan based on smart phone sound wave distance measurement |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090043504A1 (en)* | 2007-05-31 | 2009-02-12 | Amrit Bandyopadhyay | System and method for locating, tracking, and/or monitoring the status of personnel and/or assets both indoors and outdoors |
| CN104180805A (en)* | 2014-08-29 | 2014-12-03 | 中国海洋大学 | Smart phone-based indoor pedestrian positioning and tracking method |
| CN104282221A (en)* | 2013-07-01 | 2015-01-14 | 北京四维图新科技股份有限公司 | Method for constructing road network of indoor map |
| CN104394588A (en)* | 2014-11-15 | 2015-03-04 | 北京航空航天大学 | Indoor positioning method based on Wi-Fi fingerprints and multi-dimensional scaling analysis |
| CN104655128A (en)* | 2015-03-11 | 2015-05-27 | 武汉大学 | Indoor and outdoor parallel navigation system applicable to intelligent mobile terminal |
| CN105263113A (en)* | 2015-10-26 | 2016-01-20 | 深圳大学 | Wi-Fi location fingerprint map building method and system based on crowd-sourcing |
| CN105547301A (en)* | 2016-02-25 | 2016-05-04 | 华南理工大学 | Indoor map construction method and device based on geomagnetism |
| US20160223340A1 (en)* | 2015-02-03 | 2016-08-04 | The Regents Of The University Of Michigan | Last-Mile Navigation Using Smartphones |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090043504A1 (en)* | 2007-05-31 | 2009-02-12 | Amrit Bandyopadhyay | System and method for locating, tracking, and/or monitoring the status of personnel and/or assets both indoors and outdoors |
| CN104282221A (en)* | 2013-07-01 | 2015-01-14 | 北京四维图新科技股份有限公司 | Method for constructing road network of indoor map |
| CN104180805A (en)* | 2014-08-29 | 2014-12-03 | 中国海洋大学 | Smart phone-based indoor pedestrian positioning and tracking method |
| CN104394588A (en)* | 2014-11-15 | 2015-03-04 | 北京航空航天大学 | Indoor positioning method based on Wi-Fi fingerprints and multi-dimensional scaling analysis |
| US20160223340A1 (en)* | 2015-02-03 | 2016-08-04 | The Regents Of The University Of Michigan | Last-Mile Navigation Using Smartphones |
| CN104655128A (en)* | 2015-03-11 | 2015-05-27 | 武汉大学 | Indoor and outdoor parallel navigation system applicable to intelligent mobile terminal |
| CN105263113A (en)* | 2015-10-26 | 2016-01-20 | 深圳大学 | Wi-Fi location fingerprint map building method and system based on crowd-sourcing |
| CN105547301A (en)* | 2016-02-25 | 2016-05-04 | 华南理工大学 | Indoor map construction method and device based on geomagnetism |
| Title |
|---|
| 许强: ""基于信号分析的室内定位特征点识别技术研究"", 《中国优秀硕士学位论文全文数据库信息科技辑》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108668245A (en)* | 2018-04-13 | 2018-10-16 | 哈尔滨工业大学 | An indoor positioning method based on WiFi and geomagnetic field database |
| CN110647600A (en)* | 2018-06-26 | 2020-01-03 | 百度在线网络技术（北京）有限公司 | Three-dimensional map construction method and device, server and storage medium |
| CN110647600B (en)* | 2018-06-26 | 2023-10-20 | 百度在线网络技术（北京）有限公司 | Three-dimensional map construction method, device, server and storage medium |
| CN109798900A (en)* | 2019-03-08 | 2019-05-24 | 珠海格力电器股份有限公司 | Indoor positioning method and device of air sensor and air sensor |
| CN110132266A (en)* | 2019-05-05 | 2019-08-16 | 深圳市荣盛智能装备有限公司 | Floor discrimination method, device, electronic equipment and storage medium |
| CN110132266B (en)* | 2019-05-05 | 2020-06-30 | 深圳市荣盛智能装备有限公司 | Floor discrimination method, device, electronic device and storage medium |
| CN111750851A (en)* | 2019-09-10 | 2020-10-09 | 广东小天才科技有限公司 | A method, device and intelligent device for identifying moving mode between floors |
| CN110907981A (en)* | 2019-12-09 | 2020-03-24 | Oppo广东移动通信有限公司 | Positioning mode control method and device and electronic equipment |
| CN111368014A (en)* | 2019-12-23 | 2020-07-03 | 广东小天才科技有限公司 | A method for generating motion trajectory, terminal device and storage medium |
| CN111368014B (en)* | 2019-12-23 | 2024-04-19 | 广东小天才科技有限公司 | A method for generating a motion trajectory, a terminal device and a storage medium |
| CN111311748A (en)* | 2020-02-19 | 2020-06-19 | 广东小天才科技有限公司 | Indoor stereogram construction method and device, terminal equipment and storage medium |
| CN111311748B (en)* | 2020-02-19 | 2023-06-30 | 广东小天才科技有限公司 | Indoor stereogram construction method and device, terminal equipment and storage medium |
| CN114125696A (en)* | 2020-08-31 | 2022-03-01 | 华为技术有限公司 | Construction method, positioning method and device of fingerprint map of multi-floor building |
| WO2022042655A1 (en)* | 2020-08-31 | 2022-03-03 | 华为技术有限公司 | Method for constructing fingerprint map of multi-floor building, positioning method, and apparatus |
| CN112401877A (en)* | 2020-10-27 | 2021-02-26 | 中国电力科学研究院有限公司 | Method and system for monitoring behavior state of target object |
| WO2023005865A1 (en)* | 2021-07-28 | 2023-02-02 | 华为技术有限公司 | Method for constructing indoor map and related apparatus |
| CN113848878A (en)* | 2021-08-24 | 2021-12-28 | 深圳大学 | Construction method of indoor and outdoor 3D pedestrian road network based on crowd-source data |
| CN113848878B (en)* | 2021-08-24 | 2023-08-08 | 深圳大学 | Construction Method of Indoor and Outdoor 3D Pedestrian Network Based on Crowdsource Data |
| CN114111784A (en)* | 2021-10-26 | 2022-03-01 | 杭州电子科技大学 | Crowdsourcing-based automatic construction method and system for indoor corridor map |
| CN116224341A (en)* | 2022-09-08 | 2023-06-06 | 北京交通大学 | Method and system for constructing indoor floor plan based on smart phone sound wave distance measurement |
| CN116184312A (en)* | 2022-12-22 | 2023-05-30 | 泰州雷德波达定位导航科技有限公司 | Indoor crowdsourcing fingerprint library construction method based on semantic Wi-Fi |
| CN116184312B (en)* | 2022-12-22 | 2023-11-21 | 泰州雷德波达定位导航科技有限公司 | Indoor crowdsourcing fingerprint library construction method based on semantic Wi-Fi |
| Publication | Publication Date | Title |
|---|---|---|
| CN106448431A (en) | Mobile phone sensor-based indoor planar graph construction method adopting crowdsourcing mode | |
| CN109525935B (en) | Intelligent floor sensing method and control system for universal indoor environment | |
| Zhou et al. | ALIMC: Activity landmark-based indoor mapping via crowdsourcing | |
| US9664521B2 (en) | System and method for localizing a trackee at a location and mapping the location using signal-based features | |
| Alzantot et al. | Crowdinside: Automatic construction of indoor floorplans | |
| CN106441292B (en) | A kind of building indoor plane figure method for building up based on crowdsourcing IMU inertial guidance data | |
| KR101322778B1 (en) | Method and apparatus for identification of points of interest within a predefined area | |
| CN104180805B (en) | Indoor Pedestrian Location and Tracking Method Based on Smartphone | |
| US11885900B2 (en) | Method and system for tracking a mobile device | |
| CN109413578B (en) | An indoor positioning method based on the fusion of WIFI and PDR | |
| CN108225304A (en) | Based on method for rapidly positioning and system in Multiple Source Sensor room | |
| US20200049832A1 (en) | A method and computer processing apparatus for generating data relating to a vertical structure of a built environment and detecting a floor change | |
| US20160377698A1 (en) | System and a method for tracking mobile objects using cameras and tag devices | |
| CN107036597A (en) | A kind of indoor positioning air navigation aid based on inertial sensor built in smart mobile phone | |
| CN111829516A (en) | An autonomous pedestrian localization method based on smartphone | |
| CN108156580B (en) | A smart phone-based indoor floor location method | |
| CN109211229A (en) | A kind of personnel's indoor orientation method based on mobile phone sensor and WiFi feature | |
| CN106595633A (en) | Indoor positioning method and device | |
| Peng et al. | Indoor floor plan construction through sensing data collected from smartphones | |
| CN106871894B (en) | Map matching method based on conditional random field | |
| CN110413655A (en) | A Floor Recognition Method Based on Improved Hidden Markov Model | |
| Lin et al. | Deep learning-based multifloor indoor tracking scheme using smartphone sensors | |
| Ehrlich et al. | Pedestrian localisation inside buildings based on multi-sensor smartphones | |
| Luo et al. | iMap: Automatic inference of indoor semantics exploiting opportunistic smartphone sensing | |
| Moder et al. | Smartphone-based indoor positioning utilizing motion recognition |
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication | Application publication date:20170222 | |
| WD01 | Invention patent application deemed withdrawn after publication |