CN102968822A - Three-dimensional medical image segmentation method based on graph theory - Google Patents

Abstract

The invention discloses a three-dimensional medical image segmentation method based on the graph theory. The three-dimensional medical image segmentation method based on the graph theory is characterized by including: (1), a bilateral filtering model is used for removing speckle noise in a three-dimensional medical image; (2) mapping from a three-dimensional image to a three-dimensional diagram is built, statistics is performed on an adjacency relation between top points, and weight of the side for connecting the two top points is calculated; (3) nonincremental sequencing is performed on the weight of each side in the diagram, each tree generated at last is guaranteed to be a minimum spanning tree; (4) an area comparison criterion is defined and used for performing statistics on statistical information difference of voxel gray level of two areas and difference statistical information of each inner voxel gray level of the two areas; and (5) all sequenced sides in the diagram are gone through, the area comparison criterion is used as a judging criterion, fusion is performed if the judging criterion is fit, each area corresponds to one minimum spanning tree, and finally a forest is formed. The three-dimensional medical image segmentation method based on the graph theory improves accuracy of extraction of area-of-interest in segmentation of the three-dimensional medical image and simultaneously has robustness on inherent speckle noise and weak boundary.

Description

A kind of dividing method of the 3 d medical images based on graph theory

Technical field

The present invention relates to computing machine and move in technical field of medical image processing, particularly a kind of dividing method of the 3 d medical images based on graph theory.

Background technology

Medical Image Processing and to analyze be the key components of medical image increases day by day to the function influence of medical research and clinical practice, and its result makes the clinician more direct, more clear to the observation of inside of human body diseased region, and diagnosis rate is also higher.From image area-of-interest being separated is that graphical analysis and identification are at first to need the problem that solves, its restricting image process in development and the application of other correlation technique, for this problem, people have proposed image Segmentation Technology.It refers to according to the pixel characteristic of image image is divided into a series of each other mutual not overlapping homogeneous zones, and extracts technology and the process in interesting target zone.The 3 d medical images cutting techniques is the important technology during 3 d medical images is processed and analyzed, because the characteristic of tissue echo is different, there are inevitably noise and weak, false boundary problem in the medical image, picture quality may be not high, thus 3 d medical images to cut apart be the classic problem of ultrasonoscopy process field.

Summary of the invention

The shortcoming that the object of the invention is to overcome prior art provides a kind of dividing method that can effectively solve the 3 d medical images of over-segmentation and less divided with not enough.

In order to achieve the above object, the present invention is by the following technical solutions:

The dividing method of a kind of 3 d medical images based on graph theory of the present invention comprises the steps:

(1), uses bilateral filtering model, the speckle noise in the removal medical image;

(2), set up 3-D view to the mapping of three-dimensional plot, the syntople between the statistics summit and the weight of calculating the limit that connects two summits;

(3), the weight on each limit among the figure is carried out nonincremental ordering, guarantee that the last every one tree that generates all is minimum spanning tree;

(4), defined range is to criterion relatively, in order to statistical information difference and two intra-zones voxel of object gray difference statistical information separately of the voxel intensity of adding up two zones;

(5), all limits after the ordering among the figure are traveled through, with regional correlation than criterion as judgment criterion, the words that meet merge, each corresponding minimum spanning tree in zone forms a forest at last.

Preferably, step (2) is specially, set up image to figure G=(V, E) mapping, G representative graph wherein, V represents vertex set, E representative edge collection, the syntople between the statistics summit and the weight of calculating the limit that connects two summits, each voxel is regarded as a summit in the image herein, each voxel is connected with its 26 neighborhood, obtains the limit of figure, the weights on limit are corresponding two tissue points v _iAnd v _j. voxel value difference, i.e. gray scale difference is with I (v _i) the expression vertex v _iIntensity, i.e. herein gray scale, the expression formula of gray scale difference is as follows:

w _ij=|I(v _i)-I(v _j)|。

Preferably, in the step (4), defined range contrast criterion is specially: in order to the similarity degree in two zones is assessed, statistical information difference and two intra-zones voxel of object gray difference statistical information separately according to each tissue points gray scale compare, determine whether to merge this two zones, in figure G, difference, intra-zone difference and zone are to penetralia difference between the meeting defined range;

At first, region difference: to any two zones

Area difference between them is the difference of their gray averages, and expression formula is as follows:

Dif(C ₁,C ₂)=|μ(C ₁)-μ(C ₂)|

Secondly, intra-zone difference: to arbitrary region

Its inner variance is defined as the standard variance of its minimum spanning tree, and expression formula is:

Int(C)=σ(C)

At last, regional to minimum internal diversity:

MInt(C ₁,C ₂)=min(Int(C ₁)+τ(C ₁),Int(C ₂)+τ(C ₂))

Wherein τ () is threshold function, is defined as follows:

$\mathrm{\τ}\left(C\right)=\frac{k}{\left|C\right|}\·(1+\frac{1}{\mathrm{\α}})$

Wherein k and α are two positive parameters, | C| represents the size of regional C, and namely should the zone contained voxel sum can be adjusted by adjusting k, α the dividing degree of image.

Preferably, described region difference, intra-zone difference and zone can obtain regional correlation than criterion to minimum internal diversity, are used for judging two adjacent regional C of cutting procedure ₁And C ₂Whether merge, wherein

Be defined as follows:

$D({\mathrm{<figure-callout\; id="1"\; label="C"\; filenames="HDA00002046844300021.png,HDA00002046844300032.png"\; state="\{\{state\}\}">C</figure-callout>}}_1,C_2)=\left\{\begin{array}{cc}\mathrm{true},& \mathrm{if\; Dif}({\mathrm{<figure-callout\; id="1"\; label="C"\; filenames="HDA00002046844300021.png,HDA00002046844300032.png"\; state="\{\{state\}\}">C</figure-callout>}}_1,C_2)>\mathrm{MInt}({\mathrm{<figure-callout\; id="1"\; label="C"\; filenames="HDA00002046844300021.png,HDA00002046844300032.png"\; state="\{\{state\}\}">C</figure-callout>}}_1,C_2)\\ \mathrm{false},& \mathrm{other}\end{array}\right.$

When region difference is D (C greater than the zone to minimum internal diversity ₁, C ₂) be true time, regional C ₁And C ₂Do not merge, otherwise then these two zones are merged.

Preferably, in the step (5), before merging, see each summit as an independently subgraph, then travel through all the ordering after the limit collection, if the limit of current traversal belongs to two different zones, then determine whether to merge this two zones according to judgment criterion, if merge, then form a larger zone, the like, until traveled through all limits, final original figure forms a forest, wherein every a subgraph of setting in the corresponding diagram, also a zone in the representative image.

The present invention has following advantage and effect with respect to prior art:

1, the present invention has used simple in structure and has had the graph-theory techniques that abundant theory is supported, has proposed the three-dimensional medical image segmentation method based on graph theory: at first select a kind of bilateral filtering model, ultrasonoscopy is carried out denoising; Then set up 3-D view to the mapping of three-dimensional plot, the syntople between the statistics summit and the weight of calculating the limit that connects two summits; Again the weight on each limit among the figure is carried out nonincremental ordering, ordering is in order to guarantee that the last every one tree that generates all is minimum spanning tree; Defined range is to criterion relatively afterwards, in order to statistical information difference and two intra-zones voxel of object gray difference statistical information separately of the voxel intensity of adding up two zones; Then all limits after the ordering among the figure are traveled through, with regional correlation than criterion as judgment criterion, the words that meet merge, each corresponding minimum spanning tree in zone forms a forest at last; In the image segmentation process, suitably adjust adjustable parameter wherein, can effectively solve over-segmentation and less divided phenomenon, can cut apart 3-D view more exactly, obtain desirable segmentation effect.This method has robustness to speckle noise intrinsic in the 3 d medical images and weak boundary.

Description of drawings

Fig. 1 is process flow diagram of the present invention;

Fig. 2 (a) is that present embodiment six neighborhoods are built the synoptic diagram of module;

Fig. 2 (b) is that present embodiment 12 neighborhoods are built the synoptic diagram of module;

Fig. 3 (a)-Fig. 3 (f) is the construction process figure of the minimum spanning tree that relates to of present embodiment graph theory;

Fig. 4 (a), 5(a), 6(a)-Fig. 4 (f), 5(f), 6(f) dividing method of present embodiment and the dividing method of existing snakes method and FCM design sketch that the fetus phantom is cut apart;

Fig. 4 (g), Fig. 5 (g), Fig. 6 (g) are the result schematic diagrams that among present embodiment Fig. 4 (f), Fig. 5 (f), Fig. 6 (f) area-of-interest is shown separately.

Embodiment

The present invention is described in further detail below in conjunction with embodiment and accompanying drawing, but embodiments of the present invention are not limited to this.

Implement the medical image that the technical program needs medical supply to collect, the Type B ultrasonoscopy that present embodiment has used the ultrasonic device instrument to collect in this stage, extracting view data with computing machine from the Type B ultrasonoscopy is reconstructed into 3 d medical images and then carries out three-dimensional segmentation, show graphical interface of user with pure flat escope, can adopt C and C Plus Plus to work out all kinds of handling procedures, just can implement preferably the present invention.

System results of the present invention mainly comprises and building figure and two stages of fusion as shown in Figure 1; Present embodiment comprises the steps: based on the dividing method of the 3 d medical images of graph theory

(1), uses bilateral filtering model, the speckle noise in the removal medical image;

(2), set up 3-D view to the mapping of three-dimensional plot, the syntople between the statistics summit and the weight of calculating the limit that connects two summits;

(3), the weight on each limit among the figure is carried out nonincremental ordering, guarantee that the last every one tree that generates all is minimum spanning tree;

(4), defined range is to criterion relatively, in order to statistical information difference and two intra-zones voxel of object gray difference statistical information separately of the voxel intensity of adding up two zones;

(5), all limits after the ordering among the figure are traveled through, with regional correlation than criterion as judgment criterion, the words that meet merge, each corresponding minimum spanning tree in zone forms a forest at last.

Building the figure stage is to set up image to the mapping of figure, mainly is syntople and calculating limit power between the statistics summit; Fusing stage is to determine according to decision criteria whether two adjacent areas merge, the decision criteria of using is that regional correlation is than criterion, wherein defined intra-zone comparison criterion, interregional comparison criterion and zone to the inner criterion of minimum, according to above-mentioned three concept definition regional correlations than criterion.

The figure stage of building in the present embodiment is namely set up image to figure G=(V, E) mapping (wherein G representative graph, V represent vertex set, E representative edge collection), mainly be the syntople between the statistics summit and the weight of calculating the limit on two summits of connection.A tissue points in each summit corresponding three-dimensional medical image, every limit is connecting two tissue points.Because there are 26 neighborhood points on each summit (tissue points) in the 3 d medical images, so the kind of syntople is more.Take A as datum vertex, can consider its three in abutting connection with direction (being top to bottom, left and right, front and rear six neighborhoods), six in abutting connection with direction (i.e. 12 neighborhoods) or 13 in abutting connection with direction (26 neighborhood), etc.Shown in Fig. 2 (a) and Fig. 2 (b), list six neighborhoods and built the figure template with these two of 12 neighborhoods, in order to image is traveled through, other template is similarly.The weights on limit are two tissue points v that the limit connects _iAnd v _jGray scale difference (with I (v _i) the expression vertex v _iI.e. herein the gray scale of intensity), expression formula is as follows:

w _ij＝|I(v _i)-I(v _j)|

The weights on limit have reflected the similar or difference degree between the summit, and namely the strength difference between the summit reflects herein is gray difference between the summit.The scheme that the definition of the weights on limit is herein just used at present also can be chosen more suitably weights definition, certainly in order to obtain better segmentation result in research and implementation from now on.

The weight to each limit among the figure in the present embodiment sorts with nonincremental order, and ordering is in order to guarantee that the last every one tree that generates all is minimum spanning tree.The weight sum of minimum spanning tree namely under this tree each summit (tissue points) gray scale and be minimum in all spanning trees, therefore can guarantee that the similarity of every corresponding each voxel of intra-zone of minimum spanning tree is the highest, and the difference between the different tree is maximum.Fig. 3 is the construction process of minimum spanning tree, and Fig. 3 (a) weighs with the limit on initial summit, contains 6 summits, and 10 limits make all limits invalid (it is arranged sequentially that limit power is pressed non-decreasing); Fig. 3 (b) selects minimum edge power to begin to construct minimum spanning tree, includes these two summits in the spanning tree scope, makes the limit effective; Fig. 3 (c) selects the summit V5 nearest with spanning tree in the residue summit, includes spanning tree in, makes corresponding limit effective; Fig. 3 (d) selects the summit V4 nearest with spanning tree in the residue summit, includes spanning tree in, makes corresponding limit effective; Fig. 3 (e) selects the summit V2 nearest with spanning tree in the residue summit, includes spanning tree in, makes corresponding limit effective; Fig. 3 (e) selects the summit V2 nearest with spanning tree in the residue summit, includes spanning tree in, makes corresponding limit effective.The minimum spanning tree structure is complete.Fig. 3 (a) has provided limit and the limit power of original summit and existence, and opposite side power is carried out the ordering of non-decreasing, and makes all limits invalid (6 summits, 10 possible limits); Fig. 3 (b) selects minimum limit power, connects two summits that this limit connects, and makes this limit effective, and these two summits are included in the spanning tree; Fig. 3 (c), 3(d), 3(e), 3(f) in the residue summit, select a not summit in spanning tree at every turn, the limit power on the summit in this summit and the spanning tree has minimum limit power in the residue invalid edges, with choose the summit include the spanning tree scope in, and so that the limit that connects is effective.Final spanning tree has minimum limit power summation, therefore is called minimum spanning tree.

Defined range in the present embodiment is to comparing criterion, compare in order to statistical information difference and two intra-zones voxel of object gray difference statistical information separately to the voxel intensity between two zones, determined whether by comparative result and merge these two zones.

In this decision criteria, need the following several concepts of definition:

At first be intra-zone difference: to arbitrary region

Its inner variance is defined as the standard variance σ (C) (the corresponding minimum spanning tree in each zone) of its minimum spanning tree, and expression formula is:

Int(C)=σ(C)

Intra-zone difference has embodied the dispersion degree of voxel intensity, and variance is less, and the intensity profile of intra-zone voxel is more concentrated, and then intra-zone is more level and smooth; Otherwise variance is larger, and the intensity profile of intra-zone voxel is overstepping the bounds of propriety loose, and the inside in zone is just more level and smooth so.

Next is region difference: to any two zones

Area difference between them is the difference (gray average is the average of the gray scale of all voxels of same zone) of their gray averages, and expression formula is as follows:

Dif(C ₁,C ₂)＝|μ(C ₁)-μ(C ₂)|

Wherein μ (C) is the gray average of regional C.

Then be the zone to minimum internal diversity: it to the intra-zone difference in two zones and separately threshold function and compare, wherein less value just represents that this zone is to (being regional C ₁And C ₂) minimum internal diversity, and directly get simply the internal diversity smaller in two zones, expression formula is as follows:

MInt(C ₁,C ₂)=min(Int(C ₁)+τ(C ₁),Int(C ₂)+τ(C ₂))

Wherein τ () is threshold function, is defined as follows:

$\mathrm{\&tau;}\left(C\right)=\frac{k}{\left|C\right|}\&CenterDot;(1+\frac{1}{\mathrm{\&alpha;}})$

Wherein k and α are two positive parameters, | C| represents the size of regional C, namely should the zone contained voxel sum; Can adjust by adjusting k, α the dividing degree of image.

The defined formula of region difference, intra-zone difference and threshold function is the scheme that this patent is used at present, can update in the middle of research and implementation backward in the hope of obtaining more suitably comparison criterion.Also may be defined as the difference of each regional standard variance, threshold function exponentially that threshold function can be existing definition or linearly proportional etc. such as region difference.

At last, use above three concepts and can obtain regional correlation than criterion, be used for judging two adjacent regional C of cutting procedure ₁And C ₂(wherein

) whether merge, be defined as follows:

$D({\mathrm{<figure-callout\; id="1"\; label="C"\; filenames="HDA00002046844300021.png,HDA00002046844300032.png"\; state="\{\{state\}\}">C</figure-callout>}}_1,C_2)=\left\{\begin{array}{cc}\mathrm{true},& \mathrm{if\; Dif}({\mathrm{<figure-callout\; id="1"\; label="C"\; filenames="HDA00002046844300021.png,HDA00002046844300032.png"\; state="\{\{state\}\}">C</figure-callout>}}_1,C_2)>\mathrm{MInt}({\mathrm{<figure-callout\; id="1"\; label="C"\; filenames="HDA00002046844300021.png,HDA00002046844300032.png"\; state="\{\{state\}\}">C</figure-callout>}}_1,C_2)\\ \mathrm{false},& \mathrm{other}\end{array}\right.$

When region difference is D (C greater than the zone to minimum internal diversity ₁, C ₂) be true time, regional C ₁And C ₂Do not merge, otherwise then these two zones are merged.

Parameter alpha is adjusted result's segmentation precision by the adjustment of control band signal to noise ratio (S/N ratio) to threshold function from microcosmic.Work as area size | C| and k one timing, α is less, and threshold function τ (C) and zone are to minimum internal diversity MInt (C ₁, C ₂) just larger, the possibility of fusion increases thereupon; Vice versa.Similar, k dividing degree of result on the macroscopic view is adjusted, and works as area size | C| and α one regularly, k is less, threshold function τ (C) and regional to minimum internal diversity MInt (C ₁, C ₂) just less, the possibility of fusion reduces thereupon; Vice versa.

The fusing stage of this embodiment, at the beginning of merging, each summit (being tissue points) can see and make an independently i.e. zone independently of subgraph, so to carrying out facility with limit after the non-incremental order ordering among the figure.When two zones are adjacent areas, when they have similar gray average and meet regional correlation than this cor-responding identified theorems of criterion, then these two zones are fused into a large zone, relatively proceed, until traveled through all limits, final original figure has formed a forest, wherein every a subgraph of setting in the corresponding diagram, also a zone in the representative image.

Following experiment is the 3 d medical images segmentation effect that adopts method of the present invention front and back, is used for the validity of checking the inventive method.

In order to measure the segmentation accuracy of the inventive method, we have carried out split-run test to 10 width of cloth from the three-dimensional type-B ultrasonic figure that fetus phantom, resolution phantom and tissue collect, and compare with result that other partitioning algorithm obtains, show that such as Fig. 4,5,6 wherein a width of cloth three-dimensional ultrasound pattern uses several diverse ways to cut apart the contrast effect figure of generation.Fig. 4 (a), 5 (a), 6(a) be that original three-dimensional data is called for short former figure; Fig. 4 (b), 5(b), 6(b) be to use the bilateral filtering model raw data to be processed the filtering result who obtains; Fig. 4 (c), 5(c), 6(c) be the profile of the area-of-interest that obtains with the snakes method, this profile obviously and initial profile have near the certain difference, particularly both feet; Fig. 4 (d), 5(d), 6(d) be to cut apart the result who obtains with algorithm of the present invention, each corresponding a kind of different color in zone can identify different zones very soon; Fig. 4 (e), 5 (e), 6(e) be the result who from (d), area-of-interest is shown separately, the area-of-interest of this figure is the health of fetus; Fig. 4 (f), 5(f), 6(f) be to cut apart the result who obtains with FCM Algorithms, it is three kinds that the classification number is got in this experiment, the corresponding a kind of color of every class; Fig. 4 (g), 5 (g), 6(g) be the result who from (f), area-of-interest is shown separately.Fig. 4 (e), 5(e), 6(e), (g) be respectively the area-of-interest in the segmentation result of the inventive method and FCM clustering method, area-of-interest during clustering method is cut apart is that the fetus body part namely is divided into different classifications by over-segmentation, and the extracorporeal subregion of fetus is divided into a class with the fetus health on every side, and clearly: segmentation effect of the present invention is better than the segmentation effect of FCM cluster.In summary, segmentation effect of the present invention obviously is better than snakes method and FCM clustering method.

As shown in table 1 below, with the inventive method and other two kinds classical methods, 8 width of cloth are cut apart from the three-dimensional data that the resolution phantom gathers, show that various distinct methods carry out the accuracy measurement result that three-dimensional segmentation produces.Can find out that from this table using accuracy that the inventive method cuts apart is that the effect cut apart of the method for FCM is good than traditional snakes method and classical fuzzy c clustering method, accuracy has improved a lot.

Table 1

Above-described embodiment is the better embodiment of the present invention; but embodiments of the present invention are not restricted to the described embodiments; other any do not deviate from change, the modification done under Spirit Essence of the present invention and the principle, substitutes, combination, simplify; all should be the substitute mode of equivalence, be included within protection scope of the present invention.

Claims (5)

1. the dividing method based on the 3 d medical images of graph theory is characterized in that, comprises the steps:

(1), uses bilateral filtering model, the speckle noise in the removal medical image;

(2), set up 3-D view to the mapping of three-dimensional plot, the syntople between the statistics summit and the weight of calculating the limit that connects two summits;

(3), the weight on each limit among the figure is carried out nonincremental ordering, guarantee that the last every one tree that generates all is minimum spanning tree;

(4), defined range is to criterion relatively, in order to statistical information difference and two intra-zones voxel of object gray difference statistical information separately of the voxel intensity of adding up two zones;

(5), all limits after the ordering among the figure are traveled through, with regional correlation than criterion as judgment criterion, the words that meet merge, each corresponding minimum spanning tree in zone forms a forest at last.

2. the dividing method of the 3 d medical images based on graph theory according to claim 1 is characterized in that step (2) is specially, set up image to figure G=(V, E) mapping, G representative graph wherein, V represents vertex set, E representative edge collection, syntople between the statistics summit and the weight of calculating the limit that connects two summits are regarded each voxel as a summit in the image herein, and each voxel is connected with its 26 neighborhood, obtain the limit of figure, the weights on limit are corresponding two tissue points v _iAnd v _j. voxel value difference, i.e. gray scale difference is with I (v _i) the expression vertex v _iIntensity, i.e. herein gray scale, the expression formula of gray scale difference is as follows:

w _ij=|I(v _i)-I(v _j)|。

3. the dividing method of the 3 d medical images based on graph theory according to claim 1, it is characterized in that, in the step (4), defined range contrast criterion is specially: in order to the similarity degree in two zones is assessed, statistical information difference and two intra-zones voxel of object gray difference statistical information separately according to each tissue points gray scale compare, determine whether to merge this two zones, in figure G, difference, intra-zone difference and zone are to penetralia difference between the meeting defined range;

At first, region difference: to any two zones

Area difference between them is the difference of their gray averages, and expression formula is as follows:

Dif(C ₁,C ₂)＝|μ(C ₁)-μ(C ₂)|

Secondly, intra-zone difference: to arbitrary region

Its inner variance is defined as the standard variance of its minimum spanning tree, and expression formula is:

Int(C)=σ(C)

At last, regional to minimum internal diversity:

MInt(C ₁,C ₂)=min(Int(C ₁)+τ(C ₁),Int(C ₂)+τ(C ₂))

Wherein τ () is threshold function, is defined as follows:

$\mathrm{\&tau;}\left(C\right)=\frac{k}{\left|C\right|}\&CenterDot;(1+\frac{1}{\mathrm{\&alpha;}})$

Wherein k and α are two positive parameters, | C| represents the size of regional C, and namely should the zone contained voxel sum can be adjusted by adjusting k, α the dividing degree of image.

4. the dividing method of the 3 d medical images based on graph theory according to claim 3, it is characterized in that, described region difference, intra-zone difference and zone can obtain regional correlation than criterion to minimum internal diversity, are used for judging two adjacent regional C of cutting procedure ₁And C ₂Whether merge, wherein

Be defined as follows:

$D(C_1,C_2)=\left\{\begin{array}{cc}\mathrm{true},& \mathrm{if\; Dif}(C_1,C_2)>\mathrm{MInt}(C_1,C_2)\\ \mathrm{false},& \mathrm{other}\end{array}\right.$

When region difference is D (C greater than the zone to minimum internal diversity ₁, C ₂) be true time, regional C ₁And C ₂Do not merge, otherwise then these two zones are merged.

5. the dividing method of the 3 d medical images based on graph theory according to claim 1, it is characterized in that, in the step (5), before merging, see each summit as an independently subgraph, then travel through all the ordering after the limit collection, if the limit of current traversal belongs to two different zones, then determine whether to merge this two zones according to judgment criterion, if merge, then form a larger zone, the like, until traveled through all limits, final original figure forms a forest, the wherein subgraph of every tree in the corresponding diagram, also a zone in the representative image.

Images