[go: up one dir, main page]

EP1938270A2 - Verfahren zur segmentierung in einem n-dimensionalen merkmalsraum und verfahren zur klassifikation auf grundlage von geometrischen eigenschaften segmentierter objekte in einem n-dimensionalen datenraum - Google Patents

Verfahren zur segmentierung in einem n-dimensionalen merkmalsraum und verfahren zur klassifikation auf grundlage von geometrischen eigenschaften segmentierter objekte in einem n-dimensionalen datenraum

Info

Publication number
EP1938270A2
EP1938270A2 EP06806044A EP06806044A EP1938270A2 EP 1938270 A2 EP1938270 A2 EP 1938270A2 EP 06806044 A EP06806044 A EP 06806044A EP 06806044 A EP06806044 A EP 06806044A EP 1938270 A2 EP1938270 A2 EP 1938270A2
Authority
EP
European Patent Office
Prior art keywords
objects
dimensional
space
classes
steps
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP06806044A
Other languages
English (en)
French (fr)
Inventor
Wolf Delong
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Carl Zeiss Microscopy GmbH
Original Assignee
Carl Zeiss Imaging Solutions GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Carl Zeiss Imaging Solutions GmbH filed Critical Carl Zeiss Imaging Solutions GmbH
Publication of EP1938270A2 publication Critical patent/EP1938270A2/de
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/10—Segmentation; Edge detection
    • G06T7/11—Region-based segmentation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/10—Segmentation; Edge detection
    • G06T7/194—Segmentation; Edge detection involving foreground-background segmentation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/60—Type of objects
    • G06V20/69—Microscopic objects, e.g. biological cells or cellular parts
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/10—Image acquisition modality
    • G06T2207/10056—Microscopic image
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/20—Special algorithmic details
    • G06T2207/20092—Interactive image processing based on input by user
    • G06T2207/20104—Interactive definition of region of interest [ROI]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/30—Subject of image; Context of image processing
    • G06T2207/30004—Biomedical image processing
    • G06T2207/30024—Cell structures in vitro; Tissue sections in vitro

Definitions

  • the invention relates to a method for segmenting objects in an n-dimensional feature space, which is present as a data space, and to a method for classification on the basis of geometric properties of segmented objects in an n-dimensional data space.
  • the dimension n of the data space can be any natural number.
  • An example of a 2-dimensional data space is, for example, the amount of data associated with a phase contrast image in the microscopy, an example of a 3-dimensional data space, the amount of data associated with a color image with the color channels R-GB, and an example of a 16-dimensional data space to a radar image with 16 spectral channels associated amount of data.
  • This object to provide a method for segmentation is achieved by a method having the features of claim 1.
  • Advantageous embodiments of this method result from the features of the dependent claims 2 to 4 and 8 to 13.
  • Claim 14 specifies a suitable computer system and claim 15 specifies a suitable computer program product.
  • the segmentation method according to claim 1 comprises the following method steps: In a first step, the user selects a single data area in the n-dimensional feature space. This selected data area is always interpreted by the system as containing at least two classes of objects to be segmented. In subsequent steps, the system first determines a separation function in the n-dimensional feature space to distinguish the at least two classes and subsequently applies this separation function to the entire data space or a larger subset of the data space. This segmentation result is then visually presented to the user in real time.
  • the results can be optimized in a real-time feedback loop using the pattern recognition capabilities of the user. Furthermore, additional features of the objects to be segmented, such as number of objects in the image, relative area of objects, minimum and maximum size, shape factors such as eccentricity, fralal dimension as a measure of the smoothness of the boundary lines or other suitable properties can be given. This information can be specified by the user as well as automatically extracted from the image by suitable methods. If the user is not yet satisfied with the segmentation result achieved, he can subsequently change the selected data area and thus visually display in each case the segmentation result changed by the system due to the then also changed separation function in real time.
  • a larger number of classes can be specified.
  • the number of classes can also be determined by an automatic procedure.
  • a data area should also be selected by the user, which contains pixels or data points of a corresponding number of classes.
  • the separation function can be determined by first determining a reference point of the features (Si) for each dimension of the feature space by a mathematical method, subsequently projecting all data points to all combinations of two-dimensional subspaces of the n-dimensional feature space, and finally by a two-dimensional error minimization method a phase value and an amplitude value to a predetermined wave function are determined so that a suitably defined approximation error for this wave function is minimized by a suitable method.
  • a suitable method For sinusoidal or cosine wave functions, such an approximation error is the sum of the squared differences that is minimized by the least squares method.
  • the wave function is an integer-periodic, continuous function.
  • the wavefunction k is greater than two with k, and the resulting k classes can be combined into at least two classes.
  • the wave function may be three-fold and the resulting three classes may be two Classes are summarized.
  • the classes with the largest local variance of the gray value distribution can be combined.
  • the feature space can be three-dimensional and contain RGB image data of a digital color image.
  • the feature space may be four-dimensional and contain image data of four fluorescence channels acquired with four detectors at different wavelengths of light.
  • the method can be successively applied to different locations of an object by successively selecting different data areas belonging to the same object. By interpreting each of these data areas such that it contains at least two classes of objects to be segmented, and based thereon determining the separation function, several classes then result, at least two of which are subsequently reunited. In this way, for example, an object that is embedded in two or more different backgrounds can be segmented so that the different backgrounds are distinguished.
  • the above method in which the separation function is determined from a wave function, can also be applied to a method for classification on the basis of geometric properties previously according to any method of segmented objects in an n-dimensional data space.
  • first at least two objects are selected as representatives for two different classes in a first step, subsequently a number (m) of geometric features per object is calculated by calculating wavefunctions of different integer wavefunctions and finally the objects are calculated on the basis of the determined number of geometric features or Subsets thereof classified.
  • the previously required segmentation of the objects can in principle be carried out by means of an arbitrary method, but particularly advantageously according to a method according to the present invention.
  • phase values and amplitude values can be calculated from the wave functions, wherein the amplitude values characterize the shape of the objects and the phase values characterize the orientations of the objects.
  • the amplitude values calculated from the wave functions describe the shape of the objects size-invariant, translation-invariant and rotationally invariant.
  • a computer system suitable for carrying out a method according to the invention should have means (1) for interactively inputting and selecting image areas and a monitor for real-time visualization of the results achieved.
  • processor and a data memory for a computer program with a software code by means of which the method according to the invention can be implemented.
  • FIG. 1 a schematic diagram of a system suitable for carrying out the invention
  • FIG. 2 shows a block diagram of the method steps taking place in the segmentation method according to the invention
  • FIG. 3 shows a block diagram of the method steps taking place in the classification method according to the invention
  • FIG. 4 shows a microscope image with cells as a starting point for explaining the method according to the invention
  • FIG. 5 shows the segmented image generated by the system from the image in FIG. 4;
  • FIGS. 6 to 8 shows the segmented image generated by the system from the image in FIG. 4;
  • FIG. 9 explanations of the generation of the dumbbells in FIGS. 6 to 8
  • FIG. 10 a three-dimensional representation of one derived from FIGS. 6 to 8
  • FIG. 11 A phase-contrast image as an example of a texture image
  • FIGS. 12 and 13 FIG.
  • Segmentation method generated feature spaces that are used for the detection of
  • FIG. 14 a two-dimensional histogram of the images in FIGS. 12 and 13;
  • FIG. 15 shows a threefold wave function;
  • 16 the image from FIG. 11 and the feature space of the texture information for a selected pointing region
  • FIG. 17 Images for explaining the shape recognition
  • FIG. 1 shows a system comprising a computer (2) with a built-in main memory (4) and processor (3).
  • main memory (4) is a program loadable, which enables the processor (3) for carrying out the method according to the invention.
  • To the computer (2) is a monitor (1) and an input means (5), e.g. a mouse, connected. Using the mouse, the user can move a pointing area raised in the image displayed by the monitor (1) relative to the image.
  • the pointing area is here provided with the reference numeral (24).
  • the pointing area (24) should be positioned relative to the image such that the pointing area (24) comprises a part of the object (23) to be segmented and a part of the image background (22).
  • the running segmentation process will be explained below with reference to FIG. 2 using the example of a color image.
  • the starting point in this case is the image (7), which exists as color brightness information in the three primary colors red, green and blue as a function of the two spatial coordinates x, y.
  • a first step (8) the user selects a region in the image (7) which should contain the object to be segmented and image background or image parts of two objects to be distinguished.
  • the image information in this selected pointing region is interpreted by the system in a subsequent step (8) such that at least two classes of objects are contained in the selected pointing region.
  • a separation function is determined on the basis of the image information in the pointing area.
  • suitable features such as color brightness values in the three primary colors are analyzed and in a step (10) a reference point of the various features is determined. Then, in a step (11), all data points are projected onto all two-dimensional subspaces of the feature space. From this projection, which will be described in more detail below, phase values and amplitude values that determine the separation function as a wave function result in a subsequent step (12). In a subsequent step (13), this separation function is applied to the entire data space - or the subspace thereof to be segmented - and the result of the segmentation is displayed in real time in a step (14). As already stated above, the user first roughly points to the boundary between an object (23) and the background (24) or to the boundary between two different adjoining objects as indicated in FIG.
  • the user selects an arbitrarily shaped area (22), z. A circle, and positions that pointing area to cover a portion of the object (23) and at the same time a portion of the background (24).
  • the segmentation system can therefore assume that the boundary of an object runs within the circle.
  • it can be assumed that both the texture / color of the object and the texture / color of the background are present in the pointing area. So this is not only a simplification of the necessary work steps, but at the same time an increase in the information content, namely the information about different textures / colors on the one hand and the border between the textures / colors on the other.
  • the set of selected pixels should be such that it can be decomposed into two (or more) disjoint subsets of which one can be assigned to exactly one of several objects or the background.
  • This increased information content can, for example, be exploited so that the recognition of an object can take place online while the user travels the pointing area over the image.
  • the pointing area can be controlled, for example, by a mouse, a touchpad, a touch screen, a trackball, a joystick or other pointing device used to move the cursor on computers, and then a separation function is determined based on the texture / color in the pointing area
  • the result of the segmentation is shown in Fig. 5.
  • a wave function is preferably used, and the determination of a suitable separation function will be described below in more detail by an example.
  • the user has in the process of the invention during the movement in the image with the pointing area the immediate feedback of the computer program (in real time), whether this has correctly detected the object sought, or if corrections are necessary at some edge points of the object.
  • the mean value important for the classification can be optimized by shifting the pointing region, and likewise the representative selection of the relevant pixel subsets can be optimized.
  • Such methods are: a) the selection according to the distance of the local point to the known separation planes or their centers of gravity, b) the interpolation between the planes using the relative image coordinates of the example objects and the current picture element (morphing), c) the use of self-learning approaches such as linear or non-linear neural networks or d) the application of all separation planes and the use of the maximum distance.
  • a) the selection according to the distance of the local point to the known separation planes or their centers of gravity b) the interpolation between the planes using the relative image coordinates of the example objects and the current picture element (morphing)
  • c) the use of self-learning approaches such as linear or non-linear neural networks or d) the application of all separation planes and the use of the maximum distance.
  • the present invention has the further advantage that it works in arbitrarily high-dimensional feature spaces.
  • An example here is the three-dimensional color space with the colors red, green and blue.
  • Another, even higher-dimensional example would be radar images with 16 or more spectral channels.
  • the method is not limited to image processing. It works in any higher-dimensional feature space described by locally changing scalar fields.
  • the constructed classifier for the separation areas is by constructionem invariant against translation, rotation and extension. With suitable further processing, this also applies to the design recognition described in more detail later.
  • Such invariance properties are only possible by the usual methods by complex mathematical treatments such as e.g. To achieve local Fourier analyzes or Gabor wavelets, whereby the serious advantage of real-time capability is lost.
  • the image is taken from the color values of a certain environment for which a difference is to be calculated.
  • these are the 3 color channels with the indices 1, 2, 3. So, in this example, there are 3 dimensions, and for each dimension, a number of metrics corresponding to the number of image pixels in the pointing area.
  • the Characteristics Snm divided by measured values and dimension form an n * m matrix in the general case
  • the coefficients of a phase matrix and an amplitude matrix are calculated for all two-relationships ij with j> i between the dimensions from the features Sij.
  • the dumbbells arise by plotting 2 sine waves instead of Cartesian coordinates over a circle of radius r.
  • the dumbbells arise in this form if r is chosen equal to the amplitude amp of the sine wave.
  • the rotation of the dumbbell relative to the axes results from the respectively associated phase values.
  • the dumbbell value d from the center of rotation of the polar coordinates is then:
  • a separation area (31) in the 3-dimensional color space is now calculated.
  • This separation surface is shown in FIG. 10 in 3D.
  • the separation area is determined by the fact that the mean value from calculation step 1 lies at this level.
  • the following operations still determine the normal vector of the separation surface.
  • the components of the interface result from the maxima of the amplitudes in the amplitude matrix.
  • the plane two-dimensional subspace of the feature space
  • the result of the calculation steps 1 to 3 are 2 vectors, namely the vector mean from the coordinate origin to the mean on the separating surface and the vector plane perpendicular to the separating surface. This makes it possible to decide for each pixel on the basis of its color value Sk, on the softer side of the separating surface it lies, or to which object to be segmented it belongs. For this purpose, a threshold is first calculated, which is given by the scalar product of the two vectors mean and plane.
  • Threshold scalar product (me ⁇ / -z, /? / ⁇ A7e)
  • the color value lies before the separation surface if the scalar product (Sk, p / ö «e) is smaller than the threshold and the color value lies behind the separation surface if the scalar product (Sk, p / ⁇ 7" ze) is greater than or equal to the threshold ,
  • the calculation steps 2 and 3 can be omitted.
  • the threshold from calculation step 4 is then equal to the mean value from calculation step 1, since the plane from calculation step 3 thereby shrinks to a point.
  • the plane of calculation step 3 shrinks to a straight line.
  • the above method corresponds to the result of the known method for segmenting gray scale images by determining an optimized threshold (Calculation of the mean value, division of the pixel quantity into two subset with the mean value as threshold, calculation of the mean values of the two subsets, these mean values correspond to the emphases in the indicated procedure).
  • steps 1 to 4 can be segmented objects that are distinguishable by their color or gray value from the background. But now there are pictures in which the objects can not be distinguished from the background by their color or gray value, but by their brightness distribution.
  • An example of this is the image of cancer cells as shown in Figure 11. In normal light, these cancer cells are largely transparent. Polarized light makes the cells visible in so-called phase contrast. The objects are distinguished by their brightness dynamics and not by a brightness range from the homogeneous background.
  • a feature space adapted for this task is generated.
  • the image is transformed before editing so that the real-time capability is restored using three classes.
  • a pointing region of the size of, for example, 3 by 3 pixels or larger is automatically applied for each pixel i, j of the image to be processed.
  • its distance from the separation surface is calculated for each pixel of the pointing region. All these distances are added up correctly according to the location of the pointing area.
  • FIGS. 12 and 13 now illustrate a two-dimensional feature space which is used for the
  • the feature space must still be normalized, so that both dimensions of the feature space comprise the same number range, e.g. the range of numbers between 0 and 1 has to be particularly favorable
  • a two-dimensional feature space it can be imaged as a two-dimensional histogram, which is shown in FIG.
  • the pixels form a triangle in the feature space, with the pixels at the top at the top are the pixels of the background, right below the bright pixels within the objects and lower left are the dark pixels of the cells.
  • Such a triangular shape can be recognized with a wave function of period 3.
  • a cosine (3 ⁇ ) is fitted according to exactly the same scheme as in the above calculation step 2.
  • Such a wave function of period 3 is shown in FIG. 15 on the left in Cartesian coordinates and in FIG. 15 on the right in polar coordinates.
  • the 16 shows the feature values Dist and Plen for the pointing region 31 in the left-hand part of FIG. 16.
  • the pixels in the phase range of the upper oscillation belong to the background and the pixels in the phase range of the two lower oscillations belong to the object.
  • the amplitude of the oscillation is a measure of the quality of detection.
  • a possible alternative is the use of a Kohonen neural network with 3 classes as described in T. Kohonen, Self-Organizing Maps, Springer Verlag, ISBN 3-540-62017-6.
  • the background is then the class with the smallest class variance and the object is the other two classes.
  • the disadvantage here is that no quality of the classification is recognizable.
  • the method of using wavefunctions can also be used for the character recognition or for the classification of objects.
  • the corresponding method is shown in FIG.
  • the starting point (15) is the already segmented image.
  • at least two objects to be distinguished are selected by the user in a subsequent step (16).
  • a subsequent step (17) a number of geometric features are calculated by calculating wave functions.
  • Phase values and amplitude values are again calculated from the wave functions in a subsequent step (18), and the objects are subsequently classified in a step (19) on the basis of the geometric features.
  • the classification result is visualized in a step 20 in real time.
  • This classification method can be used, for example, for design recognition.
  • worms in a phase contrast recording are recognized above via texture segmentation. These worms exist in two forms, stretched (alive) (see left part of picture) and rolled up (dead) (see right part of picture).
  • the pointing area necessary for the wave functions is the object itself and the feature space are directly the pixel coordinates of the objects.
  • the wave functions 2 fit of a cosine (2 ⁇ )
  • 7 fit of a cosine (7 ⁇ )
  • xc, yc be the center of gravity of the object.
  • the calculation takes place after calculation step 1 as the mean value in the individual dimensions x and y.
  • Calculation step 2 as a program: For each pixel x, y of the object
  • the shape coefficients (numbers between 0 and 1) are shown as a block diagram.
  • This block diagram in turn represents a six-dimensional feature space (shape space).
  • the above segmentation method can now be used again by calculating the separation surface between the worm forms in this six-dimensional shape space by means of wave functions.
  • One worm shape then lies on one side of the separation surface and the other worm form on the other side of the separation surface.
  • the above classification is invariant to translation, rotation, mirroring, enlargement, and reduction without a previous elaborate transformation of image space into an invariant property space.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Biomedical Technology (AREA)
  • General Health & Medical Sciences (AREA)
  • Molecular Biology (AREA)
  • Multimedia (AREA)
  • Image Analysis (AREA)

Abstract

Die Erfindung betrifft ein Segmentierungsverfahren mit folgenden Schritten: Vom Benutzer wird in einem ersten Schritt im n-dimensionalen Merkmalsraum ein einziger Datenbereich ausgewählt. Dieser ausgewählte Datenbereich wird vom System grundsätzlich so interpretiert, dass dieser mindestens zwei Klassen von zu segmentierenden Objekten enthält. In nachfolgenden Schritten bestimmt das System zunächst eine Trennfunktion im n- dimensionalen Merkmalsraum zur Unterscheidung der wenigstens zwei Klassen und wendet nachfolgend diese Trennfunktion auf den gesamten Datenraum oder eine größere Teilmenge des Datenraums an. Dieses Segmentierungsergebnis wird dann dem Benutzer in Echtzeit visuell dargeboten. Ein zweiter Aspekt der Erfindung betrifft ein Verfahren zur Klassifikation von Objekten auf Grundlage von geometrischen Eigenschaften zuvor nach einem beliebigen Verfahren segmentierter Objekte in einem n-dimensionalen Datenraum ausnutzen. Dazu werden zunächst in einem ersten Schritt mindestens zwei Objekte als Repräsentanten für zwei verschiedene Klassen ausgewählt, nachfolgend eine Anzahl (m) geometrischer Merkmale pro Objekt durch Berechnung von Wellenfunktionen verschiedener ganzzahliger Wellenfunktionen berechnet und schließlich werden die Objekte auf Grundlage der bestimmten Anzahl an geometrischen Merkmalen oder Teilmengen davon klassifiziert. Die zuvor erforderliche Segmentierung der Objekte kann nach einem Verfahren nach der vorliegenden Erfindung erfolgen.

Description

Verfahren zur Segmentierung in einem n-dimensionalen Merkmalsraum und Verfahren zur Klassifikation auf Grundlage von geometrischen Eigenschaften segmentierter Objekte in einem n-dimensionalen Datenraum
Die Erfindung betrifft ein Verfahren zur Segmentierung von Objekten in einem n- dimensionalen Merkmalsraum, der als Datenraum vorliegt und ein Verfahren zur Klassifikation auf Grundlage von geometrischen Eigenschaften von segmentierten Objekten in einem n-dimensionalen Datenraum.
Derartige Verfahren werden beispielsweise in der Bildanalyse oder bei der Auswertung vor Radarsignalen benötigt. Die Dimension n des Datenraums kann dabei eine beliebige natürliche Zahl betragen. Ein Beispiele für einen 2-dimensionalen Datenraum ist beispielsweise die zu einem Phasenkontrastbild in der Mikroskopie gehörige Datenmenge, ein Beispiel für einen 3-dimensionalen Datenraum die zu einem Farbbild mit den Farbkanälen R- G-B gehörige Datenmengen und ein Beispiel für einen 16-dimensionalen Datenraum die zu einem Radarbild mit 16 spektralen Kanälen zugehörige Datenmenge.
Nach dem Stand der Technik kann die Erkennung von Objekten in Bildern z.B. mit Hilfe zyklischer, interaktiver Bildanalyse erfolgen. Ein derartiges Verfahren ist in der EP 1 154 369 A2 bzw. der DE 10017551 Al beschrieben. Bei diesem Verfahren werden vom Benutzer die ihn interessierenden Bildbereiche grob markiert und ein Computerprogramm klassifiziert daraus die vollständigen Bildbereiche in ihren richtigen Grenzen. Nachteilig dabei ist, dass der Benutzer in wenigstens zwei Schritten zwei Bereiche markieren muss, z.B. das ihn interessierende Objekt und den Hintergrund oder zwei verschiedene Objekte, die aneinandergrenzen. Da zeitlich nacheinander zwei Bildbereiche ausgewählt werden müssen, ist dieses Verfahren nicht wirklich echtzeitfähig.
Es ist ein erstes Ziel der vorliegenden Erfindung, ein Verfahren zur Segmentierung anzugeben, mit dem Objekte in einem n-dimensionalen, als Datenraum vorliegenden Merkmalsraum segmentiert werden können, und bei dem der Benutzer nur einen einzigen Bildbereich auszuwählen braucht. Dieses Ziel ein Verfahren zur Segmentierung anzugeben wird mit einem Verfahren mit den Merkmalen des Anspruchs 1 gelöst. Vorteilhafte Ausgestaltungen dieses Verfahrens ergeben sich aus den Merkmalen der abhängigen Ansprüche 2 bis 4 und 8 bis 13.
Es ist ein zweites Ziel der vorliegenden Erfindung, ein Verfahren zur Klassifikation auf Grundlage von geometrischen Eigenschaften von segmentierten Objekten in einem n- dimensionalen Datenraum anzugeben. Dieses Ziel wird durch ein Verfahren mit den Merkmalen des Anspruchs 5 gelöst. Vorteilhafte Ausgestaltungen dieses Verfahren ergeben sich aus den Merkmalen der abhängigen Ansprüche 6 und 7.
Die beiden oben genannten Verfahren sollen vorzugsweise computerimplementiert ausführbar sein. Dafür gibt Anspruch 14 ein geeignetes Computersystem und Anspruch 15 ein geeignetes Computerprogrammprodukt an.
Das Segmentierungsverfahren gemäß Anspruch 1 enthält die folgenden Verfahrensschritte: Vom Benutzer wird in einem ersten Schritt im n-dimensionalen Merkmalsraum ein einziger Datenbereich ausgewählt. Dieser ausgewählte Datenbereich wird vom System grundsätzlich so interpretiert, dass dieser mindestens zwei Klassen von zu segmentierenden Objekten enthält. In nachfolgenden Schritten bestimmt das System zunächst eine Trennfunktion im n- dimensionalen Merkmalsraum zur Unterscheidung der wenigstens zwei Klassen und wendet nachfolgend diese Trennfunktion auf den gesamten Datenraum oder eine größere Teilmenge des Datenraums an. Dieses Segmentierungsergebnis wird dann dem Benutzer in Echtzeit visuell dargeboten.
Beim erfindungsgemäßen S egmentierungs verfahren können die Ergebnisse in einer Echtzeit- Rückkopplungsschleife unter Verwendung der Mustererkennungsfähigkeiten des Benutzers zielgerichtet optimiert werden. Weiterhin können zusätzliche Merkmale der zu segmentierenden Objekte wie z.B. Anzahl der Objekte im Bild, relative Fläche der Objekte, minimale und maximale Größe, Formfaktoren wie Exzentrizität, fratale Dimension als Maß für die Glätte der Begrenzungslinien oder andere geeignete Eigenschaften mit vorgegeben werden. Diese Angaben können sowohl durch den Benutzer vorgegeben als auch durch geeignete Verfahren automatisch aus dem Bild extrahiert werden. Wenn der Benutzer mit dem erzielten Segmentierungsergebnis noch nicht zufrieden sein sollte, kann er den ausgewählten Datenbereich nachfolgend verändern und erhält so in Echtzeit jeweils das vom System aufgrund der dann auch geänderten Trennfunktion geänderte Segmentierungsergebnis visuell angezeigt.
Anstelle von nur zwei Klassen kann auch eine größere Anzahl an Klassen vorgegeben werden. Die Anzahl der Klassen kann auch durch ein automatisches Verfahren bestimmt werden. Entsprechend der gewünschten Anzahl an Klassen sollte dann natürlich auch ein Datenbereich vom Benutzer ausgewählt werden, der Bildpunkte oder Datenpunkte einer entsprechenden Anzahl an Klassen enthält.
Die Bestimmung der Trennfunktion kann dadurch erfolgen dass zunächst für jede Dimension des Merkmalsraums durch ein mathematisches Verfahren ein Referenzpunkt der Merkmale (Si) bestimmt wird, nachfolgend alle Datenpunkte auf alle Kombinationen von zweidimensionalen Subräumen des n-dimensionalen Merkmalsraums projiziert werden und schließlich durch ein zweidimensionales Fehlerminimierungsverfahren ein Phasenwert und ein Amplitudenwert zu einer vorbestimmten Wellenfunktion so bestimmt werden, dass ein geeignet definierter Approximationsfehler für diese Wellenfunktion durch ein dafür geeignetes Verfahren minimiert wird. Für sinusförmige oder kosinusförmige Wellenfunktionen ist ein derartiger Approximationsfehler die Summe der quadrierten Differenzen, die durch die Methode der kleinsten Fehlerquadrate minimiert wird. Die Wellenfunktion ist dabei eine ganzzahlig-periodische, stetige Funktion.
Als Verfahren zur Bestimmung der Trennfunktion können alternativ zu dem oben beschriebenen auf Wellenfunktionen basierenden Verfahren alle Verfahren zur Bestimmung von Trennfunktionen für n-dimensionale Datensätze angewendet werden. Beispiele dafür sind Verfahren mit nicht überwachtem Lernen, z.B. Kohonenkarten, „Neural Gas"-Algorithmen, ART-Netze.
Ist beispielsweise der n-dimensionale Merkmalsraum eine Grauwertverteilung, der lokale Mittelwert der Grauwertverteilung und die lokale Varianz der Grauwertverteilung, so ist die Wellenfunktion k-zählig mit k größer als zwei, und die daraus resultierenden k Klassen können zu mindestens zwei Klassen zusammen gefasst werden. Beispielsweise kann die Wellenfunktion drei-zählig sein und die daraus resultierenden drei Klassen können zu zwei Klassen zusammengefasst werden. Insbesondere können die Klassen mit der größten lokalen Varianz der Grauwertverteilung zusammengefasst werden.
Wie bereits eingangs genannt, kann der Merkmalsraum dreidimensional sein und RGB- Bilddaten eines digitalen Farbbildes enthalten. Alternativ kann der Merkmalsraum vierdimensional sein und Bilddaten von mit vier Detektoren bei unterschiedlichen Lichtwellenlängen aufgenommenen vier Fluoreszenzkanälen enthalten.
Das Verfahren kann nacheinander an verschiedenen Stellen eines Objekts angewendet werden, indem nacheinander unterschiedliche Datenbereiche, die zu demselben Objekt gehören, ausgewählt werden. Durch Interpretation jeder dieser Datenbereiche derart, dass er mindestens zwei Klassen von zu segmentierenden Objekten enthält und darauf basierendem Bestimmen der Trennfunktion ergeben sich dann mehrere Klassen von denen nachfolgend mindesten zwei wieder vereinigt werden. Auf diese Weise lässt sich beispielsweise ein Objekt, das in zwei oder mehr verschiedene Hintergründe eingebettet ist, so segmentieren, dass auch die verschiedenen Hintergründe unterschieden werden.
Das oben genannte Verfahren, bei dem die Trennfunktion aus einer Wellenfunktion bestimmt wird, lässt sich auch auf ein Verfahren zur Klassifikation auf Grundlage von geometrischen Eigenschaften zuvor nach einem beliebigen Verfahren segmentierter Objekte in einem n- dimensionalen Datenraum ausnutzen. Dazu werden zunächst in einem ersten Schritt mindestens zwei Objekte als Repräsentanten für zwei verschiedene Klassen ausgewählt, nachfolgend eine Anzahl (m) geometrischer Merkmale pro Objekt durch Berechnung von Wellenfunktionen verschiedener ganzzahliger Wellenfunktionen berechnet und schließlich werden die Objekte auf Grundlage der bestimmten Anzahl an geometrischen Merkmalen oder Teilmengen davon klassifiziert. Die zuvor erforderliche Segmentierung der Objekte kann grundsätzlich mittels eines beliebigen Verfahrens erfolgen, besonders vorteilhaft jedoch nach einem Verfahren nach der vorliegenden Erfindung.
Zur Berechnung der Anzahl geometrischer Objekte können aus den Wellenfunktionen Phasenwerte und Amplitudenwerte berechnet werden, wobei die Amplitudenwerte die Gestalt der Objekte charakterisieren und die Phasenwerte die Orientierungen der Objekte charakterisieren. Die aus den Wellenfunktionen berechneten Amplitudenwerte beschreiben die Gestalt der Objekte größeninvariant, translationsinvariant und rotationsinvariant. Ein Computersystem, das zur Ausführung eines Verfahrens nach der Erfindung geeignet ist, sollte Einrichtungen (1) zum interaktiven Eingeben und Auswählen von Bildbereichen und einen Monitor zur Echtzeit-Visualisierung der erzielten Ergebnisse aufweisen. Zusätzlich sollte natürlich auch ein Prozessor und ein Datenspeicher für ein Computerprogramm mit einem Softwarecode vorhanden sein, mittels dem das erfindungsgemäße Verfahren implementierbar ist.
Nachfolgend werden Ausführungsbeispiele der Erfindung anhand der Figuren näher erläutert. Dabei zeigen:
Figur 1 : Eine Prinzipskizze eines zur Ausführung der Erfindung geeigneten Systems aus
Computer, Monitor und Eingabeeinheit; Figur 2: ein Blockdiagramm der beim erfindungsgemäßen Segmentierungsverfahren ablaufenden Verfahrensschritte; Figur 3: ein Blockdiagramm der beim erfindungsgemäßen Klassifikationsverfahren ablaufenden Verfahrensschritte; Figur 4: ein Mikroskopbild mit Zellen als Ausgangspunkt zur Erläuterung des erfindungsgemäßen Verfahrens;
Figur 5: das vom System aus dem Bild in Figur 4 erzeugte segmentierte Bild; Figuren 6 bis 8:
Die Darstellungen von Projektionen in zweidimensionale Subräume eines RGB-
Bilds; Figur 9: Erläuterungen zur Erzeugung der Hanteln in den Figuren 6 bis 8 aus
WeI lenfunktionen ; Figur 10: eine dreidimensionale Darstellung einer aus den Figuren 6 bis 8 abgeleiteten
Trennfläche im RGB-Raum;
Figur 11 : Ein Phasenkontrast-Bild als Beispiel eines Texturbildes Figuren 12 und 13:
Zwei aus dem Bild in Figur 1 1 durch das erfindungsgemäßen
Segmentierungsverfahren erzeugte Merkmalsräume, die für die Erkennung der
Helligkeitsdynamik im Bild in Figur 1 1 geeignet sind;
Figur 14: ein zweidimensionales Histogramm der Bilder in Figuren 12 und 13; Figur 15: eine dreizählige Wellenfunktion; Figur 16:das Bild aus Figur 1 1 und den Merkmalsraum der Texturinformation für einen ausgewählten Zeigebereich Figur 17: Bilder zur Erläuterung der Gestalterkennung
In der Figur 1 ist ein System aus einem Computer (2) mit einem eingebauten Arbeitsspeicher (4) und Prozessor (3) dargestellt. In den Arbeitsspeicher (4) ist ein Programm ladbar, das den Prozessor (3) zur Ausführung des erfindungsgemäßen Verfahrens befähigt. An den Computer (2) ist ein Monitor (1) und ein Eingabemittel (5), z.B. eine Maus, angeschlossen. Mit Hilfe der Maus kann der Benutzer einen in dem vom Monitor (1) angezeigten Bild hervor gehobenen Zeigebereich relativ zum Bild bewegen.
Ein Beispiel für ein praktisches Bild ist in der Figur 4 dargestellt. Der Zeigebereich ist hier mit dem Bezugszeichen (24) versehen. Der Zeigebereich (24) sollte relativ zum Bild so positioniert werden, dass der Zeigebereich (24) ein Teil des zu segmentierenden Objekts (23) sowie einen Teil des Bildhintergrundes (22) umfasst.
Das ablaufende Segmentierverfahren wird nachfolgend anhand der Figur 2 am Beispiel eines Farbbildes erläutert. Ausgangspunkt ist in diesem Fall das Bild (7), das als Farbhelligkeitsinformation in den drei Grundfarben rot, grün und blau als Funktion der zwei Ortskoordinaten x, y vorliegt. In einem ersten Schritt (8) wählt der Benutzer einen Bereich in dem Bild (7) aus, der das zu segmentierende Objekt und Bildhintergrund oder Bildteile von zwei zu unterscheidenden Objekten enthalten sollte. Die Bildinformation in diesem ausgewählten Zeigereich wird vom System in einem nachfolgenden Schritt (8) so interpretiert, dass mindestens zwei Klassen von Objekten im ausgewählten Zeigebereich enthalten sind. In den nachfolgenden Schritten wird anhand der Bildinformation im Zeigebereich eine Trennfunktion bestimmt. Dazu werden in Frage kommenden Merkmale, wie z.B. Farbhelligkeitswerte in den drei Grundfarben analysiert und in einem Schritt (10) ein Referenzpunkt der verschiedenen Merkmale bestimmt. Dann werden in einem Schritt (11) alle Datenpunkte auf alle zweidimensionalen Subräume des Merkmalsraums projiziert. Aus dieser Projektion, die nachfolgend noch detaillierter beschrieben wird, resultieren in einem nachfolgenden Schritt (12) Phasenwerte und Amplitudenwerte, die die Trennfunktion als Wellenfunktion bestimmen. Diese Trennfunktion wird in einem nachfolgenden Schritt (13) auf den gesamten Datenraum - oder den zu segmentierenden Teilraum davon - angewendet und das Ergebnis der Segmentierung in einem Schritt (14) in Echtzeit angezeigt. Wie bereits oben gesagt, zunächst zeigt der Benutzer grob auf die Grenze zwischen einem Objekt (23) und dem Hintergrund (24) oder auf die Grenze zwischen zwei unterschiedlichen, aneinandergrenzenden Objekten wie in Figur 4 angedeutet. Wie in der eingangs genannten EP 1 154 369 A2 wählt der Benutzer hierzu einen beliebig geformten Bereich (22), z. B. einen Kreis, und positioniert diesen Zeigebereich so, dass er einen Teil des Objektes (23) und gleichzeitig einen Teil des Hintergrundes (24) überdeckt. Das Segmentierungssystem kann daher davon ausgehen, dass innerhalb des Kreises die Grenze eines Objektes verläuft. Außerdem kann es wie in der EP 1 154 369 A2 davon ausgehen, dass im Zeigebereich sowohl die Textur/Farbe des Objektes, als auch die Textur/Farbe des Hintergrundes vorliegen. Das ist also nicht nur eine Vereinfachung der notwendigen Arbeitsschritte, sondern gleichzeitig eine Erhöhung des Informationsgehaltes, nämlich die Information über unterschiedliche Texturen/Farben einerseits und die Grenze zwischen den Texturen/Farben andererseits. Die Menge der ausgewählten Pixel sollte so beschaffen sein, dass sie in zwei (oder mehr) disj unkte Teilmengen zerlegt werden kann, von denen jeweils eine genau einem von mehreren Objekten oder dem Hintergrund zugeordnet werden kann. Dieser erhöhte Informationsgehalt kann z.B. dazu ausgenutzt werden, dass die Erkennung eines Objektes online erfolgen kann, während der Benutzer den Zeigebereich über das Bild fährt. Der Zeigebereich kann z.B. über eine Maus, ein Touchpad, einen Tochscreen, einen Trackball, ein „Joystick" oder ein anderes für die Bewegung des Cursors bei Computern eingesetztes Zeigeinstrument gesteuert werden. Auf der Grundlage der Textur/Farbe im Zeigebereich wird dann eine Trennfunktion ermittelt, die nachfolgend auf das gesamte Bild angewendet wird. Das Ergebnis der Segmentierung ist in Figur 5 dargestellt. Als Trennfunktion wird vorzugsweise eine Wellenfunktion verwendet. Das Bestimmen einer geeigneten Trennfunktion wird weiter unter noch genauer an einem Beispiel beschrieben.
Der Benutzer hat beim erfindungsgemäßen Verfahren während der Bewegung im Bild mit dem Zeigebereich die sofortige Rückmeldung des Computerprogramms (in Echtzeit), ob dieses das gesuchte Objekt auch richtig erkannt hat, oder ob an einigen Randstellen des Objektes Korrekturen notwendig sind. Damit kann z.B. der für die Klassifikation wichtige Mittelwert durch Verschieben des Zeigebereichs optimiert werden und ebenso kann die repräsentative Auswahl der relevanten Pixel- Teilmengen optimiert werden. Bei Bildern, die starke Inhomogenitäten aufweisen, kann ggf. ein weiterer Zeigebereich ausgewählt werden, der dazu benutzt wird, die zu untersuchende Pixelmenge um weitere repräsentative Daten zu erweitern. Es ergeben sich dann N Trennebenen, aus denen für jeden Bildpunkt durch ein geeignetes Verfahren ein lokaler Klassifikator für die Segmentierung bestimmt wird. Als solche Verfahren kommen in Frage: a) die Auswahl nach dem Abstand des lokalen Punkts zu den bekannten Trennebenen bzw. dessen Schwerpunkten, b) die Interpolation zwischen den Ebenen unter Benutzung der relativen Bildkoordinaten der Beispielobjekte und des aktuellen Bildelements (Morphing), c) die Verwendung von selbstlernenden Ansätzen wie linearen oder nichtlinearen neuronalen Netzen oder d) die Anwendung aller Trennebenen und die Benutzung des maximalen Abstands. Neben diesen vier genannten Verfahren sind jedoch auch andere Verfahren möglich.
Gegenüber dem Stand der Technik hat die hier vorgelegte Erfindung den weiteren Vorteil, dass sie in beliebig hochdimensionalen Merkmalsräumen funktioniert. Ein Beispiel hier ist der dreidimensionale Farbraum mit den Farben rot, grün und blau. Ein weiteres, noch höherdimensionales Beispiel wären Radarbilder mit 16 oder mehr Spektralkanälen.
Es sei ausdrücklich darauf hingewiesen, dass das Verfahren nicht auf die Bildverarbeitung beschränkt ist. Es funktioniert in jedem höherdimensionalen Merkmalsraum, der durch lokal sich ändernde skalare Felder beschrieben ist.
Der so konstruierte Klassifikator für die Trennbereiche ist per constructionem invariant gegen Translation, Rotation und Streckung. Bei geeigneter Weiterverarbeitung gilt dies auch für die später noch näher beschriebene Gestalterkennung. Solche Invarianzeigenschaften sind nach den üblichen Verfahren nur durch aufwendige mathematische Behandlungen wie z.B. lokale Fourieranalysen oder Gabor- Wavelets zu erzielen, wodurch der gravierende Vorteil der Echtzeitfähigkeit verloren geht.
Segmentierung mittels zirkulärer Wellenfunktionen:
Dem Bild werden die Farbwerte einer gewissen Umgebung, für die ein Unterschied berechnet werden soll, entnommen. Beim Beispiel des Farbbildes sind dieses die 3 Farbkanäle mit den Indizes 1 ,2,3. Es gibt in diesem Beispiel also 3 Dimensionen und zu jeder Dimension eine Anzahl an Messwerten, die der Anzahl der Bildpixel im Zeigebereich entspricht. Die Merkmale Snm aufgeteilt nach Messwerte und Dimension bilden im allgemeinen Fall eine n*m Matrix
Dimensionen 1 ... n Messwerte 1 ... m
1. Rechenschritt:
Zunächst werden die Mittelwerte der Merkmale in den einzelnen Dimensionen berechnet:
1 m mean, = — * ∑slk
Diese Mittelwerte bilden Referenzpunkte im Merkmalsraum. Anstatt durch Mittelwertbildung können die Referenzpunkte aber auch anderweitig bestimmt werden.
2. Rechenschritt:
In einem nachfolgenden zweiten Schritt werden für alle Zweier-Beziehungen ij mit j>i zwischen den Dimensionen aus den Merkmalen Sij die Koeffizienten einer Phasen- und einer Amplitudenmatrix berechnet. Im Beispiel von drei Farben sind das die Phasen-Koeffizienten φ12 , φ13 und φ23 , sowie die Amplituden-Koeffizienten ampn , ampu und amp23 für die Beziehungen rot-grün, rot-blau und grün-blau { reIJ = ^ amp * cos(2φ )
imtJ = ∑amp * sin(2φ) k = \ mit φ = arctan s,k ~ m,
amp = τ]{slk - m, f + (sß - m] J im.. φ = 0.5arctan( — -) re„
}
In den vorstehenden Gleichungen sind dabei m; und nij die im ersten Rechenschritt berechneten Mittelwerte in den einzelnen Dimensionen.
Eine Alternative ist, die Gewichtung von re und im durch die Amplituden amp wegzulassen. Die Wahl des Verfahrens ergibt sich durch die vorgegebenen Randbedingungen, vor allem die Art des Bildaufnahmeverfahrens (Phasenkontrast, mehrkanalige Fluoreszenz, etc.). Anschaulich werden die 3-dimensionalen Farbwerte jeweils in die Ebenen rot-grün, rotblau und grün-blau projiziert. Diese ist in den Figuren 6 bis 8 dargestellt. In diesen Ebenen wird jeweils ein Cosinus(2φ ) in Polarkoordinaten nach dem kleinsten Fehlerquadrat gefittet Diese hanteiförmigen Gebilde (26, 29) teilen die Farbwerte in zwei Klassen, die schwarzen Messwerte (28) und die weißen Messwert (25). Dabei ist das Zentrum (27, 30) der Hanteln (26, 29) jeweils der Mittelwert aus dem ersten Rechenschritt.
Wie in Figur 9 dargestellt, ergeben sich die Hanteln, indem man 2 Sinusschwingungen statt in Kartesischen Koordinaten über einem Kreis mit Radius r abbildet. Die Hanteln ergeben sich in dieser Form, falls r gleich der Amplitude amp der Sinusschwingung gewählt wird. Die Drehung der Hantel relativ zu den Achsen ergibt sich aus den jeweils zugehörigen Phasenwerten. Der Hantelwert d vom Drehzentrum der Polarkoordinaten aus ist dann:
d(a) - r + amp * cos(2α - φ )
3. Rechenschritt:
In einem 3. Rechenschritt wird jetzt eine Trennfläche (31) im 3-dimensionalen Farbraum berechnet. Diese Trennfläche zeigt Figur 10 in 3D-Darstellung. Die Trennfläche ist dadurch bestimmt, dass der Mittelwert aus Rechenschritt 1 auf dieser Ebene liegt. Mit den folgenden Operationen wird noch der Normalenvektor der Trennfläche bestimmt.
Die Komponenten der Trennfläche ergeben sich aus den Maxima der Amplituden in der Amplitudenmatrix. Hierbei wird von der Ebene (zweidimensionaler Subraum des Merkmalsraums ) mit dem größten Amplitudenmaximum gestartet und nachfolgen die Ebenenkoeffizienten für die einzelnen Ebenen in der Reihenfolge mit absteigendem Amplitudenmaximum berechnet. Wenn die größte Amplitude in der Grün-blau-Ebene vorliegt, ergeben sich die Flächenkomponenten c2 und c3 zu: c2 = amp*cos(φ) c3 = amp* sin(φ)
Liegt die nächst größere Amplitude in der Rot-grün-Ebene, so ergibt sich die letzte fehlende Flächenkomponente cl zu: cl = amp* cos(φ)
Bei höherdimensionalen Daten sind dann entsprechend weitere Ebenenkoeffizienten in absteigender Reihenfolge der Amplitudenwerte zu berechnen.
4. Rechenschritt:
Das Ergebnis der Rechenschritte 1 bis 3 sind 2 Vektoren, nämlich der Vektor mean vom Koordinatenursprung zum Mittelwert auf der Trennfläche und der Vektor plane senkrecht auf der Trennfläche. Damit lässt sich für jeden Bildpunkt an Hand dessen Farbwert Sk entscheiden, auf weicher Seite der Trennfläche er liegt, bzw. zu welchem zu segmentierenden Objekt er gehört. Dazu wird zunächst eine Schwelle berechnet, die durch das Skalarprodukt der beiden Vektoren mean und plane gegeben ist.
Schwelle = Skalarprodukt(meα/-z,/?/αA7e)
Damit ergibt sich dann:
Der Farbwert liegt vor der Trennfläche, falls das Skalarprodukt(Sk,p/ö«e) kleiner als die Schwelle ist und der Farbwert liegt hinter der Trennfläche, falls das Skalarprodukt(Sk,p/ύ7"ze) größer oder gleich der Schwelle ist.
Im Sonderfall von Graubildern (=eindimensionaler Merkmalsraum) können die Rechenschritte 2 und 3 entfallen. Die Schwelle aus Rechenschritt 4 ist dann gleich dem Mittelwert aus Rechenschritt 1 , da die Ebene aus Rechenschritt 3 dabei zu einem Punkt schrumpft. In einem zweidimensionalen Merkmalsraum schrumpft die Ebene aus Rechenschritt 3 zu einer Geraden.
Das obige Verfahren entspricht im Ergebnis dem Ergebnis des bekannten Verfahrens zur Segmentierung von Grauwertbildern durch Bestimmung einer optimierten Schwelle (Berechnung des Mittelwerts, Aufteilung der Pixelmenge in zwei Teilmenge mit dem Mittelwert als Schwelle, Berechnen der Mittelwerte der beiden Teilmengen; diese Mittelwerte entsprechen den Schwerpunkten im angegebenen Verfahren).
Textursegmentierung:
Mit den obigen Rechenschritten 1 bis 4 lassen sich Objekte segmentieren, die durch ihre Farbe oder Grauwert vom Hintergrund unterscheidbar sind. Nun gibt es aber Bilder, bei denen sich die Objekte nicht durch ihre Farbe oder Grauwert, sondern durch ihre Helligkeitsverteilung vom Hintergrund unterscheiden lassen. Ein Beispiel dafür ist das Bild von Krebszellen, wie in Figur 1 1 dargestellt. Im normalen Licht sind diese Krebszellen weitgehend durchsichtig. Durch polarisiertes Licht werden die Zellen im sog. Phasenkontrast sichtbar. Die Objekte unterscheiden sich dabei durch ihre Helligkeitsdynamik und nicht durch einen Helligkeitsbereich vom homogenen Hintergrund.
Mit Hilfe der obigen Rechenschritte 1 bis 3 wird zunächst ein für diese Aufgabe angepasster Merkmalsraum erzeugt. Das Bild wird vor der Bearbeitung transformiert, sodass dann unter Verwendung von drei Klassen wieder die Echtzeit-Fähigkeit entsteht. Dazu wird ein Zeigebereich der Größe von z.B. 3 mal 3 Bildpunkten oder größer automatisch für jeden Bildpunkt i,j des zu bearbeitenden Bildes angewendet. Anstatt nun wie in Rechenschritt 4 das Objekt im Bild zu rekonstruieren, wird für jeden Bildpunkt des Zeigebereiches sein Abstand von der Trennfläche berechnet. Alle diese Abstände werden entsprechend dem Ort des Zeigebereiches stellenrichtig aufaddiert. Es sei: mean, } Mittelwert des Zeigebereiches an der Stelle i,j plane , } Ebenenvektor des Zeigebereiches an der Stelle i,j thresht ] = Slalarprodukt(meanl } , plane, ) Dann ist:
Dist, j = ^ ^ Skalarprodukt{S ,_k j_, , plane, ; ) - thresh, } k=-\ I=-]
Das Ergebnis Dist i,j ist in Figur 12 dargestellt.
Zusätzlich werden die Längen des Ebenenvektors plane ebenfalls stellenrichtig aufaddiert. Es sei plen, j = J Skalarprodukt{plane, } , plane, : ) Dann ist: fc=+l /=+1
Plenu = ∑ ∑Plen,-kj-i k=-\ /=-1
Das Ergebnis Plen i,j ist in Figur 13 dargestellt
Die Figuren 12 und 13 stellen nun einen zweidimensionalen Merkmalsraum dar, der für die
Erkennung der Helligkeitsdynamik geeignet ist. Zunächst muss der Merkmalsraum noch normiert werden, damit beide Dimensionen des Merkmalsraums den gleichen Zahlenbereich umfassen, z.B. den Zahlenbereich zwischen 0 und 1. Als besonders günstig hat sich dabei die
Sigmoidfunktion
;/ = l /(l + exp(-g(x - x0)) herausgestellt.
Es sei m die Anzahl aller Bildpunkte, dann ist
1 m meand = — * ^ Distk m t=i
1 m meanp = — * ^ Plenk m k=\ und die Normierung über die Sigmoidfunktion erfolgt dadurch, dass für x die Zahlenwerte von Dist bzw. Plen und für x0 meand bzw. meanp eingesetzt werden.
Als zweidimensionaler Merkmalsraum lässt er sich als zweidimensionales Histogramm abbilden, das in Figur 14 dargestellt ist. Die Bildpunkte bilden im Merkmalsraum ein Dreieck, wobei die Bildpunkte an der Spitze oben die Bildpunkte des Hintergrundes sind, rechts unten die hellen Bildpunkte innerhalb der Objekte und links unten die dunklen Bildpunkte der Zellen liegen. Eine solche Dreiecksform lässt sich mit einer Wellenfunktion der Periode 3 erkennen. Hierzu wird nach exakt demselben Schema wie im obigen Rechenschritt 2 ein Cosinus(3φ) gefittet. Eine derartige Wellenfunktion der Periode 3 ist in Figur 15 links in kartesischen Koordinaten und in Figur 15 rechts in Polarkoordinaten dargestellt. Der rechte Bildteil in Figur 16 zeigt die Merkmalswerte Dist und Plen für den Zeigebereich 31 im linken Bildteil der Figur 16. Im Bild gehören dann die Bildpunkte im Phasenbereich der oberen Schwingung zum Hintergrund und die Bildpunkte im Phasenbereich der beiden unteren Schwingungen zum Objekt. Die Amplitude der Schwingung ist ein Maß für die Güte der Erkennung. Nach dem Stand der Technik ist eine mögliche Alternative die Verwendung eines Kohonen Neuronalen Netzwerks mit 3 Klassen wie in T. Kohonen, Self-Organizing Maps, Springer Verlag, ISBN 3-540-62017-6 beschrieben. Hintergrund ist dann die Klasse mit der kleinsten Klassenvarianz und das Objekt sind die beiden anderen Klassen. Nachteilig dabei ist aber, dass keine Güte der Klassifikation erkennbar wird.
Gestalterkennung :
Das Verfahren, Wellenfunktionen zu verwenden, lässt sich auch zur Gestalterkennung bzw. zur Klassifizierung von Objekten ausnutzen. Das entsprechende Verfahren ist in Figur 3 dargestellt. Bei diesem Verfahren ist der Startpunkt (15) das bereits segmentierte Bild. Bei diesem Verfahren werden in einem nachfolgenden Schritt (16) vom Benutzer mindestens zwei zu unterscheidende Objekte ausgewählt. In einem nachfolgenden Schritt (17) werden eine Anzahl geometrischer Merkmale durch Berechnung von Wellenfunktionen berechnet. Aus den Wellenfunktionen werden in einem nachfolgenden Schritt (18) wieder Phasenwerte und Amplitudenwerte berechnet und die Objekte werden nachfolgend in einem Schritt (19) auf Grundlage der geometrischen Merkmale klassifiziert. Das Klassifizierungsergebnis wird in einem Schritt 20 in Echtzeit visualisiert.
Dieses Klassifikationsverfahren lässt sich beispielsweise zur Gestalterkennung nutzen. Im Beispiel von Figur 17 sind oben über Textursegmentierung Würmer in einer Phasenkontrastaufnahmen erkannt. Diese Würmer existieren in zwei Formen, gestreckt (lebendig) (siehe linker Bildteil) und eingerollt (tot) (siehe rechter Bildteil). Der für die Wellenfunktionen notwendige Zeigebereich ist dazu das Objekt selbst und der Merkmalsraum sind unmittelbar die Bildpunktkoordinaten der Objekte. Im Beispiel von Figur 17 werden die Wellenfunktionen 2 (Fit eines Cosinus(2φ)) bis 7 (Fit eines Cosinus(7φ)) berechnet. Daraus werden die Gestalt Koeffizienten (aus den Phasenwerten und den Amplitudenwerten der Wellenfunktionen) berechnet:
Die Darstellung erfolgt nachfolgend in Programmform. Die Vorgehensweise ist völlig identisch zum obigen Rechenschritt 2.
Sei xc, yc der Schwerpunkt des Objektes. Die Berechnung erfolgt nach Rechenschritt 1 als Mittelwert in den einzelnen Dimensionen x und y. Rechenschritt 2 als Programm: Für jedes Pixel x,y des Objektes
{ zx = x - xc; zy = y - yc;
phi = atan2(zy,zx); dist = sqrt(zx * zx + zy * zy); distsum += dist;
Summenbildung für die Koeffizienten
for(k=0;k<ncoefficient;k++)
{ dcos[k] += dist * cos(k*phi); dsin[k] += dist * sin(k*phi);
} } Normierung for(k=0;k< ncoefficient;k++)
{ amp[k] = sqrt(dcos[k] * dcos[k] + dsin[k] * dsin[k]) / distsum;
} amp[k] sind die Gestalt Koeffizienten
In Figur 17 sind unten die Gestalt Koeffizienten (Zahlenwerte zwischen 0 und 1) als Blockdiagramm dargestellt. Dieses Blockdiagramm repräsentiert seinerseits einen sechsdimensionalen Merkmalsraum (Gestaltraum). Für die Unterscheidung der beiden Wurmformen lässt sich nun obiges Segmentierungsverfahren wiederum verwenden, indem mittels Wellenfunktionen die Trennfläche zwischen den Wurmformen in diesem sechsdimensionalen Gestaltraum berechnet wird. Die eine Wurmform liegt dann auf der einen Seite der Trennfläche und die andere Wurmform auf der anderen Seite der Trennfläche. Die obige Klassifikation ist invariant gegenüber Translation, Rotation, Spiegelung, Vergrößerung und Verkleinerung ohne eine vorhergehende aufwendige Transformation des Bildraums in einen invarianten Eigenschaftsraum.

Claims

Patentansprüche:
1. Verfahren zur Segmentierung in einem n-dimensionalen Merkmalsraum, der als Datenraum vorliegt, mit den Schritten: a) Auswählen eines einzigen Datenbereichs, b) Interpretieren des ausgewählten Datenbereichs derart, dass dieser mindestens zwei Klassen von zu segmentierenden Objekten enthält, c) Bestimmen einer Trennfunktion im n-dimensionalen Merkmalsraum zur Unterscheidung der wenigstens zwei Klassen, d) Verallgemeinern durch Anwenden der Trennfunktion bzw. der sich durch lokale Interpolation der Trennfunktionen ergebenden Trennfunktion auf den gesamten Datenraum oder eine größere Teilmenge des Datenraums, und e) Echtzeit-Visualisierung des durch die Verallgemeinerung erzielten Ergebnisses.
2. Verfahren nach Anspruch 1, wobei die Trennfunktion dadurch bestimmt wird, dass f) für jede Dimension des Merkmalsraums durch ein mathematisches Verfahren ein Referenzpunkt der Merkmale (Si) bestimmt wird, g) alle Datenpunkte auf alle Kombinationen von zweidimensionalen Subräumen des n-dimensionalen Merkmalsraums projiziert werden und h) durch ein zweidimensionales Fehlerminimierungsverfahren ein Phasenwert und ein Amplitudenwert zu einer vorbestimmten Wellenfunktion so bestimmt werden, dass der Approximationsfehler in jedem der Subräume minimal wird.
3. Verfahren nach Anspruch 2, wobei die Wellenfunktion eine ganzzahlig-periodische, stetige Funktion ist.
4. Verfahren nach einem der Ansprüche 1 - 3, mit folgenden zusätzlichen zwischen den Schritten c) und d) zwischengeschalteten Schritten: cl) Durchführung der Schritte a) bis c) in einer interaktiven Rückkopplungsschleife bis die lokale Trennfunktion anwendungsbezogen optimiert ist, und c2) Wiederholung der Schritte a) bis cl) für andere Objekte im Bild und Sammeln und abspeichern der sich ergebenden Trennfunktionen.
5. Verfahren zur Klassifikation auf Grundlage von geometrischen Eigenschaften segmentierter Objekte in einem n-dimensionalen Datenraum mit den Schritten: a) Auswählen von mindestens zwei Objekten als Repräsentanten für zwei verschiedene Klassen, b) Bestimmen von einer Anzahl (m) geometrischer Merkmale pro Objekt durch Berechnung von Wellenfunktionen verschiedener ganzzahliger Wellenfunktionen und, c) Klassifizieren der Objekte auf Grundlage der bestimmten Anzahl an geometrischen Merkmalen oder Teilmengen davon.
6. Verfahren nach Anspruch 5, wobei aus den Wellenfunktionen Phasenwerte und Amplitudenwerte berechnet werden und wobei die Amplitudenwerte die Gestalt der Objekte charakterisieren und die Phasenwerte die Orientierungen der Objekte charakterisieren.
7. Verfahren nach Anspruch 5 oder 6, wobei aus den Wellenfunktionen Amplitudenwerte berechnet werden, die die Gestalt der Objekte größeninvariant, translationsinvariant und rotationsinvariant beschreiben.
8. Verfahren nach Anspruch 2, 3 oder 4, wobei der n-dimensionale Merkmalsraum eine Grauwertverteilung, der lokale Mittelwert der Grauwertverteilung und die lokale Varianz der Grauwertverteilung ist, die Wellenfunktion k- zählig ist mit k größer als zwei, und die daraus resultierenden k Klassen zu mindestens zwei Klassen zusammen gefasst werden.
9. Verfahren nach Anspruch 8, wobei die Wellenfunktion drei-zählig ist und die daraus resultierenden drei Klassen zu zwei Klassen zusammen gefasst werden.
10. Verfahren nach Anspruch 8 oder 9, wobei die Klassen mit der größten lokalen Varianz der Grauwertverteilung zusammen gefasst werden.
1 1. Verfahren nach einem der Ansprüche 1 - 4, wobei der Merkmalsraum dreidimensional ist und RGB- Bilddaten eines digitalen Farbbildes enthält.
12. Verfahren nach einem der Ansprüche 1 - 4, wobei der Merkmalsraum vierdimensional ist und Bilddaten von mit vier Detektoren bei unterschiedlichen Lichtwellenlängen aufgenommener vier Fluoreszenzkanäle enthält.
13. Verfahren nach Anspruch 1, wobei das Objekt an mehr als einer Stelle ausgewählt wird, das Verfahren nach den Schritten b) und c) für jeden der ausgewählten Objektbereiche durchgeführt wird und mindestens zwei der sich ergebenden Klassen nachfolgend vereinigt werden.
14. Computersystem, das zur Ausführung eines Verfahrens nach einem der Ansprüche 1 bis 13 geeignet ist und Einrichtungen (1) zum interaktiven Eingeben und Auswählen von Bildbereichen und einen Monitor zur Echtzeit-Visualisierung der erzielten Ergebnisse aufweist.
15. Computerprogrammprodukt, das in den Speicher eines digitalen Computers ladbar ist und einen Softwarecode zur Durchführung eines Verfahrens mit den Schritten nach einem der Ansprüche 1 bis 13 aufweist, wenn das Programm auf dem Computer abläuft.
EP06806044A 2005-10-11 2006-10-05 Verfahren zur segmentierung in einem n-dimensionalen merkmalsraum und verfahren zur klassifikation auf grundlage von geometrischen eigenschaften segmentierter objekte in einem n-dimensionalen datenraum Withdrawn EP1938270A2 (de)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE102005049017A DE102005049017B4 (de) 2005-10-11 2005-10-11 Verfahren zur Segmentierung in einem n-dimensionalen Merkmalsraum und Verfahren zur Klassifikation auf Grundlage von geometrischen Eigenschaften segmentierter Objekte in einem n-dimensionalen Datenraum
PCT/EP2006/009623 WO2007042195A2 (de) 2005-10-11 2006-10-05 Verfahren zur segmentierung in einem n-dimensionalen merkmalsraum und verfahren zur klassifikation auf grundlage von geometrischen eigenschaften segmentierter objekte in einem n-dimensionalen datenraum

Publications (1)

Publication Number Publication Date
EP1938270A2 true EP1938270A2 (de) 2008-07-02

Family

ID=37525867

Family Applications (1)

Application Number Title Priority Date Filing Date
EP06806044A Withdrawn EP1938270A2 (de) 2005-10-11 2006-10-05 Verfahren zur segmentierung in einem n-dimensionalen merkmalsraum und verfahren zur klassifikation auf grundlage von geometrischen eigenschaften segmentierter objekte in einem n-dimensionalen datenraum

Country Status (4)

Country Link
US (1) US8189915B2 (de)
EP (1) EP1938270A2 (de)
DE (1) DE102005049017B4 (de)
WO (1) WO2007042195A2 (de)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2352076B (en) * 1999-07-15 2003-12-17 Mitsubishi Electric Inf Tech Method and apparatus for representing and searching for an object in an image
JP5462866B2 (ja) * 2008-05-14 2014-04-02 コーニンクレッカ フィリップス エヌ ヴェ 画像セグメンテーションに基づく画像分類
JP5415730B2 (ja) * 2008-09-04 2014-02-12 任天堂株式会社 画像処理プログラム、画像処理装置、画像処理方法、および画像処理システム
CN102800050B (zh) * 2011-05-25 2016-04-20 国基电子（上海）有限公司 N维特征空间连通性计算方法
CN102592135B (zh) * 2011-12-16 2013-12-18 温州大学 融合目标空间分布和时序分布特征子空间的视觉跟踪方法
US11972078B2 (en) * 2017-12-13 2024-04-30 Cypress Semiconductor Corporation Hover sensing with multi-phase self-capacitance method

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5313532A (en) * 1990-01-23 1994-05-17 Massachusetts Institute Of Technology Recognition of patterns in images
JPH07123447A (ja) * 1993-10-22 1995-05-12 Sony Corp 画像信号記録方法および画像信号記録装置、画像信号再生方法および画像信号再生装置、画像信号符号化方法および画像信号符号化装置、画像信号復号化方法および画像信号復号化装置、ならびに画像信号記録媒体
US5793888A (en) * 1994-11-14 1998-08-11 Massachusetts Institute Of Technology Machine learning apparatus and method for image searching
FR2740220B1 (fr) * 1995-10-18 1997-11-21 Snecma Procede de detection automatique des zones expertisables dans des images de pieces mecaniques
US6526168B1 (en) * 1998-03-19 2003-02-25 The Regents Of The University Of California Visual neural classifier
US6480627B1 (en) * 1999-06-29 2002-11-12 Koninklijke Philips Electronics N.V. Image classification using evolved parameters
DE10017551C2 (de) * 2000-04-08 2002-10-24 Carl Zeiss Vision Gmbh Verfahren zur zyklischen, interaktiven Bildanalyse sowie Computersystem und Computerprogramm zur Ausführung des Verfahrens
US20020122491A1 (en) * 2001-01-03 2002-09-05 Marta Karczewicz Video decoder architecture and method for using same
US20020165839A1 (en) * 2001-03-14 2002-11-07 Taylor Kevin M. Segmentation and construction of segmentation classifiers
KR100446083B1 (ko) * 2002-01-02 2004-08-30 삼성전자주식회사 움직임 추정 및 모드 결정 장치 및 방법
WO2004111934A2 (en) * 2003-06-16 2004-12-23 Dynapix Intelligence Imaging Inc. Segmentation and data mining for gel electrophoresis images

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2007042195A2 *

Also Published As

Publication number Publication date
US20080253654A1 (en) 2008-10-16
DE102005049017B4 (de) 2010-09-23
WO2007042195A3 (de) 2007-09-07
US8189915B2 (en) 2012-05-29
WO2007042195A2 (de) 2007-04-19
DE102005049017A1 (de) 2007-04-12

Similar Documents

Publication Publication Date Title
DE60215063T2 (de) System und verfahren zur ermittlung von bildähnlichkeiten
DE60034668T2 (de) Methode zur texturanalyse von digitalen bildern
DE69428089T2 (de) Gerät und Verfahren zur Bildanalyse
DE69031774T2 (de) Adaptiver Gruppierer
DE60114469T2 (de) Methode und Gerät zur Bestimmung von interessanten Bildern und zur Bildübermittlung
DE60109278T2 (de) Verfahren und Gerät zur Lokalisierung von Schriftzeichen in Bildern aus einer Digitalkamera
DE69805798T2 (de) Fingerabdrukklassifikation mittels raumfrequenzteilen
EP1316057B1 (de) Auswerten von kantenrichtungsinformation
DE69322095T2 (de) Verfahren und gerät zur identifizierung eines objekts mittels eine geordneten folge von grenz-pixel-parametern
DE102017220307B4 (de) Vorrichtung und Verfahren zum Erkennen von Verkehrszeichen
DE60217748T2 (de) Verfahren und Gerät zur Anzeige eines Bildraumes
DE102019127282A1 (de) System und Verfahren zum Analysieren einer dreidimensionalen Umgebung durch tiefes Lernen
DE112015000964T5 (de) Bildverarbeitungsvorrichtung, Bildverarbeitungsverfahren und Bildverarbeitungsprogramm
DE69231049T2 (de) Bildverarbeitung
DE60303138T2 (de) Vergleichen von mustern
WO2007042195A2 (de) Verfahren zur segmentierung in einem n-dimensionalen merkmalsraum und verfahren zur klassifikation auf grundlage von geometrischen eigenschaften segmentierter objekte in einem n-dimensionalen datenraum
WO2010133204A1 (de) Vorrichtung und verfahren zur identifizierung des urhebers eines kunstwerkes
DE102022201780A1 (de) Visuelles Analysesystem zum Bewerten, Verstehen und Verbessern tiefer neuronaler Netze
DE102020215930A1 (de) Visuelle analytikplattform zum aktualisieren von objektdetektionsmodellen in anwendungen des autonomen fahrens
DE19928231C2 (de) Verfahren und Vorrichtung zur Segmentierung einer Punkteverteilung
DE60033580T2 (de) Verfahren und gerät zur klassifizierung eines bildes
DE10017551C2 (de) Verfahren zur zyklischen, interaktiven Bildanalyse sowie Computersystem und Computerprogramm zur Ausführung des Verfahrens
DE112019004112T5 (de) System und verfahren zur analyse mikroskopischer bilddaten und zur erzeugung eines annotierten datensatzes zum training der klassifikatoren
DE102019105293A1 (de) Schätzung der Bewegung einer Bildposition
EP2096578A2 (de) Verfahren und Vorrichtung zur Charakterisierung der Formation von Papier

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20080308

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LI LT LU LV MC NL PL PT RO SE SI SK TR

17Q First examination report despatched

Effective date: 20101122

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: CARL ZEISS MICROIMAGING GMBH

DAX Request for extension of the european patent (deleted)
RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: CARL ZEISS MICROSCOPY GMBH

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: EXAMINATION IS IN PROGRESS

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20170503