# US 2021/0065376 A1 · Region Merging Image Segmentation Algorithm Based on Boundary Extraction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0065376 A1
- Document ID: US20210065376A1
- Status: Published application
- Kind: A1
- Application number: 17/086,153
- Filed: 2020-10-30
- Published: 2021-03-04
- Earliest claimed: 2019-02-14
- Assignees: China Institute of Water Resources and Hydropower Research
- Applicants: China Institute of Water Resources and Hydropower Research
- Inventors: Wenlong SONG; Rui TANG; Juan LV; Jingxuan LU; Kun YANG; Zhicheng SU; Yuanyuan DUAN; Xuejun ZHANG; Lihua ZHAO; Yizhu LU; Hongjie LIU
- Web page: https://patentgrep.com/patent/US20210065376A1

## CPC

- G06T 7/187: involving region growing; involving region merging; involving connected component labelling
- G06T 7/11: Region-based segmentation
- G06T 7/12: Edge-based segmentation
- G06T 7/40: Analysis of texture (depth or shape recovery from texture G06T7/529)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A Region Merging image segmentation algorithm based on boundary extraction is disclosed, comprising the steps of calculating a gradient image, extracting a boundary and carrying out initial segmentation and Region Merging, wherein the initial segmentation can be omitted. In the Region Merging process, the ratio of the length of boundary extraction result lies on the adjacent edge between adjacent regions to the length of the adjacent edge is taken as the merging cost, the regions are merged according to the ascending order of the mean gradient value in the region, and a texture difference evaluation mechanism is introduced to remove the error segmentation. The algorithm solves the problems of the other current segmentation algorithms, such as over-segmentation, easy to be influenced by noise and illumination, large in computation and memory consumption, in need of a large number of samples being marked manually and the like. Besides, all regions or all categories achieve the best segmentation result on one final segmentation result. These advantageous features can reduce the computational resource consumption of subsequent tasks and improve their processing effect.

## Claims

### Claim 1

A Region Merging image segmentation algorithm based on boundary extraction, characterized in that steps of the algorithm comprise calculating a gradient image, extracting a boundary, carrying out initial segmentation and Region Merging, wherein
the initial segmentation can be omitted; and
the Region Merging comprises steps of:
(1) sorting all regions according to MO(Rj) by ascending order;
(2) iterate over the sorted regions;
(2.1) iterate over an adjacent region of a current region Ri;
(2.1.1) for a certain adjacent region Rj of the region Ri, if MO(Rj)≤MO(Rj) and Cij≤Tc, remembering the Rj that has smallest MO(Rj);
(2.2) removing the boundary between Rj and the adjacent region Rj that has smallest MO(Rj);
(3) if there being boundaries been broken, back to step 1;
(4) if there being no boundary been broken, go to end.

### Claim 2 (depends on 1)

The Region Merging image segmentation algorithm based on boundary extraction according to claim 1, characterized in that
a texture difference evaluation mechanism can also be added in a Region Merging rule to remove error segmentation, and a Region Merging step after the texture evaluation mechanism is added as follows:
(1) set τind to 0;
(2) sort all regions according to MO(Ri) by ascending order;
(3) set Cind and Σind to 0;
(4) iterate over the sorted regions;
(4.1) iterate over an adjacent region of the current region Ri;
(4.1.1) for a region Rj adjacent to the region Ri, if NO(Rj)≤MO(Ri) and Cij≤Tc;
(4.1.1.1) if RSI(Ri)>Trsi and InDij≤Tind, remember the adjacent region Rj that has the smallest InDij;
(4.1.1.2) if RSI(Ri)≤Trsi, remember the adjacent region Rj that has the smallest InDij;
(4.2) remove the boundary between Ri and its adjacent region Rj that their lea InDij is smallest;
(4.3) let Cind+=1, Σind+=InDij, and
T
ind
=
max

(
T
ind
,
z
ind
C
ind
)
;
(5) If there were boundaries been broken, back to step 2;
(6) If there were no boundaries been broken, go to end.

### Claim 3 (depends on 1)

The Region Merging image segmentation algorithm based on boundary extraction according to claim 1, characterized in that
the merging is carried out according to an ascending order of a gradient mean value in a region, wherein the formula of a region merging order metric MO(Ri) is as follows:
MO(Ri)=avg(Ig(p|p∈Ig∩Ri));
and a merging cost Cij of a region is a length ratio of a part, belonging to a boundary extraction result, of an immediately adjacent edge of an immediately adjacent region, and the formula is as follows:
C
ij
=
Len

(
E
ij
⋂
I
e
)
Len

(
E
ij
)
.

### Claim 4 (depends on 2)

The Region Merging image segmentation algorithm based on boundary extraction according to claim 2, characterized in that
a region intensity index RSI(Ri) is a mean value of the merging cost Cij, larger than a threshold value Tc, of all the immediately adjacent edges of the region Ri, and the formula is as follows:
RSI

(
R
i
)
=
∑
C
ij
>
T
c

C
ij
∑
C
ji
>
T
c

1
.

### Claim 5 (depends on 2)

The Region Merging image segmentation algorithm based on boundary extraction according to claim 2, characterized in that
the merging is carried out according to an ascending order of a gradient mean value in a region, wherein the formula of a region merging order metric MO(Ri) is as follows:
MO(Ri)=avg(Ig(p|p∈Ig∩Ri));
and a merging cost Cij of a region is a length ratio of a part, belonging to a boundary extraction result, of an immediately adjacent edge of an immediately adjacent region, and the formula is as follows:
C
ij
=
Len

(
E
ij
⋂
I
e
)
Len

(
E
ij
)
.
