The detection and recogni6on of a moving object in a sequence of time varying images proves to be a very important task in machine intelligence in general and computer vision in particular. Recently, parametric domain techniques have been successfully used with a number of variants. In such melhods, the image is transfonned into some parameter space and the motion detection process is applied in that space. A recent parametric domain is the Randomized Hough Transform (RHT) that uses random sampling mechanism in the image space, score accumulation in the parameter space, and bridge between them using a converging mapping. The use of such method for motion detection is called the Motion Detection Randomized Hough Transform (MDRHT). Since random sampling is used, the process of establishing correspondence between sets of points belonging to the same object in successive motion frames proves to be the most important problem in this methodology. Improving the accuracy of correspondence rules will improve the performance of the algorithm. In the present work, motion detection was considered through the analysis of a sequence

of time varying gay level image stream using the RHT algorithm that provides an efficient simple non-model based methodology using edge pixels as features. The objective of our work was to construct a set of correspondence rules that would maximize the ability of the methodology to detect motion parameters for both pure translational and pure rotational motions restricted to 2-D rigid objects. Analysis of accuracy and efficiency of correspondence were restricted to the cases of two points and three point pairs to select rules maximizing the performance. For that purpose, five different correspondence rules were investigated. The first three were 2-point rules that were used in previous researches. They measure correspondence through 2-point x-and y-differences, City Block distances and Euclidean distances, respectively. The present work introduced the two remaining rules for the first time. These are 3-point rules that measure correspondences through 3-point City Dlock distances and triangular areas, respectively. We have developed a mathematical analysis of the invariance of the five rules given for both pure translational and pure rotational motions. The analysis proved that the five

selected rules are invariant under pure translation while only rule (3) and rule (5) were invariant under pure rotation. In order to compare the performances of our randomized motion detection methodology for the different rules, a perfonnance parameter was introduced to measure the capability of peak detection in the RHT space. For translational motion, different simulation experiments were conducted with varying sizes of random samples. The results obtained for the translational motion indicated that our 3-point algorithms are in general superior to the previous 2-point algorithms. In particular, algorithm (5) that uses equal triangle areas gave the hjghest performance, outperforming the next in performance (2-point City Block distance) by a factor of almost 3 times. In order to study the affect of noise on the algorithms' performance, a salt and pepper noise with different levels was added to the frames images. The results for translational motion showed that algorithm (5) again has the performance which is three times better than other algorithms and proved to be robust against noisy conditions.

Different simulation experiments were also conducted for the case of pure rotational motion. The two algorithms that proved to be invariant under rotation (using correspondence rules 3 and 5) have been tested for different rotation angles using various numbers of trials NT. Also in this case, our 3-point algorithm proved to outperform the 2- point algorithm by a factor of almost 7 times. Similar conclusions are obtained for the robustness of algorithm (5) under varying angles of rotation, RHT spatial resolution, and correspondence tolerance.


School of Sciences and Engineering


Computer Science & Engineering Department

Degree Name

MS in Computer Science

Date of Award


Online Submission Date


First Advisor

Amr Goneid

Committee Member 1

Ahmed Sameh

Committee Member 2

Awad Khalil

Committee Member 3

Abdel Badei Salem

Document Type



131 leaves

Library of Congress Subject Heading 1

Computer vision


The American University in Cairo grants authors of theses and dissertations a maximum embargo period of two years from the date of submission, upon request. After the embargo elapses, these documents are made available publicly. If you are the author of this thesis or dissertation, and would like to request an exceptional extension of the embargo period, please write to thesisadmin@aucegypt.edu

Call Number

Thesis 2005/94