Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
Thank you for your great job. But I think if we want to express a pixel
image(x,y)
in an image, the better way to find that in an array is
Array(x * width + y)
. Then we can assign the loop of rows by increase 1, and don't worry about the boundary thing. This maybe easier for me to understand. I noticed you manipulate the rows width by width. But there seems a little bug with this in the above code.
package EPIC;
public class EdgeDetection {
public static int[] processEdges(int[] image, int width, int threshold){
//throw out invalid input
if(image == null){
throw new NullPointerException();
}
if(width < 1){
throw new IllegalArgumentException();
}
if(image.length < width || image.length % width > 0){
throw new IllegalArgumentException();
}
//create output array and preprocess
final int[] output = new int[image.length];
final int numRows = image.length / width;
int xMin, xMax, yMin, yMax, maxDiff, index, pos;
//do the interior of the image
for(int row = 0; row < numRows; row++){
for(int col = 0; col < width; col++){
pos = image[row * width + col];
xMin = (col == 0) ? 0 : col -1;
xMax = (col == width -1) ? col : col + 1;
yMin = (row == 0) ? 0 : row - 1;
yMax = (row == numRows -1) ? row : row + 1;
if(meetsThreshold(xMin, xMax, yMin, yMax, width, image, pos, threshold)){
output[row * width + col] = pos;
}
}
}
return output;
}
private static boolean meetsThreshold(int xMin, int xMax, int yMin, int yMax,
int width, int[] image, int value, int threshold){
int temp;
for(int row = yMin; row <= yMax; row++){
for(int col = xMin; col <= xMax; col++){
temp = Math.abs(value - image[row * width + col]);
if(temp >= threshold){
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int width = 5;
int image[] = {
1,1,1,1,1,
1,9,1,1,1,
1,1,1,1,1,
1,1,1,1,1,
1,1,1,1,1,};
int out[] = processEdges(image, width, 2);
for (int i = 0; i < out.length; i++) {
if (i % width == 0) {
System.out.println();
}
System.out.print(" " + out[i]);
}
}
}
Logic:
2d cordinated to 1d indexes conversion logic:
k = (i*colSize) + j;//i,j are 2d indexes and k is the 1d index corresponding
1. for all points in the 1d that has 8 surrounding neighbors, compute the difference
2. even if one difference is above the threshold, then return it as edge
public class EdgeDetection {
public static int get1DIndex(int i, int j, int rowSize, int colSize){
if(i < 0 || j<0){
System.out.println("Invalid co-ordinated received");
return -1;
}
int k = (i*colSize) + j;
return k;
}
public static boolean isEdgePixel(int[] mat, int r, int c, int rowSize, int colSize, int threshold){
int neighbours[]; //for neighbor pixels
neighbours = new int[9];
int k=0;
//populate the neighbor values
for (int i=r-1; i<=r+1; i++){
for(int j=c-1; j<=c+1; j++){
neighbours[k] = mat[get1DIndex(i,j,rowSize,colSize)];
k++;
}
}
//replace with diff
for (int i=0; i<9; i++){
neighbours[i] = neighbours[4] - neighbours[i];
//System.out.println("Neighbors diff are: "+neighbours[i]);
if(neighbours[i] > threshold){
return true;
}
}
//if neighbours[4] is max
return false;
}
public static void detectEdge(int[] mat, int rowSize, int colSize, int threshold){
if(rowSize < 3 || colSize<3){
System.out.println("Matrix too small for edge detection");
}
int i,j,k;
for (i=1;i<rowSize-1;i++){
for(j=1;j<colSize-1;j++){
k = get1DIndex(i, j, rowSize, colSize);
if(isEdgePixel(mat,i,j,rowSize,colSize,threshold))
System.out.println("Coordinates: "+i+","+j+" , PixelValue: "+mat[k]);
}
}
}
public static void main(String[] args){
int mat[] = {1,2,3,4,99,6,7,8,9};
detectEdge(mat, 3, 3, 50);
}
}
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef struct {
unsigned char r, g, b, a;
}ARGB;
typedef union {
ARGB color;
unsigned raw;
}PixelType;
static_assert( sizeof(unsigned) == 4 * sizeof(unsigned char), "type size is wrong" );
static const PixelType PixelWhite { {0xFF, 0xFF, 0xFF, 0xFF} };
const unsigned img_rgba_width = 16;
const unsigned img_rgba_height = 16;
const unsigned char img_rgba[] = {
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0xcc, 0xcc, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff, 0xfd, 0x5c, 0x5c, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x72, 0x72, 0x72, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff, 0xfe, 0x43, 0x43, 0xff,
0xfe, 0x43, 0x43, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff,
0xf6, 0x40, 0x40, 0xff, 0xf6, 0x40, 0x40, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff, 0xf1, 0x3e, 0x3e, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xea, 0x3c, 0x3c, 0xff, 0xea, 0x3c, 0x3c, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xea, 0x3c, 0x3c, 0xff,
0xf9, 0x67, 0x67, 0xff, 0xea, 0x3c, 0x3c, 0xff, 0xea, 0x3c, 0x3c, 0xff,
0xea, 0x3c, 0x3c, 0xff, 0xf9, 0x67, 0x67, 0xff, 0xea, 0x3c, 0x3c, 0xff,
0xea, 0x3c, 0x3c, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe3, 0x39, 0x39, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff,
0xe3, 0x39, 0x39, 0xff, 0xe3, 0x39, 0x39, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xdb, 0x37, 0x37, 0xff,
0xff, 0xff, 0xff, 0xff, 0xdb, 0x37, 0x37, 0xff, 0xdb, 0x37, 0x37, 0xff,
0xf9, 0x67, 0x67, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xf9, 0x67, 0x67, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf9, 0x67, 0x67, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xff, 0xff, 0xff, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xd2, 0x35, 0x35, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xff, 0xff, 0xff, 0xff, 0xd2, 0x35, 0x35, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xff, 0xff, 0xff, 0xff, 0xd2, 0x35, 0x35, 0xff,
0xd2, 0x35, 0x35, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xff, 0xff, 0xff, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xf9, 0x67, 0x67, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xf9, 0x67, 0x67, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xff, 0xff, 0xff, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff,
0xcc, 0x1f, 0x36, 0xff, 0xcc, 0x1f, 0x36, 0xff, 0x75, 0x75, 0x75, 0xff,
0xcc, 0xcc, 0xcc, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff, 0x75, 0x75, 0x75, 0xff,
0x75, 0x75, 0x75, 0xff
};
unsigned getPixelIndex(unsigned row, unsigned column, unsigned width)
{
return row * width + column;
}
PixelType const*generateImage(unsigned width, unsigned height)
{
return reinterpret_cast<PixelType const*>(img_rgba);
}
unsigned getPixelDifference(const PixelType& a, const PixelType& b)
{
const auto sum1 = a.color.r + a.color.g + a.color.b;
const auto sum2 = b.color.r + b.color.g + b.color.b;
return abs(sum1 - sum2);
}
PixelType *findEdges(unsigned width, unsigned height, PixelType const* original, unsigned threashold)
{
PixelType *result = new PixelType[ width * height];
for (unsigned r = 0; r < height; ++r)
for (unsigned c = 0; c < width; ++c)
{
const auto& pt = original[getPixelIndex(r, c, width)];
unsigned diff = 0;
if (c > 0) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r, c - 1, width)]) );
if (c < width-1) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r, c + 1, width)]) );
if (r > 0) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r - 1, c, width)]) );
if (r < height-1) diff = max(diff, getPixelDifference(pt, original[getPixelIndex(r + 1, c, width)]) );
if (diff > threashold)
result[getPixelIndex(r, c, width)].raw = PixelWhite.raw;
}
return result;
}
void displayEdgeImage(unsigned width, unsigned height, PixelType const* edges, bool (*predicate)(const PixelType& pixel))
{
for (unsigned r = 0; r < height; ++r)
{
for (unsigned c = 0; c < width; ++c)
if ( predicate(edges[getPixelIndex(r, c, width)]) )
cout << "* ";
else
cout << " ";
cout << endl;
}
}
void Epic3()
{
PixelType const*original = generateImage(img_rgba_width, img_rgba_height);
const auto lambda = [](const PixelType& pixel)->bool {return pixel.color.r > 200 && pixel.color.g > 200 && pixel.color.b > 200;};
displayEdgeImage(img_rgba_width, img_rgba_height, original, lambda);
PixelType *edges = findEdges(img_rgba_width, img_rgba_height, original, 200);
displayEdgeImage(img_rgba_width, img_rgba_height, edges, lambda);
}
#if !defined(_MSC_VER)
int main()
{
Epic3();
return 0;
}
#endif
Readable and tested code for four adjacent cells. You can extend it to 8 also easily.
public class EdgeDetection {
public static int[] processEdges(int image[], int height, int width, int threshold) {
if(image == null) {
return null;
}
if(width == 1) {
return null;
}
if(image.length < width || image.length % width > 0) {
return null;
}
int n = image.length;
int left, right, top, bottom, k, value, diff;
int output[] = new int[n];
for(int row = 0; row < n; row += width) {
for(int col = row; col < row + width; col++) {
boolean exceed = false;
value = image[col];
if(col - 1 >= 0) {
left = image[col - 1];
diff = Math.abs(left - value);
if(diff >= threshold) {
exceed = true;
}
}
if(col + 1 < width) {
right =image[col + 1];
diff = Math.abs(right - value);
if(diff >= threshold) {
exceed = true;
}
}
if(col + width < n) {
bottom = image[ width + col];
diff = Math.abs(bottom - value);
if(diff >= threshold) {
exceed = true;
}
}
if(col - width >= 0) {
top = image[col - width];
diff = Math.abs(top - value);
if(diff >= threshold) {
exceed = true;
}
}
if(exceed)
output[col] = value;
}
}
return output;
}
public static void main(String args[]) {
int image[] = {1,3,4,5,2,4,6,3,5,6,7,3,8,2,12,52};
int threshold = 3;
int [] output = processEdges(image, 4, 4, threshold);
for(int i = 0; i < output.length; ++i) {
System.out.println(output[i]);
}
}
}
You have to compare maximum of all the difference with the threshold value. I think your code should be changed to as follows:
if(col - 1 >= 0) {
left = image[col - 1];
diff_left = Math.abs(left - value);
}
if(col + 1 < width) {
right =image[col + 1];
diff_right = Math.abs(right - value);
}
if(col + width < n) {
bottom = image[ width + col];
diff_bottom = Math.abs(bottom - value);
}
if(col - width >= 0) {
top = image[col - width];
diff_top = Math.abs(top - value);
}
int temp_diff = Math.max(Math.max(diff_left,diff_right),
Math.max(diff_top,diff_bottom));
if(temp_diff > threshold)
output[col] = value;
else
output[col] = 0;
}
This question is similar to question "Mountain point" (CC post id: 5165388048367616).
But this question is quite vague since:
0. How to convert a 2D image to 1D array? In row-major order or column-major order?
1. It never mentioned the exact definition of "adjacent pixels". (4 adjacent pixels? or 8?)
2. Are border points considered as edge pixels? (This is especially important when W or H is 1.)
3. Do we only consider positive difference or absolute difference? (Image a checker pattern. If absolute difference is used then all pixels are edge pixels.)
- Zortlord October 27, 2014