Revision history [back]

first i would like to thank @sturkmen and waiting him to explain his idea for OMR , and i would like to see other ideas from other Guru memebers

now I would like to share with you another idea for solving OMR , i will use matTemplate to solve the problem the proposed idea works as follow:

convert input image to gray
convert gray to Black and white
detect skew angle
detect the Area of the Questions and Answers in the scanned answer sheet
detect the Area of the Questions and Answers in the scanned answer sheet
match the All answers with predefined empty answers , if the confidence level is low , that is mean the answer is checked

Here is the code to do the task

#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
#include <stdio.h>

using namespace std;
using namespace cv;


int main( int, char** argv )
{
    //Start OMR application 
    //1-open the image under test as gray scale
    Mat greyMat = imread("C:\\temp\\14639435664447751.jpg",CV_LOAD_IMAGE_GRAYSCALE);

    //2-convert image from gray scale to black and white using adaptive thresholding
    Mat blackAndWhiteMat;
    adaptiveThreshold( greyMat, blackAndWhiteMat , 255,CV_ADAPTIVE_THRESH_MEAN_C,CV_THRESH_BINARY_INV,13, 1 );
    imwrite("C:\\temp\\AdaptiveBW.jpg",blackAndWhiteMat);

    //3-detect the skew angle using HoughTrnasform
    double dAngle = 0.; 
    Size size = blackAndWhiteMat.size();
    vector<Vec4i> lines;
    HoughLinesP(blackAndWhiteMat, lines, 1, CV_PI/180, 100, size.width / 2.f, 20);  
    double ftan = 0.;
    double angle = 0.;
    unsigned nb_lines = lines.size();
    for (unsigned i = 0; i < nb_lines; ++i)
    {       
        ftan = (double)(lines[i][3] - lines[i][1]) / (double)(lines[i][2] - lines[i][0]) ;      
        angle += atan(ftan);
    }
    angle /= nb_lines; // mean angle, in radians.
    // convert angle from radians to degree
    dAngle = angle * 180 / CV_PI ;

    //4-Rotate the image to correct the skew angle  
    Mat DeskewedMat,DeskewedMatOrg;
    bool bKeepOldSize = false;//if true we will use the old image size, false calcualte the new image size
    Size ImgSize = size;
    Point2f pt(blackAndWhiteMat.cols/2., blackAndWhiteMat.rows/2.);    
    Mat r = getRotationMatrix2D(pt, dAngle, 1.0);
    //Calculate the new image size if required
    cv::Rect bbox = cv::RotatedRect(pt,blackAndWhiteMat.size(), dAngle).boundingRect();
    if(bKeepOldSize == false)
    {
        // adjust transformation matrix and destination matrix
        r.at<double>(0,2) += bbox.width/2.0 - pt.x;
        r.at<double>(1,2) += bbox.height/2.0 - pt.y;
        ImgSize = bbox.size();
        DeskewedMat.create(ImgSize,blackAndWhiteMat.type());        
    }
    warpAffine(blackAndWhiteMat, DeskewedMat, r, ImgSize,INTER_LANCZOS4,BORDER_CONSTANT,Scalar(255));
    bitwise_not(DeskewedMat,DeskewedMat);
    //original rotated image
    warpAffine(greyMat, DeskewedMatOrg, r, ImgSize,INTER_LANCZOS4,BORDER_CONSTANT,Scalar(255));
    imwrite("C:\\temp\\DeskewedBW.jpg",DeskewedMat);

    //5-Now find the exam questions header and the answer using template matching   
    Mat resultMat;//final matrix which will be used to show the selected answers
    cvtColor(DeskewedMatOrg,resultMat,CV_GRAY2BGR); 
    Mat TemplMat = imread("C:\\temp\\Questions Header Template.png",CV_LOAD_IMAGE_GRAYSCALE);
    Mat AnswersTemplMat = imread("C:\\temp\\Answers Template.png",CV_LOAD_IMAGE_GRAYSCALE);
    int res_width,res_height,nWidth,nTWidth,nHight,nTHight;
    Rect HeaderRect,AnswerRect;
    double      minval, maxval;
    Point       minloc, maxloc;
    nWidth = DeskewedMat.cols;
    nTWidth = TemplMat.cols;
    nHight = DeskewedMat.rows;
    nTHight = TemplMat.rows;
    res_width  = nWidth - nTWidth + 1;
    res_height = nHight - nTHight + 1;
    Mat res = Mat(res_height,res_width,CV_32FC1);
    matchTemplate(DeskewedMat,TemplMat,res,CV_TM_CCOEFF_NORMED);
    minMaxLoc( res, &minval, &maxval, &minloc, &maxloc, Mat() );    
    HeaderRect.x = maxloc.x;
    HeaderRect.y = maxloc.y;
    HeaderRect.width = nTWidth;
    HeaderRect.height = nTHight;
    AnswerRect.x = HeaderRect.x;
    AnswerRect.y = HeaderRect.y + HeaderRect.height ;
    AnswerRect.width = HeaderRect.width;
    AnswerRect.height = AnswersTemplMat.rows;

    //6-Now start to collect the answers from the exam sheet
    int iQuestionsNum = 20;//you have 20 question in the paper
    int iAnswersNum = 4;//you have 4 answers in every question
    double iQuestionWidth = (double)AnswerRect.width / iQuestionsNum;
    double iQuestionHeight = iQuestionWidth +1;
    int iCheckedAnswersNum = 0;
    int i = 0,j=0;
    bool bIsAChecked,bIsBChecked,bIsCChecked,bIsDChecked;
    Mat AnswerTmpl[4];
    AnswerTmpl[0] = imread("C:\\temp\\A Empty Template.png",CV_LOAD_IMAGE_GRAYSCALE);
    AnswerTmpl[1] = imread("C:\\temp\\B Empty Template.png",CV_LOAD_IMAGE_GRAYSCALE);
    AnswerTmpl[2] = imread("C:\\temp\\C Empty Template.png",CV_LOAD_IMAGE_GRAYSCALE);
    AnswerTmpl[3] = imread("C:\\temp\\D Empty Template.png",CV_LOAD_IMAGE_GRAYSCALE);
    string Answer[4];
    Answer[0] = "A";    Answer[1] = "B";    Answer[2] = "C";    Answer[3] = "D";    Mat OneAnswerMat;
    Rect OneAnswerRect; 
    for (i = 0 ; i< iQuestionsNum ; i++)
    {
        bIsAChecked=bIsBChecked=bIsCChecked=bIsDChecked = false;
        iCheckedAnswersNum = 0;

        for (j=0;j< iAnswersNum; j++)
        {
            OneAnswerRect.x = AnswerRect.x + i * iQuestionWidth - 2;
            if(OneAnswerRect.x < 0 )
                OneAnswerRect.x = 0;
            OneAnswerRect.width = iQuestionWidth + 10;
            if((OneAnswerRect.x + OneAnswerRect.width) > DeskewedMat.cols )
                OneAnswerRect.width = OneAnswerRect.width - 10 ;
            OneAnswerRect.y = AnswerRect.y + j * iQuestionHeight - 2;
            if(OneAnswerRect.y < 0 )
                OneAnswerRect.y;
            OneAnswerRect.height = iQuestionHeight + 10;
            if((OneAnswerRect.y + OneAnswerRect.height) > DeskewedMat.rows)
                OneAnswerRect.height = OneAnswerRect.height - 10;
            OneAnswerMat = DeskewedMat(OneAnswerRect);
            imwrite("c:\\temp\\OnAnswerRect.jpg",OneAnswerMat);
            //Check if A,B,C,D is Checked
            res_width  = OneAnswerMat.cols - AnswerTmpl[j].cols + 1;
            res_height = OneAnswerMat.rows - AnswerTmpl[j].rows + 1;
            res = Mat(res_height,res_width,CV_32FC1);
            matchTemplate(OneAnswerMat,AnswerTmpl[j],res,CV_TM_CCOEFF_NORMED);
            minMaxLoc( res, &minval, &maxval, &minloc, &maxloc, Mat() );
            if (maxval < 0.7)//the matching with empty template is low so the choice is checked     
            {
                bIsAChecked = true ; 
                iCheckedAnswersNum++;
                //Draw the selected answer
                putText(resultMat , Answer[j] , Point(OneAnswerRect.x+AnswerRect.x+5,OneAnswerRect.y+HeaderRect.y+5),FONT_HERSHEY_PLAIN,2,Scalar(0,0,255),2);
            }
        }
        //now mark the empty answers
        if(iCheckedAnswersNum == 0)  // there is no checked answers
        {
            OneAnswerRect.x = AnswerRect.x + i * iQuestionWidth;
            OneAnswerRect.width = iQuestionWidth;
            OneAnswerRect.y = AnswerRect.y ;
            OneAnswerRect.height = AnswerRect.height;
            cv::rectangle(resultMat,OneAnswerRect,Scalar(0,255,0),2);
        }
        if(iCheckedAnswersNum > 1)  // there is multiple checked answers
        {
            OneAnswerRect.x = AnswerRect.x + i * iQuestionWidth;
            OneAnswerRect.width = iQuestionWidth;
            OneAnswerRect.y = AnswerRect.y ;
            OneAnswerRect.height = AnswerRect.height;
            cv::rectangle(resultMat,OneAnswerRect,Scalar(255,0,0),2);
        }
    }

    imwrite("c:\\temp\\OMRFinalresult.jpg",resultMat);
    /// end OMR

  return 0;
}

Now lets explain what is going on step by step

1-open the the image as grey scale image

Mat greyMat = imread("C:\\temp\\14639435664447751.jpg",CV_LOAD_IMAGE_GRAYSCALE);

2-Convert image from gray scale to BW , i used adaptive threshold because light in the image is changing from area to area , i had tested some other methodologies to binarization the best result obtained by using sauvola but the code is too much , i used the following function to binarize the image

adaptiveThreshold( greyMat, blackAndWhiteMat , 255,CV_ADAPTIVE_THRESH_MEAN_C,CV_THRESH_BINARY_INV,13, 1 );

and here it the result image image description

3-detect the skew angles , for simplicity i used hough transform , you can use any other method such as rotated bound rect for the bigest contour , or you can use CC or PCA , and here it's the used function

HoughLinesP(blackAndWhiteMat, lines, 1, CV_PI/180, 100, size.width / 2.f, 20);

take the average of the resulted angle of all lines

4-Correct the skew by using the following

warpAffine(blackAndWhiteMat, DeskewedMat, r, ImgSize,INTER_LANCZOS4,BORDER_CONSTANT,Scalar(255));

the corrected skew image will be as the following imag image description

5- we now need to find the questions and answers area , i will use matchTemplet to do that, the first step i would to have the fixed in the sheet , so i selected the following area in the image to be as a template image image description the return from match template is the rectangle which have the selected area , we will use the returned rectangle as arefrense to get the coordinates of all required parts in the image .

6-Now i will use matchtemplate again to decide the answer is checked or not , as follow , prepare empty patterns for choises A,B,C,D as the following images

image description

Now we can calculate the coordinate of every single question and every single answer , example for question number 20 i will check the chooise D is selected or not as follow i will use the confidence returned from matchtemplate between the following calculated area in the image image description and the previuse prepared tempate D the confidence here is very high because the images are nearly similar , if the confince is low that mean the answer is checked , we will calculate all answers for every question and the result will be as the following image

and here it is another example image description