The Comeback. Physics 301: Advanced Image and Video Processing

It's been so long since I have opened this blog. The number of page views is immense! It's surprising. Perhaps the lower years who also took Physics 186 under Dr. Soriano used it as a reference (just like what I did back then, looking through older students' blogs haha). Apparently, I have also made it public, so those who searched google about image processing might have stumbled upon this. If I had known, I should have made more effort to write my reports well. I've seen some embarrassing typographical and grammatical errors! So if you're one of those following this blog, I sincerely apologize for this. Good news to you also, I'm back to writing my results in class activities and discussing them online.

Since I am already in graduate school (2nd year, Masters in Physics), it's about time to upgrade this blog -- understanding photographs -- on a new higher level. Physics 301 is one of the Special Topics in Experimental Physics course being offered this semester as an elective. It's course title is Advanced Signal and Image Processing and it is currently handled by none other than (as always, the one and only) Dr. Maricor Soriano. I was so ecstatic when I first received an email requiring me to take this subject. Apparently Dr. Soriano had already spoken to my adviser regarding this, and they both agreed that I should take it. But even if they didn't require me, I'd still do. It's not so often that you get the opportunity to learn new skills that are very useful -- for free!

-------------------------------------------------------------------------------------------------------------------------------------

Image Feature Extraction using the Freeman Vector Code

So now, enough with the introduction. Let's start by discussing first the goal of the activity. The idea is to ease the effort of arranging pairs in performing karyotyping out of an image of a randomly positioned chromosomes. We do this by extracting the shape of a chromosome and rotate them in an upright manner. In the early days, karyotyping is done manually by tracing the shape of the chromosome, cutting it, and pasting it at a desired position. Nowadays, this kind of activity can be done in a more sophisticated manner, by utilizing the power of our computer to do the manual work for us. The basic premise is that, we have to have a developed technique to perform what we want.

Since our topic for this activity is on image feature extraction, we will be using this method to do our goal. Feature extraction is basically the process of transforming a set of data, usually in the form of an image or a signal, into a numerical representation so that it can be used in machine learning [1]. In this work, we are only concerned with the edges of the chromosome. By performing built in simple edge detection in Matlab, I was able to extract the following chromosome.

Figure 1: Raw edge-detected chromosome (unsmoothened)

Notice that the detected edges are not smooth. In order for us to rotate the image, the program has to detect a specific feature in the image to be used as base points. These base points will be used to obtain the angle necessary for rotation. Most of the time, chromosomes are rectangular in shape, so that it consists of four distinct rounded corners. We can use these rounded corners as feature we need to detect. If we attempt to look at the convexity and concavity of these edges, we will be able to detect unnecessary abrupt changes. Thus, we need to perform smoothing. In our first problem set, we utilized the use of Fourier descriptors to translate the contour. We then performed fast Fourier transform (fft) to get the frequencies. By clipping the parts where no useful information is present, we reduced the noise in the signal, thereby producing a smoother contour.

Now to be able to convert the contours (XY-locations) into pattern recognizable numerical values, we use the freeman vector code in translating the white pixel locations into a series of numbers. After obtaining the X and Y locations of these white pixels that are arranged in a clockwise order, we can choose an arbitrary location as a starting point.

(a)                                     (b)

Figure 2. Feature extraction using the freeman vector code. Image taken from J. Ballista's work [2]

From the chosen origin, we scan the eight nearest neighboring sites for another white pixel. Depending on the location of the white pixel, we assign the numerical values as dictated by the pattern in Figure 2b. It is important to note that we have to do this in a clockwise manner, because at any arbitrary location, you will always have two neighboring white pixels. I dedicated quite a number of time in performing this part of the work. I didn't want to use an if-else algorithm, because it takes up too much space in the code. At first, I just used the basic find method in looking for the edge positions. The resulting locations are not arranged clockwise, which is why it was harder for me to implement the algorithm I have planned. When I found out that there is a one-liner built-in Matlab syntax in getting the X and Y values of the edges in a clockwise manner, everything became much easier. I took the difference between two successive x-locations as well as y-locations. From the differences, I was able to easily assign the freeman vector code for each xy-pixel.

Figure 3. Diagram of writing the freeman vector code using successive differences between X-Y points.

In order to obtain the concavity or convexity of the edges. We may then borrow the idea of J.Balista et. al[2] for concavity detection. In their paper, they took the vector gradient of the freeman vector, which is essentially the derivative of the edges. After which, they took the running sum of three consecutive numbers in the gradient for further smoothing. The following figure taken from their paper demonstrates this procedure.

Figure 4. Example of assigning Freeman vector code and getting its vector gradient

In mathematical sense, we are taking the derivative of the contour. Note that for values greater than zero, contour is convex. If it is equal to zero, then it is a line, but if it's less than zero, then it's concave (with respect to the exterior). After several attempts of extracting the corners of my chromosome, I decided to smoothen the contour such that the resulting shape is that of the rod. After all, we are only concerned at the angle of orientation. In doing this, I was sure that majority of the detected convex contour would be at both ends of the chromosome. I then took the distance of each detected points from the centroid, and filtered only those that are far enough. 

Figure 5. Original and processed shape of the chromosome. The line gives the angle with respect to the horizontal. Superimposed red circles give the location of convexity.

Only the observed clustering of points in both ends of the chromosome are detected. I just took the average of these points to obtain the center. Since two points determine a line, I was able to extract the line of orientation as seen in Figure 5. After getting the line, we can now extract the angle needed for rotation. We can do this by just getting the arc tangent of the ratio between two points in the line. Finally, I got the following result.

Figure 6. Original and rotated image of the chromosome

I also tried using my code with another chromosome, and it was successful. I got the following:

Figure 7. Original and rotated image of another chromosome

Although the rotations made in Figures 6 and 7 are not exactly along their axes, I have at least successfully oriented the two vertically.

The only disadvantage of the use of freeman vector code is its limitation with regards to its inapplicability to discontinuous blobs.

[1] Feature extraction. Sci-kit Learn. Retrieved August 17, 2015 from http://scikit-learn.org/stable/modules/feature_extraction.html

[2] H. Freeman (1961) ‘On the encoding of arbitrary geometric configurations’, IRE Trans. on Electronic Computers, 10(2):260-268.

[3] Piper, J., & Granum, E. (1989) ’On fully automatic feature measurement for banded chromosome classification’ Cytometry, 10(3): 242-255.

[4] J. Balista, M. Soriano, C. Saloma (2010) ‘Compact time-independent pattern representation of entire human gait cycle for tracking of gait irregularities’, Pattern Recognition Letters 31(1):20-27.