Invention content
The purpose of the embodiment of the present invention is to provide a kind of high in the clouds map map updating method and equipment based on Octree,Solution can be provided for one or more problems mentioned in above-mentioned background technology, realize high in the clouds map rejuvenation.
To achieve these goals, one embodiment of the invention provides a kind of high in the clouds map updating method based on Octree,This method includes：Receive location information and the cloud point information corresponding to the location information；According to the location information, in OctreeThe Octree that the plane space residing for the position is formed is determined in storage organization；And update this using described cloud informationThe Octree that plane space residing for position is formed.
Optionally, the Octree storage organization memory contains multiple Octrees for default size plane space.
Optionally, using described cloud information come the step of updating Octree that the plane space residing for the position is formedIncluding：In the case where the plane space residing for the position is located within a default size plane space, described cloud is utilizedInformation updates the Octree that the preset plane space size is formed；Or it is located in the plane space residing for the position multipleIn the case of within the intersection region of default size plane space, using described cloud information update to involved by the intersection regionOctree.
Optionally, the location information and corresponding to the location information cloud point information received from movable termination.
Optionally, the location information and corresponding to the location information cloud point via GPRS network or Wifi networks and fromThe movable termination receives.
Correspondingly, one embodiment of the invention also provides a kind of high in the clouds map rejuvenation equipment based on Octree, the equipment packetIt includes：Receiving unit, for receiving location information and the cloud point information corresponding to the location information；Determination unit, for according to instituteLocation information is stated, the Octree that the plane space residing for the position is formed is determined in Octree storage organization；And updateUnit, for updating the Octree that the plane space residing for the position is formed using described cloud information.
Optionally, the Octree storage organization memory contains multiple Octrees for default size plane space.
Optionally, the updating unit is for performing the following operations：It is pre- to be located at one in the plane space residing for the positionIf in the case of within size plane space, update that the preset plane space size is formed using described cloud information eightFork tree；Or it is located at the situation within the intersection region of multiple default size plane spaces in the plane space residing for the positionUnder, using described cloud information update to the Octree involved by the intersection region.
Optionally, the location information and corresponding to the location information cloud point information received from movable termination.
Optionally, the location information and corresponding to the location information cloud point via GPRS network or Wifi networks and fromThe movable termination receives.
Correspondingly, one embodiment of the invention provides a kind of electronic equipment, including：At least one processor；And with instituteState the memory of at least one processor communication connection；Wherein, be stored with can be by least one processor for the memoryThe instruction of execution, described instruction are performed by least one processor, so that at least one processor performs above-mentioned baseIn the high in the clouds map updating method of Octree.
Correspondingly, an embodiment of the present invention provides a kind of non-transient computer readable storage medium storing program for executing, the non-transient calculatingMachine readable storage medium storing program for executing stores computer instruction, and the computer instruction is above-mentioned based on Octree for performing the computerHigh in the clouds map updating method.
Correspondingly, an embodiment of the present invention provides a kind of computer program product, the computer program product includes depositingThe calculation procedure on non-transient computer readable storage medium storing program for executing is stored up, the computer program includes program instruction, when the journeyWhen sequence instruction is computer-executed, the computer is made to perform the above-mentioned high in the clouds map updating method based on Octree.
Through the above technical solutions, by using Octree space storage method, memory space can be saved.On the other hand,When needing to carry out map rejuvenation, can be accurately positioned out in the map that server is stored needs the part changed.
The other feature and advantage of the embodiment of the present invention will be described in detail in subsequent specific embodiment part.
Specific embodiment
The specific embodiment of the embodiment of the present invention is described in detail below in conjunction with attached drawing.It should be understood that thisLocate described specific embodiment and be merely to illustrate and explain the present invention embodiment, be not intended to restrict the invention embodiment.
Fig. 1 is the structure diagram of high in the clouds map updating system that one embodiment of the invention provides.As shown in Figure 1, the cloudEnd, which provides more new system, may include movable equipment 100A-100C and cloud server 200, movable equipment 100A-100CCan be vehicle, 200 memory of cloud server contains high in the clouds map, and each vehicle can ask high in the clouds to the cloud server 200Map, and then navigated according to the high in the clouds map or other operations, such as watch current traffic information (for example, which roadIn traffic congestion, which road is unimpeded etc.).The movable equipment 100A-100C can be via various communications with cloud server 200Network communicates, such as IEEE 802.16 (i.e. worldwide interoperability for microwave accesses (WiMAX)), CDMA2000, CDMA2000 1x,It is CDMA2000EV-DO, Interim Standard 2000 (IS-2000), Interim Standard 95 (IS-95), Interim Standard 856 (IS-856), completeBall mobile communication system (GSM), enhanced data rates for gsm evolution (EDGE), GSM EDGE (GERAN) etc..
Each of wherein described movable equipment 100A-100C can obtain the current location of its own, such as it is worked asFront position coordinate, and the current location and the request of local map corresponding with current location point cloud are sent to the high in the cloudsServer 200, the cloud server 200 may be in response to local map point cloud request, obtained out of its storage high in the clouds mapLocal map point cloud corresponding with the current location, and the cloud is sent back into the movable equipment 100A-100C, withJust movable equipment 100A-100C is navigated using the local map point cloud.The cloud that following embodiment of the present invention is providedEnd map updating method can perform in the cloud server of the high in the clouds map updating system shown in FIG. 1, certainly, and the present inventionFollowing embodiment is also not limited only to perform in the cloud server of high in the clouds map updating system shown in Fig. 1, can be withIt is implemented in the server of existing offline map updating system.
Fig. 2 is the flow chart of the high in the clouds map updating method based on Octree that one embodiment of the invention provides.Such as Fig. 2 institutesShow, the high in the clouds map updating method based on Octree includes：
Step S210 receives location information and the cloud point information corresponding to the location information；
The location information may be, for example, latitude and longitude information, also can be characterize its position in a certain reference frame itsHis location information.The location information can be obtained by the GPS positioning system that is equipped in movable equipment, certainly other can position determinePosition mode is also feasible, and movable equipment can also receive location information and/or based on from two by air interface from base stationOr more the adjacent base station timing of signal that receives determine its position.It is to be appreciated that consistent with embodimentWhile, which can obtain location information by any suitable location determining method.
The cloud point information can perceive surrounding ring by camera, high-resolution laser equipment, infrared video camera etc.The equipment in border obtains, and movable equipment can obtain the environmental information of its present position by the capture device to perceive, such asWhich orientation there are barrier, there are which kind of barrier etc., and as the point cloud information corresponding to the location information.
Step S220 according to the location information, determines the plane space residing for the position in Octree storage organizationThe Octree formed.
Octree (octree) is a kind of tree data structure for being used to describe three dimensions.Each node table of OctreeShow the volume element of a square, each node there are eight child nodes, and the volume element represented by this eight child nodes is added inIt is equal to the volume of father node together.Bifurcated center of the General Central point as node.Fig. 3 divides region for Octree and spaceCorrespondence.As shown in figure 3, a space can be considered as a cuboid (preferably cube), the root section of corresponding OctreePoint；The cuboid is divided into eight level-1 areas again, each level-1 area corresponds to the level-one child node of root node；FurtherEach level-1 area is further partitioned into eight level-2 areas by ground, and each level-2 area corresponds to the level-one corresponding to the level-1 areaThe child node of child node, i.e. two level child node ... are divided in space by the above method layer by layer, corresponding each node of OctreeThe environmental information that corresponding space divides region is stored, such as the space divides in region whether have barrier.It finally, can basisThe environmental information stored in each division region stored in Octree storage organization establishes space map.The present invention is implementedExample is to carry out Octree modeling, the size of General Spatial for giving the region of space size using the data structure of OctreeThe space of 100mx100mx3m can be chosen, if using 0.1m as the resolution ratio in space, corresponding 3D grid sizes are1000x1000x30, by the space compression method based on Octree, the map storage size in this space can be compressed to 10mbWithin space size.
Step S230 updates the Octree that the plane space residing for the position is formed using described cloud information.
The cloud point information is parsed, and analysis result is updated to the cloud using Octree data store organisationIn the octree structure corresponding to the position stored before holding in server.It can be stored with before in the cloud serverOne corresponds to the Octree storage organization of one spatial dimension of Mr. Yu, can be divided into the spatial dimension multiple with the flat of default sizeSpace of planes (for example, 100mx100mx3m), the Octree storage organization is interior to be contained in multiple default size plane spaceThe Octree of each default size plane space, there are node intersections between each other for these Octrees.
The technical solution provided by the embodiment by using Octree space storage method, can save memory space.On the other hand, when needing to carry out map rejuvenation, can be accurately positioned out in the map that server is stored needs the part changed,Only the Octree corresponding to the part is updated, it is convenient and efficient.
Fig. 4 is the flow chart of the high in the clouds map updating method based on Octree that another embodiment of the present invention provides.Such as Fig. 4It is shown, it invents the high in the clouds map updating method based on Octree that another embodiment provides and includes：
Step S410 receives location information and the cloud point information corresponding to the location information.
The principle of this step and the step S210 in previous embodiment realize that process and effect are identical, in order to succinctly hereinIt repeats no more.
Step S420 according to the location information, determines the plane space residing for the position in Octree storage organizationThe Octree formed.
The principle of this step and the step S220 in previous embodiment realize that process and effect are identical, in order to succinctly hereinIt repeats no more.
Step S430, judge the plane space residing for the position be located at a default size plane space within or positionWithin the intersection region of multiple default size plane spaces.It is to be located at a default size in the space plane residing for the positionIn the case of within plane space, step S440 is performed；It is located at multiple default sizes in the plane space residing for the position to put downIn the case of within the intersection region of space of planes, step S450 is performed.
Fig. 5 is is carrying out the plane space schematic diagram involved by the high in the clouds map updating method based on Octree.Such as Fig. 5 institutesShow, the block of two kinds of gray scales is shown in figure, wherein the deeper region of every piece of gray scale can represent the plane space institute of 100m*100mThe Octree of composition, and every piece of shallow region of gray scale friendship can represent eight forks of the intersection region between the deeper region of above-mentioned gray scaleTree.For the point cloud information for corresponding to location A, it is only necessary to carry out environment to the Octree information in the region residing for location AModeling is updated with dynamic map.For the point cloud information for corresponding to B location, it is only necessary to the intersection region residing for B locationOctree information carry out environmental modeling and dynamic map and update.
Step S440 updates the Octree that the preset plane space size is formed using described cloud information.
Step S450, using described cloud information update to the Octree involved by the intersection region.
Fig. 6 is is carrying out the node schematic diagram involved by the high in the clouds map updating method based on Octree.When what is receivedWhen point cloud information corresponds to location A, Map building can be carried out according to the Octree in the region residing for the location A to be deposited before obtainingThe point cloud information in the region corresponding to the location A of storage, and compare the point cloud in the region corresponding to the location A stored before thisInformation and the point cloud information corresponding to location A received, according to difference between the two come eight to the region residing for location AThe child node of fork tree is updated.It, can be according to the region residing for the B location when the point cloud information received corresponds to B locationOctree carry out Map building with the point cloud information in the region corresponding to the B location stored before, and compare this itThe point cloud information in the region corresponding to the B location of preceding storage and the point cloud information corresponding to B location received, according to the twoBetween difference be updated come the child node of the Octree to the region residing for B location.Since B location is related to the zone of intersectionDomain, therefore the update also needs the adjacent child node of the Octree in the region to corresponding to the B location to be updated.It thereby, can be realNow smooth map extraction and map rejuvenation.
Also there are following implementation situations：When the point cloud information received corresponds to location A, according to Octree storage organizationThe point cloud information corresponding to the location A received is parsed to generate Octree；Later, it is sought from Octree storage organizationLook for the Octree in the region corresponding to the location A stored before；Two Octrees are compared, and according between the twoDifference be updated come the child node of the Octree to the region residing for the location A stored in Octree storage organization.WhenWhen the point cloud information received corresponds to B location, according to Octree storage organization to the point cloud corresponding to the B location that is receivedInformation is parsed to generate Octree；Later, the friendship corresponding to the B location stored before from the searching of Octree storage organizationPitch multiple Octrees in region；The Octree that parsing obtains is compared with the correspondence child node in multiple Octree, andIt is saved according to comparison result come the son of multiple Octrees to the intersection region residing for the B location stored in Octree storage organizationPoint is updated.
It should be noted that above-mentioned location information and cloud point information corresponding to the location information can be received from shown in Fig. 1Movable termination in embodiment, the location information and cloud point corresponding to the location information can be via GPRS network or WifiNetwork and from the movable termination receive.Certainly, the present invention is not limited thereto, the location information and corresponding to the position believeThe cloud point information of breath can also store the equipment of the location information and the cloud point information corresponding to the location information received from other.
Fig. 7 is the structure diagram of the high in the clouds map rejuvenation equipment based on Octree that one embodiment of the invention provides.PhaseIt answers, one embodiment of the invention also provides a kind of high in the clouds map rejuvenation equipment based on Octree, which includes：Receiving unit710, for receiving location information and the cloud point information corresponding to the location information；Determination unit 720, for according to the positionInformation determines the Octree that the plane space residing for the position is formed in Octree storage organization；And updating unit730, for updating the Octree that the plane space residing for the position is formed using described cloud information.
Optionally, the Octree storage organization memory contains multiple Octrees for default size plane space.
Optionally, the updating unit 730 is for performing the following operations：It is located at one in the plane space residing for the positionIn the case of within default size plane space, formed using described cloud information to update the preset plane space sizeOctree；Or it is located at the situation within the intersection region of multiple default size plane spaces in the plane space residing for the positionUnder, using described cloud information update to the Octree involved by the intersection region.
Optionally, the location information and corresponding to the location information cloud point information received from movable termination.
Optionally, the location information and corresponding to the location information cloud point via GPRS network or Wifi networks and fromThe movable termination receives.
About the high in the clouds map rejuvenation equipment based on Octree in above-described embodiment, wherein modules perform operationConcrete mode is described in detail in the embodiment in relation to this method, and explanation will be not set forth in detail herein.
Fig. 8 is the hardware configuration signal of the electronic equipment provided in an embodiment of the present invention for performing high in the clouds map updating methodFigure, as shown in figure 8, the equipment includes one or more processors 810 and memory 820, with a processor 810 in Fig. 8For.
Performing the electronic equipment of high in the clouds map updating method can also include：Input unit 830 and output device 840.
Processor 810, memory 820, input unit 830 and output device 840 can pass through bus or other modesIt connects, in Fig. 8 for being connected by bus.
Processor 810 can be central processing unit (Central Processing Unit, CPU).Processor 810 may be used alsoThink other general processors, digital signal processor (Digital Signal Processor, DSP), application-specific integrated circuit(Application Specific Integrated Circuit, ASIC), field programmable gate array (Field-Programmable Gate Array, FPGA) either other programmable logic device, discrete gate or transistor logic,The combination of the chips such as discrete hardware components or above-mentioned all kinds of chips.General processor can be microprocessor or the processingDevice can also be any conventional processor etc..
Memory 820 is used as a kind of non-transient computer readable storage medium storing program for executing, available for storing non-transient software program, non-Transient computer executable program and module, such as the environment sensing modeling method pair of the movable equipment in the embodiment of the present applicationProgram instruction/the module (for example, attached receiving unit shown in Fig. 7 710, determination unit 720 and updating unit 730) answered.PlaceReason device 810 is stored in non-transient software program, instruction and module in memory 820 by operation, so as to execute serverVarious function application and data processing, that is, realize above method embodiment movable equipment environment sensing modeling method.
Memory 820 can include storing program area and storage data field, wherein, storing program area can store operation systemSystem, the required application program of at least one function；Storage data field can be stored to be modeled according to the environment sensing of movable equipmentDevice uses created data etc..In addition, memory 820 can include high-speed random access memory, can also includeNon-transient memory, for example, at least a disk memory, flush memory device or other non-transient solid-state memories.OneIn a little embodiments, memory 820 is optional including relative to the remotely located memory of processor 810, these remote memories canTo pass through the environment sensing model building device of network connection to movable equipment.The example of above-mentioned network includes but not limited to interconnectNet, intranet, LAN, mobile radio communication and combinations thereof.
Input unit 830 can receive input number or character information and generate with the high in the clouds map based on OctreeThe key signals that the user setting and function control of more new equipment are related input.Output device 840 may include the displays such as display screenEquipment.
One or more of modules are stored in the memory 820, when by one or more of processorsDuring 810 execution, the method as shown in Fig. 2 and 4 is performed.
The said goods can perform the method that the embodiment of the present invention is provided, and has the corresponding function module of execution method and hasBeneficial effect, the technical detail of detailed description in the present embodiment, not for details, reference can be made to the phase in the embodiment as shown in Fig. 2 and 4Close description.
The embodiment of the present invention additionally provides a kind of non-transient computer storage medium, and the computer storage media is stored withComputer executable instructions, the computer executable instructions can perform the ring of the movable equipment in above-mentioned any means embodimentBorder Sensing model method.Wherein, the storage medium can be magnetic disc, CD, read-only memory (Read-OnlyMemory, ROM), random access memory (Random Access Memory, RAM), flash memory (FlashMemory), hard disk (Hard Disk Drive, abbreviation：) or solid state disk (Solid-State Drive, SSD) etc. HDD；InstituteThe combination of memory of mentioned kind can also be included by stating storage medium.
It is that can lead to it will be understood by those skilled in the art that realizing all or part of flow in above-described embodiment methodIt crosses computer program and is completed to instruct relevant hardware, the program can be stored in a computer read/write memory mediumIn, the program is when being executed, it may include such as the flow of the embodiment of above-mentioned each method.Wherein, the storage medium can be magneticDish, CD, read-only memory (ROM) or random access memory (RAM) etc..
Although being described in conjunction with the accompanying the embodiment of the present invention, those skilled in the art can not depart from the present inventionSpirit and scope in the case of various modifications and variations can be made, such modifications and variations are each fallen within by appended claims instituteWithin the scope of restriction.