Image Set Operations

Mathematical Morphology

Morphology is a tool for extracting information from images on the basis of spatial structure and relationships. Such spatial elements of region shape as boundaries, skeletons and the convex hull can be found. Morphology is useful for preprocessing images to fill in holes and remove noise.

Morphology is based on set theory . We will construct some IDL tools to carry out set operations that can be combined with standard morphological operations such as dilation and erosion.

Set Indexes

Two images named A1 and A2 are shown at the right. The background in each image is 0 and the foregraound is 1, represented by black and white.

All of the pixels that have a certain property can be found with the WHERE function.

k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0)

k1 and k2 are indexes of pixel sets. They are actually vectors in IDL that have as many components as there are in the set.

Index Structure

The index of a pixel at location (x,y) is k=N*y+x where N is the number of columns in the image. The set indexes are relative to the position of the set in the base image.

The column and row indexes of all of the pixels in a set can be found with the following commands:

y=k/N x=k MOD N

Note that x and y are vectors with as many elements as k.

The images A1 and A2 are of size 256x256. The first six elements of the vector k1 and its column and row values are:

k1[0:5]=[36411 36666 36667 36920 36921 36922] x1[0:5]=[59 58 59 56 57 58] x1[0:5]=[142 143 143 144 144 144]

Image Reflection

A standard morphological operation is the reflection of all of the points in a set about the origin of the set. The origin of a set is not necessarily the origin of the base.

Shown at the right is an image and its reflection about a point (shown in red). The second pane shows the original image in green and the reflected image in white.

An IDL function that computes the reflection of a set of points needs to know the original index set, the origin and the number of columns and rows in the image.

Assume that the set k and the origin kp are known.

imSiz=SIZE(A1) khat=Reflection(k,kp,imSiz[1],imSiz[2]) Ar=BYTARR(imSiz[1],imSiz[2]) Ar[khat]=1B

FUNCTION REFLECTION,k,kc,ncols,nrows ;+ ;khat=REFLECTION(k,kc,ncols,nrows) is the reflection of image set k ;about the origin represented by kc. The number of columns and rows in the ;base image must be provided. ; ;HISTORY ;Written by HR Sept. 1999 for SIMG-782 ;- IF N_PARAMS() LT 4 THEN MESSAGE,'REFLECTION has too few arguments' ;Find the rectangular coordinats of the set points and the origin. x=k MOD ncols y=k/ncols xc=kc MOD ncols yc=kc/ncols ;Reflect about the origin. If x=xc + dx then xr=xc-dx=2*xc-x. ;Same for yr. xr=2*xc-x yr=2*yc-y ;Keep the points that fall within the base image frame. is=WHERE(xr GE 0 AND xr LT ncols AND yr GE 0 and yr LT nrows) khat=yr[is]*ncols+xr[is] RETURN,khat END

Some other reflections are shown at the right. The Reflection function chops off the part of the reflection that falls outside the frame.

In the second pane the original set is shown in green for reference. The reflected set is in white.

The area shown in blue is the region of overlap of the original and reflected image. The reflected image includes both the white and blue parts.

Set Union

The union of two or sets includes all of the points that are in one or more of the sets.

This is illustrated at the right. In the first pane the set A1 (white) is overlaid with the set A2 (red). The right pane shows the union set.

k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) ku=Union(k1,k2) Au=BYTARR(imSiz[1],imSiz[2]) Au[ku]=1B

Set Intersection

The intersection of sets includes the points that are in all of the sets. Use Intersection to find the common points.

The common area of sets A1 (white) and A2 (red) is highlighted in green. The right pane shows the intersection set.

k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) ku=Intersection(k1,k2) Au=BYTARR(imSiz[1],imSiz[2]) Au[ku]=1B

Set Complement

The complement of a set is the set of pixels that are not in the set. The complement is always in reference to a global set.

The function COMPLEMENT finds the complement relative to all of the pixels in an image. The complement of the set A1 is the set of white pixels in the right-hand pane.

k1=WHERE(A1 GT 0) npixels=imSiz[4] ;Number of pixels in image ku=Complement(k1,npixels) Ac=BYTARR(imSiz[1],imSiz[2]) Ac[ku]=1B

Set Difference

The difference of two sets A and B is the set of points in A and not in B.

These are the points that are in A and in the complement of B.

The sets A1 (white) and A2 (red) with their overlap (green) are shown in the left pane. The difference is shown in the right pane.

k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) kd=Difference(k1,k2) Ad=BYTARR(imSiz[1],imSiz[2]) Ad[kd]=1B

Dilation

Dilation involves an image set A and a structuring element S. The origin of the structuring element is placed on each pixel of A. If any part of the structuring element is then within A, add the pixel at the origin to the dilation set D.

D=DILATE(A,S) is a built-in IDL function. A must be a binary image and S a binary structuring element.

Erosion

Erosion involves an image set A and a structuring element S. The origin of the structuring element is placed on each pixel of A. If all of the structuring element is then within A, add the pixel at the origin to the dilation set E.

E=ERODE(A,S) is a built-in IDL function. A must be a binary image and S a binary structuring element.

Opening

The Opening operation is a combination of dilation and erosion. It smooths the contour of an image, breaks narrow connections between image parts, and eliminates thin protrusions. Opening uses a structuring element for each step.

An opening function that is constructed by combining the dilation and erosion operations is:

Opening(A,S)=Dilate(Erode(A,S), S)

First Erode with S then Dilate with S.

The effect of opening the BW1 image with a 7x7 structuring element is shown in the right pane. You should try this operation on other images and with other structuring elements.

Closing

The Closing operation is also a combination of dilation and erosion, but in reverse order. It also smooths the boundaries of objects. But instead of breaking or eliminating parts of objects, it tends to fuse narrow breaks and close small holes.

Closing(A,S)=Erode(Dilate(A,S),S)

The effect of closing the BW1 image with a 7x7 structuring element is shown in the right pane. You should try this operation on other images and with other structuring elements.

Boundary Extraction

The boundary of an object is a very important part of its spatial description. We may define the boundary B(A) as the set of pixels in A with a neighbor that is not in A.

One method of finding the boundaries of objects in a binary image is to use morphology. If E=Erode(A,S) where S is a 3x3 structuring element, then every boundary pixel will be eliminated. The boundary pixels are those in A and the complement of E.

The boundary can be computed using logic statements.

B=A AND NOT ERODE(A,S)

Set Indexes Two images named A1 and A2 are shown at the right. The background in each image is 0 and the foregraound is 1, represented by black and white. All of the pixels that have a certain property can be found with the WHERE function. k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) k1 and k2 are indexes of pixel sets. They are actually vectors in IDL that have as many components as there are in the set.
*Index Structure* The index of a pixel at location (x,y) is k=Ny+x where N is the number of columns in the image. The set indexes are relative to the position of the set in the base image.* The column and row indexes of all of the pixels in a set can be found with the following commands: y=k/N x=k MOD N Note that x and y are vectors with as many elements as k.	The images A1 and A2 are of size 256x256. The first six elements of the vector k1 and its column and row values are: k1[0:5]=[36411 36666 36667 36920 36921 36922] x1[0:5]=[59 58 59 56 57 58] x1[0:5]=[142 143 143 144 144 144]

*Image Reflection* A standard morphological operation is the reflection of all of the points in a set about the origin of the set. The origin of a set is not necessarily the origin of the base. Shown at the right is an image and its reflection about a point (shown in red). The second pane shows the original image in green and the reflected image in white.
An IDL function that computes the reflection of a set of points needs to know the original index set, the origin and the number of columns and rows in the image. Assume that the set k and the origin kp are known. imSiz=SIZE(A1) khat=Reflection(k,kp,imSiz[1],imSiz[2]) Ar=BYTARR(imSiz[1],imSiz[2]) Ar[khat]=1B	FUNCTION REFLECTION,k,kc,ncols,nrows ;+ ;khat=REFLECTION(k,kc,ncols,nrows) is the reflection of image set k ;about the origin represented by kc. The number of columns and rows in the ;base image must be provided. ; ;HISTORY ;Written by HR Sept. 1999 for SIMG-782 ;- IF N_PARAMS() LT 4 THEN MESSAGE,'REFLECTION has too few arguments' ;Find the rectangular coordinats of the set points and the origin. x=k MOD ncols y=k/ncols xc=kc MOD ncols yc=kc/ncols ;Reflect about the origin. If x=xc + dx then xr=xc-dx=2xc-x. ;Same for yr. xr=2xc-x yr=2yc-y ;Keep the points that fall within the base image frame. is=WHERE(xr GE 0 AND xr LT ncols AND yr GE 0 and yr LT nrows) khat=yr[is]ncols+xr[is] RETURN,khat END
Some other reflections are shown at the right. The Reflection function chops off the part of the reflection that falls outside the frame. In the second pane the original set is shown in green for reference. The reflected set is in white. The area shown in blue is the region of overlap of the original and reflected image. The reflected image includes both the white and blue parts.
*Set Union* The union of two or sets includes all of the points that are in one or more of the sets. This is illustrated at the right. In the first pane the set A1 (white) is overlaid with the set A2 (red). The right pane shows the union set. k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) ku=Union(k1,k2) Au=BYTARR(imSiz[1],imSiz[2]) Au[ku]=1B
*Set Intersection* The intersection of sets includes the points that are in all of the sets. Use Intersection to find the common points. The common area of sets A1 (white) and A2 (red) is highlighted in green. The right pane shows the intersection set. k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) ku=Intersection(k1,k2) Au=BYTARR(imSiz[1],imSiz[2]) Au[ku]=1B
*Set Complement* The complement of a set is the set of pixels that are not in the set. The complement is always in reference to a global set. The function COMPLEMENT finds the complement relative to all of the pixels in an image. The complement of the set A1 is the set of white pixels in the right-hand pane. k1=WHERE(A1 GT 0) npixels=imSiz[4] ;Number of pixels in image ku=Complement(k1,npixels) Ac=BYTARR(imSiz[1],imSiz[2]) Ac[ku]=1B
Set Difference The difference of two sets A and B is the set of points in A and not in B. These are the points that are in A and in the complement of B. The sets A1 (white) and A2 (red) with their overlap (green) are shown in the left pane. The difference is shown in the right pane. k1=WHERE(A1 GT 0) k2=WHERE(A2 GT 0) kd=Difference(k1,k2) Ad=BYTARR(imSiz[1],imSiz[2]) Ad[kd]=1B
Dilation Dilation involves an image set A and a structuring element S. The origin of the structuring element is placed on each pixel of A. If any part of the structuring element is then within A, add the pixel at the origin to the dilation set D. D=DILATE(A,S) is a built-in IDL function. A must be a binary image and S a binary structuring element.
Erosion Erosion involves an image set A and a structuring element S. The origin of the structuring element is placed on each pixel of A. If all of the structuring element is then within A, add the pixel at the origin to the dilation set E. E=ERODE(A,S) is a built-in IDL function. A must be a binary image and S a binary structuring element.
Opening The Opening operation is a combination of dilation and erosion. It smooths the contour of an image, breaks narrow connections between image parts, and eliminates thin protrusions. Opening uses a structuring element for each step. An opening function that is constructed by combining the dilation and erosion operations is: Opening(A,S)=Dilate(Erode(A,S), S) First Erode with S then Dilate with S. The effect of opening the BW1 image with a 7x7 structuring element is shown in the right pane. You should try this operation on other images and with other structuring elements.
*Closing* The Closing operation is also a combination of dilation and erosion, but in reverse order. It also smooths the boundaries of objects. But instead of breaking or eliminating parts of objects, it tends to fuse narrow breaks and close small holes. Closing(A,S)=Erode(Dilate(A,S),S) The effect of closing the BW1 image with a 7x7 structuring element is shown in the right pane. You should try this operation on other images and with other structuring elements.
Boundary Extraction The boundary of an object is a very important part of its spatial description. We may define the boundary B(A) as the set of pixels in A with a neighbor that is not in A. One method of finding the boundaries of objects in a binary image is to use morphology. If E=Erode(A,S) where S is a 3x3 structuring element, then every boundary pixel will be eliminated. The boundary pixels are those in A and the complement of E. The boundary can be computed using logic statements. B=A AND NOT ERODE(A,S)