What is image segmentation

Image segmentation: overview


1 seminar: Image segmentation and computer vision WS 2005/06 Jens Kürbig and Martina Sauter

2 Content: 1. Introduction 2. Pixel-oriented processes 3. Edge-oriented processes 4. Region-oriented processes 5. Model-based processes 6. Texture-oriented processes 2

3 1. Introduction 1.1 Concept of image segmentation Question: What is image segmentation? Quote: to check each individual pixel to see whether it belongs to an object of interest or not. This operation is called segmentation ... ([2], p. 449) 3

4 1. Introduction I.e. image segmentation is the process of checking each individual pixel to determine whether it belongs to an image object that is of interest to us. Image segmentation should: combine different image points into meaningful groups separate image objects from the background separate image objects from one another In short: which image points belong together? 4th

5 1. Introduction Results: Binary image (black and white image): Image point has value 1 belongs to the object Image point has value 0 does not belong to the object Image is divided into meaningful regions Outlines of the objects But: The image segmentation is not used to determine whether the found object makes sense or not. After segmentation, the shape of the object can be examined more closely. 5

6 1. Introduction 1.2 Application medicine: e.g. Cancer detection, computed tomography Carcinogenic breast tissue and the associated extracted three-phase image Computed tomography original image segmented image 6

7 1. Introduction of binarization of keratin networks in the cytoskeleton Original image, segmented image with threshold value method, segmented image (processed) 7

8 1. Introduction to handwriting recognition: hand / signature recognition Quality control: optical inspection Geography: segmentation of aerial photographs Original image segmented image with region growing 8

9 1. Introduction 1.3 Classification Image segmentation is part of the first step in image analysis Image analysis: Scene Image acquisition Image preprocessing Segmentation Feature extraction Classification / evaluation Statement 9

10 1. Introduction 1.4 Overview of the process Idea: Imitation of the human eye There are three ways in which the human eye recognizes several pixels as one object: Color, Shape, Texture 10

11 1. Introduction What all segmentation methods have in common: Properties are assigned to each pixel Properties are used to subdivide the pixels into groups In the following our properties: Gray value Gray value: indicates the brightness of the pixel values ​​between 0 and 255 (because it is stored in binary in 8 bits; 0 corresponds to black 255 corresponds to white 2 8 possibilities) 11

12 1. Introduction Image segmentation is divided into: Pixel-oriented processes Edge-oriented processes Region-oriented processes Model-based processes Texture-oriented processes 12

13 2. Pixel-oriented method it is decided individually for each pixel to which object it belongs. The method usually results in complete segmentations 13

14 2. Pixel-oriented method Method using threshold value method Gray value of the pixel is compared with a threshold value Binarization of the image with only one threshold value Several threshold values ​​possible for several phases Advantages Simple implementation Fast method Complete binarization Good results when binarization of evenly illuminated images 14

15 2. Pixel-oriented method Threshold determination using a histogram - mean value between two maxima - local minima - manual definition - Ostu method Optimally bimodal histogram 15

16 2. Pixel-oriented method Histogram of the original Original gray value image 16

17 2. Pixel-oriented methods Disadvantages: susceptibility to changes in brightness Only one-dimensional value is used (no additional information for multi-channel images) No coherent segmentation Strong dependence on the threshold value 17

18 2. Pixel-oriented process Original gray value image segmented. Image with threshold 90 segmented. Image with threshold

19 2. Pixel-oriented methods Possible threshold value methods Global threshold value: a threshold value is used for the entire image Local threshold value: the image is divided into regions and each region has its own threshold value Dynamic threshold value: a region is created around each pixel with its own threshold value Calculation time takes from above downwards to susceptibility to the brightness values ​​decreases 19

20 3. Edge-oriented methods 3.1 Term in the image is searched for edges and contours Idea: meaningful regions are delimited by an edge abrupt change in gray value between meaningful regions Examples of edge-oriented methods: Snakes (see next week's lecture) watershed transformation that always provides closed edges (see later lecture) Approach via gradients 20

21 3. Edge-oriented process Original image, segmented image with edge-oriented process 21

22 3. Edge-oriented methods 3.2 A method approach using gradients: Gray value is represented by a function g (x), where x indicates the pixel position. The initial image is examined line by line. The extremes of the gradient are edge points Edge points 22

23 3rd Edge-Oriented Method Function h (x) corresponds to gray value in a line at position x 1st derivative of h (x) 2nd derivative of h (x) 23

Edge-Tacking: The algorithm only supplies edge points. Edge-tracking algorithm for completion One possible edge-tracking algorithm: Hough transformation (Section 5.2) Advantages of edge-oriented versus pixel-oriented methods: recognize image objects better, even with different brightness, with non-uniform background, here considered in g (x ) 24

25 4. Region-oriented methods The region-oriented methods consider point sets as a whole and try to find connected objects 25

26 4. Region-based methods Method: Region Growing Split-and-Merge Pyramid Linking 26

27 4. Region-oriented method Region-Growing-Principle: Definition of seed points as starting region Neighboring points are added to the region if the value of the distance function between the gray value of the point under consideration and the mean value of the gray values ​​of the neighboring region is below a threshold value Points are also added if they already belong to another region (possible union of regions) repeat growth until none is possible. Choice of suitable seed points is important Number of seed points is the upper limit for the number of regions 27

28 4. Region-oriented split-and-merge principle: Starting point: entire image as one region Use of a homogeneity criterion If the gray value of the image point is greater than a threshold value Division of the region (split) The regions that arise are compared with neighboring regions according to the criterion (Merge) Repetition for all regions that are created, up to sufficiently homogeneous Regions that are created often have angular edges, anti-aliasing necessary for post-processing 28

29 4. Region-oriented methods Pyramid linking or pyramid growth Principle: To simplify matters, the method for 1D images or image strips is explained. The method can easily be extended to the application of a 2D image. Method uses pyramid-like data structure from different levels. The lowest level is the original image.Each pixel on the upper level is the average value of four adjacent pixels from the level below.After reaching the top layer, each pixel is connected to 2 adjacent pixels from the next lower level. The criteria for this are that the image points must have contributed to the color value of the higher level and have the smallest color distance to this. 29

30 4. Region-oriented procedures 30

31 4. Region-oriented process pyramid growth (II) Update of the color values ​​by recalculating the new connections between the pixels If a pixel has no downward connection, the color value is set to zero Connections are then set anew and pixels recalculated. Repeat the process until there are links no longer change 31

32 4. Region-oriented procedures 32

33 4. Region-oriented procedures 33

34 4. Region-oriented processes Pyramid growth (III): Creation of links between pixels that extend from the top to the bottom level In this way, several pixels on the original image are combined into a class. The process copes well with noise, as each pixel is assigned to a class can process is fast and only takes 1/7 of the storage space of the original image 34

35 5. Model-based procedures 5.1 Term so far: Basis only local information (i.e. only local observation of the pixels) but human perception system very complex Local information not efficient! Now: Model-based segmentation requires prior knowledge of the image. 35

36 5. Model-based methods Possible additional information about the image: The geometric shape of the objects This additional information can then be compared with the local information. Model-based methods 36

37 5. Model-based methods 5.2 Hough transformation method for recognizing geometrical figures (e.g. circles, straight lines) Prerequisite: geometrical figures can be parameterized Starting point: e.g. segmented image with edge points, broken lines are completed with Hough transformation to continuous line segments 37

38 5. Model-based methods before Hough transformation after Hough transformation 38

39 5. Model-based methods Ann .: the image objects sought are straight lines The following condition must be met for all edge points found: [x n, yn] T yn = a0 + a1x n (1) a 1 = y x n n 1 a x n 0 (2) 39

40 5. Model-based methods 40

41 5. Model-based method (2) is a straight line in a vector space, which is spanned by 0 and. This vector space is called model space. a a 1 Each edge point shown. [x n, yn] T is a straight line in the model space T Ann .: all points [x n, yn] lie on a straight line. All straight lines in the model space intersect at a point 41

42 5. Model-based methods This intersection point [a 0, a1] of the straight line equation (1). T a 0 a 1 is what we are looking for and this transformation from the vector space, which is spanned by x and y, into the model space is called the Hough transformation. But in practice: if one does not use (1) reason for this: a 1 can become infinite (if (1) is a straight line parallel to the y-axis) 42

43 5. Model-based methods Therefore the normal form of a straight line is used: where x cos (θ) + y sin (θ) = n = cos (sin (θ) θ) d x n = y d with [0) θ, π d θ 43

44 5. Model-based procedures Our model space is spanned by and. (, finite) θ d θ d Disadvantage of the Hough transformation: every single point has to be transformed into the model space high effort 44

45 6. Texture-oriented methods Often a segment is not characterized by a uniform color, but rather by a uniform structure. Texture-oriented methods try to use the structure as a criterion for homogeneity

46 6. Texture-oriented methods Definition of a texture: Texture means the image that is displayed on the surface of a virtual body. Textures can change practically every property of a surface in a targeted manner Smoothness behavior. 46

Texture-oriented methods Methods: Co-currence matrices Texture energy measures (Texture Energy Measure) Run length matrices (Run Length Matrix) Signal-theoretic concepts (e.g. gabor filtering) Markov random fields (MRF) 47

48 6. Texture-oriented methods There are different forms of Markov random fields: Normalized Form Canonical Form Hierarchical Gibbs Random Field * Auto Models: Auto-logistic Model Auto-normal Model Auto-binomial Model (explained in more detail below) Gibbs Random Field is a Specialized case of an MRF The following explanations only result from [1], more detailed and detailed derivations or explanations can be found in literature [4]. 48

49 6. Texture-oriented methods Auto-binomial model: β β β β β β β β β β β 6 2 α β β 2 6 β β β β β β β β β β Evaluation of a point x and its neighbors in relation to x With different orders, only parts of the neighbors are considered. With the first order: the four direct neighbors With the second order: all eight direct neighbors, etc. 49

50 6. Texture-Oriented Methods Markov Random Fields: Textures in an nxn gray value image are described with the values ​​{0 ,, N-1} Values ​​of an image point B (x), where x = (x, y) correlates with the neighboring points. A point y is called Neighbor of x, if for a suitable neighborhood U, which belongs to the set of neighboring points V, the following applies for the transition probability: p (b (x) B (U))> 0 for all x, x = (x, y) p (b (x) B (U)) = p (b (x) B (S \ {x})) where B (U) = {B (u) u UV} and S is the set of all grid points, i.e. { x}) = {B (s) s S {x} B (S \ \ 50

51 6. Texture-oriented methods Probability of success from point x: where T: = α + algorithm for generating a texture (auto-binomial MRF): Choose an output color for the image B (x), where x = (x, y), with gray values, uniformly distributed, nxn pixel Determine the order and constants α, β i etc. to determine the transition probabilities p ϑ (T): = exp (T) / (1 + exp (T)) (xi, yi β B ((xi) UN 1 kk (B ((x, y)) = k B (U)) = ϑ (T) (1 ϑ (i, yi)) T)) N 1 k 51

52 6. Texture-oriented method Repeat the following loop until there is no more change in the image: 1. Select two points (x 0, y 0) and (~ x ~ 0, y 0) of different color B ((x 0, y 0 )) and B ((~ x ~ 0, y)). Now create a coloring B ((x, y 0, which corresponds to B ((x, y)) except for the swapped values ​​of the points (x 0, y0) and ~)) new (x, ~ 0 y0). Find: r: = p (Bnew ((x, y)) B (U)) 0 p (B ((x, y)) B (U)) n 1 x =, y = 0 (x 0, y 0 2nd remark: Here only the direct neighbors of the points and (~ x ~ 0, y 0) in the product are to be considered. If r 1, then replace the gray values ​​B ((x, y)) with B new ((x, y)); otherwise generate a realization of a random number u [01,) uniformly distributed. If r> u, then replace B ((x, y)) with B new ((x, y)) 3. Name the new coloring again B (x, y)) 52

53 Literature [1] A. Janser, W. Luther, W. Otten Computer graphics and image processing, Vieweg [2] B. Jähne, Digital image processing, Springer, 2001 [3] S.Z. Li, Markov Random Field Modeling in Computer Vision, Springer, 1995 [4] Prof. Dr. Volker Schmidt, Markov chains, (53