module_3-lec1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Release the Kraken!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The next library we're going to look at is called Kraken, which was developed by Université \n",
    "# PSL in Paris. It's actually based on a slightly older code base, OCRopus. You can see how the\n",
    "# flexible open-source licenses allow new ideas to grow by building upon older ideas. And, in\n",
    "# this case, I fully support the idea that the Kraken - a mythical massive sea creature - is the\n",
    "# natural progression of an octopus!\n",
    "#\n",
    "# What we are going to use Kraken for is to detect lines of text as bounding boxes in a given\n",
    "# image. The biggest limitation of tesseract is the lack of a layout engine inside of it. Tesseract\n",
    "# expects to be using fairly clean text, and gets confused if we don't crop out other artifacts.\n",
    "# It's not bad, but Kraken can help us out be segmenting pages. Lets take a look."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# First, we'll take a look at the kraken module itself\n",
    "import kraken\n",
    "help(kraken)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# There isn't much of a discussion here, but there are a number of sub-modules that look\n",
    "# interesting. I spend a bit of time on their website, and I think the pageseg module, which\n",
    "# handles all of the page segmentation, is the one we want to use. Lets look at it\n",
    "from kraken import pageseg\n",
    "help(pageseg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# So it looks like there are a few different functions we can call, and the segment\n",
    "# function looks particularly appropriate. I love how expressive this library is on the\n",
    "# documentation front -- I can see immediately that we are working with PIL.Image files,\n",
    "# and the author has even indicated that we need to pass in either a binarized (e.g. '1')\n",
    "# or grayscale (e.g. 'L') image. We can also see that the return value is a dictionary\n",
    "# object with two keys, \"text_direction\" which will return to us a string of the\n",
    "# direction of the text, and \"boxes\" which appears to be a list of tuples, where each\n",
    "# tuple is a box in the original image.\n",
    "#\n",
    "# Lets try this on the image of text. I have a simple bit of text in a file called\n",
    "# two_col.png which is from a newspaper on campus here\n",
    "from PIL import Image\n",
    "im=Image.open(\"readonly/two_col.png\")\n",
    "# Lets display the image inline\n",
    "display(im)\n",
    "# Lets now convert it to black and white and segment it up into lines with kraken\n",
    "bounding_boxes=pageseg.segment(im.convert('1'))['boxes']\n",
    "# And lets print those lines to the screen\n",
    "print(bounding_boxes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Ok, pretty simple two column text and then a list of lists which are the bounding boxes of \n",
    "# lines of that text. Lets write a little routine to try and see the effects a bit more\n",
    "# clearly. I'm going to clean up my act a bit and write real documentation too, it's a good\n",
    "# practice\n",
    "def show_boxes(img):\n",
    "    '''Modifies the passed image to show a series of bounding boxes on an image as run by kraken\n",
    "    \n",
    "    :param img: A PIL.Image object\n",
    "    :return img: The modified PIL.Image object\n",
    "    '''\n",
    "    # Lets bring in our ImageDraw object\n",
    "    from PIL import ImageDraw\n",
    "    # And grab a drawing object to annotate that image\n",
    "    drawing_object=ImageDraw.Draw(img)\n",
    "    # We can create a set of boxes using pageseg.segment\n",
    "    bounding_boxes=pageseg.segment(img.convert('1'))['boxes']\n",
    "    # Now lets go through the list of bounding boxes\n",
    "    for box in bounding_boxes:\n",
    "        # An just draw a nice rectangle\n",
    "        drawing_object.rectangle(box, fill = None, outline ='red')\n",
    "    # And to make it easy, lets return the image object\n",
    "    return img\n",
    "\n",
    "# To test this, lets use display\n",
    "display(show_boxes(Image.open(\"readonly/two_col.png\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Not bad at all! It's interesting to see that kraken isn't completely sure what to do with this\n",
    "# two column format. In some cases, kraken has identified a line in just a single column, while\n",
    "# in other cases kraken has spanned the line marker all the way across the page. Does this matter?\n",
    "# Well, it really depends on our goal. In this case, I want to see if we can improve a bit on this.\n",
    "#\n",
    "# So we're going to go a bit off script here. While this week of lectures is about libraries, the\n",
    "# goal of this last course is to give you confidence that you can apply your knowledge to actual\n",
    "# programming tasks, even if the library you are using doesn't quite do what you want. \n",
    "#\n",
    "# I'd like to pause the video for the moment and collect your thoughts. Looking at the image above,\n",
    "# with the two column example and red boxes, how do you think we might modify this image to improve\n",
    "# kraken's ability to text lines?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Thanks for sharing your thoughts, I'm looking forward to seeing the breadth of ideas that everyone\n",
    "# in the course comes up with. Here's my partial solution -- while looking through the kraken docs on \n",
    "# the pageseg() function I saw that there are a few parameters we can supply in order to improve \n",
    "# segmentation. One of these is the black_colseps parameter. If set to True, kraken will assume that \n",
    "# columns will be separated by black lines. This isn't our case here, but, I think we have all of the\n",
    "# tools to go through and actually change the source image to have a black separator between columns.\n",
    "#\n",
    "# The first step is that I want to update the show_boxes() function. I'm just going to do a quick\n",
    "# copy and paste from the above but add in the black_colseps=True parameter\n",
    "def show_boxes(img):\n",
    "    '''Modifies the passed image to show a series of bounding boxes on an image as run by kraken\n",
    "    \n",
    "    :param img: A PIL.Image object\n",
    "    :return img: The modified PIL.Image object\n",
    "    '''\n",
    "    # Lets bring in our ImageDraw object\n",
    "    from PIL import ImageDraw\n",
    "    # And grab a drawing object to annotate that image\n",
    "    drawing_object=ImageDraw.Draw(img)\n",
    "    # We can create a set of boxes using pageseg.segment\n",
    "    bounding_boxes=pageseg.segment(img.convert('1'), black_colseps=True)['boxes']\n",
    "    # Now lets go through the list of bounding boxes\n",
    "    for box in bounding_boxes:\n",
    "        # An just draw a nice rectangle\n",
    "        drawing_object.rectangle(box, fill = None, outline ='red')\n",
    "    # And to make it easy, lets return the image object\n",
    "    return img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The next step is to think of the algorithm we want to apply to detect a white column separator.\n",
    "# In experimenting a bit I decided that I only wanted to add the separator if the space of was\n",
    "# at least 25 pixels wide, which is roughly the width of a character, and six lines high. The\n",
    "# width is easy, lets just make a variable\n",
    "char_width=25\n",
    "# The height is harder, since it depends on the height of the text. I'm going to write a routine\n",
    "# to calculate the average height of a line\n",
    "def calculate_line_height(img):\n",
    "    '''Calculates the average height of a line from a given image\n",
    "    :param img: A PIL.Image object\n",
    "    :return: The average line height in pixels\n",
    "    '''\n",
    "    # Lets get a list of bounding boxes for this image\n",
    "    bounding_boxes=pageseg.segment(img.convert('1'))['boxes']\n",
    "    # Each box is a tuple of (top, left, bottom, right) so the height is just top - bottom\n",
    "    # So lets just calculate this over the set of all boxes\n",
    "    height_accumulator=0\n",
    "    for box in bounding_boxes:\n",
    "        height_accumulator=height_accumulator+box[3]-box[1]\n",
    "        # this is a bit tricky, remember that we start counting at the upper left corner in PIL!\n",
    "    # now lets just return the average height\n",
    "    # lets change it to the nearest full pixel by making it an integer\n",
    "    return int(height_accumulator/len(bounding_boxes))\n",
    "\n",
    "# And lets test this with the image with have been using\n",
    "line_height=calculate_line_height(Image.open(\"readonly/two_col.png\"))\n",
    "print(line_height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Ok, so the average height of a line is 31.\n",
    "# Now, we want to scan through the image - looking at each pixel in turn - to determine if there\n",
    "# is a block of whitespace. How bit of a block should we look for? That's a bit more of an art\n",
    "# than a science. Looking at our sample image, I'm going to say an appropriate block should be\n",
    "# one char_width wide, and six line_heights tall. But, I honestly just made this up by eyeballing\n",
    "# the image, so I would encourage you to play with values as you explore.\n",
    "# Lets create a new box called gap box that represents this area\n",
    "gap_box=(0,0,char_width,line_height*6)\n",
    "gap_box"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# It seems we will want to have a function which, given a pixel in an image, can check to see\n",
    "# if that pixel has whitespace to the right and below it. Essentially, we want to test to see\n",
    "# if the pixel is the upper left corner of something that looks like the gap_box. If so, then\n",
    "# we should insert a line to \"break up\" this box before sending to kraken\n",
    "#\n",
    "# Lets call this new function gap_check\n",
    "def gap_check(img, location):\n",
    "    '''Checks the img in a given (x,y) location to see if it fits the description\n",
    "    of a gap_box\n",
    "    :param img: A PIL.Image file\n",
    "    :param location: A tuple (x,y) which is a pixel location in that image\n",
    "    :return: True if that fits the definition of a gap_box, otherwise False\n",
    "    '''\n",
    "    # Recall that we can get a pixel using the img.getpixel() function. It returns this value\n",
    "    # as a tuple of integers, one for each color channel. Our tools all work with binarized\n",
    "    # images (black and white), so we should just get one value. If the value is 0 it's a black\n",
    "    # pixel, if it's white then the value should be 255\n",
    "    #\n",
    "    # We're going to assume that the image is in the correct mode already, e.g. it has been\n",
    "    # binarized. The algorithm to check our bounding box is fairly easy: we have a single location \n",
    "    # which is our start and then we want to check all the pixels to the right of that location \n",
    "    # up to gap_box[2]\n",
    "    for x in range(location[0], location[0]+gap_box[2]):\n",
    "        # the height is similar, so lets iterate a y variable to gap_box[3]\n",
    "        for y in range(location[1], location[1]+gap_box[3]):\n",
    "            # we want to check if the pixel is white, but only if we are still within the image\n",
    "            if x < img.width and y < img.height:\n",
    "                # if the pixel is white we don't do anything, if it's black, we just want to\n",
    "                # finish and return False\n",
    "                if img.getpixel((x,y)) != 255:\n",
    "                    return False\n",
    "    # If we have managed to walk all through the gap_box without finding any non-white pixels\n",
    "    # then we can return true -- this is a gap!\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Alright, we have a function to check for a gap, called gap_check. What should we do once\n",
    "# we find a gap? For this, lets just draw a line in the middle of it. Lets create a new function\n",
    "def draw_sep(img,location):\n",
    "    '''Draws a line in img in the middle of the gap discovered at location. Note that\n",
    "    this doesn't draw the line in location, but draws it at the middle of a gap_box\n",
    "    starting at location.\n",
    "    :param img: A PIL.Image file\n",
    "    :param location: A tuple(x,y) which is a pixel location in the image\n",
    "    '''\n",
    "    # First lets bring in all of our drawing code\n",
    "    from PIL import ImageDraw\n",
    "    drawing_object=ImageDraw.Draw(img)\n",
    "    # next, lets decide what the middle means in terms of coordinates in the image\n",
    "    x1=location[0]+int(gap_box[2]/2)\n",
    "    # and our x2 is just the same thing, since this is a one pixel vertical line\n",
    "    x2=x1\n",
    "    # our starting y coordinate is just the y coordinate which was passed in, the top of the box\n",
    "    y1=location[1]\n",
    "    # but we want our final y coordinate to be the bottom of the box\n",
    "    y2=y1+gap_box[3]\n",
    "    drawing_object.rectangle((x1,y1,x2,y2), fill = 'black', outline ='black')\n",
    "    # and we don't have anything we need to return from this, because we modified the image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Now, lets try it all out. This is pretty easy, we can just iterate through each pixel \n",
    "# in the image, check if there is a gap, then insert a line if there is.\n",
    "def process_image(img):\n",
    "    '''Takes in an image of text and adds black vertical bars to break up columns\n",
    "    :param img: A PIL.Image file\n",
    "    :return: A modified PIL.Image file\n",
    "    '''\n",
    "    # we'll start with a familiar iteration process\n",
    "    for x in range(img.width):\n",
    "        for y in range(img.height):\n",
    "            # check if there is a gap at this point\n",
    "            if (gap_check(img, (x,y))):\n",
    "                # then update image to one which has a separator drawn on it\n",
    "                draw_sep(img, (x,y))\n",
    "    # and for good measure we'll return the image we modified\n",
    "    return img\n",
    "\n",
    "# Lets read in our test image and convert it through binarization\n",
    "i=Image.open(\"readonly/two_col.png\").convert(\"L\")\n",
    "i=process_image(i)\n",
    "display(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Not bad at all! The effect at the bottom of the image is a bit unexpected to me, but it makes\n",
    "# sense. You can imagine that there are several ways we might try and control this. Lets see how \n",
    "# this new image works when run through the kraken layout engine\n",
    "display(show_boxes(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Looks like that is pretty accurate, and fixes the problem we faced. Feel free to experiment\n",
    "# with different settings for the gap heights and width and share in the forums. You'll notice though \n",
    "# method we created is really quite slow, which is a bit of a problem if we wanted to use\n",
    "# this on larger text. But I wanted to show you how you can mix your own logic and work with\n",
    "# libraries you're using. Just because Kraken didn't work perfectly, doesn't mean we can't\n",
    "# build something more specific to our use case on top of it.\n",
    "#\n",
    "# I want to end this lecture with a pause and to ask you to reflect on the code we've written\n",
    "# here. We started this course with some pretty simple use of libraries, but now we're\n",
    "# digging in deeper and solving problems ourselves with the help of these libraries. Before we\n",
    "# go on to our last library, how well prepared do you think you are to take your python\n",
    "# skills out into the wild?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}