access icon free Unrestricted LR detection for biomedical applications using coarse-to-fine hierarchical approach

© The Institution of Engineering and Technology
Received 15/05/2017, Accepted 13/04/2018, Revised 07/03/2018, Published 19/04/2018

In this study, the authors present a simple, reliable, fast, unrestricted-shape geometry, and accurate algorithm which runs in O(log2  n) time to find the axis-parallel largest rectangle (LR) inside a given region of interest (ROI), where n is the image size in one dimension, which means that the proposed model can work in real time. The proposed approach is successful in detecting the LR of arbitrary orientation that is fully contained in the ROI as well. Also, the present algorithm can find the largest empty rectangle in a space containing a set of zero points, whether the axis-parallel rectangle or the oriented one. The strategy followed here is to accelerate LR detection process by searching the rectangle with the largest area inscribed in the ROI, by starting first with the lowest-resolution version of the original image for determining the LR four corners’ coordinates, then next searching the new LR corners’ scaled coordinates in the higher power resolutions in a multiple resolutions hierarchical model and therefore, a corresponding coarse-to-fine inference procedure recursively eliminates the search space of the LR four corners coordinates. For finding the largest oriented rectangle, the same hierarchical procedures are followed, but combined with rotation-angle resolution.

Inspec keywords: image resolution; search problems

Other keywords: unrestricted LR detection; image pixels; coarse-to-fine hierarchical approach; biomedical applications; multiple resolutions hierarchical model; convex-hull polygon

Subjects: Optical, image and video signal processing; Optimisation techniques; Combinatorial mathematics; Computer vision and image processing techniques; Optimisation techniques; Combinatorial mathematics

References

    1. 1)
      • 5. Aggarwal, A., Suri, S.: ‘Fast algorithms for computing the largest empty rectangle’. In: Proc. Third Annual Symp. Computational Geometry, 1987, p. 12.
    2. 2)
      • 14. Studholme, C., Hill, D.L., Hawkes, D.J.: ‘An overlap invariant entropy measure of 3D medical image alignment’, Pattern Recognit., 1999, 32, p. 15.
    3. 3)
      • 15. Molano, R., Rodríguez, P.G., Caro, A., et al: ‘Finding the largest area rectangle of arbitrary orientation in a closed contour’, Appl. Math. Comput., 2012, 218, (19), pp. 9866–9874, p. 8.
    4. 4)
      • 2. Chazelle, B., Drysdale, R.L., Lee, D.T.: ‘Computing the largest empty rectangle’. STACS, Heidelberg, 1984, p. 11.
    5. 5)
      • 3. Chazelle, B., Drysdale, R.L., Lee, D.T.: ‘Computing the largest empty rectangle’, SIAM J. Comput., 1986, 15, (1), p. 16.
    6. 6)
      • 12. Gibert, G., D'Alessandro, D., Lance, F.: ‘Face detection method based on photoplethysmography’. Proc. 2013 10th IEEE Int. Conf. on Advanced Video and Signal Based Surveillance (AVSS), Krakow, Poland, August 2013, pp. 449–453.
    7. 7)
      • 7. Gutiérrez, G., Paramá, J.R.: ‘Finding the largest empty rectangle containing only a query point in large multidimensional databases’. Int. Conf. Scientific and Statistical Database Management, 2012.
    8. 8)
      • 9. Nandy, S.C., Bhattacharya, B.B., Ray, S.: ‘Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design’. Proc. Int. Conf. on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, December 1990, p. 14.
    9. 9)
      • 11. Sanches, T., Antunes, J., Correia, P.L.: ‘A single sensor hand biometric multimodal system’. Proc. 15th European Signal Processing Conf., Poznan, Poland, September 2007, pp. 30–34.
    10. 10)
      • 8. McKenna, M., O'Rourke, J., Suri, S.: ‘Finding the largest rectangle in an orthogonal polygon’. Proc. 23rd Allteron Conf. Communication, Control and Computing, Urbana-Champaign, IL, USA, 1985, p. 9.
    11. 11)
      • 6. Sarkar, A., Biswas, A., Dutt, M., et al: ‘Finding largest rectangle inside a digital object,’ Int. Workshop on Computational Topology in Image Context, Marseille, France, June 2016.
    12. 12)
      • 13. De Luca, V., Benz, T., Kondo, S., et al: ‘The 2014 liver ultrasound tracking benchmark’, Phys. Med. Biol., 2015, 60, (14), p. 5571.
    13. 13)
      • 4. Daniels, K., Milenkovic, V., Roth, D.: ‘Finding the largest area axis-parallel rectangle in a polygon’, Comput. Geom., Theory Appl., 1997, C7, p. 23.
    14. 14)
      • 10. MPEG7 CE Shape-1 Part B. Available at http://www.imageprocessingplace.com/root_files_V3/image_databases/MPEG7_CE-Shape-1_Part_B.zip, accessed October 2017.
    15. 15)
      • 1. Chang, J., Yap, C.: ‘A polynomial solution for the potato-peeling problem’, Discrete Comput. Geom., 1986, 1, (2), p. 27.
    16. 16)
      • 16. Rogers, S.K., Amburn, P., Berkey, T.S., et al: ‘Method and system for segmenting desired regions in digital mammograms’, US Patent, 6091841, 2000.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2017.0509
Loading

Related content

content/journals/10.1049/iet-ipr.2017.0509
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading