# US 11,308,710 B2 · Polygonal region detection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,710 B2 - Document ID: US11308710B2 - Status: Granted - Kind: B2 - Application number: 16/768,062 - Filed: 2018-10-24 - Published: 2020-11-12 - Granted: 2022-04-19 - Earliest claimed: 2018-02-02 - Assignees: Beijing Sankuai Online Technology Co., Ltd - Applicants: Beijing Sankuai Online Technology Co., Ltd - Inventors: Beier Zhu; Rui Zhang - Web page: https://patentgrep.com/patent/US11308710B2 ## CPC - G06T 7/12: Edge-based segmentation - G06T 7/13: Edge detection - G06T 7/136: involving thresholding - G06T 7/543: from line drawings - G06V 10/25: Determination of region of interest [ROI] or a volume of interest [VOI] - G06V 10/457: {by analysing connectivity, e.g. edge linking, connected component analysis or slices} - G06T 2207/10004: Still image; Photographic image - G06T 2207/20061: Hough transform - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Various embodiments provide a polygonal region detection method and apparatus, a computer readable storage medium and an electronic device. In those embodiments, a to-be-detected image can be obtained. A plurality of line segments in the image can be calculated based on a line detection algorithm. The plurality of line segments meeting a merging condition can be merged into a line segment. Crosspoints of the pairwise merged line segments can be calculated according to the merged line segments in the image. A polygonal region can be generated with the crosspoints as vertexes of the polygonal region in the image. ## Claims ### Claim 1 A polygonal region detection method, comprising: obtaining, by at least one processor, a to-be-detected image; calculating, by the at least one processor, line segments in the image based on a line detection algorithm; merging, by the at least one processor, a plurality of line segments meeting a merging condition into a merged line segment; determining, by the at least one processor, crosspoints of pairwise merged line segments according to the merged line segment; and generating, by the at least one processor, a polygonal region with the crosspoints as vertexes of the polygonal region in the image; wherein merging the plurality of line segments meeting the merging condition into the merged line segment comprises: obtaining, by the at least one processor, any two adjacent line segments; calculating, by the at least one processor, projection lengths of the two line segments on the same coordinate axis; and merging, by the at least one processor, the two line segments into a merged line segment when both of vertical distances between two end points of the line segment with the shorter projection length and the other line segment are less than a threshold. ### Claim 2 (depends on 1) The method according to claim 1, wherein merging the two line segments into the line segment comprises: obtaining, by the at least one processor, two farthest end points of the two line segments; and connecting, by the at least one processor, the two end points to obtain a merged line segment. ### Claim 3 (depends on 1) The method according to claim 1, wherein determining the crosspoints of the pairwise merged line segments according to the merged line segments in the image comprises: setting, by the at least one processor, a direction of each merged line segment clockwise or counter clockwise with a center of the image as an origin to obtain a line segment vector; obtaining, by the at least one processor, an intersection point between every two line segment vectors; and determining, by the at least one processor, the intersection point as the crosspoint when the intersection point meets a crosspoint condition. ### Claim 4 (depends on 3) The method according to claim 3, wherein the crosspoint condition comprises the followings: the crosspoint of the two line segment vectors is located in the image; one of the two line segment vectors takes the crosspoint as a terminal point, and the other of the line segment vectors takes the crosspoint as a starting point; and an interior angle constituted by the two line segment vectors meets a set angle range. ### Claim 5 (depends on 1) The method according to claim 1, wherein generating the polygonal region with the crosspoints as the vertexes of the polygonal region in the image comprises: generating, by the at least one processor, the quadrangular region with four crosspoints as the vertexes of the quadrangular region in the image when any four crosspoints meet a condition of generating the quadrangular region. ### Claim 6 (depends on 5) The method according to claim 5, wherein the condition of generating the quadrangular region comprises: obtaining, by the at least one processor, a crosspoint A with a coordinate value being greater than 0 and a crosspoint B with a coordinate value being less than 0 under the same coordinate axis with a center point of the image as an origin of coordinates; obtaining, by the at least one processor, an intersection point C constituted by an incident line segment vector of the crosspoint A and an emergent line segment vector of the crosspoint B; obtaining, by the at least one processor, an intersection point D constituted by an emergent line segment vector of the crosspoint A and an incident line segment vector of the crosspoint B; and determining, by the at least one processor, the points A, B, C and D to meet the condition of generating the quadrangular region when both of the intersection points C and D meet a crosspoint condition; and, wherein the incident line segment vector is a line segment vector pointing to the crosspoint; and the emergent line segment vector is a line segment vector starting from the crosspoint. ### Claim 7 (depends on 1) The method according to claim 1, wherein the method further comprises: calculating, by the at least one processor, a duty ratio of each side of the polygonal region, wherein the duty ratio of each side of the polygonal region is a ratio of a solid line length of the side to a length of the side; and deleting, by the at least one processor, the polygonal region when the duty ratio of each side of the polygonal region does not meet a duty ratio condition. ### Claim 8 (depends on 7) The method according to claim 7, wherein the duty ratio condition comprises at least one of the followings: a sum of duty ratios of any i number of sides is greater than an ith preset duty ratio; or a sum of duty ratios of N number of sides is greater than an Nth preset duty ratio, wherein N is an integer greater than 1; and, wherein i is a positive integer of [1N], and N is the number of sides of the polygonal region; the ith preset duty ratio is greater than an (i−1)th preset duty ratio; and the duty ratio is a value greater than 0 and less than or equal to 1. ### Claim 9 (depends on 1) The method according to claim 1, wherein the method further comprises: calculating, by the at least one processor, a feature parameter vector of each polygonal region when a plurality of polygonal regions are generated, wherein the feature parameter vector comprises at least one feature parameter; ranking, by the at least one processor, the plurality of polygonal regions according to the feature parameter vector of each polygonal region; and determining, by the at least one processor, the preset number of top ranked polygonal regions as optimal polygonal regions. ### Claim 10 (depends on 9) The method according to claim 9, wherein ranking the plurality of polygonal regions according to the feature parameter vector of each polygonal region comprises: calculating, by the at least one processor, a difference value between the feature parameter vectors of the two polygonal regions; and determining, by the at least one processor, a sequence of the two polygonal regions according to a mapping relationship between the difference value and a ranking function. ### Claim 11 (depends on 10) The method according to claim 10, wherein each feature parameter further corresponds to a coefficient when there are a plurality of feature parameters in the feature parameter vector. ### Claim 12 (depends on 9) The method according to claim 9, wherein the feature parameters comprise at least one of the followings: a first feature parameter, denoting a total duty ratio of all sides of the polygonal region; a second feature parameter, denoting a sum of ratios of a projection length of each side of the polygonal region in a main direction to an image length in the main direction; a third feature parameter, denoting a similarity degree between interior angles of the polygonal region and interior angles of a regular polygon; or a fourth feature parameter, denoting a KL divergence between an internal gray and an external gray of the polygonal region. ### Claim 13 A non-transitory computer readable storage medium storing a computer program, wherein when the computer program is executed by a processor, the processor is configured to perform: obtaining a to-be-detected image; calculating line segments in the image based on a line detection algorithm; merging a plurality of line segments meeting a merging condition into a merged line segment; determining crosspoints of the pairwise merged line segments according to the merged line segment; and generating a polygonal region with the crosspoints as vertexes of the polygonal region in the image; wherein merging the plurality of line segments meeting the merging condition into the line segment comprises: obtaining any two adjacent line segments; calculating projection lengths of the two line segments on the same coordinate axis; and merging the two line segments into the line segment when both of vertical distances between two end points of the line segment with the shorter projection length and the other line segment are less than a threshold. ### Claim 14 An electronic device, comprising: a processor; and a memory configured to store an executable instruction of the processor; wherein the processor is configured to perform: obtaining a to-be-detected image; calculating line segments in the image based on a line detection algorithm; merging a plurality of line segments meeting a merging condition into a merged line segment; determining crosspoints of pairwise merged line segments according to the merged line segments; and generating a polygonal region with the crosspoints as vertexes of the polygonal region in the image; wherein merging the plurality of line segments meeting the merging condition into the line segment comprises: obtaining any two adjacent line segments; calculating projection lengths of the two line segments on the same coordinate axis; and merging the two line segments into the line segment when both of vertical distances between two end points of the line segment with the shorter projection length and the other line segment are less than a threshold. ### Claim 15 (depends on 14) The electronic device according to claim 14, wherein merging the two line segments into the line segment comprises: obtaining two farthest end points of the two line segments; and connecting the two end points to obtain a merged line segment. ### Claim 16 (depends on 14) The electronic device according to claim 14, wherein determining the crosspoints of the pairwise merged line segments according to the merged line segments in the image comprises: setting a direction of each merged line segment clockwise or counter clockwise with a center of the image as an origin to obtain a line segment vector; obtaining an intersection point between every two line segment vectors; and determining the intersection point as the crosspoint when the intersection point meets a crosspoint condition. ### Claim 17 (depends on 14) The electronic device according to claim 14, wherein generating the polygonal region with the crosspoints as the vertexes of the polygonal region in the image comprises: generating a quadrangular region with four crosspoints as the vertexes of the quadrangular region in the image when any four crosspoints meet a condition of generating the quadrangular region. ### Claim 18 (depends on 17) The electronic device according to claim 17, wherein generating the quadrangular region with the four crosspoints as the vertexes of the quadrangular region in the image when any four crosspoints meet the condition of generating the quadrangular region comprises: obtaining a crosspoint A with a coordinate value being greater than 0 and a crosspoint B with a coordinate value being less than 0 under the same coordinate axis with a center point of the image as an origin of coordinates; obtaining an intersection point C constituted by an incident line segment vector of the crosspoint A and an emergent line segment vector of the crosspoint B; obtaining an intersection point D constituted by an emergent line segment vector of the crosspoint A and an incident line segment vector of the crosspoint B; and determining the points A, B, C and D to meet the condition of generating the quadrangular region when both of the intersection points C and D meet a crosspoint condition; wherein the incident line segment vector is a line segment vector pointing to the crosspoint; and the emergent line segment vector is a line segment vector starting from the crosspoint.