Auto-focus algorithm based on maximum gradient and threshold

(1)

National Institute Of Technology Rourkela

Undergrad Thesis

Auto-Focus Algorithm Based On Maximum Gradient And Threshold

Submitted By:

Sumeet Mahapatra

Supervisor:

Prof. Ramesh Kumar Mohapatra

A thesis submitted in fulfilment of the requirements for the degree of Bachelor in Technology(B. Tech.)

in the

Computer Science Engineering National Institute Of Technology Rourkela

May 2014

(2)

Declaration of Authorship

I hereby declare that all the work contained in this report is my own work unless otherwise acknowledged. Also, all of my work has not been previously submitted for any academic degree. All sources of quoted information have been acknowledged by means of appropriate references.

Sumeet Mahapatra NIT Rourkela.

i

(3)

Certificate

This is to certify that the work in the project entitled Auto-Focus Algorithm Based On Maximum gradient And threshold by Sumeet Mahapatra is a record of their work carried out under my supervision and guidance in partial fulfilment of the requirements for the award of the degree of Bachelor of Technology in Computer Science and Engineering.

Prof. Ramesh Kumar Mohapatra Dept. of Computer Science and Engineering National Institute of Technology Rourkela Rourkela-769008

(4)

Acknowledgements

I have taken a lot of deliberations in this venture. But it wouldn’t have been been conceivable without the help and backing of numerous people. I want to enlarge my true appreciation and thank them.

I would like to express my humble regards to Prof Ramesh Kumar Mohapatra under whose supervision and guidance I completed my project. His consistent direction and eagerness to impart his unfathomable information made me comprehend this project and its appearances in incredible profundities.

I am highly obliged to all the professors of Department of Computer Science And En- gineering, NIT Rourkela for instilling in me the basic knowledge about the field that greatly benefitted me carrying out the project and achieving the goal.

Finally I want to express my sincere gratitude to my parents for their blessing, my frineds and comrades for their assistance and wishes for the fruitful fulfillment of the project.

Sumeet Mahapatra 110CS0133

Dept. of Computer Science and Engineering National Institute of Technology Rourkela

iii

(5)

Abstract

So as to conquer the disservices of the conventional auto-focus algorithm which are poor in real time performance, feeble in anti-noise capability and powerless against the impact of contrast and background pixels, here an auto-focus algorithm focused around greatest gradient and threshold is proposed. It presents an edge component and takes another sort of versatile threshold to evacuate the pixels sullied by noise and background in the picture, then uses enhanced Sobel operators to concentrate maximum gray gradient after picture pre processing and figures assessment esteem. The trial results demonstrate that the proposed algorithm has great continuous-execution, solid unimodality, high sensitivity and strong anti-noise capability. What’s more, the algorithm is less impacted by contrast and background in the picture. It can additionally control the sensitivity and focusing reach of the focusing function. So the proposed algorithm is most suitable for auto focus.

Keywords : Auto-focus, gradient, threshold, Sobel operators.

(6)

List of Figures

2.1 Flowchart of active auto-focus process . . . 6

2.2 Flowchart representation of auto-focus method . . . 6

4.1 Energy Gradient Graph . . . 13

4.2 brenner gradient graph . . . 13

4.3 Roberts’ gradient graph . . . 14

4.4 Variant gradient graph . . . 14

4.5 Max gradient and Thershold graph . . . 14

4.6 Table of Energy gradient graph . . . 15

4.7 Table of brenner gradient graph . . . 15

4.8 Table of Roberts’ gradient graph . . . 15

4.9 Table of Variant gradient graph . . . 16

4.10 Table of Max gradient and Thershold graph . . . 16

vii

(9)

Chapter 1

Introduction

1.1 WHAT IS DIGITAL IMAGE PROCESSING

An image is a two-dimensional function, f(a, b), where a and b are spatial directions and the amplitude of f at any pair of directions (a, b) is known as the intensity or gray level of the image at that point. At the point when a,b and the amplitude values of f are all limited, discrete amounts, we call the image a digital image. The most basic or essential unit of a digital image are known as pixels.

Advanced digital technology has made it conceivable to control multi-dimensional signals with frameworks that range from simple digital circuits to advanced parallel computers.

The objective of this control could be isolated into three classifications:

An image may be acknowledged to hold sub-images frequently alluded to as regions- of-interest or essentially regions. This idea reflects the way that images often at times hold accumulations of objects each of which might be the premise for a region. In a modern image handling framework it ought to be conceivable to apply particular image processing operations to selected region Along these lines a piece of an image (region) may be transformed to smother motion blur while an alternate part may be handled to enhance colour version.

Most more often than not, image processing frameworks oblige that the images be acces- sible in digitized structure, that is, .arrays of finite length binary words. For digitization, the given Image is examined on a discrete framework and each one example or pixel is quantized utilizing a limited number of bits. The digitized image is processed by a computer. To show a digital image, it is initially changed over into an analog signal, which is scanned onto a display.

The paradigm of digital image processing can be distinguished into three distinguished computer processes, namely:

1

(10)

Chapter 1. Introduction 2

Low- level procedures include primitive operations, for example, image pre processing to lessen noise, contrast improvement and image sharpening. A low level methodology is portrayed by the reality it has images as its input and output.

Mid- level processes on images involves tasks such as segmentation (partitioning an image into regions or objects). A mid-level processing is characterized by the fact that its input is image but its outputs are attributes created from these images.

High- level include ’understanding’ a group of perceived objects as in image dissec- tion, and at the most distant end of continuum performing the cognitive capacities typically connected with vision.

1.2 APPLICATIONS OF DIGITAL IMAGE PROCESS- ING:

Digital image processing methods have the following principle application regions:

Improvement of pictorial information for human interpretation

Processing of image data for storage, transmission and representation for au- tonomous machine perception.

Accurate calculation in an effective tracking application of an erratically moving object (shape, direction, speed are not constant) taking into account external factors.

Further classification of detected object (vehicle, human, animal, etc.) which involves a high level expertise in image processing

Detecting a threat in long range in advance and generate an alarm in order to allow the user time to take necessary measures requires precise image processing techniques. Using latest image processing techniques, images up to 3km distance can be detected.

Factors like snow and fog which tend to blur the image can be done away with by using elimination and fog elimination filters in image processing techniques.

Intelligent transport system and machine vision.

Forensic image processing and biomedical image processing.

Human-Computer interaction and knowledge extraction.

(11)

1.3 INTRODUCTION TO AUTO-FOCUS

An optical AF system uses a control system, sensor and a motor to fully focus automat- ically or on a manually selected point or region. An electronic range finder has a display instead of the motor; the adjustment of the optical system has to be done manually until indication. Autofocus methods are distinguished by their type active or passive or hybrid variant.

Auto-focus systems depend on one or more sensors to determine correct focus. Some AF frameworks depend on a solitary sensor, while others utilize an array of sensors.

Most advanced SLR cameras use through-the-viewpoint optical AF sensors, with a different sensor cluster giving light metering, in spite of the fact that the later could be customized to prioritize its metering to the same region as one or the more of the AF sensors.

Through-the-lens optical auto focusing is presently regularly speedier and more exact than might be attained physically with a common viewfinder, in spite of the fact that more exact manual focus could be accomplished with unique adornments, for example, focusing magnifiers.

Most of the multiple-sensor Auto Focus cameras allow manual choice of dynamic sensors, and numerous offer programmed determination of sensors utilizing algorithms which en- deavor to recognize the area of the object. Some Auto Focus cameras can locate when the object moves towards or far from the camera including velocity and acceleration information, and keep focus on objects

The information gathered from Auto Focus sensor are utilized to control an electrome- chanical system that adjusts the focus of the optical system. A variance of auto-focus is an electronicrangefinder, a system in which focus information are given to the operator, however modification of the optical system is still performed physically.

Auto-focus technology based on digital image processing is the key technology of digital imaging system. In recent years, auto-focus technology has been widely used in a variety of image acquisition and inspection equipments, such as cameras, video cameras, micro- scopes and scanners, and so on. In video monitoring and tracking system, the changes of the distance between moving target and camera will cause defocusing and imaging blurredly. The quality of target’s image within the field of view has a significant impact on identifying and tracking the target accurately. In order to acquire clear images of the target, it must be focusing in real time to meet the real-time monitoring and tracking requirements.

Auto-focus algorithm based on digital image processing can be divided into gray gradient function, gray entropy function and spectrum function. An accurate and effective focusing algorithm should have good unbias property, unimodality, real-time performance, sensitivity and anti-noise capability. Spectrum function is difficult to meet the real time

(12)

requirements because of a large amount of calculations. Entropy function is vulnerable to the external environment which will result in sensitivity reducing and focus point being misjudjed.

1.4 MOTIVATION

Autofocus system is one of the most important systems used in sophisticated and other digital cameras. The previous conventions for automating the focus were tedious and time taking. So there was a need to reduce the manual effort and improve the automation process of the focus of cameras.

1.5 OBJECTIVE

Designing an autofocus system will help to reduce the tedious and manual work needed.

It will also help in faster and quicker realization of focusing and defocusing of camera.

I will be emphasizing more on the implementation of the proposed algorithm so as to develop a better way of focusing the camera lens and adjustment of focus motor and zoom motor.

1.6 THESIS OUTLINE

This thesis is organized as follows. Chapter 2 discusses about the literature review while the proposed work is outlined in Chapter 3. Chapter 4 shows the implementation and results of the proposed work. Finally Chapter 5 concludes the entire thesis and gives a broad overview of the project.

(13)

Chapter 2

Literature Review

With the quick advancement of digital image processing technologies, the configuration of a purchaser-level advanced camera is aimed to present user-friendly cameras which mean to give simple approach to acquire fantastic imaging with insignificant client in- tervention in assignments, for example, Auto-Focus . The essential thought of AF is to supplant the dull procedure of manual focusing with programmed alteration of the lens of the camera to the correct place, guaranteeing the image is decently situated at the central plane . Auto Focus is an important component influencing the sharpness of a final captured image. It is focused around the way that an object in the picture shows up the most sharpened when it is in focus. Generally, image will be blurry if it is out of focus . In this way, the highest quality imaging is obtained in substantialsharpness part by how the lens is balanced by camera’s Auto Focus system to bring an image into focus where is augmented.

Many Auto Focus systems were developed in the past, which can be classified into two types of systems:

1. Active Auto Focus 2. Passive Auto Focus

2.1 ACTIVE AUTO FOCUS PROCESS:

When the active autofocus method starts, the camera sends patterns. After receiving the reflected patterns, the camera calculates the distance between the camera and the objective and adjusts the position of its lens accordingly. This type of AF needs sensors to send patterns and receive them, which in turn increases the space and cost of the camera. When the image is viewed through glass, the unwanted reflections gives wrong

5

(14)

Chapter 2. Literature Review 6

Figure 2.1: Flowchart of active auto-focus process

Figure 2.2: Flowchart representation of auto-focus method

readings. These erroneous readings can also be generated with too many objects near the main object.

2.2 PASSIVE AUTO-FOCUS PROCESS:

This autofocus action is monitored and controlled by the computer or the camera. The passive process consists of three different processes in it, namely focusing region selection,

(15)

sharpness measurement and AF peak value algorithm. A passive Auto Focus framework ordinarily works in an iterative way. Initially, an image is captured by the camera at the current lens position. Next, the focusing area determination system figures out which image captured is utilized for sharpness calculation. At that point, a sharpness estimation is connected to that focusing area to compute a fitness value. At last, a peak search step is performed to get the most maximum sharpness or best lens position from the fitness values.. This passive method would have trouble in lower light situation. If sharpness is being compromised then the solution is to change the threshold. The main problem with passive autofocus is to find an algorithm that is easy to compute and has good focus. The active type of autofocus methods is often faster than the passive type because of the more computation of the passive type.

2.3 CONVENTIONAL CONTINUOUS AF ALGORITHMS

At the initial stage, the course along which to search down an in-focus position is looked for by discovering the heading in which the sharpness measure processed by a low- recurrence BPF increments by means of a basic experimentation system. In the wake of choosing the direction, the next stage includes a coarse-to-fine hill-climbing search known as the hill-climb servo system to focus the in-focus position. The search rapidly moves over the hill utilizing the sharpness measure focused around a low recurrence BPF and afterward switches to a high-recurrence BPF for adjusting the coarsely evaluated position.

The pursuit typically starts by looking at sharpness in a little, focused centering area, as it is accepted that the fancied article is ordinarily put in the centre region. In the event that the search can’t discover a peak to focus utilizing the sharpness measure from the little area, it extends the area to a bigger, focused centering region. In the next stage, sharpness esteem at the in-focus position is analyzed against the reference value utilizing a limit Tvariation acquired at the end of the hill-climbing search with a specific end goal to figure out whether refocusing is essential.

There are numerous challenges that emerge when attempting to convey the traditional methods. Initially, the basic experimentation technique used to focus the direction of search could be effectively rejected because of noisy sharpness tests. Such an erroneous choice can prompt extended blur time which causes uneasiness for the client. Addition- ally, the customary hill-climbing search method system, which identifies a peak when there is a sign change in the contrast between the present and past sharpness qualities, is inclined to lapses because of noises.

Moreover, the accepted search strategy additionally yields conflicting focusing outcomes.

Think about the instance of different objects in a scene, which brings about various peaks

(16)

in the sharpness measure relating to diverse objects. In the event that the search was begun from far focus to close focus, then the camera might concentrate on the far object, and the other way around, since it stops at the first peak experienced. This conflict frequently prompts a wanted close object not being brought into focus. Yet an alternate weakness of the traditional systems is the utilization of a focused centering area. This does not permit focusing of off-focused articles and consequently does not help subject position as indicated by the guideline-of-thirds photography rules which serves to generate a satisfying image or video scene. The utilization of a bigger focusing object in circumstances where a peak can’t be found in a more modest area additionally causes more issues following in the bigger area, different sharpness peaks get predominant.

With no system to manage numerous peaks, the consequence of customary Auto Focus is hence rendered essentially non-compelling, particularly for zoom lens cameras.

2.4 SHARPNESS FUNCTION

Digital Cameras and smartphone cameras have an aloof AF characteristic that changes the focus motor position to accomplish a sharp picture without any client intercession. In passive Auto Focus, a focused picture is acquired by adjusting the separation between the image sensor and the lens utilizing the sharpness of caught images. AF focused around pixel process technique is a more adaptable and favoured innovation . It exploits the way that an object in an image shows up the most sharpened when it is overall focused. Overall, picture will be blurry in out of focus position. Focus functions is a quantitative portrayal of the picture sharpness in arithmetic The greatest quality of assessment function shows the focus region. On the off chance that the clarity evaluation function is applied to the focusing paradigm, the curve of image clarity evaluation function will have a solitary peak.. In passive Auto Focus, a measure of picture sharpness or a sharpness function is concentrated from captured images at diverse lens positions and after that the in-focus position is acquired by locating the sharpness function’s peak.

Auto Focus sharpness evaluation function’s principle is that high recurrence parts in focused images are more than that in defocused images of a scene. Sharpness evaluation function reflects the diverse levels of focus picture’s quality. The values ought to have the capacity to show tedious progressions with the area of the lens changes. The accompanying criteria are utilized as a part of the choice and assessment of the focus functions.

Unimodality:The focus function must be unimodal, only a single maximum or minimum should be present.

Accuracy: The extremum must be present when the system is in focus.

(17)

Reproducibility: A sharp top of the extremum results in good reproducibility.

General applicability: The focus functions must not be limited to some special type(s) of images;

Insensitivity to other parameters. If during the focus process other parameters change, the autofocus process should not be disturbed.

Implementation: The system must be easy to implement.

Auto-focus algorithm based on digital image processing can be divided into gray gradient function, gray entropy function and spectrum function . Spectrum function is difficult to meet the real time requirements because of a large amount of calculations. Entropy function is vulnerable to the external environment which will result in sensitivity reducing and focus point being misjudging . Gray gradient functions are simple calculation and easy realization.

2.5 GRAY GRADIENT FUNCTION

The focusing basis of gray gradient focusing algorithms is on the high frequency components of the image. When fully focused, the image is clearest and its high frequency components are richest. It means the image has the richest edges. But out-of-focus image is blur, which reflects the attenuation of the high frequency components in the frequency domain. It means the reduction of the edges’ information of the image. Gray gradient functions calculate the gradient of the image first, and then evaluate the clarity of the image via some kind of processing. Gray gradient functions are widely used because they are easy to realize and have good real-time performance. Several common shades of gray gradient evaluation functions are listed in the following.

suppose that W1, W2, W3, W4 are four forms of Sobel templates, which represent horizontal direction, vertical direction, positive 45-angle direction and negative 45-angle direction respectively

I(x,y) is a pixel of an image I. M and N represent height and width of the image respectively.

1) Energy Gradient Function F_Energy =P

x

P

y[I(x+ 1, y)−I(x, y)]²+ [I(x, y+ 1)−I(x, y)]² 2) Roberts Gradient Function

F_Rob=P

x

P

y[I(x+ 1, y+ 1)−I(x, y)]²+ [I(x+ 1, y)−I(x, y+ 1)]²

(18)

3) Brenner Gradient Function FBren=P

x

P

y[I(x+ 2, y)−I(x, y)]² 4) Variance Function

FBren=P

x

P

y[I(x+ 2, y)−µ]² µ= 1/M N[P

x

P

y[I(x+ 2, y)−µ]²]

Research shows that the traditional focusing algorithms’ realtime performance, sensitivity and anti-noise capability are still difficult to meet the requirements of video monitoring and tracking system. Therefore an auto-focus algorithm based on maximum gradient and threshold is proposed It acquaints two adaptive threshold parameters with lessen the impedance of noise and background pixels and utilization enhanced Sobel operators to extract the maximum gradient of the image to calculate evaluation values This algorithm can enhance AF effectiveness, reliability and real time performance.

(19)

Chapter 3

Proposed Work

First, the gradient direction of an image may be onedirection of positive 45-angle direction, negative 45-angledirection, horizontal direction or vertical direction. However, the traditional focusing functions only use somespecific directions while calculating gradient value. For example, Energy gradient function and Tenengrad function usethe gradient of the horizontal direction and vertical direction, Roberts gradient function uses the gradient of the positive 45-angle direction and negative 45-angle direction, and Brenner function only uses horizontal direction. However, when the real gradient direction is not in the specific direction selected, the evaluation value calculated will be inaccurate.

Second, noise introduced in the imaging process cannot be fully cleared, which has some effect on focusing function. In addition, the background pixels in the focusing area will not only increase the amount of calculation but also reduce focusing sensitivity and accuracy. An auto-focus algorithm based on maximum gradient and threshold is proposed to improve auto-focus real-time performance, sensitivity and antinoise capability. The algorithm takes adaptive threshold to weaken the influence of noise and background first, and then uses the maximum gradient to extract edges and calculate evaluation value.

3.1 MAXIMUM GRADIENT ALGORITHM

The Sobel operator has a certain amount of anti-noise capability. The four Sobel operators are used by the maximum gradient algorithm to find the maximum gradient direction which is assumed as the real gradient direction.

Maximum gradient algorithm can achieve the real image edge to improve focusing sensitivity.

G(x, y) =max(I(x, y)⊕w₁, I(x, y)⊕w₂, I(x, y)⊕w₃, I(x, y)⊕w₄) G(x,y) represents maximum gradient value of the pixel I(x,y).

11

(20)

Chapter 3. Proposed Work 12

3.2 THRESHOLD FUNCTION

Noise and background pixels have certain effect on unimodality, sensitivity, anti-noise capability of the focusing function and real-time performance. Threshold can be used to reduce these effects. The choice of threshold should be done properly. If the threshold is too large, it will remove the actual gradient of the target. If the threshold is too small, it can’t diminish the impact of noise and background pixels extremely well .

The adaptive global threshold of thek_thimage frame is T. T is equal toα T_k. Threshold factorαcontrols the sensitivity and focusing range of the focusing function. Then select the pixel I(x,y) as the center of the image window of 3*3 and calculate the variance of the image window as the local threshold.

3.3 CALCULATIONS STEPS OF THE PROPOSED AL- GORITHM

(1) The optimal threshold Tk of the kth image frame is obtained using the Otsu algorithm and then the global threshold T of the image is calculated,α represents threshold factor.

T =α T_k,α = [0,1]

(2) Choosing any pixel I(x, y) of the k_th image frame, except for the pixels in the first row, the first column, the last row and the last column, the mean and the variance of thew_th image window of 3*3 is calculated according to the following formula.

µ (x, y) represents the mean of the wth image window of 3*3. (3) Compare the values of σ_w²(x,y) and T. It does not regard I(x,y) as edge pixel and calculate its maximum gradient and evaluation value only when is greater than T. Otherwise it believes that the pixel’s gradient is caused by the interference of noise or background.

f(n) =

( G(x, y), if(σ²(x, y)> T) ifw= 1 (M −2)∗(N −2))

0 Else

(4) The evaluation value of the kth image frame is FVk . F V_k =P(M−2)∗(N−2)

w=1

(21)

Chapter 4

Implementation And Results

In this chapter the results are analysed. The various Gray Gradient functions were im- plemented and their corresponding results were found.

GRAPHS AND TABLES OF GRADIENT FUNCTION

Figure 4.1: Energy Gradient Graph

Figure 4.2: brenner gradient graph 13

(22)

Chapter 2. Implementation And Results 14

Figure 4.3: Roberts’ gradient graph

Figure 4.4: Variant gradient graph

Figure 4.5: Max gradient and Thershold graph

(23)

Figure 4.6: Table of Energy gradient graph

Figure 4.7: Table of brenner gradient graph

Figure 4.8: Table of Roberts’ gradient graph

(24)

Figure 4.9: Table of Variant gradient graph

Figure 4.10: Table of Max gradient and Thershold graph

(25)

Chapter 5

Conclusion

Images acquired by video motoring and tracking system have the following characteris- tics. First, images captured by CCD will always contain noise. Second, image contrast may be low due to the weather or other reasons. Third, image of the focusing area (including the monitor screen and the target area) may contain plenty of background pixels.

In addition, it requires the average processing time of the focusing function should be as less as possible to ensure real-time motoring and tracking. The experimental results show that the proposed algorithm has good real-time performance, strong unimodality, high sensitivity and strong anti-noise capability. It can adapt to the changes of the environmental contrast and the influence of background pixels in focusing area. More- over, the sensitivity and the focusing range can be controlled by selecting the value of threshold factor. So the proposed algorithm is suitable for auto-focus.

17

(26)

Bibliography

[1] Chunhong Mo, Bo Liu An Auto focus algorithm based on maximum gradient and threshold” 5th International Congress on Image and signal Processing(CISP 2012)

[2] Gao Zan Jiang, Wei Zhiu Kong-feng,Auto Focusing Algorithm based on most gradient and threshold ”, Journal of electron IC Measurement and instrument, vol 21, pp 49- 54 October 2007.

[3] LIANG Min-hua, WU Zhi-yong, CHEN Tao,Auto-focusing adjustment of theodolites by largest the gradient method,” Optics and Precision Engineering, vol. 17, pp. 3016- 3021, December 2009

[4] LIU Li-shuang , SUN Shuang-hua , L¨u Nai-guang, Study on theselection method of focusing function in vision system,” Journal of Beijing Institute of Machinery, vol.

23, pp. 1-4, December 2008.

[5] ZHAO Hui, BAO Ge-tang, TAO Wei, .Experimental research and analysis of auto- matic focusing function for imaging measurement, ”Optics and Precision Engineer- ing, vol. 12, pp. 531-536, October 2004.

[6] Jie He, Rongzhen Zhou, Zhiliang Hong. Modified Fast Climbing Search Auto-focus Algorithm with Adaptive Step Size Searching Technique for Digital Camera”, IEEE Trans. on Consumer Electronics, vol. 49, pp.257-262, May 2003.

[7] Kehtarnavaz N. and Oh H.-J.,Development and Real-Time Implementation of a Rule- Based Auto-Focus Algorithm,” Real-Time Imaging, vol. 9, issue 3, pp. 197-203, 2003.

18

Auto-focus algorithm based on maximum gradient and threshold

National Institute Of Technology Rourkela

Undergrad Thesis