Thursday 12 April 2012

d-touch Mobile- Part 3

In our last two posts we discussed about d-touch markers and how d-touch mobile library can be configured and used in an Android application. In this post we are going to discuss the architecture of the d-touch mobile library.

There are three main entities or classes of the d-touch mobile library.
  1. HIPreference
  2. DetectMarker
  3. MarkerConstraint
The sequence diagram of these entities is shown in figure 1:

Figure 1: Sequence diagram of d-touch mobile library




HIPreference

This class is used to store preferences which are used to define the constraints for the d-touch markers. This class contains two sets of parameters. The first set defines the type of the d-touch markers which d-touch mobile library should detect. This set contains the following paramters:
  • minium branches: It defines the minimum number of branches a d-touch marker can contain.
  • maximum branches: It defines the maximum number of branches a d-touch marker can contain.
  • empty branches: It defines the number of empty branches a d-touch marker can contain. A valid d-touch marker should at least have one non-empty branch.
  • maximum leaves: It defines the number of leaves a branch can contain.
These constraints are useful to restrict d-touch marker which should be recognised by an application. For example if we want to restrict our application to detect only those markers which have between 3 to 4 branches then we can set the minimum branches to 3 and the maximum branches to 4. 

The second set of parameters is used for validation. We use checksum for the validation. This set contains following parameters:
  • Validation Branches: It defines the number of validation branches a marker should have.
  • Validation Branch leaves: This parameter defines the number of leaves a validation branch should contain.
  • Checksum Modulo: This parameter defines the checksum modulo.
In order to calculate the checksum of a d-touch marker code the program first verifies the number of validation branches in the code. It then adds all the leaves in all the branches including validation branches and divides the total by the checksum modulo parameter. If the total number of leaves is completely divisible by the checksum modulo then the marker is considered as valid. Lets take an example to clarify it. For example if the preferences are set as follows:
  • Validation Branches: 4
  • Validation Branch leaves: 1
  • Checksum Modulo: 10
and for example our maker looks like as shown in figure 2:
Figure 2: Dtouch marker with validation branches.
As you can see from figure 2 that the marker has total eight branches among which four branches have exactly one leaf. So there are four validation branches in this marker. Now if we count the total number of leaves in this marker we get the result as 20. If we divide the total number of leaves i.e. 20 by the checksum modulo which is 10 then we get the result as 2.  This means that the marker shown in figure 2 is a valid marker.

DetectMarker

This class is used to check if the given nodes represent a valid d-touch marker. A valid d-touch marker has one dark region and is called root. The root region has one or more light region and these light regions are referred as branches. Each branch node can have zero or more dark regions. The dark regions inside branches are called leaves. Marker in figure 2 is a valid d-touch marker. For more information about the d-touch marker please refer to d-touch Mobile Part 1 blog.

verifyRoot

As shown in figure 1, an external module calls verifyRoot function to check if the node represents a valid d-touch marker root node. A node is a valid root if it has one or more valid branches and each branch has zero or more valid leaves. A root node should also fulfills the constraints defined in the preference class. 

This function receives following parameters:
  • rootIndex: This is the index of the node which we want to test as the root of the d-touch marker.
  • rootNode: This points to the root node.
  • hierarchy: This contains the hierarchy of the nodes in the image. It is used to trace root node, branches and their leaves.
  • codes: This is an empty list and if a marker is valid then the verifyRoot function fills the code of that marker in this list.
One question which might come into mind would be how to get the parameter values which are required as an input to the verifyRoot function? As we have mentioned in our previous post that we use OpenCV to process images. In order to get the values for above parameters we use OpenCV function called findContours. This function is called as follows:
Imgproc.findContours(contourImg, mComponents, mHierarchy, Imgproc.RETR_TREE, Imgproc.CHAIN_APPROX_NONE);
findCountours function finds contours or regions in the image and returns the list of regions in the components parameter and the whole hierarchy in the hierarchy parameter. For more information please refer to the OpenCV documentation.
After getting the list of components we iterate through this list and test each component for a valid d-touch marker root node. The implementation is as follows:
    for (int i = 0; i < mComponents.size(); i++){
      //clean this list.
      code.clear();
      if (markerDetector.verifyRoot(i, mComponents.get(i), mHierarchy,code)){
       //if marker found.
       marker.setCode(code);
       //marker.setComponent(mComponents.get(i));
       marker.setComponentIndex(i);
       markerFound = true;
       break;
      }
 }
In this code we iterate through the list of components which is determined through findContours function. We check if a particular component is a valid d-touch marker through verifyRoot function. Now lets see the logic behind verifyRoot function.
 
public Boolean verifyRoot(int rootIndex, Mat rootNode, Mat hierarchy, List<integer> codes){
  Boolean valid = false;
  int branchCount = 0;
  int emptyBranchCount = 0;
  int currentBranchIndex = -1;
  BranchStatus status;
    
  //get the nodes of the root node.
  double[] nodes = hierarchy.get(0, rootIndex);
  //get the first child node.
  currentBranchIndex = (int)nodes[FIRST_NODE];

  //if there is a branch node then verify branches.
  if (currentBranchIndex >= 0 ){
   //loop until there is a branch node.
   while(currentBranchIndex >= 0){
    //verify current branch.
    status = verifyBranch(currentBranchIndex, hierarchy, codes);
    //if branch is valid or empty.
    if (status == BranchStatus.VALID || status == BranchStatus.EMPTY ){
     branchCount++;
     if (status == BranchStatus.EMPTY){
      emptyBranchCount++;
      if (emptyBranchCount > mPreference.getMaxEmptyBranches()){
       return false;
      }
     }
     //get next node. 
     nodes = hierarchy.get(0, currentBranchIndex);
     currentBranchIndex = (int)nodes[NEXT_NODE];
    }
    else if (status == BranchStatus.INVALID)
     return false;
   }
   if (emptyBranchCount > mPreference.getMaxEmptyBranches())
    valid = false;
   //Marker should have at least one non-empty branch. If all branches are empty then return false.
   else if ((emptyBranchCount - branchCount) == 0)
    valid = false;
   else if (branchCount >= mPreference.getMinBranches() && branchCount <= mPreference.getMaxBranches()){
    if (verifyMarkerConstraint(codes)){
     Collections.sort(codes);
     valid = true;
    }else
     valid = false;
   }
  }
  return valid;
 }
This function first gets the immediate hierarchy of the root node. From this immediate hierarchy it retrieves the first child node of the root node. In the while loop it verifies if the current child node is a valid branch. If it is a valid branch or an empty branch then it increases the branch counter. If it is an empty branch then it also increases the empty branch counter. Please note that an empty branch is also a valid branch but it is not true vice versa. It then gets the next sibling of the current branch node and runs the same process again. After all the child nodes are verified as valid branches it verifies the marker against the constraints defined in the preferences. If  during the verification process a branch is identified as an invalid then the process stops and the root is considered as an invalid d-touch marker.

verifyBranch

verifyBranch function is called from verifyRoot function to check if a particular node is a valid branch. A node is a valid branch if it has zero or more valid leaves. A valid branch should also fulfills the constrainsts defined in the preference class. In order to validate a node as a valid branch it checks if its child nodes are valid leaves. It then verifies the branch against constraints defined in the preferences class. In case of valid branch the total number of leaves in this valid branch are added in the code list as part of the code.
private BranchStatus verifyBranch(int branchIndex, Mat hierarchy, List<integer> codes){
  int leafCount = 0;
  int currentLeafIndex = -1;
  BranchStatus status = BranchStatus.INVALID;
  
  //get first leaf node.
  double[] nodes = hierarchy.get(0, branchIndex);
  currentLeafIndex = (int)nodes[FIRST_NODE];
  if (currentLeafIndex >= 0){
   //loop until there is a leaf node.
   while(currentLeafIndex >= 0){
    if (verifyLeaf(currentLeafIndex, hierarchy)){
     leafCount++;
     //get next leaf node.
     nodes = hierarchy.get(0, currentLeafIndex);
     currentLeafIndex = (int)nodes[NEXT_NODE];
    }else{
     status = BranchStatus.INVALID;
     return status;
    }
   }
  }
  //if no leaf then the branch is empty.
  if (leafCount == 0)
   status = BranchStatus.EMPTY;
  else if (leafCount <= mPreference.getMaxLeaves())
   status = BranchStatus.VALID;
  //add leaf count in branch code. Only add it when leaf count is greater than 0.
  if(leafCount > 0 ) 
   codes.add(leafCount);
  return status;
 }
This function retreives the hierarchy of the current branch node. It then retreives the first child node and checks if it a valid leaf. If the child node is valid leaf then it increase the leaf count. If the leaf node is invalid then the branch is considered as an invalid. After all the child nodes of a branch node are verified as leaves this process verifies the branch against the constraints defined in the preferences class. If the branch validation is successful then the total number of leaves in a branch are added in the code list.

verifyLeaf

This function is called from the verifyBranch function to check if a particular node is a valid leaf. A node is a valid leaf if it does not have any child nodes. The implementation of this function is very simple:
 
 private Boolean verifyLeaf(int leafIndex, Mat hierarchy){
  Boolean valid = true;
  //Get nodes of branch index.
  double[] nodes = hierarchy.get(0, leafIndex);
  //check if there is no child node.
  if (nodes[FIRST_NODE] >= 0){
   valid = false;
  } 
  return valid;
 }
It simply checks if there are any child nodes of this node. If there are no child nodes then it returns true otherwise it returns false.

MarkerConstraint

This class is used to verify the d-touch code against the validation constraints defined in the preference class. We have discussed the validation constraints in the HIPreference section. This class is called from verifyRoot function to validate the marker code against the validation constraint. The verification is done by calling the verifyMarkerCode function.

verifyMarkerCode

This function first checks the validation branches and then calculates the checksum as shown below:
 public Boolean verifyMarkerCode(){
  Boolean valid = false;
  if (verifyValidationBranches())
   valid = verifyChecksum();
  return valid;
 }

verifyValidationBranches

This function simply checks if the d-touch marker code has number of validation branches as mentioned in the preferences class. The code is shown below:
 private boolean verifyValidationBranches(){
  boolean valid = false;
  int numberOfValidationBranches = 0;
  for (int code : markerCodes){
   if (code == mPreference.getValidationBranchLeaves()){
    numberOfValidationBranches++;
   }
  }
  if (numberOfValidationBranches >= mPreference.getValidationBranches())
   valid = true;
  return valid;
 }

verifyChecksum

This function first calculates the total number of leaves in a d-touch code by simply adding all the numbers in a code. For example if a code is 1:1:1:1:2:4:4:6 then the total number of leaves in the marker are 1+1+1+1+2+4+4+6 = 20.  It divides the total sum by the checksum modulo. If the mod is zero then it means the checksum of the code is valid. The function is implemented as follows:
 private boolean verifyChecksum(){
  boolean valid = false;
  int numberOfLeaves = 0;
  for (int code: markerCodes){
   numberOfLeaves += code;
  }
  if (mPreference.getChecksumModulo() > 0){
   double checksum = numberOfLeaves % mPreference.getChecksumModulo();
   if (checksum == 0){
    valid = true;
   }
  }
  return valid;
 }
  I hope this documentation is helpful to understand the d-touch mobile library. If you would like to see the d-touch mobile library in action then please check the code deployed on the github website.

No comments:

Post a Comment