{"id":3024,"date":"2019-10-08T16:36:22","date_gmt":"2019-10-08T23:36:22","guid":{"rendered":"http:\/\/blogs.oregonstate.edu\/gemmlab\/?p=3024"},"modified":"2020-09-16T16:40:37","modified_gmt":"2020-09-16T23:40:37","slug":"demystifying-the-algorithm","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/gemmlab\/2019\/10\/08\/demystifying-the-algorithm\/","title":{"rendered":"Demystifying the algorithm"},"content":{"rendered":"\n

By Clara Bird, Masters Student, OSU Department of Fisheries and Wildlife, Geospatial Ecology of Marine Megafauna Lab<\/strong><\/p>\n\n\n\n

Hi everyone! My name is Clara Bird<\/a> and I am\nthe newest graduate student in the GEMM lab. For my master\u2019s thesis I will be\nusing drone footage of gray whales to study their foraging ecology. I promise\nto talk about how cool gray whales in a following blog post, but for my first effort\nI am choosing to write about something that I have wanted to explain for a\nwhile: algorithms. As part of previous research projects, I developed a few semi-automated\nimage analysis algorithms and I have always struggled with that jargon-filled\nphrase. I remember being intimidated by the term algorithm and thinking that I\nwould never be able to develop one. So, for my first blog I thought that I\nwould break down what goes into image analysis algorithms and demystify a term\nthat is often thrown around but not well explained.<\/p>\n\n\n\n

What is an algorithm?<\/strong><\/p>\n\n\n\n

The dictionary broadly defines an\nalgorithm as \u201ca step-by-step procedure for solving a problem or accomplishing\nsome end\u201d (Merriam-Webster). Imagine an algorithm as a flow chart (Fig. 1), where\neach step is some process that is applied to the input(s) to get the desired\noutput. In image analysis the output is usually isolated sections of the image\nthat represent a specific feature; for example, isolating and counting the\nnumber of penguins in an image. Algorithm development involves figuring out\nwhich processes to use in order to consistently get desired results. I have\nconducted image analysis previously and these processes typically involve figuring\nout how to find a certain cutoff value. But, before I go too far down that\nroad, let\u2019s break down an image and the characteristics that are important for\nimage analysis.<\/p>\n\n\n\n

\"\"
Figure 1. An example of a basic algorithm flow chart. There are two inputs: variables A and B. The process is the calculation of the mean of the two variables.<\/figcaption><\/figure>\n\n\n\n

What is an image?<\/strong><\/p>\n\n\n\n

Think of an image as a spread sheet,\nwhere each cell is a pixel and each pixel is assigned a value (Fig. 2). Each\nvalue is associated with a color and when the sheet is zoomed out and viewed as\na whole, the image comes together.  In\ncolor imagery, which is also referred to as RGB, each pixel is associated with\nthe values of the three color bands (red, green, and blue) that make up that\ncolor. In a thermal image, each pixel\u2019s value is a temperature value. Thinking\nabout an image as a grid of values is helpful to understand the challenge of\ntranslating the larger patterns we see into something the computer can interpret.\nIn image analysis this process can involve using the values of the pixels\nthemselves or the relationships between the values of neighboring pixels. <\/p>\n\n\n\n

\"\"
Figure 2. A diagram illustrating how pixels make up an image. Each pixel is a grid cell associated with certain values. Image Source: https:\/\/web.stanford.edu\/class\/cs101\/image-1-introduction.html<\/a><\/figcaption><\/figure>\n\n\n\n

Our brains take in the whole\npicture at once and we are good at identifying the objects and patterns in an\nimage. Take Figure 3 for example: an astute human eye and brain can isolate and\nidentify all the different markings and scars on the fluke. Yet, this process\nwould be very time consuming. The trick to building an algorithm to conduct\nthis work is figuring out what processes or tools are needed to get a computer\nto recognize what is marking and what is not. This iterative process is the algorithm\ndevelopment.<\/p>\n\n\n\n

\"\"
Figure 3. Photo ID image of a gray whale fluke.<\/figcaption><\/figure>\n\n\n\n

Development<\/strong><\/p>\n\n\n\n

An image analysis algorithm will\ntypically involve some sort of thresholding. Thresholds are used to classify an\nimage into groups of pixels that represent different characteristics. A\nthreshold could be applied to the image in Figure 3 to separate the white color\nof the markings on the fluke from the darker colors in the rest of the image.\nHowever, this is an oversimplification, because while it would be pretty simple\nto examine the pixel values of this image and pick a threshold by hand, this threshold\nwould not be applicable to other images. If a whale in another image is a\nlighter color or the image is brighter, the pixel values would be different\nenough from those in the previous image for the threshold to inaccurately\nclassify the image. This problem is why a lot of image analysis algorithm\ndevelopment involves creating parameterized processes that can calculate the\nappropriate threshold for each image.<\/p>\n\n\n\n

One successful method used to\ndetermine thresholds in images is to first calculate the frequency of color in\neach image, and then apply the appropriate threshold. Fletcher et al. (2009)\ndeveloped a semiautomated algorithm to detect scars in seagrass beds from\naerial imagery by applying an equation to a histogram of the values in each\nimage to calculate the threshold. A histogram is a plot of the frequency of\nvalues binned into groups (Fig. 4). Essentially, it shows how many times each value\nappears in an image. This information can be used to define breaks between\ngroups of values. If the image of the fluke were transformed to a gray scale, then\nthe values of the marking pixels would be grouped around the value for white\nand the other pixels would group closer to black, similar to what is shown in\nFigure 4. An equation can be written that takes this frequency information and\ncalculates where the break is between the groups. Since this method calculates\nan individualized threshold for each image, it\u2019s a more reliable method for\nimage analysis. Other characteristics could also be used to further filter the\nimage, such as shape or area.<\/p>\n\n\n\n

However, that approach is not the\nonly way to make an algorithm applicable to different images; semi-automation\ncan also be helpful. Semi-automation involves some kind of user input. After\nuploading the image for analysis, the user could also provide the threshold, or\nthe user could crop the image so that only the important components were maintained.\nKeeping with the fluke example, the user could crop the image so that it was\nonly of the fluke. This would help reduce the variety of colors in the image\nand make it easier to distinguish between dark whale and light marking.<\/p>\n\n\n\n

\"\"
Figure 4. Example histogram of pixel values. Source: Moallem et al. 2012<\/figcaption><\/figure>\n\n\n\n

Why algorithms are important<\/strong><\/p>\n\n\n\n

Algorithms are helpful because they\nmake our lives easier. While it would be possible for an analyst to identify\nand digitize each individual marking from a picture of a gray whale, it would\nbe extremely time consuming and tedious. Image analysis algorithms significantly\nreduce the time it takes to process imagery. A semi-automated algorithm that I\ndeveloped to count penguins from still drone imagery can count all the penguins\non a one km2<\/sup> island in about 30 minutes, while it took me 24 long hours\nto count them by hand (Bird et al. in prep<\/em>). Furthermore, the process\ncan be repeated with different imagery and analysts as part of a time series\nwithout bias because the algorithm eliminates human error introduced by\ndifferent analysts.<\/p>\n\n\n\n

Whether it\u2019s a simple combination\nof a few processes or a complex series of equations, creating an algorithm requires\nbreaking down a task to its most basic components. Development involves\ntranslating those components step by step into an automated process, which after\nmany trials and errors, achieves the desired result. My first algorithm project\ntook two years of revising, improving, and countless trials and errors.  So, whether creating an algorithm or working\nto understand one, don\u2019t let the jargon nor the endless trials and errors stop\nyou. Like most things in life, the key is to have patience and take it one step\nat a time.<\/p>\n\n\n\n

References<\/strong><\/p>\n\n\n\n

Bird, C. N., Johnston, D.W., Dale, J. (in prep<\/em>).\nAutomated counting of Adelie penguins (Pygoscelis adeliae) on Avian and\nTorgersen Island off the Western Antarctic Peninsula using Thermal and\nMultispectral Imagery. Manuscript in preparation <\/em><\/p>\n\n\n\n

\ufeffFletcher, R. S., Pulich, W. \u2021, & Hardegree, B. (2009). A Semiautomated Approach for Monitoring Landscape Changes in Texas Seagrass Beds from Aerial Photography. https:\/\/doi.org\/10.2112\/07-0882.1<\/a> <\/p>\n\n\n\n

Moallem, Payman & Razmjooy, Navid. (2012). Optimal Threshold Computing in Automatic Image Thresholding using Adaptive Particle Swarm Optimization. Journal of Applied Research and Technology. 703. <\/p>\n\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

By Clara Bird, Masters Student, OSU Department of Fisheries and Wildlife, Geospatial Ecology of Marine Megafauna Lab Hi everyone! My name is Clara Bird and I am the newest graduate student in the GEMM lab. For my master\u2019s thesis I will be using drone footage of gray whales to study their foraging ecology. I promise … Continue reading Demystifying the algorithm<\/span><\/a><\/p>\n","protected":false},"author":9938,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[188686,1],"tags":[187573,1061,712928,635445,1237698,513,1185187,1237678,142],"class_list":["post-3024","post","type-post","status-publish","format-standard","hentry","category-current-projects","category-uncategorized","tag-algorithms","tag-analysis","tag-analytical-processes","tag-gemm-lab","tag-geospatial-analysis","tag-marine-mammals","tag-marine-megafauna","tag-technologies","tag-technology"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/posts\/3024","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/users\/9938"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/comments?post=3024"}],"version-history":[{"count":3,"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/posts\/3024\/revisions"}],"predecessor-version":[{"id":3031,"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/posts\/3024\/revisions\/3031"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/media?parent=3024"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/categories?post=3024"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/gemmlab\/wp-json\/wp\/v2\/tags?post=3024"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}