JP4115934B2 - A method for adapting potential terms to optimal path extraction in real time - Google Patents

Abstract

The invention relates to a method for segmenting an image [IM] by path extraction using minimization of at least a potential [POT], said potential being calculated [CAS] from a feature [FEA] of the image [IM] using a cost assignment function [CAF], said calculation [CAS] being realized using the definition of two groups of points [NP and PP] in a neighborhood of a drawn [DRW] contour: the ones that are considered to be relevant to a boundary, called positive points [PP] and the ones that are not considered to be relevant to said boundary, called negative points [NP]. A refined characterization of positive points is constructed by combining characterizations of positive and negative points and the cost assignment function [CAF] is modified [CAL] using this refined characterization. The invention proposes also a fully automatic simultaneous adaptation of the different cost assignment functions of the individual potentials in a total function of potentials, and their relative weightings.

Description

【Technical field】
[0001]
The present invention relates to a method for image segmentation by path extraction using at least potential minimization, wherein the potential is calculated from image features using a cost distribution function. The method uses contours drawn to modify the cost distribution function.
[Background]
[0002]
Such a method is described in W.W. A. Barrett and E.M. N. Mortensen's paper Interactive Segmentation with Intelligent Scissors, Graphical Models and Image Processing 60, pp 349-384, 1998. Assuming that a contour is drawn that is reasonable compared to the actual image boundary, the potential function is modified to favor a contour that has the same characteristics as a valid drawn contour . This correction is realized by correcting the cost distribution function. The more specific values of features that are considered relevant for a boundary, the lower the cost. Such idea features are symbolized by the characterization of the points in the last segment of the path (called the training path). The potential function is initialized, and during the extraction by minimization of that function, this initial overall characterization is iteratively modified with the point features in the hypothesized effective drawn contour .
[0003]
In conventional methods, point features are defined for points that lie on an assumed valid drawn contour . Therefore, points belonging to the boundary can have various aspects along the drawn path, so that such path extraction is not reliable.
DISCLOSURE OF THE INVENTION
[Means for Solving the Problems]
[0004]
The object of the present invention is an improved method for segmenting an image by path extraction using at least potential minimization, said method using a contour or potential function drawn to modify the potential Is to provide a method. The improved method provides a more reliable and derived potential function.
[0005]
The method according to the invention is:
Initializing the cost distribution function;
Defining two groups of points near the contour to be drawn, the group considered to be related to the boundary is called the positive point, and the group not considered to be related to the boundary is negative Stages, called points;
Defining a positive point characterization from the feature;
Defining a negative point characterization from the feature;
Constructing a refined characterization of positive points by combining positive and negative point characterizations; and using this refined characterization to modify the cost distribution function;
Have
[0006]
The technique of the present invention is based on the definition of points in the “negative” group as well as “positive”. A positive group of points has a point that is considered to be associated with a boundary in the image, meaning a point that is on or near the drawn contour , while a negative group of points has a point that is not considered to be associated with the boundary . Because of the negative information, as the region characterized and considered by the method grows, the resulting potential allows for more reliable extraction of paths by potential minimization.
[0007]
In a preferred embodiment, comparing the characterization of positive and negative points for several potentials, the individual potentials in all potential functions that need to be minimized to find a path. It is useful in adapting to the weighting.
BEST MODE FOR CARRYING OUT THE INVENTION
[0008]
Referring to FIG. 1, the image IM is characterized by at least a potential POT, which is obtained by applying a cost distribution function to the feature FEA in the distribution stage CAS. Its features are intended to represent image boundaries and are obtained directly from the simple operational steps OPE in the image. Such features can be, for example, as follows.
P _G : “gradient characteristics”, ie the magnitude of the gradient,
P _D : “Characteristic of gradient direction”,
P _L : “Laplacian feature”, ie, Laplacian zero crossing P _I (or P _O ): “Internal (or external) intensity feature”, ie at the boundary of the gradient direction (or opposite the gradient direction) Pixel intensity,
P _E : “edge intensity feature”, ie pixel intensity at the boundary.
[0009]
For more details on these features, see W.C. A. Barrett and E.M. N. Mortensen's paper Interactive Segmentation with Intelligent Scissors, Graphical Models and Image Processing 60, pp 349-384, 1998.
[0010]
The main problem with such a path extraction method is that the potential used needs to be appropriate for different boundaries of the image. If the potential is appropriate, ie, the feature is transformed using a cost partition function, the boundary corresponds to the minimum of the potential.
[0011]
Therefore, the potential is adapted to be appropriate for the image. This means that the cost distribution function must be modified to highlight an interesting part of each feature FEA.
[0012]
For some features (eg, pixel intensity), it is difficult to determine which value is suitable without prior knowledge of the boundary to be extracted. As it was drawn in the drawing step DRW contour (e.g., contours drawn by the user) training methods using is why it is useful. The individual potentials are constructed using a cost distribution function CAF that is applied to the feature FEA at the cost distribution CAS stage. Training is used to dynamically modify such a cost distribution function CAF in a calculation phase CAL using information available from the drawing phase DRW. The training method results in a modification of the cost distribution function CAF and therefore a modification of the potential POT.
[0013]
More particularly, the present invention relates to such training aspects of information usage and methods that are available after the drawing phase DRW. The purpose of the training is to adapt the cost distribution function to the characteristics of the contour drawn during path extraction.
[0014]
W. A. Barrett and E.M. N. A paper by Mortensen, Interactive Segmentation with Intelligent Scissors, Graphical Models and Image Processing 60, pp 349-384, 1998, introduced the following scheme. That is, assuming that the contour to be drawn is valid or related to the boundaries present in the image, the cost distribution function is in the calculation stage shown in FIG. 2 because contours having the same aspect for each feature are preferred. Will be corrected. In a preferred embodiment, the contour is drawn by the user because the user can define a first approach of the boundary by looking at the image. FIG. 2 shows an example of point characterization in the form of a curve showing the distribution of points for a parameter of features (eg intensity). The cost distribution function is initialized. For example, the initial cost distribution function is the inverse of the overall histogram GFH of features, which reports the characteristics, ie, the characterization of the distribution of points with respect to intensity, for example. During extraction, the initial characterization GFH is iteratively modified to a new characterization NFC by using information DCI from the drawn contour . The new cost distribution function CAF is therefore the inverse of the new characterization NFC.
[0015]
In conventional methods, training is limited to a portion of the path itself and considers only “positive” information. The present invention proposes to define points for groups of positive and negative training.
[0016]
The group of positive training is near the drawn contour , which is assumed to be associated with a boundary on the image, and the group of negative training is away. In the first embodiment (see FIG. 3a), the positive point is a point on pictured contours and a distance from the first contour is less than the first distance, and, the negative points, to be drawn contour Other points that exist in the rectangular area defined around. This embodiment takes into account many points and therefore requires a long calculation. Another boundary exists in the rectangular area, indicating an error in path extraction.
[0017]
In another embodiment (see FIG. 3b), the distance from the positive point contour drawn present and on the contour drawn is less points than the first distance, and negative points, from pictured contour Another point that is further away from the first distance and closer than the second distance. Both regions now follow the shape of the path as a boundary. This method also considers many points and is therefore time consuming.
[0018]
In the preferred embodiment (see FIG. 3c), a group of positive and negative points has been selected as the translation of the drawn contour DC that is parallel to this drawn contour DC. The group of positive points is the group of p nearest neighbors, and the group of negative points is the group of n next transforms. The points present in the different transformed segments can be weighted by their distance to the training path in the characterization definition. With such weighting, representing the information from the drawn contour DC (eg, the curve DCI in FIG. 2) is because the nearest point of the DC has a stronger weight than the other points in the curve construction. Consider such weighting. The group of negative / positive points can be symmetric with respect to gradient magnitude and edge strength features, as shown in FIG. 3c. However, depending on the direction of the gradient in the path, the direction of the path and the features considered to account for the asymmetry aspect of the “inner” and “outer” features, the asymmetry training region for them It is possible to adopt.
[0019]
Referring to FIG. 1 for the embodiment provided in FIG. 3, the information from the contour drawn is doubled according to the present invention. Here, PP corresponds to a group of positive training points, and NP corresponds to a group of negative training points.
[0020]
Referring to FIG. 4, a group of positive / negative training points builds two distinct training characterizations corresponding to positive points (FIG. 4a) and negative points (FIG. 4b), respectively. Used for. The algebraic difference (Fig. 4c) between the positive characterization (Fig. 4a) and the negative characterization (Fig. 4b) is calculated, and the cost distribution function (Fig. 4d) is the same as shown in Fig. 4c. The scale of the difference is reversed. Referring to FIG. 2, the information DCI from the contour drawn is the algebraic difference between the group of positive points and the group of negative points according to the present invention. This difference defines a refined characterization of positive points. Compared to FIG. 2, in FIG. 4, the cost distribution function is calculated using initializing to zero and therefore not using the overall histogram (or characterization) of the features. For this initialization, it is not necessary to have any a priori knowledge of the cost distribution function.
[0021]
The result of the method according to the present invention is that the use of such a refined positive point characterization significantly detracts from negative region feature values, while positive region gray levels are advantageous. It is to be made.
[0022]
In the preferred embodiment, several potentials corresponding to different features are used. As a result, a potential function is defined, and path extraction minimizes the potential function. In practice, the potential function is a complex potential.
[0023]
Using such a potential allows a significant adaptation of the function that needs to be minimized for the image. The boundary in this case is still defined as the minimum of the potential function.
[0024]
Dijkstra and Cohen and Kimmel have proposed various algorithms to examine paths from such potential functions (A note on two-probe in connection with graphs, Numerche math9, 26 by EW Dijkstra, 1959, and Global Minimum for Active Control Models by L. Cohen and R. Kimmel: a Minimal Path Approach, International Journal of Computer Vision, pp 57-78.
[0025]
For example, the potential function is the sum of the six individual potential weights of the data being driven. It is defined as follows in a graph arc directed from point p to point q.
[0026]
P (p, q) = ω _G P _G (q) + ω _L P _L (q) + ω _D P _D (p, q) + ω _I P _I (q) + ω _O P _O (q) + ω _E P _E (q )
Here, P _G , P _L , P _D , P _O , and P _E are the features described above, but are converted using a cost distribution function so as to have a potential, and ω is a weighting of the corresponding potential. It is.
[0027]
When such a function is defined, another advantage of using a group of positive training points and a group of negative training points is the characterization of both groups of points for each individual potential. Is to facilitate the adaptation of the corresponding individual potential weights in the overall potential function. For example, if the characterization between positive and negative points is sufficiently distinguishable for a given feature, as in FIG. 4, the considered feature is associated with the boundary and its weight is increased. Can be assumed to be possible. This allows for outstanding features to be selected for a given image, or exact features to be selected from a number of features (eg, selection of an appropriate resolution for the contour of the object). .
[0028]
The advantage of using these two positive and negative characterizations is therefore doubled. That is, constructing an adaptive potential for each feature by adapting the cost distribution function configuration, and automatically adapting the weighting of the individual potentials in the potential function as described below.
[0029]
The introduction of the negative region generates not only a better individual potential, but also an automatic weighting of all these potentials in the full function of the potential.
[0030]
Such synergistic segmentation tools allow non-professionals to immediately segment the contours of anatomical objects from any collection mode. Effectively, one need for this segmentation is to outline using visual decisions from the image. The robustness of the method is that when the user requests a path between two points, the minimum potential path can be determined directly by minimizing the potential that the method generates according to the present invention. . This segmentation can be applied in real time by automatic adaptation of the cost distribution function after each contour is drawn.
[0031]
Referring to FIG. 5, the imaging apparatus APP includes an image segmenting apparatus SEG for executing the segmentation method as described above, the imaging apparatus having a display unit DIS, and a drawing unit for defining a contour in the image IM. Have The segmentation device SEG and the display means receive the image IM from the acquisition means ACQ, which may or may not be included in the imaging device APP itself. The segmentation method can be suitably performed on a programmed computer or a special purpose processor having software / hardware means arranged to perform functionalization or calculations in accordance with the present invention.
[0032]
In certain embodiments of such segmentation devices, interactivity has been introduced into the optimal path approach. This method provides the user with greater control over the segmentation process. The idea is as follows. That is, the starting point is selected by the user at the boundary to be extracted and the optimum contour is calculated and drawn in real time between the starting point and the current cursor point. In this way, user control is applied during extraction. This interactivity allows the contours to be drawn to be generated. This means that the device according to the invention has a drawing means DRW that allows the user to interact in real time. The exact training provided by the present invention is an important feature when the user's drawing is not very accurate.
[Brief description of the drawings]
FIG. 1 is a block diagram of a segmentation method according to the present invention.
FIG. 2 is a diagram illustrating a calculation stage of a cost distribution function.
FIG. 3 illustrates several embodiments of the present invention.
FIG. 4 is a diagram illustrating a calculation stage of a cost distribution function according to the present invention.
FIG. 5 is a block diagram of an imaging apparatus in which the present invention is implemented.

Claims (5)

By segmenting means performs the path extraction using minimization of at least potential, a how you segmenting an image, the potential is calculated from the feature of the image using a cost distribution function, it is a method :
Initializing the cost distribution function;
Defining two groups of points in the vicinity of the drawn contour , the group of points considered to be related to the boundary is called a positive point, and the group of points not considered to be related to the boundary is negative A stage, called a point;
Defining the characteristics of a positive point from the features;
Defining a characteristic of a negative point from the feature;
Building an improved characteristic of the positive point by combining the characteristic of the positive point and the characteristic of the negative point; and using the improved characteristic to modify the cost distribution function;
A method having
The neighborhood of the drawn contour is
And each of the lateral regions of the contour intends mimic the shape of the contour around said contour,
A plurality of translation paths having a shape similar to the drawn outline and translated with respect to the drawn outline ;
Selected from the group having
A method characterized by that. The method of claim 1, wherein the negative point and positive point, or the characteristic of the negative point or positive point, uses the weight of the point according to the distance to the drawn contour. A method characterized in that it is defined. The method according to claim 1 or 2, wherein:
Constructing a function of potential by weighting and adding a plurality of potentials corresponding to a plurality of features, wherein the weighting uses the characteristics of the negative points and the characteristics of the positive points in different features Calculated; and minimizing the function of the potential to find the path;
A method characterized by comprising: Image display means;
And the run how you segment the image according to any one of claims 1 to 3 Rousset segment means; drawn drawing means contours to be defined in the image;
An imaging apparatus comprising: The imaging apparatus according to claim 4, wherein the drawing unit is capable of drawing the drawn outline by a user.

Images