Finding the four corners of each quadrilateral shapes in an image
I though of using a corner detector like harris, but it gives me many additional corners (as the sides of the shapes are not really straight due to discretization.


In that case you should keep only the strongest feature points.


  the corners may actually be lost and look like a curved line as shown
  below, even though the image before segmentation had these clear 4
  corners.


In that case, you can use scale space, first blur the images excessively, then use Harris, or directly use SIFT detector and keep only the features points of the scale, that match your desired points.