International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 2510

ISSN 2229-5518

Automatic Waterway Detection Applying K- means Clustering

Mehnaz Tabassum

Abstract— Detection of transportation network from geographical map image is an important task of document analysis and recognition. The extracted segments are applied to different machine vision and embedded system. The task is very complex because of having overlapping objects, intersected lines etc in map. Keeping this in mind, the present thesis paper describes an adaptive method, which has been applied to extract efficient waterway (an important portion of transportation network) that ove overcome the previous limitations. Different from the existent methods, proposed approach is efficient both in segmentation results and further reconstruction. And the experimental results are close to human perceptions; therefore this method provides better and more robust performance than either of the individual methods. We hope this method will find diverse applications in Automatic waterway from geographical map and also image analysis.

Index Terms—image analysis, image segmentation, k-means clustering, L*a*b color space, map, regions of interest, transportation network

1 INTRODUCTION

—————————— ——————————
MAGES are considered as one of the most important medi- um of conveying information. An image can have thousand times better impression than hundreds lines of document. Understanding images and extracting the information from them such that the information can be used for other tasks is an important aspect of Machine learning. An example of ma- chine learning form image can separate road network from image which helps the car to choose optimum path from source to destination. Color image segmentation [1], whose purpose is to decompose an image into meaningful partitions,
is widely applied in multimedia analysis.
A map is a visual representation of an area, a symbolic de-
piction highlighting relationships between elements of that space such as objects, regions, and themes. A city map will include not only the city's transport network, but also other important information, such as city sights or public institu-
tions [14]. The extraction of Region of Interest (ROI) from overlapping objects of city map such as transportation net- work is a challenging problem in color image analysis. The problem is much complex in city map analysis is more com- plex since there are more types of data, various types of lines, possible curvature and even branching of graphics[10][11][12].
Clustering is a feature-space method of Color image seg- mentation. This method classifies pixels to different groups in a predefined color space. K-Means clustering is popular for its
————————————————
• Mehnaz Tabassum is currently doing job as a lecturer in Computer Science and Engineering department at jagan- nath University, Dhaka, Bangladesh PH-01913497661. E- mail: mtabassum2013@gmail.com
simplicity for implementation [16], and it is commonly applied for grouping pixels in images. The choices of color space may have significant influences on the result of image segmenta- tion. There are many kinds of color space [19], including RGB, YCbCr, YUV, HSV, CIE L*a*b*, and CIE L*u*v*. Although RGB, YCbCr, and YUV color spaces are commonly used in raw data and coding standards but they are not close to hu- man perceptions. Unlike the RGB and CMYK color models, Lab color is designed to approximate human vision. It aspires to perceptual uniformity, and its L component closely matches human perception of lightness [15]. It can thus be used to make accurate color balance corrections by modifying output curves in the ‘a’ and ‘b’ components, or to adjust the lightness contrast using the L component.

2 LITERATURE REVIEW

The separation of text from map was done by researchers till date. Fletcher and Kasturi [3] developed an algorithm for text string separation from mixed text/graphics image. Taking account of curving labeled road names in the map, Tan and Ng [4] developed a system using the pyramid to extract text strings. Both methods, however, assume that the text does not touch or overlap with graphics. Touching lines with text is important for engineer drawings [9-11], especially maps [12]. This problem is much more complex since there are more types of data, various types of lines, possible curvature and even branching of the graphics. An approach in [5] introduced an algorithm which permits to extract text on binary images. Then regions may have characters is selected using the maxi- mum connected components. The characters are merged into words using Hough Transform. But, it does not support the overlapping of text and graphics elements of images which is a common problem of topographic maps. In [11], authors de- velop a model to extract black characters in city maps. They use street lines data to recover the characters composing street names. Due to the possible overlapping between street names and street lines describing the street, they develop a specific

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 2511

ISSN 2229-5518

OCR algorithm to produce an efficient text file of street names. More recently, a text/graphic separation method applied to color thematic maps has been described in [10],[9],[15]. The authors describe a segmentation technique based on 24 images obtained by a combination of color components (R,G, B, (R+B)/2, etc.). The resultant binary image constructed from the mix of theses 24 images is then used in an OCR-based recognition system with neural networks.

3 Automatic Waterway Separation Process

Color map contains several overlapping objects with different in color, shape and size. The ROI is focused to the water-way. The process of extraction of transport network deals with max- imum connected waterway detection. This separation process using k-means clustering is depicted in figure 1 which is ex- plained in the following section
video cameras, and on magnetic disk or solid-state memory card by digital cameras. Digital color images can be digitized from film or paper by scanners. After the image has been ob- tained, various methods of processing can be applied to the image to perform the many different vision tasks required today. The images used in this paper are acquired from google map in RGB image format.
c. RGB to L*a*b* Conversion
As next step in the processing, measured RGB values in the
map image are converted to CIE L*a*b*. Here L* describes
lightness; its values can range between 0 (black) to 100 (white).
The other two variables describe the actual color, with a* rep- resenting green (negative values) or red (positive) and b* rep- resenting blue (negative) or yellow (positive values). The con- version of RGB to the L*a*b* system is done via an intermedi-
ate step, by translating RGB values into CIE XYZ values. The standard conversion from RGB to XYZ values, which was used shipboard, uses the following equation [16]:

X

(X R .CR ) (X G .CG ) (X B .CB )

R

  

  

Y  =  (YR .CR ) (YG .CG ) (YB .CB )  ⋅ G

(1)

 Z 

 (Z R .CR ) (ZG .CG ) (Z B .CB )

 B 

Where X, Y, Z are the CIE tri-stimulus values of a color. R, G, B are the red, green, and blue channels of a color as measured in the image. XR, YR, ZR, and so on are the chromacities of the RGB primaries of the camera; and for R, G, and B.

C = tristimulus

value of

unit

amount of

camera

primary

chromacity of

the

primary

However, for computational purposes, the terms (XR · CR), (YR · CR), (ZR · CR), and so on are taken together as a single unknown constant each, giving

X

X ' '

X '

R

Y  =  Y ' Y '

Y '  ⋅ G

   R G

B   

(2)

 Z   ' Z

'   B 

Figure- 1: Waterway Detection Process
This standard conversion implies that the lines calculated for X, Y, and Z intersect the origin of the axes i.e., that pure black has values equal to, or very close to (0,0,0) in both the XYZ and RGB vector space.

X

a1

X ' '

X '

R

a. Data Resources and Software used

Y  = a  +  Y ' Y '

Y '  ⋅ G

(3)
For this research purpose we used K-Means Clustering Tech-

   2   R G

B   

nique for color based Image segmentation. The images are of parts of different regions of Bangladesh. The entire work is

 Z 

a3   ZG

'   B 

carried out using MatLab R2010a, Adobe Photoshop 7.0 and
MS-Office.
b. Image Acquisition
The first stage of any vision system is the image acquisition stage. Color images of scenes and objects can be captured on photographic film by conventional cameras, on video tape by
In this case, information about four colors is needed to solve the constants (i.e. the red, green, blue, and gray chips). Writing out the matrix multiplication and rearranging the sets of linear equations yields the following for the X-values of the four col- or chips used:

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 2512

ISSN 2229-5518

X r  l Rr Gr

Br

a1

  

X g  = l Rg Gg

B   X

g  ⋅  R

objects into three clusters and pixel values distance is meas-
ured [18] by the Euclidean distance metric.

X b  l Rb Gb

  

Bb

X G

 

e. Connected component labeling of Image

 X gr 

l

Rgr

Ggr

Bgr 

X B

(4)
Connected component labeling is used in computer vision to detect connected regions in binary digital images, although
Here, Rr, Gr, and Br, and Xr, Yr, and Zr are the measured channels and the known XYZ values respectively for the red chip; subscripts g = green, b = blue, and gr = gray apply to the other three color chips used. Typically, values for the con- stants a1, a2, and a3 are found to range between 1.5 and 4.5, demonstrating that an offset from the origin of the X, Y, and Z axes is indeed present.
The XYZ values estimated for the data in the line scan are then further converted to CIE L*a*b* values using the following equations [16]:
color images and data with higher-dimensionality can also be processed.[22][20][2] When integrated into an image recogni- tion system or human-computer interaction interface, connect- ed component labeling can operate on a variety of infor- mation.[2][3] Blob extraction is generally performed on the resulting binary image from a thresholding step. Blobs may be counted, filtered, and tracked. We have used this technique to filter pixel value based thresholding for separate connected components from K-Means clustered imaging output. 8- connected component algorithm is applied to label connected
  Y
16 

L= 116 f   −


 (5)
neighbor.
  Yn
116 

  X

Y 

f. Process of Waterway

a= 500 f


 − f  

(6)
After getting the segmented image several de-noising and re-

  X n

  Y

Yn 

Z 

construction techniques [8] are applied for identifying water- way from the map. In map water portions are colored with blue color. Smaller sized water colored for pond, small lake,

b= 200 f


 − f  

(7)
ditch etc. are removed. Then labeling is applied to detect the

  Yn

Z n 

boundary of waterway.
with f(Y/Yn) = (Y/Yn)1/3 for Y/Yn > 0.008856 and f(Y/Yn) =
7.787(Y/Yn) + 16/116 for Y/Yn ≤ 0.008856; f(X/Xn) and
f(Z/Zn) are defined similarly. Xn, Yn, and Zn are the tristimu-
lus values of a reference white. For this study, the known XYZ
values of the white color chip are used as reference values.
d. K-Means clustering in L*a*b Color Space
Clustering is a way to separate groups of objects. K-means
clustering treats each object as having a location in space [15].
It finds partitions such that objects within each cluster are as close to each other as possible, and as far from objects in other clusters as possible.
The K-means algorithm [17] is an iterative technique that is used to partition an image into K clusters. The basic algorithm is:
• Pick K cluster centers, either randomly or based on some heuristic
• Assign each pixel in the image to the cluster that min- imizes the distance between the pixel and the cluster center.
• Re-compute the cluster centers by averaging all of the pixels in the cluster
• Repeat steps 2 and 3 until convergence is attained
(e.g. no pixels change clusters)
In this case, distance is the squared or absolute difference be- tween a pixel and a cluster center. The difference is typically based on pixel color, intensity, texture, and location, or a weighted combination of these factors [18]. Here the color in- formation exists in the ‘a*b*’ space. ROI objects are pixels with
‘a*’ and ‘b*’ values. The process used K-means to cluster the
g. De-Noising:
For removal noise from the waterway, we have applied color
based thresholding [8]. Then image is converted into binary
image. This binary image is then feed for reconstruction the
missing water portion.
h. Reconstruction of Waterway:
Because of removal of overlapping objects, text and line seg-
ments, some portions of waterway disappeared. We have ap-
plied structuring elements to reconstruct [12] the missing por- tion of the waterway.
i. Maximum connected waterway Identification:
After removal of noise and reconstruction, we have applied
bounded area labeling and identified the largest connected
water area from the image.

5 RESULTS AND DISCUSSIONS

At first RGB map image is converted to L*a*b color space. Then color based K-Means clustering algorithm is applied into map image to segment different colored portions from map image. After that road and waterway is separated into differ- ent segment.While processing, the approaches was to de- noising by color-based threshold and removal of small sized objects as treated as noise. The segmented and noise removed image converted into binary for blob analysis for reconstruct. Different types of structuring elements are applied for recon- struct the waterway as a part of transportation network. Final- ly get the bounded waterway, which is close to human percep- tions.
The input and output images are shown below as order as

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 2513

ISSN 2229-5518

workflow. The input images we trial, are shown below:


Image 1 Image 2
After K-Means clustering in L*a*b Color Space

Original Map Colorspace 1


Colorspace 2 Colorspace 3



Figure 2 : K-Means Output of Map Image 1
After Processing of Waterway we get the following output:

Original Map Colorspace 1


Colorspace 2 The Boundaries of Waterway



Figure 3: Sepaterated Waterway after processing of
Map Image 1
After K-Means clustering in L*a*b Color Space

Original Map Colorspace 1


Colorspace 2 Colorspace 3



Figure 4: K-means Output of Map Image 2
After Processing of Waterway we get the following output:

Original Map Colorspace 1


Colorspace 2 The Boundaries of Waterway



Figure 5: Separated Waterway after Processing of
Map Image 2
We know that, Extraction of Region of Interest from geograph- ical map image is very complex because of having overlapping objects, intersected lines etc in map. Here our Regions of inter- est is the main waterway, which is a unique work done so far.
Here the achievement is the separation of waterway from a map image with overlapping object, text and color. But map to map it may vary. At the outset, we research on various map images to get idea about the extraction process. Always try to find the answers of the question; what will be the best process for which types of map, how could get the closest outcome to

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 2514

ISSN 2229-5518

our projected ROI i.e. the main waterway. In this way, finally we selected the map images from google map and from gov- ernment site of Bangladesh, which are of parts of different areas of Bangladesh, and applied K-means clustering for seg- mentation which is appropriate for that map and general tem- plate matching technique to check the performances of those two methods. Finally, we get the end result that is close to human observation.

6 SUMMARIES

Extraction of Region of Interest from geographical map im- age is an important task of document analysis and recognition. The extracted segments are applied to different machine vi- sion and embedded system. The task is very complex because of having overlapping objects, intersected lines etc in map. Segmentation based on a single feature such as color, Shape or object often lacks adequate discriminatory information and so is unable to obtain accurate result. In this work, the method have been applied to extract efficient waterway region from geographical maps is color based segmentation applying K- means clustering awhich overcome the previous limitations. Different from the existent methods, this proposed approach is efficient both in segmentation results and further reconstruc- tion also. And our experimental results are close to human perceptions; therefore our methods provide better and more robust performance than either of the individual methods. We hope these methods will find diverse applications in ROI ex- traction from geographical map and also image analysis.

7 LIMITATIONS AND FUTURE WORKS

Performance of efficient Regions extraction from maps de- pends and varies for map to map. Color based K-means clus- tering is not applicable when there are less color variations. The map images we exercise here give satisfactory results for waterway by this technique.
For future developments, this output can be converted into graphs which can be processed by embedded system in to drive vehicle and vessel automatically from source to destina- tion and follow optimum path. More works need for extrac- tion of rail network, roads and narrow waterways. If cluster- ing of different maps on the basis of scale can be implemented, then accurate extraction of the whole transportation network will be founded.

REFERENCES

[1] L. Lucchese and S. Mitray, “Color image segmentation: A state-of-the art survey,” in Proceedings of the Indian National Science Acade- my,Mar. 2001, pp. 207–221, (Invited Paper)

[2] G. Nagy, “Twenty years of document image analysis in PAMI”, IEEE

Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 1, pp. 38 - 62, January 2000

[3] D. S. Doermann, “An introduction to vectorization and segmenta- tion, in Graphics Recognition: Algorithms and Systems”, K. Tombre

and A. K. Chhabra (eds.), Lecture Notes in Computer Science 1389, Springer, pp. 1 – 8, 1998

[4] L. A. Fletcher and R. Kasturi, “A robust algorithm for text string

separation from mixed text/graphics images”, IEEE Transactions on

Pattern Analysis and Machine Intelligence, Vol. 10, No. 6, pp. 910 -

918, November 1988

[5] C. L. Tan and P. O. Ng, “Text extraction using pyramid, Pattern

recognition”, Vol. 31, No. 1, pp. 63 – 72, 1998

[6] D. Wang and S. N. Srihari, “Analysis of form images, in Document Image Analysis”, H. Bunke, P. S. P. Wang, H. Baird (eds.), World Sci- entific, pp. 1031 – 1051, 1994

[7] S. Naoi, Y. Hotta, M. Yabuki, and A. Asakawa, “Global interpolation

in the segmentation of handwritten characters overlapping a border”, Proceeding of 1st IEEE International Conference on Image Pro- cessing, pp. 149 – 153, 1994

[8] J. Yoo, M. Kim, S. Y. Han, and Y. Kwon, “Line removal and restora- tion of handwritten characters on the form documents”, Proceeding of 4th International Conference on Document Analysis and Recogni- tion, pp. 128 - 131, 1997

[9] K. Lee, H. Byun, and Y. Lee, “Robust reconstruction of damaged

character images on the form documents. In Graphics Recognition: Algorithms and Systems”, K. Tombre and A. K. Chhabra (eds.), Lec- ture Notes in Computer Science 1389, Springer, pp. 149 – 162, 1998

[10] R. Kasturi, S. T. Bow, W. El-Masri, J. Shah, J. R. Gattiker, and U. B.

Mokate, “A system for interpretation of line drawings, IEEE Transac- tions on Pattern Analysis and Machine Intelligence”, Vol. 12, No. 10, pp. 978 - 992, October 1990

[11] D. Dori and Liu W., “Vector-based segmentation of text connected to graphics in engineering drawings, in Advances in Structural and Syntactical Pattern Recognition”, P. Perner, P. Wang, A. Rosenfeld (eds.), Springer, pp. 322 – 331, 1996

[12] Z. Lu, “Detection of text regions from digital engineering drawings”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.

20, No. 4, pp. 431 - 439, April 1998

[13] Ruini Cao , Chew Lim Tan, “Text/Graphics Separation in Maps”, Selected Papers from the Fourth International Workshop on Graphics Recognition Algorithms and Applications, p.167-177, September 07-

08, 2001

[14] Amândio Cordeiro , Pedro Pina, “COLOUR MAP OBJECT SEPARA-

TION”, Mid-Term Symposium of the new ISPRS Technical Commis- sion 7, on “Thematic Processing, Modelling and Analysis of Remote- ly Sensed Data”

[15] Samma, Ali Salem Bin; Salam, Rosalina Abdul, “Adaptation of K-

Means Algorithm for Image Segmentation”, International Journal of

Signal Processing, October 1, 2009

[16] MacQueen, J. B. (1967). "Some Methods for classification and Analy-

sis of Multivariate Observations". 1. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. pp. 281–297. MR0214227. Zbl 0214.46201.

[17] Vattani, A. (2009). "k-means requires exponentially many iterations

even in the plane". Proceedings of the 25th Symposium on Computa- tional Geometry (SoCG).

[18] H. Samet and M. Tamminen (1988). "Efficient Component Labeling of

Images of Arbitrary Dimension Represented by Linear Bintrees". IEEE Transactions on Pattern Analysis and Machine Intelligence (TI- EEE Trans. Pattern Anal. Mach. Intell.) 10: 579.

[19] Michael B. Dillencourt and Hannan Samet and Markku Tamminen

(1992). "A general approach to connected-component labeling for ar- bitrary image representations”

[20] Cabo, and T.B. Pedersen, "Integrating Data Warehouses with Web

Data: A Survey," IEEE Trans. Knowledge and Data Eng., preprint, 21

Dec. 2007, doi:10.1109/TKDE.2007.190746.(PrePrint)

IJSER © 2013 http://www.ijser.org