EE368: Digital Image ProcessingProject ReportIan [email protected] UniversityAbstract—An algorithm to detect and decode visual codemarkers in medium resolution images is presented. The algorithmuses adaptive methods to segment the image to identify objects.The objects are then used to form candidate markers which areexamined for several criteria. Potential markers are then sampledand guide information present in the marker is used to verifythe data. The algorithm is invariant to scale and rotation and isrobust to motion blur and varying illumination. The algorithmis implemented in C and takes approximately 100 ms to executeper image using a Pentium 4 3.40 GHz computer.I. INTRODUCTIONThe presence of cameras in cell phones is becoming ex-tremely commonplace as the price of inclusion plummets.As more and more people are equipped with these camerasit becomes feasible to develope a range of applications thatutilize the camera for purposes other than simply taking asnapshot. One such application is to use the camera to samplethe data contained in a visual code marker and to use this asa code to reference information. A typical use case might beto include a visual code marker next to the advertisment fora movie. By taking an image of the marker the phone candecode the data and then query a backend database for thelocal screening times of the movie.To achieve this type of application the camera must be ableto reliably identify and decode visual markers. This reportdetails the development and implementation of an algorithmthat can be used for this purpose. The report first analyses theproblem and establishes the requirements for the algorithm.It then examines the major steps of the algorithm and how itmeets the requirements. The results of testing the algorithmare discussed before the report concludes with a summary.II. ALGORITHM DESIGNBefore the design of the algorithm was started the problemwas analysed to develop some ideas about how the visualcode markers could be effectively detected and the issues thatwould need to be solved. Once a basic high level method wasestablished the lower level stages of the proposed algorithmwere designed and tested. The follow sections detail how theproblem was analysed and the resulting algorithm.A. Problem AnalysisFigure 1 shows the format of the visual code marker. Themarker is composed of an 11× 11 grid of binary elements. Thebinary elements are represented by a black square for a ‘1’ anda white square for ‘0’. The origin of the array is defined to bethe top left corner (that is, the corner opposite the intersectionof the guide bars) and the data is ordered in column majororder. The central region of the marker contains 83 bits of data.The remaining 38 bits are spaced at the corners and are usedto form guide elements. The guide elements consist of threecorner square elements and two guide bars. The guide barsare perpendicular to each other and are of different lengths. Inaddition to the 11×11 array the marker also has a white borderextending (at least) one element width around the array. Thisborder serves the same purpose as the border around barcodesand ensures that the marker is separate from any backgroundit is placed on.The image source is a digital image from a camera equippedcell phone. The image is of VGA resolution (640 × 480)and provided as a compressed 8-bit RGB JPEG file. Thecompression ratio is approximately 18:1. This resolution iscomparatively low but it is of course definately adequate tosample and extract the data from the markers under the rightconditions. Of more importance are the conditions under whichthe image is obtained. Specifically, the camera is most likelyto be handheld, leading to a degree of motion blur, and to bepositioned somewhat haphazardly, leading to arbitrary trans-formations in angle, translation and perspective. Furthermore,the lighting conditions are not controlled and it is possiblethat the illumination will not be constant over the image anddefinately not between images. The high contrast between thebinary elements (black vs. white) will help to differentiate thebinary values under a wide range of lighting conditions. Themarker is likely to be a small fraction of the total image data.It is expected that the marker will be approximately between100 × 100 and 150 × 150 pixels. As part of the project briefthe image may contain one to three markers in an image.Although it may be possible to find the location of markersby perhaps looking for mixed dark/light regions it is essentialthat the guide elements be used to orient the marker. Correctorientation is required so that the data can be read in ameaningful way. The provision of the perpendicular guide barsallows the detection of any rotation of the marker. In addition,if necessary, the observed change in the 90oangle could beused to estimate the perspective of the camera view, openingup the possibility of rectifying the image. The corner guideelements can be used to accurately determine the extent of themarker. This will be particularly important when the viewingperspective distorts the shape of the marker.This analysis has shown that the algorithm must be able todetect and orient multiple code markers located anywhere inthe image. It must be robust enough to cope with rotation,perspective, motion blur and variations in illumination andsize. It has also been shown that the marker contains structureand other design aspects to help overcome these issues.guide sectionsblank spacedatahigh contrastFig. 1. Analysis of the visual code marker.B. Dectection AlgorithmThe development of the algorithm is based on the idea thatthe guide bar pair is the key element that can be used toidentify marker candidates in an image. Once potential guidebar pairs are identified the incorrect candidates can be filteredout by looking at other characteristics of the marker. Thisprimarily includes finding the three corner guide elements insensible locations relative to the guide bar pair. In addition,for any marker that is sampled the correct guide ‘data’ canbe compared against what is expected to further remove falsepositives.The general idea of the algorithm is that aims to have a highdetection rate and then to apply a set of loose filters to prunethe number of candidates to a sensible number. Typically anumber of false positives are sampled but the final verificationof the guide bits is used to (hopefully) eliminate these.The main steps of the detection