{"cells":[{"metadata":{},"cell_type":"markdown","source":"![](https://miro.medium.com/max/1200/1*VXZ8CamGG2Z0M0N4t0Fmng.jpeg)","execution_count":null},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","collapsed":true},"cell_type":"markdown","source":"# Object Detection : Historical Perspective \n## Some Object Detection History (2001-2017)\n\n### 1. The first efficient Face Detector (Viola-Jones Algorithm, 2001)\n\n- An efficient algorithm for face detection was invented by Paul Viola & Michael Jones \n- Their demo showed faces being detected in real time on a webcam feed.\n- Was the most stunning demonstration of computer vision and its potential at the time. \n- Soon, it was implemented in OpenCV & face detection became synonymous with Viola and Jones algorithm.\n- __BASIC IDEA__: \n    1. Took a bunch of faces as data. \n    2. Hard-coded the features of a face.\n    3. Trained an SVM(Classifier) on the featureset of the faces.\n    4. Used that Classifier to detect faces!\n\n![alt text](https://www.researchgate.net/profile/Salah_Eddine_Bekhouche/publication/275043966/figure/fig2/AS:294542428393474@1447235795083/Fig-2-The-proposed-approach-a-Viola-Jones-algorithm-b-Active-Shape-Models-with.png \"Logo Title Text 1\")\n\n![alt text](https://ars.els-cdn.com/content/image/1-s2.0-S2468067216300116-gr1.jpg \"Logo Title Text 1\")\n\n- __*Disadvantage*__ : It was unable to detect faces in other orientation or configurations (tilted,upside down,wearing a mask,etc.) \n\n---\n\n### 2. Much more efficient detection technique (Histograms of Oriented Gradients, 2005)\n\n- Navneet Dalal and Bill Triggs invented \"HOG\" for pedestrian detection\n- Their feature descriptor, Histograms of Oriented Gradients (HOG), significantly outperformed existing algorithms in this task\n- Handcoded features, just like before\n\n- For every single pixel, we want to look at the pixels that directly surrounding it:\n\n![Alt Text](https://cdn-images-1.medium.com/max/1440/1*RZS05e_5XXQdofdRx1GvPA.gif)\n\n- Goal is, how dark is current pixel compared to surrounding pixels?\n- We will then draw an arrow showing in which direction the image is getting darker:\n\n![Alt Text](https://cdn-images-1.medium.com/max/1440/1*WF54tQnH1Hgpoqk-Vtf9Lg.gif)\n\n- We repeat that process for every single pixel in the image\n- Every pixel is replaced by an arrow. These arrows are called gradients\n- Gradients show the flow from light to dark across the entire image:\n\n![Alt Text](https://cdn-images-1.medium.com/max/1440/1*oTdaElx_M-_z9c_iAwwqcw.gif)\n\n- We'll break up the image into small squares of 16x16 pixels each\n- In each square, we’ll count up how many gradients point in each major direction\n- Then we’ll replace that square in the image with the arrow directions that were the strongest.\n- End result? Original image converted into simple representation that captures basic structure of a face in a simple way:\n- Detecting faces means find the part of our image that looks the most similar to a known HOG pattern that was extracted from a bunch of other training faces:\n\n![Alt Text](https://cdn-images-1.medium.com/max/1440/1*6xgev0r-qn4oR88FrW6fiA.png)\n\n- __BASIC IDEA__ : \n    1. For an Image $I$, analyze each pixel $P_{i}$ of $I$ for the relative dark pixels directly surounding it.\n    2. Then add an arrow pointing in the direction of the flow of darkness relative to $P_{i}$.\n    3. This process of assigning an oriented gradient to a pixel __p__ by analyzing it's surrounding pixels is performed for every pixel in the image.\n    4. Assuming __HOG($I$)__ as a function that takes an input as an Image __I__, what it does is replaces every pixel with an arrow. Arrows = Gradients. Gradients show the flow from light to dark across an antire image.\n    5. Since complex feaatures like eyes may end up giving too many gradients, we need to aggregate the whole __HOG(I)__ in order to make a *'global representation'* . \n    So, we break up the image into squares of $16$x$16$ and assign an aggregate gradient $G'$ to each square ,where the aggregate function could be _max(All gradients inside the square)_,_min()_,etc. \n\n\n- __*Disadvantage*__ : Despite being good in many applications, it still used hand coded features which failed in a more generalized setting with much noise and distractions in the background.\n    \n ---\n\n### The Deep Learning Era begins (2012)\n\n- Convolutional Neural Networks became the gold standard for image classification after Kriszhevsky's CNN's performance during ImageNet\n\n![Alt Text](https://image.slidesharecdn.com/cnn-toupload-final-151117124948-lva1-app6892/95/convolutional-neural-networks-cnn-65-638.jpg?cb=1455889178)\n\nWhile these results are impressive, image classification is far simpler than the complexity and diversity of true human visual understanding.\n\n![Alt Text](https://cdn-images-1.medium.com/max/1600/1*bGTawFxQwzc5yV1_szDrwQ.png)\n\nIn classification, there’s generally an image with a single object as the focus and the task is to say what that image is\n\n![Alt Text](https://cdn-images-1.medium.com/max/1600/1*8GVucX9yhnL21KCtcyFDRQ.png)\n\nBut when we look at the world around us, we carry out far more complex task\n\n![Alt Text](https://cdn-images-1.medium.com/max/1600/1*NdwfHMrW3rpj5SW_VQtWVw.png)\n\nWe see complicated sights with multiple overlapping objects, and different backgrounds and we not only classify these different objects but also identify their boundaries, differences, and relations to one another!\n\nCan CNNs help us with such complex tasks? Yes.\n\n![Alt Text](https://irenelizihui.files.wordpress.com/2016/02/cnn2.png)\n\n![Alt Text](https://www.pyimagesearch.com/wp-content/uploads/2017/03/imagenet_vgg16.png)\n\n- We can take a classifier like VGGNet or Inception and turn it into an object detector by sliding a small window across the image\n- At each step you run the classifier to get a prediction of what sort of object is inside the current window. \n- Using a sliding window gives several hundred or thousand predictions for that image, but you only keep the ones the classifier is the most certain about.\n- This approach works but it’s obviously going to be very slow, since you need to run the classifier many times.It's a brute-force-y approach.AND computationaly expensive.\n\n- __BASIC IDEA__ :\n    1. Take an image $I$ and divide it into $n$ equal squares($i$). Then, $I$ is a set of smaller images  ($i_{1}$,$i_{2}$,$i_{3}$...$i_{n}$)\n    2. Run __X__ a pre-trained image classifier CNN over each square $i$.\n    3. __X__ analyzes each square $i$ and classifies it into a object class $l$ with a probability score of $\\alpha$.\n    4. This operation result into a bunch of labels __X__($I$) = ($l_{1}, \\alpha_1 $),($l_{2}, \\alpha_2 $) ... ($l_{n}, \\alpha_n$)  , where  ($l_{1},\\alpha_1 $) = __X__($i_{1}$).\n    5. We keep only those labels, which the CNN feels most confident about i.e. the labels with the highest scores.\n    6. Approach for identifiction is Labeling then Detection.\n    \n\n---\n\n### A better approach, R-CNN\n\n![Alt Text](https://cdn-images-1.medium.com/max/1600/1*ZQ03Ib84bYioFKoho5HnKg.png)\n\n- R-CNN creates bounding boxes, or region proposals, using a process called Selective Search \n- At a high level, Selective Search looks at the image through windows of different sizes, and for each size tries to group together adjacent pixels by texture, color, or intensity to identify objects.\n\n![Alt Text](https://cdn-images-1.medium.com/max/1600/0*Sdj6sKDRQyZpO6oH.)\n\n1. Generate a set of proposals for bounding boxes.\n2. Run the images in the bounding boxes through a pre-trained AlexNet and finally an SVM to see what object the image in the box is.\n3. Run the box through a linear regression model to output tighter coordinates for the box once the object has been classified.\n \n###### Some improvements to R-CNN\nR-CNN: https://arxiv.org/abs/1311.2524\nFast R-CNN: https://arxiv.org/abs/1504.08083\nFaster R-CNN: https://arxiv.org/abs/1506.01497\nMask R-CNN: https://arxiv.org/abs/1703.06870\n\n---\n\nBut YOLO takes a different approach\n\n### What is YOLO?\nIf you aren't motivated enough to know what it is may be this video will get you excited!\n(https://www.youtube.com/watch?v=VOC3huqHrss)\n\n- YOLO takes a completely different approach. \n- It’s not a traditional classifier that is repurposed to be an object detector. \n- YOLO actually looks at the image just once (hence its name: You Only Look Once) but in a clever way.\n\nYOLO divides up the image into a grid of 13 by 13 cells:\n\n![Alt Text](http://machinethink.net/images/yolo/Grid@2x.png)\n\n- Each of these cells is responsible for predicting 5 bounding boxes. \n- A bounding box describes the rectangle that encloses an object.\n- YOLO also outputs a confidence score that tells us how certain it is that the predicted bounding box actually encloses some object.\n- This score doesn’t say anything about what kind of object is in the box, just if the shape of the box is any good.\n\nThe predicted bounding boxes may look something like the following (the higher the confidence score, the fatter the box is drawn):\n\n![Alt Text](http://machinethink.net/images/yolo/Boxes@2x.png)\n\n- For each bounding box, the cell also predicts a class. \n- This works just like a classifier: it gives a probability distribution over all the possible classes. \n- YOLO was trained on the PASCAL VOC dataset, which can detect 20 different classes such as:\n\n- bicycle\n- boat\n- car\n- cat\n- dog\n- person\n\n- The confidence score for the bounding box and the class prediction are combined into one final score that tells us the probability that this bounding box contains a specific type of object. \n- For example, the big fat yellow box on the left is 85% sure it contains the object “dog”:\n\n![Alt Text](http://machinethink.net/images/yolo/Scores@2x.png)\n\n- Since there are 13×13 = 169 grid cells and each cell predicts 5 bounding boxes, we end up with 845 bounding boxes in total. \n- It turns out that most of these boxes will have very low confidence scores, so we only keep the boxes whose final score is 30% or more (you can change this threshold depending on how accurate you want the detector to be).\n\nThe final prediction is then:\n\n![Alt Text](http://machinethink.net/images/yolo/Prediction@2x.png)\n\n- From the 845 total bounding boxes we only kept these three because they gave the best results. \n- But note that even though there were 845 separate predictions, they were all made at the same time — the neural network just ran once. And that’s why YOLO is so powerful and fast.\n\nThe architecture of YOLO is simple, it’s just a convolutional neural network:\n\n![Alt Text](https://i.imgur.com/QH0CvRN.png)\n\nThis neural network only uses standard layer types: convolution with a 3×3 kernel and max-pooling with a 2×2 kernel. No fancy stuff. There is no fully-connected layer in YOLOv2.\n\nThe very last convolutional layer has a 1×1 kernel and exists to reduce the data to the shape 13×13×125. This 13×13 should look familiar: that is the size of the grid that the image gets divided into.\n\nSo we end up with 125 channels for every grid cell. These 125 numbers contain the data for the bounding boxes and the class predictions. Why 125? Well, each grid cell predicts 5 bounding boxes and a bounding box is described by 25 data elements:\n\n- x, y, width, height for the bounding box’s rectangle\n- the confidence score\n- the probability distribution over the classes\n\nUsing YOLO is simple: you give it an input image (resized to 416×416 pixels), it goes through the convolutional network in a single pass, and comes out the other end as a 13×13×125 tensor describing the bounding boxes for the grid cells. All you need to do then is compute the final scores for the bounding boxes and throw away the ones scoring lower than 30%.\n\n### Improvements to YOLO v1\n\nYoLO v2 vs YoLO v1\n\n- Speed (45 frames per second — better than realtime)\n- Network understands generalized object representation (This allowed them to train the network on real world images and predictions on artwork was still fairly accurate).\n- faster version (with smaller architecture) — 155 frames per sec but is less accurate.\n\nPaper here\nhttps://arxiv.org/pdf/1612.08242v1.pdf","execution_count":null},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","collapsed":true,"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}