FastAlgorithmforRobustTemplateMatching.pdf资源-CSDN文库

版权申诉

92 浏览量 2022-05-10 22:29:52 上传评论收藏 928KB PDF 举报

资源详情

资源评论

230 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 51, NO. 1, JANUARY 2003

Fast Algorithm for Robust Template Matching

With M-Estimators

Jiun-Hung Chen, Chu-Song Chen, and Yong-Sheng Chen

Abstract—In this paper, we propose a fast algorithm for

speeding up the process of template matching that uses M-esti-

mators for dealing with outliers. We propose a particular image

hierarchy called the

-pyramid that can be exploited to generate

a list of ascending lower bounds of the minimal matching errors

when a nondecreasing robust error measure is adopted. Then,

the set of lower bounds can be used to prune the search of the

-pyramid, and a fast algorithm is thereby developed in this

paper. This fast algorithm ensures finding the global minimum of

the robust template matching problem in which a nondecreasing

M-estimator serves as an error measure. Experimental results

demonstrate the effectiveness of our method.

Index Terms—Fast algorithm, M-estimator, robust template

matching, template matching.

I. INTRODUCTION

INDING a pattern or template in a signal is an important

problem for signal and image processing. This so-called

template matching can be applied to many applications such

as image and video coding, pattern recognition, and visual

tracking. It is usually assumed in template matching that the

signal segments of interests do not change their appearances

very much. Hence, template matching based on the criteria

such as the sum of absolute difference (SAD) or the sum of

squared difference (SSD) is commonly adopted. The popularity

of using template matching for applications of signal or image

processing is mainly due to its ease of implementation together

with the many fast algorithms that can be used to speed up the

matching process for various applications [1], [7], [8], [13],

[15], [22], [25], [26], [28], [29], [35], [39].

In a cluttered environment, however, some outliers such

as impulse noises or partial occlusions may occur during

the matching processes. In this situation, the SAD and SSD

criteria are no longer suitable for template matching because

they treat the outliers and inliers evenly when calculating the

error measures. One possible remedy for this weakness is to

use a robust criterion instead of SAD or SSD. For this, the

M-estimator technique [2], [16], [30], [38] is one of the most

popular methods to solve the problem of robust parameter

estimation and has been applied in many studies [3]–[5],

Manuscript received October 17, 2001; revised August 14, 2002. This work

was supported in part by the National Science Council of Taiwan, R.O.C., under

Grants NSC 90-2213-E-001-033 and NSC91-2213-E-001-022. The associate

editor coordinating the review of this paper and approving it for publication

was Dr. Xiang-Gen Xia.

J.-H. Chen and C.-S. Chen are with the Institute of Information Science,

Academia Sinica, Taipei, Taiwan, R.O.C. (e-mail: song@iis.sinica.edu.tw).

Y.-S. Chen is with the Integrated Brain Research Laboratory, Department

Medical Research and Education, Taipei Veterans General Hospital, Taipei,

Taiwan, R.O.C.

Digital Object Identifier 10.1109/TSP.2002.806551

[11], [12], [14], [23], [31]–[33], [36]. The basic idea of the

M-estimator technique is to limit the influence of outliers in

the matching error. In principle, the effects of the outlier can be

suppressed with the M-estimator technique and therefore better

estimations are obtained.

A typical procedure for finding solutions with M-estimators

is the iterative-reweight procedure [30]. In each iteration of this

procedure, a weighted least-square problem is solved and then

the weights are adjusted for the next iteration for further refine-

ment. Hence, when applying the iterative-reweight procedure

for robust template matching, in each iteration, another template

matching problem must be solved based on a weighted SSD

error measure, in addition to which, multiple iterations are also

necessary. Therefore, the computation of robust error measures

is very time-consuming, although more accurate results can be

obtainedbyadopting a robusterrormeasureinsteadofnonrobust

ones.

In the past, many methods have been proposed to speed

up the matching process where the simple SAD or SSD criterion

is used. However, to our knowledge, no method has been ad-

dressed for speeding up the process of template matching where

robust error measures are used. In this paper, we propose a fast

method for solving this problem. We will present this method by

assuming that a two-dimensional (2-D) signal (e.g., an image) is

used. Nevertheless, our algorithm can be easily generalized for

any

-dimensional signal .

On the other hand, there are already many methods for

speeding up the process of template matching where nonrobust

error measures are used. These methods can be divided into

two classes. The methods in the first class only find a local

minimum while the ones in the second class definitely find

the global minimum. In principle, almost all the methods in

the first class formulate the template matching as a search

problem and find a solution by adopting the greedy strategy.

Examples include the three-step search algorithm [22], the

gradient-descent based method [29] and others [1], [8], [13],

[15], [28], [35], [39]. The genetic algorithm-based methods [8],

[28] or the simulated annealing-based method [35] may have

chances of finding the global minimum if their parameters are

set appropriately to the given problems, but can not ensure that

it will always be found. In essence, since these methods do

not guarantee finding the global minimum, they are generally

faster than those ensuring the global optimality.

The methods in the second class guarantee finding the global

minimum, and the main idea of this class is basically prune

and search [7], [25], [26]. Hence, the main issue of this class of

approaches is on how to design the search strategies for pruning

Another problem of the iterative-reweight procedure is that it can not defi-

nitely find the global optimum.

CHEN et al.: FAST ALGORITHM FOR ROBUST TEMPLATE MATCHING WITH M-ESTIMATORS 231

unnecessary searching branches. The successive elimination

algorithm proposed by Li and Salari [26] eliminates impossible

sites successively during the searching process by using lower

bounds derived from the triangle inequality. Their method can

guarantee obtaining the global minimum, as does the full search

(FS) method, and it is more efficient. In [25], Lee and Chen ex-

tendedthisideabyusing ablock-sum-pyramidstructure,wherea

set of ascending lower bounds can be derivedand serve as useful

guidelinestoprunethesearchprocess.However,theperformance

oftheir method dependsonthe searchorder. Recently,Chenetal.

further refined it by using a winner-update strategy [7], which is

not only irrelevant to the search order butis also faster.

Similar to those methods that ensure finding the global min-

imum but using nonrobust error measures introduced above [7],

[25], [26], the method developed in this paper also adopts an in-

equality in a particular image hierarchy to speed up the template-

matching process with robust error measures. In essence, a set

of ascending lower bounds of the minimal matching error can be

generated with our method as long as the robust error measure is

nondecreasing. This set of lower bounds can then serve as useful

guidelines for pruning the redundant branches of the searching

process. In addition, our method can ensure finding the global

minimum, as the FS method does for robust template matching.

This paper is organized as follows. Section II introduces the

image hierarchy used in this work and the associated ascending

lower bound list. Section III presents the search strategies and

our main algorithm. Section IV shows some experimental re-

sults. Finally, some discussion and conclusions are given in Sec-

tions V and VI, respectively.

II. P

ROBLEM FORMULATION, -PYRAMID,

AND FUNDAMENTAL INEQUALITY

A. Problem Formulation

We denote

as the intensity at position in an

image

. Assume that and are images. The sum

of robust differences (SRD) between two images

and is

defined as follows:

SRD

(1)

where

: is a robust error

measure (or a robust loss function) [2], [16], [38], and

is a

parameter controlling the shape of

Typically, the robust

error measure,

, is selected according to how it reduces the

influences of outliers. Given an image template

whose size is

and an image whose size is ,

the robust template matching problem is defined as finding the

position (

, ) with the minimum SRD among all possible

search positions in the image

SRD

(2)

Some common robust error measures will be introduced in Section II-E. In

particular, if



(

x; 

(or

) for all



, then (1) becomes SSD (or SAD).

where is an image block with its upper-left point

being

in the image , and the number of search sites is

B. P-Feasible

To simplify the notation of the robust error measures, we de-

fine

for all (3)

and abbreviate

to be for the cases without ambiguity

in the following.

Definition 1 [

-Feasible]: A robust error measure is

-feasible if it satisfies both the following two conditions.

is nondecreasing, i.e., implies

for all .

2) For each pair of nonnegative values

, the fol-

lowing inequality with respect to the

-norm holds:

(4)

where

is a 2-D vector, and

is the -norm of , . In particular,

Some properties associated with the

-feasible defined above

are investigated in the following.

Property 1: Every nondecreasing

is -feasible.

Proof: This property can be easily derived according to

the definitions.

Property 2: If a robust error measure

is -feasible, that

implies it is also

-feasible for all .

Proof: See Appendix A.

If a

-feasible robust error measure is used as the matching

criterion, an ascending lower bound list of the matching errors

can be obtained by constructing an image pyramid with respect

to the

-norm, as described in the following.

-Pyramid and Fundamental Inequality

Assume that

. For each image

block

that is contained in

the image

,a -pyramid of is defined as a set of images

, where and

the size of

is .

is referred to as the image on the level of the -pyramid.

Level 0 and level

are called the highest and the lowest levels of

the

-pyramid, respectively. Given an image on the level

, the image on the level is constructed using

the following equation:

(5)

where

and

Accordingly, the pyramids from level to level 0 can be con-

structed iteratively. Totally,

-pyramids

are constructed from the image

. Fig. 1 shows an illustration of

the pyramids constructed from a one–dimensional (1-D) signal.

Following the notions shown in (1), we define the SRD

between

and on the level by SRD

232 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 51, NO. 1, JANUARY 2003

SRD for . Furthermore,

we denote SRD

SRD if a fixed is

considered [where

is defined in (3)]. Then, it can be shown

that the following fundamental inequality holds for the image

hierarchy defined above.

Theorem 1: Given a robust error measure

that is -fea-

sible, then for all

, ,

SRD

SRD SRD

(6)

Proof: See Appendix B.

Hence, given a image template

and an image block

, a set of ascending lower bounds,

SRD

, can be obtained ac-

cording to Theorem 1.

Notice that the number of robust differences involved in

the computation of each lower bound SRD

is , which is smaller than , the

number of robust differences required forSRD

Therefore, the lower bounds can be computed more efficiently

than the sum of robust differences with respect to the original

image. In particular, the higher are the levels in a pyramid, the

faster are the computations of the associated lower bounds.

In fact, the ratio of the required number of the computations

of the robust differences on the level

to that required for

the level

is . Accordingly, even when all of the

lower bounds are computed, the required time is less than

of that required for the level , the

original image block. Such an ascending lower bound list of

the matching error can be used for speeding up the matching

process by incorporating it into a systematic search strategy, as

introduced in Section III.

Remark 1 [Efficient Construction of the

-Pyramids of an

Image]: A

-pyramid of each image block can be constructed

independently by using (5). However, it is very time-con-

suming if each pyramid is constructed independently. In

fact, the

-pyramids can be constructed more efficiently by

considering the computation and storage redundancies between

neighboring image blocks when constructing and storing the

-pyramids. We introduce this method by using an example, as

shown in Fig. 1. Considering node

in the first level image

of Pyramid 1, as shown in Fig. 1, one can observe that node

is also contained in Pyramid 3. Similarly, node B (or C) is

shared by Pyramids 2 and 4 (or Pyramids 3 and 5). Hence, if

each pyramid is constructed independently according to (5),

the values of nodes A, B, and C will be computed twice: once

for each pyramid. In our work, to remove this redundancy

and to save computation and storage of the

-pyramids for all

the image blocks, the method illustrated in Fig. 1 is adopted.

That is,

, the image containing every node of the first-level

images of all the pyramids, is first constructed based on

Similarly,

can be constructed based on . After and

are constructed, all the pyramids are then available, as shown

in Fig. 1. More details about efficient construction of pyramids

can be found in [7].

Remark 2 [Free Sampling]: Intheabovedescription,apartic-

ular level of the

-pyramid is built with the -norm of the 2 2

Fig. 1.

-pyramid constructed from a 1-D signal where each element in higher

levels is composed of its two son elements. Five

-pyramidsare depicted in solid

or dashed lines. The three black nodes are the ones that are shared between two

pyramids.

pointsfromitslowerneighborlevel,asshownin(5).We refertoit

asthe2–2downsamplinginthiscase.Ingeneral,wecanuse

–

downsamplinginstead of 2–2 downsamplingfor all , ,

and the associated

-pyramid can be reconstructed in a similar

way as well. Similarly,

downsampling can be used for a 1-D

signaland

– – downsamplingcan beusedforathree–dimen-

sional (3-D) signal, and so on, where

D. Characterization of

-Feasible Robust Error Measures

In Section II-C, we have shownthat if a

-feasible robust error

measure is selected for template matching, then we can con-

struct an ascending lower bound list associated with a particular

image hierarchy: the

-pyramid. Before introducing the search

procedure that exploits the series of lower bounds in detail, we

illustrate an important issue about whether such a lower-bound

list can be constructed. In particular, the following problem is

worthy of being addressed.

“Given a robust error measure

, under what condi-

tion can it be ensured that we can always find a

such that is -feasible?”

In this paper, we tackle this problem in consideration of the

class of nondecreasing robust error measures. In fact, Property

1 has shown that if a robust error measure is nondecreasing, it is

-feasible. Therefore, when the -pyramids are built for both

the template and the image blocks, an ascending lower bound

list can then be constructed according to Theorem 1. Hence, it

ensures that every nondecreasing robust error measure is

-fea-

sible for some

because is a trivial solution.

In addition

, let us further investigate the other values that allow

a robust error measure to be

-feasible. Given a nondecreasing

robust error measure,

, let , which is the feasible set asso-

ciated with

, be defined as the set of values allowing to be

-feasible: is -feasible . By considering

the maximal lower bound of

, the following property can be

derived.

Property 3: Given a

that is nondecreasing, there exists

a discriminative value

such that is -feasible for all

and is not -feasible for all , where is the

maximal lower bound of

, which is the feasible set associated

with

How to construct a list of ascending lower bounds for the general class of

robust error measures that are not necessary to be nondecreasing remains an

open problem.

剩余13页未读，继续阅读

评论收藏

内容反馈

版权申诉

Fast Algorithm for Robust Template Matching.pdf

评论0

最新资源

Fast Algorithm for Robust Template Matching.pdf

评论0

最新资源

相关推荐

Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector.pdf

An Approximate Message Passing Algorithm for robust face recognition.pdf

Edge Based Template Matching.pdf

Maximum Matching Algorithm.pdf

【2】A fast learning algorithm for deep belief nets.pdf

AN EFFICIENT PARALLEL ALGORITHM FOR SKEIN HASH FUNCTIONS.pdf

Algorithm-map_matching.zip

A Distributed Geo-Routing Algorithm for Wireless Sensor Networks.pdf

A Fast ICP Algorithm for 3-D.pdf

论文研究-A Fast Greedy Algorithm for Outlier Mining.pdf

A Robust Algorithm for Portfolio.pdf

A fast learning algorithm for deep belief nets.pdf

A Fast Bacterial Swarming Algorithm for high-dimensional .pdf

An Algorithm for Vector Quantizer Design.pdf

A fast learning algorithm for deep belief nets.rar

Algorithm-texas_algorithm.zip

An improved ant colony algorithm for robot path planning.pdf

A Parallel Algorithm for Polygon Rasterization.pdf

A Decentralized Reconstruction Algorithm for Distributed Compressed Sensing.pdf

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

李飞飞自传 我看见的世界 The World I see

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

4个亲测好用的ChatGPT4渠道

农村公交与异构无人机协同配送优化

学术海报模板+论文科研+研究生

李飞飞自传我看见的世界 The World I see