CN119338816B - Room processing method, system and equipment for full-coverage search task - Google Patents

Abstract

The invention relates to a room processing method, a system and equipment for a full coverage search task, which are used for carrying out image processing and room segmentation on a map established by an unmanned aerial vehicle by utilizing an OpenCV open source computer vision library by providing a room processing means based on OpenCV edge detection and a two-way connected edge table data structure. The room is segmented by adopting Canny edge detection and Hough transformation technology, and is represented by DCEL data structures, so that room segmentation and topology construction under a full-coverage search task are effectively completed, structural information is provided for subsequent multi-robot (unmanned aerial vehicle) task allocation and search, and experimental results show that the method is better in processing various complex room structures.

Description

Room processing method, system and equipment for full-coverage search task

Technical Field

The invention belongs to the technical field of image processing, and relates to a room processing method, system and equipment for a full-coverage search task.

Background

When performing a full coverage search task for a specified spatial region, there are mainly two methods for decomposing the spatial region environment, one is a classical cell (cell) decomposition method and the other is a cell grid (grid) method. The cell decomposition method decomposes unobstructed free space into simple, non-overlapping regions. One of the simplest unit decomposition methods is a trapezoidal decomposition method which deals with only planar polygonal obstacle spaces, and a decomposition method based on Morse decomposition has the ability to deal with non-polygonal spaces, but it cannot deal with a linear environment. The decomposition method based on the unit grids has the decision difficulty in terms of grid size, roughness and complexity. Thus, in summary, for room decomposition of a spatial environment with walls and doors, the present decomposition technology has a technical problem that room segmentation and topology construction under the task of full coverage search are difficult to effectively perform.

Disclosure of Invention

Aiming at the problems in the traditional method, the invention provides a room processing method facing the full-coverage search task, a room processing system facing the full-coverage search task and a computer device, which can effectively perform room segmentation and topology construction under the full-coverage search task.

In order to achieve the above object, the embodiment of the present invention adopts the following technical scheme:

in one aspect, a room processing method for a full coverage search task is provided, including the steps of:

Sweeping a task space area by using an unmanned aerial vehicle and constructing an original map by using a SLAM algorithm;

image enhancement and edge detection are carried out on an original map by applying a Canny algorithm in an OpenCV library, so that a clear map image is obtained;

Extracting line segments of the map image by using Hough transformation, detecting straight lines in the map image and finishing the datamation of the map image;

Establishing DCEL data structures of the map images according to the set half-connection rules according to the straight lines of the map images;

After extracting the vertexes and edges in the map image by utilizing the DCEL data structure, traversing all half edges in the DCEL data structure to obtain all faces;

and constructing a room topological graph corresponding to the map image by using the vertexes, the edges and the faces.

In another aspect, a room processing system facing to a full coverage search task is provided, including:

the map building module is used for sweeping the task space area through the unmanned aerial vehicle and building an original map by using a SLAM algorithm;

the image enhancement module is used for carrying out image enhancement and edge detection on the original map by applying a Canny algorithm in an OpenCV library to obtain a clear map image;

The data processing module is used for extracting line segments of the map image by using Hough transformation, detecting straight lines in the map image and finishing data processing of the map image;

The structure building module is used for building DCEL data structures of the map images according to the straight lines of the dataized map images and the set half connection rules;

The plane segmentation module is used for traversing all half sides in the DCEL data structure to obtain all surfaces after extracting vertexes and sides in the map image by utilizing the DCEL data structure;

and the topology construction module is used for constructing a room topology map corresponding to the map image by using the vertexes, the edges and the faces.

In yet another aspect, a computer device is provided, including a memory storing a computer program and a processor implementing the steps of the room processing method described above for a full coverage search task when the computer program is executed by the processor.

In yet another aspect, there is also provided a computer readable storage medium having stored thereon a computer program which, when executed by a processor, performs the steps of the room processing method for a full coverage search task described above.

One of the above technical solutions has the following advantages and beneficial effects:

According to the room processing method, system and equipment for the full-coverage search task, through providing a room processing means based on OpenCV edge detection and two-way communication edge table (DCEL) data structures, an OpenCV open source computer vision library is utilized to perform image processing and room segmentation on a map established by an unmanned aerial vehicle. The room is segmented by adopting Canny edge detection and Hough transformation technology, a DCEL data structure is used for representing the room, room segmentation and topology construction under the full-coverage search task are effectively completed, structural information is provided for subsequent multi-robot (unmanned aerial vehicle) task allocation and search, and experimental results show that the method is better in processing various complex room structures (such as concave polygons, hole polygons and the like).

Drawings

In order to more clearly illustrate the technical solutions of the embodiments or the conventional techniques of the present invention, the drawings required for the descriptions of the embodiments or the conventional techniques will be briefly described below, and it is apparent that the drawings in the following description are only some embodiments of the present invention, and other drawings may be obtained according to the drawings without inventive effort for those skilled in the art.

FIG. 1 is a flow diagram of a room processing method facing a full coverage search task in one embodiment;

FIG. 2 is an effect diagram of an original map constructed by SLAM algorithm in one embodiment;

FIG. 3 is a schematic diagram of Canny edge detection results in one embodiment;

FIG. 4 is a schematic diagram of a Hough transform detection line effect in one embodiment;

FIG. 5 is an exemplary diagram of a dual connection edge table in one embodiment;

FIG. 6 is a flow diagram of constructing DCEL a linked list of data structures in one embodiment;

FIG. 7 is a schematic diagram of an application scenario of a room processing method facing a full coverage search task in one embodiment;

FIG. 8 is a schematic diagram of a room cut, area, and constructed topology graph in one embodiment, wherein (a) is a room cut and area schematic and (b) is a constructed topology graph;

FIG. 9 is a block diagram of a room processing system facing a full coverage search task in one embodiment.

Detailed Description

The present invention will be described in further detail with reference to the drawings and examples, in order to make the objects, technical solutions and advantages of the present invention more apparent. It should be understood that the specific embodiments described herein are for purposes of illustration only and are not intended to limit the scope of the invention. Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. The terminology used in the description of the invention herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention.

It is noted that reference herein to "an embodiment" means that a particular feature, structure, or characteristic described in connection with the embodiment may be included in at least one embodiment of the invention. The appearances of the phrase in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Those skilled in the art will appreciate that the embodiments described herein may be combined with other embodiments. The term "and/or" as used in the present specification and the appended claims refers to any and all possible combinations of one or more of the associated listed items, and includes such combinations.

Embodiments of the present invention will be described in detail below with reference to the attached drawings in the drawings of the embodiments of the present invention.

Plane segmentation (Planar Subdivision) is a fundamental problem in computational geometry, and refers to the process of dividing a plane into several mutually disjoint regions with a set of line segments or curves. These areas are often referred to as facets or cells. Plane segmentation may be seen as a division or decomposition of a plane such that points inside each region satisfy some specific property or relationship. Plane segmentation is typically represented by a planar rectilinear graph (PLANAR STRAIGHT-LINE GRAPH) whose vertices correspond to the end points and intersection points of line segments, edges correspond to line segments or to the curve itself, and faces correspond to the segmented regions.

There are many ways of planar segmentation, of which the scan line algorithm is more common. The scanning line algorithm sorts and updates the line segments according to the intersecting condition of the scanning lines and the line segments through a vertical scanning line which scans the plane from left to right, so as to obtain a plane segmentation result. The researcher applies a scanline algorithm to generate an optimal coverage path that breaks the coverage area into sub-areas, selects a sequence of these sub-areas, and then generates a path that covers each sub-area in turn. In the conventional scan line algorithm, the scan directions of all sub-regions are the same, and researchers have proven that for a convex polygon environment, one side perpendicular to the boundary of the coverage region is the direction of optimal single scan line decomposition based on the conventional scan line algorithm.

On this basis, researchers have also proposed the concept of minimum height and (MSA) decomposition, which can lead to better decomposition results by allowing different sub-regions to use different scan directions. To generate the MSA decomposition, researchers use scan line decompositions in multiple directions to obtain an initial cell decomposition, which is then combined using a dynamic programming algorithm. The method effectively combines the advantages of a scanning line algorithm and dynamic programming. Furthermore, researchers have also revealed the inherent link of optimal decomposition to polygonal diameter functions by analyzing the scanline decomposition process.

In recent years, another popular approach is the DCEL (doubly connected edge list) structure-based approach. DCEL is a common data structure that contains three basic elements, face, half, and vertex. Researchers have proposed a plane segmentation method based on DCEL, which has the innovation point of being capable of processing overlapped polygons, and also capable of processing complex situations such as polygon superposition without edge intersection, polygons with holes and the like. Also researchers have proposed a distributed DCEL method (distributed doubly connected edge list, DCEL) that extends DCEL to distributed environments where DDCEL uses a two-stage paradigm to generate vertices, half-edges, and faces, which has significant performance advantages over the prior art that supports large-scale spatial networks.

For room decomposition processing of space environment with walls and doors facing the full coverage search task, no intensive research work exists at present, and the problem is solved by image processing calculation in the specification. The DCEL data structure is innovatively used for representing and organizing points, line segments and planes in the bitmap, the SLAM (Simultaneous Localization AND MAPPING, instant positioning and mapping) map is divided, the area of each room is calculated, and the vertex weighted topological graph is successfully constructed, so that task allocation of subsequent rooms is facilitated.

The method based on DCEL data structure can segment the map and even the overlapped map well, and DCEL can be further expanded to a distributed environment. However, the use of DCEL data structures in map segmentation for robotic (unmanned) full coverage search tasks has not been studied in the prior art. Furthermore, research has found that there is no way to connect segmented rooms through gates, modeling vertices in a topology graph connected by edges, and construction of this topology graph is critical for a full coverage search robot (unmanned aerial vehicle) because the topology graph is the basis for task allocation.

For better understanding of the technical solutions given in the present specification, the following first describes related technical terms related to the present specification:

SLAM is a widely used technology in robots and autonomous vehicles that allows robots to construct a map of an environment and determine their own position in the map simultaneously in an unknown environment. This technique is achieved by incorporating inputs from sensors such as lidar, cameras and inertial measurement units. Basic composition of SLAM:

(1) Sensor data a laser radar (LiDAR) calculates distance by emitting a laser beam and measuring the time it is reflected back, thus constructing a 3D point cloud of the surrounding environment. The camera captures images of the environment, and motion can be estimated and a map constructed by visual algorithms (e.g., feature point matching, optical flow methods, etc.). An Inertial Measurement Unit (IMU) then provides information about the acceleration and angular velocity of the robot for aiding in positioning and reducing errors. (2) Front-end processing, namely processing sensor data in real time, extracting characteristic points or image characteristics in the environment, and carrying out preliminary motion estimation. (3) And (3) back-end optimization, namely optimizing the motion estimation and map information obtained by the front end, reducing accumulated errors and improving the accuracy and the robustness of the system. Common methods include graph optimization, filters (e.g., kalman filters, particle filters, etc.), and the like. (4) And loop detection, namely identifying whether the robot returns to the position visited before, which is helpful for correcting accumulated errors and realizing map construction of global consistency. (5) And constructing a map of the surrounding environment according to the data and the processing result of the sensor. The map may be a sparse feature point map, a semi-dense depth map, or a dense three-dimensional reconstructed map.

Image processing refers to a technique of analyzing and processing an image with a computer to extract useful information, improve visual effects, or satisfy other demands. Image processing generally includes parts such as image compression, enhancement and restoration, matching, description, and recognition. Specifically, the method comprises the following steps:

(1) Image transformation by converting the processing in the spatial domain into processing in the transform domain using various image transformation methods such as fourier transform, walsh transform, discrete cosine transform, etc., to reduce the amount of computation and obtain more efficient processing. (2) Image coding compression, namely, the data quantity of the descriptive image is reduced through coding compression technology, so that the image transmission and processing time are saved, and the occupied memory capacity is reduced. (3) The image enhancement and restoration aims to improve the quality of the image, such as noise removal, image definition improvement and the like, and the image enhancement does not consider the reason of image degradation, while the image restoration principle requires that the reason of image degradation is known to a certain extent, a degradation model is built according to the degradation process, and then the original image is restored or reconstructed by adopting a certain filtering method. (4) Image segmentation, namely extracting meaningful characteristic parts in an image, such as edges, areas and the like in the image, which is the basis for further image recognition, analysis and understanding. (5) Image description, which is a necessary premise for image recognition and understanding, can be used for describing the characteristics of objects by adopting geometric characteristics of binary images, and image description of general images comprises two-dimensional shape description (boundary description and region description), two-dimensional texture feature description and the like. (6) The image classification (recognition) belongs to the category of pattern recognition, and the main content is that the image is subjected to certain preprocessing (enhancement, restoration and compression) and then subjected to image segmentation and feature extraction, so that judgment classification is carried out.

OpenCV (Open Source Computer Vision Library) is an open source computer vision and machine learning software library which provides rich functions and algorithms and is widely applied to the fields of image processing, image analysis, machine vision and the like. Cross-platform computer vision libraries based on Apache 2.0 permissions can run on a variety of operating systems such as Linux, windows, macOS, android and iOS. Functional features of OpenCV include:

(1) And the image processing comprises the steps of providing basic image processing functions such as filtering, edge detection, image transformation and the like, and carrying out operations such as enhancement, noise reduction, smoothing, restoration and the like on the image. (2) The object detection and recognition support algorithms such as face detection, target tracking and image segmentation, and the like, and can be used for applications such as real-time monitoring, image analysis, video monitoring and the like. (3) Feature extraction and description, namely providing feature extraction and description algorithms such as SIFT (Scale-INVARIANT FEATURE TRANSFORM, scale invariant feature transform), SURF (Speeded Up Robust Features, accelerated robust feature), ORB (Oriented FAST and Rotated BRIEF) and the like, and being used for tasks such as image registration, panoramic stitching and the like. (4) The machine learning algorithm comprises a normal Bayes, K nearest neighbors, a support vector machine, a decision tree, a random forest, an artificial neural network and the like, and can be used for tasks such as image classification, clustering and the like. (5) Deep learning DNN (Deep Neural Network ) module supports loading of pre-trained deep learning models for advanced tasks such as image recognition and target detection.

Hough (Hough transform) straight line-Hough straight line transform in OpenCV is a technique of detecting a straight line in an image, which converts a straight line detection problem into an accumulation problem of a parameter space by representing the straight line in the image in a polar coordinate space. The following is a detailed explanation of Hough line transformation in OpenCV:

(1) The basic principle of hough transform is that the hough space is a feature space for image analysis describing line segments or curves of the same shape in the image, and for straight line detection the dimension of the parameter space is 2, i.e. the slope and intercept of the straight line (usually denoted distance and angle in polar coordinates). (2) Mapping mechanism, which maps points in the image space to the parameter space, wherein a straight line in the image space corresponds to one point in the parameter space, and the point in the image space corresponds to one curve in the parameter space. (3) Voting mechanism-each edge point "votes" for each potential line in the parameter space to which it may belong, the position of the vote being dependent on the angle of the line and its distance from the origin, each element in the accumulator array receiving the votes and accumulating the votes. (4) Peak detection-analyzing the accumulator array to find the cell with the highest vote count, these peaks representing the line supported by the highest number of edge points and being considered the most likely line in the image.

A two-way linked list (Double Connected Edge List, DCEL) is a data structure that represents a planar polygonal mesh (e.g., polygon partition, etc.). It builds the structure of the graph primarily through the interconnection of edges (Edges), vertices (Vertices), and Faces (Faces) so that each element has two-way access to its neighbors. DCEL is widely used in the fields of computational geometry and graphics, especially in dealing with problems such as polygon segmentation, clipping and boolean operations. DCEL is mainly composed of the following three parts:

(1) Edges (Edges) each connect two vertices and belong to two faces (or just to an outer region, a boundary), each has two pointers in DCEL, one pointing to the vertex from which it starts and the other pointing to the vertex from which it ends (destination), and each also points to the face to the left (leftFace) and to the face to the Right (RIGHTFACE), in some cases only one face or both face pointers may point to a particular "outer" or "infinite" face if the edge is part of an outer boundary. (2) Vertices Vertices are corner points of a polygon, each edge starting at or ending at a vertex, and DCEL each vertex maintains a list (typically a circular or doubly linked list) pointing to all edges from the vertex. (3) Faces (Faces) are regions surrounded by edges, either inside or outside the polygon, and in DCEL each face maintains a list (also typically a circular or doubly linked list) pointing to all edges around the face, which list may contain all boundary edges for the outside region.

The topology graph is an abstract graph, and is mainly used for showing the connection mode between devices in a network, and not showing the physical position or distance of the devices. It derives from topology, a method to study geometric characteristics independent of size, distance. In the fields of network management, communication, computer science, etc., topology plays a key role because it helps people to more clearly understand the structure and interaction of complex systems. The topological graph mainly comprises the following elements:

(1) Nodes-representing devices in the network such as routers, switches, servers, etc. These nodes are the basic elements in the topology graph for representing the actual devices in the network. (2) Links, representing the connection between nodes, are typically represented by wires, cables or optical fibers. Links are key elements of connecting nodes in a topology graph that demonstrate physical or logical connections between devices. (3) The weight (optional) represents the cost or delay of the connection, such as delay time or bandwidth size. This element is very useful in evaluating network performance and can help people understand how good the different connection paths are.

In one embodiment, as shown in fig. 1, a room processing method facing a full coverage search task is provided, which may include the following processing steps S10 to S20:

S10, sweeping a task space area through an unmanned plane and constructing an original map by using a SLAM algorithm;

S12, performing image enhancement and edge detection on an original map by applying a Canny algorithm in an OpenCV library to obtain a clear map image;

S14, extracting line segments of the map image by using Hough transformation, detecting straight lines in the map image and finishing the datamation of the map image;

s16, establishing DCEL data structures of the map images according to the set half-edge connection rules according to the straight lines of the map images;

S18, after extracting the vertexes and edges in the map image by utilizing the DCEL data structure, traversing all half edges in the DCEL data structure to obtain all faces;

S20, constructing a room topological graph corresponding to the map image by using the vertexes, the edges and the faces.

According to the room processing method facing the full coverage search task, through providing a room processing means based on OpenCV edge detection and a two-way communication edge table (DCEL) data structure, an OpenCV open source computer vision library is utilized to perform image processing and room segmentation on a map established by an unmanned aerial vehicle. The room is segmented by adopting Canny edge detection and Hough transformation technology, a DCEL data structure is used for representing the room, room segmentation and topology construction under the full-coverage search task are effectively completed, structural information is provided for subsequent multi-robot (unmanned aerial vehicle) task allocation and search, and experimental results show that the method is better in processing various complex room structures (such as concave polygons, hole polygons and the like).

It should be noted that, assuming that the SLAM algorithm is constructed to obtain a bitmap (referred to as an original map) of the unknown space environment as shown in fig. 2, the lines in fig. 2 represent obstacles or walls. Because the map boundary blurring, noise and other conditions may occur in the original map constructed by the SLAM algorithm, the original map needs to be processed first to enhance the definition of the image, and after the relatively clear map image is obtained, the line segments in the map image need to be detected and the room needs to be cut off by the line segments, so as to complete the room area processing.

Firstly, image enhancement and edge detection are carried out, wherein a map constructed by SLAM algorithm is an RGB three-channel image, and the image can be converted into a single channel by graying operation, so that the data processing process is simplified. To enhance the sharpness of the wall (image contour), edge detection is performed using classical Canny algorithm. The Canny algorithm is a multi-scale edge detection algorithm, aims to obtain the accurate boundary of an image, and can achieve the effects of optimizing the definition of the image and enabling the image description after data processing to be more accurate.

The Canny algorithm is widely applied to the field of image processing and is continuously improved and innovated. Using Canny edge detection, there are typically several steps of denoising the image prior to detecting the image edges, typically using a gaussian smoothing filter to reduce noise, calculating gradient magnitude and direction, typically at 4 angles, 0, 45, 90 and 135 degrees, performing non-maximum suppression to eliminate non-edge pixels, leaving only a few thin lines, and selecting a hysteresis threshold that requires retaining or excluding two thresholds for the pixels to select an edge. A clear map image can be obtained using the Canny algorithm as shown in fig. 3.

And then carrying out line segment extraction, namely completing the task of cutting a room by Hough transformation, so that the image generated by Canny edge detection is subjected to line detection by using Hough transformation in the embodiment, and obtaining line segment coordinates. The Hough transform is mainly used to detect geometric shapes in images, such as straight lines and circles. The Hough transformation principle is to identify the target shape by mapping pixel points in a map image to a parameter space and searching peak points in the parameter space by accumulation.

In the aspect of straight line detection, the Hough transformation maps each pixel point in the map image into a curve in a parameter space, and an intersection point of the straight line in the parameter space is the straight line in the map image.

In one embodiment, regarding the step S14, the process of detecting the straight line in the map image may further include the following processing steps:

dividing line segments in the map image into two types of horizontal line segments and vertical line segments, and setting a spacing threshold;

For the horizontal line segments, if the difference between the vertical coordinates of the two horizontal line segments is smaller than the interval threshold value and the horizontal coordinates are overlapped, determining that the two horizontal line segments are overlapped;

for the vertical line segments, if the difference between the abscissas of the two vertical line segments is smaller than the interval threshold value and the ordinates of the two vertical line segments are overlapped, determining that the two vertical line segments are overlapped line segments;

and respectively reserving the longest line segments in the overlapped line segments.

It should be noted that, in this embodiment, the existence of the gate is ignored by the line segment obtained by Hough transformation by adjusting the parameters, and the effect can be shown in fig. 4, and it can be seen that although all the line segments are detected, there is a phenomenon that the line segments overlap. In order to solve the overlapping problem, the line segments are divided into two types of horizontal line segments and vertical line segments, and a proper interval threshold is set according to the size and the shape of the map to distinguish the horizontal line segments from the vertical line segments without leakage. For horizontal line segments, if the difference between the abscissas of the two line segments is smaller than the spacing threshold and the abscissas are overlapped, the overlapped line segments are regarded as overlapped line segments, and for vertical line segments, if the difference between the abscissas of the two line segments is smaller than the spacing threshold and the abscissas are overlapped, the line segments overlapped with each other are screened out, and then the longest line segment in the overlapped line segments is reserved, so that the line segment screening is completed.

In one embodiment, regarding the above step S14, the process of completing the datamation of the map image may further include the following processing steps:

if the pair of horizontal line segments and the vertical line segment are determined to be disjoint, and the difference between the ordinate of the horizontal line segment and the abscissa of the vertical line segment is smaller than the interval threshold value, the line segment with the relatively smaller length is prolonged, so that the horizontal line segment and the vertical line segment are intersected.

It will be appreciated that to prevent the line segments that would otherwise intersect from breaking, the ordinate of the horizontal line segments are compared with the abscissa of the vertical line segments, and if it is determined that they do not intersect and the difference between the abscissa and the ordinate is within the spacing threshold, they should originally coincide, at which time the line segments of smaller length are lengthened to ensure intersection with longer line segments. Thus, relatively accurate line segment coordinates are obtained, and the datamation of the map image is finally completed.

Then, sub-region segmentation and area calculation based on DCEL data structures are performed. The digitized map image requires cutting out the boundary of each room. And then according to the conversion of the pixel length of the boundary and the actual length (such as the wall length), the length of each room in the map image is calculated, so that the area calculation of each room can be performed, and a good foundation is laid for the subsequent balanced distribution task and area of multiple robots (unmanned aerial vehicles). The focus of this stage is therefore how to use DCEL data structures for vertex and edge representation, and process computations for the plan view and line segments.

The extraction of the walls from the map image is followed by the representation of a plurality of line segments, which form a room and which are associated with a corner vertex, which require appropriate data structures and calculation steps.

As shown in FIG. 5, DCEL (Doubly Connected Edge List, double-linked list) is a common data structure suitable for use in a plane-connected graph representing an embedded plane. DCEL is a Half-Edge based data structure that links vertices, edges, and faces together, and DCEL constructors generate and store each segmented vertex, half, and face given an input space network represented by a set of line segments.

A vertex is a node at which two or more line segments intersect, corresponding to a graph vertex of a spatial network, such as a corner of a room in a map area where a plurality of walls intersect. The half is segmented by line segments along their length and has directional components, a start vertex and a target vertex. Two opposite-directional halves (double halves) represent each undirected line segment, with the starting vertex of the first half being the target vertex of the second half, and vice versa. Thus, each half corresponds to a directed graph edge (wall) in space.

Depending on the orientation of the half, a relationship between the vertices and the half may be established where the half has a starting vertex and a target vertex, each half is assigned to its starting vertex, ordered clockwise, and added to the list of half starting vertices. For example, in FIG. 5, the half assigned to vertex A is ordered clockwise by e1, e2, and e3. The face is formed by connecting the vertexes and the half edges with the same direction end to end, and half edge connection rules are set for constructing the connection between the half edges and the face. The rule for half connection may be such that the halves of vertex A are ordered clockwise e1, e2 and e3, with half e1.Twin being first made to be the next half e2, then so on, half e2.Twin being the next half e3, half e3.Twin being the next half e1. And processing the half-edge list of all vertexes according to the connection rule to complete DCEL data structure construction.

The vertices and half-edges can be directly extracted from the input line segment, the two endpoints of the line segment represent the two vertices of the line segment, and each line segment (undirected edge) is represented by two half-edges (directed edges). Unlike extracting vertices and half, extracting faces is not straightforward. To generate all faces of the planar segment, DCEL construct a function calls a concrete flow that extracts all closed polygons formed by the set of planar line segments.

The specific flow is as shown in fig. 6, with the vertex set v= { V1, V2, & gt, vn }, the edge set e= { E1, E2, em, n and m are positive integers not less than 2, and previous and next relations represent front and back relations of half, respectively. The DCEL data structure of the undirected plan G is a linked list made up of half sides, and the input is line segment information in the map. Since the Hough transform results in a line segment that is as long as possible, there are intersections in the middle of the line segment rather than undirected edges. In this embodiment, intersecting line segments are found, and longer line segments are divided into small line segments at the intersection points, so that room re-representation is completed, and at this time, no intersection point exists between the line segments, which represents an undirected edge in the map image. From this information, a vertex list and a half-side list of the map image can be created.

Starting from one half, the surface can be enclosed by the connected half back to the starting point. It can be seen from fig. 5 that the left side of the passing half is the enclosed surface. Thus after constructing DCEL data structures, each half is checked, if not already associated with a face, then to the left plane of that edge, and loops forward to the next edge until it returns to the original edge. And finally, each face is corresponding to the first associated half, so that all faces are represented and the relationship between the half and the face is completed.

After DCEL data structure construction is completed, a vertex is given, half of the vertex starting from that vertex can be obtained and ordered in a clockwise direction. Given a half, it may correspond to the left face of that half. Given a face, one of the halves that make up the face can be obtained. Thus, the connection between the vertex and the half side and the surface is completed.

Further, by traversing DCEL all halves of the data structure, all facets can be obtained, each of which is calculated in area. For a face, traversing DCEL the half of the data structure that makes up the face, calculating the cross products of the adjacent halves and summing, and dividing by 2 to obtain the directed area. Finally, the area and the vertex of each face (i.e., room) are output as shown in fig. 8. The room area values of fig. 7 can well correspond to areas in the map image, so the method of map segmentation and area calculation through DCEL data structures is efficient and accurate.

In practical application, an original map can be constructed by sweeping a specified unknown space region (also called a task space region) through an unmanned plane and using a SLAM algorithm, edge detection is performed by applying a Canny algorithm in an OpenCV library, straight lines in a map image are detected by using Hough transformation, and then a DCEL data structure of the map image is established through straight line information according to the processing procedure of the DCEL data structure which is introduced in an important way, so that plane segmentation can be conveniently performed, and the problems of representing and cutting L-shaped rooms are solved. Finally, the area and vertex information of each room are obtained to draw a topological graph of the task environment where the unmanned aerial vehicle is currently located, as shown in fig. 7 and 8, preparation is provided for task allocation of multiple robots (unmanned aerial vehicles), in fig. 8, w represents the area size of the room in the physical world and also corresponds to the weight of the corresponding vertex in the topological graph.

Specifically, after the aerial unmanned aerial vehicle rapidly scans a large area to generate an original map, the ground multi-robot system can divide the map into small rooms by using the scheme, and then allocate the rooms to each ground robot, so that the subsequent full-coverage search process is completed at the fastest time and the ground robots have no mutual interference. The proposal is a room processing means based on OpenCV edge detection and a two-way communication edge table (DCEL) data structure, and experimental results verify the effectiveness of the proposal and the important basic function of the proposal on task allocation of heterogeneous ground robot systems.

It should be understood that, although the steps in fig. 1 are shown in sequence as indicated by arrows, the steps are not necessarily performed in sequence as indicated by the arrows. The steps are not strictly limited to the order of execution unless explicitly recited herein, and the steps may be executed in other orders. Moreover, at least a portion of the steps of fig. 1 may include multiple sub-steps or stages that are not necessarily performed at the same time, but may be performed at different times, nor does the order in which the sub-steps or stages are performed necessarily occur sequentially, but may be performed alternately or alternately with other steps or at least a portion of the sub-steps or stages of other steps.

In one embodiment, as shown in fig. 9, a room processing system 100 for a full coverage search task is provided, which may include a mapping module 11, an image enhancement module 13, a datamation module 15, a structure building module 17, a plane segmentation module 19, and a topology construction module 21. The mapping module 11 is used for sweeping the task space area through the unmanned aerial vehicle and constructing an original map by using a SLAM algorithm. The image enhancement module 13 is configured to apply a Canny algorithm in an OpenCV library to perform image enhancement and edge detection on the original map, so as to obtain a clear map image. The data processing module 15 is configured to perform line segment extraction on the map image using Hough transform, detect a straight line in the map image, and complete data processing of the map image. The structure building module 17 is configured to build a DCEL data structure of the map image according to a set rule of half connection according to the line of the map image that is dataized. The plane segmentation module 19 is configured to extract vertices and edges in the map image by using the DCEL data structure, and traverse all half edges in the DCEL data structure to obtain all faces. The topology construction module 21 is configured to construct a room topology map corresponding to the map image by using the vertices, edges and faces.

The room processing system 100 facing the full coverage search task performs image processing and room segmentation on a map established by an unmanned aerial vehicle by using an OpenCV open source computer vision library by proposing a room processing means based on an OpenCV edge detection and two-way connected edge table (DCEL) data structure. The room is segmented by adopting Canny edge detection and Hough transformation technology, a DCEL data structure is used for representing the room, room segmentation and topology construction under the full-coverage search task are effectively completed, structural information is provided for subsequent multi-robot (unmanned aerial vehicle) task allocation and search, and experimental results show that the method is better in processing various complex room structures (such as concave polygons, hole polygons and the like).

In one embodiment, the data processing module 15 is further configured to divide the line segments in the map image into two types, namely a horizontal line segment and a vertical line segment, and set a distance threshold, determine that the two horizontal line segments overlap the line segments if the difference between the vertical coordinates of the two horizontal line segments is smaller than the distance threshold and the horizontal coordinates overlap, determine that the two vertical line segments overlap the line segments if the difference between the horizontal coordinates of the two vertical line segments is smaller than the distance threshold and the vertical coordinates overlap, and respectively reserve the longest line segments in the overlapping line segments.

In one embodiment, the data processing module 15 is further configured to, in completing the data processing of the map image, extend a line segment with a relatively smaller length to intersect the horizontal line segment and the vertical line segment when it is determined that the pair of horizontal line segment and the vertical line segment are disjoint and a difference between an ordinate of the horizontal line segment and an abscissa of the vertical line segment is smaller than the pitch threshold.

It will be appreciated that, regarding the specific limitation of the room processing system 100 facing the full coverage search task, reference may be made to the corresponding limitation of the room processing method facing the full coverage search task hereinabove, and the description thereof will not be repeated herein.

The various modules in the room processing system 100 described above that are directed to the full coverage search task may all or in part be implemented in software, hardware, and combinations thereof. The above modules may be embedded in hardware or may be independent of a device with a data processing function, or may be stored in a memory of the device in software, so that the processor may call and execute operations corresponding to the above modules, where the device may be, but is not limited to, various image computing devices existing in the art.

In one embodiment, a computer device is provided, which comprises a memory and a processor, wherein the memory stores a computer program, the processor realizes the following processing steps when executing the computer program, namely, sweeping a task space area by an unmanned plane and constructing an original map by using a SLAM algorithm, carrying out image enhancement and edge detection on the original map by using a Canny algorithm in an OpenCV library to obtain a clear map image, carrying out line segment extraction on the map image by using Hough transformation, detecting straight lines in the map image and completing the datamation of the map image, establishing a DCEL data structure of the map image according to a set half-edge connection rule according to the straight lines of the datamation map image, traversing all half edges in a DCEL data structure to obtain all faces after utilizing the DCEL data structure to extract peaks and edges in the map image, and constructing a room topology map corresponding to the map image by utilizing the peaks and the edges.

In one embodiment, the processor may also implement the steps or sub-steps added to the embodiments of the room processing method for the full coverage search task described above when executing the computer program.

In one embodiment, a computer readable storage medium is provided, wherein a computer program is stored on the computer readable storage medium, when the computer program is executed by a processor, the processing steps are realized, namely, a task space area is swept through an unmanned plane, an original map is constructed by using a SLAM algorithm, an image enhancement and edge detection are carried out on the original map by using a Canny algorithm in an OpenCV library to obtain a clear map image, a line segment extraction is carried out on the map image by using Hough transformation, a straight line in the map image is detected, the datamation of the map image is completed, a DCEL data structure of the map image is built according to a set half-edge connection rule according to the straight line of the datamation map image, all half edges in the DCEL data structure are traversed to obtain all faces after the vertexes and edges are extracted by using the DCEL data structure, and a room topological graph corresponding to the map image is constructed by using the vertexes and the edges and the faces.

In an embodiment, the computer program may further implement the steps or sub-steps added in the embodiments of the room processing method for the full coverage search task, when the computer program is executed by the processor.

Those skilled in the art will appreciate that implementing all or part of the above-described methods may be accomplished by way of a computer program, which may be stored on a non-transitory computer readable storage medium and which, when executed, may comprise the steps of the above-described embodiments of the methods. Any reference to memory, storage, database, or other medium used in embodiments provided herein may include non-volatile and/or volatile memory. The nonvolatile memory can include Read Only Memory (ROM), programmable ROM (PROM), electrically Programmable ROM (EPROM), electrically Erasable Programmable ROM (EEPROM), or flash memory. Volatile memory can include Random Access Memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in a variety of forms such as Static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double Data Rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous link (SYNCHLINK) DRAM (SLDRAM), memory bus dynamic random access memory (Rambus DRAM, RDRAM for short), and interface dynamic random access memory (DRDRAM), among others.

The technical features of the above embodiments may be arbitrarily combined, and all possible combinations of the technical features in the above embodiments are not described for brevity of description, however, as long as there is no contradiction between the combinations of the technical features, they should be considered as the scope of the description.

The foregoing examples illustrate only a few embodiments of the invention, which are described in detail and are not to be construed as limiting the scope of the invention. It should be noted that it is possible for those skilled in the art to make several variations and modifications without departing from the spirit of the present invention, which fall within the protection scope of the present invention. The scope of the invention should therefore be pointed out in the appended claims.

Claims (7)

1. A room processing method for a full coverage search task, characterized by comprising the steps of: The original map is constructed by sweeping the mission space area with a drone and using the SLAM algorithm; Apply the Canny algorithm in the OpenCV library to perform image enhancement and edge detection on the original map to obtain a clear map image; Using Hough transform to extract line segments from the map image, detect straight lines in the map image and complete digitization of the map image; According to the straight lines of the digitized map image, the DCEL data structure of the map image is established according to the set half-edge connection rule; the set half-edge connection rule is as follows: the half-edges of vertex A are e1, e2 and e3 after being sorted clockwise, first, the next half-edge of half-edge e1.twin is e2, and then by analogy, the next half-edge of half-edge e2.twin is e3, and the next half-edge of half-edge e3.twin is e1; After extracting vertices and edges in the map image using the DCEL data structure, traverse all half edges in the DCEL data structure to obtain all faces; The room topology map corresponding to the map image is constructed using the vertices, edges and faces. 2. The room processing method for full coverage search task according to claim 1 is characterized in that, in the process of detecting the straight line in the map image, it also includes the steps of: Classifying the line segments in the map image into two categories: horizontal line segments and vertical line segments, and setting a spacing threshold; For a horizontal line segment, if the difference between the ordinates of two horizontal line segments is less than the spacing threshold and the abscissas overlap, the two horizontal line segments are determined to be overlapping line segments; For vertical line segments, if the difference between the horizontal coordinates of two vertical line segments is less than the spacing threshold and the vertical coordinates overlap, the two vertical line segments are determined to be overlapping line segments; The longest line segments among the overlapping line segments are retained respectively. 3. The room processing method for full coverage search task according to claim 2 is characterized in that the process of completing the digitization of the map image further comprises the steps of: If a pair of horizontal line segments and vertical line segments are determined to be non-intersecting, and the difference between the ordinate of the horizontal line segment and the abscissa of the vertical line segment is less than the spacing threshold, the line segment with a relatively smaller length is extended so that the horizontal line segment and the vertical line segment intersect. 4. A room processing system for full coverage search tasks, characterized by comprising: Mapping module, which is used to sweep the mission space area by drone and build the original map using SLAM algorithm; An image enhancement module is used to apply the Canny algorithm in the OpenCV library to perform image enhancement and edge detection on the original map to obtain a clear map image; A digitization module, used for extracting line segments from the map image using Hough transform, detecting straight lines in the map image and completing digitization of the map image; a structure building module, for building a DCEL data structure of the map image according to the straight lines of the digitized map image and the set half-edge connection rule; the set half-edge connection rule is as follows: the half-edges of vertex A are e1, e2 and e3 after being sorted clockwise, firstly, the next half-edge of half-edge e1.twin is e2, and then by analogy, the next half-edge of half-edge e2.twin is e3, and the next half-edge of half-edge e3.twin is e1; A plane segmentation module, used to extract vertices and edges in the map image using the DCEL data structure, and then traverse all half edges in the DCEL data structure to obtain all faces; A topology construction module is used to construct a room topology map corresponding to the map image using the vertices, edges and faces. 5. The room processing system for full coverage search tasks according to claim 4, characterized in that the data module, in the process of detecting the straight line in the map image, is further used to: Classifying the line segments in the map image into two categories: horizontal line segments and vertical line segments, and setting a spacing threshold; For a horizontal line segment, if the difference between the ordinates of two horizontal line segments is less than the spacing threshold and the abscissas overlap, the two horizontal line segments are determined to be overlapping line segments; For vertical line segments, if the difference between the horizontal coordinates of two vertical line segments is less than the spacing threshold and the vertical coordinates overlap, the two vertical line segments are determined to be overlapping line segments; The longest line segments among the overlapping line segments are retained respectively. 6. According to claim 5, the room processing system for full coverage search tasks is characterized in that, in the process of completing the digitization of the map image, the digitization module is also used to extend the line segment with a relatively small length so that the horizontal line segment and the vertical line segment intersect when it is determined that a pair of horizontal line segments and vertical line segments are non-intersecting and the difference between the longitudinal coordinate of the horizontal line segment and the abscissa of the vertical line segment is less than the spacing threshold. 7. A computer device comprising a memory and a processor, wherein the memory stores a computer program, wherein when the processor executes the computer program, the steps of the room processing method for a full coverage search task as described in any one of claims 1 to 3 are implemented.