Texture is an important element to human vision. Belesz [13] has reported that a "preattentive visual system" exists which can almost instantaneously identify "textons", the preattentive elements of textures. The human visual system has also been found to decompose the retinal image into narrow bands of frequency and orientation which are important for discerning texture primitives [3]. Textures also have been used in 3-D visual recognition systems to provide cues to scene depth and surface orientation. In graphics systems, greater "realism" is achieved when textures are mapped to 3-D surfaces. Human beings also tend to relate texture elements of varying size to a plausible 3-D surface [1]. Texture features have been used to identify contents of ariel imagery such as bodies of water, crop fields and mountains. Finally, textures may be used to describe content of many real-world images: for example, clouds, trees, bricks, hair, fabric all have textural characteristics. Particularly when combined with color and shape information the details important for human vision are provided [6].
Because of the fundamental importance of texture information for human vision, texture can be used to provide a meaningful tool for searching image databases. By identifying texture contents of images in the database, a user may search through large volumes of images using texture keys. A "Query-by-texture" can be formulated to search through the image database, which will return images found to contain regions of similar texture. Ideally, there is no restriction that the textures belong to predefined classes. Furthermore, the "Query-by-texture" can be combined with other descriptions of color and shape, in the formulation of overall image content-based queries.
2.2 Texture Discrimination and Segmentation
Towards the development of the "Query-by-texture" mechanism, it is necessary to find a meaningful measure of the similarity of textures (texture discrimination) and to develop a procedure for segmenting images based on textural content (texture segmentation). Furthermore, a discriminant function is needed to gauge the similarity between textured regions and the texture key used for searching. Likewise, the discriminant function can also be used to match blocks within each image to produce the texture segmentation.
Using a quad-tree data structure, we carry out texture segmentation by grouping image spatial blocks using feature sets developed for the discrimination of the full set of 112 Brodatz [5] textures. In our approach, all feature sets are computed directly from the Quadrature Mirror Filter (QMF) wavelet representation of the images. While the QMF wavelet features have been found to provide good classification of Brodatz textures, we found in our previous work [20] that feature sets derived from other typical image representations, such as DCT transform and uniform subband representation, are also effective. Although more sophisticated feature extraction techniques have been studied for texture discrimination [16][11], an image database may contain hundreds of thousands of images. Therefore, it is beneficial when segmentation can be performed using data directly available in the given image representations. We have focussed on QMF wavelet features keeping in mind the application to large image databases. Although, our approach is general enough to use instead other sophisticated features sets that discriminate between textures.
Because the goal of this segmentation is to provide indexing of images in the database, we relax the constraint that the segmentation provide perfect boundary extraction. Our segmentation is successful when representations of the important regions of texture of the images are obtained. Using the spatial quad-tree approach, each quad-tree node points to a block of image data. Children nodes are merged when a discriminant function indicates that the children blocks contain sufficiently similar textures. The "Query-by-texture" examines the blocks identified by the quad-tree structure to test the similarity to the texture-key.
3. Quad-Tree Segmentation
Typically in a top-down quad-tree decomposition, a full quad-tree data structure is formed by splitting a single parent node into four children. Then all descendants are recursively split into children until some minimum bound is reached. We use the quad-tree decomposition to perform spatial segmentation by assigning a condition by which nodes are split. We also added a post-processing routine for adjoining similar spatially adjacent nodes with different parents. A final block grouping stage can be added to merge all similar blocks to obtain arbitrarily shaped regions, which was not yet investigated in this research.
We have also modified the quad-tree structure to allow each parent node to have two, three or four children, as shown in Figure 2(a). The results of a modified quad-tree decomposition performed on the "Barbara" image appears in Figure 2(b). When all four children cannot be merged together, subsets of the children may be paired horizontally or vertically depending on which arrangements group the most similar children.
Using the top-down approach, we perform texture feature extraction on the spatial blocks pointed to by each children node. Based on the values of the texture features, all, some or none of the children are spawned. For each spatial block, this requires feature extraction, computation of the distance between the children and the parent, and comparison to a distance threshold to test condition for merging children.
4. Texture Feature Extraction
4.1 Block-based features
Some approaches to texture segmentation fall under the category of pixel-based schemes. In general, pixel-based segmentation schemes evaluate the texture features in a neighborhood surrounding each pixel in an image. When neighboring pixels are classified similarly, regions of texture are formed. Of course, a difficulty results when image pixels border several textured regions. Then the features may not resemble those of the nearby textures. Sophisticated techniques are often adopted to decipher this border information between textures. However, in an image database application, precision in border extraction may not be necessary as long as a block of each texture is identified. Since the blocks of texture may suffice for matching, we adopt a computationally less expensive quad-tree approach for image segmentation which can use traditional texture discriminant functions to group blocks within the image. By utilizing a block-based approach towards feature extraction, the loss in boundary localization is a direct result of the uncertainty principle [22]. However, since we use blocks of data from which to compute texture features, the spatial localization can be traded off for better spectral selectivity and statistically computed features.
4.2 Wavelet subband features
Effectively, we treat each block as a separate image of texture. Any features extracted from the blocks that provide discrimination may be used. For our experiments, we have chosen to use features extracted from the QMF wavelet decomposition of each block because of the reasonable discrimination performance found for classifying Brodatz textures. The features are computed from the mean absolute value and variance measures on the subbands produced from three iterations of QMF wavelet decomposition. This feature was found to give 93% correct classification of the complete set of 112 Brodatz textures [20]. The wavelet feature-based texture classification process is illustrated in Figure 3.
The QMF wavelet subband decomposition is an orthogonal approximation to that produced by Gabor filters. Gabor filters have been applied to texture segmentation by Bovick [4] and Jain [12]. The advantage of these wavelet spatial-frequency approaches is that simple statistics computed from the subband images may be used because the images have limited spectral information [12]. Gabor filters have found particular application in texture discrimination because a filter set can consist of arbitrarily scaled and rotated filters. Gabor filter banks have also been found to approximate the mechanisms of human vision [12]. The filters also meet the minimum combined uncertainty in both spatial and spatial-frequency domains. Most Gabor filter banks used for texture discrimination do not provide a complete basis for decomposition as shown in Figure 4(a). The QMF wavelet decomposition does provide an orthogonal basis but does not provide as much granularity for identifying frequency directional components as shown in Figure 4(b). A QMF wavelet decomposition of the Barbara image appears in Figure 4(c).
We combine the quad-tree data structure with wavelet subband representation to perform image segmentation as follows: for each quad-tree block, features are extracted by computing the wavelet decomposition of the block, as indicated in Figure 5(a). Features are obtained by measuring statistics from the wavelet subbands. However, in general, to perform wavelet decomposition, image borders require padding before filtering is carried out. Typically, padding information is taken from within the image based on some rule, such as mirror extension of borders. Since we are dealing with image blocks and not actually separate image entities, the border information can be extracted from neighboring image blocks by borrowing border pixels in the filtering operation.
Done this way, the wavelet decomposition and feature extraction processes are no longer independent for each spatial block. But the exchange offers an elegant solution for padding, and the order of operations can be reversed. First the entire image is decomposed using wavelet filtering, then quad-tree spatial blocks point to appropriate regions in the full wavelet image, as shown in Figure 5(b). Furthermore, features can be extracted directly from the wavelet images, if the wavelet representation is used to store images in the database. We placed some focus on this representation since the wavelet representation has a number of beneficial qualities in the image database application, such as providing a multiresolution structure and energy compaction to enable compression.
5. Textural Similarity
5.1 Training
Sample textures from the Brodatz texture collection were used to obtain a discriminant function using Fisher Discriminant Analysis. This procedure constructs linear composites of the features which provide for maximum average separation among training classes [9]. In our previous work, a discriminant function generated from a fractional subset of Brodatz textures was found to provide effective discrimination among all Brodatz textures [20]. We hope that using the complete set of 112 Brodatz classes in training will construct a discriminant function general enough to discriminant between new and unknown textures. The Mahalanobis [10] distance, which is actually the Euclidean distance in the transformed feature space, was used to measure the similarity between textures. In ordinary classification of textures or comparisons of many textures, the relative rankings of the Mahalanobis distances are used to identify closest matches. Subsequently, in response to a "Query-by-texture", all textures in the database will be sorted by this distance to the texture-key. This search requires no threshold to be established for when textures are no longer "similar." However, to decide whether two textures are similar or not, as in quad-tree segmentation, requires a threshold in distance. In general it can be difficult to set this threshold for all textures. We have used observations made on the distributions of the 112 Brodatz texture classes in feature-space to estimate an effective threshold for similarity between textures.
5.2 Distance Threshold
Using a fixed distance threshold for determining whether two textures are sufficiently similar will not be optimal for all types of textures. Depending on the characteristics captured by the extracted feature sets and the particular derived non-singular mapping to a transformed feature space, the within-class variance for visibly similar textures will vary from class to class. We have found that the distance threshold depends heavily on the block size from which the features are extracted and on the energy of the feature set.
5.2.1 Block Size
There is an inverse relation between block size and the accuracy in the estimation of the underlying probability distribution based on statistical measures produced from the blocks. Since smaller texture blocks will contain fewer data points from which to derive statistical features, there will be a larger deviation in features extracted from these blocks of similar textures. This results in a greater variance in distance between possibly similar textures, necessitating a higher distance threshold for comparing textures of smaller block size. Likewise, features extracted from larger blocks produce smaller within-class variation, necessitating a lower distance threshold for comparing textures of larger block size.
5.2.2 Feature Set Energy
The within-class variation is also correlated to the magnitude of the transformed feature sets, as depicted in Figure 6(a). For a texture class i, the distance 
in feature space for a member of that class to the centroid 
of that class is a function of the energy of the feature set 
. Textures that produce high energy features sets typically belong to classes with the largest within-class variance. Likewise, textures producing low energy features typically belong to texture classes with small within-class variance. Figure 6(b) shows the energy plot of four Brodatz textures that illustrate this relationship. The distance threshold can be determined from information about the textures being compared, namely image region size and energy of the feature set.
5.2.3 Distance Threshold Computation
To develop distance thresholds to be used for quad-tree segmentation, we examined the training texture cuts taken from Brodatz collection previously, and observed a strong positive correlation (0.75) between the quotient of feature energy and image size, and distance to correct class. Performing a linear regression analysis on this data, the threshold function in EQ 1 was obtained. Here 
is the threshold to be used in the Mahalanobis distance, 
is the energy of the transformed feature vector and s is the number of pixels in the image block.
(EQ 1)
5.2.4 Threshold for Quad-tree Splitting
Beginning with the complete image as the first node, the quad-tree is formed by iteratively splitting each node into children nodes. Four children are spawned by each parent and based on the texture features extracted for each child, conditions for merging are tested. The distance threshold is computed for each child as a function of the child feature energy and block size using EQ 1. Then the distances in feature space are measured from the parent node to each child. If the distances to all four children fall within the respective thresholds of the children a single texture is declared in the parent node, as illustrated in Figure 7(a). Then the parent is marked as a terminal node and the children are deleted. If a single texture is not present, then tests for pair-wise grouping of children are performed. When the distance between the next two closest children falls below both respective thresholds, the children are merged, see Figure 7(b). When no children are close, all children are kept as nodes, and quad-tree iteration continues on each child, see Figure 7(c).
5.2.5 Likelihood ratio test
In actuality the value of the distance threshold will determine the trade-off between Pd, the probability of correct detection of similar textures and Pf, the probability of false detection. Due to the nature of the underlying distributions of parent-child distances when a single textured region is present versus the case when more than one texture among children blocks is present, Pd and Pf will always increase and decrease together. This can be observed in the histogram plots of parent-child distances for the two cases presented in Figure 6(c). Furthermore, a result of signal detection theory based on initial work on target identification tells us that using a likelihood ratio test, Pd can always be higher than or equal to Pf. Therefore, an alternative to formulating the distance threshold formula from training data as in the previous section, is to measure the apriori probability distributions of distances between parent-child blocks. Then the threshold can be shifted to adjust the trade-off between Pd and Pf. This framework allows the capability to adjust the texture segmentation to the optimal trade-off between Pd and Pf, given some cost functions for each.
6. Indexing images by texture
6.1 Processing of Texture Key
The texture key provided by the user to initiate a texture-based search can be examined for information on the scale of the texture process. The texture process scale is determined by the size of the fundamental elements which are repeated in some way to form the texture. By performing a quad-tree based texture segmentation on the key, ideally, a single quad-tree node will result, indicating that one texture is present. Starting from some initial small block size, and performing quad-tree bottom-up decomposition on the texture key at successively larger starting block sizes, eventually a complete merge will result. If this is not the case, then it is most likely that the texture key does not contain a single texture, or the scale of the texture process is larger than the texture key size. If a single texture is found, then the smallest block size that produces a full merge of the texture key indicates the minimum block size in the database to be examined. This scale information obtained by processing the texture key can reduce the number of searches for a "Query-by-texture". Blocks in the database that are smaller than the minimum block size obtained will not have to be considered.
6.2 Query-by-texture
An image database was generated by randomly compositing five cuts per image from 134 images consisting of 112 Brodatz texture images and 22 real world images to generate a database of 200 images. To generate the composite images, first four random pieces were tiled in each of the corners to cover the entire image area. Then a fifth random cut was positioned in the center, overlapping parts of the four cuts. Finally, a random shift was applied in both the x and y directions with a wrap around of image data to scramble the blocks of texture. This produced images each with five possibly distinct textures contained in possibly many disjoint regions. "Queries-by-texture" were then performed on this composite image database using cuts from the Brodatz textures as texture keys. A typical result from a "Query-by-texture" on this composite texture image database is shown in Figure 8
7. Searching FEAture space
7.1 hierarchical searching
As the number of images and textured regions increases it becomes necessary to utilize a searching procedure more efficient than exhaustive search. One natural by-product of feature-space compaction performed by the Fisher Discriminant Analysis on the Brodatz texture data is the ordering in significance of discriminant functions that results. This energy compaction may be exploited by adapting a hierarchical approach to searching. This way each dimension of the feature space can by searched successively in order of significance. For example, a binary search may be conducted on sorted feature data beginning with the most significant discriminant functions. At first the candidate match list will be kept larger than the final desired number of retrievals. As the candidate list is searched further, using the remaining discriminant functions, the list will be further truncated until the closest matches are found. This technique of successive refinement reduces the complexity of searching the high-dimensional feature space.
7.2 feature space partitioning
A second alternative to searching the high-dimensional texture feature space is to partition the feature space. This way the search can be conducted in two stages. The first will identify the appropriate partition in feature space to search. Next the search will examine only the data points in the partition. However, if the dimension of the feature space is large it is unlikely that uniform partitioning will be optimal. For example, data may be confined to several partitions while remaining are empty. This will result in non-uniform search performance.
7.3 data clustering
An improvement over partitioning the feature space is to gather data points into clusters. Again the search will be broken into two stages. The first will identify the appropriate cluster, and the second will search all the data points in that cluster. Search performances at each stage can be regulated by the clustering algorithm. A bound set on the maximum number of data points per cluster will produce a bound on the second stage of the search algorithm. This results in more consistent performance than partitioning the feature space.
8. Conclusion
We have presented a method for performing "Query-by-texture" on an image database. Texture has been shown to be a viable characteristic of visual information by which image data may be indexed in a large image database. Using a quad-tree approach to image segmentation, feature sets are extracted from image blocks and conditions for merging are determined by a texture discriminant function. Without resolving border details between textured regions, we use the homogeneous rectangular blocks of texture within each image to perform indexing in the database. Our approach, in general, places no limitations on how features are extracted from image blocks, nor does it require that the features even be texture. We have used specifically features sets based on the QMF wavelet decomposition because of the discrimination performance, and the benefits this representation offers in a database application. The quad-tree method offers an efficient approach towards segmenting and representing textures present in an image, and provides a general framework by which other discriminating features can be used for image segmentation.
8.1 Future Work
We are currently extending the texture segmentation and "Query-by-texture" methods to a database of real-world images that consist of images from nature, art, architecture and medicine. The "Query-by-texture" feature will be integrated with keyword indexing to provide the user with both textual and visual keys for searching for images in the database. We will also be exploring other features such as color and shape to be used to perform overall content-based queries of image databases. This work will be part of the Content-Based Visual Query System and Video On-Demand prototype efforts at Columbia University [24].
References:
[1] Dana H. Ballard and Christopher M. Brown, Computer Vision, Prentice-Hall, Inc., 1982.
[2] R. Barber, W. Equitz, M. Flickner, W. Niblack, D. Petrovic, P. Yanker, "Efficient Query by Image Content for Very Large Image Databases", COMPCON, San Francisco, 1993.
[3] Jacob Beck and Anne Sutter and Richard Ivry, "Spatial Frequency Channels and Perceptual Grouping in Texture Segregation", Computer Vision, Graphics, and Image Processing, 1987, Vol. 37, pp. 299--325.
[4] A. C. Bovick, "Analysis of Multichannel Narrow-Band Filters for Image Texture Segmentation", I.E.E.E. Transactions on Signal Processing, Vol. 39, No. 9, September 1991, pp. 2025 - 2043.
[5] P. Brodatz, Textures: a Photographic Album for Artists and Designers, Dover, New York, 1965.
[6] Terry Caelli and David Reye, "On the Classification of Image Regions by Colour, Texture and Shape", Pattern Recognition, Vol. 26, No. 4, pp. 461--470, 1993.
[7] S. K. Chang, C. W. Yan, D. C. Dimitroff and T. Arndt, "An Intelligent Image Database System", I.E.E.E. Transactions on Software Engineering, vol. 14, no. 5, May 1988.
[8] N. Dal Degan, R. Lancini, P. Migliorati and S. Pozzi, "Still images retrieval from a remote database: The system Imagine", Signal Processing: Image Communications, vol. 5, 1993, pp 219 - 234.
[9] William R. Dillon and Matthew Goldstein, Multivariate Analysis, John Wiley & Sons, 1984
[10] Keinosuke Fukunaga, Introduction to Statistical Pattern Recognition, Harcourt Brace Javanovich, 1990.
[11] Robert Haralick, "Statistical and Structural Approaches to Texture", Proceedings of the I.E.E.E., May 1979, Vol. 61, No. 5, pp. 786--803.
[12] Anil K. Jain and Farshid Farrokhia, "Unsupervised Texture Segmentation Using Gabor Filters", Pattern Recognition, Vol. 24, No. 12, pp. 1167--1186, 1991.
[13] B. Julesz and J.R. Bergen, "Textons, The Fundamental Elements in Preattentive Vision and Perception of Textures", 1983, pp. 243--456.
[14] Amlan Kundu and Jia-Lin Chen, "Texture Classification Using QMF Bank-Based Decomposition", GVGIP: Graphical Models and Image Processing, September, 1992, Vol. 54, No. 5, pp. 369--384.
[15] Wayne Niblack, "Querying large image databases by content", OE Reports of The International Society for Optical Engineering, No. 123, March 1994, pp. 15.
[16] Philippe P. Ohanian and Richard C. Dubes, "Performance Evaluation for Four Classes of Textural Features", Pattern Recognition, Vol. 25, No. 8, pp. 819--833, 1992.
[17] Todd R. Reed and J.M. Hans du Buf, "A Review of Recent Texture Segmentation and Feature Extraction Techniques", CVGIP:Image Understanding, Vol. 57, No. 3, May 1993, pp. 359--372
[18] Hanan Samet, Applications of Spatial Data Structures -- Computer Graphics, Image Processing, and GIS, Addison - Wesley Publishing Company, 1990.
[19] Hanan Samet, "The Quadtree and Related Hierarchical Data Structures", Computing Surveys, Vol. 16, No. 2, June 1984, pp. 187--257.
[20] John R. Smith and Shih-Fu Chang, "Transform Features for Texture Classification and Discrimination in Large Image Databases", accepted for I.E.E.E. International Conference on Image Processing (ICIP) in Austin, Texas 1994.
[21] M. Spann and R. Wilson, "A Quad-Tree Approach to Image Segmentation which Combines Statistical and Spatial Information", Pattern Recognition, Vol. 18, No. 3/4, pp. 257--269, 1985.
[22] Roland Wilson and Michael Spann, Image Segmentation and Uncertainty, Research Studies Press, John Wiley & Sons, 1988.
[23] J. You and H.A. Cohen, "Classification and Segmentation of Rotated and Scaled Textured Images Using Texture Tuned Masks", Pattern Recognition, Vol. 26, No. 2, pp. 245--258, 1993.
[24] Shih-Fu Chang and Dimitri Anastassiou, "Development of an Advanced Image/Video Server in the Video on Demand Testbed," IEEE Workshop on Visual Signal Processing & Communications, New Jersey, September, 1994.
FIGURE 1. Columbia University's Content-Based Visual Query System -- Graphical User Interface, showing collection of art images.
FIGURE 2. (a) Modified Spatial Quad-tree representation -- each tree parent can have two, three or four children, (b) Texture-Based Quad-tree segmentation of the Barbara image. Each Quad-tree node is indicated by white bordered region.
FIGURE 3. Texture classifier using wavelet subband features.
FIGURE 4. (a) typical Gabor filter tilings used for texture discrimination, and (b) frequency tiling produced by orthogonal separable (QMF) wavelet decomposition, and (c) QMF wavelet decomposition of the Barbara image.
FIGURE 5. (a) Quad-tree decomposition followed by wavelet-based feature extraction performed on quad-tree blocks, (b) Quad-tree blocks point to regions in wavelet image for feature extraction.
FIGURE 6. (a) the distance
FIGURE 7. Splitting examples. Note: circle radius = distance threshold for each child as computed as a function of child energy and block size. (a) No Split -- all children belong to single class, (b) Split into two -- children 0 and 3 form a texture class, and children 1 and 2 form a second texture class, (c) Split into four -- four texture classes present in this spatial block.
FIGURE 8. "Query-by-Texture" -- using a cut from Brodatz texture D101 as a texture-key to search through the image database. The three closest matches shown at the bottom are returned to user using multi-resolution retrieval.
Generated with CERN WebMaker
of each texture class member to the centroid 
of the class is a function of energy of the feature set
, (b) first two most significant dimensions in feature space for four random Brodatz texture classes, (c) histograms of the sums of distances of children to parent when one single homogeneous texture present and more than one texture present
