{"cells":[{"metadata":{"trusted":true,"_uuid":"e9cfb85efafc0e551276d6d7e7ad199df60540f0"},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"d4e3d6783b4519f71afe323d92d504dfde208c92"},"cell_type":"markdown","source":"For python users, this is a R script that you could run off-the-shelf and get images of larger patches. Then you can read them by cv2/PIL and continue with post-processing.\n\n## Original Message\nThe strategy to solve the puzzle is simple:\n\n1.- Define dissimilarity between 2 images over an edge as the distance  between the pixels in the common edges  It seems better to compare a combination of  2 pixel stripes , instead of only the edge.\n2.-  For each image find the 2 more promising candidates for each edge (up,down),(down,up) and (left,right),(rigth,left). This is done using k-NN\n3.- Define the compatibility of a pair of images over an edge  as 1- r ,  being r the ratio of dissimilarities with the best candidate and the second one.  Two images are more compatible if the second candidate is  a weak one.  \n4.- Filter the candidate list making a cut in dissimilarity and compatibility.\n\n5.- From this list, build all possible vertical, and horizontal stripes of images\n6.- Combine all strips.\n\nAnd that's all\n\n\n\n"},{"metadata":{"_uuid":"cea7cecfe4ea3f97cc34e0d58c2655fcd2cfddef","_execution_state":"idle","trusted":true,"_kg_hide-input":true,"_kg_hide-output":true},"cell_type":"code","source":"require(data.table)\npath='../input/'\nrle=fread(paste0(path,'camelyon16-cancer-wsi-list-tumor-050/camelyon16_train_tumor_006.csv'))\nstest=fread(paste0(path,'camelyon16-cancer-wsi-list-tumor-050/camelyon16_train_tumor_007.csv'))\nlmod=paste0(rle$id,'.tif')\nltest=paste0(stest$id,'.tif')\n\nprint(length(lmod))\nprint(length(ltest))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"f51eed690549db83e4e3cb59ecf3e7ee33b5d7df"},"cell_type":"code","source":"read_img<-function(fname,spath){\n  im=load.image(paste0(path,'histopathologic-cancer-detection/',spath,'/',fname))\n  return(as.vector(im[,,1,1]))\n}\n# read_mask<-function(fname,spath){\n#   im=load.image(paste0(path,spath,'/masks/',fname))\n#   return(as.vector(im[,,1,1]))\n# }\n","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"e097c7302211f283969bb7a63da7aba5187161ee"},"cell_type":"markdown","source":"Read all images in train+test"},{"metadata":{"trusted":true,"_uuid":"2cc2d11a1d523418b16ab0bcb0645e769bbf480e"},"cell_type":"code","source":"# It must be divided by two when added\n# It should be greater than 500 when added\n\nlibrary(doParallel)\ncl <- makeCluster(4)\nregisterDoParallel(cl)\nsystem.time({\n#   train <- foreach(i = 1:length(lmod), .packages = c('imager'),.combine='rbind') %dopar% {\n#     read_img(lmod[i],'train')\n#   }\n  train <- foreach(i = 1:500, .packages = c('imager'),.combine='rbind') %dopar% {\n    read_img(lmod[i],'train')\n  }\n})\n\n# system.time({\n#   masks <- foreach(i = 1:length(lmod), .packages = c('imager'),.combine='rbind') %dopar% {\n#     read_mask(lmod[i],'train')\n#   }\n# })\n\nsystem.time({\n#   test <- foreach(i = 1:length(ltest), .packages = c('imager'),.combine='rbind') %dopar% {\n#     read_img(ltest[i],'test')\n#   }\n  test <- foreach(i = 1:500, .packages = c('imager'),.combine='rbind') %dopar% {\n#     read_img(ltest[i],'test')\n    read_img(ltest[i],'train')\n  }\n})\nstopCluster(cl)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"f6aca76ab370813a0a0993192a54f903e97940c7"},"cell_type":"markdown","source":"For each image,  define  up, down,left and right edge predictions."},{"metadata":{"trusted":true,"_uuid":"43ca4dd70c96044b996e80dc2a439a05e87dcc81"},"cell_type":"code","source":"di=96\nli=nrow(train)+nrow(test)\nall_arr=array(rbind(train,test),dim=c(li,di,di))\n\nall_u_ex=scale(2*all_arr[,1,]-all_arr[,2,])\nall_d_ex=scale(2*all_arr[,di,]-all_arr[,di-1,])\n\nall_u_ex=t(apply(all_u_ex,1,function(x)scale(x,center = T,scale = T)))\nall_d_ex=t(apply(all_d_ex,1,function(x)scale(x,center = T,scale = T)))\n\nall_u_ex[is.na(all_u_ex)]=0\nall_d_ex[is.na(all_d_ex)]=0\n\nall_l_ex=scale(2*all_arr[,,1]-all_arr[,,2])\nall_r_ex=scale(2*all_arr[,,di]-all_arr[,,di-1])\n\nall_l_ex=t(apply(all_l_ex,1,function(x)scale(x,center = T,scale = T)))\nall_r_ex=t(apply(all_r_ex,1,function(x)scale(x,center = T,scale = T)))\n\nall_l_ex[is.na(all_l_ex)]=0\nall_r_ex[is.na(all_r_ex)]=0\n","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"89e3be7955474812ace8b78842af7442c8c6178e"},"cell_type":"markdown","source":"Use k-NN to find the two more similar images  to fit each edge "},{"metadata":{"trusted":true,"_uuid":"8e244475edd35e0d5d9080767d4d21036956dc9e"},"cell_type":"code","source":"require(FNN)\nsystem.time(neldu<-get.knnx(all_d_ex,all_u_ex,k=2))\nsystem.time(nelud<-get.knnx(all_u_ex,all_d_ex,k=2))\n\nsystem.time(nelr<-get.knnx(all_l_ex,all_r_ex,k=2))\nsystem.time(nerl<-get.knnx(all_r_ex,all_l_ex,k=2))\n\n","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"c1c14ec8d85e35c6e9b0caa3a3f49d783731b880"},"cell_type":"markdown","source":""},{"metadata":{"_uuid":"23c5d2ee2bfd4f46e18dd6ca04cdc4b2694ead1d"},"cell_type":"markdown","source":"Code to combine best neighbors , first making  horizontal and vertical strips, and finally combining them"},{"metadata":{"trusted":true,"_uuid":"7da92b397ebbc56bb63cda2ef133ebe52fa7dd2c"},"cell_type":"code","source":"gen_mosaic<-function(ad,ac){\n  #generate candidates left-right\n  \n  dlr=cbind(as.data.table(nelr$nn.index),as.data.table(nelr$nn.dist))\n  colnames(dlr)=c('i1','i2','d1','d2')\n  dlr[,i0:=1:nrow(dlr)]\n  dlr[,c:=1-d1/d2] # Compatibility\n  \n\n  drl=cbind(as.data.table(nerl$nn.index),as.data.table(nerl$nn.dist))\n  colnames(drl)=c('i1','i2','d1','d2')\n  drl[,i0:=1:nrow(drl)]\n  drl[,c:=1-d1/d2]\n\n\n  bb2=merge(dlr,drl,by.x='i0',by.y='i1')\n  \n  #filter by disimilarity and compatibility\n  bb2=bb2[i0!=i1 & d1.x<ad & c.x>ac & c.y>ac]\n\n\n    \n   #find left-right strips \n    \n  nt=nrow(all_arr)\n  lcols=list()\n  eval=array(F,nt)\n    \n  for(i in 1:nt){\n    if(!eval[i]){\n      lt=c(i)\n      eval[i]=F\n      cond=T\n      i0=i\n      while(cond){\n        i1=bb2$i1[bb2$i0==i0]\n        if(length(i1)==1 & length(which(lt==i1))==0){\n          lt=c(i1,lt)\n          i0=i1\n          eval[i1]=T\n        }\n        else\n          cond=F\n      }\n      cond=T\n      i0=i\n      while(cond){\n        i1=bb2$i0[bb2$i1==i0]\n        if(length(i1)==1  & length(which(lt==i1))==0){\n          lt=c(lt,i1)\n          i0=i1\n          eval[i1]=T\n        }\n        else\n          cond=F\n      }\n      if(length(lt)>1){\n        #print(lt)\n        lcols=append(lcols,list(lt))\n      }     \n    }\n  }\n\n #Same for up-down\n\n  ddu=cbind(as.data.table(neldu$nn.index),as.data.table(neldu$nn.dist))\n  colnames(ddu)=c('i1','i2','d1','d2')\n  ddu[,i0:=1:nrow(ddu)]\n  ddu[,c:=1-d1/d2]\n \n\n\n  dud=cbind(as.data.table(nelud$nn.index),as.data.table(nelud$nn.dist))\n  colnames(dud)=c('i1','i2','d1','d2')\n  dud[,i0:=1:nrow(dud)]\n  dud[,c:=1-d1/d2]\n \n  bb=merge(ddu,dud,by.x='i0',by.y='i1')\n\n  bb=bb[i0!=i1 & d1.x<ad & c.x>ac & c.y>ac]\n\n    \n  #Generate up-down stripes  \n  nt=nrow(all_arr) \n  lrows=list()\n  eval=array(F,nt)\n  for(i in 1:nt){\n    if(!eval[i]){\n      lt=c(i)\n      eval[i]=F\n      cond=T\n      i0=i\n      while(cond){\n        i1=bb$i1[bb$i0==i0]\n        if(length(i1)==1 & length(which(lt==i1))==0){\n          lt=c(i1,lt)\n          i0=i1\n          eval[i1]=T\n        }\n        else\n          cond=F\n      }\n      cond=T\n      i0=i\n      while(cond){\n        i1=bb$i0[bb$i1==i0]\n        if(length(i1)==1  & length(which(lt==i1))==0){\n          lt=c(lt,i1)\n          i0=i1\n          eval[i1]=T\n        }\n        else\n          cond=F\n      }\n      if(length(lt)>1){\n        #print(lt)\n        lrows=append(lrows,list(lt))\n      }     \n    }\n  }\n\n  #Finally combine rows and colums\n  \n  rc=array(0,dim=c(nt,2))\n\n  for(i in 1:length(lrows))rc[lrows[[i]],1]=i\n  for(i in 1:length(lcols))rc[lcols[[i]],2]=i\n\n  rc=as.data.table(rc)\n\n  bt=rbind(bb,bb2)\n  \n  require(igraph)\n  gra3=graph_from_edgelist(as.matrix(bt[,.(i0,i1)]))\n  clu=components(gra3)\n\n  ls=lapply(1:clu$no,function(x)which(clu$membership==x))\n\n  lls=unlist(lapply(ls,length))\n\n  dd=data.table(i=1:length(lls),l=lls)\n\n  dd=dd[order(-l)]\n  list(dd,ls,rc,lrows,lcols)\n}","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"58de0812772a3a16de1a2bb90641ee8e6ff1e87a"},"cell_type":"markdown","source":"Here go the magic! : Find all mosaics from the individual images"},{"metadata":{"trusted":true,"_uuid":"cdfe5667929041e5977b47b042dd5f8435214d98"},"cell_type":"code","source":"disim=10\ncompat=.25\nldd=gen_mosaic(disim,compat)\n\ndd=ldd[[1]] # All mosaics ordererd by number of images\nls=ldd[[2]]\nrc=ldd[[3]]\nlrows=ldd[[4]] \nlcols=ldd[[5]]\n\ndd\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"e0ec6063c82a0066c4a46d693c6d38edc74d1a5d"},"cell_type":"code","source":"require(imager)\n\n\n# From seed, complete row and column\ncomplete<-function(se,mat){\n  \n  ir0=unlist(rc[se,1])\n  ic0=unlist(rc[se,2])\n  \n  x0=mat[which(mat[,1]==se),2]\n  y0=mat[which(mat[,1]==se),3]\n  \n  if(ir0>0){\n    r0=lrows[[ir0]]\n    \n    for(i in 1:length(r0)){\n      if(length(which(mat[,1]==r0[i]))==0)mat=rbind(mat,c(r0[i],x0-which(r0==se)+i,y0,0))\n    }\n  }\n  if(ic0>0){\n    c0=rev(lcols[[ic0]])\n    for(i in 1:length(c0)){\n      if(length(which(mat[,1]==c0[i]))==0)mat=rbind(mat,c(c0[i],x0,y0-which(c0==se)+i,0))\n    }\n  }\n  mat[which(mat[,1]==se),4]=1\n  unique(mat)\n}\n\n\n# Complete iteratively a mosaic from a seed image\ngen_mos<-function(se){\n  mat=array(c(se,0,0,0),dim=c(1,4))\n  \n  while(sum(mat[,4])<nrow(mat)){\n    for(i in 1:nrow(mat)){\n      if(mat[i,4]==0)mat=complete(mat[i,1],mat)\n    }\n  }\n  \n  mat[,2]=mat[,2]-min(mat[,2])\n  mat[,3]=mat[,3]-min(mat[,3])\n  mat\n}\n\nplmos<-function(mat,ii){\n  imsize <- 96\n    \n  lx=max(mat[,2])+1\n  ly=max(mat[,3])+1\n  \n  n=nrow(mat)\n  \n  mos=array(0,dim=c(lx*imsize,ly*imsize))\n  \n  mosmas=mos*0\n  for(k in 1:n){\n    fi=mat[k,2]\n    co=mat[k,3]\n    id1=mat[k,1]\n    mos[fi*imsize+c(1:imsize),co*imsize+c(1:imsize)]=all_arr[id1,,]\n    mosmas[fi*imsize+c(1:imsize),co*imsize+c(1:imsize)]=all_arr[id1,,]\n    # uncomment this line if you want the annotated image instead of the raw one\n    #if(id1<=4000)mosmas[fi*101+c(1:101),co*101+c(1:101)]=masks[id1,]\n  }\n  \n  mos=add.color(as.cimg(mos))\n  R(mos)=as.cimg(mosmas)\n  png(filename=paste(ii,\".png\",sep = \"\"),width=nrow(mos), height=ncol(mos))\n  #plot(as.cimg(mos),)\n  op <- par(mar = rep(0, 4))\n  plot(mos, axes=FALSE, ann=FALSE)\n  par(op)\n  dev.off()\n}","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"ee169633f51138b42b85f897e129240fe405334f"},"cell_type":"markdown","source":"There are no solutions after #384.\n\n\n\n\n\n"},{"metadata":{"trusted":true,"_uuid":"8cfbf882fb1fc4ab3645913e6f3b45cb204ca57a","_kg_hide-output":false},"cell_type":"code","source":"for(ii in 1:400){\n    mat=gen_mos(ls[[dd[ii,i]]][1])\n    png(filename=paste(ii,\".png\",sep = \"\"),width=7500, height=7500)\n    plmos(mat,ii)\n    dev.off()\n}","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"364208424bead492ddc411afc02e6a936b2768b2"},"cell_type":"markdown","source":""}],"metadata":{"kernelspec":{"display_name":"R","language":"R","name":"ir"},"language_info":{"mimetype":"text/x-r-source","name":"R","pygments_lexer":"r","version":"3.4.2","file_extension":".r","codemirror_mode":"r"}},"nbformat":4,"nbformat_minor":1}