Dual Transition Uniform Lbp Matrix for Efficient Image Retrieval

Published Online July 2015 in MECS DOI: 10.5815/ijigsp.2015.08.06

There are many general-purpose image retrieval systems are proposed in the literature [1]. One of the popular among these retrieval systems is content-based image retrieval (CBIR). CBIR critically and accurately assist users in finding visually related images with in huge collection of images.In a typical CBIR approach, a user submits an image based query and that can be used by the application to extract visual features from image. The visual features may include by a set of quantitative features, extracted from regions of interest (ROIs) of the image like shape, color, texture and local features depending upon the type of image retrieval system being used. These features are used in order to search and retrieve similar images from image database. The CBIR system finds an appropriate distance between the query image and feature data set to find the best matches in the corresponding feature space [2]. By this the image retrieval system displays images which are having closest similarity that can be used by application. Therefore the main motive behind CBIR is, to search for similar images directly on their visual content. In addition, the performance of CBIR systems is often constrained by the low-level properties of these features because they cannot effectively model the user’s high-level expectations [3]. This is referred in the literature as the ‘‘semantic gap’’ problem.

Plenty of literature is available showing problems related to text-based query, for example, search experience and domain expertise can affect the content based image retrieval (CBIR) performance [4, 5]. In the similar way an ill-defined problems or queries can produce poor results. The previous works on CBIR are suffering with many contextual factors like interaction time [6], user’s subjective perception of relevance [7, 8] and environmental settings [9, 10]. Even today many researchers are working on approaches based on CBIR and it still under investigation. The knowledge of how relevant the particular piece of information (document or image) is to the user and how its content can be reused in order to find documents or images that are similar [11]. Documents or images that are similar to the relevant content have a very high probability of relevance [12]. To address the various problems of image retrieval based on CBIR various researchers proposed a variety of algorithms. Most of these approaches ignored the existence of others [13-19]. Methods based on one specific algorithm (e.g., color, texture or shape) can work effectively only on specific types of images. Local binary pattern (LBP) [27] is very useful and popular approaches recently found for CBIR, because it describes the local contents and attributes significantly which is a very useful tool. The features derived based on LBP are used by many researchers in wide spread of applications like texture classification, face recognition, facial expression recognition, age classification, medical image processing etc. [20-26]. The present paper reduces overall dimensionality of LBP and thus reduced the complexity and derived dual transition uniform LBP matrix (DULBPM) for efficient image retrieval.

The rest of the paper is organized as follows. Section II delivers about related work and section III delivers the proposed approach. Section IV presents results achieved by applying the proposed approach on different texture images. Section V concludes the paper.

• II.    Related Work

  The proposed Dual matrix is derived from the basic LBP operators. The Local Binary Pattern (LBP) was introduced by Ojala et al [27] in 1996. LBP is simple, computationally efficient, robust, and derives local attributes efficiently. With these features, many researchers started working with LBP in various domains and especially in face recognition [1, 31, 32, 39]. The LBP is a powerful tool to describe the local attributes of a texture. In the LBP the grey level image is converted into binary by taking the central pixel value as a threshold and this grey level value is compared with its neighborhood values. The resulting binary valued image is treated as a local descriptor. The basic LBP was initially derived on a 3*3 neighborhood. This LBP operator can also be represented with different variation of (P, R) where P represents the number of neighborhood pixels and R is the Radius. By this the basic LBP operator is represented as (8,1). The 8-bit binary representation or 8-neighboring pixels on a 3*3 neighborhood or (8, 1) derives a LBP code that ranges from 0 to 255.

The LBP operator takes the following form as given in equation 1.

LBP ₍₈,у = Z^„2" S(P_C- P)      (1)

Where ‘n’ runs over the central pixel C, P_cand P_n at c and n and S(u) will be 1 LBP encoding process on a is given in Fig.1

8 neighbors (0 to 7) of the are the grey level intensities if u 0 and 0 otherwise. The 3*3 neighborhood i.e. (8, 1)

(a)

P c as threshold P c =8

1	1	0
1		0
1	0	0

(b)

Binary Code: 11000011

LBP

Code:195 (c)

• Fig. 1.    Encoding of basic LBP operator.

The binary weights of LBP can be given in eight different ways as shown in Fig.2.

The value of the LBP changes by the representation of the weights. The LBP can be calculated in 8 different ways for a 3×3 neighborhood as shown in Fig. 2. That is for any 3×3 neighborhood one can generate eight LBP values. The LBP value for the Fig.1 (a) in all eight directions as represented in Fig.2 is given as 227, 242, 121, 188, 94, 47, 151, and 203 respectively.

20	21	22
27		23
26	25	24

27	20	21
26		22
25	24	23

(a)

26	27	20
25		21
24	23	22

(b)

25	26	27
24		20
23	22	21

(c)                                       (d)

24	25	26
23		27
22	21	20
(e)
22	23	24
21		25
20	27	26

(g)

23	24	25
22		26
21	20	27

21	22	23
20		24
27	26	25

(h)

• Fig. 2.    Eight Different Ways of measuring LBP weights on a 3×3 neighborhood.

Many researchers worked on Uniform Local Binary Pattern (ULBP) and Non Uniform Local Binary Pattern (NULBP) and derived many conclusions. An LBP is uniform if it contains at most one - zero to one and one -one to zero transition in a circular manner. For example 11111111 (0 transitions), 00000001 (2 transitions) are uniform, whereas 11001100  (4 transitions), and

01011111  (5 transitions), 10101100  (6 transitions),

01010101 (8 transitions) are not uniform. Some of the researchers [1, 14, 19, 27, 28, 44] considered only

ULBP’s for classification, recognition and for solving other problems because of the following reasons. a) ULBP’s are treated as the fundamental properties of texture image. b) 80 to 85% of the texture images contain only ULBP’s. c) There are 192 NULBP’s and treating them as miscellaneous will reduce lot of dimensionality without losing much of the texture content. The other group of researchers [29,30,31,32,33,34,35 ] considered a part or few of NULBP’s along with ULBP’s and proved that this combination yielded a better or a little progress than by considering only ULBP’s. From this one can understand that ULBP’s can be treated as the fundamental properties of the texture image, however considering them only may lose some basic information. Therefore it is better to consider a sub set of NULBP’s.

From the above discussion it is evident that the major problem is how to select a subset from NULPBP’s to improve the overall performance and to reduce overall dimensionality. For this the present paper divided the basic LBP operator with 8 neighboring pixels into two four bit LBP operators on a radius of 1. The present paper considered all transitions i.e uniform and non- uniform on the dual LBP, then derived a dual LBP matrix and image retrieval is performed on this.

• III.    Derivation Of The Proposed Dual Uniform Lbp Matrix (Dulbpm)

LBP on a 3x3 neighborhood generates 0 to 255 i.e. 256 different patterns. One can retrieve the texture image based on the 256 LBP in the following way.

• 1.    Find the individual histogram of 256 LBP’s on the texture, by convolving the local 3x3 neighborhood in an overlapped manner. Place them in the feature library.

• 2.    For texture image retrieval find the individual histograms of 256 LBP’s on the query texture image.

• 3.    Apply Euclidean distance measure between the individual histograms of the 256 LBP’s of query texture image with database texture images.

• 4.    Pick up the nearest one i.e. the database texture that exhibits shortest Euclidean distance with the query texture image. If the query and the retrieved texture images are same then it represents a hit otherwise a miss.

The major disadvantage of this method is due to its high complexity and dimensionality. In this method one should evaluate the histogram of all individual 256 LBP’s and Euclidean distance should be found in between the 256 features.

Further research on LBP invented uniform LBP (ULPB) [28]. The 59 ULPB’s out of 256 LBP’s are named as uniform LBP’s and they contains at most two bit wise circular transitions form 0 to 1 or 1 to 0. The Ojala et.al [27] proved that most of the textures contain more than 80% of the patterns as ULBP. That’s why ULBP represents the fundamental unit of LBP. One can retrieve images based on the histogram of ULBP’s. This also becomes a complex task because one should find Euclidean distance between 59 patterns of query and feature database textures.

The aim of the present paper is to reduce this complexity. For this, the proposed method divided the local 3x3 neighborhood into dual sets of four pixels each. The first set is called diagonal LBP contains the four pixels d 1 , d 2 , d 3 , d 4 as shown in Fig.3a in red color. The second set is named as corner LBP contains the corner pixels c 1 , c 2 , c 3 , c 4 as shown in Fig.3a in green color. The four pixels of diagonal LBP and corner LBP forms 16 LBP’s each.

Fig. 3.a. Cross and diagonal pixel representation in LBP.

The four bit LBP forms zero, two and four transitions of 0 to 1 or 1 to 0. The LBP codes 0(0000) and 15 (1111) forms zero transitions. The four bit circular LBP codes 1(0001), 2(0010), 3(0011), 4(0100), 6(0110), 7(0111), 8(1000), 9(1001), 11(1011), 12(1100), 13(1101) and 14(1110) forms 2 circular transitions from 0 to 1 or 1 to 0. The four bit LBP codes 5(0101) and 10(1010), forms 4 circular transitions from 0 to 1 or 1 to 0 and they does not fall into ULBP group. The present paper evaluated and created a 2-D matrix that corresponds to the histogram of uniform transitions of DIAGONAL LBP versus corner LBP. The dual uniform LBP matrix (DULBPM) is a 2-D matrix and it is shown in Fig.3b.

No. of uniform transitions on corner LBP No. of uniform transitions on DIAGONAL LBP 0 2 0 2 fig.3.b. the structure of dulbpm.

The rows of the proposed DULBPM contain the number of uniform transitions of corner LBP and columns contain the number of uniform transitions of diagonal LBP. The DULBPM (i, j) refers to the frequency occurrence of the ith uniform transition of corner LBP versus of jth uniform transition of the diagonal LBP.

The Fig.4.a represents a LBP. The four pixels of corner LBP and diagonal LBP are represented with green and red color respectively. The corner LBP and diagonal LBP of Fig.4.a forms a four bit LBP codes of 1111 and 0110 respectively and they form 0 and 2 circular bitwise transitions from 0 to 1 or 1 to 0 respectively. This results the DULBPM entry as

corner LBP = 1111 = 0 transitions diagonal LBP=0110 = 2 transitions

DULBPM(0,2)=DULBPM(0,2)+1;

Fig. 4.a. LBP representation.

Fig.4.b. Representation of DULBPM.

DULBPM (0, 2) = DULBPM (0, 2) + 1. This is shown in Fig. 4.b

In the similar way the four bit corner LBP and diagonal LBP of Fig.5.a exhibits 2 and 2 transitions respectively. This results the entry of DULBPM (2, 2) =DULBPM (2,

Fig. 5.a. LBP representation.

Fig. 5.b. Representation of DULBPM.

The DULBPM dimensions are 2x2, means they contain only 4 entries. Initially the 2-D DULBPM is initialized to zero. The above process is repeated on the entire texture image to form DULBPM for each texture. The feature or training library database consists of DULBPM for each texture. The proposed DULBPM not considered the 4 transitions on corner LBP and diagonal LBP because they are not part of ULBP. If one considers them, then the proposed matrix becomes dual LBP matrix (DLBPM) and it contains 9 entries with a dimension of 3x3.

• IV.    Results And Discussions

  To test the efficacy of the proposed DULBPM the present research tested this on animal fur, rubber, leaf and car texture images of resolution 256x256. These images are collected from a Google database. The DULBPM is a 2x2 2-D matrix i.e. it consists of 4 entries only and DULBPM entries are initialized to zero. DULBPM is evaluated for 1000 different textures of animal fur, rubber, leaf and car textures and placed in the feature or training database. Whenever a query texture image is given, the DULBPM is evaluated on this and the Euclidean distance is measured between the query texture image and all the textured images of the feature set. The texture of feature database that exhibits the minimum Euclidean distance is selected as a retrieved image. If the retrieved image exactly matches the query image, then it represent a hit otherwise a miss. The Table 1 represents the DULBPM entries of 20 animal fur texture images. In all the tables’ col-1 and col-2 represents the 0 and 2 transitions of diagonal LBP and row-1 and row-2 represents the 0 and 2 transitions of corner LBP respectively. For example in Table 1 the DULBPM (0, 0) for A_F_1 texture represents a value 8042. In the similar way in Table 1 for animal fur-4 texture (A_F_4) DULBPM (2, 2) =52661. Table 2, 3 and 4 represents the 2-D DULBPM entries for rubber, leaf and car texture respectively. The texture retrieval is performed separately based on Euclidian distance between query texture image and feature database texture images using individual entries of DULBPM. That is based on 0 verses 0, 0 verses 2, 2 verses 0, 2 verses 2 bitwise transition of corner LBP verses diagonal LBP.

The image retrieval rate is calculated using the DULBPM(0, 2) , DULBPM(2, 0) and DULBPM(2, 2) entries for the above four group of textures. The Table 5 gives the texture image retrieval rate for different transition of DULBPM. From the table it is evident that the retrieval based on DULBPM (2, 0) and DULBPM (0, 2) entries shown higher performance. There are only two bitwise zero transitions on each of the diagonal and corner LBP, that’s why the DULBPM (0, 0) attained a normal average retrieval rate of 53%.

Table 1. DULBPM entries for animal fur texture.

1	A_F_1	8042	3362
		3991	49121
2	A_F_2	8776	2910
		3320	49510
3	A_F_3	6003	3537
		3843	51133
4	A_F_4	6541	2098
		3216	52661
5	A_F_5	9335	3011
		3950	48220
6	A_F_6	9697	4169
		4073	46577
7	A_F_7	6314	2421
		3038	52743
8	A_F_8	13792	466
		915	49343
9	A_F_9	6499	5125
		5711	47181
10	A_F_10	8347	4342
		4430	47397
11	A_F_11	7229	5175
		5725	46387
12	A_F_12	8448	3929
		5165	46974
13	A_F_13	8448	3929
		5165	46974
14	A_F_14	7230	5069
		6982	45235
15	A_F_15	9463	5181
		5669	44203
16	A_F_16	9270	2475
		3538	49233
17	A_F_17	6904	1942
		3666	52004
18	A_F_18	8731	2494
		3926	49365
19	A_F_19	6220	4079
		6584	45635
20	A_F_20	8463	6281
		7669	55203

Table 2. DULBPM entries for rubber texture.

1	Rubber_1	9527	1518
		2198	51273
2	Rubber_2	9349	2480
		3999	48688
3	Rubber_3	9673	1824
		2953	50066
4	Rubber_4	11172	2385
		2680	48279
5	Rubber_5	9103	2444
		3440	49529
6	Rubber_6	8442	2370
		3032	50672
7	Rubber_7	8855	3037
		2994	49630
8	Rubber_8	11408	2151
		2911	48046
9	Rubber_9	7992	3596
		4414	48514
10	Rubber_10	7460	3297
		3943	49816
11	Rubber_11	8827	1295
		3063	51331
12	Rubber_12	8519	1511
		2854	51632
13	Rubber_13	8833	2388
		3808	49487
14	Rubber_14	7980	2719
		4079	49738
15	Rubber_15	12427	686
		1500	49903
16	Rubber_16	10991	1176
		1839	50510
17	Rubber_17	7090	2938
		4704	49784
18	Rubber_18	12898	2345
		7650	2675
19	Rubber_19	13172	2885
		1480	43229
20	Rubber_20	8153	2466
		3240	49400

Table 3. DULBPM entries for leaf texture.

1	Leaf_1	6751	2745
		5109	49911
2	Leaf_2	6392	3390
		5412	49322
3	Leaf_3	6613	2628
		4566	50709
4	Leaf_4	8659	4601
		3016	48240
5	Leaf_5	9493	2363
		2786	49874
6	Leaf_6	8983	2036
		3062	50435
7	Leaf_7	5595	3166
		5072	50683
8	Leaf_8	10516	2307
		2157	49536
9	Leaf_9	8751	2943
		5514	47308
10	Leaf_10	9042	1179
		2313	51982
11	Leaf_11	6456	2349
		3878	51833
12	Leaf_12	9353	2812
		4672	47679
13	Leaf_13	7066	2556
		4213	50681
14	Leaf_14	6177	3484
		4378	50477
15	Leaf_15	7496	2253
		3730	51037
16	Leaf_16	4885	3662
		5155	50814
17	Leaf_17	8649	1600
		2752	51515
18	Leaf_18	31167	1328
		1802	30219
19	Leaf_19	5191	2457
		4055	52813
20	Leaf_20	6810	2075
		4366	51265

Table 4. DULBPM entries for car texture.

1	Car_1	30011	19
		487	33999
2	Car_2	18996	23
		425	45072
3	Car_3	28303	673
		1863	33677
4	Car_4	27217	9
		435	36855
5	Car_5	31025	10
		363	33118
6	Car_6	29912	7
		657	33940
7	Car_7	21218	32
		481	42785
8	Car_8	22528	20
		375	41593
9	Car_9	26010	11
		444	38051
10	Car_10	29910	10
		389	34207
11	Car_11	22297	15
		248	41956
12	Car_12	22710	10
		273	41523
13	Car_13	27429	26
		345	36716
14	Car_14	20774	12
		450	43280
15	Car_15	24073	24
		534	39885
16	Car_16	17184	1817
		3680	41835
17	Car_17	12204	793
		3121	48398
18	Car_18	13406	1024
		2651	47435
19	Car_19	18886	1699
		2289	41642
20	Car_20	22247	7
		431	41831

Table 5. Retrieval rates of different transitions based on DULBPM entries.

ujhTexture Databases	Retrieval rates 0-0 Transition of DULBPM	Retrieval rates 0-2 Transition of DULBPM	Retrieval rates 2-0 transition of DULBPM	Retrieval rates 2-2 transition of DULBPM
Animal fur	33	60	60	33.33
Rubber	40	66.66	53.33	33.33
Leaf	46.66	66.66	66.6	40
Car	73.33	86.6	93.3	46.6
Average retrieval rate	53.3	69.98	68.3	38.315

From the Tables 1, 2, 3 and 4 it is clearly evident that the histogram of DULBPM (2, 2) shows a very high values for all the considered textures. The reason for this is there are 12 four bit LBP codes that shows exactly two transitions from 0 to 1 or 1 to 0 on each of the corner and diagonal LBP. That why the DULBPM (2, 2) resulted a very high values in the above tables. These histograms of DULBPM (2, 2) have no significant ranges of difference among the considered textures because the present paper integrated all 12 LBP four bit codes under one label. The reason for significant improvement for texture retrieval using DULBPM(0,2) and DULBPM(2,0) is a relation between 2 codes (with 0 transitions) versus 12 codes (with 2 transitions) of 4 bit corner and diagonal LBP and also vice versa. Ojala et. al [27] proved 80% to 90% of textures contains uniform LBP windows on 3x3 neighborhood i.e only 10% to 15 % windows are nonuniform LBP. The present paper outlines all 100% dual LBP’s each with 4 bits on a 3x3 neighborhood are uniform. Therefore there is no rule for NULBP’s on the considered DULBPM for any kind of application.

• V.    Conclusions

The problems related to, which features of image gives best CBIR result remains unsolved. To address this present research focused CBIR based on LBP. LBP characterizes the all significant local image content with higher levels of semantics. One of the disadvantages with LBP is its high dimensionality. The proposed DULBPM reduced the overall dimensionality of evaluating the histograms of 256 patterns of LBP and also 59 patterns of ULBP. The low dimensionality and accuracy of the DULBPM made the LBP to be more suitable to large volumes of data (big-data) and to real time applications. In the proposed DULBPM one has to evaluate only the histograms of four features instead of 256 and 59. Further the present paper also evaluated the transitions of nonuniform LBP’s that is DLBPM (4, 0), DLBPM (4, 2), DLBPM (4, 4), DLBPM (0, 4) and they resulted zero only. This clearly indicates that in the considered diagonal LBP the frequency occurrences of 4 or NULBP transitions are zero. The retrieval rates of DULBPM (0, 2) and DULBPM (2, 0) are higher when compared to the other DULBPM entries.