9512.net
甜梦文库
当前位置:首页 >> >>

A Fast Texture Feature Extraction Method for Region- based Image Segmentation


A Fast Texture Feature Extraction Method for Regionbased Image Segmentation

Hui Zhang, Jason E. Fritts, Sally A. Goldman

Washington University

Introduction
Image segmentation: Decomposes an image into several constituent components, which ideally correspond to real-world objects. Region-based image segmentation: an image is partitioned into connected regions by grouping neighboring pixels of similar features. Features of interest: color, texture, shape, etc.

Introduction
To achieve fine-grain segmentation at the pixel level, we must be able to define features on a perpixel basis. Extracting color information is straightforward. Texture feature extraction is very computationally intensive for individual pixels.

Pixel-level Texture Features

Fast Texture Feature Extraction
Basic Idea
? Usually the neighboring pixels are highly correlated. Nearly identical results are generated by performing nearly identical computations in typical methods. Trade off decreased computational complexity with a small amount of distortion.

?

solid color

?

uniform texture

Fast Texture Feature Extraction
Basic Steps

1. Divide the target image into high-level blocks (1st level backbone blocks) 2. Apply Fast Texture Estimation Algorithms (FTEA) 3. Color-texture Alignment 4. Handle out-of-block pixels

Fast Texture Feature Extraction
Backbone Blocks

Fast Texture Feature Extraction
Auxiliary Texture Features
Sliding window for extracting:
texture features for pixel p(i,j)
P(i,j) B2(i,j)
P(i+k/2, j+k/2)

texture features for pixel p(i+k/2,j+k/2): backbone block texture features for backbone block B2(i,j) key pixel texture features for key pixel p(i, j)

P(i,j)

Key pixel

Fast Texture Feature Extraction
Fast Texture Estimation Algorithm
First 1st level backbone blocks Next 1st level backbone blocks high level backbone blocks

Hierarchy control yes Divide block to next higher level blocks Go to next highest level blocks >1 1

Solid Color Estimation
(solid color?)

no yes Uniform Texture Estimation no
(uniform texture?)

0 Texture Feature Assignment

Highest level is

Finished

Fast Texture Feature Extraction
Fast Texture Estimation Algorithm
Solid Color Estimation
(solid color?)

Backbone Block Texture Measure, M(Bs),
h v o M ( B s ) = VTB B s + VTB B s + VTB Bs

( )

( )

( )

For a backbone block B(i,j) and a given texture feature threshold T: If M(B) <= T, there are negligible variation in color. Go to “Texture Feature Assignment”. If M(B) > T, there are non-negligible texture values in B. Go to “Uniform Texture Estimation”.

M(B)

a backbone (16x16)

Fast Texture Feature Extraction
Fast Texture Estimation Algorithm
Uniform Texture Estimation
(uniform texture?)

Backbone Block Texture Distance, D(B1s,B2s):
o o + VTK Pkey ( B1s ) ? VTK Pkey ( B2s )

h h v v s D( B1s , B2s ) = VTK Pkey ( B1s ) ? VTK Pkey ( B2s ) + VTK Pkey ( B1s ) ? VTK Pkey ( B2 )

(

)

(

(

)

)

(

)

(

)

(

)

For a backbone block B and a texture feature threshold T, compute the D with the right, below and diagonally right-below neighboring backbone block key pixels at the same level: If all three backbone block texture distances are less than the threshold. Go to “Texture Feature Assignment”. Otherwise, go to “Hierarchy Control” and repeat the steps at a higher level.

D_right D_below

D_diagonal

Fast Texture Feature Extraction
Fast Texture Estimation Algorithm
Hierarchy control Divide block to next higher level blocks Go to next highest level blocks >1 1
the backbone block has no solid color or uniform texture divide it into 4 higher level backbone blocks the backbone block has solid color or uniform texture all pixels in this block get texture features, go to next highest level blocks If the next highest level is 0 all pixels in the image* get their texture features 1 all pixels in this 1st level backbone block get their texture features >1 Estimate texture features for pixels in small blocks (high level backbone blocks)

0

Highest level is

Finished

Fast Texture Feature Extraction
Fast Texture Estimation Algorithm

Texture Feature Assignment

the backbone block has solid color or uniform texture Every pixel get the same texture features as the key pixel

Fast Texture Feature Extraction
Color-Texture Alignment
? Reason: The defining window of texture and the texture feature estimation window are different ? Consequence: Each pixel p(i, j) after FTEA has the texture features of p(i+blocksize/2, j+blocksize/2).
K

S

p

? Shift before shift of the texture features, the color and texture of each pixel is mis-aligned.

defining window

estimation window

Fast Texture Feature Extraction
Out-of-block pixels
? Out-of-block (OoB) pixels: pixels that cannot be covered by 1st level backbone blocks ?FTEA cannot assign texture feature values for OoB pixels. ? Color-texture alignment give some OoB pixels texture features. ? For remaining pixels: ? start with smaller sliding windows and extract texture features for each of them individually, ? just use the texture features of the nearest key pixel as its texture features. ? These numbers are usually small: ? If the 1st level backbone block size b = 4, the largest possible number of OoB pixels is (M+N+7); If b = 8, the largest possible number is (3M+3N+23).

Experimental Details
Experimental Images:

Red Rose (199x133)

Dinosaur (175 * 117)

Tower (134 * 201)

Mountain (202 * 135)

Experimental Details
Speedup of Fast Texture Extraction

Texture Extraction Time vs. Threshold T (where 0<= T <= 1) Time(usec) 350000 300000 250000 200000 150000 100000 50000 0 0 0.2 0.4 0.6 0.8 1 Threshold (0<=T<=1)

Time(usec) 350000 300000 250000 200000 150000 100000 50000 0 1

Texture Extraction Time vs. Threshold T (where T>= 1) Rose Dinosaur Mountain Tower

10

100

1000

10000

100000

Threshold(T>=1, logarithmic scale)

Experimental Details
Speedup of Fast Texture Extraction
Image Red Rose Dinosaur Mountain Tower Pixel-level time 16 16 16 16 Threshold = 0 11.87 8.12 11.39 10.74 Threshold = 0.2 7.82 4.67 7.42 5.86 Threshold = 1 6.46 4.30 6.76 5.21 Block-level extract time 1 1 1 1

Table 1: The normalized extraction time Image Red Rose Dinosaur Mountain Tower Threshold =0 345281 174558 339837 339092 Threshold Time = 0.2 Reduction (%) 227493 126051 221667 147526 34.11% 27.79% 34.77% 56.5% Threshold =1 187829 111997 202035 135897 Time Reduction (%) 45.6% 35.84% 40.55% 59.92%

Table 2: The reduction of extraction time when texture threshold = 0.2 and 1 (Unit: μsec.)

Experimental Details
Effectiveness of Fast Texture Extraction
Effectiveness Measures:
Distortion Percentage (DP):
? ? M ?1 N ?1 T ? ∑∑ | Vs (i, j ) ? Vs0 (i, j ) | ? ( M * N ) ? ? i =0 j =0 ? ? T = DPs = ? ? M ?1 N ?1 0 ? ∑∑ Vs (i, j ) ? ( M * N ) ? ? ? ? i =0 j =0
M ?1 N ?1 i =0 j =0

∑∑ | V

T s

(i, j ) ? Vs0 (i, j ) |
T s

M ?1 N ?1 i =0 j =0

∑∑V

(i, j )

Fast Extraction Signal Noise Ratio (FESNR):
? ? M ?1 N ?1 T ? ∑∑ (Vs (i, j )) 2 ? ( M * N ) ? ? i = 0 j =0 ? ? T = FESNR s = ? ? M ?1 N ?1 T ? ∑∑ (Vs (i, j ) ? Vs0 (i, j )) 2 ? ( M * N ) ? ? ? ? i =0 j = 0
M ?1 N ?1 i =0 j = 0 T s

∑∑ (V

T s

(i, j )) 2

M ?1 N ?1 i = 0 j =0

∑∑ (V

(i, j ) ? Vs0 (i, j )) 2

Experimental Details
Effectiveness: Distortion Percentage
Distortion Percentage of Fast Extraction (Dinosaur) 180.00% 160.00% 140.00% 120.00% 100.00% 80.00% 60.00% 40.00% 20.00% 0.00% 0.1 1 10 100 1000 10000 100000 Fast Extraction Threshold (Logarithmetic scale) Distortion Percentage of Fast Extraction (Mountain) 160.00% 140.00% 120.00% 100.00% 80.00% 60.00% 40.00% 20.00% 0.00% 0.1 1 10 100 1000 10000 Fast Extraction Threshold (Logarithmetic scale) 100000 Mountain_HL Mountain_LH Mountain_HH 180.00% 160.00% 140.00% 120.00% 100.00% 80.00% 60.00% 40.00% 20.00% 0.00% 0.1 1 10 100 1000 10000 100000 Fast Extraction Threshold (Logarithmetic scale) Tower_HL Tower_LH Tower_HH Dinosaur_HL Dinosaur_LH Dinosaur_HH 140.00% 120.00% 100.00% 80.00% 60.00% 40.00% 20.00% 0.00% 0.1 1 10 100 1000 10000 100000 Fast Extraction Threshold (Logarithmetic scale) Distortion Percentage of Fast Extraction (Tower) RedRose_HL RedRose_LH RedRose_HH Distortion Percentage of Fast Extraction (Red Rose)

Experimental Details
Effectiveness: FESNR
FESNR of Dinosaur 20 Dinosaur_HL 15 Dinosaur_LH Dinosaur_HH 15 20 RedRose_HL RedRose_LH RedRose_HH FESNR of Red Rose

FENSR

5

FESNR
0.1 1 10 100 1000 Fast Extraction Threshold (logarithmic scale) 10000 100000

10

10

5

0

0

-5

-5 0.1 1 10 100 1000 Fast Extarction Threshold (logarithmic scale) 10000 100000

FESNR of Mountain 20 Mountain_HL 15 Mountain_LH Mountain_HH 15
FENSR FESNR

FESNR of Tower 25 20 Tower_HL Tower_LH Tower_HH

10

10 5

5

0

0 -5 0.1 1 10 100 1000 Fast Extraction Threshold (logarithmic scale) 10000 100000 0.1 1 10 100 1000 Fast Extraction Threshold (logarithmic scale) 10000 100000

-5

Experimental Results
For Distortion Percentages : If T is in [0, 1], DP < 10% If T is in (1, 5], DP < 20% Distortion Percentages vs. Reduction of computation time (RoCT) threshold is 0.2: DP: 0.6%~3.7%, RoCT: 27.8% ~ 56.5% threshold is 1: DP: 2.2%~7.7%, RoCT: 35.8% ~ 59.9% For FESNR: When T < 1, the FESNR is usually very high, and with increasing of T, the FESNR decreases slightly. When T > 1, the FESNR decreases much more quickly. When T is in the range (0, 1]. It greatly increases the extraction speed, but with only a small amount of distortion.

Conclusions
FTEA takes advantage of the similarities between neighboring pixels. It greatly increases the extraction speed while keeping the distortion within a reasonable range. The threshold T is user-defined, so we can balance the extraction speed and the distortion according to specific situations. Notice when T is 0, we cannot get the exactly same result as using traditional methods. Use variable-sized sliding window for the key pixel texture features, which leads to inconsistent feature accuracy. Or remove the first step in the FTEA, which solves this problem, but results in slower feature extraction.

References
Trygve Randen, and John Hakon Husoy, “Filtering for Texture Classification: A Comparative Study”, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 21, no. 4, pp. 291-310, April 1999 E. Saber and A. M. Tekalp, “Integration of Color, Shape, and Texture for Automatic Image Annotation and Retrieval,” Journal of Electronic Imaging (special issue), vol. 7, no. 3, pp. 684-700, July 1998 M. Unser, “Texture Classification and Segmentation Using Wavelet Frames”, IEEE Trans. on Image Processing, Vol. 4, No. 11, Nov. 1995, 1549-1560. James Wang, Jia Li, and Gio Wiederhold, “SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture Libraries”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 9, pp. 947-963, Sept. 2001 Jianqing Liu and Yee-Hong Yang, “Multi-resolution color Image segmentation”, IEEE Transaction on Pattern Analysis and Machine Intelligence, 16(7), pp. 689-700, 1994 M. Borsotti, P. Campadelli, and R. Achettini, “Quantitative evaluation of color image segmentation results”, Pattern recognition letters, 19, pp.741-747, 1998 Hui Zhang, Jason Fritts, and Sally Goldman, “An Entropy-based Objective Evaluation Method for Image Segmentation”, Storage and Retrieval Methods and Applications for Multimedia. Proceedings of the SPIE, vol. 5307, pp. 38-49, 2003.


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图