## How to obtain the chain code

In the previous post I discussed simple techniques to estimate the boundary length of a binarized object. These techniques are based on the chain code. This post will detail how to obtain such a chain code. The algorithm is quite simple, but might not be trivial to understand. Future posts will discuss other measures that can be derived from such a chain code.

In short, the chain code is a way to represent a binary object by encoding only its boundary. The chain code is composed of a sequence of numbers between 0 and 7. Each number represents the transition between two consecutive boundary pixels, 0 being a step to the right, 1 a step diagonally right/up, 2 a step up, etc. In the post Measuring boundary length, I gave a little more detail about the chain code. Worth repeating here from that post is the figure containing the directions associated to each code:

The chain code thus has as many elements as there are boundary pixels. Note that the position of the object is lost, the chain code encodes the shape of the object, not its location. But we only need to remember the coordinates of the first pixel in the chain to solve that. Also note, the chain code encodes a single, solid object. If the object has two disjoint parts, or has a hole, the chain code will not be able to describe the full object.

### Image to chain code

Let’s assume we have a binary image with a single object in it. Using DIPimage, we could generate a suitable test image thus:

`img = rr<30;`

The algorithm also needs an array with the definition of each of the chain codes. Call this a “cipher” if you will. Indexing in this array with one code from the chain gives the change in coordinates as you go from one pixel to the next:

directions = [ 1, 0 1,-1 0,-1 -1,-1 -1, 0 -1, 1 0, 1 1, 1];

Thus, `directions(cc+1,:)`

, where `cc`

is one code from the chain, yields the `[x,y]`

increment for the coordinates. The `+1`

is necessary because MATLAB indexing starts at 1, whereas the first code is 0.

The algorithm starts at any pixel that is on the object’s boundary. We will use MATLAB’s function `find`

to find the first “on” pixel in the image:

indx = find(dip_array(img),1)-1;

We subtract one from the index to obtain 0-based indices, which are much easier to use than MATLAB’s 1-based indices. Next we convert this index into image coordinates:

sz = imsize(img); start = [floor(indx/sz(2)),0]; start(2) = indx-(start(1)*sz(2));

MATLAB is column-major, meaning that indices increase downward first. The function `find`

returned the first object pixel using this column-major indexing, meaning that none of the columns to the left have any object pixels, and in this column, none of the pixels above have any object pixels. The boundary possibly continues downward on one side, and up/right on the other side. That is, from this point the possible steps are chain codes 0, 1, 6 and 7. Codes 3, 4 and 5 all point to the column to the left, which we know is empty, and code 2 points up, where we also know the object cannot be. We choose to follow the boundary clockwise (though it is equally valid to define the chain code counter-clockwise if one so wishes), and thus we need to try the possible steps in this order: 1, 0, 7, 6. If the step 1 yields an object pixel, this is the pixel that continues the boundary in the clockwise direction. If this pixel is empty, we try to see if we find the object using step 0, etc. Once the next pixel is found, this step is repeated again and again until we have travelled all the way around the object and return to the initial pixel at coordinates `start`

. However, each next step has different limits for which directions are possible. The first direction to try (the “most clockwise” neighbour, if you will) is the one that is two codes up from the previous step. That is, the boundary makes a 90° left turn. It cannot make a 135° left turn, because that pixel is also a neighbour to the previous pixel, and if the object is there, the previous step would have pointed to it instead. As before, we first try the “most clockwise” step first, then continue down the codes until we find an object pixel. The following code implements this algorithm:

cc = []; % The chain code coord = start; % Coordinates of the current pixel dir = 1; % The starting direction while 1 newcoord = coord + directions(dir+1,:); if all(newcoord>=0) && all(newcoord<sz) ... && img(newcoord(1),newcoord(2)) cc = [cc,dir]; coord = newcoord; dir = mod(dir+2,8); else dir = mod(dir-1,8); end if all(coord==start) && dir==1 % back to starting situation break; end end

The loop above combines the loop over all the neighbours of a pixel (to find the next boundary pixel) and the loop over all the boundary pixels. This makes the code a lot simpler. We have a starting coordinate and a starting direction. Inside the loop, we test the pixel pointed at by this direction. If it contains an object pixel, we add this direction as a code in the chain, set the current pixel to the newly found boundary pixel, initialize the starting direction to the 90° left turn, and continue on with the loop. If the pixel pointed at contains background (or is outside the image domain), we decrease the direction by one and continue on with the loop. The loop continues until we are back at the starting position (that is, at the same coordinates and direction).

As I said before, this algorithm is very simple, though it might be difficult to understand. I recommend you take a paper and a pen and draw out the steps of the algorithm, until you are satisfied that it always works as intended. Also note, for example, the special case of an object with a single pixel: The algorithm looks in all directions once, then meets the finishing requirements and quits. Thus, a single pixel object has 0 elements in the chain code.

### Chain code to image

The inverse algorithm, walking over the codes in the chain and drawing the boundary back in the image, is much more trivial. We first create an empty, binary image, then start at coordinates `start`

, and modify the coordinates by adding `directions(cc(ii)+1,:)`

, in a loop over `ii`

:

border = newim(sz,'bin'); coords = start; for ii=1:length(cc) border(coords(1),coords(2)) = 1; coords = coords + directions(cc(ii)+1,:); end joinchannels('rgb',img,border')*255

The final command, `joinchannels`

, overlays the two binary images in colour, the original one in red and the newly drawn boundary in green. Where the two overlap, the pixels appear yellow. As you can see, the whole boundary is yellow, indicating that the pixels represented by the chain code are the boundary pixels of the object.

Just for the MATLAB vectorization aficionados out there, I’ve put together this second version of the last algorithm. See if you can figure out how it works!

stride = [sz(2);1]; step = directions*stride; indx = cumsum([start*stride;step(cc+1)]); border = newim(sz,'bin'); border(indx) = 1;

Its good and educative. I need more resources to fully comprehend.

Hi Adams,

You can check a text book like Sonka, Hlavac & Boyle, or Gonzalez & Woods. But I very much recommend you use the MATLAB debugger to step through the code one line at the time, and see how it operates.

Thank you very much.

can i ask you something? what direction is the [ 1, 0; 1 ,-1; etc?]

1,0 is right?

1, -1 is down right? because i don’t understand this.. i understood the 0, 1, 2 , 3…. but not this.

Indeed, (1,0) is right, and corresponds to the 0 chain code; (1,-1) corresponds to the 1 chain code, etc. Thus,

`directions(cc+1,:)`

gives the (dx,dy) coordinate increment corresponding to chain code`cc`

. For any set of coordinates (x,y), adding this increment brings you to the coordinates for the next point on the contour:`[x,y]+directions(cc+1,:)`

. (Note that y increases down, and thus (0,-1) is the up direction!)How can i use the chain code with the array of picture by using VB6?

With my greating.

Dina Jamal.

Sorry Dina, I don’t know much about VB6. But I know it is possible to link your VB6 programs to DIPlib, which contains functions to obtain chain codes and compute their length. See http://www.diplib.org/.

I have a mamogram image with cancerous part in particular area of the image. i have the chain code representation of that cancer part. now, how do i extract or seperate the cancer part of the image.i have the starting point of the image how do i get the cancer part of the image using the chain code i have?

Nivedhitha,

If you use the last bit of code on this post, you will have an image where the border pixels of your cancer are marked. With a command like

`fillholes(border,1)`

you will fill in the inner part. Now you have an image where all cancer pixels are marked.Hi Cris!

I’d like to show in one figure my original image (with the object), then the segmentation of that image (just the white object in black background) and the image that came out of the joinchannels, like using a subplot, is that possible??

Gianna,

Yes, you can, but you have to use standard Matlab handle graphics commands. The DIPimage display will always show only one image per figure window. The function

`image`

will show a Matlab array as an image in an axis:`img = readim;`

bin = threshold(img);

col = joinchannels('rgb',img,bin);

figure, colormap(gray)

subplot(1,3,1), image(dip_array(img));

subplot(1,3,2), image(uint8(bin*255));

`subplot(1,3,3), image(double(col)/255);`

Cris,

Hey, so I am traversing a tree like structure and I am trying to figure out what the code would do if it find a new pixel in two different directions- like two different branches? ( I was looking at this part: ““most clockwise” step first, then continue down the codes until we find an object pixel. “) I want to apply recursion. Let me know your thoughts

Tina,

The algorithm I describe indeed always takes the “most clockwise” step. The algorithm tracks a closed contour, which has no branches. Even if the object itself has branches, and one boundary pixel can have multiple neighbours that are also boundary pixels, there is always one neighbour pixel that is the next one along the contour. There is no need for recursion here.

Cris,

i have an image with selected red edge ellipse, and i don’t know how to obtain chain code for this area

Tyo,

You need to segment your image, so you know which pixels form the object. How to do this depends very much on the image, there’s no one-size-fits-all algorithm to do this. I recommend reading a book on image analysis for ideas. Once you have that, you can apply the code in this post to get the chain code.

Cris,

I used your matlab code to obtain the chain code of a binary fire image. I got an output cc. I didn’t fully understand what the output means, so I have to ask you.

Our goal is to represent the shape of the fire region by retrieving the 8-connected chain code of a given extracted region. A number of points should be used “from the chain code representation

of the boundary,” and these points were then sent to the fourier domain.

So, by all means what points/output should I send to the fourier domain? Is it the cc variable?

Dearick,

The output

`cc`

is the chain code. What it means is described in this blog post. You can convert`cc`

to coordinates of boundary pixels, also described in this post. Those coordinates you can then put into a vector and apply the Fourier transform. How to do this should be described in your text book/lecture notes, I’d wager. Good luck with the exercise! 🙂Cris,

I successfully got the chain code and sent the coordinates in the fourier domain. But is there a way to get the chain code without the dip image tool? Will processing be faster if the code is converted into a normal matlab code?

Dearick,

If speed is important, use the DIPlib function to get the chain code:

`cc = dip_imagechaincode(img,2,1)`

(with`img`

a labelled image not a binary image, and the last parameter is the label ID of the object to get the chaincode for). It can get multiple chain codes at once, see the help.If you want to avoid using the DIPimage toolbox, you could easily convert the code to pure MATLAB; just remember that in DIPimage image objects the indexing starts at 0 and is (x,y), whereas in MATLAB it starts at 1 and is (y,x). Pure MATLAB code will be a little faster, as indexing into a DIPimage image object is slower than indexing into an array.

Dear Sir, How can I compute convex perimeter of a boundary image. I am very thankful for Your favourable reply

Dear Venkateswara,

Take a look at this page where I explain how to get the convex hull from the chain code. The convex hull is a polygon, and it’s perimeter can be obtained simply by adding the lengths of the sides.

amazing. very clearly elaborated

Hi Cris,

Firstly thanks for the thorough explanation of chain code. I wanna ask a few questions:

1. I have found some similar Matlab code Boundary Tracing : http://www.mathworks.com/help/images/ref/bwtraceboundary.html which I think work similarly like chain code but cannot return the encode except traced contour only. Do u think it can be extended to chain code like algorithm.

2. Can this algorithm interpret a 2D object as 3D object? For your information, i am working on single pixel wide drawing and try to determine the junction and get the depth value so that can later be used for 3D reconstruction. In other words, do you think chain code one of the suitable technique to derive the 3D information?

Do you think it can work? Thanks in advance.

Hi Naddy,

1. Yes, this is more or less the same algorithm, but it returns the coordinates of the pixels. You can then convert the coordinates into a chain code, which is quite simple. Given the output array

`B`

,`diff(B)`

is an array where the rows are [1,0], [1,-1], etc. There are 8 of these combinations, each one corresponds to a chain code.2. I’m not sure what you’re asking here, but the chain code does not extend to 3D.

Many Thanks Cris for fast replied, I really appreciate those efforts you put on it. Last but not least, Do you have any idea, what is suitable algorithm I may use to interpret 2D line drawing, maybe you have something in your mind. As I mentioned previously now I processing the line drawing to be converted to 3D object by using Matlab. In other words, I am working on a line drawing interpreter, and the main objective is to derive the depth (Z) value from this 2D line drawing. Just share your idea if you have it. Again Thanks Cris.

Hi again Naddy,

Your problem doesn’t sound trivial at all. You could try the Hough transform (

`hough`

,`houghpeaks`

,`houghlines`

) to find the lines in your drawing. Interpreting the 3D object represented would then require quite a bit of logic…Hi again Cris, Now I’m successfully installed the DipLib and run the chain code program.One simple question, What is meant by img=rr<30;. So Let say I have my own image, I just need to import my image by using toolbox appeared after run the dipstart.m?

Sorry, i have to ask this simple question due to insufficient time. Really appreciate on your assistance

Thanks again

Hi Naddy,

`img=rr<30`

creates the test image.`rr`

is an image where each pixel's value is the distance to the origin.To read in your own image, use

`readim`

. You then probably need to`threshold`

it to make it into a binary image.Thanks Cris,

Now I am using readim to import my thinned image, but No chain code series returned.

I think it should be workable since it binary image with single line drawing closed contours .

Many thanks again Cris, Now I am near to obtain chain code.Just a matter of an image now

Cris, sorry my disturbing again. Now I can apply my own image after applied the imfill function to fill the holes. However, this algorithm just managed to trace external boundaries isnt? how about internal boundaries?

Hi Naddy,

The chain code algorithm as described here traces the external boundary. You can start it at a pixel on an internal boundary, and it will trace that. But there is no way of encoding multiple boundaries in one chain.

If you just want to trace all the boundaries, without using any chain codes, you can simply do

`bdilation(img,1)-img)`

or`img-berosion(img,1)`

.Sir,

I am getting an error if i try to use my own image for this code. The error is

Undefined function ‘dip_array’ for input arguments of type ‘uint8’.

Please tell me what do i have to change.

Thanks in advance

Ash,

That is because

`img`

is expected to be a`dip_image`

object.Start with

`img=dip_image(img)`

, then run the other commands in the post.Sir,

I am getting an error in dimensions and i am new to this, So please tell me what to do?

“Error using =0) && all(newcoord<sz)

Sir,

I am getting an error like:

“Error using > (greater than symbol)

Matrix dimensions must agree.”

Please tell me what to do.

Ash,

I’m not sure what problem you run into, given the information you give, it could be any number of things. Have you installed DIPimage? Is your input image two-dimensional and binary?

Yes it is two-dimensional but not binary. Should i change it to binary first.. I have installed DIPimage..

Yes, the code expects a binary image as input. try the

`threshold`

function.sir,

Is there any algorithm that I can use to convert binary bits to geometrical shape format and again retrieve bits back ? Can we use chain code fo that ?As i’am newbies for this fiels sorry if i’am wrong.

Varun,

The code on this page shows how to convert a pixel-based representation of a binary object to a polygonal boundary representation, and back again. I’m not sure what else you are looking for.

Hi Cris;

I try to measure the lengths of interfacial area in a polymermix. Can I do that with chain code ?

I did it with simple Imaging Processing Toolbox codes and it is good if I have solid objects

Belove you can see some picture of my study

Regards

http://imageshack.com/a/img29/3469/iw0q.jpg

http://imageshack.com/a/img33/651/upm7.jpg

http://imageshack.com/a/img833/7417/8mgk.jpg

Hi Turi,

I’m sure you can do this with chain codes. I guess you are having trouble measuring the length of the ‘inner’ boundaries. Note that you can start the chain code algorithm at any pixel in your image. If you start it at one of the ‘inner’ boundaries you’ll get the chain code for that contour.

Good luck!

Hi Chris ;

You wrote”The chain code encodes a single, solid object. If the object has two disjoint parts, or has a hole, the chain code will not be able to describe the full object

”

I have this problem with my own codes.

B = bwboundaries(D,8,’noholes’);

imshow(D); hold on;

for k=1:length(B),

boundary = B{k};

plot(boundary(:,2),…

boundary(:,1),’r’,’LineWidth’,2);

end

x=boundary(:,2);

y=boundary(:,1);

My plot follow the border and come back to the start point. Is there any solution for it ?

Because as you see a mixture is very confusing and I dont any idea where start my plot or where end?

Thank you so much

How to apply these for regular images, without using DIPimage toolbox?

Turi,

I’m not sure what the problem is. The chain code algorithm I posted follows a single, closed contour. There is a bit of code first that looks for the first object pixel in the image. From there on, it follows the contour. If you change this start point, it will follow another contour, even one that is inside an object. Just pick any start point on each of the contours you want to measure, and compute the chain codes from those points.

cdh,

It should not be difficult to rewrite the code here to be plain MATLAB. Sorry I cannot help with that.

Hi Chris

i need to detection the point in image and mesurments distance in image foot…how us chain code to detection point in image,,,,thanks

Fatima,

The chain code is not useful for detection, you can only use it once you have detected your object.

hii i wana ask..how to obtain the chaincode of many objects in an image?

Easiest is to label the image (connected component analysis that assigns the same object ID to each pixel belonging to the same connected component), and then run the algorithm described here once for each object.

hi cris,

i’ve tried to apply CCL to the objects but there are too many errors.. can u help me a little bit? is it possible to get chaincode staright away without applying CCL first?

Rohayu,

Try this in MATLAB with DIPimage:

img = threshold(readim('cermet'));

img = label(img);

cc = dip_imagechaincode(img,2,[]);

ccwill be a struct array with a chain code for each object inimg.hi cris

currently i’ve conducted a project of classifying normal and abnormal red blood cell. but i got stuck on the same problem. is this source code possible to label the image coz ive run the source code ur given..but still cant run?

i=imread(‘imagecrop.png’);

c=rgb2gray(i); %conversion to gray

%imshow(i);

l=graythresh(c);%threshold value for getting a binary image

f=im2bw(c,l); %converting the grayscale image to binary vth reference to the threshold level

x=bwareaopen(f,40000); %to remove the xtra noise nd defining the area,area cud be found out by using imtool

imshow(x);

[q,n]=bwlabel(x,4); %label connected components in 8×8 pixels(not more than 8),n=no.of objects

graindata=regionprops(q,’basic’);

for j=1:5

a = graindata(j).Centroid;

a = round(a);

y = a(1)

x = a(2)

rectangle(‘Position’,[y-4 x-4 8 8],’EdgeColor’,’r’);

drawnow;

end

Rohayu,

I don’t know what problem you get stuck on, or what errors you are getting, so I cannot help you. If you want help, you need to be specific!

Note that the code I’ve posted requires DIPimage. Did you install DIPimage?

Dear sir

I am working on the “Lung segmentation in CT scan images”, Initially i have applied the adaptive thresholding in MATLAB for the lung segmentation and obtain the binary image from it, Now i have to Extract the Lung Boundary by applying bidirectional chain code (In horizontal & vertical Direction). But I don’t know how to apply this bidirectional chain code in MATLAB.

I would like to Know how to obtain the bidirectional chain code of the o/p binary image..? and How to trace the boundary from the obtained chain code on the output Binary image ?

Thanks in Advance

Ganesh,

If this “bidirectional chain code” is something different from what I describe on this page, you’ll have to find another source explaining it. Did you search the literature?

Dear Sir

Thanks for your reply, Yes sir i have searched the literature. In the bidirectional chain code number number corresponding to the direction from one pixel (i) to the next (i+1) in a chain, c(i) belongs to {0, 1, -1}, where i represents the index value for the pixel. The assigned code word for each direction is based on the Horizontal and vertical encoding coordinate system. The details procedure is mentioned in the following steps.

Step 1: Horizontal code word generation, In this Horizontal code word generations the encoder moves along the boundary in the clockwise way.

Step 2: Arrow map generation, An arrow map is generated to represent the directions that the encoder moves.

Step 3: Code word Assignment, A code word is assigned to each arrow according to Horizontal coordinate encoding system.{ Horizontal encoding coordinate system is : If f(x,y) is the center pixel then the Horizontal encoding coordinate system is like this [f(x,y+1)=-1, f(x+1,y-1)=-1, f(x,y-1)=0, f(x-1,y-1)=1, f(x,y-1)=1, f(x-1,y+1)=1, f(x,y+1)=0, f(x,y+1)=0]}

Step 4: Vertical code word generation, The vertical code word is generated in similar manner, but using the vertical encoding coordinate system. { Vertical encoding coordinate system is : [f(x,y+1)=0, f(x+1,y-1)=1, f(x,y-1)=1, f(x-1,y-1)=1, f(x,y-1)=0, f(x-1,y+1)=-1, f(x,y+1)=-1, f(x,y+1)=-1]}

Please help me to solve this problem, Thanks in Advance

Ganesh,

I fail to see what the problem is. This cannot be difficult to implement.

You are not expecting me to write code for you, are you?

Dear sir

thank you once agin for your reply. I will try to implement it, I was not expecting you to write code for me.

i just wanted to know the procedure for finding bidirectional chain code & also wanted to know, how to trace the boundary from the obtain chain code.

Ganesh,

It seems to me that this “bidirectional chain code” you obtain the same way as I describe above, but instead of writing down a number between 0 and 7, you write down the change in x or y coordinates. Chain code 0 = [1,0], chain code 1 = [1,1], etc. Basically, the

steparray in the last bit of code. There you also see how to convert this back to pixel indices, so you can draw the boundary over your image.Thank You so much it will solve my problem.

Hello Cris

I would like to know can we apply the chain code to the object given in the link below..? Because as per the information given in your blog, Chain code will not able to describe the full objects are disjoint.

If it is possible to find the chain code then, How to find the starting point of this two objects. How to draw the boundary back in the image using MATLAB ..?

The Input binary image is given in this link

https://imageshack.com/i/f0ivqBORp

If you answer this question it would be great help for me. Thanking you

Mani,

Please see above a question asked on this page about two weeks ago. The solution is to do connected component labelling, then find the first pixel with value 1, first pixel with value 2, etc., and get the chain code starting at each of these. Drawing the boundaries back into the image works the same as with a single chain.

Thank you very much.

hi how to get shape index of images?

Hello sir,

i want to implement chain code on Character image R but i dont know how to apply chain code on Character image….

please give some idea about Freeman chain code on image….basic procedure…

thnks

Ryu,

There are many shape descriptors for objects. One of the better known ones is the circularity, a normalised ratio of area divided by the square of the perimeter. See elsewhere in this blog how to compute those.

Shavidatt,

The basic procedure is outlined in this post, I don’t understand what you’re asking me.

Respected sir,

i want to detect the curve of R character image using chain code….how to do this….

please give me procedure for apply chain code on character image if i dont want to use DIPImage toolbox….

suggest me…

Shividatt,

Sorry, the procedure is described above, I’m sure it’s not difficult to rewrite the code in any other language.

I hope you’re not expecting me to write code for you or to do your homework for you!

Respected sir,

when i run above chain code the figure(1),figure(2)……display gain an again how to stop this…..i want to display only one chain code image. how to do this….

and i use another method also fchcode() but i am getting only chain code….how to display original image using chain code……

please help me….

Respected sir,

when i run above chain code i am getting image but the image is displayed again an again figure(1),figure(2)… and pixel marker above image…..how to stop this

sir is this possible chain code of same image can be different….

Respected sir,

when i run below code:

I=imread(‘thinning.jpg’);

c=fchcode(I)

i got the error at fchcode() input curve is broken…..please how to solve this problem

Shivadatt,

Writing the same comment twice is not going to get you a reply faster.

If you don’t want MATLAB to show the output, add a semicolon (;) to the end of the command.

You can get different chain codes from the same image: if there are different boundaries, each boundary yields a valid chain code. Also, depending on the start point along the boundary, the chain code will look different (it will simply be a rotated version of the same code).

I have no idea what

`fchcode`

is, how could I possibly help you with it???Sir I have to find the chain code direction between two given points.. Please help me with this..

Thank You..

Naarani,

I’m not sure what you’re asking. If the points are neighbours, you can find the chain code for the step using the lookup table in this post. If the points are further apart, you could consider drawing a line between the two (search for my blog post on Bresenham lines) and use the code in this post to get the chain code.