Hybrid Trademark Retrieval Using Boundary and Region

Hybrid Trademark Retrieval Using Boundary and Region

AnubhootiPapola*1,Sanjay Papola2

Dept. Computer Science and Engineering 1.SelaQui Institute Of Engineering & Technology, India,

2. Uttaranchal Institute of Technology, India

ABSTRACT

Trademark is the most disputed item and its infringement is one of the biggest issues in Intellectual Property Rights. Therefore, to grant a new trademark or to prevent infringement of trademark a search is carried out to investigate if the new trademark applied for matches with an already issued trademark. Considering the fact that the trademark database is very huge and keeps on increasing constantly, the manual search is definitely not a correct solution; an Information Communication and Technology (ICT) based system is required to automate this process. Shape is easily the most important feature for the trademark image. Content based image retrieval

i.e. CBIR systems are developed to find similarity between image by using the content of image like color, shape in an image. There are several algorithms related to shape extraction that have been used in past in other applications. So for extracting similar trademarks in a system it is better to develop some dedicated algorithms that produce good results in other application rather than to invent some new algorithm for shape extraction. In this work a new approach is proposed for extracting similar shapes in trademark database. Retrieval Efficiency can be improved as both boundary and region features of shape are considered and their weighted combination is used in this work.

1. Introduction

   Intellectual Property Rights (IPR) is a field where some issues are very complex to solve. Among those issues, TRADEMARK infringement is very hard and challenging task. A trademark is a distinct sign used as an intellectual property by any individual, business organization or any other judicial entity. It can be an image, a logo, symbol, design, word, phrase or a combination of these. Trademark is basically used to distinguish one business organization from other and thereby distinguish their products or services from others as well. Two trademark images can be conflicting not only if they are geometrically similar in a side by side comparison but also if they are visually similar in appearance. A trademark image can be suspected to cause infringement if it is similar to an already registered trademark image sufficient enough to

   arouse confusion. Similarity can be judged in numerous ways but the intention of a trademark retrieval system is to prevent trademark infringement. Various techniques have been used for extracting information from image out of which one is CBIR which takes out content of image as feature. Trademark images are submitted in binary form. But now a days color trademarks are also submitted for validation. Therefore, Color trademarks are used as a color image so when we are applying CBIR( Content based retrieval) techniques on any color image, its content can be represented in the form of color, texture, shape and some other features. All the features are important in getting the content of an image. But, literature survey shows that fact Shape feature is a feature which dominates on other features in retrieving trademarks. It is because in trademark generally consists of less objects as compared to other

   normal color images which makes shape feature dominating. Thats why in this project only shape feature is taken into account for matching or comparing the features of trademark images to get trademarks that are similar by content. There exist two problems when image is described using shape

   • technology of trademark retrieval based- on shape features and spatial distribution

   • Problem of invariance of features. When features are extracted of an image the features should be translation, rotation, scale invariant and start point issue must be solved.

2. Proposed Approach

As discussed earlier that boundary techniques of shape are not responsive to any local changes in shape which makes computation easy but region based methods have high computation due to its responsiveness towards local changes. Hence in this thesis it is proposed that if for extracting the shape feature both methods are used i.e. boundary and region based methods. A flexible combination of weights are used to combine both boundary and region features which can lead to better retrieval results in comparison to using only boundary or region based method alone.

From this a conclusion is derived that Fourier Descriptors is a good technique for comparing boundary features and Zernike Moment for Region features of an image. Hence lets see these two techniques in detail:

2.1 Fourier Descriptors:

It is a popular method for describing shape or contour parameterization.

It brings the power of Fourier theory in the field of shape description. The basic idea of fourier descriptors is to apply the discrete Fourier transform on the signature of a shape and obtaining the Fourier coefficients which will describe the boundary of a shape. The main reason behind the application of discrete Fourier transform in shape description is to represent the boundary points of a shape in frequency domain by a set of numbers that corresponds to the frequency content of whole shape. When a shape is analyzed in frequency domain with the help of some set of numbers generally the set is kept to be small to avoid the description of noise means a small set of numbers describe the shape more accurately as it prevents description of noise that affect spatial position of boundary pixels.

In general, the boundary points are x and y coordinates. Fourier descriptors obtained from these points by applying DFT will give spatial frequencies of these boundary points. The first descriptor called d.c. component is simply the average of all points which gives the centre in complex form. The second element or first harmonic is the radius of circle that best covers boundary points. Higher order components describe the finer details of shape. the ellipse and its fourier components can be seen in below diagram which shows that low order components have more influence.

Figure3.1. Boundary of an Ellipse

Figure3.2. Fourier components of Ellipse of figure3.1

The fourier descriptors of shape can be calculated mainly in two steps. In First Step, first the signature of a shape is computed for representation of shape. In second step fourier transform is applied on signature values to obtain the fourier coefficients. But first of all we need boundary points on which shape signature is computed .For this some preprocessing is required.

1. Preprocessing

   The preprocessing involves following steps:

   1. Convert the image into binary: First of all image is converted into its binary form by applying im2bw function of Matlab which uses a threshold of .5 for conversion.

      Find the objects and their boundaries: when we get a binary image, we extract the boundaries of different objects present in the image. In this process, some noise also occurred in the form of objects. So those objects are eliminated by checking their boundary length. If the boundary length of an object is lesser than the average length of all objects boundary length then that object is treated as noise and will be discarded from the computation.

      Figure3.3. Flow chart of Preprocessing before Fourier Descriptors

      After preprocessing, the fourier descriptors are computed for each relevant object of an image. As sated earlier, fourier descriptors are computed on shape signature values. Therefore, first we have to compute the shape signature and there are various shape signatures which can be considered for computing fourier descriptors.

2. Shape Signature

   The output of preprocessing step is the boundary coordinates of shapes which are two dimensional. But if we have that information in one dimensional then it is easy to compare shapes. So we need a function which converts the two dimensional information into one dimensional and that function is called as shape signature. It represent 2D boundaries in 1 dimension. There exists various shape signatures but the most commonly used are Complex Coordinates, Curvature Function, Centroid Distance Function. All of these are explained in brief below:

   Complex Coordinates: this is very simple function for converting into 1D by representing boundary points in complex form.

   S(a) = x(a) + iy(a);

   To make this translation invariant, we can shift coordinates:

   S(a) = (x(a) x1) + ( y(a) y1);

   Where (x1,y1) are the centroid of coordinates of boundary.

   Centroid Distance Function : In this a distance function is derived which is computed as distance of boundary points from centroid of shape. this is very easy and effective as compared to other signature function. Therefore, in this project we are using this function for calculating the shape of signature and hence will help in computing the fourier descriptors of shape.

   D( a) = ( ( 1)2 + ( 1)2 )1 2

   As the centroid is subtracted here also, so it is also invariant to translation.

   Curvature : It is an important boundary feature in which the second derivative of boundary and tangent boundary first derivative has been taken.The function of curvature is

   K(s) = 1 ;

   In this function, successive boundary angles are differentiated in window w and

   = ( )

   ()

   Cumulative Angular function As boundary angles can also represent shapes but the tangent function

   take values in range 0-2.this arose some discontinuity of size 2. Hence, to overcome this problem cumulative angular function is defined which computes the angular bend between the current position and starting position i.e.

   = [ 0 ] mod 2

   After normalization of this function in accordance with human perception that a circle is shapeless, it becomes

   =

   2

   Here L denotes total boundary points.

   Based on the previous work done in this field means in extracting shape boundary feature we derive a conclusion that centroid distance function is better and more effective than other shape signature techniques. It can be easily seen in the figure below:

   Where

   Figure3.4. Precision and recall of Existing System during different shape signatures

   As above figure shows that precision and recall values are much better in centroid distance than any other signature function. The reason behind more effectiveness of central distance is that it is completely derived from boundary coordinates and it has some region information also due to which it captures both local and global information of shape. Therefore it is not wrong to say that central distance is a shape representation technique which lies between boundary based technique and region based technique. However, complex coordinates and cumulative angular function capture only information that consists of local features only. Thats why they are not as robust as centroid distance function. When human perception is considered, the curvature function is a good feature but if shape is represented using only local information then it does not provide so much information about shape or we can say it is

   meaningless to describe a shape by local features only. Also in this second derivates of a boundary are calculated which is unreliable.Therefore in this project, centroid distance function is used as a shape signature which is used in computing the fourier descriptors.

3. Computation of Fourier Descriptors

Now we get the input on which we compute the fourier descriptors. So, for calculating FD fourier transform is applied on shape signature values obtained using centroid distance function.

So using Eq.

Figure 3.5. Flow Chart of showing the process of fourierdescriptors computation

1. Zernike Moment

   Zernike moments [13] are defined as complex number moment over a unit circle which takes a set or group of polynomials that are complex and orthogonal in nature.

   It is first inferred by Teague to overcome the problem of information redundancy that came in popular geometric moments discussed in chapter2. Zernike Moment is calculated as:

   = , [ , ] dxdy

   where m = 0,1.. , f(x,y) is current pixel of

   image and * is hetero conjugation or complex conjugate and m, n are both integers satisfying m –

   =0

   =0

   = 1 1 ()

   2

   ,d = 0,1,2N-1

   |n| is even and |n| .

   (, )are radial orthogonal polynomials

   Now the fourier descriptors obtained using central distance have rotation and translation invariant. Thus only scale invariance has to be achieved. For this magnitude of all the descriptors are divided by

   the magnitude of the first descriptor i.e.

   This integral is computed over unit circle i.e.

   2 + 2 1

   = () and – (2)

   = 2

   1 1

   1 !

   21 – (3)

   1=0

   1! + 1 ! 1 !

   |1 | , |2 |, |3 |.|1 | 2 2

   |0|

   |0|

   |0|

   |0|

   But our domain is image processing and as we are

   These are called Normalized Fourier Descriptors.

   The flow chart below lists all the steps that are used in computing the FD.

   working on digital images so for digital images we require formula of Zernike Moment which can be obtained by replacing integrals with summation. Hence, Eq. 1 becomes

   = +1 (, ) [ , ]

   (4)

   Above formulas are used to compute the Zernike moment of an object. Now, how these formulas are used for computing Zernike Moment is listed below in a stepwise manner:

   1. All the database images and query image is normalized to size 256×256

   2. Secondly, the radial orthogonal polynomials are computed using Eq. 3.

   3. In 3rd step, Zernike basis function are

      computed using Eq. 2

   4. Then Zernike moment of image is computed using Zernike basis function by using formula in Eq. 4

      For calculation of Zernike moments of an image, what is done first, an image or interested region of an image has taken or identified, then we map that region to the origin of unit circle in polar coordinate system. In calculation, the pixels internal to unit circle are considered. Rest of the pixels is excluded. From origin to each boundary coordinate point, a vector K is drawn whose length will describe the coordinates. is the angle which is measured from x-axis to vector K is given as:

      = tan1 , where x = Kcos , y = Ksin

      Below there are some points [16] that assure why Zernike Moment is chosen for this project:

      1. Rotation Invariant: the magnitude of Zernike moments i.e. | | are rotational invariant. This property is achieved due to mapping of image to unit circle. Change in phase express the rotation of shape and if

      is angle of rotation, Zernike moment of

      original and rotated image is given by

      and respectively, then

      Zernike moment due to its orthogonal nature gives unique contribution and independent of information with other moments.

      1. Robustness: Zernike moments are robust to noise and minor variations in shape are identified in high order moments.

      2. Effectivenes: when image description is done using moments, Out of Zernike Moments and other moments like geometric moments, Zernike has better retrieval efficiency i.e. Zernike moment describe an image better than any other moment.

      3. Ease in Reconstruction: Reconstruction of an image from Zernike moments of an image is easy.

      4. Multi-Level Representation: An important advantage or feature of Zernike polynomial is that Global features of shape are represented by Lower order Zernike Polynomials and Local features of shape are given by higher order polynomials i.e. image is represented at different level.

      Before Calculating Zernike Moments, image is normalized using Cartesian Moments which will help in achieving invariance in scale and translation.

      =

      | | = | | = | |

      1. Expressiveness in Information: As told earlier Zernike basis function are orthogonal and due to this orthogonal nature the problem of information redundancy is solved. Each moment has some information but in geometric moments information is overlapped with different orders and repetition but each

         Figure3.6. Flow Chart showing the computation of Zernike Moments

2. Feature Matching

   Feature matching in case of Image retrieval measures to what degree the two images are similar. This is called feature matching because in this we match the feature vectors obtained by feature extraction method. Feaure vectors can be matched in different ways but the method we are using in this project is based on distance.

   There exists various distance measures such as Euclidean distance,mahalanobis, and manhattanetc.Each distance measure has its own importance but the Euclidean distance measure is easy in computation and produce good results.

   Suppose A is a query image and B is one of database image and if their feature vectors are and and they are given as

   = { 1, 2 ,..}

   = { 1 , 2 ,.. }

   D= || – || = 1( )2

   =

   =

   If feature vector consists of complex numbers then the Euclidean distance between two complex numbers lets say a + ib and c+ id is:

   = ( )2 + ( )2

   By using Euclidean distance, the Zernike moments values and fourier descriptors obtained for query image and for database images are compared to get the similar images based on shape.

3. Combining the Features

   Getting the retrieval result using only single feature may produce inefficient result. It may either retrieve images not similar to query image or may fail to retrieve images similar to query image. Hence to produce efficient results, we used

   combination of several features instead of using single feature.

   Therefore, boundary features and features obtained in terms of moments after applying Zernike moment function are combined to get better retrieval

   As each feature has its different value so they are combined using variable weights using the following formula:

   S = . + .

   +

   and are the contribution factors assigned to distance values for Fourier Descriptors and for Zernike moment respectively.

4. Implementation Details

   Before this section, a lot of study has been done on trademark and its infringement problem. Various techniques are also discussed to solve this problem using CBIR techniques. After literature survey an idea is proposed to get better results. Now in this section all the processes with all intermediate steps or process is shown through a flowchart or flow diagram. The flow chart on next page reveal out all the steps that has to follow sequentially and at each step, the process followed or technique used is written which is explained earlier in detail in this chapter.

   query image in the trademark dataset .If suppose the query image should fall in the Pth class then all trademark images in the Pth class are relevant images in database, (let be that number) which helps in calculating the recall of a system i.e.

   Recall = , -> no. of relevant images

   retrieved.

   For Precision = , is no. of retrieved images

   	Fourier descriptors	Zernike Moment
   Precision	55.6	63.3
   Recall	66.3	67.2

   	Fourier descriptors	Zernike Moment
   Precision	55.6	63.3
   Recall	66.3	67.2

   which is fixed to 15. Table 1 below shows the recall and precision values obtained by taking each feature alone at a time.

5. DATASET

The database consists of uncompressed images in BMP format. All the images are uniform in size. The dimension of each image is 256*256. All the images are kept at uniform size so that no diversion due to different sizes occurs in the result. All the trademarks are obtained from Trademarks Journal available on IP India from class 16 and class 38 only. The database is available at website of IP India i.e. http://ipindia.nic.in/tmr_new/default.htm

1. RESULT AND DISCUSSIONS

   Result of this project depends on the efficiency of the system developed in this work. Efficiency of system can be measured by Precision and Recall.

   Each image in database belongs to some class. therefore, images fall in same class are treated as similar images. After this process, when user presents the query image our system first finds in which class the query image belongs to and then calculates total number of pertinent images to that

   Table 4.1 Recall and precision in percentage by taking each feature alone at a time.

   The conclusion we derive from table1 is that the retrieval precision based on Fourier descriptors is greater than Zernike Moment. Therefore when these two features are combined using Eq. 12 weight assigned to Fourier Descriptors feature values should be more than the feature values of Zernike Moment to get better result. The recall and precision obtained using this weighted combination is shown below:

   	Proposed method
   Precision	64.2
   Recall	66.7

   Table4.1 Recall and precision values of the suggested system improving computational efficiency

   As we can compare from table 1 and 2 that for proposed or hybrid method both precision and recall is increased significantly.

   SNAPSHOTS of GUI and Results

   Figure4.1. Snapshot of GUI in which query image is presented to system

   Figure4.2. Snapshot of GUI showing the similar retrieved images corresponding to query image.

2. CONCLUSIONS AND FUTURE WORK

   1. Conclusion

      In this thesis, issue of granting a new trademark and prevention of its infringement is analyzed using CBIR techniques. In this shape of query trademark is matched with database images to retrieve similar trademarks in database with respect to query image. A hybrid approach is used in this thesis which combined the boundary features and region features of shape instead of finding similarity using either boundary or region feature

      only. Up to now the systems developed for trademark retrieval are developed either using boundary or region feature. The result obtained using hybrid approach shows a significant increase in precision and recall of system means better retrieval results are obtained. The techniques used in this thesis for boundary extraction and region extraction of shape are Fourier Descriptors and Zernike Moment Technology which gives better results than other shape techniques in their domain.

      So, concluion derived from this work is that when two good techniques of boundary and region features are used in combined manner to retrieve similar trademarks then the results obtained using hybrid approach is better than the results obtained using single feature.

   2. Future Work

In future we can also use color, texture and spatial information with the techniques used in this work. The reason of not using these features in this thesis is that time complexity of Zernike Moment is very high. If it is possible to reduce the time complexity of Zernike Moment then retrieval results can be improved using other features like color of an image.

REFERENCES

1. T. Kato, Database architecture for content- based image retrieval, Proceedings of SPIE ImageStorage and Retrieval Systems, vol. 1662, pp. 112-123, 1992.

2. J.K. Wu, C.P. Lam, B.M. Mehtre, Y.J. Gao, and A. Narasimhalu, Content-based retrieval for trademark registration, Multimedia Tools Application, vol. 3, no. 3, pp. 245-267, 1996.

3. J. P. Eakins, M.E. Graham, and J.M. Boardman, Evaluation of a trademark image retrieval system, Information Retrieval Research, the 19th Annual BCS-IRSG Colloquium on IRResearch, 1997

4. Jain, A.K., &Vailaya, A. Shape-based retrieval: a case study with trademark image databases. Pattern Recognition, 31(9) 1369- 1390, 1998.

5. Kim, Y.S., & Kim, W.Y. Content-based trademark retrieval system using a visually salient feature Image and VisionComputing, 16, 931-939, 1998.

6. Ravela, S., &Manmatha, R. Multi-modal retrieval of trademark images using global similarity. Internal Report,University of Massachusetts at Amherst, 1999

7. A. Cerri, M. Ferri and D. Giorgi, Retrieval of trademark images by means of size functions, Graphical Models, vol. 68, no. 5-6, pp. 451- 471, 2006.

8. M. Hussain and J.P. Eakins, Component- based visual clustering using the self- organizing map, Neural Networks, vol. 20, no. 2, pp. 260-273, 2007.

9. Alwis, S. and Austin, J. Trademark image retrieval using multiple features. Presented at CIR-99: The Challenge ofImage Retrieval,

   Newcastle-upon-Tyne, U.K., Feb. 1999

10. Leung, W.H. & Chen, T. Trademark retrieval using contour skeleton classification. Proc. IEEE Intl. Conf. on Multimed. and Expo (ICME 2002), Lausanne, Switzerland, Aug. 2002.

11. E.G.M. Petrakis, K. Kontis, and E. Voutsakis, Relevance feedback methods for logo and trademark image retrieval on the

    Web, Proceedings of the 2006 ACM Symposium on AppliedComputing, pp. 1084-1088, 2006.

12. M.H. Hung, C.H. Hsieh, and C.-M. Kuo, Similarity retrieval of shape images based on database classification,Journal of Visual Communication & Image Representation, vol. 17, no. 5, 970- 985, 2006

13. W.-Y. Kim and Y.-S. Kim, A region-based shape descriptor using Zernike moments,Signal

    Processing: Image Communication, vol. 16, no. 1-2, pp. 95-102, 2000

14. ThawarArif, ZyadShaaban, LalaKrekor, Sami Baba, Object classification via geometrical, Zernike and Legendre Moments, Journal of Theoretical and Applied Information Technology, Vol. 7 No.1 (pp 031 037).

15. Lei Li, Dongsheng Wang, Guohua Cui Trademark Image Retrieval using Region Zernike Moments Second International Symposium on Intelligent Information Technology Application( IEEE 2008).

16. Ye Bin, PengJia-xiong Improvement and Invariance Analysis of Zernike Moments using as a Region based Shape Descriptor

17. .M. Flickner et al "Query by image and video content" IEEE Computer 28(9), 23-32, Sep 1995

18. Mr. Kondekar V. H., Mr. Kolkure

    V. S., Prof.Kore S.N Image Retrieval Techniques based on Image Features: A State of Art approach for CBIR, (IJCSIS) International Journal of Computer Science and Information Security, Vol. 7, No. 1, 2010.

19. Ranjeet Kumar, R.C.Tripathi, M.D. Tiwari A Comprehensive study on Content Based Trademark Retrieval System International Journal of Computer Applications (0975 8887) Volume 13 No.6, January 2011